Splits x86 into 32 and 64 bit (XCC)
[akaros.git] / kern / arch / x86 / pmap32.c
1 #ifdef __SHARC__
2 #pragma nosharc
3 #define SINIT(x) x
4 #endif
5
6 /* See COPYRIGHT for copyright information. */
7 #include <arch/x86.h>
8 #include <arch/arch.h>
9 #include <arch/mmu.h>
10 #include <arch/apic.h>
11
12 #include <error.h>
13 #include <sys/queue.h>
14
15 #include <atomic.h>
16 #include <string.h>
17 #include <assert.h>
18 #include <pmap.h>
19 #include <kclock.h>
20 #include <env.h>
21 #include <stdio.h>
22 #include <kmalloc.h>
23 #include <page_alloc.h>
24
25 // These variables are set in i386_vm_init()
26 pde_t* boot_pgdir;              // Virtual address of boot time page directory
27 physaddr_t RO boot_cr3;         // Physical address of boot time page directory
28
29 // Global variables
30 page_t *RO pages = NULL;          // Virtual address of physical page array
31
32 // Global descriptor table.
33 //
34 // The kernel and user segments are identical (except for the DPL).
35 // To load the SS register, the CPL must equal the DPL.  Thus,
36 // we must duplicate the segments for the user and the kernel.
37 //
38 segdesc_t gdt[] =
39 {
40         // 0x0 - unused (always faults -- for trapping NULL far pointers)
41         SEG_NULL,
42
43         // 0x8 - kernel code segment
44         [GD_KT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 0),
45
46         // 0x10 - kernel data segment
47         [GD_KD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 0),
48
49         // 0x18 - user code segment
50         [GD_UT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 3),
51
52         // 0x20 - user data segment
53         [GD_UD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 3),
54
55         // 0x28 - tss, initialized in idt_init()
56         [GD_TSS >> 3] = SEG_NULL,
57
58         // 0x30 - LDT, set per-process
59         [GD_LDT >> 3] = SEG_NULL
60 };
61
62 pseudodesc_t gdt_pd = {
63         sizeof(gdt) - 1, (unsigned long) gdt
64 };
65
66 // --------------------------------------------------------------
67 // Set up initial memory mappings and turn on MMU.
68 // --------------------------------------------------------------
69
70 static void check_boot_pgdir(bool pse);
71
72 //
73 // Given pgdir, a pointer to a page directory,
74 // walk the 2-level page table structure to find
75 // the page table entry (PTE) for linear address la.
76 // Return a pointer to this PTE.
77 //
78 // If the relevant page table doesn't exist in the page directory:
79 //      - If create == 0, return 0.
80 //      - Otherwise allocate a new page table, install it into pgdir,
81 //        and return a pointer into it.
82 //        (Questions: What data should the new page table contain?
83 //        And what permissions should the new pgdir entry have?
84 //        Note that we use the 486-only "WP" feature of %cr0, which
85 //        affects the way supervisor-mode writes are checked.)
86 //
87 // This function abstracts away the 2-level nature of
88 // the page directory by allocating new page tables
89 // as needed.
90 // 
91 // boot_pgdir_walk may ONLY be used during initialization,
92 // before the page_free_list has been set up.
93 // It should panic on failure.  (Note that boot_alloc already panics
94 // on failure.)
95 //
96 // Supports returning jumbo (4MB PSE) PTEs.  To create with a jumbo, pass in 2.
97 // 
98 // Maps non-PSE PDEs as U/W.  W so the kernel can, U so the user can read via
99 // UVPT.  UVPT security comes from the UVPT mapping (U/R).  All other kernel pages
100 // protected at the second layer
101 static pte_t*
102 boot_pgdir_walk(pde_t *COUNT(NPDENTRIES) pgdir, uintptr_t la, int create)
103 {
104         pde_t* the_pde = &pgdir[PDX(la)];
105         void* new_table;
106
107         if (*the_pde & PTE_P) {
108                 if (*the_pde & PTE_PS)
109                         return (pte_t*)the_pde;
110                 return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(la)];
111         }
112         if (!create)
113                 return NULL;
114         if (create == 2) {
115                 if (JPGOFF(la))
116                         panic("Attempting to find a Jumbo PTE at an unaligned VA!");
117                 *the_pde = PTE_PS | PTE_P;
118                 return (pte_t*)the_pde;
119         }
120         new_table = boot_alloc(PGSIZE, PGSIZE);
121         memset(new_table, 0, PGSIZE);
122         *the_pde = (pde_t)PADDR(new_table) | PTE_P | PTE_W | PTE_U | PTE_G;
123         return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(la)];
124 }
125
126 //
127 // Map [la, la+size) of linear address space to physical [pa, pa+size)
128 // in the page table rooted at pgdir.  Size is a multiple of PGSIZE.
129 // Use permission bits perm|PTE_P for the entries.
130 //
131 // This function may ONLY be used during initialization,
132 // before the page_free_list has been set up.
133 //
134 // To map with Jumbos, set PTE_PS in perm
135 static void
136 boot_map_segment(pde_t *COUNT(NPDENTRIES) pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
137 {
138         uintptr_t i;
139         pte_t *pte;
140         // la can be page unaligned, but weird things will happen
141         // unless pa has the same offset.  pa always truncates any
142         // possible offset.  will warn.  size can be weird too. 
143         if (PGOFF(la)) {
144                 warn("la not page aligned in boot_map_segment!");
145                 size += PGOFF(la);
146         }
147         if (perm & PTE_PS) {
148                 if (JPGOFF(la) || JPGOFF(pa))
149                         panic("Tried to map a Jumbo page at an unaligned address!");
150                 // need to index with i instead of la + size, in case of wrap-around
151                 for (i = 0; i < size; i += JPGSIZE, la += JPGSIZE, pa += JPGSIZE) {
152                         pte = boot_pgdir_walk(pgdir, la, 2);
153                         *pte = PTE_ADDR(pa) | PTE_P | perm;
154                 }
155         } else {
156                 for (i = 0; i < size; i += PGSIZE, la += PGSIZE, pa += PGSIZE) {
157                         pte = boot_pgdir_walk(pgdir, la, 1);
158                         if (*pte & PTE_PS)
159                                 // if we start using the extra flag for PAT, which we aren't,
160                                 // this will warn, since PTE_PS and PTE_PAT are the same....
161                                 warn("Possibly attempting to map a regular page into a Jumbo PDE");
162                         *pte = PTE_ADDR(pa) | PTE_P | perm;
163                 }
164         }
165 }
166
167 // Set up a two-level page table:
168 //    boot_pgdir is its linear (virtual) address of the root
169 //    boot_cr3 is the physical adresss of the root
170 // Then turn on paging.  Then effectively turn off segmentation.
171 // (i.e., the segment base addrs are set to zero).
172 // 
173 // This function only sets up the kernel part of the address space
174 // (ie. addresses >= ULIM).  The user part of the address space
175 // will be setup later.
176 //
177 // From UWLIM to ULIM, the user is allowed to read but not write.
178 // Above ULIM the user cannot read (or write). 
179 void
180 vm_init(void)
181 {
182         pde_t* pgdir;
183         uint32_t cr0, edx;
184         size_t n;
185         bool pse;
186
187         pse = enable_pse();
188         if (pse)
189                 cprintf("PSE capability detected.\n");
190
191         // we paniced earlier if we don't support PGE.  turn it on now.
192         // it's used in boot_map_segment, which covers all of the mappings that are
193         // the same for all address spaces.  and also for the VPT mapping below.
194         lcr4(rcr4() | CR4_PGE);
195
196         // set up mtrr's for core0.  other cores will do the same later
197         setup_default_mtrrs(0);
198
199         /*
200          * PSE status: 
201          * - can walk and set up boot_map_segments with jumbos but can't
202          *   insert yet.  need to look at the page_dir and friends.
203          * - anything related to a single struct page still can't handle 
204          *   jumbos.  will need to think about and adjust Page functions
205          * - do we want to store info like this in the struct page?  or just check
206          *   by walking the PTE
207          * - when we alloc a page, and we want it to be 4MB, we'll need
208          *   to have contiguous memory, etc
209          * - there's a difference between having 4MB page table entries
210          *   and having 4MB Page tracking structs.  changing the latter will
211          *   break a lot of things
212          * - showmapping and friends work on a 4KB granularity, but map to the
213          *   correct entries
214          * - need to not insert / boot_map a single page into an area that is 
215          *   already holding a jumbo page.  will need to break the jumbo up so that
216          *   we can then insert the lone page.  currently warns.
217          * - some inherent issues with the pgdir_walks returning a PTE, and we
218          *   don't know whether it is a jumbo (PDE) or a regular PTE.
219          */
220
221         //////////////////////////////////////////////////////////////////////
222         // create initial page directory.
223         pgdir = boot_alloc(PGSIZE, PGSIZE);
224         memset(pgdir, 0, PGSIZE);
225         boot_pgdir = pgdir;
226         boot_cr3 = PADDR(pgdir);
227         // helpful if you want to manually walk with kvm / bochs
228         //printk("pgdir va = %p, pgdir pa = %p\n\n", pgdir, PADDR(pgdir));
229
230         //////////////////////////////////////////////////////////////////////
231         // Recursively insert PD in itself as a page table, to form
232         // a virtual page table at virtual address VPT.
233         // (For now, you don't have understand the greater purpose of the
234         // following two lines.  Unless you are eagle-eyed, in which case you
235         // should already know.)
236
237         // Permissions: kernel RW, user NONE, Global Page
238         pgdir[PDX(VPT)] = PADDR(pgdir) | PTE_W | PTE_P | PTE_G;
239
240         // same for UVPT
241         // Permissions: kernel R, user R, Global Page
242         pgdir[PDX(UVPT)] = PADDR(pgdir) | PTE_U | PTE_P | PTE_G;
243
244         //////////////////////////////////////////////////////////////////////
245         // Map all of physical memory at KERNBASE. 
246         // Ie.  the VA range [KERNBASE, 2^32) should map to
247         //      the PA range [0, 2^32 - KERNBASE)
248         // We might not have 2^32 - KERNBASE bytes of physical memory, but
249         // we just set up the mapping anyway.
250         // Permissions: kernel RW, user NONE
251         // Your code goes here: 
252         
253         // this maps all of the possible phys memory
254         // note the use of unsigned underflow to get size = 0x40000000
255         //boot_map_segment(pgdir, KERNBASE, -KERNBASE, 0, PTE_W);
256         // but this only maps what is available, and saves memory.  every 4MB of
257         // mapped memory requires a 2nd level page: 2^10 entries, each covering 2^12
258         // need to modify tests below to account for this
259         if (pse) {
260                 // map the first 4MB as regular entries, to support different MTRRs
261                 boot_map_segment(pgdir, KERNBASE, JPGSIZE, 0, PTE_W | PTE_G);
262                 boot_map_segment(pgdir, KERNBASE + JPGSIZE, maxaddrpa - JPGSIZE, JPGSIZE,
263                                  PTE_W | PTE_G | PTE_PS);
264         } else
265                 boot_map_segment(pgdir, KERNBASE, maxaddrpa, 0, PTE_W | PTE_G);
266
267         // APIC mapping: using PAT (but not *the* PAT flag) to make these type UC
268         // IOAPIC
269         boot_map_segment(pgdir, IOAPIC_BASE, PGSIZE, IOAPIC_PBASE, 
270                          PTE_PCD | PTE_PWT | PTE_W | PTE_G);
271         // Local APIC
272         boot_map_segment(pgdir, LAPIC_BASE, PGSIZE, LAPIC_PBASE,
273                          PTE_PCD | PTE_PWT | PTE_W | PTE_G);
274
275         // Check that the initial page directory has been set up correctly.
276         check_boot_pgdir(pse);
277
278         //////////////////////////////////////////////////////////////////////
279         // On x86, segmentation maps a VA to a LA (linear addr) and
280         // paging maps the LA to a PA.  I.e. VA => LA => PA.  If paging is
281         // turned off the LA is used as the PA.  Note: there is no way to
282         // turn off segmentation.  The closest thing is to set the base
283         // address to 0, so the VA => LA mapping is the identity.
284
285         // Current mapping: VA KERNBASE+x => PA x.
286         //     (segmentation base=-KERNBASE and paging is off)
287
288         // From here on down we must maintain this VA KERNBASE + x => PA x
289         // mapping, even though we are turning on paging and reconfiguring
290         // segmentation.
291
292         // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
293         // (Limits our kernel to <4MB)
294         /* They mean linear address 0:4MB, and the kernel < 4MB is only until 
295          * segmentation is turned off.
296          * once we turn on paging, segmentation is still on, so references to
297          * KERNBASE+x will get mapped to linear address x, which we need to make 
298          * sure can map to phys addr x, until we can turn off segmentation and
299          * KERNBASE+x maps to LA KERNBASE+x, which maps to PA x, via paging
300          */
301         pgdir[0] = pgdir[PDX(KERNBASE)];
302
303         // Install page table.
304         lcr3(boot_cr3);
305
306         // Turn on paging.
307         cr0 = rcr0();
308         // CD and NW should already be on, but just in case these turn on caching
309         cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_MP;
310         cr0 &= ~(CR0_TS|CR0_EM|CR0_CD|CR0_NW);
311         lcr0(cr0);
312
313         // Current mapping: KERNBASE+x => x => x.
314         // (x < 4MB so uses paging pgdir[0])
315
316         // Reload all segment registers.
317         asm volatile("lgdt gdt_pd");
318         asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
319         asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
320         asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
321         asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
322         asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
323         asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT));  // reload cs
324         asm volatile("lldt %%ax" :: "a" (0));
325
326         // Final mapping: KERNBASE+x => KERNBASE+x => x.
327
328         // This mapping was only used after paging was turned on but
329         // before the segment registers were reloaded.
330         pgdir[0] = 0;
331
332         // Flush the TLB for good measure, to kill the pgdir[0] mapping.
333         tlb_flush_global();
334 }
335
336 //
337 // Checks that the kernel part of virtual address space
338 // has been setup roughly correctly(by i386_vm_init()).
339 //
340 // This function doesn't test every corner case,
341 // in fact it doesn't test the permission bits at all,
342 // but it is a pretty good sanity check. 
343 //
344 static physaddr_t check_va2pa(pde_t *COUNT(NPDENTRIES) pgdir, uintptr_t va);
345
346 static void
347 check_boot_pgdir(bool pse)
348 {
349         uint32_t i, n;
350         pde_t *pgdir, pte;
351
352         pgdir = boot_pgdir;
353
354         // check phys mem
355         //for (i = 0; KERNBASE + i != 0; i += PGSIZE)
356         // adjusted check to account for only mapping avail mem
357         if (pse)
358                 for (i = 0; i < maxaddrpa; i += JPGSIZE)
359                         assert(check_va2pa(pgdir, KERNBASE + i) == i);
360         else
361                 for (i = 0; i < maxaddrpa; i += PGSIZE)
362                         assert(check_va2pa(pgdir, KERNBASE + i) == i);
363
364         // check for zero/non-zero in PDEs
365         for (i = 0; i < NPDENTRIES; i++) {
366                 switch (i) {
367                 case PDX(VPT):
368                 case PDX(UVPT):
369                 case PDX(LAPIC_BASE): // LAPIC mapping.  TODO: remove when MTRRs are up
370                         assert(pgdir[i]);
371                         break;
372                 default:
373                         //if (i >= PDX(KERNBASE))
374                         // adjusted check to account for only mapping avail mem
375                         // and you can't KADDR maxpa (just above legal range)
376                         // maxaddrpa can be up to maxpa, so assume the worst
377                         if (i >= PDX(KERNBASE) && i <= PDX(KADDR(maxaddrpa-1)))
378                                 assert(pgdir[i]);
379                         else
380                                 assert(pgdir[i] == 0);
381                         break;
382                 }
383         }
384
385         /* check permissions
386          * user read-only.  check for user and write, should be only user
387          * eagle-eyed viewers should be able to explain the extra cases.
388          * for the mongoose-eyed, remember that weird shit happens when you loop
389          * through UVPT.  Specifically, you can't loop once, then look at a jumbo
390          * page that is kernel only.  That's the end of the page table for you, so
391          * having a U on the entry doesn't make sense.  Thus we check for a jumbo
392          * page, and special case it.  This will happen at 0xbf701000.  Why is this
393          * magical?  Get your eagle glasses and figure it out. */
394         for (i = UWLIM; i < ULIM; i+=PGSIZE) {
395                 pte = get_va_perms(pgdir, (void*SAFE)TC(i));
396                 if (pte & PTE_P) {
397                         if (i == UVPT+(VPT >> 10))
398                                 continue;
399                         if (*pgdir_walk(pgdir, (void*SAFE)TC(i), 0) & PTE_PS) {
400                                 assert((pte & PTE_U) != PTE_U);
401                                 assert((pte & PTE_W) != PTE_W);
402                         } else {
403                                 assert((pte & PTE_U) == PTE_U);
404                                 assert((pte & PTE_W) != PTE_W);
405                         }
406                 }
407         }
408         // kernel read-write.
409         for (i = ULIM; i <= KERNBASE + maxaddrpa - PGSIZE; i+=PGSIZE) {
410                 pte = get_va_perms(pgdir, (void*SAFE)TC(i));
411                 if ((pte & PTE_P) && (i != VPT+(UVPT>>10))) {
412                         assert((pte & PTE_U) != PTE_U);
413                         assert((pte & PTE_W) == PTE_W);
414                 }
415         }
416         // special mappings
417         pte = get_va_perms(pgdir, (void*SAFE)TC(UVPT+(VPT>>10)));
418         assert((pte & PTE_U) != PTE_U);
419         assert((pte & PTE_W) != PTE_W);
420
421         // note this means the kernel cannot directly manipulate this virtual address
422         // convince yourself this isn't a big deal, eagle-eyes!
423         pte = get_va_perms(pgdir, (void*SAFE)TC(VPT+(UVPT>>10)));
424         assert((pte & PTE_U) != PTE_U);
425         assert((pte & PTE_W) != PTE_W);
426
427         cprintf("check_boot_pgdir() succeeded!\n");
428 }
429
430 // This function returns the physical address of the page containing 'va',
431 // defined by the page directory 'pgdir'.  The hardware normally performs
432 // this functionality for us!  We define our own version to help check
433 // the check_boot_pgdir() function; it shouldn't be used elsewhere.
434
435 static physaddr_t
436 check_va2pa(pde_t *COUNT(NPDENTRIES) _pgdir, uintptr_t va)
437 {
438         pte_t *COUNT(NPTENTRIES) p;
439         pde_t *COUNT(1) pgdir;
440
441         pgdir = &_pgdir[PDX(va)];
442         if (!(*pgdir & PTE_P))
443                 return ~0;
444         if (*pgdir & PTE_PS)
445                 return PTE_ADDR(*pgdir);
446         p = (pte_t*COUNT(NPTENTRIES)) KADDR(PTE_ADDR(*pgdir));
447         if (!(p[PTX(va)] & PTE_P))
448                 return ~0;
449         return PTE_ADDR(p[PTX(va)]);
450 }
451
452 /* 
453  * Remove the second level page table associated with virtual address va.
454  * Will 0 out the PDE for that page table.
455  * Panics if the page table has any present entries.
456  * This should be called rarely and with good cause.
457  * Currently errors if the PDE is jumbo or not present.
458  */
459 error_t pagetable_remove(pde_t *pgdir, void *va)
460 {
461         pde_t* the_pde = &pgdir[PDX(va)];
462
463         if (!(*the_pde & PTE_P) || (*the_pde & PTE_PS))
464                 return -EFAULT;
465         pte_t* page_table = (pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde));
466         for (int i = 0; i < NPTENTRIES; i++) 
467                 if (page_table[i] & PTE_P)
468                         panic("Page table not empty during attempted removal!");
469         *the_pde = 0;
470         page_decref(pa2page(PADDR(page_table)));
471         return 0;
472 }
473
474 // Given 'pgdir', a pointer to a page directory, pgdir_walk returns
475 // a pointer to the page table entry (PTE) for linear address 'va'.
476 // This requires walking the two-level page table structure.
477 //
478 // If the relevant page table doesn't exist in the page directory, then:
479 //    - If create == 0, pgdir_walk returns NULL.
480 //    - Otherwise, pgdir_walk tries to allocate a new page table
481 //      with page_alloc.  If this fails, pgdir_walk returns NULL.
482 //    - Otherwise, pgdir_walk returns a pointer into the new page table.
483 //
484 // This is boot_pgdir_walk, but using page_alloc() instead of boot_alloc().
485 // Unlike boot_pgdir_walk, pgdir_walk can fail.
486 //
487 // Hint: you can turn a Page * into the physical address of the
488 // page it refers to with page2pa() from kern/pmap.h.
489 //
490 // Supports returning jumbo (4MB PSE) PTEs.  To create with a jumbo, pass in 2.
491 pte_t*
492 pgdir_walk(pde_t *pgdir, const void *SNT va, int create)
493 {
494         pde_t* the_pde = &pgdir[PDX(va)];
495         page_t *new_table;
496
497         if (*the_pde & PTE_P) {
498                 if (*the_pde & PTE_PS)
499                         return (pte_t*)the_pde;
500                 return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(va)];
501         }
502         if (!create)
503                 return NULL;
504         if (create == 2) {
505                 if (JPGOFF(va))
506                         panic("Attempting to find a Jumbo PTE at an unaligned VA!");
507                 *the_pde = PTE_PS | PTE_P;
508                 return (pte_t*)the_pde;
509         }
510         if (kpage_alloc(&new_table))
511                 return NULL;
512         memset(page2kva(new_table), 0, PGSIZE);
513         /* storing our ref to new_table in the PTE */
514         *the_pde = (pde_t)page2pa(new_table) | PTE_P | PTE_W | PTE_U;
515         return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(va)];
516 }
517
518 /* Returns the effective permissions for PTE_U, PTE_W, and PTE_P on a given
519  * virtual address.  Note we need to consider the composition of every PTE in
520  * the page table walk. */
521 int get_va_perms(pde_t *pgdir, const void *SNT va)
522 {
523         pde_t the_pde = pgdir[PDX(va)];
524         pte_t the_pte;
525
526         if (!(the_pde & PTE_P))
527                 return 0;
528         if (the_pde & PTE_PS)
529                 return the_pde & (PTE_U | PTE_W | PTE_P);
530         the_pte = ((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(the_pde)))[PTX(va)];
531         if (!(the_pte & PTE_P))
532                 return 0;
533         return the_pte & the_pde & (PTE_U | PTE_W | PTE_P);
534 }
535
536 void
537 page_check(void)
538 {
539         page_t *pp, *pp0, *pp1, *pp2;
540         page_list_t fl[1024];
541         pte_t *ptep;
542
543         // should be able to allocate three pages
544         pp0 = pp1 = pp2 = 0;
545         assert(kpage_alloc(&pp0) == 0);
546         assert(kpage_alloc(&pp1) == 0);
547         assert(kpage_alloc(&pp2) == 0);
548
549         assert(pp0);
550         assert(pp1 && pp1 != pp0);
551         assert(pp2 && pp2 != pp1 && pp2 != pp0);
552
553         // temporarily steal the rest of the free pages
554         for(int i=0; i<llc_cache->num_colors; i++) {
555                 fl[i] = colored_page_free_list[i];
556                 LIST_INIT(&colored_page_free_list[i]);
557         }
558
559         // should be no free memory
560         assert(kpage_alloc(&pp) == -ENOMEM);
561
562         // Fill pp1 with bogus data and check for invalid tlb entries
563         memset(page2kva(pp1), 0xFFFFFFFF, PGSIZE);
564
565         // there is no page allocated at address 0
566         assert(page_lookup(boot_pgdir, (void *) 0x0, &ptep) == NULL);
567
568         // there is no free memory, so we can't allocate a page table 
569         assert(page_insert(boot_pgdir, pp1, 0x0, 0) < 0);
570
571         // free pp0 and try again: pp0 should be used for page table
572         page_decref(pp0);
573         assert(page_insert(boot_pgdir, pp1, 0x0, 0) == 0);
574         tlb_invalidate(boot_pgdir, 0x0);
575         // DEP Should have shot down invalid TLB entry - let's check
576         { TRUSTEDBLOCK
577           int *x = 0x0;
578           assert(*x == 0xFFFFFFFF);
579         }
580         assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
581         assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
582         assert(kref_refcnt(&pp1->pg_kref) == 2);
583         assert(kref_refcnt(&pp0->pg_kref) == 1);
584
585         // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
586         assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, 0) == 0);
587         assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
588         assert(kref_refcnt(&pp2->pg_kref) == 2);
589
590         // Make sure that pgdir_walk returns a pointer to the pte and
591         // not the table or some other garbage
592         {
593           pte_t *p = (pte_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(boot_pgdir[PDX(PGSIZE)]));
594           assert(pgdir_walk(boot_pgdir, (void *SNT)PGSIZE, 0) == &p[PTX(PGSIZE)]);
595         }
596
597         // should be no free memory
598         assert(kpage_alloc(&pp) == -ENOMEM);
599
600         // should be able to map pp2 at PGSIZE because it's already there
601         assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, PTE_U) == 0);
602         assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
603         assert(kref_refcnt(&pp2->pg_kref) == 2);
604
605         // Make sure that we actually changed the permission on pp2 when we re-mapped it
606         {
607           pte_t *p = pgdir_walk(boot_pgdir, (void*SNT)PGSIZE, 0);
608           assert(((*p) & PTE_U) == PTE_U);
609         }
610
611         // pp2 should NOT be on the free list
612         // could happen if ref counts are handled sloppily in page_insert
613         assert(kpage_alloc(&pp) == -ENOMEM);
614
615         // should not be able to map at PTSIZE because need free page for page table
616         assert(page_insert(boot_pgdir, pp0, (void*SNT) PTSIZE, 0) < 0);
617
618         // insert pp1 at PGSIZE (replacing pp2)
619         assert(page_insert(boot_pgdir, pp1, (void*SNT) PGSIZE, 0) == 0);
620
621         // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
622         assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
623         assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
624         // ... and ref counts should reflect this
625         assert(kref_refcnt(&pp1->pg_kref) == 3);
626         assert(kref_refcnt(&pp2->pg_kref) == 1);
627
628         // pp2 should be returned by page_alloc
629         page_decref(pp2);       /* should free it */
630         assert(kpage_alloc(&pp) == 0 && pp == pp2);
631
632         // unmapping pp1 at 0 should keep pp1 at PGSIZE
633         page_remove(boot_pgdir, 0x0);
634         assert(check_va2pa(boot_pgdir, 0x0) == ~0);
635         assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
636         assert(kref_refcnt(&pp1->pg_kref) == 2);
637         assert(kref_refcnt(&pp2->pg_kref) == 1);
638
639         // unmapping pp1 at PGSIZE should free it
640         page_remove(boot_pgdir, (void*SNT) PGSIZE);
641         assert(check_va2pa(boot_pgdir, 0x0) == ~0);
642         assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
643         assert(kref_refcnt(&pp1->pg_kref) == 1);
644         assert(kref_refcnt(&pp2->pg_kref) == 1);
645         page_decref(pp1);
646
647         // so it should be returned by page_alloc
648         assert(kpage_alloc(&pp) == 0 && pp == pp1);
649
650         // should be no free memory
651         assert(kpage_alloc(&pp) == -ENOMEM);
652
653         // forcibly take pp0 back
654         assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
655         boot_pgdir[0] = 0;
656         assert(kref_refcnt(&pp0->pg_kref) == 1);
657
658         // Catch invalid pointer addition in pgdir_walk - i.e. pgdir + PDX(va)
659         {
660           // Give back pp0 for a bit
661           page_decref(pp0);
662
663           void *SNT va = (void *SNT)((PGSIZE * NPDENTRIES) + PGSIZE);
664           pte_t *p2 = pgdir_walk(boot_pgdir, va, 1);
665           pte_t *p = (pte_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(boot_pgdir[PDX(va)]));
666           assert(p2 == &p[PTX(va)]);
667
668           // Clean up again
669           boot_pgdir[PDX(va)] = 0;
670         }
671
672         // give free list back
673         for(int i=0; i<llc_cache->num_colors; i++)
674                 colored_page_free_list[i] = fl[i];
675
676         // free the pages we took
677         page_decref(pp0);
678         page_decref(pp1);
679         page_decref(pp2);
680         assert(!kref_refcnt(&pp0->pg_kref));
681         assert(!kref_refcnt(&pp1->pg_kref));
682         assert(!kref_refcnt(&pp2->pg_kref));
683
684         cprintf("page_check() succeeded!\n");
685 }
686
687 /* Walks len bytes from start, executing 'callback' on every PTE, passing it a
688  * specific VA and whatever arg is passed in.  Note, this cannot handle jumbo
689  * pages. */
690 int env_user_mem_walk(env_t* e, void* start, size_t len,
691                       mem_walk_callback_t callback, void* arg)
692 {
693         pte_t *pt;
694         uint32_t pdeno, pteno;
695         physaddr_t pa;
696
697         assert((uintptr_t)start % PGSIZE == 0 && len % PGSIZE == 0);
698         void* end = (char*)start+len;
699         uint32_t pdeno_start = PDX(start);
700         uint32_t pdeno_end = PDX(ROUNDUP(end,PTSIZE));
701         /* concerned about overflow.  this should catch it for now, given the above
702          * assert. */
703         assert((len == 0) || (pdeno_start < pdeno_end));
704
705         for (pdeno = pdeno_start; pdeno < pdeno_end; pdeno++) {
706                 if (!(e->env_pgdir[pdeno] & PTE_P))
707                         continue;
708                 /* find the pa and a pointer to the page table */
709                 pa = PTE_ADDR(e->env_pgdir[pdeno]);
710                 pt = (pte_t*COUNT(NPTENTRIES)) KADDR(pa);
711                 /* figure out where we start and end within the page table */
712                 uint32_t pteno_start = (pdeno == pdeno_start ? PTX(start) : 0);
713                 uint32_t pteno_end = (pdeno == pdeno_end - 1 && PTX(end) != 0 ?
714                                       PTX(end) : NPTENTRIES );
715                 int ret;
716                 for (pteno = pteno_start; pteno < pteno_end; pteno++) {
717                         if (!PAGE_UNMAPPED(pt[pteno]))
718                                 if((ret = callback(e, &pt[pteno], PGADDR(pdeno, pteno, 0), arg)))
719                                         return ret;
720                 }
721         }
722         return 0;
723 }
724
725 /* Frees (decrefs) all pages of the process's page table, including the page
726  * directory.  Does not free the memory that is actually mapped. */
727 void env_pagetable_free(env_t* e)
728 {
729         static_assert(UVPT % PTSIZE == 0);
730         assert(e->env_cr3 != rcr3());
731         for(uint32_t pdeno = 0; pdeno < PDX(UVPT); pdeno++)
732         {
733                 // only look at mapped page tables
734                 if (!(e->env_pgdir[pdeno] & PTE_P))
735                         continue;
736
737                 // find the pa and va of the page table
738                 physaddr_t pa = PTE_ADDR(e->env_pgdir[pdeno]);
739
740                 // free the page table itself
741                 e->env_pgdir[pdeno] = 0;
742                 page_decref(pa2page(pa));
743         }
744
745         // free the page directory
746         physaddr_t pa = e->env_cr3;
747         e->env_cr3 = 0;
748         page_decref(pa2page(pa));
749         tlbflush();
750 }
751
752 /* 
753
754     // testing code for boot_pgdir_walk 
755         pte_t* temp;
756         temp = boot_pgdir_walk(pgdir, VPT + (VPT >> 10), 1);
757         cprintf("pgdir = %p\n", pgdir);
758         cprintf("test recursive walking pte_t* = %p\n", temp);
759         cprintf("test recursive walking entry = %p\n", PTE_ADDR(temp));
760         temp = boot_pgdir_walk(pgdir, 0xc0400000, 1);
761         cprintf("LA = 0xc0400000 = %p\n", temp);
762         temp = boot_pgdir_walk(pgdir, 0xc0400070, 1);
763         cprintf("LA = 0xc0400070 = %p\n", temp);
764         temp = boot_pgdir_walk(pgdir, 0xc0800000, 0);
765         cprintf("LA = 0xc0800000, no create = %p\n", temp);
766         temp = boot_pgdir_walk(pgdir, 0xc0600070, 1);
767         cprintf("LA = 0xc0600070 = %p\n", temp);
768         temp = boot_pgdir_walk(pgdir, 0xc0600090, 0);
769         cprintf("LA = 0xc0600090, nc = %p\n", temp);
770         temp = boot_pgdir_walk(pgdir, 0xc0608070, 0);
771         cprintf("LA = 0xc0608070, nc = %p\n", temp);
772         temp = boot_pgdir_walk(pgdir, 0xc0800070, 1);
773         cprintf("LA = 0xc0800070 = %p\n", temp);
774         temp = boot_pgdir_walk(pgdir, 0xc0b00070, 0);
775         cprintf("LA = 0xc0b00070, nc = %p\n", temp);
776         temp = boot_pgdir_walk(pgdir, 0xc0c00000, 0);
777         cprintf("LA = 0xc0c00000, nc = %p\n", temp);
778
779         // testing for boot_map_seg
780         cprintf("\n");
781         cprintf("before mapping 1 page to 0x00350000\n");
782         cprintf("0xc4000000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc4000000, 1));
783         cprintf("0xc4000000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc4000000, 1)));
784         boot_map_segment(pgdir, 0xc4000000, 4096, 0x00350000, PTE_W);
785         cprintf("after mapping\n");
786         cprintf("0xc4000000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc4000000, 1));
787         cprintf("0xc4000000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc4000000, 1)));
788
789         cprintf("\n");
790         cprintf("before mapping 3 pages to 0x00700000\n");
791         cprintf("0xd0000000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0000000, 1));
792         cprintf("0xd0000000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0000000, 1)));
793         cprintf("0xd0001000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0001000, 1));
794         cprintf("0xd0001000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0001000, 1)));
795         cprintf("0xd0002000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0002000, 1));
796         cprintf("0xd0002000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0002000, 1)));
797         boot_map_segment(pgdir, 0xd0000000, 4096*3, 0x00700000, 0);
798         cprintf("after mapping\n");
799         cprintf("0xd0000000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0000000, 1));
800         cprintf("0xd0000000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0000000, 1)));
801         cprintf("0xd0001000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0001000, 1));
802         cprintf("0xd0001000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0001000, 1)));
803         cprintf("0xd0002000's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xd0002000, 1));
804         cprintf("0xd0002000's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xd0002000, 1)));
805
806         cprintf("\n");
807         cprintf("before mapping 1 unaligned to 0x00500010\n");
808         cprintf("0xc8000010's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc8000010, 1));
809         cprintf("0xc8000010's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc8000010, 1)));
810         cprintf("0xc8001010's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc8001010, 1));
811         cprintf("0xc8001010's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc8001010, 1)));
812         boot_map_segment(pgdir, 0xc8000010, 4096, 0x00500010, PTE_W);
813         cprintf("after mapping\n");
814         cprintf("0xc8000010's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc8000010, 1));
815         cprintf("0xc8000010's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc8000010, 1)));
816         cprintf("0xc8001010's &pte: %08x\n",boot_pgdir_walk(pgdir, 0xc8001010, 1));
817         cprintf("0xc8001010's pte: %08x\n",*(boot_pgdir_walk(pgdir, 0xc8001010, 1)));
818
819         cprintf("\n");
820         boot_map_segment(pgdir, 0xe0000000, 4096, 0x10000000, PTE_W);
821
822 */