Part 4 of 7 · 2 min read
Stack overflow
In plain words: A stack overflow happens when the stack passes its limit. The usual causes are a recursion that is too deep (or never ends), and a big local array. The effect is a segmentation fault.
How deep can a recursion go? The depth is the stack limit divided by the frame size. The test function has a local array of 100 bytes and other data, and the measured frame is about 144 bytes. The program catches SIGSEGV on a separate stack and prints the depth reached:
| Stack limit | Depth reached | Bytes per call |
|---|---|---|
1 MiB (ulimit -s 1024) |
7,086 | about 148 |
| 8 MiB (default) | 58,050 | about 144.5 |
| 16 MiB | 116,310 | about 144.2 |
The depth is in proportion to the limit, as it should be. (The 1 MiB figure is slightly off because the program's start-up data, such as the environment strings, uses a part of the stack.) A recursion of 100,000 levels, which is fine for a language that grows its stack, crashes a C program with a default stack.
A big local array does the same in one step. The three functions below each use 16 MiB with memset:
| Where the 16 MiB lives | Result |
|---|---|
Local array: char a[16 << 20] |
segmentation fault (exit code 139) |
static array, in the data segment |
works |
malloc(16 << 20) on the heap |
works |
The fix is the rule of thumb for C: keep big or unbounded data off the stack. Use the heap (page 1) for large arrays, and replace a deep recursion by a loop with an explicit stack or counter. Raising the limit with ulimit -s helps only when the depth is bounded and known.
Stack overflow
A stack overflow is the failure that occurs when a process needs more stack than its limit allows, usually through a recursion that is too deep or a large local array, and that the kernel reports by sending the process SIGSEGV.
Example: with an 8 MiB limit, a function that allocates 16 MiB of local array crashes at its first call.
Common mistake
A "segmentation fault" does not always mean a bad pointer. A program that crashes at its first call of a function with a big local array, or deep in a recursion, has overflowed the stack. gdb shows a backtrace thousands of frames long, and that is the sign.
Check yourself:
1. What decides the depth of a recursion before the crash?
2. Why does the 16 MiB static array work, and the local array not?
3. Name two ways to fix a stack overflow.