这一部分任务就是完成5个函数
做之前，要先分析一下内存分布和地址转换的内容。这些内容都是我做的时候边做边摸索的，遇到做不下去，就观察一下查一查；如果不明白下面这些的话，这几个函数是完不成的。如果想直接看答案，这部分可以跳过。
下面是lab1里面就介绍了的内存分布。
+------------------+ <- 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
小于640KB的部分，即小于0x000A0000的部分，叫做low memory。
在0x000A0000~0x00100000之间的部分，是VGA显示设置字段、扩展ROM字段、BIOS ROM字段。
从0x00100000，即1MB部分开始向上，就是内核被加载到的物理地址，实验文档中是(where the boot loader loaded the kernel into physical memory)。虚拟地址对应于0xf0100000，映射到物理地址0x00100000。
页表项采用线性表来存储。
具体地说，每一张页表都对应有一个结构体，记录当前页的使用情况，和下一张空闲页表结构体的地址（如果当前页已被使用，就设置为指向NULL）。同时，有一个指向第一张空闲页表的结构体的指针。通过这个指针，和结构体中指向下一个空闲页表的地址，我们就能得到一个包含所有空闲页表的单链表。
这个页表的结构体见下，在/home/yichuan/6.828/lab/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.
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;
};
指向空闲页表结构体的指针见下，在/home/yichuan/6.828/lab/kern/pmap.c。
static struct PageInfo *page_free_list; // Free list of physical pages
pplink就是指向下一张空闲页表结构体的指针，ppref就是表示是否对应页已被使用。
有一个结构体数组用来保存所有的页表结构体，pages，后续page_init()函数中还要写这个数组。
之后问题就来了：要我写的话，数组结构体中我除了包含pplink和ppref之外，还要包含一个指向对应页的指针，来对结构体对应的页面进行操作。这个指针应该是必不可少的，但是这里显然没有。我一直往下做，做到了page_alloc()函数，发现了这个问题，发现如果搞不懂的话就做不下去了。
最后发现，没有这个对应页的指针，是因为使用其他方法同样可以得到映射关系。这个映射就是，直接通过page_free_list，减去pages（就是结构体数组的首地址），得到当前结构体在数组中的索引，将这个索引左移12位，得到一个页的起始地址（因为显然为212的倍数，而一页大小即212），这就是这个结构体映射到的页的物理地址。但是，由于这个内核程序默认按虚拟地址处理地址，所以还要将物理地址转换为虚拟地址。物理地址转换成虚拟地址很简单，直接加个0xf0000000就可以了。这就是由页表结构体转换得到对应物理页的过程。
这是页表项的结构，来自于/home/yichuan/6.828/lab/inc/mmu.h
// 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)).
这是一个二级页表，但也可以理解为，前20位为页号，后12位为页内偏移。
// 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;
// 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);
}
// 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;
else if (n > 0) {
result = nextfree;
nextfree += ROUNDUP(n, PGSIZE); //如果n大于零，就这么搞。注意这里res和nex的用法，nex始终指向被分配出来的空白空间的开头，而nex始终指向被分配空间的结尾，就象这里，可以对指针直接加整型数，来表示指针的移动和分配空间
return result;
}
return NULL;
}
boot_alloc函数在提示上也说了，这是在未设置虚拟内存系统时使用的分配函数，在设置了虚拟内存系统后，page_init才是实际的分配函数。读一下英文提示，仿照一下他给出的nextfree为空时的代码，写起来不难。
但是要注意end[]。英文提示中说，“end是一个由链接器自动生成的魔数符号，指向kernel的bss段的结尾：第一个没有被链接器分配给任何内核代码和全局变量的地址”。
结合后面我们补充的代码，可以知道，boot_alloc分配保证了每次系统初始化时分配总是从end[]开始，所以后面我用来调试的代码分配内存时，也都是保证了都在0xf0000000之后，或者范围再小一点，都在end[]之后；写一个C程序测试malloc的分配，会发现每次分配的地址就不是都在0xf0000000之后，波动范围要宽得多，但是以xv6内核上面的结果推知，这个分配也应该是在我们测试的linux操作系统的end[]之后。
上面已经说了pages的含义了，按照英文提示，这里就是直接分配一个页表结构体数组，再对这个结构体数组使用memset初始化即可。
//
// 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(sizeof(struct PageInfo) * npages);
memset(pages, 0, sizeof(struct PageInfo) * npages);
看英文说明，由于内存各个部分有的已被使用，有的未被使用，所以分配时要注意区间，英文提示中已经给出了分配区间。
实践中发现，不能分配的部分不用处理，只要标记可分配部分的标记位为pp_ref=0即可。如何设置为可分配的代码原始程序中已经提供，照着写就行了。
npages_basemem = basemem / (PGSIZE / 1024); //表示basemem中有多少个页,basemem指的是最低的640K内存
但是问题在于，EXTPHYSMEM之后的起始代码如何设置。其实使用bootalloc分配时，就可以确定ext部分从哪里开始可以分配内存，之后使用PGNUM
#define PGNUM(la) (((uintptr_t) (la)) >> PTXSHIFT) //由地址得到页号
而PADDR宏定义见下，在/home/yichuan/6.828/lab/kern/pmap.h
#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;
}
则ext段如何处理就有答案了：先使用bootalloc分配内存，返回一个指向虚拟地址的指针，再使用PADDR得到分配位置的物理地址（xv6的地址转换比较简单，虚拟地址 - 内核加载到的虚拟地址基址，就是物理地址），最后使用PGNUM将物理地址重新转换为页号（右移12位即可），即得到在对应页结构体在页表结构体数组中的索引，可以用这个索引来进行初始化。
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.
// 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!
//看上面的说明能看个差不多，关键是EXTPHYSMEM之后的内存空间用什么来确定。
size_t i;
for (i = 1; i< npages_basemem; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
//这两个宏在头文件里有，阅读源码时就需要理解，所以直接拿来用。
for (i = PGNUM(PADDR(boot_alloc(0))); 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)
{
// Fill this function in
if (page_free_list == NULL) return NULL;
struct PageInfo* res = page_free_list;
//cprintf("\n\npage_free_list: %x\n", page_free_list);
page_free_list = page_free_list->pp_link;
//cprintf("res: %x\n", res);
//cprintf("pp-pages: %x\n",page2pa_test(res));
//cprintf("page2pa(pp): %x\n",page2pa(res));
res->pp_link = NULL;
if (alloc_flags & ALLOC_ZERO)
memset(page2kva(res), '\0', PGSIZE);
//cprintf("res after transmit: %x\n\n\n", res);
return res;
}
我试过，res->pp_ref不能赋值为1，直接不用管就行了，赋值为0也可以；不能memset不执行就else将res = NULL，这样也过不了测试。
为了弄清楚页表结构，我用了上述cprintf测试语句进行测试。同时，在/home/yichuan/6.828/lab/kern/pmap.h中加入函数page2pa_test()，见下。
static inline physaddr_t
page2pa_test(struct PageInfo *pp)
{
cprintf("pp: %x\n",pp);
cprintf("pages: %x\n",pages);
cprintf("sizeof( PageInfo): %x\n",sizeof(struct PageInfo));
return pp - pages;
}
测试后发现，一个页表结构体占8字节，即指针减法res - pages = 地址之差 * 8，
下面是page2kva函数
static inline void*
page2kva(struct PageInfo *pp)
{
return KADDR(page2pa(pp));
}
将物理地址转换成内核虚拟地址，KADDR宏见下。
#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); //KERNBASE = 0xF0000000
}
page2pa(pp)定义如下，可以看到，就是上文页表结构部分所说，结构体索引左移12位，即得页面实际存储位置的物理地址，这就是页结构体与页面本身的映射方式。
static inline physaddr_t
page2pa(struct PageInfo *pp)
{
return (pp - pages) << PGSHIFT;
}
那么全流程就清楚了：使用pagefreelist得到一个空闲页表项赋给res，之后pagefreelist更新；使用page2kva得到页表结构体对应页面的内核虚拟地址，memset赋值，返回res即可。
看好英语提示就解决了：将一个页返回freelist。由于上文已经说过，空闲页按单链表方式存储，所以这样写。
//
// 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 || pp->pp_link) panic("Page isn't empty!\n");
pp->pp_link = page_free_list;
page_free_list = pp;
}
下面是来自于/home/yichuan/6.828/lab/inc/memlayout.h文件中的虚拟内存分布图。
/*
* 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" 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.
*/