How does the code handle a stack overflow? Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. Can you point me to some code?
Try it, just write a tiny function that calls itself and has a local variable (make sure to use the variable after the function call so it's not optimized away).
Something like:
int recurse(int foo) {
int bar;
printf("%d\n", foo);
bar = recurse(foo + 1);
printf("%d\n", bar); //this is just to avoid bar being optimized away
return bar;
}
By me it seg-faults after 174,594 calls. Presumably that has to do with the size of the stack and the memory allocated for the function.
It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over.
In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls.
If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
> you have to anticipate and handle a stack overflow cleanly. How do you do this?
You use sigaltstack and catch SIGSEGV.
It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
> Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling.
On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies.
Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page.
Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault.
So in absence of extra precaution, using heap memory isn't any safer than using stack memory.
It's typically handled by ignoring the issue and bumping up the maximum stack size if it becomes a problem. For example, I once wrote a Java indexer that simply failed on very long chains of function calls.
