45 Dynamic memory

45.1 Borrowing, and giving back

The syntax is two functions. malloc(number of bytes) borrows that many contiguous slots from the warehouse and returns their starting address, and free(address) gives back what was borrowed.

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

int main(void)
{
    int count = 5;
    int *scores = malloc(count * sizeof *scores);   /* borrowed from the warehouse */

    if (scores == nullptr) {                        /* borrowing can fail */
        printf("allocation failed\n");
        return 1;
    }

    int sum = 0;
    for (int i = 0; i < count; i += 1) {
        scores[i] = (i + 1) * 10;
        sum += scores[i];
    }
    printf("total: %d\n", sum);

    free(scores);                                   /* what is borrowed is returned */
    return 0;
}

total: 150

Three practices are stamped into the demonstration.

Compute the size as sizeof *pointer. count * sizeof *scores is “the size of one element × the count”, asking for the size through the target rather than a type name — so the line needs no fixing later if the type changes.

Borrowing can fail. malloc returns a null pointer when the warehouse is short — so check before writing (chapter 36′s rule becomes practice here). Write without checking and it is a null dereference and collapse.

Give back what you borrowed. Forget free and those slots stay tied up until the program ends — a memory leak. It does not show in a short program, but in a long-running server it seeps away little by little and eventually eats the machine.

45.2 How to write a malloc call — an old argument

There are several ways to write the same allocation, and the C world has argued for thirty years about which is right. Find a piece on this subject online and it is usually heated, because both sides have grounds. Let us measure and decide.

/* Three ways of writing a malloc call — how they differ. */
#include <stdio.h>
#include <stdlib.h>

struct node { int id; double weight; };

int main(void)
{
    /* -- the recommended form: the type name never appears -- */
    struct node *a = malloc(4 * sizeof *a);
    if (!a) return 1;

    /* -- the C++-compatible form: the type name twice -- */
    struct node *b = (struct node *)malloc(4 * sizeof(struct node));
    if (!b) { free(a); return 1; }

    /* -- the compromise: cast, but take the size from the target -- */
    struct node *c = (struct node *)malloc(4 * sizeof *c);
    if (!c) { free(a); free(b); return 1; }

    printf("all three reserve the same size: %zu, %zu, %zu bytes\n",
           4 * sizeof *a, 4 * sizeof(struct node), 4 * sizeof *c);

    puts("\n[sizeof *p does not read p — an unevaluated operand]");
    struct node *nul = NULL;
    printf("  even with p null, sizeof *p computes as %zu\n", sizeof *nul);
    puts("  because the size comes from the TYPE, not from the value.");

    puts("\n[write the name twice and the two can drift apart]");
    puts("  struct node *p = (struct node *)malloc(n * sizeof(struct gadget));");
    puts("  ^ the type name is in two places, so fixing only one is possible.");
    puts("  written as sizeof *p, that accident CANNOT BE WRITTEN.");

    puts("\n[a danger both forms share — overflow in the multiplication]");
    size_t huge = (size_t)-1 / sizeof(struct node) + 1;
    printf("  huge * sizeof *a wraps around to %zu\n", (size_t)(huge * sizeof *a));
    puts("  -> malloc can SUCCEED with a tiny size. Check the count first, or"); 
    puts("     use calloc(count, size), which checks the multiplication itself.");

    free(a); free(b); free(c);
    return 0;
}

all three reserve the same size: 64, 64, 64 bytes

[sizeof *p does not read p — an unevaluated operand]
  even with p null, sizeof *p computes as 16
  because the size comes from the TYPE, not from the value.

[write the name twice and the two can drift apart]
  struct node *p = (struct node *)malloc(n * sizeof(struct gadget));
  ^ the type name is in two places, so fixing only one is possible.
  written as sizeof *p, that accident CANNOT BE WRITTEN.

[a danger both forms share — overflow in the multiplication]
  huge * sizeof *a wraps around to 0
  -> malloc can SUCCEED with a tiny size. Check the count first, or
     use calloc(count, size), which checks the multiplication itself.

45.2.1 Four reasons for form 1

First, when the type changes there is only one place to fix. This is the biggest reason. The Linux kernel’s coding style puts it this way — spelling the type name out “hurts readability and introduces an opportunity for a bug when the pointer variable type is changed but the corresponding sizeof that is passed to a memory allocator is not”.

Think of the common act of changing an int * into a struct node *. Form 1 needs only the declaration changed and the size follows; form 2 needs two places changed, and forgetting one compiles cleanly with too small a block.

Second, the type name never appears, so it cannot drift. This goes one step beyond “only one place to fix” — in form 1 there is no way to write it wrongly.

Third, sizeof *p does not read p. At first sight it looks like dereferencing a pointer that has not been allocated yet. It is not: the operand of sizeof is not evaluated (chapter 49). The listing confirms it — sizeof *p computes fine with p null, because the size comes from the type, not the value.

Fourth, the cast used to hide a bug. Before the standard and in the C89 era, calling malloc without including <stdlib.h> made the compiler assume “a function returning int”. Putting that int into a pointer draws a diagnostic — and the cast wipes that diagnostic away. Reproduced by measurement:

Honesty requires adding that this fourth reason has nearly lost its force today. C99 removed implicit function declarations, and in C23 it is an outright error — measured, error: implicit declaration of function 'malloc' appears with or without the cast. “The cast hides a bug” is now a historical explanation, not a present reason. When a piece still wields it as the clincher, check which decade it is describing.

45.2.2 The case for form 2 — CERT MEM02-C

The other side has standards behind it too. The SEI CERT C Coding Standard’s MEM02-C is titled “Immediately cast the result of a memory allocation function call into a pointer to the allocated type”, and its rationale is this — “casting the result of malloc() to the appropriate pointer type enables the compiler to catch subsequent inadvertent pointer conversions”.

The claim holds. Compile CERT’s own example and the difference is plain.

That the cast promotes a warning into an error is true. But the third row shows the heart of the argument — form 1 needs no diagnostic, because there is no mistake to diagnose. And CERT itself rates this recommendation severity low, likelihood unlikely, priority P3.

45.2.3 Form 3 and the “C++ compatibility” reason — is it real?

The most frequently heard reason for the cast is “because it must build with a C++ compiler too”. C++ does not allow an implicit conversion from void * to another pointer type, so without a cast it genuinely fails to compile — measured, error: invalid conversion from 'void*' to 'int*'.

Three things deserve weighing before accepting that reason.

First, C++ does not recommend malloc in the first place. The way to obtain memory in C++ is new, and more properly containers and smart pointers. So “a malloc call that also builds as C++” means keeping code C++ does not recommend conformant to C++ syntax. It is worth asking what that buys.

Second, the compatibility is not actually obtained. This is decisive. A modern C file with the cast dutifully applied was handed to a C++ compiler:

That is, the cast does not get the file into C++. The ordering constraint on designated initialisers, _Generic, variable length arrays, restrict, compound literals, flexible array members — the two languages have diverged steadily since 1989, and C23 and C++23 are further apart than ever (chapter 96). What one cast buys is not compatibility but the illusion of it.

Third, what is really shared is the header, not the .c file. The realistic place where C and C++ meet is a header (extern "C", chapter 56) — and headers do not call malloc. The calls live in implementation files, and those are compiled by a C compiler.

p = malloc(n * sizeof *p);   /* with a large n the product wraps */

45.3 The alignment of the address returned — because it does not know what will go in

/* The alignment of the address malloc returns, and the price of borrowing and returning */
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 300000

static double seconds_since(struct timespec t0)
{
    struct timespec t1;
    timespec_get(&t1, TIME_UTC);
    return (double)(t1.tv_sec - t0.tv_sec) + (double)(t1.tv_nsec - t0.tv_nsec) / 1e9;
}

static void *volatile sink;      /* holds the allocation so optimisation cannot erase it */

int main(void)
{
    /* ── (1) alignment: not knowing what will be put in it, it gives the strictest ── */
    printf("alignment of max_align_t = %zu bytes\n", alignof(max_align_t));

    size_t misaligned = 0;
    void *p[8];
    for (int i = 0; i < 8; i++) {
        p[i] = malloc(1);                    /* even asking for a single byte */
        if ((uintptr_t)p[i] % alignof(max_align_t) != 0) misaligned++;
    }
    printf("of 8 one-byte requests, ones breaking the default alignment: %zu\n", misaligned);
    printf("address gap between two neighbouring blocks: %td bytes (for a request of 1)\n",
           (char *)p[1] - (char *)p[0]);
    for (int i = 0; i < 8; i++) free(p[i]);

    /* ── (2) the price: the same work three ways ── */
    struct timespec t0;
    unsigned long long acc = 0;

    timespec_get(&t0, TIME_UTC);
    for (int i = 0; i < N; i++) {           /* borrow and return every time */
        char *b = malloc(64);
        if (!b) return 1;
        b[0] = (char)i;
        acc += (unsigned char)b[0];
        sink = b;
        free(b);
    }
    double t_alloc = seconds_since(t0);

    char *reused = malloc(64);
    if (!reused) return 1;
    timespec_get(&t0, TIME_UTC);
    for (int i = 0; i < N; i++) {           /* borrow once and keep using it */
        reused[0] = (char)i;
        acc += (unsigned char)reused[0];
        sink = reused;
    }
    double t_reuse = seconds_since(t0);
    free(reused);

    timespec_get(&t0, TIME_UTC);
    for (int i = 0; i < N; i++) {           /* put it on the stack instead */
        char b[64];
        b[0] = (char)i;
        acc += (unsigned char)b[0];
        sink = b;
    }
    double t_stack = seconds_since(t0);

    printf("\n%d iterations\n", N);
    printf("  malloc + free each time : %7.4f s  (%5.1f ns each)\n", t_alloc, t_alloc / N * 1e9);
    printf("  borrowed once, reused   : %7.4f s  (%5.1f ns each)\n", t_reuse, t_reuse / N * 1e9);
    printf("  a stack array           : %7.4f s  (%5.1f ns each)\n", t_stack, t_stack / N * 1e9);
    printf("\n(total %llu — a value used so the computation is not erased)\n", acc);
    return 0;
}

alignment of max_align_t = 16 bytes
of 8 one-byte requests, ones breaking the default alignment: 0
address gap between two neighbouring blocks: 32 bytes (for a request of 1)

300000 iterations
  malloc + free each time :  0.0036 s  ( 12.0 ns each)
  borrowed once, reused   :  0.0006 s  (  2.0 ns each)
  a stack array           :  0.0007 s  (  2.3 ns each)

(total 114739248 — a value used so the computation is not erased)

The question the first part of the example answers is this. You borrowed a mere one byte with malloc(1) — may that address sit just anywhere?

It may not. Because malloc hands out the place without knowing what will go in. A double may be placed there, or a pointer, or a large struct. So the standard promises this — an address returned by the malloc family satisfies the alignment suitable for any basic type. The name given to that “strictest basic alignment” is max_align_t, and on this machine it is 16 bytes (chapter 6′s alignment rule made flesh).

Two things follow.

First, borrowing small does not mean the place is small. In the example eight one-byte borrowings gave neighbouring blocks 32 bytes apart. It is because of the space left over to satisfy alignment and the management information (size, status) the allocator attaches to each block. It means a program that borrows countless small pieces uses far more memory than it asked for, and that is why the arena and pool approaches we see later were born (chapter 84).

Second, stricter alignment must be requested separately. SIMD instructions or hardware DMA sometimes require 64-byte or 4096-byte alignment, and for that there is C11′s aligned_alloc(alignment, size). Two rules must be kept — the alignment must be a power of two, and in C11 the size had to be a multiple of the alignment (C23 lifted that restriction). What it returns is still given back with free.

45.4 The price of two cheap-looking lines — why allocation is expensive

The latter part of the example repeats the same work three ways, 300,000 times, and measures the time. Borrowing and giving back every time is noticeably slower than reuse or the stack — a little over ten nanoseconds per round on this machine. The value itself differs by machine and allocator, but the fact of a two-orders-of-magnitude difference is the same everywhere.

Why is it expensive? malloc looks like the one line “give me slots” but is in fact one round trip to the warehouse management office.

1. Find a free piece of the right size. The allocator manages returned pieces in lists by size and picks a suitable one when a request comes. Searching the list, cutting a large piece when needed, putting the remainder back in the list — all of it is data-structure manipulation.
2. Write management information. The size and status must be written per block so that free can later know “how many bytes this was.” So allocation involves writing.
3. Ask the operating system when short. When the warehouse is empty it obtains more address space with a system call (brk or mmap). That means going into the kernel and back, which is far more expensive. Fortunately it does not happen often — the allocator takes plenty and cuts it up.
4. With several threads, locks appear. The warehouse ledger is a shared resource, so contention between threads slows it (chapter 80′s story of races). That is why modern allocators keep a small cache per thread.
5. The cache is cold. A freshly obtained address is usually not in the cache, so the first access is slow (chapter 11′s ladder). Conversely a reused buffer is already up in the cache — half the reason the reuse side is fast in the example is here.

So a practical rule follows. Do not allocate inside a hot loop. Borrow once in advance and reuse, put what has a known size on the stack, or borrow many at once and cut them up. The last is the arena, and chapter 84 and Part XII are that story.

45.5 Borrowing in one dimension, using it as two

Chapter 38 showed real multidimensional arrays such as int m[3][4]. But when the size is settled at run time that syntax cannot be used, and so the commonest shape in practice is to borrow one run and read it along two axes.

The heart of it is one line of arithmetic. Borrow rows × cols slots at once and find slot (i, j) as i * cols + j. That is exactly the layout of a real two-dimensional array (row-major, chapter 38) — so the performance is the same and the cache behaves the same way (chapter 11).

/* Allocating in one dimension and using it as two — the commonest shape in practice.
   The subscript arithmetic is shut inside one macro instead of written by hand. */
#include <stdckdint.h>
#include <stdio.h>
#include <stdlib.h>

/* The subscript macro: every argument wrapped in parentheses (chapter 57), and the
   product raised to size_t. i and j are evaluated once, so side effects are safe. */
#define AT(p, cols, i, j)  ((p)[(size_t)(i) * (size_t)(cols) + (size_t)(j)])

/* The size computation can overflow — if it does, no allocation is attempted (ch. 52, 80). */
static int *alloc_grid(size_t rows, size_t cols)
{
    size_t cells, bytes;
    if (ckd_mul(&cells, rows, cols))          return NULL;
    if (ckd_mul(&bytes, cells, sizeof(int)))  return NULL;
    return malloc(bytes);
}

int main(void)
{
    const size_t rows = 3, cols = 4;
    int *g = alloc_grid(rows, cols);
    if (!g) { puts("allocation failed"); return 1; }

    /* ── (1) filling and reading — one macro does the subscripts ─── */
    for (size_t i = 0; i < rows; i++)
        for (size_t j = 0; j < cols; j++)
            AT(g, cols, i, j) = (int)(i * 10 + j);

    printf("a 3x4 held in row-major order:\n");
    for (size_t i = 0; i < rows; i++) {
        printf("  ");
        for (size_t j = 0; j < cols; j++)
            printf("%3d", AT(g, cols, i, j));
        printf("\n");
    }

    /* ── (2) the memory is one continuous run ─────────────────────── */
    printf("\nsweeping the same memory in one dimension: ");
    for (size_t k = 0; k < rows * cols; k++)
        printf(k ? " %d" : "%d", g[k]);
    printf("\n(the same layout as a real int m[3][4] — row-major)\n");

    /* ── (3) the common accident: row and column swapped ──────────── */
    printf("\nAT(g, cols, 1, 2) = %d   (row 2, item 3)\n", AT(g, cols, 1, 2));
    printf("AT(g, cols, 2, 1) = %d   (row 3, item 2 — a different slot)\n", AT(g, cols, 2, 1));

    /* ── (4) an overflowing size request is refused ───────────────── */
    int *huge = alloc_grid((size_t)-1 / 2, 8);
    printf("\nan absurd size request: %s\n", huge ? "allocated" : "refused, the computation overflowed");
    free(huge);

    free(g);
    return 0;
}

a 3x4 held in row-major order:
    0  1  2  3
   10 11 12 13
   20 21 22 23

sweeping the same memory in one dimension: 0 1 2 3 10 11 12 13 20 21 22 23
(the same layout as a real int m[3][4] — row-major)

AT(g, cols, 1, 2) = 12   (row 2, item 3)
AT(g, cols, 2, 1) = 21   (row 3, item 2 — a different slot)

an absurd size request: refused, the computation overflowed

Three things need care here.

First, do not scatter the subscript arithmetic by hand. Write p[i * cols + j] all over the code and the moment one place forgets cols it quietly reads a different slot. Shut it inside one macro, as the example does, and there is one place to fix. When writing the macro, keep chapter 57′s rules — wrap every argument in parentheses, and raise the product to size_t to avoid overflow.

#define AT(p, cols, i, j)  ((p)[(size_t)(i) * (size_t)(cols) + (size_t)(j)])

Second, the size computation itself can overflow. rows * cols * sizeof(int) is a product of three numbers, easy to overflow, and an overflow means borrowing a small vessel and using it as a large array — the worst kind of accident. The example checks with ckd_mul (chapters 52 and 81) first and does not even attempt the allocation if it overflows.

Third, nail down the order of rows and columns in the documentation. AT(g, cols, 1, 2) and AT(g, cols, 2, 1) are different slots. Half the mistakes come from here, so name the parameters rows and cols plainly and write the order down.

45.6 Ownership — who is responsible for giving it back

The address malloc gave can be copied into several variables and can travel between functions. And yet free must be called exactly once — from which comes a core discipline of C programming: fixing one subject that at any moment holds the responsibility for releasing that memory, the notion of ownership. C has no syntax that enforces ownership — so ownership is expressed in comments, names and conventions (“this function transfers ownership of the returned pointer”, and so on). That modern languages lifted ownership into the type system (Rust’s ownership, C++‘s smart pointers) is the result of making the machine enforce this discipline — the concern of the neighbouring languages seen in chapter 1 arose exactly here.

45.7 Closing Part VII

The layout of memory is complete — on the ladder of registers and caches (chapter 11) sit C’s three storage durations (automatic, static, dynamic), and pointers travel over them. We got the concept in chapter 35, the rules in chapters 36–37, contiguous memory and strings in chapters 38–42, a safe component in chapter 43, and lifetime and the warehouse in chapters 44–45. We have gone once round the place where C’s power and its danger live together.

We have seen dynamic memory’s syntax, discipline and price. How an allocator actually manages the warehouse, what alternative allocators and alternative standard libraries are widely used today, and what layout a program’s memory is laid out on in an operating system and in an embedded chip are treated in two chapters at the end of Part XI (chapters 83 and 84).

The next part is short but long deferred — the structs and unions put off in Part V with “declarations that make types come after we have a memory model.” That condition is now met.