From: Ben Pfaff Date: Thu, 26 Aug 2004 19:06:27 +0000 (+0000) Subject: Start work on program loading. X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=8ca3547f6c4d6d01a76d3ce642a0c1bf884c4c2a Start work on program loading. --- diff --git a/src/Makefile.inc b/src/Makefile.inc index 19b911c..6ed310e 100644 --- a/src/Makefile.inc +++ b/src/Makefile.inc @@ -5,6 +5,7 @@ VPATH := $(TOP_SRCDIR)/threads VPATH := $(VPATH):$(TOP_SRCDIR)/devices VPATH := $(VPATH):$(TOP_SRCDIR)/lib VPATH := $(VPATH):$(TOP_SRCDIR)/filesys +VPATH := $(VPATH):$(TOP_SRCDIR)/userprog -include *.d @@ -21,6 +22,7 @@ THREADS_SRC += switch.S # Thread switch routine. THREADS_SRC += interrupt.c # Interrupt core. THREADS_SRC += intr-stubs.S # Interrupt stubs. THREADS_SRC += synch.c # Synchronization. +THREADS_SRC += paging.c # Page tables. THREADS_SRC += palloc.c # Page allocator. THREADS_SRC += malloc.c # Subpage allocator. @@ -43,6 +45,9 @@ FILESYS_SRC = filesys.c # Filesystem core. FILESYS_SRC += file.c # Individual files. FILESYS_SRC += filesys-stub.c # Stub helper code. +# User process code. +USERPROG_SRC = addrspace.c # Address spaces. + # Objects. OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES))) diff --git a/src/threads/init.c b/src/threads/init.c index 477676e..f7702cd 100644 --- a/src/threads/init.c +++ b/src/threads/init.c @@ -1,3 +1,4 @@ +#include "init.h" #include #include #include @@ -8,6 +9,7 @@ #include "lib.h" #include "malloc.h" #include "mmu.h" +#include "paging.h" #include "palloc.h" #include "random.h" #include "serial.h" @@ -24,34 +26,20 @@ size_t kernel_pages; /* Amount of physical memory, in 4 kB pages. */ size_t ram_pages; -static void init_page_table (void); -static void setup_gdt (void); +static void gdt_init (void); void power_off (void); -struct thread *a, *b; - static void -tfunc (void *aux UNUSED) +main_thread (void *aux UNUSED) { - for (;;) - { - size_t count, i; - if (random_ulong () % 5 == 0) - { - printk ("%s exiting\n", thread_current ()->name); - break; - } - count = random_ulong () % 25 * 10000; - printk ("%s waiting %zu: ", thread_current ()->name, count); - for (i = 0; i < count; i++); - printk ("%s\n", thread_current ()->name); - } + thread_execute ("a.out"); } int main (void) { extern char _text, _end, __bss_start; + struct thread *t; /* Clear out the BSS segment. */ memset (&__bss_start, 0, &_end - &__bss_start); @@ -71,9 +59,8 @@ main (void) is free. Give it to the page allocator. */ palloc_init ((void *) (KERN_BASE + kernel_pages * NBPG), (void *) (PHYS_BASE + ram_pages * NBPG)); - - init_page_table (); - setup_gdt (); + paging_init (); + gdt_init (); malloc_init (); random_init (); @@ -84,57 +71,18 @@ main (void) #ifdef FILESYS filesys_init (false); + filesys_self_test (); #endif thread_init (); - { - struct thread *t; - int i; - - for (i = 0; i < 4; i++) - { - char name[2]; - name[0] = 'a' + i; - name[1] = 0; - t = thread_create (name, tfunc, NULL); - } - thread_start (t); - } + t = thread_create ("main", main_thread, NULL); + thread_start (t); printk ("Done!\n"); return 0; } -/* Populates the page directory and page table with the kernel - virtual mapping. */ -static void -init_page_table (void) -{ - uint32_t *pd, *pt; - uint32_t paddr; - - pd = palloc_get (PAL_ASSERT | PAL_ZERO); - pt = NULL; - for (paddr = 0; paddr < NBPG * ram_pages; paddr += NBPG) - { - uint32_t vaddr = paddr + PHYS_BASE; - size_t pde_idx = PDENO(vaddr); - size_t pte_idx = PTENO(vaddr); - - if (pd[pde_idx] == 0) - { - pt = palloc_get (PAL_ASSERT | PAL_ZERO); - pd[pde_idx] = (uint32_t) vtop (pt) | PG_U | PG_W | PG_P; - } - - pt[pte_idx] = paddr | PG_U | PG_W | PG_P; - } - - /* Set the page table. */ - asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd))); -} - static uint64_t make_seg_desc (uint32_t base, uint32_t limit, @@ -184,7 +132,7 @@ struct tss *tss; /* Sets up a proper GDT. The bootstrap loader's GDT didn't include user-mode selectors or a TSS. */ static void -setup_gdt (void) +gdt_init (void) { uint64_t gdtr_operand; @@ -192,7 +140,7 @@ setup_gdt (void) few fields of it are ever referenced, and those are the only ones we initialize. */ tss = palloc_get (PAL_ASSERT | PAL_ZERO); - tss->esp0 = (uint32_t) ptov(0xc0020000); + tss->esp0 = (uint32_t) ptov(0x20000); tss->ss0 = SEL_KDSEG; tss->bitmap = 0xdfff; diff --git a/src/threads/paging.c b/src/threads/paging.c new file mode 100644 index 0000000..190d4fc --- /dev/null +++ b/src/threads/paging.c @@ -0,0 +1,229 @@ +#include "paging.h" +#include +#include +#include "init.h" +#include "lib.h" +#include "mmu.h" +#include "palloc.h" + +static uint32_t *base_page_dir; + +static uint32_t +make_pde (uint32_t *pagetab) +{ + ASSERT (PGOFS ((uintptr_t) pagetab) == 0); + + return vtop (pagetab) | PG_U | PG_P | PG_W; +} + +static uint32_t +make_pte (uint32_t *page, bool writable) +{ + uint32_t entry; + + ASSERT (PGOFS ((uintptr_t) page) == 0); + + entry = vtop (page) | PG_U | PG_P; + if (writable) + entry |= PG_W; + return entry; +} + +static uint32_t * +pde_get_pagetab (uint32_t pde) +{ + ASSERT (pde & PG_P); + + return ptov (PGROUNDDOWN (pde)); +} + +static void * +pte_get_page (uint32_t pte) +{ + ASSERT (pte & PG_P); + + return ptov (PGROUNDDOWN (pte)); +} + +/* 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 + only maps the first 4 MB of RAM, so it 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 * NBPG; + void *vaddr = ptov (paddr); + size_t pde_idx = PDENO ((uintptr_t) vaddr); + size_t pte_idx = PTENO ((uintptr_t) vaddr); + + if (pd[pde_idx] == 0) + { + pt = palloc_get (PAL_ASSERT | PAL_ZERO); + pd[pde_idx] = make_pde (pt); + } + + pt[pte_idx] = make_pte (vaddr, true); + } + + /* Set the page table. */ + asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd))); +} + +uint32_t * +pagedir_create (void) +{ + uint32_t *pd = palloc_get (0); + memcpy (pd, base_page_dir, NBPG); + return pd; +} + +void +pagedir_destroy (uint32_t *pd) +{ + void *kpage, *upage; + + for (kpage = pagedir_first (pd, &upage); kpage != NULL; + kpage = pagedir_next (pd, &upage)) + palloc_free (kpage); + palloc_free (pd); +} + +static uint32_t * +lookup_page (uint32_t *pagedir, void *upage, bool create) +{ + uint32_t *pagetab; + uint32_t *pde; + + ASSERT (pagedir != NULL); + ASSERT (PGOFS ((uintptr_t) upage) == 0); + ASSERT ((uintptr_t) upage < PHYS_BASE); + + /* Check for a page table for UPAGE. + If one is missing, create one if requested. */ + pde = pagedir + PDENO ((uint32_t) upage); + if (*pde == 0) + { + if (create) + { + pagetab = palloc_get (PAL_ZERO); + if (pagetab == NULL) + return NULL; + + *pde = make_pde (pagetab); + } + else + return NULL; + } + + /* Return the page table entry. */ + pagetab = pde_get_pagetab (*pde); + return &pagetab[PTENO ((uintptr_t) upage)]; +} + +bool +pagedir_set_page (uint32_t *pagedir, void *upage, void *kpage, + bool writable) +{ + uint32_t *pte; + + ASSERT (PGOFS ((uintptr_t) kpage) == 0); + + pte = lookup_page (pagedir, upage, true); + if (pte != NULL) + { + *pte = make_pte (kpage, writable); + return true; + } + else + return false; +} + +void * +pagedir_get_page (uint32_t *pagedir, void *upage) +{ + uint32_t *pte = lookup_page (pagedir, upage, false); + return pte != NULL && *pte != 0 ? pte_get_page (*pte) : NULL; +} + +void +pagedir_clear_page (uint32_t *pagedir, void *upage) +{ + uint32_t *pte = lookup_page (pagedir, 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 < NBPG / 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 << PGSHIFT)); + return kpage; + } + } + } + + return NULL; +} + +static void * +scan_pd (uint32_t *pd, unsigned pde_idx, void **upage) +{ + for (; pde_idx < PDENO (PHYS_BASE); pde_idx++) + { + uint32_t pde = pd[pde_idx]; + + if (pde != 0) + { + void *kpage = scan_pt (pde_get_pagetab (pde), pde_idx, 0, upage); + if (kpage != NULL) + return kpage; + } + } + + return NULL; +} + +void * +pagedir_first (uint32_t *pagedir, void **upage) +{ + return scan_pd (pagedir, 0, upage); +} + +void * +pagedir_next (uint32_t *pd, void **upage) +{ + unsigned pde_idx, pte_idx; + void *kpage; + + pde_idx = PDENO (*upage); + pte_idx = PTENO (*upage); + kpage = scan_pt (pde_get_pagetab (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 *pagedir); diff --git a/src/threads/paging.h b/src/threads/paging.h new file mode 100644 index 0000000..02fa3ca --- /dev/null +++ b/src/threads/paging.h @@ -0,0 +1,21 @@ +#ifndef HEADER_PAGING_H +#define HEADER_PAGING_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, + bool writable); +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 /* paging.h */ diff --git a/src/threads/thread.c b/src/threads/thread.c index 0c3c544..82d33f0 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -5,6 +5,7 @@ #include "lib.h" #include "mmu.h" #include "palloc.h" +#include "random.h" uint32_t thread_stack_ofs = offsetof (struct thread, stack); @@ -71,6 +72,18 @@ thread_current (void) return stack_to_thread (esp); } +#ifdef USERPROG +void +thread_execute (const char *filename) +{ + struct thread *t = thread_current (); + + if (!addrspace_load (&t->addrspace, filename)) + panic ("%s: program load failed", filename); + panic ("%s: loaded", filename); +} +#endif + void thread_ready (struct thread *t) { @@ -173,3 +186,37 @@ thread_sleep (void) thread_current ()->status = THREAD_BLOCKED; thread_schedule (); } + +static void +tfunc (void *aux UNUSED) +{ + for (;;) + { + size_t count, i; + if (random_ulong () % 5 == 0) + { + printk ("%s exiting\n", thread_current ()->name); + break; + } + count = random_ulong () % 25 * 10000; + printk ("%s waiting %zu: ", thread_current ()->name, count); + for (i = 0; i < count; i++); + printk ("%s\n", thread_current ()->name); + } +} + +void +thread_self_test (void) +{ + struct thread *t; + int i; + + for (i = 0; i < 4; i++) + { + char name[2]; + name[0] = 'a' + i; + name[1] = 0; + t = thread_create (name, tfunc, NULL); + } + thread_start (t); +} diff --git a/src/threads/thread.h b/src/threads/thread.h index b72c372..a9b3251 100644 --- a/src/threads/thread.h +++ b/src/threads/thread.h @@ -4,6 +4,10 @@ #include #include "list.h" +#ifdef USERPROG +#include "addrspace.h" +#endif + enum thread_status { THREAD_RUNNING, @@ -17,7 +21,10 @@ struct thread enum thread_status status; char name[16]; uint32_t *stack; - struct list_elem rq_elem; + list_elem rq_elem; +#ifdef USERPROG + struct addrspace addrspace; +#endif }; void thread_init (void); @@ -27,6 +34,10 @@ struct thread *thread_create (const char *name, void thread_destroy (struct thread *); struct thread *thread_current (void); +#ifdef USERPROG +void thread_execute (const char *filename); +#endif + void thread_start (struct thread *); void thread_ready (struct thread *); void thread_exit (void); @@ -35,4 +46,6 @@ void thread_yield (void); void thread_sleep (void); void thread_schedule (void); +void thread_self_test (void); + #endif /* thread.h */ diff --git a/src/userprog/Makefile b/src/userprog/Makefile new file mode 100644 index 0000000..495615d --- /dev/null +++ b/src/userprog/Makefile @@ -0,0 +1,3 @@ +all: +%: + $(MAKE) -C build $@ diff --git a/src/userprog/addrspace.c b/src/userprog/addrspace.c index effd25f..4e317c5 100644 --- a/src/userprog/addrspace.c +++ b/src/userprog/addrspace.c @@ -1,12 +1,26 @@ #include "addrspace.h" +#include +#include "debug.h" +#include "file.h" +#include "filesys.h" +#include "lib.h" +#include "mmu.h" +#include "malloc.h" +#include "paging.h" +#include "palloc.h" /* We load ELF binaries. The following definitions are taken - from the ELF specification more-or-less literally. */ + from the ELF specification more-or-less verbatim. */ /* ELF types. */ typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off; typedef uint16_t Elf32_Half; +#define PE32Wx PRIx32 +#define PE32Ax PRIx32 +#define PE32Ox PRIx32 +#define PE32Hx PRIx16 + /* Executable header. This appears at the very beginning of an ELF binary. */ struct Elf32_Ehdr @@ -41,14 +55,20 @@ struct Elf32_Phdr Elf32_Word p_align; }; -/* Values for p_type in struct Elf32_Phdr. */ -#define PT_NULL 0 /* Ignore this program header. */ -#define PT_LOAD 1 /* Loadable segment. */ -#define PT_DYNAMIC 2 /* Dynamic linking info. */ -#define PT_INTERP 3 /* Name of dynamic loader. */ -#define PT_NOTE 4 /* Auxiliary info. */ -#define PT_SHLIB 5 /* Reserved. */ -#define PT_PHDR 6 /* Program header table. */ +/* Values for p_type. */ +#define PT_NULL 0 /* Ignore. */ +#define PT_LOAD 1 /* Loadable segment. */ +#define PT_DYNAMIC 2 /* Dynamic linking info. */ +#define PT_INTERP 3 /* Name of dynamic loader. */ +#define PT_NOTE 4 /* Auxiliary info. */ +#define PT_SHLIB 5 /* Reserved. */ +#define PT_PHDR 6 /* Program header table. */ +#define PT_STACK 0x6474e551 /* Stack segment. */ + +/* Flags for p_flags. */ +#define PF_X 1 /* Executable. */ +#define PF_W 2 /* Writable. */ +#define PF_R 4 /* Readable. */ #define LOAD_ERROR(MSG) \ do { \ @@ -58,11 +78,81 @@ struct Elf32_Phdr goto error; \ } while (0) +static bool +load_segment (struct addrspace *as, struct file *file, + const struct Elf32_Phdr *phdr) +{ + uintptr_t start, end; + uint8_t *upage; + off_t filesz_left; + + ASSERT (as != NULL); + ASSERT (file != NULL); + ASSERT (phdr != NULL); + ASSERT (phdr->p_type == PT_LOAD); + + /* p_offset and p_vaddr must be congruent modulo NBPG. */ + if (phdr->p_offset % NBPG != phdr->p_vaddr % NBPG) + { + printk ("%#08"PE32Ox" and %#08"PE32Ax" not congruent modulo %#x\n", + phdr->p_offset, phdr->p_vaddr, (unsigned) NBPG); + return false; + } + + /* p_memsz must be at least as big as p_filesz. */ + if (phdr->p_memsz < phdr->p_filesz) + { + printk ("p_memsz (%08"PE32Wx") < p_filesz (%08"PE32Wx")\n", + phdr->p_memsz, phdr->p_filesz); + return false; + } + + /* Validate virtual memory region to be mapped. */ + start = PGROUNDDOWN (phdr->p_vaddr); + end = PGROUNDUP (phdr->p_vaddr + phdr->p_memsz); + if (start >= PHYS_BASE || end >= PHYS_BASE || end < start) + { + printk ("bad virtual region %08lx...%08lx\n", + (unsigned long) start, (unsigned long) end); + return false; + } + + filesz_left = phdr->p_filesz + (phdr->p_vaddr - start); + file_seek (file, ROUND_DOWN (phdr->p_offset, NBPG)); + for (upage = (uint8_t *) start; upage < (uint8_t *) end; upage += NBPG) + { + size_t read_bytes = filesz_left >= NBPG ? NBPG : filesz_left; + size_t zero_bytes = NBPG - read_bytes; + uint8_t *kpage = palloc_get (0); + if (kpage == NULL) + return false; + + if (file_read (file, kpage, read_bytes) != (int) read_bytes) + return false; + memset (kpage + read_bytes, 0, zero_bytes); + filesz_left -= read_bytes; + + if (pagedir_get_page (as->pagedir, upage)) + { + palloc_free (kpage); + return false; + } + pagedir_set_page (as->pagedir, upage, kpage, true); + } + + return true; +} + bool addrspace_load (struct addrspace *as, const char *filename) { - Elf32_Ehdr ehdr; - struct file *file; + struct Elf32_Ehdr ehdr; + struct file *file = NULL; + off_t file_ofs; + bool success = false; + int i; + + as->pagedir = pagedir_create (); file = filesys_open (filename); if (file == NULL) @@ -71,25 +161,72 @@ addrspace_load (struct addrspace *as, const char *filename) /* Read and verify executable header. */ if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr) LOAD_ERROR (("error reading executable header")); - if (memcmp (ehdr.e_ident, "\x7fELF\1\1\1", 7) != 0) - LOAD_ERROR (("not an ELF file")); + if (memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7) != 0) + LOAD_ERROR (("file is not ELF")); if (ehdr.e_type != 2) - LOAD_ERROR (("not an executable")); + LOAD_ERROR (("ELF file is not an executable")); if (ehdr.e_machine != 3) - LOAD_ERROR (("not an x86 binary")); + LOAD_ERROR (("ELF executable is not x86")); if (ehdr.e_version != 1) - LOAD_ERROR (("unknown ELF version %d", (int) ehdr.e_version)); + LOAD_ERROR (("ELF executable hasunknown version %d", + (int) ehdr.e_version)); if (ehdr.e_phentsize != sizeof (struct Elf32_Phdr)) - LOAD_ERROR (("bad program header size", (int) ehdr.e_phentsize)); + LOAD_ERROR (("bad ELF program header size")); if (ehdr.e_phnum > 1024) - LOAD_ERROR (("too many program headers")); + LOAD_ERROR (("too many ELF program headers")); /* Read program headers. */ + file_ofs = ehdr.e_phoff; + printk ("e_phnum=%d\n", ehdr.e_phnum); + for (i = 0; i < ehdr.e_phnum; i++) + { + struct Elf32_Phdr phdr; - as->page_dir = create_page_dir (); - list_init (&as->vmas); + file_seek (file, file_ofs); + if (file_read (file, &phdr, sizeof phdr) != sizeof phdr) + LOAD_ERROR (("error reading program header")); + printk ("%x: %08x, %08x %08x %08x %05x %05x\n", + file_tell (file), + phdr.p_type, + phdr.p_offset, phdr.p_vaddr, phdr.p_paddr, + phdr.p_filesz, phdr.p_memsz); + file_ofs += sizeof phdr; + switch (phdr.p_type) + { + case PT_NULL: + case PT_NOTE: + case PT_PHDR: + case PT_STACK: /* Stack segment. */ + /* Ignore this segment. */ + break; + case PT_DYNAMIC: + case PT_INTERP: + case PT_SHLIB: + /* Reject the executable. */ + LOAD_ERROR (("unsupported ELF segment type %d\n", phdr.p_type)); + break; + default: + printk ("unknown ELF segment type %08x\n", phdr.p_type); + break; + case PT_LOAD: + if (!load_segment (as, file, &phdr)) + goto error; + break; + } + } + success = true; - - + error: + if (file != NULL) + file_close (file); + if (!success) + addrspace_destroy (as); + return success; +} +void +addrspace_destroy (struct addrspace *as) +{ + if (as != NULL && as->pagedir != NULL) + pagedir_destroy (as->pagedir); } diff --git a/src/userprog/addrspace.h b/src/userprog/addrspace.h index b6f2cc3..8feb6b5 100644 --- a/src/userprog/addrspace.h +++ b/src/userprog/addrspace.h @@ -1,21 +1,15 @@ #ifndef HEADER_ADDRSPACE_H #define HEADER_ADDRSPACE_H 1 -#include "list.h" - -struct vma - { - struct list_elem elem; - uint32_t start, end; - void **pages; - }; +#include +#include "hash.h" struct addrspace { - uint32_t *page_dir; - struct list vmas; + uint32_t *pagedir; }; -void addrspace_load (struct addrspace *, const char *); +bool addrspace_load (struct addrspace *, const char *); +void addrspace_destroy (struct addrspace *); #endif /* addrspace.h */