35.1. ビン

戻る		次へ

　ビンはフリーチャンクを保持するデータ構造です。

　フリーチャンクを連結するとフリーリストなんて表現を使うこともありますが、それとは微妙に違うと思います。

　ビンには 4 種類のものがあります。

Fast bin（ファーストビン）
Unsorted bin（未整理のチャンクのビン）
Small bin（小さめのチャンクのビン）
Large bin（大きめのチャンクのビン）

　これらのビンは malloc_state 構造体に定義されています。

malloc.c（https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c）.

1674 struct malloc_state
1675 {
1676   /* Serialize access.  */
1677   __libc_lock_define (, mutex);
1678
1679   /* Flags (formerly in max_fast).  */
1680   int flags;
1681
1682   /* Set if the fastbin chunks contain recently inserted free blocks.  */
1683   /* Note this is a bool but not all targets support atomics on booleans.  *
1684   int have_fastchunks;
1685
1686   /* Fastbins */
1687   mfastbinptr fastbinsY[NFASTBINS];
1688
1689   /* Base of the topmost chunk -- not otherwise kept in a bin */
1690   mchunkptr top;
1691
1692   /* The remainder from the most recent split of a small request */
1693   mchunkptr last_remainder;
1694
1695   /* Normal bins packed as described above */
1696   mchunkptr bins[NBINS * 2 - 2];

　Fast bin（ファーストビン）は fastbinsY[] 配列に保管されます。

　16 バイトから 80 バイトまでのサイズを保有できますが、以下のような特徴があります。

ビンの数は 10 個
サイズは範囲ではなく、特定値をサポート
各ビンは LIFO / 単方向の連結リストを持つ
32 ビットアーキテクチャでは 8 バイト間隔 [16,24,32,40,48,56,64,72,80,88]
64 ビットアーキテクチャでは 16 バイト間隔 [32,48,64,80,96,112,128,144,160,176]

　ビンは 10 個あり 32 ビットから 64 ビットのアーキテクチャかによって、各ビンが保持するバイトサイズは異なります。

　まあ、考え方としては良く使うバイトサイズのフリーチャンクは、早く取り出せるデータ構造にキャッシュしてみたいな感じです。

　それで Fast bin（ファーストビン）なるものは以下のソースコードに記述されてます。

malloc.c（https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c）.

1570 /*
1571    Fastbins
1572
1573     An array of lists holding recently freed small chunks.  Fastbins
1574     are not doubly linked.  It is faster to single-link them, and
1575     since chunks are never removed from the middles of these lists,
1576     double linking is not necessary. Also, unlike regular bins, they
1577     are not even processed in FIFO order (they use faster LIFO) since
1578     ordering doesn't much matter in the transient contexts in which
1579     fastbins are normally used.
1580
1581     Chunks in fastbins keep their inuse bit set, so they cannot
1582     be consolidated with other free chunks. malloc_consolidate
1583     releases all chunks in fastbins and consolidates them with
1584     other free chunks.
1585  */
1586
1587 typedef struct malloc_chunk *mfastbinptr;
1588 #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1589
1590 /* offset 2 to use otherwise unindexable first 2 bins */
1591 #define fastbin_index(sz) \
1592   ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1593
1594
1595 /* The maximum fastbin request size we support */
1596 #define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
1597
1598 #define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

　この中で注目すべきは MAX_FAST_SIZE と fastbin_index(sz) となります。

　まずは MAX_FAST_SIZE ですが、これは最大値のことです。

　SIZE_SZ は size_t 型のバイトサイズと同じと考えると 64 ビットアーキテクチャだと 8 バイトなので 160 バイトが最大サイズですね。

　32 ビットアーキテクチャだと SIZE_SZ は 4 バイトと推理できるので 80 バイトになります。

表35.1 fastbin_index(sz) の結果

sz の値	8	16	24	32	40	48	56	64	72	80	88	96	112	128	144	160	176
32 ビットのインデックス	-1	0	1	2	3	4	5	6	7	8	9
64 ビットのインデックス		-1		0		1		2		3		4	5	6	7	8	9

　このように 32 ビットアーキテクチャでは 16 バイトから 88 バイトを 8 バイト間隔にしたビンが存在します。

　64 ビットアーキテクチャでは 32 バイトから 176 バイトを 16 バイト間隔にしたビンが存在します。

　最後にNFASTBINS はファーストビンの中の要素数ですが request2size(req) マクロを使っています。

　request2size(req) の定義は以下のようになります。

malloc.c（https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c）.

  1217 /* pad request bytes into a usable size -- internal version */
  1218
  1219 #define request2size(req)                                         \
  1220   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
  1221    MINSIZE :                                                      \
  1222    ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

　考え方としては小さけりゃ MINSIZE にし、後はアラインメントを取るってことみたいです。

　複雑なので検証用のプログラムを用意してみましょう。

main.c.

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <stddef.h>
  4
  5 #define INTERNAL_SIZE_T size_t
  6 #define SIZE_SZ sizeof(size_t)
  7 #define MALLOC_ALIGN_MASK (2*SIZE_SZ - 1)
  8
  9 #define NBINS             128
 10 #define NSMALLBINS         64
 11 #define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
 12 #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
 13 #define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
 14
 15 struct malloc_chunk {
 16
 17   INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
 18   INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
 19
 20   struct malloc_chunk* fd;         /* double links -- used only if free. */
 21   struct malloc_chunk* bk;
 22
 23   /* Only used for large blocks: pointer to next larger size.  */
 24   struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
 25   struct malloc_chunk* bk_nextsize;
 26 };
 27
 28 /* The smallest possible chunk */
 29 #define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
 30
 31 /* The smallest size we can malloc is an aligned minimal chunk */
 32
 33 #define MINSIZE  \
 34   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
 35
 36
 37 /* pad request bytes into a usable size -- internal version */
 38
 39 #define request2size(req)                                         \
 40   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
 41    MINSIZE :                                                      \
 42    ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
 43
 44 /* offset 2 to use otherwise unindexable first 2 bins */
 45 #define fastbin_index(sz) \
 46   ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
 47
 48
 49 /* The maximum fastbin request size we support */
 50 #define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
 51
 52 #define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
 53
 54 int main()
 55 {
 56   printf("%d\n",NFASTBINS);
 57   return 0;
 58 }

ビルドと出力結果.

$ gcc main.c
$ ./a.out
10

　これによると NFASTBINS は 10 として評価されます。