Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
$B%a%b%j4IM}!"(BBuddy$B%7%9%F%`!"(Bkmalloc$B!"%9%i%V%"%m%1!<%?(B

$B%a%b%j4IM}!"(BBuddy$B%7%9%F%`!"(Bkmalloc$B!"%9%i%V%"%m%1!<%?(B

					2011$BG/(B01$B7n(B11$BF|(B
$B>pJs2J3XN`(B $B%*%Z%l!<%F%#%s%0%7%9%F%`(B II

                                       $BC^GHBg3X(B $B%7%9%F%`>pJs9)3X8&5f2J(B 
                                       $B%3%s%T%e!<%?%5%$%(%s%9@l96(B, $BEE;R!&>pJs9)3X7O(B
                                       $B?7>k(B $BLw(B
                                       <yas@is.tsukuba.ac.jp>

$B$3$N%Z!<%8$O!" http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2010/2011-01-11
$B$"$k$$$O!" http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

$B"#O"Mm;v9`(B

Softlab $B8&5f<<>R2p(B

$B6541!'HDLn(B $B9N;0!"?7>k(B $BLw!":4F#(B $BAo(B
$BJg=8!'#6?M(B
$B%F!<%^!'%*%Z%l!<%F%#%s%0!&%7%9%F%`!"%;%-%e%j%F%#!"J,;6%7%9%F%`!"8@8l=hM}7O!"$=$NB>!#(B
$B>l=j!'(B3E302
$BF|;~(B
1. 2010$BG/(B12$B7n(B08$BF|(B ($B?e(B) 16:45-18:00 ($B=*N;(B)
2. 2010$BG/(B12$B7n(B14$BF|(B ($B2P(B) 16:45-18:00 ($B=*N;(B)
3. 2011$BG/(B01$B7n(B11$BF|(B ($B2P(B) 16:45-18:00 ($BK\F|(B)

$B"#:#F|$NBg;v$JOC(B

Buddy$B%7%9%F%`$K$h$kJ*M}%a%b%j$N4IM}(B
kmalloc() $B$H(B kfree()
$B%9%i%V%"%m%1!<%?(B

$B"#%a%b%j4IM}(B

$BJ*M}%a%b%j$r4IM}$9$k!#(B$B3F%a%b%j$N%U%l!<%`$4$H$K!"2?$K;H$o$l$F$$$k$N(B $B$+!"6u$$$F$$$k$N$+$r4IM}$9$k!#%a%b%j$,I,MW$K$J$C$?$i!"6u$$$F$$$k$b$N$r(B $B3d$jEv$F$k!#(B
$B%+!<%M%k<+?H$NO@M}%"%I%l%96u4V$r4IM}$7!"J*M}%a%b%j$r3d$jEv$F$k!#(B
$B%f!<%6!&%W%m%;%9$KBP$7$F!"O@M}%"%I%l%96u4V$r4IM}$7!"(B $BJ*M}%a%b%j$r3d$jEv$F$k!#(B
$B6u$$$F$$$k%a%b%j$,ITB-$7$F$-$?$i!"%Z!<%8%"%&%H$7$?$j!"(B $B%W%m%;%9$r;&$7$F6u$-%a%b%j$r3NJ]$9$k!#(B

$B"!L\I8(B

$B30It%U%i%0%a%s%F!<%7%g%s$r>/$J$/$9$k!#(B
$BJ,$+$j$d$9$$(B API

$B8zN($N$h$$

$B"#J*M}%a%b%j$N4IM}(B

Linux $B$G$O!"Ek:\$5$l$F$$$k%a%b%j$r%Z!<%8%5%$%:(B(4KB-8KB$B$,0lHLE*(B)$B$GJ,3d$74IM}$9$k!#(B $B$=$l$rJ*M}%Z!<%8(B(physical page)$B!"$"$k$$$O!"%Z!<%8!&%U%l!<%`(B(page frame)$B$H8F$V!#(B
1$B$D$N%Z!<%8!&%U%l!<%`$K$O!"9=B$BN(B struct page $B$G4IM}$9$k!#(B
$BA4%a%b%j$O!"9=B$BN(B struct page $B$NG[Ns$H$7$FJ];}$5$l$k!#(B $B$?$H$($P!"%Z!<%8%5%$%:(B 4KB $B$G!"(B1GB $B$NJ*M}%a%b%j$r;}$C$?%7%9%F%`$G$O!"(B 1024*1024*1024/(4*1024) == 262,144 $B8D$NMWAG$+$i$J$kG[Ns$G4IM}$5$l$k!#(B

$B"!%Z!<%89=B$BN(B

include/linux/mm_types.h
  34:	struct page {
  35:	        unsigned long flags;            /* Atomic flags, some possibly
  36:	                                         * updated asynchronously */
  37:	        atomic_t _count;                /* Usage count, see below. */
...
  48:	        union {
  49:	            struct {
  50:	                unsigned long private;          /* Mapping-private opaque data:
  57:	                struct address_space *mapping;  /* If low bit clear, points to
  64:	            };
...
  69:	            struct page *first_page;    /* Compound tail pages */
  70:	        };
...
  71:	        union {
  72:	                pgoff_t index;          /* Our offset within mapping. */
  73:	                void *freelist;         /* SLUB: freelist req. slab lock */
  74:	        };
  75:	        struct list_head lru;           /* Pageout list, eg. active_list
...
  89:	        void *virtual;                  /* Kernel virtual address (NULL if
  90:	                                           not kmapped, ie. highmem) */
...
 103:	};

count: $B%Z!<%8$N;2>H%+%&%s%H!#(B0 $B$+Ii$J$i!"$=$N%Z!<%8!&%U%l!<%`$O6u$$$F(B $B$$$k(B( $BB>$NL\E*$G;H$C$F$h$$(B)$B$3$H$r0UL#$9$k!#(B 1$B0J>e$J$i!"0J2<$NL\E*$G;H$o$l$F$$$k!#(B
- $B%Z!<%8!&%-%c%C%7%e(B(page cache)
- $B%W%i%$%Y!<%H$J%G!<%?(B
- $B%W%m%;%9$N%Z!<%8%F!<%V%k(B
mappping: $B%Z!<%8$,%Z!<%8!&%-%c%C%7%e(B($B%U%!%$%k$N0lIt$HBP1~$7$F$$$k%a%b%j(B)$B$rJ];}$7$F$$$k;~!"(B $B%"%I%l%96u4V9=B$BN(B(struct address_space)$B$H7k$S$D$1$i$l$k!#(B mappping $B%U%#!<%k%I$O!"$=$N%Z!<%8$,%a%s%P$H$J$C$F$$$k%"%I%l%96u4V9=B$BN$r;X$9!#(B $B%"%I%l%96u4V9=B$BN$, lru: Least Recently Used $B$G%a%b%j4IM}$r9T$&$?$a$NAPJ}8~%j%9%H!#(B active_list ($B;H$o$l$F$$$k%a%b%j$N%j%9%H(B)$B$+(B inactive_list ($B;H$o$l$F$$$J$$%a%b%j$N%j%9%H!"B>$NL\E*$K;H$C$F$b$h$$%a%b%j$N%j%9%H(B)$B$K$D$J$,$l$k!#(B
virtual: $B$=$N%Z!<%8$N%+!<%M%kFb$N%"%I%l%9!#(B high memory $B$H8F$P$l$F$$$k%a%b%j$N>l9g!"$3$l$O(B NULL $B$K$J$C$F$$$k$N$G!"(B $B%+!<%M%kFb$N%W%m%0%i%`$+$i%"%/%;%9$9$k;~$K$OF0E*$K%^%C%W$9$kI,MW$,$"$k!#(B

page$B9=B$BN$N(Bflags($B
PG_locked	$B%Z!<%8$,%T%sN1$a$5$l$F$$$k!#%Z!<%8%"%&%H$5$l$J$$!#F~=PNO$N=hM}Cf$K@_Dj$5$l!"40N;8e$K2r=\|$5$l$k!#(B
PG_error	$B$3$N%Z!<%8$KBP$7$FF~=PNO%(%i!<$,@8$8$?!#(B
PG_referenced	$B%G%#%9%/F~=PNO$N$?$a$K;2>H$5$l$F$$$k!#(B
PG_uptodate	$B%Z!<%8$NFbMF$,M-8z$G$"$k!#F~NO=hM}$,40N;$7$?!#(B
PG_dirty	$B%Z!<%8$NFbMF$,JQ99$5$l$?!#(B
PG_lru	$B%Z!<%8%s%0$N$?$a$N(B LRU $B%j%9%H$K$"$k!#(B
PG_active	$B%Z!<%8$,%"%/%F%#%V$G$"$k!#(B
PG_slab	$B%9%i%V!&%"%m%1!<%?$G3d$jEv$F$i$l$?!#(B
PG_arch_1	$B%"!<%-%F%/%A%c8GM-$N%Z!<%8>uBV(B
PG_reserved	$B%Z!<%8%"%&%H6X;_!"$^$?$O!"%V!<%I;~$N%a%b%j!&%"%m%1!<%?$G3d$jEv$F$i$l$?(B
PG_private	$B%Z!<%8$NFbMF$,L58z(B(page->private $B$,M-8z$JFbMF$rJ];}$7$F$$$k(B)
PG_writeback	$B=q$-La$7Cf(B
PG_compound	$BJ#9g%Z!<%8(B
PG_reclaim	$B3+J\|$9$Y$-%Z!<%8(B

$B"!%a%b%j!&%>!<%s(B

$BNr;KE*$JET9g$d%O!<%I%&%'%"$N@)Ls$G!"%a%b%j!&%Z!<%8$r!V%>!<%s!W$H8F$P$l$kNN0h$KJ,3d$7$F4IM}$9$k!#(B

$B$h$/;H$o$l$k%>!<%s$N

ZONE_DMA

($B8E$$%G%P%$%9$G$b(B) DMA $B$G%"%/%;%92DG=$J%Z!<%8!&%U%l!<%`!#(B x86 $B$G$O!"(B0-16M$B!#(B ISA $B%P%9$N%G%P%$%9$G(B 0-16M $B$7$+%"%/%;%9$G$-$J$$$b$N$,$"$C$?!#(B

ZONE_NORMAL

($B8E$$%G%P%$%9$N(B)DMA $B$G$O%"%/%;%9$G$-$J$$$,!"%+!<%M%k$N2>A[%"%I%l%96u4V$K>o$K%^%C%W$5$l$F$$$k!#(B x86 $B$G$O!"(B16MB-896MB$B$^$G!#(B

ZONE_HIGMEM

$BIaCJ$O%+!<%M%k$N2>A[%"%I%l%96u4V$K%^%C%W$5$l$F$$$J$$!#(B $B;H$&$H$-$K$O%^%C%W$7$F;H$$!";H$$=*$o$C$?$i%"%s%^%C%W$9$k!#(B x86 $B$G$O!"(B896MB $B$h$jBg$-$$=j!#(B

$B"!(Bzone$B9=B$BN(B

include/linux/mmzone.h

 280:	struct zone {
...
 284:	        unsigned long watermark[NR_WMARK];
...
 321:	        struct free_area        free_area[MAX_ORDER];
...
 391:	        wait_queue_head_t       * wait_table;
 392:	        unsigned long           wait_table_hash_nr_entries;
 393:	        unsigned long           wait_table_bits;
...
 418:	        const char              *name;
 419:	} ____cacheline_internodealigned_in_smp;
...
 158:	enum zone_watermarks {
 159:	        WMARK_MIN,
 160:	        WMARK_LOW,
 161:	        WMARK_HIGH,
 162:	        NR_WMARK
 163:	};
... 
  23:	#ifndef CONFIG_FORCE_MAX_ZONEORDER
  24:	#define MAX_ORDER 11
  25:	#else
  26:	#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  27:	#endif
  28:	#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

watermark: $B%a%b%j$,$3$N?e0L(B(warter mark)$B$r2<2s$k$H!"%+!<%M%k$O(B $B%a%b%jITB-BP:v$rH/F0$9$k!#(B
free_area: $BMxMQ2DG=$JNN0h$rJ];}$9$k!#(B
wait_table, wait_table_hash_nr_entries, wait_table_bits: $B%a%b%j$,(B $BB-$j$J$$;~$K!"%W%m%;%9$r%9%j!<%W$5$;$k$?$a$K;H$&!#%9%j!<%WCf!"%+!<%M%k(B $B$OB>$N%W%m%;%9$N%a%b%j$r%Z!<%8%"%&%H$9$k$J$I$7$F6u$-%a%b%j$r:n$k$h$&$K(B $B$,$s$P$k!#%9%j!<%W$+$i2r=|$5$l$?$i!"$b$&0lEY%a%b%j$r3NJ]$9$k$3$H$r;n$_(B $B$k!#(B
name: $B%>!<%s$NL>A0!#(B

$B"!%Z!<%8%U%l!<%`$N3dEv$F$H3+J|(B

$B%Z!<%8!&%U%l!<%`$O!"J*M}%a%b%j!#(B Linux $B%+!<%M%kFb$G$O!"

alloc_pages(gfp_mask,order): 2$B$N(Border$B>h(B(^order, 1 << order)$BC10L$G%a%b%j$r(B $B3d$jEv$F$k!#@hF,$N%Z!<%8%U%l!<%`$KBP1~$7$?(B struct page $B$X$N%]%$%s%?$rJV$9!#(B

page_address(page): struct page$B$X$N%]%$%s%?$+$i%"%/%;%92DG=$JO@M}%"%I%l%9$rF@$k!#(B

__get_free_pages(gfp_mask,order): 2$B$N(Border$B>h$N%a%b%j$r3dEv$F!"O@M}%"%I%l%9$rF@$k!#(B

alloc_page(gfp_mask): 1$B%Z!<%83d$jEv$F!"(Bstruct page $B$X$N%]%$%s%?$rJV$9!#(B

__get_free_page(gfp_mask): 1$B%Z!<%83d$jEv$F!"HVCO$rJV$9!#(B

get_zeroed_page(gfp_mask): 0 $B$GKd$a$i$l$?(B1$B%Z!<%8$NO@M}%"%I%l%9$rJV$9!#(B

__free_pages(page,order)

free_pages(addr, order)

free_page(order)

include/linux/gfp.h

 302:	static inline struct page *
 303:	alloc_pages(gfp_t gfp_mask, unsigned int order)
 304:	{
...
 306:	}
 316:	extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
 314:	#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

 328:	extern void __free_pages(struct page *page, unsigned int order);
 329:	extern void free_pages(unsigned long addr, unsigned int order);
 333:	#define free_page(addr) free_pages((addr), 0)

$B"!30It%U%i%0%a%s%F!<%7%g%s(B

$BJ*M}%U%l!<%`$N3dEv$F$H3+J|$r7+$jJV$7$F$$$/$H!"30It%U%i%0%a%s%F!<%7%g%s(B (external fragmentation) $B$,@8$8$k!#A4BN$H$7$F$O6u$-%a%b%j$OB8:_$7$F$$$k(B $B$N$K!">.$5$J%a%b%j!&%U%l!<%`$,$"$A$3$A$KJ,;6$7$F$$$F!"Bg$-$5$N%Z!<%8%U(B $B%l!<%`$,B8:_$7$J$$$?$a$K%a%b%j$,3d$jEv$F$i$l$J$$>uBV$K4Y$k!#(B

$B"!(BBuddy$B%7%9%F%`(B

$B!V(BBuddy $B%7%9%F%`!W$O!"(BLinux $B$G;H$o$l$F$$$k30It%U%i%0%a%s%F!<%7%g%s$r5/(B $B$3$7$K$/$$%a%b%j3dEv$F%"%k%4%j%:%`!#(B

$BMxMQ2DG=$J%a%b%j!&%V%m%C%/$N%j%9%H$r4IM}$9$k!#(B $B%j%9%H$N?t$O!"(BMAX_ORDER$B8D!#(B
$B3F%j%9%H$O!"(B2$B$N$Y$->h$NBg$-$5$N%a%b%j!&%V%m%C%/$rJ];}$9$k(B( 2 ⁰, 2 ¹, 2 ², ..., 2 ^{(MAX_ORDER-1)}, )$B!#(B
$B%Z!<%8%U%l!<%`$N3dEv$F(B(alloc_pages())$B$G$O!"(B $BI,MW$J:G>.$N%a%b%j!&%V%m%C%/$r3d$jEv$F$k!#(B($BBg$-$J%V%m%C%/$r29B8$9$k!#(B) 2 ^order $B$,M_$7$$;~$K!"(B $B$=$N%a%b%j$,$"$l$P!"$=$l$rJV$9!#(B $B$J$1$l$P!"(B2 ^order+1 $B$rC5$7$F!"$=$l$r(B $BH>J,$KJ,3d$7$F!"JV$9!#(B $B!J;H$o$J$+$C$?J,$O!"(B2 ^order $B$N%j%9%H$K$D$J$0!#!K(B
$B%Z!<%8%U%l!<%`$N3+J|(B(__free_pages())$B$G$O!"(B 2 ^order $B$N%5%$%:$N%V%m%C%/$rMxMQ2DG=$J%j%9%H$K@\B3$9$k!#(B $BF1$8Bg$-$5$N%V%m%C%/$NCf$GO"B3$7$F$$$k$b$N(B(buddy)$B$,$J$$$+$rC5$9!#(B $B$"$l$P!"7k9g$7$FBg$-$J%V%m%C%/(B(2 ^(order+1)) $B$K$7$F%j%9%H$K@\B3$9$k!#(B

$B?^(B1(a) Buddy$B%7%9%F%`$K$h$k6u$-%Z!<%8$N4IM}(B($BO@M}E*$J8+J}(B)

$B?^(B1(b) Buddy$B%7%9%F%`$K$h$k6u$-%Z!<%8$N4IM}(B($B@~7A$J8+J}(B)

$B"!(BBuddy$B%7%9%F%`$N>uBV(B

/proc/buddyinfo $B$r8+$k$H!"8=:_$N6u$-%Z!<%8$N>uBV$,J,$+$k!#(B

% cat /proc/buddyinfo 
Node 0, zone      DMA      6      5      3      3      4      2      2      0      1      1      2 
Node 0, zone   Normal    476   2577    990    354    174    104     65     34     19      1    135 
Node 0, zone  HighMem   1416   2920   1718   1082    933    504    251    152     87     43     53 
%

$B$3$NNc$G$O!"(BDMA $B%>!<%s$N(B 2 ⁰ (4KB) $B$K!"(B6 $B8D!"(B 2 ¹ (8KB) $B$K!"(B5 $B8D!"!&!&!&!"(B2 ¹⁰ $B$K(B2$B8D$N6u$-$,$"$k!#(B $B30It%U%i%0%a%s%F!<%7%g%s$,5/$-$k$H!"Bg$-$J2t$,>/$J$/$J$k!#(B

$B"#(Bkmalloc$B$H(Bkfree

$BJ*M}%a%b%j$O!"%Z!<%8C10L!J(B4KB$B$N%Z!<%8%U%l!<%`C10L!K$G4IM}$7$F$$$k!#(B $B$7$+$7!"%+!<%M%kFb$N%G!<%?9=B$$O!"(B4KB $B$K$T$C$?$j$O$^$i$J$$!#(B Linux $B$G%Z!<%8C10L$G$O$J$$C10L$G%a%b%j$r3NJ]!&3+J|$G$-$k$K$O!"

kmalloc(), kfree(): malloc(), free() $B$HN`;w$N(B API

$B%9%i%V!&%"%m%1!<%?(B

$B"!(Bkmalloc()

C$B8@8l$N%f!<%66u4V$G;H$($k%i%$%V%i%j(B malloc() $B$K;w$F$$$k!#(B

void *kmalloc(size_t size, gfp_t flags)

$B0z?t(B

size: $B%P%$%H?t(B
flags: $B%U%i%0(B($B0J2<$G@bL@(B)

$B7k2L(B: $B:GDc8B!"(Bsize $BJ,$N%a%b%j$r3d$jEv$F!"$=$N@hF,$NHVCO!J%+!<%M%kFb$N2>(B $BA[%"%I%l%9!K$rJV$9!#3d$jEv$F$i$l$?%a%b%j$O!"J*M}E*$K$bO"B3$K$J$k!#3dEv(B $B$F$G$-$J$$;~$K$O!"(BNULL $B$rJV$9!#(B

$B"!(Bkmalloc()$B$N%U%i%0(B(gfp_t)

kmalloc() $B$d(B __get_free_pages(), alloc_pages(), alloc_page() $B$G$O!"(B gfp_t $B$N%U%i%0(B(gfp_mask) $B$H$7$F!" $B7?(B $B@bL@(B GFP_ATOMIC $B9bM%@hEY!#%9%j!<%WIT2D!#3d9~$_%O%s%I%i$d2J,(B(bottom half)$B$G;H$&!#(B GFP_NOIO $B%9%j!<%W2D!"F~=PNOIT2D!#(B GFP_NOFS $B%9%j!<%W2=!"F~=PNO2D!"%U%!%$%kA`:nIT2D!#%U%!%$%k%7%9%F%`$N$N%U%!%$%k%7%9%F%`$NA`:n$r3+;O$7$J$$(B)$B!#(B GFP_KERNEL $B%+!<%M%kMQ%a%b%jDL>o$NJ}K!!#%9%j!<%W2D!#%f!<%6!&%W%m%;%9$N%3%s%F%-%9%H$G;H$&!#(B GFP_USER $B%f!<%66u4VMQ$N%a%b%j$NDL>o$NJ}K!!#%9%j!<%W2D!#(B GFP_HIGHUSER HIGHMEM$B%>!<%s$+$i$N3dEv$F!#%9%j!<%W2D!#(B GFP_DMADMA$B%>!<%s$+$i$N3dEv$F!#%G%P%$%9!&%I%i%$%PEy$,;H$&!#(B $B$3$N$h$&$J%U%i%0$,B8:_$9$kI,MW@-!#(B

$B%9%j!<%W$9$k2DG=@-$,$"$k$+$J$$$+$,=EMW!#(B
$B%a%b%j$,3NJ]$G$-$J$$;~$K$O!"%Z!<%8%"%&%H$7$F3NJ]$9$k2DG=@-$,$"$k!#(B
$B%Z!<%8%"%&%H$K$O!"F~=PNO$,H<$&!#F~=PNOCf$O!"%W%m%;%9$O!"(B $B%9%j!<%W$9$k!J(Bblocked$B>uBV$K$J$k!K!#(B
$B3d$j9~$_%O%s%I%i!Jl=j$,$"$k!#(B
$BF~=PNO=hM}$N$?$a$K%a%b%j$,I,MW$K$J$C$F!"%a%b%j$r3NJ]$9$k$3$H$,$"$k!#(B
$B%a%b%j$,3NJ]$G$-$J$$;~$K$O!"%Z!<%8%"%&%H$7$F3NJ]$9$k2DG=@-$,$"$k!#(B
$B%Z!<%8%"%&%H$K$O!"F~=PNO$,H<$&!#(B
$BF~=PNO=hM}$N$?$a$K%a%b%j$,I,MW$K$J$C$F!"%a%b%j$r3NJ]$9$k$3$H$,$"$k!#(B
$B%a%b%j$,3NJ]$G$-$J$$;~$K$O!"%Z!<%8%"%&%H$7$F3NJ]$9$k2DG=@-$,$"$k!#(B
$B%Z!<%8%"%&%H$K$O!"F~=PNO$,H<$&!#(B
$BF~=PNO=hM}$N$?$a$K%a%b%j$,I,MW$K$J$C$F!"%a%b%j$r3NJ]$9$k$3$H$,$"$k!#(B
$B%a%b%j$,3NJ]$G$-$J$$;~$K$O!"%Z!<%8%"%&%H$7$F3NJ]$9$k2DG=@-$,$"$k!#(B
$B%Z!<%8%"%&%H$K$O!"F~=PNO$,H<$&!#(B
$B!&!&!&!#(B

$B"!(Bkfree()

void kfree(const void *objp)

C$B8@8l$N%f!<%66u4V$G;H$($k%i%$%V%i%j(B free() $B$H;w$F$$$k!#(B kmalloc() $B$G3d$jEv$F$?%a%b%j$r2rJ|$9$k!#(B

$B"!(Bvmalloc()$B$H(Bvfree()

kmallc()/kfree() $B$H;w$F$$$k$,!"3d$jEv$F$i$l$k%a%b%j$OJ*M}E*$KO"B3$7$F$$(B $B$kJ]>Z$O$J$$!#!J%+!<%M%k6u4V$N2>A[%"%I%l%9$H$7$F$OO"B3$7$F$$$k!#!K(B

$B"#%9%i%V%"%m%1!<%?(B(slab allocator)

$BF1$8Bg$-$5$N9=B$BN$r3d$jEv$F$k;~$K;H$&!#(B kmalloc(), kfree() $B$h$j$b!"8zN($,$h$$!#(B

$B"!(Bfree list$BJ}<0$H$=$NLdBjE@(B

$B9=B$BN$N3dEv$F$K$O!"(Bfree list $BJ}<0$,;H$o$l$k$3$H$b$"$k!#(B

$B9=B$BN$r3d$jEv$F$k;~$K$O!"(Bfree list $B$+$i free list $B$,6u$J$i!"9=B$BN$,J#?tF~$k$h$&$JBg$-$J%a%b%j(B($B%Z!<%8C10L(B)$B$r(B $B3dEv$F!"(Bfree list $B$K$D$J$0!#(B
$B9=B$BN$,;H$o$l$J$/$J$C$?$i!"(Bfree list $B$K$D$J$0!#(B

$B$3$NJ}K!$G$O!"%a%b%j$K6u$-$,$"$C$F$b!"2rJ|$G$-$k$+4JC1$K$O$o$+$i$J$$!#(B

$B?^(B? $B%U%j!<%j%9%H$NNc(B

$B%*%V%8%'%/%H$O!"(B1$B%Z!<%8$K(B2$B8DF~$k!#(B $B%*%V%8%'%/%H$,

object 2

object 6

object 3

object 1

$B?^(B? $B%U%j!<%j%9%H$NNc(B($B%Z!<%8$r0U<1(B)

object 2 $B$H(B object 3 $B$NItJ,$O!"(B1$B%Z!<%86u$$$F$$$k!#(B

$B"!%9%i%V!&%"%m%1!<%?$NL\I8(B

$B$h$/;H$o$l$k%*%V%8%'%/%H$O!"$9$0$K3+J|$5$l$k798~$K$"$k!#(B $B$=$N@- free list $B$G$O!"%a%b%j!&%U%i%0%a%s%F!<%7%g%s$,5/$-$k!#(B $B%9%i%V!&%"%m%1!<%?$G$O!"J#?t$NL$;HMQ$N%a%b%j$r$D$J$2$FBg$-$/$7$F!"(B $B3+J|$G$-$k!#(B
$B%-%c%C%7%e$O!"%^%k%A%W%m%;%C%5$G$O!"(BCPU $B$4$H$K3d$jEv$F$?$k$J$I$7$F!"(B $B%m%C%/$r8:$i$9!#(B
$B%*%V%8%'%/%H$,JL$N%-%c%C%7%e!&%i%$%s$K>h$k$h$&$K!"!V?'$r$D$1$k(B(colored)$B!W!#(B

$B%9%i%V!&%"%m%1!<%?<+?H$O!"(Balloc_pages() $BEy$N%Z!<%8C10L$N%a%b%j3dEv$F(B $B5!G=$r8F=P$7$F%a%b%j$r3NJ]$9$k!#(B

$B"!%Z!<%8!&%U%l!<%`!"%9%i%V!"%*%V%8%'%/%H$N4X78(B

$B?^(B? $B%Z!<%8!&%U%l!<%`!"%9%i%V!"%*%V%8%'%/%H$N4X78(B

$B%*%V%8%'%/%H$NBg$-$5(B($B9=B$BN$NBg$-$5(B)$B$O!"%W%m%0%i%_%s%0$NET9g$G7h$^$k!#(B $B%Z!<%8$NBg$-$5$H$OL54X78!#(B
$B#1$D$N%9%i%V$O!"%X%C%@$HJ#?t$N%*%V%8%'%/%H$+$i9=@.$5$l$k!#(B
$B>.$5$$%*%V%8%'%/%H$O!"(B1$B%9%i%V$,(B1$B$D$N%Z!<%8%U%l!<%`$K<}$^$k$h$&$K$9$k$3$H$,B?$$!#(B
$B#1$D$N%9%i%V$,!"J#?t$N%Z!<%8%U%l!<%`$K$^$?$,$k$3$H$b$"$k!#(B

$B"!(Bkmem_cache_create()

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *))

$B0z?t(B

name: $BJ8;zNs$NL>A0!#(B/proc/slabinfo $B$G;H$o$l$k!#(B
size: $B%*%V%8%'%/%H$N%5%$%:!#(B
align: $B%*%V%8%'%/%H$KI,MW$J%"%i%$%s%a%s%H!#(B
flags: $B%U%i%0!#(BSLAB_PANIC $B$,;XDj$5$l$k$H!"%a%b%j$N3dEv$F$K<:GT$9$l$P!"(B $B%7%9%F%`$,%/%i%C%7%e$9$k!#(BSLAB_CACHE_DMA $B$,;XDj$5$l$k$H!"(BZONE_DMA $B$N%a%b%j$K(B $B3d$jEv$F$i$l$k!#(B
ctor: $B%*%V%8%'%/%H$N%3%s%9%H%i%/%?!#?7$7$$%Z!<%8$,3d$jEv$F$i$l$kEY(B $B$K8F$P$l$k4X?t$X$N%]%$%s%?!#(B

$B7k2L(B: $B@.8y$7$?;~$K$O!"(Bstruct kmem_cache $B$X$N%]%$%s%?!#(B $B<:GT$9$k$H(BNULL$B!#?7$7$$%Z!<%8$,3d$jEv$F$i$l$?;~$K$O!"(Bctor $B$G(B $B;XDj$5$l$?4X?t$,8F$P$l$k!#(B

$B"!(Bkmem_cache_destroy()

void kmem_cache_destroy(struct kmem_cache *c)

kmem_cache_create() $B$G3d$jEv$F$?(B struct kmem_cache *$B$r3+J|$9$k!#(B shutdown ($BEE8;$r@Z$kA`:n(B)$B$G8F$P$l$k$3$H$,$"$k!#(B

$B"!(Bkmem_cache_alloc()$B$H(Bkmem_cache_free()

void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)

$B@8@.$7$?(B struct kmem_cache *$B$r;H$C$F%*%V%8%'%/%H$N%a%b%j$r3d$jEv$F$k!#(B $B3d$jEv$F$?%*%V%8%'%/%H$N%a%b%j$O!"(Bkmem_cache_free()$B$G3+J|$9$k!#(B

$B"!(B/proc/slabinfo

/proc/slabinfo $B$r8+$k$H!"%9%i%V%"%m%1!<%?$N>uBV$,$o$+$k!#(B

% cat /proc/slabinfo  
slabinfo - version: 2.0
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <batchcount> <limit> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
ip_conntrack_expect      0      0    256   15    1 : tunables  120   60    8 : slabdata      0      0      0
ip_conntrack          22     50    384   10    1 : tunables   54   27    8 : slabdata      5      5      0
nfs_direct_cache       0      0     68   58    1 : tunables  120   60    8 : slabdata      0      0      0
nfs_write_data        36     42    512    7    1 : tunables   54   27    8 : slabdata      6      6      0
...
task_struct           84    115   1408    5    2 : tunables   24   12    8 : slabdata     23     23      0
anon_vma             767   1130     16  226    1 : tunables  120   60    8 : slabdata      5      5      0
pgd                   54    238     32  119    1 : tunables  120   60    8 : slabdata      2      2      0
pmd                  123    123   4096    1    1 : tunables   24   12    8 : slabdata    123    123      0
size-131072(DMA)       0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-131072            0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-65536(DMA)        0      0  65536    1   16 : tunables    8    4    0 : slabdata      0      0      0
size-65536             2      2  65536    1   16 : tunables    8    4    0 : slabdata      2      2      0
...
size-32             8314   8925     32  119    1 : tunables  120   60    8 : slabdata     75     75      0
kmem_cache           150    150    256   15    1 : tunables  120   60    8 : slabdata     10     10      0
%

$B%9%i%V!&%"%m%1!<%?$K$O!"#2

$B@lMQ!#$?$H$($P!"(Btask_struct $B$J$i!"(Bsizeof(struct task_struct) $B$H$7$F%-%c%C%7%e$KJ]B8!#(B $BA0H>$KI=<($5$l$k!#(B

$BHFMQ!#$$$/$D$+$NBg$-$5$N%a%b%j!#(B32$B!"(B64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072$B!#(B $B8eH>$N(B size-$BHV9f(B $B!#(B DMA $B$,IU$$$F$$$k$b$N$O!"(BDMA $B2DG=$J%a%b%j!#(B

$B"!MxMQNc(B(task_struct)

kernel/fork.c
 112:	static struct kmem_cache *task_struct_cachep;
...
 202:	void __init fork_init(unsigned long mempages)
 203:	{
...
 206:	#define ARCH_MIN_TASKALIGN      L1_CACHE_BYTES
...
 209:	        task_struct_cachep =
 210:	                kmem_cache_create("task_struct", sizeof(struct task_struct),
 211:	                        ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);
...
 110:	# define alloc_task_struct()    kmem_cache_alloc(task_struct_cachep, GFP_KERNEL)
 111:	# define free_task_struct(tsk)  kmem_cache_free(task_struct_cachep, (tsk))

L1_CACHE_BYTES $B$G!"9=B$BN$NHVCO$r>/$7$:$D$:$i$7$J$,$i!"%-%c%C%7%e(B $B$N%i%$%s$,$V$D$+$i$J$$$h$&$K$9$k!#(B
SLAB_PANIC $B$K$h$j!"%a%b%j$,3d$jEv$F$i$l$J$1$l$P!"(Bpanic ($B%7%9%F%`A4(B $BBN$r%/%i%C%7%e(B)$B$9$k!#(B
$B%3%s%9%H%i%/%?$O!"$J$7!#(B

$B"!(Bstruct slab

mm/slab.c
 200:	struct slab {
 201:	        struct list_head list;
 202:	        unsigned long colouroff;
 203:	        void *s_mem;            /* including colour offset */
 204:	        unsigned int inuse;     /* num of objs active in slab */
 205:	        kmem_bufctl_t free;
...
 207:	};

list: $B%9%i%V$N%j%9%H$r:n$k!#(B
colouroff: $B!V?'!W$N%*%U%;%C%H!#(B
s_mem: $B%9%i%V$N:G=i$N%*%V%8%'%/%H$X$N%]%$%s%?!#(B
inuse: $B%9%i%VCf$NMxMQ$5$l$F$$$k%*%V%8%'%/%H$N?t!#(B
free: $BG[Ns$O!"%9%i%V$N6u$-$r4IM}$9$kG[Ns$NE:;z(B($B:G=i$NMxMQ2DG=$J%*(B $B%V%8%'%/%H$NE:;z(B)$B$rJ];}$9$k!#(B

$B?^(B? $B%Z!<%8!&%U%l!<%`!"%9%i%V!"%*%V%8%'%/%H$N4X78(B

$B"!(Bkmem_list3

mm/slab.c
 269:	struct kmem_list3 {
 270:	        struct list_head slabs_partial; /* partial list first, better asm code */
 271:	        struct list_head slabs_full;
 272:	        struct list_head slabs_free;
...
 281:	};

$B%9%i%V$NJ,N`(B

$BItJ,E*$KMxMQ(B(slabs_partial)
$BA4ItMxMQ(B(slabs_full)
$BA4It6u$-(B(slabs_free)

$B?^(B? $B%9%i%V$N%j%9%H(B

$B6u$-$J$/$J$k$H!"(B__get_free_pages() $B$G(BBuddy$B%7%9%F%`$+$i $BA4It6u$-$,!"$"$k$7$-$$CM0J>e$KA}$($k$H!"(Bfree_pages() $B$G(BBuddy$B%7%9%F%`$KJV5Q$9$k!#(B

$B"#%/%$%:(B4 $B%a%b%j4IM}!"(BBuddy$B%7%9%F%`!"(Bkmalloc$B!"%9%i%V%"%m%1!<%?(B

$B!zLdBj(B(401) struct page

struct page$B$NBg$-$5$O!"%"!<%-%F%/%A%c$d%3%s%Q%$%k;~$N%*%W%7%g%s$K$h$C$F(B $B0[$J$k!#$"$k%7%9%F%`$G!"(Bstruct page$B$NBg$-$5$,(B 40 $B%P%$%H$G$"$C$?$H$9$k!#(B $B$=$N%7%9%F%`$K!"(B1GB $B$N%a%b%j$,Ek:\$5$l$F$$$?;~!"(Bstruct page$B$N$?$a$K!"2?(B MB$B$N%a%b%j$,;H$o$l$k$+!#%Z!<%8%5%$%:$O!"(B4KB$B$H$9$k!#(B

$B!zLdBj(B(402) Buddy$B%7%9%F%`(B

$B?^(B1 Buddy$B%7%9%F%`$K$h$k6u$-%Z!<%8$N4IM}(B $B

1$B%Z!<%8$N3NJ](B

$B!zLdBj(B(403) kmalloc()$B$H(Bkfree()

$B0J2<$O!"%f!<%66u4V$G%a%b%j$r3dEv$F!"MxMQ$7!"3+J|$9$k%W%m%0%i%`$N0lIt$G$"$k!#(B

   struct s1 *p;
   p = malloc( sizeof(struct s1) );
   use( p );
   free( p );

$B$3$N%W%m%0%i%`$r!"%+!<%M%kFb$GF0$+$9$3$H$rA[Dj$7$F(Bkmalloc() $B$H(B kfree() $B$r;H$C$F=q$-49$($J$5$$!#$?$@$7!"(Bgfp $B$N%U%i%0$H$7$F$O!"(BGFP_KERNEL $B$r;H$$$J$5$$!#(B

$BMxMQ(B
   struct s1 *p;
   /*$B2sEz(B*/
   use( p );
   /*$B2sEz(B*/

$B!zLdBj(B(404) $B%9%i%V%"%m%1!<%?(B

$BLdBj(B(403) $B$N%W%m%0%i%`$r!"%9%i%V%"%m%1!<%?$r;H$C$F=q$-49(B $B$($J$5$$!#$9$J$o$A!"(Bkmem_cache_create()$B!"(Bkmem_cache_alloc()$B!"$*$h$S!"(B kmem_cache_free()$B$r;H$C$F=q$-49$($J$5$$!#$?$@$7!"(Bkmem_cache_create() $B$N(B $BBh(B3$B0z?t$N(Balign $B$H$7$F$O!"(B0$B$r!"Bh(B4$B0z?t$N(Bflags$B$H$7$F$O!"(BSLAB_PANIC$B!"Bh(B5$B0z(B $B?t$N%3%s%9%H%i%/%?$H$7$F$O!"(BNULL $B$r;XDj$7$J$5$$!#(B

$B=i4|2=(B
   /*$B2sEz(B*/

$BMxMQ(B
   struct s1 *p;
   /*$B2sEz(B*/
   use( p );
   /*$B2sEz(B*/

Last updated: 2011/01/11 14:19:55

Yasushi Shinjo / <yas@is.tsukuba.ac.jp>