764
物理內存管理係統設計與實現
作者：王智通
一、前言
我們在前麵講述進程設計與調 度的時候涉及到， 當內核要創建一個進程的時候， 會分配一個進程描述符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; 內存塊的大小
unsigned int type; 內存塊的類型
};
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;
unsigned int i;
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)
————————————————————–
| kernel_code | kernel_data | kernel_bss | buddy & slab |
————————————————————–
大家有注意到從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 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)
return NULL;
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;
}
return addr;
五、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| …
—–
|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)
{
int i;
for (i = 0; i < SLAB_NUM; i++) {
void *addr;
// 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;
void *base;
int idx;
// 根據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;
void *obj;
int idx;
if (size < 0 || size > 1024)
return NULL;
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”);
return NULL;
}
obj = get_slab_obj(s, &(slab_cache_array[idx]));
return obj;
}
// 遍曆slab鏈表找到一個空閑的slab結構。
list_for_each(p, (&slab_cache_array[idx].list)) {
s = list_entry(p, struct slab, list);
if (s && s->free_num) {
// 找到一個空閑的obj。
obj = get_slab_obj(s, &(slab_cache_array[idx]));
return obj;
}
}
return NULL;
}
五、 總結
內核使用buddy和slab共同來維護物理內存， 我們在下堂課中將開始講述內核對虛擬內存的管理。
最後更新：2017-04-03 07:57:05
上一篇：
Web 研發模式演變
下一篇： [互聯網]你剛才在淘寶上買了一件東西
- MFC Edit控件 error:“DDX_Control”: 不能將參數 3 從“int”轉換為“CWnd &”
- asp.net的MVC編程、MV編程以及URL重寫
- andriod遊戲音效
- 使用 Rodeo 分析總統候選人的推特內容
- uva 103 - Stacking Boxes DAG最長路
- 據說一個成功的研發團隊應具備這9大屬性
- Java4Android之httpclient學習與應用
- java中報錯java.sql.Timestamp cannot be cast to java.sql.Date
- undefined reference to libiconv_open ext/iconv/.libs/iconv.o by install phpsource
- 一周見聞 »高收入主播逃稅，大數據能答應？