Stack Overflow

A stack overflow is the condition that occurs when a program’s call stack exceeds its allocated memory — when the orderly column of return addresses, local variables, and saved registers grows past its boundary and begins overwriting whatever lives next door. It is the computational equivalent of filling a glass past the brim, except the glass is made of memory and the liquid is function calls and the table underneath is the rest of your program.

The stack overflow is one of the oldest failure modes in computing. It predates the term “software engineering.” It predates structured programming. It predates, by some decades, the website that would name itself after it. It is the natural consequence of two facts: stacks are finite, and programmers are optimistic.

“The stack is a promise. Every CALL says ‘I will return.’ The stack overflow is what happens when too many promises are made and none are kept.”
— The Lizard, who keeps no promises that require memory allocation

The Stack

A stack is a Last-In, First-Out data structure. The last thing placed on the stack is the first thing removed. PUSH adds an item. POP removes one. This is the entire interface. It is elegant, minimal, and sufficient to track the execution flow of every program ever written.

When a function is called, the processor pushes the return address onto the stack — the location in memory where execution should resume after the function completes. The function may push additional data: saved registers, local variables, parameters for the next function call. This collection of data — return address, saved state, locals — is a stack frame. Each function call adds a frame. Each return removes one. The stack grows and shrinks with the rhythm of the program’s execution, an accordion of context.

On the Z80, the stack was not an abstraction. It was a 16-bit register called SP — the Stack Pointer — that held a memory address. PUSH decremented SP by two and wrote two bytes at the new address. POP read two bytes from the address SP held and incremented SP by two. CALL pushed the program counter onto the stack and jumped. RET popped the program counter and resumed. The stack was not managed by a runtime. The stack was not protected by an operating system. The stack was a register pointing at memory, and the programmer was responsible for everything.

“A stack frame is just a promise with a return address. Recursion is making the same promise over and over. A stack overflow is bankruptcy.”
— The Caffeinated Squirrel, who once wrote a recursive Fibonacci and crashed a machine with 32GB of RAM

The Overflow

A stack overflow occurs when the stack grows beyond its allocated space. In modern systems, the operating system assigns a fixed stack size — typically one to eight megabytes — and places a guard page at the boundary. When the stack pointer crosses the guard page, the OS delivers a signal (SIGSEGV on Unix, STATUS_STACK_OVERFLOW on Windows), and the process terminates with the quiet dignity of a segmentation fault.

On the Z80, there was no guard page. There was no operating system. There was no allocated stack region. The stack pointer was a register that pointed at memory, and if the stack grew past the area the programmer intended, it overwrote whatever was there — program code, display memory, system variables, the interrupt vector table. The machine did not crash with a helpful error message. The machine crashed with visual corruption, unexpected behaviour, or a hard lock that required a power cycle.

The most common cause of stack overflow, in every era, is recursion without a base case:

function collapse(n):
    return collapse(n)    // no base case, no termination, no survivors

Each recursive call adds a stack frame. Without a base case to stop the recursion, frames accumulate until the stack is exhausted. The function does not compute a result. The function computes a crash. The depth at which the crash occurs depends on the stack size and the frame size, but the crash itself is certain — as certain as any mathematical proof, and considerably more dramatic.

The Stack as Paintbrush

On the Z80, the stack pointer was just a register. It was meant to point at the stack. It could point anywhere.

riclib pointed it at the screen.

The ZX Spectrum’s display file occupied memory from address 16384 to 22527 — 6,144 bytes of pixel data. To clear the screen, the naive approach used LDIR, the block copy instruction, at 21 T-states per iteration. The fast approach — the approach that separated the Z80 programmer from the Z80 user — was to save the real stack pointer, disable interrupts, point SP at the end of the display file, load HL with zero, and execute PUSH HL 3,072 times. Each PUSH wrote two zero bytes to the screen and decremented SP. The screen cleared at 11 T-states per two bytes instead of 21 — nearly four times faster.

This was, technically, a deliberate stack overflow. The stack pointer was aimed at memory that was not the stack, and PUSH operations wrote data past any sane boundary of what a stack should contain. The Z80 did not object. The Z80 had no opinion about what constituted a stack. The Z80 executed PUSH: write two bytes, decrement SP. Where SP pointed was the programmer’s problem.

But there was a price. While SP pointed at the display file, the real stack did not exist. If a maskable interrupt fired during the screen clear, the Z80’s interrupt handler would push the program counter onto “the stack” — which was now the middle of the screen. The return address would appear as two corrupted pixels. The interrupt handler would execute, attempt to return, and pop whatever happened to be in the display file as a return address. The program counter would jump to an address determined by the pixel pattern at that screen location. The machine would crash — not with an error, but with the particular aesthetic violence of a Z80 executing screen data as code.

The solution: DI before, EI after. Disable Interrupts. Enable Interrupts. Two instructions, two bytes, the difference between a technique and a catastrophe. This was the discipline of low-level programming: you could use the stack as a paintbrush, but you had to turn off the interrupts first, because the price of using the stack for something other than the stack was that nothing else could use the stack either.

“DI/EI. The two most important instructions in any screen clear. Not because of what they do, but because of what happens when you forget them.”
— The Lizard, who has never forgotten a DI in four decades

Recursion and Its Consequences

Recursion is the technique of a function calling itself to solve progressively smaller instances of a problem. It is mathematically elegant, pedagogically beloved, and a reliable mechanism for producing stack overflows in production systems.

The canonical example is factorial:

factorial(n):
    if n <= 1: return 1       // base case — the thing that prevents the crash
    return n * factorial(n-1)  // recursive case — the thing that causes the crash if the above line is missing

Each call to factorial adds a stack frame. For factorial(5), the stack grows five frames deep and unwinds cleanly. For factorial(100000), the stack grows one hundred thousand frames deep and — on most systems, with most default stack sizes — does not unwind at all.

Some languages offer tail-call optimisation, which converts certain recursive calls into loops, reusing the current stack frame instead of allocating a new one. Scheme guarantees it. Haskell provides it. Most other languages mention it in conference talks and do not implement it, leaving the programmer to discover the stack limit experimentally, which is the traditional method.

“Tail-call optimisation is the compiler saying ‘I see what you’re trying to do and I’m going to fix it for you.’ Most compilers do not say this. Most compilers watch you fall.”
— A Passing AI, who has no stack but understands the concept of running out of context

The Website

In 2008, Joel Spolsky and Jeff Atwood launched a question-and-answer website for programmers and named it after a crash condition. This was either an act of knowing irony or an accurate prediction of what would happen to the site’s architecture at scale.

Stack Overflow the website became the largest repository of programming knowledge on the internet — a place where every error message, every obscure API behaviour, every “how do I center a div” question was answered, debated, duplicated, closed as duplicate, reopened, re-closed, and eventually indexed by Google. It is the site that taught more programmers to program than every university combined, which is either a testament to the power of community knowledge or an indictment of computer science education, depending on who you ask and whether they have tenure.

The naming choice was apt in ways the founders may not have intended. A stack overflow occurs when a system accumulates too many unresolved contexts. Stack Overflow the website accumulates questions faster than they can be answered, answers faster than they can be verified, and opinions faster than they can be moderated. The stack of human knowledge grows without a base case. The recursion has no termination condition. The only thing preventing the overflow is the moderators, who function as the DI instruction — disabling interrupts long enough for the system to remain coherent.

Measured Characteristics

Phenomenon:                         stack overflow
Cause:                              stack growth exceeding allocated memory
Most common trigger:                recursion without a base case
Second most common trigger:         deeply nested function calls
Z80 stack implementation:           SP register, no protection, no limits
Z80 stack overflow consequence:     creative machine death
Modern stack overflow consequence:  segmentation fault (less creative)
Default stack size (Linux):         8 MB
Default stack size (Z80 Spectrum):  whatever memory you didn't use for anything else
DI instruction:                     the price of using the stack as a paintbrush
EI instruction:                     the return to civilisation
PUSH HL T-states:                   11
LDIR T-states per iteration:        21
Speed advantage of stack abuse:     3.8x
Website named after it:             stackoverflow.com (2008-present)
Website's relationship to concept:  nominative determinism
Recursive definition:               see Stack Overflow

See Also

• Z80 Assembly — Where the stack pointer was just a register, and you could point it at the screen, and the machine would let you.
• O Notation — The mathematics of growth rates. A stack overflow is what happens when growth is O(n) and memory is O(1).
• ZX Spectrum — The machine where the screen clear trick was invented, tested, and crashed dozens of times before DI was remembered.
• riclib — The entity who caused stack overflows deliberately, as a screen-clearing technique, on hardware with no memory protection. The Lizard approved.