· 7 years ago · Dec 07, 2018, 07:16 PM
1/* see copyright for copyright information. */
2
3#include <inc/x86.h>
4#include <inc/mmu.h>
5#include <inc/error.h>
6#include <inc/string.h>
7#include <inc/assert.h>
8
9#include <kern/pmap.h>
10#include <kern/kclock.h>
11
12// These variables are set by i386_detect_memory()
13size_t npages; // Amount of physical memory (in pages)
14static size_t npages_basemem; // Amount of base memory (in pages)
15
16// These variables are set in mem_init()
17pde_t *kern_pgdir; // Kernel's initial page directory
18struct PageInfo *pages; // Physical page state array
19static struct PageInfo *page_free_list; // Free list of physical pages
20
21
22// --------------------------------------------------------------
23// Detect machine's physical memory setup.
24// --------------------------------------------------------------
25
26static int
27nvram_read(int r)
28{
29 return mc146818_read(r) | (mc146818_read(r + 1) << 8);
30}
31
32static void
33i386_detect_memory(void)
34{
35 size_t basemem, extmem, ext16mem, totalmem;
36
37 // Use CMOS calls to measure available base & extended memory.
38 // (CMOS calls return results in kilobytes.)
39 basemem = nvram_read(NVRAM_BASELO);
40 extmem = nvram_read(NVRAM_EXTLO);
41 ext16mem = nvram_read(NVRAM_EXT16LO) * 64;
42
43 // Calculate the number of physical pages available in both base
44 // and extended memory.
45 if (ext16mem)
46 totalmem = 16 * 1024 + ext16mem;
47 else if (extmem)
48 totalmem = 1 * 1024 + extmem;
49 else
50 totalmem = basemem;
51
52 npages = totalmem / (PGSIZE / 1024);
53 npages_basemem = basemem / (PGSIZE / 1024);
54
55 cprintf("Physical memory: %uK available, base = %uK, extended = %uK\n",
56 totalmem, basemem, totalmem - basemem);
57}
58
59
60// --------------------------------------------------------------
61// Set up memory mappings above UTOP.
62// --------------------------------------------------------------
63
64static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm);
65static void check_page_free_list(bool only_low_memory);
66static void check_page_alloc(void);
67static void check_kern_pgdir(void);
68static physaddr_t check_va2pa(pde_t *pgdir, uintptr_t va);
69static void check_page(void);
70static void check_page_installed_pgdir(void);
71
72// This simple physical memory allocator is used only while JOS is setting
73// up its virtual memory system. page_alloc() is the real allocator.
74//
75// If n>0, allocates enough pages of contiguous physical memory to hold 'n'
76// bytes. Doesn't initialize the memory. Returns a kernel virtual address.
77//
78// If n==0, returns the address of the next free page without allocating
79// anything.
80//
81// If we're out of memory, boot_alloc should panic.
82// This function may ONLY be used during initialization,
83// before the page_free_list list has been set up.
84static void *
85boot_alloc(uint32_t n)
86{
87 static char *nextfree; // virtual address of next byte of free memory
88 char *result;
89
90 // Initialize nextfree if this is the first time.
91 // 'end' is a magic symbol automatically generated by the linker,
92 // which points to the end of the kernel's bss segment:
93 // the first virtual address that the linker did *not* assign
94 // to any kernel code or global variables.
95 if (!nextfree) {
96 extern char end[];
97 nextfree = ROUNDUP((char *) end, PGSIZE);
98 }
99
100 // Allocate a chunk large enough to hold 'n' bytes, then update
101 // nextfree. Make sure nextfree is kept aligned
102 // to a multiple of PGSIZE.
103 //
104 // LAB 2: Your code here.
105 if((uint32_t)nextfree > KERNBASE+4*1024*1024)
106 panic("boot_alloc: OUT OF MEMORY!");
107 result = nextfree;
108 if(n>0){
109 nextfree = ROUNDDOWN(nextfree + n + PGSIZE, PGSIZE);
110 }
111
112 return result;
113 //return NULL;
114}
115
116// Set up a two-level page table:
117// kern_pgdir is its linear (virtual) address of the root
118//
119// This function only sets up the kernel part of the address space
120// (ie. addresses >= UTOP). The user part of the address space
121// will be set up later.
122//
123// From UTOP to ULIM, the user is allowed to read but not write.
124// Above ULIM the user cannot read or write.
125void
126mem_init(void)
127{
128 uint32_t cr0;
129 size_t n;
130
131 // Find out how much memory the machine has (npages & npages_basemem).
132 i386_detect_memory();
133
134 // Remove this line when you're ready to test this function.
135 //panic("mem_init: This function is not finished\n");
136
137 //////////////////////////////////////////////////////////////////////
138 // create initial page directory.
139 kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
140 memset(kern_pgdir, 0, PGSIZE);
141
142 //////////////////////////////////////////////////////////////////////
143 // Recursively insert PD in itself as a page table, to form
144 // a virtual page table at virtual address UVPT.
145 // (For now, you don't have understand the greater purpose of the
146 // following line.)
147
148 // Permissions: kernel R, user R
149 kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;
150
151 //////////////////////////////////////////////////////////////////////
152 // Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
153 // The kernel uses this array to keep track of physical pages: for
154 // each physical page, there is a corresponding struct PageInfo in this
155 // array. 'npages' is the number of physical pages in memory. Use memset
156 // to initialize all fields of each struct PageInfo to 0.
157 // Your code goes here:
158 pages = (struct PageInfo *) boot_alloc(npages*(sizeof (struct PageInfo)));
159 memset(pages, 0, npages*(sizeof (struct PageInfo)));
160
161 //////////////////////////////////////////////////////////////////////
162 // Now that we've allocated the initial kernel data structures, we set
163 // up the list of free physical pages. Once we've done so, all further
164 // memory management will go through the page_* functions. In
165 // particular, we can now map memory using boot_map_region
166 // or page_insert
167 page_init();
168
169 check_page_free_list(1);
170 check_page_alloc();
171 check_page();
172
173 //////////////////////////////////////////////////////////////////////
174 // Now we set up virtual memory
175
176 //////////////////////////////////////////////////////////////////////
177 // Map 'pages' read-only by the user at linear address UPAGES
178 // Permissions:
179 // - the new image at UPAGES -- kernel R, user R
180 // (ie. perm = PTE_U | PTE_P)
181 // - pages itself -- kernel RW, user NONE
182 // Your code goes here:
183 boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U|PTE_P);
184
185 //////////////////////////////////////////////////////////////////////
186 // Use the physical memory that 'bootstack' refers to as the kernel
187 // stack. The kernel stack grows down from virtual address KSTACKTOP.
188 // We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
189 // to be the kernel stack, but break this into two pieces:
190 // * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
191 // * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
192 // the kernel overflows its stack, it will fault rather than
193 // overwrite memory. Known as a "guard page".
194 // Permissions: kernel RW, user NONE
195 // Your code goes here:
196 boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W | PTE_P);
197
198 //////////////////////////////////////////////////////////////////////
199 // Map all of physical memory at KERNBASE.
200 // Ie. the VA range [KERNBASE, 2^32) should map to
201 // the PA range [0, 2^32 - KERNBASE)
202 // We might not have 2^32 - KERNBASE bytes of physical memory, but
203 // we just set up the mapping anyway.
204 // Permissions: kernel RW, user NONE
205 // Your code goes here:
206 boot_map_region(kern_pgdir, KERNBASE, ROUNDDOWN(0xffffffff-KERNBASE,PGSIZE), (physaddr_t)0 , PTE_W | PTE_P);
207 // Check that the initial page directory has been set up correctly.
208 check_kern_pgdir();
209
210 // Switch from the minimal entry page directory to the full kern_pgdir
211 // page table we just created. Our instruction pointer should be
212 // somewhere between KERNBASE and KERNBASE+4MB right now, which is
213 // mapped the same way by both page tables.
214 //
215 // If the machine reboots at this point, you've probably set up your
216 // kern_pgdir wrong.
217 lcr3(PADDR(kern_pgdir));
218
219 check_page_free_list(0);
220
221 // entry.S set the really important flags in cr0 (including enabling
222 // paging). Here we configure the rest of the flags that we care about.
223 cr0 = rcr0();
224 cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_MP;
225 cr0 &= ~(CR0_TS|CR0_EM);
226 lcr0(cr0);
227
228 // Some more checks, only possible after kern_pgdir is installed.
229 check_page_installed_pgdir();
230}
231
232// --------------------------------------------------------------
233// Tracking of physical pages.
234// The 'pages' array has one 'struct PageInfo' entry per physical page.
235// Pages are reference counted, and free pages are kept on a linked list.
236// --------------------------------------------------------------
237
238//
239// Initialize page structure and memory free list.
240// After this is done, NEVER use boot_alloc again. ONLY use the page
241// allocator functions below to allocate and deallocate physical
242// memory via the page_free_list.
243//
244void
245page_init(void)
246{
247 // The example code here marks all physical pages as free.
248 // However this is not truly the case. What memory is free?
249 // 1) Mark physical page 0 as in use.
250 // This way we preserve the real-mode IDT and BIOS structures
251 // in case we ever need them. (Currently we don't, but...)
252 // 2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
253 // is free.
254 // 3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
255 // never be allocated.
256 // 4) Then extended memory [EXTPHYSMEM, ...).
257 // Some of it is in use, some is free. Where is the kernel
258 // in physical memory? Which pages are already in use for
259 // page tables and other data structures?
260 //
261 // Change the code to reflect this.
262 // NB: DO NOT actually touch the physical memory corresponding to
263 // free pages!
264 /*
265 size_t i;
266 for (i = 0; i < npages; i++) {
267 pages[i].pp_ref = 0;
268 pages[i].pp_link = page_free_list;
269 page_free_list = &pages[i];
270 }
271 */
272 // 2)
273 size_t i;
274 for (i = 1; i < npages_basemem; i++) {
275 pages[i].pp_ref = 0;
276 pages[i].pp_link = page_free_list;
277 page_free_list = &pages[i];
278 }
279 // 1)
280 pages[0].pp_ref = 1;
281 // 4)
282 for (i =(uint32_t) (boot_alloc(0)-KERNBASE)/PGSIZE; i < npages; i++) {
283 pages[i].pp_ref = 0;
284 pages[i].pp_link = page_free_list;
285 page_free_list = &pages[i];
286 }
287}
288
289//
290// Allocates a physical page. If (alloc_flags & ALLOC_ZERO), fills the entire
291// returned physical page with '\0' bytes. Does NOT increment the reference
292// count of the page - the caller must do these if necessary (either explicitly
293// or via page_insert).
294//
295// Be sure to set the pp_link field of the allocated page to NULL so
296// page_free can check for double-free bugs.
297//
298// Returns NULL if out of free memory.
299//
300// Hint: use page2kva and memset
301struct PageInfo *
302page_alloc(int alloc_flags)
303{
304 // Fill this function in
305 if(page_free_list == NULL)
306 return NULL;
307 struct PageInfo* allocated_page = page_free_list;
308 page_free_list = allocated_page->pp_link;
309 allocated_page->pp_link = NULL;
310 if(alloc_flags & ALLOC_ZERO)
311 memset(page2kva(allocated_page), '\0', PGSIZE);
312 return allocated_page;
313}
314
315//
316// Return a page to the free list.
317// (This function should only be called when pp->pp_ref reaches 0.)
318//
319void
320page_free(struct PageInfo *pp)
321{
322 // Fill this function in
323 // Hint: You may want to panic if pp->pp_ref is nonzero or
324 // pp->pp_link is not NULL.
325 if(pp->pp_link != NULL)
326 panic("pp_link is not null!");
327 if(pp->pp_ref != 0)
328 panic("pp_ref is not zero!");
329 pp->pp_link = page_free_list;
330 page_free_list = pp;
331
332}
333
334//
335// Decrement the reference count on a page,
336// freeing it if there are no more refs.
337//
338void
339page_decref(struct PageInfo* pp)
340{
341 if (--pp->pp_ref == 0)
342 page_free(pp);
343}
344
345// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
346// a pointer to the page table entry (PTE) for linear address 'va'.
347// This requires walking the two-level page table structure.
348//
349// The relevant page table page might not exist yet.
350// If this is true, and create == false, then pgdir_walk returns NULL.
351// Otherwise, pgdir_walk allocates a new page table page with page_alloc.
352// - If the allocation fails, pgdir_walk returns NULL.
353// - Otherwise, the new page's reference count is incremented,
354// the page is cleared,
355// and pgdir_walk returns a pointer into the new page table page.
356//
357// Hint 1: you can turn a PageInfo * into the physical address of the
358// page it refers to with page2pa() from kern/pmap.h.
359//
360// Hint 2: the x86 MMU checks permission bits in both the page directory
361// and the page table, so it's safe to leave permissions in the page
362// directory more permissive than strictly necessary.
363//
364// Hint 3: look at inc/mmu.h for useful macros that manipulate page
365// table and page directory entries.
366//
367pte_t *
368pgdir_walk(pde_t *pgdir, const void *va, int create)
369{
370 // Fill this function in
371 pde_t* pde;
372 pte_t* pte;
373
374 pde = &pgdir[PDX(va)];
375 if(*pde & PTE_P)
376 pte = (pte_t*)KADDR(PTE_ADDR(*pde));
377 else if (create){
378 struct PageInfo* allocated_page = page_alloc(ALLOC_ZERO);
379 if(allocated_page==NULL)
380 return NULL;
381 allocated_page->pp_ref++;
382 *pde = page2pa(allocated_page) | PTE_P | PTE_W | PTE_U;
383 pte = (pte_t*)KADDR(PTE_ADDR(*pde));
384 }else
385 return NULL;
386 return (pte+PTX(va));
387}
388
389//
390// Map [va, va+size) of virtual address space to physical [pa, pa+size)
391// in the page table rooted at pgdir. Size is a multiple of PGSIZE, and
392// va and pa are both page-aligned.
393// Use permission bits perm|PTE_P for the entries.
394//
395// This function is only intended to set up the ``static'' mappings
396// above UTOP. As such, it should *not* change the pp_ref field on the
397// mapped pages.
398//
399// Hint: the TA solution uses pgdir_walk
400static void
401boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
402{
403 // Fill this function in
404 pte_t* pte;
405 for(int i=0; i<size/PGSIZE; ++i, va+=PGSIZE, pa+=PGSIZE){
406 pte = pgdir_walk(pgdir,(void *)va, 1);
407 if(pte==NULL)
408 panic("No memory");
409 *pte = pa | perm | PTE_P;
410 }
411}
412
413//
414// Map the physical page 'pp' at virtual address 'va'.
415// The permissions (the low 12 bits) of the page table entry
416// should be set to 'perm|PTE_P'.
417//
418// Requirements
419// - If there is already a page mapped at 'va', it should be page_remove()d.
420// - If necessary, on demand, a page table should be allocated and inserted
421// into 'pgdir'.
422// - pp->pp_ref should be incremented if the insertion succeeds.
423// - The TLB must be invalidated if a page was formerly present at 'va'.
424//
425// Corner-case hint: Make sure to consider what happens when the same
426// pp is re-inserted at the same virtual address in the same pgdir.
427// However, try not to distinguish this case in your code, as this
428// frequently leads to subtle bugs; there's an elegant way to handle
429// everything in one code path.
430//
431// RETURNS:
432// 0 on success
433// -E_NO_MEM, if page table couldn't be allocated
434//
435// Hint: The TA solution is implemented using pgdir_walk, page_remove,
436// and page2pa.
437//
438int
439page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
440{
441 // Fill this function in
442 pte_t* pte = pgdir_walk(pgdir, va, 1);
443 if(pte == NULL){
444 return -E_NO_MEM;
445 }
446 pp->pp_ref++;
447 if(*pte & PTE_P){
448 page_remove(pgdir, va);
449 tlb_invalidate(pgdir, va);
450 }
451 *pte = page2pa(pp) | perm | PTE_P;
452 return 0;
453}
454
455//
456// Return the page mapped at virtual address 'va'.
457// If pte_store is not zero, then we store in it the address
458// of the pte for this page. This is used by page_remove and
459// can be used to verify page permissions for syscall arguments,
460// but should not be used by most callers.
461//
462// Return NULL if there is no page mapped at va.
463//
464// Hint: the TA solution uses pgdir_walk and pa2page.
465//
466struct PageInfo *
467page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
468{
469 // Fill this function in
470 pte_t* pte = pgdir_walk(pgdir, va, 0);
471 if(pte_store != 0)
472 *pte_store = pte;
473 if(pte == NULL)
474 return NULL;
475 else
476 return pa2page(PTE_ADDR(*pte));
477}
478
479//
480// Unmaps the physical page at virtual address 'va'.
481// If there is no physical page at that address, silently does nothing.
482//
483// Details:
484// - The ref count on the physical page should decrement.
485// - The physical page should be freed if the refcount reaches 0.
486// - The pg table entry corresponding to 'va' should be set to 0.
487// (if such a PTE exists)
488// - The TLB must be invalidated if you remove an entry from
489// the page table.
490//
491// Hint: The TA solution is implemented using page_lookup,
492// tlb_invalidate, and page_decref.
493//
494void
495page_remove(pde_t *pgdir, void *va)
496{
497 // Fill this function in
498 pte_t* pte = (pte_t*)1;
499 struct PageInfo* page = page_lookup(pgdir, va, &pte);
500 if(page != NULL){
501 page_decref(page);
502 if(*pte & PTE_P){
503 *pte = 0;
504 tlb_invalidate(pgdir, va);
505 }
506 }
507}
508
509//
510// Invalidate a TLB entry, but only if the page tables being
511// edited are the ones currently in use by the processor.
512//
513void
514tlb_invalidate(pde_t *pgdir, void *va)
515{
516 // Flush the entry only if we're modifying the current address space.
517 // For now, there is only one address space, so always invalidate.
518 invlpg(va);
519}
520
521
522// --------------------------------------------------------------
523// Checking functions.
524// --------------------------------------------------------------
525
526//
527// Check that the pages on the page_free_list are reasonable.
528//
529static void
530check_page_free_list(bool only_low_memory)
531{
532 struct PageInfo *pp;
533 unsigned pdx_limit = only_low_memory ? 1 : NPDENTRIES;
534 int nfree_basemem = 0, nfree_extmem = 0;
535 char *first_free_page;
536
537 if (!page_free_list)
538 panic("'page_free_list' is a null pointer!");
539
540 if (only_low_memory) {
541 // Move pages with lower addresses first in the free
542 // list, since entry_pgdir does not map all pages.
543 struct PageInfo *pp1, *pp2;
544 struct PageInfo **tp[2] = { &pp1, &pp2 };
545 for (pp = page_free_list; pp; pp = pp->pp_link) {
546 int pagetype = PDX(page2pa(pp)) >= pdx_limit;
547 *tp[pagetype] = pp;
548 tp[pagetype] = &pp->pp_link;
549 }
550 *tp[1] = 0;
551 *tp[0] = pp2;
552 page_free_list = pp1;
553 }
554
555 // if there's a page that shouldn't be on the free list,
556 // try to make sure it eventually causes trouble.
557 for (pp = page_free_list; pp; pp = pp->pp_link)
558 if (PDX(page2pa(pp)) < pdx_limit)
559 memset(page2kva(pp), 0x97, 128);
560
561 first_free_page = (char *) boot_alloc(0);
562 for (pp = page_free_list; pp; pp = pp->pp_link) {
563 // check that we didn't corrupt the free list itself
564 assert(pp >= pages);
565 assert(pp < pages + npages);
566 assert(((char *) pp - (char *) pages) % sizeof(*pp) == 0);
567
568 // check a few pages that shouldn't be on the free list
569 assert(page2pa(pp) != 0);
570 assert(page2pa(pp) != IOPHYSMEM);
571 assert(page2pa(pp) != EXTPHYSMEM - PGSIZE);
572 assert(page2pa(pp) != EXTPHYSMEM);
573 assert(page2pa(pp) < EXTPHYSMEM || (char *) page2kva(pp) >= first_free_page);
574
575 if (page2pa(pp) < EXTPHYSMEM)
576 ++nfree_basemem;
577 else
578 ++nfree_extmem;
579 }
580
581 assert(nfree_basemem > 0);
582 assert(nfree_extmem > 0);
583
584 cprintf("check_page_free_list() succeeded!\n");
585}
586
587//
588// Check the physical page allocator (page_alloc(), page_free(),
589// and page_init()).
590//
591static void
592check_page_alloc(void)
593{
594 struct PageInfo *pp, *pp0, *pp1, *pp2;
595 int nfree;
596 struct PageInfo *fl;
597 char *c;
598 int i;
599
600 if (!pages)
601 panic("'pages' is a null pointer!");
602
603 // check number of free pages
604 for (pp = page_free_list, nfree = 0; pp; pp = pp->pp_link)
605 ++nfree;
606
607 // should be able to allocate three pages
608 pp0 = pp1 = pp2 = 0;
609 assert((pp0 = page_alloc(0)));
610 assert((pp1 = page_alloc(0)));
611 assert((pp2 = page_alloc(0)));
612
613 assert(pp0);
614 assert(pp1 && pp1 != pp0);
615 assert(pp2 && pp2 != pp1 && pp2 != pp0);
616 assert(page2pa(pp0) < npages*PGSIZE);
617 assert(page2pa(pp1) < npages*PGSIZE);
618 assert(page2pa(pp2) < npages*PGSIZE);
619
620 // temporarily steal the rest of the free pages
621 fl = page_free_list;
622 page_free_list = 0;
623
624 // should be no free memory
625 assert(!page_alloc(0));
626
627 // free and re-allocate?
628 page_free(pp0);
629 page_free(pp1);
630 page_free(pp2);
631 pp0 = pp1 = pp2 = 0;
632 assert((pp0 = page_alloc(0)));
633 assert((pp1 = page_alloc(0)));
634 assert((pp2 = page_alloc(0)));
635 assert(pp0);
636 assert(pp1 && pp1 != pp0);
637 assert(pp2 && pp2 != pp1 && pp2 != pp0);
638 assert(!page_alloc(0));
639
640 // test flags
641 memset(page2kva(pp0), 1, PGSIZE);
642 page_free(pp0);
643 assert((pp = page_alloc(ALLOC_ZERO)));
644 assert(pp && pp0 == pp);
645 c = page2kva(pp);
646 for (i = 0; i < PGSIZE; i++)
647 assert(c[i] == 0);
648
649 // give free list back
650 page_free_list = fl;
651
652 // free the pages we took
653 page_free(pp0);
654 page_free(pp1);
655 page_free(pp2);
656
657 // number of free pages should be the same
658 for (pp = page_free_list; pp; pp = pp->pp_link)
659 --nfree;
660 assert(nfree == 0);
661
662 cprintf("check_page_alloc() succeeded!\n");
663}
664
665//
666// Checks that the kernel part of virtual address space
667// has been set up roughly correctly (by mem_init()).
668//
669// This function doesn't test every corner case,
670// but it is a pretty good sanity check.
671//
672
673static void
674check_kern_pgdir(void)
675{
676 uint32_t i, n;
677 pde_t *pgdir;
678
679 pgdir = kern_pgdir;
680
681 // check pages array
682 n = ROUNDUP(npages*sizeof(struct PageInfo), PGSIZE);
683 for (i = 0; i < n; i += PGSIZE)
684 assert(check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i);
685
686
687 // check phys mem
688 for (i = 0; i < npages * PGSIZE; i += PGSIZE)
689 assert(check_va2pa(pgdir, KERNBASE + i) == i);
690
691 // check kernel stack
692 for (i = 0; i < KSTKSIZE; i += PGSIZE)
693 assert(check_va2pa(pgdir, KSTACKTOP - KSTKSIZE + i) == PADDR(bootstack) + i);
694 assert(check_va2pa(pgdir, KSTACKTOP - PTSIZE) == ~0);
695
696 // check PDE permissions
697 for (i = 0; i < NPDENTRIES; i++) {
698 switch (i) {
699 case PDX(UVPT):
700 case PDX(KSTACKTOP-1):
701 case PDX(UPAGES):
702 assert(pgdir[i] & PTE_P);
703 break;
704 default:
705 if (i >= PDX(KERNBASE)) {
706 assert(pgdir[i] & PTE_P);
707 assert(pgdir[i] & PTE_W);
708 } else
709 assert(pgdir[i] == 0);
710 break;
711 }
712 }
713 cprintf("check_kern_pgdir() succeeded!\n");
714}
715
716// This function returns the physical address of the page containing 'va',
717// defined by the page directory 'pgdir'. The hardware normally performs
718// this functionality for us! We define our own version to help check
719// the check_kern_pgdir() function; it shouldn't be used elsewhere.
720
721static physaddr_t
722check_va2pa(pde_t *pgdir, uintptr_t va)
723{
724 pte_t *p;
725
726 pgdir = &pgdir[PDX(va)];
727 if (!(*pgdir & PTE_P))
728 return ~0;
729 p = (pte_t*) KADDR(PTE_ADDR(*pgdir));
730 if (!(p[PTX(va)] & PTE_P))
731 return ~0;
732 return PTE_ADDR(p[PTX(va)]);
733}
734
735
736// check page_insert, page_remove, &c
737static void
738check_page(void)
739{
740 struct PageInfo *pp, *pp0, *pp1, *pp2;
741 struct PageInfo *fl;
742 pte_t *ptep, *ptep1;
743 void *va;
744 int i;
745 extern pde_t entry_pgdir[];
746
747 // should be able to allocate three pages
748 pp0 = pp1 = pp2 = 0;
749 assert((pp0 = page_alloc(0)));
750 assert((pp1 = page_alloc(0)));
751 assert((pp2 = page_alloc(0)));
752
753 assert(pp0);
754 assert(pp1 && pp1 != pp0);
755 assert(pp2 && pp2 != pp1 && pp2 != pp0);
756
757 // temporarily steal the rest of the free pages
758 fl = page_free_list;
759 page_free_list = 0;
760
761 // should be no free memory
762 assert(!page_alloc(0));
763 // there is no page allocated at address 0
764 assert(page_lookup(kern_pgdir, (void *) 0x0, &ptep) == NULL);
765
766 // there is no free memory, so we can't allocate a page table
767 assert(page_insert(kern_pgdir, pp1, 0x0, PTE_W) < 0);
768
769
770 // free pp0 and try again: pp0 should be used for page table
771 page_free(pp0);
772 assert(page_insert(kern_pgdir, pp1, 0x0, PTE_W) == 0);
773 assert(PTE_ADDR(kern_pgdir[0]) == page2pa(pp0));
774 assert(check_va2pa(kern_pgdir, 0x0) == page2pa(pp1));
775 assert(pp1->pp_ref == 1);
776 assert(pp0->pp_ref == 1);
777
778 // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
779 assert(page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W) == 0);
780 assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
781 assert(pp2->pp_ref == 1);
782
783 // should be no free memory
784 assert(!page_alloc(0));
785
786 // should be able to map pp2 at PGSIZE because it's already there
787 assert(page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W) == 0);
788 assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
789 assert(pp2->pp_ref == 1);
790
791 // pp2 should NOT be on the free list
792 // could happen in ref counts are handled sloppily in page_insert
793 assert(!page_alloc(0));
794
795 // check that pgdir_walk returns a pointer to the pte
796 ptep = (pte_t *) KADDR(PTE_ADDR(kern_pgdir[PDX(PGSIZE)]));
797 assert(pgdir_walk(kern_pgdir, (void*)PGSIZE, 0) == ptep+PTX(PGSIZE));
798
799 // should be able to change permissions too.
800 assert(page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W|PTE_U) == 0);
801 assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
802 assert(pp2->pp_ref == 1);
803 assert(*pgdir_walk(kern_pgdir, (void*) PGSIZE, 0) & PTE_U);
804 assert(kern_pgdir[0] & PTE_U);
805
806 // should be able to remap with fewer permissions
807 assert(page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W) == 0);
808 assert(*pgdir_walk(kern_pgdir, (void*) PGSIZE, 0) & PTE_W);
809 assert(!(*pgdir_walk(kern_pgdir, (void*) PGSIZE, 0) & PTE_U));
810
811 // should not be able to map at PTSIZE because need free page for page table
812 assert(page_insert(kern_pgdir, pp0, (void*) PTSIZE, PTE_W) < 0);
813
814 // insert pp1 at PGSIZE (replacing pp2)
815 assert(page_insert(kern_pgdir, pp1, (void*) PGSIZE, PTE_W) == 0);
816 assert(!(*pgdir_walk(kern_pgdir, (void*) PGSIZE, 0) & PTE_U));
817
818 // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
819 assert(check_va2pa(kern_pgdir, 0) == page2pa(pp1));
820 assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp1));
821 // ... and ref counts should reflect this
822 assert(pp1->pp_ref == 2);
823 assert(pp2->pp_ref == 0);
824
825 // pp2 should be returned by page_alloc
826 assert((pp = page_alloc(0)) && pp == pp2);
827
828 // unmapping pp1 at 0 should keep pp1 at PGSIZE
829 page_remove(kern_pgdir, 0x0);
830 assert(check_va2pa(kern_pgdir, 0x0) == ~0);
831 assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp1));
832 assert(pp1->pp_ref == 1);
833 assert(pp2->pp_ref == 0);
834
835 // test re-inserting pp1 at PGSIZE
836 assert(page_insert(kern_pgdir, pp1, (void*) PGSIZE, 0) == 0);
837 assert(pp1->pp_ref);
838 assert(pp1->pp_link == NULL);
839
840 // unmapping pp1 at PGSIZE should free it
841 page_remove(kern_pgdir, (void*) PGSIZE);
842 assert(check_va2pa(kern_pgdir, 0x0) == ~0);
843 assert(check_va2pa(kern_pgdir, PGSIZE) == ~0);
844 assert(pp1->pp_ref == 0);
845 assert(pp2->pp_ref == 0);
846
847 // so it should be returned by page_alloc
848 assert((pp = page_alloc(0)) && pp == pp1);
849
850 // should be no free memory
851 assert(!page_alloc(0));
852
853 // forcibly take pp0 back
854 assert(PTE_ADDR(kern_pgdir[0]) == page2pa(pp0));
855 kern_pgdir[0] = 0;
856 assert(pp0->pp_ref == 1);
857 pp0->pp_ref = 0;
858
859 // check pointer arithmetic in pgdir_walk
860 page_free(pp0);
861 va = (void*)(PGSIZE * NPDENTRIES + PGSIZE);
862 ptep = pgdir_walk(kern_pgdir, va, 1);
863 ptep1 = (pte_t *) KADDR(PTE_ADDR(kern_pgdir[PDX(va)]));
864 assert(ptep == ptep1 + PTX(va));
865 kern_pgdir[PDX(va)] = 0;
866 pp0->pp_ref = 0;
867
868 // check that new page tables get cleared
869 memset(page2kva(pp0), 0xFF, PGSIZE);
870 page_free(pp0);
871 pgdir_walk(kern_pgdir, 0x0, 1);
872 ptep = (pte_t *) page2kva(pp0);
873 for(i=0; i<NPTENTRIES; i++)
874 assert((ptep[i] & PTE_P) == 0);
875 kern_pgdir[0] = 0;
876 pp0->pp_ref = 0;
877
878 // give free list back
879 page_free_list = fl;
880
881 // free the pages we took
882 page_free(pp0);
883 page_free(pp1);
884 page_free(pp2);
885
886 cprintf("check_page() succeeded!\n");
887}
888
889// check page_insert, page_remove, &c, with an installed kern_pgdir
890static void
891check_page_installed_pgdir(void)
892{
893 struct PageInfo *pp, *pp0, *pp1, *pp2;
894 struct PageInfo *fl;
895 pte_t *ptep, *ptep1;
896 uintptr_t va;
897 int i;
898
899 // check that we can read and write installed pages
900 pp1 = pp2 = 0;
901 assert((pp0 = page_alloc(0)));
902 assert((pp1 = page_alloc(0)));
903 assert((pp2 = page_alloc(0)));
904 page_free(pp0);
905 memset(page2kva(pp1), 1, PGSIZE);
906 memset(page2kva(pp2), 2, PGSIZE);
907 page_insert(kern_pgdir, pp1, (void*) PGSIZE, PTE_W);
908 assert(pp1->pp_ref == 1);
909 assert(*(uint32_t *)PGSIZE == 0x01010101U);
910 page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W);
911 assert(*(uint32_t *)PGSIZE == 0x02020202U);
912 assert(pp2->pp_ref == 1);
913 assert(pp1->pp_ref == 0);
914 *(uint32_t *)PGSIZE = 0x03030303U;
915 assert(*(uint32_t *)page2kva(pp2) == 0x03030303U);
916 page_remove(kern_pgdir, (void*) PGSIZE);
917 assert(pp2->pp_ref == 0);
918
919 // forcibly take pp0 back
920 assert(PTE_ADDR(kern_pgdir[0]) == page2pa(pp0));
921 kern_pgdir[0] = 0;
922 assert(pp0->pp_ref == 1);
923 pp0->pp_ref = 0;
924
925 // free the pages we took
926 page_free(pp0);
927
928 cprintf("check_page_installed_pgdir() succeeded!\n");
929}