この記事はLinux Advent Calendar 2017の1日目の記事です。Linuxのスラブアロケーター仕組みを多少弄りながら学んでみます。
スラブアロケーターとはなんぞやというところはSlab allocation - Wikipediaを参照してください。スラブアロケーターはSolaris5.4で最初に実装されたようです。 Linuxカーネルプログラミングで動的にメモリを確保するのに使用するkmalloc()もスラブアロケーターを使用しています。
目次
Linuxには3種類の実装があり、カーネルのコンフィグでどれを使用するかを選択します。
SLAB
Solaris型のスラブアローケーターのようです。SLUBが出てくるまではこちらがLinuxのスラブアロケーターとして選択されてました。詳解Linuxカーネルで説明されているスラブアロケーターもこれです。openSUSEはこれを使ってたと思います。
SLUB
FedoraやArch Linuxなんかではこれが使われています。スラブに使うpageはcpu毎に割り当てたり、fast pathの場合はlocklessにスラブオブジェクトを確保できるような作りになってます。SLUBに関してはslub の検索結果 - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ過去にいくつか記事を書きました。
SLOB
K&R型のアロケーターです。SLABやSLUBと違い、スラブオブジェクトは固定長になっていなくて、キューが3つあり、256bytes以下ならsmallリストから必要なサイズを切り出して返す形になってます。cgroupsのmemcgは非対応です。
各スラブアロケーターのまとめ
さくっと説明しましたが詳しい違いはSlab allocators in the Linux Kernel: SLAB, SLOB, SLUBにわかりやすくまとまっています。
そういえば、UNIX V7のmallocの実装が UNIXカーネルソースツアー！で見ることができます。
実装
3種類の実装がありますが、全てが独立しているわけではなくて共通部分と個別の実装部に分かれています。
共通で使われるコードは以下の3ファイルにあります。
例えばスラブを新規に作るkmem_cache_create()はslab_common.cに実装があり、実装に依存しない共通的な処理はこちらで行い、スラブアロケーター固有の処理は各スラブアロケーターで実装している__kmem_cache_create()で呼ぶ流れになっています。
kmem_cache構造体がスラブアロケーターの主要なデータ構造です。どの実装でも使用する変数はありますが、実装としてはスラブアロケーター毎に分かれています。例えば、kmem_cache構造体のlistという変数はkmem_cache_create()で作成したスラブを管理するためのリストでこれはどのスラブアロケーターでも必要な変数となってます。
struct list_head list;
kmem_cache構造体はこの他にもどの実装でも共通で必要になる変数があります。
また、page構造体にもスラブアロケーター用のデータ構造が入っています。連結リストに使うlru変数や、次の空きスラブオブジェクトを指すfreelist変数などがあります。
SLUBとSLOBのfreelist変数はこのような感じになります。
図_slubとslobのfreelist
SLUBの場合はスラブオブジェクトは固定長なので次の空きスラブオブジェクトを指します。ページ内に空きスラブオブジェクトが無い場合はNULLを指します。SLOBの場合はリストから必要なサイズを切り出すので、freelist変数は次の利用可能な位置を指すことになります。フラグメンテーションが無ければここを起点としてサイズを切り出せますし、フラグメンテーションがある場合は確保したいサイズがある領域をページ内で探す必要があります。
スラブ用のページ
SetPageSlab()を使ってスラブ用のページとしてセットします。その他、必要に応じてフラグを設定するのですが、SetPageSlab()は必須です。SLOBの場合は、空き領域があるページにはSetPageSlobFree()でフラグをセットし、空き領域がなくなったページにはClearPageSlobFree()でフラグを外します。
SLOBでは使用していませんが、page構造体からkmem_cache構造体にアクセスできるようにslab_cache変数があります。SLUBでkfree()が呼ばれた場合はこのslab_cache変数から、該当のkmem_cache構造体にアクセスできます。
弄ってみる
ここではSLOBをベースに新しいスラブアロケーターを足す形で弄ってみたいと思います。名前はslmbとします。今のところ大雑把にリストを各cpuに持たせるようにしたのと、リストの数を増やした程度の実装となってます。
最低限必要な準備
新しく追加する場合、自前のスラブアロケーターをカーネルのコンフィグレーションで設定できる必要があるのでinit/Kconfigに設定を追加します。あ、ベースのカーネルは4.14.0です。
diff --git a/init/Kconfig b/init/Kconfig
index 3c1faaa2af4a..2d1ac7f952fb 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1551,6 +1551,12 @@ config SLOB
allocator. SLOB is generally more space efficient but
does not perform as well on large systems.
+config SLMB
+ depends on EXPERT
+ bool "SLMB (SLOB with multi processer support Allocator)"
+ help
+ SLMB is based on SLOB.
+
endchoice
config SLAB_MERGE_DEFAULT
アロケータの実装はmm/slmb.cに書くのでMakefileも変更が必要です。
diff --git a/mm/Makefile b/mm/Makefile
index 4659b93cba43..4d39ad32e641 100644
--- a/mm/Makefile
+++ b/mm/Makefile
@@ -12,6 +12,7 @@ KASAN_SANITIZE_slub.o := n
# free pages, or a task is migrated between nodes.
KCOV_INSTRUMENT_slab_common.o := n
KCOV_INSTRUMENT_slob.o := n
+KCOV_INSTRUMENT_slmb.o := n
KCOV_INSTRUMENT_slab.o := n
KCOV_INSTRUMENT_slub.o := n
KCOV_INSTRUMENT_page_alloc.o := n
@@ -65,6 +66,7 @@ obj-$(CONFIG_NUMA) += mempolicy.o
obj-$(CONFIG_SPARSEMEM) += sparse.o
obj-$(CONFIG_SPARSEMEM_VMEMMAP) += sparse-vmemmap.o
obj-$(CONFIG_SLOB) += slob.o
+obj-$(CONFIG_SLMB) += slmb.o
obj-$(CONFIG_MMU_NOTIFIER) += mmu_notifier.o
obj-$(CONFIG_KSM) += ksm.o
obj-$(CONFIG_PAGE_POISONING) += page_poison.o
kmem_cache構造体も自前で用意するのでinclude/linux/slmb_deh.hというファイルを作成し、そこで実装を書いていきます。
あとはmm/slab.hでslmb_def.hを読み込ませれば完了です。
+#ifdef CONFIG_SLMB
+#include <linux/slmb_def.h>
+#endif
+
最低限必要なのはこれくらいです。後はガンガン実装していけます( ´∀｀)bｸﾞｯ!t
もし、memcgの対応はとりあえず止めとくという場合は以下のような条件の部分に自分のアロケータの定義も入れていきます。
#ifndef CONFIG_SLOB
↑と↓です。
#if defined(CONFIG_MEMCG) && !defined(CONFIG_SLOB)
今回最終的に変更したファイルはこのようになってます。ほぼmemcgに対応しないための変更です。
masami@miko:~/linux-kernel (slmb %=)$ git diff origin/master --stat
include/linux/list_lru.h | 4 +-
include/linux/memcontrol.h | 6 +-
include/linux/sched.h | 2 +-
include/linux/slab.h | 14 +--
include/linux/slmb_def.h | 28 ++++++
init/Kconfig | 6 ++
mm/Makefile | 2 +
mm/list_lru.c | 12 +--
mm/memcontrol.c | 16 ++--
mm/slab.h | 18 ++--
mm/slab_common.c | 14 +--
mm/slmb.c | 729 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
12 files changed, 810 insertions(+), 41 deletions(-)
実装開始
SLMBはSLOBをベースとしているので解説も基本的にはSLOBベースとなります。
データ構造
雑にリストを増やしてます。
SLOBの場合は256バイト以下用のfree_slob_small、1024バイト以下用のfree_slob_medium、1024バイト以上用のfree_slob_largeがあります。SLMBでは以下のようにサイズを分けてみました。
+enum SLMB_LIST_SIZE_TYPES {
+ SLMB_SLAB_BREAK_8 = 0,
+ SLMB_SLAB_BREAK_16,
+ SLMB_SLAB_BREAK_24,
+ SLMB_SLAB_BREAK_32,
+ SLMB_SLAB_BREAK_40,
+ SLMB_SLAB_BREAK_48,
+ SLMB_SLAB_BREAK_56,
+ SLMB_SLAB_BREAK_64,
+ SLMB_SLAB_BREAK_96,
+ SLMB_SLAB_BREAK_128,
+ SLMB_SLAB_BREAK_256,
+ SLMB_SLAB_BREAK_1024,
+};
リストはpage構造体を要素とするリストです。page構造体のlru変数がリストに使われます。これはSLUBなどでも同じです。
SLMBではリストをこのようにして、
+struct slmb_slab_lists {
+ struct slmb_slab_list lists[SLMB_NUM_LIST_TYPES];
+};
以下のようにしてcpu毎にリストを持たせてます。
+DEFINE_PER_CPU(struct slmb_slab_lists, slab_lists);
SLOBでは空き領域がなくなったスラブ（ページ）はリストから外します。SLUBも空きオブジェクトがなくなったスラブを管理するリストはありません。
ロック
ロックについてはSLOBと同様にspin_lock_irqsave()でローカルCPUからの割り込みを止める形です。SLUBはfastpathの場合はlocklessで動作します。SLUBで空きオブジェクトが存在する場合、先に示した図_slubとslobのfreelistのようにSLUBの場合はfreelistが指す先を更新すれば良いだけです。SLUBではこの更新にはcmpxchg命令を使った更新方法を採用していてアトミックにポインタを書き換えることができます。
SLOBの場合はページ内から適切な空き要素を探さないといけないのでその手段が使えないですね。
初期化
スラブアロケーターは初期化してから使えるようになります。初期化の関数は2つあります。
- kmem_cache_init()
- kmem_cache_init_late()
初期化のメイン処理はkmem_cache_init()です。SLUB、SLOBはkmem_cache_init_late()での処理は特にありません。SLABは処理があります。
kmem_cache_init()ではスラブアロケーターを使用可能にするため、kmem_cache構造体用のスラブを作成します。
また、スラブアロケーターは状態を持っていて、slab_stateという変数で状態管理されています。mm/slab.hに状態が定義されています。
enum slab_state {
DOWN,
PARTIAL,
PARTIAL_NODE,
UP,
FULL
};
SLOBの場合はkmem_cache_init()の段階ではUP、kmem_cache_init_late()でFULLに変わります。kmem_cache_init_late()は状態をFULLに変えているだけなので、実質kmem_cache_init()でFULL状態になっても問題ない気がします。SLUBの場合はslab_sysfs_init内でFULLに変更しています。
初期化時はリストの初期化を行うのでfor_each_possible_cpu()でcpu毎にループして初期化をしています。
+ for_each_possible_cpu(cpu) {
+ struct slmb_slab_lists *lists = &per_cpu(slab_lists, cpu);
+ pr_info("%s: SLMB: intialize slob list cpu %d\n", __func__, cpu);
+ init_slmb_slab_lists(lists);
+ }
最初はfor_each_online_cpu()で良いだろうと思っていたのですが、kmem_cache_init()が呼ばれた時点ではonlineなcpuが1つしかなかったのでcpu0のリストしか初期化できず、あとになってcpu1とかのリストにアクセスしようとしたところでOOPSが発生しました。そんなわけで、onlineではなくて、カーネルが認識したcpu数でループとしてます。
+ for (i = 0; i < SLMB_NUM_LIST_TYPES; i++) {
+ struct slmb_slab_list *p = &lists->lists[i];
+ INIT_LIST_HEAD(&p->list);
+ }
SLMB_NUM_LIST_TYPESはスラブオブジェクトのサイズの数です。SLOBは256バイト以下、1024バイト以下、1024バイト以上の3つのリストで実装していたのでそれを増やしています。
kmem_cache_init()ではkmem_cache構造体用のスラブを作ります。SLOBでは以下のように作っています。
struct kmem_cache kmem_cache_boot = {
.name = "kmem_cache",
.size = sizeof(struct kmem_cache),
.flags = SLAB_PANIC,
.align = ARCH_KMALLOC_MINALIGN,
};
SLMBはSLOBそのままの作りになってます。このkmem_cache_boot変数をkmem_cacheという変数（mm/slab_common.cにあり）に代入します。
kmem_cache_bootの内容としては、スラブの名前はkmem_cache、サイズはkmem_cache構造体のサイズ、メモリ確保できない場合はパニックさせるって感じですね。
SLUBの場合はkmem_cache_int()mm/slub.cで設定して、kmem_cache変数に代入しています。
kmem_cacheはkmem_cache_create()でスラブを作る時のスラブとして使用します。
初期化処理はSLOBは大した処理はありませんが、SLUBやSLABだとkmem_cache構造体のためのスラブキャッシュを作るなど、SLOBよりも行う処理は多いです。
kmem_cache_create()
スラブの作成はkmem_cache_create()で行います。ここで指定されたサイズのスラブオブジェクトを作るわけです。SLUBやSLABの場合は実際に専用のkmme_cache構造体を作ります。スラブのマージ機能が有効な場合はちょっと違いますが。スラブのマージ機能は、作ろうとしたスラブと同じサイズのスラブがあれば新たにスラブを作るのではなくてそのスラブを使うようにします。
/sys/kernel/slab/でスラブの情報が見れるのですが、例えば、user_namespace用のスラブは488バイトのサイズで、t-0000488というスラブを参照してます。これはuser_namespaceという名前がt-0000488へのエイリアスとなってる感じですね。
$ ls -la /sys/kernel/slab/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 kmalloc-1024 -> :t-0001024/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 kmalloc-128 -> :t-0000128/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 kmalloc-16 -> :t-0000016/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 kmalloc-192 -> :t-0000192/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 kmalloc-2048 -> :t-0002048/
~
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 user_namespace -> :t-0000488/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 vm_area_struct -> :tA-0000192/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 xfrm_dst_cache -> :t-0000448/
lrwxrwxrwx. 1 root root 0 Nov 18 14:55 zswap_entry -> :t-0000056/
SLOBの場合はスラブの管理方法が3個のリストで行われていて、サイズごとの管理は実質していません。そのため、新しいkmem_cache構造体にkmem_cache_alloc()時に使用するgfpフラグの設定だけ行っています。サイズごとに管理してないので/sys/kernel/slab/もありません。また、/proc/slabinfoもありません。
スラブオブジェクトのアロケート
スラブオブジェクトのアロケートはkmem_cache_alloc()ですね。SLOBの場合はslob_alloc_node()がメインの処理です。ちなみに、kmem_cache_alloc()はNUMAのノード指定なし、kmem_cache_alloc_node()は指定したノードからアロケートするとなります。
SLOBではアロケートするサイズがPAGE_SIZE以上の場合はBuddyシステムを使ってページを確保し、先頭アドレスをそのまま返します。なので、スラブオブジェクトとして管理しない形です。
アロケートするサイズが小さければ事前に用意したリストを使って必要なサイズを切り出して返します。
kmem_cache_alloc()はSLOBがSLAB・SLUBと大きく違うところですね。SLAB・SLUBはスラブオブジェクトのサイズごとに専用のスラブがありますが、SLOB・SLMBはリストから必要なサイズを切り出して返します。SLMBではSLOBよりは細かくリストを分けてますが、確保するサイズによっては切り出しが必要です。
SLOBでのスラブオブジェクト取得は以下のような流れで行います。
kmem_cache_alloc()
-> slob_alloc_node()
-> slob_alloc()
-> slob_page_alloc() *1
-> slob_new_pages()
-> slob_page_alloc()
*1のslob_page_alloc()でスラブオブジェクトが取得できなかった場合は、その後のslob_new_pages()でスラブ用に新しいページを確保し、再度slob_page_alloc()でスラブオブジェクトの取得を行います。スラブオブジェクトが取得できなかったらページを確保するという動きはSLUBなんかも同じです。SLUBの場合はページを確保する前に別のNUMAノードを見に行ったりとかありますが。
SLOBの場合はリストにあるページから必要なサイズの空き領域を探す形です。ページ内に空き領域が見つかった場合はそのページが次回の呼び出し時に最初に探索するページになるようにしたりしてます。また、リストの操作中はspin_lock_irqsave()でロックを取っています。
SLUBの場合は空きオブジェクトがあればそのオブジェクトを返すのと、freelistが次の空きオブジェクトを指すようにします。
スラブオブジェクトのfree
kfree()やkmem_cache_free()の処理です。SLOBの場合、PAGE_SIZE以上の大きさの場合はBuddyシステムを使ってページを確保していたので、freeの場合もBuddyシステムにページを返します。そうでない場合は、SLOB側で処理します。kfree()の場合、解放するオブジェクトのアドレスしかわかりません。そのため、ここからスラブオブジェクトが所属するリストやkmem_cache構造体にアクセスする必要があります。と言っても、SLOBの場合はkmem_cache構造体は必要なくて、リストさえ分かればOKです。
アドレスからそのアドレスのpage構造体にアクセスするのにはvirt_to_page()を使います。SLUBの場合はvirt_to_head_page()を使っていますが、基本的には同じようなものです。
リストにはどうやってアクセスするかというとkfree()でサイズを計算していて、そこで出した結果から該当のリストを見つけることができます。kmem_cache_free()、kfree()どちらも解放処理の実装はslob_free()で行います。SLOBの場合は使用中のオブジェクトの前にある空きスラブオブジェクトにサイズや次の空きスラブオブジェクトまでのoffsetが書かれています。
実験
hackbenchをこんな感じで動かしてみます。実行環境はkvm上のfedora 26でcpuは4個です。ここではmenuconfigでスラブアロケーターをSLUBやSLOBに変えたというだけで、カーネルの設定、バージョンなどはSLMBと同じです。
#!/bin/bash
uname -a
echo "./hackbench 10 process 20000"
./hackbench 10 process 20000
echo "./hackbench 10 process 20000"
./hackbench 10 process 20000
echo "./hackbench 10 process 20000"
./hackbench 10 process 20000
echo "./hackbench 1 process 20000"
./hackbench 1 process 20000
echo "./hackbench 1 process 20000"
./hackbench 1 process 20000
echo "./hackbench 1 process 20000"
./hackbench 1 process 20000
これで、SLOB、SLMB、SLUBのベンチマークを取ってみます。
./hackbench 10 process 20000 の結果
| test |
slob |
slmb |
slub |
| 1 |
121.498 |
97.809 |
39.611 |
| 2 |
122.532 |
96.766 |
58.401 |
| 3 |
118.115 |
95.485 |
50.799 |
./hackbench 1 process 20000 の結果
| test |
slob |
slmb |
slub |
| 1 |
9.591 |
8.539 |
8.097 |
| 2 |
9.656 |
8.433 |
7.580 |
| 3 |
9.594 |
8.782 |
7.830 |
SLUBはやっぱ速いですね(ﾟдﾟ)！でも、SLMBも性能は良くなってます。
SLOBとSLMBでcpuを1個にして比較するとこうなります。
| test |
slob |
slmb |
| 10 process 20000 |
211.408 |
199.935 |
| 10 process 20000 |
232.415 |
218.371 |
| 10 process 20000 |
220.579 |
218.583 |
| 1 process 20000 |
10.107 |
19.218 |
| 1 process 20000 |
10.070 |
19.597 |
| 1 process 20000 |
10.521 |
19.472 |
1cpuで1プロセスだと逆に遅くなると。
SLMBで./hackbench 10 process 20000を4cpuの環境で実行した時の遅い人たち。
結局のところ、リストを扱う時のロックに行き着きますね。
SLUBの場合はこうなります。
SLUBもロックに時間を取られる傾向はありますが、よく見てみると、wake_up_sync_key()で時間がかかっていて、SLUBに関連する処理に時間がかかっているのではないというのが見えます。
この後
（´-`）.｡oO(やっぱりスクラッチから作る？もしくは、より改造していくか
