「MIT 6.828」MIT 6.828 Fall 2018 lab2

// 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.
//由于已经开启了分页机制，并且只在[0,4KM]和[KERNBASE,KERNBASE+4MB]设置了页表，所以在这之外的虚拟内存无法映射，会out of memory。
//如下是分配连续的kernel虚拟空间。
static void *
boot_alloc(uint32_t n)
{
	//注意这个变量是staic变量，存储在.data区,长期存在且维护。
	static char *nextfree;	// virtual address of next byte of free memory, 这里存储了下一个空位置，直接在这里分配后再移动该指针到下一个空位置
	char *result;

	// Initialize nextfree if this is the first time.
	// 'end' is a magic symbol automatically generated by the linker,
	// which points to the end of the kernel's bss segment:
	// the first virtual address that the linker did *not* assign
	// to any kernel code or global variables.
	if (!nextfree) {
		extern char end[];
		nextfree = ROUNDUP((char *) end, PGSIZE);  //也就是下一个空闲的page位置在kernel的bss段后的第一个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;
	}
	if(n>0){
        if (PADDR(nextfree) + n > (npages + 1) * PGSIZE) {
        	panic("out of memory\n");
    	}  
		char * nowalloc = nextfree;
		nextfree = nextfree + n;
		nextfree = ROUNDUP(nextfree,PGSIZE);
		return nowalloc;
	}
	
	return NULL;
}

  //由于初始的entry_pgdir是将虚拟地址[KERNBASE, KERNBASE+4MB)和[0, 4MB)映射到了物理地址空间[0, 4MB)，因此通过将高地址虚拟空间的kernel地址-KERNBASE，就可以转换为物理内存下的kernel地址空间
  //故这个宏为takes a kernel virtual address-> returns the corresponding physical address
  /* This macro takes a kernel virtual address -- an address that points above
   * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
   * and returns the corresponding physical address.  It panics if you pass it a
   * non-kernel virtual address.
   */
  #define PADDR(kva) _paddr(__FILE__, __LINE__, kva)
  
  static inline physaddr_t
  _paddr(const char *file, int line, void *kva)
  {
  	if ((uint32_t)kva < KERNBASE)
  		_panic(file, line, "PADDR called with invalid kva %08lx", kva);
  	return (physaddr_t)kva - KERNBASE;
  }

//在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.
	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.

	uint16_t pp_ref;
};


//在pmap.c中定义
// These variables are set by i386_detect_memory()
size_t npages;			// Amount of physical memory (in pages)
static size_t npages_basemem;	// Amount of base memory (in pages)

// These variables are set in mem_init()
pde_t *kern_pgdir;		// Kernel's initial page directory
struct PageInfo *pages;		// Physical page state array
static struct PageInfo *page_free_list;	// Free list of physical pages

n = sizeof(struct PageInfo) * npages;
pages = (struct PageInfo*)boot_alloc(n);
memset(pages,0,n);

//主要是判断哪些page是free的，哪些是in use的。

// --------------------------------------------------------------
// Tracking of physical pages.
// The 'pages' array has one 'struct PageInfo' entry per physical page.
// Pages are reference counted, and free pages are kept on a linked list.
// --------------------------------------------------------------
//追踪物理内存，pages 保存的每一个页的信息，有些页实际上是不能用的。
//
// Initialize page structure and memory free list.初始化页面结构和空闲内存
// After this is done, NEVER use boot_alloc again.  ONLY use the page
// allocator functions below to allocate and deallocate physical
// memory via the page_free_list.
//从这以后 就再也不会用 boot_alloc【只能紧挨着kernel结尾分配连续的内存页】，只有page分配函数在 page_free_list 上面进行操作了.
//也就是说在这个函数执行以后，就从page_free_list体现出了哪些内存是空闲的，只能在空闲的内存中进行分配。
void
page_init(void)
{
	// 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.  比如第0号页存了实模式下面的IDT（中断向量表）和BIOS。不可以再将第0页内存进行分配
	//     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. 除去第0页之后，从第一个起到base memory的结尾是可以用的。
	//  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
	//     never be allocated. 之后有一块是给IO用的，这段内存空洞不能分配。
	//  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!
	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]; //注意这个page_free_list是倒序连接的，也就是说分配内存的时候，会先使用extended memory，才会使用到base memory。
        //NULL<-[0]<-[1]<-[2]<-……<-page_free_list
	}
	// 根据上面他给的提示写，1)0号页是实模式的IDT和BIOS不应该添加到空闲页，所以
	pages[1].pp_link=pages[0].pp_link; //即next指向page_free_list
	pages[0].pp_ref = 1;//可以随意设置，因为这个页都没有进free list，永远都不可能用去分配。【如果某个页是free，才会用到】
	pages[0].pp_link=NULL; //表示in use
	//2)是说那一块可以用，也就是上一次实验说的低地址，所以不用做修改,也就是保持page 1~ page npages_basemem
	//3)存IO的那一块不能分配，地址是从[IOPHYSMEM,EXTPHYSMEM)
	size_t range_io=PGNUM(IOPHYSMEM),range_ext=PGNUM(EXTPHYSMEM); //PGNUM宏，就是参数/PGSIZE。
	pages[range_ext].pp_link=pages[range_io].pp_link;
	for (i = range_io; i < range_ext; i++) pages[i].pp_link = NULL;  //IO使用的内存全部设置为已分配,不在free list中

	//4)在extended memory中分配了一些内存页面给内核，其后还有已经被分配的kern_pgdir和pages【即之前是分配的内核页目录，和为每个页分配数据结构】。直接 找到了boot_alloc(0),瞬间明白..这个直接把页表的空间也算上去了，所以准确来说应该是内核+页表+页目录的内存（可能内核包括页表和页目录..）。
	size_t free_top = PGNUM(PADDR(boot_alloc(0))); //boot_alloc两次，得到的下一个free的位置。
	pages[free_top].pp_link = pages[range_ext].pp_link;
	for(i = range_ext; i < free_top; i++) pages[i].pp_link = NULL; //包括kernel、kernel page table directory和pages结构所在的区域都设置为不可再分配。
}
//注意：kernel是在extended memory的起始位置1MB=0x100000物理地址开始装载的。

//其他的实现方式    
    pages[0].pp_ref = 1;
    pages[0].pp_link = page_free_list; // null
    for (i = 1; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    int npages_extmem = EXTPHYSMEM/PGSIZE;
    int npages_freeextmem = ((uint32_t)(struct PageInfo *)(pages + npages)-KERNBASE)/PGSIZE; //-KERNBASE转换为物理地址空间【是手动kernel空间页表地址转换】
    for ( int i = npages_freeextmem ; i < npages ; i++)
    {
        pages[i].pp_ref = 0 ;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }

struct PageInfo *
page_alloc(int alloc_flags)
{
    if (!page_free_list) return NULL;
    struct PageInfo* ret = page_free_list;
    page_free_list = page_free_list->pp_link;
    ret -> pp_link = NULL;
    memset(page2kva(ret),0,PGSIZE);//因为现在已经开起来页表地址转换【设置了cr0和cr3】，因此需要用虚拟地址操作地址空间的赋值等，这样cpu才能正确切换/转换。
    if (alloc_flags & ALLOC_ZERO)
    {
        memset(page2kva(ret),'\0',PGSIZE);
    }
    // cprintf("ret:x\n",ret);
    return ret;
}
//间接调用了KADDR和page2pa进行地址转换
static inline void*
page2kva(struct PageInfo *pp) //根据PageInfo，得到该页的虚拟地址【必须是位于kernel空间的页，才可以这样转换】
{
	return KADDR(page2pa(pp));
}
//将物理地址转换为内核虚拟地址，即+KERNBASE	
/* This macro takes 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)
static inline void*
_kaddr(const char *file, int line, physaddr_t pa)
{
	if (PGNUM(pa) >= npages)
		_panic(file, line, "KADDR called with invalid pa %08lx", pa);
	return (void *)(pa + KERNBASE);
}

static inline physaddr_t
page2pa(struct PageInfo *pp) 
{
	return (pp - pages) << PGSHIFT;  //根据当前PageInfo和pages的距离，得到是第几个页，再左移12位，得到当前页的物理基地址
}
#define PGSHIFT		12		// log2(PGSIZE)【PGSIZE=2^12】

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!=0 || pp->pp_link)
    { //要求free的指针不为空，且指向该该空间的指针数=0
        panic("page_free: pp_ref is nonzero or pp_link is not NULL");
    }
    // how to return something in a void function?
    // 相当于在链表头插入一个节点
    pp->pp_link = page_free_list;
    page_free_list = pp ;
}

// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
// a pointer to the page table entry (PTE) for linear address 'va'.
// This requires walking the two-level page table structure.
//
// The relevant page table page might not exist yet.【通过pgdir中表项的Present bits】
// If this is true, and create == false, then pgdir_walk returns 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.
//
// Hint 1: you can turn a PageInfo * into the physical address of the
// page it refers to with page2pa() from kern/pmap.h.
//
// Hint 2: the x86 MMU checks permission bits in both the page directory
// and the page table, so it's safe to leave permissions in the page
// directory more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that manipulate page
// table and page directory entries.
//给定一个页目录表指针 pgdir ，该函数应该返回线性地址va所对应的页表项指针。
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{   //va是线性地址
	// Fill this function in
	assert(pgdir);  //pgdir没有present bit，如果某个任务被调度，一定会保证pg dir被正确设置。【详见参考Present Bit第三段】
	//如果pgdir不为空。那么还需要考虑页表为空和不为空两种情况。
	//为空时，如果create不为false，那么就要创建新的页表
	//参考inc/mmu.h中可用的宏，便于得到各个字段
    
    pde_t *pde = &pgdir[PDX(va)]; //首先获取va线性地址对应的页目录项的entry指针
    if (!(*pde & PTE_P)) { //读取pgdir_entry的PTE_P位【主要是用于表示当前这个entry是否可用，是否存在，详见参考】，如果不存在
        if (!create) return NULL;  //且不允许创建新的，直接return NULL
        struct PageInfo *page = page_alloc(ALLOC_ZERO);   //如果运行创建，就建立新的page table【每张page table的大小就是一个页面】
        if (!page) return NULL;  //分配失败返回NULL
        assert(page->pp_ref == 0);  //初次分配的页面引用应该位0
        page->pp_ref++;       //页面被分配后引用+1
        assert(page->pp_link == NULL);  //已经不在page_free_list中了,pp_link字段无效
        *pde = page2pa(page) | PTE_P | PTE_U | PTE_W;  //在pgdir中的条目写入page table的基地址【物理地址】和权限位，PTE_W[Read/write access]、PTE_U[User level]【详见参考】
    }
    // 获取页表项
    return (pte_t*)(KADDR(PTE_ADDR(*pde))) + PTX(va); //*pde读取va在pgdir对应的表项，PTE_ADDR(pte)为表项去掉权限位得到的页表物理基地址，KADDR(PTE_ADDR(*pde))为va对应页表的虚拟地址，(pte_t*)(KADDR(PTE_ADDR(*pde))) + PTX(va)为页表中va对应页表项的指针【指向虚拟地址的指针】。
}

// Address in page table or page directory entry 【from inc/imm.h】
#define PTE_ADDR(pte)	((physaddr_t) (pte) & ~0xFFF)

static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	size_t pgs = size / PGSIZE;    
	if (size % PGSIZE != 0) {
		pgs++;
	}                            //计算总共有多少页
	for (int i = 0; i < pgs; i++) {
		pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);//获取va对应的PTE的地址
		if (pte == NULL) {
			panic("boot_map_region(): out of memory\n");
		}
		*pte = pa | PTE_P | perm; //修改va对应的PTE的值，也就是在二级页表里面设置va对应于pa【由于两者都是页对齐，因此是虚拟基地址和物理基地址，不需要额外清空pa的低位】。
		pa += PGSIZE;             //更新pa和va，进行下一轮循环
		va += PGSIZE;
	}
}

// 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,(const void*)va,false); //如果对应的页表不存在，不进行创建,因为这里只是查找
	if(pte==NULL)
		return NULL;
	if(!(*pte & PTE_P)){
		return NULL;
	}

	struct PageInfo* retpp = pa2page(PTE_ADDR(*pte));
	if(pte_store!=NULL){
		*pte_store = pte; 
	}
	return retpp;
}

// 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 = NULL;
	struct PageInfo* pp= page_lookup(pgdir,va,&pte);
	if(!pp)
		return;
	*pte = 0;  //这个页对应的页表项应该被置0
	page_decref(pp); //free and decrease pp_ref here
	tlb_invalidate(pgdir,va);
}

//相关函数：
//
// Decrement the reference count on a page,
// freeing it if there are no more refs.
//
void
page_decref(struct PageInfo* pp)
{
	if (--pp->pp_ref == 0)  //当减少一个虚拟页映射到这个物理页时，ref--。
		page_free(pp);     //当完全没有虚拟页对应这个物理页时，才考虑free这个物理页到page_free_list中
}

// 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,(const void *)va,true); //拿到va对应的PTE地址，如果va对应的页表还没有分配，则分配一个物理页作为页表
	if(pte==NULL){
		return -E_NO_MEM;
	}
    pp->pp_ref++; //这里要注意，pp->pp_ref++这条语句，一定要放在page_remove之前，这是为了处理一种特殊情况：pp已经映射到va上了。
	if(*pte & PTE_P){
		page_remove(pgdir,va); //如果这个va，已经映射到pp了，而且是唯一的映射。那么在remove的时候，会检查pp_ref是否为0，如果为0，那么va对应的物理页，也就是pp，就会被回收到page_free_list中。这时候释放了之后需要再被映射的pp页。故需要提前将pp_ref++，避免pp被回收。
	}
	*pte = page2pa(pp) | PTE_P | perm;
	tlb_invalidate(pgdir,va);

	return 0;
}

//////////////////////////////////////////////////////////////////////
	// 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
	// Your code goes here:
	// 在kern_pgdir页目录下进行设置，将虚拟地址的UPAGES映射到物理地址pages数组开始的位置
	boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U); //boot_map_region中自带会设置PTE_P权限
//内核虚拟内存中存储的pages是内核可以修改变动的【实际对应的物理地址在低端位置，是内核.bss段之后的一小块物理区域，由boot_alloc和人工构建的初始线性页目录和页表：entry_pgdir及entry_pgtable负责分配和管理】。
//这里把pages再映射到UPAGES的位置，设置权限位PTE_U【for applications procedures and data.】和有效位PTE_P，但是没有其他权限
//在地址范围[ UTOP，ULIM ]中，用户和内核都可以访问。
//而UPAGES包含在其中，但是用户访问时，该位置不具备WX权限，只可R。
//但是kernel中的pages【位于高地址的内核虚拟空间】是具备RW权限的【因为人工构建的初始线性页目录和页表设置了PTE_W权限】
//也就是说内核可以访问UPAGES空间，得到通过这里设置的map找到物理pages，也可以通过在内核虚拟空间读取pages，通过entry_pgdir及entry_pgtable找到物理地址的pages。
//但是用户只能通过访问UPAGES空间，找到pages，且只能R。
//默认PTE_P的表项只可R/W bits为0，即为可读。如果设置了W则可读写。

//////////////////////////////////////////////////////////////////////
	// 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
	// Your code goes here:
	// 'bootstack'定义在/kernel/entry.
	boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);

//////////////////////////////////////////////////////////////////////
	// 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.
//原来的初始人工页表是VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
//现在设置为VA's [KERNBASE, 2^32) to PA's [0, 2^32 - KERNBASE)
//也就是现在的映射涵盖了之前的初始映射，权限不变依旧是PTE_P|PTE_W
	// Permissions: kernel RW, user NONE
	// Your code goes here:
	boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);