第2章 內(nèi)存管理

本章思考題

1．在系統(tǒng)啟動(dòng)時(shí)，ARM Linux內(nèi)核如何知道系統(tǒng)中有多大的內(nèi)存空間？

2．在32bit Linux內(nèi)核中，用戶(hù)空間和內(nèi)核空間的比例通常是3:1，可以修改成2:2嗎？

3．物理內(nèi)存頁(yè)面如何添加到伙伴系統(tǒng)中，是一頁(yè)一頁(yè)添加，還是以2的幾次冪來(lái)加入呢？

4．內(nèi)核的一級(jí)頁(yè)表存放在什么地方？?jī)?nèi)核空間的二級(jí)頁(yè)表又存放在什么地方？

5．用戶(hù)進(jìn)程的一級(jí)頁(yè)表存放在什么地方？二級(jí)頁(yè)表又存放在什么地方？

6．在ARM32系統(tǒng)中，頁(yè)表是如何映射的？在ARM64系統(tǒng)中，頁(yè)表又是如何映射的？

7．請(qǐng)簡(jiǎn)述Linux內(nèi)核在理想情況下頁(yè)面分配器（page allocator）是如何分配出連續(xù)物理頁(yè)面的。

8．在頁(yè)面分配器中，如何從分配掩碼（gfp_mask）中確定可以從哪些zone中分配內(nèi)存？

9．頁(yè)面分配器是按照什么方向來(lái)掃描zone的？

10．為用戶(hù)進(jìn)程分配物理內(nèi)存，分配掩碼應(yīng)該選用GFP_KERNEL，還是GFP_HIGHUSER_MOVABLE呢？

11．slab分配器是如何分配和釋放小內(nèi)存塊的？

12．slab分配器中有一個(gè)著色的概念（cache color），著色有什么作用？

13．slab分配器中的slab對(duì)象有沒(méi)有根據(jù)Per-CPU做一些優(yōu)化？

14．slab增長(zhǎng)并導(dǎo)致大量不用的空閑對(duì)象，該如何解決？

15．請(qǐng)問(wèn)kmalloc、vmalloc和malloc之間有什么區(qū)別以及實(shí)現(xiàn)上的差異？

16．使用用戶(hù)態(tài)的API函數(shù)malloc()分配內(nèi)存時(shí)，會(huì)馬上為其分配物理內(nèi)存嗎？

17．假設(shè)不考慮libc的因素，malloc分配100Byte，那么實(shí)際上內(nèi)核是為其分配100Byte嗎？

18．假設(shè)兩個(gè)用戶(hù)進(jìn)程打印的malloc()分配的虛擬地址是一樣的，那么在內(nèi)核中這兩塊虛擬內(nèi)存是否打架了呢？

19．vm_normal_page()函數(shù)返回的是什么樣頁(yè)面的struct page數(shù)據(jù)結(jié)構(gòu)？為什么內(nèi)存管理代碼中需要這個(gè)函數(shù)？

20．請(qǐng)簡(jiǎn)述get_user_page()函數(shù)的作用和實(shí)現(xiàn)流程。

21．請(qǐng)簡(jiǎn)述follow_page()函數(shù)的作用的實(shí)現(xiàn)流程。

22．請(qǐng)簡(jiǎn)述私有映射和共享映射的區(qū)別。

23．為什么第二次調(diào)用mmap時(shí)，Linux內(nèi)核沒(méi)有捕捉到地址重疊并返回失敗呢？

      #strace捕捉某個(gè)app調(diào)用mmap的情況
      mmap(0x20000000, 819200, PROT_READ|PROT_WRITE,
      MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20000000
      …
      mmap(0x20000000, 4096, PROT_READ|PROT_WRITE,
      MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20000000

24．struct page數(shù)據(jù)結(jié)構(gòu)中的_count和_mapcount有什么區(qū)別？

25．匿名頁(yè)面和page cache頁(yè)面有什么區(qū)別？

26．struct page數(shù)據(jù)結(jié)構(gòu)中有一個(gè)鎖，請(qǐng)問(wèn)trylock_page()和lock_page()有什么區(qū)別？

27．在Linux 2.4.x內(nèi)核中，如何從一個(gè)page找到所有映射該頁(yè)面的VMA？反向映射可以帶來(lái)哪些便利？

28．閱讀Linux 4.0內(nèi)核RMAP機(jī)制的代碼，畫(huà)出父子進(jìn)程之間VMA、AVC、anon_vma和page等數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系圖。

29．在Linux 2.6.34中，RMAP機(jī)制采用了新的實(shí)現(xiàn)，在Linux 2.6.33和之前的版本中稱(chēng)為舊版本RMAP機(jī)制。那么在舊版本RMAP機(jī)制中，如果父進(jìn)程有1000個(gè)子進(jìn)程，每個(gè)子進(jìn)程都有一個(gè)VMA，這個(gè)VMA里面有1000個(gè)匿名頁(yè)面，當(dāng)所有的子進(jìn)程的VMA同時(shí)發(fā)生寫(xiě)復(fù)制時(shí)會(huì)是什么情況呢？

30．當(dāng)page加入lru鏈表中，被其他線(xiàn)程釋放了這個(gè)page，那么lru鏈表如何知道這個(gè)page已經(jīng)被釋放了？

31．kswapd內(nèi)核線(xiàn)程何時(shí)會(huì)被喚醒？

32．LRU鏈表如何知道page的活動(dòng)頻繁程度？

33．kswapd按照什么原則來(lái)?yè)Q出頁(yè)面？

34．kswapd按照什么方向來(lái)掃描zone？

35．kswapd以什么標(biāo)準(zhǔn)來(lái)退出掃描LRU？

36．手持設(shè)備例如Android系統(tǒng)，沒(méi)有swap分區(qū)或者swap文件，kswapd會(huì)掃描匿名頁(yè)面LRU嗎？

37．swappiness的含義是什么？kswapd如何計(jì)算匿名頁(yè)面和page cache之間的掃描比重？

38．當(dāng)系統(tǒng)充斥著大量只訪(fǎng)問(wèn)一次的文件訪(fǎng)問(wèn)（use-one streaming IO）時(shí)，kswapd如何來(lái)規(guī)避這種風(fēng)暴？

39．在回收page cache時(shí)，對(duì)于dirty的page cache, kswapd會(huì)馬上回寫(xiě)嗎？

40．內(nèi)核有哪些頁(yè)面會(huì)被kswapd寫(xiě)回交換分區(qū)？

41．ARM32 Linux如何模擬這個(gè)Linux版本的L_PTE_YOUNG比特位呢？

42．如何理解Refault Distance算法？

43．請(qǐng)簡(jiǎn)述匿名頁(yè)面的生命周期。在什么情況下會(huì)產(chǎn)生匿名頁(yè)面？在什么條件下會(huì)釋放匿名頁(yè)面？

44.KSM是基于什么原理來(lái)合并頁(yè)面的？

45．在KSM機(jī)制里，合并過(guò)程中把page設(shè)置成寫(xiě)保護(hù)的函數(shù)write_protect_page()有這樣一個(gè)判斷：

      if (page_mapcount(page) + 1 + swapped ! = page_count(page)) {
              goto out_unlock;
        }

請(qǐng)問(wèn)這個(gè)判斷的依據(jù)是什么？

46．如果多個(gè)VMA的虛擬頁(yè)面同時(shí)映射了同一個(gè)匿名頁(yè)面，那么此時(shí)page->index應(yīng)該等于多少？

47．為什么Dirty COW小程序可以修改一個(gè)只讀文件的內(nèi)容？

48．在Dirty COW內(nèi)存漏洞中，如果Dirty COW程序沒(méi)有madviseThread線(xiàn)程，即只有procselfmemThread線(xiàn)程，能否修改foo文件的內(nèi)容呢？

49．假設(shè)在內(nèi)核空間獲取了某個(gè)文件對(duì)應(yīng)的page cache頁(yè)面的struct page數(shù)據(jù)結(jié)構(gòu)，而對(duì)應(yīng)的VMA屬性是只讀，那么內(nèi)核空間是否可以成功修改該文件呢？

50．如果用戶(hù)進(jìn)程使用只讀屬性（PROT_READ）來(lái)mmap映射一個(gè)文件到用戶(hù)空間，然后使用memcpy來(lái)寫(xiě)這段內(nèi)存空間，會(huì)是什么樣的情況？

51．請(qǐng)畫(huà)出內(nèi)存管理中常用的數(shù)據(jù)結(jié)構(gòu)的關(guān)系圖，如mm_struct、vma、vaddr、page、pfn、pte、zone、paddr和pg_data等，并思考如下轉(zhuǎn)換關(guān)系。

? 如何由mm數(shù)據(jù)結(jié)構(gòu)和虛擬地址vaddr找到對(duì)應(yīng)的VMA？

? 如何由page和VMA找到虛擬地址vaddr？

? 如何由page找到所有映射的VMA？

? 如何由VMA和虛擬地址vaddr找出相應(yīng)的page數(shù)據(jù)結(jié)構(gòu)？

? page和pfn之間的互換。

? pfn和paddr之間的互換。

? page和pte之間的互換。

? zone和page之間的互換。

? zone和pg_data之間的互換。

52．請(qǐng)畫(huà)出在最糟糕的情況下分配若干個(gè)連續(xù)物理頁(yè)面的流程圖。

53．在Android中新添加了LMK（Low Memory Killer），請(qǐng)描述LMK和OOM Killer之間的關(guān)系。

54．請(qǐng)描述一致性DMA映射dma_alloc_coherent()函數(shù)在ARM中是如何管理cache一致性的？

55．請(qǐng)描述流式DMA映射dma_map_single()函數(shù)在ARM中是如何管理cache一致性的？

56．為什么在Linux 4.8內(nèi)核中要把基于zone的LRU鏈表機(jī)制遷移到基于Node呢？

很多同學(xué)接觸Linux的內(nèi)存管理是從malloc()這個(gè)C語(yǔ)言庫(kù)函數(shù)開(kāi)始的，也是從那時(shí)開(kāi)始就知道了有虛擬內(nèi)存這個(gè)概念，那虛擬內(nèi)存究竟是什么呢？怎么虛擬？對(duì)于只關(guān)注上層應(yīng)用程序編程的同學(xué)來(lái)說(shuō)，可能不是太關(guān)心這些知識(shí)。可是如果不了解一些這方面知識(shí)，就很難設(shè)計(jì)出高效的應(yīng)用程序。比較早期的操作系統(tǒng)是沒(méi)有虛擬內(nèi)存這個(gè)概念的，為什么現(xiàn)代操作系統(tǒng)都有虛擬內(nèi)存這個(gè)概念，包括Windows和Linux？要弄明白虛擬內(nèi)存，你可能需要了解什么是MMU、頁(yè)表、物理內(nèi)存、物理頁(yè)面、建立映射關(guān)系、按需分配、缺頁(yè)中斷和寫(xiě)時(shí)復(fù)制等機(jī)制和概念。

當(dāng)了解MMU時(shí)，除了要了解MMU工作原理外，還會(huì)接觸到Linux內(nèi)核如何建立頁(yè)表映射，其中也包括用戶(hù)空間頁(yè)表的建立和內(nèi)核空間頁(yè)表的建立，以及內(nèi)核是如何查詢(xún)頁(yè)表和修改頁(yè)表的。

當(dāng)了解物理內(nèi)存和物理頁(yè)面時(shí)，會(huì)接觸到struct pg_data_t、struct zone和struct page等數(shù)據(jù)結(jié)構(gòu)，這3個(gè)數(shù)據(jù)結(jié)構(gòu)描述了系統(tǒng)中物理內(nèi)存的組織架構(gòu)。struct page數(shù)據(jù)結(jié)構(gòu)除了描述一個(gè)4KB大小（或者其他大小）的物理頁(yè)面外，還包含很多復(fù)雜而有趣的成員。

當(dāng)了解怎么分配物理頁(yè)面時(shí)，會(huì)接觸到伙伴系統(tǒng)機(jī)制和頁(yè)面分配器（page allocator），頁(yè)面分配器是內(nèi)存管理中最復(fù)雜的代碼之一。

有了物理內(nèi)存，那怎么和虛擬內(nèi)存建立映射關(guān)系呢？在Linux內(nèi)核中，描述進(jìn)程的虛擬內(nèi)存用struct vm_area_struct數(shù)據(jù)結(jié)構(gòu)。虛擬內(nèi)存和物理內(nèi)存采用建立頁(yè)表的方法來(lái)完成建立映射關(guān)系。為什么和進(jìn)程地址空間建立映射的頁(yè)面有的叫匿名頁(yè)面，而有的叫page cache頁(yè)面呢？

當(dāng)了解malloc()怎么分配出物理內(nèi)存時(shí)，會(huì)接觸到缺頁(yè)中斷，缺頁(yè)中斷也是內(nèi)存管理中最復(fù)雜的代碼之一。

這時(shí)，虛擬內(nèi)存和物理內(nèi)存已經(jīng)建立了映射關(guān)系，這是以頁(yè)為基礎(chǔ)的，可是有時(shí)內(nèi)核需要小于一個(gè)頁(yè)面大小的內(nèi)存，那么slab機(jī)制就誕生了。

上面已經(jīng)建立起虛擬內(nèi)存和物理內(nèi)存的基本框圖，但是如果用戶(hù)持續(xù)分配和使用內(nèi)存導(dǎo)致物理內(nèi)存不足了怎么辦？此時(shí)頁(yè)面回收機(jī)制和反向映射機(jī)制就應(yīng)運(yùn)而生了。

虛擬內(nèi)存和物理內(nèi)存的映射關(guān)系經(jīng)常是建立后又被解除了，時(shí)間長(zhǎng)了，系統(tǒng)物理頁(yè)面布局變得凌亂不堪，碎片化嚴(yán)重，這時(shí)內(nèi)核如果需要分配大塊連續(xù)內(nèi)存就會(huì)變得很困難，那么內(nèi)存規(guī)整機(jī)制（Memory Compaction）就誕生了。

上述是一位笨叔叔學(xué)習(xí)Linux內(nèi)核內(nèi)存管理知識(shí)中痛并快樂(lè)著的心路歷程。

本章主要介紹Linux內(nèi)核管理中一些基本的知識(shí)，包括內(nèi)存初始化、頁(yè)表映射過(guò)程、內(nèi)核內(nèi)存布局圖、伙伴系統(tǒng)、slab分配器、vmalloc、VMA操作、malloc、mmap、缺頁(yè)中斷、page引用計(jì)數(shù)、反向映射、頁(yè)面回收、匿名頁(yè)面的宿命、頁(yè)面遷移、內(nèi)存規(guī)整、KSM、Dirty COW等內(nèi)容，內(nèi)存管理包羅萬(wàn)象，本書(shū)不可能面面俱到。

本章大部分內(nèi)容是以ARM Vexpress平臺(tái)為例來(lái)講述的，如何搭建該實(shí)驗(yàn)平臺(tái)請(qǐng)參考第6.1節(jié)。建議讀者先閱讀第6.1節(jié)，并且在Ubuntu 16.04機(jī)器上先搭建這樣一個(gè)簡(jiǎn)單好用的實(shí)驗(yàn)平臺(tái)，本章列出的一些實(shí)驗(yàn)數(shù)據(jù)可能和讀者的數(shù)據(jù)有些許不同。

除了依照本章列出來(lái)的思考題來(lái)閱讀內(nèi)存管理代碼之外，從用戶(hù)態(tài)的API來(lái)深入了解Linux內(nèi)核的內(nèi)存管理機(jī)制也是一個(gè)很好的方法，下面列出常見(jiàn)的用戶(hù)態(tài)內(nèi)存管理相關(guān)的API。

      void *malloc(size_t size);
      void free(void *ptr);

      void *mmap(void *addr, size_t length, int prot, int flags,
                  int fd, off_t offset);
      int munmap(void *addr, size_t length);

      int getpagesize(void);

      int mprotect(const void *addr, size_t len, int prot);

      int mlock(const void *addr, size_t len);
      int munlock(const void *addr, size_t len);

      int madvise(void *addr, size_t length, int advice);
      void *mremap(void *old_address, size_t old_size,
                size_t new_size, int flags, ... /* void *new_address */);

      int remap_file_pages(void *addr, size_t size, int prot,
                  ssize_t pgoff, int flags);

第2.8節(jié)講述malloc()函數(shù)在Linux內(nèi)核的實(shí)現(xiàn)，第2.9節(jié)講述mmap()在Linux內(nèi)核中的實(shí)現(xiàn)，第2.17節(jié)用到madvise()這個(gè)API，相信讀者閱讀完本章之后會(huì)更容易理解這些用戶(hù)態(tài)API的實(shí)現(xiàn)。

第2.19節(jié)總結(jié)了Linux內(nèi)核內(nèi)存管理中常用的數(shù)據(jù)結(jié)構(gòu)之間錯(cuò)綜復(fù)雜的關(guān)系，同時(shí)也歸納了內(nèi)核中常用的內(nèi)存管理相關(guān)的API，相信讀者在了解數(shù)據(jù)結(jié)構(gòu)和API之后對(duì)內(nèi)存管理會(huì)有更深刻的理解。

為了行文方便，本章有如下一些約定。

? 忽略了對(duì)大頁(yè)面的處理，默認(rèn)省略了CONFIG_TRANSPARENT_HUGEPAGE的支持。

? 默認(rèn)省略了對(duì)鎖的討論，關(guān)于鎖在內(nèi)存管理中的應(yīng)用詳見(jiàn)第4.7節(jié)。

? 對(duì)page cache的討論比較少。

? 由于本書(shū)的實(shí)驗(yàn)對(duì)象ARM Vexpress平臺(tái)不支持NUMA架構(gòu)，因此為了簡(jiǎn)化默認(rèn)，本章忽略了對(duì)NUMA相關(guān)代碼的討論。

? 忽略了對(duì)memory cgroup的討論。