Operations of the Fastbin
Fastbins are a singly-linked list of chunks. The point of these is that very small chunks are reused quickly and efficiently. To aid this, chunks of fastbin size do not consolidate (they are not absorbed into surrounding free chunks once freed).
A fastbin is a LIFO (Last-In-First-Out) structure, which means the last chunk to be added to the bin is the first chunk to come out of it. Glibc only keeps track of the HEAD, which points to the first chunk in the list (and is set to 0
if the fastbin is empty). Every chunk in the fastbin has an fd
pointer, which points to the next chunk in the bin (or is 0
if it is the last chunk).
When a new chunk is freed, it's added at the front of the list (making it the head):
The
fd
of the newly-freed chunk is overwritten to point at the old head of the listHEAD is updated to point to this new chunk, setting the new chunk as the head of the list
Let's have a visual demonstration (it will help)! Try out the following C program:
We get:
As you can see, the chunk a
gets reassigned to chunk f
, b
to e
and c
to d
. So, if we free()
a chunk, there's a good chance our next malloc()
- if it's of the same size - will use the same chunk.
It can be really confusing as to why we add and remove chunks from the start of the list (why not the end?), but it's really just the most efficient way to add an element. Let's say we have this fastbin setup:
In this case HEAD points to a
, and a
points onwards to b
as the next chunk in the bin (because the fd
field of a
points to b
). Now let's say we free another chunk c
. If we want to add it to the end of the list like so:
We would have to update the fd
pointer of b
to point at c
. But remember that glibc only keeps track of the first chunk in the list - it only has the HEAD stored. It has no information about the end of this list, which could be many chunks long. This means that to add c
in at the end, it would first have to start at the head and traverse through the entire list until it got to the last chunk, then overwrite the fd
field of the last chunk to point at c
and make c
the last chunk.
Meanwhile, if it adds at the HEAD:
All we need to do is:
Set the
fd
ofc
to point ata
This is easy, as
a
was the old head, so glibc had a pointer to it stored already
HEAD is then updated to
c
, making it the head of the listThis is also easy, as the pointer to
c
is freely available
This has much less overhead!
For reallocating the chunk, the same principle applies - it's much easier to update HEAD to point to a
by reading the fd
of c
than it is to traverse the entire list until it gets to the end.
Last updated