When you call a friend, put them on hold to take a second call, and then on hold again for a third, you have to remember who is waiting and what you were talking about with each of them. When the third call ends you return to the second, and when that ends, to the first. The most recent call always finishes first.
Function calls in a program behave exactly like this. While main waits for f, and f waits for g, each of them has its own parameters, local variables and "where was I?" information that must be kept safe. The compiler cannot just generate instructions for the function bodies; it must also decide where all this information lives while the program runs and generate the code that sets it up and tears it down. That organisation is the runtime environment.
The runtime environment is the set of conventions and data structures, set up by the compiler together with the operating system and runtime library, that manage memory while a program executes: the layout of code and data, the allocation of storage for each procedure call, the passing of parameters and return values, and access to non-local names.
In this chapter we look at how a program's memory is laid out, what an activation and an activation tree are, what goes inside an activation record, who does what in a calling sequence, and how a procedure reaches variables that are not its own (static vs dynamic scope, access links and displays). The C examples were compiled with GCC 15.2 on x86-64 Linux and the outputs shown are real; the access-link and display tables were produced by a small simulator.
How a Program's Memory Is Organised
When the operating system loads a program, it gives it a range of (virtual) addresses. The compiler and runtime divide that range into areas, each managed differently:
high addresses
+---------------------------+
| Stack | activation records; grows DOWN
| | |
| v |
| |
| (free) |
| |
| ^ |
| | |
| Heap | malloc / new; grows UP
+---------------------------+
| Static data (.data/.bss) | globals, static locals; size fixed at compile time
+---------------------------+
| Code (.text) | machine instructions; fixed size, usually read-only
+---------------------------+
low addressesCode: its size is known after compilation, so it is placed in a fixed area.
Static data: global variables and
staticlocals. Their size is known at compile time too, so their addresses can be fixed (relative to the start of the area) by the compiler. Initialised data goes in.data; zero-initialised data in.bss.Stack: holds one activation record per currently active call. It grows and shrinks as functions are called and return.
Heap: holds data whose lifetime is not tied to any call, created by
mallocornewand freed explicitly or by a garbage collector.
The stack and heap are placed at opposite ends of the free space so that each can grow without the compiler fixing a limit between them. This small C program prints one address from each area:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int g_init = 5; /* initialized data */
int g_zero; /* bss */
void depth(int n) {
int local = n;
printf("depth(%d): &local = %p\n", n, (void *)&local);
if (n < 3) depth(n + 1);
}
int main(void) {
static int s = 1;
int *h = malloc(sizeof *h);
printf("code : main = %p\n", (void *)(uintptr_t)main);
printf("data : &g_init = %p\n", (void *)&g_init);
printf("data : &s = %p\n", (void *)&s);
printf("bss : &g_zero = %p\n", (void *)&g_zero);
printf("heap : h = %p\n", (void *)h);
depth(1);
free(h);
return 0;
}code : main = 0x401201
data : &g_init = 0x404030
data : &s = 0x404034
bss : &g_zero = 0x40403c
heap : h = 0x229ef010
depth(1): &local = 0x7ffcbb953524
depth(2): &local = 0x7ffcbb9534f4
depth(3): &local = 0x7ffcbb9534c4(Compiled with gcc -std=c17 -Wall -no-pie; heap and stack addresses change from run to run because of address-space layout randomisation, but the ordering does not.) Code is lowest, then static data, then the heap, and the stack is far up near the top. Each deeper call to depth gets its local at a lower address, 0x30 = 48 bytes below the previous one: every call pushed a new 48-byte activation record and the stack grew downward.
Procedures, Activations and Lifetimes
A procedure (function, method) is a piece of program text. An activation is one execution of it. A recursive function has one procedure but may have many activations alive at the same time, each with its own copies of parameters and locals.
The lifetime of an activation is the time from its call to its return. For ordinary sequential programs (no threads, no exceptions escaping, no coroutines), lifetimes are properly nested: if p calls q, then q's activation ends before p's does. That nesting is the reason a stack is the right data structure for activations.
Activation Trees
An activation tree shows the activations during one run of a program: each node is an activation, the root is the activation of main, and the children of a node are the activations it calls, ordered left to right in the order they are called.
Take the naive Fibonacci function:
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}The activation tree for fib(4):
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)Properties worth remembering:
The sequence of calls is a preorder traversal of the tree: fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0).
The sequence of returns is a postorder traversal.
At any moment, the activations that are alive are exactly those on the path from the root to the current node. When fib(0) at the bottom left is running, the live activations are fib(4), fib(3), fib(2), fib(0).
The tree has 9 nodes, so fib(4) causes 9 activations, but the stack never holds more than 4 fib records at once (the number of levels in the tree). In general naive fib(n) makes 2·F(n+1) − 1 calls (9 for n = 4, 177 for n = 10) yet needs stack depth only n (for n ≥ 1). This difference between "total activations" and "maximum stack depth" is a favourite exam question.
The Control Stack
The control stack (or call stack) holds an activation record for each live activation. A call pushes a record; a return pops it. The contents of the stack at any moment correspond to the root-to-current path in the activation tree.
While the leftmost fib(0) runs:
+-----------+ <- top (lowest address)
| fib(0) |
+-----------+
| fib(2) |
+-----------+
| fib(3) |
+-----------+
| fib(4) |
+-----------+
| main |
+-----------+ <- bottomThe Activation Record
An activation record (also called a stack frame) is the block of memory that holds all the information needed by one activation of a procedure.
A general activation record contains the following fields. Real compilers drop or merge some of them, and their order depends on the target machine, but this is the standard textbook picture:
+------------------------------+
| Actual parameters | values (or addresses) supplied by the caller
+------------------------------+
| Returned value | space for the result (often a register instead)
+------------------------------+
| Control link | points to the CALLER's activation record
+------------------------------+
| Access link | points to the record of the enclosing scope
+------------------------------+
| Saved machine status | return address, saved registers
+------------------------------+
| Local data | the procedure's local variables
+------------------------------+
| Temporaries | compiler temporaries, spilled values
+------------------------------+Field | Why it is needed |
|---|---|
Actual parameters | The callee needs its arguments. In practice the first few are passed in registers (6 integer registers on x86-64 Linux). |
Returned value | The caller needs the result. Also usually a register ( |
Control link (dynamic link) | To restore the caller's frame pointer on return. Following control links walks the call chain, which is what a debugger's backtrace does. |
Access link (static link) | Only in languages with nested procedures: to reach variables of lexically enclosing procedures. C does not need it. |
Saved machine status | The return address (where to continue in the caller) and registers that must be preserved across the call. |
Local data | Each activation needs its own copy; this is what makes recursion work. |
Temporaries | Values of expressions that do not fit in registers. |
Why Is the Record Laid Out This Way?
The fields that the caller and callee must agree on (parameters, return value) are placed at the boundary between the two records, near the caller's end, so the caller can fill them in without knowing anything about the callee's locals. Fixed-size fields (links, machine status) are in the middle, so they are at a known offset from the frame pointer. Locals and temporaries, whose sizes only the callee knows, are at the far end. A frame pointer register (rbp on x86-64) points to a fixed place in the record, and every local is accessed at a constant offset from it.
Here is GCC's real code for a small function (gcc -O0 -S -masm=intel, assembler directives removed):
int add3(int a, int b, int c) {
int s = a + b;
s = s + c;
return s;
}
int main(void) { return add3(1, 2, 3); }add3:
endbr64 ; CET landing pad (Ubuntu's GCC adds it by default)
push rbp ; save caller's frame pointer (control link)
mov rbp, rsp ; set up our own frame pointer
mov DWORD PTR -20[rbp], edi ; a (parameters arrived in registers,
mov DWORD PTR -24[rbp], esi ; b stored into the frame at -O0)
mov DWORD PTR -28[rbp], edx ; c
mov edx, DWORD PTR -20[rbp]
mov eax, DWORD PTR -24[rbp]
add eax, edx
mov DWORD PTR -4[rbp], eax ; s is the local at offset -4
mov eax, DWORD PTR -28[rbp]
add DWORD PTR -4[rbp], eax
mov eax, DWORD PTR -4[rbp] ; return value goes in eax
pop rbp ; restore caller's frame pointer
ret ; pop return address and jump to it
main:
endbr64
push rbp
mov rbp, rsp
mov edx, 3 ; caller puts actual parameters
mov esi, 2 ; in the agreed registers
mov edi, 1
call add3 ; pushes return address, jumps
pop rbp
retEvery field from the textbook picture is there: the return address (pushed by call), the saved old rbp (the control link), the locals and parameters at fixed negative offsets from rbp, and the returned value in eax. (Since add3 calls nobody, GCC does not even move rsp down; x86-64 Linux lets a leaf function use the 128 bytes below rsp, the "red zone".)
Calling and Return Sequences
The code that creates an activation record is the calling sequence; the code that destroys it and resumes the caller is the return sequence. The work is split between caller and callee. Code in the callee appears once; code in the caller is repeated at every call site, so it is better to put as much as possible in the callee.
Calling Sequence
Caller evaluates the actual parameters and places them in registers or in the new record.
Caller stores the return address (the
callinstruction does this) and jumps to the callee. The old stack top / frame pointer is saved as the control link.Callee saves the old frame pointer and any registers it will use that must be preserved, and sets up its own frame pointer.
Callee reserves space for its locals and temporaries (moves the stack pointer), initialises locals if needed, and starts executing its body.
Return Sequence
Callee places the return value where the caller expects it (a register or the return-value field).
Callee restores the saved registers and the caller's frame pointer and stack pointer (using the control link).
Callee jumps to the return address.
Caller picks up the return value. (With some conventions, such as C's
cdeclon 32-bit x86, the caller also removes the arguments it pushed; this is what makesprintf's variable number of arguments possible, because only the caller knows how many it pushed.)
Variable-Length Data on the Stack
A local array whose size is known only at run time (a C99 variable-length array, for example) cannot be at a fixed offset. The usual trick: the fixed part of the record contains a pointer to the array, and the array itself is placed after the fixed part, at the top of the stack. Locals are still at constant offsets, and the array is reached through its pointer.
Access to Non-Local Data
A procedure uses its own locals through the frame pointer. But what about names declared outside it? That depends on the language's scope rule.
Static (Lexical) vs Dynamic Scope
Static (lexical) scope: a name refers to the declaration in the nearest enclosing block in the program text. Determined at compile time. C, C++, Java, Python, Pascal.
Dynamic scope: a name refers to the most recent declaration still active at run time, found by searching back through the calling chain. Early Lisp, and shell variables declared with
localin bash.
The same program in both styles. First, bash, which uses dynamic scope for local:
x=10
show() { echo "x = $x"; }
fun() { local x=20; show; }
fun
showx = 20
x = 10Now C, which uses static scope:
#include <stdio.h>
int x = 10;
void show(void) { printf("x = %d\n", x); }
void fun(void) { int x = 20; (void)x; show(); }
int main(void) { fun(); show(); return 0; }x = 10
x = 10In C, show was written where only the global x is visible, so it always prints 10. In bash, show was called from inside fun, whose x = 20 is the most recent active declaration, so the first call prints 20. Dynamic scope is easy to implement (follow the control links and search) but makes programs hard to reason about, which is why almost all modern languages use static scope.
Languages Without Nested Procedures (C)
In C, functions cannot be nested. Every name is either local to the current function (found via the frame pointer) or global (at a fixed static address). No links are needed, which is one reason C's runtime is so simple.
Nested Procedures and Access Links
Languages like Pascal, Ada, ML and (with closures) JavaScript and Python allow a procedure to be declared inside another. An inner procedure may use the outer one's locals, which live in the outer procedure's activation record, somewhere down the stack. Which record? Not necessarily the caller's: the caller might be a sibling, or the inner procedure itself (recursion).
Define the nesting depth: 1 for the outermost procedure, plus 1 for each level of nesting. Consider:
procedure main; { depth 1 } var x
procedure A; { depth 2 } var y
procedure B; { depth 3 } var z ... uses x, y, z; calls C
procedure C; { depth 3 } ... uses y; calls B
begin ... call B ... end; { body of A }
begin ... call A ... end. { body of main }Each activation record gets an access link pointing to the most recent activation of the procedure that textually encloses it. Two rules make everything work.
Rule 1: using a name. If a procedure at depth np uses a name declared at depth na (na ≤ np), follow np − na access links from the current record, then use the name's fixed offset in the record you arrive at. The count is known at compile time.
Rule 2: setting the link on a call. When a procedure at depth np calls one at depth nq:
If nq > np (calling a procedure declared directly inside the caller, so nq = np + 1): the new access link points to the caller's record.
If nq ≤ np: follow np − nq + 1 access links from the caller; the record reached is the new access link.
Trace the call sequence main → A → B → C → B (records numbered #0, #1, ... in push order):
Call | np → nq | Links followed from caller | New record's access link |
|---|---|---|---|
main calls A (#1) | 1 → 2 | 0 (callee nested in caller) | main #0 |
A calls B (#2) | 2 → 3 | 0 | A #1 |
B calls C (#3) | 3 → 3 | 3 − 3 + 1 = 1 (B → A) | A #1 |
C calls B (#4) | 3 → 3 | 1 (C → A) | A #1 |
control links access links
#4 B --> #3 (C) --> #1 (A)
#3 C --> #2 (B) --> #1 (A)
#2 B --> #1 (A) --> #1 (A)
#1 A --> #0 (main) --> #0 (main)
#0 mainNow in the second B (#4), using x (depth 1) means following 3 − 1 = 2 links: #4 → #1 → #0, which is main's record, correct. Using y (depth 2): 1 link, to #1, A's record. Notice how the control links (who called whom) and the access links (who encloses whom in the text) are completely different chains.
Displays
Following k links costs k memory loads. A display makes every non-local access cost one load. It is an array d where d[i] points to the most recent active record of depth i. A name at depth na is found at d[na] + offset.
Maintenance is simple: when a procedure at depth k is called, it saves the old d[k] in its own record and sets d[k] to point to itself; on return it restores the saved value. For the same call sequence:
After call | Saved in new record | d[1] | d[2] | d[3] |
|---|---|---|---|---|
main | - | main #0 | - | - |
A | old d[2] (none) | main #0 | A #1 | - |
B | old d[3] (none) | main #0 | A #1 | B #2 |
C | old d[3] = B #2 | main #0 | A #1 | C #3 |
B | old d[3] = C #3 | main #0 | A #1 | B #4 |
Why is it safe that C overwrote d[3], hiding B #2? Because while C runs, B's locals are not visible to C (they are siblings), so nothing needs d[3] = B #2. When C returns, d[3] is restored to B #2.
Point | Access links | Display |
|---|---|---|
Cost of using a non-local at depth difference k | k loads (follow k links) | 1 load (index the display) |
Cost per call | Set one link (may follow several links) | Save and set one display entry |
Extra storage | One pointer per record | One array of size = maximum depth, plus one saved entry per record |
Best when | Nesting is shallow (the usual case) | Deep nesting with many non-local uses |
Common Mistakes
Confusing the control link with the access link. The control link points to the caller; the access link points to the lexically enclosing procedure. They are equal only when a procedure is called by the procedure that encloses it.
Confusing procedure and activation. One procedure, many activations (recursion).
Counting activations as the stack depth. Total activations = number of nodes in the activation tree; maximum stack depth = the number of nodes on its longest root-to-leaf path (plus main).
Saying the call sequence is postorder. Calls follow preorder; returns follow postorder.
Thinking C needs access links. C has no nested functions, so non-locals are globals with static addresses. (GCC's nested-function extension does use a "static chain", which is an access link.)
Mixing up the hop counts. Using a name: np − na hops. Setting a callee's link when nq ≤ np: np − nq + 1 hops.
Interview and Exam Questions
Q1. Why can activation records be kept on a stack?
Because in a sequential language, activation lifetimes are properly nested: a called procedure finishes before its caller does. So the most recently created record is always the first to be destroyed, which is last-in first-out.
Q2. A recursive function f(n) calls f(n−1) and f(n−2) for n > 1 and returns immediately for n ≤ 1. How many activations of f are created by f(5), and what is the maximum number of f records on the stack at once?
The calls satisfy C(n) = 1 + C(n−1) + C(n−2) with C(0) = C(1) = 1, giving C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15. The longest root-to-leaf path is f(5), f(4), f(3), f(2), f(1), so the maximum is 5 records.
Q3. What is the difference between the control link and the access link?
The control (dynamic) link points to the activation record of the caller and is used to restore the caller's environment on return. The access (static) link points to the activation record of the lexically enclosing procedure and is used to reach non-local variables under static scope.
Q4. Under dynamic scope, how is a non-local name found?
By searching backwards along the control links, from the current activation to its caller, its caller's caller and so on, until an activation that declares the name is found (or by keeping, for each name, a stack of its current bindings).
Q5. A procedure at nesting depth 4 uses a variable declared at depth 2. How many access links are followed? What about with a display?
4 − 2 = 2 access links. With a display, one access: d[2] gives the record directly.
Q6. Which tasks of the calling sequence are done by the caller and which by the callee?
Caller: evaluates and places the actual parameters, saves the return address and jumps (the call instruction). Callee: saves the old frame pointer and preserved registers, sets up its frame pointer, allocates space for locals and temporaries. On return the callee places the result, restores registers and the frame pointer, and jumps back; the caller collects the result (and, in some conventions, pops the arguments).
Q7. Why are locals accessed relative to a frame pointer rather than at fixed addresses?
Because each activation needs its own copy (for recursion) and records are created at different addresses at run time. The offset of each local within its record is fixed at compile time, so base-plus-offset addressing works for every activation.
Summary
A running program's memory is divided into code, static data, heap (grows up) and stack (grows down).
An activation is one execution of a procedure. The activation tree shows all activations of a run; calls follow preorder, returns postorder, and the live activations are the root-to-current path, held on the control stack.
An activation record holds parameters, returned value, control link, access link, saved machine status (return address, registers), locals and temporaries.
The calling sequence is split between caller (parameters, return address) and callee (save registers, frame pointer, allocate locals); the return sequence reverses it.
Non-locals: with static scope the declaration is found from the program text; with dynamic scope from the call chain. For nested procedures, access links (np − na hops) or a display (one lookup) locate the right record.
We have seen how the stack holds activation records. In Storage Allocation & Parameter Passing we compare static, stack and heap allocation in detail and see the different ways an actual parameter can be passed to a procedure.