slab allocatorの内部実装

page frameは4K単位の管理なので、比較的小さいメモリ領域を確保するときに効率が悪い。そこで、linux2.6では、slab allocatorという仕組みを用いて小さな領域を効率的にreserved/freeするようになっている。cacheという概念自体はfileだけでなく、小さい領域を管理するための一般化された仕組みなので、やや想像しづらい。ということで、詳しめにまとめてみた。

reference

Understanding the Linux kernel: ch.8 Memory Management
前回の記事と同様にlinux kernel 2.6.11で確認してる
Intel SDM vol.3 ch.11のcacheの部分
Computer Organization and DesignのFigure5.12, Figure5.18あたりのcacheの図

概要

モチベーションとしては、一定のサイズのkernel内の構造体(inodeならstruct inode, tcpのportのbindの管理ならstruct tcp_bind_bucket)の領域を確保したい。しかしながら、Buddy System Algorithm¹では page frame単位(4K-byte)で領域の管理をしているので、それより小さい領域確保の場合、非効率である。
まず、cache descriptorを作成する。(tcp_bind_bucketなら、struct kmem_cache_t tcp_bucket_cachep)。ここで、どんなslabを作るのかを決める。cache descriptorはslabを管理してる。 -> kmem_cache_create
slab descriptorはobjectという領域を管理している。使用可能な領域なら自由に使える。これでPAGE_SIZEよりもより小さいサイズの領域をalloc/freeできる様になっている。
slabはcache descriptorの情報から複数作れるので、slab内のobjectが使用可能かどうかをcache descriptorから一元管理したい。そういう動機があり、local cacheがcache descriptorにある。local cacheでは使用可能なobjectのaddressがいくつか管理されているので、local cacheを経由して使用可能なobjectのaddressを入手できる。 -> kmem_cache_alloc
もし、local cacheの使用可能なobjectが枯渇した場合は、objectとslabとを新たに作って(cache_growのkmem_getpagesおよびalloc_slabmgmt)、使用可能なobjectをrefillする。 -> cache_alloc_refill

cache

使用可能なobjectを管理するためには、(specific) cacheか(general) cacheを用いる。

前者は、一定のサイズのobjectを管理する場合(e.g. 特定の構造体の領域)の場合で、専用のcache descriptorを作ることでobjectを管理する。

一方後者は、それ以外の場合で、この場合は、boot時に構成したmalloc_sizesを用いる。malloc_sizesでは、32 or 64 or 128 or 256...の大きさのobjectを管理しているcache descriptorのdescriptorで、malloc_sizes内のcache descriptorでobjectを管理している。例えば、確保したい領域が56byteの場合、すっぽり入る最小の箱の大きさ(64)のsizeのobjectを管理しているcache descriptor(malloc_sizesのCACHE(64))を用いる。

なお、malloc_sizesはかなりトリッキーな構造体で、https://gist.github.com/knknkn1162/b063e1890586f35c84d8fb2672c427fe のようになっているので、結構オモシロイと思った。

kmem_cache_t	create	create from	alloc	alloc from
cache_cache	kmem_cache_init	-	-
malloc_sizes[i]->cs_(dma)cachep	kmem_cache_init	-	-
(specific) cache	kmem_cache_create	cache_cache	kmem_cache_alloc	kmem_cache_createで作成した構造体
(general) cache	-	-	kmalloc	malloc_sizes[i]->cs_(dma)cachep

kmallocも内部では、kmem_cache_alloc(kmem_cache_t *cachep, int flags)を使っていて、第一引数は、malloc_sizes[i]->cs_(dma)cachepとなる。(ZONE_DMAの場合cs_dmacachepを使う)

なので、slab allocatorを把握するためには、cache descriptorを構成するためのkmem_cache_createとkmem_cache_allocを把握できれば良さげ。

kmem_cache_createにて
- cache descriptor(struct kmem_cache_t)の作成とこの構造体の初期化
- local cache(cache descriptorのarrayメンバで管理されている)の初期化
kmem_cache_alloc (kmem_cache_t *cachep, int flags)にて、
- local cacheに使用可能なobjectがあれば(array->avail > 0)それを用いる
- そうでなければ、cache_alloc_refill

一応例があったほうがイメージしやすいかもなので、今回はinode cache(struct kmem_cache_t inode_cachep)を例にしてみる。

Note) ちなみに、struct task_structはtask_struct_cachepでkmem_cache_allocされていて、struct thread_info(4Kのstack領域)はkmallocを用いてallocされてる²。

kmem_cache_create

(inode) cache(struct kmem_cache_t inode_cachep)は、start_kernel -> inode_init -> kmem_cache_createにて作成する。ざっくりとは下のような感じ。

- inode_cachep = kmem_cache_create("inode_cache", sizeof(struct inode), 0, SLAB_PANIC, init_once, NULL);
  - kmem_cache_t *cachep = NULL;
  - cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
  -  memset(cachep, 0, sizeof(kmem_cache_t));
  -  cachep->num(Number of objects)とcachep->gfporder(usually =1)を決める(`PAGE_SIZE >> cachep->gfporder`にて、各slabの大きさが決まる)
  -  cachepの他のメンバも決める
    - cachep->slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t) + sizeof(struct slab), 4);
    - cachep->objsize = ALIGN(size, 4);
    - cachep->color_off = align = 4
  - local cache(cachep->array)の構成(最初は空)
    - cachep->array[cpu_id]->avail = 0; # 最初local cacheはzero
    - cachep->array[cpu_id] = BOOT_CPUCACHE_ENTRIES; // #define BOOT_CPUCACHE_ENTRIES 1
    - ac_data(cachep)->batchcount = 1;
    - ac_data(cachep)->touched = 0;
  -  list_add(&cachep->next, &cache_chain): register cachep`static struct list_head cache_chain;`
  -  return cachep

大きくポイントは2つ。１つ目は、inode_cachep自体、cache_cacheというcache(struct kmem_cache_t)からallocateされているところ。(cache_cacheはkmem_cache_initにて構成されている)

もう一つは、local cache(cachep->array)の初期化である。

あとは、CFLGS_OFF_SLABも大事かもしれない。構造体のサイズが512[byte]以上なら、CFLGS_OFF_SLABが付けられる。(今回は、sizeof(struct inode)は512byte以上でないので、このフラグはつかない) これは、後々確保されるobjectをslab descriptor(struct slab)の直後に配置してよいか、そうでないかを示すフラグ。確保するサイズが大きすぎると、特定の場所よりも、もうチョット領域の大きい場所にobjectを確保するのが良いという理由から。詳しくは、Understanding the Linux kernelのFigure 8-5. Relationships between slab and object descriptorsを見れば意味がわかると思う。

kmem_cache_alloc

inodeの場合、inode = (struct inode *) kmem_cache_alloc(inode_cachep, SLAB_KERNEL);という風にalloc[^slab_kernel]する。 void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)という形をしていて、戻り値は確保した領域のaddressである。

この関数は確保する領域のsizeが陽に含まれていないので、結構混乱するが、cachep->objsizeにて、確保する領域のsizeがわかる。(cache descriptor自体は特定の大きさの領域(構造体の領域など)を確保するためのものということを思い出す。

この関数のポイントとしては、local cache内に使用可能なobjectがあれば、それを使うことと、なければ、inode_cachep内の既存のslabから調達する。もし、全く使えるobjectがないときは、1~2page分の領域をBuddy System Algorithmを用いて確保し³、その領域をstruct slabとそれに付随する複数のobjectに割り当てることで、使用可能なobjectを作成する。

kmem_cache_alloc->__cache_alloc
  - ac = cachep->array[smp_processor_id()](local cache(`struct へのpointer)とする。
  - objp = ac_entry(ac)[--ac->avail]: local cacheに使用可能なobjectがある時、それを使う
  - objp = cache_alloc_refill(cachep, flags): 上記以外の場合
    - [retry]: まず、以下の三種類の方法でobjectを取得を試し、そのobjectの先頭アドレスをlocal cacheに保存する:
      - shared local cacheから(cachep->lists->shared)
      - cachep->lists->slabs_partialから
      - cachep->lists->slabs_freeから
    - 上記が全くだめだった場合(`ac->avail == 0`)
      - cache_grow(cachep, flags, -1): slabとobject達を作成する。
        - cachep->colour_next++: これは、cacheのindexを意図的にずらすためのもの
        - offset *= cachep->colour_off: slab descriptorのoffset
        - objp = kmem_getpages(cachep, flags, -1): `PAGE_SIZE >> cachep->gfporder(=1)`分の領域確保
          - page = alloc_pages(flags, cachep->gfporder): Buddy System Algorithmを用いて2page分の領域を確保
          - addr = page_address(page): page -> virtual addressに変換
          - SetPageSlab(page): 2page分のpage->flagsに`PG_slab`をセット
        - slabp = alloc_slabmgmt(cachep, objp, offset, local_flags):
          - slabp = objp+colour_off; colour_off += cachep->slab_size;
          - slabp->s_mem = objp+colour_off;(objectの先頭アドレス)
        - set_slab_attr: page->lruの設定(このpageはpage descriptorなので、objpとは別であることに注意)
          - page->lru.next = (struct list_head *)cachep
          - page->lru.prev = (struct list_head *)slabp
        - cache_init_objs(cachep, slabp, ctor_flags):
          - cachep->ctor(objp, cachep, ctor_flags): inodeの場合は、init_once(`struct inode`としてobjectを初期化)
          - `struct slab`の直後の`kmem_bufctl_t`達の中身を埋める
        - list_add_tail(&slabp->list, &(cachep->lists->slabs_free))
      - if (!ac->avail) goto retry: もう一回、cache_alloc_refillの最初の部分に戻る。今度は、`cachep->lists->slabs_free`からobjectを取得できるようになっている。

ややこしいところだけ、ピックアップ：

ac_entry(ac)は(void**)(ac+1);で一見難しそうだが、図にすると、void*(objectのaddress)の配列の先頭を表していることがわかる:

f:id:knknkn11626:20190406164915j:plain — ac_entry

次にslabがどのような形をしていくかみていく。これは、cache->object_sizeが小さい場合はslab descriptor(struct slab)とobjectの数のkmem_bufctl_tの後にobjectが配置される(Fig8-6にも似たような図がある)：

f:id:knknkn11626:20190406232334j:plain — slab

cachep->colour_next*cachep->colour_offはL1 cacheのindexを意図的にずらすためのもの。もし、ずらさなかったとしたら、作成されたslabはobjectの数も同じだし、sizeも同等なので、(cachepと結びついている)他のslabとobjectの下位アドレスは同じになるが、hardwareのcache構造上少しまずい。(cache missしやすくなる)

以下、cacheの前提知識をある程度必要とするので、少し難しい⁴。

f:id:knknkn11626:20190406232646j:plain — x86: pentium4のcache構造

Intel SDM Table 11-1.のL1 Data Cacheによれば、

Pentium 4 and Intel Xeon processors (Based on Intel NetBurst microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line size.

とあるので⁵、これをもとに書いたのが上の図になる(多分)。

slabに話を当てはめると、もし、ずらさなかったとしたら、tagの部分は異なるが、[11:4]のindexの部分は同じとなる2つのobjectが生成される。この場合、objectのdataを探す時、同じindexをたどってしまうことになり、cache missのrateが高くなるかもしれない。そこで、indexの部分は同じとならないように、objectの位置を少しだけずらす(最初の数バイト空白cachep->colour_next*cachep->colour_offを入れることにより、indexがズレるので、cache missが減ることが期待できる。

struct slabの直後のkmem_bufctl_t達は次のobjectがどこにあるかは indexのかたちで表されている(kmem_bufctl_tの型はunsigned shortになっているのはそういった理由から)。この中身を埋める部分は、以下のようになっている。

// cache_init_objs
slabp->free = 0;
kmem_bufctl_t* obj_idxs = (kmem_bufctl_t *)(slabp+1); // slabp->freeのすぐ直後のaddress
obj_idxs[0] = 1;
obj_idxs[1] = 2;
// .. skip
obj_idxs[cachep->num-1] = BUFCTL_END; // BUFCTL_END: 次のobject
// obj_idxs[cachep->num-1]の直後にobjectがnum個配置されている

これで、slab内のfreeのobjectを順番にたどっていけるというわけだ。cache_alloc_refillのcachep->lists->slabs_(partial|free)にて、slabのobject達を取得するときは、この要領で順番にたどり、objectのaddressを取得し、local cacheに置くようなロジックになっている。

補足

kmem_cache_createとkmem_cache_allocをそれなりに詳しく説明したが、cache, slab, objectの全体の関係の把握は以下の図のようになる。手書きで汚いけど。。

f:id:knknkn11626:20190407121937j:plain — cache slab objectの関係

buddy system algorithmについては、この記事で説明しないが、Understanding the Linux kernel: ch.8に詳しい説明がある。Page frameを理解すればそれほど難しくないと思う(あと、pagingと混同しないこと。kernel領域の0xC000_0000から896MBの領域は4MB-pagingであるが、このpagingの枠組みとは独立にpage frameという概念がある。こちらは4K-byte単位で管理されている。)↩
dup_task_struct()を見る限り↩
ただし、小さな領域(< 512 bytes)の場合。大きな領域の場合は、object用の領域とstruct slabの場所が別になるが、詳細は省略。↩
cacheの概要については、chapter5を見ればよい。特に、Computer Organization and DesignのFigure5.12, Figure5.18あたり。↩
Pentium 4 古いが、Understanding the Linux Kernel ch.2にThe L1_CACHE_BYTES macro yields the size of a cache line in bytes. On Intel models earlier than the Pentium 4, the macro yields the value 32; on a Pentium 4, it yields the value 128.とあるので、これを上げた。x64の比較的新しい場合はcacheの構成が違うと思うので、いつか調べてみたい。↩

私のひらめき日記

ようこそ

slab allocatorの内部実装

slab allocatorの内部実装

reference

概要

cache

kmem_cache_create

kmem_cache_alloc

補足