僕の務める会社でも memcached はほとんどのサービスで利用されています。
今は業務も少ないので、ひまつぶしにmemcachedのコードを読んでいました。
Slab Allocatorの部分に興味を持ったので、それについてわかったことのメモ。
以下のサイトで事前知識を付けてからコードを読みました。
memcachedを知り尽くす：第2回 memcachedのメモリストレージを理解する
Slab Allocator : メモリの確保・管理を行うメカニズム
・メモリアロケーションでオーバーヘッドの大きいmalloc()を極力呼ばない
・一度アロケートしたメモリ領域を再利用してメモリフラグメンテーションを抑える
これらを実現するために以下のルールでメモリアロケーションを行っています。
・memcachedの初期化時にmalloc()で大きな領域(slabと呼ばれる, デフォルトで1MB)を確保
・あるslab classに属するslabは全て同一サイズのchunkで構成される
・chunkサイズはslab classにより異なる
・各slabはどのchunkが使われていないかを指すポインタを持っている
・chunkは不要になったらfree()されるのではなく、再利用するためにchunkリストに戻される
・もし利用可能なchunkがなくなった場合は、malloc()して新しいslabを作成する
Slab Allocatorの実装は slabs.h, slabs.c
・ slabclass_t 構造体
chunkサイズやslabのリストを持っています。
これを見ると、chunkのことをコード上ではitemと呼んでいる模様。
[csharp]
typedef struct {
unsigned int size; /* sizes of items */
unsigned int perslab; /* how many items per slab */
void **slots; /* list of item ptrs */
unsigned int sl_total; /* size of previous array */
unsigned int sl_curr; /* first free slot */
void *end_page_ptr; /* pointer to next free item at end of page, or 0 */
unsigned int end_page_free; /* number of items remaining at end of last alloced page */
unsigned int slabs; /* how many slabs were allocated for this class */
void **slab_list; /* array of slab pointers */
unsigned int list_size; /* size of prev array */
unsigned int killing; /* index+1 of dying slab, or zero if none */
size_t requested; /* The number of requested bytes */
} slabclass_t;
static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];
[/csharp]
・Slab Allocatorは固定数のslabclass_t配列を持ち、chunkサイズでソートされている
・slabclass_t配列のインデックス番号はclsidと呼ばれ、これはslab classを識別するためのidになっている
Slab Allocatorのメインインタフェース
[csharp]
unsigned int slabs_clsid(const size_t size);
void *slabs_alloc(size_t size, unsigned int id);
void slabs_free(void *ptr, size_t size, unsigned int id);
[/csharp]
malloc()が実際にメモリ割り当てを行っているのに対して、
slab_alloc()はあらかじめ確保した領域から、最適なサイズのchunkを返しているだけです。
同様に、free()が実際にメモリ解放を行っているのに対して、
slab_free()はchunkをリスト(slabclass_tのslots)に戻しているだけです。
[csharp]
unsigned int clsid;
item *it;
clsid = slabs_clsid(item_size); // item_sizeに応じてclsidを決める
it = slabs_alloc(item_size, clsid); // item_sizeとclsidをもとにchunkの割り当てを行う
slabs_free(it, item_size, clsid); // chunkをリストに戻す
[/csharp]
このSlab Allocatorの仕組みは、Linuxカーネルでも使われているとのことです。
時間があれば続きを読んでいきたいと思います。