目錄 每個子系統都給其它子系統提供了接口,你甚至不需要深入每個子系統的細節,僅僅搞清楚子系統的接口就可以進行內核級的程序開發了。 內核地址空間的布局 初始化和固定映射 Boot mem 高端內存 VM 和 vmalloc 物理內存管理 slab 管理 page cache swap cache 和 swap file 虛存管理(vma) swap out swap in mm fault handle mmap 我的理解是這樣: 1.可以分成兩個部分討論: 內核空間的內存管理 用戶空間的內存管理 2 對於用戶空間管理,正如你說的,核心是映射,映射操作由cpu自動完成的,但是如何映射是Linux定的。 正如數學中定義的,關於一個映射有3個要素; 定義域 映射規則 V 值域 因此要完成一個映射的定義,需要 在用戶空間分配一個定義域(vm_area_strUCt的分配等操作); 在“物理地址”上分配一個值域(內核空間的分配----頁面級分配器); 定義映射(頁表操作); 3 對於其它操作,也可以從這個3要素來考慮 比如交換: 就是把一部分值域“搬遷”到“外設”中,映射原象一端固定住,“象”一端也跟著移到“外設”中 交換中的缺頁中斷 不過是把部分“值域”再搬回到內存中來 內核地址空間的布局 我們計算一下, 如果4G的空間都有映射那麼頁表占去了多少空間:一個頁表4K(一個pte代表4K), pgd 中有1024 項(每一項代表4K空間 ),那麼就需要 4K*(1024+1) = 4M+4k 的空間. 內核的pgd 是 swapper_pg_dir,靜態分配, 系統初始化時把前768項空出來. 也就是只初始化了3G以上的空間, 編譯時內核的虛擬地址從3G開始.這樣內核通過這個頁目錄尋址.初始化時映射的這一部分空間稱為預映射.預映射把所有物理內存映射到內核, 同時p--v 轉換非常簡單,使得內核無須維護自己的虛擬空間,並且能夠方便的存取用戶空間. 眾所周知的,__pa 宏基於這樣的預映射.內核擁有獨立的pgd, 也就是說內核的虛擬空間是獨立於其他程序的.這樣以來和其他進程完全沒有聯系.那麼我們所說的用戶在低3G,內核在最高1G,為所有用戶共享, 又是怎麼回事呢? 其實很簡單, 進程頁表前768項指向進程的用戶空間,如果進程要訪問內核空間,如系統調用,則進程的頁目錄中768項後的項指向swapper_pg_dir的768項後的項。然後通過swapper_pg_dir來訪問內核空間。一旦用戶陷入內核,就使用內核的swapper_pg_dir(不是直接使用而是保持用戶pgd 768後面的和 swapper_pg_dir 一致,共享內核頁表{因為到內核不切換pgd?}看看do_page_fault ^_^ 的相關處理)進行尋址! linux 把他的1G線性空間分成了幾個部分: 1) Linux將整個4G線性地址空間分為用戶空間和內核空間兩部分,而內核地址空間又被劃分為"物理內存區", "虛擬內存分配區", "高端頁面映射區","專用頁面映射區", "系統保留映射區"幾個區域. 2) 在標准配置下, 物理區最大長度為896M,系統的物理內存被順序映射在物理區中,在支持擴展頁長(PSE)和全局頁面(PGE)的機器上,物理區使用4M頁面並作為全局頁面來處理(呵呵,沒有白白計算). 當系統物理內存大於896M時,超過物理區的那部分內存 稱為高端內存,低端內存和高端內存用highmem_start_page變量來定界,內核在存取高端內存時必須將它們映射到"高端頁面映射區". 3) Linux保留內核空間最頂部128K區域作為保留區,緊接保留區以下的一段區域為專用頁面映射區,它的總尺寸和每一頁的用途由fixed_address枚舉結構在編繹時預定義,用__fix_to_virt(index)可獲取專用區內預定義頁面的邏輯地址.在專用頁面區內為每個CPU預定義了一張高端內存映射頁,用於在中斷處理中高端頁面的映射操作. 4) 距離內核空間頂部32M, 長度為4M的一段區域為高端內存映射區,它正好占用1個頁幀表所表示的物理內存總量, 它可以緩沖1024個高端頁面的映射.在物理區和高端映射區之間為虛存內存分配區, 用於vmalloc()函數,它的前部與物理區有8M隔離帶, 後部與高端映射區有8K(2.4為4k?)的隔離帶. 5) 當系統物理內存超過4G時,必須使用CPU的擴展分頁(PAE)模式所提供的64位頁目錄項才能存取到4G以上的物理內.在PAE模式下, 線性地址到物理地址的轉換使用3級頁表,第1級頁目錄由線性地址的最高2位索引, 每一目錄項對應1G的尋址空間,第2級頁目錄項以9位索引, 每一目錄項對應2M的尋址空間, 第3級頁目錄項以9位索引,每一目錄項對應4K的頁幀. 除了頁目錄項所描述的物理地址擴展為36位外,64位和32位頁目錄項結構沒有什麼區別. 在PAE模式下,包含PSE位的中級頁目錄項所對應的頁面從4M減少為2M. 內核的1G線性空間(灰色代表已經建立映射,只有物理區為完全映射) 物理區 8M隔離 vmalloc 區 8K隔離 4M的高端映射區 固定映射區 128K 保留區 V 和物理區對應的物理內存 被映射到高端映射區的物理內存 其他高端物理內存 下面從代碼中尋找一下根據(上面的分析好像不是2.4.0, ^_^): 下面的代碼摘自 include/asm-386/pgtable.h /* Just any arbitrary offset to the start of the vmalloc VM area: the * current 8MB value just means that there will be a 8MB "hole" after the * physical memory until the kernel virtual memory starts. That means that * any out-of-bounds memory Accesses will hopefully be caught. * The vmalloc() routines leaves a hole of 4kB between each vmalloced * area for the same reason. ;) */ #define VMALLOC_OFFSET (8*1024*1024) #define VMALLOC_START (((unsigned long) high_memory + 2*VMALLOC_OFFSET-1) & ~(VMALLOC_OFFSET-1)) #define VMALLOC_VMADDR(x) ((unsigned long)(x)) #define VMALLOC_END (FIXADDR_START) 可以看出物理區 和 VM 區中間的那個空洞.而vmalloc區結束和固定映射區開始也應該是4k的空洞啊! fixmap.h fixed_addresses 看看這個結構就知道,高端內存映射區屬於固定內存區的一種,並且每個cup一個. enum fixed_addresses { #ifdef CONFIG_X86_LOCAL_APIC FIX_APIC_BASE, /* local (CPU) APIC) -- required for SMP or not */ #endif #ifdef CONFIG_X86_IO_APIC FIX_IO_APIC_BASE_0, FIX_IO_APIC_BASE_END = FIX_IO_APIC_BASE_0 + MAX_IO_APICS-1, #endif #ifdef CONFIG_X86_VISWS_APIC FIX_CO_CPU, /* Cobalt timer */ FIX_CO_APIC, /* Cobalt APIC Redirection Table */ FIX_LI_PCIA, /* Lithium PCI Bridge A */ FIX_LI_PCIB, /* Lithium PCI Bridge B */ #endif #ifdef CONFIG_HIGHMEM FIX_KMAP_BEGIN, /* reserved pte's for temporary kernel mappings */ FIX_KMAP_END = FIX_KMAP_BEGIN+(KM_TYPE_NR*NR_CPUS)-1, #endif __end_of_fixed_addresses }; 這個文件的以下定義也非常有意義: /* * used by vmalloc.c. * * Leave one empty page between vmalloc'ed areas and * the start of the fixmap, and leave one page empty * at the top of mem.. */ #define FIXADDR_TOP (0xffffe000UL) #define FIXADDR_SIZE (__end_of_fixed_addresses need_resched = 1; cpu_idle(); } arch/i386/kernel/setup.c void __init setup_arch(char **cmdline_p) { unsigned long bootmap_size; unsigned long start_pfn, max_pfn, max_low_pfn; int i; ....... setup_memory_region(); //有的系統 e820 不太好使,可能偽造一個 bios e820 ....... init_mm.start_code = (unsigned long) &_text; //初始化 init_mm ...... code_resource.start = virt_to_bus(&_text); ...... data_resource.start = virt_to_bus(&_etext); ...... #define PFN_UP(x) (((x) + PAGE_SIZE-1) >> PAGE_SHIFT) #define PFN_DOWN(x) ((x) >> PAGE_SHIFT) #define PFN_PHYS(x) ((x) MAXMEM_PFN) { highstart_pfn = MAXMEM_PFN; printk(KERN_NOTICE "%ldMB HIGHMEM available.\n", pages_to_mb(highend_pfn - highstart_pfn)); } #endif /* * Initialize the boot-time allocator (with low memory only): */ bootmap_size = init_bootmem(start_pfn, max_low_pfn); /* * 把所有可用的低端內存注冊於 bootmem allocator . */ ....... /* * Reserve the bootmem bitmap itself as well. We do this in two * steps (first step was init_bootmem()) because this catches * the (very unlikely) case of us accidentally initializing the * bootmem allocator with an invalid RAM area. */ reserve_bootmem(HIGH_MEMORY, (PFN_PHYS(start_pfn) + bootmap_size + PAGE_SIZE-1) - (HIGH_MEMORY)); /* * reserve physical page 0 - it's a special BIOS page on many boxes, * enabling clean reboots, SMP operation, laptop functions. */ reserve_bootmem(0, PAGE_SIZE); ...... paging_init(); ...... /* * Request address space for all standard RAM and ROM resources * and also for regions reported as reserved by the e820. */ ..... request_resource(&iomem_resource, &vram_resource); //可以研究一下 /* request I/O space for devices used on all i[345]86 PCs */ ....... } 什麼是e820? 跟著鏈接去看看. boot mem 見專門章節吧!我們的重點是 arch/i386/mm/Init.c /* * paging_init() sets up the page tables - note that the first 8MB are * already mapped by head.S. * * This routines also unmaps the page at virtual kernel address 0, so * that we can trap those pesky NULL-reference errors in the kernel. */ void __init paging_init(void) { pagetable_init(); //設置頁表 __asm__( "movl %%ecx,%%cr3\n" ::"c"(__pa(swapper_pg_dir))); //重置cpu頁目錄 __flush_tlb_all(); #ifdef CONFIG_HIGHMEM kmap_init(); #endif { //計算管理區大小 unsigned long zones_size[MAX_NR_ZONES] = {0, 0, 0}; unsigned int max_dma, high, low; } return; } static void __init pagetable_init (void) { unsigned long vaddr, end; pgd_t *pgd, *pgd_base; int i, j, k; pmd_t *pmd; pte_t *pte; /* * This can be zero as well - no problem, in that case we exit * the loops anyway due to the PTRS_PER_* conditions. */ end = (unsigned long)__va(max_low_pfn*PAGE_SIZE); //首先設置低端內存 pgd_base = swapper_pg_dir; ..... i = __pgd_offset(PAGE_OFFSET); //看到設置的虛擬空間了吧? ..... /* * Fixed mappings, only the page table structure has to be * created - mappings will be set by set_fixmap(): */ vaddr = __fix_to_virt(__end_of_fixed_addresses - 1) & PMD_MASK; fixrange_init(vaddr, 0, pgd_base); #if CONFIG_HIGHMEM /* * Permanent kmaps: */ vaddr = PKMAP_BASE; fixrange_init(vaddr, vaddr + PAGE_SIZE*LAST_PKMAP, pgd_base); pgd = swapper_pg_dir + __pgd_offset(vaddr); pmd = pmd_offset(pgd, vaddr); pte = pte_offset(pmd, vaddr); pkmap_page_table = pte; //找到 pkmap區(4m)在內核虛擬空間所對應的頁表 #endif } 希望能夠理清高端內存和固定映射的概念及管理方式.為此再看看 kmap_init() /* * NOTE: pagetable_init alloc all the fixmap pagetables contiguous on the * physical space so we can cache the place of the first one and move * around without checking the pgd every time. */ #if CONFIG_HIGHMEM pte_t *kmap_pte; //內核映射的頁表 pgprot_t kmap_prot; #define kmap_get_fixmap_pte(vaddr) pte_offset(pmd_offset(pgd_offset_k(vaddr), (vaddr)), (vaddr)) void __init kmap_init(void) { unsigned long kmap_vstart; /* cache the first kmap pte */ kmap_vstart = __fix_to_virt(FIX_KMAP_BEGIN); kmap_pte = kmap_get_fixmap_pte(kmap_vstart); kmap_prot = PAGE_KERNEL; } #endif /* CONFIG_HIGHMEM */ Boot mem 高端內存 在一般情況下,Linux在初始化時,總是盡可能的將所有的物理內存映射到內核地址空間中去。如果內核地址空間起始於0xC0000000,為vmalloc保留的虛擬地址空間是128M,那麼最多只能有(1G-128M)的物理內存直接映射到內核空間中,內核可以直接訪問。如果還有更多的內存,就稱為高端內存,內核不能直接訪問,只能通過修改頁表映射後才能進行訪問。 內存分區可以使內核頁分配更加合理。當系統物理內存大於1G時,內核不能將所有的物理內存都預先映射到內核空間中,這樣就產生了高端內存,高端內存最適於映射到用戶進程空間中。預映射的部分可直接用於內核緩沖區,其中有一小塊可用於DMA操作的內存,留給DMA操作分配用,一般不會輕易分配。內存分區還可以適應不連續的物理內存分布,是非一致性內存存取體系(NUMA)的基礎。 先看看代碼中的注釋: In linux\include\linux\mmzone.h(version 2.4.16, line 67) /* * On machines where it is needed (eg PCs) we divide physical memory * into multiple physical zones. On a PC we have 3 zones: * * ZONE_DMA 896 MB only page cache and user processes */ 高端頁面的映射 1) 高端物理頁面共享一塊4M的映射區域,該區域對齊於4M頁邊界,並用一張頁表(pkmap_page_table)來完成映射操作。高端頁面的映射地址由其頁結構中virtual成員給出。 2) 高端映射區邏輯頁面的分配結構用分配表(pkmap_count)來描述,它有1024項,對應於映射區內不同的邏輯頁面。當分配項的值等於零時為自由項,等於1時為緩沖項,大於1時為映射項。映射頁面的分配基於分配表的掃描,當所有的自由項都用完時,系統將清除所有的緩沖項,如果連緩沖項都用完時,系統將進入等待狀態。 3) 頁緩沖盡可能地使用高端頁面,當通過塊結構刷新高端頁面時,系統會在提交塊設備> ,原請求塊,同時中轉塊被釋放。 還是結合源碼看一看, 給我的感覺是這樣的: 在 include/linux/highmem.h 中沒有定義 CONFIG_HIGHMEM 時, 有 void *kmap(struct page *page) { return page_address(page); } #define page_address(page) ((page)->virtual) 而在定義了CONFIG_HIGHMEM 時其定義變為: include/linux/asm_i386/highmem.h static inline void *kmap(struct page *page) { if (in_interrupt()) BUG(); if (page virtual; if (!vaddr) vaddr = map_new_virtual(page); //對於已經被沖掉的頁面,需要重映射 pkmap_count[PKMAP_NR(vaddr)]++; //邏輯頁面操作 if (pkmap_count[PKMAP_NR(vaddr)] 0~mem的映射有了,而且是固定不變的。vmalloc的部分(3G+mem+128M?, -固定映射區)的映射並不是總被定義,而且會變.vmalloc就是分一個頁面,建一個映射,把分到的vm地址返回.vmalloc修改的是swapper_pg_dir ,基准頁目錄.這樣的話也會產生一些問題,舉一個例子(lucian_yao) 一個問題我沒有想清楚:假定在某個時候用__vmalloc將[ 3.5G, 3.5G+1M ]映射到[ 2M, 3M ]這個時候進入進程A,然後在中斷中訪問[3.5G, 3.5G+1M]這段空間,由缺頁fault將進程A的頁表補上[3.5G, 3.5G+1M]映射到[ 2M, 3M ]然後,釋放了[ 3.5G, 3.5G+1M ],再次重新分配[3.5G, 3.5G+1M],這個時候[3.5G, 3.5G+1M]映射到[ 5M, 6M ]但是這個時候(仍然使用進程A的頁表)訪問[3.5G, 3.5G+1M],由於沒有出現缺頁fault,訪問到的實際地址是[ 2M, 3M ],這不是不對了嗎?是不是我理解上有什麼問題? (jkl) 在進程的內核頁目錄中補上的是只是頁目錄項,而頁表對所有進程來說是共用的,不管vfree()多大的內存塊,在vmalloc()時新分配的頁表不會被釋放,當重新vmalloc()時,仍舊使用原來的頁表。do_page_fault使得進程的內核頁目錄項與swapper_pg_dir保持同步,swapper_pg_dir的內核頁目錄項一旦建立就不再被改變,需要改變的只是共享的頁表而已。 說的神些,kmalloc分配連續的物理地址,vmalloc分配連續的虛擬地址.並且有如下結論: memory.c 主要負責一部分用戶空間的虛存映射工作 也就是 0-3G的映射 vmalloc.c 主要負責內核空間高端的內存分配和映射 實際上: 用戶空間 0 - 3G do_brk 調用來分配, 還有一些函數處理映射工作(比如memory.c中的函數) 內核空間 3G - 3G + mem kmalloc, __get_free_pages 來分配 內核空間 3G + mem + 隔離帶 - 4G vmalloc 其中 mem 可以看成是內存的大小,會自動檢測到,也可以由命令行指定. memory.c 中的的copy_page_range。clear_page_tables等函數是用於 建立或撤消映射,do_wp_page,do_no_page,do_swap_page等用於頁面故障時處理。而vmscan.c則是處理頁面交換。 並且vmalloc為了捕獲越界,vm中間是有洞的.關於這些,看看下面的討論把: 提問: vmalloc()函數分配內存的虛擬地址從3G+high_memory+hole_8M開始其中hign_memory為實際物理內存,hole_8M為8M的隔離帶為什麼要有8M的隔離帶?這樣豈不是很浪費虛擬地址空間嗎?另外分配的內存塊之間有一個4K的隔離頁,這樣是不是也很浪費虛擬地址空間? (jkl) Linux用這些空洞來檢測存儲器讀寫越界故障,當然空洞越大出現破壞性故障的可能性就越小,8M的空洞正好用兩個頁目錄項來標記,4K的空洞用一個頁表項來標記,由於一般物理內存遠小於線性地址空間,因此這種浪費是微不足到的。 謝謝您的回答,第一次請教問題,就得到您的耐心回答,非常感謝我還是有點不明白: 那為何用兩個頁目錄表,用一個不行嗎?甚至用一個4k的頁表不就夠了嗎?加一個空洞,是不是利用了頁保護的屬性?如果越界的話,不論空洞的大小都應該產生異常,對嗎?不明白空洞越大越安全的原因另外3G+phymem+8M給vmaloc剩下的空間不多了,如果實際物理內存接近1G的話,是不是vmaloc函數就不能使用了?我感覺空間並不充裕 (jkl) 隔離帶的大小是任意的,但如果隔離帶不夠大的話,有可能會被故障代碼跨過引起破壞。當內核有代碼引用到這些隔離帶的地址時,這些地址對應的頁目錄項或頁表項由於被標記為"不存在",就會產生頁故障,這樣就可以准確定位故障所在。如果物理內存非常大,造成內核虛擬空間不足時,可以減小內核的起始線性地址,通過減小用戶程序的虛擬地址空間來增大內核的虛擬空間。如果物理內存超過2G,可通過一個內核補丁big Physical Memory for IA-32將應用程序與內核的頁目錄分開,盡管這樣還是只能管理3.8G,如果物理內存還要大,就要使用64位的體系了。 物理內存管理 kernel頁表 kernel的pgd是在開始setup_32時初始化的,它應該使cr3指向swapper_pg_dir(這個變量在arch\i386\kernel.head.s中),它的定義如下: ENTRY(swapper_pg_dir) .long 0x00102007 .fill __USER_PGD_PTRS-1,4,0 /* default: 767 entries */ .long 0x00102007 /* default: 255 entries */ .fill __KERNEL_PGD_PTRS-1,4,0 這裡面只有兩項非空,用戶空間的第一項和kernel空間的第一項,它們都指向地址0x00102000,也就是pg0,這個頁表中裝的是從物理地址0-4M的內容。但是這個pgd並不會一直這樣,在start_kernel中會調用paging_init把它完全重新改掉。paging_init將初始化線性空間從start_mem到end_mem的頁表項。它做的第一件事就是把swapper_pg_dir的第一項清0,用於捕獲null訪問。然後它會進入一個循環,這個循環有兩種結果,如果你的CPU是Pentium以上,那麼它就把分成4M為單位的頁。然後把填入pgd中;否則就按4K進行分頁,如果pgd中的項為空,就從start_mem開始分配一頁作為頁表,然後在頁表中順序填入物理頁幀的首地址,如果超過了end_mem,就在頁表中填入0。 在swapper_pg_dir中的第一項和第768項都有一個指向pg0的項,因為,初始化的時候,其中有兩個工作要做: 1.啟動頁機制,這個時候從物理地址尋址轉為虛地址尋址,為確保平滑過渡,在低端(0到4M)的映射是恆同映射 2 跳到內核,實際上內存仍然保存在物理地址0-4M,這個時候,實際上是通過虛擬地址3G-4G訪問的,為了平滑過渡,將3G-3G+4M的虛地址映射和0-4M虛地址一致,這樣,開啟頁面映射後跳到內核時已經運行於3G以上的地址了,從這以後,內核自己的尋址都在3G以上了。 內核的內存分配主要會涉及到三組分配函數: 1)頁面分配器 __get_free_pages()/__free_pages() 2)0xc0000000 ~ 0xc0000000+phymem kmalloc()/kfree() 3) 0xc0000000+phymem+8M_hole ~ 4G vmalloc()/vfree() 以下簡要的給予介紹: 一:頁面分配器: 頁面分配器是最底層的內存分配,主要用於物理內存頁的分配,在內核初始化時,調用paging_init創建swap_page_dir,使得從PAGE_OFFSET到PAGE_OFFSET+PhyMem的內核虛擬空間與0~PhyMem的物理空間建立起一一對應的關系。所以__get_free_pages返回的是實際物理+PAGE_OFFSET(由ADDRESS宏實現變換)。 頁面分配器采用的是“伙伴”算法。主要涉及兩個重要全局變量。 1)struct free_area_struct free_area[NR_MEM_TYPES][NR_MEM_LISTS]; 空閒塊數組 2)mem_map_t * mem_map 邏輯頁,標示每個物理頁的使用情況,根據系統的實際內存,在內核初啟時,由mem_init初始化。 具體實現請閱讀源碼及參看《UNIX高級教程 系統技術內幕》、 二:kmalloc/kree kmalloc 分配的是從PAGE_OFFSET~PAGE_OFFSET+PhyMem之間的內核空間,用於分配連續物理空間。將kmalloc返回值減去PAGE_OFFSET就是實際的物理地址。 我現在看的源碼(2.2.14)kmalloc實現采用了slab分配器算法。具體的實現請參閱lucian_yao以前的貼子及 《UNIX高級教程 系統技術內幕》。 三:vmalloc/vfree 用於分配內核位於PAGE_OFFSET+PhyMem+8M_hole ~ 4G的虛擬空間, vmalloc的實現比較簡單,主要是維護struct vm_struct vmlist鏈表 當然vmalloc會調用kmalloc以分配vm_struct,然後為虛擬空間創建頁表。 這裡我有一個疑問就是用vmalloc分配的內存似乎不會被swap出去,希望有高手指教。再有就是用malloc分配的位於數據段上端至brk之間的堆。 這部分似乎要用到sys_remap,sys_munmap系統調用,以後看源碼再說吧。剛看了點皮毛,寫出點心得,就是想暴露一下自己的一些模糊概念,以期有高手指正。 [jkl]內核要求實時性很高,可加載模塊本身就是用vmalloc()分配的內存,它是不能允許極慢的磁盤交換的。 slab 管理 slab分配器在內存分配中起的作用 slab分配器通過頁面級分配器獲得頁塊後,做進一步的精細分配, 將這個頁塊分割成一個個的對象,有點類似c中的malloc c, mfree的作用。 cache描述符 struct kmem_cache_s { /* 1) each alloc & free */ /* full, partial first, then free */ struct list_head slabs; struct list_head *firstnotfull; unsigned int objsize; unsigned int flags; /* constant flags */ unsigned int num; /* # of objs per slab */ spinlock_t spinlock; #ifdef CONFIG_SMP unsigned int batchcount; #endif /* 2) slab additions /removals */ /* order of pgs per slab (2^n) */ unsigned int gfporder; /* force GFP flags, e.g. GFP_DMA */ unsigned int gfpflags; size_t colour; /* cache colouring range */ unsigned int colour_off; /* colour offset */ unsigned int colour_next; /* cache colouring */ kmem_cache_t *slabp_cache; unsigned int growing; unsigned int dflags; /* dynamic flags */ /* constructor func */ void (*ctor)(void *, kmem_cache_t *, unsigned long); /* de-constructor func */ void (*dtor)(void *, kmem_cache_t *, unsigned long); unsigned long failures; /* 3) cache creation/removal */ char name[CACHE_NAMELEN]; struct list_head next; #ifdef CONFIG_SMP /* 4) per-cpu data */ cpucache_t *cpudata[NR_CPUS]; #endif #if STATS unsigned long num_active; unsigned long num_allocations; unsigned long high_mark; unsigned long grown; unsigned long reaped; unsigned long errors; #ifdef CONFIG_SMP atomic_t allochit; atomic_t allocmiss; atomic_t freehit; atomic_t freemiss; #endif #endif }; slabs用它將這個cache的slab連成一個鏈表 firstnotfull指向第一個不滿的slab,當分配(復用)對象的時候,首先考慮在它指向的slab裡分配. objsize該cache中對象大小 flags num對象個數 gfporder該cache中slab一個占用多少頁面,當構造新的slab,按照這個大小向頁面級分配器申請頁面。 gfpflags申請頁面時,向頁面級分配器提出的要求,例如是否要求申請DMA的頁面,是否要求申請是原子的(即頁面分配器在分配的時候不能被阻塞) colour colour的范圍,這個cache的slab依次用0,1,...,colour-1,0,1,...為顏色。 colour_off這個cache中colour粒度,例如為一個L1-CACHE線。 colour_next下一個colour數,當cache分配一個新的slab時,采用這個colour,也就是colour * colour_off為slab空出的字節數 slabp_cache 當這個cache中的slab,其管理部分(slab描述符和kmem_bufctl_t數組)放在slab外面時,這個指針指向放置的通用cache growing dflags ctor 指向對象的構造器,在這個cache創建一個新的slab時,對裡面所有的對象都進行一次構造調用(參見slab的設計思想中關於對象復用部分) dtor 指向對象的析構器,在這個cache銷毀一個slab時,對裡面所有的對象都進行一次析構調用 failures name 這個cache的名字 next 用它和其它的cache串成一個鏈,在這個鏈上按照時鐘算法定期地回收某個cache的部分slab slab描述符 typedef struct slab_s { struct list_head list; unsigned long colouroff; void *s_mem; /* including colour offset */ unsigned int inuse; /* num of objs active in slab */ kmem_bufctl_t free; } slab_t; list用於鏈表,這個鏈表將cache中所有的slab連接起來 colouroff這個slab中第一個對象距離slab起始位置(也就是頁塊起始位置)的字節數,實際上s_mem=頁塊首地址+colouroff s_mem這個slab中第一個對象的起始位置 inuse這個slab中被使用的對象個數,用於調整slab格局,當inuse=0說明這個slab全空,將這個slab從部分滿的slab段中移動到全空的slab段中 free第一個未用對象的ID, 當在這個slab"分配"(復用)對象時,首先用這個ID的對象。 通用cache索引結構 用這個結構組成的數組cache_sizes給不同尺寸的通用cache提供索引 typedef struct cache_sizes { size_t cs_size; kmem_cache_t *cs_cachep; kmem_cache_t *cs_dmacachep; } cache_sizes_t; cs_size通用cache的對象尺寸 cs_cachep指向一個通用cache, 它的對象尺寸為cs_size cs_dmacachep指向一個通用DMA的cache, 它的對象尺寸為cs_size Slab分配器的結構 Slab 分配器用於管理內核的核心對象。 它有若干個 cache 組成。每個 cache 管理一個特定類的對象。 每個cache有若干個 slab (Slab分配器的名字可能就是怎麼來的)組成,每個 slab 實際上就是若干個頁面組成的一個頁塊。這個頁塊被細分成許多對象。 cache為管理這些slab, 通過 cache描述符( kmem_cache_t )以及指針將這些 slab 連起來。 驗證 cache的數據結構中下面這個字段: struct kmem_cache_s { struct list_headslabs; ... ... } 與slab結構中下面字段: typedef struct slab_s { struct list_headlist; ... } slab_t; 共同構成這個鏈表. slab如何管理它的對象 一個 slab 通過自己的 kmem_bufctl_t 數組,來管理它的空閒對象。這個數組的元素和該 slab中的對象是一一對應的。 初始化一個slab時,每個對象都是空的,所以這個數組每個元素(除最後一個)都指向下一個: 在kmem_cache_init_objs中 static inline void kmem_cache_init_objs (kmem_cache_t * cachep, slab_t * slabp, unsigned long ctor_flags) { int i; for (i = 0; i num; i++) { .. ... slab_bufctl(slabp)[ i ] = i+1; } slab_bufctl(slabp)[i-1] = BUFCTL_END; ... ... } 分配對象時,在下面的語句中, objp = slabp->s_mem + slabp->free*cachep->objsize; slabp->free=slab_bufctl(slabp)[slabp->free]; 取出free的數值1,計算對象1的位置即可。然後將free指向3. 回收(應該說將對象置為未用)時,將數組中對象對應的元素插入鏈表頭即可: slab_bufctl(slabp)[objnr] = slabp->free; slabp->free = objnr; cache如何管理它的slab 格局 一個cache的所有 slab 通過指針連成一個隊列,這些 slab的排列始終保持一個格局: 全滿的,部分滿的,和全空的。 另外,cache 描述符有一個指針始終指向第一個不滿的slab(首先可能是部分滿的,其次是全空的),當它指向描述符本身的時候,說明沒有不滿的 slab了。當 slab 是否滿的狀態有變化時,cache會調整它的位置,以保持上述格局,例如一個部分滿的 slab由於它的最後一個對象被設置為不使用,即它為全空的了,那麼它將被調整到全空的slab部分中。 當分配一個新的對象時,cache 首先通過 firstnotfull 找到它的第一個不滿的slab, 在那麼分配對象。如果沒有不滿的slab, 則向頁面級分配器申請一個頁塊,然後初始化為一個slab. 回收對象 當回收一個對象時,即便在這之後,這個對象所在的 slab 為全空,cache也不會將這個 slab 占用的頁塊還給頁面級分配器。 回收slab slab分配器算法提供兩種回收slab的方式,一種是回收某個特定的cache的所有全空的slab,直到有用戶又在該cache分配新的 slab為止( kmem_cache_shrink);一種是對所有的 cache 采用時鐘算法,每次選擇一個比較合適的 cache,回收它部分的空 slab( kmem_cache_reap ). 驗證 每次分配的時候總是考察從firstnotfull指向的第一個不滿的slab: #define kmem_cache_alloc_one(cachep) ({ slab_t*slabp; /* Get slab alloc is to come from. */ { struct list_head* p = cachep->firstnotfull;/*slabs) goto alloc_new_slab;/*簿褪撬狄湊飧鯿ache的slab全滿了,要麼就沒有slab,這個時候要分配新的slab*/ slabp = list_entry(p,slab_t, list); } kmem_cache_alloc_one_tail(cachep, slabp); }) 在後面的kmem_cache_alloc_one_tail函數中在這個firstnotfull指向的slab中分配一個對象,如果這個slab因此而滿了,則將firstnotfull指向下一個不滿的slab: static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp) { ... ... slabp->free=slab_bufctl(slabp)[slabp->free]; if (slabp->free == BUFCTL_END)/*firstnotfull = slabp->list.next; ... ... } 下面看看"釋放"一個對象時,是如何保持隊列的格局的: static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp) { ... ... if (slabp->inuse-- ==cachep->num)/*inuse)/*firstnotfull;/*床糠致畝恿型凡?/ cachep->firstnotfull = &slabp->list; if (slabp->list.next == t) return; list_del(&slabp->list); list_add_tail(&slabp->list, t); return; } moveslab_free: /* * was partial, now empty. * c_firstnotfull might point to slabp * FIXME: optimize */ { struct list_head *t = cachep->firstnotfull->prev; list_del(&slabp->list); list_add_tail(&slabp->list,&cachep->slabs);/*firstnotfull == &slabp->list) cachep->firstnotfull = t->next; return; } } slab的管理部分 slab描述符和管理空閒對象用的數組(kmem_bufctl_t)不妨被稱為slab的管理部分 slab的管理部分放置的位置 1. 管理部分可以和對象都放在slab裡 2. 管理部分也可以放到slab外面(在某個通用的cache中,見通用cache) 1. 如果對象比較大,那麼把管理部分放到slab裡面,會浪費slab大量空間。舉一個極端的例子,對象大小為2K, 頁塊為4K,那麼如果把管理部分放到slab裡面,這個頁塊就只能放一個對象,浪費的空間=4k-2k-管理部分的尺寸接近2K! 2. 但是放在外面會帶來一些小小的效率上的損失。 如果管理部分和對象放在兩個地方,那麼一定是在不同的頁塊中。於是用戶申請一個對象時,首先要訪問slab管理部分,然後提供指向未用對象的指針,然後用戶訪問這個對象的地址。這樣,完成一個流程需要訪問兩個頁塊,也就是在TLB上要"踩"上兩個腳印(footprint). 如果管理部分和對象放在一個slab中,因而很有可能在一個頁塊中,因此完成這個流程只需在TLB上踩上一個腳印。在引起TLB失效的可能性上,前者比後者大,因而效率低。 Color slab算法中利用slab的剩余空間來做平移,第1個slab不平移;第2個slab平移1個colour粒度;...;周而復始. void __init kmem_cache_init(void) { size_t left_over; init_MUTEX(&cache_chain_sem); INIT_LIST_HEAD(&cache_chain); kmem_cache_estimate(0, cache_cache.objsize, 0, &left_over,&cache_cache.num);/*colour_next;/*colour_next++;/*colour_next >=cachep->colour)/*colour_next = 0; offset *=cachep->colour_off;/*num * sizeof(kmem_bufctl_t) +sizeof(slab_t)); /*inuse = 0; slabp->colouroff = colour_off; slabp->s_mem =objp+colour_off;/*free指向該對象即可。為了保證這個cache中的slab格局(滿,部分滿,全空),必要的時候,要調整這個slab在鏈表中的位置,具體地說: slab原本是滿的,那麼需要將它移動到部分滿的slab中去(goto moveslab_partial) slab原本是部分滿的,現在空了,那麼將它移動到空的slab中去(moveslab_free) ~~~~~~~~ 空間回收 ~~~~~~ 所謂空間回收包括兩個工作: slab分配器把slab中的對象析構(如果有析構器的話) 將占用的頁面交還給頁面級分配器 slab的回收 kmem_slab_destroy -------------------------------------------------- 如果其中的對象有析構函數,則對這個slab中每個對象調用析構函數將這個slab占用的頁面交還給頁面級分配器.如果這個slab的管理部分在外面的話,還要到通用cache中free它的管理部分(將這個管理部分設為未用) cache的頁面回收:__kmem_cache_shrink ------------------------------------------------------ 特點是針對某個特定的cache,將它的全空的slab全部回收從這個cache的最後一個slab往前考察(注意cache的slab的格局),回收所有全空的slab kmem_slab_destroy,除非有其它用戶在這個cache分配新的slab(這部分我還沒有仔細考慮). cache的頁面回收: kmem_cache_reap ------------------------------------------ 在所有cache范圍內考察,每次選擇一個cache, 回收它的部分空的slab,這實際上是個垃圾回收的工作。所有在使用的cache描述符構成一個循環鏈表。為公平起見,reap采用時鐘算法,每次從當前指針位置遍歷 REAP_SCANLEN 個cache(當然可能中途結束遍歷),對這些cache進行考察,選出最佳的cache,對它的頁面進行回收: (1)排除一些當前不能回收的cache (2)計算剩下的cache中,每個cache可回收的slab個數,以及權重pages (3)選出其中權重最大的,如果某個cache的可回收的slab個數已經達到要求(>=REAP_PERFECT),就結束遍歷,對這個cache進行回收 回收:不回收這個cache中所有的空的slab, 只回收約80%, 方式和 __kmem_cache_shrink 一樣 注: 用戶接口指外部用戶可以調用的接口,其它為內部調用接口 藍色字是slab分配器的一件主要工作 綠色字是一件工作中的主要線索 一般分配一個對象,首先要創建一個cache來管理所有同類的對象(通用cache除外)。如果有cache了,那麼就在其中分配一個對象。 (用戶接口) 初始化一個cache (kmem_cache_create ) ------------------------------------ 在進行一些合法性檢查之後,首先在cache_cache中分配這個cache的描述符。 然後對一些尺寸進行處理,包括:size至少是字對齊的 對象對齊方式至少是字對齊的,如果要求是CACHE對齊,那麼方式為CACHE對齊,或者是1/2CACHE對齊(如果對象尺寸它所在的頁面 ----> cache 和 slab 第一個映射很容易(頁對齊即可)在這個函數裡主要設置第二個映射, 臨時借用了page結構裡的一個鏈表結構(這個結構list在頁面級分配器管理空閒頁面用,現在不使用)next, prev分配用來指向cache, slab. page cache swap cache 和 swap file