std::map causes "stack overflow" under low memory situation

Question

This application is being developed in VS2010 on Windows XP in C++.

When computer was running very low on physical memory (and paging file was disabled as it was our test case), this line of the code:

std::map<UINT, std::vector<void *>> MyMap;

caused "stack overflow" error in malloc.c

'return HeapAlloc(_crtheap, 0, size ? size : 1);'

Unhandled exception at 0x7c90e8e5 in MyApp.exe: 0xC00000FD: Stack overflow.

This call was made from one of threads of the application. If memory low was error, it should have thrown bad_alloc

Can someone please advice what could be reason here.

EDIT:

This is how actual stack looks like

ntdll.dll!7c90e8e5()    

[Frames below may be incorrect and/or missing, no symbols loaded for ntdll.dll] 

ntdll.dll!7c9100d3()    

MyApp.exe!_heap_alloc_base(unsigned int size=72)  Line 55   C

MyApp.exe!_heap_alloc_dbg_impl(unsigned int nSize=36, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0af3f0e4)  Line 431 + 0x9 bytes   C++

MyApp.exe!_nh_malloc_dbg_impl(unsigned int nSize=36, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0, int * errno_tmp=0x0af3f0e4)  Line 239 + 0x19 bytes C++

MyApp.exe!_nh_malloc_dbg(unsigned int nSize=36, int nhFlag=0, int nBlockUse=1, const char * szFileName=0x00000000, int nLine=0)  Line 302 + 0x1d bytes  C++

MyApp.exe!malloc(unsigned int nSize=36)  Line 56 + 0x15 bytes   C++

MyApp.exe!operator new(unsigned int size=36)  Line 59 + 0x9 bytes   C++

MyApp.exe!std::_Allocate<std::_Tree_nod<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >::_Node>(unsigned int _Count=1, std::_Tree_nod<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >::_Node * __formal=0x00000000)  Line 36 + 0x15 bytes C++

MyApp.exe!std::allocator<std::_Tree_nod<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >::_Node>::allocate(unsigned int _Count=1)  Line 187 + 0xb bytes C++

MyApp.exe!std::_Tree_val<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >::_Tree_val<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >(const std::less<unsigned int> & _Parg=less, std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > > _Al={...})  Line 544 + 0xd bytes C++

MyApp.exe!std::_Tree<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >::_Tree<std::_Tmap_traits<unsigned int,std::vector<void *,std::allocator<void *> >,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > >,0> >(const std::less<unsigned int> & _Parg=less, const std::allocator<std::pair<unsigned int const ,std::vector<void *,std::allocator<void *> > > > & _Al={...})  Line 699 C++

Answer 1

  #define STACKSIZE (1024*896)

That's certainly a problem, the main thread of your program is teetering on the edge of tripping the page guard exception that initiates the stack overflow exception. HeapAlloc() will fail for two basic reasons on Windows. The common one you've been assuming so far, running out of address space is the normal failure mode.

But Windows also provides a strong guarantee that any virtual memory allocation can always be mapped to RAM. It doesn't have anything similar to an "out of memory killer" that random aborts processes when memory is over-committed and no RAM is available to fix a page fault. An allocation is always committed with a guarantee that the RAM page can be either discarded or swapped to disk. If you run Windows without a paging file then that guarantee does get to be hard to provide. The commit failing is an obvious possibility.

What happens next is hard to guess at, your stack trace doesn't give any hints. Be sure to configure the symbol server so you get symbols for ntdll.dll. But clearly, HeapAlloc() will follow a different path than it normally does when the commit fails. I'd guess at some kind of debugger probe, no idea really. With a deeper nesting, requiring more stack space. Which would be enough to trip the stack guard page and trigger the stackoverflow exception.

Not so sure if fixing this problem really matters, your program is dead either way. Recovering from commit failure is almost impossible. It is completely random, affected by VM allocations in other processes. Running without a page file requires lots of RAM and very careful control over what processes are allowed to run on the machine. RAM is a wholeheckofalot cheaper than anything you could possibly do in software.

Answer 2

I realized this is not an issue specific to std::map really. When memory is low and no paging file exists, a simple application also can cause stack overflow. This is because Windows reserves certain amount of memory per thread for stack. However, it not necessarily will be able to commit the memory. In that case "stack overflow" happens.

#include <stdio.h>
#include <conio.h>

#define STACKSIZE (1024*896)

void FunctionWithBigStack()
{
    char stack[STACKSIZE];
    printf("\nAllocated %d KB stack successfully", STACKSIZE/1024);
    stack[STACKSIZE-1] = 123; // Let's use 'stack' array so that optimizer won't discard it while compiling
}

int _tmain(int argc, _TCHAR* argv[])
{
    printf("\nThrough another application, try make all the memory full and then press a key to call a function that has %d KB stack", STACKSIZE/1024);
    _getch();
    FunctionWithBigStack();
    return 0;
}

This application runs perfect under normal memory conditions but if we make memory full while it is waiting for keystroke, we can see FunctionWithBigStack crashes with "stack overflow"

Answer 3

Low memory does not mean bad_alloc always. Call stack also consumes memory. If the system is unable to create new stack for another function call or limit of number of callstack is achieved, it will give stack overflow error.

I think HeapAlloc is part of CRT (basically C function call). new operator throws bad_alloc, not HeapAlloc.