Run-Time Storage Organization

Run-time storage organization. At run time the executing target program's memory is partitioned into separate areas, each holding a different category of data — the generated instructions, fixed global/static data, dynamically allocated objects, and the per-call working storage for active procedures.

The compiler does not place every datum at a fixed address. Instead it decides which area each kind of value belongs to and computes relative offsets within that area; the actual base addresses are fixed only when the program is loaded and run.

The two interesting areas grow dynamically as the program runs: the stack holds storage for procedure calls (it shrinks and grows with the call/return pattern), and the heap holds data whose lifetime is not tied to any single call.

A typical run-time memory image is laid out as four areas. We use the convention that lower addresses are at the top and addresses increase downward.

What lives in each area:

• Code (text) — the generated machine instructions. Its size is fixed at compile/link time.
• Static — global variables and static data. Their sizes and addresses are known at compile time, so they get a fixed spot.
• Heap — data allocated explicitly at run time (malloc, new) whose lifetime is not tied to a procedure call. Here it grows downward toward higher addresses.
• Stack — one activation record per active procedure call. Here it grows upward toward lower addresses.

The heap and the stack grow toward each other into the shared free gap between them. This lets either area expand as needed; the program runs out of memory only when the two ends meet.

Activation record (stack frame). The contiguous block of storage allocated for one activation of a procedure — that is, one call. Each call gets its own activation record; it is pushed on entry and popped on return.

Its fields, top to bottom in a common layout:

Each field in one line:

• returned value — where this call leaves its result for the caller to read.
• actual parameters — the argument values the caller placed here for this call.
• control link — points to the caller's activation record (used to pop back on return).
• access link / saved machine status — the return address to resume the caller, plus saved registers (and, in nested-scope languages, an access link to a non-local frame).
• local data — storage for the procedure's local variables.
• temporaries — slots for intermediate values the generated code needs while evaluating expressions.

Take the running program:

Each call to fib builds an activation record. fib has one parameter n, no locals, and needs temporaries to hold the two recursive results before adding them:

Why several records coexist. Because fib is recursive, evaluating fib(n - 1) happens before fib(n - 2) returns to do its add — so multiple fib activations are alive on the stack at the same time, each with its own n. This is the control stack: the chain of currently active calls, growing on each call and shrinking on each return.

Three separate fib records, three separate values of n (3, 2, 1), each with its own control link back to the caller. As each call returns, its record is popped and control follows the control link back to the waiting caller.

• Run-time memory is partitioned by data category: code, static, heap, stack.
• Code and static are fixed size (known at compile time); heap and stack grow dynamically.
• With lower addresses on top, the heap grows downward and the stack grows upward, toward each other into the shared free gap.
• An activation record is the storage for one call: returned value, parameters, control link, return address + saved registers, locals, and temporaries.
• The control link points to the caller's record, threading the active calls into the control stack.
• A recursive procedure like fib keeps many activation records alive at once, each with its own copy of the parameters and temporaries.