BUAA_OS_LAB 2 内存管理2

Thinking 2.1

CPU 运行程序时通过访存指令发出访存请求，进行内存读写操作。在计算机组成原理等硬件实验中，CPU 通常直接发送物理地址，这是为了简化内存操作，让大家关注 CPU 内部的计算与控制逻辑。而在实际程序中，访存、跳转等指令以及用于取指的 PC 寄存器中的访存目标地址都是虚拟地址。我们编写的 C 程序中也经常通过对指针解引用来进行访存，其中指针的值也会被视为虚拟地址，经过编译后生成相应的访存指令。

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

• 在编写的 C 程序中，指针变量中存储的地址是虚拟地址。MIPS 汇编程序中 lw 和 sw 使用的也是是虚拟地址。
• 虚拟地址是指程序中使用的地址，而不是实际物理内存中的地址。在程序运行时，操作系统会将虚拟地址转换为物理地址，然后再进行访问。这样做的好处是可以让多个程序同时运行，而不会相互干扰。物理地址是指实际的内存地址，即硬件上的内存单元编号。

Thinking 2.2

请思考下述两个问题：

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

解答：

• 用宏实现链表的好处在于代码简洁，效率高，而且可以提高代码的可重用性。
• 单向链表的实现最简单，但是除了在头部和某个元素插入删除，都需要遍历，并且只能从头部遍历，效率较低
• 循环链表有三种实现
  • 第一种和单向链表类似，只不过是首位相接
  • 第二种和第三种则不然。和本实验的双向链表一样，它们都能实现对应功能在头部和元素两边插入。但是它们效率更高的点在于它们可以在尾部插入，从尾部遍历。
• 本实验的链表已经分析过了，不再赘述。

Thinking 2.3

Thinking 2.3 请阅读 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 pp_ref;
    }* lh_first;
}

B:

struct Page_list{
  struct {
    struct {
      struct Page *le_next;
      struct Page **le_prev;
    } pp_link;
    u_short pp_ref;
  } lh_first;
}

C:

struct Page_list{
  struct {
    struct {
      struct Page *le_next;
      struct Page **le_prev;
    } pp_link;
     _short pp_ref;
  }* lh_first;
}

最外层：

struct Page_list  {
  struct Page *lh_first;
}

page：

struct Page{
  struct {
    struct Page *le_next;
    struct Page **le_prev;
  } pp_link;
  u_short pp_ref;
}; 

选择C。这是因为lh_first是指针，指向对应的地址，而pp_link是普通结构体，不是指针。pp_link是上面示意图中的右边部分，而lh_first指向第一个页表项的地址，是Page的指针。

Thinking 2.4

请思考下面两个问题：

• 请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。
• 请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID
  段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。

解答：

• ASID（Address Space Identifier） ASID：Address Space IDentifier
  是一个用于标识进程地址空间的唯一标识符。在 R3000-TLB 中，ASID 的作用是为了提高 TLB 的性能，将 TLB 分成 Global 和 process-specific。查找 TLB 表项时，除了需要提供 VPN，还需要提供 ASID（同一虚拟地址在不同的地址空间中通常映射到不同的物理地址）。当 TLB 试图解析虚拟页号时，它确保当前运行进程的 ASID 与虚拟页相关的 ASID 相匹配。如果不匹配，那么就作为 TLB 失效。除了提供地址空间保护外，ASID 允许 TLB 同时包含多个进程的条目。如果 TLB 不支持独立的 ASID，每次选择一个页表时（例如，上下文切换时），TLB 就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。
• 根据《IDT R30xx Family Software Reference Manual》的 Chapter 6，ASID 段的位数为$11 - 6 + 1 = 6$，R3000 中可容纳不同的地址空间的最大数量为 $64$ 个。

Thinking 2.5

• tlb_invalidate 和 tlb_out 的调用关系？
• 请用一句话概括 tlb_invalidate 的作用。
• 逐行解释 tlb_out 中的汇编代码。

解答：

• tlb_invalidate 和 tlb_out 之间的调用关系是 tlb_invalidate 函数内部回调用 tlb_out 函数。
• tlb_invalidate 的作用是使虚拟地址对应的 TLB 表项失效，下次访问这个地址就会触发 TLB 重填，完成对 TLB 的更新。tlb_out 函数根据传入的参数（TLB 的 Key）找到对应的 TLB 表项，并将其清空。
• tlb_out 中的汇编代码如下：

tlb_out:
    mfc0    t0, CP0_ENTRYHI
    mtc0    a0, CP0_ENTRYHI
    nop
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    tlbp
    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
    nop
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    tlbwi
    nop

.set reorder

NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI
        j       ra
END(tlb_out)

• 第一行：将 CP0_ENTRYHI 寄存器中的内容读入 t0 中。
• 第二行：将 a0 寄存器中的内容写入 CP0_ENTRYHI 中。
• 第三行：nop，针对体系结构流水线和延迟槽设计。
• 第四行：随后使用 tlbp 指令，根据 EntryHi 中的 Key 查找对应的旧表项，将表项的索引存入 Index。
• 第五行：nop，针对体系结构流水线和延迟槽设计。
• 第六行：将 CP0_INDEX 寄存器的值写入 t1 寄存器中。
• 第七行：如果 t1 寄存器的值小于等于零，跳转到 NO_SUCH_ENTRY。
• 第八行 将 CP0_ENTRYHI 寄存器中的内容置零
• 第九行 将 CP0_ENTRYLO0 寄存器中的内容置零
• 第十行 nop，针对体系结构流水线和延迟槽设计
• 第十一行 使用 tlbwi 指令，将 EntryHi 和 EntryLo 中的值写入索引指定的表项。此时旧表项的 Key 和 Data 被清零，实现将其无效化。
• 第十二行 nop，针对体系结构流水线和延迟槽设计
• 第十三行 将 CP0_ENTRYHI 寄存器中的内容读入 t0 中。
• 第十四行 返回。

Thinkong 2.6

任选下述二者之一回答：

• 简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上
  的区别。
• 简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上
  的区别。

第一问：

• X86 体系结构中的内存管理机制是基于分段和分页的。分段是将程序的地址空间划分为若干个段，每个段都有自己的基地址和长度，可以独立地进行保护和共享。分页是将整个物理内存划分为若干个大小相等的页，每个页都有自己的物理地址和虚拟地址，可以独立地进行保护和共享。X86 体系结构中使用了一级段表 + 两级页表，每个页表项占用 4 字节，因此每个页表可以映射 1024 个页表项，每个页表可以映射 4MB 的物理内存。
• 与 MIPS 相比，在内存管理上，X86 体系结构使用了分段和分页相结合的方式，而 MIPS 只使用了分页。此外，X86 体系结构中使用了两级页表，而 MIPS 只使用了一级页表(不确定)。

Thinking A.1

在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在 64 位系统中采用三级页表机制，页面大小 4KB。由于 64 位系统中字长为8B，且页目录也占用一页，因此页目录中有 512 个页目录项，因此每级页表都需要 9 位。因此在 64 位系统下，总共需要 $3 \times 9 + 12 = 39$ 位就可以实现三级页表机制，并不需要 64位。

现考虑上述 39 位的三级页式存储系统，虚拟地址空间为 512 GB，若三级页表的基地
址为 PTBase，请计算：

• 三级页表页目录的基地址。
• 映射到页目录自身的页目录项（自映射）。

解答：

• PTBase 这 4MB 空间的起始位置（也就是第一个三级页表的基地址）对应着页目录的第一个页目录项。同时由于 $2^{3 \times 9} = 128M$ 个页表项和 $512GB$ 地址空间是线性映射的，不难算出 PTBase 这一个地址对应的应该是第 $PTBase >> 12$ 个页表项（这一个页表项也就是第一个第二级页表项）。由于一个页表项占 8B 空间，因此第二级页表项基地址的偏移为 $(PTBase >> 12) \times 8$，即 $PTBase >> 9$。而 $PTBase >> 9$ 是 第 $PTBase >> 21$ 个第一级页表项，由于一个页表项占 8B 空间，因此第一级页表项基地址的偏移为 $(PTBase >> 21) \times 8$，即 $PTBase >> 18$。故三级页表页目录的基地址$PDBase + PTBase >> 18$。
• 映射到页目录自身的页目录项为 $PTBase >> 18 + PTBase >> 9 + PTBase$。

难点分析

第一个重要的难点是 Exercise 2.2 完成 include/queue.h 中空缺的函数 LIST_INSERT_AFTER。

这里理解双向链表很困难。因为这里涉及了指针的指针的概念。

le_prev设置为**Page的好处在于：

• 节省了头指针空间。头指针不再需要完整Page结构体，而是只需要四个字节的指针。

• 无论是从前插入，还是从后插入，都比较简便。特别是从前插入，不需要特判头指针(无需做类型转换)

这道题的思路如图：

而本次实验难度最大的就是 Exercise 2.6 完成 pgdir_walk 函数 这一个部分。

但是这个解释过于抽象，实在看不懂。于是我搬来了课程组给出的图，结合实验代码尝试理解：

pgdir_walk，顾名思义，可以理解为walk pgdir，也就是使得页面目录移动。

该函数的作用是：给定一个虚拟地址，在给定的页目录中查找这个虚拟地址对应的物理地址，如果存在这一虚拟地址对应的页表项，则返回这一页表项的地址；如果不存在这一虚拟地址对应的页表项（不存在这一虚拟地址对应的二级页表、即这一虚拟地址对应的页目录项为空或无效），则根据传入的参数进行创建二级页表，或返回空指针。

我们的最终目标是什么？获取一个页表项的地址。怎么获取它？我们注意到我们的MOS操作系统是使用两级页表的，我们手中的虚地址，是由页目录索引、页表索引以及页表项内的偏移量组成的。为了获取最终的页表项，我们需要先由页目录基地址+页目录索引得到对应的页表，再由页表+页表索引得到最终的页表项。好比我们想找到一本书的某一页，我们有这本书的目录、章节相对于目录的位置，这一页在章节中的位置。我们可以先查到这一页在哪一章，再查到这一页在本章的哪一节。

现在我们大致懂得了这个过程的基本原理，我们不妨抽象一下这个结构，使之适用于更多级的页表结构。假设我们手中有第$k$级目录的地址$base$和第$k+1$级子目录相对与$k$级目录的偏移量$\delta$（或者索引，位置），我们通过$base + \delta$就可以得到第$k+1$子目录的地址，这个过程可以递归进行。

解决了这个问题，我们就可以很快写出代码了：

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); //get 31-22 address of va //PDBase + PDX + 00_2 | co expression
        /* Step 2: If the corresponding page table is not existent (valid) and parameter `create`
         * is set, create one. Set the permission bits 'PTE_D | PTE_V' for this new page in the
         * page directory.
         * If failed to allocate a new page (out of memory), return the error. */
        /* Exercise 2.6: Your code here. (2/3) */
        if ( (*pgdir_entryp & PTE_V) == 0)
        {
                if (create)
                {
                        if ( page_alloc(&pp) != 0)
                        {
                                return -E_NO_MEM;
                        }
                        *pgdir_entryp = page2pa(pp);
                        *pgdir_entryp = *pgdir_entryp | PTE_D | PTE_V;
                        pp->pp_ref++;
                }
                else 
                {
                        *ppte = NULL;
                        return 0; //directly return
                }
        }
        /* Step 3: Assign the kernel virtual address of the page table entry to '*ppte'. */
        /* Exercise 2.6: Your code here. (3/3) */
        *ppte = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp)) + PTX(va);
        return 0;
}

需要注意的点:

• 这里可能会在页目录表项无效且 create 为真时，使用 page_alloc 创建一个页表，此时应维护申请得到的物理页的 pp_ref 字段。 记得实时更新 pp_ref 字段，无论是创建页表项或者使用页表项，都要考虑是否需要更新 pp_ref。
• *ppte = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp)) + PTX(va)这个语句不是特别好像，似乎应该这么写:*ppte = (Pte *)KADDR(*pgdir_entryp) + PTX(va)，但是这样就kernel panic了，为什么呢？这是因为*pgdir_entryp为页表对应的地址，而这个地址低12位是不为零的，会作为一些功能位，如果不清零的直接加上PTX(va)，就会将功能位也参与运算，导致地址计算错误。所以要使用低位清零函数KADDR(*pgdir_entryp)将低12位清零，以保证正确性。

实验体会

lab2的实验难度骤增，光是完成实就久花费了15小时。撰写报告又另外花费了10小时。主要发现纯页式管理系统比较容易理解，但是多级页式管理系统就过于抽象了。此外还有页式管理系统页不太理解。经过理论课的学习和实验课的探索，到撰写实验报告时基本搞懂了原理和实现，但是还要在之后的实验中熟练运用。让我们一起继续加油！

课上

• 只通过了exam，extra坐大牢
• 主要还是考试之前没复习，准备时间太少了
• exam实际上就是去年lab2_2的exam，extra主要考察实现一个内外存交换系统

exam

题目：给定页目录pgdir, 权限掩码perm_mask，指定页pp，查找此页目录下二级页表项，满足：

• 此页表项有效
• 此页表项对应的物理页号和pp指向的虚页所对应的物理页号相等
• 权限掩码$\lceil$满足$\rfloor$perm_mask
  • 满足是指：
    • 对于0-11的每一个权限位，当前页表项的权限不小于perm_mask（也就是当前页表项的每一位大于等于perm_mask的每一位）

代码（C89风格，比较冗长）

u_int page_perm_stat(Pde *pgdir, struct Page *pp, u_int perm_mask) {
    int i;
    int j;
    int k;
    int flag;
    u_int cnt = 0;
    Pde* pgdir_entryp;
    Pte* table_entry;
    for (i = 0; i < 1024; ++i) {
            pgdir_entryp = pgdir + i;
            if ((*pgdir_entryp & PTE_V) != 0) {
                    for (k = 0; k < 1024; ++k) {
                            table_entry = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp)) + k;
                            if ((*table_entry & PTE_V) != 0 && PPN(*table_entry) == PPN(page2pa(pp))) {
                                    flag = 1;
                                    for (j = 0; j < 12; ++j) {
                                            if ((*table_entry & (1 << j)) < (perm_mask & (1 << j))) {
                                                    flag = 0;
                                                    break;
                                            }
                                    }
                                    if (flag) {
                                            cnt++;
                                    }
                            }
                    }
            }
    }
    //printk("%u\n",cnt);
    return cnt;
}

后面发现判断perm有更好的办法：

*table_entry & perm_mask == perm_mask
/*
*table_entry & perm_mask
    perm_mask权限位为0的时候结果必为0，也就是说一定满足;
    perm_mask权限位为1的时候，只有*table_entry此位也为1结果才为1，才能满足.
这就正好对应权限位的要求
/*

笔者对许多宏的应用还不熟练，以上代码如果用更多的宏进行优化，将提升可读性。

这个题的坑点在于我们判断的是二级页表项，所以在这之前一定要确保二级页表有效！此外还要注意操作系统只能看见虚拟地址，所以得到物理地址后，除非直接得到偏移，否则如果要获取其数据，必须要用KADDR转换成内核虚地址，才能访问数据！最后是PTE_ADDR的使用。由于页目录起始也是页表，所以Pde和Pte其实可以认为是一个类型，而且由于页表中的0-11位被充分利用起来，成为各种权限位，所以使用地址的时候，必须用PTE_ADDR把低位刷掉，这样才能得到对应页表项指向的页面的基地址，否则可能产生页面访问的越界！

extra

没做出来，但是看了陈奕帅大佬的代码后知道该怎么写了（感谢尊贵的理塘王者）。

本题要实现一个内外存交换系统。当内存不足时，将不常用的一页内存换出到外存，然后初始化并使用这一页，当内存充足的时候再将外存的页换回到内存。

实验是代码填空，所以不再赘述题目，直接根据大佬的代码分析讲解：

#include <swap.h>

struct Page_list page_free_swapable_list;
static u_char *disk_alloc();
static void disk_free(u_char *pdisk);

void swap_init() {
	LIST_INIT(&page_free_swapable_list);
	for (int i = SWAP_PAGE_BASE; i < SWAP_PAGE_END; i += BY2PG) {
		struct Page *pp = pa2page(i);
		LIST_REMOVE(pp, pp_link);
		LIST_INSERT_HEAD(&page_free_swapable_list, pp, pp_link);
	}
}

// Interface for 'Passive Swap Out'
struct Page *swap_alloc(Pde *pgdir, u_int asid) {
	// Step 1: Ensure free page
	if (LIST_EMPTY(&page_free_swapable_list)) {
		/* Your Code Here (1/3) */
		u_long swap_pa=SWAP_PAGE_BASE; // 获取交换页面基地址
		u_long da=disk_alloc(); // 分配一页外存（由于是数组模拟，返回的指针就是va虚地址）
		for(int i=0; i<1024; i++) { //遍历当前的页目录的二级页表项，操作方法同lab2-exam，这里先遍历一级页表项
			if(*(pgdir+i) & PTE_V) { //如果一级页表项有效，找到对应的二级页表
				Pte *pt=(Pte*)KADDR(PTE_ADDR(*(pgdir+i))); // 套路操作，由页表项的内容获取下一级页表（或者页面）的虚地址
				for(int j=0; j<1024; j++) { // 遍历二级页表项
					if((*(pt+j) & PTE_V) && PPN(swap_pa)==PPN(*(pt+j))) { //如果二级页表项有效，且两者物理页号相等
						*(pt+j)&=(~PTE_V); //将PTE_V置为0
						*(pt+j)|=PTE_SWP; //将PTE_SWP置为1，表示换出
						*(pt+j)=((*(pt+j)) & 0xFFF) | da; //将原内存页面低12位权限为拼接到分配的外存页面
						u_long va=((u_long)i << PDSHIFT) | ((u_long)j <<PGSHIFT); // 产生原内存物理页面虚拟地址
						tlb_invalidate(asid, va); //冲刷掉这一页的tlb，使得这一页可用
					}
				}
			}
		}
		memcpy(da, KADDR(swap_pa), BY2PG); //将原内存页面的内容复制到外存页面
		LIST_INSERT_HEAD(&page_free_swapable_list, pa2page(swap_pa), pp_link); //将此页面插入到page_free_swapable_list
	}

	// Step 2: Get a free page and clear it
	struct Page *pp = LIST_FIRST(&page_free_swapable_list);
	LIST_REMOVE(pp, pp_link);
	memset((void *)page2kva(pp), 0, BY2PG);

	return pp;
}

// Interfaces for 'Active Swap In'
static int is_swapped(Pde *pgdir, u_long va) {
	/* Your Code Here (2/3) */
	//判断是否交换了
	Pte *pte;
	pgdir_walk(pgdir, va, 0, &pte); //查找是否有空闲页
	if(pte==NULL) // 判断是否为空
		return 0;
	if(*pte & PTE_SWP) return 1; //如果被交换了且无效，返回1
	else return 0; //其他都返回零，都是无效情况
}

static void swap(Pde *pgdir, u_int asid, u_long va) {
	/* Your Code Here (3/3) */
	// 将处于外存的页面换回到内存
	Pte *pte; 
    pgdir_walk(pgdir, va, 0, &pte); //查找空闲内存页
	u_long swap_pa=page2pa(swap_alloc(pgdir, asid)); //查找一页被交换的内存页所对应的外存页，使用swap之前一定要用is_swapped进行判断，避免无效操作
    u_long da=PTE_ADDR(*pte); //获取页表项的地址
	memcpy(KADDR(swap_pa), da, BY2PG); //将da的内容复制到swap_pa对应的内核虚地址中
    for(int i=0; i<1024; i++) { //这一个部分的功能和上面相同
        if(*(pgdir+i) & PTE_V) {
                Pte *pt=(Pte*)KADDR(PTE_ADDR(*(pgdir+i)));
                for(int j=0; j<1024; j++) {
                        if((*(pt+j) & PTE_SWP) && PPN(da)==PPN(*(pt+j))) {
                            *(pt+j)&=(~PTE_SWP);
                            *(pt+j)|=PTE_V;
                            *(pt+j)=((*(pt+j)) & 0xFFF) | swap_pa;
                            u_long tva=((u_long)i << PDSHIFT) | ((u_long)j <<PGSHIFT);
                            tlb_invalidate(asid, tva);
                        }
                }
        }
    }
    disk_free(da); //释放外存内容
}

Pte swap_lookup(Pde *pgdir, u_int asid, u_long va) {
	// Step 1: If corresponding page is swapped out, swap it in
	if (is_swapped(pgdir, va)) {
		swap(pgdir, asid, va);
	}

	// Step 2: Look up page table element.
	Pte *ppte;
	page_lookup(pgdir, va, &ppte);

	// Step 3: Return
	return ppte == NULL ? 0 : *ppte;
}

// Disk Simulation (Do not modify)
u_char swap_disk[SWAP_DISK_NPAGE * BY2PG] __attribute__((aligned(BY2PG)));
u_char swap_disk_used[SWAP_DISK_NPAGE];

static u_char *disk_alloc() {
	int alloc = 0;
	for (;alloc < SWAP_DISK_NPAGE && swap_disk_used[alloc]; alloc++) {
		;
	}
	assert(alloc < SWAP_DISK_NPAGE);
	swap_disk_used[alloc] = 1;
	return &swap_disk[alloc * BY2PG];
}

static void disk_free(u_char *pdisk) {
	int offset = pdisk - swap_disk;
	assert(offset % BY2PG == 0);
	swap_disk_used[offset / BY2PG] = 0;
}

void physical_memory_manage_check(void) {
	struct Page *pp, *pp0, *pp1, *pp2;
	struct Page_list fl;
	int *temp;

	// should be able to allocate three pages
	pp0 = pp1 = pp2 = 0;
	assert(page_alloc(&pp0) == 0);
	assert(page_alloc(&pp1) == 0);
	assert(page_alloc(&pp2) == 0);

	assert(pp0);
	assert(pp1 && pp1 != pp0);
	assert(pp2 && pp2 != pp1 && pp2 != pp0);

	// temporarily steal the rest of the free pages
	fl = page_free_list;
	// now this page_free list must be empty!!!!
	LIST_INIT(&page_free_list);
	// should be no free memory
	assert(page_alloc(&pp) == -E_NO_MEM);

	temp = (int *)page2kva(pp0);
	// write 1000 to pp0
	*temp = 1000;
	// free pp0
	page_free(pp0);
	printk("The number in address temp is %d\n", *temp);

	// alloc again
	assert(page_alloc(&pp0) == 0);
	assert(pp0);

	// pp0 should not change
	assert(temp == (int *)page2kva(pp0));
	// pp0 should be zero
	assert(*temp == 0);

	page_free_list = fl;
	page_free(pp0);
	page_free(pp1);
	page_free(pp2);
	struct Page_list test_free;
	struct Page *test_pages;
	test_pages = (struct Page *)alloc(10 * sizeof(struct Page), BY2PG, 1);
	LIST_INIT(&test_free);
	// LIST_FIRST(&test_free) = &test_pages[0];
	int i, j = 0;
	struct Page *p, *q;
	for (i = 9; i >= 0; i--) {
		test_pages[i].pp_ref = i;
		// test_pages[i].pp_link=NULL;
		// printk("0x%x  0x%x\n",&test_pages[i], test_pages[i].pp_link.le_next);
		LIST_INSERT_HEAD(&test_free, &test_pages[i], pp_link);
		// printk("0x%x  0x%x\n",&test_pages[i], test_pages[i].pp_link.le_next);
	}
	p = LIST_FIRST(&test_free);
	int answer1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	assert(p != NULL);
	while (p != NULL) {
		// printk("%d %d\n",p->pp_ref,answer1[j]);
		assert(p->pp_ref == answer1[j++]);
		// printk("ptr: 0x%x v: %d\n",(p->pp_link).le_next,((p->pp_link).le_next)->pp_ref);
		p = LIST_NEXT(p, pp_link);
	}
	// insert_after test
	int answer2[] = {0, 1, 2, 3, 4, 20, 5, 6, 7, 8, 9};
	q = (struct Page *)alloc(sizeof(struct Page), BY2PG, 1);
	q->pp_ref = 20;

	// printk("---%d\n",test_pages[4].pp_ref);
	LIST_INSERT_AFTER(&test_pages[4], q, pp_link);
	// printk("---%d\n",LIST_NEXT(&test_pages[4],pp_link)->pp_ref);
	p = LIST_FIRST(&test_free);
	j = 0;
	// printk("into test\n");
	while (p != NULL) {
		//      printk("%d %d\n",p->pp_ref,answer2[j]);
		assert(p->pp_ref == answer2[j++]);
		p = LIST_NEXT(p, pp_link);
	}

	printk("physical_memory_manage_check() succeeded\n");
}