Linux 記憶體基礎

地址類型

linux內核中有許多種不同的地址類型

用戶虛擬地址用戶空間看到的常規地址，通過頁表可以將虛擬地址和物理地址映射起來
物理地址用在cpu和內存之間的地址叫做物理地址
總線地址外圍總線和內存之間的地址叫做總線地址。通常他們和物理地址相同
內核邏輯地址內核的常規地址空間，必定有對應的物理內存與之映射。kmalloc返回的就是內核邏輯地址
內核虛擬地址內核虛擬地址和內核邏輯地址的相同之處在於，他們都將內核空間的地址映射到物理內存上。但是內核虛擬地址不一定是線性的和一對一的。vmalloc返回的是虛擬地址。

虛擬內存

虛擬內存是用來描述一種不直接映射計算機物理內存的方法。分頁是在虛擬內存與物理內存轉換時用到的。請參閱intel手冊瞭解更多分頁系統的知識。

低於896MB的每頁內存都被直接映射到內核空間。高於896的內存，又稱高端內存，不會一直映射到內存空間，而是使用kmap和kmap_atomic來臨時映射。剩餘的126MB內存的一部分用於映射高端內存。

內核內存從PAGE_OFFSET開始，在x86架構中它的值是0xc0000000(3G)，高於PAGE_OFFSET的虛擬內存用於內核空間，低於的用於用戶空間。

x86系統內存子系統初始化

首先設置頁表(可能有多級)
完成內核內存映射(內核中的物理內存和邏輯地址只有一個固定的OFFSET，PAGE_OFFSET)

用戶空間的內存管理

struct mm_struct 進程內存空間的最高級別管理結構
struct vm_area_struct 內存區域，組成進程內存
pgd_t *pgd 進程頁表指針

閱讀ULK3學習更多內存管理的細節

物理地址和頁

物理地址被分成離散的單元，成為頁。目前大多數系統的頁面大小都為4k。實際使用的時候應該使用指定體系架構下的頁面大小PAGE_SIZE。PAGE_SHIFT可以將地址轉換為頁幀。

高端和低端內存

系統中邏輯地址和虛擬地址不一致的情況產生了高端內存和低端內存的說法。

通常linux x86內核將4GB的虛擬地址分割為用戶空間和內核空間；在二者的上下文中使用相同的映射。一個典型的分配是將低地址3GB分給用戶空間，將剩下的高地址1GB分給內核空間。這樣由於內核只能直接操作已經映射了物理內存的虛擬地址，所以內核在大內存系統中就不能直接訪問所有的物理內存。這樣就產生了高端內存和低端內存的說法。

高端內存

高端內存是沒有直接映射到物理內存的內核邏輯地址

HighMemory

應對高端內存

高端物理內存在需要使用時會被臨時映射到內核虛擬內存上
內核經常訪問的數據被放在低端內存上
內核偶爾訪問的數據最好放在高端內存上
不同內存區域的內存分配和換頁應該有一個平衡

臨時映射

kmap和kunmap，產生一個永久的內存映射，但他們有一個全局鎖，不適合SMP系統
kmap_atomic和kunmap_atomic，常用於SMP系統，產生的映射地址是每個CPU私有的

在訪問特定的高端內存之前，內核必須建立明確的虛擬映射，使該頁可以在內核地址空間被訪問。

總的來說高端內存就是沒有邏輯地址的內存，反之就是低端內存。

內存映射和結構

由於高端內存中無法使用邏輯地址，所以內核中處理內存的函數趨向於使用指向page結構的指針。該結構保存了內核需要知道的所有物理內存的信息。系統中的每個物理頁都和一個page結構對應。

page結構和虛擬地址之間轉換的函數和宏：

struct page *virt_to_page(void *kaddr);
struct page *pfn_to_page(int pfn);
void *page_addr(struct page *page);

分頁

In a virtual memory system all of these addresses are virtual addresses and not physical addresses. These virtual addresses are converted into physical addresses by the processor based on information held in a set of tables maintained by the operating system.在虛擬內存系統中，所有的地址都是虛擬地址而不是物理地址。這些虛擬地址可以通過操作系統維護的一系列的錶轉換為物理地址。

To make this translation easier, virtual and physical memory are divided into handy sized chunks called pages. These pages are all the same size, they need not be but if they were not, the system would be very hard to administer. Linux on Alpha AXP systems uses 8 Kbyte pages and on Intel x86 systems it uses 4 Kbyte pages. Each of these pages is given a unique number; the page frame number (PFN).為了使這個轉換更加簡單，虛擬地址和物理地址都被分成叫做內存頁面小的內存塊。所有的頁面都是同樣大小。每頁內存都有一個唯一的編號，這種編號叫做頁幀號。

In this paged model, a virtual address is composed of two parts; an offset and a virtual page frame number. If the page size is 4 Kbytes, bits 11:0 of the virtual address contain the offset and bits 12 and above are the virtual page frame number. Each time the processor encounters a virtual address it must extract the offset and the virtual page frame number. The processor must translate the virtual page frame number into a physical one and then access the location at the correct offset into that physical page. To do this the processor uses page tables.在這種分頁模式下，虛擬地址由兩部分組成；頁幀內的偏移和虛擬頁幀號。如果頁面大小是4KB，11:0這些位就是頁幀內偏移，12位以上的叫做頁幀號。每當處理器遇到虛擬內存地址，它就會把地址中的頁內偏移和頁幀號解出來。處理器通過頁表把虛擬幀號轉換成物理幀號，然後在加上頁內偏移就可以找到對應的物理地址了。

頁表

現代系統中，處理器需要使用某種機制將虛擬地址轉換成物理地址。這種機制被成為頁表；它基本上是一個多層樹形結構，結構化的數組中包含了虛擬地址到物理地址的映射和相關的標誌位。

demand paging

Linux uses demand paging to load executable images into a processes virtual memory. Whenever a command is executed, the file containing it is opened and its contents are mapped into the processes virtual memory. This is done by modifying the data structures describing this processes memory map and is known as memory mapping. However, only the first part of the image is actually brought into physical memory. The rest of the image is left on disk. As the image executes, it generates page faults and Linux uses the processes memory map in order to determine which parts of the image to bring into memory for execution.Linux使用按需分頁來將可執行鏡像載入到進程的虛擬內存空間。每當命令執行時，命令的文件被打開，內容被映射到進程的虛擬內存上。這裡是通過修改進程的內存映射相關結構體來實現的，這個過程也叫做內存映射。不過，只有鏡像的開頭部分被真正的放進了物理內存。餘下部分還在磁盤上。鏡像執行的時候，它將持續的產生頁面異常，linux通過進程的內存映射表來確定鏡像的哪個部分需要被載入物理內存執行。

Shared virtual memory

Virtual memory makes it easy for several processes to share memory. All memory access are made via page tables and each process has its own separate page table. For two processes sharing a physical page of memory, its physical page frame number must appear in a page table entry in both of their page tables. 虛擬內存使得多個進程共享內存更加簡單。所有的內存訪問都要通過頁表來實現。對於共享一個物理頁的兩個進程來說，這個物理頁面必須同時在兩個進程的頁表中都有相應的頁表項。

虛擬內存區

VMA是用於管理進程地址空間中不同區域的內核數據結構。

進程的內存映射至少包含下面這些區域：

程序可執行代碼區域（text）
數據區（bss，stack，data）
與每個活動的內存映射區對應的區域

可以cat /proc/<pid/maps>來查看具體進程的內存映射。

當用戶空間進程調用mmap時，系統會創建一個新的VMA來相應它。

注意vm_area_struct這個重要的數據結構（定義在中）。

內存映射處理

系統中每個進程（除了內核空間的輔助線程）都有一個struct mm_struct結構（定義在中），其中包含了大量的內存管理信息。多個進程可以共享內存管理結構，linux就是使用這種方法實現線程的。

mmap設備操作

mmap可以將用戶空間的內存和設備內存映射起來，這樣在訪問分配地址範圍內的內存時就相當於訪問設備內存了。

並非所有的設備都能進行mmap抽象：

像串口這樣面向流的設備就不能
mmap的另一個限制：必須以PAGE_SIZE為單位進行映射，因為內核只能在頁表一級上對虛擬地址進行管理。

為了執行mmap，驅動程序只需要為該地址範圍建立合適的頁表，並將vma->vm_ops替換為一系列的新操作就可以了。有兩種建立頁表的方法：使用remap_pfn_range函數一次全部建立；通過VMA的fault方法一次建立一個新頁表。

內存映射的方法

重新映射特定的I/O區域
重新映射ram
重新映射內核虛擬地址
執行直接I/O訪問

分配內存

這裡我們來看看內核為設備驅動程序提供的內存管理接口。

Kmalloc函數

kmalloc內存分配工具和malloc的使用方法很接近。它的原型是：

\#include <linux/slab.h> void *kmalloc(size_t size, int flags);

flags參數以多種方式控制kmalloc的行為

最常用的標誌是GFP_KERNEL(GFP的來源是因為kmalloc最終會調用get_free_pages函數)，這個標誌允許kmalloc在頁面不足的情況下休眠。

如果在進程上下文之外使用kmalloc，比如中斷處理例程中就需要使用GFP_ATOMIC標誌，不會休眠

其他標誌都定義在文件中，請閱讀該文件後使用他們

size參數

內核中使用基於頁面的方式管理內存，因此和用戶空間的基於堆的簡單內存管理有很大的差別

由於slab分配器（即kmalloc的底層實現）最大分配的內存單元是128KB，所以如果分配的內存過大，最好不要使用kmalloc方法

高速緩存

內核實現了一些內存池，內核驅動程序通過使用它們可以減少內存分配的次數。

它的api在中，類型為kmem_cache_t。

內存池

內存池其實是某種形式的高速緩衝，它試圖始終保持空閒的狀態，方便那些要求內存分配不能失敗的代碼使用。

它的api在中，類型為mempool_t。

get_free_pages和相關函數

如果驅動使用較大塊的內存，則適合使用面向頁的分配技術。

get_zeroed_page(unsigned int flags); 返回指向新頁面的指針並清零
__get_free_page(unsigned int flags); 返回指針但不清零
__get_free_pages(unsigned int flags, unsigned int order); 分配2^order個連續頁面，不清零

頁分配核心 alloc_pages

alloc_pages用來分配描述用struct page描述的頁面內存，使用這種結構描述的內核內存在某些地方使用起來非常方便。

struct page *alloc_pages_node(int nid, unsigned int flags, unsigned int order);

vmalloc以及相關函數

vmalloc分配虛擬地址空間的連續內存。儘管可能這段內存在物理上可能不是連續的。

通過vmalloc獲得的內存使用起來效率不高，如果可能，應該直接和單個的頁面打交道，也就是使用前面的函數來處理而不是使用vmalloc。vmalloc分配的虛擬地址上可能沒有物理內存對應。

kmalloc和__get_free_pages返回的虛擬地址內存範圍與物理內存的範圍是一一對應的。但vmalloc和ioremap使用的地址範圍則是完全虛擬的，每次分配都需要適當的設置頁表來建立內存區域。

ioremap也和vmalloc一樣建立新頁表，但它不會分配內存。它更多用於映射設備緩衝到虛擬內核空間。值得注意的是不能把ioremap返回的指針直接當作內存使用，應該使用I/O函數來訪問。

vmalloc的一個小缺點是它不能在原子上下文中使用。

相關的函數定義在中。

per-CPU變量

當建立一個per-CPU變量時，系統的每個處理器都會擁有該變量的副本。對於per-CPU變量的訪問幾乎不需要鎖定，因為每個處理器有自己的副本。

注意當處理器在修改某個per-CPU變量的臨界區中間時，它可能被搶佔，需要避免這種情況發生。所以我們應該顯式地調用get_cpu_var訪問某給定變量的當前處理器副本，結束後調用put_cpu_var。

使用方法：

DEFINE_PER_CPU(type, name);
動態分配： void alloc_percpu(type); void __alloc_percpu(size_t size, size_t align);
per_cpu_ptr(void *per_cpu_var, int cpu_id);返回給定cpu_id的per_cpu_var指針

DMA

DMA(Direct Memory Access)是一種高級的硬件機制，它允許外設直接和主內存之間進行I/O傳輸而不用CPU的幹預。

DMA數據傳輸概覽

有兩種方式可以引發DMA數據傳輸：軟件對數據的請求；硬件異步地把數據傳給系統。

第一種情況：
- 進程調用read，驅動程序分配一個DMA緩衝，然後讓硬件把數據傳輸到這裡，此時進程睡眠
- 硬件把數據寫入到DMA緩衝，寫完之後產生一箇中斷
- 中斷處理程序獲取輸入的數據，應答中斷並喚醒進程，進程即可讀取DMA緩衝裡面的數據
第二種情況：
- 硬件產生中斷，宣告有數據到來
- 中斷處理程序分配緩衝區，告訴硬件向哪裡傳輸數據
- 外設將數據寫入緩衝，完成後產生另一箇中斷
- 處理程序分發新數據，喚醒相關進程，然後執行清理工作

可以看出，高效的DMA傳輸依賴於中斷報告。

分配DMA緩衝區

DMA緩衝區的主要問題是：當大於一頁時，它必須佔用連續的物理頁，這是因為多數外設總線都使用物理地址。

驅動作者必須謹慎的為DMA分配正確的內存類型，並不是所有的內存區間都適合DMA操作。外設不能使用高端內存。
對於有限制的設備，應使用GFP_DMA標誌調用內存分配函數。

DIY分配

使用get_free_pages分配大於128KB內存的時候很容易失敗返回-ENOMEM。此時的辦法是在引導時分配內存或者為緩衝區保留頂部物理內存。

如果要為DMA分配一大塊內存，最好考慮分散聚集I/O。

總線地址

硬件和程序代碼使用不同的地址，所以需要有一個地址轉換。

通用DMA層

由於多種系統對緩存和DMA的處理不同，內核提供了一個通用DMA層，建議在用到DMA時使用該層。struct device隱藏了描述設備的總線細節，在使用通用DMA層時需要使用到該結構的指針。

接下來的DMA函數都需要包含文件

確定設備的DMA能力

int dma_set_mask(struct device *dev, u64 mask); 可以用來確定設備是否支持DMA。

內存分配實現

下面將介紹linux內核中針對不同的應用場景實現的不同內存分配算法。

頁框分配，zoned buddy算法
內存區分配，slab 分配器
非連續內存區管理，虛擬內存映射

在支持NUMA的linux內核當中，系統的物理內存被分為多個節點，在單獨節點內，任一給定cpu訪問頁面所需要的時間都是相同的。每個節點的物理內存又分成多個內存區（zone）。x86下內存區有ZONE_DMA、ZONE_NORMAL和ZONE_HIGHMEM。x86_32系統上，ZONE_HIGHMEM中的內存沒有直接映射到內核線性地址上，在每次使用之前都需要先設置頁表映射內存。每個zone下面的內存都是以頁框為單位來管理的。

每個zone的內存頁面是通過buddy算法來管理的。

zoned buddy

頁框分配算法需要解決external fragmentation的內存管理問題。linux內核使用buddy算法來解決這個問題。把所有的空閒頁分組為2^(order-1)大小的塊鏈表。order的最大值為11，所以一共有11個這樣的鏈表。鏈表的元素最小的為4k(1一個頁面大小)，最大的為4M(2^10個頁面大小)。請求內存時，內核首先從最接近請求大小的鏈表中查詢，如果有這樣的空閒單元，則直接使用。如果沒有則一次遞增到更大塊的內存鏈表中查詢，如果有則將內存分出最接近請求大小的塊，在把餘下的內存拆分添加到較小的內存鏈表中。

核心函數

核心接口

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
struct page * alloc_pages(gfp_t gfp_mask, unsigned int order);
void __free_pages(struct page *page, unsigned int order);

核心實現

struct page * __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist, nodemask_t *nodemask);

Slab Allocator(對象緩存分配)

The fundamental idea behind slab allocation technique is based on the observation that some kernel data objects are frequently created and destroyed after they are not needed anymore. This implies that for each allocation of memory for these data objects, some time is spent to find the best fit for that data object. Moreover, deallocation of the memory after destruction of the object contributes to fragmentation of the memory, which burdens the kernel some more to rearrange the memory.Slab 算法的發現是基於內核中內存使用的一些特點：一些需要頻繁使用的同樣大小數據經常在使用後不久又再次被用到；找到合適大小的內存所消耗的時間遠遠大於釋放內存所需要的時間。所以Slab算法的發明人認為內存對象在使用之後不是立即釋放給系統而是將它們用鏈表之類的數據結構管理起來以備將來使用，頻繁分配和釋放的內存對象應該用緩存管理起來。Linux的slab分配器就是基於這樣的想法實現的，這個算法在空間和時間上都有很高的效率。

Slab implementation

下面是Slab分配器中的主要數據結構之間的關係圖。最上層是cache_chain，它是slab緩存的一個鏈表。這個鏈表用來查找需要分配內存大小的最佳匹配。鏈表中的元素是用來管理給定大小內存的一個緩存池指針kmem_cache。

Slab分配器的主要結構

每個緩存對象包含了slab對象的鏈表。一個slab對象是一塊連續內存（頁面）。其中有三個slab對象鏈表：

slabs_full,完全分配好的slab對象鏈表
slabs_partial,部分分配好的slab對象鏈表
slabs_empty,空對象鏈表，slab對象都沒有分配好

其中空對象鏈表是內存回收的主要候選來源。slab鏈表上的對象是一塊連續內存，這塊內存被分成內存數據對象。這些數據對象是slab緩存上分配和釋放的最小單位。

由於數據對象是從slab上分配的，所以單個的slab可以從一個slab鏈表移動到另一個slab鏈表。比如當slabs_partial上的一個slab的內存對象全部被分配了之後，這個slab就從slabs_partial上移動到slabs_full。當slabs_full上的一個slab上的部分內存對象被釋放之後，這個slab就從slabs_full鏈表移動到slabs_partial上，當這個slab上的所有內存對象都被釋放之後，它就會再次移動到slabs_empty上。

slab分配器帶來的好處

通過緩存類似對象數據，內核中頻繁的小數據對象的分配不會再消耗過多的時間，同時減少了系統的內存碎片
slab分配支持常用對象數據的初始化，減少了同類對象數據重複的初始化過程
slab分配支持硬件緩存對齊和著色，這樣不同緩存下的對象數據可以使用同樣的硬件緩存行，可以提高系統的性能

接口

struct kmem_cache *;緩存指針，用於分配，釋放緩存中的數據對象
struct kmem_cache *kmem_cache_create( const char *name, size_t size, size_t align, unsigned long flags, void (*ctor)(void*, struct kmem_cache *, unsigned long), void (*dtor)(void*, struct kmem_cache *, unsigned long));創建緩存，ctor和dtor兩個回調函數是提供給用戶初始化和釋放對象數據用的
void kmem_cache_destroy( struct kmem_cache *cachep );銷燬緩存
void* kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags );從緩存中分配對象數據，其中的flags和kmalloc函數使用的標記一樣，用於控制緩存內部從buddy system中分配內存頁面的行為
void kmem_cache_free( struct kmem_cache *cachep, void *objp );回收數據到緩存中的slab對象
void *kmalloc( size_t size, int flags );kmalloc和前面的從緩存中分配對象數據一樣，只不過它不需要提供一個特定的緩存，它通過遍歷系統中可用的緩存來分配對象數據。這樣我們終於知道kmalloc的實現了，它是slab分配器的一個接口
void kfree( const void *objp );

TODOS

segmentation
swaping
demand paging