BUAA-OS Lab2 实验笔记

继上一篇,我们已经跳转到了init/init.c中的mips_init函数,即内核初始化的入口点,一起回顾一下:

#ifdef MOS_INIT_OVERRIDDEN
#include <generated/init_override.h>
#else
void mips_init(u_int argc, char **argv, char **penv, u_int ram_low_size) {
	printk("init.c:\tmips_init() is called\n");

    // lab2:
	//mips_detect_memory(ram_low_size);
	//mips_vm_init();
	//page_init();
}
#endif

那么后续有哪些初始化操作呢?

内核程序启动

探测硬件可用内存:mips_detect_memory函数

mips_detect_memory()的实现位于 kern/pmap.c，作用是探测硬件可用内存，并初始化一些内存管理相关的变量。 > 记得吗?QEMU模拟器提供bootloader的启动功能,已经帮助完成可用物理内存的探测,通过ram_low_size传入. > > 函数中变量意义: > * memsize: 总物理内存对应的字节数; > * npage:总物理页数.(每一个物理页,大小为1024字节)

void mips_detect_memory(u_int _memsize) {
	/* Step 1: Initialize memsize. */
	memsize = _memsize;

	/* Step 2: Calculate the corresponding 'npage' value. */
	/* Exercise 2.1: Your code here. */
	npage=memsize/PAGE_SIZE;
	printk("Memory size: %lu KiB, number of pages: %lu\n", memsize / 1024, npage);
}

进行内存管理的空间分配: mips_init函数

void mips_vm_init() {
	pages = (struct Page *)alloc(npage * sizeof(struct Page), PAGE_SIZE, 1);
	printk("to memory %x for struct Pages.\n", freemem);
	printk("pmap.c:\t mips vm init success\n");
}

在进入alloc函数前,我们先看看CPU指令的访存机制:

在实际程序中,CPU发出的访存、跳转、取指等指令的目标地址都是虚拟地址.在4Kc上,软件访存的虚拟地址会先被MMU硬件映射到物理地址;再使用物理地址 访问内存或其他外设。映射与内存布局如下: * kseg0(虚拟地址:0x80000000~0x9fffffff):存放内核代码与数据 * 虚拟地址->物理地址:最高位置0 * kseg1(虚拟地址:0xa0000000~0xbfffffff):访问外设 * 虚拟地址->物理地址:最高3位置0 * kuseg(虚拟地址:0x00000000~0x7fffffff):存放用户程序代码与数据** * 虚拟地址->物理地址:通过 TLB 转换

现在,我们进入mips_init中调用的alloc函数,其意义如下: 1. 分配npage * sizeof(struct Page)字节的物理内存,并返回初始的虚拟地址,同时将地址按照PAGE_SIZE字节对齐; 2. 将对应内存空间清0(clear);

void *alloc(u_int n, u_int align, int clear) {
	extern char end[];
	//end定义在kernel.lds中:. = 0x80400000;end = . ;
	//在kseg0中:0x80400000映射至0x400000(虚拟地址最高位清0，转为物理地址)
	//从0x400000开始分配物理内存
	u_long alloced_mem;
	
	//表示:小于freemem的物理地址均已被分配(不再分配)
	if (freemem == 0) {
		freemem = (u_long)end; // end
	}

	/* Step 1: freemem向上对齐 */
	freemem = ROUND(freemem, align);

	/* Step 2: 保存空闲物理空间的起始地址 */
	alloced_mem = freemem;

	/* Step 3: 更新. */
	freemem = freemem + n;

	panic_on(PADDR(freemem) >= memsize);
	//PADDR(x)定义在include/mmu.h中
	//PADDR(x)返回虚拟地址x对应物理地址的宏(x需为kseg0中的虚拟地址)
	//KADDR(x)返回物理地址x位于kseg0的虚拟地址

	/* Step 4: 内存空间清0. */
	if (clear) {
		memset((void *)alloced_mem, 0, n);
	}

	/* Step 5: 返回虚拟地址起始地址. */
	return (void *)alloced_mem;
}

总结alloc的功能: 从物理地址0x400000开始,分配并清空npage * sizeof(struct Page)字节的物理内存;返回对应的虚拟内存起始地址. > 分配的这段物理内存位于kseg0中,使用两个宏完成地址转换: > > * PADDR(x):由虚拟地址x,得物理地址(最高位清0) >

#define ULIM 0x80000000
#define PADDR(kva)({
    if (_a < ULIM) panic("PADDR called with invalid kva %08lx", _a);
    _a - ULIM;
)}

> * KADDR(x):由物理地址x,得虚拟地址; >

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

从alloc返回mips_vm_init可知:

void mips_vm_init() {
	pages = (struct Page *)alloc(npage * sizeof(struct Page), PAGE_SIZE, 1);
}

pages为虚拟内存的起始地址.

在回到mips_init函数后,继续执行page_init函数之前,让我们先转移视线,看看物理内存管理的方式和数据结构.

物理内存管理

MOS 中的采取页式内存管理，采用链表管理空闲物理页框。 > 在实验里，内存管理的代码位于 kern/pmap.c 中。函数的声明位于 include/pmap.h 中。

链表数据结构

一起瞧瞧不同链表的形式吧!

头部结构体

//单向链表：
#define SLIST_HEAD(name, type)                                          
struct name {                                                           
    struct type *slh_first; /* first element */                     
}
 //双向链表：
#define LIST_HEAD(name, type)                                           
struct name {                                                           
    struct type *lh_first;  /* first element */                     
}
 //循环链表：
#define CIRCLEQ_HEAD(name, type)                                        
struct name {                                                           
    struct type *cqh_first;         
    struct type *cqh_last;          
}

链表项结构体

//单向链表：链表项包含⼀个指向下⼀个元素的指针sle_next.
#define SLIST_ENTRY(type)                                               
struct {
    struct type *sle_next; /* next element*/
}

//双向链表：链表项包含指向下⼀个元素的指针le_next,和指向前⼀个链表项le_next的指针`le_prev`.
#define LIST_ENTRY(type)                                                
struct {
    struct type *le_next;   /* next element */
    struct type **le_prev;  /* address of previous next element */
}

//循环链表：链表项包含指向前⼀个和下⼀个元素的指针cqe_prev,cqe_next.
#define CIRCLEQ_ENTRY(type)
struct{
    struct type *cqe_next;  /* next element */
    struct type *cqe_prev;  /* previous element */ 
}

链表操作

• 单向链表

   //只能在指定节点后插⼊，不能在之前插⼊
  #define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   
      (elm)->field.sle_next = (slistelm)->field.sle_next;             
      (slistelm)->field.sle_next = (elm);                             
  } while (/*CONSTCOND*/0)
  
   //移除：
  #define SLIST_REMOVE(head, elm, type, field) do {                       
  //判断是否为头节点
      if ((head)->slh_first == (elm)) {
          SLIST_REMOVE_HEAD((head), field);
      }
      else {
          struct type *curelm = (head)->slh_first;
          //要删除指定节点时，需从头节点开始遍历，找到该节点的前序节点
          while(curelm->field.sle_next != (elm)) curelm = curelm->field.sle_next;
      } while (/*CONSTCOND*/0)
  }

• 循环链表：链表项包含指向前⼀个和下⼀个元素的指针cqe_prev,cqe_next.

  //节点后插⼊：
  #define CIRCLEQ_INSERT_AFTER(head,listelm,elm,field) do {
      (elm)->field.cqe_next=(listelm)->field.cqe_next;
      (elm)->field.cqe_prev = (listelm);
      //注意listelm是否为尾节点：若是，更新尾节点为elm.
      if ((listelm)->field.cqe_next == (void *)(head)) 
          (head)->cqh_last = (elm);
      else 
          (listelm)->field.cqe_next->field.cqe_prev = (elm);         
      (listelm)->field.cqe_next = (elm); 
  }while (/*CONSTCOND*/0)
  
   //节点前插⼊：
  #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {
          (elm)->field.cqe_next = (listelm);
          (elm)->field.cqe_prev = (listelm)->field.cqe_prev;
          //若listelm为头节点：若是，更新头节点为elm.
          if ((listelm)->field.cqe_prev == (void *)(head))            
              (head)->cqh_first = (elm);   
          else                                                           
              (listelm)->field.cqe_prev->field.cqe_next = (elm);     
          (listelm)->field.cqe_prev = (elm);                            
   } while (/*CONSTCOND*/0)
  
   //移除：
  #define CIRCLEQ_REMOVE(head, elm, field) do {                          
          //若被移除元素elm是尾节点：
          if ((elm)->field.cqe_next == (void *)(head))                  
              (head)->cqh_last = (elm)->field.cqe_prev;            
          else                                                       
              (elm)->field.cqe_next->field.cqe_prev =(elm)->field.cqe_prev;
          //若被移除元素elm是头节点：
          if ((elm)->field.cqe_prev == (void *)(head))                   
                  (head)->cqh_first = (elm)->field.cqe_next;             
          else                                                           
                  (elm)->field.cqe_prev->field.cqe_next =(elm)->field.cqe_next; 
   } while (/*CONSTCOND*/0)

• 双向链表：链表项包含指向下⼀个元素的指针struct type *le_next,和指向前⼀个链表项struct type **le_next的指针le_prev.

操作	单向链表	循环链表	双向链表
链表头部插入	O(1)	O(1)	O(1)
链表尾部插入	O(n)	O(1)	O(1)
指定位置插入	O(n)	O(n)	O(n)
删除头节点	O(1)	O(n)	O(1)
删除尾节点	O(n)	O(1)	O(1)
删除指定节点	O(n)	O(n)	O(n)

C++中可以使用std::stack<T> 定义一个类型为T的栈，Java中可以使用HashMap<K,V> 定义一个键类型为K且值类型为V的哈希表。这种模式称为泛型，C语言并没有泛型的语法，因 此需要通过宏另辟蹊径来实现泛型。

⽤宏实现链表的好处：

• 代码复⽤性增强：宏是预处理器指令，在编译前插⼊代码。因此可在多个地⽅复⽤。

• 提⾼性能：宏在编译时展开，在运⾏时没有额外的函数调⽤开销。

• 跨平台兼容性：宏是C/C++等编程语⾔的⼀部分，在Window、Linux等操作系统上，只要编译 器⽀持宏，就可以使⽤宏操作链表。

页式内存管理：采用若干个页控制块

物理页结构体: struct Page

typedef LIST_ENTRY(Page) Page_LIST_entry_t;
struct Page {
	Page_LIST_entry_t pp_link; /* free list link */		//链表项
	u_short pp_ref;		//这一页物理内存被引用的次数:有多少虚拟页映射到该物理页
};

npage 个 Page 和 npage 个物理⻚⾯⼀⼀顺序对应。（分配npage * sizeof(struct Page)字节的物理内存） * 若⾸个Page 的地址为 P，则 P[i] 对应从0 开始计数的第i个物理⻚⾯。

空闲链表：struct Page_list page_free_list;

struct Page_list{
    struct {
        struct {
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;      //双向链表项
        u_short pp_ref;     //当前物理页的引用次数
    }* lh_first;
}
struct Page_list page_free_list;

当一个进程需要分配内存时：将空闲链表头部的页控制块对应的那一页物理内存分配出去，将该页控制块从空闲链表中删去；

当一页物理内存被使用完毕（引用次数为0）时：将其对应的页控制块重新插入到空闲链表的头部。

相关函数

物理页面管理初始化：page_init

初始化+页对齐后： * 已使用的页控制块引用次数全部标1； * 剩下的物理页面的引用次数全部标为0，并将它们对应的页控制块插入到page_free_list.

已分配的页面：0~(index-1)

未分配的页面：index~(npage-1)

void page_init(void) {
	/* Step 1: Initialize page_free_list. */
	LIST_INIT(&page_free_list);

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

	/* Step 3: Mark all memory below `freemem` as used (set `pp_ref` to 1) */
	int index=(freemem-KSEG0)/PAGE_SIZE;
	while(index--) pages[index].pp_ref=1;	

	/* Step 4: Mark the other memory as free. */
	for(index=(freemem-KSEG0)/PAGE_SIZE;index<npage;index++){
		pages[index].pp_ref=0;
		LIST_INSERT_HEAD(&page_free_list,&pages[index],pp_link);
	}
}

页面分配：page_alloc函数

• 如果空闲链表没有可用页，返回异常返回值； > 一般的操作系统中，当物理页全部被映射（所有内存空间均被占用），若需要申请新的物理页，则需要将一些在内存中的物理页置换到硬盘中，采用FIFO算法或LRU算法等等。
• 如果空闲链表有可用的页，取出链表头部的一页；初始化后，将该页对应的页控制块的地址放到调用者指定的地方。

  int page_alloc(struct Page **new) {
  	/* Step 1: Get a page from free memory. If fails, return the error code.*/
  	struct Page *pp;
  
  	//取出空闲块链表page_free_list头部的页控制块，并从链表中移除
  	if(LIST_EMPTY(&page_free_list)) return -E_NO_MEM;
  	pp=LIST_FIRST(&page_free_list);
  
  	LIST_REMOVE(pp, pp_link);
  
  	/* Step 2: Initialize this page with zero.
  	 * Hint: use `memset`. */
  	//page2kva(pp):KADDR(page2pa(pp));
  	//KADDR(x)将物理地址x翻译为kseg0中的虚拟地址,memset第一个参数使用虚拟地址
  	//(void*)转为字节类型
  	memset((void *)page2kva(pp),0,PAGE_SIZE);
  	*new = pp;	//将pp指向的空间，赋值为该页控制块的地址
  	return 0;
  }

减少物理页面引用：page_decref函数

• 令 pp 对应页控制块的引用次数减少 1;
  • 如果引用次数为 0,调用page_free 函数将对应物理页面重新设置为空闲页面

    void page_decref(struct Page *pp) {
    	assert(pp->pp_ref > 0);
    
    	/* If 'pp_ref' reaches to 0, free this page. */
    	if (--pp->pp_ref == 0) {
    		page_free(pp);
    	}
    }

回收物理页面：page_free函数

• 将pp指向的页控制块，重新插入到page_free_list中

  void page_free(struct Page *pp) {
  	assert(pp->pp_ref == 0);
  	/* Just insert it into 'page_free_list'. */
  	LIST_INSERT_HEAD(&page_free_list,pp,pp_link);
  }

虚拟内存管理

• 对于kseg0：PADDR, KADDR完成虚拟地址和对应的物理地址的转换；
• 对于kuseg：两级页表结构完成地址转换。

两级页表结构

> 两个宏以快速获取偏移量：PDX(va)可以获取虚拟地址va的31-22位，PTX(va) 可以获取虚拟地址 va 的21-12 位。 >

#define PDSHIFT 22
#define PDX(va) ((((u_long)(va)) >> PDSHIFT) & 0x03FF)
#define PGSHIFT 12
#define PTX(va) ((((u_long)(va)) >> PGSHIFT) & 0x03FF)

每个页表均由1024个页表项组成；每个页表项由32位组成：包括20位物理页号以及12位标志位。 * 12位标志位包含高6位硬件标志位，与低6位软件标志位： * 高6位硬件标志位：存入EntryLo寄存器中，供硬件使用（例如标志位PTE_V、PTE_D 就分别对应 EntryLo 中的 V、D 标志位）； * 低6位软件标志位：不会被存入 TLB 中，仅供软件使用（例如标志位PTE_COW、PTE_LIBRARY 不对应任何硬件标志位，仅在页表的部分操作中被操作系统软件利用）。

// ⻚表项的物理⻚号部分:31~12位,也即:物理⻚基地址
#define PTE_ADDR(pte) (((u_long)(pte)) & ~0xFFF)
 // ⻚表项的权限位部分:11~0位
#define PTE_FLAGS(pte) (((u_long)(pte)) & 0xFFF)

常用权限位： * PTE_V：有效位，若某页表项的有效位为1，则该页表项有效，其中高20位是对应的物理页号； * PTE_D：可写位，若某页表项的可写位为1，则允许经由该页表项对物理页进行写操作； * PTE_C_CACHEABLE：可缓存位，配置对应页面的访问属性为可缓存（通常对于所有物理页面，都将其配置为可缓存，以允许CPU使用cache加速对这些页面的访存请求） * PTE_G： 全局位，若某页表项的全局位为1，则TLB仅通过虚页号匹配页表项，而不匹配ASID（ Lab3 中，用于映射 pages 和 envs 到用户空间） * PTE_COW：写时复制位（在 Lab4 中用到，用于实现 fork 的写时复制机制） * PTE_LIBRARY：共享页面位

页表相关函数

二级页表检索函数：pgdir_walk函数

• 给定⼀个虚拟地址va ,在⼀级页表基地址pgdir 指向的页⽬录中，查找该虚拟地址va对应的二级页表项,将其地址写⼊*ppte .
  • 如果create不为0，且对应的二级页表不存在：使用page_alloc函数分配一页物理内存，用于存放二级页表；如果分配失败则返回错误码
• 过程：找到⼀级页表项->读出物理页号，找到⼆级页表基地址->找到⼆级页表项

  static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) {
  	Pde *pgdir_entryp;
  	struct Page *pp;
  
  	//1.pgdir_entryp指向va对应的⼀级⻚表项:
  	//pgdir为⼀级⻚表基地址，PDX(va)为⼀级⻚表偏移量
  	//*pgdir_entryp为⻚表项内容(32位：20位物理⻚号+12位权限位）
  	pgdir_entryp=pgdir+PDX(va);	
  
  	 //2.处理对应⼀级⻚表项⽆效的情况:
  	 //int page_alloc(struct Page **new)     //申请空闲的物理⻚块，其地址存⼊new.
  	if(!(*pgdir_entryp & PTE_V)){			//对应⼆级⻚表不存在/有效位为0.
  		if(create){
  			if(page_alloc(&pp)==-E_NO_MEM){		//pp指向分配的空闲⻚控制块
  				//分配空闲物理⻚失败，超出内存
  				*ppte=NULL;
  				return -E_NO_MEM;	
  			}
  			pp->pp_ref++;		//申请到的物理⻚的引⽤次数+1
  			//更新⼀级⻚表项pgdir_entryp:
  			//page2pa(pp)获得:⻚控制块pp对应物理基地址
  			*pgdir_entryp=page2pa(pp) | PTE_C_CACHEABLE | PTE_V;
  		}else{
  			*ppte=NULL;return 0;
  		}
  	}
  
  	//3.将⼆级⻚表项的虚拟地址，写⼊*ppte
  	//⼆级⻚表基地址：PTE_ADDR(*pgdir_entryp)；PTX(va)为⼆级⻚表偏移量
  	//(⻚表在内核kseg0中,⽤KADDR转为虚拟地址)
  	*ppte=(Pte *)KADDR(PTE_ADDR(*pgdir_entryp)+PTX(va)*4);
  	return 0;
  }

增加地址映射函数：pgdir_insert函数

• 给定⼀个虚拟地址va，在⼀级页表基地址pgdir指向的⻚⽬录中，将虚拟地址va映射⾄页控制块pp对应的物理页面。

  int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) {
  	Pte *pte;
  
  	// 1.获取va对应的⼆级⻚表项
  	// [1]检查是否va已经存在映射?
  	pgdir_walk(pgdir, va, 0, &pte);		// 不存在,返回NULL;存在,*pte为该虚拟地址对应的⼆级⻚表项
  
  	if (pte && (*pte & PTE_V)) {		// 存在且有效
  	// [2]现有映射的⻚，和待插⼊的⻚，是否⼀致？
  		//*(&pte)=pte⾥存储⼆级⻚表项的地址，pte为(Pte *)类型，*pte为⼆级⻚表项内容
  		//pa2page()由⼆级⻚表项内容,找到pages中对应的⻚控制块
  		if (pa2page(*pte) != pp) {
  			page_remove(pgdir, asid, va);	//不⼀样，移除现有映射
  		} else {		//⼀样：更新映射的权限位
  			tlb_invalidate(asid, va);		//(1)删掉TLB中缓存的⻚表项
  			*pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
  			//(2)更新内存中的⻚表项：下次加载va所在⻚时，TLB从⻚表中加载该项
  			return 0;
  		}
  	}
  
  	// 2. 删掉TLB中缓存的va对应⻚表项
  	tlb_invalidate(asid,va);
  
  	// 3. 重新获取/申请va对应的⼆级⻚表项pte
  	if(pgdir_walk(pgdir,va,1,&pte)==-E_NO_MEM){	
  		//create=1,允许申请新的页控制块,将va对应的二级页表项地址存入pte
  		return -E_NO_MEM;
  	}
  
  	// 4. 填写二级页表项:物理页号(由新映射的pp页控制块决定)+权限位
  	*pte=page2pa(pp)| perm | PTE_C_CACHEABLE | PTE_V;
  	pp->pp_ref++;
  
  	return 0;
  }

寻找映射的物理地址函数：page_lookup函数

• 在⼀级⻚表基地址pgdir指向的页⽬录中，返回虚拟地址 va 映射的物理页面的页控制块；将ppte 指向的页表项内容，设为对应的二级页表项地址。

  struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte) {
  	struct Page *pp;
  	Pte *pte;
  
  	// 1. 寻找是否存在这一页表项？
  	pgdir_walk(pgdir, va, 0, &pte);
  
  	// 若页表项不存在或无效：返回空指针
  	if (pte == NULL || (*pte & PTE_V) == 0) {
  		return NULL;
  	}
  
  	// 获取页表项*pte对应页控制块pp
  	pp = pa2page(*pte);
  	if (ppte) {
  		*ppte = pte;
  	}
  
  	return pp;
  }

取消地址映射函数：page_remove函数

• 在⼀级⻚表基地址pgdir指向的页⽬录中，删除va虚拟地址va对物理地址的映射。

  void page_remove(Pde *pgdir, u_int asid, u_long va) {
  	Pte *pte;
  
  	// 1. 查找va对应的页控制块：如果查找失败，说明不存在这一映射，在这一映射，
  	struct Page *pp = page_lookup(pgdir, va, &pte);
  	if (pp == NULL) {
  		return;
  	}
  
  	// 2. 查找成功，则解除其被va的映射
  	page_decref(pp);
  
  	// 清空对应的二级页表项，和该映射在TLB中的缓存
  	*pte = 0;
  	tlb_invalidate(asid, va);
  	return;
  }

补充：include/pmap.h中定义的地址和页控制块转换函数：

extern struct Page *pages;
extern struct Page_list page_free_list;
// 页表项pp的物理页号：
static inline u_long page2ppn(struct Page *pp) {
	return pp - pages;
}

// 页控制块pp,对应物理⻚的基地址:（填充pte常⽤）
// 获取物理页号page2ppn(pp),左移12位
static inline u_long page2pa(struct Page *pp) {
	return page2ppn(pp) << PGSHIFT;
}

// 获取物理地址pa,对应页控制块:（读取pte）
static inline struct Page *pa2page(u_long pa) {
// 物理页号PPN(pa)
	if (PPN(pa) >= npage) {
		panic("pa2page called with invalid pa: %x", pa);
	}
 	return &pages[PPN(pa)];
}

// 页控制块pp,对应物理页虚拟地址
static inline u_long page2kva(struct Page *pp) {
// KADDR:物理地址->虚拟地址
return KADDR(page2pa(pp));
}

// 虚拟地址va,对应物理⻚地址pa
static inline u_long va2pa(Pde *pgdir, u_long va) {
Pte *p;

// 1. pgdir更新为:指向对应一级页表项
//pgdir指向页目录基地址,PDX(va)为一级页表偏移量
pgdir = &pgdir[PDX(va)];	//或写为:pgdir=pgdir+PDX(va);
if (!(*pgdir & PTE_V)) {	//检查⻚表项是否有效(是否映射⾄物理⻚)
	return ~0;
}

// 2. p指向二级页表基地址:
// PTE_ADDR(*pgdir)获取物理⻚基地址;KADDR(pa)转为虚拟地址
//KADDR(pa)转为虚拟地址
p = (Pte *)KADDR(PTE_ADDR(*pgdir));
if (!(p[PTX(va)] & PTE_V)) {
	return ~0;
}
// 3. p[PTX(va)]指向va对应的二级页表项,获取物理页地址
// PTX(va)为⼆级页表偏移量
return PTE_ADDR(p[PTX(va)]);
}

访问内存与TLB重填

在4Kc中，TLB由⼀组Key +两组Data 组成。 * 映射：< VPN, ASID > TLB−−−→ < PFN, N, D, V, G > 1. TLB 采⽤奇偶⻚的设计，即使⽤ VPN 中的⾼ 19 位与 ASID 作为Key ，⼀次查找到两个Data （⼀对相邻⻚⾯的两个⻚表项）； 2. ⽤ VPN 中的最低 1 位在两个 Data 中选择命中的结果。 > 在对TLB进行维护（无效化、重填）时，除了维护目标页面，同时还需要维护目标页面的邻居页面。

TLB组成

• Key（EntryHi）：
  • VPN：Virtual Page Number
    • 当 TLB 缺失（CPU 发出虚拟地址，TLB 查找对应物理地址但未查到）时，EntryHi 中的 VPN 自动（由硬件）填充为对应虚拟地址的虚页号。
    • 当需要填充或检索TLB表项时，软件需要将VPN段填充为对应的虚拟地址。
  • ASID：Address Space IDentifier
    • 用于区分不同的地址空间。查找TLB表项时，除了需要提供VPN，还需要提供ASID（同一虚拟地址在不同的地址空间中通常映射到不同的物理地址）。
• Data（EntryLo）：
  • PFN：Physical Frame Number
    • 软件通过填写PFN，接着使用TLB写指令，才可以将此时EntryHi中的Key与EntryLo 中的 Data 写入 TLB。
  • C：Cache Coherency Attributes 标识页面的 cache 访问属性。PTE_C_CACHEABLE 与PTE_C_UNCACHEABLE 宏可用于填充该段。
  • D：Dirty。事实上是可写位。当该位为1时，对应的页可写；否则对相应页的任何写操作都将引发TLB异常。
  • V：Valid。如果该位为 0，则任何访问对应页的操作都将引发TLB异常。
  • G：Global。如果该位为1，则CPU发出的虚拟地址只需要与该表项的VPN匹配，即可与此TLB项匹配成功（不需要检查ASID是否匹配）。

ASID的必要性： ASID(Address Space Identifier)是地址空间标识符，⽤于在多进程操作系统中标识不同进程的虚拟地址空间。 * 隔离不同进程的地址空间：在多进程环境中，每个进程有相互独⽴的虚拟地址空间，通过ASID进行隔离； * 避免TLB污染：当多个进程共享同⼀个TLB时，若⽆ASID区分，可能出现⼀个进程的地址翻译结果覆盖另⼀个进程的翻译结果的情况，即所谓的“TLB污染”，导致错误的内存访问。通过ASID，操作系统可以将每个进程的地址翻译结果分别存储在TLB中，避免了这种污染。 * 优化性能：当进程切换时，操作系统可以通过ASID，清除或标记与当前进程⽆关的TLB条⽬，确保当前进程快速获取其地址翻译结果。

在MIPS 4Kc中，ASID字段的位数通常是 8 位。这意味着可以有 \(2^8=256\) 个不同的ASID。但是由于TLB的大小是固定的，因此可以容纳的不同地址空间的最大数量受到TLB的大小限制。MIPS 4Kc中的TLB共有 \(64\) 个条目。每个TLB条目可以映射一个虚拟地址到一个物理地址。

因此即使ASID有 \(256\) 个不同的取值，但实际上，MIPS 4Kc可以同时支持的不同地址空间的最大数量仍然是 \(64\) 个。

TLB维护流程

1. 更新页表中虚拟地址对应的页表项的同时，将TLB中对应的旧表项无效化；
2. 在下一次访问该虚拟地址时，硬件会触发TLB重填异常，此时操作系统对TLB进行重填。

TLB旧表项无效化：tlb_invalidate函数

//⽣成⼀个从 l（低位）到 h（⾼位）的位掩码:
#define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
#define NASID 256

//TLB旧表项⽆效化:删除进程asid对应的虚拟地址va,在TLB中的旧表项
void tlb_invalidate(u_int asid, u_long va) {
	//(va & ~GENMASK(PGSHIFT, 0)) :将va的低PGSHIFT位清零
	//(NASID - 1)⽣成⼀个位掩码，⽤于确保asid的值在有效范围内(0~255)
 	//新的Entryhi值：VPN+ASID
	tlb_out((va & ~GENMASK(PGSHIFT, 0)) | (asid & (NASID - 1)));
}

tlb_invalidate函数调用MIPS汇编文件 tlb_asm.S 中的叶函数 tlb_out： > 因流水线设计架构原因，tlbp指令的前后都应各插入一个nop以解决数据冒险。

LEAF(tlb_out)       
/* 关闭MIPS汇编器的指令重排优化，确保指令按特定顺序执⾏ */
.set noreorder      
	/* 将协处理器 0 中寄存器 CP0_ENTRYHI 中的数据写入到通用寄存器 t0 中  */
	mfc0    t0, CP0_ENTRYHI    
	/* 将通用寄存器 a0（旧表项的Key：即VPN+ASID） 中的数据写入到协处理器 0 中寄存器 CP0_ENTRYHI 中 */
	mtc0    a0, CP0_ENTRYHI    
	/* 添加空指令避免数据冲突 */
	nop

	/* 根据 EntryHi 中的 Key 查找对应的旧表项，将表项的索引存⼊ Index */
	tlbp       
	nop

	/* 将协处理器 0 中寄存器 CP0_INDEX 中的数据写入到通用寄存器 t1 中 */
	mfc0    t1, CP0_INDEX      

/* 告诉汇编器恢复对指令的重新排序 */
.set reorder
	/* 检查TLB查询效果是否无效：若t1<0,跳转⾄NO_SUCH_ENTRY标签处 */
	bltz    t1, NO_SUCH_ENTRY  
/* 告诉汇编器禁止对指令重新排序 */
.set noreorder
    /* 如果t1>0(TLB中存在Key对应的表项),清除TLB条⽬: 将CP0_ENTRYHI,CP0_ENTRYLO0,CP0_ENTRYLO1置0. */ 
	mtc0    zero, CP0_ENTRYHI
	mtc0    zero, CP0_ENTRYLO0
	mtc0    zero, CP0_ENTRYLO1
	nop

	/* 以 Index 寄存器中的值为索引将 EntryHi 与 EntryLo 中的数据写入到 TLB 中对应表项 */
	tlbwi      
.set reorder
NO_SUCH_ENTRY:
	/* 将通用寄存器 t0 的内容（原始ENTRYHI值）写回到协处理器 0 中的寄存器 CP0_ENTRYHI 中 */
	mtc0    t0, CP0_ENTRYHI    
	/* 跳转回ra（返回地址）寄存器指定的地址 */
	j       ra             
END(tlb_out)

TLB重填：do_tlb_refill函数

由于4Kc中存在的奇偶页设计，该过程需重填触发异常的页面，及其邻居页面。将两个页面对应的页表项先写入EntryLo寄存器，再填入TLB。

NESTED(do_tlb_refill, 24, zero)
	/* 读取异常相关寄存器:
		CP0_BADVADDR：存储了发生 TLB 缺失异常时访问的虚拟地址（即导致异常的地址）；
		CP0_ENTRYHI：存储了 TLB 匹配的高位部分，包括虚拟页号（VPN）和 ASID */
	mfc0    a1, CP0_BADVADDR
	mfc0    a2, CP0_ENTRYHI
	andi    a2, a2, 0xff /* CP0_ENTRYHI 的低 8 位存储 ASID */
.globl do_tlb_refill_call;
do_tlb_refill_call:
	/* addi sp, sp, -24：在栈上分配 24 字节空间，用于存储：
		3 个参数（Pte *, u_int, u_int）
		2 个返回值（偶页表项、奇页表项）
		1 个返回地址（ra）*/
	addi    sp, sp, -24 
	/* 保存当前函数的返回地址 ra */
	sw      ra, 20(sp) 
	/* a0 传递 sp + 12 的地址，_do_tlb_refill 会将返回值存储到 sp+12 及 sp+16 */
	addi    a0, sp, 12 
	/* 调用 _do_tlb_refill 函数，该函数负责查找触发异常的地址对应的页表项 */
	jal     _do_tlb_refill 
	/* 取回 _do_tlb_refill 返回的页表项：取出偶数页表项到 a0，奇数页表项到 a1 */
	lw      a0, 12(sp) 
	lw      a1, 16(sp) 
	/* 恢复 ra */
	lw      ra, 20(sp) 
	/* 释放栈空间，恢复 sp */
	addi    sp, sp, 24 
	/* 将寄存器值写入 CP0 */
	mtc0    a0, CP0_ENTRYLO0 
	mtc0    a1, CP0_ENTRYLO1 
	nop
	/* 随机选择一个 TLB 表项，并将 CP0_ENTRYHI、CP0_ENTRYLO0 和 CP0_ENTRYLO1 的值写入 TLB */
	tlbwr
	jr      ra
END(do_tlb_refill)

预留参数和返回值空间后，调用_do_tlb_refill函数：根据虚拟地址和ASID查找页表，将对应的奇偶页表项写回其第一个参数所指定的地址。

void _do_tlb_refill(u_long *pentrylo, u_int va, u_int asid) {
	tlb_invalidate(asid, va);
	Pte *ppte;
	
	/* 调用'page_lookup'以查找虚拟地址va，在当前进程页表中对应的页表项'*ppte'：
	1. 如果'page_lookup'返回'NULL'，表明'*ppte'找不到，使用'passive_alloc'为va所在的虚拟页面分配物理页面，直至'page_lookup'返回不为'NULL'则退出循环。 */ 
	while(page_lookup(cur_pgdir,va,&ppte)==NULL){
		passive_alloc(va,cur_pgdir,asid);
	}

	ppte = (Pte *)((u_long)ppte & ~0x7);
	pentrylo[0] = ppte[0] >> 6;
	pentrylo[1] = ppte[1] >> 6;
}

总流程图

内存管理部分已经完成啦！下一个Lab，将实现进程调度和中断异常处理。