#navi_header|C言語系| お題：malloc(3)で確保したメモリをfree(3)するときに、なぜメモリサイズを渡す必要がないのか調査せよ #more|| #outline|| ---- * malloc(3)とページサイズ取得、関係値の算出 $ locate malloc.c ... /usr/src/lib/libc/stdlib/malloc.c ... malloc(3)のソースから主要部分を抜き書きすると、下のようになる。 #pre||> void * malloc(size_t size) { /* ... */ if (!malloc_started) malloc_init(); if (malloc_sysv && !size) r = 0; else r = imalloc(size); /* ... */ return (r); } ||< 通常であればmalloc_init()の後にimalloc()を呼んでいる。imalloc()の主要コードを見てみる。 #pre||> /* * Allocate a piece of memory */ static void * imalloc(size_t size) { void *result; /* ... */ if ((size + malloc_pagesize) < size) /* Check for overflow */ result = 0; else if (size <= malloc_maxsize) result = malloc_bytes(size); else result = malloc_pages(size); /* ... */ return result; } ||< malloc_maxsizeを以下の場合はmalloc_bytes(), 越える場合はmalloc_pages()を呼んでいる。 malloc_maxsizeの定義を調べてみる。 #ifndef malloc_maxsize #define malloc_maxsize ((malloc_pagesize)>>1) #endif malloc_pagesizeの半分になっている。malloc_pagesizeの定義を調べてみる。 /* * Page size related parameters, computed at run-time. */ static size_t malloc_pagesize; static size_t malloc_pageshift; static size_t malloc_pagemask; ファイル内グローバル変数になっている。値を初期化しているのは、malloc_init()中の以下のコードになっている。 /* * Compute page-size related variables. */ malloc_pagesize = (size_t)sysconf(_SC_PAGESIZE); malloc_pagemask = malloc_pagesize - 1; for (malloc_pageshift = 0; (1UL << malloc_pageshift) != malloc_pagesize; malloc_pageshift++) /* nothing */ ; この箇所を切り出して動かしてみる。 test1.c: #code|c|> #include #include static size_t malloc_pagesize; static size_t malloc_pageshift; static size_t malloc_pagemask; int main(int argc, char *argv[]) { malloc_pagesize = (size_t)sysconf(_SC_PAGESIZE); malloc_pagemask = malloc_pagesize - 1; for (malloc_pageshift = 0; (1UL << malloc_pageshift) != malloc_pagesize; malloc_pageshift++) /* nothing */ ; printf("malloc_pagesize = %d\n", malloc_pagesize); printf("malloc_pageshift = %d\n", malloc_pageshift); printf("malloc_pagemask = %d\n", malloc_pagemask); return 0; } ||< $ cc -Wall -o test1 test1.c $ ./test1 malloc_pagesize = 4096 malloc_pageshift = 12 malloc_pagemask = 4095 malloc_pagesizeは4096バイトで、"/sbin/sysctl -n hw.pagesize"からも取得出来る。malloc_pageshiftについてはビットシフトさせるときの桁数として頻出している。malloc_pagemaskについては-1されているので、丁度 "malloc_pageshift - 1" 桁分が全て1となり、名前の通りbitmaskとして使われている。2進数で表せば次のようになる。 malloc_pagesize = 100...0 (12桁) = 4096 malloc_pagemask = 11...1 (11桁) = 4095 malloc_maxsizeに戻れば、今回の環境では2048となる。imalloc()まで戻ると、次のように場合分けされる。 要求サイズが2048バイト以下：malloc_bytes() 要求サイズが2048バイトを越える：malloc_pages() * pageround()マクロとptr2idx()マクロ 「デーモン君のソース探検」ではこの後malloc_pages()の探索に進む。今回の読書メモでも同様に進めてみるが、準備としてmalloc_pages()で使われている２つのマクロについて先に確認しておく。 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask))) #define ptr2idx(foo) \ (((size_t)(uintptr_t)(foo) >> malloc_pageshift)-malloc_origo) pageround()はpagesizeの倍数に丸める為のマクロになっている。たとえばfooが4098とすれば、 100...10 + 11...11 ---------- 1000...01 = (foo) + (malloc_pagemask) &1100...00 = &(~(malloc_pagemask)) ---------- 1000...00 = 8192 と言う具合に、一旦malloc_pagemask分加算して端数が落ちないように底上げした後、malloc_pagemaskの反転bitでANDを取れば綺麗に4096の倍数に丸められる。 ptr2idx()は、アドレスからページ管理の為のインデックスに変換するマクロになっている・・・らしい。データ構造がまだこの時点では明らかになっていないため、断言出来ない。ptr2idxで使われているmalloc_origoについては、malloc_init()中の以下のコードで初期化されている。 #pre||> /* Allocate one page for the page directory */ page_dir = (struct pginfo **) MMAP(malloc_pagesize); if (page_dir == (struct pginfo **) -1) wrterror("mmap(2) failed, check limits.\n"); /* * We need a maximum of malloc_pageshift buckets, steal these from the * front of the page_directory; */ malloc_origo = pageround((size_t)(uintptr_t)sbrk((intptr_t)0)) >> malloc_pageshift; malloc_origo -= malloc_pageshift; malloc_ninfo = malloc_pagesize / sizeof *page_dir; ||< まずMMAPはmalloc.c内のマクロ定義で次のようなmmap(2)のラッパーになっている。 #pre||> #ifndef MMAP_FD #define MMAP_FD (-1) #endif /* ... */ /* Macro for mmap */ #define MMAP(size) \ mmap(0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \ MMAP_FD, (off_t)0); ||< MAP_ANON + ファイル記述子が-1の場合、特にファイルとは結びつかずにメモリ領域が確保される。APUEのChapter14, Fig14.32を見る限りでは、mmap(2)が返すメモリアドレスはsbrk(2)が操作するheap領域とは重ならないようになっているらしい。つまり、sbrk(2)とは無関係なメモリ領域にmalloc_pagesize、つまり１ページ分のメモリ領域を確保した事になる。その領域はpginfo構造体のダブルポインタである page_dir に格納されている。 その後この時点でのheap先頭を sbrk(0) により取得し、そのアドレスをページサイズ単位で丸め、さらにpageshift分右シフトさせている。 malloc_origo = pageround((size_t)(uintptr_t)sbrk((intptr_t)0)) >> malloc_pageshift; さらにpageshift分、縮めている。 malloc_origo -= malloc_pageshift; ここでptr2idx()マクロと比べてみると、ちょうどお互いに逆処理を行っていることが分かる。 ptr2idx(foo) = (foo >> malloc_pageshift) - malloc_origio malloc_origo = (pageround(sbrk(0)) >> malloc_pageshift) - malloc_pageshift よって、 ptr2idx(foo) = (foo >> malloc_pageshift) - ((pageround(sbrk(0)) >> malloc_pageshift) + malloc_pageshift fooに渡るのはmalloc()処理の中で扱われるので、おおむねページサイズの整数倍になっている=pageround()処理されているアドレスだろう。ptr2idxでmalloc.cを検索してみると、次のようにpage_dirを配列とした時の添字に使われている。 page_dir[ptr2idx(アドレス)] つまりptr2idxはアドレスを元にしてpage_dirにアクセスする時の添字を返すマクロであることが分かる。これにより、pginfo構造体のポインタにアクセス出来る(page_dirはpginfo構造体へのダブルポインタ)。またmalloc_pageshiftで底上げ調整が行われている為、例えアドレスが0だったとしても、ptr2idx()を通すと malloc_pageshift に変換される。 ptr2idx(0) == malloc_pageshift 今回の環境であれば malloc_pageshift は 12 なので、 page_dir[ptr2idx(0)] => page_dir[12] となる。page_dir[0] - [11]の用途はページサイズ以下のメモリ割り当てで使われ、詳細は後述する。 もちろん、初期状態ではpginfo構造体へのポインタ用の領域は１ページサイズ分しかmmap(2)で確保されていない。pginfo構造体へのポインタがいくつ格納出来るかは、malloc_init()の次の行でmalloc_ninfo変数に初期値が計算され、格納されている。 malloc_ninfo = malloc_pagesize / sizeof *page_dir; もしpginfo構造体(へのポインタ)の数がこれを越えようとした場合は、map_pages()の中で自動判定・extend_pgdir()で再度MAP_ANONでmmap(2)しなおしている。 * malloc_pages()：ページサイズの半分を越える領域の確保 malloc_pages()まで戻る。malloc_pages()のコードで重要部分を抜き書きすると次のようになる。エラー処理や過去にfree()したページの探索部分は削っている。 #pre||> /* * Allocate a number of complete pages */ static void * malloc_pages(size_t size) { void *p, *delay_free = 0; size_t idx; /* サイズをページサイズで丸める */ idx = pageround(size); if (idx < size) { errno = ENOMEM; return NULL; } else size = idx; p = 0; /* ... */ /* ページ単位に変換してmap_pages()に渡す */ size >>= malloc_pageshift; /* Map new pages */ if (!p) p = map_pages(size); if (p) { /* 確保したアドレス範囲に対応する page_dir[XX] に、MALLOC_FIRSTを先頭にしてMALLOC_FOLLOWを埋める */ idx = ptr2idx(p); page_dir[idx] = MALLOC_FIRST; for (i=1;i #include #include #include #include static size_t malloc_origo; static size_t malloc_pagesize; static size_t malloc_pageshift; static size_t malloc_pagemask; #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask))) #define ptr2idx(foo) \ (((size_t)(uintptr_t)(foo) >> malloc_pageshift)-malloc_origo) void do_malloc(size_t size) { void *ptr; size_t idx; int i; ptr = malloc(size); printf("malloc(%d) = %p\n", size, ptr); idx = ptr2idx(ptr); size = pageround(size) >> malloc_pageshift; printf("page_dir[%d] = MALLOC_FIRST\n", idx); for (i = 1; i < size; i++) { printf("page_dir[%d] = MALLOC_FOLLOW\n", idx + i); } } int main(int argc, char *argv[]) { void *ptr; malloc_pagesize = (size_t)sysconf(_SC_PAGESIZE); malloc_pagemask = malloc_pagesize - 1; for (malloc_pageshift = 0; (1UL << malloc_pageshift) != malloc_pagesize; malloc_pageshift++) /* nothing */ ; ptr = sbrk((intptr_t)0); malloc_origo = pageround((size_t)(uintptr_t)ptr) >> malloc_pageshift; malloc_origo -= malloc_pageshift; do_malloc(1 * 4096 + 1); do_malloc(3 * 4096 + 1); return 0; } ||< コンパイル＋実行例 #pre||> $ cc -Wall -o test3 test3.c $ ./test3 malloc(4097) = 0x804b000 page_dir[13] = MALLOC_FIRST page_dir[14] = MALLOC_FOLLOW malloc(12289) = 0x805d000 page_dir[31] = MALLOC_FIRST page_dir[32] = MALLOC_FOLLOW page_dir[33] = MALLOC_FOLLOW page_dir[34] = MALLOC_FOLLOW ||< この時点で、アドレスのみでfree(3)を行える手がかりは掴めてきた。アドレスからpage_dirのインデックスに変換するマクロは用意され、さらにmalloc(3)された時にページ単位で確保されたか判定する為のマジックナンバーも判明した。 そこで早速、free(3)の本体であるifree()関数を見てみる。 ** ifree() → free_pages()による解放処理 ifree()で重要な部分は以下のコードである。見て分かる通り、ptr2idx()マクロで取得した添字でpage_dirにアクセスし、MALLOC_MAGIC以下ならページ単位で確保された事を意味するのでfree_pages()を呼んでいる。 #pre||> static void ifree(void *ptr) { struct pginfo *info; size_t idx; /* ... */ idx = ptr2idx(ptr); /* ... */ info = page_dir[idx]; if (info < MALLOC_MAGIC) free_pages(ptr, idx, info); else free_bytes(ptr, idx, info); return; } ||< free_pages()側では以下のコードでMALLOC_FREEに更新している。 #pre||> static __inline__ void free_pages(void *ptr, size_t idx, struct pginfo *info) { /* ... */ /* Count how many pages and mark them free at the same time */ page_dir[idx] = MALLOC_FREE; for (i = 1; page_dir[idx+i] == MALLOC_FOLLOW; i++) page_dir[idx + i] = MALLOC_FREE; ||< この後に、free(3)された領域管理用のpgfree構造体の確保やリスト操作が続くが今回のお題とは関係が薄い為、省略する。 ここまででページ単位でのmalloc(3)/free(3)の関係は把握出来た。続いてページサイズの半分以下のケースについて追ってみる。 * malloc_bytes() : ページサイズの半分以下の領域確保 imalloc()のコードより、ページサイズの半分以下のメモリ確保にはmalloc_bytes()が使われる。 malloc_bytes()ではpginfo構造体が出てくるので、ここでpginfo構造体の定義をソースより抜き出してみる。 #pre||> struct pginfo { struct pginfo *next; /* next on the free list */ void *page; /* Pointer to the page */ u_short size; /* size of this page's chunks */ u_short shift; /* How far to shift for this size chunks */ u_short free; /* How many free chunks */ u_short total; /* How many chunk */ u_int bits[1]; /* Which chunks are free */ }; /* * How many bits per u_int in the bitmap. * Change only if not 8 bits/byte */ #define MALLOC_BITS (8*sizeof(u_int)) ||< 今の時点ではコメント内容の多くが不明だが、とりあえずmalloc_bytes()の中へ進んでみる。 まず前半部分： #pre||> static void * malloc_bytes(size_t size) { size_t i; int j; u_int u; struct pginfo *bp; int k; u_int *lp; /* Don't bother with anything less than this */ if (size < malloc_minsize) size = malloc_minsize; /* Find the right bucket */ j = 1; i = size-1; while (i >>= 1) /* サイズのビット桁をカウントし、page_dirの添字とする */ j++; /* If it's empty, make a page more of that size chunks */ if (!page_dir[j] && !malloc_make_chunks(j)) return 0; bp = page_dir[j]; ||< page_dirの添字については、ページ単位の場合はptr2idx()マクロによりpageshift分底上げされていたことを思い出すと、今回の環境ではpageshiftが12なので malloc_pages : page_dir[12] - malloc_bytes : page_dir[0] - [11] までアクセスされることになる。 なお最小サイズがmalloc_minsizeに補正され、上のdefineを見ると16になっている為、実際はpage_dir[4]以降を扱う。 添字はjに格納され、page_dir[j]が空の場合はmalloc_make_chunks()で領域が確保されるらしい。malloc_make_chunks()については後ほど追ってみるが、ざっと眺めた限りではpginfo構造体を確保して多少弄っているようだ。 bpにはpage_dir[j]で参照されるpginfo構造体のアドレスが格納される。そしてmalloc_bytes()の後半が以下のように続く。 #pre||> /* Find first word of bitmap which isn't empty */ for (lp = bp->bits; !*lp; lp++) ; /* Find that bit, and tweak it */ u = 1; k = 0; while (!(*lp & u)) { u += u; k++; } *lp ^= u; /* If there are no more free, remove from free-list */ if (!--bp->free) { page_dir[j] = bp->next; bp->next = 0; } /* Adjust to the real offset of that chunk */ k += (lp-bp->bits)*MALLOC_BITS; k <<= bp->shift; if (malloc_junk) memset((u_char*)bp->page + k, SOME_JUNK, (size_t)bp->size); return (u_char *)bp->page + k; } ||< 最初にpginfo構造体のbitsメンバに対して、空でない要素を探すループがある。元々のpginfo構造体の定義としてはbitsメンバはu_intの1要素の配列なので、malloc_make_chunks()の中で弄られていることが予想される。 空でないu_int要素が見つかると、bitsを調べ空いているbitが見つかればXORでそのbitをセットするのが次のコードブロックにあたる。 /* Find that bit, and tweak it */ u = 1; k = 0; while (!(*lp & u)) { u += u; /* 2倍している＝"u <<= 1" */ k++; } *lp ^= u; /* XOR */ freeについては省略して、その後、飛び越したu_intの要素分ｘそのbit桁(MALLOC_BITS)を計算し、shiftメンバ分だけシフトさせる事で実際のoffsetが計算される。 /* Adjust to the real offset of that chunk */ k += (lp-bp->bits)*MALLOC_BITS; k <<= bp->shift; 最後にpageメンバにoffsetを加算した値を返すことで、malloc_bytes()は呼び出し元に戻る。 return (u_char *)bp->page + k; ** malloc_make_chunks()の流れ 続いてpginfo構造体を初期化するmalloc_make_chunks()を見てみるが、解説の殆どは「デーモン君のソース探検」で書かれている為、こちらの読書メモではざっくりと読み散らす程度に留める。((べ、別にソースが理解出来なかったわけじゃ以下ｒｙ)) 最初に1ページ分ざっくりと確保してしまう。 /* Allocate a new bucket */ pp = malloc_pages(malloc_pagesize); 続いてmalloc_bytes()から渡されてきたbits桁数に応じて、u_intの配列要素bitsメンバを増やした場合の構造体サイズを計算している。 /* Find length of admin structure */ l = (int)offsetof(struct pginfo, bits[0]); l += sizeof bp->bits[0] * (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS); "offsetof"についてはstddef.hで定義されたマクロである。0番地アドレスを仮の構造体先頭アドレスにすることで、メンバへのオフセットを計算出来る。 stddef.h:#define offsetof(type, member) \ ((size_t)(unsigned long)(&((type *)0)->member)) 桁数と計算された構造体の大きさに応じて、先ほど確保した1ページの中にpginfo構造体を含めてやりくりするか、pginfo構造体は別の場所に確保するか場合分けしている。 /* Don't waste more than two chunks on this */ if ((1<<(bits)) <= l+l) { bp = (struct pginfo *)pp; } else { bp = (struct pginfo *)imalloc((size_t)l); if (!bp) { ifree(pp); return 0; } } その後pginfo構造体の各メンバを初期化している。 bp->size = (1<shift = bits; bp->total = bp->free = malloc_pagesize >> bits; bp->page = pp; もしも1ページ内でpginfo構造体も含めてやりくりする場合は、 bp = bp->page = pp が成立する。 この後bitsメンバが初期化され(省略)、もし1ページ内でpginfo構造体も含めてやりくりする場合は、pginfo構造体の分だけbitsメンバを調整する処理が以下のコードブロックになる： if (bp == bp->page) { /* Mark the ones we stole for ourselves */ for(i=0;l > 0;i++) { bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS)); bp->free--; bp->total--; l -= (1 << bits); } } 最後にpage_dirやnextメンバを調整して完了となる。 page_dir[ptr2idx(pp)] = bp; bp->next = page_dir[bits]; page_dir[bits] = bp; ざっくりとだがこれでmalloc_bytes()およびmalloc_make_chunks()の動きを把握出来た。 対になるfree_bytes()については解説を省略するが、pginfo構造体の情報を用いて該当bitをクリアし、同時にfreeした領域の管理情報をそうさしている。 かなりややこしかったが、以上でmalloc(3)とfree(3)で、なぜfree(3)がメモリアドレスだけで領域を解放できるのか判明した。まずページサイズの半分より大きい場合はページサイズ単位に丸め、アドレスから管理情報のインデックス番号へ変換するマクロにより、free(3)ではアドレスだけで管理情報を適切に操作出来る。 ページサイズの半分以下の場合はまず1ページ分確保してしまい、内部を実際に指定されたサイズで分割し、bitmapで利用状況を管理する。free(3)からも管理情報にアクセスできるようになっているため、同様にアドレスだけで解放処理を行うことが出来る。 ページサイズの半分以下の場合の処理が特に複雑になっているが、その理由とこのmallocの設計思想については「デーモン君のソース探検」を参照のこと。 今回のお題については、ここまで。 #navi_footer|C言語系|