読者です 読者をやめる 読者になる 読者になる

Linux 2.0.40の頃のkmalloc()

kernel linux

たまには古いカーネルでも読んでみましょう的なところで、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のメモリを確保して返すことになります。呼び出し元にはヘッダーの領域を返す必要な無いので、ヘッダーの終了アドレスの次の位置を返すことになります。図にすると↓のような感じですね。

f:id:masami256:20160819232743p:plain

struct block_headerのfbh_nextが次の空き領域を指してるわけですね。

ちなみにSLUBだとヘッダーで管理って方法はとっていません。雑に図を描くとこうなります。

f:id:masami256:20160820000040p:plain

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)

改訂3版 Linuxエンジニア養成読本 (Software Design plus)