58 Managing memory — lifetime, ownership, and other languages’ collectors

58.1 What memory management is — who, and when#

Memory management is deciding who returns borrowed memory, and when. Borrowing is easy in every language. The hard part is the moment of returning. Too early is a use after free; too late, or never, is a leak (chapter 57). Languages differ in how they decide that moment, and that difference does much to set a language’s character.

C is the first row. The language does not decide when to return, so the programmer has to set the rules that decide. The next section sets out those rules.

58.2 Habits for governing lifetime in C#

58.2.1 One owner — written in names and comments#

The rule of chapter 46 is the starting point. For every block, fix one owner responsible for returning it. C has no syntax to write this down, so it is written in names and comments. There are common conventions.

• Paired names such as _create / _destroy or _new / _free. The partner of the function that made it returns it.
• In the comment of a function returning a pointer, write “the caller owns it” or “lent — do not return”.
• For every pointer member of a structure, write whether “this structure owns it” or “it only points at someone else’s”.

The third matters most. A function that frees a structure must return only the members it owns; returning a member that merely points elsewhere is a double free.

58.2.2 Pair each acquisition with its release, and clean up at one exit#

In a function that borrows several resources, leaks usually happen on the path that failed half-way. C’s old idiom gathers the cleanup in one place at the end of the function and jumps there on failure.

int load(const char *path)
{
    int rc = -1;
    FILE *f = nullptr;
    char *buf = nullptr;

    f = fopen(path, "rb");
    if (f == nullptr) goto out;
    buf = malloc(4096);
    if (buf == nullptr) goto out;
    /* ... work ... */
    rc = 0;
out:
    free(buf);                      /* free(nullptr) does nothing */
    if (f != nullptr) fclose(f);
    return rc;
}

Setting every pointer to nullptr at the start is the key to this shape. Whichever step fails, the cleanup section returns “only what was borrowed” with the same code. Some conventions frown on goto, but for this use large projects written in C, the Linux kernel among them, use it widely (chapter 42).

58.2.3 Grouping things with the same lifetime#

Instead of managing the lifetime of each block separately, there is a way of borrowing things that die together as one lump. The memory used while handling one request, while drawing one frame or while parsing one file all ends together. Borrow such things from an arena and the individual frees disappear; at the end only the arena is returned (chapter 99). Leaks and double frees shrink structurally — there is only one thing to return. In exchange, while the arena lives, a single block inside it cannot be returned early. A design that passes the allocator as an argument (chapter 104) lets the caller choose between an arena and individual malloc calls.

58.2.4 Why nullptr after freeing is half a fix#

free(p); p = nullptr; is a good habit. Freeing again through that variable becomes free(nullptr) and nothing happens; reading through it is likely to stop on the spot with a null dereference. But what it guards is that one variable. Other variables holding a copy of the same address, structure members, list elements are left dangling as before. Guarding the lifetime of an object with many aliases needs another device — the handles of the next section are one.

58.3 A data structure that detects dangling references — handles with generation numbers#

The trouble with a pointer is that you cannot ask whether the object is dead. A pointer has only an address and does not know what is at that address now. So there is a design that refers to objects by handle instead of pointer. The objects live in a pool of fixed slots, and a handle is a pair (slot number, generation). Every time a slot is returned, its generation goes up by one.

/* Handles with generation numbers --- references that *can detect* dangling.
 * Hand out (slot number, generation) instead of a pointer. Each return of a slot raises its generation,
 * so an old handle no longer matches and is judged "an object already dead". The slot may be reused. */
#include <stdint.h>
#include <stdio.h>

enum { SLOTS = 4 };

typedef struct { uint32_t index, gen; } handle;

typedef struct {
    double   value[SLOTS];
    uint32_t gen[SLOTS];        /* generation per slot */
    bool     used[SLOTS];
} pool;

static bool pool_new(pool *p, double v, handle *out)
{
    for (uint32_t i = 0; i < SLOTS; i++) {
        if (!p->used[i]) {
            p->used[i] = true;
            p->value[i] = v;
            *out = (handle){ i, p->gen[i] };
            return true;
        }
    }
    return false;               /* no free slot */
}

static void pool_free(pool *p, handle h)
{
    if (h.index < SLOTS && p->used[h.index] && p->gen[h.index] == h.gen) {
        p->used[h.index] = false;
        p->gen[h.index]++;      /* ★ every handle to this slot goes stale at this moment */
    }
}

/* Return the place if the object is alive, otherwise NULL --- you *can ask* before using it. */
static double *pool_get(pool *p, handle h)
{
    if (h.index >= SLOTS || !p->used[h.index] || p->gen[h.index] != h.gen)
        return NULL;
    return &p->value[h.index];
}

static void show(pool *p, const char *name, handle h)
{
    double *v = pool_get(p, h);
    if (v) printf("%-6s (slot %u, gen %u) -> %.1f\n", name, (unsigned)h.index, (unsigned)h.gen, *v);
    else   printf("%-6s (slot %u, gen %u) -> stale handle, object is gone\n",
                  name, (unsigned)h.index, (unsigned)h.gen);
}

int main(void)
{
    pool p = {0};
    handle a, b;
    if (!pool_new(&p, 1.5, &a)) return 1;
    show(&p, "a", a);

    pool_free(&p, a);               /* return the object a referred to */
    if (!pool_new(&p, 9.0, &b)) return 1;  /* the same slot is reused */
    show(&p, "b", b);
    show(&p, "a", a);               /* as a pointer, this would have read b's value */
    return 0;
}

a      (slot 0, gen 0) -> 1.5
b      (slot 0, gen 1) -> 9.0
a      (slot 0, gen 0) -> stale handle, object is gone

After a was returned, b came into the same slot 0. Had a been a pointer, it would now read b’s value — the case where a use after free reads someone else’s object without a sound. As a handle, its generation (0) differs from the slot’s (1), so it is judged “an object already dead”. The slot is reused, yet the old reference does not come back to life.

This shape is often called a generational index, and such a pool a slot map. It gains three things. Dangling references can be detected, objects sit together in a contiguous array that suits the cache (chapter 12), and a handle is an integer, so it keeps its meaning when written to a file or passed to another process. The price is one comparison per access, and the day the generation number wraps around and equals an old handle again — with a 32-bit generation, one slot must be reused more than four billion times for that day to come.

58.4 Writing what was borrowed in a ledger — poisoning and quarantine#

Part of what ASan does can be imitated with a small allocator wrapped around malloc and free. Write every borrowed block in a ledger, and instead of freeing a returned block at once, keep it in quarantine and paint it with a poison value.

/* A small checking allocator --- every borrowed block is written in a ledger.
 * A returned block is not freed at once but kept in *quarantine* (painted with poison 0xDD). So when a
 * second free arrives, the address still points at a living object and can be compared with the ledger.
 * Had it really been freed, using that pointer value at all would be outside the contract (C23 6.2.4p2). */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { MAX_BLOCKS = 16 };

typedef struct {
    unsigned char *p;
    size_t size;
    const char *where;
    bool released;          /* returned, but in quarantine */
} entry;
static entry book[MAX_BLOCKS];

static void *chk_malloc(size_t size, const char *where)
{
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        if (book[i].p == NULL) {
            unsigned char *p = malloc(size);
            if (p == NULL) return NULL;
            book[i] = (entry){ p, size, where, false };
            return p;
        }
    }
    return NULL;                        /* the ledger is full */
}

static void chk_free(void *ptr, const char *where)
{
    if (ptr == NULL) return;
    unsigned char *p = ptr;
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        entry *e = &book[i];
        if (e->p == NULL) continue;
        if (p == e->p) {
            if (e->released) {
                printf("  %s: double free of the block from %s\n", where, e->where);
            } else {
                memset(e->p, 0xDD, e->size);    /* paint with poison */
                e->released = true;             /* quarantine: not freed yet */
            }
            return;
        }
        /* "Is it inside this block?" is not asked with < on pointers --- comparing the size of pointers
           to different objects is outside the contract (6.5.9). Ask with integer addresses (implementation-defined). */
        uintptr_t a = (uintptr_t)p, lo = (uintptr_t)e->p;
        if (a > lo && a - lo < e->size) {
            printf("  %s: free of an address inside the block from %s (offset %ju)\n",
                   where, e->where, (uintmax_t)(a - lo));
            return;
        }
    }
    printf("  %s: free of a pointer this allocator never gave out\n", where);
}

/* At the end: report what was never returned as a leak, and really free everything, quarantined blocks too. */
static void chk_finish(void)
{
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        if (book[i].p == NULL) continue;
        if (!book[i].released)
            printf("  leak: %zu bytes from %s\n", book[i].size, book[i].where);
        free(book[i].p);
        book[i] = (entry){0};
    }
}

int main(void)
{
    char *name = chk_malloc(16, "line A");
    char *tmp  = chk_malloc(64, "line B");
    int  *nums = chk_malloc(4 * sizeof *nums, "line C");
    if (!name || !tmp || !nums) return 1;

    strcpy(name, "ok");
    chk_free(tmp, "line D");
    chk_free(tmp, "line E");            /* second free */
    chk_free(name + 1, "line F");       /* middle of a block */
    chk_free(name, "line G");
    printf("  first byte of the released block from line B: 0x%02X\n",
           (unsigned)(unsigned char)tmp[0]);    /* in quarantine, so reading is inside the contract */

    puts("at exit:");
    chk_finish();                       /* nums was never returned */
    return 0;
}

  line E: double free of the block from line B
  line F: free of an address inside the block from line A (offset 1)
  first byte of the released block from line B: 0xDD
at exit:
  leak: 16 bytes from line C

Three things were caught: the second free (line E), returning the middle of a block (line F), and a block never returned (line C, a leak). The first byte of the quarantined block is 0xDD — had there been a use after free, a value like this would have come out and stood out.

★ Quarantine is the heart of this allocator. Had the returned block been freed at once, comparing that pointer with the ledger on the second free would itself be outside the contract (the pointer zap of chapter 57). While the block is kept alive, the address still points at a living object, so comparing and reading are both inside the contract. ASan catches use after free the same way — it keeps returned blocks in quarantine for a while and does not hand them to other requests. So a use after free that comes after the quarantine filled up and the block was reused can escape ASan too.

58.5 Reference counting — returning by counting#

Reference counting keeps, for every object, a count of “how many references point at me”, and returns the object the moment the count reaches 0. Making a reference raises the count (retain); dropping it lowers the count (release). Because the object is returned the moment the last reference disappears, the time of return is predictable and there is no need to stop and work the way a collector does.

CPython puts a reference count on every object. Swift uses ARC (Automatic Reference Counting), in which the compiler inserts retain and release automatically. Rust has Rc (one thread) and Arc (several threads) for when ownership is not enough. Large libraries written in C also attach counts to their objects and use this method by hand (the object model of chapter 68 is an example).

There are two prices. First, the count must be updated every time a reference is copied. When several threads share the same object that update has to be an atomic operation (chapter 95), and atomic operations cost more than ordinary additions. Second, there is a more fundamental weakness: objects that point at each other, a cycle.

/* Reference counting --- count "how many point at me" and return the object the moment it reaches 0.
 * And its weakness: two objects pointing at each other (a cycle) never reach 0.
 * Make one side a *weak reference* (one that does not raise the count) and the cycle comes apart. */
#include <stdio.h>
#include <stdlib.h>

typedef struct node node;
struct node {
    const char *name;
    int   refs;
    node *strong;       /* a reference that raises the count */
    node *weak;         /* a reference that does not raise the count --- not an owner */
};

static int live;        /* nodes not yet returned */

static node *node_new(const char *name)
{
    node *n = calloc(1, sizeof *n);
    if (n == NULL) exit(1);
    n->name = name;
    n->refs = 1;        /* the creator holds the first reference */
    live++;
    return n;
}

static node *retain(node *n) { if (n) n->refs++; return n; }

static void release(node *n)
{
    if (n == NULL || --n->refs > 0) return;
    printf("  free %s\n", n->name);
    release(n->strong);             /* drop the strong reference I hold */
    free(n);
    live--;
}

int main(void)
{
    puts("cycle of two strong references:");
    node *a = node_new("a"), *b = node_new("b");
    a->strong = retain(b);
    b->strong = retain(a);          /* a -> b -> a */
    release(a);
    release(b);                     /* every outside reference has been dropped */
    printf("  still alive: %d (a.refs %d, b.refs %d) --- leaked\n", live, a->refs, b->refs);

    /* The demonstration is over, so break the cycle by hand --- without a collector, this job is a person's. */
    a->strong = NULL; b->strong = NULL;
    free(a); free(b); live -= 2;

    puts("same shape, back edge made weak:");
    node *c = node_new("c"), *d = node_new("d");
    c->strong = retain(d);
    d->weak = c;                    /* d -> c does not raise the count */
    release(c);
    release(d);
    printf("  still alive: %d\n", live);
    return 0;
}

cycle of two strong references:
  still alive: 2 (a.refs 1, b.refs 1) --- leaked
same shape, back edge made weak:
  free c
  free d
  still alive: 0

When a and b point strongly at each other, each count stops at the 1 held by the other even after every outside reference is dropped. Nobody can reach them, yet they are never returned — a cycle is a leak reference counting cannot reclaim. The remedy is to make one direction a weak reference, a reference that does not raise the count: a parent points strongly at its child and the child weakly at its parent. In the second demonstration, once d pointed weakly at c, both were returned on time.

Weak references bring a problem of their own. If the object they point at disappears first, the weak reference dangles. So the weak references of real systems are made so that you can ask “is it still alive?”. Swift’s weak becomes nil by itself when the object goes away, and Rust’s Weak checks with upgrade whether it is alive before use. The weak member in the demonstration above survived without any such device, only by never being read again — asking whether the object is still alive is a job the generation handles of the earlier section can do.

CPython keeps a separate collector for cycles. Reference counting is the basis, and a cycle collector supplements what it cannot reclaim (the Python documentation’s word is “supplements”). The tracing collection of the next section is exactly that collector.

58.6 Tracing collection — is it reachable?#

Tracing garbage collection does not count “who points at me”; it searches for “can it be reached from the roots?”. The roots are what the program holds right now — local variables, global variables, registers — and an object reachable from the roots by following pointers is alive, while the rest is garbage. The part of the runtime that does this is the garbage collector, or collector for short. Whether something “will be used again” cannot be known, so the collector approximates it by “can it be reached?”. What is reachable but never used again cannot be reclaimed by a collector either — this is the “leak despite a collector” we will see later.

58.6.1 Mark-sweep#

The simplest collector has two phases. In the mark phase it marks every object reachable from the roots, and in the sweep phase it walks all allocated objects and returns those without a mark.

/* A toy mark-sweep collector --- life and death decided by "is it reachable from the roots?".
 * Even a cycle reference counting could not reclaim is reclaimed once cut off from the roots. Unlike a real
 * collector, roots are registered by hand --- C has no ledger saying "where the pointers are". */
#include <stdio.h>
#include <stdlib.h>

typedef struct obj obj;
struct obj {
    char  name;
    obj  *ref[2];       /* two places that point at other objects */
    bool  marked;
    int   survived;     /* how many collections it survived */
    obj  *next_alloc;   /* list of every object the collector knows */
};

static obj *all;                /* every allocated object */
static obj *roots[4];           /* roots: what the program holds right now */

static obj *gc_new(char name)
{
    obj *o = calloc(1, sizeof *o);
    if (o == NULL) exit(1);
    o->name = name;
    o->next_alloc = all;
    all = o;
    return o;
}

static void mark(obj *o)
{
    obj *stack[64];             /* an explicit stack instead of recursion --- so deep graphs do not overflow the call stack */
    size_t top = 0;
    if (o) stack[top++] = o;
    while (top > 0) {
        obj *x = stack[--top];
        if (x->marked) continue;        /* marks each object once, even in a cycle */
        x->marked = true;
        for (int i = 0; i < 2; i++)
            if (x->ref[i] && !x->ref[i]->marked && top < sizeof stack / sizeof stack[0])
                stack[top++] = x->ref[i];
    }
}

static void collect(void)
{
    for (size_t i = 0; i < sizeof roots / sizeof roots[0]; i++)
        mark(roots[i]);                 /* (1) mark: what the roots reach */

    printf("  freed:");
    for (obj **p = &all; *p != NULL; ) { /* (2) sweep: return what has no mark */
        obj *o = *p;
        if (!o->marked) {
            *p = o->next_alloc;
            printf(" %c", o->name);
            free(o);
        } else {
            o->marked = false;          /* clear for the next collection */
            o->survived++;
            p = &o->next_alloc;
        }
    }
    printf("\n  alive:");
    for (obj *o = all; o != NULL; o = o->next_alloc)
        printf(" %c(survived %d)", o->name, o->survived);
    printf("\n");
}

int main(void)
{
    obj *a = gc_new('a'), *b = gc_new('b'), *c = gc_new('c');
    a->ref[0] = b;
    b->ref[0] = c;
    c->ref[0] = b;                      /* b <-> c cycle */
    roots[0] = a;
    (void)gc_new('t');                  /* a temporary nobody holds */

    puts("collection 1 (root: a):");
    collect();

    a->ref[0] = NULL;                   /* cut the road from a to the cycle */
    (void)gc_new('u');
    puts("collection 2 (a no longer points at the cycle):");
    collect();

    roots[0] = NULL;                    /* empty the roots, final collection */
    puts("collection 3 (no roots):");
    collect();
    return 0;
}

collection 1 (root: a):
  freed: t
  alive: c(survived 1) b(survived 1) a(survived 1)
collection 2 (a no longer points at the cycle):
  freed: u c b
  alive: a(survived 2)
collection 3 (no roots):
  freed: a
  alive:

In the first collection only t, held by no one, was reclaimed. b and c form a cycle pointing at each other, but they are reachable from the root a, so they lived. Before the second collection the road from a to the cycle was cut, and the whole cycle was reclaimed — exactly the shape that stayed behind to the end in the reference counting demonstration. Marking passes each object of a cycle only once, by “skip it if already marked”.

There is one thing the demonstration does by hand. It registered the roots directly in the roots array. A real collector’s runtime knows where on the stack and in which registers there are pointers — because the compiler builds that ledger for it. C has no such ledger. That difference is the story of the later section “Attaching a collector to C”.

58.6.2 Copying collection — gathering while moving#

Mark-sweep leaves objects where they are. So after running long, gaps appear between living objects (fragmentation, chapter 99). Copying collection divides memory into two regions and, on collection, moves only the living objects into the other region, packed together. The region left behind becomes empty as a whole. Fragmentation disappears and allocation becomes as cheap as pushing a pointer forward. In exchange, objects’ addresses change, so every pointer that pointed at them must be fixed — something possible only for a collector that knows where every pointer is.

58.6.3 Generational collection — most objects die young#

Measuring real programs gives a recurring observation: most objects die soon after they are made, and objects that have lived long keep living long. This is called the generational hypothesis. Generational collection leans on it. New objects are put in a young generation that is collected often and cheaply. Objects that survive a few collections are promoted to an old generation that is collected rarely. Since all of memory need not be walked every time, each collection gets shorter. The “survived” counts printed by the mark-sweep demonstration are the raw material of this promotion — a, having survived several times, is a candidate for the old generation.

The price is pointers that cross generations. If an old object points at a young one, that pointer must be treated like a root when only the young generation is collected. So the collector puts a write barrier on every store of a pointer into an old object, recording it, and gathers the records in a remembered set. Every pointer store costs a few more instructions. CPython’s cycle collector also divided objects into three generations up to 3.13 (the incremental collector of 3.14 has two).

58.6.4 Incremental and concurrent collection#

If the program is stopped while the collector works (stop-the-world), responses are interrupted. Incremental collection cuts that work into small pieces slipped in between the program’s steps, and concurrent collection runs on another thread alongside the program. Go’s collector is mark-sweep, does most of its work concurrently with the program, and does not move objects.¹ Running alongside means the program may change pointers while the collector is marking, so a write barrier is needed here too.

58.7 What collectors cost#

A collector takes “when to return it” away from people. In exchange it takes something back.

The second row can be seen in numbers. Go’s default setting (GOGC=100) starts the next collection after allocating as much again as the live heap (and roots) — if the live objects are 8 MiB, it leaves room for that much more garbage to pile up. Doubling GOGC (to 200) doubles the headroom and roughly halves the CPU spent on collection. The cost of a collector is a choice of whether to pay in time or in space.

58.8 When the compiler tracks ownership#

The fourth answer to “who returns memory, and when” neither counts nor searches at run time; it decides where to return memory at compile time.

C++‘s RAII (Resource Acquisition Is Initialization) ties a resource to an object’s lifetime. When the object leaves its scope its destructor returns the resource, and the compiler knows where that is. It is as if the compiler wrote the goto out cleanup section above for you. Rust goes one step further. Each value has one owner; when the owner leaves its scope the value is returned; after it is handed to someone else (a move), the old name can no longer be used. The compiler checks that a lent reference cannot outlive the value it borrows. Of the “lifetime accidents” of the previous chapter, use after free and double free become compile errors in safe Rust code. The ownership rule of chapter 46 — once written only in comments and names — has been raised into the type system.

C has attempts in this direction too. GCC and Clang provide the extension attribute __attribute__((cleanup(f))), which calls a function when a variable leaves its scope. On the standards side, work began in 2025 on making defer, which writes down in advance what to do when a block ends, into a technical specification (ISO/IEC TS 25755) — a document of extensions beside the standard rather than the standard itself, and absent from C23 as this book is written. Neither proves ownership. They only have the compiler remember the place of cleanup for you.

58.9 Attaching a collector to C#

A collector can be attached to C programs too. The best known is the Boehm–Demers–Weiser collector. Replace malloc with GC_malloc, delete the frees, and most C programs are said to run as before.³

C has no ledger of “where the pointers are”, so this collector is conservative. Among the words of the stack, the globals and the heap, every value that looks like a pointer is treated as a pointer. A single integer that happens to look like an address can keep a large object alive — an error on the side of reclaiming too little. There is an accident in the other direction as well. What that collector’s documentation warns about directly is programs that hide pointers: writing a pointer to a file and reading it back, memcpying it to a misaligned place, converting a pointer to an integer and back. If the collector cannot see the pointer, it reclaims an object still in use as garbage.

That list overlaps exactly with the provenance story of chapter 38. The technique of turning a pointer into an integer, mixing bits into it and making it a pointer again (the low-bit tags of chapter 4) is the place where the pointer disappears — in the eyes of a collector and in the eyes of a compiler tracking provenance alike. This is why C finds it hard to have a collector by default: as long as the language gives the freedom to treat pointers like integers, the collector’s premise of “finding every pointer” does not hold.

58.10 Closing Part IX#

Part IX, “Deep corners”, is over — how to read operators as contracts (chapter 52), how to put bits to real work (chapter 53), how to handle approximation (chapter 54), how to handle failure (chapter 55), how to know the world outside the contract (chapter 56), and how to sort and govern the memory errors that happen most often in that world (chapters 57–58). The seven chapters share one theme: C is a language that entrusts much to the programmer, and the person who knows what has been entrusted writes safe code.

Five parts remain. Every program so far has been a single file — now it grows into several files (chapter 60), we face the layer of preprocessing and translation (chapter 65), we weigh how to imitate object orientation in C (chapter 70), we learn the terrain of the standard library (chapter 76), we treat proven head on (Part XIII), and we close the book with the practices of modern C (chapter 115).

The next part is the story of composing a program. Its first chapter is the place we have used only as a six-line convention until now — main itself. We see its three forms, and where the value it returns goes.