Linuxカーネルは、Solarisから派生した、スラブキャッシュと呼ばれるサイズに応じたオブジェクトとしてメモリを割り当てる方法を使用していますが、組み込みシステムでは長い間使用されてきました。
メモリ管理の目的は、さまざまな目的のために個々のユーザー間でメモリを共有できる方法を提供することです。メモリ管理方法は、以下の2つの機能を満たす必要があります：
- メモリ管理に必要な時間の最小化
- ****一般的なアプリケーション用の空きメモリ
メモリ管理はまさにトレードオフのゼロサムゲームです。管理に使うメモリは少なくて済みますが、利用可能なメモリの管理に多くの時間を費やすアルゴリズムを開発することができます。あるいは、メモリを効率的に管理するアルゴリズ ムを開発することもできますが、より多くのメモリを使用します。最終的には、特定のアプリケーションのニーズが、このトレードオフの選択を促します。
どのメモリー・マネージャーも、ヒープ・ベースの割り当て戦略を使います。この手法では、大きなメモリチャンクを使用して、ユーザーが定義した目的のためにメモリを提供します。ユーザーがメモリーのチャンクを必要とする場合、あるサイズのメモリーを割り当てるよう要求します。ヒープ・マネージャは利用可能なメモリを調べ、メモリ・チャンクを返します。検索プロセスで使用されるアルゴリズムには、ファーストフィットとベストフィットがあります。
このヒープベースの割り当て戦略の根本的な問題は断片化です。メモリブロックが割り当てられると、異なるタイミングで異なる順序で返されます。このため、ヒープに穴が空き、空きメモリを効率的に管理するのに時間がかかります。このアルゴリズムは通常、メモリ使用効率は高いのですが、ヒープの管理に時間がかかります。
バディメモリアロケーションと呼ばれるもう一つの方法は、メモリーを2の累乗のパーティションに分割し、ベストフィット法を用いてメモリー要求を割り当てる、より高速なメモリー割り当て技術です。ユーザーがメモリを解放すると、バディ・ブロックがチェックされ、隣接するブロックも解放されているかどうかが確認されます。もしそうなら、メモリブロックはメモリの断片化を最小化するためにマージされます。このアルゴリズムは時間効率は良いのですが、ベストフィット法を使うためメモリの無駄があります。
スラブキャッシュ
Linuxで使われているスラブアロケータは、Jeff BonwickがSunOSオペレーティングシステムのために導入したアルゴリズムに基づいています。Jeffは、カーネル内の一般的なオブジェクトを初期化するのに必要な時間が、オブジェクトの割り当てと解放に必要な時間を上回ることを発見しました。そこで彼は、メモリはグローバルなメモリプールに戻すのではなく、特定の目的のために初期化されたままにしておくべきだと結論づけました。たとえば、ミューテックス・ロックにメモリが割り当てられた場合、ミューテックス・ロックの初期化関数は、ミューテックス・ロックにメモリが割り当てられたときに一度だけ実行されればよい***。その後のメモリ割り当てでは、この初期化関数を実行する必要はありません。なぜなら、リリースとデストラクトの呼び出しによって、メモリはすでに必要な状態になっているからです。
Linuxのスラブ・アロケータは、このアイデアと他のいくつかのアイデアを使って、空間と時間の両方で効率的なメモリ・アロケータを構築しています。
図1はスラブ構造のハイレベルな構成です。cache_chain の各要素はスラブ構造への参照です。cache_chainの各要素はkmem_cache構造体への参照です。これは、管理される所定のサイズのオブジェクトのプールを定義します。
図1.スラブディストリビューターの主要構造
各キャッシュにはスラブのリストがあり、これは連続したメモリブロックです。スラブには3つのタイプがあります：
スラブ・フル
完全割当スラブ
スラブ_パーシャル
部分的に割り当てられたスラブ
スラブ・エンプティ
空のスラブ、または割り当てられたオブジェクトがありません。
注意：slabs_emptyリストにあるスラブは、再利用のための主な選択肢です。このプロセスによって、スラブによって使用されたメモリは他のユーザが使用できるようにオペレーティング・システムに戻されます。
スラブ・リストの各スラブは、個々のオブジェクトに分割された連続したメモリ・ブロックです。これらのオブジェクトは特定のキャッシュに割り当てられ、解放される基本要素です。スラブはスラブアロケータが動作する最小の割り当て単位であり、スラブを拡張する必要がある場合、これが拡張される最小の値であることに注意してください。通常、各スラブは複数のオブジェクトとして割り当てられます。
オブジェクトはスラブから割り当てられ、解放されるので、1つのスラブはスラブリスト間で移動することができます。例えば、スラブ内のオブジェクトが全て使い切られると、スラブはslabs_partialリストからslabs_fullリストに移動します。スラブが完全に割り当てられ、いくつかのオブジェクトが解放されると、スラブはslabs_fullリストからslabs_partialリストに移動します。全てのオブジェクトが解放されると、slabs_partialリストからslabs_emptyリストに移動します。
#p#
I. スラブ関連のデータ構造
1) スラブキャッシュ記述子
struct kmem_cache {
struct array_cache *array[NR_CPUS];//効率を上げるため、各CPUはスラブ・フリー・オブジェクト・キャッシュを持っている。
/* 2) Cache tunables. Protected by cache_chain_mutex */
unsigned int batchcount;//ローカル・キャッシュに移動したオブジェクトの数、またはローカル・キャッシュから移動したオブジェクトの数。
unsigned int limit;//のローカル・キャッシュ・フリー・オブジェクトである。***番号
unsigned int shared;
unsigned int buffer_size;
struct kmem_list3 *nodelists[MAX_NUMNODES];//slabキャッシュ解放、部分解放、3つのチェーンテーブルのスラブ解放なし
unsigned int flags; /* constant flags */
unsigned int num;//每个slab obj的个数
unsigned int gfporder;//各スラブ内の連続ページフレーム数
gfp_t gfpflags;//ページ・フレームの割り当て時にパートナー・システムに渡されるフラグ
size_t colour;//slab使用色数
unsigned int colour_off; //slabのカラー・オフセットは、次のように解析される。
struct kmem_cache *slabp_cache; //ストレージ・スラブ・ディスクリプタ・キャッシュを指す。
unsigned int slab_size;//単一のスラブのサイズ
unsigned int dflags; /* dynamic flags */
//オブジェクト生成のためのコンストラクタ
void (*ctor) (void *, struct kmem_cache *, unsigned long);
//オブジェクトのデストラクタ
void (*dtor) (void *, struct kmem_cache *, unsigned long);
const char *name;//slabキャッシュの名前
struct list_head next;//このフィールドを通して、キャッシュプをキャッシュプ・チェーン・テーブルにリンクする。
}
2) スラブ記述子
struct slab {
struct list_head list; //スラブをスラブ・チェーン・テーブルにリンクする。，slabs_full, slabs_paril, slabs_free
unsigned long colouroff;//slab ***オブジェクトのオフセット
void *s_mem; //slab ***オブジェクトのアドレス
unsigned int inuse; //使用されているオブジェクトの数
kmem_bufctl_t free; //次にどの解放オブジェクトを使用するかを示す
unsigned short nodeid;//スラブはどのメモリノードに属するか？
}
スラブ記述子は2つの場所に格納されます：
外部スラブ記述子: スラブの外部で、cache_sizeが指す共通キャッシュに格納。
内部スラブ記述子：スラブに割り当てられたメモリの***ページフレームの先頭にスラブ内部に格納。
3) スラブキュー記述子
struct kmem_list3 {
struct list_head slabs_partial; //オブジェクトはチェーンテーブルのスラブ記述子の一部として使用される。
struct list_head slabs_full;//オブジェクトはチェーン・テーブルのスラブ記述子を占有する。
struct list_head slabs_free;//解放オブジェクトのみを含むスラブ記述子の連鎖リスト
unsigned long free_objects;//キャッシュ内の空きオブジェクト数。
unsigned int free_limit;
unsigned int colour_next; /* Per-node cache coloring */
spinlock_t list_lock;
struct array_cache *shared; //全CPUで共有されるローカルキャッシュを指す。
struct array_cache **alien; /* on other nodes */
unsigned long next_reap; //スラブのページ解放アルゴリズムで使用される
int free_touched; //スラブのページ解放アルゴリズムで使用される
}
4) スラブオブジェクト記述子
typedef unsigned int kmem_bufctl_t;
各オブジェクトはkmem_bufctl_t型のオブジェクト記述子を持ち、各スラブ記述子はスラブ内の個々のオブジェクトを記述するkmem_bufctl_t型の配列を持ちます。ディスクリプタは、配列のインデックスを使用してオブジェクトの連鎖リストを形成し、実際に次に利用可能な空きオブジェクトを記録します。オブジェクト記述子は内部オブジェクト記述子と外部オブジェクト記述子にも分けられます：
- 内部オブジェクト記述子：スラブ内部に格納され、記述子によって記述されたオブジェクトの前に格納されます。
- 外部オブジェクト記述子：キャッシュ記述子のslabp_cacheフィールドが指す共通キャッシュ内のスラブ外部に格納。
スラブ記述子とスラブオブジェクトの間の組織図を以下に示します：
スラブのローカルオブジェクトキャッシュ
Linux 2.6 マルチプロセッサをより良くサポートし、スピンロックの競合を減らし、ハードウェア・キャッシュをより良く利用するために、スラブ・アロケータの各キャッシュは、解放されたオブジェクトへのポインタの配列で構成されるスラブ・ローカル・キャッシュとして知られるCPUごとのデータ構造を含んでいます。このようにして、スラブ・オブジェクトの解放と割り当てはローカル・ポインタ配列にのみ影響し、同時実行を減らします。ローカル配列がオーバーフローまたはアンダーフローした場合にのみ、スラブ構造が関与します。関連するデータ構造は以下の通りです：
struct array_cache {
unsigned int avail;//そのコードは次のように解析される： ローカル・キャッシュで利用可能なオブジェクトの数、および解放された配列の場所のインデックス。
unsigned int limit;//ローカル・キャッシュのサイズ
unsigned int batchcount;//ローカル・キャッシュが満たされたり空になったりしたときに使用されたオブジェクトの数。
unsigned int touched;//ローカル・キャッシュが最近使用されたなら、それを1にセットする。
spinlock_t lock;
void *entry[0];
}
また、マルチCPU環境では、キャッシュ記述子の lists.shared フィールドにアドレスが格納される共有キャッシュがあります。 ローカル共有キャッシュはすべてのCPUで共有されるため、オブジェクトをローカルキャッシュから別のキャッシュに簡単に移動できます。
III.スラブメモリのカラーリング
例えば、キャッシュライン32バイトの場合、0～31バイトが一度にメモリから書き込まれ/読み出され、32～63バイトが一度にメモリから書き込まれ/読み出されます......。
また、キャッシュのメモリー位置は任意ではありません。
キャッシュ・アドレス0は、メモリ・アドレス0、32、64......に対応します。
キャッシュ・アドレス1は、メモリ・アドレス1、33、65......に対応します。
...
スラブのサイズは整数ページでなければならないので、開始アドレスの最後の12ビットはゼロです。そうすると、2つのスラブの各オブジは同じサイズを持つので、2つのスラブの各オブジは同じキャッシュ行に対応します。 このようにすると、同じ位置を持つ2つのオブジに頻繁にアクセスしなければならなくなり、キャッシュをリフレッシュするのが簡単になり、効率が低下します。
色付けとは、2つ目のスラブの最初にキャッシュ・ラインを空けることです。そうすることで、2つのスラブの各オブジが千鳥配置のキャッシュに対応し、同じ位置にある2つのオブジが頻繁にアクセスされても同じキャッシュ・ラインを使わないようにします。
しかし、この方法にも限界があります。2つのスラブ内のobjオブジェクトへのアクセスは比較的ランダムであり、どの2つがキャッシュラインにあるかは保証されません。
#p#
IV.スラブ・メモリの要求
カーネル・コードのkmem_cachep_alloc()関数は、スラブ経由でオブジェクトを割り当てます：
static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
void *objp;
struct array_cache *ac;
check_irq_off();
//プロセスが置かれているCPUのidでスラブのローカルキャッシュを取得する。
ac = cpu_cache_get(cachep);
//ローカルキャッシュにフリーのスラブオブジェクトがあるか？
if (likely(ac->avail)) {
//もし空きオブジェクトがあれば、ローカル・キャッシュ配列から空きオブジェクトを取り出し、それを使用する。
STATS_INC_ALLOCHIT(cachep);
//ローカル・キャッシュを最近使ったものとしてマークする。
ac->touched = 1;
//の配列から***そのコードは次のように解析される。，HOHO
objp = ac->entry[--ac->avail];
} else {
STATS_INC_ALLOCMISS(cachep);
//ローカル・キャッシュに空きオブジェクトがなくなったので、ローカル・キャッシュを埋める必要がある。
objp = cache_alloc_refill(cachep, flags);
}
return objp;
}
cache_alloc_refill()ローカルキャッシュを埋めるために使用されるだけでなく、場所の本質のスラブの割り当て、コード解析は次のとおりである：
static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
int batchcount;
struct kmem_list3 *l3;
struct array_cache *ac;
check_irq_off();
//根据cpu id得到slab本地高速缓存的数据结构
ac = cpu_cache_get(cachep);
retry:
//batchcount今回解放されるオブジェクトの数を記録する。
batchcount = ac->batchcount;
if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
batchcount = BATCHREFILL_LIMIT;
}
//スラブ・チェーン・テーブルの対応するメモリ・ノードを取得する kmem_list3,各メモリ・ノードは、解放、部分解放、非解放のスラブ・チェーン・テーブルを持つ。
//対応するCPUが自分のメモリー・ノードにアクセスするのが最速だからだ。
l3 = cachep->nodelists[numa_node_id()];
BUG_ON(ac->avail > 0 || !l3);
spin_lock(&l3->list_lock);
//ローカル共有キャッシュからローカルキャッシュへ、解放オブジェクトを埋める。
//システムにとって、ローカル・キャッシュを満たすフリー・オブジェクトは、そのメモリ・ノード上のフリー・オブジェクトでもある。
if (l3->shared && transfer_objects(ac, l3->shared, batchcount))
goto alloc_done;
while (batchcount > 0) {
struct list_head *entry;
struct slab *slabp;
//最初に部分的に解放されたスラブからフリーオブジェクトの割り当て内部で、完全に解放されたスラブを保持する。
//slab十分なメモリーがない場合、メモリーを取り戻すことができる。
entry = l3->slabs_partial.next;
//部分的に解放されたスラブがもうない場合、完全に解放されたスラブに移動して
if (entry == &l3->slabs_partial) {
l3->free_touched = 1;
entry = l3->slabs_free.next;
//完全に解放されたスラブもなくなった場合、スラブ・キャッシュ用に新しいスラブを割り当てなければならない。
if (entry == &l3->slabs_free)
goto must_grow;
}
slabp = list_entry(entry, struct slab, list);
check_slabp(cachep, slabp);
check_spinlock_acquired(cachep);
//スラブ内のフリー・オブジェクトが存在しなくなるか割り当てられるまで、スラブからフリー・オブジェクトを割り当てる。
//kmem_cache_free()関数には十分な数の解放オブジェクトがある。
while (slabp->inuse < cachep->num && batchcount--) {
STATS_INC_ALLOCED(cachep);
STATS_INC_ACTIVE(cachep);
STATS_SET_HIGH(cachep);
//ここで、解放オブジェクトを取得する
ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
numa_node_id());
}
check_slabp(cachep, slabp);
/* move slabp to correct slabp list: */
list_del(&slabp->list);
//対応するスラブの空きメモリが確保されていれば、それをスラブに入れる。_fullコードは次のように解析される： __cache_free()
if (slabp->free == BUFCTL_END)
list_add(&slabp->list, &l3->slabs_full);
else
list_add(&slabp->list, &l3->slabs_partial);
}
must_grow:
l3->free_objects -= ac->avail;
alloc_done:
spin_unlock(&l3->list_lock);
//オブジェクトは割り当てられていない。
if (unlikely(!ac->avail)) {
int x;
//キャッシュに新しいスラブをリクエストする。
x = cache_grow(cachep, flags, numa_node_id());
/* cache_grow can reenable interrupts, then ac could change. */
ac = cpu_cache_get(cachep);
if (!x && ac->avail == 0) /* no objects in sight? abort */
return NULL;
//ローカル・キャッシュをゼロから再作成する
if (!ac->avail) /* objects refilled by interrupt? */
goto retry;
}
ac->touched = 1;
//ローカルキャッシュに戻る***解放オブジェクトのアドレス
return ac->entry[--ac->avail];
}
#p#
V. スラブメモリの解放
スラブ・メモリはkmem_cache_free()関数で解放され、主な処理部分は__cache_free()関数で、そのコードは以下のように解析されます：
static inline void __cache_free(struct kmem_cache *cachep, void *objp)
{
struct array_cache *ac = cpu_cache_get(cachep);
check_irq_off();
objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
if (cache_free_alien(cachep, objp))
return;
//ローカル・キャッシュで利用可能な空きオブジェクトがまだ上限に達していない場合、空きオブジェクトはローカル・キャッシュに入れられる
if (likely(ac->avail < ac->limit)) {
STATS_INC_FREEHIT(cachep);
ac->entry[ac->avail++] = objp;
return;
} else {
//cache_flusharray()ローカル・キャッシュから解放されたオブジェクトをスラブに入れる。
cache_flusharray(cachep, ac);
ac->entry[ac->avail++] = objp;
}
}
static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
{
int batchcount;
struct kmem_list3 *l3;
int node = numa_node_id();
//解放されたオブジェクトのバッチカウントがスラブに返される。
batchcount = ac->batchcount;
check_irq_off();
//得到对应内存节点的slab list3,上面记录着该节点的slab链表
l3 = cachep->nodelists[node];
spin_lock(&l3->list_lock);
//優先順位は最初にローカル共有キャッシュに戻される。
//freeオブジェクトは、各cpuの割り当て時にメモリノードを使用するためだけのものであり、メモリアクセスの効率は次のようになる。***。
if (l3->shared) {
struct array_cache *shared_array = l3->shared;
int max = shared_array->limit - shared_array->avail;
if (max) {
if (batchcount > max)
batchcount = max;
//バッチ数の配列要素をローカルキャッシュにコピーする。
memcpy(&(shared_array->entry[shared_array->avail]),
ac->entry, sizeof(void *) * batchcount);
shared_array->avail += batchcount;
goto free_done;
}
}
//ローカルキャッシュがない場合、スラブに戻す
free_block(cachep, ac->entry, batchcount, node);
free_done:
spin_unlock(&l3->list_lock);
ac->avail -= batchcount;
//少し前進するために残りの空きオブジェクトの削除後、ほほう、まだいくつかの空きオブジェクトが残っているかもしれない！
memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);
}
static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,
int node)
{
int i;
struct kmem_list3 *l3;
for (i = 0; i < nr_objects; i++) {
void *objp = objpp[i];
struct slab *slabp;
//まずオブジェクトから、それがあるページを取得し、次にページから、それ自身のスラブを取得する。
//page->lru.prevページが属するスラブはkmem_cache_free()関数に記録される。
slabp = virt_to_slab(objp);
l3 = cachep->nodelists[node];
list_del(&slabp->list);
check_spinlock_acquired_node(cachep, node);
check_slabp(cachep, slabp);
//対応するスラブに入れる
slab_put_obj(cachep, slabp, objp, node);
STATS_DEC_ACTIVE(cachep);
l3->free_objects++;
check_slabp(cachep, slabp);
/* fixup slab chains */
//slabすべてのオブジェクトが返された
if (slabp->inuse == 0) {
//slabキャッシュの空きオブジェクト数が制限を超えた場合、スラブを解放して
//占有しているメモリを解放する
if (l3->free_objects > l3->free_limit) {
l3->free_objects -= cachep->num;
slab_destroy(cachep, slabp);
} else {
//完全に解放されたスラブ・チェーン・テーブルに追加する
list_add(&slabp->list, &l3->slabs_free);
}
} else {
//部分的に解放されたスラブ・チェーン・テーブルに追加する
list_add_tail(&slabp->list, &l3->slabs_partial);
}
}
}
