Skip to main content

​
Overview

The first-fit algorithm is the core allocation strategy used by glibc malloc when selecting a free chunk to satisfy a memory request. When malloc needs to allocate memory, it searches through the appropriate bin and returns the first chunk that is large enough, rather than searching for the best-fitting chunk.
This seemingly simple design decision has significant implications for heap exploitation, particularly in use-after-free scenarios.

​
How First-Fit Works

When you call malloc(size), the allocator:
1

Calculates required size

Converts the requested size to the actual chunk size needed (including metadata and alignment).
2

Searches for a free chunk

Looks through the appropriate bin (tcache, fastbin, smallbin, etc.) for a free chunk.
3

Returns first match

Returns the first chunk that is large enough, even if a better-fitting chunk exists later in the list.
4

Splits if necessary

If the chunk is significantly larger than needed, it may be split, with the remainder returned to the free list.
First-fit prioritizes speed over optimal memory usage. It avoids traversing the entire free list to find the best match.

​
Demonstration Program

The following program demonstrates first-fit allocation behavior:
first_fit.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	fprintf(stderr, "This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.\n");
	fprintf(stderr, "glibc uses a first-fit algorithm to select a free chunk.\n");
	fprintf(stderr, "If a chunk is free and large enough, malloc will select this chunk.\n");
	fprintf(stderr, "This can be exploited in a use-after-free situation.\n");

	fprintf(stderr, "Allocating 2 buffers. They can be large, don't have to be fastbin.\n");
	char* a = malloc(0x512);
	char* b = malloc(0x256);
	char* c;

	fprintf(stderr, "1st malloc(0x512): %p\n", a);
	fprintf(stderr, "2nd malloc(0x256): %p\n", b);
	fprintf(stderr, "we could continue mallocing here...\n");
	fprintf(stderr, "now let's put a string at a that we can read later \"this is A!\"\n");
	strcpy(a, "this is A!");
	fprintf(stderr, "first allocation %p points to %s\n", a, a);

	fprintf(stderr, "Freeing the first one...\n");
	free(a);

	fprintf(stderr, "We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at %p\n", a);

	fprintf(stderr, "So, let's allocate 0x500 bytes\n");
	c = malloc(0x500);
	fprintf(stderr, "3rd malloc(0x500): %p\n", c);
	fprintf(stderr, "And put a different string here, \"this is C!\"\n");
	strcpy(c, "this is C!");
	fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
	fprintf(stderr, "first allocation %p points to %s\n", a, a);
	fprintf(stderr, "If we reuse the first allocation, it now holds the data from the third allocation.\n");
}

​
Running the Program

gcc first_fit.c -o first_fit
./first_fit

​
Key Observations

Let’s break down what happens in this program:
1

Initial allocations

char* a = malloc(0x512);  // Gets address 0x555555559260
char* b = malloc(0x256);  // Gets address 0x555555559780
strcpy(a, "this is A!");
Two chunks are allocated. Pointer a contains “this is A!”.
2

Free first chunk

free(a);  // Returns chunk to free list
The 0x512-byte chunk is freed and added to the appropriate bin (likely unsorted bin or tcache).
3

Allocate smaller chunk

c = malloc(0x500);  // Gets address 0x555555559260
strcpy(c, "this is C!");
Because 0x500 < 0x512, the freed chunk at a’s address is large enough. First-fit returns this chunk immediately.
4

Use-after-free

fprintf(stderr, "first allocation %p points to %s\n", a, a);
// Prints: first allocation 0x555555559260 points to this is C!
Now a and c point to the same memory. Reading from a shows data written via c.
Critical Security Implication: The old pointer a still points to valid memory, but that memory now belongs to a new allocation c. This is a use-after-free vulnerability.

​
Exploitation Implications

First-fit allocation makes certain heap exploits more reliable:

​
Use-After-Free (UAF)

Example UAF scenario
struct User {
    char name[64];
    void (*print)(struct User*);
};

// Allocate and free a User object
struct User* user = malloc(sizeof(struct User));
user->print = print_user;
free(user);

// Attacker can allocate same-sized chunk
char* attacker_data = malloc(sizeof(struct User));
strcpy(attacker_data, "\x90\x90...\x41\x41\x41\x41...");

// Now user->print points to attacker-controlled data!
user->print(user);  // Can hijack control flow

​
Heap Spray

First-fit makes heap spraying more predictable:
1

Allocate many objects

Fill the heap with objects containing exploit payloads.
2

Trigger vulnerability

Cause a UAF or similar bug that allocates memory.
3

Exploit

Because of first-fit, the vulnerability is likely to reuse one of your controlled chunks.

​
Heap Feng Shui

Exploiters can manipulate heap layout by:
  1. Allocating chunks in specific order
  2. Freeing strategic chunks to create controlled free list
  3. Triggering vulnerability that allocates from manipulated free list
  4. Achieving predictable memory reuse due to first-fit
First-fit makes the heap state more deterministic, which actually helps attackers create reliable exploits.

​
Why Not Best-Fit?

You might wonder why glibc doesn’t use a best-fit algorithm (find the smallest chunk that fits). The answer is performance:

First-Fit

  • Fast: O(1) to O(n) with early exit
  • Returns first match found
  • Less memory traversal
  • Good locality

Best-Fit

  • Slow: O(n) always
  • Must check all chunks
  • More memory traversal
  • Better memory efficiency
For most applications, the performance gain from first-fit outweighs the slight memory fragmentation cost.

​
Defense Considerations

To protect against first-fit-based exploits:
1

Avoid use-after-free

Null out pointers after freeing them, and implement proper lifetime management.
2

Use memory safety tools

AddressSanitizer can detect UAF bugs during development.
3

Consider safe languages

Languages with automatic memory management eliminate entire classes of heap exploits.
4

Enable hardening features

Use allocators with additional security checks (e.g., safe linking in modern glibc).

​
Practical Exercise

Try this experiment with the program:
1

Modify the allocation size

Change malloc(0x500) to malloc(0x520) (larger than the freed chunk).
2

Observe the result

The new allocation will get a different address because it doesn’t fit.
3

Try with tcache

Allocate/free 7 same-sized chunks to fill tcache, then observe first-fit behavior.

Tcache Poisoning

Exploit tcache’s LIFO structure with first-fit

Fastbin Dup

Double-free with first-fit allocation

House of Spirit

Create fake chunks that first-fit will allocate

Heap Basics

Review malloc fundamentals

​
Summary

First-fit allocation is:
  • Fast: Returns the first suitable chunk without exhaustive search
  • Predictable: Same allocation patterns produce consistent results
  • Exploitable: Enables reliable use-after-free and heap grooming attacks
  • Fundamental: Understanding this is essential for heap exploitation

Build docs developers (and LLMs) love

Get started for freeTalk to us