作者：王智通
一、前言
我们在前面讲述进程设计与调 度的时候涉及到， 当内核要创建一个进程的时候， 会分配一个进程描述符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共同来维护物理内存， 我们在下堂课中将开始讲述内核对虚拟内存的管理。
