lab2实验报告

思考题

Thinking 2.1

题面

1
请根据上述说明，回答问题：在编写的 C 程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址，还是物理地址？

回答

答：C程序中指针变量中存储的地址被视为虚拟地址。MIPS汇编程序中lw和sw指令使用的地址被视为虚拟地址。

Thinking 2.2

题面

1
2
3
请思考下述两个问题：
• 从可重用性的角度，阐述用宏来实现链表的好处。
• 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。

回答

  1. 采用宏定义对链表相关操作进行封装，使得相关操作可复用，减少了每次使用重新再书写的工作量，同时还减小了复杂度，使代码可读性更好，便于维护。
  2. 先查看/usr/include/sys/queue.h中单向链表和循环链表的实现：
    三者在插入与删除操作上有一定的性能差别：
    1). 对于单向链表，由于所有节点都只维护了一个指向下一个节点的指针，因此在删除时需要遍历链表找到删除节点的前一个节点，同样的，在给定节点前插入也需要遍历链表得到前一个节点。但是在给定节点后插入则不需要经过遍历，直接插入即可。
    2). 对于循环链表，其中头结点head维护指向循环链表的头尾指针(cqh_first和cqh_last)，而头尾节点分别通过cqe_prev和cqe_next指针指向head节点再通过相应的指针，完成对于对方的访问(头对尾，尾对头)。因此删除、在一个节点前插入和在一个节点后插入都相对单向链表容易，跟我们实现的双向链表有异曲同工之妙，但是与双向链表不同的是删除和插入操作需要特判头尾节点的情况，也是head起到连接头尾节点的作用导致的。

    3). 对于双向链表，除了维护指向第一个节点指针的head节点，其余节点都维护一个指向下一个节点的指针和指向上一个节点的指向下一个节点的指针的指针，这样一来删除和在节点后插入时只需要特判是否是最后一个节点即可，而在节点前插入时则需要判断是否是第一个节点(head外的)，删除和插入的效率与循环链表基本一致。

Thinking 2.3

题面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
请阅读 include/queue.h 以及 include/pmap.h, 将 Page_list 的结构梳理清楚，选择正确的展开结构。
A:
struct Page_list {
        struct {
                struct {
                        struct Page * le_next;
                        struct Page * le_prev;
                } pp_link;
                u_short p_ref;
        } * lh_first;
}

B:
struct Page_list {
        struct {
                struct {
                        struct Page * le_next;
                        struct Page ** le_prev;
                } pp_link;
                u_short p_ref;
        } lh_first;
}

C:
struct Page_list {
        struct {
                struct {
                        struct Page * le_next;
                        struct Page ** le_prev;
                } pp_link;
                u_short p_ref;
        } * lh_first;
}

回答

选择C。
首先在include/pmap.h中有:

1
2
3
4
5
6
7
8
9
10
11
12
13
LIST_HEAD(Page_list, Page);
typedef LIST_ENTRY(Page) Page_LIST_entry_t;

struct Page {
        Page_LIST_entry_t pp_link; /* free list link */

        // Ref is the count of pointers (usually in page table entries)
        // to this page.  This only holds for pages allocated using
        // page_alloc.  Pages allocated at boot time using pmap.c's "alloc"
        // do not have valid reference count fields.

        u_short pp_ref;
};

其中LIST_HEAD()和LIST_ENTRY()是queue.h中的宏:

1
2
3
4
5
6
7
8
9
10
#define LIST_HEAD(name, type)                                                                      \
        struct name {                                                                              \
                struct type *lh_first; /* first element */                                         \
        }

#define LIST_ENTRY(type)                                                                           \
struct {                                                                                   \
        struct type *le_next;  /* next element */                                          \
        struct type **le_prev; /* address of previous next element */                      \
}

全部拼接起来就是C:

1
2
3
4
5
6
7
8
9
struct Page_list {
        struct {
                struct {
                        struct Page * le_next;
                        struct Page ** le_prev;
                } pp_link;
                u_short p_ref;
        } * lh_first;
}

Thinking 2.4

题面

1
2
3
请思考下面两个问题：
• 请阅读上面有关 TLB 的描述，从虚拟内存和多进程操作系统的实现角度，阐述 ASID的必要性。
• 请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’sManual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc 中可容纳不同的地址空间的最大数量。

回答

  1. 多进程操作系统中，对于不同的进程，操作系统都会分配一个页表，而每个页表都有自己的虚拟空间，因此同一虚拟地址由于在不同虚拟空间的缘故通常会映射到不同的物理地址上，假若没有ASID来标识当前虚拟地址是在哪个虚拟空间中，很有可能会将该虚拟地址映射到错误的物理地址上去。

  2. 由于EntryHi寄存器的ASID段有8位，因此，4Kc中可容纳不同的地址空间的最大数量为256个。

Thinking 2.5

题面

1
2
3
4
请回答下述三个问题：
• tlb_invalidate 和 tlb_out 的调用关系？
• 请用一句话概括 tlb_invalidate 的作用。
• 逐行解释 tlb_out 中的汇编代码。

回答

  1. tlb_invalidate函数如下： 
    1
    2
    3
    void tlb_invalidate(u_int asid, u_long va) {
          tlb_out((va & ~GENMASK(PGSHIFT, 0)) | (asid & (NASID - 1)));
          }
    其中在该函数中通过传递参数的形式调用了tlb_out函数。
  2. 在页表内容发生改变后及时更新TLB。
  3. tlb_out函数代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    LEAF(tlb_out) #函数开头声明
    .set noreorder #设定手动设置延迟槽模式
            mfc0    t0, CP0_ENTRYHI #将原有的EntryHi中的值读取到t0寄存器中
            mtc0    a0, CP0_ENTRYHI #将传入的原有的旧表项的Key传入EntryHi寄存器中
            nop #手动延迟
            /* Step 1: Use 'tlbp' to probe TLB entry */
            /* Exercise 2.8: Your code here. (1/2) */
            tlbp #依据旧表项的Key查找TLB将表项索引写入Index寄存器中(未找到则最高位置1，相当于将Index置负)
            nop #手动延迟
            /* Step 2: Fetch the probe result from CP0.Index */
            mfc0    t1, CP0_INDEX #获取旧表项的索引
    .set reorder #设定编译器自动延迟模式
            bltz    t1, NO_SUCH_ENTRY #判断索引是否为负，为负就跳到未找到标签，否则继续下列操作
    .set noreorder #设定手动延迟模式
            mtc0    zero, CP0_ENTRYHI 
            mtc0    zero, CP0_ENTRYLO0
            mtc0    zero, CP0_ENTRYLO1 #将EntryHi、EntryLo0、EntryLo1赋值为0
            nop
            /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
            /* Exercise 2.8: Your code here. (2/2) */
            tlbwi #使用tlbwi指令以Index中值为索引，将上述EntryHi、EntryLo0和EntryLo1写入TLB对应页表项中
    .set reorder #设定自动延迟模式
       
    NO_SUCH_ENTRY: #未找到标签
            mtc0    t0, CP0_ENTRYHI #复原EntryHi原有的值
            j       ra #返回函数
    END(tlb_out)  #函数结束符
    tlb_out函数的主要流程就是先根据传给a0寄存器的参数查找对应的旧表项，表项索引赋给Index寄存器，然后再根据Index寄存器中的索引值进行相应的操作，如果找到了(索引大于等于0)，就通过tlbwi指令将相应索引对应的表项的TLB的Key和Data置0；否则，就先把原有的EntryHi赋给其再退出。

Thinking 2.6

题面

1
请结合 Lab2 开始的 CPU 访存流程与下图中的 Lab2 用户函数部分，尝试将函数调用与 CPU 访存流程对应起来，思考函数调用与 CPU 访存流程的关系。

回答

用户进程运行过程中，访存指令会触发CPU访存，如果查询目标页面在TLB中，则能够正常完成访存；否则，会触发TLB Miss，将跳转到异常处理程序，该程序通过调用tlb_invalidate()函数使TLB对应的旧表项无效，并且通过do_tlb_refill()函数重填TLB，其中do_tlb_refill()函数调用了_do_tlb_refill()函数，后者是重填的效果的主要执行者，其调用了page_lookup()函数寻找对应的页表项，并在找不到或者找到的无效的情况下通过调用passive_alloc()函数其中的page_alloc()函数和page_insert()函数分配新的页面，并且建立好虚实地址间的映射关系。最后回写TLB，重新进行访存，完成CPU访存。
因此，多个函数调用组成了一个完整的CPU访存。

Thinking 2.7

题面

1
2
3
4
从下述三个问题中任选其一回答：
• 简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。
• 简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上的区别。
• 简单了解并叙述 LoongArch 中的内存管理机制，比较 LoongArch 与 MIPS 在内存管理上的区别。

回答

我选择X86与MIPS的比较。
X86体系结构中的内存管理机制：

  • 虚拟地址，同实验所用机制类似，为每个进程分配独立的虚拟地址空间，通过MMU进行虚地址向实地址的转换。
  • 分页和分段，前者同实验所用机制基本一致，不过X86一般采用多级页表结构；而后者通过用来提供一种保护机制，限制程序访问内存的范围。
  • 内存保护，提供内存保护机制，防止不同进程间的相互访问以及访问越界。
    与MIPS的区别：
  • MIPS页表结构更为简答，X86为多级页表结构。
  • MIPS通常不采用分段机制。
  • 虚拟内存实现上，具体细节可能不同，比如替换算法的选择。
  • 内存保护上，实现方式不一定一致，比如X86的特权级数量更多，提供更细致的权限控制。

lab2课下

Exercise 2.1

题面

1
2
请参考代码注释，补全 mips_detect_memory 函数。
在实验中，指定了硬件可用内存大小 memsize，请你用内存大小 memsize 完成总物理页数 npage 的初始化。

回答

根据网站给出的测试点可以推断出其值与memsize的KB值呈差3倍的关系，也就是推断出来每一页占4KB，但是这是为什么呢？貌似在到该页之前指导书并没有明确指出，一页是多少B？(莫名其妙的题目)
解密了阅读到后面的mips_vm_init()函数中有用到一个名为PAGE_SIZE，几经查找，终于在./include/mmu.h中找到了其定义，正如其名就是一页的大小(以字节为单位，4096B)，因此这里直接用内存大小去除以PAGE_SIZE就行，虽然但是此前的指导书一点未提及，我怎么会知道有一个PAGE_SIZE的宏已经被定义了。

Exercise 2.2

题面

1
2
完成 include/queue.h 中空缺的函数 LIST_INSERT_AFTER。
其功能是将一个元素插入到已有元素之后，可以仿照 LIST_INSERT_BEFORE函数来实现。

回答

先来看看LIST_INSERT_BEFORE函数：

1
2
3
4
5
6
7
#define LIST_INSERT_BEFORE(listelm, elm, field)                                                    \
do {                                                                                       \
        (elm)->field.le_prev = (listelm)->field.le_prev;                                   \
        LIST_NEXT((elm), field) = (listelm);                                               \
        *(listelm)->field.le_prev = (elm);                                                 \
        (listelm)->field.le_prev = &LIST_NEXT((elm), field);                               \
} while (0)

关于这里为什么使用do{...}while(),我认为这里是因为宏定义的缘故，为了只让其中的四行代码只运行一次使用do...while是再合适不过了。
一行一行分析，第一行将elm的le_prev与listelm保持一致；第二行将elm的le_next指向listelm；第三行将原有链表中listelm上游的节点的le_next(通过对listelm的le_prev解引用获得)指向elm；第四行将listelm的le_prev指向elm的le_next，完成插入。

因此LIST_INSERT_AFTER()只需依葫芦画瓢即可，不过需要注意的是与前插不同的是，后插的节点很有可能是最后一个，这是需要特殊考虑一下的。

Exercise 2.3

题面

1
2
3
4
5
6
7
完成 page_init 函数。
请按照函数中的注释提示，完成上述操作。此外，这里也给出一些提示：
1. 使用链表初始化宏 LIST_INIT。
2. 将 freemem 按照 PAGE_SIZE 进行对齐（使用 ROUND 宏为 freemem 赋值）。
3. 将 freemem 以下页面对应的页控制块中的 pp_ref 标为 1。
4. 将其它页面对应的页控制块中的 pp_ref 标为 0 并使用 LIST_INSERT_HEAD 将
其插入空闲链表。

回答

根据提示，第一、二步依葫芦画瓢的使用宏定义即可，主要是第三、四步，其中在pmap.c中定义了struct Page * pages、u_long npage和u_long freemem等全局变量，其中pages通过alloc()函数已经分配了相应的内存空间，作为每页的页控制块，其部分页面已被分配出去，也就是到freemem对齐后对应的页面之前的页(不包括其对应的页)，通过PADDR(freemem) / npage即可得到相应的未分配的起始页号，这里的页号实际上是页框号也就是物理实际的内存，因此需要将freemem转换成实地址后再除去页大小才可获得页号，则只需通过循环即可将此前的页面的页控制块的pp_ref和此后的分别置1和置0，主要是如何将未分配的页面的页控制块利用LIST_INSERT_HEAD加入到空闲链表中令人犯难，主要是该宏内部又使用了许多宏，导致过多的宏定义令人眼花缭乱，这里拽出相关的宏：

1
2
3
4
5
6
7
8
9
10
#define LIST_FIRST(head) ((head)->lh_first)
#define LIST_INSERT_HEAD(head, elm, field)                                                         \
        do {                                                                                       \
                if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)                        \
                        LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);              \
                LIST_FIRST((head)) = (elm);                                                        \
                (elm)->field.le_prev = &LIST_FIRST((head));                                        \
        } while (0)

#define LIST_NEXT(elm, field) ((elm)->field.le_next)

仔细阅读可以发现，LIST_INSERT_HEAD()的参数中head会进行LIST_FIRST()的宏操作，因此其应该是一个指向拥有lh_first域的头结点的指针，而elm参数会进行LIST_NEXT()操作，因此其应该是一个指向拥有一个拥有le_prev和le_next域的field域的普通节点的指针，回看Thinking 2.3发现，Page_list、Page和pp_link分别符合这三个参数的要求，因此，此处的对于该宏的使用要注意前两个空一定要是Page_list *和Page *类型的指针。

Exercise 2.4

题面

1
2
3
4
完成 page_alloc 函数。
在 page_init 函数运行完毕后，在 MOS 中如果想申请存储空间，都需要通过这个函数来申请分配。该函数的逻辑简单来说，可以表述为：
1. 如果空闲链表没有可用页，返回异常返回值。
2. 如果空闲链表有可用的页，取出链表头部的一页；初始化后，将该页对应的页控制块的地址放到调用者指定的地方。填空时，你可能需要使用链表宏`LIST_EMPTY`与函数`page2kva`。

回答

page2kva函数定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static inline u_long page2ppn(struct Page *pp) {
        return pp - pages;
}

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

static inline struct Page *pa2page(u_long pa) {
        if (PPN(pa) >= npage) {
                panic("pa2page called with invalid pa: %x", pa);
        }
        return &pages[PPN(pa)];
}

static inline u_long page2kva(struct Page *pp) {
        return KADDR(page2pa(pp));
}

#define KADDR(pa)                                                                                  \
        ({                                                                                         \
                u_long _ppn = PPN(pa);                                                             \
                if (_ppn >= npage) {                                                               \
                        panic("KADDR called with invalid pa %08lx", (u_long)pa);                   \
                }                                                                                  \
                (pa) + ULIM;                                                                       \
        })

#define PPN(pa) (((u_long)(pa)) >> PGSHIFT)

#define ULIM 0x80000000

第一步先通过LIST_EMPTY()来判断空闲链表是否为空。然后若不为空，再通过LIST_FIRST()将空闲链表的第一个空闲页控制块赋值给pp，运用LIST_REMOVE()将其从空闲链表中删去，为了使用memset()将pp对应的页的所有内存置0，观察到在alloc()函数中有使用memset()初始化分配的页面，其中三个参数分别为(void *)alloced_mem、0和n(npage * sizeof(struct Page))，其中(void *)alloced_mem是指向初始分配内存的地址，0代表写入的值，而n则代表了总共要写入的空间大小(字节数)，因此依葫芦画瓢，此处只需要通过page2kva()函数获得相应的分配地址，写入0到sizeof(struct Page)空间即可。

Exercise 2.5

题面

1
2
完成 page_free 函数。
提示：使用链表宏 LIST_INSERT_HEAD，将页结构体插入空闲页结构体链表。

回答

注意：LIST_INSERT_HEAD()的参数为head、elm和field。

Exercise 2.6

题面

1
2
3
4
5
6
完成 pgdir_walk 函数。
该函数的作用是：给定一个虚拟地址，在给定的页目录中查找这个虚拟地址对应的页表项，将其地址写入 *ppte。
• 如果这一虚拟地址对应的二级页表存在，则设置 *ppte 为这一页表项的地址；
• 如果这一虚拟地址对应的二级页表不存在（即这一虚拟地址对应的页目录项无效），
则当 create 不为 0 时先创建二级页表再查找页表项，为 0 时则将 *ppte 设置为空指针。
注意，这里可能会在页目录项无效且 create 为真时，使用 page_alloc 创建一个页表，此时应维护申请得到的物理页的 pp_ref 字段。

回答

首先需要理解在二级页表机制中，虚地址与实地址的映射关系,根据代码一行一行给出查找过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) {
        Pde *pgdir_entryp;
        struct Page *pp;

        /* Step 1: Get the corresponding page directory entry. */
        /* Exercise 2.6: Your code here. (1/3) */
        pgdir_entryp = pgdir + PDX(va);//利用指向物理内存页目录基地址指针pgdir，加上偏移PDX(),得到一级页表项
        /* Step 2: If the corresponding page table is not existent (valid) then:
         *   * If parameter `create` is set, create one. Set the permission bits 'PTE_C_CACHEABLE |
         *     PTE_V' for this new page in the page directory. If failed to allocate a new page (out
         *     of memory), return the error.
         *   * Otherwise, assign NULL to '*ppte' and return 0.
         */
        /* Exercise 2.6: Your code here. (2/3) */
        if ((PTE_FLAGS(*pgdir_entryp) & PTE_V) == 0) { //判断该页表项是否无效
                //invalid
                if (create != 0) { //根据create参数决定是否新建一个二级页表，也就是新分配一个页来存储新建的二级页表
                        if (page_alloc(&pp) != 0) {
                                return -E_NO_MEM; //内存满了
                        }
                        pp->pp_ref++; //新建的二级页表被引用了，引用次数加一
                        //set the pp_ref
                        *pgdir_entryp = page2pa(pp) | PTE_C_CACHEABLE | PTE_V; //设置一级页表项的值为新建二级页表的基地址的物理页号作为高20位，低12位赋值为 PTE_C_CACHEABLE | PTE_V 的权限位
                        //set new page in the page directory
                }
                else {
                        *ppte = NULL; //将给定的存放指向二级页表的指针的指针置NULL
                        return 0;
                }
        }
        /* Step 3: Assign the kernel virtual address of the page table entry to '*ppte'. */
        /* Exercise 2.6: Your code here. (3/3) */
        u_long validTablePPN = PTE_ADDR(*pgdir_entryp); //一级页表项有效或者新建了一个新的二级页表，通过PTE_ADDR获取一级页表项中存储的高20位低位置0获得相应的对应的二级页表的物理地址
        //get the ppn of the page table 
        *ppte = (Pte *)KADDR(validTablePPN) + PTX(va); //将得到的物理地址转换为kseg0上的虚地址并通过(Pte *)强制转换成页表项类型，通过加上二级页表偏移PTX()，得到物理内存上的二级页表项对应的虚地址并将其赋给*ppte
        return 0;
}

Exercise 2.7

题面

1
完成 page_insert 函数（补全 TODO 部分）。

回答

该函数本质上是想将给定的虚地址va和页控制块指针pp对应的页的第一个页表项基地址，也就是第一个4B，建立映射关系。具体分析见逐行注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) {
        Pte *pte;

        /* Step 1: Get corresponding page table entry. */
        pgdir_walk(pgdir, va, 0, &pte); //使用pgdir_walk()函数获取可能存在的原有的虚地址va与某个二级页表项对应的关系，这里pte可能是NULL也可能是可能的二级页表项对应的虚地址
	
        if (pte && (*pte & PTE_V)) { //当pte为后者且值有效时
                if (pa2page(*pte) != pp) { //此时对于pte的解引用得到的就是二级页表项存储的值，由于pa2page函数是将物理地址右移12位后利用高20位的物理页号通过pages指针得到相应的页控制块，因此此处不用考虑二级页表项的低12位权限位
                        page_remove(pgdir, asid, va); //如果原有映射对应的页控制块与给定的不同，那么就需要将其删去，也就是解绑映射，这里解绑的只是二级页表项与实际物理页的映射，并不是一级页表项同二级页表项的映射，因此后续才能重新获得二级页表
                } else {
                        tlb_invalidate(asid, va); //如果一致，那只要改权限位就可以了，但是此处由于该页表项可能存在于TLB中，所以需将TLB中的拷贝无效化，便于下次访问到的时候进行重填
                        *pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
                        return 0;
                }
        }

        /* Step 2: Flush TLB with 'tlb_invalidate'. */
        /* Exercise 2.7: Your code here. (1/3) */
        tlb_invalidate(asid, va); //pte为NULL或者pte值无效时，先针对后者，同样将相应可能在TLB中的拷贝无效
        /* Step 3: Re-get or create the page table entry. */
        /* If failed to create, return the error. */
        /* Exercise 2.7: Your code here. (2/3) */
        if (pgdir_walk(pgdir, va, 1, &pte) != 0) { //为NULL或者无效或者解绑映射后，通过可新建二级页表的方式使用pgdir_walk，重建或重新获得解绑后的二级页表项，假若内存满了，就返回异常
                return -E_NO_MEM;
        } //get the page table entry by re-get or creation
        /* Step 4: Insert the page to the page table entry with 'perm | PTE_C_CACHEABLE | PTE_V'
         * and increase its 'pp_ref'. */
        /* Exercise 2.7: Your code here. (3/3) */
        *pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V; //将新获得的二级页表项的值赋值为pp的物理页号置在高20位与权限位在低12位的结果
        pp->pp_ref++; //相应的引用次数增加，这里是对插入的页的增加
        return 0;
}

Exercise 2.8

题面

1
2
3
完成 kern/tlb_asm.S 中的 tlb_out 函数。该函数根据传入的参数（TLB 的Key）找到对应的 TLB 表项，并将其清空。
具体来说，需要在两个位置插入两条指令，其中一个位置为 tlbp，另一个位置为 tlbwi。
因流水线设计架构原因，tlbp 指令的前后都应各插入一个 nop 以解决数据冒险。

回答

根据提示给出相应答案即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
LEAF(tlb_out) #函数开头声明
  .set noreorder #设定手动设置延迟槽模式
          mfc0    t0, CP0_ENTRYHI #将原有的EntryHi中的值读取到t0寄存器中
          mtc0    a0, CP0_ENTRYHI #将传入的原有的旧表项的Key传入EntryHi寄存器中
          nop #手动延迟
          /* Step 1: Use 'tlbp' to probe TLB entry */
          /* Exercise 2.8: Your code here. (1/2) */
          tlbp #依据旧表项的Key查找TLB将表项索引写入Index寄存器中(未找到则最高位置1，相当于将Index置负)
          nop #手动延迟
          /* Step 2: Fetch the probe result from CP0.Index */
          mfc0    t1, CP0_INDEX #获取旧表项的索引
  .set reorder #设定编译器自动延迟模式
          bltz    t1, NO_SUCH_ENTRY #判断索引是否为负，为负就跳到未找到标签，否则继续下列操作
  .set noreorder #设定手动延迟模式
          mtc0    zero, CP0_ENTRYHI 
          mtc0    zero, CP0_ENTRYLO0
          mtc0    zero, CP0_ENTRYLO1 #将EntryHi、EntryLo0、EntryLo1赋值为0
          nop
          /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
          /* Exercise 2.8: Your code here. (2/2) */
          tlbwi #使用tlbwi指令以Index中值为索引，将上述EntryHi、EntryLo0和EntryLo1写入TLB对应页表项中
  .set reorder #设定自动延迟模式

  NO_SUCH_ENTRY: #未找到标签
          mtc0    t0, CP0_ENTRYHI #复原EntryHi原有的值
          j       ra #返回函数
  END(tlb_out)  #函数结束符

Exercise 2.9

题面

1
完成 kern/tlbex.c 中的 _do_tlb_refill 函数。

回答

根据提示完成相应填空即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void _do_tlb_refill(u_long *pentrylo, u_int va, u_int asid) {
        tlb_invalidate(asid, va); //无效化TLB中对应的页表项，因为要重填嘛
        Pte *ppte;
        /* Hints:
         *  Invoke 'page_lookup' repeatedly in a loop to find the page table entry '*ppte'
         * associated with the virtual address 'va' in the current address space 'cur_pgdir'.
         *
         *  **While** 'page_lookup' returns 'NULL', indicating that the '*ppte' could not be found,
         *  allocate a new page using 'passive_alloc' until 'page_lookup' succeeds.
         */

        /* Exercise 2.9: Your code here. */
        while (1) {
                if (page_lookup(cur_pgdir, va, &ppte) == NULL) { //通过循环不断获取给定的va在二级页表机制中的二级页表项，
                // 如果获取为空就通过passive_alloc函数新分配一个二级页表并建立相应的映射，
                // 这里暂时未考虑内存满的替换情况
                        passive_alloc(va, cur_pgdir, asid);
                }
                else {
                        break;
                }
        }
        ppte = (Pte *)((u_long)ppte & ~0x7); //将ppte与偶页表项对齐
        pentrylo[0] = ppte[0] >> 6; 
        pentrylo[1] = ppte[1] >> 6; //奇偶页机制下分别获取当前页表项和下一个页表项值的高26位
}

Exercise 2.10

题面

1
完成 kern/tlb_asm.S 中的 do_tlb_refill 函数。

回答

根据提示完成相应填空即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
NESTED(do_tlb_refill, 24, zero)
        mfc0    a1, CP0_BADVADDR #将发生异常的访存地址存入a1中
        mfc0    a2, CP0_ENTRYHI 
        andi    a2, a2, 0xff /* ASID is stored in the lower 8 bits of CP0_ENTRYHI */
.globl do_tlb_refill_call;
do_tlb_refill_call:
        addi    sp, sp, -24 /* Allocate stack for arguments(3), return value(2), and return address(1) */
        sw      ra, 20(sp) /* [sp + 20] - [sp + 23] store the return address */
        addi    a0, sp, 12 /* [sp + 12] - [sp + 19] store the return value */
        jal     _do_tlb_refill /* (Pte *, u_int, u_int) [sp + 0] - [sp + 11] reserved for 3 args */
        lw      a0, 12(sp) /* Return value 0 - Even page table entry */
        lw      a1, 16(sp) /* Return value 1 - Odd page table entry */
        lw      ra, 20(sp) /* Return address */
        addi    sp, sp, 24 /* Deallocate stack */
        mtc0    a0, CP0_ENTRYLO0 /* Even page table entry */
        mtc0    a1, CP0_ENTRYLO1 /* Odd page table entry */
        nop
        /* Hint: use 'tlbwr' to write CP0.EntryHi/Lo into a random tlb entry. */
        /* Exercise 2.10: Your code here. */
        tlbwr  #tlbwr指令将EntryHi和EntryLo的值随机填写到一个TLB页表项中
        jr      ra 
END(do_tlb_refill)

lab2难点分析

物理内存管理

在完成跳转后，为了建立物理内存管理机制，先要预先利用alloc()函数初始化分配物理页框的页控制块的存储空间，并建立好空闲页控制块链表，alloc函数(跳板机版本)如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void *alloc(u_int n, u_int align, int clear) {
        extern char end[];
        u_long alloced_mem;

        /* Initialize `freemem` if this is the first time. The first virtual address that the
         * linker did *not* assign to any kernel code or global variables. */
        if (freemem == 0) {
                freemem = (u_long)end; // end
        }

        /* Step 1: Round up `freemem` up to be aligned properly */
        freemem = ROUND(freemem, align);

        /* Step 2: Save current value of `freemem` as allocated chunk. */
        alloced_mem = freemem;

        /* Step 3: Increase `freemem` to record allocation. */
        freemem = freemem + n;

        // Panic if we're out of memory.
        panic_on(PADDR(freemem) >= memsize);

        /* Step 4: Clear allocated chunk if parameter `clear` is set. */
        if (clear) {
                memset((void *)alloced_mem, 0, n);
        }

        /* Step 5: return allocated chunk. */
        return (void *)alloced_mem;
}
/* End of Key Code "alloc" */

有意思的是，指导书给的版本有亿点小不同，首先是函数声明处，指导书还有static修饰。此外，在Step 3之后的panic_on()处，指导书给的是如下一个条件判断：

1
2
3
if(PADDR(freemem) >= memsize) {
    panic("out of memory");
}

处于好奇我去找了一下跳板机上给的这个panic_on函数，发现其在./include/printK.h中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void _panic(const char *, int, const char *, const char *, ...)
#ifdef MOS_HANG_ON_PANIC
    __attribute__((noreturn))
#endif
    ;

#define panic(...) _panic(__FILE__, __LINE__, __func__, __VA_ARGS__)

#define panic_on(expr)                                                                             \
        do {                                                                                       \
                int _r = (expr);                                                                   \
                if (_r != 0) {                                                                     \
                        panic("'" #expr "' returned %d", _r);                                      \
                }                                                                                  \
        } while (0)

#endif /* _printk_h_ */

其中panic_on是预处理包装的一个条件判断”函数”，当传入的值转化为int类型后不为0，就会触发panic()另一个宏定义的”函数”，进而将其中的参数以变长参数形式触发_panic(__FILE__, __LINE__, __func__, __VA_ARGS__)函数,此处只有该函数的声明，具体的定义在./kern/panic.c函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void _panic(const char *file, int line, const char *func, const char *fmt, ...) {
        u_long sp, ra, badva, sr, cause, epc;
        asm("move %0, $29" : "=r"(sp) :);
        asm("move %0, $31" : "=r"(ra) :);
        asm("mfc0 %0, $8" : "=r"(badva) :);
        asm("mfc0 %0, $12" : "=r"(sr) :);
        asm("mfc0 %0, $13" : "=r"(cause) :);
        asm("mfc0 %0, $14" : "=r"(epc) :);

        printk("panic at %s:%d (%s): ", file, line, func);

        va_list ap;
        va_start(ap, fmt);
        vprintfmt(outputk, NULL, fmt, ap);
        va_end(ap);

        printk("\n"
               "ra:    %08x  sp:  %08x  Status: %08x\n"
               "Cause: %08x  EPC: %08x  BadVA:  %08x\n",
               ra, sp, sr, cause, epc, badva);

#if !defined(LAB) || LAB >= 3
        extern struct Env envs[];
        extern struct Env *curenv;
        extern struct Pde *cur_pgdir;

        if ((u_long)curenv >= KERNBASE) {
                printk("curenv:    %x (id = 0x%x, off = %d)\n", curenv, curenv->env_id,
                       curenv - envs);
        } else if (curenv) {
                printk("curenv:    %x (invalid)\n", curenv);
        } else {
                printk("curenv:    NULL\n");
        }

        if ((u_long)cur_pgdir >= KERNBASE) {
                printk("cur_pgdir: %x\n", cur_pgdir);
        } else if (cur_pgdir) {
                printk("cur_pgdir: %x (invalid)\n", cur_pgdir);
        } else {
                printk("cur_pgdir: NULL\n", cur_pgdir);
        }
#endif

#ifdef MOS_HANG_ON_PANIC
        while (1) {
        }
#else
        halt();
#endif
}
```  
此外，不同于常见的双向链表，存储页控制块的链表封装了许多宏方便操作：   
- LIST_HEAD(name, type),创建一个名为`name`链表的头部结构体，包含一个指向type类型结构体的可指向链表首个元素的指针。
- LIST_ENTRY(type)，作为一个特殊的类型出现，例：`LIST_ENTRY(Page) a;`，其本质是一个包括**指向下一个元素的指针`le_next`和指向前一个元素链表项`le_next`的指针`le_prev`**的链表项，作为指针的指针，`le_prev`便利于当删除一个元素时更改前一个元素链表项的`le_next`。
- LIST_EMPTY(head)，判断head是否为空。
- LIST_FIRST(head)，返回head对应链表的首个元素
- LIST_INIT(head)，初始化head
- LIST_NEXT(elm, field)，返回**指针elm**指向的元素在对应链表中的下一个元素的指针，定义如下:`#define LIST_NEXT(elm, field) ((elm)->field.le_next)`，因此`elm`指向的结构体包含一个名为`field`的字段，该字段存储该节点的`le_next`和`le_prev`的值，类型是一个链表项`LIST_ENTRY(type)`，此后的`field`同义。
- LIST_INSERT_AFTER(listelm, elm, field)，将`elm`插到已有元素`listelm`后
- LIST_INSERT_BEFORE(listelm, elm, field)，插到前
- LIST_INSERT_HEAD(head, elm, field)，插到head对应的链表头部
- LIST_REMOVE(elm, field)，删除elm   
此外，还封装了一些操作链表的函数：
```c
void page_init(void); //初始化物理页面管理
int page_alloc(struct Page **pp); //分配物理页面
void page_free(struct Page *pp); //回收物理页面到空闲页面链表
void page_decref(struct Page *pp); //减少物理页面引用

这些都是需要理解并牢牢掌握的。

虚拟存储管理

其实，虚存是假象出来的，它的唯一用途就是通过映射关系来访问物理内存，而不同段的虚存有不同的映射方式:

由于kseg0和kseg1是近乎直接映射，所以此处的难点主要是通过二级页表机制转换的kuseg和kseg2段：
，由于只能对虚拟内存进行访问，因此在通过一级页表偏移后得到的一级页表项虚地址转换后得到的一级页表项物理地址不能直接就在物理内存上通过得到的物理页号然后访问相应物理的二级页表项，而是仍需要先转换成虚地址(由于在低512MB是可以直接利用kseg0段的映射方式进行转换)，再利用kseg0段的映射方式得到相应的物理地址，这也是不同虚拟段的不同映射方式但是映射关系确定导致的。
其余就是需要掌握一些与页表机制相关的宏和函数：

  • PDX(va)(获取虚地址va的31-22位)和PTX(va)(获取21-12).
  • PTE_V，有效位，为1说明页表项有效。
  • PTE_D，可写位，为1说明允许经由页表项对物理页进行写操作。
  • PTE_G，全局位，为1则TLB仅由虚页号匹配表项，不匹配ASID。
  • PTE_C_CACHEABLE，可缓存位，配置对应页面访问属性为可缓存。
  • PTE_COW，写时复制位。
  • PTE_LIBRARY，共享页面位。
  • int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte), 将一级页表基地址pgdir对应的两级页表结构中的va虚地址所在的二级页表项的指针存储在ppte指向空间上。若create!=0且对应二级页表不存在，则会使用page_alloc分配一页物理内存用于存放二级页表，满了直接报错。
  • int page_insert(Pde *pgdir, u_int asid, struct Page * pp, u_long va, u_int perm),将一级页表基地址pgdir对应的两级页表结构中虚地址va映射到页控制块pp对应的物理页，并将权限设置为perm。
  • struct Page * page_lookup(Pde * pgdir, u_long va, Pte **ppte)，返回一级页表基地址pgdir对应两级页表结构中虚地址va映射的物理页面的页控制块，同时将ptte指向的空间设为对应的二级页表项地址，没找到是会返回NULL的，要看清楚。
  • void page_remove(Pde * pgdir, u_int asid, u_long va)，删除一级页表基地址pgdir对应两级页表结构中va对于物理地址的映射，若存在，则相应物理页面引用次数自减一。

访存与TLB重填

TLB前置知识

拓展了计组学习到的TLB，每个TLB实际上由一组Key和两组Data组成。其中Key由EntryHi寄存器的高19位VPN和低8位ASID组成，而Data则由EntryLo寄存器中的高20位PFN和中间6位权限位组成：

此外，还有对TLB进行查找和填入的软件指令需要掌握：

  • tlbr:以Index寄存器中值为索引，读出TLB中对应表项到EtryHi与EntryLo1、EntryLo0中。
  • tlbwi，以Index寄存器值为索引，将EtryHi与EntryLo1、EntryLo0值写入索引指定TLB表项中。
  • tlbwr，将EtryHi与EntryLo1、EntryLo0的数据随机写到一个TLB表项中(使用Random进行随机指定表项)
  • tlbp，根据EtryHi中的(VPN+ASID)，查找TLB中与之对应的表项，并将其索引存入Index寄存器中，若未找到，则Index最高位置1。

以及为了进行TLB维护而定义的函数：
通过tlb_invalidate()函数删除特定虚地址在TLB中的旧表项，其主要依靠在kern/tlb_asm.S中的tlb_out函数，tlb_out被调用时，a0寄存器中存放传入的参数，值为旧表项的Key(VPN+ASID)，使用mtc0将Key写入EntryHi，再用tlbp根据EntryHi中Key查找相应旧表项，将其索引存入Index，索引值>=0，向EtryHi与EntryLo1、EntryLo0中写入0，之后使用tlbwi指令，将EtryHi与EntryLo1、EntryLo0的值写入索引指定表项。此时旧表项key和Data清零，已无效。
由do_tlb_refill函数完成TLB重填的工作，因为4Kc中有奇偶页设计，其需要重填触发异常的页面及邻居页面。重填时先将两个页面对应页表项写入EntryLo寄存器，再填入TLB。
TLB维护大体流程如下：

  1. 从BadVAddr中取出引出缺失的虚地址。
  2. 从EntryHi的0-7位取出当前进程的ASID。
  3. 先在栈上为返回地址、待填入TLB页表项及函数参数传递预留空间。以存储奇偶页表项地址、触发异常虚地址和ASID为参数，调用_do_tlb_refill函数，其完成了依据虚地址和ASID查找页表并将对应奇偶页表项写回第一个参数指定地址。
  4. 页表项存入EntryLo0和EntryLo1，执行tlbwr将EtryHi与EntryLo1、EntryLo0随机写入TLB一个页表项中。

    当page_llokup()函数在页表中找不到对应表项时，可通过passive_alloc()函数进行处理。若虚地址合法，可为其申请二级页表物理页面(page_alloc)，并将虚地址映射到物理页面(page_insert)上。

心得体会

  • lab2一来代码量激增(不只是编写的更有阅读的)，因为为了理解一个函数的用处，由于封装了过多的宏函数(对于熟练者那是一件美事，但是对于初学者简直要命)，一开始我总是要多开窗口去查看相应的宏函数的作用，直到舍友跟我提及ctags，我才将这个开学时一学而过的东西重新拾起来，在家目录的.vimrc文件中在原有的第一行末尾：
    set tags=tags加上,../tags加可以完成对于当前目录和下一级目录的ctags跳转，简直是阅读代码的利器，妈妈再也不用担心我读不懂代码了。
  • 当然这单元更重要的还是理解整个内存管理机制的构建以及运作方式是如何，下为两张为了便于理解我的作图：


    不是很好看，但是画出来写一下确实好理解了很多，因为真正理解下来，那些曾经认为的晦涩和繁琐也已然化作祛魅，成为理解OS路上的奠基之石。