目录
一、前景回顾
二、位图bitmap及函数实现
三、内存池划分
四、运行
前面我们已经花了一个回合来完善了一下我们的系统，包括增加了makefile，ASSERT以及一些常见的字符串操作函数。关于makefile，还是我以前学习Linux系统编程的时候学了一点点，很久没用导致就几乎都忘了，还是花了一下午时间去补了一下。看来知识这个东西，还是得温故而知新。
随时还是要回过头来总结一下我们的工作，上面是目前为止的工作，其实我们可以看到，现在我们的主要工作就是不停地往init_all()里面去填充一系列初始化函数，本回合也不例外，今天我们开始进入内存管理系统。
长话短说，举个例子，当我们的程序在申请使用一块物理内存时，该物理内存肯定是不能被占用的。所以这就要求我们每使用一块物理内存，就需要做个标记，这个标记用来指示该物理内存是否已被占用。而我们又知道内存被划分为多个4KB大小的页，如果我们的系统能够标记每一页的使用情况，这样上面的问题就迎刃而解了。所以基于位图bitmap的思想，我们有了如下的位图与内存的关系：
如图所示，我们知道1个字节等于8位，我们用每一位0或者1的状态来表示一页内存是否被占用，0就是未被占用，1就被已被占用。所以我们用一页内存4KB，就可以表示4*1024*8*4KB=128MB内存。
在project/lib/kernel目录下，新建bitmap.c和bitmap.h文件,还需要完善一下stdint.h文件。
1 #ifndef__LIB_KERNEL_BITMAP_H 2 #define__LIB_KERNEL_BITMAP_H 3 #include "stdint.h" 4 5 6 #define BITMAP_MASK 1 7 8 struct bitmap { 9 uint32_t btmp_bytes_len;10 uint8_t *bits;11 };12 13 void bitmap_init(struct bitmap *btmp);14 bool bitmap_scan_test(struct bitmap *btmp, uint32_t bit_idx);15 int bitmap_scan(struct bitmap *btmp, uint32_t cnt);16 void bitmap_set(struct bitmap *btmp, uint32_t bit_idx, int8_t value);17 18 #endifbitmap.h
1 #include "bitmap.h" 2 #include "stdint.h" 3 #include "string.h" 4 #include "debug.h" 5 6 /*将位图btmp初始化*/ 7 void bitmap_init(struct bitmap *btmp) 8 { 9 memset(btmp->bits, 0, btmp->btmp_bytes_len);10 }11 12 /*判断bit_idx位是否为1， 若为1则返回true，否则返回false*/13 bool bitmap_scan_test(struct bitmap *btmp, uint32_t bit_idx)14 {15 uint32_t byte_idx = bit_idx / 8;16 uint32_t bit_odd = bit_idx % 8;17 return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_odd));18 }19 20 /*在位图中申请连续cnt个位，成功则返回其起始地址下标，否则返回-1*/21 int bitmap_scan(struct bitmap *btmp, uint32_t cnt)22 {23 ASSERT(cnt >= 1);24 uint32_t idx_byte = 0;25 26 while ((idx_byte < btmp->btmp_bytes_len) && (btmp->bits[idx_byte] == 0xff))27 idx_byte++;28 29 if (idx_byte == btmp->btmp_bytes_len)30 return -1;31 32 int idx_bit = 0;33 34 while ((btmp->bits[idx_byte] & (uint8_t)(BITMAP_MASK << idx_bit)))35 idx_bit++;36 37 int bit_idx_start = idx_bit + 8 * idx_byte;38 if (cnt == 1)39 return bit_idx_start;40 41 //记录还有多少位可以判断42 uint32_t bit_left = (btmp->btmp_bytes_len)*8 - bit_idx_start;43 uint32_t next_bit = bit_idx_start + 1;44 uint32_t count = 1;45 46 bit_idx_start = -1;47 while (bit_left-- > 0) {48 if (!(bitmap_scan_test(btmp, next_bit)))49 count++;50 else 51 count = 0;52 if (count == cnt) {53 bit_idx_start = next_bit - cnt + 1;54 break;55 }56 next_bit++;57 }58 return bit_idx_start;59 }60 61 /*将位图btmp的bit_idx位设置为value*/62 void bitmap_set(struct bitmap *btmp, uint32_t bit_idx, int8_t value) 63 {64 ASSERT((value == 1) || (value == 0));65 uint32_t byte_idx = bit_idx / 8;66 uint32_t bit_odd = bit_idx % 8;67 if (value)68 btmp->bits[byte_idx] |= (BITMAP_MASK << bit_odd);69 else 70 btmp->bits[byte_idx] &= ~(BITMAP_MASK << bit_odd);71 }bitmap.c
1 #ifndef __LIB_STDINT_H__ 2 #define __LIB_STDINT_H__ 3 typedef signed char int8_t; 4 typedef signed short int int16_t; 5 typedef signed int int32_t; 6 typedef signed long long int int64_t; 7 typedef unsigned char uint8_t; 8 typedef unsigned short int uint16_t; 9 typedef unsigned int uint32_t;10 typedef unsigned long long int uint64_t;11 12 #define true113 #define false014 #define NULL ((void *)0)15 #define bool_Bool16 17 #endifstdint.h
除去页表和操作系统1MB的内存，我们将剩余的物理内存均分为两部分，一部分用于操作系统自己使用，称作内核内存，另一部分用于用户进程使用，称作用户内存。所以，针对这两块内存，需要有两个位图来管理。
另外，由于我们现在处于保护模式下，且开启了分页机制，所以每个进程使用的都是虚拟地址，且名义上都有4GB的虚拟地址大小。进程在申请内存时，首先应该是申请一块虚拟内存，随后操作系统再在用户内存空间中分配空闲的物理块，最后在该用户进程自己的页表中将这两种地址建立好映射关系。
因此，每新建一个进程，我们需要为每一个进程提供一个管理虚拟地址的内存池，也就是需要一个位图来管理。
最后，再啰嗦一下，针对内核也不例外，因为内核也是用的虚拟地址，所以我们也需要一个位图来管理内核的虚拟地址。
说了这么多，还是联系实际内存分布来讲一下内存池具体是怎么个划分法。
在我们前面讲解分页机制那一回，操作系统底层1MB加上页表和页表项所占用的空间，我们已经使用了0x200000，即2MB的内存，忘记的同学请看这里第08回开启分页机制，所以我们的内存分配是从地址0x200000开始。如下图所示：
我们的系统只有32MB的内存，在bochsrc.disk文件中可以看到，也可以在这里设置为其他内存，所以最高可以寻址到0x1FFFFFF处。
可分配的内存从0x200000到0x1FFFFFF处，均分后内核内存的范围就从0x200000~0x10fffff处，用户内存就从0x1100000~到0x1FFFFFF处。按道理来说，32MB空间的位图仅需要1/4物理页便能表示完，但是考虑到拓展性，我们便在0x9a000到0x9e000中间预留了4页，即共计16KB的大小来存储位图。
我们知道内核内存位图和用户内存位图是用来表示内核内存和用户内存的，那么内核虚拟地址位图表示的内存范围是多少呢？事实上，在Linux中任意一个进程的高1GB的空间都是被映射到内核，也即是说我们的内核空间最多只有1GB，因此内核虚拟地址也只有1GB。内核所使用的虚拟地址从0xc0000000开始，除去已经占用的1MB内存，那么内核所能使用的虚拟地址便是从0xc0100000到0xFFFFFFFF。实际到不了0xFFFFFFFF，因为我们这个系统的内核空间有限，按我们现在的规划，内核空间被分配了15MB，所以虚拟地址最多只能到0xc0100000+15MB=0xc0FFFFFF。
最后便是代码实现，在目录project/kernel下建立memory.c和memory.h文件。
#include "memory.h"#include "print.h"#include "stdio.h"#include "debug.h"#include "string.h"#define PG_SIZE 4096 //页大小/*0xc0000000是内核从虚拟地址3G起，* 0x100000意指低端内存1MB，为了使虚拟地址在逻辑上连续* 后面申请的虚拟地址都从0xc0100000开始*/#define K_HEAP_START 0xc0100000 #define PDE_IDX(addr) ((addr & 0xffc00000) >> 22)#define PTE_IDX(addr) ((addr & 0x003ff000) >> 12)struct pool {struct bitmap pool_bitmap; //本内存池用到的位图结构uint32_t phy_addr_start; //本内存池管理的物理内存的起始地址 uint32_t pool_size;//内存池的容量};struct pool kernel_pool, user_pool;//生成内核内存池和用户内存池struct virtual_addr kernel_vaddr;//此结构用来给内核分配虚拟地址/*初始化内存池*/static void mem_pool_init(uint32_t all_mem) {put_str("mem_pool_init start\n");/*目前页表和页目录表的占用内存* 1页页目录表 + 第0和第768个页目录项指向同一个页表 + 第769～1022个页目录项共指向254个页表 = 256个页表*/uint32_t page_table_size = PG_SIZE * 256;uint32_t used_mem = page_table_size + 0x100000;//目前总共用掉的内存空间uint32_t free_mem = all_mem - used_mem;//剩余内存为32MB-used_memuint16_t all_free_pages = free_mem / PG_SIZE;//将剩余内存划分为页，余数舍去，方便计算/*内核空间和用户空间各自分配一半的内存页*/uint16_t kernel_free_pages = all_free_pages / 2; uint16_t user_free_pages = all_free_pages - kernel_free_pages; /*为简化位图操作，余数不用做处理，坏处是这样会丢内存，不过只要内存没用到极限就不会出现问题*/uint32_t kbm_length = kernel_free_pages / 8; //位图的长度单位是字节uint32_t ubm_length = user_free_pages / 8;uint32_t kp_start = used_mem; //内核内存池的起始物理地址uint32_t up_start = kp_start + kernel_free_pages * PG_SIZE; //用户内存池的起始物理地址/*初始化内核用户池和用户内存池*/kernel_pool.phy_addr_start = kp_start;user_pool.phy_addr_start = up_start;kernel_pool.pool_size = kernel_free_pages * PG_SIZE; user_pool.pool_size = user_free_pages * PG_SIZE;kernel_pool.pool_bitmap.btmp_bytes_len = kbm_length;user_pool.pool_bitmap.btmp_bytes_len = ubm_length;/***********内核内存池和用户内存池位图*************内核的栈底是0xc009f00，减去4KB的PCB大小，便是0xc009e00*这里再分配4KB的空间用来存储位图，那么位图的起始地址便是*0xc009a00,4KB的空间可以管理4*1024*8*4KB=512MB的物理内存*这对于我们的系统来说已经绰绰有余了。*//*内核内存池位图地址*/kernel_pool.pool_bitmap.bits = (void *)MEM_BIT_BASE;//MEM_BIT_BASE(0xc009a00)/*用户内存池位图地址紧跟其后*/user_pool.pool_bitmap.bits = (void *)(MEM_BIT_BASE + kbm_length);/*输出内存池信息*/put_str("kernel_pool_bitmap_start:");put_int((int)kernel_pool.pool_bitmap.bits);put_str("\n");put_str("kernel_pool.phy_addr_start:");put_int(kernel_pool.phy_addr_start);put_str("\n");put_str("user_pool_bitmap_start:");put_int((int)user_pool.pool_bitmap.bits);put_str("\n");put_str("user_pool.phy_addr_start:");put_int(user_pool.phy_addr_start);put_str("\n");/*将位图置0*/bitmap_init(&kernel_pool.pool_bitmap);bitmap_init(&user_pool.pool_bitmap);/*初始化内核虚拟地址的位图，按照实际物理内存大小生成数组*/kernel_vaddr.vaddr_bitmap.btmp_bytes_len = kbm_length;/*内核虚拟地址内存池位图地址在用户内存池位图地址其后*/kernel_vaddr.vaddr_bitmap.bits = (void *)(MEM_BIT_BASE + kbm_length + ubm_length);/*内核虚拟地址内存池的地址以K_HEAP_START为起始地址*/kernel_vaddr.vaddr_start = K_HEAP_START;bitmap_init(&kernel_vaddr.vaddr_bitmap);put_str("mem_pool_init done\n");}/*内存管理部分初始化入口*/void mem_init(void){put_str("mem_init start\n");uint32_t mem_bytes_total = 33554432; //32MB内存 32*1024*1024=33554432mem_pool_init(mem_bytes_total);put_str("mem_init done\n");}/*在pf表示的虚拟内存池中申请pg_cnt个虚拟页* 成功则返回虚拟地址的起始地址，失败返回NULL*/static void *vaddr_get(enum pool_flags pf, uint32_t pg_cnt){int vaddr_start = 0;int bit_idx_start = -1;uint32_t cnt = 0;if (pf == PF_KERNEL) {bit_idx_start = bitmap_scan(&kernel_vaddr.vaddr_bitmap, pg_cnt);if (bit_idx_start == -1) {return NULL;}/*在位图中将申请到的虚拟内存页所对应的位给置1*/while (cnt < pg_cnt) {bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 1);}vaddr_start = kernel_vaddr.vaddr_start + bit_idx_start * PG_SIZE;} else { //用户内存池 将来实现用户进程再补充}return (void *)vaddr_start;}/*得到虚拟地址vaddr所对应的pte指针* 这个指针也是一个虚拟地址，CPU通过这个虚拟地址去寻址会得到一个真实的物理地址* 这个物理地址便是存放虚拟地址vaddr对应的普通物理页的地址* 假设我们已经知道虚拟地址vaddr对应的普通物理页地址为0xa* 那么便可以通过如下操作完成虚拟地址和普通物理页地址的映射* *pte = 0xa*/uint32_t *pte_ptr(uint32_t vaddr) {uint32_t *pte = (uint32_t *)(0xffc00000 + \((vaddr & 0xffc00000) >> 10) + \PTE_IDX(vaddr) * 4);return pte;}/*得到虚拟地址vaddr所对应的pde指针* 这个指针也是一个虚拟地址，CPU通过这个虚拟地址去寻址会得到一个真实的物理地址* 这个物理地址便是存放虚拟地址vaddr对应的页表的地址，使用方法同pte_ptr()一样*/uint32_t *pde_ptr(uint32_t vaddr) {uint32_t *pde = (uint32_t *)(0xfffff000 + PDE_IDX(vaddr) * 4);return pde;}/*在m_pool指向的物理内存地址中分配一个物理页* 成功则返回页框的物理地址，失败返回NULL*/static void *palloc(struct pool *m_pool){int bit_idx = bitmap_scan(&m_pool->pool_bitmap, 1);if (bit_idx == -1) {return NULL;}/*在位图中将申请到的物理内存页所对应的位给置1*/bitmap_set(&m_pool->pool_bitmap, bit_idx, 1);/*得到申请的物理页所在地址*/uint32_t page_phyaddr = (m_pool->phy_addr_start + bit_idx * PG_SIZE); return (void *)page_phyaddr;}/*在页表中添加虚拟地址_vaddr与物理地址_page_phyaddr的映射*/static void page_table_add(void *_vaddr, void *_page_phyaddr){uint32_t vaddr = (uint32_t)_vaddr;uint32_t page_phyaddr = (uint32_t)_page_phyaddr;uint32_t *pde = pde_ptr(vaddr);uint32_t *pte = pte_ptr(vaddr);//先判断虚拟地址对应的pde是否存在if (*pde & 0x00000001) {ASSERT(!(*pte & 0x00000001));*pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);} else { //页目录项不存在，需要先创建页目录再创建页表项uint32_t pde_phyaddr = (uint32_t)palloc(&kernel_pool);*pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);/* 将分配到的物理页地址pde_phyaddr对应的物理内存清0*避免里面的陈旧数据变成页表项*//* 这个地方不能这样memset((void *)pde_phyaddr, 0, PG_SIZE);* 因为现在我们所使用的所有地址都是虚拟地址，虽然我们知道pde_phyaddr是真实的物理地址* 可是CPU是不知道的，CPU会把pde_phyaddr当作虚拟地址来使用，这样就肯定无法清0了* 所以解决问题的思路就是：如何得到pde_phyaddr所对应的虚拟地址。*/memset((void *)((int)pte & 0xfffff000), 0, PG_SIZE);ASSERT(!(*pte & 0x00000001));*pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);}}/*分配pg_cnt个页空间，成功则返回起始虚拟地址，失败返回NULL*/void *malloc_page(enum pool_flags pf, uint32_t pg_cnt){ASSERT((pg_cnt > 0) && (pg_cnt < 3840));void *vaddr_start = vaddr_get(pf, pg_cnt);if (vaddr_start == NULL) {return NULL;}uint32_t vaddr = (uint32_t)vaddr_start;uint32_t cnt = pg_cnt;struct pool *mem_pool = pf & PF_KERNEL ? &kernel_pool : &user_pool;/*因为虚拟地址连续，而物理地址不一定连续，所以逐个做映射*/while (cnt-- > 0) {void *page_phyaddr = palloc(mem_pool);if (page_phyaddr == NULL) {return NULL;}page_table_add((void *)vaddr, page_phyaddr);vaddr += PG_SIZE;}return vaddr_start;}/*从内核物理内存池中申请pg_cnt页内存，成功返回其虚拟地址，失败返回NULL*/void *get_kernel_pages(uint32_t pg_cnt){void *vaddr = malloc_page(PF_KERNEL, pg_cnt);if (vaddr != NULL) {memset(vaddr, 0, pg_cnt * PG_SIZE);}return vaddr;}/*得到虚拟地址映射的物理地址*/uint32_t addr_v2p(uint32_t vaddr){uint32_t *pte = pte_ptr(vaddr);return ((*pte & 0xfffff000) + (vaddr & 0x00000fff));}memory.c
#ifndef__KERNEL_MEMORY_H#define__KERNEL_MEMORY_H#include "stdint.h"#include "bitmap.h"#define MEM_BIT_BASE 0xc009a000/*虚拟地址池，用于虚拟地址管理*/struct virtual_addr {struct bitmap vaddr_bitmap;//虚拟地址用到的位图结构uint32_t vaddr_start;//虚拟地址起始地址};/*内存池标记，用于判断用哪个内存池*/enum pool_flags {PF_KERNEL = 1,PF_USER = 2};#definePG_P_11 //页表项或页目录项存在属性位，存在#definePG_P_00 //页表项或页目录项存在属性位，不存在#definePG_RW_R 0 //R/W属性位值，不可读/不可写#definePG_RW_W 2 //R/W属性位值，可读/可写#definePG_US_S 0 //U/S属性位值，系统级#definePG_US_U 4 //U/S属性位值，用户级void mem_init(void);void *get_kernel_pages(uint32_t pg_cnt);uint32_t addr_v2p(uint32_t vaddr);#endifmemory.h
关于代码这块，如果读者认真去读的话，可能会对这两个函数有所困惑，当时我也是思考了挺久，这里我尝试以我的理解方式来讲解一下，希望能对读者有所帮助。
uint32_t *pte_ptr(uint32_t vaddr) {uint32_t *pte = (uint32_t *)(0xffc00000 + \((vaddr & 0xffc00000) >> 10) + \PTE_IDX(vaddr) * 4);return pte;}uint32_t *pde_ptr(uint32_t vaddr) {uint32_t *pde = (uint32_t *)(0xfffff000 + PDE_IDX(vaddr) * 4);return pde;}
先看pde_ptr函数，这个函数的作用就是给定一个虚拟地址A，返回该地址所在的页表的位置。注意，这个返回的地址也是虚拟地址B，只是这个虚拟地址B在我们的页表机制中，映射到虚拟地址A所在页表的真实物理地址，有点绕，需要多读一下。
那么如何得到这个虚拟地址B呢？
首先来分析一个虚拟地址，例如0xFFFFF001。
我们知道它的地址高10位是用来在页目录表中寻址找到页表地址，中间10位是用来在页表中寻址找到物理页地址，最后12位是用来在物理页中做偏移的。
又因为我们在页目录表中的最后一项中将本该填写的页表地址填写为页目录表的地址，所以现在我们通过0xFFFFF000这样的地址就能访问到页目录表本身，此时对于CPU来讲，页目录表就是一个物理页。不清楚的同学可以将数据带进去寻址以便理解。那么对于虚拟地址0xFFFFF001来说，他所在的页表地址是高10位决定的，我们通过PDE_IDX()函数，便能得到这高10位数据，随后再将该10位数据乘以4加上0xFFFFF000，便能得到虚拟地址0xFFFFF001所对应的页表的虚拟地址。
再来看pte_ptr函数，这个函数的作用就是给定一个虚拟地址A，返回该地址所在的物理页的地址，同样的，这个返回的地址也是一个虚拟地址，这里称作虚拟地址B。我们知道，物理页的地址是存放在页表中的，所以我们需要先得到页表地址。
还是以虚拟地址A，0xFFFFF001为例。
首先我们构建一个虚拟地址C，0xFFC00000，这个地址带进去寻址很好理解，我们只看高10位，寻址完后依旧是跳转到页目录表地址处，注意，此时CPU认为它是一个页表，而不是页目录表。接下来我们将虚拟地址A的高10位（通过 (vaddr & 0xffc00000) >> 10的方式得到）用来在这个页表中寻址，得到一个地址。这个地址其实就是虚拟地址A所在页表的地址，最后我们将虚拟地址A的中间10位（通过 (vaddr & 0x003FF000) >> 10的方式得到）乘以4，用来在这个页表中（此时CPU认为这是一个物理页，所以需要手动乘4）寻址，便得到了虚拟地址A所对应的物理页的虚拟地址。
写到这里，我还是感觉没有说的很清楚，限于表达能力有限，希望读者能够一边画图一边理解吧。
前面说了这么多，是时候验证一下我们的代码正确性。修改init.c和main.c文件，最后，不要忘记在makefile中增加bitmap.o和memory.o。
#include "init.h"#include "print.h"#include "interrupt.h"#include "timer.h"#include "memory.h"void init_all(void){put_str("init_all\n");idt_init();timer_init();mem_init();}init.c
#include "print.h"#include "init.h"#include "memory.h"int main(void){put_str("HELLO KERNEL\n");init_all();void *addr = get_kernel_pages(3);put_str("\n get_kernel_page start vaddr is ");put_int((uint32_t)addr);put_str("\n");while(1); }main.c
可以看到运行效果与我们实际规划一致，这一回就到这里。预知后事如何，请看下回分解。