物理內(nèi)存的組織方式
前面咱們講虛擬內(nèi)存，涉及物理內(nèi)存的映射的時候，我們總是把內(nèi)存想象成它是由連續(xù)的一頁一頁地塊組成的。我們可以從 0 開始對物理頁編號，這樣每個物理頁都會有個頁號。
由于物理地址是連續(xù)的，頁也是連續(xù)的，每個頁大小也是一樣的。因而對于任何一個地址，只要直接除一下每頁的大小，很容易直接算出在哪一頁。每個頁面有一個結(jié)構(gòu) struct page 表示，這個結(jié)構(gòu)也是放在一個數(shù)組里面，這樣根據(jù)頁號，很容易通過下標找到相應(yīng)的 struct page 結(jié)構(gòu)。
如果是這樣，整個物理內(nèi)存的布局就非常簡單、易管理，這就是最經(jīng)典的平坦內(nèi)存模型（Flat Memory Model）。
我們講 x86 的工作模式的時候，講過 CPU 是通過總線去訪問內(nèi)存的，這就是最經(jīng)典的內(nèi)存使用方式。
在這種模式下，CPU 也會有多個，在總線的一側(cè)。所有的內(nèi)存條組成一大片內(nèi)存，在總線的另一側(cè)，所有的 CPU 訪問內(nèi)存都要過總線，而且距離都是一樣的，這種模式稱為SMP（Symmetric multiprocessing），即對稱多處理器。當然，它也有一個顯著的缺點，就是總線會成為瓶頸，因為數(shù)據(jù)都要走它。
為了提高性能和可擴展性，后來有了一種更高級的模式，NUMA（Non-uniform memory access），非一致內(nèi)存訪問。在這種模式下，內(nèi)存不是一整塊。每個 CPU 都有自己的本地內(nèi)存，CPU 訪問本地內(nèi)存不用過總線，因而速度要快很多，每個 CPU 和內(nèi)存在一起，成為一個 NUMA 節(jié)點。但是，在本地內(nèi)存不足的情況下，每個 CPU 都可以去另外的 NUMA 節(jié)點申請內(nèi)存，這個時候訪問延時就會比較長。
這樣，內(nèi)存被分成了多個節(jié)點，每個節(jié)點再被分成一個一個的頁面。由于頁需要全局唯一定位，頁還是需要有全局唯一的頁號的。但是由于物理內(nèi)存不是連起來的了，頁號也就不再連續(xù)了。于是內(nèi)存模型就變成了非連續(xù)內(nèi)存模型，管理起來就復雜一些。
這里需要指出的是，NUMA 往往是非連續(xù)內(nèi)存模型。而非連續(xù)內(nèi)存模型不一定就是 NUMA，有時候一大片內(nèi)存的情況下，也會有物理內(nèi)存地址不連續(xù)的情況。
后來內(nèi)存技術(shù)牛了，可以支持熱插拔了。這個時候，不連續(xù)成為常態(tài)，于是就有了稀疏的內(nèi)存模型。
更多l(xiāng)inux內(nèi)核視頻教程文檔資料免費領(lǐng)取后臺私信【內(nèi)核】自行獲取。
內(nèi)核學習網(wǎng)站：
Linux內(nèi)核源碼/內(nèi)存調(diào)優(yōu)/文件系統(tǒng)/進程管理/設(shè)備驅(qū)動/網(wǎng)絡(luò)協(xié)議棧-學習視頻教程-騰訊課堂
NUMA節(jié)點
我們主要解析當前的主流場景，NUMA 方式。我們首先要能夠表示 NUMA 節(jié)點的概念，于是有了下面這個結(jié)構(gòu) typedef struct pglist_data pg_data_t，它里面有以下的成員變量：
- 每一個節(jié)點都有自己的 ID：node_id；
- node_mem_map 就是這個節(jié)點的 struct page 數(shù)組，用于描述這個節(jié)點里面的所有的頁；
- node_start_pfn 是這個節(jié)點的起始頁號；
- node_spanned_pages 是這個節(jié)點中包含不連續(xù)的物理內(nèi)存地址的頁面數(shù)；
- node_present_pages 是真正可用的物理頁面的數(shù)目。
例如，64M 物理內(nèi)存隔著一個 4M 的空洞，然后是另外的 64M 物理內(nèi)存。這樣換算成頁面數(shù)目就是，16K 個頁面隔著 1K 打開頁面，然后是另外 16K 個頁面。這種情況下，node_spanned_pages 就是 33K 個頁面，node_present_pages 就是 32K 個頁面。
typedef struct pglist_data {
struct zone node_zones[MAX_NR_ZONES];
struct zonelist node_zonelists[MAX_ZONELISTS];
int nr_zones;
struct page *node_mem_map;
unsigned long node_start_pfn;
unsigned long node_present_pages; /* total number of physical pages */
unsigned long node_spanned_pages; /* total size of physical page range, including holes */
int node_id;
......
} pg_data_t;
每一個節(jié)點分成一個個區(qū)域 zone，放在數(shù)組 node_zones 里面。這個數(shù)組的大小為 MAX_NR_ZONES。我們來看區(qū)域的定義。
enum zone_type {
#ifdef CONFIG_ZONE_DMA
ZONE_DMA,
#endif
#ifdef CONFIG_ZONE_DMA32
ZONE_DMA32,
#endif
ZONE_NORMAL,
#ifdef CONFIG_HIGHMEM
ZONE_HIGHMEM,
#endif
ZONE_MOVABLE,
__MAX_NR_ZONES
};
ZONE_DMA 是指可用于作 DMA（Direct Memory Access，直接內(nèi)存存取）的內(nèi)存。DMA 是這樣一種機制：要把外設(shè)的數(shù)據(jù)讀入內(nèi)存或把內(nèi)存的數(shù)據(jù)傳送到外設(shè)，原來都要通過 CPU 控制完成，但是這會占用空間 CPU，影響 CPU 處理其他事情，所以有了 DMA 模式。CPU 只需向 DMA 控制器下達指令，讓 DMA 控制器來處理數(shù)據(jù)的傳送，數(shù)據(jù)傳送完畢后再把信息反饋給 CPU，這樣就可以解放 CPU。
對于 64 位系統(tǒng)，有兩個 DMA 區(qū)域。除了上面說的 ZONE_DMA，還有 ZONE_DMA32。在這里你大概能理解 DMA 的原理就可以，不必糾結(jié)，我們后面會講 DMA 的機制。
ZONE_NORMAL 是直接映射區(qū)，就是上一節(jié)講的，從物理內(nèi)存到虛擬內(nèi)存的內(nèi)核區(qū)域，通過加上一個常量直接映射。
ZONE_HIGHMEM 是高端內(nèi)存區(qū)，就是上一節(jié)講的，對于 32 位系統(tǒng)來說超過 896M 的地方，對于 64 未必要有的一段區(qū)域。
ZONE_MOVABLE 是可移動區(qū)域，通過將物理內(nèi)存劃分為可移動分配區(qū)域和不可移動分配區(qū)域來避免內(nèi)存碎片。
這里你需要注意一下，我們剛才對于區(qū)域的劃分，都是針對物理內(nèi)存的。
nr_zones 表示當前節(jié)點的區(qū)域的數(shù)量。node_zonelists 是備用節(jié)點和它的內(nèi)存區(qū)域的情況。前面講 NUMA 的時候，我們講了 CPU 訪問內(nèi)存，本節(jié)點速度最快，但是如果本節(jié)點內(nèi)存不夠怎么辦，還是需要去其他節(jié)點進行分配。畢竟，就算在備用節(jié)點里面選擇，慢了點也比沒有強。
既然整個內(nèi)存被分成了多個節(jié)點，那 pglist_data 應(yīng)該放在一個數(shù)組里面。每個節(jié)點一項，就像下面代碼里面一樣：
struct pglist_data *node_data[MAX_NUMNODES] __read_mostly;
區(qū)域
到這里，我們把內(nèi)存分成了節(jié)點，把節(jié)點分成了區(qū)域。接下來我們來看，一個區(qū)域里面是如何組織的。
表示區(qū)域的數(shù)據(jù)結(jié)構(gòu) zone 的定義如下：
struct zone {
......
struct pglist_data *zone_pgdat;
struct per_cpu_pageset __percpu *pageset;
unsigned long zone_start_pfn;
/*
* spanned_pages is the total pages spanned by the zone, including
* holes, which is calculated as:
* spanned_pages = zone_end_pfn - zone_start_pfn;
*
* present_pages is physical pages existing within the zone, which
* is calculated as:
* present_pages = spanned_pages - absent_pages(pages in holes);
*
* managed_pages is present pages managed by the buddy system, which
* is calculated as (reserved_pages includes pages allocated by the
* bootmem allocator):
* managed_pages = present_pages - reserved_pages;
*
*/
unsigned long managed_pages;
unsigned long spanned_pages;
unsigned long present_pages;
const char *name;
......
/* free areas of different sizes */
struct free_area free_area[MAX_ORDER];
/* zone flags, see below */
unsigned long flags;
/* Primarily protects free_area */
spinlock_t lock;
......
} ____cacheline_internodealigned_in_
在一個 zone 里面，zone_start_pfn 表示屬于這個 zone 的第一個頁。
如果我們仔細看代碼的注釋，可以看到，spanned_pages = zone_end_pfn - zone_start_pfn，也即 spanned_pages 指的是不管中間有沒有物理內(nèi)存空洞，反正就是最后的頁號減去起始的頁號。
present_pages = spanned_pages - absent_pages(pages in holes)，也即 present_pages 是這個 zone 在物理內(nèi)存中真實存在的所有 page 數(shù)目。
managed_pages = present_pages - reserved_pages，也即 managed_pages 是這個 zone 被伙伴系統(tǒng)管理的所有的 page 數(shù)目，伙伴系統(tǒng)的工作機制我們后面會講。
per_cpu_pageset 用于區(qū)分冷熱頁。什么叫冷熱頁呢？咱們講 x86 體系結(jié)構(gòu)的時候講過，為了讓 CPU 快速訪問段描述符，在 CPU 里面有段描述符緩存。CPU 訪問這個緩存的速度比內(nèi)存快得多。同樣對于頁面來講，也是這樣的。如果一個頁被加載到 CPU 高速緩存里面，這就是一個熱頁（Hot Page），CPU 讀起來速度會快很多，如果沒有就是冷頁（Cold Page）。由于每個 CPU 都有自己的高速緩存，因而 per_cpu_pageset 也是每個 CPU 一個。
頁
了解了區(qū)域 zone，接下來我們就到了組成物理內(nèi)存的基本單位，頁的數(shù)據(jù)結(jié)構(gòu) struct page。這是一個特別復雜的結(jié)構(gòu)，里面有很多的 union，union 結(jié)構(gòu)是在 C 語言中被用于同一塊內(nèi)存根據(jù)情況保存不同類型數(shù)據(jù)的一種方式。這里之所以用了 union，是因為一個物理頁面使用模式有多種。
**第一種模式，要用就用一整頁。**這一整頁的內(nèi)存，或者直接和虛擬地址空間建立映射關(guān)系，我們把這種稱為匿名頁（Anonymous Page）。或者用于關(guān)聯(lián)一個文件，然后再和虛擬地址空間建立映射關(guān)系，這樣的文件，我們稱為內(nèi)存映射文件（Memory-mApped File）。
如果某一頁是這種使用模式，則會使用 union 中的以下變量：
- struct address_space *mapping 就是用于內(nèi)存映射，如果是匿名頁，最低位為 1；如果是映射文件，最低位為 0；
- pgoff_t index 是在映射區(qū)的偏移量；
- atomic_t _mapcount，每個進程都有自己的頁表，這里指有多少個頁表項指向了這個頁；
- struct list_head lru 表示這一頁應(yīng)該在一個鏈表上，例如這個頁面被換出，就在換出頁的鏈表中；
- compound 相關(guān)的變量用于復合頁（Compound Page），就是將物理上連續(xù)的兩個或多個頁看成一個獨立的大頁。
**第二種模式，僅需分配小塊內(nèi)存。**有時候，我們不需要一下子分配這么多的內(nèi)存，例如分配一個 task_struct 結(jié)構(gòu)，只需要分配小塊的內(nèi)存，去存儲這個進程描述結(jié)構(gòu)的對象。為了滿足對這種小內(nèi)存塊的需要，Linux 系統(tǒng)采用了一種被稱為slab allocator的技術(shù)，用于分配稱為 slab 的一小塊內(nèi)存。它的基本原理是從內(nèi)存管理模塊申請一整塊頁，然后劃分成多個小塊的存儲池，用復雜的隊列來維護這些小塊的狀態(tài)（狀態(tài)包括：被分配了 / 被放回池子 / 應(yīng)該被回收）。
也正是因為 slab allocator 對于隊列的維護過于復雜，后來就有了一種不使用隊列的分配器 slub allocator，后面我們會解析這個分配器。但是你會發(fā)現(xiàn)，它里面還是用了很多 slab 的字眼，因為它保留了 slab 的用戶接口，可以看成 slab allocator 的另一種實現(xiàn)。
還有一種小塊內(nèi)存的分配器稱為slob，非常簡單，主要使用在小型的嵌入式系統(tǒng)。
如果某一頁是用于分割成一小塊一小塊的內(nèi)存進行分配的使用模式，則會使用 union 中的以下變量：
- s_mem 是已經(jīng)分配了正在使用的 slab 的第一個對象；
- freelist 是池子中的空閑對象；
- rcu_head 是需要釋放的列表。
struct page {
unsigned long flags;
union {
struct address_space *mapping;
void *s_mem; /* slab first object */
atomic_t compound_mapcount; /* first tail page */
};
union {
pgoff_t index; /* Our offset within mapping. */
void *freelist; /* sl[aou]b first free object */
};
union {
unsigned counters;
struct {
union {
atomic_t _mapcount;
unsigned int active; /* SLAB */
struct { /* SLUB */
unsigned inuse:16;
unsigned objects:15;
unsigned frozen:1;
};
int units; /* SLOB */
};
atomic_t _refcount;
};
};
union {
struct list_head lru; /* Pageout list */
struct dev_pagemap *pgmap;
struct { /* slub per cpu partial pages */
struct page *next; /* Next partial slab */
int pages; /* Nr of partial slabs left */
int pobjects; /* Approximate # of objects */
};
struct rcu_head rcu_head;
struct {
unsigned long compound_head; /* If bit zero is set */
unsigned int compound_dtor;
unsigned int compound_order;
};
};
union {
unsigned long private;
struct kmem_cache *slab_cache; /* SL[AU]B: Pointer to slab */
};
......
}
頁的分配
好了，前面我們講了物理內(nèi)存的組織，從節(jié)點到區(qū)域到頁到小塊。接下來，我們來看物理內(nèi)存的分配。
對于要分配比較大的內(nèi)存，例如到分配頁級別的，可以使用伙伴系統(tǒng)（Buddy System）。
Linux 中的內(nèi)存管理的“頁”大小為 4KB。把所有的空閑頁分組為 11 個頁塊鏈表，每個塊鏈表分別包含很多個大小的頁塊，有 1、2、4、8、16、32、64、128、256、512 和 1024 個連續(xù)頁的頁塊。最大可以申請 1024 個連續(xù)頁，對應(yīng) 4MB 大小的連續(xù)內(nèi)存。每個頁塊的第一個頁的物理地址是該頁塊大小的整數(shù)倍。
第 i 個頁塊鏈表中，頁塊中頁的數(shù)目為 2^i。
在 struct zone 里面有以下的定義：
struct free_area free_area[MAX_ORDER];
MAX_ORDER 就是指數(shù)。
#define MAX_ORDER 11
當向內(nèi)核請求分配 (2^(i-1)，2^i] 數(shù)目的頁塊時，按照 2^i 頁塊請求處理。如果對應(yīng)的頁塊鏈表中沒有空閑頁塊，那我們就在更大的頁塊鏈表中去找。當分配的頁塊中有多余的頁時，伙伴系統(tǒng)會根據(jù)多余的頁塊大小插入到對應(yīng)的空閑頁塊鏈表中。
例如，要請求一個 128 個頁的頁塊時，先檢查 128 個頁的頁塊鏈表是否有空閑塊。如果沒有，則查 256 個頁的頁塊鏈表；如果有空閑塊的話，則將 256 個頁的頁塊分成兩份，一份使用，一份插入 128 個頁的頁塊鏈表中。如果還是沒有，就查 512 個頁的頁塊鏈表；如果有的話，就分裂為 128、128、256 三個頁塊，一個 128 的使用，剩余兩個插入對應(yīng)頁塊鏈表。
上面這個過程，我們可以在分配頁的函數(shù) alloc_pages 中看到。
static inline struct page *
alloc_pages(gfp_t gfp_mask, unsigned int order)
{
return alloc_pages_current(gfp_mask, order);
}
/**
* alloc_pages_current - Allocate pages.
*
* @gfp:
* %GFP_USER user allocation,
* %GFP_KERNEL kernel allocation,
* %GFP_HIGHMEM highmem allocation,
* %GFP_FS don't call back into a file system.
* %GFP_ATOMIC don't sleep.
* @order: Power of two of allocation size in pages. 0 is a single page.
*
* Allocate a page from the kernel page pool. When not in
* interrupt context and apply the current process NUMA policy.
* Returns NULL when no page can be allocated.
*/
struct page *alloc_pages_current(gfp_t gfp, unsigned order)
{
struct mempolicy *pol = &default_policy;
struct page *page;
......
page = __alloc_pages_nodemask(gfp, order,
policy_node(gfp, pol, numa_node_id()),
policy_nodemask(gfp, pol));
......
return page;
}
alloc_pages 會調(diào)用 alloc_pages_current，這里面的注釋比較容易看懂了，gfp 表示希望在哪個區(qū)域中分配這個內(nèi)存：
- GFP_USER 用于分配一個頁映射到用戶進程的虛擬地址空間，并且希望直接被內(nèi)核或者硬件訪問，主要用于一個用戶進程希望通過內(nèi)存映射的方式，訪問某些硬件的緩存，例如顯卡緩存；
- GFP_KERNEL 用于內(nèi)核中分配頁，主要分配 ZONE_NORMAL 區(qū)域，也即直接映射區(qū)；
- GFP_HIGHMEM，顧名思義就是主要分配高端區(qū)域的內(nèi)存。
另一個參數(shù) order，就是表示分配 2 的 order 次方個頁。
接下來調(diào)用 __alloc_pages_nodemask。這是伙伴系統(tǒng)的核心方法。它會調(diào)用 get_page_from_freelist。這里面的邏輯也很容易理解，就是在一個循環(huán)中先看當前節(jié)點的 zone。如果找不到空閑頁，則再看備用節(jié)點的 zone。
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
......
for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask) {
struct page *page;
......
page = rmqueue(ac->preferred_zoneref->zone, zone, order,
gfp_mask, alloc_flags, ac->migratetype);
......
}
每一個 zone，都有伙伴系統(tǒng)維護的各種大小的隊列，就像上面伙伴系統(tǒng)原理里講的那樣。這里調(diào)用 rmqueue 就很好理解了，就是找到合適大小的那個隊列，把頁面取下來。
接下來的調(diào)用鏈是 rmqueue->__rmqueue->__rmqueue_smallest。在這里，我們能清楚看到伙伴系統(tǒng)的邏輯。
static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
int migratetype)
{
unsigned int current_order;
struct free_area *area;
struct page *page;
/* Find a page of the appropriate size in the preferred list */
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = &(zone->free_area[current_order]);
page = list_first_entry_or_null(&area->free_list[migratetype],
struct page, lru);
if (!page)
continue;
list_del(&page->lru);
rmv_page_order(page);
area->nr_free--;
expand(zone, page, order, current_order, area, migratetype);
set_pcppage_migratetype(page, migratetype);
return page;
}
return NULL;
}
從當前的 order，也即指數(shù)開始，在伙伴系統(tǒng)的 free_area 找 2^order 大小的頁塊。如果鏈表的第一個不為空，就找到了；如果為空，就到更大的 order 的頁塊鏈表里面去找。找到以后，除了將頁塊從鏈表中取下來，我們還要把多余的的部分放到其他頁塊鏈表里面。expand 就是干這個事情的。area–就是伙伴系統(tǒng)那個表里面的前一項，前一項里面的頁塊大小是當前項的頁塊大小除以 2，size 右移一位也就是除以 2，list_add 就是加到鏈表上，nr_free++ 就是計數(shù)加 1。
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
unsigned long size = 1 << high;
while (high > low) {
area--;
high--;
size >>= 1;
......
list_add(&page[size].lru, &area->free_list[migratetype]);
area->nr_free++;
set_page_order(&page[size], high);
}
}
