實體記憶體管理系統設計與實作

作者：王智通

一、前言

我們在前面講述程序設計與調 度的時候涉及到， 當核心要建立一個程序的時候， 會配置設定一個程序描述符struct task_struct結構， 當時調用了一個叫做alloc_page()的函數， 它向核心申請了一個實體記憶體頁， 本節我們将讨論作業系統對實體記憶體的管理和使用。

二、 glibc與kernel的關系

首先我們先回想下， c/c++程式員在寫應用程式的時候， 會用到glibc的malloc()函數來給程序配置設定一塊記憶體， 看看下面的例子：

wzt@exploit:~/code$ cat mem.c

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

char *p;

p = malloc(4);

printf(“%p\n”, p);

}

wzt@exploit:~/code$ gcc -o mem mem.c

wzt@exploit:~/code$ ./mem

0x8ba9008

mem.c用malloc在程序空間的0x8ba9008位址開始處配置設定了4個位元組大小的連續空閑記憶體。 現在有2個問題要大家考慮下：

1、指針p指向的0x8ba9008位址屬于實體記憶體還是虛拟記憶體？

2、程式什麼都沒做， 用malloc配置設定到的記憶體為什麼不從位址0開始？

3、malloc究竟都做了什麼事？

第一個問題似乎很好回答， 它當然是虛拟記憶體了， 但深究一下為什麼os不使用實體記憶體，而使用虛拟記憶體呢？

實體記憶體與虛拟記憶體的關聯：

物 理記憶體指的是計算機實際的記憶體實體容量的大小， 你去買電腦的時候人家會說這台機器記憶體是2g的，指的是實體記憶體。 作業系統當然可以使用實體記憶體來給程序使用， 但是實體記憶體的大小有限， 在許多年前， 計算機的實體記憶體隻有幾十k， 幾m大小，作業系統能建立的程序數量就非常少，一個程序用到的記憶體也是有限， 即使現在普通pc機都有4g左右的實體記憶體大小， 一個遊戲程式就可能用到上百m的記憶體， 如果作業系統這麼使用實體記憶體的話， 能幹的事就非常少了。 這就誕生了虛拟記憶體的概念了， cpu在硬體設計上支援虛拟記憶體， 作業系統根據cpu的硬體支援， 可以讓程序使用實體硬碟來做記憶體， 這樣每個程序能用到的記憶體就很大了。 我們在第2堂課專門講述了實體記憶體到虛拟記憶體的映射過程， 使用虛拟記憶體，還是可以讓每個程序都有4g記憶體的大小， 但是程序之間又是互相獨立，不受幹擾的。

第二個問題， mem這個程序什麼都沒做， 用malloc配置設定的記憶體為什麼不是從0開始呢？ 要回答這個問題， 我們得先了解下一個程序在虛拟記憶體中的布局， 注意不是實體記憶體哦。 我們以linux程序在x86體系架構下的情景做例子：

0×0                                                                       0xffffffff(4g)

——————————————————————————–

| 空洞 | code | data |       heap       |     stack     |  kernel               |

|             |      ——>     |    <——-   |

v                                                v

0×8000000                                       0xc0000000

大家一定很奇怪， 為什麼代碼段是從0×8000000開始的呢？ 其實這是連結器ld搞的鬼， 當時我們是這麼編譯的：

gcc -o mem mem.c, gcc在調用ld做連結的時候， 使用了ld的-ttext參數， ld通過此參數可以把.o檔案用的函數和資料重定位到想要的位址下， ld預設的連結腳本就是0×8000000， 至于ld為什麼不從位址0處開始連結， 筆者也不是很清楚， 如果有哪位同學知道的話，請寫信給我， 先謝過了。 既然知道是ld的ttext參數搞的鬼， 那我們自己連結下程式看看：

wzt@exploit:~/code$ gcc -c mem.c

wzt@exploit:~/code$ ld -ttext 0×0 -o mem mem.o

ld: warning: cannot find entry symbol _start; defaulting to 0000000000000000

mem.o: in function `main’:

mem.c:(.text+0×11): undefined reference to `malloc’

mem.c:(.text+0x2a): undefined reference to `printf’

報錯了，因為mem用到了malloc和printf， 它們是glibc的函數， 我們ld的時候并沒有把它們連結進去。

第三個問題， malloc是如何實作的？

前面在用ld連結的時候， 我們沒有把glibc連結進去， 是以無法使用malloc函數。大家要注意c程式在運作的時候不是從main函數開始運作，它運作的開始位址是glibc的一個初始化函數， 它複雜初始化程序運作時要用到的io函數， 記憶體配置設定函數， 字元串操作函數等等。glibc裡有一個記憶體配置設定器， 它的作用就是給程序提供記憶體配置設定， malloc是它其中的一個功能。 malloc又會調用sys_brk和mmap系統調用向核心申請一塊記憶體，它們的關系如下：

—————       —————–      —————————

|  user space |   –> |     glibc     |  –> |     kernel(buddy & slab)|

程序向glibc申請記憶體， glibc又從核心申請記憶體，接下來我們開始讨論下核心是如何管理記憶體的。

三、實體記憶體大小的檢測

這 裡先要澄清一下2個概念： 我們在講作業系統管理記憶體的時候，包括2個方面， 一個是作業系統核心對記憶體的管理， 一個是glibc庫對記憶體的管理。 在前面小節中， 我們讨論了glibc對記憶體的管理， 知道它最終還是會向核心來申請記憶體， 在這小節中，我們将讨論核心是如何管理與使用記憶體的。

當作業系統在啟動的時候， 勢必要檢測下計算機的實體記憶體大小是多少， 然後它才能對其進行管理。 在bootloader運作的時候， 會先通過bios的15号中斷來擷取實體記憶體的布局， 一個實體記憶體大的布局大緻如下：

physical memory layoout:

(0mb – 1mb)

0×0   0×1000                  0xa0000  0xb8000   0xf0000     0xfffff

————————————————————–

|     | kernel_pg_dir | usable | usable | video  | reserved  |

(1mb – >=64mb)

0×10000                                  0×400000            0×4000000

| kernel_code | kernel_data | kernel_bss | buddy & slab      |

這 是wos作業系統對實體記憶體的使用布局， 我用bochs模拟了64m的實體記憶體， 大家要注意作業系統不能随意的使用實體記憶體的前1m資源，它裡面有一些硬體裝置和bios保留的資料資訊， 如果我們的作業系統把這部分記憶體也占用了的話， 可能造成某些很詭異的bug。對于前1m記憶體的布局， 作業系統可以讓bootloader在啟動的時候通過bios的15号中斷來擷取實體記憶體的布局。

boot.s

…

call get_memory_mmap

enter_protect_mode

get_memory_mmap:

movw $0, %ebx        # ebx填充0。

movw $0×2000, %di    # es:di指向bios提供的一個實體記憶體位址描述符。

check_mm:

movw $0xe820, %ax       # ax必須填充為0xe820。

movl $0x534d4150, %edx  # bios要用到的标志， 必須填充為0x534d4150。

int $0×15        # 調用int 0×15，使用bios的15号中斷， 來獲得一個實體記憶體位址描述符。

jc failed        # 如果調用失敗就跳轉到failed标号處， bootloader就啟動失敗了。

addw $20, %di           # 一個實體記憶體位址描述符大小為20位元組。

movw $0×3000, %si    # 循環調用int 0×15, 直到bx為0。

incw (%si)

cmpw $0, %bx

jne check_mm

ret

執 行完get_memory_mmap後， bootloader會把實體記憶體結構儲存在0×2000開始處的實體記憶體處， 當wos在進入保護模式，開始初始化記憶體管理系統的時候， 要調用print_mm_mmap()函數， 來進一步解析實體記憶體布局， 計算實體記憶體的大小， 哪些實體記憶體可用，哪些記憶體不用。

一個實體記憶體位址描述符的結構如下， 這是bios中規定的結構：

struct mm_ards {

unsigned int base_addr_low;    記憶體塊的位址的低32位

unsigned int base_addr_high;    記憶體塊的位址的高32位

unsigned int length_low;        記憶體塊的長度的低32位

unsigned int length_high;       記憶體塊的長度的高32位

unsigned int type;              記憶體塊的類型

};

void print_mm_mmap(void)

// bootloader把記憶體塊的大小儲存在了0×3000位址處

unsigned int *phy_addr = (unsigned int *)0×3000;

unsigned int i;

mm_mmap_count = *phy_addr;

dbgprint(“mm_mmap_count: %d\n”, mm_mmap_count);

第一個實體記憶體位址描述符儲存在0×2000處

phy_addr = (unsigned int *)0×2000;

for (i = 0; i < mm_mmap_count; i++) {

// 不斷填充mm_ards結構即可。

mm_e820[i].base_addr = *phy_addr;

mm_e820[i].limit = *(phy_addr + 2);

mm_e820[i].type = *(phy_addr + 4);

phy_addr += 5;

在解析完實體記憶體位址描述符後， 我們還得進一步解析它， 在抽象下， wos定義的結構：

struct phy_mmap {

unsigned int base_addr;         記憶體塊的起始位址

unsigned int limit;             記憶體塊的大小

struct phy_mmap mm_e820[max_phy_seg];

最後使用setup_phy_memory函數來獲得記憶體的大小。

void setup_phy_memory(void)

unsigned int code_size, data_size;

unsigned int len;

phy_mem_size = 0;

for (i = 0; i < mm_mmap_count; i++) {    // mm_mmap_count是剛才bootloader提供的記憶體塊數量。

if (mm_e820[i].type == 2)       // 記憶體塊不可用

continue;

len = mm_e820[i].base_addr + mm_e820[i].limit; // 計算記憶體塊長度

if (len > phy_mem_size) {

dbgprint(“0x%x 0x%x 0x%x\n”, mm_e820[i].base_addr,

mm_e820[i].limit, mm_e820[i].type);

phy_mem_size = len;

printk(“physical memory size: 0x%x — %d(mb)\n”,

phy_mem_size, phy_mem_size / 1024 / 1024);

phy_page_num = phy_mem_size / page_size;

printk(“physical page num: %d\n”, phy_page_num);

kernel_pde_num = phy_mem_size / (4*1024*1024);

printk(“kernel pde num: %d\n”, kernel_pde_num);

code_size = (unsigned int)&_etext – (unsigned int)&_text;

data_size = (unsigned int)&_edata – (unsigned int)&_etext;

printk(“kernel code size: %d(kb) data size: %d(kb)\n”,

code_size / 1024, data_size / 1024);

由于前1m記憶體的特殊性， 我将wos的核心代碼放置在1m位址的開始處：

0×10000(1m)                          0×400000(4m)        0×4000000(64m)

大家有注意到從1-4m的實體記憶體被核心代碼和資料給占用了，那麼4m以上的空間就是用來給作業系統和程序配置設定資源的記憶體了。

四、實體記憶體的管理

内 核現在要管理從4m到64m的記憶體， 在記憶體管理系統在初始化完後， 之後所有的記憶體配置設定請求都是從這60m記憶體裡配置設定的，無論是作業系統的， 還是應用程式的。那麼核心要使用什麼樣的算法才能最高效率的滿足記憶體的配置設定和回回收呢？ linux核心是通過2種方法來管理記憶體的：在需要大塊記憶體配置設定的時候， 使用buddy（夥伴）算法來配置設定， 在需要小塊記憶體的時候使用slab/slub高速緩存系統來配置設定。buddy是記憶體管理的最上層結構， 它配置設定若幹個連續的實體記憶體頁， 一個實體頁大小為4kb， 也是說通過buddy系統配置設定得到的記憶體最少是4kb，它管理的是大記憶體塊。slab基于buddy， 将一個實體記憶體頁分成若幹小塊進行管理， 是以slab用于管理小塊。

wos也采用buddy和slab來管理實體記憶體。

buddy夥伴系統算法：

buddy 系統用于配置設定n個連續的實體記憶體頁， 一個實體頁4k大小。 為了快速配置設定， buddy将空閑實體頁劃分成了11個連結清單， 每個連結清單依次儲存1,2,4,8,16,32,64,128,256,512,1024個連續的實體頁。1024個實體頁代表kernel一次最多可以分 配4m位元組的空閑記憶體。它的結構如下：

+—-+

|1024|–> …

|512 |

|256 |

|128 |

| 64 |

+—-+   +———————————–+

| 32 |–>|             page_size*32          | –> …

| 16 |

| 8  |

+—-+   +—————————+   +—————————-+

| 4  |–>|         page_size*4       |–>|         page_size*4        |

| 2  |

+—-+   +———–+   +———–+

| 1  |–>| page_size |–>| page_size |

我們用一個struct mm_buddy數組來管理這些記憶體塊，結構如下:

struct mm_buddy {

int size;        // chunk的大小

int chunk_num;        // chunk的數目

int order;        // 用于計算chunk大小

int free_num;           // 空閑的chunk數目

int total_num;          // 總共的chunk數目

int obj_map[max_buddy_chunk_num]; // chunk索引

void *obj[max_buddy_chunk_num];   // chunk數組

obj_map和obj用來定為buddy上的一個空閑塊，obj儲存了buddy上的所有空閑塊的位址， obj_map是對應空閑塊的标志。

每個記憶體塊由struct mm_buddy_chunk來描述：

struct mm_buddy_chunk {

void *chunk_pos;

int inuse;

struct list_head list;

2、初始化:

為了快速定為struct mm_buddy結構， 我們用mm_buddy_array[11]數組來管理所有struct mm_buddy結構。

初始化buddy系統就是對這個數組進行指派。

void init_buddy_list(void)

void *base;

int i, j;

base = mm_buddy_base;   // 從4m記憶體位址開始

for (i = 0; i < buddy_chunk_num; i++) {

mm_buddy_array[i].size = page_size * (1 << i) * buddy_chunk_num;

mm_buddy_array[i].chunk_num = buddy_size[i];

mm_buddy_array[i].order = i;

mm_buddy_array[i].free_num = buddy_chunk_num;

mm_buddy_array[i].total_num = buddy_chunk_num;

for (j = 0; j < buddy_chunk_num; j++)

mm_buddy_array[i].obj[j] = base + j * (page_size * (1 << i));

for (j = 0; j < max_buddy_chunk_num; j++)

mm_buddy_array[i].obj_map[j] = 0;

base += mm_buddy_array[i].size;

3、配置設定算法：

假 設現在要配置設定一個連續1個實體頁的空閑記憶體， 那麼首先找到數組下标為0的struct mm_buddy結構，然後搜尋這個記憶體塊連結清單， 找到一個還有剩餘記憶體的struct mm_buddy結構， 從中選取一個空閑塊傳回。 如果數組下标為0的struct mm_buddy結構沒有空閑記憶體了， 這時就逐層向上搜尋有剩餘的struct mm_buddy結構。假設現在在下标為2的struct mm_buddy結構中找到了還有空閑記憶體的struct mm_buddy_chunk結構， 它首先将這個塊劃分一個實體頁出來， 然後就要對剩餘的3個實體頁進行分解。依次劃分2個實體頁給數組下标1的struct mm_buddy結構， 劃分最後1個實體頁給下标為0的struct mm_buddy結構。通過算法來達到減少記憶體碎片的目的， 這個就是夥伴系統的核心算法。

alloc_page 函數用來配置設定2^order數目的連續實體頁， 比如order為0表示就配置設定一個實體頁，order為1表示配置設定2個實體頁， order為2，配置設定4個實體頁。 下面是alloc_page函數的核心代碼實作， 完整源代碼在附件中。釋放算法基本就是逆過程， 下文不在講述， 大家可以參考源代碼。

void *alloc_page(int order)

int idx;

void *addr;

if (mm_buddy_array[order].free_num) {

addr = alloc_buddy_chunk(order);

return addr;

for (idx = order + 1; idx < buddy_chunk_num; idx++) {

if (mm_buddy_array[idx].free_num) {

//printk(“alloc page from order: %d\n”, idx);

addr = __alloc_page(order, idx);

if (addr)

return null;

void *__alloc_page(int old_order, int new_order)

int i, next;

void *base, *new_base, *addr;

for (i = 0; i < mm_buddy_array[new_order].total_num; i++) {

if (!mm_buddy_array[new_order].obj_map[i]) {

mm_buddy_array[new_order].obj_map[i] = 1;

next = i;

break;

if (next >= mm_buddy_array[new_order].total_num)

mm_buddy_array[new_order].free_num–;

base = addr = mm_buddy_array[new_order].obj[next];

new_base = base + (1 << new_order) * page_size;

while (new_order > old_order) {

new_order–;

new_base -= (1 << new_order) * page_size;

next = ++mm_buddy_array[new_order].total_num;

mm_buddy_array[new_order].obj_map[next] = 0;

mm_buddy_array[new_order].free_num++;

mm_buddy_array[new_order].obj[next - 1] = new_base;

五、kernel slab高速緩存算法

1、資料結構

kernel buddy夥伴系統是用來配置設定連續實體頁的，因為核心是管理記憶體的基本機關是實體頁。 如果核心代碼想要配置設定小記憶體，比如32位元組，buddy就沒辦法提供了。slab配置設定算法被用來管理小的記憶體塊。它的基本思想是将一個實體頁劃分成多個小 的obj塊， 為了減少記憶體碎片， slab将每個實體頁劃分成了大小為

8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096的小塊。 slab的結構如下：

——-     ——     ——

|cache|–>  |slab| –> |slab|

|cache|

—–

|cache| …

——-    ——     ——

|cache|–> |slab| –> |slab|

|cache|–>|slab|–>|slab|

——-   ——   ——

每個cache由struct slab_cache來描述:

struct slab_cache {

struct slab_obj_cache obj_cache;    /* 用來實作obj的本地高速緩存 */

void *slab_page;            /* 最後一個slab的位址， kfree的時候用到 */

int slab_size;                /* slab的大小 */

int slab_num;                /* cache中， slab的數目 */

int free_num;                           /* cache中剩餘slab的數目 */

int align;                              /* 用于cpu高速緩存 */

int color_num;                /* slab的顔色， 用于cpu l1 cache */

int color_next;                         /* 下一個slab的顔色 */

char name[slab_cache_name_len];        /* slab的名字 */

void (*ctor)(void);            /* cache的初始化函數 */

void (*dtor)(void);            /* cache的結束函數 */

struct list_head list;                  /* 用于連結每個slab */

struct list_head cache_list;            /* 用于連結每個cache */

一個slab的結構如下：

+———————————————–+

| struct slab | bufctl | obj | obj | …| color |

每個slab的最前面是這個slab的管理結構， bufctl是個數組，用于将後面的obj連結起來。obj就是一個要配置設定的對象， color用于cpu cache對齊。它的結構如下：

struct slab {

int obj_num;                /* slab中obj的數目 */

int free_num;                /* 剩餘obj的數目 */

int free_idx;                /* slab中下一個空閑obj的索引 */

void *base;                /* slab中第一個obj的位址 */

struct list_head list;            /* 用于連結每個slab */

2、初始化

先初始化每個cache, cache用slab_cache_array數組來管理。

void init_general_slab_cache(void)

int i;

printk(“init genernal slab cache.\n”);

for (i = 0; i < slab_size_num; i++) {

slab_cache_array[i].slab_size = slab_size[i];

slab_cache_array[i].slab_num = slab_num;

slab_cache_array[i].free_num = 0;

slab_cache_array[i].ctor = null;

slab_cache_array[i].dtor = null;

slab_cache_array[i].color_num =

compute_slab_color_num(slab_size[i], page_size);

slab_cache_array[i].color_next = 0;

slab_cache_array[i].obj_cache.limit = 0;

init_list_head(&slab_cache_array[i].list);

init_slab(&slab_cache_array[i], slab_size[i]);

每個cache預設有2個slab, 他們用連結清單連結起來。

int init_slab(struct slab_cache *slab_cache, int size)

for (i = 0; i < slab_num; i++) {

// alloc_page是buddy系統提供的api， 用來配置設定一頁實體記憶體。

addr = alloc_page(page_order_zero);

if (!addr) {

printk(“alloc page failed.\n”);

return -1;

//printk(“slab alloc page at 0x%x\n”, addr);

// 繼續初始化每個slab

__init_slab(slab_cache, addr, size);

return 0;

void __init_slab(struct slab_cache *slab_cache, void *addr, int size)

struct slab *new_slab = (struct slab *)addr;

// 根據size來計算slab中obj的數目。

new_slab->obj_num = compute_slab_obj_num(size, page_size);

new_slab->free_num = new_slab->obj_num;

// slab_bufctl數組中儲存的是下一個空閑的obj索引， 相當于用連結清單的形式把obj連結起來。

for (idx = 0; idx < new_slab->obj_num – 1; idx++)

slab_bufctl(new_slab)[idx] = idx + 1;

slab_bufctl(new_slab)[idx] = -1;

if (slab_cache->ctor)

slab_cache->ctor();

slab_cache->slab_page = addr;

slab_cache->free_num += new_slab->free_num;

slab_cache->color_next = get_slab_color(slab_cache);

new_slab->free_idx = 0;

list_add_tail(&(new_slab->list), &(slab_cache->list));

new_slab->base = set_slab_base_addr(addr, new_slab);

new_slab->base = fix_slab_base_addr(new_slab->base,

slab_cache->color_next);

2、配置設定算法

先根據size的大小計算對應的slab_cache_array數組下标， 然後周遊slab連結清單， 找到一個

還有空閑obj的slab。 在通過get_slab_obj函數從中取得一個空閑的obj。

void *get_slab_obj(struct slab *slab, struct slab_cache *slab_cache)

void *obj;

obj = slab->base + slab_cache->slab_size * slab->free_idx;

slab->free_idx = slab_bufctl(slab)[slab->free_idx];

slab->free_num–;

slab_cache->free_num–;

return obj;

void *kmalloc(int size)

struct slab *s = null;

struct list_head *p = null;

if (size < 0 || size > 1024)

idx = check_slab_size(size);

// 當cache中沒有空閑的slab時就擴充這個cache, 重新生成一個slab。

if (!slab_cache_array[idx].free_num) {

printk(“expand slab obj in %d.\n”, idx);

if (!(s = expand_slab(&slab_cache_array[idx]))) {

printk(“expand slab failed.\n”);

obj = get_slab_obj(s, &(slab_cache_array[idx]));

// 周遊slab連結清單找到一個空閑的slab結構。

list_for_each(p, (&slab_cache_array[idx].list)) {

s = list_entry(p, struct slab, list);

if (s && s->free_num) {

// 找到一個空閑的obj。

五、 總結

核心使用buddy和slab共同來維護實體記憶體， 我們在下堂課中将開始講述核心對虛拟記憶體的管理。