jemallocを読んでみる(その2)

昨日書いたとおり、jemallocのうち、size classがSmallである場合のallocation処理についてみてみます。
はじめにmalloc処理です。

void *
malloc(size_t size)
{
	void *ret;

/*  **** 1 ****  */
	if (malloc_init()) {
		ret = NULL;
		goto RETURN;
	}

/*  **** 2 ****  */
	if (size == 0) {
#ifdef MALLOC_SYSV
		if (opt_sysv == false)
#endif
			size = 1;
#ifdef MALLOC_SYSV
		else {
			ret = NULL;
			goto RETURN;
		}
#endif
	}

/*  **** 3 ****  */
	ret = imalloc(size);

1の部分はアリーナの初期化です。毎回初期化して重そうですが、malloc_initの中でフラグを見て既に初期化されているとすぐ戻ってくるようになっています。また、malloc_initはstatic関数で宣言されているので、まともなコンパイラならインライン化されて関数呼び出しのオーバヘッドもないと思います。初期化されていないときは実際に初期化処理に入りますが、その先はジャングルのようです。
2の部分はsizeが0の処理です。malloc(0)の挙動についてはsizeが1のメモリ領域が返るのが決まりだと思っていたのですが、NULLが返る場合もあるのかなと思いました。昔、X68000のmallocがNULLを返して色々なプログラムが動かなくて困ったことを思い出しました。
3のimallocがアロケーション処理の本体です。さらに中を見てみます。この後は、retがNULLだった場合のエラー処理が続きます。

static inline void *
imalloc(size_t size)
{

	assert(size != 0);

	if (size <= arena_maxclass)
		return (arena_malloc(choose_arena(), size, false));
	else
		return (huge_malloc(size, false));
}

sizeによってarena_mallocとhuge_mallocに分けられます。先頭のコメントに書いてあるとおり、ある程度以上のサイズのメモリ領域は複数の連続したアリーナから取るということが書いてありますが、huge_mallocがそれにあたると思います。今日はarena_mallocを見てみます。

static inline void *
arena_malloc(arena_t *arena, size_t size, bool zero)
{

	assert(arena != NULL);
	assert(arena->magic == ARENA_MAGIC);
	assert(size != 0);
	assert(QUANTUM_CEILING(size) <= arena_maxclass);

	if (size <= bin_maxclass) {
		return (arena_malloc_small(arena, size, zero));
	} else
		return (arena_malloc_large(arena, size, zero));
}

ここで、sizeによってsmallとlargeに分けられます。それぞれのアロケーションの方針も先頭のコメントに書いてあります。
今日は、arena_malloc_smallの前半について見てみます。

static inline void *
arena_malloc_small(arena_t *arena, size_t size, bool zero)
{
	void *ret;
	arena_bin_t *bin;
	arena_run_t *run;

	if (size < small_min) {
		/* Tiny. */
		size = pow2_ceil(size);
		bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW +
		    1)))];
#if (!defined(NDEBUG) || defined(MALLOC_STATS))
		/*
		 * Bin calculation is always correct, but we may need
		 * to fix size for the purposes of assertions and/or
		 * stats accuracy.
		 */
		if (size < (1U << TINY_MIN_2POW))
			size = (1U << TINY_MIN_2POW);
#endif
	} else if (size <= small_max) {
		/* Quantum-spaced. */
		size = QUANTUM_CEILING(size);
		bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
		    - 1];
	} else {
		/* Sub-page. */
		size = pow2_ceil(size);
		bin = &arena->bins[ntbins + nqbins
		    + (ffs((int)(size >> opt_small_max_2pow)) - 2)];
	}
	assert(size == bin->reg_size);

mallocするサイズが小さい場合(size classがsmall)、あらかじめ用意された列(run)から切り出していきます。ここで挙げた処理は切り出すための列がどれかを計算する処理です。sizeによってさらに細かく場合分けします。

Tiny

sizeが2,4,8の場合です。pow2_ceil(n)はn以上で一番小さい2のべき乗を返す関数です。例えば、pow2_ceil(6)は8を返します。この関数の定義はなかなか技巧的で楽しいです。

Quantum-spaced

sizeが16, 32, 48, .... 496, 512の場合です。QUANTUM_CEILING(size)はsizeを16の倍数に切り上げるマクロです。

Sub-page

sizeが1024, 2048の場合です。

こうやって求めた列(ここではbinという変数に入っている)から割り当てるメモリ領域を切り出します。切り出す処理はまた今度ということで。

あーー、しんどい。つづく