ࡱ;   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry  !"#$%&'()*+-./023456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmno ®`VTextStarWriter 5.0q{:k SfxDocumentInfo Mike |1Mike |1@ȰMike |1 Info 0 Info 1 Info 2 Info 3 |1 <44Standard LIBIMBEDDED LIBIMBEDDED TASK,0,1,H32,0,100,1,2368;426126;110;0;422394;14971;430699;0;0SW5HDR.0|1@Ȱ!Outline0 #ZSBX sb Z Standard StarBASICSBX ARSBX AR SBX AR2c%bqqOSWG, A<  #$%&'()*./0123456789:;<=>?@ABCDGHK  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFQRSTU0R'&@ TimesNewRomanX'@d X' @X'(!@. !. XA'2*@'dxdxdxdXXJJ@NX@dPM' TimesNewRoman$' '(. . p. @ . . . . . P. . . !. $. `'. 0*. -. /. 2. p5. @8. ;. =. @. 6')(02 StandardStandard@ Text bodyStandard Text body2A'List Text bodyList'CaptionStandardCaption'' '2A'JJIndexStandardIndex'JJ FooterStandardFooter@('JJ<|?Oh+'0 h t 32@;G@0ڔ@N(@⹘Mike Mike SW5HDR.0|1@Ȱ! Frameformat ZeichenformatTextformatvorlageStandard Text bodyListCaption IndexFooterRoot 10Standard  Illustration Table TextDrawingY  .Y  .Y  .Y .q= GeneralGeneraldNC#,###.00#,###.00SystemNC #,##0.00 CCC#,##0.00 CCCNC$#,##0.--;[RED]-$#,##0.-- $#,##0.---$#,##0.--REDNC$ MM/DD/YYYYMM/DD/YYYY def/SystemNC%MM/DD/YYMM/DD/YY def/SystemNC&NNNNMMMM DD, YYYYNNNNMMMM  DD, YYYYSystemNC' MMM D, YYMMM D, YY def/SystemNC. [HH]:MM:SS.00 [HH ]:MM:SS .00NC3MM/DD/YYYY HH:MM:SS MM/DD/YYYY HH :MM:SS  NCK MMM D, YYYYMMM D, YYYY def/SystemNCL MMMM D, YYYYMMMM  D, YYYY def/SystemNCM NN, MMM D, YYNN, MMM D, YY def/SystemNCNNN, MMMM D, YYYYNN, MMMM  D, YYYY def/SystemNCONNNNMMMM D, YYYYNNNNMMMM  D, YYYY def/SystemNCP D. MMM. YYYYD. MMM. YYYYDIN 5008 (EN 28601)NCQ D. MMMM YYYYD. MMMM  YYYYDIN 5008 (EN 28601)NCRMM-DDMM-DDDIN 5008 (EN 28601)NCSYY-MM-DDYY-MM-DDDIN 5008 (EN 28601)NCT YYYY-MM-DDYYYY-MM-DDDIN 5008 (EN 28601)NCUWWWWNCBXoeP<p5 2$99 SAP/=APd(ddAPddA PAu Prk FooterSYAPddADPN;T2SA @A0SAAP/=APd(ddAPddZSW5HDR.0|1@ȰC(569a(Build:5169)(SV569)]D!Address Book Fileaddress! Frameformat ZeichenformatTextformatvorlageStandard Text bodyListCaption IndexFooterRoot 10Standard  Illustration Table TextDrawingd"$1 4 5*jK standard.dic soffice.dicZsun.dic@ IgnoreAllListY  .Y  .Y  .Y .6NhT5Memory ManagementSA A @T$SA A @T6Intel x86 hardwareSA A @T$SA A @T]!Supports segmentation over pagingS1APdddA A @T<S1APdddA A @TK(segid, offset)S1APdddA A @TZ| <- segmentation hardwareS'APdddA @A8TJlinear addressS1APdddA A @TP| <- paging hardwareS1APdddA A @TLphysical addressS1APdddA A @T<S1APdddA A @TRSegment id is implicitly or explicitly associated with a Segment Selector registerS1APdddA A @T<S1APdddA A @Tm-CS -code segment (default for fetch accesses)S'APdddA @A8Tr6DS -data segment (default for non-stack data accesses)S1APdddA A @Tz>SS - stack segment (default for stack ops (push/pop/call/ret))S1APdddA A @Tz>ES - extra segment used by default in memory to memory copies S1APdddA A @Te)FS - extra segments never used by defaultS1APdddA A @T>GSS1APdddA A @T<S1APdddA A @Te)Segment selector registers are 16 bits. S1APdddA A @T<S1APdddA A @To3High order 13 bits provide segment descriptor indexS1APdddA A @TWTI bit indicates GDT or LDTS1APdddA A @THLow order two bits contain RPL / CPL (request / current) privilege levelS1APdddA A @T<S1APdddA A @TGActual attributes of a segment are contained in the segment descriptor S1APdddA A @A8 4FA8 FGTFS;APdddA  A A @Tw1Segment descriptors are 64 bits (8 bytes in size)S;APdddA  A A @TBReside in Global or Local descriptor tables of up to 8192 entries S;APdddA  A A @Tr,Entry 0 always represents an invalid segmentS;APdddA  A A @TFS;APdddA  A A @TaSegment descriptors containS;APdddA  A A @TFS;APdddA  A A @T032 bit base virtual or linear address of segmentS;APdddA  A A @A8  Ts-20 bit size of the segment in bytes or pages S;APdddA  A A @Tj.G (granularity) flag specifies bytes or pagesS1APdddA A @TKS (system) flagS1APdddA A @TK4 bit type flagS1APdddA A @T@dataS1APdddA A @T@codeS1APdddA A @T?TSSS1APdddA A @T?LDTS1APdddA A @T<S1APdddA A @TKSelector registers have an "invisible" extension that holds descriptor dataS;APdddA PA A @T<S1APdddA A @T~>Validity checking is done when the selector register is loadedS'APdddA @A8>TFMain Memory need not be accessed again to refer to segment attributes S1APdddA A @T<S1APdddA A @TQSegmentation in LinuxS1APdddA A @T<S1APdddA A @Td(Linux makes minimal use of segmentationS1APdddA A @TJNo LDT is usedS1APdddA A @TLGDT is as shown.S1APdddA A @T<S1APdddA A @TW6 /*SHAPdddACourierA A @Ty&7 * The layout of the GDT under Linux:SHAPdddACourierA A @TV8 *SHAPdddACourierA A @Ta9 * 0 - nullSHAPdddACourierA A @Tf10 * 1 - not usedSHAPdddACourierA A @Tq11 * 2 - kernel code segmentSHAPdddACourierA A @Tq12 * 3 - kernel data segmentSHAPdddACourierA A @T413 * 4 - user code segment <-- new cacheline SHAPdddACourierA A @To14 * 5 - user data segmentSHAPdddACourierA A @Tf15 * 6 - not usedSHAPdddACourierA A @Tf16 * 7 - not usedSHAPdddACourierA A @T417 * 8 - APM BIOS support <-- new cacheline SHAPdddACourierA A @Tn18 * 9 - APM BIOS supportSHAPdddACourierA A @Tn19 * 10 - APM BIOS supportSHAPdddACourierA A @Tn20 * 11 - APM BIOS supportSHAPdddACourierA A @TW21 *SHAPdddACourierA A @T922 * The TSS+LDT descriptors are spread so that every CPUSHAPdddACourierA A @T<23 * has an exclusive cacheline for the per-CPU TSS and LDT:SHAPdddACourierA A @TW24 *SHAPdddACourierA A @T425 * 12 - CPU#0 TSS <-- new cacheline SHAPdddACourierA A @Tg26 * 13 - CPU#0 LDTSHAPdddACourierA A @Tg27 * 14 - not used SHAPdddACourierA A @Tg28 * 15 - not used SHAPdddACourierA A @T429 * 16 - CPU#1 TSS <-- new cacheline SHAPdddACourierA A @Tg30 * 17 - CPU#1 LDTSHAPdddACourierA A @Tg31 * 18 - not used SHAPdddACourierA A @Tg32 * 19 - not used SHAPdddACourierA A @T-33 * ... NR_CPUS per-CPU TSS+LDT's if on SMPSHAPdddACourierA A @T<S1APdddA A @T]SRAPdddA PACourierA A @TQDescriptor attributesS1APdddA A @T<S1APdddA A @T]!Kernel and user code and data useS1APdddA A @T<S1APdddA A @TLBase = 0x0000000S1APdddA A @TKLimit = 0xfffffS1APdddA A @TSG = 1 (page size units)S1APdddA A @TTD/B = 1 (32 bit offsets)S1APdddA A @T<S1APdddA A @TUKernel and user code use S1APdddA A @T<S1APdddA A @TWtype = 0x0a (readable code)S1APdddA A @T<S1APdddA A @TUKernel and user data use S1APdddA A @T<S1APdddA A @TG type = 0x02S1APdddA A @T<S1APdddA A @TG Kernel usesS1APdddA A @TAS = 1S1APdddA A @TCDPL = 0S1APdddA A @T<S1APdddA A @TE User usesS1APdddA A @TAS = 0S1APdddA A @TCDPL = 3S1APdddA A @T<S1APdddA A @TDBook refers to TSS per process.. this was discontinued in kernel 2.4S1APdddA A @T<S1APdddA A @TFS;APdddA PA A @TLIntel x86 PagingS1APdddA A @T<S1APdddA A @TdPages are 4K bytes in sizeS1APdddA A @A8T<S1APdddA A @Tg+Linear (virtual addresses) are 32 bits longS1APdddA A @Th10 bits - Page directory indexS1APdddA A @A8Td10 bits - Page table indexS1APdddA A @A8Td12 bits - Offset into pageS1APdddA A @A8T<S1APdddA A @Tj Page table and directory entriesS1APdddA A @A8 T<S1APdddA A @TD20 bits - page frame address (20 bits used since frames are aligned)S1APdddA A @A8DTbP flag - is page presentS1APdddA A @A8Tj A flag - has paged been accessedS1APdddA A @A8 ThD flag - has page been writtenS1APdddA A @A8TcR flag - page is readonlyS1APdddA A @A8T=U flag - user mode page (U = 0 -> access by PL 3 is verboten)S1APdddA A @A8=Ts)S flag - pages may be 4K or 4 MB in size S1APdddA A @A8(T<S1APdddA A @TZPCD - disable hardware cachingS1APdddA A @Ti-PWT - use write through instead of copy back.S1APdddA A @Tn2(both default to 0.. but can be reset as required)S1APpdddpA A @T<S1APpdddpA A @T<S1APdddA A @TH Linux PagingS1APdddA A @T<S1APdddA A @Tq5Intel hardware supports two level page mapping schemeS1APdddA A @TELinux software supports three level scheme (for 64 bit architectures)S1APdddA A @T<S1APdddA A @TXPage global directory (pgd)S1APdddA A @TWPage middle directory (pmd)S1APdddA A @TKPage table (pt)S1APdddA A @T<S1APdddA A @Tp4In 32 bit systems the pmd layer is effectively null.S1APdddA A @T<S1APdddA A @Tr6Page table and page directory entries are 32 bits eachS1APdddA A @Ta%There are 1024 entries in each tableS1APdddA A @TCThus page directories and page tables are 4K in size and 4K alignedS1APdddA A @T Permanently reserved page framesSXAPdddA PA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @T-Page 0 - used by BIOS to store config dataSNAPdddA TimesNewRomanA A @Tz!Page 0xa0 - 0xff more bios stuff SNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TEKernel code and data starts at page 0x100 (1 MB) and is delimited by:SNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @Tn_text start of code SNAPdddA TimesNewRomanA A @T/_etext end of code / start of initialized dataSNAPdddA TimesNewRomanA A @T8_edata end of initialized data / start of un-init data.SNAPdddA TimesNewRomanA A @Tp_end end of the kernelSNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @ThFrom System.mapSNAPdddA TimesNewRomanA A @TZ SNAPdddA TimesNewRomanA A @Tec0100000 A _textSHAPdddACourierA A @Tfc026ad91 A _etextSHAPdddACourierA A @Tfc02e77a0 A _edataSHAPdddACourierA A @Tdc0368e58 A _endSHAPdddACourierA A @TSSHAPdddACourierA A @TDHence this kernel is 0x268e58 in size --- slightly less than 2.5 MB.S'APdddA @A8DA!8D TimesNewRomanT2S'APdddA @TMAdditional memory is also permanently allocated during system initialization.SNAPdddA TimesNewRomanA A @TZ SNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TvKernel memory mappingS'APdddA @A8A!8 TimesNewRomanTYSNAPdddA TimesNewRomanA A @TMWhile the kernel is loaded physically at the 1MB line, it is mapped virtuallySNAPdddA TimesNewRomanA A @A8 %A8 %DA8 DMT/at location 0xc01000000 (the 3 GB + 1 MB line).SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TNThe value of this offset is stored in PAGE_OFFSET which is 0xc000000 for IntelSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TqAddress spacesSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T=Each address space (heavyweight process) has a page directorySXAPdddA TimesNewRomanA  A A @T8The kernel area is mapped by a single set of page tablesSXAPdddA TimesNewRomanA  A A @TVPointers to these tables are install beginning at offset 768 inside the page directorySXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TReal storage managementSbAPdddA PA TimesNewRomanA  A A @T2S'APdddA @T9Each page frame is represented by the following structureSXAPdddA TimesNewRomanA  A A @T:These are all allocated in a global array called mem_map[]SXAPdddA TimesNewRomanA  A A @T,The array can be indexed by page number. SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T151 typedef struct page {SaAPdddACourierAd A  A A @TH152 struct list_head list; /* ->mapping has some page lists. */SaAPdddACourierAd A  A A @TJ153 struct address_space *mapping; /* The inode (or ...) we belong to. */SaAPdddACourierAd A  A A @TD154 unsigned long index; /* Our offset within mapping. */SaAPdddACourierAd A  A A @TL155 struct page *next_hash; /* Next page sharing our hash bucket in S6APdddAd A @A8KA8 KA8KCourierT'156 the pagecache hash table. */SaAPdddACourierAd A  A A @TA157 atomic_t count; /* Usage count, see below. */SaAPdddACourierAd A  A A @Td158 unsigned long flags; /* atomic flags, some possibly updated asynchronously */SaAPdddACourierAd A  A A @TE160 struct list_head lru; /* Pageout list, eg. active_list;SaAPdddACourierAd A  A A @T.161 protected by pagemap_lru_lock !! */SaAPdddACourierAd A  A A @TH162 wait_queue_head_t wait; /* Page locked? Stand in line... */SaAPdddACourierAd A  A A @TC163 struct page **pprev_hash; /* Complement to *next_hash. */SaAPdddACourierAd A  A A @TI164 struct buffer_head * buffers; /* Buffer maps us to a disk block. */SaAPdddACourierAd A  A A @TF165 void *virtual; /* Kernel virtual address (NULL ifSaAPdddACourierAd A  A A @T'166 not kmapped, ie. highmem) */SaAPdddACourierAd A  A A @T@167 struct zone_struct *zone; /* Memory zone we are in. */SaAPdddACourierAd A  A A @T|168 } mem_map_t;SaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @TMA further complication is that real memory is partititioned into three zones.SXAPdddA TimesNewRomanA  A A @A8 GMTcSXAPdddA TimesNewRomanA  A A @TISA DMA area 0x0 - 0xfffffS'APdddA @A8A8 A!8 TimesNewRomanT$Normal 0x100000 -0x37fffff (896 MB)S'APdddA @A8A8 A!8 TimesNewRomanTwHigh memory > 896MBSXAPdddA TimesNewRomanA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @T6Linux uses the Buddy System in real storage managment SXAPdddA TimesNewRomanA  A A @A8 TcSXAPdddA TimesNewRomanA  A A @T6Buddy system was designed as a good compromise betweenSXAPdddA TimesNewRomanA  A A @Td SXAPdddA TimesNewRomanA  A A @T&Efficient operation of allocation/freeSXAPdddA TimesNewRomanA  A A @T-Avoidance of fragmentation of physical memorySXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TCWhy worry about fragmented physical memory in a virtual environmentSXAPdddA TimesNewRomanA  A A @T+-> some graphics cards need large DMA areasSXAPpdddpA TimesNewRomanA  A A @TcSXAPpdddpA TimesNewRomanA  A A @TFThat problem could be addressed in other ways (the big_phys_area) hackSXAPdddA TimesNewRomanA  A A @A8  A8 3AT<S1APdddA  A @TXFree storage within each zone is mapped by one of MAX_ORDER (10) free area structures ShAPdddA TimesNewRomanA  A A@ddA @A8 2AA8 CMTUThe particular structure used depends upon whether a free page belongs to a block of:SXAPdddA TimesNewRomanA  A A @Td SXAPdddA TimesNewRomanA  A A @Tssize alignmentSXAPdddA TimesNewRomanA  A A @Tv1 page 4K alignedSXAPdddA TimesNewRomanA  A A @Tv2 pages 8K alignedSXAPdddA TimesNewRomanA  A A @Tw4 pages 16K alignedSXAPdddA TimesNewRomanA  A A @Td:SXAPdddA TimesNewRomanA  A A @Tz512 pages 8 MB alignedSXAPdddA TimesNewRomanA  A A @Td SXAPdddA TimesNewRomanA  A A @T$21 typedef struct free_area_struct {SXAPdddA TimesNewRomanA  A A @A8$CourierT~!22 struct list_head free_list;SRAPdddACourierA  A A @T"23 unsigned long *map;SRAPdddACourierA  A A @Tn24 } free_area_t;SRAPdddACourierA  A A @T`25 SRAPdddACourierA  A A @T<S1APdddA  A @TgThe free_ list field points to a list of struct page where each is the first free page of a free blockSiAPddIdA TimesNewRomanA  A A @A@. A8 A8 *5TtSiAPddIdA TimesNewRomanA  A A @A@. TPThe map field is bitmap identifying states of buddies within the the entire zoneSXAPdddA TimesNewRomanA  A A @A8 TcSXAPdddA TimesNewRomanA  A A @T00 => both buddies free or both buddies allocatedSXAPpdddpA TimesNewRomanA  A A @T31 => exactly one buddy free and one buddy allocatedSXAPpdddpA TimesNewRomanA  A A @TcSXAPpdddpA TimesNewRomanA  A A @TmSbAPpdddpA PA TimesNewRomanA  A A @T^The number of bits in the bitmap is equal to (size-of-zone) / (size-of-page * 2 ^ (order + 1))SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T(Suppose there was exactly 1 MB of memorySXAPdddA TimesNewRomanA  A A @TcSXAPpdddpA TimesNewRomanA  A A @T$There are 2^20 / 2 ^12 = 2 ^ 8 pagesSXAPpdddpA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T0 Order block size sets of buddies (bits)SXAPdddA TimesNewRomanA  A A @TcSXAPpdddpA TimesNewRomanA  A A @Tm 0 4K 2^7SXAPpdddpA TimesNewRomanA  A A @Tm 1 8K 2^6SXAPpdddpA TimesNewRomanA  A A @Tn 2 16K 2^5SXAPpdddpA TimesNewRomanA  A A @Tn 3 32K 2^4SXAPpdddpA TimesNewRomanA  A A @Tn 4 64K 2^3SXAPpdddpA TimesNewRomanA  A A @To 5 128K 2^2SXAPpdddpA TimesNewRomanA  A A @To 6 256K 2^1SXAPpdddpA TimesNewRomanA  A A @To 7 512K 2^0SXAPpdddpA TimesNewRomanA  A A @TcSXAPpdddpA TimesNewRomanA  A A @TWhen a page is freed it is a simple matter to convert its frame number to a bit offset and thus determine if the buddy is free is also free. SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T3Zone mangagement SbAPdddA PA TimesNewRomanA  A A @A8TcSXAPdddA TimesNewRomanA  A A @TGfree_pages counts the number of available pages within the entire zone.SXAPdddA TimesNewRomanA  A A @A8  TFpages_min, pages_low, and pages_high drive the page stealing algorithmSXAPdddA TimesNewRomanA  A A @A8  A8  A8 $T;need_balance is a flag indicating that the zone needs pagesSXAPdddA TimesNewRomanA  A A @A8  ;TcSXAPdddA TimesNewRomanA  A A @T|36 typedef struct zone_struct {SRAPdddACourierA  A A @Tb37 /*SRAPdddACourierA  A A @T{38 * Commonly accessed fields:SRAPdddACourierA  A A @Tb39 */SRAPdddACourierA  A A @Tt40 spinlock_t lock;SRAPdddACourierA  A A @T%41 unsigned long free_pages;SRAPdddACourierA  A A @T;42 unsigned long pages_min, pages_low, pages_high;SRAPdddACourierA  A A @T'43 int need_balance;SRAPdddACourierA  A A @T`44 SRAPdddACourierA  A A @Tb45 /*SRAPdddACourierA  A A @T"46 * free areas of different sizesSRAPdddACourierA  A A @Tb47 */SRAPdddACourierA  A A @T$48 free_area_t free_area[MAX_ORDER];SRAPdddACourierA  A A @T`49 SRAPdddACourierA  A A @Tb50 /*SRAPdddACourierA  A A @T%51 * Discontig memory support fields.SRAPdddACourierA  A A @Tb52 */SRAPdddACourierA  A A @T#53 struct pglist_data *zone_pgdat;SRAPdddACourierA  A A @T|54 struct page *zone_mem_map;SRAPdddACourierA  A A @T*55 unsigned long zone_start_paddr;SRAPdddACourierA  A A @T*56 unsigned long zone_start_mapnr;SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @Tu59 * rarely used fields:SRAPdddACourierA  A A @Tb60 */SRAPdddACourierA  A A @T|61 char *name;SRAPdddACourierA  A A @T{62 unsigned long size;SRAPdddACourierA  A A @Ti 63 } zone_t;SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @T^This structure represents a layer above the zone structure that was introduced to support NUMASXAPdddA TimesNewRomanA  A A @T<A non-NUMA system consists of a single node with three zonesSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T} 99 typedef struct pglist_data {SRAPdddACourierA  A A @T%100 zone_t node_zones[MAX_NR_ZONES];SRAPdddACourierA  A A @T/101 zonelist_t node_zonelists[GFP_ZONEMASK+1];SRAPdddACourierA  A A @To102 int nr_zones;SRAPdddACourierA  A A @T|103 struct page *node_mem_map;SRAPdddACourierA  A A @T&104 unsigned long *valid_addr_bitmap;SRAPdddACourierA  A A @T} 105 struct bootmem_data *bdata;SRAPdddACourierA  A A @T$106 unsigned long node_start_paddr;SRAPdddACourierA  A A @T$107 unsigned long node_start_mapnr;SRAPdddACourierA  A A @Tz108 unsigned long node_size;SRAPdddACourierA  A A @Tn109 int node_id;SRAPdddACourierA  A A @T#110 struct pglist_data *node_next;SRAPdddACourierA  A A @Tm111 } pg_data_t;SRAPdddACourierA  A A @T`112SRAPdddACourierA  A A @T^ SRAPdddACourierA  A A @T?Pageable memory is setup via the free_area_init_core() functionSXAPdddA TimesNewRomanA  A A @A8 !?TcSXAPdddA TimesNewRomanA  A A @T}By now a considerable amount of initialization has already completed and the number of pages in each zone is should be known.SXAPdddA TimesNewRomanA  A A @T]SRAPdddACourierA  A A @Tc631 /*SRAPdddACourierA  A A @T&632 * Set up the zone data structures:SRAPdddACourierA  A A @T~!633 * - mark all pages reservedSRAPdddACourierA  A A @T&634 * - mark all memory queues emptySRAPdddACourierA  A A @T"635 * - clear the memory bitmapsSRAPdddACourierA  A A @Tc636 */SRAPdddACourierA  A A @T$637 void __init free_area_init_core(SRAPdddACourierA  A A @Tu int nid, /* 0 */SRAPdddACourierA  A A @Tq pg_data_t *pgdat, SRAPdddACourierA  A A @Tr struct page **gmap,SRAPdddACourierA  A A @T~! unsigned long *zones_size, SRAPdddACourierA  A A @T* unsigned long zone_start_paddr, /* 0 */SRAPdddACourierA  A A @T+ unsigned long *zholes_size, /* 0 */SRAPdddACourierA  A A @T" struct page *lmem_map) /* 0 */SRAPdddACourierA  A A @Tb640 {SRAPdddACourierA  A A @Tq641 struct page *p;SRAPdddACourierA  A A @Tu642 unsigned long i, j;SRAPdddACourierA  A A @Ty643 unsigned long map_size;SRAPdddACourierA  A A @T6644 unsigned long totalpages, offset, realtotalpages;SRAPdddACourierA  A A @TL645 const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1);SRAPdddACourierA  A A @Ta646 SRAPdddACourierA  A A @T'647 if (zone_start_paddr & ~PAGE_MASK)SRAPdddACourierA  A A @Ti 648 BUG();SRAPdddACourierA  A A @Ta649 SRAPdddACourierA  A A @Tq650 totalpages = 0;SRAPdddACourierA  A A @T)651 for (i = 0; i < MAX_NR_ZONES; i++) {SRAPdddACourierA  A A @T)652 unsigned long size = zones_size[i];SRAPdddACourierA  A A @Tv653 totalpages += size;SRAPdddACourierA  A A @Tb654 }SRAPdddACourierA  A A @T~!655 realtotalpages = totalpages;SRAPdddACourierA  A A @Tr656 if (zholes_size)SRAPdddACourierA  A A @T'657 for (i = 0; i < MAX_NR_ZONES; i++)SRAPdddACourierA  A A @T'658 realtotalpages -= zholes_size[i];SRAPdddACourierA  A A @Ta659 SRAPdddACourierA  A A @TA660 printk("On node %d totalpages: %lu\n", nid, realtotalpages);SRAPdddACourierA  A A @Ta661 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TvThis information is printed during the boot sequence... hence total pages includes reserved and unreserved categories.SXAPdddA TimesNewRomanA  A A @T2S'APdddA @T? 1253 Mar 21 17:16:34 waco kernel: On node 0 totalpages: 32704SRAPdddACourierA  A A @T8 1254 Mar 21 17:16:34 waco kernel: zone(0): 4096 pages.SRAPdddACourierA  A A @T9 1255 Mar 21 17:16:34 waco kernel: zone(1): 28608 pages.SRAPdddACourierA  A A @T5 1256 Mar 21 17:16:34 waco kernel: zone(2): 0 pages.SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T+sThe mem_map table of struct page is allocated here via a special purpose low level allocator alloc_bootmem_node()S8APdd;dA @A@. A8sA!8s TimesNewRomanA8 _A8  A8  A8 !A8 _sT2S'APdddA @T"662 INIT_LIST_HEAD(&active_list);SRAPdddACourierA  A A @T$663 INIT_LIST_HEAD(&inactive_list);SRAPdddACourierA  A A @Ta664 SRAPdddACourierA  A A @Td665 /*SRAPdddACourierA  A A @TB666 * Some architectures (with lots of mem and discontinous memorySRAPdddACourierA  A A @T3667 * maps) have to search for a good mem_map area:SRAPdddACourierA  A A @TA668 * For discontigmem, the conceptual mem map array starts from SRAPdddACourierA  A A @TD669 * PAGE_OFFSET, we need to align the actual array onto a mem map SRAPdddACourierA  A A @T%670 * boundary, so that MAP_NR works.SRAPdddACourierA  A A @Tc671 */SRAPdddACourierA  A A @T5672 map_size = (totalpages + 1)*sizeof(struct page);SRAPdddACourierA  A A @T(673 if (lmem_map == (struct page *)0) {SRAPdddACourierA  A A @TK674 lmem_map = (struct page *) alloc_bootmem_node(pgdat, map_size);SRAPdddACourierA  A A @T/675 lmem_map = (struct page *)(PAGE_OFFSET + SRAPdddACourierA  A A @T8676 MAP_ALIGN((unsigned long)lmem_map - PAGE_OFFSET));SRAPdddACourierA  A A @Tc677 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TT*gmap is actually an alias here for the global variable mem_map.. ain't C wonderful!S'APdddA @A8 A8 8?T]SRAPdddACourierA  A A @T,678 *gmap = pgdat->node_mem_map = lmem_map;SRAPdddACourierA  A A @T#679 pgdat->node_size = totalpages;SRAPdddACourierA  A A @T0680 pgdat->node_start_paddr = zone_start_paddr;SRAPdddACourierA  A A @T4681 pgdat->node_start_mapnr = (lmem_map - mem_map);SRAPdddACourierA  A A @Tv682 pgdat->nr_zones = 0;SRAPdddACourierA  A A @Ta683 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TGFlag all pages initially reserved. They get unreserved at end of boot.S'APdddA @A8"A8 "A!8" TimesNewRomanT2S'APdddA @Td684 /*SRAPdddACourierA  A A @T=685 * Initially all pages are reserved - free ones are freedSRAPdddACourierA  A A @T>686 * up by free_all_bootmem() once the early boot process isSRAPdddACourierA  A A @Ti 687 * done.SRAPdddACourierA  A A @Td688 */SRAPdddACourierA  A A @T9689 for (p = lmem_map; p < lmem_map + totalpages; p++) {SRAPdddACourierA  A A @Tx690 set_page_count(p, 0);SRAPdddACourierA  A A @Tv691 SetPageReserved(p);SRAPdddACourierA  A A @T$692 init_waitqueue_head(&p->wait);SRAPdddACourierA  A A @Tz693 memlist_init(&p->list);SRAPdddACourierA  A A @Tc694 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T.Initialize zone data structures for all zones.SbAPdddA PA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T%696 offset = lmem_map - mem_map; SRAPdddACourierA  A A @T)697 for (j = 0; j < MAX_NR_ZONES; j++) {SRAPdddACourierA  A A @T+698 zone_t *zone = pgdat->node_zones + j;SRAPdddACourierA  A A @Tv699 unsigned long mask;SRAPdddACourierA  A A @T#700 unsigned long size, realsize;SRAPdddACourierA  A A @Ta701 SRAPdddACourierA  A A @T&702 realsize = size = zones_size[j];SRAPdddACourierA  A A @Ts703 if (zholes_size)SRAPdddACourierA  A A @T"704 realsize -= zholes_size[j];SRAPdddACourierA  A A @Ta705 SRAPdddACourierA  A A @T1706 printk("zone(%lu): %lu pages.\n", j, size);SRAPdddACourierA  A A @Tu707 zone->size = size;SRAPdddACourierA  A A @T~!708 zone->name = zone_names[j];SRAPdddACourierA  A A @T&709 zone->lock = SPIN_LOCK_UNLOCKED;SRAPdddACourierA  A A @T|710 zone->zone_pgdat = pgdat;SRAPdddACourierA  A A @Tx711 zone->free_pages = 0;SRAPdddACourierA  A A @Tz712 zone->need_balance = 0;SRAPdddACourierA  A A @Tm713 if (!size)SRAPdddACourierA  A A @Tm714 continue;SRAPdddACourierA  A A @Ta715 SRAPdddACourierA  A A @Ty716 pgdat->nr_zones = j+1;SRAPdddACourierA  A A @Ta717 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @T;Initialize the "water marks" used to drive page stealing. S'APdddA @A8;A8 ;A!8; TimesNewRomanTcSXAPdddA TimesNewRomanA  A A @T)Balance ratios are set to {128, 128, 128}SXAPdddA TimesNewRomanA  A A @T6realsize is the size of the zone in pages - any holes.SXAPdddA TimesNewRomanA  A A @A8 T$Balance mins are set to {20, 20, 20}SXAPdddA TimesNewRomanA  A A @T(Balance maxes are set to {255, 255, 255}SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TSuppose a region has 64 MB. SXAPdddA TimesNewRomanA  A A @T#Then realsize = 2^26 / 2^12 = 2^14 SXAPdddA TimesNewRomanA  A A @T{mask = 2^14 / 2^7 = 2^ 7SXAPdddA TimesNewRomanA  A A @Trpages_min = 2^7SXAPdddA TimesNewRomanA  A A @Trpages_low = 2^8SXAPdddA TimesNewRomanA  A A @Tupages_high = 384. SXAPdddA TimesNewRomanA  A A @T]SRAPdddACourierA  A A @T0718 mask = (realsize / zone_balance_ratio[j]);SRAPdddACourierA  A A @T%719 if (mask < zone_balance_min[j])SRAPdddACourierA  A A @T"720 mask = zone_balance_min[j];SRAPdddACourierA  A A @T*721 else if (mask > zone_balance_max[j])SRAPdddACourierA  A A @T"722 mask = zone_balance_max[j];SRAPdddACourierA  A A @Tz723 zone->pages_min = mask;SRAPdddACourierA  A A @T|724 zone->pages_low = mask*2;SRAPdddACourierA  A A @T} 725 zone->pages_high = mask*3;SRAPdddACourierA  A A @Ta726 SRAPdddACourierA  A A @T,727 zone->zone_mem_map = mem_map + offset;SRAPdddACourierA  A A @T&728 zone->zone_start_mapnr = offset;SRAPdddACourierA  A A @T0729 zone->zone_start_paddr = zone_start_paddr;SRAPdddACourierA  A A @Ta730 SRAPdddACourierA  A A @TP731 if ((zone_start_paddr >> PAGE_SHIFT) & (zone_required_alignment-1))SRAPdddACourierA  A A @T<732 printk("BUG: wrong zone alignment, it will crash\n");SRAPdddACourierA  A A @Ta733 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T"734 for (i = 0; i < size; i++) {SRAPdddACourierA  A A @T0735 struct page *page = mem_map + offset + i;SRAPdddACourierA  A A @Tv736 page->zone = zone;SRAPdddACourierA  A A @Tz737 if (j != ZONE_HIGHMEM)SRAPdddACourierA  A A @T/738 page->virtual = __va(zone_start_paddr);SRAPdddACourierA  A A @T%739 zone_start_paddr += PAGE_SIZE;SRAPdddACourierA  A A @Td740 }SRAPdddACourierA  A A @T`741SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T5130 #define __pa(x) ((unsigned long)(x)-PAGE_OFFSET)SRAPdddACourierA  A A @T?131 #d      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~efine __va(x) ((void *)((unsigned long)(x)+PAGE_OFFSET))SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @THInitialize the buddy system structures here. size is expressed in pages.S'APdddA @A8+A8 +A!8+ TimesNewRomanA8 -1A8 1HT= S1APdddA  A @T^ SRAPdddACourierA  A A @Tr742 offset += size;SRAPdddACourierA  A A @Tx743 for (i = 0; ; i++) {SRAPdddACourierA  A A @T~!744 unsigned long bitmap_size;SRAPdddACourierA  A A @Ta745 SRAPdddACourierA  A A @T3746 memlist_init(&zone->free_area[i].free_list);SRAPdddACourierA  A A @T{747 if (i == MAX_ORDER-1) {SRAPdddACourierA  A A @T&748 zone->free_area[i].map = NULL;SRAPdddACourierA  A A @Tk749 break;SRAPdddACourierA  A A @Te750 }SRAPdddACourierA  A A @Ta751 SRAPdddACourierA  A A @Tf 752 /*SRAPdddACourierA  A A @T1753 * Page buddy system uses "index >> (i+1)",SRAPdddACourierA  A A @T+754 * where "index" is at most "size-1".SRAPdddACourierA  A A @Te755 *SRAPdddACourierA  A A @T0756 * The extra "+3" is to round down to byteSRAPdddACourierA  A A @T0757 * size (8 bits per byte assumption). ThusSRAPdddACourierA  A A @T4758 * we get "(size-1) >> (i+4)" as the last byteSRAPdddACourierA  A A @Tt759 * we can access.SRAPdddACourierA  A A @Te760 *SRAPdddACourierA  A A @T1761 * The "+1" is because we want to round theSRAPdddACourierA  A A @T0762 * byte allocation up rather than down. SoSRAPdddACourierA  A A @T4763 * we should have had a "+7" before we shiftedSRAPdddACourierA  A A @T3764 * down by three. Also, we have to add one asSRAPdddACourierA  A A @T3765 * we actually _use_ the last bit (it's [0,n]SRAPdddACourierA  A A @T|766 * inclusive, not [0,n[).SRAPdddACourierA  A A @Te767 *SRAPdddACourierA  A A @T0768 * So we actually had +7+1 before we shiftSRAPdddACourierA  A A @T2769 * down by 3. But (n+8) >> 3 == (n >> 3) + 1SRAPdddACourierA  A A @T2770 * (modulo overflows, which we do not have).SRAPdddACourierA  A A @Te771 *SRAPdddACourierA  A A @T2772 * Finally, we LONG_ALIGN because all bitmapSRAPdddACourierA  A A @T~!773 * operations are on longs.SRAPdddACourierA  A A @Tf 774 */SRAPdddACourierA  A A @T'775 bitmap_size = (size-1) >> (i+4);SRAPdddACourierA  A A @T/776 bitmap_size = LONG_ALIGN(bitmap_size+1);SRAPdddACourierA  A A @T} 777 zone->free_area[i].map = SRAPdddACourierA  A A @TF778 (unsigned long *) alloc_bootmem_node(pgdat, bitmap_size);SRAPdddACourierA  A A @Te779 } SRAPdddACourierA  A A @Tc780 }SRAPdddACourierA  A A @Ty781 build_zonelists(pgdat);SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @T0build_zonelists() doesn't build the free_lists. SXAPdddA TimesNewRomanA  A A @A8 $T^It builds zone eligibility / preference lists associated with allocation flags such as GFP_DMASXAPdddA TimesNewRomanA  A A @A8 W^TReal memory allocation. SbAPdddA PA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TL__get_free_pages() is the internal entry point to the buddy system allocatorSXAPdddA TimesNewRomanA  A A @A8LA8 T>The order is the log2(#pages) required to satisfy the request.S'APdddA @A8>A8 >A!8> TimesNewRomanTcSXAPdddA TimesNewRomanA  A A @THGFP_MASK can be set toS'APdddA @T2S'APdddA @TM522 /* Zone modifiers in GFP_ZONEMASK (see linux/mmzone.h - low four bits) */SaAPdddACourierAd A  A A @T523 #define __GFP_DMA 0x01SaAPdddACourierAd A  A A @T524 #define __GFP_HIGHMEM 0x02SaAPdddACourierAd A  A A @Tp525 SaAPdddACourierAd A  A A @T6526 /* Action modifiers - doesn't change the zoning */SaAPdddACourierAd A  A A @T=527 #define __GFP_WAIT 0x10 /* Can wait and reschedule? */SaAPdddACourierAd A  A A @TC528 #define __GFP_HIGH 0x20 /* Should access emergency pools? */SaAPdddACourierAd A  A A @TD529 #define __GFP_IO 0x40 /* Can start low memory physical IO? */SaAPdddACourierAd A  A A @TF530 #define __GFP_HIGHIO 0x80 /* Can start high mem physical IO? */SaAPdddACourierAd A  A A @TA531 #define __GFP_FS 0x100 /* Can call down to low-level FS? */SaAPdddACourierAd A  A A @Tp532 SaAPdddACourierAd A  A A @T=533 #define GFP_NOHIGHIO (__GFP_HIGH | __GFP_WAIT | __GFP_IO)SaAPdddACourierAd A  A A @T.534 #define GFP_NOIO (__GFP_HIGH | __GFP_WAIT)SaAPdddACourierAd A  A A @TH535 #define GFP_NOFS (__GFP_HIGH | __GFP_WAIT | __GFP_IO | __GFP_HIGHIO)SaAPdddACourierAd A  A A @T#536 #define GFP_ATOMIC (__GFP_HIGH)SaAPdddACourierAd A  A A @TG537 #define GFP_USER ( __GFP_WAIT | __GFP_IO | __GFP_HIGHIO | __GFP_FS)SaAPdddACourierAd A  A A @TZ538 #define GFP_HIGHUSER (__GFP_WAIT | __GFP_IO | __GFP_HIGHIO | __GFP_FS | __GFP_HIGHMEM)SaAPdddACourierAd A  A A @TU539 #define GFP_KERNEL (__GFP_HIGH | __GFP_WAIT | __GFP_IO | __GFP_HIGHIO | __GFP_FS)SaAPdddACourierAd A  A A @TR540 #define GFP_NFS (__GFP_HIGH | __GFP_WAIT | __GFP_IO | __GFP_HIGHIO | __GFP_FS)SaAPdddACourierAd A  A A @TH541 #define GFP_KSWAPD (__GFP_WAIT | __GFP_IO | __GFP_HIGHIO | __GFP_FS)SaAPdddACourierAd A  A A @Tp542 SaAPdddACourierAd A  A A @T]SRAPdddACourierA  A A @T:406 unsigned long __get_free_pages(unsigned int gfp_mask, SRAPdddACourierA  A A @Tw unsigned int order)SRAPdddACourierA  A A @Tb407 {SRAPdddACourierA  A A @Tu408 struct page * page;SRAPdddACourierA  A A @Ta409 SRAPdddACourierA  A A @T)410 page = alloc_pages(gfp_mask, order);SRAPdddACourierA  A A @Tl411 if (!page)SRAPdddACourierA  A A @Tl412 return 0;SRAPdddACourierA  A A @T/413 return (unsigned long) page_address(page);SRAPdddACourierA  A A @Tb414 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T7alloc_pages is a front for the usual insulating layersSRAPdddACourierA  A A @A!87 TimesNewRomanA8  TcSXAPdddA TimesNewRomanA  A A @TX361 static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order)SRAPdddACourierA  A A @Tb362 {SRAPdddACourierA  A A @Tc363 /*SRAPdddACourierA  A A @T*364 * Gets optimized away by the compiler.SRAPdddACourierA  A A @Tc365 */SRAPdddACourierA  A A @Ty366 if (order >= MAX_ORDER)SRAPdddACourierA  A A @To367 return NULL;SRAPdddACourierA  A A @T*368 return _alloc_pages(gfp_mask, order);SRAPdddACourierA  A A @Tb369 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T9Each pg_data structure contains a table of 15 zone lists SbAPdddA PA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T5A zone list is a table of pointers to zone structuresSXAPdddA TimesNewRomanA  A A @TbZone lists are predefined to include zone pointers to legal/preferred zones for each request type.S'APdddA @A8bA8 bA!8b TimesNewRomanT2S'APdddA @Ts65 #define ZONE_DMA 0SRAPdddACourierA  A A @Tv66 #define ZONE_NORMAL 1SRAPdddACourierA  A A @Tw67 #define ZONE_HIGHMEM 2SRAPdddACourierA  A A @Tw68 #define MAX_NR_ZONES 3SRAPdddACourierA  A A @T_69SRAPdddACourierA  A A @Tq70 /*SaAPdddACourierAd A  A A @T>71 * One allocation request operates on a zonelist. A zonelistSRAPdddACourierA  A A @T;72 * is a list of zones, the first one is the 'goal' of theSRAPdddACourierA  A A @TB73 * allocation, the other zones are fallback zones, in decreasingSRAPdddACourierA  A A @Tk74 * priority.SRAPdddACourierA  A A @Ta75 *SRAPdddACourierA  A A @TB76 * Right now a zonelist takes up less than a cacheline. We neverSRAPdddACourierA  A A @TC77 * modify it apart from boot-up, and only a few indices are used,SRAPdddACourierA  A A @TB78 * so despite the zonelist table being relatively big, the cacheSRAPdddACourierA  A A @T/79 * footprint of this construct is very small.SRAPdddACourierA  A A @Tb80 */SRAPdddACourierA  A A @T#81 typedef struct zonelist_struct {SRAPdddACourierA  A A @T582 zone_t * zones [MAX_NR_ZONES+1]; // NULL delimitedSRAPdddACourierA  A A @Tm83 } zonelist_t;SRAPdddACourierA  A A @T`84 SRAPdddACourierA  A A @Ty85 #define GFP_ZONEMASK 0x0fSRAPdddACourierA  A A @T`86 SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @TxThis wrapper uses the gfp_mask to identify the correct zone list containing legal/preferred zones for each request type.SRAPdddACourierA  A A @A!8x TimesNewRomanTcSXAPdddA TimesNewRomanA  A A @TL221 struct page *_alloc_pages(unsigned int gfp_mask, unsigned int order)SRAPdddACourierA  A A @Tb222 {SRAPdddACourierA  A A @T*223 return __alloc_pages(gfp_mask, order,SRAPdddACourierA  A A @TD224 contig_page_data.node_zonelists+(gfp_mask & GFP_ZONEMASK));SRAPdddACourierA  A A @Tn225 }S'APdddA @A8A8 A8CourierT2S'APdddA @TlSaAPdddACourierAd A  A A @TvSkAPdddA PACourierAd A  A A @T$The actual allocation is done here. SaAPdddACourierAd A  A A @A!8# TimesNewRomanTlSaAPdddACourierAd A  A A @T7305 struct page * __alloc_pages(unsigned int gfp_mask, SRAPdddACourierA  A A @T. unsigned int order, zonelist_t *zonelist)SRAPdddACourierA  A A @Tb306 {SRAPdddACourierA  A A @Tt307 unsigned long min;SRAPdddACourierA  A A @T} 308 zone_t **zone, * classzone;SRAPdddACourierA  A A @Tu309 struct page * page;SRAPdddACourierA  A A @Tl310 int freed;SRAPdddACourierA  A A @Ta311 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T)For each zone in the suitable zone list, SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TsSee if the number of free_pages minus the number requested is still greater then pages_low watermark of the zone. SXAPdddA TimesNewRomanA  A A @A8 A8 QZTcSXAPdddA TimesNewRomanA  A A @T2If so, the actual allocation is done by rmqueue. SXAPdddA TimesNewRomanA  A A @A8 )0TcSXAPdddA TimesNewRomanA  A A @T9The most preferred zone is remembered as the classzone. SXAPdddA TimesNewRomanA  A A @A8 -7T]SRAPdddACourierA  A A @Ty312 zone = zonelist->zones;SRAPdddACourierA  A A @Tt313 classzone = *zone;SRAPdddACourierA  A A @Tu314 min = 1UL << order;SRAPdddACourierA  A A @Tl315 for (;;) {SRAPdddACourierA  A A @Ty316 zone_t *z = *(zone++);SRAPdddACourierA  A A @Tj 317 if (!z)SRAPdddACourierA  A A @Tj 318 break;SRAPdddACourierA  A A @Ta319 SRAPdddACourierA  A A @Tv320 min += z->pages_low;SRAPdddACourierA  A A @T} 321 if (z->free_pages > min) {SRAPdddACourierA  A A @T} 322 page = rmqueue(z, order);SRAPdddACourierA  A A @Tm323 if (page)SRAPdddACourierA  A A @Tq324 return page;SRAPdddACourierA  A A @Td325 }SRAPdddACourierA  A A @Tc326 }SRAPdddACourierA  A A @Tm327 S'APdddA @A8A8 A8CourierTMArrival here means that there were not enough available pages. In this case:SkAPdddA PACourierAd A  A A @A!8M TimesNewRomanTrSgAPdddA TimesNewRomanAd A  A A @T:Mark the zone as needing to be replenished with pages and SgAPdddA TimesNewRomanAd A  A A @T3Wakeup the the page stealer (kswapd) to steal some.SgAPdddA TimesNewRomanAd A  A A @TlSaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @T~!328 classzone->need_balance = 1;SRAPdddACourierA  A A @Tg 329 mb();SRAPdddACourierA  A A @T(330 if (waitqueue_active(&kswapd_wait))SRAPdddACourierA  A A @T*331 wake_up_interruptible(&kswapd_wait);SRAPdddACourierA  A A @Ta332 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @Ty333 zone = zonelist->zones;SRAPdddACourierA  A A @Tu334 min = 1UL << order;SRAPdddACourierA  A A @Tk335 for (;;) SRAPdddACourierA  A A @T_ {SRAPdddACourierA  A A @T{336 unsigned long local_min;SRAPdddACourierA  A A @Ty337 zone_t *z = *(zone++);SRAPdddACourierA  A A @Tj 338 if (!z)SRAPdddACourierA  A A @Tj 339 break;SRAPdddACourierA  A A @Ta340 SRAPdddACourierA  A A @TrSgAPdddA TimesNewRomanAd A  A A @T5Here we test agains pages_min instead of pages_low.. S'APdddA @A82A82d A!82 TimesNewRomanA8 )A8 A8 )2T2S'APdddA @T%The value of min is the pages wanted.S'APdddA @A8  A8  A8 %TZThe value of local_min reflects the number of free pages that must remain after the alloc.SgAPdddA TimesNewRomanAd A  A A @TDIt will either be pages_min or pages_min / 4 depending on __GFP_WAITSgAPdddA TimesNewRomanAd A  A A @A8 A8 ,TrSgAPdddA TimesNewRomanAd A  A A @T$Suppose pages_min = 20 and min = 4. SgAPdddA TimesNewRomanAd A  A A @A8 A8 !T!Then local_min is first set to 20S'APdddA @A8!A8 !A8!d A!8! TimesNewRomanA8 T:If this is a no waiting request it is further reduced to 5SgAPdddA TimesNewRomanAd A  A A @T.So min + local_min is equal to either 9 or 25.SgAPdddA TimesNewRomanAd A  A A @A8 T?Thus the allocation will be made here iff free_pages > 9 or 25.SgAPdddA TimesNewRomanAd A  A A @A8 *4TrSgAPdddA TimesNewRomanAd A  A A @T|341 local_min = z->pages_min;SRAPdddACourierA  A A @T#342 if (!(gfp_mask & __GFP_WAIT))SRAPdddACourierA  A A @Tt343 local_min >>= 2;SRAPdddACourierA  A A @Tt344 min += local_min;SRAPdddACourierA  A A @T} 345 if (z->free_pages > min) {SRAPdddACourierA  A A @T} 346 page = rmqueue(z, order);SRAPdddACourierA  A A @Tm347 if (page)SRAPdddACourierA  A A @Tq348 return page;SRAPdddACourierA  A A @Td349 }SRAPdddACourierA  A A @Tc350 }SRAPdddACourierA  A A @Ta351 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T8As it says if we get here we are really low on memory...SkAPdddA PACourierAd A  A A @A!88 TimesNewRomanA8 !(T2S'APdddA @TJIf process flags require it, (under what conditions are the flags set???)SgAPdddA TimesNewRomanAd A  A A @TRwe go through the zone list one more time and this time take anything we can find.SgAPdddA TimesNewRomanAd A  A A @A8 =FTlSaAPdddACourierAd A  A A @T3352 /* here we're in the low on memory slow path */SRAPdddACourierA  A A @Ta353 SRAPdddACourierA  A A @Tk354 rebalance:SRAPdddACourierA  A A @T6355 if (current->flags & (PF_MEMALLOC | PF_MEMDIE)) {SRAPdddACourierA  A A @Tz356 zone = zonelist->zones;SRAPdddACourierA  A A @Tm357 for (;;) {SRAPdddACourierA  A A @Tz358 zone_t *z = *(zone++);SRAPdddACourierA  A A @Tk359 if (!z)SRAPdddACourierA  A A @Tk360 break;SRAPdddACourierA  A A @Ta361 SRAPdddACourierA  A A @T} 362 page = rmqueue(z, order);SRAPdddACourierA  A A @Tm363 if (page)SRAPdddACourierA  A A @Tq364 return page;SRAPdddACourierA  A A @Td365 }SRAPdddACourierA  A A @To366 return NULL;SRAPdddACourierA  A A @Tb367 }SRAPdddACourierA  A A @Ta368 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T;Arrival here means the request just can't be satisfied now.SgAPdddA TimesNewRomanAd A  A A @T`For atomic requests made by interrupt handlers that can't sleep, it's necessary to bail out now.S'APdddA @A8`A8 `A8`d A!8` TimesNewRomanTlSaAPdddACourierAd A  A A @T8369 /* Atomic allocations - we can't balance anything */SRAPdddACourierA  A A @T"370 if (!(gfp_mask & __GFP_WAIT))SRAPdddACourierA  A A @To371 return NULL;SRAPdddACourierA  A A @T`372SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @T=The variable classzone still points to the original target. SgAPdddA TimesNewRomanAd A  A A @A8  TaWe try to replenish it by stealing some stuff here... balancing may return us the memory we need.SgAPdddA TimesNewRomanAd A  A A @TlSaAPdddACourierAd A  A A @TB373 page = balance_classzone(classzone, gfp_mask, order, &freed);SRAPdddACourierA  A A @Tk374 if (page)SRAPdddACourierA  A A @To375 return page;SRAPdddACourierA  A A @Ta376 SRAPdddACourierA  A A @TrSgAPdddA TimesNewRomanAd A  A A @T(Make yet another pass over the zonelist.SgAPdddA TimesNewRomanAd A  A A @TrSgAPdddA TimesNewRomanAd A  A A @T8This pass requires pages_min remain after the allocationSgAPdddA TimesNewRomanAd A  A A @TOIt doesn't contain the local_min hack because we can't get here with __GFP_WAITSgAPdddA TimesNewRomanAd A  A A @A8  TrSgAPdddA TimesNewRomanAd A  A A @Ty377 zone = zonelist->zones;SRAPdddACourierA  A A @Tu378 min = 1UL << order;SRAPdddACourierA  A A @Tl379 for (;;) {SRAPdddACourierA  A A @Ty380 zone_t *z = *(zone++);SRAPdddACourierA  A A @Tj 381 if (!z)SRAPdddACourierA  A A @Ti 382 break;SRAPdddACourierA  A A @Ta383 SRAPdddACourierA  A A @Tw384 min += z->pages_min;SRAPdddACourierA  A A @T} 385 if (z->free_pages > min) {SRAPdddACourierA  A A @T} 386 page = rmqueue(z, order);SRAPdddACourierA  A A @Tl387 if (page)SRAPdddACourierA  A A @Tp388 return page;SRAPdddACourierA  A A @Tc389 }SRAPdddACourierA  A A @Tb390 }SRAPdddACourierA  A A @Ta391 SRAPdddACourierA  A A @T.392 /* Don't let big-order allocations loop */SRAPdddACourierA  A A @Tp393 if (order > 3)SRAPdddACourierA  A A @To394 return NULL;SRAPdddACourierA  A A @Ta395 SRAPdddACourierA  A A @T)396 /* Yield for kswapd, and try again */SRAPdddACourierA  A A @T$397 current->policy |= SCHED_YIELD;SRAPdddACourierA  A A @T'398 __set_current_state(TASK_RUNNING);SRAPdddACourierA  A A @Tm399 schedule();SRAPdddACourierA  A A @Tq400 goto rebalance;SRAPdddACourierA  A A @Tb401 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @TZrmqueue performs the mechanics of removing the free block and partitioning it if necessarySXAPdddA TimesNewRomanA  A A @A8 TPThe input parameter order is the number of pages needed to satisfy the request..SXAPdddA TimesNewRomanA  A A @A8 TcSXAPdddA TimesNewRomanA  A A @T"175 static struct page * rmqueue(SRAPdddACourierA  A A @Tm zone_t *zone, SRAPdddACourierA  A A @Tr unsigned int order)SRAPdddACourierA  A A @Tc176 {SRAPdddACourierA  A A @T2177 free_area_t * area = zone->free_area + order;SRAPdddACourierA  A A @T%178 unsigned int curr_order = order;SRAPdddACourierA  A A @T#179 struct list_head *head, *curr;SRAPdddACourierA  A A @Tv180 unsigned long flags;SRAPdddACourierA  A A @Tt181 struct page *page;SRAPdddACourierA  A A @Ta182 SRAPdddACourierA  A A @T+183 spin_lock_irqsave(&zone->lock, flags);SRAPdddACourierA  A A @Tf 184 do {SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @Tbarea points to the free area struct associated with the target allocation order in the target zoneSXAPdddA TimesNewRomanA  A A @A8 A8 TcSXAPdddA TimesNewRomanA  A A @T{185 head = &area->free_list;SRAPdddACourierA  A A @T} 186 curr = memlist_next(head);SRAPdddACourierA  A A @Ta187 SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T,If (curr == head) this free list is empty.. S'APdddA @A8,A8 ,A!8, TimesNewRomanA8 A8 TcSXAPdddA TimesNewRomanA  A A @TCWe may (or may not) know that adequate memory exists in this zone, SXAPdddA TimesNewRomanA  A A @A8 =ATFbut we never know if it resides in this order or a higher order list.SXAPdddA TimesNewRomanA  A A @T]SRAPdddACourierA  A A @Tv188 if (curr != head) {SRAPdddACourierA  A A @Tw189 unsigned int index;SRAPdddACourierA  A A @T`190SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TgS\APdddA PACourierA  A A @T0Now we have found the memory area we will use.. SXAPdddA TimesNewRomanA  A A @TQThe free list is made up of page descriptors for the first page in the block onlySXAPdddA TimesNewRomanA  A A @A8 1@TCThus by deleting the entry we effectively delete 2^order pages .. S'APdddA @A8CA8 CA!8C TimesNewRomanTFThe ones we don't need must go back on the free lists of lower orders.SXAPdddA TimesNewRomanA  A A @T_ SRAPdddACourierA  A A @T5191 page = memlist_entry(curr, struct page, list);SRAPdddACourierA  A A @T} 192 if (BAD_RANGE(zone,page))SRAPdddACourierA  A A @Tk193 BUG();SRAPdddACourierA  A A @Tv194 memlist_del(curr);SRAPdddACourierA  A A @T)195 index = page - zone->zone_mem_map;SRAPdddACourierA  A A @TcSXAPdddA TimesNewRomanA  A A @THMARK_USED is a macro used to update the bitmap associated with the area.SXAPdddA TimesNewRomanA  A A @T^There is no recombining that takes place in the top order, and thus the bitmap is not relevantSXAPdddA TimesNewRomanA  A A @TXThe expand function is used to reallocate the pages that were not used on lists of lowerSXAPdddA TimesNewRomanA  A A @Torder. If we use a block of size 8 free pages to satisfy a one page request, we create one new free block of order 1, 2, and 4. SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @T%196 if (curr_order != MAX_ORDER-1)SRAPdddACourierA  A A @T+197 MARK_USED(index, curr_order, area);SRAPdddACourierA  A A @T(198 zone->free_pages -= 1UL << order;SRAPdddACourierA  A A @Ta199 SRAPdddACourierA  A A @TG200 page = expand(zone, page, index, order, curr_order, area);SRAPdddACourierA  A A @T2201 spin_unlock_irqrestore(&zone->lock, flags);SRAPdddACourierA  A A @Ta202 SRAPdddACourierA  A A @T|203 set_page_count(page, 1);SRAPdddACourierA  A A @T} 204 if (BAD_RANGE(zone,page))SRAPdddACourierA  A A @Tk205 BUG();SRAPdddACourierA  A A @Tv206 if (PageLRU(page))SRAPdddACourierA  A A @Tk207 BUG();SRAPdddACourierA  A A @Ty208 if (PageActive(page))SRAPdddACourierA  A A @Tk209 BUG();SRAPdddACourierA  A A @Tt210 return page; SRAPdddACourierA  A A @Td211 }SRAPdddACourierA  A A @Tp212 curr_order++;SRAPdddACourierA  A A @Tj 213 area++;SRAPdddACourierA  A A @T%214 } while (curr_order < MAX_ORDER);SRAPdddACourierA  A A @T/215 spin_unlock_irqrestore(&zone->lock, flags);SRAPdddACourierA  A A @Ta216 SRAPdddACourierA  A A @Tm217 return NULL;SRAPdddACourierA  A A @Tb218 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @TKThis routine fractures high order blocks to satisfy lower order allocationsSNAPdddA PA TimesNewRomanA @A8KA8 KT\Note that the page used to satisfy the allocation comes from the end of the fractured block.SXAPdddA TimesNewRomanA  A A @A8 AET]SRAPdddACourierA  A A @T(159 static inline struct page * expand (SRAPdddACourierA  A A @Tn zone_t *zone, SRAPdddACourierA  A A @Tq struct page *page,SRAPdddACourierA  A A @Tx160 unsigned long index, SRAPdddACourierA  A A @Th int low, SRAPdddACourierA  A A @Ti int high, SRAPdddACourierA  A A @Tr free_area_t * area)SRAPdddACourierA  A A @Tb161 {SRAPdddACourierA  A A @T$162 unsigned long size = 1 << high;SRAPdddACourierA  A A @Ta163 SRAPdddACourierA  A A @Tv164 while (high > low) {SRAPdddACourierA  A A @T|165 if (BAD_RANGE(zone,page))SRAPdddACourierA  A A @Tj 166 BUG();SRAPdddACourierA  A A @Tj 167 area--;SRAPdddACourierA  A A @Tj 168 high--;SRAPdddACourierA  A A @Tn169 size >>= 1;SRAPdddACourierA  A A @T:170 memlist_add_head(&(page)->list, &(area)->free_list);SRAPdddACourierA  A A @T#171 MARK_USED(index, high, area);SRAPdddACourierA  A A @Tq172 index += size;SRAPdddACourierA  A A @Tp173 page += size;SRAPdddACourierA  A A @Tc174 }SRAPdddACourierA  A A @T{175 if (BAD_RANGE(zone,page))SRAPdddACourierA  A A @Ti 176 BUG();SRAPdddACourierA  A A @Tn177 return page;SRAPdddACourierA  A A @Tb178 }SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T+156 #define MARK_USED(index, order, area) \SRAPdddACourierA  A A @T5157 __change_bit((index) >> (1+(order)), (area)->map)SRAPdddACourierA  A A @TD90 static __inline__ void __change_bit(int nr, volatile void * addr)SWAPdddA Courier (CE)A  A A @Tf91 {SWAPdddA Courier (CE)A  A A @Tz92 __asm__ __volatile__(SWAPdddA Courier (CE)A  A A @Tq93 "btcl %1,%0"SWAPdddA Courier (CE)A  A A @Tq94 :"=m" (ADDR)SWAPdddA Courier (CE)A  A A @Tq95 :"Ir" (nr));SWAPdddA Courier (CE)A  A A @Tf96 }SWAPdddA Courier (CE)A  A A @T]SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T]SRAPdddACourierA  A A @T-Efficient management of kernel memory objectsS;APdddA PA A @A8-A8 -A!8- TimesNewRomanT<S1APdddA A @TWThe kernel often needs to keep large arrays of data structures having fixed size but...S1APdddA A @T<S1APdddA A @Td(The fixed size in not often page size. S1APdddA A @T~BHaving to interact with the buddy system for each entity allocatedS1APdddA A @T~Bwastes space (esp. if the objects are much smaller than page size)S1APdddA A @Tu9wastes time since the buddy system is not esp. efficient.S1APdddA A @T<S1APdddA A @Tx<The slab allocator introduced in solaris provides a solutionS1APdddA A @T<S1APdddA A @T(The slab allocator pre-allocates caches S1APdddA A @A8 A8 !A8 !(T%Each cache contains one or more slabsS;APdddA  A A @A8  A8  %Tt Each slab holds multiple objectsS;APdddA  A A @A8  TEThe buddy system gets involved only when slabs are allocated or freedS;APdddA  A A @TFS;APdddA  A A @T~8/proc/slabinfo provides the state of the slab allocator.S;APdddA  A A @T@cache-name, num-active-objs, total-objs, object sizeS;APdddA  A A @T9num-active-slabs, total-slabs, num-pages-per-slabS;APdddA  A A @TcSXAPdddA TimesNewRomanA  A A @T3Name Active obj #obj Sz Obj ActSlb #Slb #Pg S1APdddA A @A8 3A!83 TimesNewRomanTAkmem_cache 68 68 232 4 4 1 : 252 126SgAPdddA TimesNewRomanAd A  A A @A8AA8ACourierTAclip_arp_cache 0 0 128 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAip_conntrack 172 253 352 22 23 1 : 124 62SaAPdddACourierAd A  A A @TAtcp_tw_bucket 160 160 96 4 4 1 : 252 126SaAPdddACourierAd A  A A @TAtcp_bind_bucket 339 339 32 3 3 1 : 252 126SaAPdddACourierAd A  A A @TAtcp_open_request 118 118 64 2 2 1 : 252 126SaAPdddACourierAd A  A A @TAinet_peer_cache 177 177 64 3 3 1 : 252 126SaAPdddACourierAd A  A A @TAip_fib_hash 15 226 32 2 2 1 : 252 126SaAPdddACourierAd A  A A @TAip_dst_cache 286 288 160 12 12 1 : 252 126SaAPdddACourierAd A  A A @TAarp_cache 150 150 128 5 5 1 : 252 126SaAPdddACourierAd A  A A @TAuhci_urb_priv 1 67 56 1 1 1 : 252 126SaAPdddACourierAd A  A A @TAblkdev_requests 5376 5400 96 135 135 1 : 252 126SaAPdddACourierAd A  A A @TAnfs_read_data 117 150 384 12 15 1 : 124 62SaAPdddACourierAd A  A A @TAnfs_write_data 80 80 384 8 8 1 : 124 62SaAPdddACourierAd A  A A @TAnfs_page 320 320 96 8 8 1 : 252 126SaAPdddACourierAd A  A A @TAdnotify cache 0 0 20 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAfile lock cache 126 126 92 3 3 1 : 252 126SaAPdddACourierAd A  A A @TAfasync cache 1 202 16 1 1 1 : 252 126SaAPdddACourierAd A  A A @TAuid_cache 133 226 32 2 2 1 : 252 126SaAPdddACourierAd A  A A @TAskbuff_head_cache 426 552 160 23 23 1 : 252 126SaAPdddACourierAd A  A A @TAsock 165 387 832 36 43 2 : 124 62SaAPdddACourierAd A  A A @TAsigqueue 261 261 132 9 9 1 : 252 126SaAPdddACourierAd A  A A @TAcdev_cache 3783 3835 64 65 65 1 : 252 126SaAPdddACourierAd A  A A @TAbdev_cache 10974 10974 64 186 186 1 : 252 126SaAPdddACourierAd A  A A @TAinode_cache 273084 273952 480 34240 34244 1 : 124 62SaAPdddACourierAd A  A A @TAdentry_cache 275238 276750 128 9225 9225 1 : 252 126SaAPdddACourierAd A  A A @TAfilp 2613 2640 96 66 66 1 : 252 126SaAPdddACourierAd A  A A @TAnames_cache 12 12 4096 12 12 1 : 60 30SaAPdddACourierAd A  A A @TAbuffer_head 24748 25440 96 636 636 1 : 252 126SaAPdddACourierAd A  A A @TAmm_struct 210 210 128 7 7 1 : 252 126SaAPdddACourierAd A  A A @TAvm_area_struct 1471 1770 64 30 30 1 : 252 126SaAPdddACourierAd A  A A @TAfs_cache 236 236 64 4 4 1 : 252 126SaAPdddACourierAd A  A A @TAfiles_cache 117 117 416 13 13 1 : 124 62SaAPdddACourierAd A  A A @TAsignal_act 99 99 1312 33 33 1 : 60 30SaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @TvSkAPdddA PACourierAd A  A A @TCThe following general purpose slabs are used for kmalloc() requestsS;APdddA  A A @A8 1:TcSXAPdddA TimesNewRomanA  A A @T2Name Active obj #obj Sz Obj ActSlb #Slb #PgSaAPdddACourierAd A  A A @A82d A!82 TimesNewRomanTAsize-131072(DMA) 0 0 131072 0 0 32 : 0 0SaAPdddACourierAd A  A A @TAsize-131072 0 0 131072 0 0 32 : 0 0SaAPdddACourierAd A  A A @TAsize-65536(DMA) 0 0 65536 0 0 16 : 0 0SaAPdddACourierAd A  A A @TAsize-65536 1 1 65536 1 1 16 : 0 0SaAPdddACourierAd A  A A @TAsize-32768(DMA) 0 0 32768 0 0 8 : 0 0SaAPdddACourierAd A  A A @TAsize-32768 0 0 32768 0 0 8 : 0 0SaAPdddACourierAd A  A A @TAsize-16384(DMA) 0 0 16384 0 0 4 : 0 0SaAPdddACourierAd A  A A @TAsize-16384 0 0 16384 0 0 4 : 0 0SaAPdddACourierAd A  A A @TAsize-8192(DMA) 2 2 8192 2 2 2 : 0 0SaAPdddACourierAd A  A A @TAsize-8192 1 1 8192 1 1 2 : 0 0SaAPdddACourierAd A  A A @TAsize-4096(DMA) 0 0 4096 0 0 1 : 60 30SaAPdddACourierAd A  A A @TAsize-4096 29 29 4096 29 29 1 : 60 30SaAPdddACourierAd A  A A @TAsize-2048(DMA) 0 0 2048 0 0 1 : 60 30SaAPdddACourierAd A  A A @TAsize-2048 114 114 2048 57 57 1 : 60 30SaAPdddACourierAd A  A A @TAsize-1024(DMA) 2 4 1024 1 1 1 : 124 62SaAPdddACourierAd A  A A @TAsize-1024 212 216 1024 54 54 1 : 124 62SaAPdddACourierAd A  A A @TAsize-512(DMA) 0 0 512 0 0 1 : 124 62SaAPdddACourierAd A  A A @TAsize-512 288 288 512 36 36 1 : 124 62SaAPdddACourierAd A  A A @TAsize-256(DMA) 0 0 256 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAsize-256 300 300 256 20 20 1 : 252 126SaAPdddACourierAd A  A A @TAsize-128(DMA) 0 0 128 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAsize-128 1110 1110 128 37 37 1 : 252 126SaAPdddACourierAd A  A A @TAsize-64(DMA) 0 0 64 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAsize-64 1003 1003 64 17 17 1 : 252 126SaAPdddACourierAd A  A A @TAsize-32(DMA) 0 0 32 0 0 1 : 252 126SaAPdddACourierAd A  A A @TAsize-32 4859 4859 32 43 43 1 : 252 126SaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @TlSaAPdddACourierAd A  A A @TSSHAPdddACourierA A @T?Each of these caches is described by the kmem_cache_s structureS;APdddA PA A @A8 )5A8 5?TFS;APdddA  A A @Tn(The three lists describe slabs that are S;APdddA  A A @T\full of active objectsS;APdddA  A A @Tk%have allocated objects and free slotsS;APdddA  A A @Tg!have no allocated objects at all.S;APdddA  A A @TSSHAPdddACourierA A @Tl189 struct kmem_cache_s {SHAPdddACourierA A @Tr190 /* 1) each alloc & free */SHAPdddACourierA A @T|)191 /* full, partial first, then free */SHAPdddACourierA A @Tv#192 struct list_head slabs_full;SHAPdddACourierA A @Ty&193 struct list_head slabs_partial;SHAPdddACourierA A @Tv#194 struct list_head slabs_free;SHAPdddACourierA A @Ty&195 unsigned int objsize;SHAPdddACourierA A @T:196 unsigned int flags; /* constant flags */SHAPdddACourierA A @T>197 unsigned int num; /* # of objs per slab */SHAPdddACourierA A @To198 spinlock_t spinlock;SHAPdddACourierA A @TSSHAPdddACourierA A @Tx%203 /* 2) slab additions /removals */SHAPdddACourierA A @Tx%204 /* order of pgs per slab (2^n) */SHAPdddACourierA A @Ty&205 unsigned int gfporder;SHAPdddACourierA A @TW206 SHAPdddACourierA A @Tz'207 /* force GFP flags, e.g. GFP_DMA */SHAPdddACourierA A @Ty&208 unsigned int gfpflags;SHAPdddACourierA A @TV209SHAPdddACourierA A @T\ S'APdddA @A8A8CourierT.Each slab is described by the slab_t structureS1APdddA A @A8 %A8 %.TFS;APdddA  A A @T}s_mem addresses are virtualS;APdddA  A A @A8 A8 Tlfree is an object index S;APdddA  A A @A8 T6These are somehow used to chain free objects together.S;APdddA  A A @A8  T<S1APdddA A @TY147 /*SHAPdddACourierA A @T_ 148 * slab_tSHAPdddACourierA A @TX149 *SHAPdddACourierA A @TS150 * Manages the objs in a slab. Placed either at the beginning of mem allocatedSHAPdddACourierA A @T5151 * for a slab, or allocated from an general cache.SHAPdddACourierA A @TQ152 * Slabs are chained into three list: fully used, partial, fully free slabs.SHAPdddACourierA A @TY153 */SHAPdddACourierA A @Tn154 typedef struct slab_s {SHAPdddACourierA A @Tn155 struct list_head list;SHAPdddACourierA A @Ts 156 unsigned long colouroff;SHAPdddACourierA A @TC157 void *s_mem; /* including colour offset */SHAPdddACourierA A @TC158 unsigned int inuse; /* num of objs active in slab */SHAPdddACourierA A @TC159 kmem_bufctl_t free; /* This is an int "index" */SHAPdddACourierA A @T` 160 } slab_t;SHAPdddACourierA A @TU16SHAPdddACourierA A @TSSHAPdddACourierA A @T$The kmem_cache _s structure used to describe a cache is itself allocated from the cache_cache which is statically initialized as follows.SXAPdddA PA TimesNewRomanA A @A8 A8 RA8 R^A8 ^T2S'APdddA @T2355 /* internal cache of cache description objs */SHAPdddACourierA A @Tz'356 static kmem_cache_t cache_cache = {SHAPdddACourierA A @T;357 slabs_full: LIST_HEAD_INIT(cache_cache.slabs_full),SHAPdddACourierA A @T>358 slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial),SHAPdddACourierA A @T;359 slabs_free: LIST_HEAD_INIT(cache_cache.slabs_free),SHAPdddACourierA A @T|)360 objsize: sizeof(kmem_cache_t),SHAPdddACourierA A @Tt!361 flags: SLAB_NO_REAP,SHAPdddACourierA A @Tz'362 spinlock: SPIN_LOCK_UNLOCKED,SHAPdddACourierA A @Tv#363 colour_off: L1_CACHE_BYTES,SHAPdddACourierA A @Tt!364 name: "kmem_cache",SHAPdddACourierA A @TY365 };SHAPdddACourierA A @TW366 SHAPdddACourierA A @TYSNAPdddA TimesNewRomanA A @T The slab_s structures used to describe a slab contain not only the data items shown in the structure itself but also a table of kmem_buf_ctl_t items (which are actually ints) with one entry per object in the slab. Thus the slab control structure is variable length. SNAPdddA TimesNewRomanA A @A8  A8  A8 A8  TSSHAPdddACourierA A @TYSNAPdddA TimesNewRomanA A @T,Allocate a new object from an existing cacheSXAPdddA PA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @T-1318 static inline void * __kmem_cache_alloc(SHAPdddACourierA A @Tv# kmem_cache_t *cachep, int flags)SHAPdddACourierA A @TY1319 {SHAPdddACourierA A @Tr1320 unsigned long save_flags;SHAPdddACourierA A @Td1321 void* objp;SHAPdddACourierA A @TX1322 SHAPdddACourierA A @TSSHAPdddACourierA A @TEnsures SLAB_DMA bit of the cachep->gfpflags is consistent with the GFP_DMA setting of flags. The try_again tag is used if we are forced to allocate a new slab to the cache. SNAPdddA TimesNewRomanA A @A8 bmTYSNAPdddA TimesNewRomanA A @T~+1323 kmem_cache_alloc_head(cachep, flags);SHAPdddACourierA A @Tb1324 try_again:SHAPdddACourierA A @Tt!1325 local_irq_save(save_flags);SHAPdddACourierA A @Ti1326 #ifdef CONFIG_SMPSHAPdddACourierA A @Ti : S'APdddA @A8A8CourierT] 1346 #elseSHAPdddACourierA A @T}*1347 objp = kmem_cache_alloc_one(cachep);SHAPdddACourierA A @TSSHAPdddACourierA A @TSSHAPdddACourierA A @T1263 #define kmem_cache_alloc_one(cachep) 1264 ({ \SHAPdddACourierA A @T:1265 struct list_head * slabs_partial, * entry; \SHAPdddACourierA A @T:1266 slab_t *slabp; \SHAPdddACourierA A @Ty&1267 SHAPdddACourierA A @Tj SHAPdddACourierA A @T<See if there are any partially allocated slabs in this cacheSNAPdddA TimesNewRomanA A @T2S'APdddA @T:1268 slabs_partial = &(cachep)->slabs_partial; \SHAPdddACourierA A @T:1269 entry = slabs_partial->next; \SHAPdddACourierA A @TSSHAPdddACourierA A @TYSNAPdddA TimesNewRomanA A @T8The standard list manager is used so that entry == slabs_partial is true only if the slabs_partial list is empty. If so see if there are any completely free slabs in this cache.S_APddHdA TimesNewRomanA A @A@. A8+BCourierTYSNAPdddA TimesNewRomanA A @T:1270 if (unlikely(entry == slabs_partial)) { \SHAPdddACourierA A @T61271 struct list_head * slabs_free; \SHAPdddACourierA A @T61272 slabs_free = &(cachep)->slabs_free; \SHAPdddACourierA A @T61273 entry = slabs_free->next; \SHAPdddACourierA A @TSSHAPdddACourierA A @TUIf no completely free slabs either, then it will be necessary to allocate a new slab SNAPdddA TimesNewRomanA A @TSSHAPdddACourierA A @T61274 if (unlikely(entry == slabs_free)) \SHAPdddACourierA A @T21275 goto alloc_new_slab; \SHAPdddACourierA A @T2S'APdddA @T]SRAPdddA PACourierA A @TgIf there is a completely free slab move it from free list and add it back to the partially full list. SNAPdddA TimesNewRomanA A @T2S'APdddA @T61276 list_del(entry); \SHAPdddACourierA A @T61277 list_add(entry, slabs_partial); \SHAPdddACourierA A @T:1278 } \SHAPdddACourierA A @TW1279SHAPdddACourierA A @TSSHAPdddACourierA A @T?When we arrive here then entry is pointing to a non-empty slab.S'APdddA @A8?A!8? TimesNewRomanT;Note the macro based assignment in which the value returned by kmem_cache_alloc_one_tail() is assigned to the objp lvalue in the macro call far above. S'APdddA @A8A!8 TimesNewRomanA8 ?ZA8 nrA8CourierT:1280 slabp = list_entry(entry, slab_t, list); \SHAPdddACourierA A @T:1281 kmem_cache_alloc_one_tail(cachep, slabp); \SHAPdddACourierA A @TZ1282 })SHAPdddACourierA A @TW1283SHAPdddACourierA A @TSSHAPdddACourierA A @TX1348 SHAPdddACourierA A @Tw$1349 local_irq_restore(save_flags);SHAPdddACourierA A @Te1350 return objp;SHAPdddACourierA A @TSSHAPdddACourierA A @T[Try to allocate a new slab for the cache and if that works, go back to try_again which was SNAPdddA TimesNewRomanA A @A8 GQA8 Q[Tqdefined above.SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @Tg1351 alloc_new_slab:SHAPdddACourierA A @TSSHAPdddACourierA A @Tw$1356 local_irq_restore(save_flags);SHAPdddACourierA A @T|)1357 if (kmem_cache_grow(cachep, flags))SHAPdddACourierA A @T@1358 /* Someone may have stolen our objs. Doesn't matter, we'llSHAPdddACourierA A @Tt!1359 * just come back here again.SHAPdddACourierA A @TZ1360 */SHAPdddACourierA A @Ti1361 goto try_again;SHAPdddACourierA A @Te1362 return NULL;SHAPdddACourierA A @TY1363 }SHAPdddACourierA A @TSSHAPdddACourierA A @TSSHAPdddACourierA A @T]SRAPdddA PACourierA A @TSSHAPdddACourierA A @T=The details of internal object managment are fairly nasty... SNAPdddA TimesNewRomanA A @TNObjects are managed either on slab (small objects) or off slab (large objects)SNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TD 692 /* Determine if the slab management is 'on' or 'off' slab. */SHAPdddACourierA A @Tx% 693 if (size >= (PAGE_SIZE>>3))SHAPdddACourierA A @Tb 694 /*SHAPdddACourierA A @TD 695 * Size is large, best to place the slab management objSHAPdddACourierA A @T? 696 * off-slab (should allow better packing of objs).SHAPdddACourierA A @Tc 697 */SHAPdddACourierA A @Tx% 698 flags |= CFLGS_OFF_SLAB;SHAPdddACourierA A @TSSHAPdddACourierA A @TbThis macro appears to increment a pointer to a slab_t structure by the length of a slab_t struct, SNAPdddA TimesNewRomanA A @A8 /5A8 SZA8 ZaTHIt is used to access the object management list associated with a slab. SNAPdddA TimesNewRomanA A @T9k_mem_bufctl_t is an int that represents an object index.S'APdddA @A8A!8 TimesNewRomanA8 A8 A8 9T]SRAPdddACourierA  A A @Ts 162 #define slab_bufctl(slabp) \SHAPdddACourierA A @T1163 ((kmem_bufctl_t *)( ((slab_t*)slabp)+1) )SHAPdddACourierA A @T2S'APdddA @THslabp->free contains the index of the first free object within the slab.SXAPdddA TimesNewRomanA  A A @A8  HT9slabp->mem is a pointer to the start of the object store.SXAPdddA TimesNewRomanA  A A @A8  9T)The free objects are managed as a stack. SXAPdddA TimesNewRomanA  A A @A8 (T2S'APdddA @T41222 static inline void * kmem_cache_alloc_one_tail(SHAPdddACourierA A @Tj kmem_cache_t *cachep,SHAPdddACourierA A @Tg1223 slab_t *slabp)SHAPdddACourierA A @TY1224 {SHAPdddACourierA A @Td1225 void *objp;SHAPdddACourierA A @TX1226 SHAPdddACourierA A @Ts 1227 STATS_INC_ALLOCED(cachep);SHAPdddACourierA A @Tr1228 STATS_INC_ACTIVE(cachep);SHAPdddACourierA A @Tp1229 STATS_SET_HIGH(cachep);SHAPdddACourierA A @TX1230 SHAPdddACourierA A @TYSNAPdddA TimesNewRomanA A @T-Free object managment appears to be a table of ints in which value[index] = index of the next free object and slabp->free points to the first free object. SNAPdddA TimesNewRomanA A @A8 /3A8 3nA8 nzA8 zTcSXAPdddA TimesNewRomanA  A A @Tn1231 /* get obj pointer */SHAPdddACourierA A @Th1232 slabp->inuse++;SHAPdddACourierA A @T81233 objp = slabp->s_mem + slabp->free*cachep->objsize;SHAPdddACourierA A @T21234 slabp->free=slab_bufctl(slabp)[slabp->free];SHAPdddACourierA A @TX1235 SHAPdddACourierA A @TSSHAPdddACourierA A @T]SRAPdddA PACourierA A @T@If we just consumed the last object in the list move the slab.. SXAPdddA TimesNewRomanA  A A @A8 ?TSSHAPdddACourierA A @T01236 if (unlikely(slabp->free == BUFCTL_END)) {SHAPdddACourierA A @Tq1237 list_del(&slabp->list);SHAPdddACourierA A @T31238 list_add(&slabp->list, &cachep->slabs_full);SHAPdddACourierA A @TZ1239 }SHAPdddACourierA A @Ts 1252 objp += BYTES_PER_WORD; SHAPdddACourierA A @Te1255 return objp;SHAPdddACourierA A @TY1256 }SHAPdddACourierA A @TSSHAPdddACourierA A @TsFreeing of a single objectSNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TP1394 static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)SHAPdddACourierA A @TY1395 {SHAPdddACourierA A @Tg1396 slab_t* slabp;SHAPdddACourierA A @TX1397 SHAPdddACourierA A @Tx%1398 CHECK_PAGE(virt_to_page(objp));SHAPdddACourierA A @TSSHAPdddACourierA A @T01405 slabp = GET_PAGE_SLAB(virt_to_page(objp));SHAPdddACourierA A @T/ : (debugging stuff deleted) S'APdddA @A8/A8/CourierTYSNAPdddA TimesNewRomanA A @THHere we insert the old object into the head of the free list of the slabSNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TOThe object number is computed by dividing the object offset by the object size.S'APdddA @A8OA!8O TimesNewRomanTXThe existing first free object number is copied into the array slot index of this objectSNAPdddA TimesNewRomanA A @TGThen the slab's free list start address is set to index of this object.SNAPdddA TimesNewRomanA A @TYSNAPdddA TimesNewRomanA A @TY1430 {SHAPdddACourierA A @T?1431 unsigned int objnr = (objp-slabp->s_mem)/cachep->objsize;SHAPdddACourierA A @TX1432 SHAPdddACourierA A @T.1433 slab_bufctl(slabp)[objnr] = slabp->free;SHAPdddACourierA A @Tm1434 slabp->free = objnr;SHAPdddACourierA A @TY1435 }SHAPdddACourierA A @Tr1436 STATS_DEC_ACTIVE(cachep);SHAPdddACourierA A @TX1437 SHAPdddACourierA A @TSSHAPdddACourierA A @T]SRAPdddA PACourierA A @ThSince something was just freed a full slab may now be partial (or empty) and a partial slab may be emptySNAPdddA TimesNewRomanA A @TSSHAPdddACourierA A @Tp1438 /* fixup slab chains */SHAPdddACourierA A @TY1439 {SHAPdddACourierA A @Tr1440 int inuse = slabp->inuse;SHAPdddACourierA A @Ty&1441 if (unlikely(!--slabp->inuse)) {SHAPdddACourierA A @T,1442 /* Was partial or full, now empty. */SHAPdddACourierA A @Tq1443 list_del(&slabp->list);SHAPdddACourierA A @T31444 list_add(&slabp->list, &cachep->slabs_free);SHAPdddACourierA A @T21445 } else if (unlikely(inuse == cachep->num)) {SHAPdddACourierA A @Ti1446 /* Was full. */SHAPdddACourierA A @Tq1447 list_del(&slabp->list);SHAPdddACourierA A @T61448 list_add(&slabp->list, &cachep->slabs_partial);SHAPdddACourierA A @TZ1449 }SHAPdddACourierA A @TY1450 }SHAPdddACourierA A @TY1451 }SHAPdddACourierA A @TSSHAPdddACourierA A @THThis routine is called by kmem_cache_grow() when a new slab is required SXAPdddA PA TimesNewRomanA A @A8 +A8 +HTSIt can provide some insight into understanding on slab / off slab object managemtn.SXAPdddA TimesNewRomanA  A A @TSSHAPdddACourierA A @TX1010 SHAPdddACourierA A @T41011 /* Get the memory for a slab management obj. */SHAPdddACourierA A @T11012 static inline slab_t * kmem_cache_slabmgmt (SHAPdddACourierA A @Tj kmem_cache_t *cachep,SHAPdddACourierA A @Te1013 void *objp, SHAPdddACourierA A @Te int colour_off, SHAPdddACourierA A @Te int local_flags)SHAPdddACourierA A @TY1014 {SHAPdddACourierA A @Tg1015 slab_t *slabp;SHAPdddACourierA A @TX1016 SHAPdddACourierA A @TYSNAPdddA TimesNewRomanA A @TGThe OFF_CACHE macro just test a flag bit in the kmem_cache_s structure.SNAPdddA TimesNewRomanA A @A8 0A8 0<A8 <GTcSXAPdddA TimesNewRomanA  A A @TRFor off slab managment the managememt area is allocated from the kmem_cache cache.SXAPdddA TimesNewRomanA  A A @TSSHAPdddACourierA A @Tp1017 if (OFF_SLAB(cachep)) {SHAPdddACourierA A @T,1018 /* Slab management obj is off-slab. */SHAPdddACourierA A @TH1019 slabp = kmem_cache_alloc(cachep->slabp_cache, local_flags);SHAPdddACourierA A @Tm1020 if (!slabp)S'APdddA @A8A8CourierTg1021 return NULL;SHAPdddACourierA A @TcSXAPdddA TimesNewRomanA  A A @T)For on-slab managment the managememt area is suballocated from the area normally used to hold objects. The colour_off field is then incremented so as include the slab management area.SXAPdddA TimesNewRomanA  A A @A8 lvTSSHAPdddACourierA A @Ta1022 } else {SHAPdddACourierA A @Tm1023 /* FIXME: change toSHAPdddACourierA A @Tf1024 slabp = objpSHAPdddACourierA A @Tr1025 * if you enable OPTIMIZESHAPdddACourierA A @T\ 1026 */SHAPdddACourierA A @Tr1027 slabp = objp+colour_off;SHAPdddACourierA A @T11028 colour_off += L1_CACHE_ALIGN(cachep->num *SHAPdddACourierA A @T01029 sizeof(kmem_bufctl_t) + sizeof(slab_t));SHAPdddACourierA A @TZ1030 }SHAPdddACourierA A @Tj1031 slabp->inuse = 0;SHAPdddACourierA A @Tw$1032 slabp->colouroff = colour_off;SHAPdddACourierA A @Tx%1033 slabp->s_mem = objp+colour_off;SHAPdddACourierA A @TX1034 SHAPdddACourierA A @Tf1035 return slabp;SHAPdddACourierA A @TY1036 }SHAPdddACourierA A @TX1037 SHAPdddACourierA A @TSSHAPdddACourierA A @TOThis routine is called by kmem_cache_grow() just after it calls kmem_cache_mgmtSXAPdddA PA TimesNewRomanA A @A8 +A8 +@A8 @OT&The free object chains are setup here.SXAPdddA TimesNewRomanA  A A @TcSXAPdddA TimesNewRomanA  A A @TD1038 static inline void kmem_cache_init_objs (kmem_cache_t * cachep,SHAPdddACourierA A @T.1039 slab_t * slabp, unsigned long ctor_flags)SHAPdddACourierA A @TY1040 {SHAPdddACourierA A @T^ 1041 int i;SHAPdddACourierA A @TX1042 SHAPdddACourierA A @T|)1043 for (i = 0; i < cachep->num; i++) {SHAPdddACourierA A @T31044 void* objp = slabp->s_mem+cachep->objsize*i;SHAPdddACourierA A @T2S'APdddA @TX1053 SHAPdddACourierA A @T[1054 /*SHAPdddACourierA A @T<1055 * Constructors are not allowed to allocate memory fromSHAPdddACourierA A @T81056 * the same cache which they are a constructor for.SHAPdddACourierA A @T81057 * Otherwise, deadlock. They must also be threaded.SHAPdddACourierA A @T[1058 */SHAPdddACourierA A @Tk1059 if (cachep->ctor)SHAPdddACourierA A @T/1060 cachep->ctor(objp, cachep, ctor_flags);SHAPdddACourierA A @TSSHAPdddACourierA A @Tv#1075 slab_bufctl(slabp)[i] = i+1;SHAPdddACourierA A @TZ1076 }SHAPdddACourierA A @T~+1077 slab_bufctl(slabp)[i-1] = BUFCTL_END;SHAPdddACourierA A @Ti1078 slabp->free = 0;SHAPdddACourierA A @TY1079 }SHAPdddACourierA A @TSSHAPdddACourierA A @JGeneric PrinterSGENPRT PostScriptH`Tl`Tld,,lprdefault_queueSGENPRT7 UxxV88/\\?""t/=U&2P  *U&y0?-B&B& B!&B6&BK& E# BW& E# Bc& E# Bo& E! B{& E#  B & E!  B & E#  B & E#  B &  B & B& E# B& E# B& E# B& E# B& E# B& E# B & E# B& B#& B/& E# B;& E# BG& E# BS& E# B_& Bk& Bw& E# B& E# B & E#  B!& E# !B"& "B#& E# #B$& E# $B%& E# %B&& E# &B'& E# 'B(& E# (B)& E! )B+& E! *B,& E! +B-& E! ,B+.& E! -,U6&'& F @& g>/=U&2p  U&y0?(B& .B & /B& E# 0B$& E# 1B0&2BE&3BZ&4Bo& E# 5B{& E# 6B & E# 7B &8B &9B &:Bt &;BZ&<B@&=B&&>B &?B&@@B&AAB&BBB&CCB&DDBp&EEBV&FFB<&GGB"&HHB&IIB&JJB&KKB&LLB&MMB&NNBl&OOBR &PPB8!&QQB"&RRB#&SSB#&TTB$& UU,U6&'& F @& }/=U&2P  U&y0?B&VVB&WWB& XXB& E# YYB& E# ZZB& E! [[B+& E! \\B7& E! ]]BC& E! ^^BO & E# __B[ & E# ``Bg & E! aaBs & E! bbB & E! ccB& E# ddB& E# eeB& E! ffB& E! ggB& E# hhB& E! iiB& E! jjB& E! kkB& E# llB& E! mmB& E! nnB& E! ooB& ppB'& qq,U6&'& F @& D%/=U&2p  U&y0?'B& rrB &ssB!&ttB6& E# uuBB&E#vvBW& E# wwBc& E! xxBo& E! yyB{& E! zzB &E!{{B & E# ||B &E#}}B & E! ~~B & E! B& E! B& E! B& E! B& E! B&E!B&E!B0& E! B<& E! BH& Ep0 BT& Ep0 B`& Bl&B&B& E# B& E# B& E# B& E! B & E! B!& E! B"& E! B#& E# B$& E# B&& E# B'& E# B(& E# ,U6&'& F @& Ё%/=U&2P  4U&y0?)B&B&B*& E# B6& E# BB& E# BN& E# BZ& E# Bf& E! Br& E! B~ & E! B & E! B & E! B & E# B & E! B&E!B&E!B&E!Bl&E!BR&B8& E# BD& E# BP& E# B\& E# Bh& E# Bt&B&B& E# B& E# B& E# B& E# B& E# B&B &B"& E# B#& E# B$& E# B(%& E# B4&& E# B@'& E# BL(& E# BX)& E# ,U6&'& F @& %:/=U&2p  ¯U&y0?B&B& B!& E# B-& E# B9& E# BE&BZ&B&B&B&BV &B7 &B &B &~B3 &B &B&Bp&B/&B&B&Bl&B+&B&B&B& B&B& E# B& E# B& E# B&E#,U6&'& F @& %y/=U&2P  U&y0?$B&E#B& B& B& E# B & E# B& E! B"& E! B.&E!B5& E! BA & Ep0 BM & Ep0 BY & E! Be & E! Bq & E# B}& E# B& E# B&E!B& E! B& E! B& E! B& E! B& E! B& E! B&E!B&E!B&E!B&E!B|&E!Bb&E!Bi&E#B& E# B & E# B!& E# B"& Ep0 B#& Ep0 B$& Ep0 ,U6&'& F @& {%/=U&2p  .U&y0?B& Ep0 B & E# B& E!  B$& E!  B0& Ep0   B<& Ep0   BH& E!   BT& E!  B`& Ep0  Bl & Ep0 Bx & Ep0 B & Ep0 B & Ep0 B & Ep0 B& Ep0 B& Ep0 B& Ep0 B& Ep0 B&E#B& E# ,U6&'& F @& Ћ%/=U&2P  >U&y0?4B&B& E# B"& E# B.& E# B:& E#  BF& !BR&"B8& #B&!$B &"%B &#&B &$'B &%(B &&)B &'*Bh&(+BN&),B4&*-B&+.B&,/B&-0B&.1B&/2B&03B~&14Bd&25BJ&36B0& 47B<&58B"&69B&7:B&8;B&9<B& :=B& ;>B & <?B!& =@B"&>AB#&?BB$&@CB%&ADB&&BEBh'&CFBN(&DGB4)&EHB*&FIB+&GJB+&HKB,&ILB-&JMB.&KNB~/&LO,U6&'& F @& :%6/=U&2p  U&y0?1B& MPB &NQB&E#OSB+&PTB&QUB&RVB&SWB&TXB&UYB &VZBu &W[B[ &X\BA &Y]B' &Z^B &[_B&\`B&]aB&^bB&_cB&`dBq&aeBW&bfB=&cgB#&diB&ejB&fkB&glB&hmB&inBm&joBS&kpB9&lqB&mrB &nsB &otB!&puB"&qvB#&rwB$&sxBi%&tyBO&&uzB5'&v|BM)& w}BY*&x~B?+&yB%,&zB -&{B-& |B.& },U6&'& F @& Ч%u/=U&2P  ZU&y0?*B&~B& B&B&B&B&B&B&B&Bi &BO &B5 &B &B &B &B&B&B&Be&BK& BW&B=&B#&B &B&B&B&B&B& B& B&B&Bk&BQ &B7!&B"&B#&B#&B$&B%&B&&B'&,U6&'& F @& S%Դ/=U&2p  U&y0?B& B & B&B&B&B&B&B&B|&Bb&BH &B. &B &B &B &B &B&B&Bx&B^&BD&B*&B&B&B&,U6&'& F @& *%/=U&2P  U&y0?,B&B& B& E# B& E# B & E# B& E# B"& E# B.& E# B:& E# BF & E! BR & E! B^ & E! Bj & E! Bv & E! B&E#Bh&BN&B4&B&B&B&B&B&B&B~&Bd&BJ&B0&B&B&B&B&B&Bz &B`!&BF"&B,#&B$&B$&B%&B&&B'&B(&Bv)&,U6&'& F @&  %2/=U&2p  ¾U&y0?/B&B& B& B&B&B&B&B&B|&Bb&BH &B. &B &B &B &B &B&B&Bx&B^& BD& B*& B& B& B&B&B&B&Bt& BZ& B@& B&& B & B&B&B&B &B!&Bp"&BV#&B<$&B&& B&&!B'&"B(& #B)& $B*& %,U6&'& F @& В%q/=U&2P  EU&y0?4B&&B&'B*&E#(B@& E# )BL& E#  *BX& E# !+Bd& ",Bp&#-B&$.B&%/Bt &&0B &'1B &(2Bx &)3B$ &*4B &+5B| &,6B(&-7B&.8B&/9B,&0:B&1;B&2<B0&X3>B&4?B4&5@B&6AB&7BB8&E#8CB&9DB&:EB&;FB&<GB&=HB&>IB&?JBh&@KBN&ALB4&BMB &CNB!& DOB "& EPB#&FRB$&GSB%&HTB&&IUB'&JVB|(&KWBb)&LXBH*&MYB.+&NZB,&O[,U6&'& F @& _%İ/=U&2p  U&y0?%B& P\B & E# Q]B& E# R^B$&E#S`B<& E# TaBH&UbB.&VcB&WdB&XeB &YfB &ZgB &[hB &\iBx &]jB^&^kBD&_lB*&`mB&anB&boB&cpB&dqB&erB&fsBt&gtBZ&huB@&ivB&&jwB & kxB&lzB0& m{B<&n}B &o~B &pB!&qB"&rB#& sB$&t,U6&'& F @& Y%/=U&2P   U&y0?$B&uB& vB&wB&xB&yBj&zBP&{B6&|B&}B&~B&B &B & B & E# B &E#B& E# B& E# B& E# B& E# B&B&B&B&B&B&Bx&B^&BD&B*&B&B&B&B&B&B &Bt!&,U6&'& F @& Y%./=U&2p   U&y0?.B& B & E# B& E# B$& E# B0&B&B&B&B&Bt&BZ &B@ &B& &B &B &B &B&B&B&Bp&BV&B<& BH& BT& E# B`& E# Bl& E# Bx& E# B& E# B& E# B& E# B& E# B& E# B& E# B& E# B &B!&B"&B#&Bp$&BV%&B<&&B"'&B(&B(&B)&B*&,U6&'& F @& %m/=U&2P  ŒU&y0?B& B & B& B$& B0&E#B&B&B&B&B&B &Bz &B` &BF &B, &B&B&B&B&B&B&Bv&B\&BB& BN& BZ&E#B@&B&&B &B&B&,U6&'& F @& Д%/=U&2p  GU&y0?(B&B& B& B&E#B&B&B&B&B|& B& B & B & E# B & E# B & B &B&B&Bv&B\&BB& B(& B& B& B& B&B&B&Br&BX&B>&B$&B &B&B&B&B & B!& Bn"& BT#& B:$& ,U6&'& F @& %/=U&2P  §U&y0? B&B& B&  B& !B &"B&#B&$B&%B&&B&'Bn &(BT &)B: &*B &+B &,B &-B& .B& /B&  0B&!1B&"2B&#3B&$4B& %5B& &6B& E# '7B& E# (8B&E#)9B&*:B&+;Bp&,<BV&-=,U6&'& F @& Ш%*/=U&2p  [U&y0?)B&.>B& /?B& 0@B& 1AB & 2BB&E#3CB&4DB&5EB&6FB&7GB &8HBz & E# 9IB & :JB & ;KB & <LB&=NB& E# >OB&?PB&@QB&ARB&BSBf&CUB2&DVB&EWB&FXB&GYB&HZB&I[B&J\B|&K]Bb&L^BH&M_B. &N`B!&OaB!&PbB"&QcB#&RdB$&SeB%&TfBx&&UgB^'&Vh,U6&'& F @& е%i/=U&2P  hU&y0?*B& WiB & XjB&YkB&ZlB&[mB&\nB&]oB&^pB|&_qBb&`rBH &asB. &btB &cuB &dvB &ewB &fxB&gyB&hzBx&i{B^&j|BD&k}B*&l~B&mB&nB&oB&pB&qB&rBt&sBZ&tB@&uB&&vB &wB&xB&yB&zB &{B!&|Bp"&}BV#&E#~B<$&E#B"%&,U6&'& F @& !%/=U&2p  U&y0?8B&B& B!& B-& E# B9& E# BE& E# BQ& E! B]& E! Bi& E# Bu & B & B & E# B & E# B & E# B& E# B& E# B& B& E# B& E# B& E# B&B&B&B&Br&B1&B&B&Bn&B-&B&B&Bj&B)&B&B &Bf!&B%"&B"&B#&Bb$&B!%&B%&B&&B^'&B(&B(&B)&BZ*&B+&B+&B,&BV-&B.&B.&B/&,U6&'& F @& %/=U&2P  »U&y0?!B&B& B& E# B& B&B&Ba&B &B&B&B]&B &B &B &BY &B &B &B &BU&B&B&B&BQ&B&B&B&BM&B &B&B&BI&E#B&E#B&,U6&'& F @& P%&/=U&2p  U&y0?0B& B & B& E# B$& E! B0& E! B<& E! BH&B.&B&B&B &B &B &B &Bx &B^&BD&B*&B&B&B&B&B&B&Bt&BZ&B@& BL& BX& E# Bd& E#  Bp& E#  B|&  B& Bn& BT &B:!&B#&B#&B%&B&&B'&Bj(&BP)&B6*&B+&B,&B,&B-& ,U6&'& F @& %e/=U&2P  zU&y0?B& B&  B& !B& "B&#B&$B&%B&&B&'Bi &(BO &)B5 &*B &+B &,B & -B&$0B&1B& 2,U6&'& F @& %/=U&2p  uU&y0?+B& 3B & 4B&5B&6B& 7B&!8B&"9B&#:B|&$;Bb&%=Bz & &>B &'?Bl &(@BR &)AB8&*BB&+CB&,DB&-EB&.FB&/GB&0IBh&1JBN&2KB4&3LB&4MB& 5NB & 6OB&7PB&8QB&9RB& :SB&E&;UB & <VB!&=WB"&>XB#&?YB$&@ZB%&A[Bx&& B\B'&C]Bj(&D^BP)&E_B6*& F`,U6&'& F @& %/=U&2P  ºU&y0?"B&GaB& HbB& IcB&JdB&KeB&LfB&MgB&NhB|& OiB&PlB &QmBl &RnBR &SoB8&TpB&UqB&VrB&WsB&XtB&YuB& ZvB& [wB& \xB&]yB&^zB&_{Br&`|BX&a}B>&b~B$&cB &dB&eB&fB&gB &h,U6&'& F @& %"/=U&2p  |U&y0?+B&iB&jB& kB& E# lB& E# mB&nB&oB&pB&qB&rBn &sBT &tB: &uB & vB, & wB8& xBD&yB.&zB&{B& |B& }B& ~B& B*& B6&B&B&B&B&B&B&B&Bf&BL&B2 & B>!&BV#& Bb$&BH%&B.&&B'&B'&B(&,U6&'& F @& _%a/=U&2P  U&y0?%B&B& B&B&B&B&B&Bp&BV&B<&B" &B & B & B &B &B&B&B&B&Bj&BP&B6& BB& BN& BZ& E# Bf& E# Br& E# B~& E# B&Bp&BV&B<&B"&B &B &B!&B"&,U6&'& F @& %/=U&2p  zU&y0?B&B&B&B&B&B&B&B|&Bb&BH &B. &B &B &B &B &B&B&Bx&,U6&'& F @& л%/=U&2P  !nU&y0?+B& B & B&B&B&B&B&B&B|&Bb&BH &B. &B &B & B & B& B& B*&B&B&B&B&B&Bt& B&B&B~&Bd&BJ&B0& B& B& B& B & B!&B"&Bz#&B`$&BF%&B,&&B'&B'&B(&,U6&'& F @& g%|/=U&2p  "U&y0?B& B & B& B$&B &B&B&B&B&B& Bn & !Bz &"B` &#BF &$B, &%B&&B&'B&(B&)B& *B& +Bv& ,B\& -BB& .B(&/B&0,U6&'& F @& lZRoot Entry ®`VCompObj<Ole persist elements" SfxDocumentInfo uBasicManager2 4StarBASIC SfxWindowsCSwNumRulesUStandardjSfxStyleSheetsSummaryInformation( ,0SwPageStyleSheets$ 1StarWriterDocument&