From 3d30b9f53e93e7a29706118e74bddd91347c595e Mon Sep 17 00:00:00 2001 From: John Ousterhout Date: Mon, 17 Dec 2012 09:50:20 -0800 Subject: [PATCH] Updated sample solutions to correspond with current code. --- solutions/README | 6 + solutions/p1.patch | 101 +- solutions/p2.patch | 124 +-- solutions/p3.patch | 2061 ++++++++++++++++++----------------- solutions/p4.patch | 2552 +++++++++----------------------------------- 5 files changed, 1693 insertions(+), 3151 deletions(-) diff --git a/solutions/README b/solutions/README index 38668ba..f58a2d4 100644 --- a/solutions/README +++ b/solutions/README @@ -2,3 +2,9 @@ Sample solutions. These solutions are well written and pass all the corresponding tests. You can run them automatically with `make check' in tests/. + +The patches must be applied in order. For example, to get a solution for +Project 3, invoke the following commands in the Pintos top-level directory: + patch -p1 < p1.patch + patch -p1 < p2.patch + patch -p1 < p3.patch diff --git a/solutions/p1.patch b/solutions/p1.patch index 30c0ddd..8ebd1e9 100644 --- a/solutions/p1.patch +++ b/solutions/p1.patch @@ -1,7 +1,8 @@ -diff -Nur ../../src/devices/timer.c src/devices/timer.c ---- ../../src/devices/timer.c 2008-08-27 08:04:38.000000000 -0400 -+++ src/devices/timer.c 2008-08-27 12:42:33.000000000 -0400 -@@ -24,6 +24,9 @@ +diff --git a/src/devices/timer.c b/src/devices/timer.c +index befaaae..1aebae7 100644 +--- a/src/devices/timer.c ++++ b/src/devices/timer.c +@@ -24,6 +24,9 @@ static int64_t ticks; Initialized by timer_calibrate(). */ static unsigned loops_per_tick; @@ -11,16 +12,16 @@ diff -Nur ../../src/devices/timer.c src/devices/timer.c static intr_handler_func timer_interrupt; static bool too_many_loops (unsigned loops); static void busy_wait (int64_t loops); -@@ -45,6 +48,8 @@ - outb (0x40, count >> 8); - +@@ -37,6 +40,8 @@ timer_init (void) + { + pit_configure_channel (0, 2, TIMER_FREQ); intr_register_ext (0x20, timer_interrupt, "8254 Timer"); + + list_init (&wait_list); } /* Calibrates loops_per_tick, used to implement brief delays. */ -@@ -93,16 +98,37 @@ +@@ -84,16 +89,37 @@ timer_elapsed (int64_t then) return timer_ticks () - then; } @@ -61,7 +62,7 @@ diff -Nur ../../src/devices/timer.c src/devices/timer.c } /* Sleeps for approximately MS milliseconds. Interrupts must be -@@ -181,6 +207,17 @@ +@@ -172,6 +198,17 @@ timer_interrupt (struct intr_frame *args UNUSED) { ticks++; thread_tick (); @@ -79,9 +80,11 @@ diff -Nur ../../src/devices/timer.c src/devices/timer.c } /* Returns true if LOOPS iterations waits for more than one timer -diff -Nur ../../src/threads/fixed-point.h src/threads/fixed-point.h ---- ../../src/threads/fixed-point.h 1969-12-31 19:00:00.000000000 -0500 -+++ src/threads/fixed-point.h 2008-08-27 12:42:33.000000000 -0400 +diff --git a/src/threads/fixed-point.h b/src/threads/fixed-point.h +new file mode 100644 +index 0000000..ca88f97 +--- /dev/null ++++ b/src/threads/fixed-point.h @@ -0,0 +1,120 @@ +#ifndef THREADS_FIXED_POINT_H +#define THREADS_FIXED_POINT_H @@ -203,10 +206,11 @@ diff -Nur ../../src/threads/fixed-point.h src/threads/fixed-point.h +} + +#endif /* threads/fixed-point.h */ -diff -Nur ../../src/threads/synch.c src/threads/synch.c ---- ../../src/threads/synch.c 2006-07-20 22:05:37.000000000 -0400 -+++ src/threads/synch.c 2008-08-27 12:42:33.000000000 -0400 -@@ -113,10 +113,28 @@ +diff --git a/src/threads/synch.c b/src/threads/synch.c +index 317c68a..53197bb 100644 +--- a/src/threads/synch.c ++++ b/src/threads/synch.c +@@ -113,10 +113,28 @@ sema_up (struct semaphore *sema) ASSERT (sema != NULL); old_level = intr_disable (); @@ -238,7 +242,7 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c intr_set_level (old_level); } -@@ -192,12 +210,33 @@ +@@ -192,12 +210,33 @@ lock_init (struct lock *lock) void lock_acquire (struct lock *lock) { @@ -272,7 +276,7 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c } /* Tries to acquires LOCK and returns true if successful or false -@@ -228,11 +267,39 @@ +@@ -228,11 +267,39 @@ lock_try_acquire (struct lock *lock) void lock_release (struct lock *lock) { @@ -312,7 +316,7 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c } /* Returns true if the current thread holds LOCK, false -@@ -251,6 +318,7 @@ +@@ -251,6 +318,7 @@ struct semaphore_elem { struct list_elem elem; /* List element. */ struct semaphore semaphore; /* This semaphore. */ @@ -320,7 +324,7 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c }; /* Initializes condition variable COND. A condition variable -@@ -295,12 +363,26 @@ +@@ -295,12 +363,26 @@ cond_wait (struct condition *cond, struct lock *lock) ASSERT (lock_held_by_current_thread (lock)); sema_init (&waiter.semaphore, 0); @@ -347,7 +351,7 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c /* If any threads are waiting on COND (protected by LOCK), then this function signals one of them to wake up from its wait. LOCK must be held before calling this function. -@@ -317,8 +399,12 @@ +@@ -317,8 +399,12 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED) ASSERT (lock_held_by_current_thread (lock)); if (!list_empty (&cond->waiters)) @@ -362,9 +366,10 @@ diff -Nur ../../src/threads/synch.c src/threads/synch.c } /* Wakes up all threads, if any, waiting on COND (protected by -diff -Nur ../../src/threads/thread.c src/threads/thread.c ---- ../../src/threads/thread.c 2008-08-27 13:06:01.000000000 -0400 -+++ src/threads/thread.c 2008-08-27 13:14:12.000000000 -0400 +diff --git a/src/threads/thread.c b/src/threads/thread.c +index 87f22b8..86614f5 100644 +--- a/src/threads/thread.c ++++ b/src/threads/thread.c @@ -5,11 +5,13 @@ #include #include @@ -379,7 +384,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c #include "threads/vaddr.h" #ifdef USERPROG #include "userprog/process.h" -@@ -53,6 +55,7 @@ +@@ -53,6 +55,7 @@ static long long user_ticks; /* # of timer ticks in user programs. */ /* Scheduling. */ #define TIME_SLICE 4 /* # of timer ticks to give each thread. */ static unsigned thread_ticks; /* # of timer ticks since last yield. */ @@ -387,7 +392,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c /* If false (default), use round-robin scheduler. If true, use multi-level feedback queue scheduler. -@@ -92,6 +95,7 @@ +@@ -92,6 +95,7 @@ thread_init (void) lock_init (&tid_lock); list_init (&ready_list); list_init (&all_list); @@ -395,7 +400,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c /* Set up a thread structure for the running thread. */ initial_thread = running_thread (); -@@ -117,6 +121,18 @@ +@@ -117,6 +121,18 @@ thread_start (void) sema_down (&idle_started); } @@ -414,7 +419,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c /* Called by the timer interrupt handler at each timer tick. Thus, this function runs in an external interrupt context. */ void -@@ -134,9 +150,41 @@ +@@ -134,9 +150,41 @@ thread_tick (void) else kernel_ticks++; @@ -459,7 +464,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c } /* Prints thread statistics. */ -@@ -166,11 +214,12 @@ +@@ -166,6 +214,7 @@ tid_t thread_create (const char *name, int priority, thread_func *function, void *aux) { @@ -467,12 +472,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c struct thread *t; struct kernel_thread_frame *kf; struct switch_entry_frame *ef; - struct switch_threads_frame *sf; - tid_t tid; - - ASSERT (function != NULL); - -@@ -181,8 +230,10 @@ +@@ -180,8 +229,10 @@ thread_create (const char *name, int priority, return TID_ERROR; /* Initialize thread. */ @@ -482,9 +482,9 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c + t->nice = cur->nice; + t->recent_cpu = cur->recent_cpu; - /* Prepare thread for first run by initializing its stack. - Do this atomically so intermediate values for the 'stack' -@@ -208,6 +259,8 @@ + /* Stack frame for kernel_thread(). */ + kf = alloc_frame (t, sizeof *kf); +@@ -200,6 +251,8 @@ thread_create (const char *name, int priority, /* Add to run queue. */ thread_unblock (t); @@ -493,7 +493,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c return tid; } -@@ -228,6 +281,19 @@ +@@ -220,6 +273,19 @@ thread_block (void) schedule (); } @@ -513,7 +513,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c /* Transitions a blocked thread T to the ready-to-run state. This is an error if T is not blocked. (Use thread_yield() to make the running thread ready.) -@@ -339,11 +405,26 @@ +@@ -331,11 +397,26 @@ thread_foreach (thread_action_func *func, void *aux) } } @@ -543,7 +543,7 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c } /* Returns the current thread's priority. */ -@@ -355,33 +436,98 @@ +@@ -347,33 +428,98 @@ thread_get_priority (void) /* Sets the current thread's nice value to NICE. */ void @@ -652,22 +652,20 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c } /* Idle thread. Executes when no other thread is ready to run. -@@ -467,11 +613,13 @@ +@@ -461,9 +607,10 @@ init_thread (struct thread *t, const char *name, int priority) t->status = THREAD_BLOCKED; strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; - t->priority = priority; + t->priority = t->normal_priority = priority; t->magic = THREAD_MAGIC; +- + sema_init (&t->timer_sema, 0); + list_init (&t->donors); - old_level = intr_disable (); list_push_back (&all_list, &t->allelem); intr_set_level (old_level); - } - -@@ -495,8 +643,14 @@ +@@ -492,8 +639,14 @@ next_thread_to_run (void) { if (list_empty (&ready_list)) return idle_thread; @@ -684,9 +682,10 @@ diff -Nur ../../src/threads/thread.c src/threads/thread.c } /* Completes a thread switch by activating the new thread's page -diff -Nur ../../src/threads/thread.h src/threads/thread.h ---- ../../src/threads/thread.h 2008-08-27 08:45:26.000000000 -0400 -+++ src/threads/thread.h 2008-08-27 12:45:31.000000000 -0400 +diff --git a/src/threads/thread.h b/src/threads/thread.h +index 7965c06..6601963 100644 +--- a/src/threads/thread.h ++++ b/src/threads/thread.h @@ -4,6 +4,8 @@ #include #include @@ -696,7 +695,7 @@ diff -Nur ../../src/threads/thread.h src/threads/thread.h /* States in a thread's life cycle. */ enum thread_status -@@ -87,12 +89,26 @@ +@@ -87,12 +89,26 @@ struct thread enum thread_status status; /* Thread state. */ char name[16]; /* Name (for debugging purposes). */ uint8_t *stack; /* Saved stack pointer. */ @@ -724,7 +723,7 @@ diff -Nur ../../src/threads/thread.h src/threads/thread.h #ifdef USERPROG /* Owned by userprog/process.c. */ uint32_t *pagedir; /* Page directory. */ -@@ -125,6 +141,10 @@ +@@ -125,6 +141,10 @@ const char *thread_name (void); void thread_exit (void) NO_RETURN; void thread_yield (void); diff --git a/solutions/p2.patch b/solutions/p2.patch index 41f6764..5b36467 100644 --- a/solutions/p2.patch +++ b/solutions/p2.patch @@ -1,21 +1,16 @@ -Index: src/threads/thread.c -diff -u src/threads/thread.c~ src/threads/thread.c ---- src/threads/thread.c~ -+++ src/threads/thread.c -@@ -13,6 +13,7 @@ - #include "threads/synch.h" +diff --git a/src/threads/thread.c b/src/threads/thread.c +index 86614f5..9fa7f1c 100644 +--- a/src/threads/thread.c ++++ b/src/threads/thread.c +@@ -15,6 +15,7 @@ + #include "threads/vaddr.h" #ifdef USERPROG #include "userprog/process.h" +#include "userprog/syscall.h" #endif /* Random value for struct thread's `magic' member. -@@ -251,18 +252,19 @@ thread_tid (void) - void - thread_exit (void) - { - ASSERT (!intr_context ()); - +@@ -351,7 +352,8 @@ thread_exit (void) #ifdef USERPROG process_exit (); #endif @@ -25,38 +20,24 @@ diff -u src/threads/thread.c~ src/threads/thread.c /* Remove thread from all threads list, set our status to dying, and schedule another process. That process will destroy us when it calls thread_schedule_tail(). */ - intr_disable (); - list_remove (&thread_current()->allelem); - thread_current ()->status = THREAD_DYING; - schedule (); - NOT_REACHED (); - } -@@ -400,6 +404,10 @@ init_thread (struct thread *t, const cha +@@ -608,6 +610,10 @@ init_thread (struct thread *t, const char *name, int priority) strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; - t->priority = priority; + t->priority = t->normal_priority = priority; + list_init (&t->children); + t->wait_status = NULL; + list_init (&t->fds); + t->next_handle = 2; t->magic = THREAD_MAGIC; - } - -Index: src/threads/thread.h -diff -u src/threads/thread.h~ src/threads/thread.h ---- src/threads/thread.h~ -+++ src/threads/thread.h -@@ -4,6 +4,7 @@ - #include - #include - #include -+#include "threads/synch.h" - - /* States in a thread's life cycle. */ - enum thread_status -@@ -89,6 +90,10 @@ struct thread - uint8_t *stack; /* Saved stack pointer. */ - int priority; /* Priority. */ + sema_init (&t->timer_sema, 0); + list_init (&t->donors); +diff --git a/src/threads/thread.h b/src/threads/thread.h +index 6601963..2c85d88 100644 +--- a/src/threads/thread.h ++++ b/src/threads/thread.h +@@ -101,6 +101,10 @@ struct thread + fixed_point_t recent_cpu; /* Recent amount of CPU time. */ + struct list_elem allelem; /* List element for all threads list. */ + /* Owned by process.c. */ + struct wait_status *wait_status; /* This process's completion status. */ @@ -65,7 +46,7 @@ diff -u src/threads/thread.h~ src/threads/thread.h /* Shared between thread.c and synch.c. */ struct list_elem elem; /* List element. */ -@@ -96,11 +102,31 @@ struct thread +@@ -113,11 +117,31 @@ struct thread /* Owned by userprog/process.c. */ uint32_t *pagedir; /* Page directory. */ #endif @@ -96,12 +77,12 @@ diff -u src/threads/thread.h~ src/threads/thread.h + /* If false (default), use round-robin scheduler. If true, use multi-level feedback queue scheduler. - Controlled by kernel command-line options "-o mlfqs". -Index: src/userprog/exception.c -diff -u src/userprog/exception.c~ src/userprog/exception.c ---- src/userprog/exception.c~ -+++ src/userprog/exception.c -@@ -150,6 +150,14 @@ page_fault (struct intr_frame *f) + Controlled by kernel command-line option "-o mlfqs". */ +diff --git a/src/userprog/exception.c b/src/userprog/exception.c +index 19aca12..3682478 100644 +--- a/src/userprog/exception.c ++++ b/src/userprog/exception.c +@@ -148,6 +148,14 @@ page_fault (struct intr_frame *f) write = (f->error_code & PF_W) != 0; user = (f->error_code & PF_U) != 0; @@ -116,11 +97,12 @@ diff -u src/userprog/exception.c~ src/userprog/exception.c /* To implement virtual memory, delete the rest of the function body, and replace it with code that brings in the page to which fault_addr refers. */ -Index: src/userprog/process.c -diff -u src/userprog/process.c~ src/userprog/process.c ---- src/userprog/process.c~ -+++ src/userprog/process.c -@@ -14,11 +14,23 @@ +diff --git a/src/userprog/process.c b/src/userprog/process.c +index c0e5215..06ff27e 100644 +--- a/src/userprog/process.c ++++ b/src/userprog/process.c +@@ -14,12 +14,24 @@ + #include "threads/flags.h" #include "threads/init.h" #include "threads/interrupt.h" +#include "threads/malloc.h" @@ -144,8 +126,8 @@ diff -u src/userprog/process.c~ src/userprog/process.c + }; /* Starts a new thread running a user program loaded from - FILE_NAME. The new thread may be scheduled (and may even exit) -@@ -27,29 +39,37 @@ static bool load (const char *cmdline, v + FILENAME. The new thread may be scheduled (and may even exit) +@@ -28,29 +40,37 @@ static bool load (const char *cmdline, void (**eip) (void), void **esp); tid_t process_execute (const char *file_name) { @@ -195,7 +177,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c struct intr_frame if_; bool success; -@@ -58,10 +78,29 @@ start_process (void *file_name_) +@@ -59,10 +79,29 @@ start_process (void *file_name_) if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; if_.cs = SEL_UCSEG; if_.eflags = FLAG_IF | FLAG_MBS; @@ -228,7 +210,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c if (!success) thread_exit (); -@@ -75,18 +113,47 @@ start_process (void *file_name_) +@@ -76,18 +115,47 @@ start_process (void *file_name_) NOT_REACHED (); } @@ -281,7 +263,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c return -1; } -@@ -95,8 +162,30 @@ void +@@ -96,8 +164,30 @@ void process_exit (void) { struct thread *cur = thread_current (); @@ -312,7 +294,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c /* Destroy the current process's page directory and switch back to the kernel-only page directory. */ pd = cur->pagedir; -@@ -193,7 +284,7 @@ struct Elf32_Phdr +@@ -195,7 +285,7 @@ struct Elf32_Phdr #define PF_W 2 /* Writable. */ #define PF_R 4 /* Readable. */ @@ -320,8 +302,8 @@ diff -u src/userprog/process.c~ src/userprog/process.c +static bool setup_stack (const char *cmd_line, void **esp); static bool validate_segment (const struct Elf32_Phdr *, struct file *); static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, - bool writable); -@@ -209,13 +300,15 @@ static bool setup_stack (void **esp); + uint32_t read_bytes, uint32_t zero_bytes, +@@ -206,13 +296,15 @@ static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, and its initial stack pointer into *ESP. Returns true if successful, false otherwise. */ bool @@ -338,7 +320,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c int i; /* Allocate and activate page directory. */ -@@ -224,13 +317,22 @@ load (const char *file_name, void (**eip) +@@ -221,13 +313,22 @@ load (const char *file_name, void (**eip) (void), void **esp) goto done; process_activate (); @@ -362,7 +344,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c /* Read and verify executable header. */ if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr -@@ -284,7 +386,7 @@ load (const char *file_name, void (**eip) +@@ -302,7 +403,7 @@ load (const char *file_name, void (**eip) (void), void **esp) } /* Set up stack. */ @@ -371,7 +353,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c goto done; /* Start address. */ -@@ -294,7 +396,6 @@ load (const char *file_name, void (**eip) +@@ -312,7 +413,6 @@ load (const char *file_name, void (**eip) (void), void **esp) done: /* We arrive here whether the load is successful or not. */ @@ -379,7 +361,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c return success; } -@@ -393,10 +494,92 @@ load_segment (struct file *file, const s +@@ -424,10 +524,92 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage, return true; } @@ -475,7 +457,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c { uint8_t *kpage; bool success = false; -@@ -404,9 +587,9 @@ setup_stack (void **esp) +@@ -435,9 +617,9 @@ setup_stack (void **esp) kpage = palloc_get_page (PAL_USER | PAL_ZERO); if (kpage != NULL) { @@ -488,10 +470,10 @@ diff -u src/userprog/process.c~ src/userprog/process.c else palloc_free_page (kpage); } -Index: src/userprog/syscall.c -diff -u src/userprog/syscall.c~ src/userprog/syscall.c ---- src/userprog/syscall.c~ -+++ src/userprog/syscall.c +diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c +index 370c89b..ef31316 100644 +--- a/src/userprog/syscall.c ++++ b/src/userprog/syscall.c @@ -1,20 +1,486 @@ #include "userprog/syscall.h" #include @@ -507,8 +489,8 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c +#include "threads/malloc.h" +#include "threads/palloc.h" #include "threads/thread.h" -+#include "threads/vaddr.h" - ++#include "threads/vaddr.h" + + +static int sys_halt (void); @@ -983,10 +965,10 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + free (fd); + } +} -Index: src/userprog/syscall.h -diff -u src/userprog/syscall.h~ src/userprog/syscall.h ---- src/userprog/syscall.h~ -+++ src/userprog/syscall.h +diff --git a/src/userprog/syscall.h b/src/userprog/syscall.h +index 9059096..9d156f0 100644 +--- a/src/userprog/syscall.h ++++ b/src/userprog/syscall.h @@ -2,5 +2,6 @@ #define USERPROG_SYSCALL_H diff --git a/solutions/p3.patch b/solutions/p3.patch index a62adfd..9554a85 100644 --- a/solutions/p3.patch +++ b/solutions/p3.patch @@ -1,8 +1,8 @@ -Index: src/Makefile.build -diff -u src/Makefile.build~ src/Makefile.build ---- src/Makefile.build~ -+++ src/Makefile.build -@@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c # GDT in +diff --git a/src/Makefile.build b/src/Makefile.build +index e997d27..1057023 100644 +--- a/src/Makefile.build ++++ b/src/Makefile.build +@@ -62,7 +62,9 @@ userprog_SRC += userprog/gdt.c # GDT initialization. userprog_SRC += userprog/tss.c # TSS management. # No virtual memory code yet. @@ -13,101 +13,158 @@ diff -u src/Makefile.build~ src/Makefile.build # Filesystem code. filesys_SRC = filesys/filesys.c # Filesystem core. -Index: src/devices/timer.c -diff -u src/devices/timer.c~ src/devices/timer.c ---- src/devices/timer.c~ -+++ src/devices/timer.c -@@ -23,6 +23,9 @@ static volatile int64_t ticks; - Initialized by timer_calibrate(). */ - static unsigned loops_per_tick; - -+/* Threads waiting in timer_sleep(). */ -+static struct list wait_list; -+ - static intr_handler_func timer_interrupt; - static bool too_many_loops (unsigned loops); - static void busy_wait (int64_t loops); -@@ -43,6 +46,8 @@ timer_init (void) - outb (0x40, count >> 8); - - intr_register_ext (0x20, timer_interrupt, "8254 Timer"); -+ -+ list_init (&wait_list); - } - - /* Calibrates loops_per_tick, used to implement brief delays. */ -@@ -93,16 +93,37 @@ - return timer_ticks () - then; - } - -+/* Compares two threads based on their wake-up times. */ -+static bool -+compare_threads_by_wakeup_time (const struct list_elem *a_, -+ const struct list_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct thread *a = list_entry (a_, struct thread, timer_elem); -+ const struct thread *b = list_entry (b_, struct thread, timer_elem); -+ -+ return a->wakeup_time < b->wakeup_time; -+} -+ - /* Sleeps for approximately TICKS timer ticks. Interrupts must - be turned on. */ - void - timer_sleep (int64_t ticks) - { -- int64_t start = timer_ticks (); -+ struct thread *t = thread_current (); -+ -+ /* Schedule our wake-up time. */ -+ t->wakeup_time = timer_ticks () + ticks; - -+ /* Atomically insert the current thread into the wait list. */ - ASSERT (intr_get_level () == INTR_ON); -- while (timer_elapsed (start) < ticks) -- thread_yield (); -+ intr_disable (); -+ list_insert_ordered (&wait_list, &t->timer_elem, -+ compare_threads_by_wakeup_time, NULL); -+ intr_enable (); -+ -+ /* Wait. */ -+ sema_down (&t->timer_sema); - } - - /* Sleeps for approximately MS milliseconds. Interrupts must be -@@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args - { - ticks++; - thread_tick (); -+ -+ while (!list_empty (&wait_list)) -+ { -+ struct thread *t = list_entry (list_front (&wait_list), -+ struct thread, timer_elem); -+ if (ticks < t->wakeup_time) -+ break; -+ sema_up (&t->timer_sema); -+ list_pop_front (&wait_list); -+ } +diff --git a/src/devices/timer.c b/src/devices/timer.c +index 1aebae7..4b920e9 100644 +--- a/src/devices/timer.c ++++ b/src/devices/timer.c +@@ -206,7 +206,6 @@ timer_interrupt (struct intr_frame *args UNUSED) + if (ticks < t->wakeup_time) + break; + sema_up (&t->timer_sema); +- thread_yield_to_higher_priority (); + list_pop_front (&wait_list); + } } - - /* Returns true if LOOPS iterations waits for more than one timer -Index: src/threads/init.c -diff -u src/threads/init.c~ src/threads/init.c ---- src/threads/init.c~ -+++ src/threads/init.c -@@ -33,6 +33,8 @@ +diff --git a/src/threads/fixed-point.h b/src/threads/fixed-point.h +deleted file mode 100644 +index ca88f97..0000000 +--- a/src/threads/fixed-point.h ++++ /dev/null +@@ -1,120 +0,0 @@ +-#ifndef THREADS_FIXED_POINT_H +-#define THREADS_FIXED_POINT_H +- +-#include +- +-/* Parameters. */ +-#define FIX_BITS 32 /* Total bits per fixed-point number. */ +-#define FIX_P 16 /* Number of integer bits. */ +-#define FIX_Q 16 /* Number of fractional bits. */ +-#define FIX_F (1 << FIX_Q) /* pow(2, FIX_Q). */ +- +-#define FIX_MIN_INT (-FIX_MAX_INT) /* Smallest representable integer. */ +-#define FIX_MAX_INT ((1 << FIX_P) - 1) /* Largest representable integer. */ +- +-/* A fixed-point number. */ +-typedef struct +- { +- int f; +- } +-fixed_point_t; +- +-/* Returns a fixed-point number with F as its internal value. */ +-static inline fixed_point_t +-__mk_fix (int f) +-{ +- fixed_point_t x; +- x.f = f; +- return x; +-} +- +-/* Returns fixed-point number corresponding to integer N. */ +-static inline fixed_point_t +-fix_int (int n) +-{ +- ASSERT (n >= FIX_MIN_INT && n <= FIX_MAX_INT); +- return __mk_fix (n * FIX_F); +-} +- +-/* Returns fixed-point number corresponding to N divided by D. */ +-static inline fixed_point_t +-fix_frac (int n, int d) +-{ +- ASSERT (d != 0); +- ASSERT (n / d >= FIX_MIN_INT && n / d <= FIX_MAX_INT); +- return __mk_fix ((long long) n * FIX_F / d); +-} +- +-/* Returns X rounded to the nearest integer. */ +-static inline int +-fix_round (fixed_point_t x) +-{ +- return (x.f + FIX_F / 2) / FIX_F; +-} +- +-/* Returns X truncated down to the nearest integer. */ +-static inline int +-fix_trunc (fixed_point_t x) +-{ +- return x.f / FIX_F; +-} +- +-/* Returns X + Y. */ +-static inline fixed_point_t +-fix_add (fixed_point_t x, fixed_point_t y) +-{ +- return __mk_fix (x.f + y.f); +-} +- +-/* Returns X - Y. */ +-static inline fixed_point_t +-fix_sub (fixed_point_t x, fixed_point_t y) +-{ +- return __mk_fix (x.f - y.f); +-} +- +-/* Returns X * Y. */ +-static inline fixed_point_t +-fix_mul (fixed_point_t x, fixed_point_t y) +-{ +- return __mk_fix ((long long) x.f * y.f / FIX_F); +-} +- +-/* Returns X * N. */ +-static inline fixed_point_t +-fix_scale (fixed_point_t x, int n) +-{ +- ASSERT (n >= 0); +- return __mk_fix (x.f * n); +-} +- +-/* Returns X / Y. */ +-static inline fixed_point_t +-fix_div (fixed_point_t x, fixed_point_t y) +-{ +- return __mk_fix ((long long) x.f * FIX_F / y.f); +-} +- +-/* Returns X / N. */ +-static inline fixed_point_t +-fix_unscale (fixed_point_t x, int n) +-{ +- ASSERT (n > 0); +- return __mk_fix (x.f / n); +-} +- +-/* Returns 1 / X. */ +-static inline fixed_point_t +-fix_inv (fixed_point_t x) +-{ +- return fix_div (fix_int (1), x); +-} +- +-/* Returns -1 if X < Y, 0 if X == Y, 1 if X > Y. */ +-static inline int +-fix_compare (fixed_point_t x, fixed_point_t y) +-{ +- return x.f < y.f ? -1 : x.f > y.f; +-} +- +-#endif /* threads/fixed-point.h */ +diff --git a/src/threads/init.c b/src/threads/init.c +index cebec2c..9729de7 100644 +--- a/src/threads/init.c ++++ b/src/threads/init.c +@@ -37,6 +37,8 @@ #include "filesys/filesys.h" #include "filesys/fsutil.h" #endif +#include "vm/frame.h" +#include "vm/swap.h" - /* Amount of physical memory, in 4 kB pages. */ - size_t init_ram_pages; -@@ -124,6 +126,9 @@ main (void) + /* Page directory with kernel mappings only. */ + uint32_t *init_page_dir; +@@ -127,6 +129,9 @@ main (void) filesys_init (format_filesys); #endif @@ -117,32 +174,206 @@ diff -u src/threads/init.c~ src/threads/init.c printf ("Boot complete.\n"); /* Run actions specified on kernel command line. */ -Index: src/threads/interrupt.c -diff -u src/threads/interrupt.c~ src/threads/interrupt.c ---- src/threads/interrupt.c~ -+++ src/threads/interrupt.c -@@ -354,6 +354,8 @@ intr_handler (struct intr_frame *frame) +diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c +index e3b90dc..f897882 100644 +--- a/src/threads/interrupt.c ++++ b/src/threads/interrupt.c +@@ -360,6 +360,8 @@ intr_handler (struct intr_frame *frame) in_external_intr = true; yield_on_return = false; } + else + thread_current ()->user_esp = frame->esp; - /* Invoke the interrupt's handler. - If there is no handler, invoke the unexpected interrupt -Index: src/threads/thread.c -diff -u src/threads/thread.c~ src/threads/thread.c ---- src/threads/thread.c~ -+++ src/threads/thread.c -@@ -13,6 +13,7 @@ + /* Invoke the interrupt's handler. */ + handler = intr_handlers[frame->vec_no]; +diff --git a/src/threads/synch.c b/src/threads/synch.c +index 53197bb..317c68a 100644 +--- a/src/threads/synch.c ++++ b/src/threads/synch.c +@@ -113,28 +113,10 @@ sema_up (struct semaphore *sema) + ASSERT (sema != NULL); + + old_level = intr_disable (); +- sema->value++; + if (!list_empty (&sema->waiters)) +- { +- /* Find highest-priority waiting thread. */ +- struct thread *max = list_entry (list_max (&sema->waiters, +- thread_lower_priority, NULL), +- struct thread, elem); +- +- /* Remove `max' from wait list and unblock. */ +- list_remove (&max->elem); +- thread_unblock (max); +- +- /* Yield to a higher-priority thread, if we're running in a +- context where it makes sense to do so. +- +- Kind of a funny interaction with donation here. +- We only support donation for locks, and locks turn off +- interrupts before calling us, so we automatically don't +- do the yield here, delegating to lock_release(). */ +- if (!intr_context () && old_level == INTR_ON) +- thread_yield_to_higher_priority (); +- } ++ thread_unblock (list_entry (list_pop_front (&sema->waiters), ++ struct thread, elem)); ++ sema->value++; + intr_set_level (old_level); + } + +@@ -210,33 +192,12 @@ lock_init (struct lock *lock) + void + lock_acquire (struct lock *lock) + { +- enum intr_level old_level; +- + ASSERT (lock != NULL); + ASSERT (!intr_context ()); + ASSERT (!lock_held_by_current_thread (lock)); + +- old_level = intr_disable (); +- +- if (lock->holder != NULL) +- { +- /* Donate our priority to the thread holding the lock. +- First, update the data structures. */ +- struct thread *donor = thread_current (); +- donor->want_lock = lock; +- donor->donee = lock->holder; +- list_push_back (&lock->holder->donors, &donor->donor_elem); +- +- /* Now implement the priority donation itself +- by recomputing the donee's priority +- and cascading the donation as far as necessary. */ +- if (donor->donee != NULL) +- thread_recompute_priority (donor->donee); +- } +- + sema_down (&lock->semaphore); + lock->holder = thread_current (); +- intr_set_level (old_level); + } + + /* Tries to acquires LOCK and returns true if successful or false +@@ -267,39 +228,11 @@ lock_try_acquire (struct lock *lock) + void + lock_release (struct lock *lock) + { +- enum intr_level old_level; +- struct thread *t = thread_current (); +- struct list_elem *e; +- + ASSERT (lock != NULL); + ASSERT (lock_held_by_current_thread (lock)); + +- old_level = intr_disable (); +- +- /* Return donations to threads that want this lock. */ +- for (e = list_begin (&t->donors); e != list_end (&t->donors); ) +- { +- struct thread *donor = list_entry (e, struct thread, donor_elem); +- if (donor->want_lock == lock) +- { +- donor->donee = NULL; +- e = list_remove (e); +- } +- else +- e = list_next (e); +- } +- +- /* Release lock. */ + lock->holder = NULL; + sema_up (&lock->semaphore); +- +- /* Recompute our priority based on our remaining donations, +- then yield to a higher-priority ready thread if one now +- exists. */ +- thread_recompute_priority (t); +- thread_yield_to_higher_priority (); +- +- intr_set_level (old_level); + } + + /* Returns true if the current thread holds LOCK, false +@@ -318,7 +251,6 @@ struct semaphore_elem + { + struct list_elem elem; /* List element. */ + struct semaphore semaphore; /* This semaphore. */ +- struct thread *thread; /* Thread. */ + }; + + /* Initializes condition variable COND. A condition variable +@@ -363,26 +295,12 @@ cond_wait (struct condition *cond, struct lock *lock) + ASSERT (lock_held_by_current_thread (lock)); + + sema_init (&waiter.semaphore, 0); +- waiter.thread = thread_current (); + list_push_back (&cond->waiters, &waiter.elem); + lock_release (lock); + sema_down (&waiter.semaphore); + lock_acquire (lock); + } + +-static bool +-semaphore_elem_lower_priority (const struct list_elem *a_, +- const struct list_elem *b_, +- void *aux UNUSED) +-{ +- const struct semaphore_elem *a +- = list_entry (a_, struct semaphore_elem, elem); +- const struct semaphore_elem *b +- = list_entry (b_, struct semaphore_elem, elem); +- +- return a->thread->priority < b->thread->priority; +-} +- + /* If any threads are waiting on COND (protected by LOCK), then + this function signals one of them to wake up from its wait. + LOCK must be held before calling this function. +@@ -399,12 +317,8 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED) + ASSERT (lock_held_by_current_thread (lock)); + + if (!list_empty (&cond->waiters)) +- { +- struct list_elem *max +- = list_max (&cond->waiters, semaphore_elem_lower_priority, NULL); +- list_remove (max); +- sema_up (&list_entry (max, struct semaphore_elem, elem)->semaphore); +- } ++ sema_up (&list_entry (list_pop_front (&cond->waiters), ++ struct semaphore_elem, elem)->semaphore); + } + + /* Wakes up all threads, if any, waiting on COND (protected by +diff --git a/src/threads/thread.c b/src/threads/thread.c +index 9fa7f1c..f9f2310 100644 +--- a/src/threads/thread.c ++++ b/src/threads/thread.c +@@ -5,13 +5,11 @@ + #include + #include + #include "threads/flags.h" +-#include "threads/init.h" + #include "threads/interrupt.h" + #include "threads/intr-stubs.h" + #include "threads/palloc.h" + #include "threads/switch.h" + #include "threads/synch.h" +-#include "devices/timer.h" #include "threads/vaddr.h" #ifdef USERPROG #include "userprog/process.h" -+#include "userprog/syscall.h" - #endif +@@ -56,7 +54,6 @@ static long long user_ticks; /* # of timer ticks in user programs. */ + /* Scheduling. */ + #define TIME_SLICE 4 /* # of timer ticks to give each thread. */ + static unsigned thread_ticks; /* # of timer ticks since last yield. */ +-static fixed_point_t load_avg; /* Load average. */ - /* Random value for struct thread's `magic' member. -@@ -55,7 +56,8 @@ static void kernel_thread (thread_func * + /* If false (default), use round-robin scheduler. + If true, use multi-level feedback queue scheduler. +@@ -68,7 +65,8 @@ static void kernel_thread (thread_func *, void *aux); static void idle (void *aux UNUSED); static struct thread *running_thread (void); static struct thread *next_thread_to_run (void); @@ -152,7 +383,11 @@ diff -u src/threads/thread.c~ src/threads/thread.c static bool is_thread (struct thread *) UNUSED; static void *alloc_frame (struct thread *, size_t size); static void schedule (void); -@@ -82,9 +84,8 @@ thread_init (void) +@@ -96,13 +94,11 @@ thread_init (void) + lock_init (&tid_lock); + list_init (&ready_list); + list_init (&all_list); +- load_avg = fix_int (0); /* Set up a thread structure for the running thread. */ initial_thread = running_thread (); @@ -163,20 +398,121 @@ diff -u src/threads/thread.c~ src/threads/thread.c } /* Starts preemptive thread scheduling by enabling interrupts. -@@ -159,8 +160,8 @@ thread_create (const char *name, int pri +@@ -122,18 +118,6 @@ thread_start (void) + sema_down (&idle_started); + } + +-/* Adjust recent CPU of a thread based on load factor +- and recompute its priority. */ +-static void +-adjust_recent_cpu (struct thread *t, void *aux) +-{ +- fixed_point_t load_factor = *(fixed_point_t *)aux; +- +- t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu), +- fix_int (t->nice)); +- thread_recompute_priority (t); +-} +- + /* Called by the timer interrupt handler at each timer tick. + Thus, this function runs in an external interrupt context. */ + void +@@ -151,41 +135,9 @@ thread_tick (void) + else + kernel_ticks++; + +- if (thread_mlfqs) +- { +- /* Update load average. */ +- if (timer_ticks () % TIMER_FREQ == 0) +- { +- size_t ready_threads = list_size (&ready_list); +- if (t != idle_thread) +- ready_threads++; +- +- load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg), +- fix_mul (fix_frac (1, 60), fix_int (ready_threads))); +- } +- +- /* Increment running process's recent_cpu. */ +- if (t != idle_thread) +- t->recent_cpu = fix_add (t->recent_cpu, fix_int (1)); +- +- /* Update recent_cpu and thread priorities once per second. */ +- if (timer_ticks () % TIMER_FREQ == 0) +- { +- fixed_point_t twice_load = fix_scale (load_avg, 2); +- fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1)); +- fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1); +- +- thread_foreach (adjust_recent_cpu, &load_factor); +- } +- } +- +- /* Switch threads if time slice has expired. */ +- if (++thread_ticks >= TIME_SLICE) +- { +- if (thread_mlfqs) +- thread_recompute_priority (thread_current ()); +- intr_yield_on_return (); +- } ++ /* Enforce preemption. */ ++ if (++thread_ticks >= TIME_SLICE) ++ intr_yield_on_return (); + } + + /* Prints thread statistics. */ +@@ -215,7 +167,6 @@ tid_t + thread_create (const char *name, int priority, + thread_func *function, void *aux) + { +- struct thread *cur = thread_current (); + struct thread *t; + struct kernel_thread_frame *kf; + struct switch_entry_frame *ef; +@@ -230,10 +181,8 @@ thread_create (const char *name, int priority, return TID_ERROR; /* Initialize thread. */ -- init_thread (t, name, priority); +- init_thread (t, name, thread_mlfqs ? cur->priority : priority); - tid = t->tid = allocate_tid (); +- t->nice = cur->nice; +- t->recent_cpu = cur->recent_cpu; + init_thread (t, name, priority, allocate_tid ()); + tid = t->tid; /* Stack frame for kernel_thread(). */ kf = alloc_frame (t, sizeof *kf); -@@ -288,10 +289,11 @@ thread_tid (void) - void - thread_exit (void) +@@ -252,8 +201,6 @@ thread_create (const char *name, int priority, + + /* Add to run queue. */ + thread_unblock (t); +- if (priority > thread_get_priority ()) +- thread_yield (); + + return tid; + } +@@ -274,19 +221,6 @@ thread_block (void) + schedule (); + } + +-/* Returns true if A has lower priority than B, +- within a list of threads. */ +-bool +-thread_lower_priority (const struct list_elem *a_, +- const struct list_elem *b_, +- void *aux UNUSED) +-{ +- const struct thread *a = list_entry (a_, struct thread, elem); +- const struct thread *b = list_entry (b_, struct thread, elem); +- +- return a->priority < b->priority; +-} +- + /* Transitions a blocked thread T to the ready-to-run state. + This is an error if T is not blocked. (Use thread_yield() to + make the running thread ready.) +@@ -349,11 +283,11 @@ thread_exit (void) { ASSERT (!intr_context ()); @@ -184,9 +520,152 @@ diff -u src/threads/thread.c~ src/threads/thread.c #ifdef USERPROG process_exit (); #endif - +- syscall_exit (); +- ++ /* Remove thread from all threads list, set our status to dying, -@@ -406,23 +410,34 @@ is_thread (struct thread *t) + and schedule another process. That process will destroy us + when it calls thread_schedule_tail(). */ +@@ -399,26 +333,11 @@ thread_foreach (thread_action_func *func, void *aux) + } + } + +-static void +-recompute_priority_chain (void) +-{ +- enum intr_level old_level = intr_disable (); +- thread_recompute_priority (thread_current ()); +- thread_yield_to_higher_priority (); +- intr_set_level (old_level); +-} +- +-/* Sets the current thread's priority to PRIORITY. */ ++/* Sets the current thread's priority to NEW_PRIORITY. */ + void +-thread_set_priority (int priority) ++thread_set_priority (int new_priority) + { +- if (!thread_mlfqs) +- { +- struct thread *t = thread_current (); +- +- t->normal_priority = priority; +- recompute_priority_chain (); +- } ++ thread_current ()->priority = new_priority; + } + + /* Returns the current thread's priority. */ +@@ -430,98 +349,33 @@ thread_get_priority (void) + + /* Sets the current thread's nice value to NICE. */ + void +-thread_set_nice (int nice) ++thread_set_nice (int nice UNUSED) + { +- thread_current ()->nice = nice; +- recompute_priority_chain (); ++ /* Not yet implemented. */ + } + + /* Returns the current thread's nice value. */ + int + thread_get_nice (void) + { +- return thread_current ()->nice; ++ /* Not yet implemented. */ ++ return 0; + } + ++/* Returns 100 times the system load average. */ + int + thread_get_load_avg (void) + { +- int load_avg_int; +- enum intr_level level = intr_disable (); +- load_avg_int = fix_round (fix_scale (load_avg, 100)); +- intr_set_level (level); +- return load_avg_int; ++ /* Not yet implemented. */ ++ return 0; + } + ++/* Returns 100 times the current thread's recent_cpu value. */ + int + thread_get_recent_cpu (void) + { +- int recent_cpu_int; +- enum intr_level level = intr_disable (); +- recent_cpu_int = fix_round (fix_scale (thread_current ()->recent_cpu, 100)); +- intr_set_level (level); +- return recent_cpu_int; +-} +- +-/* Returns true if thread A has lower priority than thread B, +- within a list of donors. */ +-static bool +-donated_lower_priority (const struct list_elem *a_, +- const struct list_elem *b_, +- void *aux UNUSED) +-{ +- const struct thread *a = list_entry (a_, struct thread, donor_elem); +- const struct thread *b = list_entry (b_, struct thread, donor_elem); +- +- return a->priority < b->priority; +-} +- +-/* Recomputes T's priority in terms of its normal priority and +- its donors' priorities, if any, +- and cascades the donation as necessary. */ +-void +-thread_recompute_priority (struct thread *t) +-{ +- int old_priority = t->priority; +- int default_priority = t->normal_priority; +- int donation = PRI_MIN; +- if (thread_mlfqs) +- { +- default_priority = PRI_MAX - fix_round (t->recent_cpu) / 4 - t->nice * 2; +- if (default_priority < PRI_MIN) +- default_priority = PRI_MIN; +- else if (default_priority > PRI_MAX) +- default_priority = PRI_MAX; +- } +- if (!list_empty (&t->donors)) +- donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL), +- struct thread, donor_elem)->priority; +- t->priority = donation > default_priority ? donation : default_priority; +- if (t->priority > old_priority && t->donee != NULL) +- thread_recompute_priority (t->donee); +-} +- +-/* If the ready list contains a thread with a higher priority, +- yields to it. */ +-void +-thread_yield_to_higher_priority (void) +-{ +- enum intr_level old_level = intr_disable (); +- if (!list_empty (&ready_list)) +- { +- struct thread *cur = thread_current (); +- struct thread *max = list_entry (list_max (&ready_list, +- thread_lower_priority, NULL), +- struct thread, elem); +- if (max->priority > cur->priority) +- { +- if (intr_context ()) +- intr_yield_on_return (); +- else +- thread_yield (); +- } +- } +- intr_set_level (old_level); ++ /* Not yet implemented. */ ++ return 0; + } + + /* Idle thread. Executes when no other thread is ready to run. +@@ -597,7 +451,7 @@ is_thread (struct thread *t) /* Does basic initialization of T as a blocked thread named NAME. */ static void @@ -195,8 +674,7 @@ diff -u src/threads/thread.c~ src/threads/thread.c { enum intr_level old_level; - ASSERT (t != NULL); - ASSERT (PRI_MIN <= priority && priority <= PRI_MAX); +@@ -606,17 +460,22 @@ init_thread (struct thread *t, const char *name, int priority) ASSERT (name != NULL); memset (t, 0, sizeof *t); @@ -204,95 +682,120 @@ diff -u src/threads/thread.c~ src/threads/thread.c t->status = THREAD_BLOCKED; strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; - t->priority = priority; +- t->priority = t->normal_priority = priority; +- list_init (&t->children); ++ t->priority = priority; + t->exit_code = -1; -+ t->wait_status = NULL; + t->wait_status = NULL; + list_init (&t->children); + sema_init (&t->timer_sema, 0); + t->pagedir = NULL; + t->pages = NULL; + t->bin_file = NULL; -+ list_init (&t->fds); + list_init (&t->fds); + list_init (&t->mappings); -+ t->next_handle = 2; + t->next_handle = 2; t->magic = THREAD_MAGIC; - +- sema_init (&t->timer_sema, 0); +- list_init (&t->donors); old_level = intr_disable (); list_push_back (&all_list, &t->allelem); intr_set_level (old_level); +@@ -645,14 +504,8 @@ next_thread_to_run (void) + { + if (list_empty (&ready_list)) + return idle_thread; +- else +- { +- struct thread *max +- = list_entry (list_max (&ready_list, thread_lower_priority, NULL), +- struct thread, elem); +- list_remove (&max->elem); +- return max; +- } ++ else ++ return list_entry (list_pop_front (&ready_list), struct thread, elem); } -Index: src/threads/thread.h -diff -u src/threads/thread.h~ src/threads/thread.h ---- src/threads/thread.h~ -+++ src/threads/thread.h -@@ -2,8 +2,10 @@ + /* Completes a thread switch by activating the new thread's page +diff --git a/src/threads/thread.h b/src/threads/thread.h +index 2c85d88..b9e7b0c 100644 +--- a/src/threads/thread.h ++++ b/src/threads/thread.h +@@ -2,10 +2,10 @@ #define THREADS_THREAD_H #include +#include #include #include -+#include "threads/synch.h" + #include "threads/synch.h" +-#include "threads/fixed-point.h" /* States in a thread's life cycle. */ enum thread_status -@@ -89,18 +91,49 @@ struct thread +@@ -89,19 +89,11 @@ struct thread + enum thread_status status; /* Thread state. */ + char name[16]; /* Name (for debugging purposes). */ uint8_t *stack; /* Saved stack pointer. */ - int priority; /* Priority. */ +- +- /* Scheduler data. */ +- int priority; /* Priority, including donations. */ +- int normal_priority; /* Priority, without donations. */ +- struct list donors; /* Threads donating priority to us. */ +- struct list_elem donor_elem; /* Element in donors list. */ +- struct thread *donee; /* Thread we're donating to. */ +- struct lock *want_lock; /* Lock we're waiting to acquire. */ +- int nice; /* Niceness. */ +- fixed_point_t recent_cpu; /* Recent amount of CPU time. */ ++ int priority; /* Priority. */ + struct list_elem allelem; /* List element for all threads list. */ -+ /* Owned by process.c. */ + /* Owned by process.c. */ + int exit_code; /* Exit code. */ -+ struct wait_status *wait_status; /* This process's completion status. */ -+ struct list children; /* Completion status of children. */ -+ - /* Shared between thread.c and synch.c. */ - struct list_elem elem; /* List element. */ + struct wait_status *wait_status; /* This process's completion status. */ + struct list children; /* Completion status of children. */ --#ifdef USERPROG -+ /* Alarm clock. */ -+ int64_t wakeup_time; /* Time to wake this thread up. */ +@@ -110,18 +102,19 @@ struct thread + + /* Alarm clock. */ + int64_t wakeup_time; /* Time to wake this thread up. */ +- struct list_elem timer_elem; /* Element in wait_list. */ + struct list_elem timer_elem; /* Element in timer_wait_list. */ -+ struct semaphore timer_sema; /* Semaphore. */ + struct semaphore timer_sema; /* Semaphore. */ +- +-#ifdef USERPROG + /* Owned by userprog/process.c. */ uint32_t *pagedir; /* Page directory. */ -#endif +- struct file *bin_file; /* Executable. */ + struct hash *pages; /* Page table. */ + struct file *bin_file; /* The binary executable. */ -+ -+ /* Owned by syscall.c. */ -+ struct list fds; /* List of file descriptors. */ + + /* Owned by syscall.c. */ + struct list fds; /* List of file descriptors. */ + struct list mappings; /* Memory-mapped files. */ -+ int next_handle; /* Next handle value. */ + int next_handle; /* Next handle value. */ + void *user_esp; /* User's stack pointer. */ /* Owned by thread.c. */ unsigned magic; /* Detects stack overflow. */ - }; +@@ -165,10 +158,6 @@ const char *thread_name (void); -+/* Tracks the completion of a process. -+ Reference held by both the parent, in its `children' list, -+ and by the child, in its `wait_status' pointer. */ -+struct wait_status -+ { -+ struct list_elem elem; /* `children' list element. */ -+ struct lock lock; /* Protects ref_cnt. */ -+ int ref_cnt; /* 2=child and parent both alive, -+ 1=either child or parent alive, -+ 0=child and parent both dead. */ -+ tid_t tid; /* Child thread id. */ -+ int exit_code; /* Child exit code, if dead. */ -+ struct semaphore dead; /* 1=child alive, 0=child dead. */ -+ }; -+ - /* If false (default), use round-robin scheduler. - If true, use multi-level feedback queue scheduler. - Controlled by kernel command-line options "-o mlfqs". -Index: src/userprog/exception.c -diff -u src/userprog/exception.c~ src/userprog/exception.c ---- src/userprog/exception.c~ -+++ src/userprog/exception.c + void thread_exit (void) NO_RETURN; + void thread_yield (void); +-void thread_yield_to_higher_priority (void); +-void thread_recompute_priority (struct thread *); +-bool thread_lower_priority (const struct list_elem *, const struct list_elem *, +- void *aux); + + /* Performs some operation on thread t, given auxiliary data AUX. */ + typedef void thread_action_func (struct thread *t, void *aux); +diff --git a/src/userprog/exception.c b/src/userprog/exception.c +index 3682478..9cfcf93 100644 +--- a/src/userprog/exception.c ++++ b/src/userprog/exception.c @@ -4,6 +4,7 @@ #include "userprog/gdt.h" #include "threads/interrupt.h" @@ -301,29 +804,33 @@ diff -u src/userprog/exception.c~ src/userprog/exception.c /* Number of page faults processed. */ static long long page_fault_cnt; -@@ -148,9 +149,14 @@ page_fault (struct intr_frame *f) +@@ -148,17 +149,14 @@ page_fault (struct intr_frame *f) write = (f->error_code & PF_W) != 0; user = (f->error_code & PF_U) != 0; -- /* To implement virtual memory, delete the rest of the function -- body, and replace it with code that brings in the page to -- which fault_addr refers. */ +- /* Handle bad dereferences from system call implementations. */ +- if (!user) + /* Allow the pager to try to handle it. */ + if (user && not_present) -+ { + { +- f->eip = (void (*) (void)) f->eax; +- f->eax = 0; + if (!page_in (fault_addr)) + thread_exit (); -+ return; -+ } -+ + return; + } + +- /* To implement virtual memory, delete the rest of the function +- body, and replace it with code that brings in the page to +- which fault_addr refers. */ printf ("Page fault at %p: %s error %s page in %s context.\n", fault_addr, not_present ? "not present" : "rights violation", -Index: src/userprog/pagedir.c -diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c ---- src/userprog/pagedir.c~ -+++ src/userprog/pagedir.c -@@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd) +diff --git a/src/userprog/pagedir.c b/src/userprog/pagedir.c +index a6a87b8..eed41b5 100644 +--- a/src/userprog/pagedir.c ++++ b/src/userprog/pagedir.c +@@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd) ASSERT (pd != init_page_dir); for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++) if (*pde & PTE_P) @@ -340,15 +847,11 @@ diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c palloc_free_page (pd); } -Index: src/userprog/process.c -diff -u src/userprog/process.c~ src/userprog/process.c ---- src/userprog/process.c~ -+++ src/userprog/process.c -@@ -14,12 +14,26 @@ - #include "threads/flags.h" - #include "threads/init.h" - #include "threads/interrupt.h" -+#include "threads/malloc.h" +diff --git a/src/userprog/process.c b/src/userprog/process.c +index 06ff27e..7a15814 100644 +--- a/src/userprog/process.c ++++ b/src/userprog/process.c +@@ -18,6 +18,8 @@ #include "threads/palloc.h" #include "threads/thread.h" #include "threads/vaddr.h" @@ -356,220 +859,56 @@ diff -u src/userprog/process.c~ src/userprog/process.c +#include "vm/frame.h" static thread_func start_process NO_RETURN; --static bool load (const char *cmdline, void (**eip) (void), void **esp); -+static bool load (const char *cmd_line, void (**eip) (void), void **esp); -+ -+/* Data structure shared between process_execute() in the -+ invoking thread and start_process() in the newly invoked -+ thread. */ -+struct exec_info -+ { -+ const char *file_name; /* Program to load. */ -+ struct semaphore load_done; /* "Up"ed when loading complete. */ -+ struct wait_status *wait_status; /* Child process. */ -+ bool success; /* Program successfully loaded? */ -+ }; - - /* Starts a new thread running a user program loaded from - FILE_NAME. The new thread may be scheduled (and may even exit) -@@ -28,29 +42,37 @@ static bool load (const char *cmdline, v - tid_t - process_execute (const char *file_name) - { -- char *fn_copy; -+ struct exec_info exec; -+ char thread_name[16]; -+ char *save_ptr; - tid_t tid; - -- /* Make a copy of FILE_NAME. -- Otherwise there's a race between the caller and load(). */ -- fn_copy = palloc_get_page (0); -- if (fn_copy == NULL) -- return TID_ERROR; -- strlcpy (fn_copy, file_name, PGSIZE); -+ /* Initialize exec_info. */ -+ exec.file_name = file_name; -+ sema_init (&exec.load_done, 0); - - /* Create a new thread to execute FILE_NAME. */ -- tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy); -- if (tid == TID_ERROR) -- palloc_free_page (fn_copy); -+ strlcpy (thread_name, file_name, sizeof thread_name); -+ strtok_r (thread_name, " ", &save_ptr); -+ tid = thread_create (thread_name, PRI_DEFAULT, start_process, &exec); -+ if (tid != TID_ERROR) -+ { -+ sema_down (&exec.load_done); -+ if (exec.success) -+ list_push_back (&thread_current ()->children, &exec.wait_status->elem); + static bool load (const char *cmd_line, void (**eip) (void), void **esp); +@@ -58,7 +60,7 @@ process_execute (const char *file_name) + sema_down (&exec.load_done); + if (exec.success) + list_push_back (&thread_current ()->children, &exec.wait_status->elem); +- else + else -+ tid = TID_ERROR; -+ } -+ - return tid; - } - - /* A thread function that loads a user process and starts it - running. */ - static void --start_process (void *file_name_) -+start_process (void *exec_) - { -- char *file_name = file_name_; -+ struct exec_info *exec = exec_; - struct intr_frame if_; - bool success; - -@@ -59,10 +81,28 @@ start_process (void *file_name_) - if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; - if_.cs = SEL_UCSEG; - if_.eflags = FLAG_IF | FLAG_MBS; -- success = load (file_name, &if_.eip, &if_.esp); -+ success = load (exec->file_name, &if_.eip, &if_.esp); -+ -+ /* Allocate wait_status. */ -+ if (success) -+ { -+ exec->wait_status = thread_current ()->wait_status -+ = malloc (sizeof *exec->wait_status); -+ success = exec->wait_status != NULL; -+ } - -- /* If load failed, quit. */ -- palloc_free_page (file_name); -+ /* Initialize wait_status. */ -+ if (success) -+ { -+ lock_init (&exec->wait_status->lock); -+ exec->wait_status->ref_cnt = 2; -+ exec->wait_status->tid = thread_current ()->tid; -+ sema_init (&exec->wait_status->dead, 0); -+ } -+ -+ /* Notify parent thread and clean up. */ -+ exec->success = success; -+ sema_up (&exec->load_done); - if (!success) - thread_exit (); - -@@ -76,18 +116,47 @@ start_process (void *file_name_) - NOT_REACHED (); - } - -+/* Releases one reference to CS and, if it is now unreferenced, -+ frees it. */ -+static void -+release_child (struct wait_status *cs) -+{ -+ int new_ref_cnt; -+ -+ lock_acquire (&cs->lock); -+ new_ref_cnt = --cs->ref_cnt; -+ lock_release (&cs->lock); -+ -+ if (new_ref_cnt == 0) -+ free (cs); -+} -+ - /* Waits for thread TID to die and returns its exit status. If - it was terminated by the kernel (i.e. killed due to an - exception), returns -1. If TID is invalid or if it was not a - child of the calling process, or if process_wait() has already - been successfully called for the given TID, returns -1 -- immediately, without waiting. -- -- This function will be implemented in problem 2-2. For now, it -- does nothing. */ -+ immediately, without waiting. */ - int --process_wait (tid_t child_tid UNUSED) -+process_wait (tid_t child_tid) - { -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); -+ e = list_next (e)) -+ { -+ struct wait_status *cs = list_entry (e, struct wait_status, elem); -+ if (cs->tid == child_tid) -+ { -+ int exit_code; -+ list_remove (e); -+ sema_down (&cs->dead); -+ exit_code = cs->exit_code; -+ release_child (cs); -+ return exit_code; -+ } -+ } - return -1; - } + tid = TID_ERROR; + } -@@ -96,8 +165,35 @@ void - process_exit (void) - { - struct thread *cur = thread_current (); -+ struct list_elem *e, *next; +@@ -95,7 +97,6 @@ start_process (void *exec_) + lock_init (&exec->wait_status->lock); + exec->wait_status->ref_cnt = 2; + exec->wait_status->tid = thread_current ()->tid; +- exec->wait_status->exit_code = -1; + sema_init (&exec->wait_status->dead, 0); + } + +@@ -167,14 +168,13 @@ process_exit (void) + struct list_elem *e, *next; uint32_t *pd; +- /* Close executable (and allow writes). */ +- file_close (cur->bin_file); + printf ("%s: exit(%d)\n", cur->name, cur->exit_code); -+ -+ /* Notify parent that we're dead. */ -+ if (cur->wait_status != NULL) -+ { -+ struct wait_status *cs = cur->wait_status; + + /* Notify parent that we're dead. */ + if (cur->wait_status != NULL) + { + struct wait_status *cs = cur->wait_status; +- printf ("%s: exit(%d)\n", cur->name, cs->exit_code); + cs->exit_code = cur->exit_code; -+ sema_up (&cs->dead); -+ release_child (cs); -+ } -+ -+ /* Free entries of children list. */ -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); -+ e = next) -+ { -+ struct wait_status *cs = list_entry (e, struct wait_status, elem); -+ next = list_remove (e); -+ release_child (cs); -+ } + sema_up (&cs->dead); + release_child (cs); + } +@@ -187,7 +187,13 @@ process_exit (void) + next = list_remove (e); + release_child (cs); + } + + /* Destroy the page hash table. */ + page_exit (); -+ + + /* Close executable (and allow writes). */ + file_close (cur->bin_file); + /* Destroy the current process's page directory and switch back to the kernel-only page directory. */ pd = cur->pagedir; -@@ -194,7 +290,7 @@ struct Elf32_Phdr - #define PF_W 2 /* Writable. */ - #define PF_R 4 /* Readable. */ - --static bool setup_stack (void **esp); -+static bool setup_stack (const char *cmd_line, void **esp); - static bool validate_segment (const struct Elf32_Phdr *, struct file *); - static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, - uint32_t read_bytes, uint32_t zero_bytes, -@@ -205,13 +301,15 @@ static bool load_segment (struct file *f - and its initial stack pointer into *ESP. - Returns true if successful, false otherwise. */ - bool --load (const char *file_name, void (**eip) (void), void **esp) -+load (const char *cmd_line, void (**eip) (void), void **esp) - { - struct thread *t = thread_current (); -+ char file_name[NAME_MAX + 2]; - struct Elf32_Ehdr ehdr; - struct file *file = NULL; - off_t file_ofs; - bool success = false; -+ char *cp; - int i; - - /* Allocate and activate page directory. */ -@@ -220,13 +318,28 @@ load (const char *file_name, void (**eip) +@@ -313,6 +319,12 @@ load (const char *cmd_line, void (**eip) (void), void **esp) goto done; process_activate (); @@ -579,42 +918,19 @@ diff -u src/userprog/process.c~ src/userprog/process.c + goto done; + hash_init (t->pages, page_hash, page_less, NULL); + -+ /* Extract file_name from command line. */ -+ while (*cmd_line == ' ') -+ cmd_line++; -+ strlcpy (file_name, cmd_line, sizeof file_name); -+ cp = strchr (file_name, ' '); -+ if (cp != NULL) -+ *cp = '\0'; -+ - /* Open executable file. */ -- file = filesys_open (file_name); -+ t->bin_file = file = filesys_open (file_name); - if (file == NULL) - { + /* Extract file_name from command line. */ + while (*cmd_line == ' ') + cmd_line++; +@@ -328,7 +340,7 @@ load (const char *cmd_line, void (**eip) (void), void **esp) printf ("load: %s: open failed\n", file_name); goto done; } +- file_deny_write (file); + file_deny_write (t->bin_file); /* Read and verify executable header. */ if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr -@@ -301,7 +414,7 @@ load (const char *file_name, void (**eip) - } - - /* Set up stack. */ -- if (!setup_stack (esp)) -+ if (!setup_stack (cmd_line, esp)) - goto done; - - /* Start address. */ -@@ -311,14 +424,11 @@ load (const char *file_name, void (**eip) - - done: - /* We arrive here whether the load is successful or not. */ -- file_close (file); - return success; - } +@@ -418,8 +430,6 @@ load (const char *cmd_line, void (**eip) (void), void **esp) /* load() helpers. */ @@ -623,7 +939,7 @@ diff -u src/userprog/process.c~ src/userprog/process.c /* Checks whether PHDR describes a valid, loadable segment in FILE and returns true if so, false otherwise. */ static bool -@@ -387,79 +497,127 @@ load_segment (struct file *file, off_t o +@@ -487,38 +497,22 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage, ASSERT (pg_ofs (upage) == 0); ASSERT (ofs % PGSIZE == 0); @@ -669,127 +985,32 @@ diff -u src/userprog/process.c~ src/userprog/process.c upage += PGSIZE; } return true; +@@ -535,7 +529,7 @@ reverse (int argc, char **argv) + argv[argc - 1] = tmp; + } } - --/* Create a minimal stack by mapping a zeroed page at the top of -- user virtual memory. */ -+/* Reverse the order of the ARGC pointers to char in ARGV. */ -+static void -+reverse (int argc, char **argv) -+{ -+ for (; argc > 1; argc -= 2, argv++) -+ { -+ char *tmp = argv[0]; -+ argv[0] = argv[argc - 1]; -+ argv[argc - 1] = tmp; -+ } -+} +- + -+/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose -+ page-relative stack pointer is *OFS, and then adjusts *OFS -+ appropriately. The bytes pushed are rounded to a 32-bit -+ boundary. -+ -+ If successful, returns a pointer to the newly pushed object. -+ On failure, returns a null pointer. */ -+static void * -+push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size) -+{ -+ size_t padsize = ROUND_UP (size, sizeof (uint32_t)); -+ if (*ofs < padsize) -+ return NULL; -+ -+ *ofs -= padsize; -+ memcpy (kpage + *ofs + (padsize - size), buf, size); -+ return kpage + *ofs + (padsize - size); -+} -+ -+/* Sets up command line arguments in KPAGE, which will be mapped -+ to UPAGE in user space. The command line arguments are taken -+ from CMD_LINE, separated by spaces. Sets *ESP to the initial -+ stack pointer for the process. */ + /* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose + page-relative stack pointer is *OFS, and then adjusts *OFS + appropriately. The bytes pushed are rounded to a 32-bit +@@ -611,37 +605,19 @@ init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line, static bool --setup_stack (void **esp) -+init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line, -+ void **esp) + setup_stack (const char *cmd_line, void **esp) { - uint8_t *kpage; - bool success = false; -+ size_t ofs = PGSIZE; -+ char *const null = NULL; -+ char *cmd_line_copy; -+ char *karg, *saveptr; -+ int argc; -+ char **argv; -+ -+ /* Push command line string. */ -+ cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1); -+ if (cmd_line_copy == NULL) -+ return false; -+ -+ if (push (kpage, &ofs, &null, sizeof null) == NULL) -+ return false; - +- - kpage = palloc_get_page (PAL_USER | PAL_ZERO); - if (kpage != NULL) -+ /* Parse command line into arguments -+ and push them in reverse order. */ -+ argc = 0; -+ for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL; -+ karg = strtok_r (NULL, " ", &saveptr)) ++ struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false); ++ if (page != NULL) { -- success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true); -- if (success) -- *esp = PHYS_BASE; +- uint8_t *upage = ((uint8_t *) PHYS_BASE) - PGSIZE; +- if (install_page (upage, kpage, true)) +- success = init_cmd_line (kpage, upage, cmd_line, esp); - else - palloc_free_page (kpage); -+ void *uarg = upage + (karg - (char *) kpage); -+ if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL) -+ return false; -+ argc++; - } -- return success; -+ -+ /* Reverse the order of the command line arguments. */ -+ argv = (char **) (upage + ofs); -+ reverse (argc, (char **) (kpage + ofs)); -+ -+ /* Push argv, argc, "return address". */ -+ if (push (kpage, &ofs, &argv, sizeof argv) == NULL -+ || push (kpage, &ofs, &argc, sizeof argc) == NULL -+ || push (kpage, &ofs, &null, sizeof null) == NULL) -+ return false; -+ -+ /* Set initial stack pointer. */ -+ *esp = upage + ofs; -+ 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; -- otherwise, it is read-only. -- UPAGE must not already be mapped. -- KPAGE should probably be a page obtained from the user pool -- with palloc_get_page(). -- Returns true on success, false if UPAGE is already mapped or -- if memory allocation fails. */ -+/* Create a minimal stack for T by mapping a page at the -+ top of user virtual memory. Fills in the page using CMD_LINE -+ and sets *ESP to the stack pointer. */ - static bool --install_page (void *upage, void *kpage, bool writable) -+setup_stack (const char *cmd_line, void **esp) - { -- struct thread *t = thread_current (); -- -- /* Verify that there's not already a page at that virtual -- address, then map our page there. */ -- return (pagedir_get_page (t->pagedir, upage) == NULL -- && pagedir_set_page (t->pagedir, upage, kpage, writable)); -+ struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false); -+ if (page != NULL) -+ { + page->frame = frame_alloc_and_lock (page); + if (page->frame != NULL) + { @@ -800,124 +1021,122 @@ diff -u src/userprog/process.c~ src/userprog/process.c + frame_unlock (page->frame); + return ok; + } -+ } + } +- return success; +-} +- +-/* 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; +- otherwise, it is read-only. +- UPAGE must not already be mapped. +- KPAGE should probably be a page obtained from the user pool +- 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) +-{ +- struct thread *t = thread_current (); +- +- /* Verify that there's not already a page at that virtual +- address, then map our page there. */ +- return (pagedir_get_page (t->pagedir, upage) == NULL +- && pagedir_set_page (t->pagedir, upage, kpage, writable)); + return false; } -Index: src/userprog/syscall.c -diff -u src/userprog/syscall.c~ src/userprog/syscall.c ---- src/userprog/syscall.c~ -+++ src/userprog/syscall.c -@@ -1,20 +1,598 @@ - #include "userprog/syscall.h" - #include -+#include - #include -+#include "userprog/process.h" -+#include "userprog/pagedir.h" -+#include "devices/input.h" -+#include "devices/shutdown.h" +diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c +index ef31316..e6be702 100644 +--- a/src/userprog/syscall.c ++++ b/src/userprog/syscall.c +@@ -6,6 +6,7 @@ + #include "userprog/pagedir.h" + #include "devices/input.h" + #include "devices/shutdown.h" +#include "filesys/directory.h" -+#include "filesys/filesys.h" -+#include "filesys/file.h" + #include "filesys/filesys.h" + #include "filesys/file.h" #include "threads/interrupt.h" -+#include "threads/malloc.h" -+#include "threads/palloc.h" +@@ -13,6 +14,7 @@ + #include "threads/palloc.h" #include "threads/thread.h" -- -+#include "threads/vaddr.h" + #include "threads/vaddr.h" +#include "vm/page.h" -+ -+ -+static int sys_halt (void); -+static int sys_exit (int status); -+static int sys_exec (const char *ufile); -+static int sys_wait (tid_t); -+static int sys_create (const char *ufile, unsigned initial_size); -+static int sys_remove (const char *ufile); -+static int sys_open (const char *ufile); -+static int sys_filesize (int handle); -+static int sys_read (int handle, void *udst_, unsigned size); -+static int sys_write (int handle, void *usrc_, unsigned size); -+static int sys_seek (int handle, unsigned position); -+static int sys_tell (int handle); -+static int sys_close (int handle); + + + static int sys_halt (void); +@@ -28,11 +30,12 @@ static int sys_write (int handle, void *usrc_, unsigned size); + static int sys_seek (int handle, unsigned position); + static int sys_tell (int handle); + static int sys_close (int handle); +static int sys_mmap (int handle, void *addr); +static int sys_munmap (int mapping); -+ + static void syscall_handler (struct intr_frame *); -+static void copy_in (void *, const void *, size_t); - -+static struct lock fs_lock; -+ - void - syscall_init (void) - { - intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall"); -+ lock_init (&fs_lock); - } -+ -+/* System call handler. */ -+static void -+syscall_handler (struct intr_frame *f) -+{ -+ typedef int syscall_function (int, int, int); -+ -+ /* A system call. */ -+ struct syscall -+ { -+ size_t arg_cnt; /* Number of arguments. */ -+ syscall_function *func; /* Implementation. */ -+ }; + static void copy_in (void *, const void *, size_t); +- +-/* Serializes file system operations. */ + -+ /* Table of system calls. */ -+ static const struct syscall syscall_table[] = -+ { -+ {0, (syscall_function *) sys_halt}, -+ {1, (syscall_function *) sys_exit}, -+ {1, (syscall_function *) sys_exec}, -+ {1, (syscall_function *) sys_wait}, -+ {2, (syscall_function *) sys_create}, -+ {1, (syscall_function *) sys_remove}, -+ {1, (syscall_function *) sys_open}, -+ {1, (syscall_function *) sys_filesize}, -+ {3, (syscall_function *) sys_read}, -+ {3, (syscall_function *) sys_write}, -+ {2, (syscall_function *) sys_seek}, -+ {1, (syscall_function *) sys_tell}, -+ {1, (syscall_function *) sys_close}, + static struct lock fs_lock; + + void +@@ -71,6 +74,8 @@ syscall_handler (struct intr_frame *f) + {2, (syscall_function *) sys_seek}, + {1, (syscall_function *) sys_tell}, + {1, (syscall_function *) sys_close}, + {2, (syscall_function *) sys_mmap}, + {1, (syscall_function *) sys_munmap}, -+ }; -+ -+ const struct syscall *sc; -+ unsigned call_nr; -+ int args[3]; + }; -+ /* Get the system call. */ -+ copy_in (&call_nr, f->esp, sizeof call_nr); -+ if (call_nr >= sizeof syscall_table / sizeof *syscall_table) -+ thread_exit (); -+ sc = syscall_table + call_nr; -+ -+ /* Get the system call arguments. */ -+ ASSERT (sc->arg_cnt <= sizeof args / sizeof *args); -+ memset (args, 0, sizeof args); -+ copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt); -+ -+ /* Execute the system call, -+ and set the return value. */ -+ f->eax = sc->func (args[0], args[1], args[2]); -+} -+ -+/* Copies SIZE bytes from user address USRC to kernel address -+ DST. -+ Call thread_exit() if any of the user accesses are invalid. */ - static void --syscall_handler (struct intr_frame *f UNUSED) -+copy_in (void *dst_, const void *usrc_, size_t size) -+{ -+ uint8_t *dst = dst_; -+ const uint8_t *usrc = usrc_; + const struct syscall *sc; +@@ -93,39 +98,6 @@ syscall_handler (struct intr_frame *f) + f->eax = sc->func (args[0], args[1], args[2]); + } + +-/* Returns true if UADDR is a valid, mapped user address, +- false otherwise. */ +-static bool +-verify_user (const void *uaddr) +-{ +- return (uaddr < PHYS_BASE +- && pagedir_get_page (thread_current ()->pagedir, uaddr) != NULL); +-} +- +-/* Copies a byte from user address USRC to kernel address DST. +- USRC must be below PHYS_BASE. +- Returns true if successful, false if a segfault occurred. */ +-static inline bool +-get_user (uint8_t *dst, const uint8_t *usrc) +-{ +- int eax; +- asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:" +- : "=m" (*dst), "=&a" (eax) : "m" (*usrc)); +- return eax != 0; +-} +- +-/* Writes BYTE to user address UDST. +- UDST must be below PHYS_BASE. +- Returns true if successful, false if a segfault occurred. */ +-static inline bool +-put_user (uint8_t *udst, uint8_t byte) +-{ +- int eax; +- asm ("movl $1f, %%eax; movb %b2, %0; 1:" +- : "=m" (*udst), "=&a" (eax) : "q" (byte)); +- return eax != 0; +-} +- + /* Copies SIZE bytes from user address USRC to kernel address + DST. + Call thread_exit() if any of the user accesses are invalid. */ +@@ -134,10 +106,22 @@ copy_in (void *dst_, const void *usrc_, size_t size) + { + uint8_t *dst = dst_; + const uint8_t *usrc = usrc_; +- +- for (; size > 0; size--, dst++, usrc++) +- if (usrc >= (uint8_t *) PHYS_BASE || !get_user (dst, usrc)) +- thread_exit (); + + while (size > 0) + { @@ -934,33 +1153,34 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + usrc += chunk_size; + size -= chunk_size; + } -+} -+ -+/* Creates a copy of user string US in kernel memory -+ and returns it as a page that must be freed with -+ palloc_free_page(). -+ Truncates the string at PGSIZE bytes in size. -+ Call thread_exit() if any of the user accesses are invalid. */ -+static char * -+copy_in_string (const char *us) -+{ -+ char *ks; + } + + /* Creates a copy of user string US in kernel memory +@@ -149,25 +133,40 @@ static char * + copy_in_string (const char *us) + { + char *ks; + char *upage; -+ size_t length; -+ -+ ks = palloc_get_page (0); -+ if (ks == NULL) -+ thread_exit (); + size_t length; + + ks = palloc_get_page (0); + if (ks == NULL) + thread_exit (); +- +- for (length = 0; length < PGSIZE; length++) + + length = 0; + for (;;) -+ { + { +- if (us >= (char *) PHYS_BASE || !get_user (ks + length, us++)) + upage = pg_round_down (us); + if (!page_lock (upage, false)) + goto lock_error; + + for (; us < upage + PGSIZE; us++) -+ { + { +- palloc_free_page (ks); +- thread_exit (); + ks[length++] = *us; + if (*us == '\0') + { @@ -969,187 +1189,115 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + } + else if (length >= PGSIZE) + goto too_long_error; -+ } + } +- +- if (ks[length] == '\0') +- return ks; + + page_unlock (upage); -+ } + } +- ks[PGSIZE - 1] = '\0'; +- return ks; + + too_long_error: + page_unlock (upage); + lock_error: + palloc_free_page (ks); + thread_exit (); -+} -+ -+/* Halt system call. */ -+static int -+sys_halt (void) -+{ -+ shutdown_power_off (); -+} -+ -+/* Exit system call. */ -+static int -+sys_exit (int exit_code) -+{ + } + + /* Halt system call. */ +@@ -181,7 +180,7 @@ sys_halt (void) + static int + sys_exit (int exit_code) + { +- thread_current ()->wait_status->exit_code = exit_code; + thread_current ()->exit_code = exit_code; -+ thread_exit (); -+ NOT_REACHED (); -+} -+ -+/* Exec system call. */ -+static int -+sys_exec (const char *ufile) -+{ -+ tid_t tid; -+ char *kfile = copy_in_string (ufile); -+ -+ lock_acquire (&fs_lock); -+ tid = process_execute (kfile); -+ lock_release (&fs_lock); -+ -+ palloc_free_page (kfile); -+ -+ return tid; -+} -+ -+/* Wait system call. */ -+static int -+sys_wait (tid_t child) -+{ -+ return process_wait (child); -+} -+ -+/* Create system call. */ -+static int -+sys_create (const char *ufile, unsigned initial_size) -+{ -+ char *kfile = copy_in_string (ufile); -+ bool ok; -+ -+ lock_acquire (&fs_lock); -+ ok = filesys_create (kfile, initial_size); -+ lock_release (&fs_lock); -+ -+ palloc_free_page (kfile); -+ -+ return ok; -+} -+ -+/* Remove system call. */ -+static int -+sys_remove (const char *ufile) -+{ -+ char *kfile = copy_in_string (ufile); -+ bool ok; -+ -+ lock_acquire (&fs_lock); -+ ok = filesys_remove (kfile); -+ lock_release (&fs_lock); -+ -+ palloc_free_page (kfile); -+ -+ return ok; -+} -+ -+/* A file descriptor, for binding a file handle to a file. */ -+struct file_descriptor -+ { -+ struct list_elem elem; /* List element. */ -+ struct file *file; /* File. */ -+ int handle; /* File handle. */ -+ }; -+ -+/* Open system call. */ -+static int -+sys_open (const char *ufile) -+{ -+ char *kfile = copy_in_string (ufile); -+ struct file_descriptor *fd; -+ int handle = -1; -+ -+ fd = malloc (sizeof *fd); -+ if (fd != NULL) -+ { -+ lock_acquire (&fs_lock); -+ fd->file = filesys_open (kfile); -+ if (fd->file != NULL) -+ { -+ struct thread *cur = thread_current (); -+ handle = fd->handle = cur->next_handle++; -+ list_push_front (&cur->fds, &fd->elem); -+ } -+ else -+ free (fd); -+ lock_release (&fs_lock); -+ } -+ -+ palloc_free_page (kfile); -+ return handle; -+} -+ -+/* Returns the file descriptor associated with the given handle. -+ Terminates the process if HANDLE is not associated with an -+ open file. */ -+static struct file_descriptor * -+lookup_fd (int handle) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->fds); e != list_end (&cur->fds); -+ e = list_next (e)) -+ { -+ struct file_descriptor *fd; -+ fd = list_entry (e, struct file_descriptor, elem); -+ if (fd->handle == handle) -+ return fd; -+ } -+ -+ thread_exit (); -+} -+ -+/* Filesize system call. */ -+static int -+sys_filesize (int handle) -+{ -+ struct file_descriptor *fd = lookup_fd (handle); -+ int size; -+ -+ lock_acquire (&fs_lock); -+ size = file_length (fd->file); -+ lock_release (&fs_lock); -+ -+ return size; -+} -+ -+/* Read system call. */ -+static int -+sys_read (int handle, void *udst_, unsigned size) + thread_exit (); + NOT_REACHED (); + } +@@ -192,7 +191,7 @@ sys_exec (const char *ufile) { -- printf ("system call!\n"); -+ uint8_t *udst = udst_; -+ struct file_descriptor *fd; -+ int bytes_read = 0; -+ -+ fd = lookup_fd (handle); -+ while (size > 0) -+ { -+ /* How much to read into this page? */ -+ size_t page_left = PGSIZE - pg_ofs (udst); -+ size_t read_amt = size < page_left ? size : page_left; -+ off_t retval; + tid_t tid; + char *kfile = copy_in_string (ufile); +- + + lock_acquire (&fs_lock); + tid = process_execute (kfile); + lock_release (&fs_lock); +@@ -215,11 +214,11 @@ sys_create (const char *ufile, unsigned initial_size) + { + char *kfile = copy_in_string (ufile); + bool ok; +- ++ + lock_acquire (&fs_lock); + ok = filesys_create (kfile, initial_size); + lock_release (&fs_lock); +- ++ + palloc_free_page (kfile); + + return ok; +@@ -231,16 +230,16 @@ sys_remove (const char *ufile) + { + char *kfile = copy_in_string (ufile); + bool ok; +- ++ + lock_acquire (&fs_lock); + ok = filesys_remove (kfile); + lock_release (&fs_lock); +- ++ + palloc_free_page (kfile); + + return ok; + } +- ++ + /* A file descriptor, for binding a file handle to a file. */ + struct file_descriptor + { +@@ -320,18 +319,7 @@ sys_read (int handle, void *udst_, unsigned size) + struct file_descriptor *fd; + int bytes_read = 0; + +- /* Handle keyboard reads. */ +- if (handle == STDIN_FILENO) +- { +- for (bytes_read = 0; (size_t) bytes_read < size; bytes_read++) +- if (udst >= (uint8_t *) PHYS_BASE || !put_user (udst++, input_getc ())) +- thread_exit (); +- return bytes_read; +- } +- +- /* Handle all other reads. */ + fd = lookup_fd (handle); +- lock_acquire (&fs_lock); + while (size > 0) + { + /* How much to read into this page? */ +@@ -339,32 +327,49 @@ sys_read (int handle, void *udst_, unsigned size) + size_t read_amt = size < page_left ? size : page_left; + off_t retval; + +- /* Check that touching this page is okay. */ +- if (!verify_user (udst)) + /* Read from file into page. */ + if (handle != STDIN_FILENO) -+ { + { + if (!page_lock (udst, true)) + thread_exit (); + lock_acquire (&fs_lock); + retval = file_read (fd->file, udst, read_amt); -+ lock_release (&fs_lock); + lock_release (&fs_lock); +- thread_exit (); + page_unlock (udst); -+ } + } +- +- /* Read from file into page. */ +- retval = file_read (fd->file, udst, read_amt); + else + { + size_t i; @@ -1166,121 +1314,101 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + } + + /* Check success. */ -+ if (retval < 0) -+ { -+ if (bytes_read == 0) -+ bytes_read = -1; -+ break; -+ } + if (retval < 0) + { + if (bytes_read == 0) + bytes_read = -1; + break; + } +- bytes_read += retval; +- +- /* If it was a short read we're done. */ +- if (retval != (off_t) read_amt) +- break; + bytes_read += retval; + if (retval != (off_t) read_amt) + { + /* Short read, so we're done. */ + break; + } -+ -+ /* Advance. */ -+ udst += retval; -+ size -= retval; -+ } -+ -+ return bytes_read; -+} -+ -+/* Write system call. */ -+static int -+sys_write (int handle, void *usrc_, unsigned size) -+{ -+ uint8_t *usrc = usrc_; -+ struct file_descriptor *fd = NULL; -+ int bytes_written = 0; -+ -+ /* Lookup up file descriptor. */ -+ if (handle != STDOUT_FILENO) -+ fd = lookup_fd (handle); -+ -+ while (size > 0) -+ { -+ /* How much bytes to write to this page? */ -+ size_t page_left = PGSIZE - pg_ofs (usrc); -+ size_t write_amt = size < page_left ? size : page_left; -+ off_t retval; -+ + + /* Advance. */ + udst += retval; + size -= retval; + } +- lock_release (&fs_lock); + + return bytes_read; + } +@@ -381,7 +386,6 @@ sys_write (int handle, void *usrc_, unsigned size) + if (handle != STDOUT_FILENO) + fd = lookup_fd (handle); + +- lock_acquire (&fs_lock); + while (size > 0) + { + /* How much bytes to write to this page? */ +@@ -389,21 +393,21 @@ sys_write (int handle, void *usrc_, unsigned size) + size_t write_amt = size < page_left ? size : page_left; + off_t retval; + +- /* Check that we can touch this user page. */ +- if (!verify_user (usrc)) +- { +- lock_release (&fs_lock); +- thread_exit (); +- } +- +- /* Do the write. */ + /* Write from page into file. */ + if (!page_lock (usrc, false)) + thread_exit (); + lock_acquire (&fs_lock); -+ if (handle == STDOUT_FILENO) -+ { + if (handle == STDOUT_FILENO) + { +- putbuf (usrc, write_amt); + putbuf ((char *) usrc, write_amt); -+ retval = write_amt; -+ } -+ else -+ retval = file_write (fd->file, usrc, write_amt); + retval = write_amt; + } + else + retval = file_write (fd->file, usrc, write_amt); + lock_release (&fs_lock); + page_unlock (usrc); + + /* Handle return value. */ -+ if (retval < 0) -+ { -+ if (bytes_written == 0) -+ bytes_written = -1; -+ break; -+ } -+ bytes_written += retval; -+ -+ /* If it was a short write we're done. */ -+ if (retval != (off_t) write_amt) -+ break; -+ -+ /* Advance. */ -+ usrc += retval; -+ size -= retval; -+ } -+ -+ return bytes_written; -+} -+ -+/* Seek system call. */ -+static int -+sys_seek (int handle, unsigned position) -+{ -+ struct file_descriptor *fd = lookup_fd (handle); -+ -+ lock_acquire (&fs_lock); -+ if ((off_t) position >= 0) -+ file_seek (fd->file, position); -+ lock_release (&fs_lock); -+ -+ return 0; -+} -+ -+/* Tell system call. */ -+static int -+sys_tell (int handle) -+{ -+ struct file_descriptor *fd = lookup_fd (handle); -+ unsigned position; -+ -+ lock_acquire (&fs_lock); -+ position = file_tell (fd->file); -+ lock_release (&fs_lock); + if (retval < 0) + { + if (bytes_written == 0) +@@ -420,7 +424,6 @@ sys_write (int handle, void *usrc_, unsigned size) + usrc += retval; + size -= retval; + } +- lock_release (&fs_lock); + + return bytes_written; + } +@@ -435,7 +438,7 @@ sys_seek (int handle, unsigned position) + if ((off_t) position >= 0) + file_seek (fd->file, position); + lock_release (&fs_lock); +- + -+ return position; -+} -+ -+/* Close system call. */ -+static int -+sys_close (int handle) -+{ -+ struct file_descriptor *fd = lookup_fd (handle); -+ lock_acquire (&fs_lock); -+ file_close (fd->file); -+ lock_release (&fs_lock); -+ list_remove (&fd->elem); -+ free (fd); -+ return 0; -+} + return 0; + } + +@@ -449,7 +452,7 @@ sys_tell (int handle) + lock_acquire (&fs_lock); + position = file_tell (fd->file); + lock_release (&fs_lock); +- ++ + return position; + } + +@@ -465,8 +468,110 @@ sys_close (int handle) + free (fd); + return 0; + } + +/* Binds a mapping id to a region of memory and a file. */ +struct mapping @@ -1309,8 +1437,8 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + return m; + } + - thread_exit (); - } ++ thread_exit (); ++} + +/* Remove mapping M from the virtual address space, + writing back any pages that have changed. */ @@ -1326,7 +1454,8 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + file_close (m->file); + free (m); +} -+ + +-/* On thread exit, close all open files. */ +/* Mmap system call. */ +static int +sys_mmap (int handle, void *addr) @@ -1385,21 +1514,22 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c +} + +/* On thread exit, close all open files and unmap all mappings. */ -+void -+syscall_exit (void) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e, *next; -+ -+ for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next) -+ { + void + syscall_exit (void) + { +@@ -475,12 +580,19 @@ syscall_exit (void) + + for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next) + { +- struct file_descriptor *fd; +- fd = list_entry (e, struct file_descriptor, elem); + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem); -+ next = list_next (e); -+ lock_acquire (&fs_lock); -+ file_close (fd->file); -+ lock_release (&fs_lock); -+ free (fd); -+ } + next = list_next (e); + lock_acquire (&fs_lock); + file_close (fd->file); + lock_release (&fs_lock); + free (fd); + } + + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings); + e = next) @@ -1408,22 +1538,12 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + next = list_next (e); + unmap (m); + } -+} -Index: src/userprog/syscall.h -diff -u src/userprog/syscall.h~ src/userprog/syscall.h ---- src/userprog/syscall.h~ -+++ src/userprog/syscall.h -@@ -2,5 +2,6 @@ - #define USERPROG_SYSCALL_H - - void syscall_init (void); -+void syscall_exit (void); - - #endif /* userprog/syscall.h */ -Index: src/vm/frame.c -diff -u src/vm/frame.c~ src/vm/frame.c ---- src/vm/frame.c~ -+++ src/vm/frame.c + } +diff --git a/src/vm/frame.c b/src/vm/frame.c +new file mode 100644 +index 0000000..ef55376 +--- /dev/null ++++ b/src/vm/frame.c @@ -0,0 +1,162 @@ +#include "vm/frame.h" +#include @@ -1587,10 +1707,11 @@ diff -u src/vm/frame.c~ src/vm/frame.c + ASSERT (lock_held_by_current_thread (&f->lock)); + lock_release (&f->lock); +} -Index: src/vm/frame.h -diff -u src/vm/frame.h~ src/vm/frame.h ---- src/vm/frame.h~ -+++ src/vm/frame.h +diff --git a/src/vm/frame.h b/src/vm/frame.h +new file mode 100644 +index 0000000..496f623 +--- /dev/null ++++ b/src/vm/frame.h @@ -0,0 +1,23 @@ +#ifndef VM_FRAME_H +#define VM_FRAME_H @@ -1615,10 +1736,11 @@ diff -u src/vm/frame.h~ src/vm/frame.h +void frame_unlock (struct frame *); + +#endif /* vm/frame.h */ -Index: src/vm/page.c -diff -u src/vm/page.c~ src/vm/page.c ---- src/vm/page.c~ -+++ src/vm/page.c +diff --git a/src/vm/page.c b/src/vm/page.c +new file mode 100644 +index 0000000..f08bcf8 +--- /dev/null ++++ b/src/vm/page.c @@ -0,0 +1,293 @@ +#include "vm/page.h" +#include @@ -1913,10 +2035,11 @@ diff -u src/vm/page.c~ src/vm/page.c + ASSERT (p != NULL); + frame_unlock (p->frame); +} -Index: src/vm/page.h -diff -u src/vm/page.h~ src/vm/page.h ---- src/vm/page.h~ -+++ src/vm/page.h +diff --git a/src/vm/page.h b/src/vm/page.h +new file mode 100644 +index 0000000..b71b9da +--- /dev/null ++++ b/src/vm/page.h @@ -0,0 +1,50 @@ +#ifndef VM_PAGE_H +#define VM_PAGE_H @@ -1968,10 +2091,11 @@ diff -u src/vm/page.h~ src/vm/page.h +hash_less_func page_less; + +#endif /* vm/page.h */ -Index: src/vm/swap.c -diff -u src/vm/swap.c~ src/vm/swap.c ---- src/vm/swap.c~ -+++ src/vm/swap.c +diff --git a/src/vm/swap.c b/src/vm/swap.c +new file mode 100644 +index 0000000..76fcf71 +--- /dev/null ++++ b/src/vm/swap.c @@ -0,0 +1,85 @@ +#include "vm/swap.h" +#include @@ -2058,10 +2182,11 @@ diff -u src/vm/swap.c~ src/vm/swap.c + + return true; +} -Index: src/vm/swap.h -diff -u src/vm/swap.h~ src/vm/swap.h ---- src/vm/swap.h~ -+++ src/vm/swap.h +diff --git a/src/vm/swap.h b/src/vm/swap.h +new file mode 100644 +index 0000000..34d5d51 +--- /dev/null ++++ b/src/vm/swap.h @@ -0,0 +1,11 @@ +#ifndef VM_SWAP_H +#define VM_SWAP_H 1 diff --git a/solutions/p4.patch b/solutions/p4.patch index b94410b..5208179 100644 --- a/solutions/p4.patch +++ b/solutions/p4.patch @@ -1,19 +1,8 @@ -Index: src/Makefile.build -diff -u src/Makefile.build~ src/Makefile.build ---- src/Makefile.build~ -+++ src/Makefile.build -@@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c # GDT in - userprog_SRC += userprog/tss.c # TSS management. - - # No virtual memory code yet. --#vm_SRC = vm/file.c # Some file. -+vm_SRC = vm/page.c -+vm_SRC += vm/frame.c -+vm_SRC += vm/swap.c - - # Filesystem code. - filesys_SRC = filesys/filesys.c # Filesystem core. -@@ -62,6 +64,7 @@ filesys_SRC += filesys/file.c # Files. +diff --git a/src/Makefile.build b/src/Makefile.build +index 1057023..05e888c 100644 +--- a/src/Makefile.build ++++ b/src/Makefile.build +@@ -73,6 +73,7 @@ filesys_SRC += filesys/file.c # Files. filesys_SRC += filesys/directory.c # Directories. filesys_SRC += filesys/inode.c # File headers. filesys_SRC += filesys/fsutil.c # Utilities. @@ -21,93 +10,11 @@ diff -u src/Makefile.build~ src/Makefile.build SOURCES = $(foreach dir,$(KERNEL_SUBDIRS),$($(dir)_SRC)) OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES))) -Index: src/devices/timer.c -diff -u src/devices/timer.c~ src/devices/timer.c ---- src/devices/timer.c~ -+++ src/devices/timer.c -@@ -23,6 +23,9 @@ static volatile int64_t ticks; - Initialized by timer_calibrate(). */ - static unsigned loops_per_tick; - -+/* Threads waiting in timer_sleep(). */ -+static struct list wait_list; -+ - static intr_handler_func timer_interrupt; - static bool too_many_loops (unsigned loops); - static void busy_wait (int64_t loops); -@@ -43,6 +46,8 @@ timer_init (void) - outb (0x40, count >> 8); - - intr_register_ext (0x20, timer_interrupt, "8254 Timer"); -+ -+ list_init (&wait_list); - } - - /* Calibrates loops_per_tick, used to implement brief delays. */ -@@ -93,16 +93,37 @@ - return timer_ticks () - then; - } - -+/* Compares two threads based on their wake-up times. */ -+static bool -+compare_threads_by_wakeup_time (const struct list_elem *a_, -+ const struct list_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct thread *a = list_entry (a_, struct thread, timer_elem); -+ const struct thread *b = list_entry (b_, struct thread, timer_elem); -+ -+ return a->wakeup_time < b->wakeup_time; -+} -+ - /* Sleeps for approximately TICKS timer ticks. Interrupts must - be turned on. */ - void - timer_sleep (int64_t ticks) - { -- int64_t start = timer_ticks (); -+ struct thread *t = thread_current (); -+ -+ /* Schedule our wake-up time. */ -+ t->wakeup_time = timer_ticks () + ticks; - -+ /* Atomically insert the current thread into the wait list. */ - ASSERT (intr_get_level () == INTR_ON); -- while (timer_elapsed (start) < ticks) -- thread_yield (); -+ intr_disable (); -+ list_insert_ordered (&wait_list, &t->timer_elem, -+ compare_threads_by_wakeup_time, NULL); -+ intr_enable (); -+ -+ /* Wait. */ -+ sema_down (&t->timer_sema); - } - - /* Sleeps for approximately MS milliseconds. Interrupts must be -@@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args - { - ticks++; - thread_tick (); -+ -+ while (!list_empty (&wait_list)) -+ { -+ struct thread *t = list_entry (list_front (&wait_list), -+ struct thread, timer_elem); -+ if (ticks < t->wakeup_time) -+ break; -+ sema_up (&t->timer_sema); -+ list_pop_front (&wait_list); -+ } - } - - /* Returns true if LOOPS iterations waits for more than one timer -Index: src/filesys/Make.vars -diff -u src/filesys/Make.vars~ src/filesys/Make.vars ---- src/filesys/Make.vars~ -+++ src/filesys/Make.vars -@@ -6,8 +6,8 @@ TEST_SUBDIRS = tests/userprog tests/file - GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm +diff --git a/src/filesys/Make.vars b/src/filesys/Make.vars +index b3aa005..d04ab67 100644 +--- a/src/filesys/Make.vars ++++ b/src/filesys/Make.vars +@@ -7,7 +7,7 @@ GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm SIMULATOR = --qemu # Uncomment the lines below to enable VM. @@ -119,10 +26,11 @@ diff -u src/filesys/Make.vars~ src/filesys/Make.vars +KERNEL_SUBDIRS += vm +TEST_SUBDIRS += tests/vm +GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm -Index: src/filesys/cache.c -diff -u src/filesys/cache.c~ src/filesys/cache.c ---- src/filesys/cache.c~ -+++ src/filesys/cache.c +diff --git a/src/filesys/cache.c b/src/filesys/cache.c +new file mode 100644 +index 0000000..cd2ff1c +--- /dev/null ++++ b/src/filesys/cache.c @@ -0,0 +1,472 @@ +#include "filesys/cache.h" +#include @@ -596,10 +504,11 @@ diff -u src/filesys/cache.c~ src/filesys/cache.c + free (ra_block); + } +} -Index: src/filesys/cache.h -diff -u src/filesys/cache.h~ src/filesys/cache.h ---- src/filesys/cache.h~ -+++ src/filesys/cache.h +diff --git a/src/filesys/cache.h b/src/filesys/cache.h +new file mode 100644 +index 0000000..2483924 +--- /dev/null ++++ b/src/filesys/cache.h @@ -0,0 +1,23 @@ +#ifndef FILESYS_CACHE_H +#define FILESYS_CACHE_H @@ -624,30 +533,32 @@ diff -u src/filesys/cache.h~ src/filesys/cache.h +void cache_readahead (block_sector_t); + +#endif /* filesys/cache.h */ -Index: src/filesys/directory.c -diff -u src/filesys/directory.c~ src/filesys/directory.c ---- src/filesys/directory.c~ -+++ src/filesys/directory.c -@@ -1,4 +1,5 @@ +diff --git a/src/filesys/directory.c b/src/filesys/directory.c +index 030c1c9..9855b9d 100644 +--- a/src/filesys/directory.c ++++ b/src/filesys/directory.c +@@ -2,6 +2,7 @@ + #include #include #include +#include "filesys/free-map.h" #include "filesys/filesys.h" #include "filesys/inode.h" -@@ -21,12 +21,39 @@ struct dir_entry + #include "threads/malloc.h" +@@ -21,12 +22,39 @@ struct dir_entry bool in_use; /* In use or free? */ }; -/* Creates a directory with space for ENTRY_CNT entries in the - given SECTOR. Returns true if successful, false on failure. */ +-bool +-dir_create (block_sector_t sector, size_t entry_cnt) +/* Creates a directory in the given SECTOR. + The directory's parent is in PARENT_SECTOR. + Returns inode of created directory if successful, + null pointer on faiilure. + On failure, SECTOR is released in the free map. */ --bool +struct inode * --dir_create (block_sector_t sector, size_t entry_cnt) +dir_create (block_sector_t sector, block_sector_t parent_sector) { - return inode_create (sector, entry_cnt * sizeof (struct dir_entry)); @@ -679,7 +590,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c } /* Opens and returns the directory for the given INODE, of which -@@ -35,7 +59,7 @@ struct dir * +@@ -35,7 +63,7 @@ struct dir * dir_open (struct inode *inode) { struct dir *dir = calloc (1, sizeof *dir); @@ -688,7 +599,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c { dir->inode = inode; dir->pos = 0; -@@ -84,10 +108,8 @@ dir_get_inode (struct dir *dir) +@@ -84,10 +112,8 @@ dir_get_inode (struct dir *dir) } /* Searches DIR for a file with the given NAME. @@ -701,7 +612,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c static bool lookup (const struct dir *dir, const char *name, struct dir_entry *ep, off_t *ofsp) -@@ -120,15 +142,16 @@ dir_lookup (const struct dir *dir, const +@@ -120,15 +146,16 @@ dir_lookup (const struct dir *dir, const char *name, struct inode **inode) { struct dir_entry e; @@ -722,7 +633,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c return *inode != NULL; } -@@ -149,10 +172,11 @@ dir_add (struct dir *dir, const char *na +@@ -149,10 +176,11 @@ dir_add (struct dir *dir, const char *name, block_sector_t inode_sector) ASSERT (name != NULL); /* Check NAME for validity. */ @@ -735,7 +646,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c if (lookup (dir, name, NULL, NULL)) goto done; -@@ -175,6 +199,7 @@ dir_add (struct dir *dir, const char *na +@@ -175,6 +203,7 @@ dir_add (struct dir *dir, const char *name, block_sector_t inode_sector) success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e; done: @@ -743,7 +654,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c return success; } -@@ -192,13 +217,37 @@ dir_remove (struct dir *dir, const char +@@ -192,7 +221,11 @@ dir_remove (struct dir *dir, const char *name) ASSERT (dir != NULL); ASSERT (name != NULL); @@ -755,8 +666,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c if (!lookup (dir, name, &e, &ofs)) goto done; - /* Open inode. */ - inode = inode_open (e.inode_sector); +@@ -201,6 +234,26 @@ dir_remove (struct dir *dir, const char *name) if (inode == NULL) goto done; @@ -781,7 +691,9 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c + } + /* Erase directory entry. */ -@@ -211,6 +241,7 @@ dir_remove (struct dir *dir, const char + e.in_use = false; + if (inode_write_at (dir->inode, &e, sizeof e, ofs) != sizeof e) +@@ -211,6 +264,7 @@ dir_remove (struct dir *dir, const char *name) success = true; done: @@ -789,7 +701,7 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c inode_close (inode); return success; } -@@ -223,14 +254,17 @@ dir_readdir (struct dir *dir, char name[ +@@ -223,14 +277,17 @@ dir_readdir (struct dir *dir, char name[NAME_MAX + 1]) { struct dir_entry e; @@ -808,10 +720,10 @@ diff -u src/filesys/directory.c~ src/filesys/directory.c + inode_unlock (dir->inode); return false; } -Index: src/filesys/directory.h -diff -u src/filesys/directory.h~ src/filesys/directory.h ---- src/filesys/directory.h~ -+++ src/filesys/directory.h +diff --git a/src/filesys/directory.h b/src/filesys/directory.h +index 930acf9..b8a4593 100644 +--- a/src/filesys/directory.h ++++ b/src/filesys/directory.h @@ -14,7 +14,7 @@ struct inode; @@ -821,17 +733,18 @@ diff -u src/filesys/directory.h~ src/filesys/directory.h struct dir *dir_open (struct inode *); struct dir *dir_open_root (void); struct dir *dir_reopen (struct dir *); -Index: src/filesys/file.c -diff -u src/filesys/file.c~ src/filesys/file.c ---- src/filesys/file.c~ -+++ src/filesys/file.c -@@ -1,4 +1,5 @@ +diff --git a/src/filesys/file.c b/src/filesys/file.c +index d5fc10d..8669324 100644 +--- a/src/filesys/file.c ++++ b/src/filesys/file.c +@@ -1,5 +1,6 @@ #include "filesys/file.h" #include +#include "filesys/free-map.h" #include "filesys/inode.h" #include "threads/malloc.h" -@@ -11,6 +11,24 @@ struct file + +@@ -11,6 +12,24 @@ struct file bool deny_write; /* Has file_deny_write() been called? */ }; @@ -856,7 +769,7 @@ diff -u src/filesys/file.c~ src/filesys/file.c /* Opens a file for the given INODE, of which it takes ownership, and returns the new file. Returns a null pointer if an allocation fails or if INODE is null. */ -@@ -18,7 +34,7 @@ struct file * +@@ -18,7 +37,7 @@ struct file * file_open (struct inode *inode) { struct file *file = calloc (1, sizeof *file); @@ -865,10 +778,10 @@ diff -u src/filesys/file.c~ src/filesys/file.c { file->inode = inode; file->pos = 0; -Index: src/filesys/file.h -diff -u src/filesys/file.h~ src/filesys/file.h ---- src/filesys/file.h~ -+++ src/filesys/file.h +diff --git a/src/filesys/file.h b/src/filesys/file.h +index a33c5af..63b4a65 100644 +--- a/src/filesys/file.h ++++ b/src/filesys/file.h @@ -1,11 +1,14 @@ #ifndef FILESYS_FILE_H #define FILESYS_FILE_H @@ -884,10 +797,10 @@ diff -u src/filesys/file.h~ src/filesys/file.h struct file *file_open (struct inode *); struct file *file_reopen (struct file *); void file_close (struct file *); -Index: src/filesys/filesys.c -diff -u src/filesys/filesys.c~ src/filesys/filesys.c ---- src/filesys/filesys.c~ -+++ src/filesys/filesys.c +diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c +index 7a53f5f..51b4244 100644 +--- a/src/filesys/filesys.c ++++ b/src/filesys/filesys.c @@ -2,10 +2,12 @@ #include #include @@ -899,17 +812,17 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c #include "filesys/directory.h" +#include "threads/thread.h" - /* The disk that contains the file system. */ - struct disk *fs_device; -@@ -23,6 +25,7 @@ filesys_init (bool format) - PANIC ("hd0:1 (hdb) not present, file system initialization failed"); + /* Partition that contains the file system. */ + struct block *fs_device; +@@ -22,6 +24,7 @@ filesys_init (bool format) + PANIC ("No file system device found, can't initialize file system."); inode_init (); + cache_init (); free_map_init (); if (format) -@@ -37,6 +40,130 @@ void +@@ -36,6 +39,130 @@ void filesys_done (void) { free_map_close (); @@ -1040,7 +953,7 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c } /* Creates a file named NAME with the given INITIAL_SIZE. -@@ -44,16 +171,32 @@ filesys_done (void) +@@ -43,16 +170,32 @@ filesys_done (void) Fails if a file named NAME already exists, or if internal memory allocation fails. */ bool @@ -1082,7 +995,7 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c dir_close (dir); return success; -@@ -64,17 +199,10 @@ filesys_create (const char *name, off_t +@@ -63,17 +206,10 @@ filesys_create (const char *name, off_t initial_size) otherwise. Fails if no file named NAME exists, or if an internal memory allocation fails. */ @@ -1102,7 +1015,7 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c } /* Deletes the file named NAME. -@@ -84,12 +212,35 @@ filesys_open (const char *name) +@@ -83,21 +219,53 @@ filesys_open (const char *name) bool filesys_remove (const char *name) { @@ -1139,9 +1052,8 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c + return false; +} - static void must_succeed_function (int, bool) NO_INLINE; - #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR) -@@ -155,9 +306,18 @@ static void + /* Formats the file system. */ + static void do_format (void) { + struct inode *inode; @@ -1161,10 +1073,10 @@ diff -u src/filesys/filesys.c~ src/filesys/filesys.c + printf ("done.\n"); } -Index: src/filesys/filesys.h -diff -u src/filesys/filesys.h~ src/filesys/filesys.h ---- src/filesys/filesys.h~ -+++ src/filesys/filesys.h +diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h +index c1cda84..f181764 100644 +--- a/src/filesys/filesys.h ++++ b/src/filesys/filesys.h @@ -3,6 +3,7 @@ #include @@ -1173,7 +1085,7 @@ diff -u src/filesys/filesys.h~ src/filesys/filesys.h /* Sectors of system file inodes. */ #define FREE_MAP_SECTOR 0 /* Free map file inode sector. */ -@@ -13,9 +14,10 @@ extern struct disk *fs_device; +@@ -13,8 +14,9 @@ struct block *fs_device; void filesys_init (bool format); void filesys_done (void); @@ -1184,12 +1096,11 @@ diff -u src/filesys/filesys.h~ src/filesys/filesys.h bool filesys_remove (const char *name); +bool filesys_chdir (const char *name); - void filesys_self_test (void); - -Index: src/filesys/free-map.c -diff -u src/filesys/free-map.c~ src/filesys/free-map.c ---- src/filesys/free-map.c~ -+++ src/filesys/free-map.c + #endif /* filesys/filesys.h */ +diff --git a/src/filesys/free-map.c b/src/filesys/free-map.c +index 29ea4df..2c88a5c 100644 +--- a/src/filesys/free-map.c ++++ b/src/filesys/free-map.c @@ -3,15 +3,18 @@ #include #include "filesys/file.h" @@ -1210,7 +1121,7 @@ diff -u src/filesys/free-map.c~ src/filesys/free-map.c free_map = bitmap_create (block_size (fs_device)); if (free_map == NULL) PANIC ("bitmap creation failed--file system device is too large"); -@@ -19,34 +22,33 @@ +@@ -19,34 +22,33 @@ free_map_init (void) bitmap_mark (free_map, ROOT_DIR_SECTOR); } @@ -1261,7 +1172,7 @@ diff -u src/filesys/free-map.c~ src/filesys/free-map.c } /* Opens the free map file and reads it from disk. */ -@@ -64,6 +66,8 @@ +@@ -64,6 +66,8 @@ free_map_open (void) void free_map_close (void) { @@ -1270,7 +1181,7 @@ diff -u src/filesys/free-map.c~ src/filesys/free-map.c file_close (free_map_file); } -@@ -72,9 +76,13 @@ +@@ -72,9 +76,13 @@ free_map_close (void) void free_map_create (void) { @@ -1285,10 +1196,10 @@ diff -u src/filesys/free-map.c~ src/filesys/free-map.c /* Write bitmap to file. */ free_map_file = file_open (inode_open (FREE_MAP_SECTOR)); -Index: src/filesys/free-map.h -diff -u src/filesys/free-map.h~ src/filesys/free-map.h ---- src/filesys/free-map.h~ -+++ src/filesys/free-map.h +diff --git a/src/filesys/free-map.h b/src/filesys/free-map.h +index 316cd1c..63e35e9 100644 +--- a/src/filesys/free-map.h ++++ b/src/filesys/free-map.h @@ -11,7 +11,7 @@ void free_map_create (void); void free_map_open (void); void free_map_close (void); @@ -1299,10 +1210,10 @@ diff -u src/filesys/free-map.h~ src/filesys/free-map.h +void free_map_release (block_sector_t); #endif /* filesys/free-map.h */ -Index: src/filesys/fsutil.c -diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c ---- src/filesys/fsutil.c~ -+++ src/filesys/fsutil.c +diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c +index 447f291..8016fb3 100644 +--- a/src/filesys/fsutil.c ++++ b/src/filesys/fsutil.c @@ -38,7 +38,7 @@ fsutil_cat (char **argv) char *buffer; @@ -1312,7 +1223,7 @@ diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c if (file == NULL) PANIC ("%s: open failed", file_name); buffer = palloc_get_page (PAL_ASSERT); -@@ -117,9 +117,9 @@ +@@ -117,9 +117,9 @@ fsutil_extract (char **argv UNUSED) printf ("Putting '%s' into the file system...\n", file_name); /* Create destination file. */ @@ -1324,7 +1235,7 @@ diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c if (dst == NULL) PANIC ("%s: open failed", file_name); -@@ -162,7 +162,7 @@ fsutil_get (char **argv) +@@ -181,7 +181,7 @@ fsutil_append (char **argv) PANIC ("couldn't allocate buffer"); /* Open source file. */ @@ -1333,10 +1244,10 @@ diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c if (src == NULL) PANIC ("%s: open failed", file_name); size = file_length (src); -Index: src/filesys/inode.c -diff -u src/filesys/inode.c~ src/filesys/inode.c ---- src/filesys/inode.c~ -+++ src/filesys/inode.c +diff --git a/src/filesys/inode.c b/src/filesys/inode.c +index 3463563..58ab0d1 100644 +--- a/src/filesys/inode.c ++++ b/src/filesys/inode.c @@ -1,23 +1,38 @@ #include "filesys/inode.h" +#include @@ -1378,7 +1289,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c }; /* Returns the number of sectors to allocate for an inode SIZE -@@ -35,74 +50,59 @@ struct inode +@@ -35,74 +50,59 @@ struct inode block_sector_t sector; /* Sector number of disk location. */ int open_cnt; /* Number of openers. */ bool removed; /* True if deleted, false otherwise. */ @@ -1449,13 +1360,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c /* If this assertion fails, the inode structure is not exactly one sector in size, and you should fix that. */ ASSERT (sizeof *disk_inode == BLOCK_SECTOR_SIZE); -+ disk_inode = cache_zero (block); -+ disk_inode->type = type; -+ disk_inode->length = 0; -+ disk_inode->magic = INODE_MAGIC; -+ cache_dirty (block); -+ cache_unlock (block); - +- - disk_inode = calloc (1, sizeof *disk_inode); - if (disk_inode != NULL) - { @@ -1478,6 +1383,13 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c - free (disk_inode); - } - return success; ++ disk_inode = cache_zero (block); ++ disk_inode->type = type; ++ disk_inode->length = 0; ++ disk_inode->magic = INODE_MAGIC; ++ cache_dirty (block); ++ cache_unlock (block); ++ + inode = inode_open (sector); + if (inode == NULL) + free_map_release (sector); @@ -1485,7 +1397,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c } /* Reads an inode from SECTOR -@@ -115,29 +110,35 @@ inode_open (block_sector_t sector) +@@ -115,29 +115,35 @@ inode_open (block_sector_t sector) struct inode *inode; /* Check whether this inode is already open. */ @@ -1525,7 +1437,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c return inode; } -@@ -146,9 +147,24 @@ struct inode * +@@ -146,10 +152,25 @@ struct inode * inode_reopen (struct inode *inode) { if (inode != NULL) @@ -1551,7 +1463,8 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c + /* Returns INODE's inode number. */ block_sector_t -@@ -161,21 +183,60 @@ inode_close (struct inode *inode) + inode_get_inumber (const struct inode *inode) +@@ -168,21 +189,60 @@ inode_close (struct inode *inode) return; /* Release resources if this was the last opener. */ @@ -1617,7 +1530,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c } /* Marks INODE to be deleted when it is closed by the last caller who -@@ -187,6 +248,157 @@ inode_remove (struct inode *inode) +@@ -194,6 +254,157 @@ inode_remove (struct inode *inode) inode->removed = true; } @@ -1775,7 +1688,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c /* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET. Returns the number of bytes actually read, which may be less than SIZE if an error occurs or end of file is reached. */ -@@ -195,13 +406,12 @@ inode_read_at (struct inode *inode, void +@@ -202,13 +413,12 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) { uint8_t *buffer = buffer_; off_t bytes_read = 0; @@ -1791,7 +1704,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c /* Bytes left in inode, bytes left in sector, lesser of the two. */ off_t inode_left = inode_length (inode) - offset; -@@ -210,26 +420,16 @@ inode_read_at (struct inode *inode, void +@@ -217,26 +427,16 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) /* Number of bytes to actually copy out of this sector. */ int chunk_size = size < min_left ? size : min_left; @@ -1824,7 +1737,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c } /* Advance. */ -@@ -237,75 +437,82 @@ inode_read_at (struct inode *inode, void +@@ -244,75 +444,82 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) offset += chunk_size; bytes_read += chunk_size; } @@ -1945,7 +1858,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c return bytes_written; } -@@ -315,8 +522,12 @@ inode_write_at (struct inode *inode, con +@@ -322,8 +529,12 @@ inode_write_at (struct inode *inode, const void *buffer_, off_t size, void inode_deny_write (struct inode *inode) { @@ -1959,7 +1872,7 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c } /* Re-enables writes to INODE. -@@ -325,14 +536,47 @@ inode_deny_write (struct inode *inode) +@@ -332,14 +543,47 @@ inode_deny_write (struct inode *inode) void inode_allow_write (struct inode *inode) { @@ -2008,11 +1921,11 @@ diff -u src/filesys/inode.c~ src/filesys/inode.c +{ + lock_release (&inode->lock); } -Index: src/filesys/inode.h -diff -u src/filesys/inode.h~ src/filesys/inode.h ---- src/filesys/inode.h~ -+++ src/filesys/inode.h -@@ -7,11 +7,19 @@ +diff --git a/src/filesys/inode.h b/src/filesys/inode.h +index cb42310..380d1b7 100644 +--- a/src/filesys/inode.h ++++ b/src/filesys/inode.h +@@ -7,10 +7,18 @@ struct bitmap; @@ -2032,8 +1945,7 @@ diff -u src/filesys/inode.h~ src/filesys/inode.h block_sector_t inode_get_inumber (const struct inode *); void inode_close (struct inode *); void inode_remove (struct inode *); - off_t inode_read_at (struct inode *, void *, off_t size, off_t offset); -@@ -18,5 +27,8 @@ off_t inode_write_at (struct inode *, co +@@ -19,5 +27,8 @@ off_t inode_write_at (struct inode *, const void *, off_t size, off_t offset); void inode_deny_write (struct inode *); void inode_allow_write (struct inode *); off_t inode_length (const struct inode *); @@ -2042,342 +1954,76 @@ diff -u src/filesys/inode.h~ src/filesys/inode.h +void inode_unlock (struct inode *); #endif /* filesys/inode.h */ -Index: src/threads/init.c -diff -u src/threads/init.c~ src/threads/init.c ---- src/threads/init.c~ -+++ src/threads/init.c -@@ -33,6 +33,8 @@ - #include "filesys/filesys.h" - #include "filesys/fsutil.h" - #endif -+#include "vm/frame.h" -+#include "vm/swap.h" - - /* Amount of physical memory, in 4 kB pages. */ - size_t init_ram_pages; -@@ -124,6 +126,9 @@ main (void) - filesys_init (format_filesys); - #endif - -+ frame_init (); -+ swap_init (); -+ - printf ("Boot complete.\n"); - - /* Run actions specified on kernel command line. */ -Index: src/threads/interrupt.c -diff -u src/threads/interrupt.c~ src/threads/interrupt.c ---- src/threads/interrupt.c~ -+++ src/threads/interrupt.c -@@ -354,6 +354,8 @@ intr_handler (struct intr_frame *frame) - in_external_intr = true; - yield_on_return = false; - } -+ else -+ thread_current ()->user_esp = frame->esp; - - /* Invoke the interrupt's handler. - If there is no handler, invoke the unexpected interrupt -Index: src/threads/thread.c -diff -u src/threads/thread.c~ src/threads/thread.c ---- src/threads/thread.c~ -+++ src/threads/thread.c -@@ -13,6 +13,7 @@ - #include "threads/vaddr.h" - #ifdef USERPROG - #include "userprog/process.h" -+#include "userprog/syscall.h" - #endif - - /* Random value for struct thread's `magic' member. -@@ -55,7 +56,8 @@ static void kernel_thread (thread_func * - static void idle (void *aux UNUSED); - static struct thread *running_thread (void); - static struct thread *next_thread_to_run (void); --static void init_thread (struct thread *, const char *name, int priority); -+static void init_thread (struct thread *, const char *name, int priority, -+ tid_t); - static bool is_thread (struct thread *) UNUSED; - static void *alloc_frame (struct thread *, size_t size); - static void schedule (void); -@@ -82,9 +84,8 @@ thread_init (void) - - /* Set up a thread structure for the running thread. */ - initial_thread = running_thread (); -- init_thread (initial_thread, "main", PRI_DEFAULT); -+ init_thread (initial_thread, "main", PRI_DEFAULT, 0); - initial_thread->status = THREAD_RUNNING; -- initial_thread->tid = allocate_tid (); - } - - /* Starts preemptive thread scheduling by enabling interrupts. -@@ -159,8 +160,8 @@ thread_create (const char *name, int pri - return TID_ERROR; - - /* Initialize thread. */ -- init_thread (t, name, priority); -- tid = t->tid = allocate_tid (); -+ init_thread (t, name, priority, allocate_tid ()); -+ tid = t->tid; - - /* Stack frame for kernel_thread(). */ - kf = alloc_frame (t, sizeof *kf); -@@ -288,10 +289,11 @@ thread_tid (void) - void - thread_exit (void) - { - ASSERT (!intr_context ()); - -+ syscall_exit (); - #ifdef USERPROG - process_exit (); - #endif - - /* Remove thread from all threads list, set our status to dying, -@@ -406,23 +410,35 @@ is_thread (struct thread *t) - /* Does basic initialization of T as a blocked thread named - NAME. */ - static void --init_thread (struct thread *t, const char *name, int priority) -+init_thread (struct thread *t, const char *name, int priority, tid_t tid) - { - enum intr_level old_level; - - ASSERT (t != NULL); - ASSERT (PRI_MIN <= priority && priority <= PRI_MAX); - ASSERT (name != NULL); - - memset (t, 0, sizeof *t); -+ t->tid = tid; - t->status = THREAD_BLOCKED; - strlcpy (t->name, name, sizeof t->name); - t->stack = (uint8_t *) t + PGSIZE; - t->priority = priority; -+ t->exit_code = -1; -+ t->wait_status = NULL; -+ list_init (&t->children); -+ sema_init (&t->timer_sema, 0); -+ t->pagedir = NULL; -+ t->pages = NULL; -+ t->bin_file = NULL; -+ list_init (&t->fds); -+ list_init (&t->mappings); -+ t->next_handle = 2; +diff --git a/src/threads/thread.c b/src/threads/thread.c +index f9f2310..1c82b6c 100644 +--- a/src/threads/thread.c ++++ b/src/threads/thread.c +@@ -475,6 +475,7 @@ init_thread (struct thread *t, const char *name, int priority, tid_t tid) + list_init (&t->fds); + list_init (&t->mappings); + t->next_handle = 2; + t->wd = NULL; t->magic = THREAD_MAGIC; - old_level = intr_disable (); list_push_back (&all_list, &t->allelem); - intr_set_level (old_level); - } - -Index: src/threads/thread.h -diff -u src/threads/thread.h~ src/threads/thread.h ---- src/threads/thread.h~ -+++ src/threads/thread.h -@@ -2,8 +2,10 @@ - #define THREADS_THREAD_H - - #include -+#include - #include - #include -+#include "threads/synch.h" - - /* States in a thread's life cycle. */ - enum thread_status -@@ -89,18 +91,50 @@ struct thread - uint8_t *stack; /* Saved stack pointer. */ - int priority; /* Priority. */ - -+ /* Owned by process.c. */ -+ int exit_code; /* Exit code. */ -+ struct wait_status *wait_status; /* This process's completion status. */ -+ struct list children; /* Completion status of children. */ -+ - /* Shared between thread.c and synch.c. */ - struct list_elem elem; /* List element. */ - --#ifdef USERPROG -+ /* Alarm clock. */ -+ int64_t wakeup_time; /* Time to wake this thread up. */ -+ struct list_elem timer_elem; /* Element in timer_wait_list. */ -+ struct semaphore timer_sema; /* Semaphore. */ -+ - /* Owned by userprog/process.c. */ - uint32_t *pagedir; /* Page directory. */ --#endif -+ struct hash *pages; /* Page table. */ -+ struct file *bin_file; /* The binary executable. */ -+ -+ /* Owned by syscall.c. */ -+ struct list fds; /* List of file descriptors. */ -+ struct list mappings; /* Memory-mapped files. */ -+ int next_handle; /* Next handle value. */ -+ void *user_esp; /* User's stack pointer. */ +diff --git a/src/threads/thread.h b/src/threads/thread.h +index b9e7b0c..b60376f 100644 +--- a/src/threads/thread.h ++++ b/src/threads/thread.h +@@ -115,6 +115,7 @@ struct thread + struct list mappings; /* Memory-mapped files. */ + int next_handle; /* Next handle value. */ + void *user_esp; /* User's stack pointer. */ + struct dir *wd; /* Working directory. */ /* Owned by thread.c. */ unsigned magic; /* Detects stack overflow. */ - }; - -+/* Tracks the completion of a process. -+ Reference held by both the parent, in its `children' list, -+ and by the child, in its `wait_status' pointer. */ -+struct wait_status -+ { -+ struct list_elem elem; /* `children' list element. */ -+ struct lock lock; /* Protects ref_cnt. */ -+ int ref_cnt; /* 2=child and parent both alive, -+ 1=either child or parent alive, -+ 0=child and parent both dead. */ -+ tid_t tid; /* Child thread id. */ -+ int exit_code; /* Child exit code, if dead. */ -+ struct semaphore dead; /* 1=child alive, 0=child dead. */ -+ }; -+ - /* If false (default), use round-robin scheduler. - If true, use multi-level feedback queue scheduler. - Controlled by kernel command-line options "-o mlfqs". -Index: src/userprog/exception.c -diff -u src/userprog/exception.c~ src/userprog/exception.c ---- src/userprog/exception.c~ -+++ src/userprog/exception.c -@@ -4,6 +4,7 @@ - #include "userprog/gdt.h" - #include "threads/interrupt.h" - #include "threads/thread.h" -+#include "vm/page.h" - - /* Number of page faults processed. */ - static long long page_fault_cnt; -@@ -148,9 +149,14 @@ page_fault (struct intr_frame *f) - write = (f->error_code & PF_W) != 0; - user = (f->error_code & PF_U) != 0; - -- /* To implement virtual memory, delete the rest of the function -- body, and replace it with code that brings in the page to -- which fault_addr refers. */ -+ /* Allow the pager to try to handle it. */ -+ if (user && not_present) -+ { -+ if (!page_in (fault_addr)) -+ thread_exit (); -+ return; -+ } -+ - printf ("Page fault at %p: %s error %s page in %s context.\n", - fault_addr, - not_present ? "not present" : "rights violation", -Index: src/userprog/pagedir.c -diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c ---- src/userprog/pagedir.c~ -+++ src/userprog/pagedir.c -@@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd) - ASSERT (pd != init_page_dir); - for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++) - if (*pde & PTE_P) -- { -- uint32_t *pt = pde_get_pt (*pde); -- uint32_t *pte; -- -- for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++) -- if (*pte & PTE_P) -- palloc_free_page (pte_get_page (*pte)); -- palloc_free_page (pt); -- } -+ palloc_free_page (pde_get_pt (*pde)); - palloc_free_page (pd); - } - -Index: src/userprog/process.c -diff -u src/userprog/process.c~ src/userprog/process.c ---- src/userprog/process.c~ -+++ src/userprog/process.c -@@ -14,12 +14,27 @@ - #include "threads/flags.h" - #include "threads/init.h" - #include "threads/interrupt.h" -+#include "threads/malloc.h" - #include "threads/palloc.h" - #include "threads/thread.h" - #include "threads/vaddr.h" -+#include "vm/page.h" -+#include "vm/frame.h" - - static thread_func start_process NO_RETURN; --static bool load (const char *cmdline, void (**eip) (void), void **esp); -+static bool load (const char *cmd_line, void (**eip) (void), void **esp); -+ -+/* Data structure shared between process_execute() in the -+ invoking thread and start_process() in the newly invoked -+ thread. */ -+struct exec_info -+ { -+ const char *file_name; /* Program to load. */ -+ struct semaphore load_done; /* "Up"ed when loading complete. */ -+ struct wait_status *wait_status; /* Child process. */ +diff --git a/src/userprog/process.c b/src/userprog/process.c +index 7a15814..3d16752 100644 +--- a/src/userprog/process.c ++++ b/src/userprog/process.c +@@ -32,6 +32,7 @@ struct exec_info + const char *file_name; /* Program to load. */ + struct semaphore load_done; /* "Up"ed when loading complete. */ + struct wait_status *wait_status; /* Child process. */ + struct dir *wd; /* Working directory. */ -+ bool success; /* Program successfully loaded? */ -+ }; + bool success; /* Program successfully loaded? */ + }; - /* Starts a new thread running a user program loaded from - FILENAME. The new thread may be scheduled (and may even exit) -@@ -28,41 +43,78 @@ static bool load (const char *cmdline, v +@@ -42,6 +43,7 @@ struct exec_info tid_t process_execute (const char *file_name) { -- char *fn_copy; + struct dir *wd = thread_current ()->wd; -+ struct exec_info exec; -+ char thread_name[16]; -+ char *save_ptr; - tid_t tid; + struct exec_info exec; + char thread_name[16]; + char *save_ptr; +@@ -49,6 +51,9 @@ process_execute (const char *file_name) -- /* Make a copy of FILE_NAME. -- Otherwise there's a race between the caller and load(). */ -- fn_copy = palloc_get_page (0); -- if (fn_copy == NULL) -+ /* Initialize exec_info. */ -+ exec.file_name = file_name; + /* Initialize exec_info. */ + exec.file_name = file_name; + exec.wd = wd != NULL ? dir_reopen (wd) : dir_open_root (); + if (exec.wd == NULL) - return TID_ERROR; -- strlcpy (fn_copy, file_name, PGSIZE); -+ sema_init (&exec.load_done, 0); ++ return TID_ERROR; + sema_init (&exec.load_done, 0); /* Create a new thread to execute FILE_NAME. */ -- tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy); -- if (tid == TID_ERROR) -- palloc_free_page (fn_copy); -+ strlcpy (thread_name, file_name, sizeof thread_name); -+ strtok_r (thread_name, " ", &save_ptr); -+ tid = thread_create (thread_name, PRI_DEFAULT, start_process, &exec); -+ if (tid != TID_ERROR) -+ { -+ sema_down (&exec.load_done); -+ if (exec.success) -+ list_push_back (&thread_current ()->children, &exec.wait_status->elem); -+ else +@@ -61,8 +66,13 @@ process_execute (const char *file_name) + if (exec.success) + list_push_back (&thread_current ()->children, &exec.wait_status->elem); + else +- tid = TID_ERROR; + { + tid = TID_ERROR; + /* Don't close exec.wd; child process will have done so. */ + } -+ } + } + else + dir_close (exec.wd); -+ + return tid; } - - /* A thread function that loads a user process and starts it - running. */ - static void --start_process (void *file_name_) -+start_process (void *exec_) - { -- char *file_name = file_name_; -+ struct exec_info *exec = exec_; +@@ -76,6 +86,8 @@ start_process (void *exec_) struct intr_frame if_; bool success; @@ -2386,528 +2032,73 @@ diff -u src/userprog/process.c~ src/userprog/process.c /* Initialize interrupt frame and load executable. */ memset (&if_, 0, sizeof if_); if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; - if_.cs = SEL_UCSEG; - if_.eflags = FLAG_IF | FLAG_MBS; -- success = load (file_name, &if_.eip, &if_.esp); -+ success = load (exec->file_name, &if_.eip, &if_.esp); - -- /* If load failed, quit. */ -- palloc_free_page (file_name); -+ /* Allocate wait_status. */ -+ if (success) -+ { -+ exec->wait_status = thread_current ()->wait_status -+ = malloc (sizeof *exec->wait_status); -+ success = exec->wait_status != NULL; -+ } -+ -+ /* Initialize wait_status. */ -+ if (success) -+ { -+ lock_init (&exec->wait_status->lock); -+ exec->wait_status->ref_cnt = 2; -+ exec->wait_status->tid = thread_current ()->tid; -+ sema_init (&exec->wait_status->dead, 0); -+ } -+ -+ /* Notify parent thread and clean up. */ -+ exec->success = success; -+ sema_up (&exec->load_done); - if (!success) - thread_exit (); +@@ -334,13 +346,13 @@ load (const char *cmd_line, void (**eip) (void), void **esp) + *cp = '\0'; -@@ -76,18 +128,47 @@ start_process (void *file_name_) - NOT_REACHED (); - } - -+/* Releases one reference to CS and, if it is now unreferenced, -+ frees it. */ -+static void -+release_child (struct wait_status *cs) -+{ -+ int new_ref_cnt; -+ -+ lock_acquire (&cs->lock); -+ new_ref_cnt = --cs->ref_cnt; -+ lock_release (&cs->lock); -+ -+ if (new_ref_cnt == 0) -+ free (cs); -+} -+ - /* Waits for thread TID to die and returns its exit status. If - it was terminated by the kernel (i.e. killed due to an - exception), returns -1. If TID is invalid or if it was not a - child of the calling process, or if process_wait() has already - been successfully called for the given TID, returns -1 -- immediately, without waiting. -- -- This function will be implemented in problem 2-2. For now, it -- does nothing. */ -+ immediately, without waiting. */ - int --process_wait (tid_t child_tid UNUSED) -+process_wait (tid_t child_tid) - { -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); -+ e = list_next (e)) -+ { -+ struct wait_status *cs = list_entry (e, struct wait_status, elem); -+ if (cs->tid == child_tid) -+ { -+ int exit_code; -+ list_remove (e); -+ sema_down (&cs->dead); -+ exit_code = cs->exit_code; -+ release_child (cs); -+ return exit_code; -+ } -+ } - return -1; - } - -@@ -96,8 +177,35 @@ void - process_exit (void) - { - struct thread *cur = thread_current (); -+ struct list_elem *e, *next; - uint32_t *pd; - -+ printf ("%s: exit(%d)\n", cur->name, cur->exit_code); -+ -+ /* Notify parent that we're dead. */ -+ if (cur->wait_status != NULL) -+ { -+ struct wait_status *cs = cur->wait_status; -+ cs->exit_code = cur->exit_code; -+ sema_up (&cs->dead); -+ release_child (cs); -+ } -+ -+ /* Free entries of children list. */ -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); -+ e = next) -+ { -+ struct wait_status *cs = list_entry (e, struct wait_status, elem); -+ next = list_remove (e); -+ release_child (cs); -+ } -+ -+ /* Destroy the page hash table. */ -+ page_exit (); -+ -+ /* Close executable (and allow writes). */ -+ file_close (cur->bin_file); -+ - /* Destroy the current process's page directory and switch back - to the kernel-only page directory. */ - pd = cur->pagedir; -@@ -194,7 +302,7 @@ struct Elf32_Phdr - #define PF_W 2 /* Writable. */ - #define PF_R 4 /* Readable. */ - --static bool setup_stack (void **esp); -+static bool setup_stack (const char *cmd_line, void **esp); - static bool validate_segment (const struct Elf32_Phdr *, struct file *); - static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, - uint32_t read_bytes, uint32_t zero_bytes, -@@ -205,13 +313,15 @@ static bool load_segment (struct file *f - and its initial stack pointer into *ESP. - Returns true if successful, false otherwise. */ - bool --load (const char *file_name, void (**eip) (void), void **esp) -+load (const char *cmd_line, void (**eip) (void), void **esp) - { - struct thread *t = thread_current (); -+ char file_name[NAME_MAX + 2]; - struct Elf32_Ehdr ehdr; - struct file *file = NULL; - off_t file_ofs; - bool success = false; -+ char *cp; - int i; - - /* Allocate and activate page directory. */ -@@ -220,13 +330,28 @@ load (const char *file_name, void (**eip - goto done; - process_activate (); - -+ /* Create page hash table. */ -+ t->pages = malloc (sizeof *t->pages); -+ if (t->pages == NULL) -+ goto done; -+ hash_init (t->pages, page_hash, page_less, NULL); -+ -+ /* Extract file_name from command line. */ -+ while (*cmd_line == ' ') -+ cmd_line++; -+ strlcpy (file_name, cmd_line, sizeof file_name); -+ cp = strchr (file_name, ' '); -+ if (cp != NULL) -+ *cp = '\0'; -+ /* Open executable file. */ -- file = filesys_open (file_name); +- t->bin_file = file = filesys_open (file_name); + t->bin_file = file = file_open (filesys_open (file_name)); if (file == NULL) { printf ("load: %s: open failed\n", file_name); goto done; } +- file_deny_write (t->bin_file); + file_deny_write (file); /* Read and verify executable header. */ if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr -@@ -301,7 +426,7 @@ load (const char *file_name, void (**eip - } - - /* Set up stack. */ -- if (!setup_stack (esp)) -+ if (!setup_stack (cmd_line, esp)) - goto done; - - /* Start address. */ -@@ -311,14 +436,11 @@ load (const char *file_name, void (**eip - - done: - /* We arrive here whether the load is successful or not. */ -- file_close (file); - return success; - } - - /* 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 -@@ -386,79 +508,127 @@ load_segment (struct file *file, off_t o - ASSERT (pg_ofs (upage) == 0); - ASSERT (ofs % PGSIZE == 0); - -- 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; -- -- /* Get a page of memory. */ -- uint8_t *kpage = palloc_get_page (PAL_USER); -- if (kpage == NULL) -+ struct page *p = page_allocate (upage, !writable); -+ if (p == NULL) - return false; -- -- /* Load this page. */ -- if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes) -- { -- palloc_free_page (kpage); -- 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)) -+ if (page_read_bytes > 0) - { -- palloc_free_page (kpage); -- return false; -+ p->file = file; -+ p->file_offset = ofs; -+ p->file_bytes = page_read_bytes; - } -- -- /* Advance. */ - read_bytes -= page_read_bytes; - zero_bytes -= page_zero_bytes; -+ ofs += page_read_bytes; - upage += PGSIZE; - } - return true; - } - --/* Create a minimal stack by mapping a zeroed page at the top of -- user virtual memory. */ -+/* Reverse the order of the ARGC pointers to char in ARGV. */ -+static void -+reverse (int argc, char **argv) -+{ -+ for (; argc > 1; argc -= 2, argv++) -+ { -+ char *tmp = argv[0]; -+ argv[0] = argv[argc - 1]; -+ argv[argc - 1] = tmp; -+ } -+} -+ -+/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose -+ page-relative stack pointer is *OFS, and then adjusts *OFS -+ appropriately. The bytes pushed are rounded to a 32-bit -+ boundary. -+ -+ If successful, returns a pointer to the newly pushed object. -+ On failure, returns a null pointer. */ -+static void * -+push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size) -+{ -+ size_t padsize = ROUND_UP (size, sizeof (uint32_t)); -+ if (*ofs < padsize) -+ return NULL; -+ -+ *ofs -= padsize; -+ memcpy (kpage + *ofs + (padsize - size), buf, size); -+ return kpage + *ofs + (padsize - size); -+} -+ -+/* Sets up command line arguments in KPAGE, which will be mapped -+ to UPAGE in user space. The command line arguments are taken -+ from CMD_LINE, separated by spaces. Sets *ESP to the initial -+ stack pointer for the process. */ - static bool --setup_stack (void **esp) -+init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line, -+ void **esp) - { -- uint8_t *kpage; -- bool success = false; -+ size_t ofs = PGSIZE; -+ char *const null = NULL; -+ char *cmd_line_copy; -+ char *karg, *saveptr; -+ int argc; -+ char **argv; -+ -+ /* Push command line string. */ -+ cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1); -+ if (cmd_line_copy == NULL) -+ return false; - -- kpage = palloc_get_page (PAL_USER | PAL_ZERO); -- if (kpage != NULL) -+ if (push (kpage, &ofs, &null, sizeof null) == NULL) -+ return false; -+ -+ /* Parse command line into arguments -+ and push them in reverse order. */ -+ argc = 0; -+ for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL; -+ karg = strtok_r (NULL, " ", &saveptr)) - { -- success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true); -- if (success) -- *esp = PHYS_BASE; -- else -- palloc_free_page (kpage); -+ void *uarg = upage + (karg - (char *) kpage); -+ if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL) -+ return false; -+ argc++; - } -- return success; -+ -+ /* Reverse the order of the command line arguments. */ -+ argv = (char **) (upage + ofs); -+ reverse (argc, (char **) (kpage + ofs)); -+ -+ /* Push argv, argc, "return address". */ -+ if (push (kpage, &ofs, &argv, sizeof argv) == NULL -+ || push (kpage, &ofs, &argc, sizeof argc) == NULL -+ || push (kpage, &ofs, &null, sizeof null) == NULL) -+ return false; -+ -+ /* Set initial stack pointer. */ -+ *esp = upage + ofs; -+ 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; -- otherwise, it is read-only. -- UPAGE must not already be mapped. -- KPAGE should probably be a page obtained from the user pool -- with palloc_get_page(). -- Returns true on success, false if UPAGE is already mapped or -- if memory allocation fails. */ -+/* Create a minimal stack for T by mapping a page at the -+ top of user virtual memory. Fills in the page using CMD_LINE -+ and sets *ESP to the stack pointer. */ - static bool --install_page (void *upage, void *kpage, bool writable) -+setup_stack (const char *cmd_line, void **esp) - { -- struct thread *t = thread_current (); -- -- /* Verify that there's not already a page at that virtual -- address, then map our page there. */ -- return (pagedir_get_page (t->pagedir, upage) == NULL -- && pagedir_set_page (t->pagedir, upage, kpage, writable)); -+ struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false); -+ if (page != NULL) -+ { -+ page->frame = frame_alloc_and_lock (page); -+ if (page->frame != NULL) -+ { -+ bool ok; -+ page->read_only = false; -+ page->private = false; -+ ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp); -+ frame_unlock (page->frame); -+ return ok; -+ } -+ } -+ return false; - } -Index: src/userprog/syscall.c -diff -u src/userprog/syscall.c~ src/userprog/syscall.c ---- src/userprog/syscall.c~ -+++ src/userprog/syscall.c -@@ -1,20 +1,685 @@ - #include "userprog/syscall.h" - #include -+#include - #include -+#include "userprog/process.h" -+#include "userprog/pagedir.h" -+#include "devices/input.h" -+#include "devices/shutdown.h" -+#include "filesys/directory.h" -+#include "filesys/filesys.h" -+#include "filesys/file.h" +diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c +index e6be702..e41cbcd 100644 +--- a/src/userprog/syscall.c ++++ b/src/userprog/syscall.c +@@ -9,6 +9,7 @@ + #include "filesys/directory.h" + #include "filesys/filesys.h" + #include "filesys/file.h" +#include "threads/init.h" #include "threads/interrupt.h" -+#include "threads/malloc.h" -+#include "threads/palloc.h" - #include "threads/thread.h" -- -+#include "threads/vaddr.h" -+#include "vm/page.h" -+ -+ -+static int sys_halt (void); -+static int sys_exit (int status); -+static int sys_exec (const char *ufile); -+static int sys_wait (tid_t); -+static int sys_create (const char *ufile, unsigned initial_size); -+static int sys_remove (const char *ufile); -+static int sys_open (const char *ufile); -+static int sys_filesize (int handle); -+static int sys_read (int handle, void *udst_, unsigned size); -+static int sys_write (int handle, void *usrc_, unsigned size); -+static int sys_seek (int handle, unsigned position); -+static int sys_tell (int handle); -+static int sys_close (int handle); -+static int sys_mmap (int handle, void *addr); -+static int sys_munmap (int mapping); + #include "threads/malloc.h" + #include "threads/palloc.h" +@@ -32,17 +33,19 @@ static int sys_tell (int handle); + static int sys_close (int handle); + static int sys_mmap (int handle, void *addr); + static int sys_munmap (int mapping); +static int sys_chdir (const char *udir); +static int sys_mkdir (const char *udir); +static int sys_readdir (int handle, char *name); +static int sys_isdir (int handle); +static int sys_inumber (int handle); -+ + static void syscall_handler (struct intr_frame *); + static void copy_in (void *, const void *, size_t); - -+static void copy_in (void *, const void *, size_t); -+ +-static struct lock fs_lock; + void syscall_init (void) { intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall"); +- lock_init (&fs_lock); } -+ -+/* System call handler. */ -+static void -+syscall_handler (struct intr_frame *f) -+{ -+ typedef int syscall_function (int, int, int); -+ -+ /* A system call. */ -+ struct syscall -+ { -+ size_t arg_cnt; /* Number of arguments. */ -+ syscall_function *func; /* Implementation. */ -+ }; -+ -+ /* Table of system calls. */ -+ static const struct syscall syscall_table[] = -+ { -+ {0, (syscall_function *) sys_halt}, -+ {1, (syscall_function *) sys_exit}, -+ {1, (syscall_function *) sys_exec}, -+ {1, (syscall_function *) sys_wait}, -+ {2, (syscall_function *) sys_create}, -+ {1, (syscall_function *) sys_remove}, -+ {1, (syscall_function *) sys_open}, -+ {1, (syscall_function *) sys_filesize}, -+ {3, (syscall_function *) sys_read}, -+ {3, (syscall_function *) sys_write}, -+ {2, (syscall_function *) sys_seek}, -+ {1, (syscall_function *) sys_tell}, -+ {1, (syscall_function *) sys_close}, -+ {2, (syscall_function *) sys_mmap}, -+ {1, (syscall_function *) sys_munmap}, + + /* System call handler. */ +@@ -76,6 +79,11 @@ syscall_handler (struct intr_frame *f) + {1, (syscall_function *) sys_close}, + {2, (syscall_function *) sys_mmap}, + {1, (syscall_function *) sys_munmap}, + {1, (syscall_function *) sys_chdir}, + {1, (syscall_function *) sys_mkdir}, + {2, (syscall_function *) sys_readdir}, + {1, (syscall_function *) sys_isdir}, + {1, (syscall_function *) sys_inumber}, -+ }; -+ -+ const struct syscall *sc; -+ unsigned call_nr; -+ int args[3]; + }; -+ /* Get the system call. */ -+ copy_in (&call_nr, f->esp, sizeof call_nr); -+ if (call_nr >= sizeof syscall_table / sizeof *syscall_table) -+ thread_exit (); -+ sc = syscall_table + call_nr; -+ -+ /* Get the system call arguments. */ -+ ASSERT (sc->arg_cnt <= sizeof args / sizeof *args); -+ memset (args, 0, sizeof args); -+ copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt); -+ -+ /* Execute the system call, -+ and set the return value. */ -+ f->eax = sc->func (args[0], args[1], args[2]); -+} -+ -+/* Copies SIZE bytes from user address USRC to kernel address -+ DST. -+ Call thread_exit() if any of the user accesses are invalid. */ - static void --syscall_handler (struct intr_frame *f UNUSED) -+copy_in (void *dst_, const void *usrc_, size_t size) - { -- printf ("system call!\n"); -+ uint8_t *dst = dst_; -+ const uint8_t *usrc = usrc_; -+ -+ while (size > 0) -+ { -+ size_t chunk_size = PGSIZE - pg_ofs (usrc); -+ if (chunk_size > size) -+ chunk_size = size; -+ -+ if (!page_lock (usrc, false)) -+ thread_exit (); -+ memcpy (dst, usrc, chunk_size); -+ page_unlock (usrc); -+ -+ dst += chunk_size; -+ usrc += chunk_size; -+ size -= chunk_size; -+ } -+} -+ + const struct syscall *sc; +@@ -124,6 +132,32 @@ copy_in (void *dst_, const void *usrc_, size_t size) + } + } + +/* Copies SIZE bytes from kernel address SRC to user address + UDST. + Call thread_exit() if any of the user accesses are invalid. */ @@ -2934,133 +2125,74 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + } +} + -+/* Creates a copy of user string US in kernel memory -+ and returns it as a page that must be freed with -+ palloc_free_page(). -+ Truncates the string at PGSIZE bytes in size. -+ Call thread_exit() if any of the user accesses are invalid. */ -+static char * -+copy_in_string (const char *us) -+{ -+ char *ks; -+ char *upage; -+ size_t length; -+ -+ ks = palloc_get_page (0); -+ if (ks == NULL) -+ thread_exit (); -+ -+ length = 0; -+ for (;;) -+ { -+ upage = pg_round_down (us); -+ if (!page_lock (upage, false)) -+ goto lock_error; -+ -+ for (; us < upage + PGSIZE; us++) -+ { -+ ks[length++] = *us; -+ if (*us == '\0') -+ { -+ page_unlock (upage); -+ return ks; -+ } -+ else if (length >= PGSIZE) -+ goto too_long_error; -+ } -+ -+ page_unlock (upage); -+ } -+ -+ too_long_error: -+ page_unlock (upage); -+ lock_error: -+ palloc_free_page (ks); - thread_exit (); - } -+ -+/* Halt system call. */ -+static int -+sys_halt (void) -+{ -+ shutdown_power_off (); -+} -+ -+/* Exit system call. */ -+static int -+sys_exit (int exit_code) -+{ -+ thread_current ()->exit_code = exit_code; -+ thread_exit (); -+ NOT_REACHED (); -+} -+ -+/* Exec system call. */ -+static int -+sys_exec (const char *ufile) -+{ -+ tid_t tid; -+ char *kfile = copy_in_string (ufile); -+ -+ tid = process_execute (kfile); -+ -+ palloc_free_page (kfile); -+ -+ return tid; -+} -+ -+/* Wait system call. */ -+static int -+sys_wait (tid_t child) -+{ -+ return process_wait (child); -+} + /* Creates a copy of user string US in kernel memory + and returns it as a page that must be freed with + palloc_free_page(). +@@ -191,10 +225,8 @@ sys_exec (const char *ufile) + { + tid_t tid; + char *kfile = copy_in_string (ufile); +- +- lock_acquire (&fs_lock); + -+/* Create system call. */ -+static int -+sys_create (const char *ufile, unsigned initial_size) -+{ -+ char *kfile = copy_in_string (ufile); + tid = process_execute (kfile); +- lock_release (&fs_lock); + + palloc_free_page (kfile); + +@@ -213,12 +245,7 @@ static int + sys_create (const char *ufile, unsigned initial_size) + { + char *kfile = copy_in_string (ufile); +- bool ok; +- +- lock_acquire (&fs_lock); +- ok = filesys_create (kfile, initial_size); +- lock_release (&fs_lock); +- + bool ok = filesys_create (kfile, initial_size, FILE_INODE); -+ palloc_free_page (kfile); -+ -+ return ok; -+} -+ -+/* Remove system call. */ -+static int -+sys_remove (const char *ufile) -+{ -+ char *kfile = copy_in_string (ufile); + palloc_free_page (kfile); + + return ok; +@@ -229,12 +256,7 @@ static int + sys_remove (const char *ufile) + { + char *kfile = copy_in_string (ufile); +- bool ok; +- +- lock_acquire (&fs_lock); +- ok = filesys_remove (kfile); +- lock_release (&fs_lock); +- + bool ok = filesys_remove (kfile); -+ palloc_free_page (kfile); -+ -+ return ok; -+} -+ -+/* A file descriptor, for binding a file handle to a file. */ -+struct file_descriptor -+ { -+ struct list_elem elem; /* List element. */ -+ struct file *file; /* File. */ + palloc_free_page (kfile); + + return ok; +@@ -245,6 +267,7 @@ struct file_descriptor + { + struct list_elem elem; /* List element. */ + struct file *file; /* File. */ + struct dir *dir; /* Directory. */ -+ int handle; /* File handle. */ -+ }; -+ -+/* Open system call. */ -+static int -+sys_open (const char *ufile) -+{ -+ char *kfile = copy_in_string (ufile); -+ struct file_descriptor *fd; -+ int handle = -1; -+ + int handle; /* File handle. */ + }; + +@@ -256,20 +279,28 @@ sys_open (const char *ufile) + struct file_descriptor *fd; + int handle = -1; + +- fd = malloc (sizeof *fd); + fd = calloc (1, sizeof *fd); -+ if (fd != NULL) -+ { + if (fd != NULL) + { +- lock_acquire (&fs_lock); +- fd->file = filesys_open (kfile); +- if (fd->file != NULL) + struct inode *inode = filesys_open (kfile); + if (inode != NULL) -+ { + { +- struct thread *cur = thread_current (); +- handle = fd->handle = cur->next_handle++; +- list_push_front (&cur->fds, &fd->elem); + if (inode_get_type (inode) == FILE_INODE) + fd->file = file_open (inode); + else @@ -3076,34 +2208,17 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + free (fd); + inode_close (inode); + } -+ } -+ } -+ -+ palloc_free_page (kfile); -+ return handle; -+} -+ -+/* Returns the file descriptor associated with the given handle. -+ Terminates the process if HANDLE is not associated with an -+ open file. */ -+static struct file_descriptor * -+lookup_fd (int handle) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->fds); e != list_end (&cur->fds); -+ e = list_next (e)) -+ { -+ struct file_descriptor *fd; -+ fd = list_entry (e, struct file_descriptor, elem); -+ if (fd->handle == handle) -+ return fd; -+ } -+ -+ thread_exit (); -+} -+ + } +- else +- free (fd); +- lock_release (&fs_lock); + } + + palloc_free_page (kfile); +@@ -297,16 +328,38 @@ lookup_fd (int handle) + thread_exit (); + } + +/* Returns the file descriptor associated with the given handle. + Terminates the process if HANDLE is not associated with an + open ordinary file. */ @@ -3128,45 +2243,49 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + return fd; +} + -+/* Filesize system call. */ -+static int -+sys_filesize (int handle) -+{ + /* Filesize system call. */ + static int + sys_filesize (int handle) + { +- struct file_descriptor *fd = lookup_fd (handle); + struct file_descriptor *fd = lookup_file_fd (handle); -+ int size; -+ -+ size = file_length (fd->file); -+ -+ return size; -+} -+ -+/* Read system call. */ -+static int -+sys_read (int handle, void *udst_, unsigned size) -+{ -+ uint8_t *udst = udst_; -+ struct file_descriptor *fd; -+ int bytes_read = 0; -+ + int size; + +- lock_acquire (&fs_lock); + size = file_length (fd->file); +- lock_release (&fs_lock); + + return size; + } +@@ -319,7 +372,10 @@ sys_read (int handle, void *udst_, unsigned size) + struct file_descriptor *fd; + int bytes_read = 0; + +- fd = lookup_fd (handle); + /* Look up file descriptor. */ + if (handle != STDIN_FILENO) + fd = lookup_file_fd (handle); + -+ while (size > 0) -+ { -+ /* How much to read into this page? */ -+ size_t page_left = PGSIZE - pg_ofs (udst); -+ size_t read_amt = size < page_left ? size : page_left; -+ off_t retval; -+ + while (size > 0) + { + /* How much to read into this page? */ +@@ -327,44 +383,37 @@ sys_read (int handle, void *udst_, unsigned size) + size_t read_amt = size < page_left ? size : page_left; + off_t retval; + + /* Check that touching this page is okay. */ + if (!page_lock (udst, true)) + thread_exit (); + -+ /* Read from file into page. */ -+ if (handle != STDIN_FILENO) -+ { -+ retval = file_read (fd->file, udst, read_amt); + /* Read from file into page. */ + if (handle != STDIN_FILENO) + { +- if (!page_lock (udst, true)) +- thread_exit (); +- lock_acquire (&fs_lock); + retval = file_read (fd->file, udst, read_amt); +- lock_release (&fs_lock); +- page_unlock (udst); + if (retval < 0) + { + if (bytes_read == 0) @@ -3174,15 +2293,36 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + break; + } + bytes_read += retval; -+ } -+ else -+ { -+ size_t i; -+ -+ for (i = 0; i < read_amt; i++) + } + else + { + size_t i; + + for (i = 0; i < read_amt; i++) +- { +- char c = input_getc (); +- if (!page_lock (udst, true)) +- thread_exit (); +- udst[i] = c; +- page_unlock (udst); +- } + udst[i] = input_getc (); -+ bytes_read = read_amt; -+ } + bytes_read = read_amt; + } +- +- /* Check success. */ +- if (retval < 0) +- { +- if (bytes_read == 0) +- bytes_read = -1; +- break; +- } +- bytes_read += retval; +- if (retval != (off_t) read_amt) +- { +- /* Short read, so we're done. */ +- break; +- } + + /* Release page. */ + page_unlock (udst); @@ -3190,196 +2330,117 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + /* If it was a short read we're done. */ + if (retval != (off_t) read_amt) + break; -+ -+ /* Advance. */ -+ udst += retval; -+ size -= retval; -+ } -+ -+ return bytes_read; -+} -+ -+/* Write system call. */ -+static int -+sys_write (int handle, void *usrc_, unsigned size) -+{ -+ uint8_t *usrc = usrc_; -+ struct file_descriptor *fd = NULL; -+ int bytes_written = 0; -+ -+ /* Lookup up file descriptor. */ -+ if (handle != STDOUT_FILENO) + + /* Advance. */ + udst += retval; +@@ -384,7 +433,7 @@ sys_write (int handle, void *usrc_, unsigned size) + + /* Lookup up file descriptor. */ + if (handle != STDOUT_FILENO) +- fd = lookup_fd (handle); + fd = lookup_file_fd (handle); -+ -+ while (size > 0) -+ { -+ /* How much bytes to write to this page? */ -+ size_t page_left = PGSIZE - pg_ofs (usrc); -+ size_t write_amt = size < page_left ? size : page_left; -+ off_t retval; -+ + + while (size > 0) + { +@@ -393,10 +442,11 @@ sys_write (int handle, void *usrc_, unsigned size) + size_t write_amt = size < page_left ? size : page_left; + off_t retval; + +- /* Write from page into file. */ + /* Check that we can touch this user page. */ -+ if (!page_lock (usrc, false)) -+ thread_exit (); + if (!page_lock (usrc, false)) + thread_exit (); +- lock_acquire (&fs_lock); + + /* Do the write. */ -+ if (handle == STDOUT_FILENO) -+ { -+ putbuf ((char *) usrc, write_amt); -+ retval = write_amt; -+ } -+ else -+ retval = file_write (fd->file, usrc, write_amt); + if (handle == STDOUT_FILENO) + { + putbuf ((char *) usrc, write_amt); +@@ -404,7 +454,8 @@ sys_write (int handle, void *usrc_, unsigned size) + } + else + retval = file_write (fd->file, usrc, write_amt); +- lock_release (&fs_lock); + + /* Release user page. */ -+ page_unlock (usrc); -+ -+ /* Handle return value. */ -+ if (retval < 0) -+ { -+ if (bytes_written == 0) -+ bytes_written = -1; -+ break; -+ } -+ bytes_written += retval; -+ -+ /* If it was a short write we're done. */ -+ if (retval != (off_t) write_amt) -+ break; -+ -+ /* Advance. */ -+ usrc += retval; -+ size -= retval; -+ } -+ -+ return bytes_written; -+} -+ -+/* Seek system call. */ -+static int -+sys_seek (int handle, unsigned position) -+{ -+ if ((off_t) position >= 0) + page_unlock (usrc); + + /* Handle return value. */ +@@ -432,13 +483,8 @@ sys_write (int handle, void *usrc_, unsigned size) + static int + sys_seek (int handle, unsigned position) + { +- struct file_descriptor *fd = lookup_fd (handle); +- +- lock_acquire (&fs_lock); + if ((off_t) position >= 0) +- file_seek (fd->file, position); +- lock_release (&fs_lock); +- + file_seek (lookup_file_fd (handle)->file, position); -+ return 0; -+} -+ -+/* Tell system call. */ -+static int -+sys_tell (int handle) -+{ + return 0; + } + +@@ -446,14 +492,7 @@ sys_seek (int handle, unsigned position) + static int + sys_tell (int handle) + { +- struct file_descriptor *fd = lookup_fd (handle); +- unsigned position; +- +- lock_acquire (&fs_lock); +- position = file_tell (fd->file); +- lock_release (&fs_lock); +- +- return position; + return file_tell (lookup_file_fd (handle)->file); -+} -+ -+/* Close system call. */ -+static int -+sys_close (int handle) -+{ -+ struct file_descriptor *fd = lookup_fd (handle); -+ file_close (fd->file); + } + + /* Close system call. */ +@@ -461,9 +500,8 @@ static int + sys_close (int handle) + { + struct file_descriptor *fd = lookup_fd (handle); +- lock_acquire (&fs_lock); + file_close (fd->file); +- lock_release (&fs_lock); + dir_close (fd->dir); -+ list_remove (&fd->elem); -+ free (fd); -+ return 0; -+} -+ -+/* Binds a mapping id to a region of memory and a file. */ -+struct mapping -+ { -+ struct list_elem elem; /* List element. */ -+ int handle; /* Mapping id. */ -+ struct file *file; /* File. */ -+ uint8_t *base; /* Start of memory mapping. */ -+ size_t page_cnt; /* Number of pages mapped. */ -+ }; -+ -+/* Returns the file descriptor associated with the given handle. -+ Terminates the process if HANDLE is not associated with a -+ memory mapping. */ -+static struct mapping * -+lookup_mapping (int handle) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings); -+ e = list_next (e)) -+ { -+ struct mapping *m = list_entry (e, struct mapping, elem); -+ if (m->handle == handle) -+ return m; -+ } -+ -+ thread_exit (); -+} -+ -+/* Remove mapping M from the virtual address space, -+ writing back any pages that have changed. */ -+static void -+unmap (struct mapping *m) -+{ -+ list_remove (&m->elem); -+ while (m->page_cnt-- > 0) -+ { -+ page_deallocate (m->base); -+ m->base += PGSIZE; -+ } -+ file_close (m->file); -+ free (m); -+} -+ -+/* Mmap system call. */ -+static int -+sys_mmap (int handle, void *addr) -+{ + list_remove (&fd->elem); + free (fd); + return 0; +@@ -518,7 +556,7 @@ unmap (struct mapping *m) + static int + sys_mmap (int handle, void *addr) + { +- struct file_descriptor *fd = lookup_fd (handle); + struct file_descriptor *fd = lookup_file_fd (handle); -+ struct mapping *m = malloc (sizeof *m); -+ size_t offset; -+ off_t length; -+ -+ if (m == NULL || addr == NULL || pg_ofs (addr) != 0) -+ return -1; -+ -+ m->handle = thread_current ()->next_handle++; -+ m->file = file_reopen (fd->file); -+ if (m->file == NULL) -+ { -+ free (m); -+ return -1; -+ } -+ m->base = addr; -+ m->page_cnt = 0; -+ list_push_front (&thread_current ()->mappings, &m->elem); -+ -+ offset = 0; -+ length = file_length (m->file); -+ while (length > 0) -+ { -+ struct page *p = page_allocate ((uint8_t *) addr + offset, false); -+ if (p == NULL) -+ { -+ unmap (m); -+ return -1; -+ } -+ p->private = false; -+ p->file = m->file; -+ p->file_offset = offset; -+ p->file_bytes = length >= PGSIZE ? PGSIZE : length; -+ offset += p->file_bytes; -+ length -= p->file_bytes; -+ m->page_cnt++; -+ } -+ -+ return m->handle; -+} -+ -+/* Munmap system call. */ -+static int -+sys_munmap (int mapping) -+{ -+ unmap (lookup_mapping (mapping)); -+ return 0; -+} + struct mapping *m = malloc (sizeof *m); + size_t offset; + off_t length; +@@ -527,9 +565,7 @@ sys_mmap (int handle, void *addr) + return -1; + + m->handle = thread_current ()->next_handle++; +- lock_acquire (&fs_lock); + m->file = file_reopen (fd->file); +- lock_release (&fs_lock); + if (m->file == NULL) + { + free (m); +@@ -540,9 +576,7 @@ sys_mmap (int handle, void *addr) + list_push_front (&thread_current ()->mappings, &m->elem); + + offset = 0; +- lock_acquire (&fs_lock); + length = file_length (m->file); +- lock_release (&fs_lock); + while (length > 0) + { + struct page *p = page_allocate ((uint8_t *) addr + offset, false); +@@ -570,6 +604,58 @@ sys_munmap (int mapping) + unmap (lookup_mapping (mapping)); + return 0; + } + +/* Chdir system call. */ +static int @@ -3432,696 +2493,65 @@ diff -u src/userprog/syscall.c~ src/userprog/syscall.c + : dir_get_inode (fd->dir)); + return inode_get_inumber (inode); +} -+ -+/* On thread exit, close all open files and unmap all mappings. */ -+void -+syscall_exit (void) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e, *next; -+ -+ for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next) -+ { -+ struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem); -+ next = list_next (e); -+ file_close (fd->file); + + /* On thread exit, close all open files and unmap all mappings. */ + void +@@ -582,9 +668,8 @@ syscall_exit (void) + { + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem); + next = list_next (e); +- lock_acquire (&fs_lock); + file_close (fd->file); +- lock_release (&fs_lock); + dir_close (fd->dir); -+ free (fd); -+ } -+ -+ for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings); -+ e = next) -+ { -+ struct mapping *m = list_entry (e, struct mapping, elem); -+ next = list_next (e); -+ unmap (m); -+ } + free (fd); + } + +@@ -595,4 +680,6 @@ syscall_exit (void) + next = list_next (e); + unmap (m); + } + + dir_close (cur->wd); -+} -Index: src/userprog/syscall.h -diff -u src/userprog/syscall.h~ src/userprog/syscall.h ---- src/userprog/syscall.h~ -+++ src/userprog/syscall.h -@@ -2,5 +2,6 @@ - #define USERPROG_SYSCALL_H + } +diff --git a/src/vm/frame.c b/src/vm/frame.c +index ef55376..39b4cec 100644 +--- a/src/vm/frame.c ++++ b/src/vm/frame.c +@@ -100,7 +100,6 @@ try_frame_alloc_and_lock (struct page *page) + return NULL; + } - void syscall_init (void); -+void syscall_exit (void); +- + /* Tries really hard to allocate and lock a frame for PAGE. + Returns the frame if successful, false on failure. */ + struct frame * +diff --git a/src/vm/page.c b/src/vm/page.c +index f08bcf8..62aab36 100644 +--- a/src/vm/page.c ++++ b/src/vm/page.c +@@ -24,6 +24,7 @@ destroy_page (struct hash_elem *p_, void *aux UNUSED) + free (p); + } - #endif /* userprog/syscall.h */ -Index: src/vm/frame.c -diff -u src/vm/frame.c~ src/vm/frame.c ---- src/vm/frame.c~ -+++ src/vm/frame.c -@@ -0,0 +1,161 @@ -+#include "vm/frame.h" -+#include -+#include "vm/page.h" -+#include "devices/timer.h" -+#include "threads/init.h" -+#include "threads/malloc.h" -+#include "threads/palloc.h" -+#include "threads/synch.h" -+#include "threads/vaddr.h" -+ -+static struct frame *frames; -+static size_t frame_cnt; -+ -+static struct lock scan_lock; -+static size_t hand; -+ -+/* Initialize the frame manager. */ -+void -+frame_init (void) -+{ -+ void *base; -+ -+ lock_init (&scan_lock); -+ -+ frames = malloc (sizeof *frames * init_ram_pages); -+ if (frames == NULL) -+ PANIC ("out of memory allocating page frames"); -+ -+ while ((base = palloc_get_page (PAL_USER)) != NULL) -+ { -+ struct frame *f = &frames[frame_cnt++]; -+ lock_init (&f->lock); -+ f->base = base; -+ f->page = NULL; -+ } -+} -+ -+/* Tries to allocate and lock a frame for PAGE. -+ Returns the frame if successful, false on failure. */ -+static struct frame * -+try_frame_alloc_and_lock (struct page *page) -+{ -+ size_t i; -+ -+ lock_acquire (&scan_lock); -+ -+ /* Find a free frame. */ -+ for (i = 0; i < frame_cnt; i++) -+ { -+ struct frame *f = &frames[i]; -+ if (!lock_try_acquire (&f->lock)) -+ continue; -+ if (f->page == NULL) -+ { -+ f->page = page; -+ lock_release (&scan_lock); -+ return f; -+ } -+ lock_release (&f->lock); -+ } -+ -+ /* No free frame. Find a frame to evict. */ -+ for (i = 0; i < frame_cnt * 2; i++) -+ { -+ /* Get a frame. */ -+ struct frame *f = &frames[hand]; -+ if (++hand >= frame_cnt) -+ hand = 0; -+ -+ if (!lock_try_acquire (&f->lock)) -+ continue; -+ -+ if (f->page == NULL) -+ { -+ f->page = page; -+ lock_release (&scan_lock); -+ return f; -+ } -+ -+ if (page_accessed_recently (f->page)) -+ { -+ lock_release (&f->lock); -+ continue; -+ } -+ -+ lock_release (&scan_lock); -+ -+ /* Evict this frame. */ -+ if (!page_out (f->page)) -+ { -+ lock_release (&f->lock); -+ return NULL; -+ } -+ -+ f->page = page; -+ return f; -+ } -+ -+ lock_release (&scan_lock); -+ return NULL; -+} -+ -+/* Tries really hard to allocate and lock a frame for PAGE. -+ Returns the frame if successful, false on failure. */ -+struct frame * -+frame_alloc_and_lock (struct page *page) -+{ -+ size_t try; -+ -+ for (try = 0; try < 3; try++) -+ { -+ struct frame *f = try_frame_alloc_and_lock (page); -+ if (f != NULL) -+ { -+ ASSERT (lock_held_by_current_thread (&f->lock)); -+ return f; -+ } -+ timer_msleep (1000); -+ } + -+ return NULL; -+} -+ -+/* Locks P's frame into memory, if it has one. -+ Upon return, p->frame will not change until P is unlocked. */ -+void -+frame_lock (struct page *p) -+{ -+ /* A frame can be asynchronously removed, but never inserted. */ -+ struct frame *f = p->frame; -+ if (f != NULL) -+ { -+ lock_acquire (&f->lock); -+ if (f != p->frame) -+ { -+ lock_release (&f->lock); -+ ASSERT (p->frame == NULL); -+ } -+ } -+} -+ -+/* Releases frame F for use by another page. -+ F must be locked for use by the current process. -+ Any data in F is lost. */ -+void -+frame_free (struct frame *f) -+{ -+ ASSERT (lock_held_by_current_thread (&f->lock)); -+ -+ f->page = NULL; -+ lock_release (&f->lock); -+} -+ -+/* Unlocks frame F, allowing it to be evicted. -+ F must be locked for use by the current process. */ -+void -+frame_unlock (struct frame *f) -+{ -+ ASSERT (lock_held_by_current_thread (&f->lock)); -+ lock_release (&f->lock); -+} -Index: src/vm/frame.h -diff -u src/vm/frame.h~ src/vm/frame.h ---- src/vm/frame.h~ -+++ src/vm/frame.h -@@ -0,0 +1,23 @@ -+#ifndef VM_FRAME_H -+#define VM_FRAME_H -+ -+#include -+#include "threads/synch.h" -+ -+/* A physical frame. */ -+struct frame -+ { -+ struct lock lock; /* Prevent simultaneous access. */ -+ void *base; /* Kernel virtual base address. */ -+ struct page *page; /* Mapped process page, if any. */ -+ }; -+ -+void frame_init (void); -+ -+struct frame *frame_alloc_and_lock (struct page *); -+void frame_lock (struct page *); -+ -+void frame_free (struct frame *); -+void frame_unlock (struct frame *); -+ -+#endif /* vm/frame.h */ -Index: src/vm/page.c -diff -u src/vm/page.c~ src/vm/page.c ---- src/vm/page.c~ -+++ src/vm/page.c -@@ -0,0 +1,294 @@ -+#include "vm/page.h" -+#include -+#include -+#include "vm/frame.h" -+#include "vm/swap.h" -+#include "filesys/file.h" -+#include "threads/malloc.h" -+#include "threads/thread.h" -+#include "userprog/pagedir.h" -+#include "threads/vaddr.h" -+ -+/* Maximum size of process stack, in bytes. */ -+#define STACK_MAX (1024 * 1024) -+ -+/* Destroys a page, which must be in the current process's -+ page table. Used as a callback for hash_destroy(). */ -+static void -+destroy_page (struct hash_elem *p_, void *aux UNUSED) -+{ -+ struct page *p = hash_entry (p_, struct page, hash_elem); -+ frame_lock (p); -+ if (p->frame) -+ frame_free (p->frame); -+ free (p); -+} -+ -+ -+/* Destroys the current process's page table. */ -+void -+page_exit (void) -+{ -+ struct hash *h = thread_current ()->pages; -+ if (h != NULL) -+ hash_destroy (h, destroy_page); -+} -+ -+/* Returns the page containing the given virtual ADDRESS, -+ or a null pointer if no such page exists. -+ Allocates stack pages as necessary. */ -+static struct page * -+page_for_addr (const void *address) -+{ -+ if (address < PHYS_BASE) -+ { -+ struct page p; -+ struct hash_elem *e; -+ -+ /* Find existing page. */ -+ p.addr = (void *) pg_round_down (address); -+ e = hash_find (thread_current ()->pages, &p.hash_elem); -+ if (e != NULL) -+ return hash_entry (e, struct page, hash_elem); -+ -+ /* No page. Expand stack? */ -+ if (address >= PHYS_BASE - STACK_MAX -+ && address >= thread_current ()->user_esp - 32) -+ return page_allocate ((void *) address, false); -+ } -+ return NULL; -+} -+ -+/* Locks a frame for page P and pages it in. -+ Returns true if successful, false on failure. */ -+static bool -+do_page_in (struct page *p) -+{ -+ /* Get a frame for the page. */ -+ p->frame = frame_alloc_and_lock (p); -+ if (p->frame == NULL) -+ return false; -+ -+ /* Copy data into the frame. */ -+ if (p->sector != (block_sector_t) -1) -+ { -+ /* Get data from swap. */ -+ swap_in (p); -+ } -+ else if (p->file != NULL) -+ { -+ /* Get data from file. */ -+ off_t read_bytes = file_read_at (p->file, p->frame->base, -+ p->file_bytes, p->file_offset); -+ off_t zero_bytes = PGSIZE - read_bytes; -+ memset (p->frame->base + read_bytes, 0, zero_bytes); -+ if (read_bytes != p->file_bytes) -+ printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n", -+ read_bytes, p->file_bytes); -+ } -+ else -+ { -+ /* Provide all-zero page. */ -+ memset (p->frame->base, 0, PGSIZE); -+ } -+ -+ return true; -+} -+ -+/* Faults in the page containing FAULT_ADDR. -+ Returns true if successful, false on failure. */ -+bool -+page_in (void *fault_addr) -+{ -+ struct page *p; -+ bool success; -+ -+ /* Can't handle page faults without a hash table. */ -+ if (thread_current ()->pages == NULL) -+ return false; -+ -+ p = page_for_addr (fault_addr); -+ if (p == NULL) -+ return false; -+ -+ frame_lock (p); -+ if (p->frame == NULL) -+ { -+ if (!do_page_in (p)) -+ return false; -+ } -+ ASSERT (lock_held_by_current_thread (&p->frame->lock)); -+ -+ /* Install frame into page table. */ -+ success = pagedir_set_page (thread_current ()->pagedir, p->addr, -+ p->frame->base, !p->read_only); -+ -+ /* Release frame. */ -+ frame_unlock (p->frame); -+ -+ return success; -+} -+ -+/* Evicts page P. -+ P must have a locked frame. -+ Return true if successful, false on failure. */ -+bool -+page_out (struct page *p) -+{ -+ bool dirty; -+ bool ok; -+ -+ ASSERT (p->frame != NULL); -+ ASSERT (lock_held_by_current_thread (&p->frame->lock)); -+ -+ /* Mark page not present in page table, forcing accesses by the -+ process to fault. This must happen before checking the -+ dirty bit, to prevent a race with the process dirtying the -+ page. */ -+ pagedir_clear_page (p->thread->pagedir, p->addr); -+ -+ /* Has the frame been modified? */ -+ dirty = pagedir_is_dirty (p->thread->pagedir, p->addr); -+ -+ /* Write frame contents to disk if necessary. */ -+ if (p->file != NULL) -+ { -+ if (dirty) -+ { -+ if (p->private) -+ ok = swap_out (p); -+ else -+ ok = file_write_at (p->file, p->frame->base, p->file_bytes, -+ p->file_offset) == p->file_bytes; -+ } -+ else -+ ok = true; -+ } -+ else -+ ok = swap_out (p); -+ if (ok) -+ { -+ //memset (p->frame->base, 0xcc, PGSIZE); -+ p->frame = NULL; -+ } -+ return ok; -+} -+ -+/* Returns true if page P's data has been accessed recently, -+ false otherwise. -+ P must have a frame locked into memory. */ -+bool -+page_accessed_recently (struct page *p) -+{ -+ bool was_accessed; -+ -+ ASSERT (p->frame != NULL); -+ ASSERT (lock_held_by_current_thread (&p->frame->lock)); -+ -+ was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr); -+ if (was_accessed) -+ pagedir_set_accessed (p->thread->pagedir, p->addr, false); -+ return was_accessed; -+} -+ -+/* Adds a mapping for user virtual address VADDR to the page hash -+ table. Fails if VADDR is already mapped or if memory -+ allocation fails. */ -+struct page * -+page_allocate (void *vaddr, bool read_only) -+{ -+ struct thread *t = thread_current (); -+ struct page *p = malloc (sizeof *p); -+ if (p != NULL) -+ { -+ p->addr = pg_round_down (vaddr); -+ -+ p->read_only = read_only; -+ p->private = !read_only; -+ -+ p->frame = NULL; -+ -+ p->sector = (block_sector_t) -1; -+ -+ p->file = NULL; -+ p->file_offset = 0; -+ p->file_bytes = 0; -+ -+ p->thread = thread_current (); -+ -+ if (hash_insert (t->pages, &p->hash_elem) != NULL) -+ { -+ /* Already mapped. */ -+ free (p); -+ p = NULL; -+ } -+ } -+ return p; -+} -+ -+/* Evicts the page containing address VADDR -+ and removes it from the page table. */ -+void -+page_deallocate (void *vaddr) -+{ -+ struct page *p = page_for_addr (vaddr); -+ ASSERT (p != NULL); -+ frame_lock (p); -+ if (p->frame) -+ { -+ struct frame *f = p->frame; -+ if (p->file && !p->private) -+ page_out (p); -+ frame_free (f); -+ } -+ hash_delete (thread_current ()->pages, &p->hash_elem); -+ free (p); -+} -+ -+/* Returns a hash value for the page that E refers to. */ -+unsigned -+page_hash (const struct hash_elem *e, void *aux UNUSED) -+{ -+ const struct page *p = hash_entry (e, struct page, hash_elem); -+ return ((uintptr_t) p->addr) >> PGBITS; -+} -+ -+/* Returns true if page A precedes page B. */ -+bool -+page_less (const struct hash_elem *a_, const struct hash_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct page *a = hash_entry (a_, struct page, hash_elem); -+ const struct page *b = hash_entry (b_, struct page, hash_elem); -+ -+ return a->addr < b->addr; -+} -+ -+/* Tries to lock the page containing ADDR into physical memory. -+ If WILL_WRITE is true, the page must be writeable; -+ otherwise it may be read-only. -+ Returns true if successful, false on failure. */ -+bool -+page_lock (const void *addr, bool will_write) -+{ -+ struct page *p = page_for_addr (addr); -+ if (p == NULL || (p->read_only && will_write)) -+ return false; -+ -+ frame_lock (p); -+ if (p->frame == NULL) -+ return (do_page_in (p) -+ && pagedir_set_page (thread_current ()->pagedir, p->addr, -+ p->frame->base, !p->read_only)); -+ else -+ return true; -+} -+ -+/* Unlocks a page locked with page_lock(). */ -+void -+page_unlock (const void *addr) -+{ -+ struct page *p = page_for_addr (addr); -+ ASSERT (p != NULL); -+ frame_unlock (p->frame); -+} -Index: src/vm/page.h -diff -u src/vm/page.h~ src/vm/page.h ---- src/vm/page.h~ -+++ src/vm/page.h -@@ -0,0 +1,50 @@ -+#ifndef VM_PAGE_H -+#define VM_PAGE_H -+ -+#include -+#include "devices/block.h" -+#include "filesys/off_t.h" -+#include "threads/synch.h" -+ -+/* Virtual page. */ -+struct page -+ { -+ /* Immutable members. */ -+ void *addr; /* User virtual address. */ -+ bool read_only; /* Read-only page? */ -+ struct thread *thread; /* Owning thread. */ -+ -+ /* Accessed only in owning process context. */ -+ struct hash_elem hash_elem; /* struct thread `pages' hash element. */ -+ -+ /* Set only in owning process context with frame->frame_lock held. -+ Cleared only with scan_lock and frame->frame_lock held. */ -+ struct frame *frame; /* Page frame. */ -+ -+ /* Swap information, protected by frame->frame_lock. */ -+ block_sector_t sector; /* Starting sector of swap area, or -1. */ -+ -+ /* Memory-mapped file information, protected by frame->frame_lock. */ -+ bool private; /* False to write back to file, -+ true to write back to swap. */ -+ struct file *file; /* File. */ -+ off_t file_offset; /* Offset in file. */ -+ off_t file_bytes; /* Bytes to read/write, 1...PGSIZE. */ -+ }; -+ -+void page_exit (void); -+ -+struct page *page_allocate (void *, bool read_only); -+void page_deallocate (void *vaddr); -+ -+bool page_in (void *fault_addr); -+bool page_out (struct page *); -+bool page_accessed_recently (struct page *); -+ -+bool page_lock (const void *, bool will_write); -+void page_unlock (const void *); -+ -+hash_hash_func page_hash; -+hash_less_func page_less; -+ -+#endif /* vm/page.h */ -Index: src/vm/swap.c -diff -u src/vm/swap.c~ src/vm/swap.c ---- src/vm/swap.c~ -+++ src/vm/swap.c -@@ -0,0 +1,86 @@ -+#include "vm/swap.h" -+#include -+#include -+#include -+#include "vm/frame.h" -+#include "vm/page.h" + /* Destroys the current process's page table. */ + void + page_exit (void) +diff --git a/src/vm/swap.c b/src/vm/swap.c +index 76fcf71..ce9d25e 100644 +--- a/src/vm/swap.c ++++ b/src/vm/swap.c +@@ -4,10 +4,11 @@ + #include + #include "vm/frame.h" + #include "vm/page.h" +#include "devices/block.h" -+#include "threads/synch.h" -+#include "threads/vaddr.h" -+ + #include "threads/synch.h" + #include "threads/vaddr.h" + +-/* The swap device. */ +/* The swap partition. */ -+static struct block *swap_device; -+ -+/* Used swap pages. */ -+static struct bitmap *swap_bitmap; -+ -+/* Protects swap_bitmap. */ -+static struct lock swap_lock; -+ -+/* Number of sectors per page. */ -+#define PAGE_SECTORS (PGSIZE / BLOCK_SECTOR_SIZE) -+ -+/* Sets up swap. */ -+void -+swap_init (void) -+{ -+ swap_device = block_get_role (BLOCK_SWAP); -+ if (swap_device == NULL) -+ { -+ printf ("no swap device--swap disabled\n"); -+ swap_bitmap = bitmap_create (0); -+ } -+ else -+ swap_bitmap = bitmap_create (block_size (swap_device) -+ / PAGE_SECTORS); -+ if (swap_bitmap == NULL) -+ PANIC ("couldn't create swap bitmap"); -+ lock_init (&swap_lock); -+} -+ -+/* Swaps in page P, which must have a locked frame -+ (and be swapped out). */ -+void -+swap_in (struct page *p) -+{ -+ size_t i; -+ -+ ASSERT (p->frame != NULL); -+ ASSERT (lock_held_by_current_thread (&p->frame->lock)); -+ ASSERT (p->sector != (block_sector_t) -1); -+ -+ for (i = 0; i < PAGE_SECTORS; i++) -+ block_read (swap_device, p->sector + i, -+ p->frame->base + i * BLOCK_SECTOR_SIZE); -+ bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS); -+ p->sector = (block_sector_t) -1; -+} -+ -+/* Swaps out page P, which must have a locked frame. */ -+bool -+swap_out (struct page *p) -+{ -+ size_t slot; -+ size_t i; -+ -+ ASSERT (p->frame != NULL); -+ ASSERT (lock_held_by_current_thread (&p->frame->lock)); -+ -+ lock_acquire (&swap_lock); -+ slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false); -+ lock_release (&swap_lock); -+ if (slot == BITMAP_ERROR) -+ return false; -+ -+ p->sector = slot * PAGE_SECTORS; -+ for (i = 0; i < PAGE_SECTORS; i++) -+ block_write (swap_device, p->sector + i, -+ p->frame->base + i * BLOCK_SECTOR_SIZE); -+ -+ p->private = false; -+ p->file = NULL; -+ p->file_offset = 0; -+ p->file_bytes = 0; -+ -+ return true; -+} -Index: src/vm/swap.h -diff -u src/vm/swap.h~ src/vm/swap.h ---- src/vm/swap.h~ -+++ src/vm/swap.h -@@ -0,0 +1,11 @@ -+#ifndef VM_SWAP_H -+#define VM_SWAP_H 1 -+ -+#include -+ -+struct page; -+void swap_init (void); -+void swap_in (struct page *); -+bool swap_out (struct page *); -+ -+#endif /* vm/swap.h */ + static struct block *swap_device; + + /* Used swap pages. */ -- 2.30.2