Linuxカーネル4.1のSLUBアローケータ(ドラフト)

はじめに

本記事は過去に書いたけど諸事情により陽の目に出ていなかった文書です。完全版ではありません。satさんがスケジューラの記事を公開したのに影響され、自分も書いたものを死蔵させておくのはもったいないので公開することにしました。

qiita.com

カーネルのバージョンは4.1系です。

文書自体も完成版ではないし、markdownから手作業ではてなblogにコピペして修正してるので章立てとか変になってるところとかあるかもしれませんが気にしないでください。 一部は文書修正してます。

スラブアローケータ

Linuxにおけるメモリ確保の方法としてページ単位でメモリ確保を行うバディシステムがあります。バディアロケータはページ単位に管理を行うため、構造体など小規模なメモリを確保するために使用すると無駄が多くなってしまいます。そこで、スラブアローケータというメモリをより小さな単位で管理する仕組みを使用します。

スラブアローケータはアローケータの実装方式の一つで、Jeff Bonwick氏によりSolaris 2.4で最初に実装されました。今日ではスラブアローケータはSolarisだけでなく、LinuxFreeBSDなどのオペレーティングシステムや、memcachedのようなメモリ管理を効率的に行う必要があるミドルウェアでも採用されています。

スラブアローケータの説明に入る前に、基本的な用語を説明します。

  • スラブキャッシュ

スラブオブジェクトを管理します。スラブキャッシュはスラブオブジェクトの種類毎に作成します。メモリの確保や解放処理の要求の受付、スラブアローケータ内でのメモリ管理など、スラブアローケータの機能を提供します。スラブアローケータではメモリの確保時に実行するコンストラクタ関数を設定することもできます。Linuxではkmem_cache構造体がスラブキャッシュです。

  • スラブオブジェクト

スラブキャッシュが管理するオブジェクトです。スラブアローケータはこのスラブオブジェクトをメモリ確保要求時に返却します。

  • スラブ

スラブオブジェクトの集合です。スラブオブジェクトはバディアロケータよりページを確保し、そこにスラブオブジェクトを作成します。

  • freelist

slubアローケータにおいて、次のメモリ確保要求時に返却するするスラブオブジェクトを指すポインタです。

  • 使用中リスト

slubアローケータでは、スラブの管理には使用中リストを使用します。

スラブアローケータは管理するオブジェクトの単位でスラブキャッシュを作成します。たとえば、inode構造体用のスラブキャッシュ、task_struct構造体用のスラブキャッシュなど、通常は構造体毎にスラブキャッシュを作成します。こうして、特定の構造体用にメモリを確保する場合、その構造体に特化したアローケータよりメモリを確保を行います。このように特定のサイズに応じたアローケータを使用することで、メモリのフラグメンテーションを防ぎやすくなります。 任意のサイズのメモリを確保できるアローケータの場合、オブジェクトの確保と解放を繰り返していくうちに、メモリのフラグメンテーションが進み、空き領域の合計は十分にあるのに、メモリが断片化しているためまとまった量のメモリを確保できずに失敗する状況が発生します。

f:id:masami256:20190509234229p:plain

図_メモリのフラグメンテーション

「図_メモリのフラグメンテーション」では、最初のうちはメモリの確保のみが行われていたのでフラグメンテーションは発生していませんが、時刻が進みオブジェクトの解放が行われたため、メモリのフラグメンテーションが発生している状態です。未使用領域が2つあり、メモリ確保の要求がどちらかの未使用領域で満たせる場合は大丈夫ですが、要求サイズが各未使用領域のサイズよりも多いきい場合、仮に2つの未使用領域の合計サイズが、要求サイズよりも大きくてもメモリ確保に失敗します。 スラブアローケータは特定のサイズに特化しているため、このようなメモリのフラグメンテーションを防いでいます。

Linuxのスラブアローケータ

Linuxでは3種類のスラブアローケータの実装があり、カーネルコンフィギュレーションで使用するアロケータを変更できます。Linux 2.6.23よりslubがデフォルトのスラブアローケータとなっています。ディストリビューションによってはslabを選択しているものもあります。

slabアローケータ

slub登場以前はデフォルトのスラブアローケータでした。Solarisのスラブアローケータと同様の設計方針で実装されています。 スラブの管理にはスラブの状態に応じて複数のリストを使用します。使用するリストは、使用中オブジェクトが存在しないempty list、使用中オブジェクトと空きオブジェクトが存在するpartial list、全てオブジェクトが使用中のfull listの3つのリストがあります。 また、cache coloringと呼ぶ領域があり、ページフレーム内で空きオブジェクトの開始位置を他のスラブキャッシュとずらすために使用します。この機能は、スラブが複数存在する場合に、キャッシュラインの競合が起きないようにするための仕組みです。

slobアローケータ

シンプルな実装で、K&Rアローケータとも呼ばれています(注1)。slobアローケータはLinuxで使用可能なスラブアローケータの一つですが、slabやslubアローケータと違い、スラブをオブジェクトのサイズによって分けていません。一つのスラブで様々なサイスを取り扱います。これはプログラミング言語Cにおけるmalloc関数の実装と同様で、これがK&Rアローケータとも言われる所以です。

注1 プログラミング言語C で紹介されているUnixでのmalloc関数の実装に由来します。

slubアローケータ

slubアローケータはLinux固有のアローケータの実装です。本書ではslubアローケータについて解説します。

スラブオブジェクトの管理

slubアローケータでは空きスラブオブジェクトの管理はメタデータを別途持たせずに、スラブオブジェクトそのものに次の空きオブジェクトのアドレスを書き込みます。これにより、空きオブジェクトを管理するために別途メタデータを使用しなくてすむように設計されています。アドレスはスラブオブジェクトの先頭に書き込みます。最後の空きスラブオブジェクトには次のオブジェクトが無いため、NULLを設定します。

f:id:masami256:20190509234329p:plain

図_空きスラブオブジェクトの管理

使用中のスラブオブジェクトは特に管理を行いません。これはオブジェクトが不要になってオブジェクトを解放するときは、そのスラブオブジェクトのアドレスは自明なため、解放対象のオブジェクトが一意に決まるためです。

slubアロケータのスラブキャッシュはfreelist変数により、次回のスラブオブジェクト要求時に返却する空きスラブオブジェクトを参照しています。これにより、スラブ内に空きスラブオブジェクトが存在する間は高速にスラブオブジェクトを返却することができます。slubアローケータはスラブオブジェクトを返却する前に、次回のスラブオブジェクトのalloc時に返却するオブジェクトを参照するようにします。もし、最後の空きオブジェクトを返却した場合は、NULLを参照するようになります。この場合、次回の空きオブジェクト確保要求時に空きスラブオブジェクトの探索、もしくはスラブの作成を行うことになります。

f:id:masami256:20190509234421p:plain

図_空きスラブオブジェクトの確保

スラブオブジェクトを解放する場合、解放するスラブオブジェクトを次回のalloc要求時に返却するようにします。この時に次回のalloc要求時に返却予定だったスラブオブジェクトのアドレスを解放するスラブオブジェクトの先頭に書き込みます。

f:id:masami256:20190509234516p:plain

図_スラブオブジェクトの解放

slubアローケータではオブジェクトの確保に使用するスラブを常にCPUごとのメモリ域に置き、kmalloc関数などでスラブオブジェクトを要求された場合、このスラブから返却を行います。

f:id:masami256:20190509234657p:plain

図_percpuエリアにある構造体からスラブキャッシュの参照

使用中リスト

slubアローケータではスラブを管理する2つのリストがあります。一つはCPUと紐付いているスラブを管理するリストで、もう一つは、CPUとは紐付いておらず、スラブが所属するNUMAノード毎に管理するリストです。 CPUと紐付いている使用中リストに登録するスラブは1つだけ空きオブジェクトが存在するスラブです。また、このリストに登録できるスラブの数はcpu_partial変数にて設定されています。この値はスラブキャッシュ作成時に決定します。このリストはpage構造体のnext変数にてつながっています。この使用中リストは図_CPUに紐づく使用中リストのようになります。

f:id:masami256:20190509235150p:plain

図_CPUに紐づく使用中リスト

NUMAノードごとのは使用中リストは図_NUMAノードごとの使用中リストのように連結リストにて管理します。このリストには登録するスラブの上限はありません。

f:id:masami256:20190509235318p:plain

図_NUMAノードごとの使用中リスト

CPUと紐付いているスラブも、使用中リストにあるスラブもいずれも使用中ですが、CPUと紐付いているスラブは使用中リストでは管理しません。何かしらの理由でCPUとの紐付けを外す時に、CPUごとに保持しているスラブを使用中リストへ移動します。例えば、スラブ中に空きオブジェクトがなくなり、使用中リストから空きオブジェクトのあるスラブを探し、見つかったスラブとCPUごとのメモリ域ににあるスラブと交換したり、または、新規にスラブを作成した時に、作成したスラブをCPUごとのメモリ域に置き、CPUから参照されていたスラブを使用中リストに繋げるなどです。

CPUがスラブオブジェクトを取得するのに使用しているスラブはいずれの使用中リストの管理下にありません。スラブから空きオブジェクトが無くなった等の理由により、オブジェクトの取得対象のスラブで無くなった時に使用中リストに移動します。

スラブのマージ機能

slubとslabアロケータは同サイズのスラブキャッシュを一つのスラブキャッシュで管理する機能があり、デフォルトでこの機能は有効になっています。この機能を使用しない場合、128バイトのスラブオブジェクトを使用する機能が2つ存在した場合、スラブアローケータは2つの128バイトのスラブキャッシュを管理する必要があります。これは管理コストが増えたり、使用するページが違うため、CPUキャッシュヒット率が悪くなります。このような問題を解決するため、slab・slubアローケータでは同サイズのスラブキャッシュは一箇所で管理する仕様となっています。

マージの機能はslabとslubアローケータで詳細は異なっていて、slubアローケータでは、新規作成するスラブオブジェクトが以下の条件に当てはまる場合、新規にスラブキャッシュを作成せずに、既存のスラブキャッシュへのエイリアスを設定します。

  1. スラブオブジェクトのサイズが同一
  2. コンストラクタを使用しない
  3. slubのデバッグ機能を使用しない
  4. スラブ作成時のフラグにマージ機能を使用しないフラグが設定されていない

4のフラグについては「スラブキャッシュ生成時に設定するフラグ」にて説明します。

Chache Coloring

Cacje Coloringはスラブオブジェクトの開始アドレスをスラブ毎にずらすことによって、CPUのキャッシュライン競合を軽減させる仕組みです。slabアローケータはこの機能を採用していますが、 slubアローケータでは採用していません。CPUのキャッシュのライン調整に関してはCPUに任せる方針となっています(注1)。

注1: http://lkml.iu.edu/hypermail/linux/kernel/0808.0/1632.html

スラブの不活性化

slubアローケータはスラブオブジェクトを現在のCPUから参照されているスラブから返却します。参照されていないスラブはNUMAごとの使用中リストに繋がれますが、CPUごとのメモリ域にあるスラブをこの領域から外し、NUMAノードごとの使用中リストに移動することをスラブの不活性化と呼びます。

frozen状態

slubアローケータではスラブに対してfrozenという状態を設定します。fronzen状態にあるスラブはページの属性にPG_activeが設定されます。kmem_cache_alloc関数などによるオブジェクトの取得はこのスラブから行います。他のCPUはこのスラブからオブジェクトを取得することは出来ず、空きオブジェクトを追加する操作のみ行なえます。 CPUと紐付いているスラブはfrozen状態となり、スラブの不活性化によりCPUとのひも付けがなくなり、使用中リストにつなぐ時にスラブはfrozen状態が解除されます。

スラブキャッシュの情報

カーネルが管理しているスラブオブジェクトは/sys/kernel/debugディレクトリにて確認できます。Acpi-Namespaceなどシンボリックリンクとなっているものはslubアローケータのスラブマージ機能により、同サイズのオブジェクトを管理するスラブキャッシュとマージを行ったためです。

$ ls -l /sys/kernel/slab/  
total 0  
drwxr-xr-x 94 root root 0 May 20 20:19 ./  
drwxr-xr-x 11 root root 0 May 20 20:14 ../  
lrwxrwxrwx  1 root root 0 May 20 20:19 Acpi-Namespace -> :t-0000040/  
lrwxrwxrwx  1 root root 0 May 20 20:19 Acpi-Operand -> :t-0000072/  
lrwxrwxrwx  1 root root 0 May 20 20:19 Acpi-Parse -> :t-0000048/  
lrwxrwxrwx  1 root root 0 May 20 20:19 Acpi-ParseExt -> :t-0000072/  
lrwxrwxrwx  1 root root 0 May 20 20:19 Acpi-State -> :t-0000080/  
lrwxrwxrwx  1 root root 0 May 20 20:19 aio_kiocb -> :t-0000128/  
drwxr-xr-x  2 root root 0 May 20 20:19 anon_vma/  
lrwxrwxrwx  1 root root 0 May 20 20:19 anon_vma_chain -> :t-0000064/  
drwxr-xr-x  2 root root 0 May 20 20:14 :at-0000016/  
drwxr-xr-x  2 root root 0 May 20 20:14 :at-0000032/  
drwxr-xr-x  2 root root 0 May 20 20:14 :at-0000040/  

図_/sys/kernel/slabディレクト

ディレクトリ名には:tから始まるものや:atから始まるものがあります。これらのprefixは、スラブキャッシュ作成時に指定するflags引数に渡した(kmem_cache構造体のflags変数に設定されます)フラグを表します。表_slab_のprefixにフラグとprefixの対応を示します。:atや:dtなどはSLAB_CACHE_DMAとSLAB_NOTRACKの複合となります。これらのprefixはフラグが設定されていれば、そのprefixが使われるのですが、:tに関してはkmem_cache構造体のflagsとSLAB_NOTRACKのAND演算の結果が0の場合に設定されます。これはSLAB_NOTRACKがデバッグ機能の設定のため、値が0に設定されているためです。各フラグの内容については「スラブキャッシュ生成時に設定するフラグ」にて説明します。

prefix フラグ
:d SLAB_CACHE_DMA
:a SLAB_RECLAIM_ACCOUNT
:F SLAB_DEBUG_FREE
:t SLAB_NOTRACK

表_slabのprefix

個々のスラブキャッシュのディレクトリには以下のようなファイルが存在します。これらがスラブキャッシュの詳細になります。これらのファイルでスラブキャッシュが有効にしている機能などを確認できます。図_at-0000032ディレクトリは:at-0000032ディレクトリの様子です。

$ ls
./       align        cpu_partial  destroy_by_rcu  min_partial  objects_partial  partial          red_zone                  sanity_checks  slabs_cpu_partial  total_objects
../      alloc_calls  cpu_slabs    free_calls      objects      objs_per_slab    poison           remote_node_defrag_ratio  shrink         slab_size          trace
aliases  cache_dma    ctor         hwcache_align   object_size  order            reclaim_account  reserved                  slabs          store_user         validate

図_at-0000032ディレクト

slubアローケータのデータ構造

slubアローケータの主要な構造体には以下の4つの構造体です。

  • kmem_cache構造体
  • kmem_cache_cpu構造体
  • kmem_cache_node構造体
  • page構造体

これら4つの構造体のうち、page構造体以外はスラブアローケータのための構造体です。 スラブアローケータの核となる構造体はkmem_cache構造体です。kmem_cache構造体はslabやslubなど、スラブアローケータの実装によってデータ構造は違います。

名前 内容
cpu_slab cpuに紐付いているスラブキャッシュ
flags スラブキャッシュ生成時に指定したフラグ
min_partial 使用中のスラブキャッシュを保持できる最小の数。デフォルトは5、最大で10
size object_sizeをalignの境界に整列したサイズ
object_size メタデータを含まないスラブオブジェクトのサイズ
offset オブジェクトのサイズ+offsetで次の空きスラブオブジェクトを指す
cpu_partial cpu毎に保持できる使用中スラブキャッシュ数
oo スラブキャッシュ作成時に確保するページ数のオーダー
max スラブキャッシュ作成時に確保するページ数のオーダー数最大値
min スラブキャッシュ作成時に確保するページ数のオーダー数最小値
allocflags slabオブジェクトを確保する際に使用するgfpフラグ
refcount スラブマージ機能によってマージされたスラブキャッシュの数
ctor スラブキャッシュ作成時に呼び出すコンストラクタ関数
inuse スラブオブジェクトの使用数
align オブジェクトをsizeof(void *)の境界に整列した値。CPUのキャッシュラインに整列する場合は、先にCPUのキャッシュラインに合わせる
name スラブキャッシュの名前
list 作成したスラブキャッシュのリスト
memcg_params memory cgroup用の設定
remote_node_defrag_ratio 他のNUMAノードからスラブオブジェクトを取得する割合
node NUMAノード毎のスラブキャッシュ情報

表_kmem_cache構造体

slubオブジェクトのsize、object_sizeは図_スラブオブジェクトのようになります。

f:id:masami256:20190509235434p:plain

図_スラブオブジェクト

kmem_cache_cpu構造体はcpuコア毎にデータを保持します。page変数はpage構造体で、この変数はオブジェクトの返却を行うスラブのpage構造体を指します。 partial変数は使用中のスラブをつなぐリストとして使用しますが、list_head構造体は使用せず、page構造体のnext変数を利用してリスト管理を行います。このリストサイズはkmem_cache構造体のcpu_partial変数で設定します。

名前 内容
freelist 次の空きスラブオブジェクトへのポインタ
tid システムでユニークなトランザクションID
page スラブオブジェクトを管理しているページ
partial 使用中スラブの小規模なリスト

表_kmem_cache_cpu構造体

kmem_cache_node構造体はNUMAノード毎のデータを保持する構造体です。この構造体のデータ構造はスラブアローケータにより違い、ifdefによって、スラブアローケータ固有のメンバ変数が定義されます。slobアローケータでは使用しません。

名前 内容
list_lock sl[au]bアローケータ共通
nr_partial 使用中リストで管理しているデータ数
partial 使用中リストにあるスラブが使用しているpage構造体を管理するリスト

表_kmem_cache_node構造体

page構造体はページフレームを管理する構造体ですが、一部のフィールドはスラブアローケータが使用します。

名前 内容
freelist 空きオブジェクトを参照
counters オブジェクト数などを管理するカウンター
inuse 使用中のスラブオブジェクト数
object スラブオブジェクト数
frozen ページのfronzen状態
next 次の使用中リストへのポインタ
pages スラブキャッシュに使用しているページフレーム数
slab_page kmem_cache_cpu構造体が指すpageを指す
slab_cache ページが管理しているスラブへのポインタ

表_page構造体

page構造体はスラブが使用するページフレームに該当します。page構造体はメンバ変数に共用体を多用しているため、データ構造が複雑になっています。そのため、ソースコードを読み進める際には注意が必要です。 特によく使用するfrozen状態を設定するfrozen変数は構造体と共用体が入り組んだデータ構造のメンバ変数となっています。counters変数により1回の処理でfrozen変数を含めてデータを一括で設定した後に、frozenだけ変更する場合もあります。

データの関連

slubアローケータで使用するデータの関連

cpu、kmem_cache_cpu構造体、kmem_cache構造体、kmem_cache_node構造体、page構造体の関連は図_スラブで使用する構造体の関連のようになります。

f:id:masami256:20190509235714p:plain

図_スラブで使用する構造体の関連

スラブのライフサイクル

スラブがkmem_cache_cpu構造体から参照されているかか、kmem_cache_node構造体から参照されているかでfrozen状態が変わります。この時のfrozen状態を図_スラブの状態に示します。

f:id:masami256:20190509235746p:plain

図_スラブの状態

(1)はスラブを作成した時の状態です。スラブを作成した場合は必ずkmem_cache_cpu構造体のpage変数からスラブを参照して、このスラブからスラブオブジェクトを返却します。この状態はkmem_cache_cpu構造体からスラブが参照されているのでfrozenは1となります。

(2)はCPUごとのメモリ域からスラブが外れた状態です。この状態はスラブ内のスラブオブジェクトが全て使用中になる、または現在のCPUが使用するNUMAノードがスラブのNUMAノードと違う場合に、kmem_cache構造体のpage変数が参照するスラブの差し替えた場合です。この状態はスラブはkmem_cache_cpu構造体から参照されていませんのでfrozenは0となります。この状態に変更するために後述するdeactivate_slab関数によるスラブの不活性化処理を行います。

(3)の状態はスラブから空きスラブオブジェクトがなくなり、不活性化されたスラブがスラブオブジェクトの解放によりスラブ内に1つだけ空きオブジェクトができた場合、もしくはkmem_cache_cpu構造体が参照しているスラブのNUMAノードがCPUのNUMAノードと違った場合に、kmem_cache_node構造体の使用中リストからkmem_cache_cpu構造体の使用中リストで参照するように変更する時に起こります。この場合は、kmem_cache_cpu構造体からスラブが参照されるようになるので、frozenは1となります。

スラブアローケータの機能

スラブキャッシュ、スラブ、スラブオブジェクトに対する主な絹おは表_スラブに対する主な操作に示したものがあります。これらのうち、kmem_cache_で始まっている関数はシンボルが公開されていて、他のサブシステムから使用することができます。スラブの作成とスラブの不活性化はslub内部の処理です。

内容 対応する関数
スラブキャッシュの作成 kmem_cache_create
スラブキャッシュの破棄 kmem_cache_destroy
スラブオブエジェクトの確保 kmem_cache_alloc
スラブオブジェクトの解放 kmem_cache_free
スラブの作成 new_slab_objects
スラブの不活性化 deactivate_slab

表_スラブに対する主な機能

スラブキャッシュの作成

スラブキャッシュの作成はkmem_cache_create関数を使用します。スラブキャッシュの作成は各スラブアローケータ共通の処理と、各スラブアローケータ固有部分に分かれています。 スラブキャッシュの作成では最初にスラブがマージ可能かチェックします。作成しようとしたスラブキャッシュがマージ可能な場合は、マージ先のスラブキャッシュの参照数を増やします。既存のobject_size変数と作成しようとしていたスラブキャッシュのオブジェクトの大きさを比較し、大きいほうをobject_sizeに再設定や、オブジェクトの使用数などの設定も行います。最後に/sys/kernel/slabにシンボリックリンクファイルを作成します。シンボリックリンクの指す先はマージ先のスラブキャッシュです。マージに成功した場合はkmem_cache_create関数の処理はこれで完了となります。 スラブキャッシュのマージを行わなかった場合は、スラブキャッシュの新規作成を行います。 スラブキャッシュを新規作成する場合はdo_kmem_cache_create関数にて行います。まず、作成するスラブキャッシュのためにkmem_cache構造体のメモリを確保します。この時もスラブアローケータによりメモリを確保します。ここで、スラブキャッシュの名前、オブジェクトサイズなどのデータを設定します。また、memcgサブシステムで使用するmemcg_params変数の設定も行います。この時にmemcg_chache_params構造体のis_root_cache変数をtrueに設定しています。is_root_chache変数はスラブキャッシュの削除などで使用します。次に、各スラブアローケータ固有の処理を_kmem_cache_create関数にて行います。ここでの処理は主に、スラブキャッシュのオブジェクトサイズ、ページフレームを確保する時のオーダー、kmem_cache_alloc関数時に使用するGFPフラグなどの設定を行います。kmem_cache構造体のcpu_partial変数は各cpu毎にいくつの使用中リストを持てるかの設定です。この設定は表cpu_partial変数の設定にある条件できまります。条件は上から順にチェックします。

条件
kmem_cache_has_cpu_pertial関数がfalseを返す 0
kmem_cache構造体のsize変数がPAGE_SIZEより大きい 2
kmem_cache構造体のsize変数が1024より大きい 6
kmem_cache構造体のsize変数が256より大きい 13
全ての条件に当てはまらない場合 30

表_cpu_partial変数の設定

kmem_cache_has_cpu_partial関数はカーネルの設定でスラブアローケータの設定を有効にしない限り、常にtrueを返すのでcpu_partialが0に設定されることはありません。

次に、各NUMAノードで使用するkmem_cache_node構造体の初期化を行います。この構造体の初期化はリスト構造の初期化やスラブ数、スラブオブジェクト数を0にするなど目立った処理は特にありません。続いて、kmem_cache_cpu構造体の初期化を行いますが、こちらも特筆すべき内容はありません。__kmem_cache_create関数では最後に、作成したスラブキャッシュをsysfsより見えるように、sysfsのエントリーを作成して終了します。 __kmem_cache_create関数に成功し、do_kmem_cache_create関数に戻ったら作成したスラブキャッシュをスラブキャッシュを管理するリストに登録します。これでスラブキャッシュの作成が完了し、スラブオブジェクトの確保ができるようになります。ただし、この時点ではスラブオブジェクトはありませんので、初回のkmem_cache_alloc関数使用時にスラブを作成します。

スラブキャッシュ生成時に設定するフラグ

スラブキャッシュ生成時に設定するフラグのうちデバッグ向けのフラグを表_スラブキャッシュ生成時のフラグに示します。これらフラグの中で、SLAB_DESTROY_BY_RCU、SLAB_DESTROY_BY_RCU、SLAB_NOLEAKTRACEが設定されている場合、マージ機能は使用しません。

フラグ 内容
SLAB_HWCACHE_ALIGN スラブオブジェクトをCPUのキャッシュの境界に合わせる
SLAB_CACHE_DMA GFPフラグにGFP_DMAを設定し、DMA向けのスラブキャッシュを作成する
SLAB_PANIC kmem_cache_crate関数が失敗した場合にカーネルパニックする
SLAB_DESTROY_BY_RCU スラブキャッシュの解放時にRCUを使用して、非同期に行う
SLAB_MEM_SPREAD cpuset機能を使用しているプロセスの場合、cpusetで設定されたcpuのノードよりメモリを確保する(slabアローケータ専用)
SLAB_NOLEAKTRACE kmemleakによるトレースを行わない
SLAB_NOTRACK kmemcheckによるチェックを行わない
SLAB_RECLAIM_ACCOUNT スラブオブジェクトの回収を許する
SLAB_TEMPORARY スラブオブジェクトが短命と設定する。SLAB_RECLAIM_ACCOUNTと同様に回収可能となる

表_スラブキャッシュ作成時のフラグ

空きオブジェクトの管理

スラブ内の空きオブジェクトは、オブジェクト内のポインタによって次の空きオブジェクトを参照します。オブジェクトは使用中はデータが書き込まれていますが、オブジェクトが未使用の場合は重要なデータは存在せず、アクセスもされないため、オブジェクトの先頭に次の空きオブジェクトのアドレスを書き込んでいます。オブジェクトが不要になって解放された場合も、解放するオブジェクトの先頭に次の空きオブジェクトのアドレスを書き込みます。最後の空きオブジェクトは次の空きが無いため、NULLを設定します。ソースコード上は空きオブジェクトをfreelistと呼んでいますが、一般的な単方向連結リストなどと違い、次のオブジェクトを指す専用のポインタを持っておらず、未使用領域を次のオブジェクトを指すポインタとして使用していまます。

空きスラブオブジェクトの設定

スラブオブジェクトを作成するときは、ループしながらスラブ内の作成できるオブジェクトの数だけを設定していきます。 kmem_cache構造体の変数をs、s->offsetを0、s->sizeを16、オブジェクトのポインタをpとした時に、以下の手順で空きオブジェクトのリストを設定していきます。

  1. pの初期値をpageの先頭アドレスにする
  2. 次の空きオブジェクトのアドレスをpのアドレス + s->sizeとする
  3. pのアドレス + s->offsetの位置に、次のオブジェクトのアドレスを書き込む
  4. pの指すアドレスを現在のアドレス + s->sizeの位置に変更する
  5. 2〜4を繰り返す
  6. 作成できるオブジェクト数分、設定を行ったら、次の空きオブジェクトのアドレスをNULLに設定する。

上記の手順を図にすると「図_スラブオブジェクトのセットアップ」のようになります。

f:id:masami256:20190509235826p:plain

図_スラブオブジェクトのセットアップ

スラブオブジェクトを解放する場合は、以下の手順によって空きオブジェクトのリストを更新し、次のkmem_cache_alloc関数時には解放対象のスラブオブジェクトを返却するようにします。

  1. 解放対象のスラブオブジェクトが次の空きオブジェクトとして、現在設定されている次の空きオブジェクトを指すようにする
  2. 現在のCPUに設定されているkmem_cache_cpu構造体のfreelist変数を解放対象のスラブオブジェクトに変更

スラブオブジェクトの確保

スラブオブジェクトの確保はkmem_cache_alloc関数を使用します。kmem_cache_alloc関数はslab、slub、slobの各スラブアローケータ共通のインターフェースですが、実装はアローケータによって異なります。

スラブオブジェクトの確保におけるフローとして、下記の4パターンがあります。1はfastpathと呼ばれるパターンで、現在のCPUで使われているスラブからオブジェクトを確保できる場合で、最も高速に処理が完了します。2〜4のパターンはslowpathとなります。2はAとBのパターンがありますが、これはオブジェクトの確保時にノード番号を指定していない場合(A)・した場合(B)です。ここでオブジェクトが確保できなければ、全NUMAノードより使用中のスラブを探し、そこからオブジェクトの確保を試みます。全ノードを探索したが空きオブジェクトが見つからなかった場合は新規にスラブを作成します。

  1. 現在のCPUにあるスラブからオブジェクトを確保
  2. (A)ローカルメモリにある使用中のスラブからオブジェクトを確保。または、 (B)指定されたNUMAノードにある使用中のスラブからオブジェクトを確保
  3. 全NUMAノードから使用中のスラブを探し、そこからオブジェクトを確保
  4. スラブを新規に作成し、そこからオブジェクトを確保

スラブオブジェクトを確保する流れは図_スラブオブジェクトの確保フローのようになります。

kmem_cache_alloc()                      (1)
  -> slab_alloc()                       (2)
    -> slab_alloc_node()                (3)
      -> __slab_alloc()                 (4)
        -> deactivate_slab()            (5)
        -> get_freelist()               (6)
        -> new_slab_objects()           (7)
          -> get_partial()              (8)
            -> get_partial_node()       (9)
            -> get_any_partial()        (10)
          -> new_slab()                 (11)
            -> allocate_slab()          (12)
        -> set_freepointer()        (13)

図_スラブオブジェクトの確保フロー

スラブオブジェクトの取得はkmem_cache_alloc関数を使用しますが、実際の処理はslab_alloc_node関数から始まります。slab_alloc_node関数は、最初に現在のCPUに設定されているkmem_cache_cpu構造体を取得します。次にこのkmem_cache_cpu構造体より次の空きオブジェクトへのポインタ(freelist変数)を取得します。また、page構造体も取得します。ここで、node_match関数を呼び出し、次の2条件のいずれかを満たす場合はfastpathとなり、freelist変数をスラブオブジェクトとして呼び出し元に返却します。

  1. スラブが作成済み(page構造体がNULLでない)
  2. スラブオブジェクトを確保するNUMAノードが指定されていて、pageが所属するノードが指定されたノードと同じ

fastpathの場合は、次のkmem_cache_alloc関数の呼び出しに備え、freelistを次の空きオブジェクトを指すようにします。この時にCPU固有の先読み命令(*注1)にてfreelistをCPUのキャッシュに読み込みます。この手法により、次回のkmem_cache_alloc関数時にデータをメモリからでなくCPUのキャッシュから読み出せるようにすることで、高速化を図っています。

slowpathの場合は、__slab_alloc関数を実行します。ここでは、ローカルメモリにあるスラブより空きオブジェクトを探索します。kmem_cache_alloc関数によるスラブオブジェクトの確保では、NUMAノードの指定は行わないため、必ずローカルメモリを優先して探索します。ローカルメモリからの探索では、再度、現在のCPUに設定されているスラブキャッシュを取得し、このスラブキャッシュより参照されているスラブを取得します。 もし、スラブが存在しない場合、新たなスラブの作成に進みます。スラブの新規作成処理は後述します。スラブが存在した場合はスラブが所属するNUMAノードのチェックをnode_match関数を用いて行います。(この処理は、後述するkmem_cache_cpu構造体の更新後にジャンプして来る場合があります。)この場合もNUMAノードの指定は行っていません。よって、page構造体がNULLでなければ(スラブ用にページフレームが確保されている)、このスラブが利用可能なスラブオブジェクトの候補となります。 スラブに対する次のチェックとして、PageActiveマクロを利用し、スラブとしてい使用しているページがアクティブか調べます。もし、アクティブで無い場合、gfpフラグにALLOC_NO_WATERMARKSが設定されているか確認します。ALLOC_NO_WATERMARKSはウォーターマークのチェックをしないという設定です。このフラグがセットされていない場合は、deactivate_slab関数を使用して、スラブを不活性化します。この処理は「スラブの不活性化」で説明します。

次にpageのfreelist変数を対象にチェックを行っていきます。まず、kmem_cache_cpu構造体のfreelistが空きオブジェクトを指しているか確認し、参照先がスラブオブジェクトで無い場合は、page構造体のfreelist変数が空きオブジェクトを指しているかget_freelist関数を実行して調べます。

kmem_cache_cpu構造体のfreelist、もしくはpage構造体のfreelist変数が空きオブジェクトを指している場合、kmem_cache_cpu構造体のfreelist変数に空きオブジェクトを指しているfreelist変数を設定します。これでCPUが参照するスラブオブジェクトがfreelistになります。この処理にはload_freelistラベルが設定されて、スラブの新規作成が成功した場合にも実行します。スラブオブジェクトの設定を行ったら、呼び出し元の関数にこのスラブオブジェクトを返して、__slab_alloc関数を終了します。

スラブを新規に作成する前に、kmeme_cache_cpu構造体のpartial変数がNULLでないかチェックします。これまでの処理ではkmem_cache_cpu構造体のpage変数に設定されているスラブを対象に空きオブジェクトを探索しましたが、partial変数のチェックで、kmem_cache_cpu構造体の使用中リストに空きオブジェクトが存在するかチェックします。使用中のスラブオブジェクトが存在している場合に、kmem_cache_cpu構造体を更新し、スラブオブジェクトを取得する対象のスラブをこのスラブにします。この処理でkmem_cache_cpu構造体のpage変数とpartital変数が同じスラブを指すようになります。そして、partial変数はスラブが指す次のpage構造体に設定します。

そして、kmem_cache_cpu構造体のfreelist変数はNULLにします。これで、kmem_cache_cpu構造体のpageとpartialの設定を更新しfreelistがNULLを指すことで、、空きスラブオブジェクトは存在してないという状態になります。ここまで行ったら、slowpathの最初の処理にジャンプします。この時、ページフレームはすでに存在しているので、node_match関数によるノードのチェックから開始します。こまでの処理でローカルメモリからはスラブオブジェクトが見つからなかったため、new_slab_objects関数を実行します。この関数は大きく2つの処理があり、1つ目の処理はリモートメモリより空きオブジェクトを検索します。この処理で空きオブジェクトが見つかれば、このオブジェクトを返却できます。リモートメモリより空きオブジェクトを探すのはget_partial関数にて行います。

get_partial関数で空きスラブオブジェクトを探索する場合は、まずスラブオブジェクトを確保するNUMAノードが指定されているか確認し、ノードが指定されていなければローカルメモリ、指定があればそのノードよりスラブオブジェクトの取得を試みます。指定したノードよりスラブオブジェクトを確保する処理はget_pertial_node関数にて行います。この関数は指定されたNUMAノードにあるスラブのリスト(kmem_cache_node構造体のpartial変数)を辿り、空きスラブオブジェクトが存在するスラブを探します。スラブ中の空きスラブオブジェクトの探索はaqcuire_slab関数にて行います。スラブ内に空きスラブオブジェクトが見つかった場合は、そのスラブをfrozen状態に変更します。そして、使用中リストより、スラブのページフレームを外します。 aquire_slab関数にてり空きスラブオブジェクトが見つかった場合、スラブは以下のいずれかの状態になります。

  1. スラブオブジェクト確保したことで空きスラブオブジェクトなくなる
  2. スラブオブジェクトを確保したが、まだ空きスラブオブジェクトが存在する

1の場合は、kmem_cache_cpu構造体のpage変数にスラブが使用してるpageを設定します。 2の場合は、kmem_cache_cpu構造体のpartial変数にスラブが設定されているか確認し、スラブが設定されていた場合は、そのスラブのfrozen状態を解除し、そして、そのスラブに使用中のスラブオブジェクトがなく、使用中スラブの数が下限以上あればそのスラブはslab_discard関数にてスラブの不活性化処理を行います。使用中のスラブオブジェクトがあれば使用中リストにそのスラブを追加します。これで元々partial変数に設定されていたスラブの処理が完了したので、新しいスラブのための設定を行います。設定するのはpage構造体のデータで、オブジェクト数の設定などを行います。 スラブ中の空きスラブオブジェクト数が十分にあれば、この見つかったスラブオブジェクトを返却します。もし、空きスラブオブジェクト数が十分になければ、別のスラブを探索します。

ローカルメモリもしくは指定したノードよりスラブオブジェクトを確保できなかった場合は、全スラブを対象に空きスラブオブジェクトを探索します。これはget_any_pertial関数にて行いますが、空きスラブオブジェクト探索するか否かは、kmem_cache構造体のremote_node_defrag_ratioの設定値により変わります。remote_node_defrag_ratioが0の場合は他のノードの探索は行いません。次にCPUのタイムスタンプカウンタ値を取得し、この値を1024で割った余りがremote_node_defrag_ratioより小さかった場合も他ノードの探索は行いません。他のノードを探索しなかった場合は、new_slab_objects関数に戻り、新規にスラブオブジェクトを作成します。remote_node_defrag_ratioの値はカーネル内部とsysfsでエクスポートするときで桁数が違います。sysfs経由でこの値を設定/確認する場合は0~100までの数値を使用しますが、カーネル内部ではその値を10倍して使用します。デフォルト値は1000となっています。 スラブオブジェクトを探索する場合は、スラブが使用するZONEより、そのNUMAノードに存在するkmem_cache_node構造体を取得します。そして、そのノードからの空きスラブオブジェクトの確保が許可されている場合は、get_partial_node関数を使用して、空きスラブオブジェクトを探します。これでオブジェクトが見つかれば、そのオブジェクトを返却します。

リモートメモリを検索しても利用可能なかった場合は、new_slab_objects関数の2段階目の処理としてスラブの新規作成処理を行います。スラブの作成処理はnew_slab関数にて行います。スラブの新規作成では、まずページフレームを確保行います。ページフレームの確保とpage構造体の基本的な設定はallocate_slab関数で行います。

最初にpageの確保処理をalloc_slab_page関数にて行います。pageの確保するNUMAオードが指定されていないければ、ローカルメモリから、指定されている場合は対象のNUMAノードよりpageの確保を試みます。pageを確保する時のオーダーはkmem_cache構造体のoo変数に設定されている値を使用します。もしページフレームの確保に失敗した場合、オーダーをkmem_cache構造体のmin変数に設定されている最小のオーダー数に変更して再度alloc_slab_page関数を実行します。これでもページフレームを確保できなければNULLを返却します。

allocate_slab関数にてpageが確保できたらpage構造体のobjects変数にオブジェクト数の設定を行います。また、ページフレームを確保したZONEの状態を変更します。kmem_cache構造体のflags変数にNR_SLAB_RECLAIMABLEが設定されている場合はページ回収可能なページ数を、設定されていない場合はページ回収不可能なページ数を既存の値に追加します。ここまでの処理でスラブのためのpageの確保処理が完了となります。ページフレームの確保ができたら、次にpage構造体への設定として、page構造体のslab_cache変数に現在のkmem_cache構造体を設定し、page構造体とスラブを関連付けます。ページフレームをスラブとしてに使用していることを示すために、pageにPG_slabビットを設定します。page構造体のpfmemallocが設定されている場合は、pageにPG_activeビットを設定します。

次に、pageに対してスラブオブジェクトを1つずつ設定していきます。この処理については「スラブオブジェクトの作成」を参照してください。 最後に、page構造体の設定で、freelist変数をpageの開始アドレスに設定します。pageの開始アドレスは1つ目のスラブオブジェクトのアドレスですので、page構造体のfreelistは最初の空きスラブオブジェクトを指すことになります。inuse変数にはpage構造体のobjects変数を設定します。frozen変数には1を設定し、pageの管理をslubアローケータが行っているとマークします。以上でスラブオブジェクトの作成処理が完了となり、呼び出し元にpage構造体を返却します。

new_slab関数の実行によりスラブの作成が成功した場合は、kmem_cache_cpu構造体の設定を行います。まず、現在のCPUに設定されているkmem_cache構造体よりkmem_cache_cpu構造体のcpu_slab変数を取得します。kmem_cache_cpu構造体のpage変数がスラブのページフレームを指している場合は、現在設定されているkmem_cache_cpu構造体を一旦無効化します。この処理は「kmem_cache_cpu構造体の初期化」にて説明します。そして、page構造体のfreelistを別の変数にコピーし、page構造体のfreelist変数はNULLにします。そして、kmem_cache_cpu構造体のpage変数にnew_slab関数で作成したスラブのページフレームを設定します。kmem_cache_cpu構造体の設定が完了したら、new_slab_object関数の引数で渡されたkmem_cache_cpu構造体の変数に、設定したkmem_cache_cpu構造体を設定します。よって、new_slab_object関数の呼び出しにより、呼び出し元の__slab_alloc関数で使用していたkmem_cache_cpu構造体の内容が変わることになります。new_slab_objects関数では返り値として、コピーしておいたpage構造体のfreelist変数を返却します。

new_slab_objects関数を呼び出した__slab_alloc関数では、スラブの作成に失敗した場合は、これ以上の処理を行えないため、NULLを返します。スラブの作成に成功した場合はload_freelistラベルにジャンプします。

slab_alloc_node関数では、fastpath、slowpathいずれの場合も、スラブオブジェクトを返す前にGFPフラグをチェックし、__GFP_ZEROフラグが設定されている場合は、スラブオブジェクトに0x0を書き込みます。また、スラブオブジェクト確保時にフック関数を登録することができ、これらが設定されている場合は、スラブオブジェクトの確保前、確保後に登録されているフック関数を実行します。これらのフック関数は通常デバッグ機能向けに使われていて、スラブを使用する側からは設定できません。

注1:x86x86_64の場合はprefetcht0命令。

スラブオブジェクトの解放

kmem_cache_alloc関数で確保したスラブオブジェクトはkmem_cache_free関数で解放します。スラブオブジェクトの解放処理は図_スラブオブジェクト解放のようになります。

kmem_cache_free()
  -> cache_from_obj()
  -> slab_free()
    -> set_freepointer()    // fastpath
    -> __slab_free()        // slowpath
      -> put_cpu_partial()
        -> unfreeze_partials()
      -> discard_slab()
      -> remove_partial()

図_スラブオブジェクトの解放

kmem_cache_free関数では実質的な処理はせず、slab_free関数にて解放の処理を行います。スラブオブジェクトの解放は、確保の場合と同じくfastpathとslowpathの2パターンがあります。解放対象のオブジェクトがCPUから参照されている場合がfastpathとなり、そうでない場合はslowpathとなります。fastpathの場合は、解放するオブジェクトを次の空きオブジェクトに設定します。この時の様子を図_スラブオブジェクト解放前と図_スラブオブジェクト解放後に示します。解放前はkmem_cache_cpu構造体のfreelistは解放するスラブオブジェクトの隣にあるスラブオブジェクトを指していますが、スラブの解放後は解放したスラブオブジェクトを指すようになります。fastpathの場合は、現在使用中のスラブに対してオブジェクトの解放処理を行うため、freelistの変更だけで済んでいます。

f:id:masami256:20190509235911p:plain

図_スラブオブジェクト解放前

f:id:masami256:20190509235927p:plain

図_スラブオブジェクト解放後

slowpathの場合は__slab_\free関数にて処理を行います。

まず、以下のループでスラブが使用するpage構造体のfreelistを設定します。この時にpage構造体のデータを一部保存する一時変数として、newを使用します。

  1. kmem_cache_node構造体がNULL出ない場合は、この構造体のロックを取得(ループ1回目はkmem_cache_node構造体はNULL)
  2. page構造体のfreelist変数をprior変数にコピーし、set_freepointer関数で、priorを次に返すオブジェクトに設定
  3. newにスラブが使用しているpage構造体のcountersをコピー
  4. newのスラブオブジェクト使用数をデクリメント
  5. スラブのfrozen状態をwas_frozen変数にコピー
  6. newのオブジェクト使用数が0またはpriorがNULLかつ、スラブがfrozen状態で無かった場合7の処理を行います
  7. page構造体のfreelist変数がNULLの場合、8の処理を行い、NULLでなかった場合は9の処理を行います。いずれの処理も終了したら10に移動します
  8. スラブのfrozen状態を1にセット
  9. スラブが所属するNUMAノードのkmem_cache_node構造体を取得
  10. cmpxchg_double_slab関数でスラブのpage構造体のfreelistとcounters変数をnewに設定したデータに更新
  11. cmpxchg_double_slab関数が変更を行わなかった場合はループを終了

7の処理はソースコード上ではfreelistのチェックだけでなく、kmem_cache_has_cpu_partial関数がtrueを返すことも条件の一つなのですが、スラブのデバック機能を使用しない場合はtrueが返ります。 8の処理でfrozen状態を1に設定していますが、これはスラブが使用中リストで管理されていなかった場合になります。

上述のループを終了した段階で、kmem_cache_node構造体が取得されていない場合で、スラブをfrozen状態に変更した場合は、スラブをkmem_cache_cpu構造体のpartial変数のリストにつなぎます。 スラブをkmem_cache_cpu構造体から外すにはput_cpu_partial関数を使用します。この処理中は割り込みを禁止します。

次に、以下の処理をループで行います。

  1. 現在のCPUが参照しているkmem_cache構造体よりkmem_cache_cpu構造体のpartial変数を取得してoldpage変数に代入
  2. oldpageがNULLで無い場合は3の処理を行い、NULLだった場合はXに移動します
  3. 使用中オブジェクト数(ループ1回目は0、4手順目で更新する)がkmem_cache構造体のcpu_partialより大きい場合、unfreeze_partials関数を実行してkmem_cache_cpu構造体のpartial変数に紐づく全てのスラブのforzne状態を解除
  4. 引数で渡されたpae構造体のpage変数のpage数、使用中オブジェクト数を更新命令
  5. page変数next変数に取得したoldpageを設定
  6. this_cpu_cmpxchg関数でkmem_cache構造体のcpu_slab変数が参照しているpartialを更新したpage変数に変更
  7. this_cpu_cmpxchg関数が更新を行わなかった場合はループを終了

unfreeze_partials関数はkmem_cache_cpuのpartialリストにあるスラブのfrozen状態に変更し、kmem_cache_nodeの使用中リストに登録します。この処理では2段階のループがあります。 page構造体のデータを更新するための作業用変数としてpage、oldとnewを使用します。

  1. kmem_cache_cpu構造体のpartialに設定されているpage構造体をpageに代入
  2. スラブが使用しているpage構造体が所属するNUMAノードのkmem_cache_node構造体を取得
  3. 取得したkmem_cache_node構造体が前回取得したノード違った場合、前回のkmem_cache_nodeがNULLでなければ、ロックを解除
  4. 取得したkmem_cache_node構造体のロックを取得
  5. pageに設定されているfreelistとcountersをoldにコピー
  6. oldに設定したcountersとfreelistをnewにコピー
  7. newのfrozen変数を0に設定
  8. __cmpxchg_double_slab関数でpage変数のfreelistとcountersをnewに設定した値に更新
  9. __cmpxchg_double_slab関数が値の更新を行わなかったら11に進み、値の更新を行った場合は5に戻り、freelistとcouters変数の更新を続けます
  10. newに設定されているスラブオブジェクトの使用数が0かつ、kmem_cache_nodeにある使用中スラブ数が十分にある場合、そのスラブは不活性化の対象とします。そうでない場合はスラブをkmem_cache_node構造体の使用中リストに登録します。

上記手順の5と6は同じデータを設定していますが、7手順目でfrozen状態を解除するため、8手順目でpage変数にはfrozen状態が解除されたデータとして登録されます。

ループを抜けた時にkmem_cache_node構造体で取得したロックを解除します。 そして、ループの10手順目で削除対象のスラブが設定した場合は、discard_slab関数を実行してスラブを不活性化します。この処理は「スラブの不活性化」にて説明します。

kmem_cache_cpu構造体のデータクリア

スラブを無効化する時にkmem_cache_cpu構造体に設定されているデータのクリアを行います。この処理はflush_slab関数で行います。この関数は最初にdeactivate_slab関数を実行し、スラブを無効化します。次に、以下の3変数の値を変更します。

スラブの不活性化

スラブの不活性化処理は、下記3処理を行います。

  1. frozen状態スラブのfreelistで管理されている未使用のスラブオブジェクトを、同じスラブのpage構造体のfreelistへ移動
  2. スラブのfrozen状態解除
  3. 移動後のスラブの状態により、使用中リストへ移動、もしくは使用中リストから削除

これらの処理により、kmem_cache_cpu構造体が使用しているスラブを差し替えることができるようになります。この処理が必要になるのは2パターンあります。

  1. スラブを新規作成し、既存のスラブと置き換える
  2. スラブが不要になった場合

1のパターンは、スラブオブジェクトの確保時に既存のスラブからはスラブオブジェクトが確保できなかったため、新規にスラブを作成する場合です。2のパターンはkmem_cache_free関数によるスラブオブジェクトの解放時に、スラブ内のオブジェクトが全て空きオブジェクトになり、かつ使用中リストの数が下限以上ある場合、もしくはkmem_cache_destroy関数にてスラブキャッシュ自体を削除する場合です。

スラブの不活性化処理を行うのはdeactivate_slab関数です。処理は大きく2段階に別れていて、1段階目は空きオブジェクトの移動。2段階目はスラブのfrozen解除と使用中リストへの追加・削除です。 空きオブジェクトの移動では、frozen状態のスラブにあるfreelist(kmem_cache_cpu構造体のfreelist変数)より、空きオブジェクトを全て、同スラブのpage構造体のfreelistへ移動します。

第2段階では、最初に1段階目の処理の後に、freelistがまだ空きオブジェクトを指しているか確認し、空きオブジェクトを指している場合は、freelistがpage構造体のfreelistに設定した空きオブジェクトを指すように変更します。 この時にテンポラリの変数として、old、newと呼ぶpage構造体を使います。空きオブジェクトを指していた場合は、newの使用中スラブ数を減らし、newのfreelistがfreelistを指すようにします。空きオブジェクトを指していない場合は、newのfreelistとoldのfreelistを同じに設定します。以降の処理で、page構造体の変数を参照する際はnewを使用します。

次に、スラブが使用しているページに対する操作を決定します。どのような操作を行うかはスラブの状態に応じて決定します。スラブの状態を表_スラブの状態に示します。

状態 内容
M_NONE 何もしない(初期値)
M_PARTIAL スラブには使用中のオブジェクトがある
M_FULL スラブに空きオブジェクトが無い
M_FREE スラブに使用中オブジェクトが無い

表_スラブの状態

スラブの状態は2つの変数(l、m)により管理します。両者とも初期値はM_NONEです。まずはmについて、表_スラブの状態設定のようにmの状態を設定します。これら状態のうちM_FULLはデバッグ用途のフラグですので、通常はM_FULL状態の場合の処理はありません。

条件 設定する状態
スラブに使用中のオブジェクトがなく、NUMAノード内の使用中リスト数が下限以上に存在する M_FREE
page構造体のfreelistが空きオブジェクトを指している M_PARTIAL
その他 M_FULL

表_スラブの状態設定

次にlとmが同値でなければ、スラブが使用しているページに対する操作を行います。最初にこのコードパスを通る場合、lにはM_NONEが設定されているため、この条件は必ず真になります。そして、以下の条件に合致する処理を行います。

条件 処理内容
l == M_PARTIAL 使用中リストからスラブを削除
l == M_FULL 空きオブジェクト無しリストからスラブを削除(このリストはデバッグ用のため、通常は存在しません)
m == M_PARTIAL スラブを使用中リストに追加
m == M_FULL スラブを空きオブジェクト無しリストに追加(このリストはデバッグ用のため、通常は存在しません)

この処理が終わった後にlの値をmの値に設定します。次に、引数で渡されたpageのfreelistとcountersがoldのfreelistとcountersが同じなら、これらをnewのfreelist、countersに変更します。変更は__cmpxchg_double_slab関数で行います。もし__cmpxchg_double_slab関数がfalseを返した場合は変更を行わず、2段階目の最初の処理にジャンプし、2段階目の処理を再度実行します。変更を行った場合は最後の処理として、mがM_FREEに設定されているか確認し、M_FREEが設定されている場合はスラブは不要と判断し、discard_slab関数を実行してスラブの削除を行います。

スラブの削除

kmem_cache_free関数や、スラブの不活性化などにより、スラブ内に使用中のオブジェクトがなくなった場合にスラブの削除処理を行います。スラブの削除を行うインターフェースとなる関数はdiscard_slab関数です。スラブの削除はkmem_cache構造体のflags変数を見て、SLAB_DESTROY_BY_RCUが設定されている場合は、RCUを使用して遅延実行し、設定されていない場合はそのまま削除処理を行います。どちらの場合も削除処理として__free_slab関数を使用します。

discard_slab関数は削除対象のスラブが所属するNUMAノードのkmem_cache_node構造体を取得し、nr_slabs変数からスラブ数の減算と、解放することになるスラブオブジェクト数をobjects変数から減算します。次に、free_slab関数にて、kmem_cache構造体のflags変数にSLAB_DESTROY_BY_RCUが設定されているか確認し、設定されている場合はスラブをスラブ削除用のRCUリストにつなぎ、処理を終了します。 SLAB_DESTROY_BY_RCUが設定されていない場合は__free_salb関数にてスラブの削除を行います。RCUを使用する場合もスラブの削除実行には__free_slab関数を使用します。 __free_slab関数が呼ばれる時点で、スラブオブジェクトに対する解放処理は行われているため、この関数ではスラブが使用しているpageの解放処理が主となります。ここでの処理は、ページが所属しているZONEより、スラブが使用していたページ数の減算。ページの属性としてPG_activeとPG_slabビットを下ろします。次にpage構造体の_mapcount変数を-1に設定します。_mapcountは共用体のメンバ変数で、他にinuse、objects、frozenの3変数を持つ構造体も共用体のメンバ変数で、_mapcountに-1を設定することで、他のinuseなどの変数も無効な値に上書きされます。task_struct構造体のreclaim_state変数がNULLでなければ、回収済みのページ数に今回解放するページ数を足します。そして、__free_pages関数を使用し、ページの解放を行います。削除したスラブがkmem_cache_create関数で作成したスラブの場合は、memcgサブシステムのアカウンティング情報よりより使用していたページ数を減らします。

スラブキャッシュの削除

スラブキャッシュが不要になったらkmem_cache_destroy関数でスラブキャッシュを削除します。スラブキャッシュの削除処理はslabアローケータと共通処理とslubアローケータ固有の処理があります。スラブキャッシュの削除はまず、各アローケータ共通であるkmem_cache_destroy関数から処理が始まります。削除処理中はロックを確保し、他のスレッドから操作できないようにします。そして、スラブキャッシュの削除を行います。これは各アローケータ固有の処理で、インターフェースは__kmem_cache_shutdown関数です。__kmem_cache_shutdown関数自体は特に処理は行わず、処理はkmem_cache_close関数にて行います。 slubアローケータでは、最初に全CPUに対して以下の処理を行います。

  1. CPUから参照されているkmem_cache_cpu構造体のpageもしくはpartial変数がNULLの場合(スラブが存在しない)、何もしない
  2. page変数にスラブが設定されている場合、flush_cpu_slab関数が__flush_cpu_slab関数を実行し、3〜5の処理を行う
  3. deactivate_slab関数を実行し、スラブを不活性化。kmem_cache_cpu構造体の変数を初期化
  4. unfreeze_partials関数にてkmem_cache_cpu構造体のpartial変数に設定されてるスラブのfrozen状態を解除
  5. スラブが使用していた不要になったページをdiscard_slab関数にて解放

上記1〜5の処理で、各CPUから参照されていたkmem_cache_cpu構造体のデータを処理したので、次にNUMAノードに設定されているスラブを片付けます。この処理はkmem_cache構造体のnode変数に設定されている、kmem_cache_node構造体のpartialリストよりノードに存在するスラブに対してdiscard_slab関数を実行し、スラブを削除します。

次にCPUごとのメモリ域にあるkmem_cache構造体のcpu_slab変数のメモリを解放します。最後に、kmem_cache構造体のnodeメンバ変数で使用していたkmem_cache_node構造体のメモリを解放します。

ここまででslubアローケータ固有の処理を終了し、スラブアローケータ共通処理に戻ります。共通処理に戻ったら確保していたロックを解除し、do_kmem_cache_release関数を実行し、sysfsでエクスポートしているスラブキャッシュのエントリを削除します。これでスラブキャッシュの削除が完了となります。

スラブキャッシュのセットアップ

スラブアロケータを使用できるようにするために、カーネルの起動時にセットアップを行います。ここでセットアップするのは、kmem_cache構造体とkmem_cache_node構造体のメモリを確保するためのスラブキャッシュと、kmalloc関数で使用する様々なサイズのスラブキャッシュです。slubアローケータのスラブキャッシュを管理するためのメモリ管理機構に、slubスラブアロケータを使用します。

スラブキャッシュのセットアップ状況はいくつかの段階があります。この定義を表_スラブキャッシュのセットアップ状況に示します。セットアップの状態は表のDOWNからFULLに向かって進みます。最初はDOWNから始まります。

状態 内容
DOWN スラブキャッシュをまだ使用できない
PARTIAL slubアローケータのkmem_cache_node構造体が使用可能になった(kmem_cache_init関数内で設定)
PARTIAL_NODE slabアローケータで使用
UP スラブキャッシュを使えるようになったが、まだスラブの全機能は使用可能にはなっていない(create_kmalloc_caches関数で設定)
FULL 全て使用可能(slab_sysfs_init関数で設定)

表_スラブキャッシュのセットアップ状況

スラブキャッシュの初期化はkmem_cache_init関数が行います。この関数では最初に__initdata領域に存在する初期化時用のkmem_cache構造体とkmem_cache_node構造体のデータを使用し、スラブキャッシュを作成します。このスラブキャッシュの作成では、kmem_cache構造体のname、size、alignなどの変数を設定し、__kmem_cache_create関数を呼び出します。__kmem_cache_create関数は通常のスラブキャッシュ作成時にも使用しますが、通常時との違いとして、スラブキャッシュの作成状況による処理の変更が2箇所あります。 1つ目の変更箇所はkmem_cache_open関数から呼ばれるinit_kmem_cache_nodes関数の処理です。init_kmem_cache_nodes関数ではスラブキャッシュの作成状態がDOWNの場合、early_kmem_cache_node_alloc関数を使用してスラブキャッシュを作成します。これは、状態がDOWNの場合、まだスラブキャッシュを使用することが出来ないため、スラブを仮に作成し、そこからメモリを確保してスラブキャッシュを作成します。この場合でもスラブやページフレーム、スラブの使用中リストは設定します。

もう一箇所は__kmem_cache_create関数で、kmem_cache_open関数を実行し、スラブキャッシュが作成できたあとに状態をチェックし、状態がUP以下の場合は、sysfsへのスラブキャッシュ登録処理を行いません。よって、最初期のセットアップではスラブキャッシュを作成しただけで処理を終了します。__kmem_cache_create関数でスラブキャッシュを設定した後は、kmem_cache構造体のrefcountを-1に設定し、スラブのマージ機能対象外になるようにします。 この手順をkmem_cache構造体、kmem_cache_node構造体のスラブキャッシュのために行います。ここまで完了したらスラブキャッシュのセットアップ状況をPARTIALに設定します。

ここまでで仮のセットアップを行ったので、次に本格的なセットアップに入ります。ここからのセットアップもまずは、kmem_cache構造体用のスラブキャッシュと、kmem_cache_node構造体用のスラブキャッシュのセットアップです。これらのセットアップはbootstrap関数にて行います。まず、仮にセットアップしたスラブキャッシュを使用し、kmem_cache構造体用のメモリを確保します。そして、新しい構造体に既存のデータをコピーします。これで__flush_cpu_slab関数を使用し、CPUが参照しているスラブを無効にします。 つぎに、全NUMAノードにあるkmem_cache_node構造体のpartialリストにつながっているページフレームが参照しているslab_cache変数に、先ほど新規作成したkmem_cache構造体を設定します。 そして、スラブキャッシュを管理するslab_cachesリストに作成したkmem_cache構造体を設定します。

kmem_cache構造体とkmem_cache_node構造体のスラブキャッシュを作成したら、次にkmalloc関数用のスラブキャッシュを作成します。この処理はcreate_kmalloc_caches関数にて行います。create_kmalloc_caches関数では作成するサイズの設定を行い、create_kmalloc_cache関数にてスラブキャッシュを作成します。スラブキャッシュの作成はcreate_boot_cache関数を使用します。create_boot_cache関数は__kmem_cache_create関数を使用して、スラブキャッシュを作成しますが、この時点ではスラブキャッシュの作成状況はPARTIALになっているため、最初にkmem_cache構造体・kmem_cache_node構造体を作成した時の用にinit_kmem_cache_nodes関数ではearly_kmem_cache_node_alloc関数ではなく、通常のkmem_cache_alloc_node関数を使用します。kmalloc関数用のスラブキャッシュを作成したらスラブキャッシュの作成状態をUPに変更します。

スラブキャッシュの作成が完了したら、slab_sysfs_init関数にてスラブキャッシュの情報をsysfs経由でエクスポートします。この時にスラブキャッシュの作成状態をFULLに変更し、スラブキャッシュの機能の設定が完了します。

slubアローケータで使用するヘルパー関数

slubアローケータ内でよく使われる関数を紹介します。

__cmpxchg_double_slab関数

__cmpxchg_double_slab関数は引数を7つ受け取りますが、そのうち重要なものを表___cmpxchg_double_slabの引数に示します。

名前
struct kmem_cache * s
struct page * page
void * freelist_old
unsigned long counters_old
void * freelist_new
unsigned long counters_new

表___cmpxchg_double_slabの引数

この関数はpage->freelistとpage->countersの値がfreelist_old、counters_oldと同一の場合は、page->freelistをfreelist_new、page->countersをcounters_newの値に設定します。CPUがアトミックな更新命令を持っている場合はCPUの命令を使用し、アトミックな更新命令を持っていない場合はロックを取得した上で値の更新を行います。

slubアローケータでは他にもthis_cpu_cmpxchg_double関数やcmpxchg_double_slab関数を値の交換のために使用していますが、処理の基本的な考え方は__cmpxchg_double_slab関数と同じです。

kmalloc関数とkfree関数による動的なメモリ確保と解放

kmalloc関数

任意のサイズのメモリを動的に確保したい場合、ユーザランドのプログラムではmalloc(3)を使用しますが、Linuxカーネル内ではkmalloc関数を使用します。 kmalloc関数のインターフェースは「図_kmallocのインターフェース」のようになっています。sizeは確保するメモリの量、flagsは__get_free_pages関数でも使用している、メモリ確保時の制御フラグです。また、メモリを0x0で埋めて返すkzalloc関数などの補助的な関数もあります。

static __always_inline void *kmalloc(size_t size, gfp_t flags);
static inline void *kzalloc(size_t size, gfp_t flags);

図_kmallocのインターフェース

kmalloc関数は確保するサイズに応じて、スラブアローケータよりメモリを確保します。kmalloc関数はカーネルコンパイル時にサイズが確定していて、サイズがkmalloc用のスラブキャッシュの最大サイズ(KMALLOC_MAX_SIZE)を超える場合はページアローケータを使用してメモリを確保します。それ以外の場合はサイズに応じたkmalloc用のスラブキャッシュよりスラブオブジェクトを取得して返します。 kmalloc用のスラブキャッシュはcreate_kmalloc_caches関数にてカーネルの起動時に作成します。

ZONE_NORMALに所属するページフレームからなるkmalloc用のスラブは「図_kmallocのスラブキャッシュ」のようになっています。

lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-1024 -> :t-0001024
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-128 -> :t-0000128
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-16 -> :t-0000016
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-192 -> :t-0000192
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-2048 -> :t-0002048
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-256 -> :t-0000256
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-32 -> :t-0000032
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-4096 -> :t-0004096
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-512 -> :t-0000512
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-64 -> :t-0000064
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-8 -> :t-0000008
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-8192 -> :t-0008192
lrwxrwxrwx  1 root root 0 Jun  9 00:27 kmalloc-96 -> :t-0000096

図_kmallocのスラブキャッシュ

例えば、48バイトのsizeを指定された場合、次に大きいkmalloc-64のスラブキャッシュよりオブジェクトを確保することになります。このようにスラブアロケータを使用することで、要求するsizeによっては無駄が出てしまいますが、メモリを効率的に速く確保できるという利点もあります。

kfree関数

kmalloc関数で確保したメモリを解放するときはkfree関数を使用します。kfree関数のインターフェースは図_kfreeのインターフェースの通りです。引数に渡すのはkmalloc関数の戻り値です。

void kfree(const void *);

図_kfreeのインターフェース

kfree関数でのメモリ解放では、実質的な処理はslab_free関数にて行います。kfree関数固有な処理は特にありません。