Skip to content
Computer Internals

Level 2 · Chapter 2.6

Structs, malloc and the heap

Structs and the -> operator, why programs need memory that outlives a function call, and how malloc and free really work: chunk headers, size classes, free lists and the reuse of freed memory — measured on glibc — plus leaks, use-after-free and double free, and how other languages avoid them.

Local variables live on the stack and die when their function returns; globals live forever but have a fixed size, decided at compile time. Real programs need a third kind of memory: blocks whose size is only known at run time, and whose lifetime is decided by the program — created in one function, used in others, released when no longer needed. That's the heap, and in C you manage it by hand with malloc and free.

Heap data is usually a struct, so let's start there.

Structs and ->

A struct groups named fields into one object. The variables chapter showed how the compiler lays out its fields, with padding for alignment. To the machine, a field is just an offset: p.x is "the 4 bytes at offset 4 from the start of p".

Structs are almost always handled through pointers, and C has an operator for it: p->x means (*p).x, "the field x of the struct p points to". At the machine level it's a single instruction with a displacement, like mov eax, DWORD PTR [rax+4]: the base+displacement addressing mode exists for exactly this.

malloc and free

void *malloc(size_t size);   // a block of at least size bytes, or NULL
void  free(void *p);         // give it back

malloc returns a pointer to a new block that nobody else uses. The block stays valid until you pass it to free — whichever function you're in. calloc(n, size) also clears the block to zero, and realloc resizes one, possibly moving it. The bytes malloc returns aren't cleared: they contain whatever was there before.

The classic use is a data structure that grows as the program runs, like a linked list: each node is a struct allocated separately, holding a pointer to the next one.

Live · A linked list on the heap
C source — click a line number for a breakpoint
  1. struct Node {
  2. int value;
  3. struct Node *next;
  4. };
  6. struct Node *push(struct Node *head, int value) {
  7. struct Node *n = malloc(sizeof(struct Node));
  8. n->value = value;
  9. n->next = head;
  10. return n;
  11. }
  13. int main() {
  14. struct Node *list = 0;
  15. list = push(list, 3);
  16. list = push(list, 2);
  17. list = push(list, 1);
  19. int sum = 0;
  20. for (struct Node *p = list; p; p = p->next)
  21. sum = sum * 10 + p->value;
  23. while (list) {
  24. struct Node *next = list->next;
  25. free(list);
  26. list = next;
  27. }
  28. return sum;
  29. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

It returns 123: the list reads 1 → 2 → 3, since each push adds at the front. Unlike the dangling pointer of the previous chapter, the node that push returns stays valid after push returns: it lives on the heap, not in push's frame. Watch the Heap panel as the nodes are created, then marked freed one by one at the end.

What malloc actually does

malloc isn't a system call. It's a library function — in glibc on Linux — that manages a large region of memory obtained from the operating system and carves it into blocks. The simulator's malloc follows the same rules as glibc's on 64-bit Linux, so the numbers below are the same in both.

Every block has a header. The allocator stores the size of each block in the 8 bytes just before the address it returns. A block and its header form a chunk. On 64-bit glibc, chunk sizes are multiples of 16, and the smallest is 32 bytes. Measured with glibc 2.36:

RequestChunk sizeSize field before the blockUsable bytes
malloc(1)320x2124
malloc(24)320x2124
malloc(25)480x3140

The size field is the chunk size with the lowest bit set: sizes are multiples of 16, so the low bits are free to carry flags, and bit 0 records that the previous chunk is in use. Asking for 1 byte uses 32. That waste inside a block is internal fragmentation, the price of fast, aligned allocation. In the list demo above, the Heap panel shows each node's header, 0x21, in front of its 16 bytes.

Freed chunks go on free lists, and get reused. free doesn't return memory to the OS. It puts the chunk on a list of free chunks, sorted by size into bins, and the next malloc of a fitting size takes it back. glibc's fastest lists, the per-thread tcache, are last-in, first-out: free two 8-byte blocks and the next two malloc(8) calls return them in reverse order. That's measured on glibc, and it's what the simulator does too.

The heap grows by asking the OS. When no free chunk fits, glibc extends the heap region, traditionally with the brk system call, which moves the end of the data segment. Large requests — 128 KiB and more by default — skip the heap entirely and get their own pages from mmap. On the test machine, a malloc(10) returned an address next to the program's data, and a malloc(200000) one far away, in the region where shared libraries are mapped. Freeing an mmaped block returns it to the OS immediately.

The general problem is the one Tanenbaum describes for placing memory segments: which free hole to pick for a new block. First fit takes the first hole that's big enough, best fit the smallest one. Both split holes and leave small, useless leftovers, external fragmentation, which allocators fight by coalescing adjacent free chunks into larger ones. Modern allocators add size classes and per-thread caches on top, because malloc is called millions of times per second in real programs and has to be fast.

Heap bugs

The heap gives full control, and full responsibility. Three mistakes are classic.

Leaks. A block that's never freed stays allocated until the process exits. One leak is harmless; a leak in a loop, in a server that runs for months, eventually exhausts memory. Tools like Valgrind and LeakSanitizer (-fsanitize=address) list the blocks still allocated at exit, and where they came from.

Use after free. After free(p), p still holds the same address — nothing clears it — but the memory now belongs to the allocator, which will hand it to the next malloc of that size:

Live · Use after free
C source — click a line number for a breakpoint
  1. struct Account {
  2. int id;
  3. int balance;
  4. };
  6. int main() {
  7. struct Account *a = malloc(sizeof(struct Account));
  8. a->id = 1;
  9. a->balance = 100;
  10. free(a);
  12. struct Account *b = malloc(sizeof(struct Account));
  13. b->id = 2;
  14. b->balance = 999;
  16. return a->balance;
  17. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

It returns 999. b got the same chunk a had, so reading a->balance reads b's account. The program doesn't crash; it silently mixes two objects, which is why use-after-free is one of the most exploited bug classes in browsers and operating systems today: if an attacker controls what gets allocated in the freed chunk, they control what the stale pointer sees. Setting pointers to NULL after free turns later uses into a clean crash.

Double free. Freeing the same block twice puts it on the free list twice, so two future malloc calls would return the same memory. glibc checks for the simple case: the program is stopped with free(): double free detected in tcache 2, and dies with exit status 134, which is SIGABRT. The simulator stops with the same diagnosis.

Writing past the end of a heap block is the heap version of the stack overflow of the pointers chapter: it overwrites the next chunk's header and data. Heap exploits have long targeted the allocator's own metadata. Allocators respond with integrity checks, and since glibc 2.32 with "safe-linking", which scrambles the pointers stored in free chunks.

Other ways to manage memory

Manual malloc and free is fast and predictable, but every block's lifetime is the programmer's problem. Other languages make it someone else's:

  • Garbage collection (Java, Go, JavaScript, Python, C#): the runtime finds blocks that nothing points to anymore and frees them. No leaks of forgotten blocks, no use-after-free, at the cost of runtime work and pauses. It's the subject of the chapter on bytecode virtual machines and garbage collection.
  • Ownership (C++'s RAII and smart pointers, Rust): every block has an owner, and the compiler inserts the free when the owner goes out of scope. Rust's compiler also rejects programs that could use a block after it's freed.
  • Arenas: allocate many objects from one big block and free them all at once, as compilers and game engines often do for per-frame or per-request data.

All of them still rely on something like malloc underneath, to get memory from the OS and carve it up.

Takeaways

  • A struct's fields are offsets; p->x is (*p).x, one load with a displacement.
  • The heap holds blocks whose size is known at run time and whose lifetime the program decides: malloc gives one, free gives it back.
  • malloc is a library that splits OS memory into chunks, each with a size header just before the returned address: 32 bytes minimum on 64-bit glibc, size field 0x21.
  • free puts chunks on free lists (glibc's tcache is last-in, first-out), and the next malloc of that size reuses them. Large blocks come from mmap.
  • Leaks, use-after-free (the old pointer sees the new object) and double free (glibc aborts) are the classic heap bugs.
  • Garbage collection, ownership and arenas are the alternatives to managing lifetimes by hand.

In this level

  1. 2.1Compiled, interpreted and JIT-compiled languages
  2. 2.2From source code to a running binary
  3. 2.3Variables, types and memory layout
  4. 2.4Pointers and arrays
  5. 2.5Functions, calls and the stack
  6. 2.6Structs, malloc and the heap
  7. 2.7Control flow: if, loops, switch
  8. 2.8Bytecode virtual machines and garbage collection