北航操作系统实验Lab2 内存管理

写在前面

实验难点

• 链表的理解，以及相关宏函数的理解和使用

/* Page_list 的结构 */
struct Page_list{ 
    struct{ 
        struct{ 
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
        u_short pp_ref;
    }*lh_first;
};

• 什么时候使用虚拟地址，什么时候使用物理地址(这个很重要)
• 二级页表的自映射

根据页表的起始地址，计算出页目录的起始地址: $PGDIR\text{_}ADDR = PGTABLE\text{_}ADDR + PGTABLE\text{_}ADDR >> 10$

内存地址的划分与映射

在32位的MIPS CPU中，由于地址只能由32位的二进制数表示，同时内存的最小单位是1字节(Byte)，因此其最大寻址的空间为 $2^{32} * 1Byte = 4GB $ 。然而，这4G的空间并不是能直接使用的。提供给CPU的地址并不一定是实际访问物理内存的地址，因此又叫做虚拟地址。虚拟地址按照相应的规则转换之后才能得到真正的地址，即物理地址。这4G的虚拟地址空间，被划分为4个不同的空间。每个空间有自己的转换规则。

• kuseg( 0x0000_0000 ∼ 0x7fff_ffff)(大小为2G)
  这一段是用户模式下可用地址，经过缓存。如果CPU访问了这一段地址，假设这个地址为X，CPU并不会直接访问到物理内存上地址为X的这一段数据，而是要经过MMU的转换。可以形象地认为MMU为一个函数，假设MMU(X)=Y,则实际上CPU访问的是物理地址为Y的内存。
• kseg0( 0x8000_0000 ∼ 0x9fff_ffff )(大小为512M)
  这一段是内核地址，经过缓存。这一段的地址，同样地需要经过转换才能得到真正的物理地址。但是不需要经过复杂的MMU转换，而是直接减去一个偏移 0x80000000。也就是说，会被直接映射到 0x0000_0000~ 0x1fff_ffff 的物理地址上。在实际操作中，直接清空地址二进制的高一位（也就是按位与上 0x7fff_ffff ）即可完成该操作。
• kseg1( 0xa000_0000~ 0xbfff_ffff )（大小为512M）
  这一段地址是内核地址，不经过缓存。与kseg0类似，这一段地址向物理地址转换的方法也同样是清空虚拟地址的高三位即可完成转换。映射到物理地址的低512M区域中。(即，按位与上 0x1fff_ffff )这一段内存不经过缓存，所以适合用来映射到硬件的I/O寄存器中，以避免缓存带来的一致性问题。但是如果用于其他用途，则会因为没有缓存导致速度较慢
• kseg2( 0xc0000000~ 0xffffffff )(大小为1G)
  这一段地址是内核地址，经过缓存。且需要通过MMU进行转换。

相关代码阅读

熟练掌握相关宏对写代码非常有帮助

queue.h

定义了一系列的宏函数来简化对链表的操作。

mmu.h

pmap.h

每一个物理页面的信息都有一个Page类型的结构体表示着。pages数组就是用于表示所有物理内存页的信息，数组中的每一项都对应着一个物理页面，$pages[i]$ 对应第 $i$ 个物理页面(线性映射), 而每个物理页的大小为4KB，所以pages[i]对应的物理页的实际物理地址就是 $i << (12) $ .

static inline u_long page2pa(struct Page *pp){    
    return page2ppn(pp) << PGSHIFT;
}

实验中要注意的一些细节我都会写在代码的注释里。 同时我会尽量把自己对实验的理解写清楚。

Exercise 2.1

完善链表的一些插入操作。主要是 LIST_INSERT_TAIL 函数, 很明显我们要遍历到链表结尾，然后插入elm， 利用elm 的le_next指针来当作变量来遍历整个链表。

#define LIST_INSERT_TAIL(head, elm, field) do {                 \
                if(LIST_FIRST( (head) ) == NULL )               \ 
                        LIST_INSERT_HEAD( (head), (elm), field );     \
                else {  \
                        LIST_NEXT((elm), field) = LIST_FIRST( (head) );         \
                        while( LIST_NEXT(LIST_NEXT((elm), field ), field) != NULL )                \ 
                                LIST_NEXT((elm), field ) = LIST_NEXT(LIST_NEXT((elm), field ), field) ;     \
                        LIST_NEXT(LIST_NEXT(elm,field),field) = (elm);           \
                        (elm)->field.le_prev = &(LIST_NEXT(LIST_NEXT(elm,field),field));                        \
                        LIST_NEXT(elm,field) = NULL;            \
                        /*直接使用下面这个不对。我感觉应该是宏展开的问题,每个listelm会被替换LIST_NEXT(elm,field))。  \
                         *而elm的next会先被修改，再次使用listelm，即LIST_NEXT(elm,field)的时候就会出错，因为elm的next已被修改   \
                         LIST_INSERT_AFTER((LIST_NEXT(elm,field)), (elm), field);        \
                         */             \
                        
                }                    \
        } while(0)

Exercise 2.2

mips_init() 会对操作系统初始化。它会一次调用 mips_detect_memory(), mips_vm_init() 和 page_init()

首先就是要确定可用内存的大小。(物理内存为64MB)

void mips_detect_memory()
{
    maxpa = 1 << 26; // [,maxpa)
    /* Step 1: Initialize basemem.
     * (When use real computer, CMOS tells us how many kilobytes there are). */
    basemem = 1 << 26;
    // Step 2: Calculate corresponding npage value.
    npage = basemem >> PGSHIFT; // basemem >> 12
    extmem = 0;
}

关于alloc函数

在操作系统刚刚启动时，我们还没有建立起有效的数据结构来管理所有的物理内存，因此，出于最基本的内存管理的需求，我们需要实现一个函数来分配指定字节的物理内存。这一功能由mm/pmap.c中的alloc函数来实现。alloc函数能够按照参数align进行对齐，然后分配n字节大小的物理内存，并根据参数clear的设定决定是否将新分配的内存全部清零，并最终返回新分配的内存的首地址。

alloc函数中有个extern char end[]; end[]的地址就是0x8040 0000(虚拟地址)，在tools/scse0_3.lds处进行了定义。 freemem（全局变量) 会从end所在地址开始分配物理内存

alloc函数中还调用了bzero函数来将分配的物理内存上的值清零。这里值得注意的是该函数使用的是虚拟地址

关于mips_vm_init()函数

有了分配物理内存的功能后，接下来我们需要给操作系统内核必须的数据结构–页目录（pgdir）、内存控制块数组（pages）和进程控制块数组（envs）分配所需的物理内存。mips_vm_init()函数实现了这一功能，并且完成了相关的虚拟内存与物理内存之间的映射( boot_map_segment() 函数)。 pgdir 申请了4KB空间, pages申请了192KB空间。

Exercise 2.3

完成 page_init函数，使用include/queue.h中定义的宏函数将未分配的物理页加入到空闲链表page_free_list中去。

怎样区分物理页面有没有被使用过呢。还记得之前的mips_vm_init()调用了alloc函数吗？freemem(这是个虚拟地址)地址以下的部分都已经使用过了，即这个虚拟地址以下对应的物理页已经使用pages数组代表着这些实际物理页，因此对应着要修改page数组。

void page_init(void)
{
    /* Step 1: Initialize page_free_list. */
    /* Hint: Use macro `LIST_INIT` defined in include/queue.h. */
    LIST_INIT( (&page_free_list) );

    /* Step 2: Align `freemem` up to multiple of BY2PG. */
    freemem = ROUND(freemem, BY2PG );

    /* Step 3: Mark all memory blow `freemem` as used(set `pp_ref`
     * filed to 1) */
    /* freemem(这是个虚拟地址)地址以下的部分都已经使用过了，即这个虚拟地址以下对应的物理页已经使用
     * pages数组管理着这些实际物理页，因此对应着要修改page数组
     */
    
    int size = PADDR(freemem) / BY2PG;
    int i ;
    for(i = 0; i < size ; ++ i ) {
        pages[i].pp_ref = 1;
    }
    /* Step 4: Mark the other memory as free. */
    for(; i < npage ; ++ i) {
        pages[i].pp_ref = 0;
        LIST_INSERT_HEAD((&page_free_list), ( pages + i ), pp_link);
    }
}

Exercise 2.4

有了记录物理内存使用情况的链表之后，我们就可以不再像之前的alloc函数那样按字节为单位进行内存的分配，而是可以以页为单位进行物理内存的分配与释放。page_alloc函数用来从空闲链表中分配一页物理内存，而page_free函数则用于将一页之前分配的内存重新加入到空闲链表中。

page_alloc只是是拿到一个物理页，并没有建立物理页和虚拟地址的映射关系。

值得注意的地方是bzero使用的是虚拟地址。这两个函数中，均不会改变页表的引用次数。

int page_alloc(struct Page **pp)
{
    struct Page *ppage_temp;

    /* Step 1: Get a page from free memory. If fails, return the error code.*/
    if( LIST_EMPTY((&page_free_list)) ) return -E_NO_MEM;
    ppage_temp = LIST_FIRST((&page_free_list)) ;
    /* Step 2: Initialize this page.
     * Hint: use `bzero`. */
    // ppage_temp -> pp_ref = 1;
    /*注意：bzero使用的是虚拟地址*/
    bzero((void *)page2kva(ppage_temp), BY2PG);
    *pp = ppage_temp;//不能用 pp = &ppage_temp
    LIST_REMOVE((ppage_temp), pp_link);
    return 0;

}

void page_free(struct Page *pp)
{
    /* Step 1: If there's still virtual address refers to this page, do nothing. */
    if(pp -> pp_ref > 0) return ;
    /* Step 2: If the `pp_ref` reaches to 0, mark this page as free and return. */
    if(pp -> pp_ref == 0) { 
        LIST_INSERT_HEAD((&page_free_list), (pp), pp_link);
        return ;
    }
    /* If the value of `pp_ref` less than 0, some error must occurred before,
     * so PANIC !!! */
    panic("cgh:pp->pp_ref is less than zero\n");
}

至此，我们的内核已经能够按照分页的方式对物理内存进行管理

我们通过建立两级页表来进行虚拟内存的管理，在此基础上，我们将实现根据虚拟地址在页表中查找对应的物理地址，以及将一段虚存地址映射到一段的物理地址的功能，然后实现虚存的管理与释放，最后为内核建立起一套虚存管理系统。

Exercise 2.5

先说明一下页目录项，页表项的结构。每项占4B，共32位。前20位存储的是物理页号, 后12位是一些权限位。

PTE_ADDR(pte)函数就是得到页表项pte上的物理地址的。我们取出前20位能得到物理页号，在左移12位就能得到物理地址。因此将低12位清零就是物理地址。

boot_pgdir_walk和pgdir_walk两个函数来实现地址转换和页表的创建，这两个函数的区别仅仅在于当虚存地址所对应的页表的页面不存在的时候，分配策略的不同和使用的内存分配函数的不同。

注意：boot_pgdir_walk调用时，pages数组尚未初始化，因此boot_pgdir_walk不修改引用计数。

• 一定要记住，需要访问某一片内存时，要通过虚拟地址去访问
• 页表中填写的内容，是物理地址与上标志位
• 新建一页时，记得把标志位设置为有效

static Pte *boot_pgdir_walk(Pde *pgdir, u_long va, int create)
{

    Pde *pgdir_entryp;
    Pte *pgtable, *pgtable_entry;

    /* Step 1: Get the corresponding page directory entry and page table. */
    /* Hint: Use KADDR and PTE_ADDR to get the page table from page directory
     * entry value. */
    pgdir_entryp = pgdir + PDX(va) ; // 页目录项
    pgtable = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp)); //先取出页目录项上的物理地址，然后要再转化为虚拟地址
    /* Step 2: If the corresponding page table is not exist and parameter `create`
     * is set, create one. And set the correct permission bits for this new page
     * table. */
    
    /* 要用 PTE_V 标志位判断页表是否存在, 注意看页表是否存在是看页目录项的标志位 */
    if( !((*pgdir_entryp) & PTE_V) ) {
        if(create == 1) {
            pgtable = (Pte *)alloc(BY2PG, BY2PG, 1);// 这里要申请一个物理页，这里得到的也是虚拟地址
            (*pgdir_entryp) &= 0xFFF;//高20位清零,低12位其他属性保持不变
            (*pgdir_entryp) |= PADDR((u_long)pgtable);
            (*pgdir_entryp) |= PTE_V; // 设置权限位
        }else{
            return NULL; //失败了
        }
    }
    /* Step 3: Get the page table entry for `va`, and return it. */
    return pgtable_entry = pgtable + PTX(va);//返回页表项

}

int
pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte)
{
    Pde *pgdir_entryp;
    Pte *pgtable;
    struct Page *ppage;

    /* Step 1: Get the corresponding page directory entry and page table. */
    pgdir_entryp = pgdir + PDX(va);
    pgtable = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp));//要转化为虚拟地址才能连续访问
    /* Step 2: If the corresponding page table is not exist(valid) and parameter `create`
     * is set, create one. And set the correct permission bits for this new page
     * table.
     * When creating new page table, maybe out of memory. */
    if( !((*pgdir_entryp) & PTE_V)) {
        if(create == 1) {
            if(page_alloc(&ppage) == -E_NO_MEM) { 
                *ppte = NULL;
                return -E_NO_MEM;
            }
            ppage -> pp_ref ++; //增加引用次数
            /*ppage 是一个struct Page类型指针，并不代表一个具体页面地址*/
            pgtable = (Pte *)page2pa(ppage); // 把page转化为物理地址
            (*pgdir_entryp) &= 0xFFF;
            (*pgdir_entryp) |= (Pte)pgtable;
            (*pgdir_entryp) |= PTE_V;
            pgtable = (Pte *)KADDR((u_long)pgtable); //还要转化为虚拟地址 
        }else{
            *ppte = NULL;//失败需要把指针设为NULL
            return -E_NO_MEM;
        }
    }

    /* Step 3: Set the page table entry to `*ppte` as return value. */
    *ppte = pgtable + PTX(va); //得到页表项
    return 0;
}

Exercise 2.6

仅建立一个空的页表是没有帮组的。 我们需要在具体的物理内存与虚拟地址间建立映射，即将相应的物理页面地址填入对应虚拟地址的页表项中。

boot_map_segment函数，实现将指定的物理内存与虚拟内存建立起映射的功能。其作用是在pgdir对应的页表上，把[va,va+size)这一部分的虚拟地址空间映射到[pa,pa+size)这一部分空间。

提示： boot_map_segment函数是在boot阶段执行的，使用boot_pgdir_walk寻找页表项

if(size % BY2PG != 0) return ;

    for(i = 0; i < size; i += BY2PG) {
        pgtable_entry = boot_pgdir_walk(pgdir, va + i, 1); //得到一个页表项指针
        *pgtable_entry = pa + i; //设置物理地址
        (*pgtable_entry) |= perm|PTE_V;//设置权限位
    }

Exercise 2.7

我们已经完成了系统启动时候的内存映射，页表建立等工作。现在我们需要完成一个函数以方便其他程序进行内存映射。从现在开始，我们终于不用手动分配内存了，而是采用页式内存管理系统。

tlb_invalidate 这个函数它的作用是使得某一虚拟地址对应的tlb表项失效。从而下次访问这个地址的时候诱发tlb重填，以保证数据更新。

这个函数就是把虚拟地址和物理地址映射起来的，好让虚拟地址映射到我们刚才分配的物理页框上，再具体点，就是把对应的页表项填上。大致流程如下

• 先纯查找页表入口（create = 0, 即二级页表缺失的时候不新建）

• 如果发现对应的页表项已经映射了一个物理页：

  • 如果这一个物理页是我们需要插入的，更新tlb，修改物理页号和标志位。函数直接返回。
  • 如果这个物理页是其他的页，则先去除这一页。
• 更新tlb
• 以创建模式(create = 1)查找页表入口，如果查找错误，则返回错误代码
• 把待插入的物理页的物理地址，以及标志位给填入页表项中。同时增加页表引用计数

int
page_insert(Pde *pgdir, struct Page *pp, u_long va, u_int perm)
{
    u_int PERM;
    Pte *pgtable_entry;
    PERM = perm | PTE_V;

    /* Step 1: Get corresponding page table entry. */
    /*首先要找到虚拟地址va对应的页表项指针pgtable_entry*/
    pgdir_walk(pgdir, va, 0, &pgtable_entry);

    if (pgtable_entry != 0 && (*pgtable_entry & PTE_V) != 0) {
        if (pa2page(*pgtable_entry) != pp) {
            page_remove(pgdir, va); //里面已经包含tlb_invalidate(pgdir, va);
        } else    {
            tlb_invalidate(pgdir, va); //更新tlb
            *pgtable_entry = (page2pa(pp) | PERM); //设置页表项，修改物理页号和标志位
            return 0;
        }
    }

    /* Step 2: Update TLB. */
    
    /* hint: use tlb_invalidate function */
    tlb_invalidate(pgdir, va); //更新tlb

    /* Step 3: Do check, re-get page table entry to validate the insertion. */
    
    /* Step 3.1 Check if the page can be insert, if can’t return -E_NO_MEM */
    if(pgdir_walk(pgdir,va,1,&pgtable_entry) == -E_NO_MEM) return -E_NO_MEM; // 以创建模式得到页表项
    
    /* Step 3.2 Insert page and increment the pp_ref */
    (*pgtable_entry) = (page2pa(pp) | PERM); //设置页表项，增加物理页号和标志位
    pp -> pp_ref ++ ;
    return 0;
}

Exercise 2.8

tlb_invalidate 这个函数是由tlb_out汇编函数组成的。

tlbp: 搜索虚拟页号及ASID跟当前EntryHi中的值相匹配的TLB项，并把该项的索引保存到Index寄存器。若没有找到匹配则Index寄存器的第31位置位一(是个负值)，因而易于检测。

tlbwi : tlbwi把ENTRYHI 和ENTRYLO0写入Index所指的项

LEAF(tlb_out)
//1: j 1b
nop
    mfc0    k1,CP0_ENTRYHI
    mtc0    a0,CP0_ENTRYHI
    nop
    tlbp
    nop
    nop
    nop
    nop
    mfc0    k0,CP0_INDEX
    bltz    k0,NOFOUND
    nop
    mtc0    zero,CP0_ENTRYHI
    mtc0    zero,CP0_ENTRYLO0
    nop
    tlbwi
NOFOUND:

    mtc0    k1,CP0_ENTRYHI
    
    j    ra
    nop
END(tlb_out)