# Bins

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.

{% hint style="info" %}
*Note:* this movement **is not physical**
{% endhint %}

## 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

{% hint style="info" %}
The size include meatada
{% endhint %}

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.

{% hint style="info" %}
*Note*: Chunks in fastbins are treated as *allocated* chunks in the sense that they are not consolidated with neighboring free chunks.
{% endhint %}

## 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`.