Understanding the Heap Internals

So far in this series, we've exploited the stack buffer overflows, ROP chains, format strings. The stack is predictable: local variables go in, function returns pop them out, everything follows a strict LIFO order.

The heap is a completely different beast. It's dynamic memory malloc() and free(). Programs request memory of arbitrary sizes at arbitrary times and free it in any order. The heap allocator has to manage this chaos efficiently, and the bookkeeping metadata it uses to track allocations is exactly what attackers target.

Heap exploitation is how most modern exploits work. Browser exploits, kernel exploits, server exploits the majority involve heap corruption. The stack is too well-protected (canaries, ASLR, DEP). The heap is where the action is.

But before we can exploit the heap, we need to understand how it works. This article covers the internals of glibc's malloc (ptmalloc2) the default allocator on Linux. The next article covers the actual exploitation techniques.

I know. This going to be a very lengthy article, BTW I did not want to split this into multiple posts. Here you can find the whole complete idea about the heap you need for the Heap based buffer overflows.

Stack vs Heap

Stack:.

• Fixed size (usually 8MB per thread)
• Grows/shrinks automatically with function calls
• LIFO order (Last In - First Out)
• Managed by the compiler (push/pop)
• Local variables, function arguments, return addresses

Heap:

• Dynamic size (grows as needed)
• Allocated/freed explicitly by the programmer
• No ordering
• Managed by the allocator (malloc/free)
• Dynamically sized data, objects, buffers

To understand the differences lets consider a simple C function.

void memoryAllocation() {
    int x = 42;                    // Stack — automatic, freed when function returns

    char *buf = malloc(256);       // Heap — manual, stays until free() is called
    free(buf);                     // Programmer must free explicitly
}

The stack is simple. The heap is complex. And complexity breeds vulnerabilities.

malloc() and free() — The Interface

The programmer sees a simple API:

void *malloc(size_t size);                 // Allocate 'size' bytes, return pointer
void free(void *ptr);                      // Free previously allocated memory
void *realloc(void *ptr, size_t size);     // Resize allocation
void *calloc(size_t nmemb, size_t size);   // Allocate and zero-initialize

Behind this simple interface, glibc's malloc maintains a sophisticated system of chunks, bins, and arenas to manage memory efficiently.

Understanding the Chunks.

The first and most important concept in this tutorial is the chunk. As the first step we are going to see what is a chunk and how it looks like.

Every malloc() allocation is wrapped in a chunk.

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=4>...</block>
<block size=4>Chunk 1</block>
<block size=4>Chunk 2</block>
<block size=4>Chunk 3</block>
<block size=4>Chunk 4</block>
<block size=4>Chunk 5</block>
<block size=4>...</block>

Each chunk contains metadata (header) and the user data.

Allocated Chunk Layout

The actual layout of a chunk is something like below.

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=4>...</block>
<block size=8>Meta Data</block>
<block size=32>User Data</block>
<block size=4>...</block>

<ptr index=2>malloc( ) pointer</ptr>

We know that whenever we use malloc() function we recieve a pointer. (If memory allocation was success). This pointer is always pointed to the user data. Not to the starting of the chunk. In the 32 bit architecture the meta data is 8 bytes in size. So, if we want to get the address of the starting point of the chunk we have do substract 8 from the pointer which is returned by malloc(). We need to keep this in mind.

Now lets dive deep in to the chunk and see how it looks like.

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=4>...</block>
<block size=4>Prev size</block>
<block size=4>Size + Flags</block>
<block size=32>User Data</block>
<block size=16>Padding</block>
<block size=4>...</block>

<ptr index=1>ptr - 8</ptr>
<ptr index=2>ptr - 4</ptr>
<ptr index=3>malloc() pointer</ptr>
<ptr index=5>ptr + size - 8</ptr>

The meta data section has two parts,

Prev size

This indicates the size of the previous chunk. Actually this does not represent the size always. I'll explain it later. For now keep in mind this represents the size of the previous chunk.

prev_size stores the size of the previous chunk in memory. But only when that previous chunk is free. When the previous chunk is allocated, this 4-byte field is recycled as extra user data by the previous chunk (the prev_size overlap optimization). This is not a bug. It is intentional and documented in the allocator source. The PREV_INUSE flag in the current chunk's size field is the authoritative signal for whether prev_size is valid metadata or live user data. Off-by-one heap overflows are dangerous precisely because corrupting the prev_size of the next chunk can cause the allocator to miscompute chunk boundaries during consolidation.

Size + Flags

As the name suggests, this indicates the size field stores the chunk's total size, but the bottom 3 bits are repurposed as flags.

Wait. How that is possible? Let me explain.

The chunk size is always a multiplication of 8. Such as 8 bytes, 16 bytes, 24 bytes etc.

$$ 8_{10} = 00001000_2 $$

$$ 16_{10} = 00010000_2 $$

$$ 24_{10} = 00011000_2 $$

$$ 32_{10} = 00100000_2 $$

So the last 3 bits of the size would always be zero. We can use these three bits as the space for the flags.

Actual Size in bytes + | A | M | P |

The PREV_INUSE bit is critical for exploitation. It tells the allocator whether the chunk before this one is free.

Lets consider an example, We see following as the metadata for the current chunk.

 size + flags = 0x00000021

Now,

$$ 00000021_{16} = 33_{10} $$

So this does not mean the actual size is 33 bytes.

To get the actual size, we need to convert it into binary and disregard the last three bits,

$$ 33_{10} = 0100001_2 $$

After removing the last three digits it is 0100000.

$$ 0100000_2 = 32_{10} $$

In a programmatically we can say this in below way,

We can use the bitwise AND operator with 11111000 to get rid of the last three bits.

$$ 0100001_{2} \land 11111000_{2} $$

Size of allocation

Here I have the actual code snippet which is used in malloc(). Lets see how it allocate the memory.

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

If we consider a 32 bit environment the values of these constants are as follow.

• SIZE_SZ = 4 bytes
• MALLOC_ALIGNMENT = 8 bytes
• MALLOC_ALIGN_MASK = 7 bytes
• MINSIZE = 16 bytes

SIZE_SZ is the word size. Which means 4 bytes in 32 bit environment. MALLOC_ALIGNMENT is simply the double of the word size. The MINSIZE is the minimum size allocated for a chunk. Also MALLOC_ALIGN_MASK is simply MALLOC_ALIGNMENT - 1.

Now, it's time to see an example.

We are going to allocate a chunk with the size 14 bytes. So, we call malloc(14). Let say this is $chunk A$.

size = (14 + 4 + 7 < 16) ? 16 : (14 + 4 + 7) & ~7)

     = 25 & ~7

7   = 0000 0000 0000 0000 0000 0000 0000 0111
~7  = 1111 1111 1111 1111 1111 1111 1111 1000

25       = 0000 0000 0000 0000 0000 0000 0001 1001
~7       = 1111 1111 1111 1111 1111 1111 1111 1000

25 & ~7  = 0000 0000 0000 0000 0000 0000 0001 1000

So the allocated size for the chunk is 24 bytes. That means for this chunk, we actually allocate 24 bytes. What is the user data section's size? To get this we need to deduct 8 bytes from the allocated chunk size. These 8 bytes are allocated for the meta data section.

Chunk size       = 24 bytes

User data size   = 24 - 4 x 2 
                 = 16 bytes

That means we give 16 bytes for the user data section. Even we allocate 16 bytes, we may use 14 bytes right? Because 14 is the number of bytes we asked. Then 2 bytes will be kept as a padding.

Padding          = 16 - 14 
                 = 2 bytes

Next, we are going to allocate a chunk with the size 12 bytes. Let say this is $chunk B$.

size = (12 + 4 + 7 < 16) ? 16 : (12 + 4 + 7) & ~7)

     = 23 & ~7

23        = 0000 0000 0000 0000 0000 0000 0001 0111
7         = 0000 0000 0000 0000 0000 0000 0000 0111
~7        = 1111 1111 1111 1111 1111 1111 1111 0000 

23 & ~7   = 0000 0000 0000 0000 0000 0000 0001 0000

So the allocated size for the chunk is 16.

Chunk size          = 16 bytes

User data size      = 16 - 4 x 2
                    = 8 bytes

Here we can see that the size allocated for user data is just 8 bytes. But we requested 12 bytes to be allocated right? What's wrong with the libc malloc()?

Actually this is not a bug. There is a special concept I want to highlight. We know that these chunks are adjacent right. There is a next chunk to the current one. Let's consider this layout.

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=1>...</block>
<block size=4>Prev size</block>
<block size=4>Size + Flags</block>
<block size=24>User Data</block>
<block size=12>Padding</block>

<block size=4>Prev size</block>
<block size=4>Size + Flags</block>
<block size=24>User Data</block>
<block size=12>Padding</block>
<block size=1>...</block>

<ptr index=1>Chunk 1 starts here</ptr>
<ptr index=5>Chunk 1 ends & Chunk 2 starts here</ptr>
<ptr index=9>Chunk 2 ends here</ptr>

Chunk 2's prev_size flag is only meaningful if Chunk 1 is not in use. That means we only use this prev size flag for freeing the memory. What does that mean? If the chunk 1 is in use, we actually don't need the space allocated for chunk 2's prev_size flag. Hmm.., interesting. In this case we can use chunk 2's prev_size flag space for chunk 1.

We call this concept Borrowing. We simply ask some unused free space form the neighbor chunk.

Actual usable data size    = 8 + 4 
                           = 12 bytes

Lets see one another example, this time we are requesting 20 bytes for the $chunk C$.

size = (20 + 4 + 7 < 16) ? 16 : (20 + 4 + 7) & ~7)

     = 31 & ~7

31        = 0000 0000 0000 0000 0000 0000 0001 1111
7         = 0000 0000 0000 0000 0000 0000 0000 0111
~7        = 1111 1111 1111 1111 1111 1111 1111 1000

31 & ~7   = 0000 0000 0000 0000 0000 0000 0001 1000

So the allocated size for the chunk is 24 Bytes.

Chunk size          = 24 bytes

User data size      = 24 - 4 x 2
                    = 16 bytes

Usable data size    = 16 + 4 
                    = 20 bytes

Finally I'm going to request 40 bytes for the $Chunk D$. I took several different cases so we can clearly see this.

size = (40 + 4 + 7 < 16) ? 16 : (40 + 4 + 7) & ~7)

     = 51 & ~15

51        = 0000 0000 0000 0000 0000 0000 0011 0011
7         = 0000 0000 0000 0000 0000 0000 0000 0111
~7        = 1111 1111 1111 1111 1111 1111 1111 1000

51 & ~7   = 0000 0000 0000 0000 0000 0000 0011 0000

So the allocated size for the chunk is 48 Bytes.

Chunk size          = 48 bytes

User data size      = 48 - 4 x 2
                    = 40 bytes

Padding size        = 40 - 40
                    = 0 bytes

Usable data size    = 40 + 4 
                    = 44 bytes

Now we know how the malloc() works and how does it allocate some memory for us. Now things are getting more interesting. We need to learn what happens when we call free(). How does the memory area get freed? There are two important points we need to learn. Bins and Tcache. More specifically we can say these are the key points we need.

• unsorted / small / large bins
• fastbins
• tcache (modern glibc, default)

Understanding the Bins

When we call free(), the memory doesn't go back to the operating system immediately. Instead, glibc keeps it in a bin which is a free list it drains before ever asking the kernel for more memory. This makes repeated malloc()/free() cycles fast: the allocator reuses cached chunks instead of calling sbrk() every time.

There are four types of bins.

• Fast bins
• Unsorted bins
• Small bins
• Large bins

The Fast bin is a new concept introduced to the libc. Before that there were Unsorted bins, Small bins and Large bins. Let me explain these three first.

Just forget there is nothing called Fast bin. When we call free(), all chunks goes to the unsorted bin. Then from the unsorted bin, we put them into Large bin or Small bin in a later step. I'll explain this sorting mechanism later.

What happens when we introduce the Fast bin concept. There are some chunks which in a range of size those are going to the fat bin directly. They don't touch the unsorted bin.

Each bin type handles a different chunk size range. Here is the full picture before we dive into each one:

Now, it's the time to understand each of these separately and deeply.

Fast Bins

A fast bin is made of a linked list. More specifically a singly linked list. That means the fast bin section is a collection of linked lists.

Yes, finally an actual usage of Linked lists :).

For the chunks which have the size 0x10, there is a separate linked list (Fast bin). Similarly, for the chunks which have the size 0x20, there is another linked list.

With MALLOC_ALIGNMENT = 16 (glibc ≥ 2.26, 32-bit), valid fastbin chunk sizes are multiples of 16:

MAX_FAST_SIZE  = 80 * SIZE_SZ / 4
               = 80 * 4 / 4
               = 80

DEFAULT_MXFAST = 64 * SIZE_SZ / 4 
               = 64 * 4 / 4 
               = 64

MINSIZE        = 16
step           = MALLOC_ALIGNMENT = 8

So any chunk of size 16 through 64 (multiples of 8) is a Fast bin candidate by default.

The bin index for a given chunk size is:

cfastbin_index(sz) = (sz >> 3) - 2

By default only the first 7 are normally used (DEFAULT_MXFAST = 64 bytes on 32-bit), but the array itself always contains 10 entries. The same NFASTBINS value of 10 applies on 64-bit as well (just with larger size steps).

Remaining three indices ...

And one another important thing is fastbins are LIFO. That means last freed, first allocated.

The layout of a chunk after it is moved into a fast bin is below.

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=1>...</block>
<block size=4>Prev size</block>
<block size=4>Size + Flags</block>
<block size=4>fd</block>
<block size=12>Padding</block>
<block size=1>...</block>

<ptr index=1>ptr - 8</ptr>
<ptr index=2>ptr - 4</ptr>
<ptr index=3>malloc( ) pointer</ptr>
<ptr index=5>ptr + size -8</ptr>

As I mentioned there is a one pointer called fd. And it is placed at the user data section. Since the userdata section is not intended to be used after free() call, that region is repurposed by the allocator to store the fd pointer.

So, what does this fd pointer do? lets see.

To understand the concepts, we are going to use the following examples.

You may wondering why the Prev Size is empty in each. This is because Prev Size is useful only after these chunks are free. Wheen these are in use there is no point of keeping the prev size data.

Now, let's say these are in memory at the following addresses. The chunk starts 8 bytes before the user pointer:

Lets consider all of these chunks are allocated.Therefore all bins are empty.

fastbinsY[0]:  NULL
fastbinsY[2]:  NULL
fastbinsY[6]:  NULL

Freeing the chunk A

Since the size of the chunk is 32 bytes, it should go to the fast bin which is the index is 2 (fastbinsY[2]).

fastbinsY[2] is currently NULL. The allocator writes fd = NULL into A's user data region and updates fastbinsY[2] to point to A's chunk.

Memory at 0x5655a1a0 (A's chunk): 0x5655a1a0: 0x00000000 0x00000021 0x00000000 prev_size size|flags fd = NULL

fastbinsY[0]:  NULL

fastbinsY[2]:  0x5655a1a0  →  NULL
                   A

fastbinsY[6]:  NULL

Freeing the chunk C

The chunk C's size is also 32 bytes, it should go to the fast bin which is the index is 2 (fastbinsY[2]).

fastbinsY[2] currently points to A (0x5655a1a0). The allocator writes the current head into C's fd, then sets fastbinsY[2] to C.

fastbinsY[0]:  NULL

fastbinsY[2]:  0x5655a1d0  →  0x5655a1a0  →  NULL
                   C              A

fastbinsY[6]:  NULL

Freeing the chunk E

Same process. E's fd gets C's address.

fastbinsY[0]:  NULL

fastbinsY[2]:  0x5655a230  →  0x5655a1d0  →  0x5655a1a0  →  NULL
                   E               C              A

fastbinsY[6]:  NULL

Freeing the chunk B

Since the size of the chunk is 16 bytes, it should go to the fast bin which is the index is 1 (fastbinsY[1]). It is a completely separate list.

fastbinsY[0]:  0x5655a1c0  →  NULL
                   B

fastbinsY[2]:  0x5655a230  →  0x5655a1d0  →  0x5655a1a0  →  NULL
                   E               C              A

fastbinsY[6]:  NULL

Freeing the chunk D

D is 0x40 bytes → fastbinsY[6].

fastbinsY[0]:  0x5655a1c0  →  NULL
                   B

fastbinsY[2]:  0x5655a230  →  0x5655a1d0  →  0x5655a1a0  →  NULL
                   E               C              A

fastbinsY[6]:  0x5655a1f0  →  NULL
                   D

Freeing the chunk F

F is 0x20 bytes → fastbinsY[2]. F becomes the new head, its fd gets E's address.

fastbinsY[0]:  0x5655a1c0  →  NULL
                   B

fastbinsY[2]:  0x5655a250  →  0x5655a230  →  0x5655a1d0  →  0x5655a1a0  →  NULL
                   F              E               C              A

fastbinsY[6]:  0x5655a1f0  →  NULL
                   D

Now we have above state. We need to see what happens when we are going to re allocate a memory.

Allocating a memory from Fast bin

Now lets call malloc(24) to see what happens.

(24 + 4 + 7) & ~7  =  35 & ~7  
                   =  32  
                   =  0x20  →  fastbinsY[2]

It pops the head of fastbinsY[2] which is F and updates the bin head to F's fd (= E's address). Then it returns 0x5655a258 (F's user pointer = F's chunk address + 8).

fastbinsY[0]:  0x5655a1c0  →  NULL
                   B

fastbinsY[2]:  0x5655a230  →  0x5655a1d0  →  0x5655a1a0  →  NULL
                   E               C              A

fastbinsY[6]:  0x5655a1f0  →  NULL
                   D

What happens we call malloc(24) again?

Now pops the head of fastbinsY[2] which is F and updates the bin head to E's fd (= C's address). Then it returns 0x5655a238 (E's user pointer = E's chunk address + 8).

fastbinsY[0]:  0x5655a1c0  →  NULL
                   B

fastbinsY[2]:  0x5655a1d0  →  0x5655a1a0  →  NULL
                   C              A

fastbinsY[6]:  0x5655a1f0  →  NULL
                   D

Free order was: A → C → E → F
Return order is: F → E → C → A

This means the fast bin behaves in LIFO order.

Key properties:

• No coalescing : adjacent free chunks in fast bins are NOT merged together
• LIFO order : free(a); free(b); malloc(same_size) returns b (last freed, first out)
• Singly linked : only fd, no bk
• PREV_INUSE bit is not cleared : the next chunk doesn't know this chunk is free

Fast bins exist for performance. Small, frequent allocations (the most common case) are served extremely quickly.

Unsorted Bin

Now wea are going to understand the Unsorted Bin. As I mentioned earlier the unsorted bin is closely related to the Large bin and the Small bin. When I explain some concepts in Unsorted Bin I'll be using the small bin and large bin terms too. However, later I'll explain these two in details.

We know that whenever we free a chunk it goes to one of bins. If the chunk size is in the fast bin range, it goes to the fast bin.

To understand the unsorted bin we need to consider some chunks which are not fall under the fast bin range.

Based on the chunk size these are ultimately going to the large bin or small bin. However we do not move the freed chunks immediately to large bin or small bin. First the freed chunks are stored to the unsorted bin. As the name suggests the chunks which are in this bin are not sorted. In a later step we sort these unsorted chunks into one of small bin or large bin.

But why we don't the sorting directly? The reason is this. In most of the times, recently freed memory will be reused quickly.

The free chunk layout

When a chunk is freed into the unsorted bin, the user data area is repurposed to store free list pointers:

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=1>...</block>
<block size=4>Prev size</block>
<block size=4>Size + Flags</block>
<block size=4>fd</block>
<block size=4>bk</block>
<block size=12>Padding</block>
<block size=1>...</block>

<ptr index=1>ptr - 8</ptr>
<ptr index=2>ptr - 4</ptr>
<ptr index=3>malloc( ) pointer</ptr>
<ptr index=6>ptr + size -8</ptr>

There are two pointers called fd and bk. These pointers occupy the same memory that was previously user data. The allocator knows it is safe to write here because the chunk is free and nobody should be reading this memory anymore.

Two more things happen at the moment of the free, and they are easy to miss:

set_head(p, size | PREV_INUSE);
set_foot(p, size);
clear_inuse_bit_at_offset(nextchunk, 0);

• The freed chunk's own P bit stays set. A chunk's PREV_INUSE bit describes the chunk before it, not itself. Freeing G does not change G's P bit.

• The footer is written into the next chunk. set_foot stores the freed chunk's size into the next chunk's prev_size field, and the next chunk's P bit is cleared. That pair — prev_size + a cleared P — is the only way the allocator can later walk backward in memory to find this chunk. This is the mechanism backward consolidation depends on, and the one an off-by-one overflow corrupts.

The unsorted bin lives at index 1 of the arena's bins[] array. Like every bin, its "head" is not a real chunk. But it has two pointers called fd and bk just like a normal chunk.

The list is circular doubly linked list. When the bin is empty, head->fd and head->bk both point back at the head itself.

We will need two more bin heads later.

(smallbin_index(sz) on 32-bit is sz >> 3, so 0xd0 >> 3 = 26 and 0x1a0 >> 3 = 52.)

Setting up

To study the unsorted bin we need chunks above the fast bin range (chunk size > 64). Let's allocate six:

void *g = malloc(200);   // chunk 0xd0
void *h = malloc(200);   // chunk 0xd0
void *i = malloc(408);   // chunk 0x1a0
void *j = malloc(200);   // chunk 0xd0
void *k = malloc(200);   // chunk 0xd0
void *l = malloc(200);   // chunk 0xd0

Lets quickly calculate the chunk sizes.

(200 + 4 + 7) & ~7 = 208 = 0xd0
(408 + 4 + 7) & ~7 = 416 = 0x1a0

The bellow table is very important to understand the whole concept. This lists out the chunk addresses, there flags and necessary information.

Every size field ends in 1 because every chunk's predecessor is currently allocated, so PREV_INUSE is set everywhere. The prev_size fields are meaningless right now.

The chunks are physically contiguous. Adding each size to each address gives the next one, and the leftover at the end is the top chunk:

<label pos="top-left">Low memory</label>
<label pos="top-right">High memory</label>

<block size=1>...</block>
<block size=4>Chunk G</block>
<block size=4>Chunk H</block>
<block size=8>Chunk I</block>
<block size=4>Chunk J</block>
<block size=4>Chunk K</block>
<block size=4>Chunk L</block>
<block size=10>Top chunk</block>
<block size=1>...</block>

<ptr index=1>0x5655a1a0</ptr>
<ptr index=2>0x5655a270</ptr>
<ptr index=3>0x5655a340</ptr>
<ptr index=4>0x5655a4e0</ptr>
<ptr index=5>0x5655a5b0</ptr>
<ptr index=6>0x5655a680</ptr>
<ptr index=7>0x5655a750</ptr>
<ptr index=8>0x5657b000</ptr>

Now lets see what happens when we call free(). At the moment all chunks are allocated and the unsorted bin is empty. Both of the unsorted bin's pointers are pointing to itself.

head (0xf7faf798):  fd → 0xf7faf798
                    bk → 0xf7faf798

In every diagram below, a solid arrow is fd and a dashed arrow is bk.

bck = unsorted_chunks(av);        /* the bin head */
fwd = bck->fd;                    /* the current first chunk */
if (__glibc_unlikely (fwd->bk != bck))
    malloc_printerr ("free(): corrupted unsorted chunks");
p->fd = fwd;
p->bk = bck;
bck->fd = p;
fwd->bk = p;

New chunks are spliced in immediately after the head, on the fd side. So the head end of the list is the newest chunk, and the tail end (head->bk) is the oldest.

Freeing chunk G

G is 0xd0 bytes. It is above the fast bin range, so it is not going to check in fast bins.

glibc checks both neighbors before doing anything:

- **Backward:** G's own `PREV_INUSE` bit is 1, so the chunk before G is in use. No merge.
- **Forward:** the next chunk is H at `0x5655a270`. To learn whether *H* is free, glibc
  reads the `PREV_INUSE` bit of the chunk **after H** — that is I at `0x5655a340`, whose
  size field is `0x1a1`, so P = 1. H is in use. No merge.

G goes straight into the unsorted bin. The bin is empty. From the point of the chunk which is going to be inserted (Chunk G),

bck = head
fwd = head->fd = head

See the following diagram for better understanding.

flowchart LR
    HD(["<div style='text-align:center'>Head<br/><small>0xf7faf798</small></div>"])
    G["<div style='text-align:center'>Chunk G<br/><small>0x5655a1a0</small></div>"]

    HD -->|fd| G
    G -->|fd| HD

    HD -.->|bk| G
    G -.->|bk| HD

Now, both fd and bk pointers of the chunk G are pointing to the head. Visualize this as a circular list. Then we can easily understand the concept.

Since we released the chunk G by calling free(), we are no longer using that chunk space. We need to mark that this chunk is not in used. How to do this?

We set the prev_in_use flag of the next chunk. That means the chunk H's prev_in_use is set to zero. You can clearly see that in below table. Also note that the chunk H's prev size is set to 0x000000d0. That is because chunk G is freed. Now if libc wants that space it can the amount of available space by looking at H's prev size.

Freeing chunk I

You may wonder why I skipped H. That was intentional. H is physically adjacent to G, and freeing it would trigger coalescing which would merge the two chunks and destroy the list we are trying to study. We will come back to that in a moment.

I is 0x1a0 (416) bytes. Note that in_smallbin_range() on 32-bit means size < 512, so I is still a small-range chunk.

Neighbour check:

- **Backward:** I's P bit is 1 (H is allocated). No merge.
- **Forward:** next chunk is J at `0x5655a4e0`. The chunk after J is K at `0x5655a5b0`,
  size field `0xd1`, P = 1 → J is in use. No merge.

I is inserted at the head side. When we are considering the chunk which is going to be inserted (Chunk I),

bck = head
fwd = head->fd = G

We can represent this as below.

flowchart LR
    HD(["<div style='text-align:center'>Head<br/><small>0xf7faf798</small></div>"])
    I["<div style='text-align:center'>Chunk I<br/><small>0x5655a340</small></div>"]
    G["<div style='text-align:center'>Chunk G<br/><small>0x5655a1a0</small></div>"]


    HD -->|fd| I
    I -->|fd| G
    G -->|fd| HD

    I -.->|bk| HD
    G -.->|bk| I
    HD -.->|bk| G

Now these are the values in each memory section.

What changes in other chunks? Chunk H is already changed in last step. Now in a similar way, chunk J's prev size and prev_in_use flags are changed.

Freeing chunk K

K is 0xd0 bytes.

• Backward: K's P bit is 1 (J is allocated). No merge.
• Forward: next chunk is L at 0x5655a680. The chunk after L is the top chunk at 0x5655a750, whose P bit is 1 → L is in use. No merge.

Same insertion at the head side. From K's perspective,

bck = head
fwd = head->fd = I

If we represent the current state in a diagram,

flowchart LR
    HD(["<div style='text-align:center'>Head<br/><small>0xf7faf798</small></div>"])
    K["<div style='text-align:center'>Chunk K<br/><small>0x5655a5b0</small></div>"]
    I["<div style='text-align:center'>Chunk I<br/><small>0x5655a340</small></div>"]
    G["<div style='text-align:center'>Chunk G<br/><small>0x5655a1a0</small></div>"]

    HD -->|fd| K
    K -->|fd| I
    I -->|fd| G
    G -->|fd| HD

    HD -.->|bk| G
    G -.->|bk| I
    I -.->|bk| K
    K -.->|bk| HD

Now, this is how the flags look like. Notice that the Chunk L has changed it flags.

malloc() - the FIFO drain and sorting pass

We need to call malloc() to see the unsorted bin's other half in action.

Let's call malloc(200) again. request2size(200) = 0xd0.

Before the unsorted bin is even consulted, _int_malloc tries the exact small bin: smallbin_index(0xd0) = 26, and bin 26 is empty. So it falls through to the unsorted bin loop:

The allocator takes from the tail of the unsorted bin, which is the oldest chunk. In our case this should be chunk G.

You may remember that we inserted chunks at the head. Now removing chunks from the tail. that means the unsorted bin is FIFO (First In First Out)

G is unlinked from the list. N ow these two are happening.

head->bk = G->bk = I
I->fd = head

The requested size is 0xd0 bytes. It is same as chunk G's size. so it is an exact match. G is returned immediately.

There is one important thing to do. You may remember that when we freeing the chunk G, we did some changes to the next chunk. That means we changed the prev_in_use and Prev size of the chunk H.

Now since we are going to re use the chunk G, we need to change back those flags in chunk H. How libc identifies the next chunk of G?

It simply read the size of chunk G and adds it to the chunk G's starting address. Then it goes to chunk H and do the change.

Ultimately, H's PREV_INUSE bit is set back to 1.

Then malloc() returns chunk G's user pointer, 0x5655a1a8.

flowchart LR
    HD(["<div style='text-align:center'>Head<br/><small>0xf7faf798</small></div>"])
    K["<div style='text-align:center'>Chunk K<br/><small>0x5655a5b0</small></div>"]
    I["<div style='text-align:center'>Chunk I<br/><small>0x5655a340</small></div>"]

    HD -->|fd| K
    K -->|fd| I
    I -->|fd| HD

    HD -.->|bk| I
    I -.->|bk| K
    K -.->|bk| HD

Now lets call malloc() again. This time also we are going to request 200 bytes. That means the requested chunk size is 0xd0.

Now the candidate, (head->bk) is I. First, it is unlinked from the unsorted bin:

head->bk = I->bk = K
K->fd = head

What is the size of the chunk I? it is 0x1a0. It does not match to the requested size. Now what happens? I will not be returned. Instead it gets sorted into its real home. This is the part the name "unsorted bin" is actually about.

What should be the bin which the chunk I should be sorted into? You may remember that the size range 0x50 – 0x3f0 is owned by small bin. Therefore we put the chunk I into the small bin.

Again, the small bin is a set of linked lists. Just like the fast bins.

This is how our unsorted bin looks like after removing the chunk I.

flowchart LR
    HD(["<div style='text-align:center'>Unsorted bin head<br/><small>0xf7faf798</small></div>"])
    K["<div style='text-align:center'>Chunk K<br/><small>0x5655a5b0</small></div>"]

    HD -->|fd| K
    K -->|fd| HD

    HD -.->|bk| K
    K -.->|bk| HD

What will the small bin looks like?

Small bin 52 is empty, so I's fd and bk both become that bin's head:

flowchart LR
    HD(["<div style='text-align:center'>Small bin head<br/><small>0xf7faf798</small></div>"])
    I["<div style='text-align:center'>Chunk I<br/><small>0xf7faf798</small></div>"]

    HD -->|fd| I
    I -->|fd| HD

    HD -.->|bk| I
    I -.->|bk| HD

Since the first pick from the tail side was not exact match, libc goes to the next target. The chunk K. It do the same process.

head->bk = K->bk = head
head->fd = head

Chunk K's user data pointer is returned by malloc() and L's PREV_INUSE bit is set back to 1.

Two details worth knowing:

• The loop is bounded.MAX_ITERS = 10000. If a program frees thousands of mismatched chunks, the allocator will not walk the whole list on every allocation.

• If the unsorted bin holds exactly one chunk, and the request is in the small bin range libc chooses another path. If the chunk is big enough to split, glibc splits it directly and puts the remainder back. This keeps sequential small allocations contiguous. Every other path goes through the loop above.

Coalescing

Now back to the question we deferred. Let's rewind to the state right after free(g).

flowchart LR
    HD(["<div style='text-align:center'>Head<br/><small>0xf7faf798</small></div>"])
    G["<div style='text-align:center'>Chunk G<br/><small>0x5655a1a0</small></div>"]

    HD -->|fd| G
    G -->|fd| HD

    HD -.->|bk| G
    G -.->|bk| HD

G sitting alone in the unsorted bin, H still allocated and this time we are going to free H, which is the adjacent chunk to G.

On every non-fastbin free, glibc performs two boundary checks.

• Backward consolidation. Look at the PREV_INUSE bit in this chunk's own size field. If it is 0, the previous chunk is free. Read this chunk's prev_size field to learn how far back it starts, and walk backward to find its header.

• Forward consolidation. Look at the chunk after this one, and read the PREV_INUSE bit of the chunk after that one. This is the part that trips people up: the next chunk's own P bit describes us, not it. To find out whether the next chunk is free you have to look one chunk further.

Backward coalescing, step by step

State before free(h):

H's size field is 0x000000d0, not 0x000000d1. The P bit was cleared when G was freed, and prev_size was filled in with 0xd0 by set_foot. That is the signal free(h) is about to read.

1. prev_inuse(H) is 0 → the previous chunk is free.
2. prevsize = H->prev_size = 0xd0. New size = 0xd0 + 0xd0 = 0x1a0.
3. Walk back: p = 0x5655a270 - 0xd0 = 0x5655a1a0 — that is G.
4. Sanity check: chunksize(G) must equal prevsize. Both are 0xd0, so the check passes. (This corrupted size vs. prev_size check was added in glibc 2.26 specifically to block forged prev_size values.)
5. unlink_chunk(av, G) removes G from the unsorted bin. unlink_chunk also validates the list: fd->bk == p && bk->fd == p, or it aborts with corrupted double-linked list.
6. Forward: nextchunk is I. The chunk after I is J at 0x5655a4e0, size field 0xd1, P = 1 → I is in use. No forward merge, so glibc just clears I's P bit.
7. The merged chunk, starting at G's address with size 0x1a0, is inserted into the unsorted bin as a fresh entry.

Result:

Note the size field is 0x1a1, not 0x1a0. set_head(p, size | PREV_INUSE) always re-sets the P bit, because the chunk before the merged chunk is still in use.

Before:                          After:

0x5655a1a0  ┌──────────────┐     0x5655a1a0  ┌──────────────┐
            │ G  0xd0 free │                 │              │
0x5655a270  ├──────────────┤                 │ G+H  0x1a0   │
            │ H  0xd0 used │                 │ free         │
0x5655a340  ├──────────────┤     0x5655a340  ├──────────────┤
            │ I  0x1a0     │                 │ I  0x1a0     │

The merged chunk now spans 0x5655a1a0 to 0x5655a340, which is exactly where I begins. I's prev_size is updated to 0x1a0 and its P bit cleared, so I's size field becomes 0x000001a0.

flowchart LR
    HD(["head<br/>0xf7faf798"])
    GH["G+H  0x1a0<br/>0x5655a1a0"]

    HD -->|fd| GH
    GH -->|fd| HD
    HD -.->|bk| GH
    GH -.->|bk| HD

Forward coalescing

For the mirror case we need to free a chunk whose next neighbour is already free. Starting from a fresh allocation of all six chunks, free K first, then J:

free(k);   // K goes into the unsorted bin, L's P bit is cleared
free(j);   // J's next neighbour, K, is already free

After free(k): K is alone in the unsorted bin, and L's header is prev_size = 0x000000d0, size field 0x000000d0.

Now free(j):

1. Backward: J's own size field is 0x000000d1 — P = 1, because I is still allocated. No backward merge.
2. Forward: nextchunk = K at 0x5655a5b0, nextsize = 0xd0. inuse_bit_at_offset(K, 0xd0) reads the P bit of the chunk at 0x5655a5b0 + 0xd0 = 0x5655a680 — that is L, whose P bit is 0. So K is free.
3. unlink_chunk(av, K) pulls K out of the unsorted bin. Size becomes 0xd0 + 0xd0 = 0x1a0.
4. The merged chunk, starting at J's address, goes into the unsorted bin.

set_foot writes 0x1a0 into L's prev_size, and L's P bit stays 0.

0x5655a4e0  ┌──────────────┐
            │ J+K  0x1a0   │   ← merged, in unsorted bin
0x5655a680  ├──────────────┤
            │ L    0xd0    │   prev_size = 0x1a0, P = 0
0x5655a750  ├──────────────┤
            │ top          │

If both neighbours had been free, both branches would have fired in the same free() call and all three chunks would have become one.

Coalescing into the top chunk

There is a third case, and it is the reason the forward branch is guarded by if (nextchunk != av->top). Continue the example and free L:

free(l);

1. Backward: L's P bit is 0, prev_size = 0x1a0 → merge with J+K. New size 0xd0 + 0x1a0 = 0x270, starting at 0x5655a4e0. J+K is unlinked from the unsorted bin, which is now empty.
2. Forward: nextchunk is 0x5655a750, which is av->top. The else branch runs:

else {
    size += nextsize;
    set_head(p, size | PREV_INUSE);
    av->top = p;
}

The merged chunk swallows the entire top chunk and becomes the new top chunk. It is not placed in any bin at all:

av->top  =  0x5655a4e0
size     =  0x270 + 0x208b0  =  0x20b20     (size field 0x00020b21)

Before free(l):                      After free(l):

0x5655a4e0  ┌──────────────┐         0x5655a4e0  ┌──────────────┐
            │ J+K  0x1a0   │                     │              │
0x5655a680  ├──────────────┤                     │              │
            │ L    0xd0    │                     │ top 0x20b20  │
0x5655a750  ├──────────────┤                     │              │
            │ top 0x208b0  │                     │              │
0x5657b000  └──────────────┘         0x5657b000  └──────────────┘

Watching av->top jump backward in GDB is the clearest signal that a free merged into the wilderness. We will come back to the top chunk in its own section.

Why coalescing matters

Without it, the heap would gradually fill with small, unusable free fragments — a condition called heap fragmentation. A program that allocates and frees a million 208-byte chunks would end up unable to serve a single 416-byte request, despite having megabytes free. Coalescing reunites adjacent free memory into larger chunks that can satisfy bigger future allocations.

From an attacker's point of view, coalescing is the most interesting thing free() does, because every input it trusts lives in attacker-reachable memory:

• prev_size of the chunk being freed — reachable by a one-byte overflow of the previous chunk
• the PREV_INUSE bit — a single bit in a field adjacent to user data
• the fd / bk pointers that unlink_chunk writes through

The corrupted size vs. prev_size and corrupted double-linked list checks exist precisely because all three were trivially exploitable for years. The next article picks up from here.

Small Bins

Small bins hold chunks of a specific fixed size. There are 62 small bins (indices 2–63 in the bins[] array), each dedicated to one chunk size.

On 32-bit: sizes range from 16 to 504 bytes in 8-byte steps. On 64-bit: sizes range from 32 to 1008 bytes in 16-byte steps.

Smallbin[0]  (bins[2]):   all chunks of size 16   (32-bit) / 32   (64-bit)
Smallbin[1]  (bins[4]):   all chunks of size 24   (32-bit) / 48   (64-bit)
Smallbin[2]  (bins[6]):   all chunks of size 32   (32-bit) / 64   (64-bit)
...
Smallbin[61] (bins[124]): all chunks of size 504  (32-bit) / 1008 (64-bit)

The bin index for a chunk of size s is:

bin_index = (s >> 3) - 1    // 32-bit
bin_index = (s >> 4) - 1    // 64-bit

Key properties:

• Exact fit — malloc(24) checks only the 24-byte bin. No searching needed.
• Doubly linked FIFO — chunks are inserted at the front, removed from the back. Oldest-in, first-out. This is fairer for cache behavior than LIFO.
• Circular — like the unsorted bin, each small bin is a circular list with the bin head inside main_arena.
• No coalescing on insertion — chunks are placed in small bins as-is. Coalescing happened earlier, during free().

When malloc(n) checks the matching small bin and finds a chunk, it unlinks it from the doubly-linked list and returns it. If the bin is empty, the search continues through the unsorted bin and then large bins.

The doubly-linked structure (both fd and bk) is what makes safe unlinking possible — and what makes corrupted bk pointers useful as write-what-where primitives in exploitation. We'll return to this in the next article.

Large Bins

Large bins hold chunks that are too big for small bins. There are 63 large bins (indices 64–126 in bins[]), and each one covers a range of sizes rather than a single size. The ranges get progressively wider:

Largebin[0]  (bins[128]): 512  – 568 bytes     (32-bit) / 1024 – 1088 bytes (64-bit)
Largebin[1]  (bins[130]): 576  – 632 bytes
Largebin[2]  (bins[132]): 640  – 696 bytes
...
(ranges widen logarithmically)
...
Largebin[32] (bins[192]): 16384 – 24575 bytes
...
Largebin[62] (bins[252]): everything above ~4 MB

The first 32 bins cover 64-byte ranges; the next group covers 512-byte ranges; then 4096-byte ranges and so on. This keeps the total number of bins manageable while still giving reasonable granularity for common large sizes.

The skip list: fd_nextsize and bk_nextsize

Because each large bin holds chunks of different sizes, simply having fd/bk isn't enough for efficient lookup — you'd have to walk every chunk to find the right fit. Large bin chunks therefore carry two extra pointers in the free chunk layout:

Large free chunk:
  [ prev_size | size | fd | bk | fd_nextsize | bk_nextsize | ... ]

• fd / bk — the standard doubly-linked list, linking all chunks in this bin in insertion order
• fd_nextsize — points to the next chunk in the bin that has a different (smaller) size
• bk_nextsize — points to the previous chunk in the bin that has a different (larger) size

Chunks with the same size are linked together via fd/bk, but only the first chunk of each size has non-null fd_nextsize/bk_nextsize. This forms a skip list across distinct sizes:

Largebin[0]:
  600 bytes → 600 bytes → 580 bytes → 540 bytes → NULL
                ↑                         ↑
          (same-size group)         fd_nextsize skips here

Key properties:

• Doubly linked — supports O(1) unlinking
• Sorted descending by size — largest chunk is at the front
• Best-fit allocation — malloc(n) walks the skip list to find the smallest chunk that still fits, then splits it if necessary
• Remainder goes back to unsorted bin — the leftover after a split is inserted at the front of the unsorted bin, not back into the large bin

When malloc(n) reaches large bins it:

1. Computes the large bin index for size n
2. If the bin is non-empty and its largest chunk is big enough, walks fd_nextsize to find the smallest chunk ≥ n (best fit)
3. Unlinks that chunk, splits it if it's larger than needed, puts the remainder in the unsorted bin
4. If no chunk in that bin fits, checks successively larger bins until it finds one, or falls back to the top chunk

Tcache — The Modern Fast Path

Starting with glibc 2.26 (released in 2017), a new caching layer was added on top of everything we've discussed so far — the thread-local cache, or tcache. On any modern Linux distribution, tcache is the very first thing malloc() checks and the very first place free() deposits a chunk.

The motivation is performance. Fast bins were already fast, but they were part of the main arena — every access required taking the arena's mutex. In a multithreaded program that alone serializes all allocations. Tcache sidesteps the mutex entirely: each thread gets its own completely private cache. No locking. No synchronization. Just a pointer lookup.

The internal structures

Tcache is built around two C structs. Understanding them is the key to understanding everything else.

/* One entry: stored at the start of each free chunk in tcache */
typedef struct tcache_entry {
    struct tcache_entry *next;                  /* fd: next free chunk of same size */
    struct tcache_perthread_struct *key;         /* added glibc 2.29 — double-free guard */
} tcache_entry;

/* One of these per thread — lives at the very start of the thread's heap */
typedef struct tcache_perthread_struct {
    uint16_t counts[TCACHE_MAX_BINS];           /* how many chunks are in each bin */
    tcache_entry *entries[TCACHE_MAX_BINS];     /* head pointer for each bin (LIFO stack) */
} tcache_perthread_struct;

TCACHE_MAX_BINS defaults to 64. So the perthread struct holds 64 counters and 64 head pointers — one per size class.

The perthread struct itself is allocated on the heap the first time the thread calls malloc(). It sits at the very beginning of the heap region, right before any user allocations. In GDB you can find it by looking at the first chunk on the heap — it's not a user allocation, it's this bookkeeping structure.

Heap start:
  [ tcache_perthread_struct ]   ← ~1088 bytes, one per thread
  [ user chunk A             ]
  [ user chunk B             ]
  ...

Size classes and bin layout

On a 64-bit system, tcache covers chunk sizes from 0x20 (32 bytes) up to 0x410 (1040 bytes), in steps of 0x10 (16 bytes). That gives exactly 64 bins:

Bin  0:  chunk size 0x20   (malloc requests 0–8 bytes)
Bin  1:  chunk size 0x30   (malloc requests 9–24 bytes)
Bin  2:  chunk size 0x40   (malloc requests 25–40 bytes)
...
Bin 63:  chunk size 0x410  (malloc requests up to ~1032 bytes)

On 32-bit: chunk sizes 0x10 to 0x210, in 8-byte steps, same 64 bins.

The bin index for a requested size is:

tcache_idx = (chunk_size - 1) / (2 * SIZE_SZ)   // SIZE_SZ = 8 on 64-bit, 4 on 32-bit

Each bin is a singly-linked LIFO stack — only next (the fd equivalent), no bk. And each bin holds at most 7 chunks by default. The counts[] array tracks the current depth of each bin.

Thread's tcache:

  counts:   [3] [1] [0] [2] ...
  entries:  [0x20 bin]  →  chunk_c  →  chunk_b  →  chunk_a  →  NULL
            [0x30 bin]  →  chunk_x  →  NULL
            [0x40 bin]  →  NULL
            [0x50 bin]  →  chunk_f  →  chunk_e  →  NULL
            ...

How free() places a chunk in tcache

When free(ptr) is called, before anything else, glibc checks:

1. Is the chunk size within tcache range (≤ 0x410 on 64-bit)?
2. Is the matching bin not full (counts[idx] < 7)?

If both are true, the chunk is stashed in tcache immediately:

// Simplified from glibc malloc/malloc.c
tcache_entry *e = (tcache_entry *) chunk2mem(chunk);
e->key = tcache;                         // write perthread struct ptr (double-free guard)
e->next = tcache->entries[tc_idx];       // push: new head points to old head
tcache->entries[tc_idx] = e;             // update head
tcache->counts[tc_idx]++;                // increment counter

That's it. No coalescing. No PREV_INUSE manipulation. No lock. The chunk is pushed onto the front of the singly-linked list in a handful of instructions.

If the bin is already full (count == 7), the chunk falls through to the normal free() path — fast bins, unsorted bin, coalescing.

How malloc() retrieves a chunk from tcache

On malloc(n), tcache is checked before anything else:

// Simplified
size_t tc_idx = csize2tidx(checked_request2size(n));
if (tc_idx < TCACHE_MAX_BINS && tcache->counts[tc_idx] > 0) {
    tcache_entry *e = tcache->entries[tc_idx];   // pop from head
    tcache->entries[tc_idx] = e->next;
    tcache->counts[tc_idx]--;
    return chunk2mem(e);                         // return user pointer
}
// … fall through to arena

Pop the head, return it. No size validation (historically). No alignment check. Just a pointer. This is as fast as a allocator can get.

Tcache fill — batch loading from other bins

When malloc(n) misses tcache but finds chunks in the fast bin or unsorted bin, glibc doesn't just return one chunk. It fills the tcache first, then returns one. For fast bins specifically:

fast bin has 5 chunks of the right size
tcache has 0 chunks for that size
→ glibc moves up to min(5, 7) = 5 chunks into tcache, then pops and returns one
→ next 4 malloc() calls of the same size hit tcache directly

This batch fill amortizes the cost of accessing the arena-locked fast bin across multiple future allocations. It's a prefetch strategy: pay the lock cost once, get several lock-free allocations in return.

The same fill behavior happens when walking the unsorted bin — any chunk of matching size that gets sorted during a malloc() walk is placed into tcache rather than the small bin, up to the 7-chunk limit.

The key field — double-free detection (glibc 2.29+)

Early tcache (glibc 2.26–2.28) had no double-free detection at all. free(ptr); free(ptr); would silently create a loop in the singly-linked list, and the next two malloc() calls of the same size would both return the same chunk — a trivial exploitation primitive.

glibc 2.29 added the key field to close this gap. When a chunk is inserted into tcache, glibc writes a pointer to the current thread's tcache_perthread_struct into the chunk's key field (which occupies the bk-equivalent slot of the free chunk). On the next free(ptr) call, glibc checks:

if (e->key == tcache) {
    // Possible double-free — scan the bin to confirm
    tcache_entry *tmp = tcache->entries[tc_idx];
    while (tmp) {
        if (tmp == e) malloc_printerr("free(): double free detected in tcache 2");
        tmp = tmp->next;
    }
}

The scan is O(n) in the bin depth, but since the bin holds at most 7 entries the cost is bounded. It catches the obvious double-free. Note that it only fires if the chunk is still in tcache when freed again — if the chunk was popped by a malloc() in between, the key field gets overwritten by user data and the check doesn't trigger.

Pointer mangling — PROTECT_PTR (glibc 2.32+)

glibc 2.32 added a second hardening: the next pointer stored in tcache entries (and fast bin fd pointers) is now obfuscated using a simple XOR scheme called PROTECT_PTR:

#define PROTECT_PTR(pos, ptr) \
    ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))

#define REVEAL_PTR(ptr) \
    PROTECT_PTR (&ptr, ptr)

When storing a next pointer at address pos, glibc XORs it with pos >> 12 (the page number of the storage location). To read it back, it reverses the XOR. The "secret" is the page address of the chunk itself — an attacker can't forge a useful next pointer without knowing where the tcache entry lives in memory.

Before glibc 2.32, overwriting a freed chunk's next with an arbitrary address was enough to make the next malloc() return that address. With pointer mangling, the attacker also needs a heap address leak to compute the correct obfuscated value:

stored_next = (heap_chunk_addr >> 12) XOR target_address

Without that leak, a naively written fake next pointer decodes to garbage and the allocation returns an invalid address — usually crashing before it's useful.

The full picture: free() decision tree

free(ptr)
│
├─ Is size in tcache range AND bin not full?
│      YES → push to tcache. Done. ← the common case, no lock
│
├─ Is chunk mmap'd (IS_MMAPPED bit set)?
│      YES → munmap(). Done.
│
├─ Is size in fast bin range?
│      YES → push to fast bin. Done.  ← still no coalescing
│
└─ Otherwise (large chunk, or fast bin range but arena consolidation triggered)
       → try backward coalesce (check PREV_INUSE of this chunk)
       → try forward coalesce (check PREV_INUSE of next-next chunk)
       → place result in unsorted bin
       → if adjacent to top chunk, merge into wilderness

The full picture: malloc() decision tree

malloc(n)
│
├─ 1. tcache hit?
│      YES → pop and return. ← the common case
│
├─ 2. n > mmap threshold (~128KB)?
│      YES → mmap() a fresh region, return it
│
├─ 3. Fast bin hit?
│      YES → pop chunk, fill tcache with remaining fast bin chunks, return
│
├─ 4. Small bin exact match?
│      YES → unlink from doubly-linked bin, return
│
├─ 5. Walk unsorted bin
│      exact match → return it (possibly after filling tcache)
│      otherwise   → sort each chunk into its small or large bin as we walk
│
├─ 6. Large bin best-fit
│      find smallest chunk ≥ n via fd_nextsize skip list
│      split if necessary, put remainder in unsorted bin, return
│
├─ 7. Larger bins (check successively bigger large bins)
│
└─ 8. Top chunk (wilderness) — carve off the front
       if top chunk too small → sbrk() / mmap() to extend it, then carve

The Top Chunk (Wilderness)

At the very end of the heap sits a special chunk called the top chunk, also known affectionately as the wilderness. It represents all the unallocated memory at the top of the heap region — everything the program has requested from the OS but not yet carved up into smaller chunks.

You've already seen the top chunk in action in the GDB examples earlier. Remember this line?

0x5655a1b8: 0x00000000  0x00021e49  0x00000000  0x00000000

That 0x00021e49 is the top chunk's size field. It's huge (about 138 KB) because it's essentially "the rest of the heap." Each time a malloc() call can't find a suitable chunk in any bin, the allocator falls back to the top chunk it carves a new chunk off the front of the wilderness and shrinks the top chunk by that amount. That's why, between each malloc() in our earlier example, we saw the top chunk's size shrink from 0x21e49 → 0x21e39 → 0x21e29.

The top chunk has a few special properties:

• It's never in any bin. The allocator keeps a direct pointer to it in the arena structure (av->top).
• It has no neighbor to its right. Its PREV_INUSE bit is conceptually always set, and its "next chunk" doesn't exist — attempting to read it would walk off the end of the heap.
• It absorbs adjacent frees. When you free a chunk that sits immediately before the top chunk, it doesn't go into a bin — it's merged directly into the wilderness. We saw this at the end of the earlier example, when freeing chunk C caused the top chunk to jump backward and swallow both B and C.
• It grows the heap when exhausted. If the top chunk is too small to satisfy a request, the allocator calls sbrk() (for the main heap) or mmap() (for very large requests or secondary arenas) to extend it.
• It can shrink. If the top chunk grows beyond M_TRIM_THRESHOLD (default 128 KB), glibc trims the excess back to the OS with a negative sbrk(). This is exactly the "heap trimming" we observed at the very end of the GDB walkthrough, where 0x21e49 became 0x20e49 after glibc returned a 4 KB page to the kernel.

From an attacker's perspective, the top chunk is interesting because its size field is just another 8-byte value sitting in memory. If a heap buffer overflow lets you overwrite it, you can forge a gigantic size, and then request a huge malloc() that makes the allocator's internal pointer "wrap around" to an arbitrary address. This is the classic House of Force technique. Again — a story for the next article.

The Arena

Finally, the wrapper that ties all of this together: the arena. An arena is glibc's internal bookkeeping structure for a heap. It holds every piece of state we've discussed so far — all the bins, the top chunk pointer, a lock, and references to the underlying memory regions.

Here's a simplified view of struct malloc_state (the arena):

struct malloc_state {
    mutex_t      mutex;            // Lock for thread safety
    int          flags;
    mfastbinptr  fastbinsY[10];    // Fast bins
    mchunkptr    top;              // The top chunk
    mchunkptr    last_remainder;   // Last split remainder
    mchunkptr    bins[254];        // Unsorted + small + large bins
    unsigned int binmap[4];        // Bitmap of non-empty bins
    struct malloc_state *next;     // Linked list of arenas
    ...
};

Every Linux process has at least one arena: the main arena, which lives as a static global inside libc itself. That's why, in our earlier GDB session, chunk B's fd and bk pointers after free(b) both pointed to 0xf7faf798 — a fixed address inside libc.so. That's the main arena's unsorted bin head.

Why multiple arenas?

In a single-threaded program, the main arena is all you ever need. But in a multithreaded program, every malloc() and free() would need to take the arena lock, serializing every thread on a single mutex. That would kill performance.

So glibc creates additional arenas on demand. When a thread calls malloc() and finds the main arena locked, glibc may spin up a new arena (up to 8 * number_of_cores by default) and assign that thread to it. Each extra arena has its own heap region, allocated via mmap() rather than sbrk(), and its own independent set of bins.

Main arena  →  sbrk() heap     (thread 1)
Arena 2     →  mmap'd region   (thread 2)
Arena 3     →  mmap'd region   (thread 3)
...

This is exactly what the NON_MAIN_ARENA flag (bit 2 of the size field, the A bit) is for. When free() sees a chunk with A = 1, it knows the chunk didn't come from the main arena and has to walk back to that chunk's own arena header to put the chunk in the right bin. glibc finds the arena header by masking the chunk's address down to a heap-aligned boundary and reading a small "heap_info" struct at the start of the mmap'd region.

Thread-local state

On top of arenas, each thread also carries two pieces of thread-local state:

1. The tcache — its private fast-path cache (discussed above).
2. An "arena hint" — the last arena this thread used, so it can reuse it without searching.

Put all of this together and the full hierarchy looks like this:

Thread 1:
    tcache (private)
        │
        ▼
    Main arena (shared, locked)
        │
        ├── fastbins[10]
        ├── bins[254]   (unsorted, small, large)
        ├── top chunk   →  sbrk() heap
        └── next →  Arena 2
                        │
                        ├── fastbins[10]
                        ├── bins[254]
                        ├── top chunk  →  mmap'd heap
                        └── next →  ...

Every malloc() drills down through this structure: tcache first, then fastbins, then small/large bins, then top chunk, then sbrk/mmap. Every free() does the reverse, depositing chunks into whichever layer accepts them.

That is the full picture of glibc's malloc. Chunks wrapped in headers, organized into bins, grouped under arenas, cached per-thread, all stitched together with pointer metadata stored inside the free memory itself. And that last detail — metadata living inside the very memory the program is free to overwrite — is the crack through which every heap exploit in the next article will squeeze.