Linux操作系統(tǒng)分析8 memory.ppt

1、Linux操作系統(tǒng)分析,中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 陳香蘭（051287161312） Autumn 2010,內(nèi)存管理,2020/8/3,Linux OS Analysis,3/59,內(nèi)存管理,在前面已經(jīng)提到： Linux如何有效地利用x86的分段和分頁(yè)機(jī)制把邏輯地址轉(zhuǎn)換為物理地址 RAM的某些部分永久地分配給內(nèi)核，用以存放內(nèi)核代碼以及靜態(tài)數(shù)據(jù) RAM的其余部分稱為動(dòng)態(tài)存儲(chǔ)器（dynamic memory）,2020/8/3,Linux OS Analysis,4/59,Linux內(nèi)核的前512個(gè)頁(yè)框（假定內(nèi)核所需內(nèi)存1MB，from ULK2）,不可用的頁(yè)框,可用的頁(yè)框,內(nèi)核代碼,初始化過(guò)的

2、內(nèi)核數(shù)據(jù),未初始化過(guò)的內(nèi)核數(shù)據(jù),2020/8/3,Linux OS Analysis,5/59,動(dòng)態(tài)存儲(chǔ)器,進(jìn)程和內(nèi)核都需要?jiǎng)討B(tài)存儲(chǔ)器 屬于稀缺資源 整個(gè)系統(tǒng)的性能取決于如何有效地管理動(dòng)態(tài)存儲(chǔ)器 對(duì)動(dòng)態(tài)存儲(chǔ)器的使用要進(jìn)行優(yōu)化 原則：對(duì)于動(dòng)態(tài)存儲(chǔ)器要盡可能做到： 按需分配，不需要時(shí)釋放,2020/8/3,Linux OS Analysis,6/59,主要內(nèi)容,內(nèi)核如何給自己分配動(dòng)態(tài)存儲(chǔ)器 頁(yè)框管理 小內(nèi)存管理 非連續(xù)存儲(chǔ)區(qū)管理,2020/8/3,Linux OS Analysis,7/59,1、頁(yè)框管理,Linux采用頁(yè)作為內(nèi)存管理的基本單位 Linux采用的標(biāo)準(zhǔn)的頁(yè)框大小為4KB 由分頁(yè)單元引

3、發(fā)的缺頁(yè)異常很容易得到解釋 4KB是大多數(shù)磁盤塊大小的倍數(shù) 傳輸效率高 管理方便 例如：512M的物理內(nèi)存對(duì)應(yīng)于？個(gè)頁(yè)框？,2020/8/3,Linux OS Analysis,8/59,內(nèi)核必須記錄每個(gè)頁(yè)框的當(dāng)前狀態(tài) 哪些屬于進(jìn)程，哪些存放了內(nèi)核代碼/數(shù)據(jù) 對(duì)于動(dòng)態(tài)存儲(chǔ)器中的頁(yè)框：是否空閑，即是否可用 如果一個(gè)頁(yè)框不可用，內(nèi)核需要知道是誰(shuí)在用這個(gè)頁(yè)框 用戶態(tài)進(jìn)程、動(dòng)態(tài)分配的內(nèi)核數(shù)據(jù)結(jié)構(gòu)、靜態(tài)的內(nèi)核代碼、頁(yè)面cache、設(shè)備驅(qū)動(dòng)程序緩沖的數(shù)據(jù)等等,2020/8/3,Linux OS Analysis,9/59,頁(yè)描述符,內(nèi)核使用頁(yè)描述符來(lái)跟蹤管理物理內(nèi)存 每個(gè)物理頁(yè)框都用一個(gè)頁(yè)描述符表示 頁(yè)描

4、述符用struct page的結(jié)構(gòu)描述 參見(jiàn)mm_types.h 所有物理頁(yè)框的描述符，組織在mem_map的數(shù)組中,2020/8/3,Linux OS Analysis,10/59,mem_map數(shù)組,每個(gè)物理頁(yè)框，使用一個(gè)struct page表示，它們組織在mem_map數(shù)組中,相當(dāng)于物理內(nèi)存的一個(gè)縮影,2020/8/3,Linux OS Analysis,11/59,頁(yè)描述符中的各個(gè)字段將在用到時(shí)再逐步介紹，首先看一下 count：頁(yè)的使用引用計(jì)數(shù)器 0：空閑 0：頁(yè)已經(jīng)分配給一個(gè)或多個(gè)進(jìn)程或用戶某些內(nèi)核數(shù)據(jù)結(jié)構(gòu) flags：頁(yè)框狀態(tài)，最多可以有32個(gè)，每個(gè)使用一個(gè)位表示,2020/8

5、/3,Linux OS Analysis,12/59,頁(yè)框狀態(tài),2020/8/3,Linux OS Analysis,13/59,頁(yè)描述符將會(huì)占用很大的一段空間,由于每個(gè)struct page結(jié)構(gòu)小于64個(gè)字節(jié)，因此1MB的內(nèi)存需要使用約4個(gè)頁(yè)面來(lái)存放mem_map數(shù)組 假若系統(tǒng)中存在512MB的內(nèi)存，那么大約需要？,2020/8/3,Linux OS Analysis,14/59,關(guān)于NUMA,不考慮 物理內(nèi)存被劃分為若干個(gè)node 存取時(shí)間不等 考慮CPU局部性 Node使用數(shù)據(jù)結(jié)構(gòu)pg_data_t描述 每個(gè)node被劃分成若干個(gè)zone,2020/8/3,Linux OS Analys

6、is,15/59,存儲(chǔ)區(qū)(Memory Zones),在一個(gè)理想的體系結(jié)構(gòu)中，一個(gè)頁(yè)框就是一個(gè)物理存儲(chǔ)單元，可以用于任何事情，例如 存放內(nèi)核數(shù)據(jù)/用戶數(shù)據(jù)/緩存磁盤數(shù)據(jù)等 實(shí)際上存在硬件制約：一些頁(yè)框由于自身的物理地址的原因不能被一些任務(wù)所使用，例如 ISA總線的DMA控制器只能對(duì)ram的前16M尋址 在一些具有大容量ram的32位計(jì)算機(jī)中，CPU不能直接訪問(wèn)所有的物理存儲(chǔ)器，因?yàn)榫€性地址空間不夠,2020/8/3,Linux OS Analysis,16/59,zone,為了應(yīng)付這種限制，Linux把具有同樣性質(zhì)的物理內(nèi)存劃分成區(qū)(zones) Linux把物理存儲(chǔ)器劃分為4個(gè)區(qū) ZONE_

7、DMA ZONE_DMA32 (未見(jiàn)用） ZONE_NORMAL ZONE_HIGHMEM 參見(jiàn)枚舉類型zone_type,ZONE_DMAZONE_NORMALZONE_HIGHMEM,物理內(nèi)存,0,16MB,896MB,MAX,2020/8/3,Linux OS Analysis,17/59,ZONE_DMA 和ZONE_NORMAL區(qū)包含存儲(chǔ)器的“常規(guī)”頁(yè)，通過(guò)把它們映射到線性地址空間的3GB以上，內(nèi)核就可直接訪問(wèn) 而ZONE_HIGHMEN區(qū)中包含的存儲(chǔ)器頁(yè)面不能由內(nèi)核直接訪問(wèn),MAX,ZONE_DMA ZONE_NORMALZONE_HIGHMEM,物理內(nèi)存,0,16MB,896MB

8、,線性空間,3G,3GB,4GB,3GB+16MB,3GB+896MB,2020/8/3,Linux OS Analysis,18/59,每個(gè)zone使用struct zone表示 關(guān)鍵：free_area 小結(jié)： Mem_map、node、zone之間的關(guān)系,2020/8/3,Linux OS Analysis,19/59,動(dòng)態(tài)內(nèi)存,內(nèi)存布局： 動(dòng)態(tài)內(nèi)存及引用它的一些值,2020/8/3,Linux OS Analysis,20/59,請(qǐng)求頁(yè)框,內(nèi)核實(shí)現(xiàn)了一種底層的內(nèi)存分配機(jī)制，并提供了幾個(gè)接口供其他內(nèi)核函數(shù)調(diào)用。 分配： alloc_pages/alloc_page/alloc_pages

9、_node/alloc_pages_current/ _get_free_pages/_get_free_page/_get_dma_pages/get_zeroed_page 釋放 free_pages/_free_pages/free_page/_free_page,2020/8/3,Linux OS Analysis,21/59,調(diào)用關(guān)鍵函數(shù)：get_page_from_freelist,2020/8/3,Linux OS Analysis,22/59,類似alloc_pages，但是返回第一個(gè) 所分配頁(yè)框的線性地址,分配一個(gè)頁(yè)框，返回值同上,用來(lái)分配適用于DMA的頁(yè)框,2020/8/3

10、,Linux OS Analysis,23/59,這個(gè)函數(shù)與_get_free_page基本等價(jià)， 差別在于它把所分配頁(yè)框中的頁(yè)面數(shù)據(jù) 全部清0。 這在給用戶態(tài)的空間分配頁(yè)框時(shí)候很有 用。因?yàn)檫@個(gè)頁(yè)框雖然是可被分配的， 但是里面的數(shù)據(jù)可能包含了內(nèi)核的一些 敏感信息。 清0，可以避免信息泄露,2020/8/3,Linux OS Analysis,24/59,關(guān)于unsigned int gfp_mask,指明可在何處并以何種方式查找空閑的頁(yè)框 GFP_ATOMIC，這種分配是高優(yōu)先級(jí)的并且不能睡眠。一般在中斷處理程序，下半部分和其他不能睡眠的場(chǎng)合下使用 GFP_KERNEL，這是普通的分配模式，

11、允許睡眠。一般在用戶進(jìn)程可能調(diào)用到的內(nèi)核函數(shù)中使用，這個(gè)時(shí)候進(jìn)程是可以安全的睡眠的 GFP_DMA，設(shè)備驅(qū)動(dòng)程序需要DMA內(nèi)存時(shí)使用,2020/8/3,Linux OS Analysis,25/59,關(guān)于gfp_mask的進(jìn)一步解釋,標(biāo)志位及其含義,2020/8/3,Linux OS Analysis,26/59,2020/8/3,Linux OS Analysis,27/59,等等,2020/8/3,Linux OS Analysis,28/59,釋放頁(yè)框,如果page對(duì)應(yīng)的頁(yè)框不是被保留的頁(yè)框(PG_reserved標(biāo)志為0)，就 把描述符的count字段減1。如果count變?yōu)?，就調(diào)用

12、釋放,與上一個(gè)函數(shù)類似，只是第一個(gè)參數(shù)是要釋放的 第一個(gè)頁(yè)框的線性地址addr,2020/8/3,Linux OS Analysis,29/59,在內(nèi)核中釋放頁(yè)框時(shí)要非常小心，必須確保只釋放了所請(qǐng)求的頁(yè)框，否則內(nèi)核可能會(huì)崩潰,page = _get_free_page(GFP_KERNEL,3); If (!page) /*如果內(nèi)存不足，分配失敗，必須在這里處理這個(gè)失敗*/ /*現(xiàn)在page變量指向了8個(gè)連續(xù)頁(yè)框的起始線性地址*/ free_pages(page,3); /*現(xiàn)在頁(yè)框被釋放，不應(yīng)該再對(duì)page中存放的線性地址進(jìn)行操作*/,2020/8/3,Linux OS Analysis,3

13、0/59,頁(yè)框的管理,內(nèi)核要為分配一組連續(xù)的頁(yè)框建立一種穩(wěn)定、高效的分配策略 這種策略要解決（外部）碎片問(wèn)題： 頻繁的請(qǐng)求和釋放不同大小的一組連續(xù)頁(yè)框，必然導(dǎo)致在物理頁(yè)框中分散許多小塊的空閑頁(yè)框 這樣，即使有足夠的空閑頁(yè)框滿足請(qǐng)求，但要分配一個(gè)大塊的連續(xù)頁(yè)框可能就無(wú)法滿足了,2020/8/3,Linux OS Analysis,31/59,有兩種辦法可以避免這樣的碎片 利用MMU把一組非連續(xù)的物理空閑頁(yè)框映射到連續(xù)的線性地址空間 使用一種適當(dāng)?shù)募夹g(shù)來(lái)記錄現(xiàn)存的空閑連續(xù)頁(yè)框的情況，以盡量避免為滿足對(duì)小塊的請(qǐng)求而把大塊的空閑塊進(jìn)行分割 基于下面的原因，Linux內(nèi)核首選第二種方法 在某些情況下，必

14、須使用連續(xù)的頁(yè)框，如DMA 盡量少的修改內(nèi)核頁(yè)表,2020/8/3,Linux OS Analysis,32/59,buddy算法（伙伴算法）,Linux使用著名的伙伴算法來(lái)解決碎片問(wèn)題。 把所有空閑頁(yè)框分組為10（Linux2.6.26為11）個(gè)塊鏈表，每個(gè)塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256和512個(gè)連續(xù)的頁(yè)框 每個(gè)塊的第一個(gè)頁(yè)框的物理地址是該塊大小的整數(shù)倍 例如：大小為16個(gè)頁(yè)框的塊，其起址是164KB的倍數(shù),2020/8/3,Linux OS Analysis,33/59,伙伴的定義,例如：0和1是伙伴，1和2不是伙伴 兩個(gè)伙伴的大小必須相同，物理地址必

15、須連續(xù) 假定伙伴的大小為b 那么第一個(gè)伙伴的物理地址必須是2b4KB對(duì)齊 事實(shí)上伙伴是通過(guò)對(duì)大塊的物理內(nèi)存劃分獲得的 假如從第0個(gè)頁(yè)面開(kāi)始到第3個(gè)頁(yè)面結(jié)束的內(nèi)存 每次都對(duì)半劃分，那么第一次劃分獲得大小為2頁(yè)的伙伴 進(jìn)一步劃分，可以獲得大小為1頁(yè)的伙伴，例如0和1，2和3,0,1,2,3,0,1,2,3,2020/8/3,Linux OS Analysis,34/59,數(shù)據(jù)結(jié)構(gòu),Linux為每個(gè)zone使用各自獨(dú)立的伙伴系統(tǒng) 每個(gè)伙伴系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu)為： 空閑內(nèi)存管理數(shù)組free_area,2020/8/3,Linux OS Analysis,35/59,mem_map數(shù)組 前面介紹過(guò)的頁(yè)

16、描述符數(shù)組 每個(gè)頁(yè)描述符描述一個(gè)物理頁(yè)框 整個(gè)mem_map數(shù)組描述整個(gè)zone中的所有的物理內(nèi)存 空閑內(nèi)存管理數(shù)組 空閑內(nèi)存按照伙伴管理的方法進(jìn)行組織 使用free_area結(jié)構(gòu),2020/8/3,Linux OS Analysis,36/59,伙伴,當(dāng)兩個(gè)伙伴都為空閑的時(shí)候，就合并成一個(gè)更大的塊 該過(guò)程將一直進(jìn)行，直到找不到可以合并的伙伴為止 尋找伙伴 給定一個(gè)要釋放的空閑塊 找到其伙伴 查看其狀態(tài)：合并 or 不合并,2020/8/3,Linux OS Analysis,37/59,舉例,假設(shè)有128MB的ram。 128MB最多可以分成215=32768個(gè)頁(yè)框，214=16384個(gè)8K

17、B（2頁(yè)）的塊或213=8192個(gè)16KB（4頁(yè)）的塊，直至64個(gè)大小為512個(gè)頁(yè)的塊 假設(shè)要請(qǐng)求一個(gè)大小為128個(gè)頁(yè)框的塊(0.5MB)。 算法先f(wàn)ree_area7中檢查是否有空閑塊（塊大小為128個(gè)頁(yè)框） 若沒(méi)有，就到free_area8中找一個(gè)空閑塊（塊大小為256個(gè)頁(yè)框） 若存在這樣的塊，內(nèi)核就把256個(gè)頁(yè)框分成兩等份，一半用作滿足請(qǐng)求，另一半插入free_area7中 如果在free_area8中也沒(méi)有空閑塊，就繼續(xù)找free_area9中是否有空閑塊。,2020/8/3,Linux OS Analysis,38/59,若有，先將512分成伙伴，一個(gè)插入free_area8中，另一

18、個(gè)進(jìn)一步劃分成伙伴，取其一插入free_area7中，另一個(gè)分配出去 如果free_area9也沒(méi)有空閑塊，內(nèi)存不夠，返回一個(gè)錯(cuò)誤信號(hào),2020/8/3,Linux OS Analysis,39/59,內(nèi)存的分配與回收,閱讀相關(guān)代碼 關(guān)鍵：nr_free _free_one_page _rmqueue,buffered_rmqueue,get_page_from_freelist,_alloc_pages_internal,_alloc_pages,free_one_page,_free_pages_ok,_free_pages,mm/page_alloc.c,2020/8/3,Linux O

19、S Analysis,40/59,2020/8/3,Linux OS Analysis,41/59,2020/8/3,Linux OS Analysis,42/59,線 性 空 間 ( 3GB4GB),頁(yè)框管理小結(jié),頁(yè)描述符 Mem_map數(shù)組 Zone 空閑頁(yè)框的管理,線性空間(3GB),物理內(nèi)存：highmem,Mem_map 數(shù) 組,物理內(nèi)存： DMA,物理內(nèi)存： Normal,Zone_dma,Zone_normal,Zone_highmem,空閑頁(yè)框管理,空閑頁(yè)框管理,空閑頁(yè)框管理,伙伴算法,2020/8/3,Linux OS Analysis,43/59,2、內(nèi)存區(qū)管理(memor

20、y area),單單分配頁(yè)面的分配器肯定是不能滿足要求的 內(nèi)核中大量使用各種數(shù)據(jù)結(jié)構(gòu)，大小從幾個(gè)字節(jié)到幾十上百k不等，都取整到2的冪次個(gè)頁(yè)面那是完全不現(xiàn)實(shí)的 早期內(nèi)核的解決方法是提供大小為2,4,8,16,.,131056字節(jié)的內(nèi)存區(qū)域 需要新的內(nèi)存區(qū)域時(shí)，內(nèi)核從伙伴系統(tǒng)申請(qǐng)頁(yè)面，把它們劃分成一個(gè)個(gè)區(qū)域，取一個(gè)來(lái)滿足需求 如果某個(gè)頁(yè)面中的內(nèi)存區(qū)域都釋放了，頁(yè)面就交回到伙伴系統(tǒng),2020/8/3,Linux OS Analysis,44/59,但這種分配方法有許多值得改進(jìn)的地方： 不同的數(shù)據(jù)類型用不同的方法分配內(nèi)存可能提高效率。比如需要初始化的數(shù)據(jù)結(jié)構(gòu)，釋放后可以暫存著，再分配時(shí)就不必初始化了

21、內(nèi)核的函數(shù)常常重復(fù)地使用同一類型的內(nèi)存區(qū)，緩存最近釋放的對(duì)象可以加速分配和釋放 對(duì)內(nèi)存的請(qǐng)求可以按照請(qǐng)求頻率來(lái)分類，頻繁使用的類型使用專門的緩存，很少使用的可以使用通用緩存 使用2的冪次大小的內(nèi)存區(qū)域時(shí)硬件高速緩存沖突的概率較大，有可能通過(guò)仔細(xì)安排內(nèi)存區(qū)域的起始地址來(lái)減少硬件高速緩存沖突 緩存一定數(shù)量的對(duì)象可以減少對(duì)buddy系統(tǒng)的調(diào)用，從而節(jié)省時(shí)間并減少由此引起的硬件高速緩存污染,2020/8/3,Linux OS Analysis,45/59,Linux2.6.26中,SLOB Allocator: Simple List Of Blocks NUMA Slab Slub：slab的一個(gè)變

22、種 Kmalloc/kfree 本課介紹基本的slab算法,2020/8/3,Linux OS Analysis,46/59,slab分配器,slab分配器體現(xiàn)了這些改進(jìn)思想 slab分配器把內(nèi)存區(qū)看成對(duì)象 slab分配器把對(duì)象分組放進(jìn)高速緩存。 每個(gè)高速緩存都是同種類型內(nèi)存對(duì)象的一種“儲(chǔ)備” 例如當(dāng)一個(gè)文件被打開(kāi)時(shí)，存放相應(yīng)“打開(kāi)文件”對(duì)象所需的內(nèi)存是從一個(gè)叫做filp(file pointer)的slab分配器的高速緩存中得到的 也就是說(shuō)每種對(duì)象類型對(duì)應(yīng)一個(gè)高速緩存,2020/8/3,Linux OS Analysis,47/59,每個(gè)高速緩存被分成多個(gè)slabs，每個(gè)slab由一個(gè)或多個(gè)

23、連續(xù)的頁(yè)框組成，其中包含一定數(shù)目的對(duì)象,2020/8/3,Linux OS Analysis,48/59,每個(gè)slab有三種狀態(tài)：全滿，半滿，全空 全滿意味著slab中的對(duì)象全部已被分配出去 全空意味著slab中的對(duì)象全部是可用的 半滿介于兩者之間 當(dāng)內(nèi)核函數(shù)需要一個(gè)新的對(duì)象時(shí)， 優(yōu)先從半滿的slab滿足這個(gè)請(qǐng)求 否則從全空的slab中取一個(gè)對(duì)象滿足請(qǐng)求 如果沒(méi)有空的slab則向buddy系統(tǒng)申請(qǐng)頁(yè)面生成一個(gè)新的slab,2020/8/3,Linux OS Analysis,49/59,高速緩存描述符和slab描述符之間的關(guān)系,2020/8/3,Linux OS Analysis,50/59,

24、普通和專用高速緩存,每個(gè)高速緩存使用kmem_cache表示 普通高速緩存根據(jù)大小分配內(nèi)存 26個(gè)，2組（一組用于DMA分配，另一組用于常規(guī)分配） 每組13個(gè)，大小從25=32個(gè)字節(jié)，到217=132017個(gè)字節(jié) 數(shù)據(jù)結(jié)構(gòu)cache_sizes 數(shù)組：malloc_sizes 專用高速緩存根據(jù)類型分配,2020/8/3,Linux OS Analysis,51/59,閱讀文件kmalloc_sizes.h,2020/8/3,Linux OS Analysis,52/59,2020/8/3,Linux OS Analysis,53/59,slab分配器提供的接口,創(chuàng)建專用高速緩存：kmem_cache_create 撤銷專用高速緩存：kmem_cache_destroy 一般內(nèi)核撤銷一個(gè)模塊時(shí)會(huì)調(diào)用這個(gè)函數(shù)撤銷屬于那個(gè)模塊的cache類型 從專用高速緩沖中分配和釋放 從高速緩存中分配/釋放一個(gè)內(nèi)存對(duì)象kmem_cache_alloc/kmem_cache_free 從普通高速緩存中分配和釋放 kmalloc