OS-内存管理lab(mit6.828 lab2)

//inc/memlayout.h

// Page descriptor structures, mapped at UPAGES.
// Read/write to the kernel, read-only to user programs.
// Each struct PageInfo stores metadata for one physical page.
// Is it NOT the physical page itself, but there is a one-to-one correspondence between physical pages and struct PageInfo's.
// You can map a struct PageInfo * to the corresponding physical address with page2pa() in kern/pmap.h.


struct PageInfo {
	// Next page on the free list.
    // pp_link指向下一个空闲页
	struct PageInfo *pp_link;

	// pp_ref is the count of pointers (usually in page table entries)
	// to this page, for pages allocated using page_alloc.
	// Pages allocated at boot time using pmap.c's
	// boot_alloc do not have valid reference count fields.
	// pp_ref表示页面被引用数，如果为0，表示是空闲页
	uint16_t pp_ref;
};

	// create initial page directory.
	kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
	memset(kern_pgdir, 0, PGSIZE);

// This simple physical memory allocator is used only while JOS is setting up its virtual memory system.  
// page_alloc() is the real allocator.
// If n>0, allocates enough pages of contiguous physical memory to hold 'n' bytes.  
// Doesn't initialize the memory.  Returns a kernel virtual address.
//
// If n==0, returns the address of the next free page without allocating anything.
//
// If we're out of memory, boot_alloc should panic.
// This function may ONLY be used during initialization, before the page_free_list list has been set up.

static void *
boot_alloc(uint32_t n)
{
	static char *nextfree; // virtual address of next byte of free memory
	char *result;

	if (!nextfree)
	{
		extern char end[];
		nextfree = ROUNDUP((char *)end, PGSIZE);
	}

	// Allocate a chunk large enough to hold 'n' bytes, then update nextfree.  
	// Make sure nextfree is kept aligned to a multiple of PGSIZE.
	// LAB 2: Your code here.

	if (n == 0)
		return nextfree;
    
	//n>0
	result = nextfree;
	nextfree = ROUNDUP((char *)(nextfree + n), PGSIZE);
	if ((uint32_t)nextfree - KERNBASE > (npages * PGSIZE))
		panic("boot_alloc:out of memory!\n");
	return result;
}

//kern/pmap.h
extern struct PageInfo *pages;
extern size_t npages;

	//////////////////////////////////////////////////////////////////////
	// Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
	// The kernel uses this array to keep track of physical pages: for
	// each physical page, there is a corresponding struct PageInfo in this
	// array.  'npages' is the number of physical pages in memory.  Use memset
	// to initialize all fields of each struct PageInfo to 0.
	// Your code goes here:
	pages = (struct PageInfo *)boot_alloc(npages * sizeof(struct PageInfo));
	memset(pages, 0, npages * sizeof(struct PageInfo));

	// The example code here marks all physical pages as free.
	// However this is not truly the case.  What memory is free?
	//  1) Mark physical page 0 as in use.
	//     This way we preserve the real-mode IDT and BIOS structures
	//     in case we ever need them.  (Currently we don't, but...)
	//  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE) is free.  
	//  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must never be allocated.
	//     
	//  4) Then extended memory [EXTPHYSMEM, ...).
	//     Some of it is in use, some is free. Where is the kernel in physical memory?
	//     Which pages are already in use for page tables and other data structures?
	//     
	//
	// Change the code to reflect this.
	// NB: DO NOT actually touch the physical memory corresponding to
	// free pages!

	// 这里的代码把所有的物理页都标记为free
	size_t i;
	for (i = 0; i < npages; i++)
	{
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}

void page_init(void)
{
	size_t i;
	// page 0
	pages[0].pp_ref = 1;

	// [PGSIZE, npages_basemem * PGSIZE)都可用，npages_basemem在i386_detect_memory中获得
	for (i = 1; i < npages_basemem; i++)
	{
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}

	// [IOPHYSMEM, EXTPHYSMEM)
	for (i = IOPHYSMEM / PGSIZE; i < EXTPHYSMEM / PGSIZE; i++)
		pages[i].pp_ref = 1;

	// [EXTPHYSMEM, ...)
    // 这部分被kernel占用，不可用
	size_t first_free_page = PADDR(boot_alloc(0)) / PGSIZE;
	for (i = EXTPHYSMEM / PGSIZE; i < first_free_page; i++)
		pages[i].pp_ref = 1;

	// 其他部分都可用
	for (i = first_free_page; i < npages; i++)
	{
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
}

// Allocates a physical page.  
// If (alloc_flags & ALLOC_ZERO), fills the entire returned physical page with '\0' bytes.  
// Does NOT increment the reference count of the page - the caller must do these if necessary (either explicitly or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset

static inline void* page2kva(struct PageInfo *pp)
{
	return KADDR(page2pa(pp));
}

struct PageInfo * page_alloc(int alloc_flags)
{
	// Fill this function in
	// 如果有空闲页
	if (page_free_list)
	{
		struct PageInfo *allocated = page_free_list;
		// 修改指针
		page_free_list = allocated->pp_link;
		allocated->pp_link = NULL;
		if (alloc_flags & ALLOC_ZERO)
			memset(page2kva(allocated), '\0', PGSIZE);
		return allocated;
	}
	else
		return NULL;
}

//
// Return a page to the free list.
// (This function should only be called when pp->pp_ref reaches 0.)
//
void page_free(struct PageInfo *pp)
{
	// Fill this function in
	// Hint: You may want to panic if pp->pp_ref is nonzero or
	// pp->pp_link is not NULL.
	if (pp->pp_ref)
		panic("page_free：page %p's pp->pp_ref is nonzero", pp);
	else if (pp->pp_link)
		panic("page_free：page %p's pp->pp_link is not NULL", pp);
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

	kern_pgdir = (pde_t *)boot_alloc(PGSIZE);
	memset(kern_pgdir, 0, PGSIZE);
	cprintf("kern_pgdir:0x%08x\n", kern_pgdir);

 *                     |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
 *                     |                              | RW/--
 *                     |   Remapped Physical Memory   | RW/--
 *                     |                              | RW/--
 *    KERNBASE, ---->  +------------------------------+ 0xf0000000      --+
 *    KSTACKTOP        |     CPU0's Kernel Stack      | RW/--  KSTKSIZE   |
 *                     | - - - - - - - - - - - - - - -|                   |

// The entry.S page directory maps the first 4MB of physical memory
// starting at virtual address KERNBASE (that is, it maps virtual
// addresses [KERNBASE, KERNBASE+4MB) to physical addresses [0, 4MB)).
// We choose 4MB because that's how much we can map with one page
// table and it's enough to get us through early boot.  We also map
// virtual addresses [0, 4MB) to physical addresses [0, 4MB); this
// region is critical for a few instructions in entry.S and then we
// never use it again.

// kern/entrypgdir.c
pte_t entry_pgtable[NPTENTRIES];
__attribute__((__aligned__(PGSIZE)))
pde_t entry_pgdir[NPDENTRIES] = {
	// Map VA's [0, 4MB) to PA's [0, 4MB)
	[0]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P,
	// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
	[KERNBASE>>PDXSHIFT]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P + PTE_W
};

+------------------+  <- 0xFFFFFFFF (4GB)
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|                  |
+------------------+  <- 0x00000000

void mem_init(void)
{
	//////////////////////////////////////////////////////////////////////
	// create initial page directory.
	kern_pgdir = (pde_t *)boot_alloc(PGSIZE);
	memset(kern_pgdir, 0, PGSIZE);
	cprintf("kern_pgdir VA:0x%08x\n", kern_pgdir);
	cprintf("kern_pgdir PA:0x%08x\n", PADDR(kern_pgdir));

	//////////////////////////////////////////////////////////////////////
	// Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
	// The kernel uses this array to keep track of physical pages: for
	// each physical page, there is a corresponding struct PageInfo in this
	// array.  'npages' is the number of physical pages in memory.  Use memset
	// to initialize all fields of each struct PageInfo to 0.
	// Your code goes here:
	pages = (struct PageInfo *)boot_alloc(npages * sizeof(struct PageInfo));
	memset(pages, 0, npages * sizeof(struct PageInfo));
	cprintf("pages VA:0x%08x\n", pages);
	cprintf("pages PA:0x%08x\n", PADDR(pages));

	void *end = boot_alloc(0);
	cprintf("end VA:0x%08x\n", end);
	cprintf("end PA:0x%08x\n", PADDR(end));
}

// 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) ----/
//  \---------- PGNUM(la) ----------/

// Given 'pgdir', a pointer to a page directory, pgdir_walk returns a pointer to the page table entry (PTE) for linear address 'va'.
// pgdir_walk()以页目录pgdir和线性地址va作为参数，返回一个指向PTE（线性地址对应的页面所在页表项）的指针
// This requires walking the two-level page table structure.
// 是一个二级页表，和上图一样
//
// The relevant page table page might not exist yet.
// If this is true, and create == false, then pgdir_walk returns NULL.
// 相关页可能不存在，如果不存在且create == false，函数返回NULL
// Otherwise, pgdir_walk allocates a new page table page with page_alloc.
//    - If the allocation fails, pgdir_walk returns NULL.
//    - Otherwise, the new page's reference count is incremented, the page is cleared, and pgdir_walk returns a pointer into the new page table page.
// 否则用page_alloc分配一个页面，分配失败返回NULL；分配成功，新页的引用次数+1，页清空，返回页指针

// page directory index
#define PDX(la)		((((uintptr_t) (la)) >> PDXSHIFT) & 0x3FF)
// page table index
#define PTX(la)		((((uintptr_t) (la)) >> PTXSHIFT) & 0x3FF)
// Address in page table or page directory entry
#define PTE_ADDR(pte)	((physaddr_t) (pte) & ~0xFFF)

// Page table/directory entry flags.标志位
#define PTE_P		0x001	// Present

#define PTE_W		0x002	// Writeable

#define PTE_U		0x004	// User

#define PTE_PWT		0x008	// Write-Through

#define PTE_PCD		0x010	// Cache-Disable

#define PTE_A		0x020	// Accessed

#define PTE_D		0x040	// Dirty

#define PTE_PS		0x080	// Page Size

#define PTE_G		0x100	// Global

// a physical address and returns the corresponding kernel virtual address.  
// It panics if you pass an invalid physical address. */
#define KADDR(pa) _kaddr(__FILE__, __LINE__, pa)

enum {
	// For page_alloc, zero the returned physical page.
	ALLOC_ZERO = 1<<0,
};

pte_t * pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // 获取page directory index
	uint32_t dir_idx = PDX(va);
    // 获取page table index
	uint32_t tab_idx = PTX(va); 
    // 找到该dir_entry
	pte_t *dir_entry = &pgdir[dir_idx];
	
    // 判断有效位是否为0
	if (!(*dir_entry & PTE_P)) {
		// create=false
		if (!create)
			return NULL;

		// page_alloc
		struct PageInfo *newPage = page_alloc(ALLOC_ZERO);
		// page_alloc failed
		if (newPage == NULL)
			return NULL;

		// 引用+1
		newPage->pp_ref++;
		// 根据提示1,通过page2pa把PageInfo *转变为物理地址，并且增加Present、Writeable、User的有效位
		// 加入pgdir
		*dir_entry = (pde_t)page2pa(newPage) | PTE_P | PTE_U | PTE_W;
	}
	// 通过PTE_ADDR找到page directory entry中的地址
	// 再通过KADDR转换为虚拟地址
	pte_t *ptab = (pte_t *)KADDR(PTE_ADDR(*dir_entry));
    
	// 返回指向PTE的指针
	return &ptab[tab_idx];
}

// Map [va, va+size) of virtual address space to physical [pa, pa+size)
// in the page table rooted at pgdir.  Size is a multiple of PGSIZE, and
// va and pa are both page-aligned.
// Use permission bits perm|PTE_P for the entries.
//
// This function is only intended to set up the ``static'' mappings
// above UTOP. As such, it should *not* change the pp_ref field on the
// mapped pages.
//
// Hint: the TA solution uses pgdir_walk

static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	// 首先计算页数
	// 因为Size is a multiple of PGSIZE并且va and pa are both page-aligned
	// 所以可以直接除，不用ROUNDUP
	size_t page_num = size / PGSIZE;
	for (size_t i = 0; i < page_num; i++)
	{
		// 通过pgdir_walk把映射加入pgdir
		// 由于va类型是uintptr_t，需要强制转换成void *
		pte_t *pte = pgdir_walk(pgdir, (void *)(va + i * PGSIZE), 1);
		if (pte == NULL) {
            panic("boot_map_region: pgdir_walk failed\n");
        }
		// 修改va对应的PTE的值
		*pte = (pa + i * PGSIZE) | perm | PTE_P;
	}
}

// Return the page mapped at virtual address 'va'.
// If pte_store is not zero, then we store in it the address of the pte for this page. 
// This is used by page_remove and can be used to verify page permissions for syscall arguments,
// but should not be used by most callers.
//
// Return NULL if there is no page mapped at va.
//
// Hint: the TA solution uses pgdir_walk and pa2page.

struct PageInfo * page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, 0);
	// va没有映射到物理页面
	if (pte == NULL)
		return NULL;
	if (pte_store)
		*pte_store = pte;
	return pa2page(PTE_ADDR(*pte));
}

// Address in page table or page directory entry
#define PTE_ADDR(pte)	((physaddr_t) (pte) & ~0xFFF)

// Unmaps the physical page at virtual address 'va'.
// If there is no physical page at that address, silently does nothing.
//
// Details:
//   - The ref count on the physical page should decrement.
//   - The physical page should be freed if the refcount reaches 0.
//   - The pg table entry corresponding to 'va' should be set to 0.
//     (if such a PTE exists)
//   - The TLB must be invalidated if you remove an entry from
//     the page table.
//
// Hint: The TA solution is implemented using page_lookup, tlb_invalidate, and page_decref.

void page_remove(pde_t *pgdir, void *va)
{
	// Fill this function in
	pte_t *pte;
	struct PageInfo *page = page_lookup(pgdir, va, &pte);
	// 对应物理页不存在
	if (!page)
		return;
	// 对应物理页存在
	// ref--;pte=0;invalid tlb
	page_decref(page);
	*pte = 0;
	tlb_invalidate(pgdir, va);
}

// Map the physical page 'pp' at virtual address 'va'.
// The permissions (the low 12 bits) of the page table entry should be set to 'perm|PTE_P'.
// 
// Requirements
//   - If there is already a page mapped at 'va', it should be page_remove()d.
//   - If necessary, on demand, a page table should be allocated and inserted into 'pgdir'.
//   - pp->pp_ref should be incremented if the insertion succeeds.
//   - The TLB must be invalidated if a page was formerly present at 'va'.
//
// Corner-case hint: Make sure to consider what happens when the same
// pp is re-inserted at the same virtual address in the same pgdir.
// However, try not to distinguish this case in your code, as this
// frequently leads to subtle bugs; there's an elegant way to handle
// everything in one code path.
//
// RETURNS:
//   0 on success
//   -E_NO_MEM, if page table couldn't be allocated
//
// Hint: The TA solution is implemented using pgdir_walk, page_remove, and page2pa.

int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, 1);
	if (pte == NULL)
		return -E_NO_MEM;
	pp->pp_ref++;

	if (*pte)
		page_remove(pgdir, va); // page_remove中包含无效TLB

	*pte = page2pa(pp) | perm | PTE_P;
	return 0;
}

// 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) ----/
//  \---------- PGNUM(la) ----------/

pte_t * pgdir_walk(pde_t *pgdir, const void *va, int create)

pte_t *dir_entry = &pgdir[dir_idx];

pte_t *ptab = (pte_t *)KADDR(PTE_ADDR(pgdir[dir_idx]));

return &ptab[tab_idx];

	cprintf("pgdir_walk:pgdir=0x%08x\n", pgdir);

	cprintf("pgdir_walk:dir_entry=0x%08x\n", dir_entry);

	cprintf("pgdir_walk:ptab=0x%08x\n", ptab);

	cprintf("pgdir_walk:&ptab[tab_idx]=0x%08x\n", &ptab[tab_idx]);

pd = lcr3();
pt = * (pd + 4 * PDX);
页面= * (pt + 4 * PTX);

// 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) ----/
//  \---------- PGNUM(la) ----------/
//
// The PDX, PTX, PGOFF, and PGNUM 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)).

// page number field of address
#define PGNUM(la)	(((uintptr_t) (la)) >> PTXSHIFT)

 * ULIM, MMIOBASE -->  +------------------------------+ 0xef800000
 *                     |  Cur. Page Table (User R-)   | R-/R-  PTSIZE
 *    UVPT      ---->  +------------------------------+ 0xef400000

#if JOS_USER
// 与虚拟地址范围[UVPT, UVPT + PTSIZE]相对应的页面目录条目指向页面目录本身，因此页目录被视为页表和页目录
// The page directory entry corresponding to the virtual address range
// [UVPT, UVPT + PTSIZE) points to the page directory itself.  Thus, the page
// directory is treated as a page table as well as a page directory.
// 
// 将页目录作为页表处理的结果是：
// ①所有pte都可以通过虚拟地址为UVPT的“虚拟页表”访问，第N页的PTE存储在uvpt[N]中。
// One result of treating the page directory as a page table is that all PTEs
// can be accessed through a "virtual page table" at virtual address UVPT (to
// which uvpt is set in lib/entry.S).  The PTE for page number N is stored in
// uvpt[N].  (It's worth drawing a diagram of this!)
// 
// ②当前页目录的内容将总是在虚拟地址(UVPT + (UVPT >> PGSHIFT))中
// A second consequence is that the contents of the current page directory
// will always be available at virtual address (UVPT + (UVPT >> PGSHIFT)), to
// which uvpd is set in lib/entry.S.
//
extern volatile pte_t uvpt[];     // VA of "virtual page table"
extern volatile pde_t uvpd[];     // VA of current page directory
#endif

	//////////////////////////////////////////////////////////////////////
	// Now we set up virtual memory
	
	//将pages数组映射到UPAGE地址区域以上
	//[UPAGES, UPAGES+PTSIZE)映射到页表存储的物理地址 [pages, pages+4M)，权限：PTE_U | PTE_P
	//////////////////////////////////////////////////////////////////////
	// Map 'pages' read-only by the user at linear address UPAGES
	// Permissions:
	//    - the new image at UPAGES -- kernel R, user R
	//      (ie. perm = PTE_U | PTE_P)
	//    - pages itself -- kernel RW, user NONE
	
	// 内核栈的映射
	// 这里被划分成了[KSTACKTOP-KSTKSIZE, KSTACKTOP)和[KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE)两个部分
	// 前一段需要映射到物理地址，后一段不需要
	// 通过PADDR将bootstack转换为物理地址，然后以KSTACKTOP-KSTKSIZE为起点，KSTKSIZE为大小映射
	// [KSTACKTOP-KSTKSIZE, KSTACKTOP)映射到[bootstack,bootstack+32KB)处，权限：PTE_W | PTE_P
	//////////////////////////////////////////////////////////////////////
	// Use the physical memory that 'bootstack' refers to as the kernel stack. 
	// The kernel stack grows down from virtual address KSTACKTOP.
	// We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
	// to be the kernel stack, but break this into two pieces:
	//     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
	//     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
	//       the kernel overflows its stack, it will fault rather than
	//       overwrite memory.  Known as a "guard page".
	//     Permissions: kernel RW, user NONE
	
	//映射整个内核的虚拟空间[KERNBASE, 2*32-KERNBASE)到物理地址 [0,256M)，权限：PTE_W | PTE_P
	//////////////////////////////////////////////////////////////////////
	// Map all of physical memory at KERNBASE.
	// Ie.  the VA range [KERNBASE, 2^32) should map to
	//      the PA range [0, 2^32 - KERNBASE)
	// We might not have 2^32 - KERNBASE bytes of physical memory, but
	// we just set up the mapping anyway.
	// Permissions: kernel RW, user NONE

	// Your code goes here:
	boot_map_region(kern_pgdir, UPAGES, npages * sizeof(struct PageInfo), PADDR(pages), PTE_U | PTE_P);

	// Your code goes here:
	boot_map_region(kern_pgdir, (KSTACKTOP - KSTKSIZE), KSTKSIZE, PADDR(bootstack), PTE_W | PTE_P);

	// 0xffffffff - KERNBASE为KERNSIZE
	// Your code goes here:
	boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W | PTE_P);

	//将pages数组映射到UPAGE地址区域以上
	//[UPAGES, UPAGES+PTSIZE)映射到页表存储的物理地址 [pages, pages+4M)，权限：PTE_U | PTE_P
	boot_map_region(kern_pgdir, UPAGES, npages * sizeof(struct PageInfo), PADDR(pages), PTE_U | PTE_P);

 *    UVPT      ---->  +------------------------------+ 0xef400000
 *                     |          RO PAGES            | R-/R-  PTSIZE
 *    UPAGES    ---->  +------------------------------+ 0xef000000

struct PageInfo {
	struct PageInfo *pp_link;
	uint16_t pp_ref;
};

	// 可以把PageInfo的大小打印出来
	struct PageInfo test;
	cprintf("struct PageInfo:%d\n", sizeof(test));

// A linear address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |      Index     |                     |
// +----------------+----------------+---------------------+

typedef uint32_t pte_t;
typedef uint32_t pde_t;

// kern/entrypgdir.c中的映射
__attribute__((__aligned__(PGSIZE)))
pde_t entry_pgdir[NPDENTRIES] = {
	// Map VA's [0, 4MB) to PA's [0, 4MB)
	[0]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P,
	// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
	[KERNBASE>>PDXSHIFT]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P + PTE_W
};

// The boot page table used in entry.S and entryother.S.
// Page directories (and page tables) must start on page boundaries,
// hence the __aligned__ attribute.
// PTE_PS in a page directory entry enables 4Mbyte pages.

__attribute__((__aligned__(PGSIZE)))
pde_t entrypgdir[NPDENTRIES] = {
  // Map VA's [0, 4MB) to PA's [0, 4MB)
  [0] = (0) | PTE_P | PTE_W | PTE_PS,
  // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
  [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,
};

// Bootstrap processor starts running C code here.
// Allocate a real stack and switch to it, first
// doing some setup required for memory allocator to work.
int main(void)
{
  kinit1(end, P2V(4*1024*1024)); // phys page allocator
  kvmalloc();      // kernel page table
  mpinit();        // detect other processors
  lapicinit();     // interrupt controller
  seginit();       // segment descriptors
  picinit();       // disable pic
  ioapicinit();    // another interrupt controller
  consoleinit();   // console hardware
  uartinit();      // serial port
  pinit();         // process table
  tvinit();        // trap vectors
  binit();         // buffer cache
  fileinit();      // file table
  ideinit();       // disk 
  startothers();   // start other processors
  kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
  userinit();      // first user process
  mpmain();        // finish this processor's setup
}

// Allocate one page table for the machine for the kernel address
// space for scheduler processes.
void kvmalloc(void)
{
  kpgdir = setupkvm();
  switchkvm();
}

#define PHYSTOP 0xE000000           // Top physical memory

// Set up kernel part of a page table.
pde_t* setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  if((pgdir = (pde_t*)kalloc()) == 0)
    return 0;
  memset(pgdir, 0, PGSIZE);
  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,	//调用mappages
                (uint)k->phys_start, k->perm) < 0) {
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}

// Create PTEs for virtual addresses starting at va that refer to physical addresses starting at pa. va and size might not be page-aligned.
// 这里mappages的作用是：为映射到pa的虚拟地址va创建PTE
// 类似于JOS中的boot_map_region:把虚拟地址[va, va+size)映射到物理地址[pa, pa+size]，并且把映射关系加入到页表pgdir，修改使用权限位。
static int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;

  a = (char*)PGROUNDDOWN((uint)va);
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
  for(;;){
    //对于每一个待映射的虚拟地址，调用walkpgdir找到该地址对应的PTE地址，然后保存对应的物理地址、权限。
    if((pte = walkpgdir(pgdir, a, 1)) == 0)		
      return -1;
    if(*pte & PTE_P)
      panic("remap");
    *pte = pa | perm | PTE_P;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

// 相当于JOS中的pgdir_walk()
// Return the address of the PTE in page table pgdir that corresponds to virtual address va. 
// If alloc!=0,create any required page table pages.
static pte_t * walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  pde_t *pde;
  pte_t *pgtab;

  pde = &pgdir[PDX(va)];
  if (*pde & PTE_P)
  {
    pgtab = (pte_t *)P2V(PTE_ADDR(*pde));
  }
  else
  {
    if (!alloc || (pgtab = (pte_t *)kalloc()) == 0)
      return 0;
    // Make sure all those PTE_P bits are zero.
    memset(pgtab, 0, PGSIZE);
    // The permissions here are overly generous, but they can
    // be further restricted by the permissions in the page table
    // entries, if necessary.
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
  }
  return &pgtab[PTX(va)];
}

// This table defines the kernel's mappings, which are present in every process's page table.
static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices
};

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  int use_lock;
  struct run *freelist;
} kmem;

// main() calls kinit1() while still using entrypgdir to place just
// the pages mapped by entrypgdir on free list.
// 这里的vstart就是end的地址，在JOS里也遇到过，是.bss段结束的地方
// vend是KERNBASE + 128MB = 0x86400000
// 这里就是把[vstart, 0x86400000]的内存按页(4kb大小)进行free，kree这里会把他插入到freelist中
void kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  kmem.use_lock = 0;
  freerange(vstart, vend);	//调用了freerange()
}

// main() calls kinit2() with the rest of the physical pages
// after installing a full page table that maps them on all cores.
void kinit2(void *vstart, void *vend)
{
  freerange(vstart, vend);
  kmem.use_lock = 1;
}

void freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
    kfree(p);	//调用kfree()
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(char *v)
{
  struct run *r;

  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(v, 1, PGSIZE);

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v;
  r->next = kmem.freelist;
  kmem.freelist = r;
  if(kmem.use_lock)
    release(&kmem.lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
char* kalloc(void)
{
  struct run *r;

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  if(kmem.use_lock)
    release(&kmem.lock);
  return (char*)r;
}

// xv6
// A virtual address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |      Index     |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(va) --/ \--- PTX(va) --/

// JOS
// 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) ----/
//  \---------- PGNUM(la) ----------/

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  int use_lock;
  struct run *freelist;
} kmem;

struct PageInfo {
    // pp_link指向下一个空闲页
	struct PageInfo *pp_link;
	// pp_ref表示页面被引用数，如果为0，表示是空闲页
	uint16_t pp_ref;
};

// Page table/directory entry flags.
#define PTE_P           0x001   // Present

#define PTE_W           0x002   // Writeable

#define PTE_U           0x004   // User

#define PTE_PS          0x080   // Page Size

__attribute__((__aligned__(PGSIZE)))
pde_t entrypgdir[NPDENTRIES] = {
  // Map VA's [0, 4MB) to PA's [0, 4MB)
  [0] = (0) | PTE_P | PTE_W | PTE_PS,
  // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
  [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,	//标记超级页
};

// Page table/directory entry flags.
#define PTE_P		0x001	// Present

#define PTE_W		0x002	// Writeable

#define PTE_U		0x004	// User

#define PTE_PWT		0x008	// Write-Through

#define PTE_PCD		0x010	// Cache-Disable

#define PTE_A		0x020	// Accessed

#define PTE_D		0x040	// Dirty

#define PTE_PS		0x080	// Page Size

#define PTE_G		0x100	// Global

__attribute__((__aligned__(PGSIZE)))
pde_t entry_pgdir[NPDENTRIES] = {
	// Map VA's [0, 4MB) to PA's [0, 4MB)
	[0]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P,
	// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
	[KERNBASE>>PDXSHIFT]
		= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P + PTE_W
};

// This table defines the kernel's mappings, which are present in every process's page table.
static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices
};