From abd273ce0a9ae9267f8b0a144ea9b56d8912f9b5 Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 19 Jun 2012 23:31:28 +0200 Subject: add dynamic stack growing --- proj2.txt | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++ threads/thread.h | 2 +- userprog/exception.c | 80 +++++++++++++++++++----------- userprog/process.c | 54 +++++++++++++------- userprog/process.h | 3 ++ userprog/syscall.c | 9 ++-- userprog/syscall.h | 2 + vm/page.c | 76 +++++++++++++++++----------- vm/page.h | 35 ++++++------- 9 files changed, 300 insertions(+), 98 deletions(-) create mode 100644 proj2.txt diff --git a/proj2.txt b/proj2.txt new file mode 100644 index 0000000..5405336 --- /dev/null +++ b/proj2.txt @@ -0,0 +1,137 @@ + +---------------------------+ + | ProgOS | + | PROJECT 2: VIRTUAL MEMORY | + | DESIGN DOCUMENT | + +---------------------------+ + +---- GROUP ---- + +>> Fill in the names and email addresses of your group members. + +Peter Ketscher +Karoline Knoth +Manuel Mausz + +---- PRELIMINARIES ---- + +>> If you have any preliminary comments on your submission, notes for the +>> TAs, or extra credit, please give them here. + +>> Please cite any offline or online sources you consulted while +>> preparing your submission, other than the Pintos documentation, course +>> text, lecture notes, and course staff. + + PAGE TABLE MANAGEMENT + ===================== +---- DATA STRUCTURES ---- + +>> A1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. + +struct thread: + struct hash page_table ...page table of thread + +struct page_table_entry: + void *upage ...virtual address of page + bool loaded ...indicates if page is loaded + enum type ...type of page + union struct segment ...structure needed for lazy loading of data segments + struct hash_elem elem ...Hash element. + +---- IMPLEMENTATION ---- +>> A2: Describe how you implemented lazy page loading. How do you +>> determine the file and file offset corresponding to a virtual +>> address? + +TODO + +---- SYNCHRONIZATION ---- +>> A3: How do you deal with or prevent page faults in file system +>> routines. Argue why your solution is deadlock free. + +TODO + + STACK GROWTH + ============ + +---- DATA STRUCTURES ---- + +>> B1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. + +extern void *syscall_sp ...stored stack pointer for the "page fault inside + syscall/kernel"-case + +---- IMPLEMENTATION ---- +>> B2: Describe how you integrated the (potentially growing) stack segment +>> into your page table management implementation. + +TODO + +---- ALGORITHMS ---- +>> B3: Explain how you detect a page fault which should trigger a +>> stack growth. What asssumptions are needed for your implementation +>> to work? + +TODO + + MEMORY MAPPED FILES + =================== + +---- DATA STRUCTURES ---- + +>> C1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. + +struct page_table_entry: + union struct TODO ...structure needed for loading of memory mapped files + +---- ALGORITHMS ---- + +>> C2: Describe how memory mapped files integrate into your virtual +>> memory subsystem. + +TODO + +>> C3: Explain how you determine whether a new file mapping overlaps +>> any existing segment. + +TODO + +---- RATIONALE ---- + +>> C4: Mappings created with "mmap" have similar semantics to those of +>> data demand-paged from executables, except that "mmap" mappings are +>> written back to their original files, not to swap. This implies +>> that much of their implementation can be shared. Explain why your +>> implementation either does or does not share much of the code for +>> the two situations. + +TODO + + 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 +want--these questions are just to spur your thoughts. You may also +choose to respond anonymously in the course evaluations at the end of +the quarter. + +>> In your opinion, was this assignment, or any one of the three problems +>> in it, too easy or too hard? Did it take too long or too little time? + +>> Did you find that working on a particular part of the assignment gave +>> you greater insight into some aspect of OS design? + +>> Is there some particular fact or hint we should give students in +>> future quarters to help them solve the problems? Conversely, did you +>> find any of our guidance to be misleading? + +>> Do you have any suggestions for the TAs to more effectively assist +>> students, either for future quarters or the remaining projects? + +>> Any other comments? diff --git a/threads/thread.h b/threads/thread.h index 293d14f..ed591f4 100644 --- a/threads/thread.h +++ b/threads/thread.h @@ -114,7 +114,7 @@ struct thread 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; + struct hash page_table; /* page table of thread */ }; /* If false (default), use round-robin scheduler. diff --git a/userprog/exception.c b/userprog/exception.c index 54621fa..debe7f0 100644 --- a/userprog/exception.c +++ b/userprog/exception.c @@ -2,6 +2,8 @@ #include #include #include "userprog/gdt.h" +#include "userprog/process.h" +#include "userprog/syscall.h" #include "threads/interrupt.h" #include "threads/thread.h" #include "threads/vaddr.h" @@ -128,7 +130,8 @@ page_fault (struct intr_frame *f) 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; + void *sp; /* Stack pointer. */ + struct page_table_entry *pte; /* Page table entry. */ /* Obtain faulting address, the virtual address that was accessed to cause the fault. It may point to code or to @@ -151,38 +154,57 @@ page_fault (struct intr_frame *f) write = (f->error_code & PF_W) != 0; user = (f->error_code & PF_U) != 0; - /* To implement virtual memory, adapt the rest of the function - 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 + /* accessing r/o page is always wrong */ + if (!not_present) + thread_exit (); + + if (is_user_vaddr (fault_addr)) { - printf ("Page fault %p\n", pte); - kill (f); - } + /* if page fault occurs during syscall, use saved stack pointer */ + sp = (!user) ? syscall_sp : f->esp; + + /* try to fetch page entry */ + pte = page_table_fetch (&thread_current ()->page_table, + pg_round_down (fault_addr)); + + /* we got a page entry so try to load the page */ + if (pte != NULL) + { + if (page_load (pte)) + return; + printf ("Unable to load page at %p in %s context.\n", + fault_addr, user ? "user" : "kernel"); + } + /* there's no page in our page table but we might still have an valid + stack access and need to expand our stack. so just check for that. + the maxium offset we consider as a valid access is caused by the PUSHA + instruction. it's 32 bytes below the current stack pointer */ + else if (fault_addr >= (sp - 32) && (PHYS_BASE - fault_addr) <= STACK_SIZE) + { + if (process_grow_stack (pg_round_down (fault_addr))) + return; + printf ("Unable to grow stack %p in %s context.\n", + fault_addr, user ? "user" : "kernel"); + } - //TODO -#if 0 - if (! user) { /* syscall exception; set eax and eip */ - f->eip = (void*)f->eax; - f->eax = 0xFFFFFFFF; - return; - } else { + if (!user) + { + f->eip = (void*)f->eax; + f->eax = 0xFFFFFFFF; + return; + } + /* user process access violation */ - thread_exit(); + thread_exit (); + return; } -#endif - } else { - printf ("Page fault at %p: %s error %s page in %s context.\n", - fault_addr, - not_present ? "not present" : "rights violation", - write ? "writing" : "reading", - user ? "user" : "kernel"); - kill (f); - } + + printf ("Page fault at %p: %s error %s page in %s context.\n", + fault_addr, + not_present ? "not present" : "rights violation", + write ? "writing" : "reading", + user ? "user" : "kernel"); + kill (f); } diff --git a/userprog/process.c b/userprog/process.c index 15883d9..2771e76 100644 --- a/userprog/process.c +++ b/userprog/process.c @@ -552,24 +552,24 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage, file_seek (file, ofs); while (read_bytes > 0 || zero_bytes > 0) - { - /* Calculate how to fill this page. - We will read PAGE_READ_BYTES bytes from FILE - and zero the final PAGE_ZERO_BYTES bytes. */ - size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE; - size_t page_zero_bytes = PGSIZE - page_read_bytes; - - /* 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; - - /* Advance. */ - read_bytes -= page_read_bytes; - zero_bytes -= page_zero_bytes; - ofs += page_read_bytes; - upage += PGSIZE; - } + { + /* Calculate how to fill this page. + We will read PAGE_READ_BYTES bytes from FILE + and zero the final PAGE_ZERO_BYTES bytes. */ + size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE; + size_t page_zero_bytes = PGSIZE - page_read_bytes; + + /* 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; + + /* Advance. */ + read_bytes -= page_read_bytes; + zero_bytes -= page_zero_bytes; + ofs += page_read_bytes; + upage += PGSIZE; + } return true; } @@ -686,6 +686,24 @@ setup_stack (uint32_t **esp, const char *args) return true; } +/* expand the stack of the process by one new page + which will be installed at the address of UPAGE */ +bool +process_grow_stack (void *upage) +{ + uint8_t *kpage = palloc_get_page (PAL_USER | PAL_ZERO); + if (kpage == NULL) + return false; + + if (!process_install_page (upage, kpage, true)) + { + palloc_free_page (kpage); + return false; + } + + return true; +} + /* Adds a mapping from user virtual address UPAGE to kernel virtual address KPAGE to the page table. If WRITABLE is true, the user process may modify the page; diff --git a/userprog/process.h b/userprog/process.h index b7bca5d..ccb94cb 100644 --- a/userprog/process.h +++ b/userprog/process.h @@ -3,6 +3,8 @@ #include "threads/thread.h" +#define STACK_SIZE (1 << 23) /* 8MB maxiumum stack size */ + /* In the current implementation, the capacity is fixed to 1024 (PGSIZE/4) */ struct fd_table { struct file** fds; @@ -37,6 +39,7 @@ tid_t process_execute (const char *file_name); int process_wait (tid_t); void process_exit (void); void process_activate (void); +bool process_grow_stack (void *upage); bool process_install_page (void *upage, void *kpage, bool writable); int process_open_file(const char* fname); diff --git a/userprog/syscall.c b/userprog/syscall.c index f8e0197..541668d 100644 --- a/userprog/syscall.c +++ b/userprog/syscall.c @@ -17,6 +17,9 @@ #define STACK_SLOT_SIZE sizeof(int) +/* stored stack pointer for the "page fault inside syscall/kernel"-case */ +void *syscall_sp; + /* Prototypes for Utilities */ static int get_user (const uint8_t *uaddr); static bool put_user (uint8_t *udst, uint8_t byte); @@ -195,10 +198,10 @@ syscall_handler (struct intr_frame *f) handler* fp; bool segfault = false; int result; - void *sp = f->esp; + syscall_sp = f->esp; /* The system call number and the arguments are on the stack */ - if (! copy_from_user (&syscall_nr,sp)) + if (! copy_from_user (&syscall_nr,syscall_sp)) goto fail; switch (syscall_nr) { case SYS_HALT: fp = syscall_halt; break; @@ -217,7 +220,7 @@ syscall_handler (struct intr_frame *f) default: goto fail; } - result = fp (sp, &segfault); + result = fp (syscall_sp, &segfault); if (segfault) goto fail; f->eax = result; diff --git a/userprog/syscall.h b/userprog/syscall.h index f7ab2f3..987ceaa 100644 --- a/userprog/syscall.h +++ b/userprog/syscall.h @@ -2,4 +2,6 @@ #define USERPROG_SYSCALL_H void syscall_init (void); +extern void *syscall_sp; + #endif /* userprog/syscall.h */ diff --git a/vm/page.c b/vm/page.c index fa2433d..336353e 100644 --- a/vm/page.c +++ b/vm/page.c @@ -6,50 +6,59 @@ #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 void page_table_entry_free (struct hash_elem *e, 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); +/* initialize page table structure */ void page_table_init (struct hash *ht) { hash_init (ht, page_table_hash, page_table_cmp_less, NULL); } -unsigned +/* calulcates and returns the hash used as key of the hash/page table */ +static 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); + return hash_bytes (&pte->upage, sizeof pte->upage); } -bool +/* page table comperator needed by the hash table implementation + returns true if A is less than B, or false if A is greater than + or equal to B */ +static 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); + return (pte1->upage < pte2->upage); } +/* frees the content of page table */ void page_table_free (struct hash *ht) { hash_destroy (ht, page_table_entry_free); } -void +/* frees a single page table entry */ +static 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 +/* inserts a new entry into the page table + returns false if entry is invalid or already in the table */ +static bool page_table_insert (struct hash *ht, struct page_table_entry *pte) { if (pte == NULL) @@ -57,6 +66,8 @@ page_table_insert (struct hash *ht, struct page_table_entry *pte) return (hash_insert (ht, &pte->elem) == NULL); } +/* inserts a new entry of type segment into the page table + returns false if entry is invalid or already in the table */ bool page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable) @@ -65,7 +76,7 @@ page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage, if (pte == NULL) return false; - pte->uvaddr = upage; + pte->upage = upage; pte->type = PAGE_SEGMENT; pte->loaded = false; pte->segment.file = file; @@ -77,17 +88,20 @@ page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage, return page_table_insert (&thread_current ()->page_table, pte); } +/* fetch an entry from the page table. returns NULL if not found */ struct page_table_entry * -page_table_fetch (struct hash *ht, void *uvaddr) +page_table_fetch (struct hash *ht, void *upage) { struct page_table_entry pte; struct hash_elem *e; - pte.uvaddr = uvaddr; + pte.upage = upage; e = hash_find (ht, &pte.elem); return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL); } +/* load the page referenced by the page table entry + returns true on success or already loaded, false otherwise */ bool page_load (struct page_table_entry *pte) { @@ -95,19 +109,20 @@ page_load (struct page_table_entry *pte) 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; - } + { + 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 +/* load the segment data page */ +static bool page_load_segment (struct page_table_entry *pte) { struct segment *data = &pte->segment; @@ -122,24 +137,25 @@ page_load_segment (struct page_table_entry *pte) /* Load this page. */ if (file_read (data->file, kpage, data->read_bytes) != (int) data->read_bytes) - { - palloc_free_page (kpage); - return false; - } + { + 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; - } + if (!process_install_page (pte->upage, kpage, data->writable)) + { + palloc_free_page (kpage); + return false; + } pte->loaded = true; return true; } -bool +/* load the memory mappged file page */ +static bool page_load_mmf (struct page_table_entry *pte) { //TODO: implement diff --git a/vm/page.h b/vm/page.h index 29159fb..9cea048 100644 --- a/vm/page.h +++ b/vm/page.h @@ -8,32 +8,33 @@ /* supplemental page table entry */ struct page_table_entry { - void *uvaddr; - bool loaded; + void *upage; /* virtual address of page */ + bool loaded; /* indicates if page is loaded */ enum - { - PAGE_SEGMENT, - PAGE_MEMORY_MAPPED_FILE, - } type; + { + PAGE_SEGMENT, + PAGE_MEMORY_MAPPED_FILE, + } type; /* type of page */ union - { - struct segment { - struct file *file; - off_t ofs; - uint32_t read_bytes; - uint32_t zero_bytes; - bool writable; - } segment; - }; + /* structure needed for lazy loading of data segments */ + struct segment + { + struct file *file; + off_t ofs; + uint32_t read_bytes; + uint32_t zero_bytes; + bool writable; + } segment; + }; - struct hash_elem elem; + struct hash_elem elem; /* Hash element. */ }; 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); +struct page_table_entry *page_table_fetch (struct hash *ht, void *upage); 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); -- cgit v1.2.3