Skip to main content
Be Bitwise

Heap Allocation Basics

Heap Vulnerabilities & Use-After-Free · Exploitation Fundamentals track

12 min read

Part ofSystems Programming Companion, week 11

In this module

Dynamic Memory on the Heap

The heap is where programs keep data whose lifetime doesn't fit the stack's rigid enter/exit discipline. Stack memory comes and goes with function calls. Heap memory is handed out by malloc and handed back by free, and the program decides when. Get the bookkeeping wrong, which is surprisingly easy, and you're in vulnerability territory.

This module looks at one allocator in detail: ptmalloc2, the allocator inside GNU libc. It descends from Doug Lea's dlmalloc by way of Wolfram Gloger's ptmalloc, and it serves malloc for nearly every C and C++ program on a Linux desktop or server. Everything here describes glibc 2.35 on x86-64, the version Ubuntu 22.04 ships. The labs run on Ubuntu 24.04, which ships glibc 2.39; the structures and checks this module relies on are the same there. Allocators do change between releases, though, so when you attack a real target, read malloc/malloc.c for the exact version it links against. That one file is the ground truth, and it's better commented than its reputation suggests.

The Bump Allocator Hiding Inside malloc

The simplest possible allocator is a bump allocator. It keeps one pointer to the start of unused memory. A request returns the current pointer and advances it by the requested size. No reuse, no lists, nothing to corrupt.

ptmalloc2 has one of these at its core. It's called the top chunk: a single large free chunk at the end of the heap. When nothing better is available, malloc slices the front off the top chunk and moves the top's start forward, which is a bump allocation in all but name.

Notice the jumps are 0x50 bytes, though each request asked for 0x40. Those extra 16 bytes are where the trouble starts.

The Chunk

Every allocation lives inside a chunk. glibc describes a chunk with this struct from malloc/malloc.c (comments trimmed):

c
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd;
struct malloc_chunk* bk;
struct malloc_chunk* fd_nextsize;
struct malloc_chunk* bk_nextsize;
};

On x86-64, INTERNAL_SIZE_T is 8 bytes and so is a pointer, which gives these offsets from the start of the chunk:

OffsetFieldWhen it means something
0x00prev_sizeOnly while the chunk before this one is free (and not in tcache or a fastbin)
0x08sizeAlways. Low three bits are flags
0x10fdOnly while this chunk is free. This is also where the user pointer points
0x18bkOnly while free, and only in doubly linked bins
0x20fd_nextsizeOnly for free chunks in the large bins
0x28bk_nextsizeSame

The struct is a lie of convenience. An allocated chunk doesn't contain fd or bk at all: from offset 0x10 onwards the bytes belong to your program. malloc returns chunk + 0x10, and free(p) finds the header again by computing p - 0x10. glibc calls those two conversions chunk2mem and mem2chunk, and you'll see both names in the source.

That's the whole design in one sentence: the allocator's metadata sits in the same memory as user data, separated by nothing but arithmetic. Free chunks store their list pointers inside the space your object used to occupy. Lesson 2 shows what that means for a pointer you forgot to clear.

Sizes and Rounding

A request of n bytes becomes a chunk of size (n + 8 + 15) & ~15, with a floor of 0x20. Chunks are 16-byte aligned on x86-64 (MALLOC_ALIGNMENT is 16) and the smallest chunk, MINSIZE, is 0x20 bytes.

RequestChunk sizeUsable bytes
malloc(0)0x200x18
malloc(0x18)0x200x18
malloc(0x19)0x300x28
malloc(0x40)0x500x48
malloc(100)0x700x68

Why only 8 bytes of overhead when the header is 16? Because the prev_size field of the next chunk only matters when this chunk is free. While this chunk is in use, its owner gets to borrow those 8 bytes. So malloc(0x18) returns a pointer to 0x18 usable bytes inside a 0x20 chunk, and the last 8 of those bytes overlap the next chunk's prev_size. It's a tidy trick. It also means an off-by-one write at the end of a buffer lands directly on the neighbouring chunk's size field, which lesson 4 exploits.

The Three Flag Bits

Sizes are always multiples of 16, so the bottom four bits of size would always be zero. glibc reuses three of them:

BitNameMeaning
0x1PREV_INUSEThe chunk immediately before this one in memory is in use
0x2IS_MMAPPEDThis chunk came straight from mmap and isn't part of any heap
0x4NON_MAIN_ARENAThis chunk belongs to a thread arena, not the main arena

So a size field of 0x51 means "this chunk is 0x50 bytes and the chunk below it is in use". Read the flags off before you read the size, every time. Tools such as pwndbg print them for you, but checkpoint questions and CTF dumps won't.

PREV_INUSE is the important one for attackers. When free decides whether to merge a chunk with its lower neighbour, it doesn't look at the neighbour. It looks at its own PREV_INUSE bit, and if that's clear, it trusts prev_size to say where the neighbour starts. Two attacker-writable values steer a merge. There's one subtlety: chunks sitting in tcache or a fastbin still count as "in use" for this bit, because those caches deliberately skip merging. Only chunks that reach the unsorted, small or large bins clear their neighbour's PREV_INUSE.

Reading a Real Chunk Dump

Here's a fresh program on glibc 2.35 that does a = malloc(0x40); b = malloc(0x40); and fills a with A characters. In gdb, x/2gx prints two 8-byte words per line. Addresses are illustrative (ASLR moves the heap every run), but the layout and values match what you'd see in an unmodified program that hasn't touched stdio yet.

text
0x55555555b000: 0x0000000000000000 0x0000000000000291 <- tcache_perthread_struct chunk
... 0x280 bytes of tcache counters and list heads ...
0x55555555b290: 0x0000000000000000 0x0000000000000051 <- chunk a header
0x55555555b2a0: 0x4141414141414141 0x4141414141414141 <- a points here
0x55555555b2b0: 0x4141414141414141 0x4141414141414141
0x55555555b2c0: 0x4141414141414141 0x4141414141414141
0x55555555b2d0: 0x4141414141414141 0x4141414141414141
0x55555555b2e0: 0x0000000000000000 0x0000000000000051 <- chunk b header
0x55555555b2f0: 0x0000000000000000 0x0000000000000000 <- b points here
...
0x55555555b330: 0x0000000000000000 0x0000000000020cd1 <- top chunk

Three things to pick out:

  • The first chunk on the heap is 0x290 bytes (size field 0x291). That's the tcache_perthread_struct, the per-thread cache glibc allocates the first time a thread calls malloc. Every glibc heap since 2.26 starts with one; from 2.30 onwards it's exactly this size. Seeing 0x291 at the start of a heap dump is a quick way to orient yourself.
  • a is at 0x55555555b2a0, but its chunk starts 16 bytes earlier at 0x55555555b290. The value at 0x55555555b298 is 0x51: size 0x50, previous chunk in use.
  • The top chunk's size field reads 0x20cd1. The first sbrk grew the heap by 0x21000 bytes (132 KiB), and 0x21000 minus the 0x330 already handed out is 0x20cd0. Add PREV_INUSE, and you've got the value on screen.
Predict: if the program now calls malloc(0x28), what address does it get back, and what value appears 8 bytes before it?

Answer. 0x28 bytes rounds up to a 0x30 chunk. No freed chunks of that size exist, so malloc carves from the top chunk at 0x55555555b330. It returns 0x55555555b340, and the size field at 0x55555555b338 reads 0x31: 0x30 bytes, previous chunk (b) in use. The top chunk moves to 0x55555555b360 with size 0x20ca1.

Free List

A free list tracks chunks that are available for reuse. When memory is freed, the allocator links the chunk into a list instead of handing it back to the kernel, and later requests check those lists before carving new memory. ptmalloc2 keeps many lists, called bins, sorted by size, and stores the links inside the freed chunks themselves. Recycling makes the allocator fast. It also creates the conditions for use-after-free.

The Bins, Briefly

ptmalloc2 sorts free chunks into five kinds of bin. Lesson 2 opens up the first two, and lesson 4 covers the unsorted bin.

  • tcache (since glibc 2.26): a per-thread, singly linked cache. 64 bins, one per size from 0x20 to 0x410, each holding at most 7 chunks by default. No locking, minimal checks, and the first place both malloc and free look.
  • Fastbins: singly linked, per arena, for small chunks up to 0x80 bytes by default. Used once the matching tcache bin is full.
  • Unsorted bin: a single doubly linked list where most other freed chunks land first. malloc sorts it lazily.
  • Small bins: 62 doubly linked lists, one exact size each, below 0x400 bytes.
  • Large bins: doubly linked, each covering a range of sizes from 0x400 upwards, kept sorted by size with the extra fd_nextsize/bk_nextsize links.

The malloc Path

When you call malloc(n) on glibc 2.35, the request walks a fixed sequence. The function names are real; read them alongside the source.

  1. __libc_malloc converts n to a chunk size and computes the tcache index. If that tcache bin has a count above zero, tcache_get pops the head and returns it. This is the fast path, and for most small allocations it's the only one that ever runs. (__malloc_hook used to be checked here too. glibc 2.34 removed the hooks, and that change matters in lesson 3.)
  2. Otherwise _int_malloc takes over. If the size is in fastbin range and the fastbin has a chunk, it takes it. Any other chunks left in that fastbin are moved into the tcache bin while it's at it.
  3. If the size is in small-bin range and that small bin is non-empty, it takes from there, again stashing extras into tcache.
  4. It walks the unsorted bin. An exact fit is used (or stashed into tcache if there's room, then returned at the end). Every chunk that isn't an exact fit gets sorted into its small or large bin.
  5. It searches the large bins and then a bitmap of non-empty bins for the smallest chunk that's big enough, splitting it and putting the remainder back in the unsorted bin.
  6. If all else fails, it splits the top chunk, and if the top chunk is too small, sysmalloc grows the heap with sbrk (or mmap for secondary arenas).

Requests of 128 KiB and over skip all of this. Above M_MMAP_THRESHOLD, whose default is 128 KiB, glibc maps the chunk directly with mmap and sets IS_MMAPPED. The threshold moves upwards dynamically once a program frees such chunks, so treat 128 KiB as a starting value.

The free Path

free(p) runs in a similar order:

  1. __libc_free returns immediately for NULL. If the chunk has IS_MMAPPED set, it's handed straight back to the kernel with munmap.
  2. _int_free sanity-checks the pointer and size: the chunk must be aligned, its size can't be below MINSIZE or so large it wraps the address space. Failures abort with messages such as free(): invalid pointer and free(): invalid size.
  3. If a tcache bin exists for the size, glibc checks for a double free (lesson 2 covers how), and if the bin holds fewer than 7 chunks it calls tcache_put and returns. No merging, no neighbour checks.
  4. If the size is in fastbin range, the chunk is pushed onto the fastbin, after a check that it isn't already at the head of that list.
  5. Anything else is merged with free neighbours on either side, guided by PREV_INUSE and prev_size, and the result goes on the unsorted bin. A chunk that borders the top chunk is absorbed into the top instead.

Both paths do their cheapest work first, and the cheapest work comes with the fewest checks. tcache sits at the front of both, which is why it's the favourite target in modern heap exploitation.

Arenas and Threads

Each set of bins belongs to an arena. The main arena is a static structure called main_arena inside libc's data section, and it manages the sbrk heap. When threads contend for it, glibc creates more arenas backed by mmap, up to a default limit of eight per CPU core on 64-bit systems. Chunks from those arenas carry the NON_MAIN_ARENA bit so that free can find their owner. The tcache sits in front of all of them, one per thread, which is why it needs no lock.

The main arena living inside libc has a pleasant side effect for attackers. Any free chunk whose list pointers point back at a bin head in main_arena contains a libc address, and leaking one tells you where libc is loaded. Lesson 4 uses exactly that.

What Can Go Wrong

Stack memory is disciplined: allocation and deallocation are tied to function entry and exit. Heap memory puts that responsibility on the programmer. Forget to free: memory leak. Free twice: double free. Touch memory after freeing it: use-after-free. Write past the end: heap overflow, and on this heap the next thing past the end is another chunk's size field.

Each of those bugs gives an attacker a way to edit allocator metadata, and the allocator acts on its metadata with the full privileges of the program. The rest of this module walks through how that plays out, starting with what free actually writes into memory you thought you'd finished with.