First-Fit Allocation

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:

Calculates required size

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

Searches for a free chunk

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

Returns first match

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

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

This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.
glibc uses a first-fit algorithm to select a free chunk.
If a chunk is free and large enough, malloc will select this chunk.
This can be exploited in a use-after-free situation.
Allocating 2 buffers. They can be large, don't have to be fastbin.
1st malloc(0x512): 0x555555559260
2nd malloc(0x256): 0x555555559780
we could continue mallocing here...
now let's put a string at a that we can read later "this is A!"
first allocation 0x555555559260 points to this is A!
Freeing the first one...
We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at 0x555555559260
So, let's allocate 0x500 bytes
3rd malloc(0x500): 0x555555559260  # Same address!
3rd allocation 0x555555559260 points to this is C!
first allocation 0x555555559260 points to this is C!  # Data changed!
If we reuse the first allocation, it now holds the data from the third allocation.

Key Observations

Let’s break down what happens in this program:

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!”.

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).

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.

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:

Allocate many objects

Fill the heap with objects containing exploit payloads.

Trigger vulnerability

Cause a UAF or similar bug that allocates memory.

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:

Allocating chunks in specific order
Freeing strategic chunks to create controlled free list
Triggering vulnerability that allocates from manipulated free list
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:

Avoid use-after-free

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

Use memory safety tools

AddressSanitizer can detect UAF bugs during development.

Consider safe languages

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

Enable hardening features

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

Practical Exercise

Try this experiment with the program:

Modify the allocation size

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

Observe the result

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

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

Get Started

Fundamentals

Fastbin Techniques

Tcache Techniques

House Techniques

Bin & Chunk Manipulation

Advanced Techniques

Glibc Versions

Tools & Resources

First-Fit Allocation

Overview

How First-Fit Works

Demonstration Program

Running the Program

Key Observations

Exploitation Implications

Use-After-Free (UAF)

Heap Spray

Heap Feng Shui

Why Not Best-Fit?

First-Fit

Best-Fit

Defense Considerations

Practical Exercise

Tcache Poisoning

Fastbin Dup

House of Spirit

Heap Basics

Summary

​Overview

​How First-Fit Works

​Demonstration Program

​Running the Program

​Key Observations

​Exploitation Implications

​Use-After-Free (UAF)

​Heap Spray

​Heap Feng Shui

​Why Not Best-Fit?

First-Fit

Best-Fit

​Defense Considerations

​Practical Exercise

​Related Techniques

Tcache Poisoning

Fastbin Dup

House of Spirit

Heap Basics

​Summary

Overview

How First-Fit Works

Demonstration Program

Running the Program

Key Observations

Exploitation Implications

Use-After-Free (UAF)

Heap Spray

Heap Feng Shui

Why Not Best-Fit?

Defense Considerations

Practical Exercise

Related Techniques

Summary