Lab02

思考题

thinking 2.1

1.虚拟地址

2.虚拟地址

thinking 2.2

1.使用宏实现链表，不仅可以实现空页的链表管理，也可以实现空进程的链表管理。使用同一套宏可以实现多个链表的管理，大大提高了可重用性。

2.性能：

  1. 单向链表

     插入操作相对较为简单，因为不需要维护`le_prev`指针，但是性能相差不大

 删除操作单向链表更复杂，时间复杂度为`O(n)`，双向链表复杂度为`O(1)`

  2. 循环链表

     插入操作简单，可以在`O(1)`时间内插入链表尾部，双向链表插入尾部复杂度为`O(n)`

 删除操作与单向链表相同，时间复杂度为`O(n)`

thinking 2.3

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 pp_ref;
    }* lh_first;
}

thinking 2.4

boot_map_segment()：

boot_map_segment(pgdir, PAGES, n, PADDR(pages), PTE_R);

boot_map_segment(pgdir, ENVS, n, PADDR(envs), PTE_R);

在mips_vm_init()中被调用了两次，分别将pages数组的物理地址映射到以虚拟地址UPAGE为起始地址的内核页表，以及将envs数组的物理地址映射到以虚拟地址UENV为起始地址的内核页表。

boot_pgdir_walk：

pgtable_entry = boot_pgdir_walk(pgdir, va_temp, 1);

由boot_map_segment调用。

thinking 2.5

1.ASID：

在不同的进程中，有一部分虚拟内存是所有进程共享的，因此相同的虚拟内存，在不同的进程中回映射到不同的物理地址。为了区分不同进程的虚拟地址，引入了不同进程互不相同的ASID，在查找TLB时，需要传入虚地址和对应的ASID，这样才能正确查找到对应的物理地址。因此ASID是不可缺少的。

2.在不刷新旧的ASID值情况下，由于EntryHi寄存器中ASID值共6位，因此最多可以容纳64个不同的地址空间。

thinking 2.6

tlb_invalidate调用tlb_out

根据当前进程的状态，以虚拟地址和进程的ASID值为参数调用tlb_out完成对TLB对应内容的清除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LEAF(tlb_out)
        mfc0    k1,CP0_ENTRYHI		//$k1 = $EntryHi，暂时保存原EntryHi寄存器值
        mtc0    a0,CP0_ENTRYHI		//$EntryHi = $a0, 此时a0为调用tlb_out时传入的参数
        nop							//空操作
        tlbp						//tlbp, 根据EntryHi寄存器中的值查找对应的表项，并存入Index寄存器
        nop
        nop
        nop
        nop							//空操作, tlbp需要的时钟数
        mfc0    k0,CP0_INDEX		//$k0 = $Index
        bltz    k0,NOFOUND			//if $k0 < 0, 即Index寄存器最高位为1，代表未找到相应页，则跳转到'NOFOUND'
        nop							//空操作
        mtc0    zero,CP0_ENTRYHI	//$EntryHi = 0
        mtc0    zero,CP0_ENTRYLO0	//$EntryLo = 0
        nop							//空操作
        tlbwi						//tlbwi, 根据Index寄存器中的索引将对应的EntryHi和EntryLo清零
NOFOUND:
        mtc0    k1,CP0_ENTRYHI		//$EntryHi = $k1，将原EntryHi寄存器值写回

        j       ra					//结束函数，返回
        nop							//空操作
END(tlb_out)

thinking 2.7

PTbase对应第PTbase>>12个页表项，每个页表项大小为8B，则偏移地址为(PTbase>>12)<<3，

则二级页表基地址为PTbase|(PTbase>>12)<<3。

同理可得，页目录基地址为PTbase|(PTbase>>12)<<3|(PTbase>>21)<<3，

而映射到页目录自身的页目录项地址为PTbase|(PTbase>>12)<<3|(PTbase>>21)<<3|(PTbase>>30)<<3。

thinking 2.8

x86架构的内存管理分为两个部分，分段和分页。

分段提供了一种隔离每个进程或者任务代码、数据和栈模块的机制，保证多个进程或者任务能够在同一个处理器上运行而不会互相干扰。

分页机制实现了传统请求调页的虚拟内存系统，在这种系统中，程序的执行环境块按需要被映射到物理内存中。分页机制同样可以用来隔离多个任务。

对分页和分段机制进行不同的配置，可以分别支持简单的单任务系统、多任务系统或者使用共享内存的多处理器系统。

x86用到三个地址空间的概念：物理地址、线性地址和逻辑地址。而MIPS只有物理地址和虚拟地址两个概念。

实验难点

物理内存管理

页式内存管理

MOS结构中采取页式管理结构，将物理内存总64MB按4KB一页分成16K页。

在物理内存管理中，通过pages结构体数组对这16K页进行管理。

Page结构体中并没有记录太多复杂的信息，其中pp_ref记录了该物理内被映射的次数，pp_link是为了后续采取链表结构管理空闲链表所定义。每个Page结构体对应的物理页并不需要记录，因为结构体与物理页一一对应，通过(p - pages)<<12即可计算得到。

链表管理空闲内存

宏定义

对于空闲链表，MOS采取链表结构管理，并定义了一系列的宏便于操作。

理解并应用链表宏是物理内存管理的难点，下面把一些常用或者较为重要宏里的参数用Page结构体对应的变量代换以便于理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LIST_HEAD(Page_list, Page)
struct Page_list {
    struct Page *lh_first;
}
//定义了一个Page_list结构体类型
LIST_ENTRY(Page)
struct {
    struct Page *le_next;
    struct Page **le_prev;
}
typedef LIST_ENTRY(Page) Page_LIST_entry_t;
//定义了用于链表管理的page_entry
struct Page {
    Page_LIST_entry_t pp_link;
    u_short pp_ref;
}
//定义了Page结构体
LIST_NEXT((page), pp_link)
page->pp_link.le_next

通过转换以后可以很容易得到用于管理空闲链表的结构体定义如下：

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

宏函数

在了解了数据结构以后，便可以着手编写宏函数了。

LIST_INSERT_AFTER

由于双向链表的结构，LIST_INSERT_AFTER(listelm, elm, field)的实现并不难，先了解三个参数对应的含义：

  • listelm为链表中的元素，即用于定位的元素，在此函数中，新的元素需要被插入到该元素之后
  • elm即为新的需要被插入到链表中的元素
  • field是定义的用于链表管理的entry，在链表管理中，即为Page结构体中的pp_link

同样为了便于理解，把宏里的参数用Page结构体对应的变量代换得到代码：

1
2
3
4
5
6
7
LIST_INSERT_AFTER(listpage, page, pp_link) do {     									\
    LIST_NEXT((page), pp_link) = LIST_NEXT((listpage), pp_link);						\
	if(LIST_NEXT((listpage), pp_link) != NULL) 											\
        LIST_NEXT((listpage), pp_link)->pp_link.le_prev = &LIST_NEXT((page), pp_link);  \
    LIST_NEXT((listpage), pp_link) = (page); 											\
	(page)->pp_link.le_prev = &LIST_NEXT((listpage), pp_link);							\
} while(0)

如图所示:

InkedLIST_INSERT_AFTER_LI

LIST_INSERT_TAIL

这个相对于前一个函数复杂的地方在于，首先需要判断链表是否为空，若非空则需要从头指针遍历直到最后一个节点，然后再仿照前一个函数将新元素插入尾部元素之后。而遍历是需要循环变量的，在编写这个函数时以为不可以在宏里定义新的变量，因此用LIST_NEXT((page), pp_link)作为循环变量，代换后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
#define LIST_INSERT_TAIL(head, page, pp_link) do {                                    		\
	if ((LIST_FIRST((head)) == NULL)) LIST_INSERT_HEAD(head, page, pp_link);   				\
	else {                                                                  				\
		LIST_NEXT((page), pp_link) = LIST_FIRST((head));                               		\
		while (LIST_NEXT((LIST_NEXT((page), pp_link)), pp_link) != NULL) {               	\
			LIST_NEXT((page), pp_link) = LIST_NEXT((LIST_NEXT((page), pp_link)), pp_link);  \
		} 																					\
		LIST_NEXT(LIST_NEXT((page), pp_link), pp_link) = (page);                          	\
		(page)->pp_link.le_prev = &LIST_NEXT(LIST_NEXT((page), pp_link), pp_link);      	\
		LIST_NEXT((page), pp_link) = NULL;                                         			\
	}                      													 				\
} while (0)

在写这个函数的时候有一个小问题，在找到最后一个元素后调用LIST_INSERT_AFTER会出错，应该是尾部元素之后的空指针导致的，但是具体问题还是没有发现。

相关函数

主要是page_init(), page_alloc(), page_free()三个函数，在理解和编写完宏函数之后，以及指导书中给定框架的帮助下，这些函数并不难完成。

需要注意的是，调用page_alloc()后，通常需要给新的Page的pp_ref++；而调用page_free()前，需要给该Page的pp_ref--。

虚拟内存管理

在 R3000 上，虚拟地址映射到物理地址，随后使用物理地址来访存。与我们实验相关的映射与寻址规则（内存布局）如下：

  • 若虚拟地址处于 0x80000000~0x9fffffff (kseg0)，则将虚拟地址的最高位置 0得到物理地址，通过 cache 访存。这一部分用于存放内核代码与数据结构。
  • 若虚拟地址处于 0xa0000000~0xbfffffff (kseg1)，则将虚拟地址的最高 3 位置0 得到物理地址，不通过 cache 访存。这一部分用于映射外设。
  • 若虚拟地址处于 0x00000000~0x7fffffff (kuseg)，则需要通过 TLB 来获取物理地址，通过 cache 访存。

kseg0

对于处于kseg0内的虚拟地址，我们可以直接用如下两个宏来访问对应物理地址：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define PADDR(kva)                                                      \
    ({                                                                  \
        u_long a = (u_long)(kva);                                       \
        if (a < ULIM)						       	 	                \
            panic("PADDR called with invalid kva %08lx", a);            \
        a - ULIM;                                                       \
    })
//ULIM = 0x80000000
#define KADDR(pa)                                                       \
    ({                                                                  \
        u_long ppn = PPN(pa);										   	\
        if (ppn >= npage) 						                        \
            panic("KADDR called with invalid pa %08lx", (u_long)(pa));  \
        (pa) + ULIM;                                                    \
    })

可以看到，在该区间内的虚拟和物理地址映射较为简单，就是最高位置1置0的区别。在转换之前，是有判断机制的，即kva应当大于0x80000000，否则不能使用该宏转换；pa对应的物理页框不能大于npage，其本质也就是pa要小于最大物理内存64MB，否则这个物理地址也是不合法的。

而我们的实验重点在于kuseg段，需要填写二级页表，并通过TLB来访问物理地址。

kuseg

二级页表的填写

这是虚拟内存管理的重点，也是个人认为整个lab2中最难的部分。涉及到二级页表的相关知识，以及虚拟地址和物理地址的区别和联系。

首先借助指导书中的图便于理解二级页表的结构：

pgdir

整个二级页表的填写分为两个部分，使用两套配对的函数，时间分界点在于page_init()，但是整体过程是类似的：

  • 有变量va, pa, pgdir, pgdir_entry, pgtable, pgtable_entry，对应关系如上图所示，这些变量都是指明对应的地址，并不是地址里存的实际值
  • 整个填写二级页表的流程大体如下：
    • 计算一级页目录入口pgdir_entry = pgdir + PDX(va)
    • 由一级页目录入口获得二级页表基地址pgtable = KADDR(PTE_ADDR(*pgdir))
    • 计算二级页表入口pgtable_entry = pgtable + PTX(va)
    • 为二级页表入口设置对应的物理地址页号*pgtable_entry = PPN(pa) or *pgtable_entry = PPN(page2pa(page))
  • 在page_init()函数之前，使用boot_pgdir_walk()和boot_map_segment()函数完成填写，在其之后则使用pgdir_walk()和page_insert()函数完成填写。其中都是由后者调用前者，前者完成图示中的前三步，由后者完成第四步。

TLB的填写

所有的在低 2GB 空间的访存操作都需要经过 TLB。

TLB的重填本身是比较复杂的，不过本实验中并没有要求这个内容，只是要求完成tlb_out函数，这在理解TLB重填的过程后并不难，这里就不再展开了。但是理解TLB重填的过程还是十分重要的，在后续的实验中还会多次涉及。

实验心得与总结

只能说lab2的难度比lab1又高了一个台阶，开启了真正的地狱模式。

即使是在lab2课下拿到了满分之后，对于二级页表映射，虚拟地址和物理地址还是不能完全搞明白。

直到lab3做了一部分以后，可能和lab2对照着看，终于算是理清了头绪。