· 8 years ago · Apr 13, 2018, 07:04 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 if(((uint32_t)boot_freemem & (align-1)) != 0){
122 boot_freemem += align;
123 boot_freemem = (char *)((uint32_t)boot_freemem & ~(align-1));
124 }
125 // Step 2: save current value of boot_freemem as allocated chunk
126 v = boot_freemem;
127 // Step 3: increase boot_freemem to record allocation
128 boot_freemem += n;
129 // Step 4: return allocated chunk
130 return v;
131}
132
133// Set up a two-level page table:
134// boot_pgdir is its linear (virtual) address of the root
135// boot_cr3 is the physical adresss of the root
136// Then turn on paging. Then effectively turn off segmentation.
137// (i.e., the segment base addrs are set to zero).
138//
139// This function only sets up the kernel part of the address space
140// (ie. addresses >= UTOP). The user part of the address space
141// will be setup later.
142//
143// From UTOP to ULIM, the user is allowed to read but not write.
144// Above ULIM the user cannot read (or write).
145void
146i386_vm_init(void)
147{
148 pde_t* pgdir;
149 uint32_t cr0;
150 size_t n;
151
152 // Delete this line:
153 //panic("i386_vm_init: This function is not finished\n");
154
155 //////////////////////////////////////////////////////////////////////
156 // create initial page directory.
157 pgdir = boot_alloc(PGSIZE, PGSIZE);
158 memset(pgdir, 0, PGSIZE);
159 boot_pgdir = pgdir;
160 boot_cr3 = PADDR(pgdir);
161
162 //////////////////////////////////////////////////////////////////////
163 // Recursively insert PD in itself as a page table, to form
164 // a virtual page table at virtual address VPT.
165 // (For now, you don't have understand the greater purpose of the
166 // following two lines.)
167
168 // Permissions: kernel RW, user NONE
169 pgdir[PDX(VPT)] = PADDR(pgdir)|PTE_W|PTE_P;
170
171 // same for UVPT
172 // Permissions: kernel R, user R
173 pgdir[PDX(UVPT)] = PADDR(pgdir)|PTE_U|PTE_P;
174
175 //////////////////////////////////////////////////////////////////////
176 // Make 'pages' point to an array of size 'npage' of 'struct Page'.
177 // The kernel uses this structure to keep track of physical pages;
178 // 'npage' equals the number of physical pages in memory. User-level
179 // programs will get read-only access to the array as well.
180 // You must allocate the array yourself.
181 // Your code goes here:
182 pages = boot_alloc(sizeof(struct Page)*npage,PGSIZE);
183
184
185 //////////////////////////////////////////////////////////////////////
186 // Now that we've allocated the initial kernel data structures, we set
187 // up the list of free physical pages. Once we've done so, all further
188 // memory management will go through the page_* functions. In
189 // particular, we can now map memory using boot_map_segment or page_insert
190 page_init();
191
192 check_page_alloc();
193
194 page_check();
195
196 //////////////////////////////////////////////////////////////////////
197 // Now we set up virtual memory
198
199 //////////////////////////////////////////////////////////////////////
200 // Map 'pages' read-only by the user at linear address UPAGES
201 // (ie. perm = PTE_U | PTE_P)
202 // Permissions:
203 // - pages -- kernel RW, user NONE
204 // - the read-only version mapped at UPAGES -- kernel R, user R
205 // Your code goes here:
206 //boot_map_segment(pgdir, (uintptr_t) pages, PTSIZE, (physaddr_t) PADDR(pages), PTE_P | PTE_W);
207 boot_map_segment(pgdir, (uintptr_t) UPAGES, PTSIZE, (physaddr_t) PADDR(pages), PTE_P | PTE_U);
208
209
210 //////////////////////////////////////////////////////////////////////
211 // Map the kernel stack (symbol name "bootstack"). The complete VA
212 // range of the stack, [KSTACKTOP-PTSIZE, KSTACKTOP), breaks into two
213 // pieces:
214 // * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
215 // * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed => faults
216 // Permissions: kernel RW, user NONE
217 // Your code goes here:
218 boot_map_segment(pgdir, (uintptr_t) KSTACKTOP-KSTKSIZE, KSTKSIZE, (physaddr_t) PADDR(bootstack), PTE_P | PTE_W);
219 boot_map_segment(pgdir, (uintptr_t) KSTACKTOP-PTSIZE, PTSIZE-KSTKSIZE, (physaddr_t) 0x0, PTE_P);
220
221 //////////////////////////////////////////////////////////////////////
222 // Map all of physical memory at KERNBASE.
223 // Ie. the VA range [KERNBASE, 2^32) should map to
224 // the PA range [0, 2^32 - KERNBASE)
225 // We might not have 2^32 - KERNBASE bytes of physical memory, but
226 // we just set up the amapping anyway.
227 // Permissions: kernel RW, user NONE
228 // Your code goes here:
229 boot_map_segment(pgdir, (uintptr_t) KERNBASE, 0x10000000, (physaddr_t) 0x0, PTE_P | PTE_W);
230
231
232 // Check that the initial page directory has been set up correctly.
233 check_boot_pgdir();
234
235 //////////////////////////////////////////////////////////////////////
236 // On x86, segmentation maps a VA to a LA (linear addr) and
237 // paging maps the LA to a PA. I.e. VA => LA => PA. If paging is
238 // turned off the LA is used as the PA. Note: there is no way to
239 // turn off segmentation. The closest thing is to set the base
240 // address to 0, so the VA => LA mapping is the identity.
241
242 // Current mapping: VA KERNBASE+x => PA x.
243 // (segmentation base=-KERNBASE and paging is off)
244
245 // From here on down we must maintain this VA KERNBASE + x => PA x
246 // mapping, even though we are turning on paging and reconfiguring
247 // segmentation.
248
249 // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
250 // (Limits our kernel to <4MB)
251 pgdir[0] = pgdir[PDX(KERNBASE)];
252
253 // Install page table.
254 lcr3(boot_cr3);
255
256 // Turn on paging.
257 cr0 = rcr0();
258
259 cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_TS|CR0_EM|CR0_MP;
260 cr0 &= ~(CR0_TS|CR0_EM);
261 lcr0(cr0);
262
263 // Current mapping: KERNBASE+x => x => x.
264 // (x < 4MB so uses paging pgdir[0])
265
266 // Reload all segment registers.
267 asm volatile("lgdt gdt_pd");
268 asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
269 asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
270 asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
271 asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
272 asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
273 asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT)); // reload cs
274 asm volatile("lldt %%ax" :: "a" (0));
275
276 // Final mapping: KERNBASE+x => KERNBASE+x => x.
277
278 // This mapping was only used after paging was turned on but
279 // before the segment registers were reloaded.
280 pgdir[0] = 0;
281
282 // Flush the TLB for good measure, to kill the pgdir[0] mapping.
283 lcr3(boot_cr3);
284}
285
286//
287// Check the physical page allocator (page_alloc(), page_free(),
288// and page_init()).
289//
290static void
291check_page_alloc()
292{
293 struct Page *pp, *pp0, *pp1, *pp2;
294 struct Page_list fl;
295
296 // if there's a page that shouldn't be on
297 // the free list, try to make sure it
298 // eventually causes trouble.
299 LIST_FOREACH(pp0, &page_free_list, pp_link)
300 memset(page2kva(pp0), 0x97, 128);
301
302 // should be able to allocate three pages
303 pp0 = pp1 = pp2 = 0;
304 assert(page_alloc(&pp0) == 0);
305 assert(page_alloc(&pp1) == 0);
306 assert(page_alloc(&pp2) == 0);
307
308 assert(pp0);
309 assert(pp1 && pp1 != pp0);
310 assert(pp2 && pp2 != pp1 && pp2 != pp0);
311 assert(page2pa(pp0) < npage*PGSIZE);
312 assert(page2pa(pp1) < npage*PGSIZE);
313 assert(page2pa(pp2) < npage*PGSIZE);
314
315 // temporarily steal the rest of the free pages
316 fl = page_free_list;
317 LIST_INIT(&page_free_list);
318
319 // should be no free memory
320 assert(page_alloc(&pp) == -E_NO_MEM);
321
322 // free and re-allocate?
323 page_free(pp0);
324 page_free(pp1);
325 page_free(pp2);
326 pp0 = pp1 = pp2 = 0;
327 assert(page_alloc(&pp0) == 0);
328 assert(page_alloc(&pp1) == 0);
329 assert(page_alloc(&pp2) == 0);
330 assert(pp0);
331 assert(pp1 && pp1 != pp0);
332 assert(pp2 && pp2 != pp1 && pp2 != pp0);
333 assert(page_alloc(&pp) == -E_NO_MEM);
334
335 // give free list back
336 page_free_list = fl;
337
338 // free the pages we took
339 page_free(pp0);
340 page_free(pp1);
341 page_free(pp2);
342
343 cprintf("check_page_alloc() succeeded!\n");
344}
345
346//
347// Checks that the kernel part of virtual address space
348// has been setup roughly correctly(by i386_vm_init()).
349//
350// This function doesn't test every corner case,
351// in fact it doesn't test the permission bits at all,
352// but it is a pretty good sanity check.
353//
354static physaddr_t check_va2pa(pde_t *pgdir, uintptr_t va);
355
356static void
357check_boot_pgdir(void)
358{
359 uint32_t i, n;
360 pde_t *pgdir;
361
362 pgdir = boot_pgdir;
363
364 // check pages array
365 n = ROUNDUP(npage*sizeof(struct Page), PGSIZE);
366 for (i = 0; i < n; i += PGSIZE)
367 assert(check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i);
368
369
370 // check phys mem
371 for (i = 0; i < npage; i += PGSIZE)
372 assert(check_va2pa(pgdir, KERNBASE + i) == i);
373
374 // check kernel stack
375 for (i = 0; i < KSTKSIZE; i += PGSIZE)
376 assert(check_va2pa(pgdir, KSTACKTOP - KSTKSIZE + i) == PADDR(bootstack) + i);
377
378 // check for zero/non-zero in PDEs
379 for (i = 0; i < NPDENTRIES; i++) {
380 switch (i) {
381 case PDX(VPT):
382 case PDX(UVPT):
383 case PDX(KSTACKTOP-1):
384 case PDX(UPAGES):
385 assert(pgdir[i]);
386 break;
387 default:
388 if (i >= PDX(KERNBASE))
389 assert(pgdir[i]);
390 else
391 assert(pgdir[i] == 0);
392 break;
393 }
394 }
395 cprintf("check_boot_pgdir() succeeded!\n");
396}
397
398// This function returns the physical address of the page containing 'va',
399// defined by the page directory 'pgdir'. The hardware normally performs
400// this functionality for us! We define our own version to help check
401// the check_boot_pgdir() function; it shouldn't be used elsewhere.
402
403static physaddr_t
404check_va2pa(pde_t *pgdir, uintptr_t va)
405{
406 pte_t *p;
407
408 pgdir = &pgdir[PDX(va)];
409 if (!(*pgdir & PTE_P))
410 return ~0;
411 p = (pte_t*) KADDR(PTE_ADDR(*pgdir));
412 if (!(p[PTX(va)] & PTE_P))
413 return ~0;
414 return PTE_ADDR(p[PTX(va)]);
415}
416
417// --------------------------------------------------------------
418// Tracking of physical pages.
419// The 'pages' array has one 'struct Page' entry per physical page.
420// Pages are reference counted, and free pages are kept on a linked list.
421// --------------------------------------------------------------
422
423//
424// Initialize page structure and memory free list.
425// After this point, ONLY use the functions below
426// to allocate and deallocate physical memory via the page_free_list,
427// and NEVER use boot_alloc()
428//
429void
430page_init(void)
431{
432 // The example code here marks all pages as free.
433 // However this is not truly the case. What memory is free?
434 // 1) Mark page 0 as in use.
435 // This way we preserve the real-mode IDT and BIOS structures
436 // in case we ever need them. (Currently we don't, but...)
437 // 2) Mark the rest of base memory as free.
438 // 3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
439 // Mark it as in use so that it can never be allocated.
440 // 4) Then extended memory [EXTPHYSMEM, ...).
441 // Some of it is in use, some is free. Where is the kernel?
442 // Which pages are used for page tables and other data structures?
443 //
444 // Change the code to reflect this.
445 int i;
446 extern char end[];
447 struct Page *pbegin,*pend;
448 LIST_INIT(&page_free_list);
449 for (i = 0; i < npage; i++) {
450 pages[i].pp_ref = 0;
451 LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
452 }
453 LIST_REMOVE(&pages[0],pp_link);
454 pages[0].pp_ref = 1;
455 pbegin = pa2page(IOPHYSMEM);
456 pend = pa2page(PADDR(boot_freemem));
457 while(pbegin <= pend){
458 LIST_REMOVE(pbegin,pp_link);
459 pbegin->pp_ref = 1;
460 pbegin ++;
461 }
462}
463
464//
465// Initialize a Page structure.
466// The result has null links and 0 refcount.
467// Note that the corresponding physical page is NOT initialized!
468//
469static void
470page_initpp(struct Page *pp)
471{
472 memset(pp, 0, sizeof(*pp));
473}
474
475//
476// Allocates a physical page.
477// Does NOT set the contents of the physical page to zero -
478// the caller must do that if necessary.
479//
480// *pp_store -- is set to point to the Page struct of the newly allocated
481// page
482//
483// RETURNS
484// 0 -- on success
485// -E_NO_MEM -- otherwise
486//
487// Hint: use LIST_FIRST, LIST_REMOVE, and page_initpp
488// Hint: pp_ref should not be incremented
489int
490page_alloc(struct Page **pp_store)
491{
492 assert(pp_store != NULL);
493 struct Page * ret = LIST_FIRST(&page_free_list);
494 if(ret == NULL)
495 return -E_NO_MEM;
496 LIST_REMOVE(ret,pp_link);
497 page_initpp(ret);
498 (*pp_store) = ret;
499 return 0;
500}
501
502//
503// Return a page to the free list.
504// (This function should only be called when pp->pp_ref reaches 0.)
505//
506void
507page_free(struct Page *pp)
508{
509 if(pp == NULL)
510 return;
511 assert(pp->pp_ref == 0);
512 LIST_INSERT_HEAD(&page_free_list, pp, pp_link);
513 return;
514}
515
516//
517// Decrement the reference count on a page,
518// freeing it if there are no more refs.
519//
520void
521page_decref(struct Page* pp)
522{
523 if (--pp->pp_ref == 0)
524 page_free(pp);
525}
526
527// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
528// a pointer to the page table entry (PTE) for linear address 'va'.
529// This requires walking the two-level page table structure.
530//
531// If the relevant page table doesn't exist in the page directory, then:
532// - If create == 0, pgdir_walk returns NULL.
533// - Otherwise, pgdir_walk tries to allocate a new page table
534// with page_alloc. If this fails, pgdir_walk returns NULL.
535// - pgdir_walk sets pp_ref to 1 for the new page table.
536// - Finally, pgdir_walk returns a pointer into the new page table.
537//
538// Hint: you can turn a Page * into the physical address of the
539// page it refers to with page2pa() from kern/pmap.h.
540pte_t *
541pgdir_walk(pde_t *pgdir, const void *va, int create)
542{
543 struct Page *newpage;
544 // Fill this function in
545 if((pgdir[PDX(va)] & PTE_P) != 0){
546 return &(((pte_t *)KADDR(PTE_ADDR(pgdir[PDX(va)])))[PTX(va)]);
547 }else if(create == 0){
548 return NULL;
549 }else{
550 if(page_alloc(&newpage) < 0)
551 return NULL;
552 newpage->pp_ref = 1;
553 memset(page2kva(newpage),0,PGSIZE);
554 pgdir[PDX(va)] = page2pa(newpage) | PTE_P | PTE_U | PTE_W;
555 return &(((pte_t *)KADDR(PTE_ADDR(pgdir[PDX(va)])))[PTX(va)]);
556 }
557 assert(0);
558 return NULL;
559}
560
561//
562// Map the physical page 'pp' at virtual address 'va'.
563// The permissions (the low 12 bits) of the page table
564// entry should be set to 'perm|PTE_P'.
565//
566// Details
567// - If there is already a page mapped at 'va', it is page_remove()d.
568// - If necessary, on demand, allocates a page table and inserts it into
569// 'pgdir'.
570// - pp->pp_ref should be incremented if the insertion succeeds.
571// - The TLB must be invalidated if a page was formerly present at 'va'.
572//
573// RETURNS:
574// 0 on success
575// -E_NO_MEM, if page table couldn't be allocated
576//
577// Hint: The TA solution is implemented using pgdir_walk, page_remove,
578// and page2pa.
579//
580int
581page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm)
582{
583 // Fill this function in
584 pte_t *ppte = pgdir_walk(pgdir,va,1);
585 if(ppte == NULL)
586 return -E_NO_MEM;
587 if(((*ppte) & PTE_P) != 0){
588 if(PTE_ADDR(*ppte) != page2pa(pp)){
589 page_remove(pgdir,va);
590 }else{
591 //pp already mapped to va, balance the ++ operation below
592 pp->pp_ref--;
593 }
594 }
595 *ppte = page2pa(pp) | perm | PTE_P;
596 pp->pp_ref ++;
597 tlb_invalidate(pgdir,va);
598 return 0;
599}
600
601//
602// Map [la, la+size) of linear address space to physical [pa, pa+size)
603// in the page table rooted at pgdir. Size is a multiple of PGSIZE.
604// Use permission bits perm|PTE_P for the entries.
605//
606// This function is only intended to set up the ``static'' mappings
607// above UTOP. As such, it should *not* change the pp_ref field on the
608// mapped pages.
609//
610// Hint: the TA solution uses pgdir_walk
611static void
612boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
613{
614 // Fill this function in
615 size_t index;
616 pte_t *ppte;
617 assert((la&(PGSIZE-1)) == 0);
618 assert((pa&(PGSIZE-1)) == 0);
619 assert((size&(PGSIZE-1)) == 0);
620 for(index = 0;index < size;index+=PGSIZE){
621 ppte = pgdir_walk(pgdir, (void *)(la+index), 1);
622 (*ppte) = (pa+index)|perm|PTE_P;
623 }
624 return;
625}
626
627//
628// Return the page mapped at virtual address 'va'.
629// If pte_store is not zero, then we store in it the address
630// of the pte for this page. This is used by page_remove
631// but should not be used by other callers.
632//
633// Return 0 if there is no page mapped at va.
634//
635// Hint: the TA solution uses pgdir_walk and pa2page.
636//
637struct Page *
638page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
639{
640 // Fill this function in
641 pte_t *ppte = pgdir_walk(pgdir,va,0);
642 if(ppte == NULL)
643 return NULL;
644 if(pte_store != NULL)
645 (*pte_store) = ppte;
646 if(*ppte & PTE_P)
647 return pa2page(*ppte);
648 return NULL;
649}
650
651//
652// Unmaps the physical page at virtual address 'va'.
653// If there is no physical page at that address, silently does nothing.
654//
655// Details:
656// - The ref count on the physical page should decrement.
657// - The physical page should be freed if the refcount reaches 0.
658// - The pg table entry corresponding to 'va' should be set to 0.
659// (if such a PTE exists)
660// - The TLB must be invalidated if you remove an entry from
661// the pg dir/pg table.
662//
663// Hint: The TA solution is implemented using page_lookup,
664// tlb_invalidate, and page_decref.
665//
666void
667page_remove(pde_t *pgdir, void *va)
668{
669 pte_t *ppte;
670 struct Page *page = page_lookup(pgdir,va,&ppte);
671 if(page == NULL)
672 return;
673 page_decref(page);
674 *ppte = 0;
675 tlb_invalidate(pgdir,va);
676 return;
677}
678
679//
680// Invalidate a TLB entry, but only if the page tables being
681// edited are the ones currently in use by the processor.
682//
683void
684tlb_invalidate(pde_t *pgdir, void *va)
685{
686 // Flush the entry only if we're modifying the current address space.
687 // For now, there is only one address space, so always invalidate.
688 invlpg(va);
689}
690
691// check page_insert, page_remove, &c
692static void
693page_check(void)
694{
695 struct Page *pp, *pp0, *pp1, *pp2;
696 struct Page_list fl;
697 pte_t *ptep, *ptep1;
698 void *va;
699 int i;
700 // should be able to allocate three pages
701 pp0 = pp1 = pp2 = 0;
702 assert(page_alloc(&pp0) == 0);
703 assert(page_alloc(&pp1) == 0);
704 assert(page_alloc(&pp2) == 0);
705
706 assert(pp0);
707 assert(pp1 && pp1 != pp0);
708 assert(pp2 && pp2 != pp1 && pp2 != pp0);
709
710 // temporarily steal the rest of the free pages
711 fl = page_free_list;
712 LIST_INIT(&page_free_list);
713
714 // should be no free memory
715 assert(page_alloc(&pp) == -E_NO_MEM);
716
717 // there is no page allocated at address 0
718 assert(page_lookup(boot_pgdir, (void *) 0x0, &ptep) == NULL);
719
720 // there is no free memory, so we can't allocate a page table
721 assert(page_insert(boot_pgdir, pp1, 0x0, 0) < 0);
722
723 // free pp0 and try again: pp0 should be used for page table
724 page_free(pp0);
725 assert(page_insert(boot_pgdir, pp1, 0x0, 0) == 0);
726 assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
727 assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
728 assert(pp1->pp_ref == 1);
729 assert(pp0->pp_ref == 1);
730 // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
731 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
732 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
733 assert(pp2->pp_ref == 1);
734
735 // should be no free memory
736 assert(page_alloc(&pp) == -E_NO_MEM);
737
738
739 // should be able to map pp2 at PGSIZE because it's already there
740 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
741 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
742 assert(pp2->pp_ref == 1);
743
744 // pp2 should NOT be on the free list
745 // could happen in ref counts are handled sloppily in page_insert
746 assert(page_alloc(&pp) == -E_NO_MEM);
747
748 // check that pgdir_walk returns a pointer to the pte
749 ptep = KADDR(PTE_ADDR(boot_pgdir[PDX(PGSIZE)]));
750 assert(pgdir_walk(boot_pgdir, (void*)PGSIZE, 0) == ptep+PTX(PGSIZE));
751
752 // should be able to change permissions too.
753 assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, PTE_U) == 0);
754 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
755 assert(pp2->pp_ref == 1);
756 assert(*pgdir_walk(boot_pgdir, (void*) PGSIZE, 0) & PTE_U);
757
758 // should not be able to map at PTSIZE because need free page for page table
759 assert(page_insert(boot_pgdir, pp0, (void*) PTSIZE, 0) < 0);
760
761 // insert pp1 at PGSIZE (replacing pp2)
762 assert(page_insert(boot_pgdir, pp1, (void*) PGSIZE, 0) == 0);
763
764 // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
765 assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
766 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
767 // ... and ref counts should reflect this
768 assert(pp1->pp_ref == 2);
769 assert(pp2->pp_ref == 0);
770
771 // pp2 should be returned by page_alloc
772 assert(page_alloc(&pp) == 0 && pp == pp2);
773
774 // unmapping pp1 at 0 should keep pp1 at PGSIZE
775 page_remove(boot_pgdir, 0x0);
776 assert(check_va2pa(boot_pgdir, 0x0) == ~0);
777 assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
778 assert(pp1->pp_ref == 1);
779 assert(pp2->pp_ref == 0);
780
781 // unmapping pp1 at PGSIZE should free it
782 page_remove(boot_pgdir, (void*) PGSIZE);
783 assert(check_va2pa(boot_pgdir, 0x0) == ~0);
784 assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
785 assert(pp1->pp_ref == 0);
786 assert(pp2->pp_ref == 0);
787
788 // so it should be returned by page_alloc
789 assert(page_alloc(&pp) == 0 && pp == pp1);
790
791 // should be no free memory
792 assert(page_alloc(&pp) == -E_NO_MEM);
793
794#if 0
795 // should be able to page_insert to change a page
796 // and see the new data immediately.
797 memset(page2kva(pp1), 1, PGSIZE);
798 memset(page2kva(pp2), 2, PGSIZE);
799 page_insert(boot_pgdir, pp1, 0x0, 0);
800 assert(pp1->pp_ref == 1);
801 assert(*(int*)0 == 0x01010101);
802 page_insert(boot_pgdir, pp2, 0x0, 0);
803 assert(*(int*)0 == 0x02020202);
804 assert(pp2->pp_ref == 1);
805 assert(pp1->pp_ref == 0);
806 page_remove(boot_pgdir, 0x0);
807 assert(pp2->pp_ref == 0);
808#endif
809
810 // forcibly take pp0 back
811 assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
812 boot_pgdir[0] = 0;
813 assert(pp0->pp_ref == 1);
814 pp0->pp_ref = 0;
815
816 // check pointer arithmetic in pgdir_walk
817 page_free(pp0);
818 va = (void*)(PGSIZE * NPDENTRIES + PGSIZE);
819 ptep = pgdir_walk(boot_pgdir, va, 1);
820 ptep1 = KADDR(PTE_ADDR(boot_pgdir[PDX(va)]));
821 assert(ptep == ptep1 + PTX(va));
822 boot_pgdir[PDX(va)] = 0;
823 pp0->pp_ref = 0;
824
825 // check that new page tables get cleared
826 memset(page2kva(pp0), 0xFF, PGSIZE);
827 page_free(pp0);
828 pgdir_walk(boot_pgdir, 0x0, 1);
829 ptep = page2kva(pp0);
830 for(i=0; i<NPTENTRIES; i++)
831 assert((ptep[i] & PTE_P) == 0);
832 boot_pgdir[0] = 0;
833 pp0->pp_ref = 0;
834
835 // give free list back
836 page_free_list = fl;
837
838 // free the pages we took
839 page_free(pp0);
840 page_free(pp1);
841 page_free(pp2);
842
843 cprintf("page_check() succeeded!\n");
844}