blog of chuj

《操作系统真像还原》操作系统实现——内存池管理

Posted on May 25, 2021

操作系统需要管理内存页的映射，即虚拟地址和物理地址的映射关系，一种简单的方法是一对一映射，管理起来也比较方便，申请的时候填写页表，释放的时候清空页表就可以了，但是这样就背离了我们引入虚拟地址的初衷。而若想使用乱序映射的映射方法，我们需要用某种数据结构来管理物理内存的使用情况。

我们使用位图这种数据结构。

位图

所谓位图，其实就是一串连续的地址空间，常常表现为一个数组，其中每一位映射一个对象，这样就可以表示对象的两种状态，比如被使用和未被使用。我们使用一张位图来映射整个物理内存，粒度为页，即一位表示一张内存页的使用状态，某位为 1，代表该位映射的内存页处于被使用状态，为 0 则该页为空闲状态，可以被映射给虚拟内存页。

struct bitmap
{
    size_t bitmap_bytes_len;
    uint8_t* bits;
};

如上我们建立了一个位图管理结构体，变量 bitmap_bytes_len 表示位图总共有多少个字节，指针 bits 指向位图的基地址。

通过函数 BitmapSetBit 我们可以设置位图中的某一位

void BitmapSetBit(struct bitmap* btmp, size_t bit_idx, int8_t value)
{
    ASSERT((value == 0) || (value == 1));
    size_t byte_idx = bit_idx / 8;
    size_t bit_order = bit_idx % 8;
    if (value)
    {
       btmp->bits[byte_idx] |= (BITMAP_MASK << bit_order);
    }
    else
    {
       btmp->bits[byte_idx] &= ~(BITMAP_MASK << bit_order);
    }
}

通过函数 BitmapTestBit 可以检查某一位的值，即代表莫物理页的使用情况

int BitmapTestBit(struct bitmap* btmp, size_t bit_idx)
{
    size_t byte_idx = bit_idx / 8;
    size_t bit_order = bit_idx % 8;
    return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_order));
}

通过函数 BitmapScan 可以分配连续的 cnt 物理内存页

int BitmapScan(struct bitmap* btmp, size_t cnt)
{
    size_t byte_idx = 0;
    while (btmp->bits[byte_idx] == 0xFF && byte_idx < btmp->bitmap_bytes_len)
    {
        byte_idx++;
    }
    ASSERT(byte_idx < btmp->bitmap_bytes_len); /* this means all physic page had been mapped */
    if (byte_idx >= btmp->bitmap_bytes_len)
    {
        return -1;
    }
  
    size_t bit_idx = 0;
    while ((uint8_t)(BITMAP_MASK << bit_idx) & btmp->bits[byte_idx])
    {
        ++bit_idx;
    }

    int bit_idx_start = byte_idx * 8 + bit_idx;
    if (cnt == 1)
    {
        return bit_idx_start;
    }

    size_t bits_left = btmp->bitmap_bytes_len * 8 - bit_idx_start;
    size_t next_bit = bit_idx_start + 1;
    size_t avl_bits_count = 1;

    while (bits_left-- > 0)
    {
        if (!(BitmapTestBit(btmp, next_bit)))
        {
            avl_bits_count++;
        }
        else
        {
            avl_bits_count = 0;
        }
        if (avl_bits_count == cnt)
        {
            return next_bit - cnt + 1;
            break;
        }
        next_bit++;
    }
    return -1;
}

结构体中的 bits 指向真正的位图。

内存池

有了位图，我们就可以对物理内存和虚拟地址进行管理了，我们把内存看作一个内存池，以页为单位进行分配。

对于每个特权级（其实就只有用户级和内核级），我们使用两张位图，一张表示物理地址的映射情况，一张表示虚拟地址的映射情况，这样我们在分配内存的时候就可以先通过查虚拟地址位图判断虚拟地址是否已映射，若未被映射，则通过物理地址位图搜索可用的物理内存页。

初始化

首先要做的就是初始化内存池位图结构和虚拟地址位图，在文件 memory.h 中，我们先进行如下声明

#ifndef __KERNEL_MEMORY_H
#define __KERNEL_MEMORY_H
#include "stdint.h"
#include "bitmap.h"

/* manage virtual addr mapping */
struct virtual_addr
{
    struct bitmap vaddr_bitmap;
    size_t vaddr_start;
};

extern struct memory_pool kernel_memory_pool, user_memory_pool;
void VmemInit();
#endif

两个 memory_pool 是定义在 memory.c 中的，目的是让整个内核都可以访问到这个两个内存池结构体。内存池结构体的定义如下

struct memory_pool
{
    struct bitmap pool_bitmap;
    size_t physic_addr_start;
    size_t pool_size;
};

注意这里的内存池是针对物理内存的，所以其维护的是物理地址的起点和池的大小。

在头文件中声明了内存初始化函数 VmemInit，其定义如下

void VmemInit()
{
    sys_putstr("vmem_init start..\n");
    size_t memory_total_bytes = *(size_t *) (0x810);
    /* memory_pool init */
    VmemPoolInit(memory_total_bytes);

    sys_putstr("done\n");
}

首先先获得物理内存的大小，这是我们在 loader 中通过 BIOS 中段获取的，存储于物理地址 0x810 处。然后调用内存池初始化函数 VmemPoolInit 对内存池进行初始化。

all_mem 中存储了本机的物理内存，这里需要考虑内存的分配上限问题，换句话说就是内核内存池和用户内存池各涵盖多少物理内存，毕竟是为了学习，这里也不考虑太多，我们直接将物理内存对半分，一半给内核，一半用户。

static void VmemPoolInit(size_t all_mem)
{
    sys_putstr("    memory_pool_init start..");
    size_t page_table_size = PAGE_SIZE * 256;
    size_t used_mem = page_table_size + 0x100000;
    size_t free_mem = all_mem - used_mem;
    size_t free_pages_sum = free_mem / PAGE_SIZE;
    size_t kernel_free_pages = free_pages_sum / 2;
    size_t user_free_pages = free_pages_sum - kernel_free_pages;

    size_t kernel_bitmap_length = kernel_free_pages / 8;
    size_t user_bitmap_length = user_free_pages / 8;

    size_t kernel_memory_pool_start = used_mem;
    size_t user_memory_pool_start = kernel_memory_pool_start + kernel_free_pages * PAGE_SIZE;

    kernel_memory_pool.pool_bitmap.bitmap_bytes_len = kernel_bitmap_length;
    user_memory_pool.pool_bitmap.bitmap_bytes_len = user_bitmap_length;
    kernel_memory_pool.pool_bitmap.bits = (void *) MEM_BITMAP_BASE;
    user_memory_pool.pool_bitmap.bits = (void *) (MEM_BITMAP_BASE + kernel_bitmap_length);

    kernel_memory_pool.physic_addr_start = kernel_memory_pool_start;
    user_memory_pool.physic_addr_start = user_memory_pool_start;

    kernel_memory_pool.pool_size = kernel_free_pages * PAGE_SIZE;
    user_memory_pool.pool_size = user_free_pages * PAGE_SIZE;

    /* virtual_addr init */
    kernel_vaddr.vaddr_bitmap.bitmap_bytes_len = kernel_bitmap_length;
    kernel_vaddr.vaddr_bitmap.bits = \
        (void*)(kernel_bitmap_length + user_bitmap_length + MEM_BITMAP_BASE);
    kernel_vaddr.vaddr_start = KERNEL_HEAP_BASE;
    BitmapInit(&kernel_vaddr.vaddr_bitmap);
  
    sys_putstr("\n        kernel_pool_bitmap_start: 0x");
    sys_puthex((int)kernel_memory_pool.pool_bitmap.bits);
    sys_putstr("\n        kernel_pool_physic_addr_start: 0x");
    sys_puthex(kernel_memory_pool.physic_addr_start);

    sys_putstr("\n        user_pool_bitmap_start: 0x");
    sys_puthex((int)user_memory_pool.pool_bitmap.bits);
    sys_putstr("\n        user_pool_physic_addr_start: 0x");
    sys_puthex(user_memory_pool.physic_addr_start);

    BitmapInit(&kernel_memory_pool.pool_bitmap);
    BitmapInit(&user_memory_pool.pool_bitmap);  

    sys_putstr("\n    done\n");
}

这里先提前初始化一些变量，然后开始对两个内存池进行初始化，感觉没什么特别的，不多说了。

管理

对于一个内存池，最基本的，内核需要提供内存页的映射的方法，即将虚拟内存页和物理内存页完成映射（通过填写二级页表来完成）。同时还需要能够完成对物理页的分配和回收。

物理页的分配

在位图的帮助下，物理页分配起来其实是比较容易的，只需要遍历一遍内存池位图找到可用的内存页，然后更新位图设置该页已被使用即可，由于虚拟页和物理页是乱序映射的，所以内存页没有必要分配连续的页，一页页分配即可。

/* alloc one page from the m_pool */
static void* GetOnePhysicPage(struct memory_pool* m_pool)
{
    int bit_idx = BitmapScan(&m_pool->pool_bitmap, 1); 
    if (bit_idx == -1)
    {
        return NULL;
    }
    else
    {
        BitmapSetBit(&m_pool->pool_bitmap, bit_idx, 1);
        size_t page_physic_addr = ((bit_idx * PAGE_SIZE) + m_pool->physic_addr_start);
        return (void *) page_physic_addr;
    }
}

传入一个内存池，返回一张物理页的物理地址，如果无法分配，返回 NULL。

虚拟页的分配

虚拟页的分配需要连续，而且需要区分内核虚拟页和用户虚拟页，这里暂时还没有实现为用户分配的处理。

/* get request_page_cnt pages, they must be contiguous */
static void* GetVirtualPage(enum pool_flags pf, size_t request_page_cnt)
{
    size_t Vaddr_start = NULL;
    size_t physic_page_bit_idx = -1;
    size_t cnt = 0;
    if (pf == KERNEL_POOL)
    {
        if(( physic_page_bit_idx = BitmapScan(&kernel_memory_pool.pool_bitmap, request_page_cnt) ) != -1)
        {
            while (cnt < request_page_cnt)
            {
                BitmapSetBit(&kernel_memory_pool.pool_bitmap, physic_page_bit_idx + cnt++, 1); /* set this page is mapped */
            }
            Vaddr_start = kernel_vaddr.vaddr_start + physic_page_bit_idx * PAGE_SIZE;
        }
        else
        {
            return NULL;
        }
    }
    else
    {
        /* user pool, unused for now */
    }
    return (void *)Vaddr_start;
}

虚拟页和物理页的映射

建立映射的过程其实就是填写 PDE 和 PTE 表的过程，要填写这两张表，就需要获得两张表的虚拟地址，我们提前实现两个函数来计算，在看函数前先回顾一下硬件将虚拟地址转换为物理地址的方法

  1. 取得虚拟地址的高十位，以此为下标查 PDE 获取虚拟地址对于的 PTE 表地址，即 PTE_addr = PDE[vaddr >> 22]
  2. 取得虚拟地址的中间十位（第 21 ~ 12 位），查出物理页物理地址，即 physic_page_addr = PTE[(vaddr & 0x3FF) >> 12]
  3. 取虚拟地址低十二位，算出物理地址，即 physic_addr = physic_page_addr + vaddr & 0xFFF

用同样的方法，我们可以算出两边中表项的值。

PDE 计算

函数 GetPDEPointer(size_t vaddr) 算出虚拟地址 vaddr 在被硬件转换为物理地址时使用的页目录项的地址

#define PDE_IDX(addr) ((addr & 0xFFC00000) >> 22)
size_t* GetPDEPointer(size_t vaddr)
{
    size_t* pde = (size_t *) (0xFFFFF000 + PDE_IDX(vaddr) * 4);
    return pde;
}

建立页表时，我们把虚拟地址 0xFFFFF000 ~ 0xFFFFFFFF 映射到了 0x10000 ~ 0x10100，也就是页目录表上，所以 &PDE[vaddr >> 22] == PDE + (vaddr >> 22) * 4 == 0xFFFFF000 + PDE_IDX(vaddr) * 4，这样就算出了项的地址。

PTE 计算

函数 GetPTEPointer(size_t vaddr) 算出虚拟地址 vaddr 在被硬件转换为物理地址时使用的页表项的地址

#define PTE_IDX(addr) ((addr & 0x003FF000) >> 12)
size_t* GetPTEPointer(size_t vaddr)
{
    size_t* pte = (size_t *) (0xFFC00000 + \
        ((vaddr & 0xFFC00000) >> 10) + \
        PTE_IDX(vaddr) * 4);
    return pte;
}

理解这里的计算，我们要以地址转换硬件的视角来看，pte 变量存储的是虚拟地址，我们希望的是 pte 的虚拟地址被映射到物理地址时，指向的是 vaddr 的 PTE 表项。于是我们来看一下 pte 的虚拟地址是如何被转换的

  1. 硬件首先取高十位来计算出该虚拟地址的 PTE_addr = PDE[vaddr >> 22]，则 PTE_addr = *PDE[0xFFC / 4]，即 PTE_addr 就是 PDE 中最后一项的值，我们在建立页表时，就设置了该值为 &PDE，所以 PTE_addr = &PDE
  2. 然后硬件取得虚拟地址的中间十位（第 21 ~ 12 位），查出物理页物理地址 physic_page_addr = PTE[((vaddr & 0xFFC00000) >> 10)]，由于此处 PTE == PDE，所以 physic_page_addr = PDE[((vaddr & 0xFFC00000) >> 10)]，也就是说，physic_page_addr == PDE_of_vaddr
  3. 最后取虚拟地址低十二位，算出物理地址，即 physic_addr = physic_page_addr + ((addr & 0x003FF000) >> 12) * 4 <=> physic_addr = PDE_of_vaddr[((addr & 0x003FF000) >> 12)]

也就是说，pte 变量转为物理地址后，指向的是 PDE_of_vaddr[((addr & 0x003FF000) >> 12)]，即 PTE_of_vaddr。这样就完成了计算。

映射

映射就是填表，先通过之前提到的两个函数计算出 pde 和 pte 的地址，然后根据 pde 中是否有值分类处理

  • 有值，代表对应的 pte 已分配页，直接填写 pte 即可
  • 无值，代表对应的 pte 未分配页，先申请一个物理页，作为 pte，然后填写 pte。注意申请的物理页需要清零，否则可能会造成未来的判断错误。
static void PageMapping(void* v_addr, void* physic_page_addr)
{
    void* pde_addr = GetPDEPointer(v_addr);
    void* pte_addr = GetPTEPointer(v_addr);
  
    if ((*(size_t*)pde_addr) & PAGE_P_1) /* this PTE is existed */
    {
        /* mapping to the same physic_page */
        ASSERT(!((*(size_t*)pte_addr) & PAGE_P_1));
        if (!((*(size_t*)pte_addr) & PAGE_P_1))
        {
            *(size_t*)pte_addr = ((size_t)physic_page_addr | PAGE_P_1 | PAGE_US_U | PAGE_RW_RW);
        }
        else
        {
            PANIC("MAPPING THE SAME PHYSIC PAGE!!");
            while(1);
        }
    }
    else
    {
        size_t pte_physic_addr = (size_t)(AllocOnePhysicPage(&kernel_memory_pool));
        memset((void*)pte_physic_addr, 0, PAGE_SIZE); /* init the PTE(means nothing mapped) */
        *(size_t*)pde_addr = (pte_physic_addr | PAGE_P_1 | PAGE_US_U | PAGE_RW_RW);
        *(size_t*)pte_addr = ((size_t)physic_page_addr | PAGE_P_1 | PAGE_US_U | PAGE_RW_RW);
    }
}

分配页

当我们能够分配虚拟页和物理页，并且对他们进行映射的时候，就可以进行页分配了

void* palloc(enum pool_flags pf, size_t page_cnt)
{
    ASSERT(page_cnt < 3840);/* must less then 15M */
    void* vaddr_start = GetVirtualPage(pf, page_cnt);
    if (vaddr_start == NULL)
    {
        return vaddr_start;
    }

    struct memory_pool* m_pool = (pf == KERNEL_POOL ? &kernel_memory_pool : &user_memory_pool);
    void* page_physic_addr;
    void* vaddr = vaddr_start;
    while(page_cnt--)
    {
        page_physic_addr = AllocOnePhysicPage(m_pool);
        if (page_physic_addr == NULL)
        {
            /* free all alloced page to system, we will fill there when we finished free-related function */
            return NULL;
        }
        PageMapping(vaddr, page_physic_addr);
        vaddr += PAGE_SIZE;
    }

    return vaddr_start;
}

由于我们给虚拟机预设的内存为 32M，所以这里下小于 3840 页的断言。

分配的方式很容易，先从对应特权级的虚拟地址中分配连续的 page_cnt 各页，然后从物理地址池中一页页地申请物理页，把虚拟地址和物理页地址一一映射即可。这里当然需要考虑物理内存耗尽的情况，处理应该是一页页是否物理内存页，并释放所有的虚拟内存页，但是当前我们还没写 free 相关的函数，所以暂且不做实现。

用一个函数封装 pmalloc，处理内核中页的分配

void* kpalloc(size_t page_cnt)
{
    void* vaddr = palloc(KERNEL_POOL, page_cnt);
    if(vaddr != NULL)
    {
        memset(vaddr, 0, page_cnt * PAGE_SIZE);
    }
    return vaddr;
}

效果

更新 main.c

#include "print.h"
#include "init.h"
#include "debug.h"
#include "memory.h"

int _start()
{
    sys_putstr("this is kernel!\n");
    char a[16];
    InitAll();

    void* addr = kpalloc(5);
    sys_putstr("we got 5 contiguous virtual page, start at: 0x");
    sys_puthex(addr);
    sys_putchar('\n');

    while(1);
    return 0;
}