操作系統實現：記憶體管理

本文參考書：操作系統真像還原、電腦組成原理（微課版）

所謂記憶體管理包含：

　　物理記憶體

　　虛擬地址空間

以上就是記憶體管理中所要管理的資源。那麼記憶體管理的第一步就應該是整理出這兩種資源。

物理記憶體要分為兩部分：

　　①內核記憶體

　　②用戶記憶體

在內核態下也經常會有一些記憶體申請，比如申請個pcb、頁表等等。內核態和用戶態所試用的記憶體要分隔開，用戶態不能直接訪問內核態的記憶體。

操作系統在進入保護模式前會通過

int 15h ax = E801h 獲取記憶體大小,最大支持4G

或者其他軟中斷獲取電腦記憶體大小 mm_bytes，並將mm_bytes放在一個記憶體地址我們這裡是放在 物理地址0xb00。

這裡可能有個疑問，我們將mm_bytes 放在0xb00處，進入保護模式後開啟了虛擬地址，那怎麼知道0xb00的虛擬地址是什麼？

答：在操作系統建立頁表時，低地址物理記憶體和虛擬地址設計為1對1映射，既 0xb00物理地址== 0xb00虛擬地址。

在本文章中操作系統實現中低1M記憶體是1對1映射的。

有了物理記憶體的大小，那下一步就應該建立結構以便對記憶體進行管理。

struct pool {
   struct bitmap pool_bitmap;     // 本記憶體池用到的點陣圖結構,用於管理物理記憶體
   uint32_t phy_addr_start;     // 本記憶體池所管理物理記憶體的起始地址
   uint32_t pool_size;         // 本記憶體池位元組容量
   struct lock lock;         // 申請記憶體時互斥
};

物理記憶體也需要點陣圖進行管理 bitmap 實現之前說過了，用戶點陣圖和內核點陣圖可以放在1M內找幾個連續頁存放。看個人設計。

物理記憶體起始地址 phy_addr_start 是需要計算的，我們要知道低段記憶體部分哪些空間是被占用了。

在本文章中內核放在低1M處，1M開始處又放了256個頁（頁表實現文章）。所以

phy_addr_start = 0x100000 + PG_SIZE * 256

pool_size    內核位元組池的容量，這裡分配多少按操作系統需求來設計，本文章直接將可用記憶體容量的一半分給內核。

free_mm = mm_bytes - phy_addr_start   //可用記憶體

可用記憶體就這些但是可以直接 ÷ 2 分配給內核嗎？

答：是不行的，我們知道記憶體只要通過點陣圖管理的，每個點陣圖指向4K大小的頁，所以我們要先計算出可用記憶體有多少頁，按總頁數一半的來給pool_size

all_free_pages = free_mm / PG_SIZE;

kernel_free_pages = all_free_pages / 2;

pool_size = kernel_free_pages * PG_SIZE;

類似地用戶記憶體池做一下減法就好了。

物理記憶體頁申請

 * 成功則返回頁框的物理地址,失敗則返回NULL */
static void* palloc(struct pool* m_pool) {
   /* 掃描或設置點陣圖要保證原子操作 */
   int bit_idx = bitmap_scan(&m_pool->pool_bitmap, 1);    // 找一個物理頁面
   if (bit_idx == -1 ) {
      return NULL;
   }
   bitmap_set(&m_pool->pool_bitmap, bit_idx, 1);    // 將此位bit_idx置1
   uint32_t page_phyaddr = ((bit_idx * PG_SIZE) + m_pool->phy_addr_start);
   return (void*)page_phyaddr;
}

bit_idx是返回的是頁起始下標， bit_idx * PG_SIZE是偏移地址 + 基地址 就是物理頁位置。

虛擬記憶體管理主要是處理的是虛擬地址和物理地址映射問題。

虛擬地址管理分為：

　　內核多級頁表

　　每個進程一個多級頁表

其中進程的多級頁表，是在進程創建時申請的記憶體頁建立的這裡只說內核頁表，進程的是類似的只是多了個申請頁的過程。

內核頁表是在進入保護模式前建好了，在之前的文章里寫過。

虛擬地址所使用的結構如下：

/* 用於虛擬地址管理 */
struct virtual_addr {
/* 虛擬地址用到的點陣圖結構，用於記錄哪些虛擬地址被占用了。以頁為單位。*/
   struct bitmap vaddr_bitmap;
/* 管理的虛擬地址 */
   uint32_t vaddr_start;
};

內核二級頁表

虛擬地址低1M的地址空間和物理地址是1-1映射關係。既0號頁目錄項指向第0個頁表，第0個頁表的0-254個頁表項指向物理地址 0-1M。 

在32位系統中，所有頁表的虛擬地址 3G以上空間都是內核虛擬地址對應關係，3G空間的起始部位為頁目錄項第768項。

所以我們只需要一直更新內核頁目錄第768項到1023項所指向的頁表，就可以保證其他進程頁表的內核虛擬地址空間同步變化。

內核頁目錄的第768-1023項也是指向 0-255 號頁表。這是在未開啟保護模式前就初始化寫好的。（詳細看頁表實現文章）

至於低1M的1-1映射，主要為了方便操作。

所以內核虛擬地址結構的 vaddr_start 應該初始化為0xc0100000 ，這裡就是768項跳過了低1M空間的虛擬地址。

如何建立物理地址與虛擬地址的映射關係？

先申請一個物理地址，再申請一個虛擬地址，拿到了2個地址後，我們要在虛擬地址對應的頁表項中填寫對應的物理地址（高24位）。

如何拿到虛擬地址對應的頁表項？

首先要找到頁目錄表，頁目錄項（虛擬地址高10位）存在則拿到頁表，要判斷頁表項（虛擬地址中間10位）未使用後填入物理地址（高24位）。

　　　　　　　　　　頁目錄項不存在還要創建新頁表，再填入頁目錄項後再進行後續操作。

如何拿到頁表項物理地址？

#define PTE_IDX(addr) ((addr & 0x003ff000) >> 12)

uint32_t* pte_ptr(uint32_t vaddr) {
   /* 先訪問到頁表自己 + \
    * 再用頁目錄項pde(頁目錄內頁表的索引)做為pte的索引訪問到頁表 + \
    * 再用pte的索引做為頁內偏移*/
   uint32_t* pte = (uint32_t*)(0xffc00000 + \
     ((vaddr & 0xffc00000) >> 10) + \
     PTE_IDX(vaddr) * 4);
   return pte;
}

0xffc00000  代表選擇最後一個頁目錄項，前10位都是1，在頁表實現中，我們已經，提前設置好最後一個頁目錄項存放的是頁目錄物理基地址所以虛擬地址0xffc00000的含義是將頁目錄表當成頁表，返回的是當前頁目錄表的物理地址

（vaddr & 0xffc00000） >> 10是將vaddr虛擬地址的前10位移動到中間10位，和0xffc00000相加在這裡也可以理解為將頁目錄表當成頁表在頁目錄表中選擇頁目錄項，返回的是我們要的頁表物理地址。

PTE_IDX(vaddr) * 4  代表選擇頁表中的頁表項，也就是返回pte地址

如何拿到頁目錄項物理地址？

#define PDE_IDX(addr) ((addr & 0xffc00000) >> 22)

uint32_t* pde_ptr(uint32_t vaddr) {
   /* 0xfffff是用來訪問到頁表本身所在的地址 */
   uint32_t* pde = (uint32_t*)((0xfffff000) + PDE_IDX(vaddr) * 4);
   return pde;
}

提前設置好最後一個頁目錄項存放的是頁目錄物理基地址， 0xfffff000 前20位是 1111111111 1111111111 ，代表頁目錄表基地址

建立一一映射關係：

static void page_table_add(void* _vaddr, void* _page_phyaddr) {
   uint32_t vaddr = (uint32_t)_vaddr, page_phyaddr = (uint32_t)_page_phyaddr;
   uint32_t* pde = pde_ptr(vaddr);
   uint32_t* pte = pte_ptr(vaddr);

/************************   註意   *************************
 * 執行*pte,會訪問到pde。所以確保pde創建完成後才能執行*pte,
 * 否則會引發page_fault。因此在pde未創建時,
 * *pte只能出現在下麵最外層else語句塊中的*pde後面。
 * *********************************************************/
   /* 先在頁目錄內判斷目錄項的P位，若為1,則表示該表已存在 */
   if (*pde & 0x00000001) {
      ASSERT(!(*pte & 0x00000001));

      if (!(*pte & 0x00000001)) {   // 只要是創建頁表,pte就應該不存在,多判斷一下放心
    *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);    // US=1,RW=1,P=1
      } else {   // 調試模式下不會執行到此,上面的ASSERT會先執行.關閉調試時下麵的PANIC會起作用
    PANIC("pte repeat");
      }
   } else {       // 頁目錄項不存在,所以要先創建頁目錄項再創建頁表項.
      /* 頁表中用到的頁框一律從內核空間分配 */
      uint32_t pde_phyaddr = (uint32_t)palloc(&kernel_pool);
      *pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);

/*******************   必須將頁表所在的頁清0   *********************
* 必須把分配到的物理頁地址pde_phyaddr對應的物理記憶體清0,
* 避免裡面的陳舊數據變成了頁表中的頁表項,從而讓頁表混亂.
* pte的高20位會映射到pde所指向的頁表的物理起始地址.*/
      memset((void*)((int)pte & 0xfffff000), 0, PG_SIZE); 
/************************************************************/
      ASSERT(!(*pte & 0x00000001));
      *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);      // US=1,RW=1,P=1
   }
}

記憶體回收，將分配的頁表項的P位取消。

　　　　　　內核或者用戶物理地址bitmap改為0

　　　　　　虛擬地址bitmap 設為0

/* 將物理地址pg_phy_addr回收到物理記憶體池 */
void pfree(uint32_t pg_phy_addr) {
   struct pool* mem_pool;
   uint32_t bit_idx = 0;
   if (pg_phy_addr >= user_pool.phy_addr_start) {     // 用戶物理記憶體池
      mem_pool = &user_pool;
      bit_idx = (pg_phy_addr - user_pool.phy_addr_start) / PG_SIZE;
   } else {      // 內核物理記憶體池
      mem_pool = &kernel_pool;
      bit_idx = (pg_phy_addr - kernel_pool.phy_addr_start) / PG_SIZE;
   }
   bitmap_set(&mem_pool->pool_bitmap, bit_idx, 0);     // 將點陣圖中該位清0
}

/* 去掉頁表中虛擬地址vaddr的映射,只去掉vaddr對應的pte */
static void page_table_pte_remove(uint32_t vaddr) {
   uint32_t* pte = pte_ptr(vaddr);
   *pte &= ~PG_P_1;    // 將頁表項pte的P位置0
   asm volatile ("invlpg %0"::"m" (vaddr):"memory");    //更新tlb
}

/* 在虛擬地址池中釋放以_vaddr起始的連續pg_cnt個虛擬頁地址 */
static void vaddr_remove(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt) {
   uint32_t bit_idx_start = 0, vaddr = (uint32_t)_vaddr, cnt = 0;

   if (pf == PF_KERNEL) {  // 內核虛擬記憶體池
      bit_idx_start = (vaddr - kernel_vaddr.vaddr_start) / PG_SIZE;
      while(cnt < pg_cnt) {
     bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 0);
      }
   } else {  // 用戶虛擬記憶體池
      struct task_struct* cur_thread = running_thread();
      bit_idx_start = (vaddr - cur_thread->userprog_vaddr.vaddr_start) / PG_SIZE;
      while(cnt < pg_cnt) {
     bitmap_set(&cur_thread->userprog_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 0);
      }
   }
}

/* 釋放以虛擬地址vaddr為起始的cnt個物理頁框 */
void mfree_page(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt) {
   uint32_t pg_phy_addr;
   uint32_t vaddr = (int32_t)_vaddr, page_cnt = 0;
   ASSERT(pg_cnt >=1 && vaddr % PG_SIZE == 0); 
   pg_phy_addr = addr_v2p(vaddr);  // 獲取虛擬地址vaddr對應的物理地址

/* 確保待釋放的物理記憶體在低端1M+1k大小的頁目錄+1k大小的頁表地址範圍外 */
   ASSERT((pg_phy_addr % PG_SIZE) == 0 && pg_phy_addr >= 0x102000);
   
/* 判斷pg_phy_addr屬於用戶物理記憶體池還是內核物理記憶體池 */
   if (pg_phy_addr >= user_pool.phy_addr_start) {   // 位於user_pool記憶體池
      vaddr -= PG_SIZE;
      while (page_cnt < pg_cnt) {
     vaddr += PG_SIZE;
     pg_phy_addr = addr_v2p(vaddr);

     /* 確保物理地址屬於用戶物理記憶體池 */
     ASSERT((pg_phy_addr % PG_SIZE) == 0 && pg_phy_addr >= user_pool.phy_addr_start);

     /* 先將對應的物理頁框歸還到記憶體池 */
     pfree(pg_phy_addr);

         /* 再從頁表中清除此虛擬地址所在的頁表項pte */
     page_table_pte_remove(vaddr);

     page_cnt++;
      }
   /* 清空虛擬地址的點陣圖中的相應位 */
      vaddr_remove(pf, _vaddr, pg_cnt);

   } else {         // 位於kernel_pool記憶體池
      vaddr -= PG_SIZE;          
      while (page_cnt < pg_cnt) {
     vaddr += PG_SIZE;
     pg_phy_addr = addr_v2p(vaddr);
      /* 確保待釋放的物理記憶體只屬於內核物理記憶體池 */
     ASSERT((pg_phy_addr % PG_SIZE) == 0 && \
           pg_phy_addr >= kernel_pool.phy_addr_start && \
           pg_phy_addr < user_pool.phy_addr_start);
    
     /* 先將對應的物理頁框歸還到記憶體池 */
     pfree(pg_phy_addr);

         /* 再從頁表中清除此虛擬地址所在的頁表項pte */
     page_table_pte_remove(vaddr);

     page_cnt++;
      }
   /* 清空虛擬地址的點陣圖中的相應位 */
      vaddr_remove(pf, _vaddr, pg_cnt);
   }
}

/* 回收記憶體ptr */
void sys_free(void* ptr) {
   ASSERT(ptr != NULL);
   if (ptr != NULL) {
      enum pool_flags PF;
      struct pool* mem_pool;

   /* 判斷是線程還是進程 */
      if (running_thread()->pgdir == NULL) {
     ASSERT((uint32_t)ptr >= K_HEAP_START);
     PF = PF_KERNEL; 
     mem_pool = &kernel_pool;
      } else {
     PF = PF_USER;
     mem_pool = &user_pool;
      }

      lock_acquire(&mem_pool->lock);   
      struct mem_block* b = ptr;
      struct arena* a = block2arena(b);         // 把mem_block轉換成arena,獲取元信息
      ASSERT(a->large == 0 || a->large == 1);
      if (a->desc == NULL && a->large == true) { // 大於1024的記憶體
     mfree_page(PF, a, a->cnt); 
      } else {                 // 小於等於1024的記憶體塊
     /* 先將記憶體塊回收到free_list */
     list_append(&a->desc->free_list, &b->free_elem);

     /* 再判斷此arena中的記憶體塊是否都是空閑,如果是就釋放arena */
     if (++a->cnt == a->desc->blocks_per_arena) {
        uint32_t block_idx;
        for (block_idx = 0; block_idx < a->desc->blocks_per_arena; block_idx++) {
           struct mem_block*  b = arena2block(a, block_idx);
           ASSERT(elem_find(&a->desc->free_list, &b->free_elem));
           list_remove(&b->free_elem);
        }
        mfree_page(PF, a, 1); 
     } 
      }   
      lock_release(&mem_pool->lock); 
   }
}