ucore lab2

练习1：实现 first-fit 连续物理内存分配算法（需要编程）

物理页面的结构体如下：

/* *
 * struct Page - Page descriptor structures. Each Page describes one
 * physical page. In kern/mm/pmm.h, you can find lots of useful functions
 * that convert Page to other data types, such as phyical address.
 * 每一Page结构体描述一个物理页面
 * */
struct Page {
    int ref;                        // page frame's reference counter 该物理页面被引用的次数
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // the num of free block, used in first fit pm manager 连续内存空闲块的大小
    list_entry_t page_link;         // free list link
};

该结构四个成员变量意义如下:

1、ref表示这样页被页表的引用记数，应该就是映射此物理页的虚拟页个数。一旦某页表中有一个页表项设置了虚拟页到这个Page管理的物理页的映射关系，就会把Page的ref加一。反之，若是解除，那就减一。
2、flags表示此物理页的状态标记，有两个标志位，第一个表示是否被保留，如果被保留了则设为1（比如内核代码占用的空间）。第二个表示此页是否是free的。如果设置为1，表示这页是free的，可以被分配；如果设置为0，表示这页已经被分配出去了，不能被再二次分配。
3、property用来记录某连续内存空闲块的大小，这里需要注意的是用到此成员变量的这个Page一定是连续内存块的开始地址（第一页的地址）。
4、page_link是便于把多个连续内存空闲块链接在一起的双向链表指针，连续内存空闲块利用这个页的成员变量page_link来链接比它地址小和大的其他连续内存空闲块

其中链表结点list_entry_t的定义如下：

struct list_entry {
    struct list_entry *prev, *next;
};

typedef struct list_entry list_entry_t;

Page链表有一个表头，负责管理所有的空闲内存块，它位于kern/mm/memlayout.h：

/* free_area_t - maintains a doubly linked list to record free (unused) pages */
typedef struct {
    list_entry_t free_list;         // the list header
    unsigned int nr_free;           // # of free pages in this free list
} free_area_t;

• free_list是一个list_entry结构的双向链表指针
• nr_free则记录当前空闲页的个数

我们第一个实验需要完成的主要是default_pmm.c中的default_init，default_init_memmap，default_alloc_pages， default_free_pages几个函数的修改。

以下为各函数的实现：

/*  In the First Fit algorithm, the allocator keeps a list of free blocks
 * (known as the free list). Once receiving a allocation request for memory,
 * it scans along the list for the first block that is large enough to satisfy
 * the request. If the chosen block is significantly larger than requested, it
 * is usually splitted, and the remainder will be added into the list as
 * another free block.
 *  Please refer to Page 196~198, Section 8.2 of Yan Wei Min's Chinese book
 * "Data Structure -- C programming language".
*/
// LAB2 EXERCISE 1: YOUR CODE
// you should rewrite functions: `default_init`, `default_init_memmap`,
// `default_alloc_pages`, `default_free_pages`.
/*
 * Details of FFMA
 * (1) Preparation:
 *  In order to implement the First-Fit Memory Allocation (FFMA), we should
 * manage the free memory blocks using a list. The struct `free_area_t` is used
 * for the management of free memory blocks.
 *  First, you should get familiar with the struct `list` in list.h. Struct
 * `list` is a simple doubly linked list implementation. You should know how to
 * USE `list_init`, `list_add`(`list_add_after`), `list_add_before`, `list_del`,
 * `list_next`, `list_prev`.
 *  There's a tricky method that is to transform a general `list` struct to a
 * special struct (such as struct `page`), using the following MACROs: `le2page`
 * (in memlayout.h), (and in future labs: `le2vma` (in vmm.h), `le2proc` (in
 * proc.h), etc).
 * 利用宏le2page可以由当前链表结点得到当前的Page结构体
 */
free_area_t free_area;

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)

/*
 * (2) `default_init`:
 *  You can reuse the demo `default_init` function to initialize the `free_list`
 * and set `nr_free` to 0. `free_list` is used to record the free memory blocks.
 * `nr_free` is the total number of the free memory blocks.
 */
static void
default_init(void) {
    list_init(&free_list);  //对链表进行初始化
    nr_free = 0;
}


/*
 *  (3) `default_init_memmap`:  初始化管理空闲内存页的数据结构
 *  CALL GRAPH: `kern_init` --> `pmm_init` --> `page_init` --> `init_memmap` -->
 * `pmm_manager` --> `init_memmap`.
 *  This function is used to initialize a free block (with parameter `addr_base`,
 * `page_number`). In order to initialize a free block, firstly, you should
 * initialize each page (defined in memlayout.h) in this free block. This
 * procedure includes: 该函数用于初始化空闲块。应该对空闲块的每一页进行初始化。应进行如下工作：
 *  - Setting the bit `PG_property` of `p->flags`, which means this page is
 * valid. P.S. In function `pmm_init` (in pmm.c), the bit `PG_reserved` of
 * `p->flags` is already set.
 * 将 flags 标志设置为 PG_property，表明该页可用，需要注意的是 pmm_init 中 PG_reserved 位已经设置过了
 *  - If this page is free and is not the first page of a free block,
 * `p->property` should be set to 0.
 * 如果该页空闲并且不是空闲块的第一页，property属性应设置为0
 *  - If this page is free and is the first page of a free block, `p->property`
 * should be set to be the total number of pages in the block.
 * 如果该页是空闲块的第一页，property属性应该设置为空闲块中的页数
 *  - `p->ref` should be 0, because now `p` is free and has no reference.
 *  After that, We can use `p->page_link` to link this page into `free_list`.
 * (e.g.: `list_add_before(&free_list, &(p->page_link));` )
 * ref应被设置为0，因为这些页面是空闲的，之后我们可以用链表结点将页面连接到free_list中
 *  Finally, we should update the sum of the free memory blocks: `nr_free += n`.
 *  最后更新空闲块的个数
 */
static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(PageReserved(p));//确认本页是否为保留页
        //设置标志位
        p->flags = 0;
        SetPageProperty(p);
        p->property = 0;
        set_page_ref(p, 0);//清空引用
        list_add_before(&free_list, &(p->page_link));//插入空闲页的链表里面
    }
    nr_free += n;  //说明连续有n个空闲块，属于空闲链表
    base->property=n; //连续内存空闲块的大小为n，属于物理页管理链表
}

/*
 *  (4) `default_alloc_pages`:
 *  Search for the first free block (block size >= n) in the free list and reszie
 * the block found, returning the address of this block as the address required by
 * `malloc`.
 *  (4.1)
 *      So you should search the free list like this:
 *          list_entry_t le = &free_list;
 *          while((le=list_next(le)) != &free_list) {
 *          ...
 *      (4.1.1)
 *          In the while loop, get the struct `page` and check if `p->property`
 *      (recording the num of free pages in this block) >= n.
 *              struct Page *p = le2page(le, page_link);
 *              if(p->property >= n){ ...
 *      (4.1.2)
 *          If we find this `p`, it means we've found a free block with its size
 *      >= n, whose first `n` pages can be malloced. Some flag bits of this page
 *      should be set as the following: `PG_reserved = 1`, `PG_property = 0`.
 *      Then, unlink the pages from `free_list`.
 *          (4.1.2.1)
 *              If `p->property > n`, we should re-calculate number of the rest
 *          pages of this free block. (e.g.: `le2page(le,page_link))->property
 *          = p->property - n;`)
 *          (4.1.3)
 *              Re-caluclate `nr_free` (number of the the rest of all free block).
 *          (4.1.4)
 *              return `p`.
 *      (4.2)
 *          If we can not find a free block with its size >=n, then return NULL.
 */
static struct Page *default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {  //如果所有的空闲页的加起来的大小都不够，那直接返回NULL
        return NULL;
    }
    list_entry_t *le, *len;
    le = &free_list;    //从空闲块链表的头指针开始
    while((le=list_next(le)) != &free_list) {//依次往下寻找直到回到头指针处,即已经遍历一次
        struct Page *p = le2page(le, page_link);//将地址转换成页的结构
        if(p->property >= n){ //由于是first-fit，则遇到的第一个大于N的块就选中即可
            int i;
            for(i=0;i<n;i++){//递归把选中的空闲块链表中的每一个页结构初始化
                len = list_next(le);
                struct Page *pp = le2page(le, page_link);
                SetPageReserved(pp);
                ClearPageProperty(pp);
                list_del(le);//从空闲页链表中删除这个双向链表指针
                le = len;
            }
            if(p->property>n){
                (le2page(le,page_link))->property = p->property - n;//如果选中的第一个连续的块大于n，只取其中的大小为n的块
            }
            ClearPageProperty(p);
            SetPageReserved(p);
            nr_free -= n;//当前空闲页的数目减n
            return p;
        }
    }
    return NULL;//没有大于等于n的连续空闲页块，返回空
}


/*
 * (5) `default_free_pages`:
 *  re-link the pages into the free list, and may merge small free blocks into
 * the big ones.
 *  (5.1)
 *      According to the base address of the withdrawed blocks, search the free
 *  list for its correct position (with address from low to high), and insert
 *  the pages. (May use `list_next`, `le2page`, `list_add_before`)
 *  (5.2)
 *      Reset the fields of the pages, such as `p->ref` and `p->flags` (PageProperty)
 *  (5.3)
 *      Try to merge blocks at lower or higher addresses. Notice: This should
 *  change some pages' `p->property` correctly.
 */
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n; // 开头的页面property设置为页面数
    SetPageProperty(base);
    list_entry_t *le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        le = list_next(le);
        //两种需要合并空闲块的情况，先将需要被合并的链表结点取出
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }
    nr_free += n;
    le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        if (base + base->property <= p) {
            assert(base + base->property != p);
            break;
        }
        le = list_next(le);
    }
    // 将空闲页面结点插入到空闲页面链表中
    list_add_before(le, &(base->page_link));
}

static size_t
default_nr_free_pages(void) {
    return nr_free;
}

练习2：实现寻找虚拟地址对应的页表项（需要编程

这里我们需要实现的是get_pte函数，函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。

由于我们已经具有了一个物理内存页管理器default_pmm_manager,我们就可以用它来获得所需的空闲物理页。
在二级页表结构中,页目录表占4KB空间,ucore就可通过default_pmm_manager的default_alloc_pages函数获得一个空闲物理页，这个页的起始物理地址就是页目录表的起始地址。同理，ucore也通过这种方式获得各个页表所需的空间。页表的空间大小取决于页表要管理的物理页数n，一个页表项(32位，即4字节)可管理一个物理页,页表需要占 n/1024 物理页空间(向上取整)。这样页目录表和页表所占的总大小约为 4096+4∗n 字节。
根据LAZY，**这里我们并没有一开始就存在所有的二级页表，而是等到需要的时候再添加对应的二级页表。**当建立从一级页表到二级页表的映射时，需要注意设置控制位。这里应该设置同时设置 上PTE_U、PTE_W 和 PTE_P（定义可在mm/mmu.h）。如果原来就有二级页表，或者新建立了页表，则只需返回对应项的地址即可。
如果 create参数为 0，则get_pte返回NULL;如果 create参数不为 0，则 get_pte 需要申请一个新的物理页。

线性地址的组成：

// A linear address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |     Index      |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
//  \----------- PPN(la) -----------/
//
// The PDX, PTX, PGOFF, and PPN macros decompose linear addresses as shown.
// To construct a linear address la from PDX(la), PTX(la), and PGOFF(la),
// use PGADDR(PDX(la), PTX(la), PGOFF(la)).

一些会用到的宏和函数：

MACROs or Functions:
  PDX(la) = the index of page directory entry of VIRTUAL ADDRESS la. 返回虚拟地址的一级页表索引
  KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address. 返回物理地址pa的虚拟地址
  set_page_ref(page,1) : means the page be referenced by one time 设置page引用次数为1
  page2pa(page): get the physical address of memory which this (struct Page *) page  manages 得到page管理的物理地址
  struct Page * alloc_page() : allocation a page 分配一页
  memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s  to the specified value c.设置s指向的地址前n个字节为c
                                      

get_pte函数的实现如下：

pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {  // get page table entry 寻找线性地址对应的页表项，如果不存在，则分配新物理页面给
    pde_t *pdep = &pgdir[PDX(la)];                              // (1) find page directory entry PDX(la)找到线性地址的一级页表的索引，&pgdir[PDX(la)]得到二级页表表项的指针
    if (!(*pdep & PTE_P)) {                                     // (2) check if entry is not present 检查二级页表的页面是否在内存中
        struct Page *page;  //page将要存的是二级页表
        if (!create || (page = alloc_page()) == NULL) { // (3) check if creating is needed, then alloc page for page table 如果不用分配或分配页面失败
            return NULL;
        }
        set_page_ref(page, 1);                                  // (4) set page reference 设置页面引用次数
        uintptr_t pa = page2pa(page);                           // (5) get linear address of page 得到该物理页面的线性地址
        //注释中给了提示，If you need to visit a physical address, please use KADDR()
        memset(KADDR(pa), 0, PGSIZE);                           // (6) clear page content using memset 初始化该物理页面的内容
        *pdep = pa | PTE_U | PTE_W | PTE_P;                     // (7) set page directory entry's permission 设置可读、可写、存在位
    }
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];      // (8) return page table entry 返回页面的页表项
    //KADDR(PDE_ADDR(*pdep))找到一级页表表项的物理地址，再将物理地址转化为虚拟地址
    //PTX(la)得到虚拟地址la的页表项索引，则KADDR(PDE_ADDR(*pdep)))[PTX(la)]就是页表项
    //最后返回虚拟地址la对应的页表项的地址，该页表项存的是物理页面的地址
}

练习3：释放某虚地址所在的页并取消对应二级页表项的映射（需要编程

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

//page_remove_pte - free a Page struct which is related linear address la 解除物理页面和线性地址la的联系
//                - and clean(invalidate) pte which is related to linear address la 清除和线性地址la相关的页表项
//note: PT is changed, so the TLB need to be invalidate 页表改变了，需要将TLB无效化
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
    /* LAB2 EXERCISE 3: YOUR CODE
     *
     * Please check if ptep is valid, and tlb must be manually updated if mapping is updated
     *
     * Maybe you want help comment, BELOW comments can help you finish the code
     *
     * Some Useful MACROs and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   struct Page *page pte2page(*ptep): get the according page from the value of a ptep
     *   free_page : free a page
     *   page_ref_dec(page) : decrease page->ref. NOTICE: ff page->ref == 0 , then this page should be free.
     *   tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being
     *                        edited are the ones currently in use by the processor.
     * DEFINEs:
     *   PTE_P           0x001                   // page table/directory entry flags bit : Present
     */
    if (*ptep & PTE_P) {    //如果页表项存在
        struct Page *page = pte2page(*ptep);    //找到页表项对应的物理页面
        if (page_ref_dec(page) == 0) {  //如果没有页面引用该物理页面了
            free_page(page);    //释放该页
        }
        *ptep = 0;  //二级页表表项清零
        tlb_invalidate(pgdir, la);  //当修改的页表是进程正在使用的页表，使TLB中对应的项无效
    }
}