[自制作業系統] 第14回 記憶體管理系統
目錄
一、前景回顧
二、點陣圖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
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 }
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
除去頁表和作業系統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));
}
#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
關於程式碼這塊，如果讀者認真去讀的話，可能會對這兩個函數有所困惑，當時我也是思考了挺久，這裡我嘗試以我的理解方式來講解一下，希望能對讀者有所幫助。
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();
}
#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);
}
可以看到執行效果與我們實際規劃一致，這一回就到這裡。預知後事如何，請看下回分解。