bin_at in dlmalloc

Question

In glibc malloc.c or dlmalloc It said "repositioning tricks"As in blew, and use this trick in bin_at.

bins is a array,the space is allocated when av(struct malloc_state) is allocated.doesn't it? the sizeof(bin[i]) is less then sizeof(struct malloc_chunk*)?

When bin_at(M,1)(which is used as unsorted_chunks) is called,the result is: bin[0] - offsetof (struct malloc_chunk, fd) bin[0] - 8 is right?

Who can describe this trick for me? I can't understand the bin_at macro.why they get the bins address use this method?how it works?

Very thanks,and sorry for my poor English.

/*
     To simplify use in double-linked lists, each bin header acts
    as a malloc_chunk. This avoids special-casing for headers.
    But to conserve space and improve locality, we allocate
    only the fd/bk pointers of bins, and then use repositioning tricks
    to treat these as the fields of a malloc_chunk*.
*/

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

The malloc_chunk struct like this:

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

And the bin type like this:

typedef struct malloc_chunk* mbinptr;

struct malloc_state {
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

#if THREAD_STATS
  /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
  long stat_lock_direct, stat_lock_loop, stat_lock_wait;
#endif

  /* 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];

  /* Linked list */
  struct malloc_state *next;

#ifdef PER_THREAD
  /* Linked list for free arenas.  */
  struct malloc_state *next_free;
#endif

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

Answer 1

Presumably struct malloc_chunk looks something like:

struct malloc_chunk {
    /* ... fields here ... */
    struct malloc_chunk *fd;
    struct malloc_chunk *bk;
    /* ... more fields here ... */
};

...and the ->bins type looks like:

struct {
    struct malloc_chunk *fd;
    struct malloc_chunk *bk;
};

The bin_at macro makes a pointer to the latter structure into a fake pointer to the former structure, for the purpose of accessing the fd and bk members only (since they're the only ones that exist in the smaller one). ie bin_at(m, i)->fd and bin_at(m, i)->bk are the same as m->bins[(i - 1) * 2].fd and m->bins[(i - 1) * 2].bk, but bin_at can be used in places that expect a struct malloc_chunk * (as long as they only use the fd and bk members).

It's a bit of a hack. I wouldn't do this in your own code - remember Kernighan's advice about writing code as cleverly as possible:

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." – Brian W. Kernighan

---

OK, so ->bins isn't an array of structs at all - it's an array of struct malloc_chunk *.

Notice that ->bins[(i - 1) * 2] refers to the i-th pair of struct malloc_chunk * pointers in the ->bins array. This pair is equivalent to the fd and bk pair of pointers in a struct malloc_chunk, with the first (->bins[(i - 1) * 2]) being equivalent to fd (they could have instead made ->bins an array of the smaller struct I suggested above; it would be functionally equivalent and probably clearer).

The bin_at macro lets the code insert one of those pairs of pointers that are in the ->bins array into a linked list of struct malloc_chunk structs - without allocating an entire struct malloc_chunk. This is the space saving they are talking about.

The bin_at macro takes a index into the bins array, then does "if this pointer was actually the fd value in a struct malloc_chunk, then calculate a pointer to where that struct malloc_chunk would be". It does this by subtracting the offset of the fd member within a struct malloc_chunk from the address of the item in the bins array.

It doesn't really "locate the bins[i]" - that's straightforward (&bins[i]). It actually locates the imaginary struct malloc_chunk that bins[i] is the fd member of.

Sorry, it's complicated to explain because it's a complicated concept.