Heap Basics

Overview

The heap is a region of memory used for dynamic memory allocation. Unlike stack memory, which grows and shrinks automatically with function calls, heap memory must be explicitly allocated and freed by the programmer using functions like malloc() and free().

glibc malloc Implementation

The GNU C Library (glibc) malloc is the default memory allocator on most Linux systems. It manages heap memory efficiently by organizing freed memory into different bins based on size and reusing previously allocated chunks.

Understanding glibc malloc internals is crucial for heap exploitation, as many vulnerabilities arise from the allocator’s behavior.

Chunk Structure

Every allocation in glibc malloc is represented as a chunk. A chunk contains metadata along with the user data:

struct malloc_chunk {
  size_t      mchunk_prev_size;  /* Size of previous chunk (if free) */
  size_t      mchunk_size;       /* Size in bytes, including overhead */

  struct malloc_chunk* fd;       /* forward pointer (free chunks only) */
  struct malloc_chunk* bk;       /* backward pointer (free chunks only) */

  /* Only used for large blocks */
  struct malloc_chunk* fd_nextsize;
  struct malloc_chunk* bk_nextsize;
};

Key Points

prev_size: Stores the size of the previous chunk if it’s free
size: Contains the chunk size and three flag bits (P, M, N)
fd/bk: Forward and backward pointers form doubly-linked lists of free chunks
User data: Overlaps with fd/bk when the chunk is allocated

The fd and bk pointers are stored in the same memory location as user data when a chunk is allocated. This is why use-after-free vulnerabilities can be so dangerous.

Bin Types

glibc malloc organizes free chunks into different “bins” - data structures that hold freed chunks for efficient reuse.

tcache (Thread Cache)

Size range: Small allocations (up to 1032 bytes on 64-bit)
Structure: Singly-linked list per thread
Count: 64 bins, one per size class
Max chunks: 7 chunks per bin (default)
Performance: Fastest, no thread locking needed

Introduced in glibc 2.26, tcache is checked first before other bins.

fastbins

Size range: 16-80 bytes (64-bit), 8-64 bytes (32-bit)
Structure: Singly-linked list (LIFO)
Count: 10 bins
Coalescing: Chunks are NOT merged with adjacent free chunks
Performance: Fast, but slower than tcache

smallbins

Size range: Less than 1024 bytes (64-bit)
Structure: Doubly-linked list (FIFO)
Count: 62 bins
Coalescing: Chunks ARE merged with adjacent free chunks
Exact fit: Each bin contains one specific size

largebins

Size range: 1024 bytes and larger (64-bit)
Structure: Doubly-linked list sorted by size
Count: 63 bins
Coalescing: Chunks ARE merged with adjacent free chunks
Size range: Each bin contains a range of sizes

unsorted bin

Purpose: Temporary storage for recently freed chunks
Structure: Single doubly-linked list
Count: 1 bin
Behavior: Chunks are sorted into appropriate bins on next malloc

Allocation Mechanics

When you call malloc(size), glibc follows this allocation strategy:

Check tcache

If tcache has a chunk of the requested size, return it immediately.

Check fastbins

If the size fits a fastbin and one exists, return the head chunk.

Small request

For small sizes, check the corresponding smallbin. If empty, check unsorted bin.

Large request

For large sizes, check largebins using best-fit or exact-fit search.

Top chunk

If no suitable chunk found, split off memory from the top chunk (wilderness).

Extend heap

If top chunk is too small, extend the heap using sbrk() or mmap().

Free Mechanics

When you call free(ptr), glibc performs several operations:

Validation

Check if the pointer and chunk metadata are valid.

tcache insertion

If tcache for this size isn’t full, add the chunk and return.

Fastbin insertion

If the size fits fastbin range, add to the appropriate fastbin (LIFO).

Coalescing

Merge the chunk with adjacent free chunks (backward and forward).

Unsorted bin

Place the consolidated chunk in the unsorted bin.

Top chunk merge

If the freed chunk is adjacent to the top chunk, merge it back.

Coalescing is disabled for fastbins and tcache, making them faster but also creating opportunities for exploitation.

Size Calculations

The actual chunk size differs from the requested size:

#define SIZE_SZ (sizeof(size_t))
#define MALLOC_ALIGNMENT (2 * SIZE_SZ)
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
#define MINSIZE (offsetof(struct malloc_chunk, fd_nextsize))

#define request2size(req) \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
   MINSIZE : \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

// malloc(0x10) allocates minimum chunk
MINSIZE = 0x20
MALLOC_ALIGNMENT = 0x10

request = 0x10
chunk_size = (0x10 + 0x8 + 0xf) & ~0xf
chunk_size = 0x27 & ~0xf = 0x20

// malloc(0x88) calculation
request = 0x88
chunk_size = (0x88 + 0x8 + 0xf) & ~0xf
chunk_size = 0x9f & ~0xf = 0x90

Key Concepts for Exploitation

Many heap exploits rely on understanding these fundamental behaviors:

First-fit allocation: malloc reuses the first suitable free chunk
Use-after-free: Freed memory retains pointers (fd/bk) that overlap with user data
Chunk coalescing: Adjacent free chunks are merged (except fastbins/tcache)
Metadata corruption: Overwriting chunk headers can hijack control flow
Bin manipulation: Corrupting bin lists can cause malloc to return arbitrary addresses

Next Steps

Malloc Playground

Interactive tool to experiment with allocations

First Fit

Understanding first-fit allocation strategy

tcache Index

How tcache indices are calculated

Techniques

Explore heap exploitation techniques

Get Started

Fundamentals

Fastbin Techniques

Tcache Techniques

House Techniques

Bin & Chunk Manipulation

Advanced Techniques

Glibc Versions

Tools & Resources

Overview

glibc malloc Implementation

Chunk Structure

Key Points

Bin Types

Allocation Mechanics

Free Mechanics

Size Calculations

Key Concepts for Exploitation

Next Steps

Malloc Playground

First Fit

tcache Index

Techniques

​Overview

​glibc malloc Implementation

​Chunk Structure

​Key Points

​Bin Types

​Allocation Mechanics

​Free Mechanics

​Size Calculations

​Key Concepts for Exploitation

​Next Steps

Malloc Playground

First Fit

tcache Index

Techniques

Overview

glibc malloc Implementation

Chunk Structure

Key Points

Bin Types

Allocation Mechanics

Free Mechanics

Size Calculations

Key Concepts for Exploitation

Next Steps