Storage organisation: static, stack and heap

Why it exists

The compiler must decide where every piece of data lives while the program runs, and the answer is not the same for all data: a global variable exists for the whole run, a local variable only while its procedure runs (and a recursive procedure has several copies at once), and a node allocated with malloc lives until the program frees it, whatever the procedure that allocated it did. The compiler organises memory into three kinds of storage for these three lifetimes. GATE asks which kind a given variable uses, which language features force the stack or the heap (and the classic wrong beliefs: recursion needs a heap, recursion needs garbage collection), and what goes wrong when the wrong kind is used.

Prerequisites

You need the activation record (also called a frame) that one call of a procedure occupies, with its parameters, locals and links, from activation records.

Precise definitions

Three kinds of storage.

The memory of a process is laid out with the code and the static data at the bottom, the heap above them growing towards higher addresses, and the stack at the top growing towards lower addresses (on most machines), with unused memory between them; the C memory layout page shows it, and the operating system maps it (process address space).

Static allocation. A compiler that allocates all data statically gives every procedure one fixed record. That works only if a procedure never has two activations alive at once, that is, without recursion (early Fortran), and without variable-sized arrays or dynamic data. With recursion the second activation would overwrite the first one's parameters and locals.

Stack allocation. A record is pushed when the procedure is called and popped when it returns. Because calls and returns nest, the records are freed in the reverse order of their creation, so a stack is enough: recursion is implemented with a stack, not with a heap, and needs no garbage collection. Nested procedures with static scoping add access links or a display to reach the records of enclosing procedures (the page on activation records). With dynamic scoping no heap is needed either.

Heap allocation. Needed for data whose lifetime is not nested in the calls: objects created by a procedure that outlive it (dynamic data structures: linked lists, trees), and the environment of a procedure that is returned as a value (a closure): the returned procedure refers to variables of the record in which it was created, and that record must survive the return of its procedure, so it cannot be on the stack. A language that allows a function to return a function as its result cannot use a pure stack discipline for its activation records.

Dangling reference. A reference to storage that has been freed or popped. Stack allocation makes it easy to create one: returning the address of a local variable (return &x;) refers to a record that is popped when the procedure returns; the same applies to a returned nested procedure that uses its creator's variables. Heap storage freed too early, or freed twice, causes the same errors.

Heap management. The allocator keeps a free list; free returns a block. Over time the free space is split into many small pieces (external fragmentation); allocators merge neighbouring free blocks and choose a block by first fit, best fit or similar. A language can free dead objects automatically: garbage collection (reference counting, mark and sweep, copying collection) finds the objects that can no longer be reached. It is needed to avoid leaks in a language with a heap and no explicit free; it is not needed for recursion.

Which feature needs what.

How it works

The same programs under three policies. A tiny language with recursion, nested procedures and procedure values is run three times: with static allocation (one record per procedure), stack allocation (a record is popped on return) and heap allocation (records are kept). Recursion fails with static allocation; a returned procedure fails on the stack ("dangling") and, with static allocation, two counters share one variable; the heap gets all of them right.

How much stack does a recursion need? The space is the depth of the recursion, not the number of calls.

Worked examples

#include <stdio.h>
 
static int n_static;                         /* the one static record of fact_static: its parameter */
 
static int fact_static(int arg) {
    int r;
    n_static = arg;
    if (n_static <= 1) return 1;
    r = fact_static(n_static - 1);           /* the deeper activations overwrite n_static */
    return n_static * r;
}
 
static int fact_stack(int n) {
    int r;
    if (n <= 1) return 1;
    r = fact_stack(n - 1);
    return n * r;
}
 
int main(void) {
    printf("fact(4) with one static copy of the parameter: %d\n", fact_static(4));
    printf("fact(4) with automatic (stack) storage: %d\n", fact_stack(4));
    return 0;
}

fact(4) with one static copy of the parameter: 1
fact(4) with automatic (stack) storage: 24

#include <stdio.h>
 
static long calls;
static int depth, deepest;
 
static long fib(int n) {
    long r;
    calls++;
    depth++;
    if (depth > deepest) deepest = depth;
    r = n < 2 ? 1 : fib(n - 1) + fib(n - 2);
    depth--;
    return r;
}
 
int main(void) {
    int ns[7] = {1, 2, 3, 5, 8, 10, 15};
    for (int i = 0; i < 7; i++) {
        calls = 0;
        deepest = 0;
        fib(ns[i]);
        printf("fib(%2d): %5ld calls, deepest chain %2d\n", ns[i], calls, deepest);
    }
    return 0;
}

fib( 1):     1 calls, deepest chain  1
fib( 2):     3 calls, deepest chain  2
fib( 3):     5 calls, deepest chain  3
fib( 5):    15 calls, deepest chain  5
fib( 8):    67 calls, deepest chain  8
fib(10):   177 calls, deepest chain 10
fib(15):  1973 calls, deepest chain 15

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
static uintptr_t deepest_address;
 
static void deepest(int n) {
    volatile int local = n;                              /* one record per activation, on the stack */
    if (n == 0) deepest_address = (uintptr_t)&local;     /* the address is only compared, and only while the record exists */
    else deepest(n - 1);
}
 
static int next_static(void) {
    static int count = 0;                                /* static storage: one copy, kept between calls */
    return ++count;
}
 
static int next_automatic(void) {
    int count = 0;                                       /* automatic: a new copy in every activation */
    return ++count;
}
 
static int *make(void) {
    int *p = malloc(sizeof *p);                          /* heap: survives the return of make */
    if (p) *p = 42;
    return p;
}
 
int main(void) {
    volatile int outer = 0;
    deepest(5);
    uintptr_t a = (uintptr_t)&outer, b = deepest_address;
    printf("a local of a deeper activation has a %s address than one of its caller\n", b < a ? "LOWER" : "HIGHER");
    int s1 = next_static(), s2 = next_static(), s3 = next_static();          /* separate statements: the order of evaluating arguments is unspecified */
    int a1 = next_automatic(), a2 = next_automatic(), a3 = next_automatic();
    printf("static counter, three calls:    %d %d %d\n", s1, s2, s3);
    printf("automatic counter, three calls: %d %d %d\n", a1, a2, a3);
    int *h = make();
    if (!h) return 1;
    printf("heap block read after make() returned: %d\n", *h);
    free(h);
    return 0;
}

a local of a deeper activation has a LOWER address than one of its caller
static counter, three calls:    1 2 3
automatic counter, three calls: 1 1 1
heap block read after make() returned: 42

Cheat box

Traps and GATE patterns

Connections

The activation record of activation records is the unit that the stack holds; parameter passing decides what is copied into it. A C program sees the same three areas in the C memory layout, and malloc is the heap of dynamic memory; the operating system provides them as segments of the process address space.

PYQs

Which of the following are true?
(I)
A programming language which does not
permit global variables of any kind and has
no nesting of procedures/functions, but
permits recursion can be implemented with
static storage allocation
(II)
Multi-level
access
link
(or
display)
arrangement is needed to arrange activation
records only if the programming language
being
implemented
has
nesting
of
procedures/functions.
(III) Recursion in programming languages cannot
be implemented with dynamic storage
allocation
(IV) Nesting procedures/functions and recursion
require a dynamic heap allocation scheme
and cannot be implemented with a stack-
based allocation scheme for activation
records
(V)
Programming languages which permit a
function to return a function as its result cannot
be implemented with a stack-based storage
allocation scheme for activation records.

Consider the following statements.

I.
Symbol table is accessed only during lexical
analysis and syntax analysis.

II.
Compilers for programming languages that
support recursion necessarily need heap
storage for memory allocation in the run-time
environment.

III.
Errors violating the condition 'any variable
must be declared before its use' are detected
during syntax analysis.

Which of the above statements is/are TRUE?

Which of the following statements are Correct?
1. Static allocation of all data areas by a compiler
makes it impossible to implement recursion.
2. Automatic garbage collection is essential to
implement recursion.
3. Dynamic allocation of activation records is
essential to implement recursion.
4. Both heap and stack are essential to implement
recursion.

Which languages necessarily need heap allocation
in the runtime environment?

Self-check

Revision card

References