· 8 years ago · Apr 22, 2018, 02:20 AM
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()
13static physaddr_t maxpa; // Maximum physical address
14size_t npage; // Amount of physical memory (in pages)
15static size_t basemem; // Amount of base memory (in bytes)
16static size_t extmem; // Amount of extended memory (in bytes)
17
18// These variables are set in i386_vm_init()
19pde_t* boot_pgdir; // Virtual address of boot time page directory
20physaddr_t boot_cr3; // Physical address of boot time page directory
21static char* boot_freemem; // Pointer to next byte of free mem
22
23struct Page* pages; // Virtual address of physical page array
24static struct Page_list page_free_list; // Free list of physical pages
25
26// Global descriptor table.
27//
28// The kernel and user segments are identical (except for the DPL).
29// To load the SS register, the CPL must equal the DPL. Thus,
30// we must duplicate the segments for the user and the kernel.
31//
32struct Segdesc gdt[] =
33{
34 // 0x0 - unused (always faults -- for trapping NULL far pointers)
35 SEG_NULL,
36
37 // 0x8 - kernel code segment
38 [GD_KT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 0),
39
40 // 0x10 - kernel data segment
41 [GD_KD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 0),
42
43 // 0x18 - user code segment
44 [GD_UT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 3),
45
46 // 0x20 - user data segment
47 [GD_UD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 3),
48
49 // 0x28 - tss, initialized in idt_init()
50 [GD_TSS >> 3] = SEG_NULL
51};
52
53struct Pseudodesc gdt_pd = {
54 sizeof(gdt) - 1, (unsigned long) gdt
55};
56
57static int
58nvram_read(int r)
59{
60 return mc146818_read(r) | (mc146818_read(r + 1) << 8);
61}
62
63void
64i386_detect_memory(void)
65{
66 // CMOS tells us how many kilobytes there are
67 basemem = ROUNDDOWN(nvram_read(NVRAM_BASELO)*1024, PGSIZE);
68 extmem = ROUNDDOWN(nvram_read(NVRAM_EXTLO)*1024, PGSIZE);
69
70 // Calculate the maximum physical address based on whether
71 // or not there is any extended memory. See comment in <inc/mmu.h>.
72 if (extmem)
73 maxpa = EXTPHYSMEM + extmem;
74 else
75 maxpa = basemem;
76
77 npage = maxpa / PGSIZE;
78
79 cprintf("Physical memory: %dK available, ", (int)(maxpa/1024));
80 cprintf("base = %dK, extended = %dK\n", (int)(basemem/1024), (int)(extmem/1024));
81}
82
83// --------------------------------------------------------------
84// Set up initial memory mappings and turn on MMU.
85// --------------------------------------------------------------
86
87static void check_boot_pgdir(void);
88static void check_page_alloc();
89static void page_check(void);
90static void boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm);
91
92//
93// A simple physical memory allocator, used only a few times
94// in the process of setting up the virtual memory system.
95// page_alloc() is the real allocator.
96//
97// Allocate n bytes of physical memory aligned on an
98// align-byte boundary. Align must be a power of two.
99// Return kernel virtual address. Returned memory is uninitialized.
100//
101// If we're out of memory, boot_alloc should panic.
102// This function may ONLY be used during initialization,
103// before the page_free_list has been set up.
104//
105static void*
106boot_alloc(uint32_t n, uint32_t align)
107{
108 extern char end[];
109 void *v;
110
111 // Initialize boot_freemem if this is the first time.
112 // 'end' is a magic symbol automatically generated by the linker,
113 // which points to the end of the kernel's bss segment -
114 // i.e., the first virtual address that the linker
115 // did _not_ assign to any kernel code or global variables.
116 if (boot_freemem == 0)
117 boot_freemem = end;
118
119 // LAB 2: Your code here:
120 // Step 1: round boot_freemem up to be aligned properly
121 // Step 2: save current value of boot_freemem as allocated chunk
122 // Step 3: increase boot_freemem to record allocation
123 // Step 4: return allocated chunk
124
125 return NULL;
126}
127
128// Set up a two-level page table:
129// boot_pgdir is its linear (virtual) address of the root
130// boot_cr3 is the physical adresss of the root
131// Then turn on paging. Then effectively turn off segmentation.
132// (i.e., the segment base addrs are set to zero).
133//
134// This function only sets up the kernel part of the address space
135// (ie. addresses >= UTOP). The user part of the address space
136// will be setup later.
137//
138// From UTOP to ULIM, the user is allowed to read but not write.
139// Above ULIM the user cannot read (or write).
140void
141i386_vm_init(void)
142{
143 pde_t* pgdir;
144 uint32_t cr0;
145 size_t n;
146
147 // Delete this line:
148 panic("i386_vm_init: This function is not finished\n");
149
150 //////////////////////////////////////////////////////////////////////
151 // create initial page directory.
152 pgdir = boot_alloc(PGSIZE, PGSIZE);
153 memset(pgdir, 0, PGSIZE);
154 boot_pgdir = pgdir;
155 boot_cr3 = PADDR(pgdir);
156
157 //////////////////////////////////////////////////////////////////////
158 // Recursively insert PD in itself as a page table, to form
159 // a virtual page table at virtual address VPT.
160 // (For now, you don't have understand the greater purpose of the
161 // following two lines.)
162
163 // Permissions: kernel RW, user NONE
164 pgdir[PDX(VPT)] = PADDR(pgdir)|PTE_W|PTE_P;
165
166 // same for UVPT
167 // Permissions: kernel R, user R
168 pgdir[PDX(UVPT)] = PADDR(pgdir)|PTE_U|PTE_P;
169
170 //////////////////////////////////////////////////////////////////////
171 // Make 'pages' point to an array of size 'npage' of 'struct Page'.
172 // The kernel uses this structure to keep track of physical pages;
173 // 'npage' equals the number of physical pages in memory. User-level
174 // programs will get read-only access to the array as well.
175 // You must allocate the array yourself.
176 // Your code goes here:
177
178
179 //////////////////////////////////////////////////////////////////////
180 // Now that we've allocated the initial kernel data structures, we set
181 // up the list of free physical pages. Once we've done so, all further
182 // memory management will go through the page_* functions. In
183 // particular, we can now map memory using boot_map_segment or page_insert
184 page_init();
185
186 check_page_alloc();
187
188 page_check();
189
190 //////////////////////////////////////////////////////////////////////
191 // Now we set up virtual memory
192
193 //////////////////////////////////////////////////////////////////////
194 // Map 'pages' read-only by the user at linear address UPAGES
195 // Permissions:
196 // - the new image at UPAGES -- kernel R, user R
197 // (ie. perm = PTE_U | PTE_P)
198 // - pages itself -- kernel RW, user NONE
199 // Your code goes here:
200
201 //////////////////////////////////////////////////////////////////////
202 // Use the physical memory that bootstack refers to as
203 // the kernel stack. The complete VA
204 // range of the stack, [KSTACKTOP-PTSIZE, KSTACKTOP), breaks into two
205 // pieces:
206 // * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
207 // * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed => faults
208 // Permissions: kernel RW, user NONE
209 // Your code goes here:
210
211 //////////////////////////////////////////////////////////////////////
212 // Map all of physical memory at KERNBASE.
213 // Ie. the VA range [KERNBASE, 2^32) should map to
214 // the PA range [0, 2^32 - KERNBASE)
215 // We might not have 2^32 - KERNBASE bytes of physical memory, but
216 // we just set up the mapping anyway.
217 // Permissions: kernel RW, user NONE
218 // Your code goes here:
219
220 // Check that the initial page directory has been set up correctly.
221 check_boot_pgdir();
222
223 //////////////////////////////////////////////////////////////////////
224 // On x86, segmentation maps a VA to a LA (linear addr) and
225 // paging maps the LA to a PA. I.e. VA => LA => PA. If paging is
226 // turned off the LA is used as the PA. Note: there is no way to
227 // turn off segmentation. The closest thing is to set the base
228 // address to 0, so the VA => LA mapping is the identity.
229
230 // Current mapping: VA KERNBASE+x => PA x.
231 // (segmentation base=-KERNBASE and paging is off)
232
233 // From here on down we must maintain this VA KERNBASE + x => PA x
234 // mapping, even though we are turning on paging and reconfiguring
235 // segmentation.
236
237 // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
238 // (Limits our kernel to <4MB)
239 pgdir[0] = pgdir[PDX(KERNBASE)];
240
241 // Install page table.
242 lcr3(boot_cr3);
243
244 // Turn on paging.
245 cr0 = rcr0();
246 cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_TS|CR0_EM|CR0_MP;
247 cr0 &= ~(CR0_TS|CR0_EM);
248 lcr0(cr0);
249
250 // Current mapping: KERNBASE+x => x => x.
251 // (x < 4MB so uses paging pgdir[0])
252
253 // Reload all segment registers.
254 asm volatile("lgdt gdt_pd");
255 asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
256 asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
257 asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
258 asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
259 asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
260 asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT)); // reload cs
261 asm volatile("lldt %%ax" :: "a" (0));
262
263 // Final mapping: KERNBASE+x => KERNBASE+x => x.
264
265 // This mapping was only used after paging was turned on but
266 // before the segment registers were reloaded.
267 pgdir[0] = 0;
268
269 // Flush the TLB for good measure, to kill the pgdir[0] mapping.
270 lcr3(boot_cr3);
271}
272
273//
274// Check the physical page allocator (page_alloc(), page_free(),
275// and page_init()).
276//
277static void
278check_page_alloc()
279{
280 struct Page *pp, *pp0, *pp1, *pp2;
281 struct Page_list fl;
282
283 // if there's a page that shouldn't be on
284 // the free list, try to make sure it
285 // eventually causes trouble.
286 LIST_FOREACH(pp0, &page_free_list, pp_link)
287 memset(page2kva(pp0), 0x97, 128);
288
289 // should be able to allocate three pages
290 pp0 = pp1 = pp2 = 0;
291 assert(page_alloc(&pp0) == 0);
292 assert(page_alloc(&pp1) == 0);
293 assert(page_alloc(&pp2) == 0);
294
295 assert(pp0);
296 assert(pp1 && pp1 != pp0);
297 assert(pp2 && pp2 != pp1 && pp2 != pp0);
298 assert(page2pa(pp0) < npage*PGSIZE);
299 assert(page2pa(pp1) < npage*PGSIZE);
300 assert(page2pa(pp2) < npage*PGSIZE);
301
302 // temporarily steal the rest of the free pages
303 fl = page_free_list;
304 LIST_INIT(&page_free_list);
305
306 // should be no free memory
307 assert(page_alloc(&pp) == -E_NO_MEM);
308
309 // free and re-allocate?
310 page_free(pp0);
311 page_free(pp1);
312 page_free(pp2);
313 pp0 = pp1 = pp2 = 0;
314 assert(page_alloc(&pp0) == 0);
315 assert(page_alloc(&pp1) == 0);
316 assert(page_alloc(&pp2) == 0);
317 assert(pp0);
318 assert(pp1 && pp1 != pp0);
319 assert(pp2 && pp2 != pp1 && pp2 != pp0);
320 assert(page_alloc(&pp) == -E_NO_MEM);
321
322 // give free list back
323 page_free_list = fl;
324
325 // free the pages we took
326 page_free(pp0);
327 page_free(pp1);
328 page_free(pp2);
329
330 cprintf("check_page_alloc() succeeded!\n");
331}
332
333//
334// Checks that the kernel part of virtual address space
335// has been setup roughly correctly(by i386_vm_init()).
336//
337// This function doesn't test every corner case,
338// in fact it doesn't test the permission bits at all,
339// but it is a pretty good sanity check.
340//
341static physaddr_t check_va2pa(pde_t *pgdir, uintptr_t va);
342
343static void
344check_boot_pgdir(void)
345{
346 uint32_t i, n;
347 pde_t *pgdir;
348
349 pgdir = boot_pgdir;
350
351 // check pages array
352 n = ROUNDUP(npage*sizeof(struct Page), PGSIZE);
353 for (i = 0; i < n; i += PGSIZE)
354 assert(check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i);
355
356
357 // check phys mem
358 for (i = 0; i < npage * PGSIZE; i += PGSIZE)
359 assert(check_va2pa(pgdir, KERNBASE + i) == i);
360
361 // check kernel stack
362 for (i = 0; i < KSTKSIZE; i += PGSIZE)
363 assert(check_va2pa(pgdir, KSTACKTOP - KSTKSIZE + i) == PADDR(bootstack) + i);
364
365 // check for zero/non-zero in PDEs
366 for (i = 0; i < NPDENTRIES; i++) {
367 switch (i) {
368 case PDX(VPT):
369 case PDX(UVPT):
370 case PDX(KSTACKTOP-1):
371 case PDX(UPAGES):
372 assert(pgdir[i]);
373 break;
374 default:
375 if (i >= PDX(KERNBASE))
376 assert(pgdir[i]);
377 else
378 assert(pgdir[i] == 0);
379 break;
380 }
381 }
382 cprintf("check_boot_pgdir() succeeded!\n");
383}
384
385// This function returns the physical address of the page containing 'va',
386// defined by the page directory 'pgdir'. The hardware normally performs
387// this functionality for us! We define our own version to help check
388// the check_boot_pgdir() function; it shouldn't be used elsewhere.
389
390static physaddr_t
391check_va2pa(pde_t *pgdir, uintptr_t va)
392{
393 pte_t *p;
394
395 pgdir = &pgdir[PDX(va)];
396 if (!(*pgdir & PTE_P))
397 return ~0;
398 p = (pte_t*) KADDR(PTE_ADDR(*pgdir));
399 if (!(p[PTX(va)] & PTE_P))
400 return ~0;
401 return PTE_ADDR(p[PTX(va)]);
402}
403
404// --------------------------------------------------------------
405// Tracking of physical pages.
406// The 'pages' array has one 'struct Page' entry per physical page.
407// Pages are reference counted, and free pages are kept on a linked list.
408// --------------------------------------------------------------
409
410//
411// Initialize page structure and memory free list.
412// After this point, ONLY use the functions below
413// to allocate and deallocate physical memory via the page_free_list,
414// and NEVER use boot_alloc()
415//
416void
417page_init(void)
418{
419 // The example code here marks all pages as free.
420 // However this is not truly the case. What memory is free?
421 // 1) Mark page 0 as in use.
422 // This way we preserve the real-mode IDT and BIOS structures
423 // in case we ever need them. (Currently we don't, but...)
424 // 2) Mark the rest of base memory as free.
425 // 3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
426 // Mark it as in use so that it can never be allocated.
427 // 4) Then extended memory [EXTPHYSMEM, ...).
428 // Some of it is in use, some is free. Where is the kernel?
429 // Which pages are used for page tables and other data structures?
430 //
431 // Change the code to reflect this.
432 int i;
433 LIST_INIT(&page_free_list);
434 for (i = 0; i < npage; i++) {
435 pages[i].pp_ref = 0;
436 LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
437 }
438}
439
440//
441// Initialize a Page structure.
442// The result has null links and 0 refcount.
443// Note that the corresponding physical page is NOT initialized!
444//
445static void
446page_initpp(struct Page *pp)
447{
448 memset(pp, 0, sizeof(*pp));
449}
450
451//
452// Allocates a physical page.
453// Does NOT set the contents of the physical page to zero -
454// the caller must do that if necessary.
455//
456// *pp_store -- is set to point to the Page struct of the newly allocated
457// page
458//
459// RETURNS
460// 0 -- on success
461// -E_NO_MEM -- otherwise
462//
463// Hint: use LIST_FIRST, LIST_REMOVE, and page_initpp
464// Hint: pp_ref should not be incremented
465int
466page_alloc(struct Page **pp_store)
467{
468 // Fill this function in
469 return -E_NO_MEM;
470}
471
472//
473// Return a page to the free list.
474// (This function should only be called when pp->pp_ref reaches 0.)
475//
476void
477page_free(struct Page *pp)
478{
479 // Fill this function in
480}
481
482//
483// Decrement the reference count on a page,
484// freeing it if there are no more refs.
485//
486void
487page_decref(struct Page* pp)
488{
489 if (--pp->pp_ref == 0)
490 page_free(pp);
491}
492
493// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
494// a pointer to the page table entry (PTE) for linear address 'va'.
495// This requires walking the two-level page table structure.
496//
497// If the relevant page table doesn't exist in the page directory, then:
498// - If create == 0, pgdir_walk returns NULL.
499// - Otherwise, pgdir_walk tries to allocate a new page table
500// with page_alloc. If this fails, pgdir_walk returns NULL.
501// - pgdir_walk sets pp_ref to 1 for the new page table.
502// - pgdir_walk clears the new page table.
503// - Finally, pgdir_walk returns a pointer into the new page table.
504//
505// Hint: you can turn a Page * into the physical address of the
506// page it refers to with page2pa() from kern/pmap.h.
507//
508// Hint 2: the x86 MMU checks permission bits in both the page directory
509// and the page table, so it's safe to leave permissions in the page
510// more permissive than strictly necessary.
511pte_t *
512pgdir_walk(pde_t *pgdir, const void *va, int create)
513{
514 // Fill this function in
515 return NULL;
516}
517
518//
519// Map the physical page 'pp' at virtual address 'va'.
520// The permissions (the low 12 bits) of the page table
521// entry should be set to 'perm|PTE_P'.
522//
523// Requirements
524// - If there is already a page mapped at 'va', it should be page_remove()d.
525// - If necessary, on demand, a page table should be allocated and inserted
526// into 'pgdir'.
527// - pp->pp_ref should be incremented if the insertion succeeds.
528// - The TLB must be invalidated if a page was formerly present at 'va'.
529//
530// Corner-case hint: Make sure to consider what happens when the same
531// pp is re-inserted at the same virtual address in the same pgdir.
532//
533// RETURNS:
534// 0 on success
535// -E_NO_MEM, if page table couldn't be allocated
536//
537// Hint: The TA solution is implemented using pgdir_walk, page_remove,
538// and page2pa.
539//
540int
541page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm)
542{
543 // Fill this function in
544 return 0;
545}
546
547//
548// Map [la, la+size) of linear address space to physical [pa, pa+size)
549// in the page table rooted at pgdir. Size is a multiple of PGSIZE.
550// Use permission bits perm|PTE_P for the entries.
551//
552// This function is only intended to set up the ``static'' mappings
553// above UTOP. As such, it should *not* change the pp_ref field on the
554// mapped pages.
555//
556// Hint: the TA solution uses pgdir_walk
557static void
558boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
559{
560 // Fill this function in
561}
562
563//
564// Return the page mapped at virtual address 'va'.
565// If pte_store is not zero, then we store in it the address
566// of the pte for this page. This is used by page_remove
567// but should not be used by other callers.
568//
569// Return NULL if there is no page mapped at va.
570//
571// Hint: the TA solution uses pgdir_walk and pa2page.
572//
573struct Page *
574page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
575{
576 // Fill this function in
577 return NULL;
578}
579
580//
581// Unmaps the physical page at virtual address 'va'.
582// If there is no physical page at that address, silently does nothing.
583//
584// Details:
585// - The ref count on the physical page should decrement.
586// - The physical page should be freed if the refcount reaches 0.
587// - The pg table entry corresponding to 'va' should be set to 0.
588// (if such a PTE exists)
589// - The TLB must be invalidated if you remove an entry from
590// the pg dir/pg table.
591//
592// Hint: The TA solution is implemented using page_lookup,
593// tlb_invalidate, and page_decref.
594//
595void
596page_remove(pde_t *pgdir, void *va)
597{
598 // Fill this function in
599}
600
601//
602// Invalidate a TLB entry, but only if the page tables being
603// edited are the ones currently in use by the processor.
604//
605void
606tlb_invalidate(pde_t *pgdir, void *va)
607{
608 // Flush the entry only if we're modifying the current address space.
609 // For now, there is only one address space, so always invalidate.
610 invlpg(va);
611}
612
613// check page_insert, page_remove, &c
614static void
615page_check(void)
616{
617 struct Page *pp, *pp0, *pp1, *pp2;
618 struct Page_list fl;
619 pte_t *ptep, *ptep1;
620 void *va;
621 int i;
622
623 // should be able to allocate three pages
624 pp0 = pp1 = pp2 = 0;
625 assert(page_alloc(&pp0) == 0);
626 assert(page_alloc(&pp1) == 0);
627 assert(page_alloc(&pp2) == 0);
628
629 assert(pp0);
630 assert(pp1 && pp1 != pp0);
631 assert(pp2 && pp2 != pp1 && pp2 != pp0);
632
633 // temporarily steal the rest of the free pages
634 fl = page_free_list;
635 LIST_INIT(&page_free_list);
636
637 // should be no free memory
638 assert(page_alloc(&pp) == -E_NO_MEM);
639
640 // there is no page allocated at address 0
641 assert(page_lookup(boot_pgdir, (void *) 0x0, &ptep) == NULL);
642
643 // there is no free memory, so we can't allocate a page table
644 assert(page_insert(boot_pgdir, pp1, 0x0, 0) < 0);
645
646 // free pp0 and try again: pp0 should be used for page table
647 page_free(pp0);
648 assert(page_insert(boot_pgdir, pp1, 0x0, 0) == 0);
649 assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
650 assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
651 assert(pp1->pp_ref == 1);
652 assert(pp0->pp_ref == 1);
653
654 // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
655 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
656 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
657 assert(pp2->pp_ref == 1);
658
659 // should be no free memory
660 assert(page_alloc(&pp) == -E_NO_MEM);
661
662 // should be able to map pp2 at PGSIZE because it's already there
663 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
664 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
665 assert(pp2->pp_ref == 1);
666
667 // pp2 should NOT be on the free list
668 // could happen in ref counts are handled sloppily in page_insert
669 assert(page_alloc(&pp) == -E_NO_MEM);
670
671 // check that pgdir_walk returns a pointer to the pte
672 ptep = KADDR(PTE_ADDR(boot_pgdir[PDX(PGSIZE)]));
673 assert(pgdir_walk(boot_pgdir, (void*)PGSIZE, 0) == ptep+PTX(PGSIZE));
674
675 // should be able to change permissions too.
676 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, PTE_U) == 0);
677 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
678 assert(pp2->pp_ref == 1);
679 assert(*pgdir_walk(boot_pgdir, (void*) PGSIZE, 0) & PTE_U);
680 assert(boot_pgdir[0] & PTE_U);
681
682 // should not be able to map at PTSIZE because need free page for page table
683 assert(page_insert(boot_pgdir, pp0, (void*) PTSIZE, 0) < 0);
684
685 // insert pp1 at PGSIZE (replacing pp2)
686 assert(page_insert(boot_pgdir, pp1, (void*) PGSIZE, 0) == 0);
687 assert(!(*pgdir_walk(boot_pgdir, (void*) PGSIZE, 0) & PTE_U));
688
689 // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
690 assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
691 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
692 // ... and ref counts should reflect this
693 assert(pp1->pp_ref == 2);
694 assert(pp2->pp_ref == 0);
695
696 // pp2 should be returned by page_alloc
697 assert(page_alloc(&pp) == 0 && pp == pp2);
698
699 // unmapping pp1 at 0 should keep pp1 at PGSIZE
700 page_remove(boot_pgdir, 0x0);
701 assert(check_va2pa(boot_pgdir, 0x0) == ~0);
702 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
703 assert(pp1->pp_ref == 1);
704 assert(pp2->pp_ref == 0);
705
706 // unmapping pp1 at PGSIZE should free it
707 page_remove(boot_pgdir, (void*) PGSIZE);
708 assert(check_va2pa(boot_pgdir, 0x0) == ~0);
709 assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
710 assert(pp1->pp_ref == 0);
711 assert(pp2->pp_ref == 0);
712
713 // so it should be returned by page_alloc
714 assert(page_alloc(&pp) == 0 && pp == pp1);
715
716 // should be no free memory
717 assert(page_alloc(&pp) == -E_NO_MEM);
718
719#if 0
720 // should be able to page_insert to change a page
721 // and see the new data immediately.
722 memset(page2kva(pp1), 1, PGSIZE);
723 memset(page2kva(pp2), 2, PGSIZE);
724 page_insert(boot_pgdir, pp1, 0x0, 0);
725 assert(pp1->pp_ref == 1);
726 assert(*(int*)0 == 0x01010101);
727 page_insert(boot_pgdir, pp2, 0x0, 0);
728 assert(*(int*)0 == 0x02020202);
729 assert(pp2->pp_ref == 1);
730 assert(pp1->pp_ref == 0);
731 page_remove(boot_pgdir, 0x0);
732 assert(pp2->pp_ref == 0);
733#endif
734
735 // forcibly take pp0 back
736 assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
737 boot_pgdir[0] = 0;
738 assert(pp0->pp_ref == 1);
739 pp0->pp_ref = 0;
740
741 // check pointer arithmetic in pgdir_walk
742 page_free(pp0);
743 va = (void*)(PGSIZE * NPDENTRIES + PGSIZE);
744 ptep = pgdir_walk(boot_pgdir, va, 1);
745 ptep1 = KADDR(PTE_ADDR(boot_pgdir[PDX(va)]));
746 assert(ptep == ptep1 + PTX(va));
747 boot_pgdir[PDX(va)] = 0;
748 pp0->pp_ref = 0;
749
750 // check that new page tables get cleared
751 memset(page2kva(pp0), 0xFF, PGSIZE);
752 page_free(pp0);
753 pgdir_walk(boot_pgdir, 0x0, 1);
754 ptep = page2kva(pp0);
755 for(i=0; i<NPTENTRIES; i++)
756 assert((ptep[i] & PTE_P) == 0);
757 boot_pgdir[0] = 0;
758 pp0->pp_ref = 0;
759
760 // give free list back
761 page_free_list = fl;
762
763 // free the pages we took
764 page_free(pp0);
765 page_free(pp1);
766 page_free(pp2);
767
768 cprintf("page_check() succeeded!\n");
769}