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