实现OS记录:内存管理雏形

0x00

完成了以页为单位的内存管理的雏形，更细致的堆内存管理有待后续实现

0x01 位图

为了用尽可能少的空间标记大量内存的使用情况，需要使用名为位图的数据结构。

所谓位图简单来说就是把每一个比特（bit）和对应资源进行映射和标记（map） 。所以叫 bitmap

如何映射呢？很简单，第几位就是第几号资源。

直接放位图的实现

#ifndef __LIB_KERNEL_BITMAP_H
#define __LIB_KERNEL_BITMAP_H
#include "global.h"
#define BITMAP_MASK 1

struct bitmap{
    uint32_t bytes_len;
    uint8_t* bits;
};

void _init_bitmap(struct bitmap* btmp); // 初始化位图
_Bool _scan_bitmap_test(struct bitmap* btmp, uint32_t bit_offs); // 检测位图某一位
int _scan_bitmap(struct bitmap* btmp, uint32_t cnt); //在位图中申请连续cnt个位，成功则返回其起始位下标，否则返回-1
void _set_bitmap(struct bitmap* btmp, uint32_t bit_offs, _Bool val); //将位图btmp的bit_offs位设置为val

#endif

#include "kernel/bitmap.h"
#include "stdint.h"
#include "string.h"
#include "memfunc.h"
#include "kernel/print.h"
#include "interrupt.h"
#include "debug.h"

void _init_bitmap(struct bitmap* btmp)
{
    memset(btmp->bits, 0, btmp->bytes_len);
}

_Bool _scan_bitmap_test(struct bitmap* btmp, uint32_t bit_offs)
{
    uint32_t byte_idx = bit_offs / 8;
    uint32_t bit_idx = bit_offs % 8;
    return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_idx));
}

int _scan_bitmap(struct bitmap* btmp, uint32_t cnt)
{
    uint32_t byte_idx = 0;                    //记录空闲位所在的字节
    // 逐字节比较, 先找到第一个空闲位
    while((0xff == btmp->bits[byte_idx]) && (byte_idx < btmp->bytes_len))
    {
        byte_idx++;
    }
    ASSERT(byte_idx < btmp->bytes_len);
    if(byte_idx == btmp->bytes_len) return -1; // 无剩余空间返回-1
    // 找到了空闲位所在字节，则在该字节内逐位比对，返回空闲位的索引
    int bit_idx = 0;
    while((uint8_t)(BITMAP_MASK << bit_idx) & btmp->bits[byte_idx])
    { //注意这里&是按位与，所有位都为0才返回0,跳出循环
        bit_idx++;
    }

    int bit_offs = byte_idx * 8 + bit_idx;       //这里就是空闲位在位图中的坐标
    if(cnt == 1) return bit_offs;           //若咱们只申请数量为1

    uint32_t bit_remain = (btmp->bytes_len*8 - bit_offs);     //记录还剩下多少个位
    uint32_t next_bit = bit_offs + 1;
    uint32_t count = 1;               //用来记录找到空闲位的个数

    bit_offs = -1;               //将其置-1,若找不到连续的位就返回
    while(bit_remain-- >0)
    {
        if(!(_scan_bitmap_test(btmp, next_bit)))
        {
            count++;
        }else{
            count = 0;
        }
        if(count == cnt)
        {
            bit_offs = next_bit - cnt + 1 ;
            break;
        }
        next_bit++ ;
    }
    return bit_offs;
}

void _set_bitmap(struct bitmap* btmp, uint32_t bit_offs, _Bool val)
{
     ASSERT((val == 0) || (val == 1));
    uint32_t byte_idx = bit_offs / 8;
    uint32_t bit_odd = bit_offs % 8;
    if(val)
    {                                //value为1
        btmp->bits[byte_idx] |= (BITMAP_MASK << bit_odd);
    }else{                                    //value为0
        btmp->bits[byte_idx] &= ~(BITMAP_MASK << bit_odd);
    }
}

0x02 内存管理

还记得我们的 loader 建立好了整个内核虚拟地址空间的 PDE，但是只建立了最低 1MB 的 PTE，也就是说仅映射了最低 1MB。

我们当然不能仅仅使用这 1MB 内存。并且已经进入了虚拟地址空间，使用的也就是虚拟内存（我粗浅的理解为虚拟地址+物理内存=虚拟内存）。虚拟地址要映射好物理地址也就是有对应的物理内存才有意义，也就可以称为虚拟内存。

要管理好内存，也就需要搞清楚虚拟地址和物理地址，虚拟内存和物理内存。于是定义几个结构。

// 物理内存池结构，生成两个实例用于管理内核内存池和用户内存池
struct _pm_pool{
    struct bitmap pool_bitmap;    //本内存池用到的位图结构，用于管理内存
    uint32_t paddr_start;      //本内存池的物理起始地址
    uint32_t pool_size;
};

// 虚拟内存池结构，生成一个实例用于管理内核虚拟内存
struct _vm_pool{
    struct bitmap pool_bitmap;    //本内存池用到的位图结构，用于管理内存
    uint32_t vaddr_start;      //本内存池的虚拟起始地址
    uint32_t pool_size;
};

如下图

有关原理在开启分页机制时已经说清楚了，不再赘述。

我们需要做到工作

• 初始化内存池

• 在最低 1MB 中放置几个内存池的位图

• 就是实现几个函数，做到虚拟内存中页的申请：先获取可用的虚拟地址，然后申请出物理内存页，然后建立映射关系（也就是填充页表）。

内存池在内核代码中定义，自然处于内核本身所处的最低 1MB 中。但是位图我们没有直接定义（结构中只是指向位图的指针），我们要做的也简单，就是找一块足够长的内存填上去即可。记得在 loader 中我们只建立了最低 1MB 的映射，也就是说其他虚拟地址我们使用是违法的，所以在最低 1MB 中找一个地址。位图 1bit 对应 1 页，那么 0x1000 bytes长度的位图，就可以管理 128 MB 内存。为了支持 4 GB 内存需要留出 0x20 页来放置位图。最低 1MB 的内存剩余还很宽裕，所以不用担心放不下。

而我们需要管理的内核内存起始地址也是最低 1MB 以后，同时再跳过页目录表和已建立的页表本身。

所谓获取可用虚拟地址，其实就是扫描虚拟内存位图，找到可用的位（为0），置1，返回对应的虚拟地址。所谓申请物理内存页，其实也就是扫描物理内存池中的位图，找到可用位，置1，返回对应的物理地址。所谓的建立映射关系就是在获取的虚拟地址对应的页表项填入申请出的物理页地址。

下面是实现

#include "memory.h"
#include "stdint.h"
#include "stdtype.h"
#include "global.h"
#include "debug.h"
#include "string.h"
#include "memfunc.h"
#include "kernel/bitmap.h"
#include "kernel/print.h"

#define PG_SIZE 4096
#define PDE_IDX(addr) ((addr & 0xffc00000) >> 22)       //这里是获取虚拟地址前十位，这里就是PDE的索引值
#define PTE_IDX(addr) ((addr & 0x003ff000) >> 12)       //这里是获取虚拟地址中间十位，这里是PTE的索引值
#define K_HEAP_START 0xc0100000         //设置堆起始地址用来进行动态分配 （跳过内核本身所在的0xc0000000-0xc0100000）
#define MEM_BITMAP_BASE 0xc007e000      //0xc009f000 是内核主线程栈顶，0xc009e000 是内核主线程的 pcb
                                        // 一页长度位图可管理128MB内存，这里兼容32位机最大寻址4GB，使用32页放位图
                                        // 避免麻烦这里要使用0xc0100000以内地址，因为内核空间其他地址还没映射呢
struct _pm_pool user_pm, kernel_pm;
struct _vm_pool kernel_vm;

// 得到虚拟地址vaddr对应的页表项的指针
static uint32_t* pte_ptr(uint32_t vaddr)
{
    //根据loader建立的映射, 0xffc00000对应的是页目录表的第0项
    //用页目录索引乘以页大小（4KB）跳转到第 PDE_IDX(vaddr) 张页表
    //用页表索引乘以4（每个页表项4字节） 找到第 PTE_IDX(vaddr) 个页表项
    uint32_t* pte = (uint32_t*)(0xffc00000 | (PDE_IDX(vaddr) << 12) | (PTE_IDX(vaddr) << 2));
    return pte;
}

// 得到虚拟地址vaddr对应的页目录项的指针
static uint32_t* pde_ptr(uint32_t vaddr)
{
    //根据loader建立的映射, 0xfffff000就是页目录表本身的虚拟地址
    //用页目录索引乘以页目录项大小（4B），找到第 PDE_IDX(vaddr) 个页目录项
    uint32_t* pde = (uint32_t*)(0xfffff000 | (PDE_IDX(vaddr) << 2));
    return pde;
}


// 在对应的虚拟内存池中分配pg_cnt个虚拟页地址，成功则返回虚拟页的起始地址，失败则返回NULL (仅分配地址)
static void* _get_vaddr(_mem_pool_flag pf, uint32_t pg_cnt)
{
    int vaddr_start = 0, bit_idx_start = -1;
    uint32_t cnt = 0;
    if(pf == PF_KERNEL)
    {
        bit_idx_start = _scan_bitmap(&kernel_vm.pool_bitmap, pg_cnt);  //先查找位图看是否有连续的足够大的内存
        if(bit_idx_start == -1) return NULL;
        while(cnt < pg_cnt)
        {
            _set_bitmap(&kernel_vm.pool_bitmap, bit_idx_start + cnt, 1);
            cnt++;
        }
        vaddr_start = kernel_vm.vaddr_start + bit_idx_start * PG_SIZE;
    }else{
        //用户内存池，之后再补充
    }
    return (void*)vaddr_start;
}

// 在m_pool指向的物理内存池中分配1页，成功则返回页的物理地址，失败则返回NULL
static void* _palloc_1_p(struct _pm_pool* m_pool)
{
    int bit_idx = _scan_bitmap(&m_pool->pool_bitmap, 1);   //找一个物理页面
    if(bit_idx == -1) return NULL;
    _set_bitmap(&m_pool->pool_bitmap, bit_idx, 1);         //将对应位置1
    uint32_t page_paddr = ((bit_idx * PG_SIZE) + m_pool->paddr_start);
    return (void*)page_paddr;
}

// 页表中添加虚拟地址_vaddr与物理地址_page_phyaddr的映射
static void _new_page(void* _vaddr, void* _page_paddr)
{
    uint32_t vaddr = (uint32_t)_vaddr, page_paddr = (uint32_t)_page_paddr;
    uint32_t* pde = pde_ptr(vaddr);
    uint32_t* pte = pte_ptr(vaddr);
    // 先在页目录内判断目录项的P位，若为1则表示该表已经存在
    if(*pde & 0x00000001)
    {
        //页目录项和页表项的第0位为p，这里是判断页目录项是否存在
        ASSERT(!(*pte & 0x00000001));   //已经装载的物理页，则报错
        if(!(*pte & 0x00000001))
        {
            *pte = (page_paddr | PG_US_U | PG_RW_W | PG_P_1);
        }else{
            PANIC("pte repeat");
            *pte = (page_paddr | PG_US_U | PG_RW_W | PG_P_1);
        }
    }else{
        //页目录项不存在，所以需要先创建页目录再创建页表项
        uint32_t pde_paddr = (uint32_t)_palloc_1_p(&kernel_pm); //页表本身是一页，这一页从内核内存分配
        *pde = (pde_paddr | PG_US_U | PG_RW_W | PG_P_1);
        // 分配到的物理页地址pde_phyaddr对应的物理内存清0,
        memset((void*)((uint32_t)pte & 0xfffff000), 0, PG_SIZE); // 注意这里要用虚拟地址传参, 所以使用(uint32_t)pte & 0xfffff000
        ASSERT(!(*pte & 0x00000001));
        *pte = (page_paddr | PG_US_U | PG_RW_W | PG_P_1);
    }
}

// 在虚拟内存分配pg_cnt个页，成功则返回起始虚拟地址，失败时则返回NULL
void* _valloc_p(_mem_pool_flag pf, uint32_t pg_cnt)
{
    ASSERT(pg_cnt > 0 && pg_cnt < 32512);
    // 在虚拟内存池中申请连续的虚拟页
    void* vaddr_start = _get_vaddr(pf, pg_cnt);
    if(vaddr_start == NULL) return NULL;
    uint32_t vaddr = (uint32_t)vaddr_start, cnt = pg_cnt;
    struct _pm_pool* mem_pool = (pf == PF_KERNEL) ? &kernel_pm : &user_pm;
    //逐页分配物理内存页并映射
    while(cnt > 0)
    {
        void* page_paddr = _palloc_1_p(mem_pool);
        if(page_paddr == NULL) return NULL;
        _new_page((void*)vaddr, page_paddr);     //映射
        vaddr+=PG_SIZE;         //下一个虚拟页
        cnt--;
    }
    return vaddr_start;
}

// 封装一个分配内核虚拟内存页的函数, 成功返回虚拟地址否则NULL
void* alloc_kernel_pages(uint32_t pg_cnt)
{
    void* vaddr = _valloc_p(PF_KERNEL, pg_cnt);
    if(vaddr != NULL) memset(vaddr, 0, pg_cnt * PG_SIZE); //如果分配的地址不为空，则将页框清0后返回
    return vaddr;
}

static void _init_mem_pool(uint32_t all_mem)
{
    print("mem pool init start\n");
    //目前所有页表使用内存大小 = 页目录表本身1页 + 第0项和第768项页目录项指向的同一个页表占1页 + 第769～1022个页目录项占254页，共256页
    uint32_t page_table_used_mem = PG_SIZE * 256;
    uint32_t used_mem = page_table_used_mem + 0x100000;   //0x100000为低端1MB内存
    uint32_t free_mem = all_mem - used_mem;
    uint32_t all_free_pages = free_mem / PG_SIZE;

    uint32_t kernel_free_pages = all_free_pages / 2; // 内核和用户各占一半
    uint32_t user_free_pages = all_free_pages - kernel_free_pages;
    uint32_t kbm_length = (kernel_free_pages+7) / 8;   // 位图长度（向上取整）
    uint32_t ubm_length = (user_free_pages+7) / 8;

    // 物理内存池地址
    uint32_t kp_start = used_mem;     //kernel pool start 内核物理内存池的物理起始地址
    uint32_t up_start = kp_start + kernel_free_pages * PG_SIZE;   //user pool start 用户物理内存池的物理起始地址
    // 接下来初始化物理内存池
    kernel_pm.paddr_start = kp_start;
    user_pm.paddr_start = up_start;

    kernel_pm.pool_size = kernel_free_pages * PG_SIZE;
    user_pm.pool_size = user_free_pages * PG_SIZE;

    kernel_pm.pool_bitmap.bytes_len = kbm_length;
    user_pm.pool_bitmap.bytes_len = ubm_length;

    kernel_pm.pool_bitmap.bits = (void*)(uint32_t)MEM_BITMAP_BASE;
    user_pm.pool_bitmap.bits = (void*)((uint32_t)MEM_BITMAP_BASE + kbm_length);

    // 输出内存池信息
    print("kernel_pool_bitmap_start:");
    print((uint32_t)kernel_pm.pool_bitmap.bits);
    print("    kernel_pool_phy_addr_start:");
    print((uint32_t)kernel_pm.paddr_start);
    print("\n");
    print("user_pool_bitmap_start:");
    print((uint32_t)user_pm.pool_bitmap.bits);
    print("    user_pool_phy_addr_start:");
    print((uint32_t)user_pm.paddr_start);
    print("\n");

    // 将位图置为0
    _init_bitmap(&kernel_pm.pool_bitmap);
    _init_bitmap(&user_pm.pool_bitmap);

    // 下面初始化内核虚拟内存的位图
    kernel_vm.pool_bitmap.bytes_len = kbm_length;         //用于维护内核堆的虚拟地址，所以要和内核内存池大小一致
    kernel_vm.pool_bitmap.bits = (void*)(MEM_BITMAP_BASE + kbm_length + ubm_length);
    kernel_vm.vaddr_start = K_HEAP_START;
    _init_bitmap(&kernel_vm.pool_bitmap);
    print("     mem_pool_init done \n");
}

void _init_mem(void)
{
    print("mem init start\n");
    uint32_t mem_bytes_total = (*(uint32_t*)(0xc0000c00)); // 在 loader 中记录的内存容量
    print("all memory:");
    print(mem_bytes_total);
    print("\n");
    _init_mem_pool(mem_bytes_total);
    print("mem init done!\n");
}

0x03 验证

main.c

int main(void)
{
   print("kernel made by r3t2\n");
   init();
   void* addr = alloc_kernel_pages(3);
   print("get kernel pages start vaddr is ");
   print((uint32_t)addr);
   while(1);
   return 0;
}

可以看到成功执行。查看一下位图

(qemu) x/10bx 0xc007e000
c007e000: 0x07 0x00 0x00 0x00 0x00 0x00 0x00 0x00
c007e008: 0x00 0x00

查看一下页面是否成功申请并映射

(qemu) info tlb
...
00000000c0000000: 0000000000000000 ---DA--UW
...
00000000c00ff000: 00000000000ff000 -------UW
00000000c0100000: 0000000000200000 ---DA--UW
00000000c0101000: 0000000000201000 ---DA--UW
00000000c0102000: 0000000000202000 ---DA--UW

可以看到 00000000c0100000 到 00000000c0102000 这三页正是我们申请的。