一、前言

在linux內核中支持3中內存模型，分別是flat memory model，Discontiguous memory model和sparse memory model。所謂memory model，其實就是從cpu的角度看，其物理內存的分布情況，在linux kernel中，使用什么的方式來管理這些物理內存。另外，需要說明的是：本文主要focus在share memory的系統，也就是說所有的CPUs共享一片物理地址空間的。

本文的內容安排如下：為了能夠清楚的解析內存模型，我們對一些基本的術語進行了描述，這在第二章。第三章則對三種內存模型的工作原理進行闡述，最后一章是代碼解析，代碼來自4.4.6內核，對于體系結構相關的代碼，我們采用ARM64進行分析。

二、和內存模型相關的術語

1、什么是page frame？

操作系統最重要的作用之一就是管理計算機系統中的各種資源，做為最重要的資源：內存，我們必須管理起來。在linux操作系統中，物理內存是按照page size來管理的，具體page size是多少是和硬件以及linux系統配置相關的，4k是最經典的設定。因此，對于物理內存，我們將其分成一個個按page size排列的page，每一個物理內存中的page size的內存區域我們稱之page frame。我們針對每一個物理的page frame建立一個struct page的數據結構來跟蹤每一個物理頁面的使用情況：是用于內核的正文段？還是用于進程的頁表？是用于各種file cache還是處于free狀態……

每一個page frame有一個一一對應的page數據結構，系統中定義了page_to_pfn和pfn_to_page的宏用來在page frame number和page數據結構之間進行轉換，具體如何轉換是和memory modle相關，我們會在第三章詳細描述linux kernel中的3種內存模型。

2、什么是PFN？

對于一個計算機系統，其整個物理地址空間應該是從0開始，到實際系統能支持的最大物理空間為止的一段地址空間。在ARM系統中，假設物理地址是32個bit，那么其物理地址空間就是4G，在ARM64系統中，如果支持的物理地址bit數目是48個，那么其物理地址空間就是256T。當然，實際上這么大的物理地址空間并不是都用于內存，有些也屬于I/O空間（當然，有些cpu arch有自己獨立的io address space）。因此，內存所占據的物理地址空間應該是一個有限的區間，不可能覆蓋整個物理地址空間。不過，現在由于內存越來越大，對于32位系統，4G的物理地址空間已經無法滿足內存的需求，因此會有high memory這個概念，后續會詳細描述。

PFN是page frame number的縮寫，所謂page frame，就是針對物理內存而言的，把物理內存分成一個個的page size的區域，并且給每一個page 編號，這個號碼就是PFN。假設物理內存從0地址開始，那么PFN等于0的那個頁幀就是0地址（物理地址）開始的那個page。假設物理內存從x地址開始，那么第一個頁幀號碼就是（x>>PAGE_SHIFT）。

3、什么是NUMA？

在為multiprocessors系統設計內存架構的時候有兩種選擇：一種就是UMA（Uniform memory access），系統中的所有的processor共享一個統一的，一致的物理內存空間，無論從哪一個processor發起訪問，對內存地址的訪問時間都是一樣的。NUMA（Non-uniform memory access）和UMA不同，對某個內存地址的訪問是和該memory與processor之間的相對位置有關的。例如，對以某個節點（node）上的processor而言，訪問local memory要比訪問那些remote memory花的時間長。

三、Linux 內核中的三種memory model

1、什么是FLAT memory model？

如果從系統中任意一個processor的角度來看，當它訪問物理內存的時候，物理地址空間是一個連續的，沒有空洞的地址空間，那么這種計算機系統的內存模型就是Flat memory。這種內存模型下，物理內存的管理比較簡單，每一個物理頁幀都會有一個page數據結構來抽象，因此系統中存在一個struct page的數組（mem_map），每一個數組條目指向一個實際的物理頁幀（page frame）。在flat memory的情況下，PFN（page frame number）和mem_map數組index的關系是線性的（有一個固定偏移，如果內存對應的物理地址等于0，那么PFN就是數組index）。因此從PFN到對應的page數據結構是非常容易的，反之亦然，具體可以參考page_to_pfn和pfn_to_page的定義。此外，對于flat memory model，節點（struct pglist_data）只有一個（為了和Discontiguous Memory Model采用同樣的機制）。下面的圖片描述了flat memory的情況：

需要強調的是struct page所占用的內存位于直接映射（directly mapped）區間，因此操作系統不需要再為其建立page table。

2、什么是Discontiguous Memory Model？

如果cpu在訪問物理內存的時候，其地址空間有一些空洞，是不連續的，那么這種計算機系統的內存模型就是Discontiguous memory。一般而言，NUMA架構的計算機系統的memory model都是選擇Discontiguous Memory，不過，這兩個概念其實是不同的。NUMA強調的是memory和processor的位置關系，和內存模型其實是沒有關系的，只不過，由于同一node上的memory和processor有更緊密的耦合關系（訪問更快），因此需要多個node來管理。Discontiguous memory本質上是flat memory內存模型的擴展，整個物理內存的address space大部分是成片的大塊內存，中間會有一些空洞，每一個成片的memory address space屬于一個node（如果局限在一個node內部，其內存模型是flat memory）。下面的圖片描述了Discontiguous memory的情況：

因此，這種內存模型下，節點數據（struct pglist_data）有多個，宏定義NODE_DATA可以得到指定節點的struct pglist_data。而，每個節點管理的物理內存保存在struct pglist_data 數據結構的node_mem_map成員中（概念類似flat memory中的mem_map）。這時候，從PFN轉換到具體的struct page會稍微復雜一點，我們首先要從PFN得到node ID，然后根據這個ID找到對于的pglist_data 數據結構，也就找到了對應的page數組，之后的方法就類似flat memory了。

3、什么是Sparse Memory Model？

Memory model也是一個演進過程，剛開始的時候，使用flat memory去抽象一個連續的內存地址空間（mem_maps[]），出現NUMA之后，整個不連續的內存空間被分成若干個node，每個node上是連續的內存地址空間，也就是說，原來的單一的一個mem_maps[]變成了若干個mem_maps[]了。一切看起來已經完美了，但是memory hotplug的出現讓原來完美的設計變得不完美了，因為即便是一個node中的mem_maps[]也有可能是不連續了。其實，在出現了sparse memory之后，Discontiguous memory內存模型已經不是那么重要了，按理說sparse memory最終可以替代Discontiguous memory的，這個替代過程正在進行中，4.4的內核仍然是有3中內存模型可以選擇。

為什么說sparse memory最終可以替代Discontiguous memory呢？實際上在sparse memory內存模型下，連續的地址空間按照SECTION（例如1G）被分成了一段一段的，其中每一section都是hotplug的，因此sparse memory下，內存地址空間可以被切分的更細，支持更離散的Discontiguous memory。此外，在sparse memory沒有出現之前，NUMA和Discontiguous memory總是剪不斷，理還亂的關系：NUMA并沒有規定其內存的連續性，而Discontiguous memory系統也并非一定是NUMA系統，但是這兩種配置都是multi node的。有了sparse memory之后，我們終于可以把內存的連續性和NUMA的概念剝離開來：一個NUMA系統可以是flat memory，也可以是sparse memory，而一個sparse memory系統可以是NUMA，也可以是UMA的。

下面的圖片說明了sparse memory是如何管理page frame的（配置了SPARSEMEM_EXTREME）：

（注意：上圖中的一個mem_section指針應該指向一個page，而一個page中有若干個struct mem_section數據單元）

整個連續的物理地址空間是按照一個section一個section來切斷的，每一個section內部，其memory是連續的（即符合flat memory的特點），因此，mem_map的page數組依附于section結構（struct mem_section）而不是node結構了（struct pglist_data）。當然，無論哪一種memory model，都需要處理PFN和page之間的對應關系，只不過sparse memory多了一個section的概念，讓轉換變成了PFN<--->Section<--->page。

我們首先看看如何從PFN到page結構的轉換：kernel中靜態定義了一個mem_section的指針數組，一個section中往往包括多個page，因此需要通過右移將PFN轉換成section number，用section number做為index在mem_section指針數組可以找到該PFN對應的section數據結構。找到section之后，沿著其section_mem_map就可以找到對應的page數據結構。順便一提的是，在開始的時候，sparse memory使用了一維的memory_section數組（不是指針數組），這樣的實現對于特別稀疏（CONFIG_SPARSEMEM_EXTREME）的系統非常浪費內存。此外，保存指針對hotplug的支持是比較方便的，指針等于NULL就意味著該section不存在。上面的圖片描述的是一維mem_section指針數組的情況（配置了SPARSEMEM_EXTREME），對于非SPARSEMEM_EXTREME配置，概念是類似的，具體操作大家可以自行閱讀代碼。

從page到PFN稍微有一點麻煩，實際上PFN分成兩個部分：一部分是section index，另外一個部分是page在該section的偏移。我們需要首先從page得到section index，也就得到對應的memory_section，知道了memory_section也就知道該page在section_mem_map，也就知道了page在該section的偏移，最后可以合成PFN。對于page到section index的轉換，sparse memory有2種方案，我們先看看經典的方案，也就是保存在page->flags中（配置了SECTION_IN_PAGE_FLAGS）。這種方法的最大的問題是page->flags中的bit數目不一定夠用，因為這個flag中承載了太多的信息，各種page flag，node id，zone id現在又增加一個section id，在不同的architecture中無法實現一致性的算法，有沒有一種通用的算法呢？這就是CONFIG_SPARSEMEM_VMEMMAP。具體的算法可以參考下圖：

（上面的圖片有一點問題，vmemmap只有在PHYS_OFFSET等于0的情況下才指向第一個struct page數組，一般而言，應該有一個offset的，不過，懶得改了，哈哈）

對于經典的sparse memory模型，一個section的struct page數組所占用的內存來自directly mapped區域，頁表在初始化的時候就建立好了，分配了page frame也就是分配了虛擬地址。但是，對于SPARSEMEM_VMEMMAP而言，虛擬地址一開始就分配好了，是vmemmap開始的一段連續的虛擬地址空間，每一個page都有一個對應的struct page，當然，只有虛擬地址，沒有物理地址。因此，當一個section被發現后，可以立刻找到對應的struct page的虛擬地址，當然，還需要分配一個物理的page frame，然后建立頁表什么的，因此，對于這種sparse memory，開銷會稍微大一些（多了個建立映射的過程）。

四、代碼分析

我們的代碼分析主要是通過include/asm-generic/memory_model.h展開的。

1、flat memory。代碼如下：

#define __pfn_to_page(pfn)??? (mem_map + ((pfn) - ARCH_PFN_OFFSET))?
#define __page_to_pfn(page)??? ((unsigned long)((page) - mem_map) + ARCH_PFN_OFFSET)

由代碼可知，PFN和struct page數組（mem_map）index是線性關系，有一個固定的偏移就是ARCH_PFN_OFFSET，這個偏移是和估計的architecture有關。對于ARM64，定義在arch/arm/include/asm/memory.h文件中，當然，這個定義是和內存所占據的物理地址空間有關（即和PHYS_OFFSET的定義有關）。

2、Discontiguous Memory Model。代碼如下：

#define __pfn_to_page(pfn)??????????? \?
({??? unsigned long __pfn = (pfn);??????? \?
??? unsigned long __nid = arch_pfn_to_nid(__pfn);? \?
??? NODE_DATA(__nid)->node_mem_map + arch_local_page_offset(__pfn, __nid);\?
})

#define __page_to_pfn(pg)??????????????????????? \?
({??? const struct page *__pg = (pg);??????????????????? \?
??? struct pglist_data *__pgdat = NODE_DATA(page_to_nid(__pg));??? \?
??? (unsigned long)(__pg - __pgdat->node_mem_map) +??????????? \?
???? __pgdat->node_start_pfn;??????????????????? \?
})

Discontiguous Memory Model需要獲取node id，只要找到node id，一切都好辦了，比對flat memory model進行就OK了。因此對于__pfn_to_page的定義，可以首先通過arch_pfn_to_nid將PFN轉換成node id，通過NODE_DATA宏定義可以找到該node對應的pglist_data數據結構，該數據結構的node_start_pfn記錄了該node的第一個page frame number，因此，也就可以得到其對應struct page在node_mem_map的偏移。__page_to_pfn類似，大家可以自己分析。

3、Sparse Memory Model。經典算法的代碼我們就不看了，一起看看配置了SPARSEMEM_VMEMMAP的代碼，如下：

#define __pfn_to_page(pfn)??? (vmemmap + (pfn))?
#define __page_to_pfn(page)??? (unsigned long)((page) - vmemmap)

簡單而清晰，PFN就是vmemmap這個struct page數組的index啊。對于ARM64而言，vmemmap定義如下：

#define vmemmap??????????? ((struct page *)VMEMMAP_START - \?
???????????????? SECTION_ALIGN_DOWN(memstart_addr >> PAGE_SHIFT))

毫無疑問，我們需要在虛擬地址空間中分配一段地址來安放struct page數組（該數組包含了所有物理內存跨度空間page），也就是VMEMMAP_START的定義。

?