Why does this program terminate with "unknown signal"?

Question

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.

@user4581301 - you mean heap use? Either way, how do I do so? `top` seems unavailable in cygwin. — StoneThrow, Jan 01 '19 at 06:24
Read [how to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Consider using some [Linux distribution](https://en.wikipedia.org/wiki/Linux_distribution), since Linux is very developer friendly and has [valgrind](http://valgrind.org/) which will help you to find your memory corruption bug — Basile Starynkevitch, Jan 01 '19 at 06:24
Yes this looks like a `bad_alloc` exception and my system produces it as well. Your program uses many GB after about `# choices: 12` on my system. — , Jan 01 '19 at 06:27
Top is out of the question, but [Process Explorer](https://learn.microsoft.com/en-us/sysinternals/downloads/process-explorer) should give you a hand on Windows. — user4581301, Jan 01 '19 at 06:28
@user10605163 - is `bad_alloc` exception roughly synonymous with a failure to allocate memory on the heap? — StoneThrow, Jan 01 '19 at 06:29
It means dynamic memory could not be allocated, yes. In this case thrown by `deque::push_back`, meaning that memory for the new element could not be allocated. You simply cannot store that much stuff in your containers. Get rid of what you don't need anymore. — , Jan 01 '19 at 06:31
`addCombinationsN` does a hell of a lot of recursive adding. For fun, place `std::cout << values.size() << ',' << interimResults.size() << ',' < — user4581301, Jan 01 '19 at 06:33

score 3 · Accepted Answer · 2019-01-01T06:49:17.490

3

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.

edited Jan 01 '19 at 06:49

answered Jan 01 '19 at 06:42

On reflection, the high memory consumption makes sense: given N choices, and the need to find all combinations of size 1, 2, ..., N, the total number of those combinations is (2^N) - 1, which is huge when talking about the input sizes of ~ 30 elements. – StoneThrow Jan 01 '19 at 06:57

Why does this program terminate with "unknown signal"?

1 Answers1