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