Heap Exploitation Part 2: Understanding the Glibc Heap Implementation

Part 2: Understanding the GLIBC Heap Implementation

Welcome back to this series on understanding and exploiting the glibc heap!

In the first part of this series , I explained the basic behavior of malloc and free . We saw that, under-the-hood, malloc handles memory allocation requests by allocating memory chunks. Each chunk not only stores the “user data” region returned by malloc that the programmer will interact with, but also metadata associated with that chunk.

We saw how the heap manager’s basic chunk-allocation strategy works, and we saw how new chunks get created from the top of the heap when there are no already-freed chunks that can be recycled to service the request.

In this post, I want to talk about how this chunk-recycling strategy works, i.e., how allocations passed back to free get saved and eventually recycled to service future malloc requests. Lots of heap exploitation techniques rely on exploiting these internal mechanics—we’ll look at these in future posts—but for now, let’s just look at how these chunks get recycled by free when the heap is operating correctly.

How Does Free Work?

When a programmer is finished with an allocation from malloc (or a malloc-compatible allocation like calloc ), the programmer releases it back to the heap manager by passing it to free . The C standard defines free(NULL) to do nothing, but for all other calls to free, the heap manager’s first job is to resolve the pointer back to its corresponding chunk. The heap manager does this by subtracting the size of the chunk metadata from the pointer that was passed to free.

Free Chunk Metadata

In my last post, I also showed how live chunks store metadata alongside the “user data” region used by the programmer. These live allocations store the “chunk size”, and three bits called “A”, “M” and “P” in their metadata. Those bits help the heap manager remember if the chunk was allocated from the non-main arena, was allocated off-heap via mmap , and whether the previous chunk is free respectively.

Free chunks store metadata too. Like live allocations, they store the “chunk size”, “A”, and “P” fields, but they do not use the “M” field, since an mmap -ed chunk will always be munmap- ed during free rather than turned into a free chunk for recycling.

Free chunks also store information after the user data region using a technique called “ boundary tags ”. These boundary tags carry size information before and after the chunk. This allows chunks to be traversed starting from any known chunk and in any direction, and thereby enable very fast coalescing of adjacent free chunks.

These freed chunks are stored in corresponding “free bins” that operate as linked lists . This requires each free chunk to also store pointers to other chunks. Since the “user data” in the freed chunk is (by definition) free for use by the heap manager, the heap manager repurposes this “user data” region in freed chunks as the place where this additional metadata lives.

Recycling memory with bins

Internally, the heap manager needs to keep track of freed chunks so that malloc can reuse them during allocation requests. In a naive implementation, the heap manager could do this by simply storing all freed chunks together on some enormous linked list. This would work, but it would make malloc slow. Since malloc is a high-utilization component of most programs, this slowness would have a huge impact on the overall performance of programs running on the system.

To improve performance, the heap manager instead maintains a series of lists called “bins”, which are designed to maximize speed of allocations and frees.

There are 5 type of bins: 62 small bins, 63 large bins, 1 unsorted bin, 10 fast bins and 64 tcache bins per thread.

The small, large, and unsorted bins are the oldest type of bin and are used to implement what I’ll refer to here as the basic recycling strategy of the heap. The fast bins and tcache bins are optimizations that layer on top of these.

Confusingly, the small, large, and unsorted bins all live together in the same array in the heap manager’s source code. Index 0 is unused, 1 is the unsorted bin, bins 2-64 are small bins and bins 65-127 are large bins.

Chunk recycling: the basic strategy

Large Bins

The strategy for small bins is great for small allocations, but we can’t have a bin for every possible chunk size. For chunks over 512 bytes (1024 bytes on 64-bit), the heap manager instead uses “large bins”.

Each of the 63 “large bins” operates mostly the same way as small bins, but instead of storing chunks with a fixed size, they instead store chunks within a size range. Each large bin’s size range is designed to not overlap with either the chunk sizes of small bins or the ranges of other large bins. In other words, given a chunk’s size, there is exactly one small bin or large bin that this size corresponds to.

Because large bins store a range of sizes, insertions onto the bin have to be manually sorted, and allocations from the list require traversing the list. This makes large bins inherently slower than their small bin equivalents. Large bins are, however, used less frequently during most programs. This is because programs tend to allocate (and thus release) small allocations at a far higher rate than large allocations on average. For the same reason, “large bin” ranges are clustered towards smaller chunk sizes; the smallest “large bin” covers only the 64-byte range from 512 bytes to 576 bytes, whereas the second largest covers a size range of 256KB. The largest of the large bins covers all freed chunks above 1MB .

Unsorted Bin

The heap manager improves this basic algorithm one step further using an optimizing cache layer called the “unsorted bin”. This optimization is based on the observation that often frees are clustered together, and frees are often immediately followed by allocations of similarly sized chunks. For example, a program releasing a tree or a list will often release many allocations for every entry all at once, and a program updating an entry in a list might release the previous entry before allocating space for its replacement.

In these cases, merges of these freed chunks before putting the resulting larger chunk away in the correct bin would avoid some overhead, and being able to fast-return a recently freed allocation would similarly speed up the whole process.

The heap manager introduces the unsorted bin to take advantage of these observations. Instead of immediately putting newly freed chunks onto the correct bin, the heap manager coalesces it with neighbors, and dumps it onto a general unsorted linked list. During malloc , each item on the unsorted bin is checked to see if it “fits” the request. If it does, malloc can use it immediately. If it does not, malloc then puts the chunk into its corresponding small or large bin.

Fast Bins

Fast bins are a further optimization layered on top of the three basic bins we’ve already seen. These bins essentially keep recently released small chunks on a “fast-turnaround queue”, intentionally keeping the chunk live and not merging the chunk with its neighbors so that it can be immediately repurposed if a malloc request for that chunk size comes in very soon after the chunk is freed.

Like small bins, each fast bin is responsible only for a single fixed chunk size. There are 10 such fast bins, covering chunks of size 16, 24, 32, 40, 48, 56, 64, 72, 80, and 88 bytes plus chunk metadata.

Unlike their small bin cousins, fast bins chunks are never merged with their neighbors. In practice, the way this works is the heap manager doesn’t set the “P” bit at the start of the next chunk. If you like, you can think of this conceptually as the heap manager not “truly” freeing the chunk in the fast-bins.

Like their small bin counterparts, fast bins covers only a single chunk size, are thus automatically sorted, and so insertions and removals are incredibly fast. Moreover, since fast-binned chunks are never merge candidates, they can also be stored in singly-linked lists , rather than needing to be on doubly linked lists so that they can be removed from a list if the chunk gets merged.

The downside of fastbins, of course, is that fastbin chunks are not “truly” freed or merged, and this would eventually cause the memory of the process to fragment and balloon over time. To resolve this, heap manager periodically “ consolidates ” the heap. This “flushes” each entry in the fast bin by “actually freeing” it, i.e., merging it with adjacent free chunks, and placing the resulting free chunks onto the unsorted bin for malloc to later use.

This “consolidation” stage occurs whenever a malloc request is made that is larger than a fastbin can service (i.e., for chunks over 512 bytes or 1024 bytes on 64-bit), when freeing any chunk over 64KB (where 64KB is a heuristically chosen value), or when malloc_trim or mallopt are called by the program.

Tcache (per-thread cache) bins

The final optimization used by the heap manager to speed up allocations is the per-thread cache, or “ tcache” allocator. But first let’s look at the problem the tcache is trying to solve.

Each process on a given computer system has one or more threads running at the same time. Having multiple threads allows a process to execute multiple concurrent operations. For example, a high-volume web-server might have multiple simultaneous incoming requests, and the web-server might service each incoming request on its own thread, rather than have each request wait in line to be serviced.

Each thread in a given process shares the same address space, which is to say, each thread can see the same code and data in memory. Each thread gets its own registers and stack to store temporary local variables, but resources like global variables and the heap are shared between all of the threads.

Coordinating access to global resources like the heap is a complicated topic, and getting it wrong can lead to a problem known as “ race conditions” , which cause hard-to-debug crashes which are often also exploitable by hackers.

In our example of a website, suppose a web-request being serviced on one thread tries to update a database row, and another concurrent web-request tries to read from that same row. Normally, we’ll want to make sure the second thread never sees the row mid-write as it’s being overwritten by another thread and thus seeing the row in some partial or corrupted form. Databases solve this problem by making reads and writes appear to operate atomically : if two threads try to access the same row at the same time, one operation must complete before the next can begin. A very common way of solving these race-conditions is to force otherwise-simultaneous requests accessing a global resource into a sequential queue by using locks .

In general, locks work by one thread “marking” that it has taken ownership of a global resource before using it, then doing its operation, then marking that the resource is no longer in use. If another thread comes along and wants to use the resource and sees some other thread is using it, the thread waits until the other thread is done. This ensures that the global resource is only used by one thread at a time. But it comes with a cost: the thread that is waiting on the resource is stalling and wasting time. This is called “ lock contention ”.

For many global variables, this is an acceptable cost. But for the heap which is constantly in use by all threads, this cost quickly translates into the whole program slowing down.

The heap manager solves this problem using tcache , a per-thread cache designed to reduce lock contention for multi-threaded programs. This feature was added to the malloc memory allocation function in glibc 2.26 and is enabled by default.

Per-thread caching speeds up allocations by having per-thread bins of small chunks ready-to-go. That way, when a thread requests a chunk, if the thread has a chunk available on its tcache, it can service the allocation without ever needing to wait on a heap lock.

By default, each thread has 64 singly-linked tcache bins. Each bin contains a maximum of 7 same-size chunks ranging from 24 to 1032 bytes on 64-bit systems and 12 to 516 bytes on 32-bit systems .

How do chunks end up in tcache bins?

When a chunk is freed, the heap manager sees if the chunk will fit into a tcache bin corresponding to the chunk size. Like the fast-bin, chunks on the tcache bin are considered “in use”, and won’t be merged with neighboring freed chunks.

If the tcache for that chunk size is full (or the chunk is too big for a tcache bin), the heap manager reverts to our old slow-path strategy of obtaining the heap lock and then processing the chunk as before.

Corresponding tcache allocations are also pretty straightforward. Given a request for a chunk if a chunk is available on an appropriate tcache bin, the heap returns that chunk without ever obtaining the heap lock. If the chunk is too big for the tcache , we also continue as before.

In the case where we try and make an allocation, there is a corresponding tcache bin, but that bin is full, we do a slightly-modified allocation strategy. Rather than just taking the heap lock and finding a single chunk, we take the heap lock and opportunistically promote as many chunks as possible at this size to the tcache while we still hold the heap lock, up to the tcache bin limit of seven, and return the last matching chunk back to the user.

Putting it all together

Looking for a comprehensive training on exploit development?

Sign up for my upcoming Black Hat USA training in Las Vegas, where I will be teaching a 2-day course on “Arm-based IoT Exploit Development”. My 3-day training at Infiltrate is Sold Out. If your company is interested in private trainings and wants to save up to 50% compared to conference trainings, send a message to contact[at]azeria-labs.com.