6.828 Lab2
Background
在lab1中，boot的时候，把jos的ELF文件load到了内存中，这个时候，还没有建立jos所需要运行的页表，同时此时已经进入了保护模式，jos最开始会运行kern/entry.S 中的代码。这个代码只做了一件事情，就是建立了一个临时的页表，把VA的[0,4MB]和[KERNBASE, KERNBASE+4MB]映射到PA的[0,4MB]。
因为jos的ELFload到内存中，因为jos的代码需要运行在VA的KERNBASE + 1MB，所以这样的映射是足够的.在kern/entry.S把临时的页表安装好之后，会跳转到kern/init.c的i386_init()函数继续执行。
lab2要做的事情
在跳转到i386_init()之后，首先会进行一些初始化，比如把load到内存中的BSS段都memset为0，然后进入kern/pmap.c 的mem_init()中，lab2做的事情也是设计pmap.c的，lab2做这么几个事情:
- 初始化jos的页表(因为之前使用的是一个临时的页表，只能在[KERNBASE, KERNBASE+4MB]的虚拟地址上运行。其中包括对物理页的初始化。
- 给jos添加页表管理的函数：page_alloc, page_free, page_lookup, page_insert, pgdir_walk等。根据我的理解，所谓的操作系统上的内存管理，其实就是这些页表的管理，还有一些物理页的管理。
- 用2中实现的页表管理函数，初始化jos的整个memory layout.
好吧，因为这个memory layout太重要了，所以就贴在这里了，下面的这个memory layout不是linux kernel的，是jos的，不要看错了。
*
* Virtual memory map: Permissions
* kernel/user
*
* 4 Gig --------> +------------------------------+
* | | RW/--
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* : . :
* : . :
* : . :
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
* | | RW/--
* | Remapped Physical Memory | RW/--
* | | RW/--
* KERNBASE, ----> +------------------------------+ 0xf0000000 --+
* KSTACKTOP | CPU0's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| |
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* | CPU1's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| PTSIZE
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* : . : |
* : . : |
* MMIOLIM ------> +------------------------------+ 0xefc00000 --+
* | Memory-mapped I/O | RW/-- PTSIZE
* ULIM, MMIOBASE --> +------------------------------+ 0xef800000
* | Cur. Page Table (User R-) | R-/R- PTSIZE
* UVPT ----> +------------------------------+ 0xef400000
* | RO PAGES | R-/R- PTSIZE
* UPAGES ----> +------------------------------+ 0xef000000
* | RO ENVS | R-/R- PTSIZE
* UTOP,UENVS ------> +------------------------------+ 0xeec00000
* UXSTACKTOP -/ | User Exception Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebff000
* | Empty Memory (*) | --/-- PGSIZE
* USTACKTOP ---> +------------------------------+ 0xeebfe000
* | Normal User Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebfd000
* | |
* | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* . .
* . .
* . .
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
* | Program Data & Heap |
* UTEXT --------> +------------------------------+ 0x00800000
* PFTEMP -------> | Empty Memory (*) | PTSIZE
* | |
* UTEMP --------> +------------------------------+ 0x00400000 --+
* | Empty Memory (*) | |
* | - - - - - - - - - - - - - - -| |
* | User STAB Data (optional) | PTSIZE
* USTABDATA ----> +------------------------------+ 0x00200000 |
* | Empty Memory (*) | |
* 0 ------------> +------------------------------+ --+
*
* (*) Note: The kernel ensures that "Invalid Memory" (ULIM) is *never*
* mapped. "Empty Memory" is normally unmapped, but user programs may
* map pages there if desired. JOS user programs map pages temporarily
* at UTEMP.
*/
mem_init 做的事情
1. 有多少个物理页
在mem_init()中首先进入i386_detect_memory()，记录有多少个物理页，在这里注意有个io_hole :
+---------------------------------------+
|base_mem | io_hole | ext_mem |
+---------------------------------------+
pa 0 640k 1024k
所以说npages 和 npages_basemem + npages_extmem是相差384k大小。
2. 分配kern_pgdir
然后，通过boot_alloc函数，在bss后面分配一个PGSIZE大小的空间，作为kern_pgdir ( kernel的page directory)。 关于boot_alloc函数：这个函数只是在初始化kernel的页表的时候使用，注意一点：
因为这个时候jos还是跑在之前设定的[KERNBASE, KERNBASE+4MB]的地址空间上，使用的页表也是之前entrypgdir.c中设定的页表，所以分配的虚拟地址是有限的只能在KERNBASE 到 KERNBASE+4MB这个范围内。
3. 在kern_pgdir中插入一条 VA 未UVPT 到 kern_pgdir所在的PA的映射
kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;
UVPT : user virtual page table , 对 USER 是 RO 的。 另外还要注意这里的PADDR，因为jos的程序是运行在虚拟地址空间上的，所以kern_pgdir的值也是一个虚拟地址，不是实际的物理地址，因为当前使用的页表还是在ELF执行的时候最开始设置的页表，所以PADDR(kern_pgdir) 就是把 kern_pgdir - KERNBASE。
4. 非配所有管理物理页元数据数组 pages
物理页元数据:
/*
* 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;
};
kernel管理的物理页数组：
struct PageInfo *pages; // Physical page state array
//////////////////////////////////////////////////////////////////////
// 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.
// Your code goes here:
pages = (struct PageInfo *)boot_alloc(sizeof(struct PageInfo) * npages);
PageInfo 和 physical address 的转换：
static inline physaddr_t
page2pa(struct PageInfo *pp)
{
return (pp - pages) << PGSHIFT;
}
static inline struct PageInfo*
pa2page(physaddr_t pa)
{
if (PGNUM(pa) >= npages)
panic("pa2page called with invalid pa");
return &pages[PGNUM(pa)];
}
pages 既是一个数组，也是一个链表。 需要进行pa和pageinfo的映射的时候，那么就是数组，需要管理page_free_list的时候，通过pp_link，就能把数组中的一些值链接起来，就是链表。不得不感叹jos中代码的精巧。。。空间没有一点浪费。
5. 物理页数组npages的初始化
标记那些物理页已经使用了，同时把没有使用的物理页通过pp_link链接起来，用page_free_list管理。注意，在bss之后分配的物理页，都是用boot_alloc分配的，boot_alloc函数中又一个static 的变量 nextfree，这个变量指向下一个没有使用的连续的物理页，通过这个变量可以知道bss之后的物理页，那些使用了，那些没有使用。 注意IOHOLE必须标记为使用过的。
6. 根据虚拟地址的memory_layout 在kern_pgdir中插入对应的页表项
7. 使用新的页表 kern_pgdir 和重新设置一些flag
lcr3(PADDR(kern_pgdir));
....
页表管理函数
注意两点：
在jos的代码运行的时候，都是运行在虚拟地址空间上的，指针都是虚拟地址，一个指针指向的值也是一个虚拟的地址，不是物理地址。在jos中，为了区分虚拟地址和物理地址：
// Pointers and addresses are 32 bits long.
// We use pointer types to represent virtual addresses,
// uintptr_t to represent the numerical values of virtual addresses,
// and physaddr_t to represent physical addresses.
typedef int32_t intptr_t;
typedef uint32_t uintptr_t;
typedef uint32_t physaddr_t;
所以在给指针本身赴值的时候，需要谨慎。如，在pgdir_walk函数中:
// 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.
// 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 Page * 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
// more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that mainipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
pde_t *pde;
pte_t *pgtab;
struct PageInfo *pp;
pde = &pgdir[PDX(va)];
if (*pde & PTE_P) {
pgtab = (pte_t*)KADDR(PTE_ADDR(*pde));
} else {
if (!create || (pp = page_alloc(ALLOC_ZERO)) == 0)
return 0;
pp->pp_ref = 1;
pgtab = (pte_t*)KADDR(page2pa(pp));
*pde = PADDR(pgtab) | PTE_P | PTE_W | PTE_U;
}
return &pgtab[PTX(va)];
}
在给pgtab赋值的时候，pgtab指向的是一个虚拟地址，然后通过h/w的mmu的转换，能够将pgtab指向的虚拟地址映射到我们想要让他映射到的实际的物理地址上就需要做KADDR这样的转换。
在page_insert中的一个trick : 如果已经有一个page 映射在va上，那么需要先将这个page删除掉，但是如果page_insert同一个va很多次的时候，每次都要删除这个page，更优雅的做法:
(pp-> pp_ref) ++;
if (*pte & PTE_P )
page_remove(pgdir, va);
— EOF —