CSE Roadmap

Core tier · about 4 hours · 7 parts

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.