Bins

Free chunks collections

A bin is a list of free chunks.

There are different bins type differentiated depending on the size of chunks within them.

When a is chunk is freed, it is moved into the associated bin.

Note: this movement is not physical

Fast bins

There are 10 fast bins that contain chunks of the same size :

• 16 bytes

• 24 bytes

• 32 bytes

• 40 bytes

• 48 bytes

• 56 bytes

• 64 bytes

• 72 bytes

• 80 bytes

• 88 bytes

The size include meatada

Addition and deletion occur in a Last in Frist Out (LIFO) manner.

To store chunks, 4 fewer bytes will be available (on a platform where pointers use 4 bytes). Only the prev_size and size field of this chunk will hold metadata for allocated chunks. prev_size of next contiguous chunk will hold user data.

No two contiguous free fast chunks coalesce together.

Note: Chunks in fastbins are treated as allocated chunks in the sense that they are not consolidated with neighboring free chunks.

Unsorted bin

There is only 1 unsorted bin. Small and large chunks, when freed, end up in this bin. The primary purpose of this bin is to act as a cache layer (kind of) to speed up allocation and deallocation requests.

Small bins

There are 62 small bins.

Small bins are faster than large bins but slower than fast bins. Each bin maintains a doubly-linked list. Insertions happen at the 'HEAD' while removals happen at the 'TAIL' (in a FIFO manner).

Like fast bins, each bin has chunks of the same size. The 62 bins have sizes: 16, 24, ... , 504 bytes.

While freeing, small chunks may be coalesced together before ending up in unsorted bins.

Large bins

There are 63 large bins.

Each bin maintains a doubly-linked list. A particular large bin has chunks of different sizes, sorted in decreasing order (i.e. largest chunk at the 'HEAD' and smallest chunk at the 'TAIL'). Insertions and removals happen at any position within the list.

Like small chunks, while freeing, large chunks may be coalesced together before ending up in unsorted bins.

There are two special types of chunks which are not part of any bin.

Top chunk

It is the chunk which borders the top of an arena. While servicing malloc requests, it is used as the last resort.

If still more size is required, it can grow using the sbrk system call. The PREV_INUSE flag is always set for the top chunk.

Last remainder chunk

It is the chunk obtained from the last split.

Sometimes, when exact size chunks are not available, bigger chunks are split into two. One part is returned to the user whereas the other becomes the last remainder chunk.

Head and Tail

Each bin is represented by two values, the HEAD and TAIL.

As it sounds, HEAD is at the top and TAIL at the bottom.

Most insertions happen at the HEAD, so in LIFO structures (such as the fastbins) reallocation occurs there too, whereas in FIFO structures (such as small bins) reallocation occurs at the TAIL.

For fastbins, the TAIL is null.