slab.ps

来自「这是一个介绍 linux 编程知识的文章。」· PS 代码 · 共 1,690 行 · 第 1/5 页

(other allocators [Knuth68, Korn85, Standish80].)4 1966 1 590 2982 t
10 B f
( freeing memory are fast,)4 1287(\(2\) Allocating and)2 873 2 590 3144 t
(constant-time operations.)1 1114 1 590 3264 t
10 R f
(All we have to do is)5 957 1 1793 3264 t
(move an object to or from a freelist and update a)10 2160 1 590 3384 t
(reference count.)1 649 1 590 3504 t
10 B f
( external fragmentation \(unused)3 1647(\(3\) Severe)1 513 2 590 3666 t
( unlikely.)1 430(buffers on the freelist\) is)4 1177 2 590 3786 t
10 R f
(Over time,)1 461 1 2289 3786 t
( small,)1 289(many allocators develop an accumulation of)5 1871 2 590 3906 t
( occurs as the allocator splits)5 1211( This)1 249(unusable buffers.)1 700 3 590 4026 t
( For)1 208( to satisfy smaller requests.)4 1129(existing free buffers)2 823 3 590 4146 t
( 32-byte and 40-byte)3 874(example, the right sequence of)4 1286 2 590 4266 t
( result in a large accumulation of)6 1500(allocations may)1 660 2 590 4386 t
( \320 even though no 8-byte buffers)6 1401(free 8-byte buffers)2 759 2 590 4506 t
( segregated-)1 537( A)1 182(are ever requested [Standish80].)3 1441 3 590 4626 t
( cannot suffer this fate, since the)6 1468(storage allocator)1 692 2 590 4746 t
(only way to populate its 8-byte freelist is to actually)9 2160 1 590 4866 t
( sequence of)2 544( Any)1 253( free 8-byte buffers.)3 860(allocate and)1 503 4 590 4986 t
( no matter how)3 677(32-byte and 40-byte allocations \320)4 1483 2 590 5106 t
( can only result in population of the 32-)8 1678(complex \320)1 482 2 590 5226 t
( is)1 109( prior allocation)2 670( Since)1 296(byte and 40-byte freelists.)3 1085 4 590 5346 t
( of future allocation [Weinstock88])4 1472(a good predictor)2 688 2 590 5466 t
(these buffers are likely to be used again.)7 1663 1 590 5586 t
( fragmen-)1 400(The other reason that slabs reduce external)6 1760 2 590 5748 t
( that all objects in a slab are of the same)10 1817(tation is)1 343 2 590 5868 t
( same lifetime distribution.*)3 1200(type, so they have the)4 960 2 590 5988 t
(The resulting segregation of short-lived and long-)6 2160 1 590 6108 t
( slab granularity reduces the likeli-)5 1509(lived objects at)2 651 2 590 6228 t
( page being held hostage due to a)7 1433(hood of an entire)3 727 2 590 6348 t
(single long-lived allocation [Barrett93, Hanson90].)4 2074 1 590 6468 t
8 S1 f
(____________________________________)590 6564 w
8 R f
(* The generic caches that back)5 1087 1 806 6684 t
8 CW f
(kmem_alloc\(\))1957 6684 w
8 R f
(are a)1 174 1 2576 6684 t
( but they constitute a relatively small fraction)7 1559(notable exception,)1 601 2 590 6780 t
( \320 all of the major consumers of)7 1221(of the arena in SunOS 5.4)5 939 2 590 6876 t
(memory now use)2 561 1 590 6972 t
8 CW f
(kmem_cache_alloc\(\))1199 6972 w
8 R f
(.)2063 6972 w
10 B f
( \(per-buffer wasted)2 928(\(4\) Internal fragmentation)2 1232 2 3110 696 t
( minimal.)1 419(space\) is)1 372 2 3110 816 t
10 R f
(Each buffer is exactly the right)5 1298 1 3972 816 t
( so the only)3 536(size \(namely, the cache's object size\),)5 1624 2 3110 936 t
( of the)2 275(wasted space is the unused portion at the end)8 1885 2 3110 1056 t
( example, assuming 4096-byte pages, the)5 1755(slab. For)1 405 2 3110 1176 t
( contain)1 329(slabs in a 400-byte object cache would each)7 1831 2 3110 1296 t
( can view)2 428( We)1 219(10 buffers, with 96 bytes left over.)6 1513 3 3110 1416 t
(this as equivalent 9.6 bytes of wasted space per)8 2160 1 3110 1536 t
(400-byte buffer, or 2.4% internal fragmentation.)5 1969 1 3110 1656 t
( contains)1 390(In general, if a slab)4 891 2 3110 1818 t
10 I f
(n)4448 1818 w
10 R f
(buffers, then the)2 715 1 4555 1818 t
(internal fragmentation is at most 1/)5 1487 1 3110 1938 t
10 I f
(n)4597 1938 w
10 R f
(; thus the allo-)3 623 1 4647 1938 t
( internal)1 365(cator can actually control the amount of)6 1795 2 3110 2058 t
( How-)1 316( the slab size.)3 631(fragmentation by controlling)2 1213 3 3110 2178 t
( are more likely to cause external)6 1444(ever, larger slabs)2 716 2 3110 2298 t
( the probability of being able to)6 1332(fragmentation, since)1 828 2 3110 2418 t
(reclaim a slab decreases as the number of buffers)8 2160 1 3110 2538 t
( implementation)1 670( SunOS 5.4)2 495( The)1 231(per slab increases.)2 764 4 3110 2658 t
(limits internal fragmentation to 12.5% \(1/8\), since)6 2160 1 3110 2778 t
( empirical sweet-spot in the)4 1148(this was found to be the)5 1012 2 3110 2898 t
( and external fragmenta-)3 1067(trade-off between internal)2 1093 2 3110 3018 t
(tion.)3110 3138 w
11 B f
( Layout \320 Logical)3 904(3.2.1. Slab)1 531 2 3110 3438 t
10 R f
( slab are managed by a)5 1176(The contents of each)3 984 2 3110 3600 t
10 CW f
(kmem_slab)3110 3720 w
10 R f
(data structure that maintains the slab's)5 1584 1 3686 3720 t
(linkage in the cache, its reference count, and its list)9 2160 1 3110 3840 t
( turn, each buffer in the slab is)7 1361( In)1 162( buffers.)1 353(of free)1 284 4 3110 3960 t
(managed by a)2 588 1 3110 4080 t
10 CW f
(kmem_bufctl)3767 4080 w
10 R f
( holds)1 260(structure that)1 541 2 4469 4080 t
( and a back-)3 607(the freelist linkage, buffer address,)4 1553 2 3110 4200 t
( slab)1 215( a)1 97( Pictorially,)1 528(pointer to the controlling slab.)4 1320 4 3110 4320 t
( this \(bufctl-to-slab back-pointers not)4 1711(looks like)1 449 2 3110 4440 t
(shown\):)3110 4560 w
(one or more pages)3 758 1 3811 6746 t
3110 6666 3182 6648 Dl
3110 6666 3182 6684 Dl
5270 6666 3110 6666 Dl
5270 6666 5198 6684 Dl
5270 6666 5198 6648 Dl
(buf)3368 6326 w
3110 6162 3110 6450 Dl
3758 6162 3110 6162 Dl
3758 6450 3758 6162 Dl
3110 6450 3758 6450 Dl
(buf)4016 6326 w
3758 6162 3758 6450 Dl
4406 6162 3758 6162 Dl
4406 6450 4406 6162 Dl
3758 6450 4406 6450 Dl
(buf)4664 6326 w
4406 6162 4406 6450 Dl
5054 6162 4406 6162 Dl
5054 6450 5054 6162 Dl
4406 6450 5054 6450 Dl
(un-)5096 6266 w
(used)5071 6386 w
5054 6162 5054 6450 Dl
5270 6162 5054 6162 Dl
5270 6450 5270 6162 Dl
5054 6450 5270 6450 Dl
(kmem)3201 5546 w
(bufctl)3210 5666 w
3110 5442 3110 5730 Dl
3542 5442 3110 5442 Dl
3542 5730 3542 5442 Dl
3110 5730 3542 5730 Dl
(kmem)3849 5546 w
(bufctl)3858 5666 w
3758 5442 3758 5730 Dl
4190 5442 3758 5442 Dl
4190 5730 4190 5442 Dl
3758 5730 4190 5730 Dl
(kmem)4497 5546 w
(bufctl)4506 5666 w
4406 5442 4406 5730 Dl
4838 5442 4406 5442 Dl
4838 5730 4838 5442 Dl
4406 5730 4838 5730 Dl
(kmem)4065 4826 w
(slab)4110 4946 w
3974 4722 3974 5010 Dl
4406 4722 3974 4722 Dl
4406 5010 4406 4722 Dl
3974 5010 4406 5010 Dl
(next slab in cache)3 736 1 4470 4754 t
5270 4794 4406 4794 Dl
5270 4794 5198 4812 Dl
5270 4794 5198 4776 Dl
4406 4938 5270 4938 Dl
4406 4938 4478 4920 Dl
4406 4938 4478 4956 Dl
(prev slab in cache)3 741 1 3172 5018 t
3110 4938 3974 4938 Dl
3110 4938 3182 4920 Dl
3110 4938 3182 4956 Dl
3974 4794 3110 4794 Dl
3974 4794 3902 4812 Dl
3974 4794 3902 4776 Dl
3110 6162 3326 5730 Dl
3110 6161 3125 6089 Dl
3110 6161 3158 6105 Dl
3758 6162 3974 5730 Dl
3758 6161 3773 6089 Dl
3758 6161 3806 6105 Dl
4406 6162 4622 5730 Dl
4406 6161 4421 6089 Dl
4406 6161 4454 6105 Dl
3758 5586 3542 5586 Dl
3758 5586 3686 5604 Dl
3758 5586 3686 5568 Dl
4406 5586 4190 5586 Dl
4406 5586 4334 5604 Dl
4406 5586 4334 5568 Dl
3326 5442 4046 5010 Dl
3326 5441 3378 5389 Dl
3326 5441 3397 5420 Dl
4622 5442 4334 5010 Dl
4621 5441 4567 5392 Dl
4621 5441 4596 5372 Dl
cleartomark
showpage
restore
%%EndPage: 5 5
%%Page: 6 6
save
mark
6 pagesetup
11 B f
( Layout for Small Objects)4 1249(3.2.2. Slab)1 531 2 590 696 t
10 R f
( slab is)2 336(For objects smaller than 1/8 of a page, a)8 1824 2 590 858 t
( the slab data at)4 701(built by allocating a page, placing)5 1459 2 590 978 t
( dividing the rest into equal-size)5 1565(the end, and)2 595 2 590 1098 t
(buffers:)590 1218 w
(one page)1 365 1 1488 1892 t
590 1812 662 1794 Dl
590 1812 662 1830 Dl
2750 1812 590 1812 Dl
2750 1812 2678 1830 Dl
2750 1812 2678 1794 Dl
(buf)689 1544 w
590 1380 590 1668 Dl
921 1380 590 1380 Dl
921 1668 921 1380 Dl
590 1668 921 1668 Dl
(buf)1020 1544 w
921 1380 921 1668 Dl
1252 1380 921 1380 Dl
1252 1668 1252 1380 Dl
921 1668 1252 1668 Dl
(...)1381 1544 w
1252 1380 1252 1668 Dl
1583 1380 1252 1380 Dl
1583 1668 1583 1380 Dl
1252 1668 1583 1668 Dl
(buf)1683 1544 w
1583 1380 1583 1668 Dl
1914 1380 1583 1380 Dl
1914 1668 1914 1380 Dl
1583 1668 1914 1668 Dl
(buf)2014 1544 w
1914 1380 1914 1668 Dl
2245 1380 1914 1380 Dl
2246 1668 2246 1380 Dl
1915 1668 2246 1668 Dl
(un-)2288 1484 w
(used)2263 1604 w
2246 1380 2246 1668 Dl
2462 1380 2246 1380 Dl
2462 1668 2462 1380 Dl
2246 1668 2462 1668 Dl
(kmem)2481 1484 w
(slab)2526 1604 w
2462 1380 2462 1668 Dl
2750 1380 2462 1380 Dl
2750 1668 2750 1380 Dl
2462 1668 2750 1668 Dl
( the)1 172(Each buffer serves as its own bufctl while on)8 1988 2 590 2118 t
( since)1 249( the linkage is actually needed,)5 1331(freelist. Only)1 580 3 590 2238 t
( are essential)2 561( These)1 318(everything else is computable.)3 1281 3 590 2358 t
(optimizations for small buffers \320 otherwise we)6 2160 1 590 2478 t
( as much memory)3 797(would end up allocating almost)4 1363 2 590 2598 t
(for bufctls as for the buffers themselves.)6 1658 1 590 2718 t
( the)1 168(The freelist linkage resides at)4 1255 2 840 2880 t
10 I f
(end)2309 2880 w
10 R f
(of the)1 251 1 2499 2880 t
( debug-)1 310(buffer, rather than the beginning, to facilitate)6 1850 2 590 3000 t
( empirical observation)2 947( is driven by the)4 748(ging. This)1 465 3 590 3120 t
( structure is typically)3 925(that the beginning of a data)5 1235 2 590 3240 t
( a buffer is modi\256ed)4 910( If)1 148(more active than the end.)4 1102 3 590 3360 t
( is easier to diagnose)4 900(after being freed, the problem)4 1260 2 590 3480 t
(if the heap)2 437 1 590 3600 t
10 I f
(structure)1060 3600 w
10 R f
(\(freelist linkage\) is still intact.)4 1234 1 1454 3600 t
( for)1 161(The allocator reserves an additional word)5 1749 2 840 3762 t
(constructed objects so that the linkage doesn't)6 2160 1 590 3882 t
(overwrite any constructed state.)3 1293 1 590 4002 t
11 B f
( Layout for Large Objects)4 1259(3.2.3. Slab)1 531 2 590 4302 t
10 R f
( but)1 167(The above scheme is ef\256cient for small objects,)7 1993 2 590 4464 t
( could \256t only)3 610( It)1 136( ones.)1 250(not for large)2 529 4 590 4584 t
10 I f
(one)2157 4584 w
10 R f
(2K buffer)1 407 1 2343 4584 t
( data.)1 239(on a 4K page because of the embedded slab)8 1921 2 590 4704 t
( large \(multi-page\) slabs we lose the)6 1525(Moreover, with)1 635 2 590 4824 t
( address from the)3 753(ability to determine the slab data)5 1407 2 590 4944 t
( large objects the)3 814( for)1 187( Therefore,)1 521(buffer address.)1 638 4 590 5064 t
( is identical to the logical layout.)6 1518(physical layout)1 642 2 590 5184 t
( slab and bufctl data structures come)6 1620(The required)1 540 2 590 5304 t
( per-cache)1 426( A)1 145( caches.)1 330(from their own \(small-object!\))3 1259 4 590 5424 t
( buffer-to-bufctl)1 709(self-scaling hash table provides)3 1451 2 590 5544 t
(conversion.)590 5664 w
11 B f
( Management)1 651(3.3. Freelist)1 590 2 590 5964 t
10 R f
( list)1 172(Each cache maintains a circular, doubly-linked)5 1988 2 590 6126 t
( sorted, in)2 433( slab list is partially)4 860( The)1 232(of all its slabs.)3 635 4 590 6246 t
( come)1 276(that the empty slabs \(all buffers allocated\))6 1884 2 590 6366 t
( by the partial slabs \(some buffers)6 1563(\256rst, followed)1 597 2 590 6486 t
( and \256nally the complete slabs)5 1278(allocated, some free\),)2 882 2 590 6606 t
( freelist)1 320( cache's)1 342( The)1 232(\(all buffers free, refcnt == 0\).)5 1266 4 590 6726 t
( slab,)1 220( Each)1 266(pointer points to its \256rst non-empty slab.)6 1674 3 590 6846 t
( of available buffers.)3 924(in turn, has its own freelist)5 1236 2 590 6966 t
( memory)1 385(This two-level freelist structure simpli\256es)4 1775 2 590 7086 t
( reclaims a slab it)4 807( the allocator)2 577(reclaiming. When)1 776 3 3110 696 t
( cache's)1 337(doesn't have to unlink each buffer from the)7 1823 2 3110 816 t
(freelist \320 it just unlinks the slab.)6 1379 1 3110 936 t
11 B f
( Memory)1 436(3.4. Reclaiming)1 769 2 3110 1236 t
10 R f
(When)3110 1398 w
10 CW f
(kmem_cache_free\(\))3430 1398 w
10 R f
( slab)1 217(sees that the)2 548 2 4505 1398 t
( not immediately)2 752(reference count is zero, it does)5 1408 2 3110 1518 t
( the slab)2 357( it just moves)3 570( Instead,)1 382(reclaim the memory.)2 851 4 3110 1638 t
( all the complete)3 759(to the tail of the freelist where)6 1401 2 3110 1758 t
( that no complete slab)4 1013( ensures)1 357( This)1 269(slabs reside.)1 521 4 3110 1878 t
( broken up unless all partial slabs have been)8 1870(will be)1 290 2 3110 1998 t
(depleted.)3110 2118 w
( asks)1 209(When the system runs low on memory it)7 1701 2 3360 2280 t
( as much memory as it can.)6 1186(the allocator to liberate)3 974 2 3110 2400 t
( retains a 15-second work-)4 1106(The allocator obliges, but)3 1054 2 3110 2520 t
( prevent thrashing.)2 788(ing set of recently-used slabs to)5 1372 2 3110 2640 t
( that system performance is)4 1210(Measurements indicate)1 950 2 3110 2760 t
(fairly insensitive to the slab working-set interval.)6 2160 1 3110 2880 t
( extremes \320)2 584(Presumably this is because the two)5 1576 2 3110 3000 t
( on)1 163(zero working set \(reclaim all complete slabs)6 1997 2 3110 3120 t
( working-set \(never reclaim)3 1243(demand\) and in\256nite)2 917 2 3110 3240 t
( are both reasonable, albeit suboptimal,)5 1637(anything\) \320)1 523 2 3110 3360 t
(policies.)3110 3480 w
11 B f
( Cache Effects)2 685(4. Hardware)1 636 2 3110 3780 t
10 R f
( utilization,)1 482(Modern hardware relies on good cache)5 1678 2 3110 3942 t
( is important to design software with cache)7 1955(so it)1 205 2 3110 4062 t
( a memory allocator there are)5 1276( For)1 218(effects in mind.)2 666 3 3110 4182 t
( consider: the)2 578(two broad classes of cache effects to)6 1582 2 3110 4302 t
( the cache foot-)3 674(distribution of buffer addresses and)4 1486 2 3110 4422 t
( latter topic has)3 712( The)1 246( allocator itself.)2 690(print of the)2 512 4 3110 4542 t
( Grunwald93B],)1 692(received some attention [Chen93,)3 1468 2 3110 4662 t
( cache)1 259(but the effect of buffer address distribution on)7 1901 2 3110 4782 t