Stack and heap

Before you begin

Why this matters

In C, a pointer can outlive the thing it points to, and nothing stops you from using it. Knowing what lives in a frame and what lives on the heap prevents three common bugs: using memory that is gone, never giving memory back, and giving it back twice.

What this helps you reason about

Explain why returning a pointer to a local variable is a bug.
Decide which part of a program gives back each block of memory it asks for.
Recognize every pointer that becomes invalid when its memory is given back.

The stack-and-heap picture is a correct, useful model of how calls work, and C fits it closely. This lesson uses the picture to predict real behavior, then refines it with what it leaves out: in C, you are the one who frees heap memory.

Already know this? The short version

Automatic (local) variables last until their block ends. Returning or keeping their address gives a dangling pointer, and using it is undefined behavior.
malloc returns allocated storage that lasts until free, so a function may return it; check for NULL.
A static local has static storage duration: it is initialized before the program starts, not at the first call, and keeps its value across calls.
Copies of a pointer share one allocation. Free it exactly once, use no copy afterwards, and document which part of the program frees each allocation.
The standard speaks of storage durations, not a stack and heap. Optimized builds may keep variables in registers or remove them, and -fsanitize=address catches use after free and double free.

Go to the final check· Go to the practice tickets

Words in this lesson (8)

frame: The record of one function call that has not finished: its parameters and local variables. It is created when the call starts and removed when the call returns. The C standard does not mention frames; it calls these variables automatic.
call stack: The frames of all calls that have not finished yet, with the newest on top. A new call adds a frame on top, and a return removes it. Only the newest call runs; each call below it waits for the call it made.
heap: An area of memory for values that must outlive the call that created them. In C, memory from malloc comes from there and lasts until free.
malloc and free: malloc asks for a block of memory of a given size and returns a pointer to it, or NULL if it cannot. free gives that block back; it must be called exactly once per block.
pointer: A value that holds the address of a variable or of a block of memory, declared as in int *alias. *alias means what is stored at that address. Copying a pointer copies the address, not the memory it points to.
dangling pointer: A pointer to memory that no longer exists, such as a local of a call that has returned, or a block that was freed. Using it is undefined behavior.
undefined behavior: Code for which the C standard sets no requirements. The program may crash, print wrong results, or seem to work, and the result can change between builds.
static storage duration: The lifetime of a variable that exists for the whole run of the program. A local declared static has it: it is initialized before the program starts, not at the first call, and keeps its value between calls.

Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.

01 / The common picture

What do people mean by stack and heap?

Here is the picture most programmers learn. It is a teaching model: a simple picture that explains real behavior. Each function call gets a frame, a block of memory for its parameters and local variables. The frames are kept on the stack, also called the call stack. A new call adds a frame on top of the stack, and returning removes that frame.

Some values must stay usable after the call that created them returns, for example an object that the call gives back to its caller. A frame cannot hold such a value, because the frame is removed when the call returns. So those values are kept in a separate area of memory, called the heap, until the program no longer needs them.

In C, ordinary local variables live in the frame. malloc is the standard function that asks for heap memory, and free is the function that gives it back. Memory from malloc stays on the heap until you call free.

This model is correct for many programs. The rest of this lesson uses it to predict behavior, then refines it for the cases it does not cover.

Frames hold one call’s ordinary local variables; the heap holds memory from malloc until it is freed.

Precisely: what the C standard says

The C standard does not mention a stack or a heap. It says local variables have automatic storage duration (they last until their block ends) and malloc returns allocated storage (it lasts until free). Stack and heap are how implementations usually provide these.

02 / Frames

What happens to a call’s variables when it returns?

A frame exists only while its call is running. When inner returns, its frame is removed and doubled is gone. outer receives only the returned value.

A pointer is a value that holds the address of a variable. A pointer to doubled would still hold the old address after inner returns. Using it would be a bug, because doubled no longer exists. A pointer like this is called a dangling pointer.

main.c

int *bad_pointer(void) {
    int doubled = 6;
    return &doubled; /* bug: doubled ends here */
}

Never return the address of an ordinary local variable.

Coming from Java: Java never lets you take the address of a local variable, so this bug cannot happen there; in C the compiler at most warns.

Precisely: what compilers do

gcc warns that the function returns the address of a local variable, and at some settings returns a null pointer instead. Using such a pointer is undefined behavior: the C standard sets no requirements, so the program may appear to work, print garbage, or crash.

Experiment

Watch a frame come and go

Each call gets a frame holding its parameters and local variables. A frame exists only while its call is running. When inner returns, its frame is removed; only the returned value reaches outer.

Why it matters Local variables belong to one call. Once the call returns, the only thing the caller has is the value that was returned.

Predict what prints. Step until inner is running, then step once more. What happens to doubled?

#include <stdio.h>

int inner(int n) {
    int doubled = n * 2;
    return doubled;
}

int outer(void) {
    int start = 4;
    int result = inner(start);
    return result + 1;
}

int main(void) {
    setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
    printf("%d\n", outer());
    return 0;
}

What to look for

Watch the frame list. outer appears, then inner on top of it. When inner returns, its frame and its doubled variable are gone, and outer continues with result. Before a line runs, a variable may show a leftover value: that is uninitialized memory in this build.

Expected output

03 / Outliving a call

How can a value last longer than the call that made it?

malloc gives memory that does not belong to any frame. It lasts until free is called on it, so a function can return it. Always check for NULL, which malloc returns when it cannot provide memory.

The Variables lesson showed that copying a pointer copies only the address. Calling malloc again is different: each call gives a new block, so first and second below point to two blocks.

main.c

int *make_counter(void) {
    int *value = malloc(sizeof *value);
    if (value != NULL) *value = 3;
    return value;
}
int *first = make_counter();
int *second = make_counter(); /* a second block */

Returning memory from malloc. This is a model of what each pointer reaches, not of real addresses.

A conceptual model, not a physical memory layout or live code execution.

1 / 4

Allocate

make_counter: value: points to A
A: 3

malloc provides memory A; value points to it.

Experiment

Return memory from malloc

malloc gives memory that does not belong to any frame, and each call gives a new block. A block lasts until free is called on it. After the edit, first and second are two copies of one address, so the program must free that block once.

Why it matters In C, you decide when heap memory ends. Free each block once, and stop using every pointer to it afterwards.

Predict both numbers. Then change int *second = make_counter(); to int *second = first; and predict what happens at the two free calls.

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

int *make_counter(void) {
    int *value = malloc(sizeof *value);
    if (value != NULL) *value = 3;
    return value;
}

int main(void) {
    setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
    int *first = make_counter();
    int *second = make_counter();
    if (first == NULL || second == NULL) return 1;
    *first = 9;
    printf("%d %d\n", *first, *second);
    free(first);
    free(second);
    return 0;
}

What to look for

Step past the first return. The make_counter frame and its value pointer are gone, but first holds the same address, and the int there is 3. The second call returns a different address, and 9 3 prints. After free(first), the panel may show a strange number at first’s address: the allocator wrote its own records into the freed block, an observation of this build. After the edit, both pointers hold one address and 9 9 prints. Then free(second) frees that block a second time, and the stepper reports SIGABRT with free(): double free detected in tcache 2.

Expected output

9 3

04 / Refining the picture

Where does the picture need refining?

Here the picture needs refining. count is declared inside next_ticket, so the picture says it lives in the frame. But the word static gives count static storage duration. It exists for the whole run of the program, is set to 0 before the program starts (not at the first call), and keeps its value between calls.

main.c

int next_ticket(void) {
    static int count = 0;
    count++;
    return count; /* 1, then 2, then 3 */
}

Where a variable is declared does not by itself decide how long it lasts.

Coming from Java: A static local in C is like a private static field in Java that only one function can see.

Experiment

Keep a local between calls with static

static gives count static storage duration: it exists for the whole program and is set to 0 before the program starts, not at the first call. Without static, count is an ordinary local that starts again at 0 in every call.

Why it matters Not every variable declared inside a function lives in its frame. The storage class decides how long it lasts.

Predict all three numbers. Then remove the word static and predict again.

#include <stdio.h>

int next_ticket(void) {
    static int count = 0;
    count++;
    return count;
}

int main(void) {
    setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
    int a = next_ticket();
    int b = next_ticket();
    int c = next_ticket();
    printf("%d %d %d\n", a, b, c);
    return 0;
}

What to look for

Step into next_ticket each time. count keeps its value from the previous call, even though it is declared inside the function.

Expected output

1 2 3

05 / Releasing memory

Who decides when memory can be reused?

C has no garbage collector, the background process that other languages use to find and free unused memory. Memory from malloc lasts until your program calls free on it, exactly once. After free, every copy of the pointer is invalid.

Decide which part of the program is responsible for freeing each allocation, and write that down where the function is declared.

main.c

int *first = make_counter();
if (first != NULL) {
    int *second = first;
    *second = 9;
    free(first);
    /* Do not use second, or free it again. */
}

Free each allocation exactly once, then stop using every pointer to it.

Coming from Python: Nothing frees memory for you in C: an allocation you forget to free stays in use until the program exits, and in firmware that never exits, it stays in use for good.

Precisely: hosted and freestanding C

This lesson describes hosted C: a program that runs under an operating system, which takes back all of the program’s memory when it exits. Freestanding C, such as firmware on a microcontroller, may have no operating system and no malloc at all. Such a program usually never exits, so nothing ever takes leaked memory back, and many firmware projects allocate only at startup or not at all.

06 / The implementation

What may the compiler or runtime change?

The compiler, such as gcc, translates your C into machine instructions. When it optimizes, for example with -O2, it may keep variables in registers, small storage places inside the processor itself, instead of in memory. It may also remove variables it does not need, or merge calls. A program without undefined behavior always does something the C standard allows. Where the standard leaves a choice open, such as the order in which a call’s arguments are evaluated, -O0 and -O2 may choose differently. A program with undefined behavior, such as using memory after free, may act differently at -O2 than at -O0, so a use after free that seemed harmless in one build can fail in another.

So a variable you can see in source code may not exist in memory at all in an optimized build.

Precisely: tools for a real program

The stepper compiles with gcc at -O0, which keeps every variable visible. To find memory bugs in a real program, compile with -fsanitize=address: AddressSanitizer stops the program at a use after free or a double free, when it happens. Leaks are found by its LeakSanitizer part, which reports them when the program exits, and only on platforms that support it.

07 / Try it

When can each value’s memory be released?

Predict the print, then follow each block from malloc to the end of the program. If malloc fails, the program exits without using a NULL pointer.

main.c

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

int *make_counter(int start) {
    int *value = malloc(sizeof *value);
    if (value != NULL) *value = start;
    return value;
}

int main(void) {
    int *first = make_counter(3);
    int *second = make_counter(7);
    if (first == NULL || second == NULL) return 1;
    first = second;
    *first = 9;
    printf("%d %d\n", *first, *second);
    free(second);
    return 0;
}

What prints? After line 14, what happens to the block that held 3? And after free(second), which pointers are dangling?

Reveal the reasoning

9 9. After first = second on line 14, no pointer leads to the block that held 3, but it is still allocated: C never releases memory because nothing reaches it. It leaks until the program exits. first and second now hold one address, so *first = 9 changes the block that held 7. free(second) releases that block, so first and second are both dangling: neither may be used or freed again.

Why this matters

What this helps you reason about

What do people mean by stack and heap?

What happens to a call’s variables when it returns?

Watch a frame come and go

How can a value last longer than the call that made it?

Allocate

Return memory from malloc

Where does the picture need refining?

Keep a local between calls with static

Who decides when memory can be reused?

What may the compiler or runtime change?

When can each value’s memory be released?

Practice tickets

Keep exploring

Primary references