From b0a700d18f0a0a8c87e1a4fff3a2108e0edb0fbc Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 16 Sep 2004 23:51:14 +0000 Subject: [PATCH] Move pagedir stuff into userprog. Move flags into their own header. --- src/Makefile.build | 2 +- src/TODO | 1 + src/threads/flags.h | 8 + src/threads/init.c | 43 +++- src/threads/init.h | 6 +- src/threads/interrupt.c | 1 + src/threads/kernel.lds.S | 2 +- src/threads/loader.S | 8 +- src/threads/mmu.h | 131 ++++++++-- src/threads/paging.c | 242 ------------------- src/threads/thread.c | 1 + src/userprog/addrspace.c | 2 +- src/userprog/pagedir.c | 107 ++++++++ src/{threads/paging.h => userprog/pagedir.h} | 11 +- 14 files changed, 289 insertions(+), 276 deletions(-) create mode 100644 src/threads/flags.h delete mode 100644 src/threads/paging.c create mode 100644 src/userprog/pagedir.c rename src/{threads/paging.h => userprog/pagedir.h} (63%) diff --git a/src/Makefile.build b/src/Makefile.build index f6eb9c4..8a73485 100644 --- a/src/Makefile.build +++ b/src/Makefile.build @@ -40,7 +40,6 @@ threads_SRC += threads/switch.S # Thread switch routine. threads_SRC += threads/interrupt.c # Interrupt core. threads_SRC += threads/intr-stubs.S # Interrupt stubs. threads_SRC += threads/synch.c # Synchronization. -threads_SRC += threads/paging.c # Page tables. threads_SRC += threads/palloc.c # Page allocator. threads_SRC += threads/malloc.c # Subpage allocator. threads_SRC += threads/start.S # Startup code. @@ -76,6 +75,7 @@ filesys_SRC += filesys/fsutil.c # Utilities. # User process code. userprog_SRC = userprog/addrspace.c # Address spaces. +userprog_SRC += userprog/pagedir.c # Page directories. userprog_SRC += userprog/exception.c # User exception handler. userprog_SRC += userprog/syscall.c # System call handler. userprog_SRC += userprog/gdt.c # GDT initialization. diff --git a/src/TODO b/src/TODO index 52f1b12..8dafda6 100644 --- a/src/TODO +++ b/src/TODO @@ -4,6 +4,7 @@ * Figure out PD/PT management API. - We should document what's in mmu.h. + - pagedir.[ch] is undocumented. * Write, test VM. diff --git a/src/threads/flags.h b/src/threads/flags.h new file mode 100644 index 0000000..dd83ed2 --- /dev/null +++ b/src/threads/flags.h @@ -0,0 +1,8 @@ +#ifndef THREADS_FLAGS_H +#define THREADS_FLAGS_H 1 + +/* EFLAGS Register. */ +#define FLAG_MBS 0x00000002 /* Must be set. */ +#define FLAG_IF 0x00000200 /* Interrupt Flag. */ + +#endif /* threads/flags.h */ diff --git a/src/threads/init.c b/src/threads/init.c index 49b26a9..dbfd56b 100644 --- a/src/threads/init.c +++ b/src/threads/init.c @@ -17,7 +17,6 @@ #include "threads/loader.h" #include "threads/malloc.h" #include "threads/mmu.h" -#include "threads/paging.h" #include "threads/palloc.h" #include "threads/test.h" #include "threads/thread.h" @@ -36,6 +35,9 @@ /* Amount of physical memory, in 4 kB pages. */ size_t ram_pages; +/* Page directory with kernel mappings only. */ +uint32_t *base_page_dir; + #ifdef FILESYS /* Format the filesystem? */ static bool format_filesys; @@ -50,6 +52,7 @@ static char *initial_program; static bool power_off; static void ram_init (void); +static void paging_init (void); static void argv_init (void); static void do_power_off (void); @@ -140,6 +143,42 @@ ram_init (void) ram_pages = *(uint32_t *) ptov (LOADER_RAM_PAGES); } +/* Populates the base page directory and page table with the + kernel virtual mapping, and then sets up the CPU to use the + new page directory. Points base_page_dir to the page + directory it creates. + + At the time this function is called, the active page table + (set up by loader.S) only maps the first 4 MB of RAM, so we + should not try to use extravagant amounts of memory. + Fortunately, there is no need to do so. */ +static void +paging_init (void) +{ + uint32_t *pd, *pt; + size_t page; + + pd = base_page_dir = palloc_get (PAL_ASSERT | PAL_ZERO); + pt = NULL; + for (page = 0; page < ram_pages; page++) + { + uintptr_t paddr = page * PGSIZE; + void *vaddr = ptov (paddr); + size_t pde_idx = pd_no (vaddr); + size_t pte_idx = pt_no (vaddr); + + if (pd[pde_idx] == 0) + { + pt = palloc_get (PAL_ASSERT | PAL_ZERO); + pd[pde_idx] = pde_create (pt); + } + + pt[pte_idx] = pte_create_kernel (vaddr, true); + } + + asm volatile ("movl %0,%%cr3" :: "r" (vtop (base_page_dir))); +} + /* Parses the command line. */ static void argv_init (void) @@ -226,6 +265,8 @@ argv_init (void) PANIC ("unknown option `%s' (use -u for help)", argv[i]); } +/* Powers down the machine we're running on, + as long as we're running on Bochs or qemu. */ void do_power_off (void) { diff --git a/src/threads/init.h b/src/threads/init.h index fafb492..622dea9 100644 --- a/src/threads/init.h +++ b/src/threads/init.h @@ -2,8 +2,12 @@ #define THREADS_INIT_H #include +#include /* Physical memory size, in 4 kB pages. */ -size_t ram_pages; +extern size_t ram_pages; + +/* Page directory with kernel mappings only. */ +extern uint32_t *base_page_dir; #endif /* threads/init.h */ diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c index fca145e..8e7d575 100644 --- a/src/threads/interrupt.c +++ b/src/threads/interrupt.c @@ -3,6 +3,7 @@ #include #include #include +#include "threads/flags.h" #include "threads/intr-stubs.h" #include "threads/io.h" #include "threads/mmu.h" diff --git a/src/threads/kernel.lds.S b/src/threads/kernel.lds.S index ce5d23d..3b7f8b1 100644 --- a/src/threads/kernel.lds.S +++ b/src/threads/kernel.lds.S @@ -1,4 +1,4 @@ -#include "loader.h" +#include "threads/loader.h" OUTPUT_FORMAT("elf32-i386") OUTPUT_ARCH("i386") diff --git a/src/threads/loader.S b/src/threads/loader.S index e87a6c6..42f4899 100644 --- a/src/threads/loader.S +++ b/src/threads/loader.S @@ -39,7 +39,7 @@ */ #include "threads/loader.h" -#include "threads/mmu.h" +/*#include "threads/mmu.h"*/ #### Kernel loader. @@ -133,14 +133,16 @@ start: rep stosl # Set PDEs for 0 and LOADER_PHYS_BASE to point to the page table. +# See comments near the PG_* macros in paging.h for a description of +# the values stored here. - movl $0x11000 | PG_U | PG_W | PG_P, %eax + movl $0x11007, %eax movl %eax, %es:0 movl %eax, %es:LOADER_PHYS_BASE >> 20 # Initialize page table. - movl $PG_U | PG_W | PG_P, %eax + movl $7, %eax movl $0x400, %ecx 1: stosl addl $0x1000, %eax diff --git a/src/threads/mmu.h b/src/threads/mmu.h index 4e9340a..304053b 100644 --- a/src/threads/mmu.h +++ b/src/threads/mmu.h @@ -1,13 +1,60 @@ #ifndef THREADS_MMU_H #define THREADS_MMU_H -#ifndef __ASSEMBLER__ #include #include -#endif +#include #include "threads/loader.h" +/* Virtual to physical translation works like this on an x86: + + - The top 10 bits of the virtual address (bits 22:31) are used + to index into the page directory. If the PDE is marked + "present," the physical address of a page table is read from + the PDE thus obtained. If the PDE is marked "not present" + then a page fault occurs. + + - The next 10 bits of the virtual address (bits 12:21) are + used to index into the page table. If the PTE is marked + "present," the physical address of a data page is read from + the PTE thus obtained. If the PTE is marked "not present" + then a page fault occurs. + + - The bottom 12 bits of the virtual address (bits 0:11) are + added to the data page's physical base address, producing + the final physical address. + + + 32 22 12 0 + +--------------------------------------------------------------------+ + | Page Directory Index | Page Table Index | Page Offset | + +--------------------------------------------------------------------+ + | | | + _______/ _______/ _____/ + / / / + / Page Directory / Page Table / Data Page + / .____________. / .____________. / .____________. + |1,023|____________| |1,023|____________| | |____________| + |1,022|____________| |1,022|____________| | |____________| + |1,021|____________| |1,021|____________| \__\|____________| + |1,020|____________| |1,020|____________| /|____________| + | | | | | | | | + | | | \____\| |_ | | + | | . | /| . | \ | . | + \____\| . |_ | . | | | . | + /| . | \ | . | | | . | + | . | | | . | | | . | + | | | | | | | | + |____________| | |____________| | |____________| + 4|____________| | 4|____________| | |____________| + 3|____________| | 3|____________| | |____________| + 2|____________| | 2|____________| | |____________| + 1|____________| | 1|____________| | |____________| + 0|____________| \__\0|____________| \____\|____________| + / / +*/ + #define MASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT)) /* Page offset (bits 0:11). */ @@ -26,21 +73,12 @@ #define PDBITS 10 /* Number of page dir bits. */ #define PDMASK MASK(PDSHIFT, PDBITS) -#ifndef __ASSEMBLER__ /* Offset within a page. */ static inline unsigned pg_ofs (void *va) { return (uintptr_t) va & PGMASK; } -/* Page number. */ +/* Virtual page number. */ static inline uintptr_t pg_no (void *va) { return (uintptr_t) va >> PTSHIFT; } -/* Page table number. */ -static inline unsigned pt_no (void *va) { - return ((uintptr_t) va & PTMASK) >> PTSHIFT; -} - -/* Page directory number. */ -static inline uintptr_t pd_no (void *va) { return (uintptr_t) va >> PDSHIFT; } - /* Round up to nearest page boundary. */ static inline void *pg_round_up (void *va) { return (void *) (((uintptr_t) va + PGSIZE - 1) & ~PGMASK); @@ -72,17 +110,74 @@ vtop (void *vaddr) return (uintptr_t) vaddr - (uintptr_t) PHYS_BASE; } -#endif + +/* Page directories and page tables. -/* Page Directory Entry (PDE) and Page Table Entry (PTE) flags. */ + For more information see [IA32-v3] pages 3-23 to 3-28. + + PDEs and PTEs share a common format: + + 32 12 0 + +------------------------------------+------------------------+ + | Physical Address | Flags | + +------------------------------------+------------------------+ + + In a PDE, the physical address points to a page table. + In a PTE, the physical address points to a data or code page. + The important flags are listed below. + When a PDE or PTE is not "present", the other flags are + ignored. + A PDE or PTE that is initialized to 0 will be interpreted as + "not present", which is just fine. */ #define PG_P 0x1 /* 1=present, 0=not present. */ #define PG_W 0x2 /* 1=read/write, 0=read-only. */ #define PG_U 0x4 /* 1=user/kernel, 0=kernel only. */ #define PG_A 0x20 /* 1=accessed, 0=not acccessed. */ -#define PG_D 0x40 /* 1=dirty, 0=not dirty. */ +#define PG_D 0x40 /* 1=dirty, 0=not dirty (PTEs only). */ -/* EFLAGS Register. */ -#define FLAG_MBS 0x00000002 /* Must be set. */ -#define FLAG_IF 0x00000200 /* Interrupt Flag. */ +/* Obtains page directory index from a virtual address. */ +static inline uintptr_t pd_no (void *va) { return (uintptr_t) va >> PDSHIFT; } + +/* Returns a PDE that points to page table PT. */ +static inline uint32_t pde_create (uint32_t *pt) { + ASSERT (pg_ofs (pt) == 0); + return vtop (pt) | PG_U | PG_P | PG_W; +} + +/* Returns a pointer to the page table that page directory entry + PDE, which must "present", points to. */ +static inline uint32_t *pde_get_pt (uint32_t pde) { + ASSERT (pde & PG_P); + return ptov (pde & ~PGMASK); +} + +/* Obtains page table index from a virtual address. */ +static inline unsigned pt_no (void *va) { + return ((uintptr_t) va & PTMASK) >> PTSHIFT; +} + +/* Returns a PTE that points to PAGE. + The PTE's page is readable. + If WRITABLE is true then it will be writable as well. + The page will be usable only by ring 0 code (the kernel). */ +static inline uint32_t pte_create_kernel (uint32_t *page, bool writable) { + ASSERT (pg_ofs (page) == 0); + return vtop (page) | PG_P | (writable ? PG_W : 0); +} + +/* Returns a PTE that points to PAGE. + The PTE's page is readable. + If WRITABLE is true then it will be writable as well. + The page will be usable by both user and kernel code. */ +static inline uint32_t pte_create_user (uint32_t *page, bool writable) { + return pte_create_kernel (page, writable) | PG_U; +} + +/* Returns a pointer to the page that page table entry PTE, which + must "present", points to. */ +static inline void *pte_get_page (uint32_t pte) { + ASSERT (pte & PG_P); + return ptov (pte & ~PGMASK); +} #endif /* threads/mmu.h */ diff --git a/src/threads/paging.c b/src/threads/paging.c deleted file mode 100644 index c0d89ad..0000000 --- a/src/threads/paging.c +++ /dev/null @@ -1,242 +0,0 @@ -#include "threads/paging.h" -#include -#include -#include -#include "threads/init.h" -#include "threads/mmu.h" -#include "threads/palloc.h" - -static uint32_t *base_page_dir; - -static uint32_t make_pde (uint32_t *pt) { - ASSERT (pg_ofs (pt) == 0); - return vtop (pt) | PG_U | PG_P | PG_W; -} - -static uint32_t make_kernel_pte (uint32_t *page, bool writable) { - ASSERT (pg_ofs (page) == 0); - return vtop (page) | PG_P | (writable ? PG_W : 0); -} - -static uint32_t make_user_pte (uint32_t *page, bool writable) { - return make_kernel_pte (page, writable) | PG_U; -} - -static uint32_t * -pde_get_pt (uint32_t pde) -{ - ASSERT (pde & PG_P); - - return ptov (pde & ~PGMASK); -} - -static void * -pte_get_page (uint32_t pte) -{ - ASSERT (pte & PG_P); - - return ptov (pte & ~PGMASK); -} - -/* Populates the base page directory and page table with the - kernel virtual mapping, and then sets up the CPU to use the - new page directory. - - At the time this function is called, the active page table - (set up by loader.S) only maps the first 4 MB of RAM, so we - should not try to use extravagant amounts of memory. - Fortunately, there is no need to do so. */ -void -paging_init (void) -{ - uint32_t *pd, *pt; - size_t page; - - pd = base_page_dir = palloc_get (PAL_ASSERT | PAL_ZERO); - pt = NULL; - for (page = 0; page < ram_pages; page++) - { - uintptr_t paddr = page * PGSIZE; - void *vaddr = ptov (paddr); - size_t pde_idx = pd_no (vaddr); - size_t pte_idx = pt_no (vaddr); - - if (pd[pde_idx] == 0) - { - pt = palloc_get (PAL_ASSERT | PAL_ZERO); - pd[pde_idx] = make_pde (pt); - } - - pt[pte_idx] = make_kernel_pte (vaddr, true); - } - - pagedir_activate (pd); -} - -uint32_t * -pagedir_create (void) -{ - uint32_t *pd = palloc_get (0); - memcpy (pd, base_page_dir, PGSIZE); - return pd; -} - -void -pagedir_destroy (uint32_t *pd) -{ - void *kpage, *upage; - unsigned pde_idx; - - /* Destroy user pages. */ - for (kpage = pagedir_first (pd, &upage); kpage != NULL; - kpage = pagedir_next (pd, &upage)) - palloc_free (kpage); - - /* Destroy page table pages. */ - for (pde_idx = 0; pde_idx < pd_no (PHYS_BASE); pde_idx++) - { - uint32_t pde = pd[pde_idx]; - - if (pde != 0) - { - uint32_t *pt = pde_get_pt (pde); - palloc_free (pt); - } - } - - /* Destroy page directory. */ - palloc_free (pd); -} - -static uint32_t * -lookup_page (uint32_t *pd, void *upage, bool create) -{ - uint32_t *pt; - uint32_t *pde; - - ASSERT (pd != NULL); - ASSERT (pg_ofs (upage) == 0); - ASSERT (upage < PHYS_BASE); - - /* Check for a page table for UPAGE. - If one is missing, create one if requested. */ - pde = pd + pd_no (upage); - if (*pde == 0) - { - if (create) - { - pt = palloc_get (PAL_ZERO); - if (pt == NULL) - return NULL; - - *pde = make_pde (pt); - } - else - return NULL; - } - - /* Return the page table entry. */ - pt = pde_get_pt (*pde); - return &pt[pt_no (upage)]; -} - -bool -pagedir_set_page (uint32_t *pd, void *upage, void *kpage, - bool writable) -{ - uint32_t *pte; - - ASSERT (pg_ofs (kpage) == 0); - - pte = lookup_page (pd, upage, true); - if (pte != NULL) - { - *pte = make_user_pte (kpage, writable); - return true; - } - else - return false; -} - -void * -pagedir_get_page (uint32_t *pd, void *upage) -{ - uint32_t *pte = lookup_page (pd, upage, false); - return pte != NULL && *pte != 0 ? pte_get_page (*pte) : NULL; -} - -void -pagedir_clear_page (uint32_t *pd, void *upage) -{ - uint32_t *pte = lookup_page (pd, upage, false); - if (pte != NULL) - *pte = 0; -} - -static uint32_t * -scan_pt (uint32_t *pt, unsigned pde_idx, unsigned pte_idx, void **upage) -{ - for (; pte_idx < PGSIZE / sizeof *pt; pte_idx++) - { - uint32_t pte = pt[pte_idx]; - - if (pte != 0) - { - void *kpage = pte_get_page (pte); - if (kpage != NULL) - { - *upage = (void *) ((pde_idx << PDSHIFT) | (pte_idx << PTSHIFT)); - return kpage; - } - } - } - - return NULL; -} - -static void * -scan_pd (uint32_t *pd, unsigned pde_idx, void **upage) -{ - for (; pde_idx < pd_no (PHYS_BASE); pde_idx++) - { - uint32_t pde = pd[pde_idx]; - - if (pde != 0) - { - void *kpage = scan_pt (pde_get_pt (pde), pde_idx, 0, upage); - if (kpage != NULL) - return kpage; - } - } - - return NULL; -} - -void * -pagedir_first (uint32_t *pd, void **upage) -{ - return scan_pd (pd, 0, upage); -} - -void * -pagedir_next (uint32_t *pd, void **upage) -{ - unsigned pde_idx, pte_idx; - void *kpage; - - pde_idx = pd_no (*upage); - pte_idx = pt_no (*upage); - kpage = scan_pt (pde_get_pt (pd[pde_idx]), - pde_idx, pte_idx + 1, upage); - if (kpage == NULL) - kpage = scan_pd (pd, pde_idx + 1, upage); - return kpage; -} - -void -pagedir_activate (uint32_t *pd) -{ - if (pd == NULL) - pd = base_page_dir; - asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd))); -} diff --git a/src/threads/thread.c b/src/threads/thread.c index 90a4dcd..a1c98a6 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -3,6 +3,7 @@ #include #include #include +#include "threads/flags.h" #include "threads/interrupt.h" #include "threads/intr-stubs.h" #include "threads/mmu.h" diff --git a/src/userprog/addrspace.c b/src/userprog/addrspace.c index 65c09e4..f535bad 100644 --- a/src/userprog/addrspace.c +++ b/src/userprog/addrspace.c @@ -4,12 +4,12 @@ #include #include #include +#include "userprog/pagedir.h" #include "userprog/tss.h" #include "filesys/file.h" #include "filesys/filesys.h" #include "threads/init.h" #include "threads/mmu.h" -#include "threads/paging.h" #include "threads/palloc.h" #include "threads/thread.h" diff --git a/src/userprog/pagedir.c b/src/userprog/pagedir.c new file mode 100644 index 0000000..1bad9b2 --- /dev/null +++ b/src/userprog/pagedir.c @@ -0,0 +1,107 @@ +#include "userprog/pagedir.h" +#include +#include +#include +#include "threads/init.h" +#include "threads/mmu.h" +#include "threads/palloc.h" + +uint32_t * +pagedir_create (void) +{ + uint32_t *pd = palloc_get (0); + memcpy (pd, base_page_dir, PGSIZE); + return pd; +} + +void +pagedir_destroy (uint32_t *pd) +{ + uint32_t *pde; + + for (pde = pd; pde < pd + PGSIZE / sizeof *pde; pde++) + if (*pde & PG_P) + { + uint32_t *pt = pde_get_pt (*pde); + uint32_t *pte; + + for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++) + if (*pte & PG_P) + palloc_free (pte_get_page (*pte)); + palloc_free (pt); + } + palloc_free (pd); +} + +static uint32_t * +lookup_page (uint32_t *pd, void *upage, bool create) +{ + uint32_t *pt; + uint32_t *pde; + + ASSERT (pd != NULL); + ASSERT (pg_ofs (upage) == 0); + ASSERT (upage < PHYS_BASE); + + /* Check for a page table for UPAGE. + If one is missing, create one if requested. */ + pde = pd + pd_no (upage); + if (*pde == 0) + { + if (create) + { + pt = palloc_get (PAL_ZERO); + if (pt == NULL) + return NULL; + + *pde = pde_create (pt); + } + else + return NULL; + } + + /* Return the page table entry. */ + pt = pde_get_pt (*pde); + return &pt[pt_no (upage)]; +} + +bool +pagedir_set_page (uint32_t *pd, void *upage, void *kpage, + bool writable) +{ + uint32_t *pte; + + ASSERT (pg_ofs (kpage) == 0); + + pte = lookup_page (pd, upage, true); + if (pte != NULL) + { + *pte = pte_create_user (kpage, writable); + return true; + } + else + return false; +} + +void * +pagedir_get_page (uint32_t *pd, void *upage) +{ + uint32_t *pte = lookup_page (pd, upage, false); + return pte != NULL && *pte != 0 ? pte_get_page (*pte) : NULL; +} + +void +pagedir_clear_page (uint32_t *pd, void *upage) +{ + uint32_t *pte = lookup_page (pd, upage, false); + if (pte != NULL) + *pte = 0; +} + +void +pagedir_activate (uint32_t *pd) +{ + if (pd == NULL) + pd = base_page_dir; + asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd))); +} diff --git a/src/threads/paging.h b/src/userprog/pagedir.h similarity index 63% rename from src/threads/paging.h rename to src/userprog/pagedir.h index 8481b17..e2fd8a6 100644 --- a/src/threads/paging.h +++ b/src/userprog/pagedir.h @@ -1,11 +1,9 @@ -#ifndef THREADS_PAGING_H -#define THREADS_PAGING_H +#ifndef USERPROG_PAGEDIR_H +#define USERPROG_PAGEDIR_H 1 #include #include -void paging_init (void); - uint32_t *pagedir_create (void); void pagedir_destroy (uint32_t *); bool pagedir_set_page (uint32_t *pagedir, void *upage, void *kpage, @@ -13,9 +11,6 @@ bool pagedir_set_page (uint32_t *pagedir, void *upage, void *kpage, void *pagedir_get_page (uint32_t *pagedir, void *upage); void pagedir_clear_page (uint32_t *pagedir, void *upage); -void *pagedir_first (uint32_t *pagedir, void **upage); -void *pagedir_next (uint32_t *pagedir, void **upage); - void pagedir_activate (uint32_t *pagedir); -#endif /* threads/paging.h */ +#endif /* userprog/pagedir.h */ -- 2.30.2