First Fit

{{#include ../../../banners/hacktricks-training.md}}

First Fit

When you free memory in a program using glibc, different "bins" are used to manage the memory chunks. Here's a simplified explanation of two common scenarios: unsorted bins and fastbins.

Unsorted Bins

When you free a memory chunk that's not a fast chunk, it goes to the unsorted bin. This bin acts like a list where new freed chunks are added to the front (the "head"). When you request a new chunk of memory, the allocator looks at the unsorted bin from the back (the "tail") to find a chunk that's big enough. If a chunk from the unsorted bin is bigger than what you need, it gets split, with the front part being returned and the remaining part staying in the bin.

Example:

• You allocate 300 bytes (a), then 250 bytes (b), then free a and request again 250 bytes (c).
• When you free a, it goes to the unsorted bin.
• If you then request 250 bytes again, the allocator finds a at the tail and splits it, returning the part that fits your request and keeping the rest in the bin.
• c will be pointing to the previous a and filled with the a's contents.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins are used for small memory chunks. Unlike unsorted bins, fastbins add new chunks to the head, creating a last-in-first-out (LIFO) behavior. If you request a small chunk of memory, the allocator will pull from the fastbin's head.

Example:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

Modern glibc considerations (tcache >= 2.26)

On current glibc, "first fit" is still useful, but it is not the whole allocator story anymore:

1. Tcache is checked first. If the requested size has entries in tcache, the allocator never reaches the unsorted bin.
2. Exact fits found in the unsorted bin may be diverted into tcache first while glibc is filling the per-thread cache.
3. For small requests, glibc has a special last_remainder path that can be used before the generic unsorted-bin walk.
4. Very large requests can be served with mmap instead of the arena heap, so there may be no reusable unsorted chunk at all.

In practice, a first-fit primitive is easiest to reproduce when:

• The request size is larger than tcache_max (1032 bytes by default on 64-bit), or
• The corresponding tcache bin is already full (tcache_count defaults to 7), or
• Tcache was disabled by the environment

for (int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for (int i = 0; i < 7; i++) free(pool[i]);   // fill tcache[0x110]

If you control the environment, the following tunables are useful while studying or debugging allocator behaviour:

GLIBC_TUNABLES=glibc.malloc.tcache_count=0 ./binary
GLIBC_TUNABLES=glibc.malloc.mmap_threshold=0x200000 ./binary

The first disables tcache entirely. The second is helpful when a PoC unexpectedly gets mmapped chunks instead of arena chunks.

Reliable first-fit UAF

The most direct primitive is still the old one: free a chunk and immediately request a slightly smaller or equal size so the allocator gives you the same region back.

char *a = malloc(0x512);
char *b = malloc(0x256);
strcpy(a, "this is A!");
free(a);

char *c = malloc(0x500);   // returns the old "a" region
strcpy(c, "this is C!");

If the program still keeps a pointer to a, you now have a classic UAF:

• Reads through a disclose the new contents of c
• Writes through a corrupt c
• If the reused chunk is interpreted as a different structure, stale pointers/flags can become attacker-controlled

This is the core idea behind many note-manager and account-manager heap challenges: the allocator itself is behaving correctly, but the application still trusts a pointer to memory that has already been recycled.

Using first-fit splits for leaks or overlap

The important modern nuance is that splitting an unsorted-bin chunk does not magically create an overlap by itself. To get something stronger than a simple reallocation/UAF, you usually need an extra bug such as:

• A heap overflow that corrupts the size of a neighboring free chunk
• An off-by-one that changes which chunk will be split
• Another overlap that lets you keep a pointer into the remainder after the split

This is what recent CTFs tend to do. A common pattern is:

1. Force a large chunk into the unsorted bin.
2. Corrupt its size so the allocator believes a larger free region exists.
3. Request a smaller chunk from that forged region.
4. Let glibc split it and leave the remainder in the unsorted bin.
5. Reuse a still-reachable pointer that now overlaps the remainder and read its fd/bk pointers for a libc leak, or write through it to prepare a later tcache/fastbin attack.

In other words, modern first-fit is usually the reuse/split stage inside a longer chain, not the whole exploit by itself. The 2024 AngstromCTF heapify write-up is a good example: unsorted-bin splitting is used after a metadata corruption to keep a libc-bearing remainder overlapping attacker-controlled data. The HITCON 2024 setjmp write-up is another good reminder that you often need extra heap grooming just to get the allocator into the right state before the first-fit primitive becomes reachable.

Mitigations & Hardening

• Safe-linking (glibc >= 2.32) protects tcache/fastbin forward pointers, but it does not change how unsorted-bin chunks are reused or split.
• Malloc hooks were removed in glibc 2.34, so modern first-fit chains usually pivot into arbitrary read/write, FILE-structure corruption, tcache poisoning, or application-specific function pointers instead of __malloc_hook/__free_hook.
• Integrity checks in the doubly-linked bins still matter. If your exploit relies on a split remainder surviving long enough to be reused, any corrupted fd/bk pointers will crash the program before you get value from the primitive.

References

• https://blog.quarkslab.com/heap-exploitation-glibc-internals-and-nifty-tricks.html
• https://hackmd.io/@aneii11/H1S2snV40

{{#include ../../../banners/hacktricks-training.md}}