From e88a8c4c379d721e9901752d440a05295087da11 Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 19 Jun 2012 01:44:56 +0200 Subject: implement page table and use it for lazy loading of segments --- Makefile.build | 2 +- proj0.txt | 12 ++--- proj1.txt | 18 +++---- threads/synch.c | 8 +-- threads/thread.c | 2 +- threads/thread.h | 3 ++ userprog/exception.c | 16 +++++- userprog/process.c | 35 +++++------- userprog/process.h | 1 + vm/page.c | 147 +++++++++++++++++++++++++++++++++++++++++++++++++++ vm/page.h | 41 ++++++++++++++ 11 files changed, 239 insertions(+), 46 deletions(-) create mode 100644 vm/page.c create mode 100644 vm/page.h diff --git a/Makefile.build b/Makefile.build index e997d27..e68e721 100644 --- a/Makefile.build +++ b/Makefile.build @@ -62,7 +62,7 @@ userprog_SRC += userprog/gdt.c # GDT initialization. userprog_SRC += userprog/tss.c # TSS management. # No virtual memory code yet. -#vm_SRC = vm/file.c # Some file. +vm_SRC = vm/page.c # Filesystem code. filesys_SRC = filesys/filesys.c # Filesystem core. diff --git a/proj0.txt b/proj0.txt index 24ea011..59a0d3c 100644 --- a/proj0.txt +++ b/proj0.txt @@ -35,9 +35,8 @@ Stallings, W. - Operating Systems struct thread: int64_t wakeup_tick ...absolute tick when to wake up the thread - timer.c: -static struct list wakeup_list ...list of processes waiting for an +static struct list wakeup_list ...list of processes waiting for an wakeup event and currently put to sleep ---- ALGORITHMS ---- @@ -62,7 +61,7 @@ Thus we can return as soon as the first thread doesn't need to get unblocked. >> A4: How are race conditions avoided when multiple threads call >> timer_sleep() simultaneously? -Each thread has its own variable for saving its sleep period +Each thread has its own variable for saving its sleep period therefore no race conditions arise while setting the latter. Furthermore during the access to the static wakup_list, interrupts are disabled to prevent thread preemption. @@ -131,12 +130,11 @@ strtok() uses global data, so it is unsafe in threaded programs such as kernels. execution with user privileges. Otherwise this could lead to a kernel oops or even worse code execution within the kernel. -* Outsourcing command separation from the kernel leads to a leaner +* Outsourcing command separation from the kernel leads to a leaner less complex kernel implementation and reduces the kernel workload - because tasks like searching for a command name in file system + because tasks like searching for a command name in file system can be delegated to the shell. - SURVEY QUESTIONS ================ @@ -161,4 +159,4 @@ the quarter. >> Any other comments? -It took us about 25 hours to complete this assignment. \ No newline at end of file +It took us about 25 hours to complete this assignment. diff --git a/proj1.txt b/proj1.txt index 03c61f0..2eab2fa 100644 --- a/proj1.txt +++ b/proj1.txt @@ -1,8 +1,8 @@ - +--------------------+ - | CS 140 | - | PROJECT 1: THREADS | - | DESIGN DOCUMENT | - +--------------------+ + +--------------------+ + | CS 140 | + | PROJECT 1: THREADS | + | DESIGN DOCUMENT | + +--------------------+ ---- GROUP ---- @@ -25,8 +25,8 @@ Stallings, W. - Operating Systems http://en.wikipedia.org/wiki/Priority_inversion http://hynek.me/studies/sched_ausarbeitung.pdf - PRIORITY SCHEDULING - =================== + PRIORITY SCHEDULING + =================== ---- DATA STRUCTURES ---- @@ -214,8 +214,8 @@ and we don't have any reference to currently used semaphores/conditions inside the thread structure. Thus we simply sort the whole list inside sema_up()/ cond_signal() before unblocking the next thread. - SURVEY QUESTIONS - ================ + SURVEY QUESTIONS + ================ Answering these questions is optional, but it will help us improve the course in future quarters. Feel free to tell us anything you diff --git a/threads/synch.c b/threads/synch.c index a1b7549..a520f61 100644 --- a/threads/synch.c +++ b/threads/synch.c @@ -32,9 +32,9 @@ #include "threads/interrupt.h" #include "threads/thread.h" -static bool lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b, +static bool lock_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b, void *AUX UNUSED); -static bool semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b, +static bool semaphore_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED); /* Initializes semaphore SEMA to VALUE. A semaphore is a @@ -202,7 +202,7 @@ lock_init (struct lock *lock) /* comparison function for our descending ordered lock list. */ static bool -lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b, +lock_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b, void *AUX UNUSED) { const struct lock *l1 = list_entry (a, struct lock, elem); @@ -355,7 +355,7 @@ cond_init (struct condition *cond) /* comparison function for our descending ordered condition waiters list. */ static bool -semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b, +semaphore_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) { const struct semaphore_elem *s1 = list_entry (a, struct semaphore_elem, elem); diff --git a/threads/thread.c b/threads/thread.c index cf404b6..14889ca 100644 --- a/threads/thread.c +++ b/threads/thread.c @@ -73,7 +73,7 @@ static tid_t allocate_tid (void); /* comparison function for our descending ordered ready list. */ bool -thread_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b, +thread_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b, void *AUX UNUSED) { const struct thread *t1 = list_entry (a, struct thread, elem); diff --git a/threads/thread.h b/threads/thread.h index 9125937..293d14f 100644 --- a/threads/thread.h +++ b/threads/thread.h @@ -3,6 +3,7 @@ #include #include +#include #include #include "threads/synch.h" @@ -112,6 +113,8 @@ struct thread int saved_priority; /* saved base priority in case of priority dontation */ struct list locks; /* list of locks the thread currently holds */ struct lock *blocked_lock; /* the lock the thread currently tries to acquire (but hasn't yet) */ + + struct hash page_table; }; /* If false (default), use round-robin scheduler. diff --git a/userprog/exception.c b/userprog/exception.c index 17620ad..54621fa 100644 --- a/userprog/exception.c +++ b/userprog/exception.c @@ -5,6 +5,7 @@ #include "threads/interrupt.h" #include "threads/thread.h" #include "threads/vaddr.h" +#include "vm/page.h" /* Number of page faults processed. */ static long long page_fault_cnt; @@ -121,12 +122,13 @@ kill (struct intr_frame *f) description of "Interrupt 14--Page Fault Exception (#PF)" in [IA32-v3a] section 5.15 "Exception and Interrupt Reference". */ static void -page_fault (struct intr_frame *f) +page_fault (struct intr_frame *f) { bool not_present; /* True: not-present page, false: writing r/o page. */ bool write; /* True: access was write, false: access was read. */ bool user; /* True: access by user, false: access by kernel. */ void *fault_addr; /* Fault address. */ + struct page_table_entry *pte; /* Obtain faulting address, the virtual address that was accessed to cause the fault. It may point to code or to @@ -153,6 +155,17 @@ page_fault (struct intr_frame *f) body, adding code that brings in the page to which fault_addr refers. */ if (is_user_vaddr(fault_addr)) { + pte = page_table_fetch (&thread_current ()->page_table, pg_round_down (fault_addr)); + if (pte != NULL) + page_load (pte); + else + { + printf ("Page fault %p\n", pte); + kill (f); + } + + //TODO +#if 0 if (! user) { /* syscall exception; set eax and eip */ f->eip = (void*)f->eax; @@ -162,6 +175,7 @@ page_fault (struct intr_frame *f) /* user process access violation */ thread_exit(); } +#endif } else { printf ("Page fault at %p: %s error %s page in %s context.\n", fault_addr, diff --git a/userprog/process.c b/userprog/process.c index c13c051..15883d9 100644 --- a/userprog/process.c +++ b/userprog/process.c @@ -18,6 +18,7 @@ #include "threads/synch.h" #include "threads/thread.h" #include "threads/vaddr.h" +#include "vm/page.h" /* data structure to communicate with the thread initializing a new process */ struct start_aux_data { @@ -128,6 +129,8 @@ start_process (void *aux) process->parent_tid = aux_data->parent_thread->tid; thread->process = process; + page_table_init (&thread->page_table); + /* Initialize interrupt frame and load executable. */ memset (&if_, 0, sizeof if_); if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; @@ -251,6 +254,8 @@ process_exit (void) pagedir_destroy (pd); } + page_table_free (&thread->page_table); + /* Destroy the process structure if the parent is not alive * any more. Atomic test and set would be sufficient here. */ @@ -478,8 +483,6 @@ load (const char *args, void (**eip) (void), void **esp) /* load() helpers. */ -static bool install_page (void *upage, void *kpage, bool writable); - /* Checks whether PHDR describes a valid, loadable segment in FILE and returns true if so, false otherwise. */ static bool @@ -556,29 +559,15 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage, size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE; size_t page_zero_bytes = PGSIZE - page_read_bytes; - /* Get a page of memory. */ - uint8_t *kpage = palloc_get_page (PAL_USER); - if (kpage == NULL) - return false; - - /* Load this page. */ - if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes) - { - palloc_free_page (kpage); + /* add segment to page table for on demand loading */ + if (!page_table_insert_segment (file, ofs, upage, page_read_bytes, + page_zero_bytes, writable)) return false; - } - memset (kpage + page_read_bytes, 0, page_zero_bytes); - - /* Add the page to the process's address space. */ - if (!install_page (upage, kpage, writable)) - { - palloc_free_page (kpage); - return false; - } /* Advance. */ read_bytes -= page_read_bytes; zero_bytes -= page_zero_bytes; + ofs += page_read_bytes; upage += PGSIZE; } return true; @@ -602,7 +591,7 @@ setup_stack (uint32_t **esp, const char *args) if (kpage == NULL) return false; - if (! install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true)) { + if (! process_install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true)) { palloc_free_page (kpage); return false; } @@ -706,8 +695,8 @@ setup_stack (uint32_t **esp, const char *args) with palloc_get_page(). Returns true on success, false if UPAGE is already mapped or if memory allocation fails. */ -static bool -install_page (void *upage, void *kpage, bool writable) +bool +process_install_page (void *upage, void *kpage, bool writable) { struct thread *t = thread_current (); diff --git a/userprog/process.h b/userprog/process.h index 1609801..b7bca5d 100644 --- a/userprog/process.h +++ b/userprog/process.h @@ -37,6 +37,7 @@ tid_t process_execute (const char *file_name); int process_wait (tid_t); void process_exit (void); void process_activate (void); +bool process_install_page (void *upage, void *kpage, bool writable); int process_open_file(const char* fname); struct file* process_get_file(int fd); diff --git a/vm/page.c b/vm/page.c new file mode 100644 index 0000000..fa2433d --- /dev/null +++ b/vm/page.c @@ -0,0 +1,147 @@ +#include +#include "filesys/file.h" +#include "userprog/process.h" +#include "threads/thread.h" +#include "threads/malloc.h" +#include "threads/palloc.h" +#include "vm/page.h" + +static void page_table_entry_free (struct hash_elem *e, void *aux UNUSED); +static unsigned page_table_hash (const struct hash_elem *e, void *aux UNUSED); +static bool page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b, + void *aux UNUSED); +static bool page_table_insert (struct hash *ht, struct page_table_entry *pte); +static bool page_load_segment (struct page_table_entry *pte); +static bool page_load_mmf (struct page_table_entry *pte); + +void +page_table_init (struct hash *ht) +{ + hash_init (ht, page_table_hash, page_table_cmp_less, NULL); +} + +unsigned +page_table_hash (const struct hash_elem *e, void *aux UNUSED) +{ + const struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem); + return hash_bytes (&pte->uvaddr, sizeof pte->uvaddr); +} + +bool +page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b, + void *aux UNUSED) +{ + const struct page_table_entry *pte1 = hash_entry (a, struct page_table_entry, elem); + const struct page_table_entry *pte2 = hash_entry (b, struct page_table_entry, elem); + return (pte1->uvaddr < pte2->uvaddr); +} + +void +page_table_free (struct hash *ht) +{ + hash_destroy (ht, page_table_entry_free); +} + +void +page_table_entry_free (struct hash_elem *e, void *aux UNUSED) +{ + struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem); + free (pte); +} + +bool +page_table_insert (struct hash *ht, struct page_table_entry *pte) +{ + if (pte == NULL) + return false; + return (hash_insert (ht, &pte->elem) == NULL); +} + +bool +page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage, + uint32_t read_bytes, uint32_t zero_bytes, bool writable) +{ + struct page_table_entry *pte = malloc (sizeof *pte); + if (pte == NULL) + return false; + + pte->uvaddr = upage; + pte->type = PAGE_SEGMENT; + pte->loaded = false; + pte->segment.file = file; + pte->segment.ofs = ofs; + pte->segment.read_bytes = read_bytes; + pte->segment.zero_bytes = zero_bytes; + pte->segment.writable = writable; + + return page_table_insert (&thread_current ()->page_table, pte); +} + +struct page_table_entry * +page_table_fetch (struct hash *ht, void *uvaddr) +{ + struct page_table_entry pte; + struct hash_elem *e; + + pte.uvaddr = uvaddr; + e = hash_find (ht, &pte.elem); + return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL); +} + +bool +page_load (struct page_table_entry *pte) +{ + if (pte->loaded) + return true; + + switch (pte->type) + { + case PAGE_SEGMENT: + return page_load_segment (pte); + case PAGE_MEMORY_MAPPED_FILE: + return page_load_mmf (pte); + default: + ASSERT (false); + break; + } + return false; +} + +bool +page_load_segment (struct page_table_entry *pte) +{ + struct segment *data = &pte->segment; + + file_seek (data->file, data->ofs); + + /* Get a page of memory. */ + uint8_t *kpage = palloc_get_page (PAL_USER); + if (kpage == NULL) + return false; + + /* Load this page. */ + if (file_read (data->file, kpage, data->read_bytes) + != (int) data->read_bytes) + { + palloc_free_page (kpage); + return false; + } + memset (kpage + data->read_bytes, 0, data->zero_bytes); + + /* Add the page to the process's address space. */ + if (!process_install_page (pte->uvaddr, kpage, data->writable)) + { + palloc_free_page (kpage); + return false; + } + + pte->loaded = true; + return true; +} + +bool +page_load_mmf (struct page_table_entry *pte) +{ + //TODO: implement + return false; +} diff --git a/vm/page.h b/vm/page.h new file mode 100644 index 0000000..29159fb --- /dev/null +++ b/vm/page.h @@ -0,0 +1,41 @@ +#ifndef VM_PAGE_H +#define VM_PAGE_H + +#include +#include "hash.h" +#include "filesys/off_t.h" + +/* supplemental page table entry */ +struct page_table_entry +{ + void *uvaddr; + bool loaded; + enum + { + PAGE_SEGMENT, + PAGE_MEMORY_MAPPED_FILE, + } type; + + union + { + struct segment + { + struct file *file; + off_t ofs; + uint32_t read_bytes; + uint32_t zero_bytes; + bool writable; + } segment; + }; + + struct hash_elem elem; +}; + +void page_table_init (struct hash *ht); +void page_table_free (struct hash *ht); +struct page_table_entry *page_table_fetch (struct hash *ht, void *uvaddr); +bool page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage, + uint32_t read_bytes, uint32_t zero_bytes, bool writable); +bool page_load (struct page_table_entry *pte); + +#endif -- cgit v1.2.3