一、前言

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

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

二、和內(nèi)存模型相關(guān)的術(shù)語

1、什么是page frame？

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

每一個page frame有一個一一對應(yīng)的page數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)中定義了page_to_pfn和pfn_to_page的宏用來在page frame number和page數(shù)據(jù)結(jié)構(gòu)之間進(jìn)行轉(zhuǎn)換，具體如何轉(zhuǎn)換是和memory modle相關(guān)，我們會在第三章詳細(xì)描述linux kernel中的3種內(nèi)存模型。

2、什么是PFN？

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

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

3、什么是NUMA？

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

三、Linux 內(nèi)核中的三種memory model

1、什么是FLAT memory model？

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

需要強(qiáng)調(diào)的是struct page所占用的內(nèi)存位于直接映射（directly mapped）區(qū)間，因此操作系統(tǒng)不需要再為其建立page table。

2、什么是Discontiguous Memory Model？

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

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

3、什么是Sparse Memory Model？

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

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

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

（注意：上圖中的一個mem_section指針應(yīng)該指向一個page，而一個page中有若干個struct mem_section數(shù)據(jù)單元）

整個連續(xù)的物理地址空間是按照一個section一個section來切斷的，每一個section內(nèi)部，其memory是連續(xù)的（即符合flat memory的特點(diǎn)），因此，mem_map的page數(shù)組依附于section結(jié)構(gòu)（struct mem_section）而不是node結(jié)構(gòu)了（struct pglist_data）。當(dāng)然，無論哪一種memory model，都需要處理PFN和page之間的對應(yīng)關(guān)系，只不過sparse memory多了一個section的概念，讓轉(zhuǎn)換變成了PFN<--->Section<--->page。

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

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

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

對于經(jīng)典的sparse memory模型，一個section的struct page數(shù)組所占用的內(nèi)存來自directly mapped區(qū)域，頁表在初始化的時候就建立好了，分配了page frame也就是分配了虛擬地址。但是，對于SPARSEMEM_VMEMMAP而言，虛擬地址一開始就分配好了，是vmemmap開始的一段連續(xù)的虛擬地址空間，每一個page都有一個對應(yīng)的struct page，當(dāng)然，只有虛擬地址，沒有物理地址。因此，當(dāng)一個section被發(fā)現(xiàn)后，可以立刻找到對應(yīng)的struct page的虛擬地址，當(dāng)然，還需要分配一個物理的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數(shù)組（mem_map）index是線性關(guān)系，有一個固定的偏移就是ARCH_PFN_OFFSET，這個偏移是和估計(jì)的architecture有關(guān)。對于ARM64，定義在arch/arm/include/asm/memory.h文件中，當(dāng)然，這個定義是和內(nèi)存所占據(jù)的物理地址空間有關(guān)（即和PHYS_OFFSET的定義有關(guān)）。

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進(jìn)行就OK了。因此對于__pfn_to_page的定義，可以首先通過arch_pfn_to_nid將PFN轉(zhuǎn)換成node id，通過NODE_DATA宏定義可以找到該node對應(yīng)的pglist_data數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)的node_start_pfn記錄了該node的第一個page frame number，因此，也就可以得到其對應(yīng)struct page在node_mem_map的偏移。__page_to_pfn類似，大家可以自己分析。

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

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

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

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

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

?