CODEWITHSUNDEEP
c++crash
StoneThrow
StoneThrow

Reputation: 6275

Why does this program terminate with "unknown signal"?

The following code is meant to output combinations of size 1, 2, ..., N, given an input set of size N.

#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <exception>

template< typename V >
class Item
{
public:

  Item( const std::string& description,
        const V& value )
    : description_( description )
    , value_( value )
  {
  }

  std::string description() const { return description_; }

  V value() const { return value_; }

private:

  std::string description_;
  V value_;

friend std::ostream& operator<<( std::ostream& os, const Item& item )
{
  os << "{ \"" << item.description_ << "\", " << item.value_ << " }";
  return os;
}
};

template < typename T >
void addCombinationsN( const std::deque<T>& values,
                       std::deque<T>& interimResults,
                       size_t valuesStartIdx,
                       size_t n,
                       std::deque< std::deque<T> >& results )
{
  if ( valuesStartIdx >= values.size() ) { return; }
  if ( interimResults.size() >= n ) { return; }

  for ( int valuesIdx = valuesStartIdx;
        valuesIdx < values.size();
        ++valuesIdx )
  {
    interimResults.push_back( values[valuesIdx] );
    addCombinationsN( values, interimResults, valuesIdx+1, n, results );

    if ( interimResults.size() == n )
    {
      results.push_back( interimResults );
    }
    interimResults.pop_back();
  }
}

template < typename T >
std::deque< std::deque<T> > nChoose( const std::deque<T>& values )
{
  std::deque< std::deque<T> > retVal;
  std::deque<T> interimResults;

  std::cout << "adding all combinations from " << values.size() << " choices" << std::endl;

  for ( size_t n = 1; n <= values.size(); ++n )
  {
    std::cout << "# choices: " << n << std::endl;
    addCombinationsN < T > ( values, interimResults, 0, n, retVal );
  }
  std::cout << "done adding all choices" << std::endl;

  return retVal;
}

template< typename V >
class ItemDecCmp
{
public:
  bool operator()( std::deque< Item< V > >& a,
                   std::deque< Item< V > >& b ) const
  {
    return a.size() > b.size();
  }
};

template< typename V >
void populateChoices( std::deque< Item< V > >& items )
{
  for ( int i = 0; i < 28; ++i )
  {
    items.push_back( Item< V >( std::string( 1, '0' + i ), V(i) ) );
  }
}

int main( int argc, char* argv[] )
{
  std::deque< Item< double > > items;
  populateChoices<double>( items );

  std::deque< std::deque< Item< double > > > nChoices;
  nChoices = nChoose< Item< double > >( items );

  std::sort( nChoices.begin(), nChoices.end(), ItemDecCmp< double >() );
  std::cout << "done" << std::endl;

  for ( std::deque< std::deque< Item< double > > >::iterator i = nChoices.begin();
        i != nChoices.end();
        ++i )
  {
    for ( std::deque< Item< double > >::iterator j = i->begin();
          j != i->end();
          ++j )
    {
      std::cout << *j << " ";
    }
    std::cout << std::endl;
  }

  return 0;
}

The code produces expected results for input (i.e. the result of calling populateChoices()) containers with slightly under 30 elements. However it terminates prematurely without segfault with input containers with more elements.

Example output with input of 3 elements:

$ g++ -g main.cpp && ./a.exe
adding all combinations from 3 choices
# choices: 1
# choices: 2
# choices: 3
done adding all choices
done
{ "0", 0 } { "1", 1 } { "2", 2 }
{ "0", 0 } { "1", 1 }
{ "0", 0 } { "2", 2 }
{ "1", 1 } { "2", 2 }
{ "0", 0 }
{ "1", 1 }
{ "2", 2 }

Example output with input of 28 elements:

$ g++ -g main.cpp && ./a.exe
adding all combinations from 28 choices
# choices: 1
# choices: 2
# choices: 3
# choices: 4
# choices: 5
# choices: 6
# choices: 7
# choices: 8
# choices: 9
# choices: 10
# choices: 11

What I have tried to fix the problem:

1) I suspected I may be encountering stack overflow (no pun intended) because of the recursive algorithm. However, increasing the stack size did not change the described behavior. 

$ ulimit -a
core file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
open files                      (-n) 256
pipe size            (512 bytes, -p) 8
stack size              (kbytes, -s) 2032
cpu time               (seconds, -t) unlimited
max user processes              (-u) 256
virtual memory          (kbytes, -v) unlimited
$
$ ulimit -s 65536
$ ulimit -a
core file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
open files                      (-n) 256
pipe size            (512 bytes, -p) 8
stack size              (kbytes, -s) 65536
cpu time               (seconds, -t) unlimited
max user processes              (-u) 256
virtual memory          (kbytes, -v) unlimited
$

2) This code originally used std::vector instead of std::deque; I suspected my problem may have to do with the on-demand reallocation std::vector does under-the-hood. I switched the container to std::deque on the understanding that push_backs and pop_backs don't incur reallocation (this Q&A, among other reading), but this also did not result in any change in runtime behavior.

3) I ran the executable through gdb but can't tell what its stack trace is telling me:

(gdb) r
Starting program: /path/to/code/a.exe
[New Thread 11212.0x1884]
[New Thread 11212.0x18cc]
adding all combinations from 28 choices
# choices: 1
# choices: 2
# choices: 3
# choices: 4
# choices: 5
# choices: 6
[New Thread 11212.0x1eb4]
# choices: 7
# choices: 8
# choices: 9
# choices: 10
[New Thread 11212.0x2a5c]
[New Thread 11212.0xfa0]
# choices: 11
gdb: unknown target exception 0x20474343 at 0x7ffccb2754d8

Thread 1 "a" received signal ?, Unknown signal.
0x00007ffccb2754d8 in RaiseException () from /cygdrive/c/WINDOWS/System32/KERNELBASE.dll
(gdb) bt
#0  0x00007ffccb2754d8 in RaiseException () from /cygdrive/c/WINDOWS/System32/KERNELBASE.dll
#1  0x00000003e8ddcbf1 in cyggcc_s-seh-1!_Unwind_RaiseException () from /usr/bin/cyggcc_s-seh-1.dll
#2  0x00000003e8ddccc0 in cyggcc_s-seh-1!_Unwind_Resume_or_Rethrow () from /usr/bin/cyggcc_s-seh-1.dll
#3  0x00000003d0c57fcd in cygstdc++-6!.cxa_rethrow () from /usr/bin/cygstdc++-6.dll
#4  0x0000000100402ef7 in std::_Deque_base<Item<double>, std::allocator<Item<double> > >::_M_initialize_map (this=0x6fff5d6f7a0,
    __num_elements=11) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:707
#5  0x000000010040307a in std::_Deque_base<Item<double>, std::allocator<Item<double> > >::_Deque_base (this=0x6fff5d6f7a0, __a=...,
    __num_elements=11) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:500
#6  0x0000000100405209 in std::deque<Item<double>, std::allocator<Item<double> > >::deque (this=0x6fff5d6f7a0, __x=...)
    at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:949
#7  0x000000010040213f in __gnu_cxx::new_allocator<std::deque<Item<double>, std::allocator<Item<double> > > >::construct<std::deque<Item<double>, std::allocator<Item<double> > >, std::deque<Item<double>, std::allocator<Item<double> > > const&> (this=0xffffcb20,
    __p=0x6fff5d6f7a0, __args#0=...) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/ext/new_allocator.h:136
#8  0x0000000100404506 in std::allocator_traits<std::allocator<std::deque<Item<double>, std::allocator<Item<double> > > > >::construct<std::deque<Item<double>, std::allocator<Item<double> > >, std::deque<Item<double>, std::allocator<Item<double> > > const&> (__a=...,
    __p=0x6fff5d6f7a0, __args#0=...) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/alloc_traits.h:475
#9  0x0000000100405b04 in std::deque<std::deque<Item<double>, std::allocator<Item<double> > >, std::allocator<std::deque<Item<double>, std::allocator<Item<double> > > > >::push_back (this=0xffffcb20, __x=...)
    at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:1547
#10 0x0000000100401b08 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=20, n=11, results=...)
    at main.cpp:58
#11 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=17, n=11, results=...)
    at main.cpp:54
#12 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=15, n=11, results=...)
    at main.cpp:54
#13 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=12, n=11, results=...)
    at main.cpp:54
#14 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=10, n=11, results=...)
    at main.cpp:54
#15 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=9, n=11, results=...)
    at main.cpp:54
#16 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=6, n=11, results=...)
    at main.cpp:54
#17 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=5, n=11, results=...)
    at main.cpp:54
#18 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=4, n=11, results=...)
    at main.cpp:54
#19 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=2, n=11, results=...)
    at main.cpp:54
#20 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=0, n=11, results=...)
    at main.cpp:54
#21 0x0000000100401c1f in nChoose<Item<double> > (values=...) at main.cpp:75
#22 0x00000001004010d7 in main (argc=1, argv=0xffffcc20) at main.cpp:108

Question:

Can someone help identify what is causing this program to crash and why it manifests as just premature termination and not an identifiable signal, e.g. SEGV?

Secondary but related questions: why does gdb identify multiple threads being created - this is a single-threaded application. I also don't know what to make of the "unknown target exception."

Environment

The dev environment is cygwin on a Windows 10 64-bit Intel PC:

$ uname -a
CYGWIN_NT-10.0 My-PC 2.11.2(0.329/5/3) 2018-11-08 14:34 x86_64 Cygwin

PS - I'm sorry to ask a "help me debug" question, but in this case because I don't know what to make of what gdb is telling me, I've truly hit a mental roadblock on how to identify what specifically is wrong. I asked on Meta whether this question best fit here on on another Stack Exchange site, and opinion was split between here and Code Review.

Upvotes: 2

Views: 8616

Answers (1)

user10605163
user10605163

Reputation:

According to the stack trace the exception is thrown inside the call

results.push_back( interimResults );

and is most likely an exception of type std::bad_alloc indicating that memory for a new element for the std::deque could not be allocated, probably because not enough memory is available anymore.

Because interimResults is always pop_backed from again quickly, its size will not be really big. However results will grow very big and will consume all of the available memory.

You simply cannot store that much data. You need to release what you don't need.

Upvotes: 3

Related Questions