Understanding the glibc malloc binning implementation

Question

lately i've been studying the internals of the glibc malloc implementation. However, there is one thing i can't seem to understand regarding bin indexing. So within the malloc_state structure we have the following declarations, lightly formatted for brevity:

struct malloc_state
{
  /* 
       .
       .
       Some declarations
       .
       .
  */

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  
  /* 
       .
       .
       Some more declarations
       .
       .
  */
};

Now my question is regarding the declaration of the bins array within this structure. The bins array is declared as follows: mchunkptr bins[NBINS * 2 - 2];

And to my understanding pointers to the bins are obtained using the bin_at macro defined as follows:

typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))               \
             - offsetof (struct malloc_chunk, fd))

Now specifically, my question is as follows. Why are there approximately twice the number of bins reserved in the bins array? I understand that there is one bin reserved for the unsorted chunks resulting from a call to free and that there are NBINS number of bins for already size sorted free chunks. However, i don't understand the use for the remaining bins.

I suspect there is a reasoning behind this. However, from the source code this doesn't become clear to me. If any of you have some pointers or perhaps documentation for why this is done, that would be greatly appreciated!

Thank you in advance!

Answer 1

Since bins are doubly-linked lists, each bin header contains two pointers, not one: the first pointer points at the head of the list, and the second one points at the tail. That's why there are twice as many pointers as there are bins. (Note that bin number 0 is not used, so the number of bins is really NBINS - 1.)

As is common in doubly-linked list implementations, the list is effectively circular; the header can be viewed as a link entry. That avoids the necessity to check whether the bin is before adding an element. (In an empty bin, both first and last point at the bin header itself.) However, the forward (fd) and backward (bk) pointers in a malloc_chunk are not at the beginning of the chunk. In order to treat the pair of pointers in the bin array as a chunk entry, the address of the pair of pointers needs to be reverse offset by the offset of the fd pointer in the malloc_chunk.

A diagram might help. Here's how it looks with two chunks in the bin:

     Bins Array                Chunk 0                Chunk 1 

+--> XXXXXXXXXX <-\     /--> +--------+ <-\     /--> +--------+ <-----+
|    XXXXXXXXXX    \   /     |  p_sz  |    \   /     |  p_sz  |       |
|    XXXXXXXXXX     \ /      +--------+     \ /      +--------+       |
|    XXXXXXXXXX      X       |   sz   |      X       |   sz   |       |
|    +--------+     / \      +--------+     / \      +--------+       |
|    | [2i-2] | -->/   \     |   fd   | -->/   \     |   fd   | ->+   |
|    +--------+         \    +--------+         \    +--------+   |   |
|    | [2i-1] | -->+     \<- |   bk   |          \<- |   bk   |   |   |
|    +--------+    |         +--------+              +--------+   |   |
|                  |                                              |   |
|                  +----------------------------------------------+---+
|                                                                 |
+<----------------------------------------------------------------+

The XXXs show the reverse offset which allows the pointers to be consistent.