たまには古いカーネルでも読んでみましょう的なところで、Linux 2.0.40の頃はkmalloc()はどんな実装だったのかというところでも見てみましょう。最近のkmalloc()の実装は使用しているディストーションが採用しているスラブアローケータの__kmalloc()の実装を見てみましょう。今のkmalloc()はスラブアローケータを使用しています。SLUBだとこんな感じです。
で、Linux 2.0.40はkernel.orgのファイル作成日時で見ると08-Feb-2004 07:13となっているので、12年前にリリースされたんですね。このバージョンが2.0系の最終バージョンです。
この当時のkmallocはスラブアローケータは使用していないけど、スラブアローケータ的に要求されたサイズを一番近い2の累乗サイズに切り上げて使っています。サイズはblocksizeという変数で管理してます。
97 static const unsigned int blocksize[] = { 98 32, 99 64, 100 128, 101 252, 102 508, 103 1020, 104 2040, 105 4096 - 16, 106 8192 - 16, 107 16384 - 16, 108 32768 - 16, 109 65536 - 16, 110 131072 - 16, 111 0 112 };
切り上げかたは「要求されたサイズ＋管理用のヘッダーサイズ」に近い次のサイズです。管理用のヘッダーサイズと言うのは、割り当てたメモリ領域を管理するためのヘッダーです。データとしてはstruct block_header型で、x86_32だと8byteになります。
46 struct block_header { 47 unsigned long bh_flags; 48 union { 49 unsigned long ubh_length; 50 struct block_header *fbh_next; 51 } vp; 52 };
例えば、要求サイズが20byteだったとして、8byteがヘッダーに必要なので一番近い32byteのメモリを確保して返すことになります。呼び出し元にはヘッダーの領域を返す必要な無いので、ヘッダーの終了アドレスの次の位置を返すことになります。図にすると↓のような感じですね。
struct block_headerのfbh_nextが次の空き領域を指してるわけですね。
ちなみにSLUBだとヘッダーで管理って方法はとっていません。雑に図を描くとこうなります。
SLUBのポイントは32byteのスラブオブジェクトはヘッダーとかなくて、そのまま32byteの領域です。未使用の領域は先頭に次の空きスラブオブジェクトを指すポインタとして使用します。使用するときはこの領域毎返します。使用中のオブジェクトをkfreeで解放する場合は、また先頭の領域を次の空きスラブオブジェクト指すようにします。次の空きスラブオブジェクトをどう知るかってのはstruct kmem_cache_cpu構造体を使いますが、今日はSLUBの話ではないので、興味のある人はmm/slub.cを読みましょう。
では、kmalloc()を読んできます。
まず最初のほう。
229 void *kmalloc(size_t size, int priority) 230 { 231 unsigned long flags; 232 unsigned long type; 233 int order, dma; 234 struct block_header *p; 235 struct page_descriptor *page, **pg; 236 struct size_descriptor *bucket = sizes; 237 238 /* Get order */ 239 order = 0; 240 { 241 unsigned int realsize = size + sizeof(struct block_header); 242 for (;;) { 243 int ordersize = BLOCKSIZE(order); 244 if (realsize <= ordersize) 245 break; 246 order++; 247 bucket++; 248 if (ordersize) 249 continue; 250 printk("kmalloc of too large a block (%d bytes).\n", (int) size); 251 return NULL; 252 } 253 } 254
最初に必要なサイズを設定し、適切なサイズの領域があるか調べます。 次に、gfpのチェックですね。DMA領域からメモリ確保するかとか。
255 dma = 0; 256 type = MF_USED; 257 pg = &bucket->firstfree; 258 if (priority & GFP_DMA) { 259 dma = 1; 260 type = MF_DMA; 261 pg = &bucket->dmafree; 262 } 263 264 priority &= GFP_LEVEL_MASK; 265
ここは割り込み中なのにGFP_ATOMICを付けずにkmalloc()を呼んだ場合の処理ですね。
266 /* Sanity check... */ 267 if (intr_count && priority != GFP_ATOMIC) { 268 static int count = 0; 269 if (++count < 5) { 270 printk("kmalloc called nonatomically from interrupt %p\n", 271 __builtin_return_address(0)); 272 priority = GFP_ATOMIC; 273 } 274 }
ここから割り込みを禁止して処理が進みます。page変数は最近のSLUBとかを読んでるとstruct pageかな？って思うんですがstruct page_descriptorです。 これはkmalloc用に確保したpageを管理するのに使ってます。そして、この構造体がNULLの場合は、空き領域が無い場合なのでno_bucket_pageラベルにジャンプします。 そうでない場合はpage->firstfreeが次に返すメモリとなります。MF_FREEというのはこの領域を使用していない場合に設定されるようなので、使えると思った領域が実は空いて無かった場合のチェックですね。この場合はnot_free_on_freelistラベルに飛びます。pはstruct block_headerです。
276 save_flags(flags); 277 cli(); 278 page = *pg; 279 if (!page) 280 goto no_bucket_page; 281 282 p = page->firstfree; 283 if (p->bh_flags != MF_FREE) 284 goto not_free_on_freelist;
無事に空き領域が見つかった場合はそのままfound_itラベルのところの処理になります。firstfree変数を更新や、空き領域数(nfree)を減らしたりなどなどです。 returnするときはsizeof(struct block_header)の分を飛ばして、ヘッダーより後のアドレスを返しています。
286 found_it: 287 page->firstfree = p->bh_next; 288 page->nfree--; 289 if (!page->nfree) 290 *pg = page->next; 291 restore_flags(flags); 292 bucket->nmallocs++; 293 bucket->nbytesmalloced += size; 294 p->bh_flags = type; /* As of now this block is officially in use */ 295 p->bh_length = size; 296 #if CONFIG_SADISTIC_KMALLOC 297 memset(p+1, 0xf0, size); 298 #endif 299 return p + 1; /* Pointer arithmetic: increments past header */
次はno_bucket_pageラベルのところです。ここはpageを確保する程度です。pageはstruct pageではなくてstruct page_descriptorです。get_kmalloc_pages()はバディアローケータからページを確保して返しますが、受け取る方はstruct page_descriptor *で受け取ってるだけです。ページが確保できなければno_free_pageラベルにジャンプします。
302 no_bucket_page: 303 /* 304 * If we didn't find a page already allocated for this 305 * bucket size, we need to get one.. 306 * 307 * This can be done with ints on: it is private to this invocation 308 */ 309 restore_flags(flags); 310 311 { 312 int i, sz; 313 314 /* sz is the size of the blocks we're dealing with */ 315 sz = BLOCKSIZE(order); 316 317 page = get_kmalloc_pages(priority, bucket->gfporder, dma); 318 if (!page) 319 goto no_free_page;
ページを確保できた場合はfound_cached_pageラベルのところの処理に入ります。ここでは確保したページに対してkmallocで返す領域のヘッダーを設定していく感じですね。
320 found_cached_page: 321 322 bucket->npages++; 323 324 page->order = order; 325 /* Loop for all but last block: */ 326 i = (page->nfree = bucket->nblocks) - 1; 327 p = BH(page + 1); 328 while (i > 0) { 329 i--; 330 p->bh_flags = MF_FREE; 331 p->bh_next = BH(((long) p) + sz); 332 p = p->bh_next; 333 } 334 /* Last block: */ 335 p->bh_flags = MF_FREE; 336 p->bh_next = NULL; 337 338 p = BH(page+1); 339 }
ヘッダーの設定が終わったら、found_itラベルにジャンプします。
341 /* 342 * Now we're going to muck with the "global" freelist 343 * for this size: this should be uninterruptible 344 */ 345 cli(); 346 page->next = *pg; 347 *pg = page; 348 goto found_it;
ページを確保できなかった場合は、kmalloc_cacheというキャッシュにページがあるか調べて、あればそのページを使います。このキャッシュはkfree時に作ってるようです。条件としてはorder < 3で、DMA領域以外の場合みたいです。キャッシュも無ければ諦めます／(^o^)＼
351 no_free_page: 352 /* 353 * No free pages, check the kmalloc cache of 354 * pages to see if maybe we have something available 355 */ 356 if (!dma && order < MAX_CACHE_ORDER) { 357 page = xchg(kmalloc_cache+order, page); 358 if (page) 359 goto found_cached_page; 360 } 361 { 362 static unsigned long last = 0; 363 if (priority != GFP_BUFFER && priority != GFP_IO && 364 (last + 10 * HZ < jiffies)) { 365 last = jiffies; 366 printk("Couldn't get a free page.....\n"); 367 } 368 return NULL; 369 } 370
最後はnot_free_on_freelistラベルです。空いていると思った領域が空いてないのはおかしいのでエラーメッセージを出してからNULLを返します。
371 not_free_on_freelist: 372 restore_flags(flags); 373 printk("Problem: block on freelist at %08lx isn't free.\n", (long) p); 374 return NULL; 375 }
というわけで、2.0.40のkmalloc()を見てみました。この記事だと新しいほうの解説はほとんどしてないですけども、昔のカーネルと今のカーネルを比較しながら読んでみるのも面白いと思います。
改訂3版 Linuxエンジニア養成読本 (Software Design plus)
- 作者: 養成読本編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2016/08/23
- メディア: 大型本
- この商品を含むブログを見る
