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() interfaces

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 we 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 in 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.

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 the fast bins.

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.

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

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

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.

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

To understand this concept we need a chunk which the previous adjacent chunk is already free. Lets consider the moment G is free and H is allocated.

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.

When we call free(H), these are going to be happen:

• prev_inuse(H) is 0

We check if the chunk G is free. We can do this by examining the prev_inuse bit of H.

• prevsize = H->prev_size = 0xd0

Since we got to know that the previous chunk is free. Now we need to get the size of that free chunk. That detail is also available in current chunk We simply check the prev_size of the current chunk.

• New size = 0xd0 + 0xd0 = 0x1a0.

We merge the previous chunk with the current chunk and make a large chunk. To do that we need to travel the the previous chunk.

• Walk back to G

How we know the address of the chunk G?

Simple. we get the current chunk's address and substract the size of current size from it.

0x5655a270 - 0xd0 = 0x5655a1a0

• Sanity check: chunksize(G) must equal prevsize.

After we going to the chunk G we compare the chunk's size with the size we obtained from previous step.

Basically we check if,

chunksize(G) = H -> prev_size.

This check was added in glibc 2.26 specifically to block forged prev_size values. Just keep this in mind and we will see this in action later.

• unlink_chunk(av, G)

We need to get the chunk G from it's current bin and merge it with chunk H. At the moment chunk G is in the unsorted bin. We remove it from the unsorted bin and merge. (G + H)

• Forward check: Next we check if the chunk which is after the current one is also free. For this specific case it is the chunk I and that is allocated. No forward merging happens.

However we need to clear I's P bit. By doing that we say the chunk before I is not in use anymore.

• The merged chunk goes to unsorted bin.

The new merged chunk (G+H) which is 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.

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<br/>0x5655a1a0"]

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

Forward coalescing

To understand this, we need to free a chunk whose next neighbor is already free.

Lets consider a moment where only the chunk K is free.

K sitting alone in the unsorted bin, J still allocated and this time we are going to free J, which is the chunk right before chunk K.

At the moment the unsorted bin looks like following.

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>"]

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

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

What happens when we call free(J) ?

• prev_inuse(J) is 1

Chunk J's prev_in_use bit is set. That means I is still allocated. Therefore, No backward merging happens.

• prev_inuse(L) is 0

We need to check if the chunk right after J is free or not. How to do this? We are currently at the chunk J. What we are going to check is if chunk K is free.

Ultimately we need to check chunk L's prev_in_use bit.

At this point you know how we can travel between chunks using the sizes. So we can easily understand how this happens.

3. unlink_chunk(av, K)

We need to get the chunk K from it's current bin and merge it with chunk J. At the moment chunk K is in the unsorted bin. We remove it from the unsorted bin and merge. (J + K)

4. The merged chunk, starting at J's address, goes into the unsorted bin.

flowchart LR
    HD(["head<br/>0xf7faf798"])
    JK["J + K<br/> 0x5655a4e0"]

    HD -->|fd| JK
    JK -->|fd| HD
    HD -.->|bk| JK
    JK -.->|bk| HD

If both neighbors 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

To understand this concept, we need the chunk which is right before the top chunk. That is the chunk L.

Lets call free(L) and see what happens.

• prev_inuse (L) is 1 Since the previous chunk is already allocated backword Coalescing is not happening.

• Forward check The usual check. We need to check if the chunk right after the current one is free. If it is free we merge it with current chunk and place to the unsorted bin right. That is we observed above.

However, in this case the situation is different. The next chunk is not an ordinary chunk. It is the top chunk.

Here, we merge the current chunk into the top chunk. But we don't put this into any bin. Ultimately the top chunk pointer get changed.

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

The layout after this would be something like below.

<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=14>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>

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.

Introduction to the Tcache

All above concepts we discussed are classic glibc stuff.

There is a new caching layer was added on top of everything we have discussed so far in the glibc 2.26. This is called thread-local cache AKA Tcache.

Every time we call malloc() or free() Tcache comes into the play before any other bins.

There are two central data structures which we need to understand.

typedef struct tcache_entry {
    struct tcache_entry *next;
    uintptr_t key;
} tcache_entry;

typedef struct tcache_perthread_struct
{
  uint16_t counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread tcache_perthread_struct *tcache = NULL;

The tcache_entry structure is not normally a separate allocation. When a chunk is freed into tcache, glibc overlays the entry on the beginning of that chunk's former user-data area. The next field links to the next cached chunk, while key is used by double-free detection in applicable versions.

Per-thread organization

That struct is itself allocated with malloc() the first time the thread allocates anything, which means it sits at the very bottom of the heap, before any user chunk.

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

<block size=4>...</block>
<block size=8>tcache_perthread_struct</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>

Tcache has 64 bins covering the smallest 64 chunk sizes, stepping by MALLOC_ALIGNMENT:

#define csize2tidx(x)  (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

Plug the constants in and it is just "which multiple of the alignment is this":

64-bit:  MINSIZE = 0x20,  MALLOC_ALIGNMENT = 0x10
         csize2tidx(0x20)  = 0      csize2tidx(0x410) = 63

32-bit:  MINSIZE = 0x10,  MALLOC_ALIGNMENT = 0x08
         csize2tidx(0x10)  = 0      csize2tidx(0x208) = 63

So the coverage is:

• 64-bit: chunk sizes 0x20 through 0x410 (1040 bytes), in 0x10 steps.
• 32-bit: chunk sizes 0x10 through 0x208 (520 bytes), in 0x08 steps.

Note that on 32-bit, tcache covers everything the fast bins cover and every small bin.

flowchart TD
    T["Current thread"] --> TC["tcache pointer"]
    TC --> S["tcache_perthread_struct"]
    S --> C["counts[64]"]
    S --> E["entries[64]"]
    E --> B0["Bin 0: head pointer"]
    E --> B1["Bin 1: head pointer"]
    E --> BN["... other size-class heads"]
    B0 --> L0["Freed chunk list"]
    B1 --> L1["Freed chunk list"]

Each thread has its own tcache state. This is why the same size class can have different cached chunks in different threads.

Is the tcache structure always the first heap allocation?

No universal rule should be inferred from a heap dump. Tcache state is initialized lazily, and the backing allocation and observed heap layout depend on the version and execution path. On some common x86-64 glibc setups, the structure is visible near the start of the heap, but that is an observation to verify in the target process, not a layout guarantee.

The structure contains counters and list-head pointers that influence allocator behavior, so corruption of it can be security-relevant. However, its location, reachability, and the checks applied to later allocations must be established for the specific target; its presence alone does not imply that an attacker can overwrite it.

3. Size classes and bin indexing

Tcache has a fixed number of size-class bins in the glibc versions covered here. The bins represent chunk sizes, not raw malloc() request sizes.

A common index calculation is:

#define csize2tidx(x) \
    (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

For typical configurations:

• 64-bit: MINSIZE = 0x20, MALLOC_ALIGNMENT = 0x10. The 64 tcache bins cover chunk sizes from 0x20 through 0x410, in 0x10 increments.
• 32-bit: MINSIZE = 0x10, MALLOC_ALIGNMENT = 0x08. The 64 bins cover chunk sizes from 0x10 through 0x208, in 0x08 increments.

counts[]: [0] [3] [1] [0] ...

entries[0]:  NULL

entries[1]:  Chunk A  →  Chunk B  →  Chunk C  →  NULL

entries[2]:  Chunk D -> NULL

These are typical ranges derived from glibc's request-to-chunk-size calculation. The request size and the resulting chunk size are different concepts; metadata accounting and alignment determine which bin is used.

How free() places a chunk in tcache

• check the IS_MMAPPED bi of the chunk. If this bit is set, that means mmap'd chunk has to go back to the kernel and can never be cached. Therefore, the tcache path is not happening.

• Is the chunk size within tcache range?

Tcache supports a pre defined size range as we saw earlier. If the chunk size is not within this range it may goes into other bins.

• Is the matching bin not full (counts[idx] < 7)

The maximum number of chunks we can hold in a tcache bin is 8. If it is filled we don't call tcache put. In this case also, it goes into other bins.

If above conditions are met, we call tcache_put().

static void tcache_put(mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem(chunk);

  e->key  = tcache_key;
  e->next = PROTECT_PTR(&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

there is no coalescing orprev_inuse manipulation happens.

Anyone reading the the next chunk, still sees this one is in use. This is the same behavior as a fast bin entry.

How malloc() retrieves a chunk from tcache

First of all we check if the chunk size is available in the Tcache entries. If it is, we quickly get it and return. Otherwise go to other paths.

size_t tc_idx = csize2tidx (nb);

if (tc_idx < mp_.tcache_bins && tcache != NULL && tcache->counts[tc_idx] > 0)
  {
    tcache_entry *e = tcache->entries[tc_idx];
    tcache->entries[tc_idx] = REVEAL_PTR(e->next);
    --(tcache->counts[tc_idx]);
    e->key = 0;
    return (void *) e;
  }

Pop the head, clear the key, return it.

Tcache refilling process

Tcache is also populated from chunks found through other allocator paths. When a tcache bin is empty and malloc() finds suitable chunks in regular bins, glibc may stash additional matching chunks in tcache, subject to the bin's capacity, while satisfying the current request.

For example, if a relevant regular bin has five suitable chunks and the matching tcache bin is empty, glibc may move those chunks into tcache during the allocation path. One is returned to the caller, and the remaining cached chunks can satisfy later requests. Exact details depend on the path and glibc version.

This is one reason a heap dump can look different after a single allocation. The allocator may be doing more than returning one chunk: it may also be moving other chunks between its internal structures.

The key field and double-free detection

A double-free occurs when a program frees the same allocation more than once without a valid intervening allocation that returns ownership to the program. It is undefined behavior and can corrupt allocator state.

Early tcache implementations (glibc 2.26–2.28) lacked the later tcache-key-based duplicate detection. In glibc 2.29, a key-based check was introduced. When a freed entry's key matches the current tcache key, glibc checks the relevant list to determine whether the entry is already present. The list scan is bounded by the bin's configured capacity in ordinary circumstances.

The simplified check looks like:

if (e->key == tcache_key) {
    for (tmp = tcache->entries[tc_idx]; tmp;
         tmp = REVEAL_PTR(tmp->next)) {
        if (tmp == e)
            malloc_printerr("free(): double free detected in tcache 2");
    }
}

This is a conceptual excerpt; consult the target release for exact code and diagnostics.

How the key changed

The key is a detection aid, not a complete memory-safety guarantee. For example, a chunk that has been removed from tcache by a successful allocation no longer remains in that list, and the key is cleared as part of retrieval. A later invalid free may therefore take a different path. Corrupted size metadata can also affect which bin is examined.

Do not infer that every double-free is detected, or that bypassing this check alone makes a vulnerability exploitable.

9. Safe-linking: protecting singly linked lists

glibc 2.32 introduced safe-linking for singly linked free lists, including tcache and fast bins. Instead of storing the next pointer directly, glibc encodes it using the address where the pointer is stored.

The core operation is:

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

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

The central relationship is:

\[ E = P \oplus (L \gg 12) \]

where:

• \(E\) is the encoded pointer stored in memory;
• \(P\) is the original pointer;
• \(L\) is the address of the pointer field;
• \(\oplus\) is XOR.

Decoding applies the same XOR again:

\[ P = E \oplus (L \gg 12) \]

The shifted storage address contributes address-dependent information. It is not a cryptographic secret, and safe-linking should not be described as encryption. It raises the difficulty of straightforward pointer corruption, especially when the relevant address is unknown.

Modern glibc also checks that a tcache entry is suitably aligned before using it. A corrupted encoded pointer that decodes to an invalid or misaligned address may trigger an allocator error.

Safe-linking at a conceptual level

flowchart TD
    A["Original next pointer P"] --> C["XOR with L shifted right by 12"]
    B["Storage address L"] --> C
    C --> D["Encoded pointer E stored in chunk"]
    D --> F["Read encoded value"]
    B --> G["Recompute L >> 12"]
    F --> H["XOR with same address-derived value"]
    G --> H
    H --> I["Recovered pointer P"]

A heap-address disclosure can help an analyst calculate or validate the encoding. Whether a particular attack needs a leak depends on what addresses and constraints are already known. It is too strong to claim that every safe-linking bypass necessarily requires a heap leak.

The Top Chunk (Wilderness)

At the very end of the heap sits a special chunk called the top chunk, also known as the wilderness. It is all the memory the program has taken from the kernel but not yet carved into chunks.

We already met it twice. In our six-chunk layout it was the 0x208b0 region at 0x5655a750, sitting above chunk L. And when we freed L, backward consolidation merged J+K+L into it and the top chunk moved backward:

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

That backward jump is the clearest signal, in GDB or in a heap visualiser, that a free merged into the wilderness.

The top chunk has a few properties that make it unlike anything else on the heap:

• It is never in a bin. The arena holds a direct pointer, av->top. There is no list to walk and no fd/bk to corrupt.
• Its PREV_INUSE bit is always 1. Not by special-casing — it follows from the rules. If the chunk before top were free, it would already have been merged into top, so by construction the predecessor is always allocated.
• It has no next chunk. Reading the header after the top chunk walks off the end of the mapping. This is why the forward-consolidation branch in free() is guarded by if (nextchunk != av->top).
• It absorbs adjacent frees. A chunk freed immediately below the top chunk is not binned at all. It is swallowed, and av->top moves down to cover it.
• It grows the heap when exhausted. If top is too small for a request, sysmalloc() extends it with sbrk() for the main arena, or mmap() for a secondary arena or a request above the mmap threshold (128 KB by default, and dynamically raised up to 32 MB as the program's behaviour is observed).
• It can shrink. When the top chunk grows past M_TRIM_THRESHOLD (128 KB by default), free() calls systrim() and returns whole pages to the kernel with a negative sbrk(). A top chunk that suddenly gets smaller without an allocation happening is heap trimming.

From an attacker's point of view, the top chunk's size field is the interesting part. It is one word, it sits in memory, and it is immediately after the last user chunk on the heap — so a linear overflow of that chunk reaches it. Overwrite it with 0xffffffff and the allocator believes the wilderness is effectively infinite. Request a carefully chosen enormous size and the pointer arithmetic av->top + nb wraps, placing the new top chunk at an arbitrary address. The next malloc() then returns a pointer into whatever you aimed at. That is the classic House of Force.

glibc 2.29 killed the technique outright with four lines in _int_malloc:

victim = av->top;
size = chunksize (victim);

if (__glibc_unlikely (size > av->system_mem))
  malloc_printerr ("malloc(): corrupted top size");

A forged top size larger than everything the process has ever requested from the kernel is now an immediate abort. The technique still matters for older targets, and the shape of it — forge a size, make the allocator compute a pointer for you — recurs throughout the next article.

The Arena

Finally, the structure that owns all of this: the arena. One arena is the complete bookkeeping state for one or more heaps — every bin we have discussed, the top chunk pointer, a lock, and the links that tie multiple arenas together.

struct malloc_state
{
  __libc_lock_define (, mutex);         /* serializes access to this arena       */
  int flags;
  int have_fastchunks;                  /* set when a fast bin is non-empty      */

  mfastbinptr fastbinsY[NFASTBINS];     /* 10 fast bins                          */

  mchunkptr top;                        /* the wilderness                        */
  mchunkptr last_remainder;             /* leftover from the most recent split   */

  mchunkptr bins[NBINS * 2 - 2];        /* 254 slots = 127 bin heads             */
  unsigned int binmap[BINMAPSIZE];      /* 4 words = 128 bits, one per bin       */

  struct malloc_state *next;            /* circular list of all arenas           */
  struct malloc_state *next_free;       /* list of arenas with no attached thread*/
  INTERNAL_SIZE_T attached_threads;

  INTERNAL_SIZE_T system_mem;           /* total memory taken from the kernel    */
  INTERNAL_SIZE_T max_system_mem;
};

The bins[254] array is the one to recognise. It is 127 bin heads packed two pointers at a time — bin 1 the unsorted bin, bins 2–63 the small bins, bins 64–126 the large bins — and each "head" is a fake chunk whose fd and bk are real but whose prev_size and size overlap the neighbouring bin's pointers. That overlap is deliberate and saves 16 bytes per bin, and it is why bin_at() subtracts offsetof(struct malloc_chunk, fd).

system_mem is worth noting too. It is the value the corrupted top size check compares against, and it is also the reason that check works: it is a running total the attacker cannot inflate without actually making the process allocate.

The main arena lives in libc

Every process has at least one arena: the main arena, which is not on the heap at all. It is a static global inside libc.so:

static struct malloc_state main_arena = { ... };

This is why the unsorted bin head in all our examples was 0xf7faf798 — a libc address, not a heap address. And it is why that address is so useful. A chunk that lands in the unsorted bin alone has both fd and bk pointing back at main_arena. If the program then prints that chunk's contents without reinitialising them, you get a libc pointer at a fixed offset from the library base, which defeats ASLR in one read. The unsorted bin leak is the single most common first step in modern heap exploitation, and it exists purely because of where main_arena is stored.

Fast bins and tcache do not give you this. A lone fast bin chunk has fd = NULL, and a lone tcache entry has next = NULL (mangled or not). You need a chunk large enough to skip both caches — above 0x208 on 32-bit, above 0x410 on 64-bit — which is exactly why CTF heap challenges so often hand you a conspicuous "large" allocation option.

Why multiple arenas?

In a single-threaded program the main arena is all you ever need. In a multithreaded one, every malloc() and free() would contend on a single mutex.

So glibc creates additional arenas on demand. When a thread calls malloc() and finds the main arena's mutex already held, it may be given a new arena instead of waiting:

#define NARENAS_FROM_NCORES(n)  ((n) * (sizeof (long) == 4 ? 2 : 8))

Two arenas per core on 32-bit, eight per core on 64-bit. Past that limit, threads start sharing and contending again. Each secondary arena gets its heap from mmap() rather than sbrk(), and carries its own completely independent set of bins.

Main arena  →  sbrk() heap      (the original heap, grows upward)
Arena 2     →  mmap'd region    (thread 2)
Arena 3     →  mmap'd region    (thread 3)
...

This is what the NON_MAIN_ARENA flag — the A bit, bit 2 of the size field — is for. free() has nothing but a pointer to work with, so it has to answer "which arena does this chunk belong to?" before it can do anything:

#define heap_for_ptr(ptr) \
  ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))

#define arena_for_chunk(ptr) \
  (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)

If A is 0 the answer is &main_arena and there is nothing to look up. If A is 1, glibc masks the chunk's address down to a HEAP_MAX_SIZE boundary (32 MB on 32-bit, 64 MB on 64-bit — secondary heaps are always aligned to that) and reads the heap_info header parked at the start of that region:

typedef struct _heap_info
{
  mstate            ar_ptr;         /* arena this heap belongs to */
  struct _heap_info *prev;          /* previous heap for the same arena */
  size_t            size;           /* bytes currently mapped */
  size_t            mprotect_size;  /* bytes currently readable/writable */
  ...
} heap_info;

One masked AND and one load. Note what that means for us: flipping the A bit on a chunk you control redirects free() to read an "arena pointer" from an address derived from the chunk's own location. On 64-bit that boundary is 64 MB away, which is usually unmapped and just crashes — but it is a real, reachable code path driven by a single bit sitting next to user data.

Thread-local state

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

static __thread tcache_perthread_struct *tcache = NULL;   /* the private cache */
static __thread mstate thread_arena = NULL;               /* which arena I use */

thread_arena is a cached answer, so a thread that has already been assigned an arena goes straight to it without rescanning the arena list.

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

Thread 1                              Thread 2
   │                                     │
   ├─ tcache (private, no lock)          ├─ tcache (private, no lock)
   │     64 bins × 7 chunks              │     64 bins × 7 chunks
   │                                     │
   └─ thread_arena ──┐                   └─ thread_arena ──┐
                     ▼                                     ▼
            ┌──────────────────┐                  ┌──────────────────┐
            │   main_arena     │   next           │    Arena 2       │
            │   (in libc.so)   ├─────────────────►│   (on its heap)  │
            │                  │                  │                  │
            │  mutex           │                  │  mutex           │
            │  fastbinsY[10]   │                  │  fastbinsY[10]   │
            │  bins[254]       │                  │  bins[254]       │
            │  binmap[4]       │                  │  binmap[4]       │
            │  top ──► sbrk    │                  │  top ──► mmap    │
            └──────────────────┘                  └──────────────────┘

Every malloc() drills down through this structure: tcache first, then — if that misses — the arena lock, fast bins, small bins, the unsorted bin, large bins, the top chunk, and finally sbrk or mmap. Every free() runs it in reverse, depositing the chunk in whichever layer will accept it.

That is the full picture of glibc's malloc. Chunks wrapped in headers, organised into bins, grouped under arenas, cached per thread, all stitched together with pointer metadata stored inside the free memory itself.

And that last detail is the whole game. Every structure in this article — the fd and bk of a small bin, the nextsize ring of a large bin, the next of a tcache entry, the prev_size the allocator reads to walk backward, the size field of the top chunk — lives in memory the program is free to write to. The allocator has no choice but to trust it. Every check we met along the way (corrupted size vs. prev_size, corrupted double-linked list, malloc(): smallbin double linked list corrupted, free(): double free detected in tcache 2, malloc(): corrupted top size, safe-linking) is glibc retrofitting distrust onto a design that started out assuming none was needed.

In the next article we stop reading the allocator and start lying to it.