目錄 一、前景回顧 二、點陣圖bitmap及函數實現 三、記憶體池劃分 四、運行 一、前景回顧 前面我們已經花了一個回合來完善了一下我們的系統，包括增加了makefile，ASSERT以及一些常見的字元串操作函數。關於makefile，還是我以前學習Linux系統編程的時候學了一點點，很久沒用導致就幾乎 ...
目錄
一、前景回顧
二、點陣圖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 #endif
bitmap.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 true 1
13 #define false 0
14 #define NULL ((void *)0)
15 #define bool _Bool
16
17 #endif
stdint.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_mem
uint16_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=33554432
mem_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
};
#define PG_P_1 1 //頁表項或頁目錄項存在屬性位，存在
#define PG_P_0 0 //頁表項或頁目錄項存在屬性位，不存在
#define PG_RW_R 0 //R/W屬性位值，不可讀/不可寫
#define PG_RW_W 2 //R/W屬性位值，可讀/可寫
#define PG_US_S 0 //U/S屬性位值，系統級
#define PG_US_U 4 //U/S屬性位值，用戶級
void mem_init(void);
void *get_kernel_pages(uint32_t pg_cnt);
uint32_t addr_v2p(uint32_t vaddr);
#endif
memory.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"
