[自製操作系統] 第14回 內存管理系統
- 2022 年 7 月 7 日
- 筆記
目錄
一、前景回顧
二、位圖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"
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
可以看到運行效果與我們實際規劃一致，這一回就到這裡。預知後事如何，請看下回分解。
