bin_at в dlmalloc

Question

В glibc malloc.c или dlmalloc было сказано: " Репозиционные трюки " Как и в Blow, используйте этот трюк в bin_at.

bin - это массив, пространство выделяется при выделении av (struct malloc_state). Не так ли? sizeof (bin [i]) меньше, чем sizeof (struct malloc_chunk *)?

Когда вызывается bin_at (M, 1) (который используется как unsorted_chunks), результатом будет: bin [0] - offsetof (struct malloc_chunk, fd) bin [0] - 8 верно?

Кто может описать этот трюк для меня? Я не могу понять макрос bin_at. Почему они получают адрес бинов, используют этот метод? Как это работает?

Большое спасибо и извините за мой плохой английский.

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

Структура malloc_chunk выглядит следующим образом:

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;
};

И тип корзины такой:

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

Предположительно struct malloc_chunk выглядит примерно так:

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

... и тип ->bins выглядит следующим образом:

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

Макрос bin_at превращает указатель на последнюю структуру в поддельный указатель на прежнюю структуру, чтобы получить доступ только к элементам fd и bk (поскольку они единственные, которые существуют в меньший). то есть bin_at(m, i)->fd и bin_at(m, i)->bk совпадают с m->bins[(i - 1) * 2].fd и m->bins[(i - 1) * 2].bk, но bin_at можно использовать в местах, где ожидается struct malloc_chunk * (при условии, что они используют только fd и bk члены).

Это что-то вроде хака. Я бы не стал делать это в вашем собственном коде - помните совет Кернигана о том, как писать код как можно умнее:

"Отладка вдвое сложнее, чем запись код в первую очередь. Поэтому, если вы напишите код как умно, насколько это возможно, вы, по определение, недостаточно умное для отладки это. "- Брайан В. Керниган

---

ОК, так что ->bins это вообще не массив структур - это массив struct malloc_chunk *.

Обратите внимание, что ->bins[(i - 1) * 2] относится к i-й паре из struct malloc_chunk * указателей в массиве ->bins. Эта пара эквивалентна паре указателей fd и bk в struct malloc_chunk, причем первая (->bins[(i - 1) * 2]) эквивалентна fd (вместо этого они могли бы сделать ->bins массивом меньшего размера). структура, которую я предложил выше, она будет функционально эквивалентной и, вероятно, более понятной)

Макрос bin_at позволяет коду вставить одну из тех пар указателей, которые есть в массиве ->bins, в связанный список структур struct malloc_chunk - без выделения всего struct malloc_chunk. Это экономия места, о которой они говорят.

Макрос bin_at берет индекс в массив bins и затем "если этот указатель был на самом деле значением fd в struct malloc_chunk, то вычислить указатель на то, где будет struct malloc_chunk" , Это делается путем вычитания смещения члена fd в пределах struct malloc_chunk из адреса элемента в массиве bins.

Это на самом деле не «находит bins[i]» - это просто (&bins[i]). На самом деле он находит воображаемый struct malloc_chunk, bins[i] которого является fd членом.

Извините, это сложно объяснить, потому что это сложная концепция.