BoehmGC解読室 - 1 (small object の allocate)前編

初めに

青い本の9章を参考にしながらBoehmGCを読んでみます。
実は大分前から読み始めていましたが、ブログに書いておけば忘れないのでいいかなーと言うことで
まとめることにしました。
 

注意

BoehmGCは関数名は非常にわかりやすくて、コメントもいっぱい書いてありますので
そこの所はいいんですが、変数名が常に4文字以下くらいで軽く暗号っぽい雰囲気なので
とても燃えると思います。
 

BoehmGCって何?

Boehm GC を使ってみる
Boehm GC¤ò»È¤ª¤¦
あとはひたすらググる
 

small object と large object

GC_MALLOC というものがあります。
GCの対象にしたい構造体なり何なりをGC_MALLOCで確保することでBoehmさんがヨロシクやるのです。
(素晴らしい)
そして、青い本にはこう書いてありました。

オブジェクトは大きいものと小さいもので別々にハンドルされる。

どうやら、hblk(heap block の略)というブロックの半分以下のサイズのものは small object として扱われ、
それより、大きいものは big object として扱われるようです。
 
という事で今回は small objcet はどういう風に確保されるのか見ていきます。
 

GC_malloc

GC_mallocを見つけないとお話になりませんので、grep -r でもしますか。
いや、emacs で moccur-grep-find でもしますか。
 

// malloc.c

void * GC_malloc(size_t lb)
{
    void *op;
    void **opp;
    size_t lg;
    DCL_LOCK_STATE;

    if(SMALL_OBJ(lb)) { /** (1) **/
	lg = GC_size_map[lb]; /** (2) **/
	opp = (void **)&(GC_objfreelist[lg]); /** (3) **/
	LOCK();
        if( EXPECT((op = *opp) == 0, 0) ) {
            UNLOCK();
            return(GENERAL_MALLOC((word)lb, NORMAL)); /** (4) **/
        }
        *opp = obj_link(op);
        obj_link(op) = 0;
        GC_bytes_allocd += GRANULES_TO_BYTES(lg); /** (5) **/
        UNLOCK();
        return op;
   } else {
       return(GENERAL_MALLOC(lb, NORMAL));
   }
}

こんな感じで見つけることができました。Moccur-grep便利ですね。うん。
 

(1)SMALL_OBJ

さて、SMALL_OBJは何をやってるマクロなんでしょうか。

// gc_priv.h

#  define SMALL_OBJ(bytes) EXPECT((bytes) <= (MAXOBJBYTES), 1)

#define MAXOBJBYTES ((size_t)CPP_MAXOBJBYTES)

#define CPP_MAXOBJBYTES (CPP_HBLKSIZE/2)

EXPECT には海より深いマクロが組み込まれていますが、これはまた後日。(ヒント:__builtin_expect)
MAXOBJBYTES以下か?というのがSMALL_OBJの処理ですね。
CPP_MAXOBJBYTES で半分にしていますね。何を半分にしてるんでしょうか?

// gc_priv.h

#ifndef HBLKSIZE
# ifdef SMALL_CONFIG
#   define CPP_LOG_HBLKSIZE 10
# else
#   if (CPP_WORDSZ == 32) || (defined(HPUX) && defined(HP_PA))
      /* HPUX/PA seems to use 4K pages with the 64 bit ABI */
#     define CPP_LOG_HBLKSIZE 12
#   else
#     define CPP_LOG_HBLKSIZE 13
#   endif
# endif
#else
# if HBLKSIZE == 512
#   define CPP_LOG_HBLKSIZE 9
# endif

/** 省略 **/

# if HBLKSIZE == 16384
#   define CPP_LOG_HBLKSIZE 14
# endif
# ifndef CPP_LOG_HBLKSIZE
    --> fix HBLKSIZE
# endif
# undef HBLKSIZE
#endif


# define CPP_HBLKSIZE (1 << CPP_LOG_HBLKSIZE)

HBLKSIZEを半分にしているようですね。
irb か何かでシフト処理をやってみるとHBLKSIZEと同じになる事が分かると思います。
 

結論

SMALL_OBJは heap block size の半分以下かどうかを判断している。
 

(2)GC_size_map[lb]

lbは length byte の略っぽいです。確保するバイト数の事ですね。

// gc_priv.h
# define GC_size_map GC_arrays._size_map

struct _GC_arrays {

/** 省略 **/

    size_t _size_map[MAXOBJBYTES+1];

};

GC_arraysは後で説明するとして(という感じで逃げる)、MAXOBJBYTES+1個の配列のようです。
MAXOBJBYTESとはさっきも説明した通り、heap block size の半分ですね。
この中には何が入ってるのか、推測すると。多分、freelistのindexが入ってんだろうなーという感じ。
実際に _size_mapの値を入れている所を探してみましょうか。
 

//misc.c

void GC_init_size_map(void)
{
    int i;

    /* Map size 0 to something bigger.			*/
    /* This avoids problems at lower levels.		*/
      GC_size_map[0] = 1;
    for (i = 1; i <= GRANULES_TO_BYTES(TINY_FREELISTS-1) - EXTRA_BYTES; i++) {
        GC_size_map[i] = ROUNDED_UP_GRANULES(i);
    }
    /* We leave the rest of the array to be filled in on demand. */
}

めっけました。マクロがふんだんに使われてワケワカランっすね。

// gc_tiny_fl.h
#ifndef GC_TINY_FREELISTS
# if GC_GRANULE_BYTES == 16
#   define GC_TINY_FREELISTS 25
# else
#   define GC_TINY_FREELISTS 33	/* Up to and including 256 bytes */
# endif
#endif /* !GC_TINY_FREELISTS */

// gc_priv.h
#define TINY_FREELISTS GC_TINY_FREELISTS

# define GRANULES_TO_BYTES(n) ((n)<<3)

# define ROUNDED_UP_WORDS(n) \
	BYTES_TO_WORDS((n) + (WORDS_TO_BYTES(1) - 1 + EXTRA_BYTES))

# define BYTES_TO_WORDS(n) ((n)>>2)
# define WORDS_TO_BYTES(n) ((n)<<2)

EXTRA_BYTESは無視してください。だいたい0です。
TINY_FREELIST は 最小のfreelistの数
GRANULES_TO_BYTESは(n << 3)だから、こんな感じかぁ(1 -> 8, 2 -> 16)
BYTES_TO_WORD byte を word 単位に変換してるようですね。(4 -> 1, 8 -> 2)(64bitCPUだと当然違う)
つまり、ROUNDED_UP_WORDSは下位2bitを切り上げて、4の倍数毎(word毎)に1づつ加算されるのかなぁ?
 

>> (0 + (8 - 1)) >> 2
=> 1
>> (4 + (8 - 1)) >> 2
=> 2
>> (8 + (8 - 1)) >> 2
=> 3

 
うん、そうみたい。
(というかシフト演算とかビット演算とか凄く苦手なのでirb様様でちょこちょこ確かめました。
 ぱっと見て分かる人って凄いよねぇ。。。)
 
それで問題はこのfor分は何をやってるか何だけども。

    for (i = 1; i <= GRANULES_TO_BYTES(TINY_FREELISTS-1) - EXTRA_BYTES; i++) {
        GC_size_map[i] = ROUNDED_UP_GRANULES(i);
    }

freelistの個数を変換してループを繰り返し、GC_size_mapに4の倍数ごと1,2,3と入れているみたい。
ただ、GRANULESって何でしょうか。よく分かんないなぁ。。。
 

/*
 * We always set GRANULE_BYTES to twice the length of a pointer.
 * This means that all allocation requests are rounded up to the next
 * multiple of 16 on 64-bit architectures or 8 on 32-bit architectures.
 * This appears to be a reasonable compromise between fragmentation overhead
 * and space usage for mark bits (usually mark bytes).
 * On many 64-bit architectures some memory references require 16-byte
 * alignment, making this necessary anyway.
 * For a few 32-bit architecture (e.g. x86), we may also need 16-byte alignment
 * for certain memory references.  But currently that does not seem to be the
 * default for all conventional malloc implementations, so we ignore that
 * problem.
 * It would always be safe, and often useful, to be able to allocate very
 * small objects with smaller alignment.  But that would cost us mark bit
 * space, so we no longer do so.
 */

多分 objcet map とかのサイズの事っぽいです。
FreeListはそのサイズに乗っ取っていて、そのサイズをバイトに直したという事かなぁ。。。
誰か教えくだはい。。。
 

結論

word毎にfreelistへのindexが入ってる
 

続く

ビールを飲んで酔っ払ったのでまた明日。。。
中編へ