linux內(nèi)核之內(nèi)存管理

Linux內(nèi)核之內(nèi)存管理作者：harveywang郵箱：harvey.perfect@新浪博客地址：/harveyperfect，有關(guān)于減肥和學(xué)習(xí)英語相關(guān)的博文，歡迎交流把linux內(nèi)存管理分為下面四個(gè)層面（一）硬件輔助的虛實(shí)地址轉(zhuǎn)換（二）內(nèi)核管理的內(nèi)存相關(guān)（三）單個(gè)進(jìn)程的內(nèi)存管理（四）malloc軟件處理器硬件輔助的虛實(shí)地址轉(zhuǎn)換（以x86為例）在x86中虛實(shí)地址轉(zhuǎn)換分為段式轉(zhuǎn)換和頁轉(zhuǎn)換。段轉(zhuǎn)換過程是由邏輯地址（或稱為虛擬地址）轉(zhuǎn)換為線性地址；頁轉(zhuǎn)換過程則是將線性地址轉(zhuǎn)換為物理地址。段轉(zhuǎn)換示意圖如下X86支持兩種段，gdt和ldt（全局描述段表和局部描述符段表），在linux中只使用了4個(gè)全局描述符表，內(nèi)核空間和用戶空間分別兩個(gè)gdt，分別對(duì)應(yīng)各自的代碼段和數(shù)據(jù)段。也可以認(rèn)為在linux中變相地disable了x86的段式轉(zhuǎn)換功能。頁轉(zhuǎn)換示意圖如下在linux中x86的cr3寄存器（頁表基地址寄存器）保存在進(jìn)程的上下文中，在進(jìn)程切換時(shí)會(huì)保存或回復(fù)該寄存器的內(nèi)容，這樣每個(gè)進(jìn)程都有自己的轉(zhuǎn)換頁表，從而保證了每個(gè)進(jìn)程有自己的虛擬空間。內(nèi)核管理的內(nèi)存相關(guān)從幾個(gè)概念展開內(nèi)存管理：node、zone、buddy、slab1、NodeSGIAltix3000系統(tǒng)的兩個(gè)結(jié)點(diǎn)

如上圖，NUMA系統(tǒng)的結(jié)點(diǎn)通常是由一組CPU（如，SGIAltix3000是2個(gè)Itanium2CPU）和本地內(nèi)存組成。由于每個(gè)結(jié)點(diǎn)都有自己的本地內(nèi)存，因此全系統(tǒng)的內(nèi)存在物理上是分布的，每個(gè)結(jié)點(diǎn)訪問本地內(nèi)存和訪問其它結(jié)點(diǎn)的遠(yuǎn)地內(nèi)存的延遲是不同的，為了優(yōu)化對(duì)NUMA系統(tǒng)的支持，引進(jìn)了Node來將NUMA物理內(nèi)存進(jìn)行劃分為不同的Node。而操作系統(tǒng)也必須能感知硬件的拓?fù)浣Y(jié)構(gòu)，優(yōu)化系統(tǒng)的訪存。但是Intelx86系統(tǒng)不是NUMA系統(tǒng)。為了保持代碼的一致性，在x86平臺(tái)上，Linux將所有物理內(nèi)存都劃分到同一個(gè)Node。事實(shí)上，對(duì)于非NUMA體系結(jié)構(gòu)，也是如此處理的。Linux系統(tǒng)用定義了數(shù)組pg_data_tnode_data[MAX_NUMNODES]來管理各個(gè)node。2、ZoneLinux中Node、Zone和頁的關(guān)系每個(gè)結(jié)點(diǎn)的內(nèi)存被分為多個(gè)塊，稱為zones，它表示內(nèi)存中一段區(qū)域。一個(gè)zone用structzone結(jié)構(gòu)描述，zone的類型主要有ZONE_DMA、ZONE_NORMAL和ZONE_HIGHMEM。ZONE_DMA位于低端的內(nèi)存空間，用于某些舊的ISA設(shè)備。ZONE_NORMAL的內(nèi)存直接映射到Linux內(nèi)核線性地址空間的高端部分，ZONE_HIGHMEM位于物理地址高于896MB的區(qū)域。例如，在X86中，zone的物理地址如下：內(nèi)核空間只有1GB線性地址，如果使用大于1GB的物理內(nèi)存就沒法直接映射到內(nèi)核線性空間了。當(dāng)系統(tǒng)中的內(nèi)存大于896MB時(shí)，把內(nèi)核線性空間分為兩部分，內(nèi)核中低于896MB線性地址空間直接映射到低896MB的物理地址空間；高于896MB的128MB內(nèi)核線性空間用于動(dòng)態(tài)映射ZONE_HIGHMEM內(nèi)存區(qū)域（即物理地址高于896MB的物理空間）。3、Buddy如上圖所示，每個(gè)zone區(qū)域都采用伙伴系統(tǒng)（buddysystem）來管理空閑內(nèi)存頁面。把所有的空閑頁框分組為11個(gè)塊鏈表，每個(gè)塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個(gè)連續(xù)的頁框。鏈表編號(hào)分別為0，1，2，3，…k…10。從buddysystem中申請(qǐng)頁面過程：根據(jù)申請(qǐng)存儲(chǔ)區(qū)域大小查找對(duì)應(yīng)的編號(hào)為K的塊鏈表。如果編號(hào)K的鏈表為空，則向編號(hào)為k+1的鏈表申請(qǐng)一個(gè)存儲(chǔ)區(qū)域。如果編號(hào)為k+1鏈表不為空，系統(tǒng)從編號(hào)為k+1的鏈表上拆下一個(gè)區(qū)域，并將拆下的區(qū)域分為兩個(gè)2^k的區(qū)域，一個(gè)返還給申請(qǐng)者，另一個(gè)則掛到編號(hào)為k的鏈表。如果編號(hào)為k+1的鏈表也為空，編號(hào)為k+2的鏈表不為空。則從k+2的鏈表中拆下一個(gè)區(qū)域變?yōu)閮蓚€(gè)2^(k+1)區(qū)域，一個(gè)掛到編號(hào)為k+1的鏈表上，把另一個(gè)拆為兩個(gè)2^k的區(qū)域，一個(gè)返還給申請(qǐng)者，把另一個(gè)掛到編號(hào)為k的鏈表上。如果k+2的鏈表也為空，則一直向上迭代，直到編號(hào)為10的鏈表為止，如果編號(hào)為10的鏈表還為空，則申請(qǐng)失敗。向buddysystem中釋放頁面過程：在向buddysystem釋放頁面時(shí)，總會(huì)檢測(cè)釋放的頁面和鏈表中其他頁面是否可以組成一個(gè)更大一級(jí)的頁面，如果可以組成，則把這兩個(gè)區(qū)域組成一個(gè)并掛到更高一級(jí)的鏈表中。這個(gè)過程是迭代的，釋放過程會(huì)一層層向上找伙伴，然后合并成更大的，再向上找伙伴，實(shí)在找不到了就停止了！疑問：按照上面的說法，是否會(huì)出現(xiàn)這種情況，在釋放某個(gè)頁面導(dǎo)致所有頁面都組成了標(biāo)號(hào)為10的連續(xù)頁面了。等到再需要分配1個(gè)頁面時(shí)，又要一級(jí)一級(jí)地拆分。這樣的話效率是否很低？？是否在buddysystem每個(gè)鏈表結(jié)構(gòu)中設(shè)一個(gè)門限值會(huì)更好？釋放時(shí)標(biāo)記一下可以組成buddy的兩個(gè)連續(xù)區(qū)域，只有該級(jí)空閑的區(qū)域個(gè)數(shù)超過門限后才組成buddy并掛到上一級(jí)鏈表上。當(dāng)然，這個(gè)門限值可以由內(nèi)核根據(jù)目前總的空閑頁面數(shù)量進(jìn)行動(dòng)態(tài)調(diào)整。4、Slab下圖中給出了slab結(jié)構(gòu)的高層組織結(jié)構(gòu)。在最高層是cache_chain，這是一個(gè)slab緩存的鏈接列表?？梢杂脕聿檎易钸m合所需要的分配大小的緩存。cache_chain的每個(gè)元素都是一個(gè)kmem_cache結(jié)構(gòu)的引用。一個(gè)kmem_cache中的所有object大小都相同。slab分配器的主要結(jié)構(gòu)

slab是基于buddysystem的，每個(gè)slab占用一個(gè)或多個(gè)連續(xù)頁，即一個(gè)buddy鏈中的1個(gè)或多個(gè)頁面。每個(gè)緩存都包含了一個(gè)slabs列表，這是一段連續(xù)的內(nèi)存塊（通常都是頁面）。存在3種slab：slabs_full完全分配的slab，即其維護(hù)的空閑object鏈表為空slabs_partial部分分配的slabslabs_empty空slab，或者沒有對(duì)象被分配，即其inuse標(biāo)志位0.注意slabs_empty列表中的slab是進(jìn)行回收的主要備選對(duì)象。正是通過此過程，slab所使用的內(nèi)存被返回給操作系統(tǒng)供其他用戶使用。slab列表中的每個(gè)slab都是一個(gè)連續(xù)的內(nèi)存塊（從buddy申請(qǐng)的一個(gè)或多個(gè)連續(xù)頁），它們被劃分成一個(gè)個(gè)對(duì)象，這些對(duì)象是分配和釋放的基本元素。在slab擴(kuò)展時(shí)或把slab占用的內(nèi)存塊釋放到buddy系統(tǒng)時(shí)，slab是最小分配單位。通常來說，每個(gè)slab被分配為多個(gè)對(duì)象。由于對(duì)象是從slab中進(jìn)行分配和釋放的，因此單個(gè)slab可以在slab列表之間進(jìn)行移動(dòng)。例如，當(dāng)一個(gè)slab中的所有對(duì)象都被使用完時(shí)，就從slabs_partial列表中移動(dòng)到slabs_full列表中。當(dāng)一個(gè)slab完全被分配并且有對(duì)象被釋放后，就從slabs_full列表中移動(dòng)到slabs_partial列表中。當(dāng)所有對(duì)象都被釋放之后，就從slabs_partial列表移動(dòng)到slabs_empty列表中。slab背后的動(dòng)機(jī)與傳統(tǒng)的內(nèi)存管理模式相比，slab緩存分配器提供了很多優(yōu)點(diǎn)。首先，內(nèi)核通常依賴于對(duì)小對(duì)象的分配，它們會(huì)在系統(tǒng)生命周期內(nèi)進(jìn)行無數(shù)次分配。slab緩存分配器通過對(duì)類似大小的對(duì)象進(jìn)行緩存而提供這種功能，從而避免了常見的碎片問題。slab分配器還支持通用對(duì)象的初始化，從而避免了為同一目而對(duì)一個(gè)對(duì)象重復(fù)進(jìn)行初始化。最后，slab分配器還可以支持硬件緩存對(duì)齊和著色，這允許不同緩存中的對(duì)象占用相同的緩存行，從而提高緩存的利用率并獲得更好的性能。單個(gè)進(jìn)程的內(nèi)存管理每個(gè)進(jìn)程的task_struct中都有一個(gè)active_mm成員，類型為structmm_struct，內(nèi)核就是利用該成員管理進(jìn)程虛擬空間的。參見數(shù)據(jù)結(jié)構(gòu)task_struct，為了方便閱讀，刪除了該結(jié)構(gòu)中無關(guān)的成員變量。structtask_struct{ structmm_struct*mm,*active_mm; }參考下面的數(shù)據(jù)結(jié)構(gòu)定義。數(shù)據(jù)結(jié)構(gòu)structmm_struct中的成員mm_rb指向了一棵紅黑樹的根，該進(jìn)程的所有申請(qǐng)的虛擬空間都以起始虛擬地址為紅黑樹的key值掛到了這棵紅黑樹上。mm_struct中的成員map_count指示該進(jìn)程擁有的虛擬空間的個(gè)數(shù)，pgd指向該進(jìn)程的頁轉(zhuǎn)換表。structmm_struct{ structvm_area_struct*mmap;/*listofVMAs指向若干個(gè)VMA組成的鏈表*/ structrb_rootmm_rb;指向一棵紅黑樹 structvm_area_struct*mmap_cache; 指向最近找到的虛擬存儲(chǔ)區(qū)域 intmap_count; /*numberofVMAs*/虛擬區(qū)間的個(gè)數(shù) pgd_t*pgd;指向頁轉(zhuǎn)換表}數(shù)據(jù)結(jié)構(gòu)structvm_area_struct定義了一個(gè)連續(xù)的虛擬地址空間，包括起始地址和結(jié)束地址，以及紅黑樹節(jié)點(diǎn)vm_rb。內(nèi)核就是以vm_start為key值把vm_rb掛到進(jìn)程內(nèi)存紅黑樹上的。structvm_area_struct{ structmm_struct*vm_mm; /*Theaddressspacewebelongto.*/ unsignedlongvm_start; /*Ourstartaddresswithinvm_mm.*/ unsignedlongvm_end; /*Thefirstbyteafterourendaddresswithinvm_mm.*/ structrb_nodevm_rb; 這個(gè)虛擬區(qū)域?qū)?yīng)的紅黑樹的節(jié)點(diǎn)}內(nèi)核在給進(jìn)程分配了一塊虛擬地址內(nèi)存塊后，就將該區(qū)域掛接到進(jìn)程的紅黑樹上，此時(shí)內(nèi)核尚未給該進(jìn)程分配實(shí)際的內(nèi)存。在進(jìn)程訪問該區(qū)域時(shí)則產(chǎn)生缺頁中斷，在中斷中檢查訪問的區(qū)域已經(jīng)分配給進(jìn)程后，則分配實(shí)際內(nèi)存頁面，并更新該進(jìn)程的頁轉(zhuǎn)換查找表。中斷返回，進(jìn)程重新執(zhí)行觸發(fā)中斷的指令，并繼續(xù)運(yùn)行。當(dāng)進(jìn)程釋放一塊內(nèi)存區(qū)域后，內(nèi)核會(huì)立即收回分配給該區(qū)域的物理內(nèi)存頁面。malloc軟件下面內(nèi)容節(jié)選自文章《內(nèi)存相關(guān)分享》，連接為/CppExplore/archive/2010/03/30/111049.html應(yīng)用層面的開發(fā)并不是直接調(diào)用sbrk/mmap之類的函數(shù)，而是調(diào)用malloc/free等malloc子系統(tǒng)提供的函數(shù)，linux上安裝的大多為DougLea的dlmalloc或者其變形ptmalloc。下面以dlmalloc為例說明malloc工作的原理。

1dlmalloc下名詞解釋：

boundarytag:邊界標(biāo)記，每個(gè)空閑內(nèi)存塊均有頭部表識(shí)和尾部標(biāo)識(shí)，尾部表識(shí)的作為是合并空閑內(nèi)存塊時(shí)更快。這部分空間屬于無法被應(yīng)用層面使用浪費(fèi)的內(nèi)存空間。

smallbins:小內(nèi)存箱。dlmalloc將8,16,24......512大小的內(nèi)存分箱，相臨箱子中的內(nèi)存相差8字節(jié)。每個(gè)箱子中的內(nèi)存大小均相同，并且以雙向鏈表連接。

treebins:樹結(jié)構(gòu)箱。大于512字節(jié)的內(nèi)存不再是每8字節(jié)1箱，而是一個(gè)范圍段一箱。比如512~640,640~896.....每個(gè)箱子的范圍段依次是128，256，512......。每箱中的結(jié)構(gòu)不再是雙向鏈表，而是樹形結(jié)構(gòu)。

dvchunk:

當(dāng)申請(qǐng)內(nèi)存而在對(duì)應(yīng)大小的箱中找不到大小合適的內(nèi)存，則從更大的箱中找一塊內(nèi)存，劃分出需要的內(nèi)存，剩余的內(nèi)存稱之為dvchunk.

topchunk:當(dāng)dlmalloc中管理的內(nèi)存都找不到合適的內(nèi)存時(shí)，則調(diào)用sbrk從系統(tǒng)申請(qǐng)內(nèi)存，可以增長內(nèi)存方向的chunk稱為topchunk.

2內(nèi)存分配算法

從合適的箱子中尋找內(nèi)存塊-->從相臨的箱子中尋找內(nèi)存塊-->從dvchunk分配內(nèi)存-->從其他可行的箱子中分配內(nèi)存-->從topchunk中分配內(nèi)存-->調(diào)用sbrk/mmap申請(qǐng)內(nèi)存

3內(nèi)存釋放算法

臨近內(nèi)存合并-->如屬于topchunk，判斷topchunk>128k，是則歸還系統(tǒng)

-->不屬于chunk，則歸相應(yīng)的箱子

dlmalloc還有小內(nèi)存緩存等其他機(jī)制?？梢钥闯鼋?jīng)過dlmalloc，頻繁調(diào)