Dynamic memory · about 40 min

Stack and heap

Why this matters

Every object in a C program lives somewhere in memory for some span of time. Getting either of those wrong is behind most serious C bugs: returning the address of a local variable, keeping a pointer to memory that was released, running out of stack with a big array, or never giving memory back. Higher-level languages hide this; in C you choose, and the choice is between three kinds of storage. This lesson builds the mental model; the rest of the module puts it to work with malloc and free.

Three storage durations

The C standard says every object has a storage duration, which decides its lifetime:

storage duration	what has it	lifetime	where it usually is
static	globals, `static` locals, string literals	the whole run of the program	data segment (`.data`, `.bss`, `.rodata`)
automatic	parameters, ordinary local variables	from entering the block until leaving it	the stack
allocated	memory from `malloc`, `calloc`, `realloc`	from allocation until `free`	the heap

Here is the process memory picture from the first lesson again, now with the three kinds placed in it:

  high addresses
  +-----------------------------+
  |  stack                      |  automatic: one frame per active call
  |  [main frame][f frame]...   |  grows downward as calls nest
  |              |              |
  |              v              |
  |                             |
  |              ^              |
  |              |              |
  |  heap                       |  allocated: malloc/free, grows upward
  +-----------------------------+
  |  .bss   zero-initialized    |  static: globals and static locals
  |  .data  initialized         |
  |  .rodata string literals    |
  +-----------------------------+
  |  .text  machine code        |
  +-----------------------------+
  low addresses

You can see the regions for yourself by printing addresses with %p (the cast to void * is what %p expects):

#include <stdio.h>
#include <stdlib.h>

int global_counter = 0;

int main(void)
{
    int local = 1;
    int *heap = malloc(sizeof *heap);
    printf("code   (main):           %p\n", (void *)main);
    printf("global (global_counter): %p\n", (void *)&global_counter);
    printf("heap   (*heap):          %p\n", (void *)heap);
    printf("stack  (local):          %p\n", (void *)&local);
    free(heap);
    return 0;
}

code   (main):           0x559829483159
global (global_counter): 0x55982948602c
heap   (*heap):          0x55982c11b2a0
stack  (local):          0x7ffe29e01a14

The exact numbers change on every run (Linux randomizes the layout as a security measure), but the order does not: code and globals are low, the heap a little above them, the stack far up near the top.

The stack: fast, automatic, limited

You met the call stack in the functions module. Each call pushes a frame holding the return address, the parameters and the locals; returning pops it. Two properties follow:

Allocation is free. Making room for a frame is a single subtraction from the stack pointer register. Nothing is searched for and nothing needs to be released later.
Lifetime is tied to the call. When the function returns, its frame is popped and its locals are gone. The bytes are still physically there until the next call overwrites them, which is why using them sometimes appears to work.

  during make_squares()         after it returns           after printf() is called
  +------------------+          +------------------+       +------------------+
  | main: p = ?      |          | main: p = 0x7ff..|---+   | main: p          |---+
  +------------------+          +------------------+   |   +------------------+   |
  | make_squares:    |          | (dead bytes)     |<--+   | printf's frame   |<--+
  |  squares[0..4]   |          |  0 1 4 9 16 ?    |       |  overwrites them |
  +------------------+          +------------------+       +------------------+

The stack is also small: 8 MB by default on Linux (ulimit -s prints 8192, in KB), and much less for threads and embedded systems. A local array of four million ints needs 16 MB:

int main(void)
{
    int big[4000000];       /* 16 MB on an 8 MB stack */
    ...
}

$ ./prog
Segmentation fault (core dumped)
$ echo $?
139

That is a stack overflow: the stack pointer moved past the end of the stack region into unmapped memory, and the kernel killed the process with signal SIGSEGV (status 128 + 11 = 139). Infinitely deep recursion does the same thing one frame at a time; gcc can even warn about the obvious cases with infinite recursion detected [-Winfinite-recursion].

Static storage: always there

Globals and static locals are laid out by the compiler and linker at fixed places and exist from before main starts until the program ends. They are zero-initialized if you do not initialize them. Making a big array static moves it off the stack, which fixes the overflow above. The cost is that the size must be known at compile time, and there is exactly one copy for the whole program, shared by every call.

The heap: you decide

Sometimes neither works: you need memory whose size is only known at run time (read a number of records from input, then store them), or that must outlive the function that creates it (build a list in one function, use it in another). That is what the heap is for.

The heap is a large region managed by the C library's allocator. You ask for a number of bytes with malloc; the allocator finds a free chunk, marks it used, and returns its address. When you are done you hand it back with free. Under the hood the allocator gets big pieces of address space from the kernel (with the brk and mmap system calls) and carves them up.

int *p = malloc(100 * sizeof(int));   /* room for 100 ints, alive until free */
/* ... use p[0] .. p[99] from any function you pass p to ... */
free(p);                              /* give it back */

The trade-offs:

	stack	heap
speed	one instruction	a function call that searches free lists
size	small (megabytes)	as large as available memory
size known	at compile time (mostly)	at run time
lifetime	ends when the function returns	ends when you call `free`
cleanup	automatic	your job; forget it and you leak

The next lesson covers malloc and free in detail.

Common mistakes

Returning the address of a local. gcc warns: Take this warning seriously. gcc actually compiles the function to return a null pointer instead, so the program usually crashes with a segmentation fault. Fixes: let the caller pass in the memory to fill, use static storage if one shared copy is acceptable, or allocate on the heap and make the caller responsible for freeing.
```
main.c:7:12: warning: function returns address of local variable [-Wreturn-local-addr]
    7 |     return squares;
      |            ^~~~~~~
```
Huge local arrays. Anything more than a few tens of kilobytes does not belong on the stack. Use static or the heap.
Assuming locals start at zero. Automatic variables hold whatever bytes were left in that stack slot. Only static storage is zeroed for you. -Wall catches many cases with 'x' is used uninitialized [-Wuninitialized].
Thinking "it printed the right value, so it is fine". Reading a dead frame is undefined behavior. It may print the old value today and something else after an unrelated change.

Recap

Objects have static (whole program), automatic (until the block ends) or allocated (until free) storage duration.
Automatic objects live in stack frames: allocation is instant, lifetime ends at return, and the stack is only about 8 MB.
Static objects live in the data segment, exist for the whole run, and start at zero.
The heap gives memory whose size is chosen at run time and whose lifetime you control with malloc and free.
Never return or keep the address of a local after its function returns.

Going further: run cat /proc/self/maps in the sandbox terminal. Each line is a region of the cat process's memory: the executable's code and data, [heap], shared libraries, and [stack] near the top.

Exercises

Exercise 1 · quiz

Where does it live?

Consider this program:

int total = 0;                 /* A */

int sum(int n)                 /* B: the parameter n */
{
    static int calls = 0;      /* C */
    int result = 0;            /* D */
    calls++;
    for (int i = 1; i <= n; i++)
        result += i;
    return result;
}

Which of the marked objects live on the stack? Select all that apply.

A: total
B: the parameter n
C: calls
D: result

Answer

B: the parameter n
D: result

Parameters and ordinary local variables have automatic storage: they live in the function's stack frame and vanish when it returns. total is a global and calls is a static local, so both have static storage: they live in the data segment for the whole run of the program, which is why calls keeps counting from one call to the next. (With optimization a compiler may keep n and result in registers and never touch the stack, but conceptually they belong to the frame.)

Exercise 2 · write code

Stop returning a dead array

make_squares builds an array of squares in a local array and returns its address. By the time main uses the pointer, the function's stack frame is gone. gcc warns about it, and in fact gcc replaces the returned address with a null pointer, so the program crashes.

Fix it with the caller provides the memory pattern: change the function to

void fill_squares(int *out, int n)

which writes 0*0, 1*1, ..., (n-1)*(n-1) into out[0] ... out[n-1]. In main, declare int squares[5];, call fill_squares(squares, 5), and print the five values on one line separated by single spaces:

0 1 4 9 16

File: main.c

Starting point

#include <stdio.h>

int *make_squares(void)
{
    int squares[5];
    for (int i = 0; i < 5; i++)
        squares[i] = i * i;
    return squares;          /* address of a local: dead after return */
}

int main(void)
{
    int *p = make_squares();
    for (int i = 0; i < 5; i++)
        printf(i ? " %d" : "%d", p[i]);
    printf("\n");
    return 0;
}

Example

expected output

0 1 4 9 16

Hint 1

The array has to live in a frame that is still alive when it is printed: main's frame.

Hint 2

Declare int squares[5]; in main and pass squares to the function; inside, write out[i] = i * i;.

Reference solution

#include <stdio.h>

void fill_squares(int *out, int n)
{
    for (int i = 0; i < n; i++)
        out[i] = i * i;
}

int main(void)
{
    int squares[5];
    fill_squares(squares, 5);
    for (int i = 0; i < 5; i++)
        printf(i ? " %d" : "%d", squares[i]);
    printf("\n");
    return 0;
}

Exercise 3 · write code

Too big for the stack

This program fills an array of four million ints (16 MB) and prints the last element. It crashes with a segmentation fault before printing anything, because the array is a local variable and the stack is limited to 8 MB.

Without making the array smaller, change where it lives so the program prints exactly:

File: main.c

Starting point

#include <stdio.h>

#define N 4000000

int main(void)
{
    int big[N];
    for (int i = 0; i < N; i++)
        big[i] = i;
    printf("%d\n", big[N - 1]);
    return 0;
}

Example

expected output

Hint 1

Objects with static storage duration (globals and static locals) are not on the stack.

Hint 2

Add the keyword static in front of the array declaration, or move the declaration outside main.

Reference solution

#include <stdio.h>

#define N 4000000

int main(void)
{
    static int big[N];   /* static storage: data segment, not the stack */
    for (int i = 0; i < N; i++)
        big[i] = i;
    printf("%d\n", big[N - 1]);
    return 0;
}

Exercise 4 · quiz

Who decides when it dies?

What decides when a block of heap memory (from malloc) stops being valid?

It is freed automatically when the function that called malloc returns
It stays valid until the program calls free on it (or the program exits)
The garbage collector frees it once no pointer refers to it
It is freed at the end of the block (the closing brace) where malloc was called

Answer

It stays valid until the program calls free on it (or the program exits)

Allocated storage lives exactly as long as you say: from malloc until free. That is the heap's whole point, because it lets data outlive the function that created it. C has no garbage collector, so if you lose the last pointer to a block without freeing it, the memory stays reserved until the process exits: a leak. When the process ends, the kernel reclaims all of its memory, heap included.