1 diff --git a/src/Makefile.build b/src/Makefile.build
2 index e997d27..1057023 100644
3 --- a/src/Makefile.build
4 +++ b/src/Makefile.build
5 @@ -62,7 +62,9 @@ userprog_SRC += userprog/gdt.c # GDT initialization.
6 userprog_SRC += userprog/tss.c # TSS management.
8 # No virtual memory code yet.
9 -#vm_SRC = vm/file.c # Some file.
15 filesys_SRC = filesys/filesys.c # Filesystem core.
16 diff --git a/src/devices/timer.c b/src/devices/timer.c
17 index 1aebae7..4b920e9 100644
18 --- a/src/devices/timer.c
19 +++ b/src/devices/timer.c
20 @@ -206,7 +206,6 @@ timer_interrupt (struct intr_frame *args UNUSED)
21 if (ticks < t->wakeup_time)
23 sema_up (&t->timer_sema);
24 - thread_yield_to_higher_priority ();
25 list_pop_front (&wait_list);
28 diff --git a/src/threads/fixed-point.h b/src/threads/fixed-point.h
29 deleted file mode 100644
30 index ca88f97..0000000
31 --- a/src/threads/fixed-point.h
34 -#ifndef THREADS_FIXED_POINT_H
35 -#define THREADS_FIXED_POINT_H
40 -#define FIX_BITS 32 /* Total bits per fixed-point number. */
41 -#define FIX_P 16 /* Number of integer bits. */
42 -#define FIX_Q 16 /* Number of fractional bits. */
43 -#define FIX_F (1 << FIX_Q) /* pow(2, FIX_Q). */
45 -#define FIX_MIN_INT (-FIX_MAX_INT) /* Smallest representable integer. */
46 -#define FIX_MAX_INT ((1 << FIX_P) - 1) /* Largest representable integer. */
48 -/* A fixed-point number. */
55 -/* Returns a fixed-point number with F as its internal value. */
56 -static inline fixed_point_t
64 -/* Returns fixed-point number corresponding to integer N. */
65 -static inline fixed_point_t
68 - ASSERT (n >= FIX_MIN_INT && n <= FIX_MAX_INT);
69 - return __mk_fix (n * FIX_F);
72 -/* Returns fixed-point number corresponding to N divided by D. */
73 -static inline fixed_point_t
74 -fix_frac (int n, int d)
77 - ASSERT (n / d >= FIX_MIN_INT && n / d <= FIX_MAX_INT);
78 - return __mk_fix ((long long) n * FIX_F / d);
81 -/* Returns X rounded to the nearest integer. */
83 -fix_round (fixed_point_t x)
85 - return (x.f + FIX_F / 2) / FIX_F;
88 -/* Returns X truncated down to the nearest integer. */
90 -fix_trunc (fixed_point_t x)
96 -static inline fixed_point_t
97 -fix_add (fixed_point_t x, fixed_point_t y)
99 - return __mk_fix (x.f + y.f);
102 -/* Returns X - Y. */
103 -static inline fixed_point_t
104 -fix_sub (fixed_point_t x, fixed_point_t y)
106 - return __mk_fix (x.f - y.f);
109 -/* Returns X * Y. */
110 -static inline fixed_point_t
111 -fix_mul (fixed_point_t x, fixed_point_t y)
113 - return __mk_fix ((long long) x.f * y.f / FIX_F);
116 -/* Returns X * N. */
117 -static inline fixed_point_t
118 -fix_scale (fixed_point_t x, int n)
121 - return __mk_fix (x.f * n);
124 -/* Returns X / Y. */
125 -static inline fixed_point_t
126 -fix_div (fixed_point_t x, fixed_point_t y)
128 - return __mk_fix ((long long) x.f * FIX_F / y.f);
131 -/* Returns X / N. */
132 -static inline fixed_point_t
133 -fix_unscale (fixed_point_t x, int n)
136 - return __mk_fix (x.f / n);
139 -/* Returns 1 / X. */
140 -static inline fixed_point_t
141 -fix_inv (fixed_point_t x)
143 - return fix_div (fix_int (1), x);
146 -/* Returns -1 if X < Y, 0 if X == Y, 1 if X > Y. */
148 -fix_compare (fixed_point_t x, fixed_point_t y)
150 - return x.f < y.f ? -1 : x.f > y.f;
153 -#endif /* threads/fixed-point.h */
154 diff --git a/src/threads/init.c b/src/threads/init.c
155 index cebec2c..9729de7 100644
156 --- a/src/threads/init.c
157 +++ b/src/threads/init.c
159 #include "filesys/filesys.h"
160 #include "filesys/fsutil.h"
162 +#include "vm/frame.h"
163 +#include "vm/swap.h"
165 /* Page directory with kernel mappings only. */
166 uint32_t *init_page_dir;
167 @@ -127,6 +129,9 @@ main (void)
168 filesys_init (format_filesys);
174 printf ("Boot complete.\n");
176 /* Run actions specified on kernel command line. */
177 diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c
178 index e3b90dc..f897882 100644
179 --- a/src/threads/interrupt.c
180 +++ b/src/threads/interrupt.c
181 @@ -360,6 +360,8 @@ intr_handler (struct intr_frame *frame)
182 in_external_intr = true;
183 yield_on_return = false;
186 + thread_current ()->user_esp = frame->esp;
188 /* Invoke the interrupt's handler. */
189 handler = intr_handlers[frame->vec_no];
190 diff --git a/src/threads/synch.c b/src/threads/synch.c
191 index 53197bb..317c68a 100644
192 --- a/src/threads/synch.c
193 +++ b/src/threads/synch.c
194 @@ -113,28 +113,10 @@ sema_up (struct semaphore *sema)
195 ASSERT (sema != NULL);
197 old_level = intr_disable ();
199 if (!list_empty (&sema->waiters))
201 - /* Find highest-priority waiting thread. */
202 - struct thread *max = list_entry (list_max (&sema->waiters,
203 - thread_lower_priority, NULL),
204 - struct thread, elem);
206 - /* Remove `max' from wait list and unblock. */
207 - list_remove (&max->elem);
208 - thread_unblock (max);
210 - /* Yield to a higher-priority thread, if we're running in a
211 - context where it makes sense to do so.
213 - Kind of a funny interaction with donation here.
214 - We only support donation for locks, and locks turn off
215 - interrupts before calling us, so we automatically don't
216 - do the yield here, delegating to lock_release(). */
217 - if (!intr_context () && old_level == INTR_ON)
218 - thread_yield_to_higher_priority ();
220 + thread_unblock (list_entry (list_pop_front (&sema->waiters),
221 + struct thread, elem));
223 intr_set_level (old_level);
226 @@ -210,33 +192,12 @@ lock_init (struct lock *lock)
228 lock_acquire (struct lock *lock)
230 - enum intr_level old_level;
232 ASSERT (lock != NULL);
233 ASSERT (!intr_context ());
234 ASSERT (!lock_held_by_current_thread (lock));
236 - old_level = intr_disable ();
238 - if (lock->holder != NULL)
240 - /* Donate our priority to the thread holding the lock.
241 - First, update the data structures. */
242 - struct thread *donor = thread_current ();
243 - donor->want_lock = lock;
244 - donor->donee = lock->holder;
245 - list_push_back (&lock->holder->donors, &donor->donor_elem);
247 - /* Now implement the priority donation itself
248 - by recomputing the donee's priority
249 - and cascading the donation as far as necessary. */
250 - if (donor->donee != NULL)
251 - thread_recompute_priority (donor->donee);
254 sema_down (&lock->semaphore);
255 lock->holder = thread_current ();
256 - intr_set_level (old_level);
259 /* Tries to acquires LOCK and returns true if successful or false
260 @@ -267,39 +228,11 @@ lock_try_acquire (struct lock *lock)
262 lock_release (struct lock *lock)
264 - enum intr_level old_level;
265 - struct thread *t = thread_current ();
266 - struct list_elem *e;
268 ASSERT (lock != NULL);
269 ASSERT (lock_held_by_current_thread (lock));
271 - old_level = intr_disable ();
273 - /* Return donations to threads that want this lock. */
274 - for (e = list_begin (&t->donors); e != list_end (&t->donors); )
276 - struct thread *donor = list_entry (e, struct thread, donor_elem);
277 - if (donor->want_lock == lock)
279 - donor->donee = NULL;
280 - e = list_remove (e);
286 - /* Release lock. */
288 sema_up (&lock->semaphore);
290 - /* Recompute our priority based on our remaining donations,
291 - then yield to a higher-priority ready thread if one now
293 - thread_recompute_priority (t);
294 - thread_yield_to_higher_priority ();
296 - intr_set_level (old_level);
299 /* Returns true if the current thread holds LOCK, false
300 @@ -318,7 +251,6 @@ struct semaphore_elem
302 struct list_elem elem; /* List element. */
303 struct semaphore semaphore; /* This semaphore. */
304 - struct thread *thread; /* Thread. */
307 /* Initializes condition variable COND. A condition variable
308 @@ -363,26 +295,12 @@ cond_wait (struct condition *cond, struct lock *lock)
309 ASSERT (lock_held_by_current_thread (lock));
311 sema_init (&waiter.semaphore, 0);
312 - waiter.thread = thread_current ();
313 list_push_back (&cond->waiters, &waiter.elem);
315 sema_down (&waiter.semaphore);
320 -semaphore_elem_lower_priority (const struct list_elem *a_,
321 - const struct list_elem *b_,
324 - const struct semaphore_elem *a
325 - = list_entry (a_, struct semaphore_elem, elem);
326 - const struct semaphore_elem *b
327 - = list_entry (b_, struct semaphore_elem, elem);
329 - return a->thread->priority < b->thread->priority;
332 /* If any threads are waiting on COND (protected by LOCK), then
333 this function signals one of them to wake up from its wait.
334 LOCK must be held before calling this function.
335 @@ -399,12 +317,8 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
336 ASSERT (lock_held_by_current_thread (lock));
338 if (!list_empty (&cond->waiters))
340 - struct list_elem *max
341 - = list_max (&cond->waiters, semaphore_elem_lower_priority, NULL);
343 - sema_up (&list_entry (max, struct semaphore_elem, elem)->semaphore);
345 + sema_up (&list_entry (list_pop_front (&cond->waiters),
346 + struct semaphore_elem, elem)->semaphore);
349 /* Wakes up all threads, if any, waiting on COND (protected by
350 diff --git a/src/threads/thread.c b/src/threads/thread.c
351 index 9fa7f1c..f9f2310 100644
352 --- a/src/threads/thread.c
353 +++ b/src/threads/thread.c
357 #include "threads/flags.h"
358 -#include "threads/init.h"
359 #include "threads/interrupt.h"
360 #include "threads/intr-stubs.h"
361 #include "threads/palloc.h"
362 #include "threads/switch.h"
363 #include "threads/synch.h"
364 -#include "devices/timer.h"
365 #include "threads/vaddr.h"
367 #include "userprog/process.h"
368 @@ -56,7 +54,6 @@ static long long user_ticks; /* # of timer ticks in user programs. */
370 #define TIME_SLICE 4 /* # of timer ticks to give each thread. */
371 static unsigned thread_ticks; /* # of timer ticks since last yield. */
372 -static fixed_point_t load_avg; /* Load average. */
374 /* If false (default), use round-robin scheduler.
375 If true, use multi-level feedback queue scheduler.
376 @@ -68,7 +65,8 @@ static void kernel_thread (thread_func *, void *aux);
377 static void idle (void *aux UNUSED);
378 static struct thread *running_thread (void);
379 static struct thread *next_thread_to_run (void);
380 -static void init_thread (struct thread *, const char *name, int priority);
381 +static void init_thread (struct thread *, const char *name, int priority,
383 static bool is_thread (struct thread *) UNUSED;
384 static void *alloc_frame (struct thread *, size_t size);
385 static void schedule (void);
386 @@ -96,13 +94,11 @@ thread_init (void)
387 lock_init (&tid_lock);
388 list_init (&ready_list);
389 list_init (&all_list);
390 - load_avg = fix_int (0);
392 /* Set up a thread structure for the running thread. */
393 initial_thread = running_thread ();
394 - init_thread (initial_thread, "main", PRI_DEFAULT);
395 + init_thread (initial_thread, "main", PRI_DEFAULT, 0);
396 initial_thread->status = THREAD_RUNNING;
397 - initial_thread->tid = allocate_tid ();
400 /* Starts preemptive thread scheduling by enabling interrupts.
401 @@ -122,18 +118,6 @@ thread_start (void)
402 sema_down (&idle_started);
405 -/* Adjust recent CPU of a thread based on load factor
406 - and recompute its priority. */
408 -adjust_recent_cpu (struct thread *t, void *aux)
410 - fixed_point_t load_factor = *(fixed_point_t *)aux;
412 - t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
413 - fix_int (t->nice));
414 - thread_recompute_priority (t);
417 /* Called by the timer interrupt handler at each timer tick.
418 Thus, this function runs in an external interrupt context. */
420 @@ -151,41 +135,9 @@ thread_tick (void)
426 - /* Update load average. */
427 - if (timer_ticks () % TIMER_FREQ == 0)
429 - size_t ready_threads = list_size (&ready_list);
430 - if (t != idle_thread)
433 - load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg),
434 - fix_mul (fix_frac (1, 60), fix_int (ready_threads)));
437 - /* Increment running process's recent_cpu. */
438 - if (t != idle_thread)
439 - t->recent_cpu = fix_add (t->recent_cpu, fix_int (1));
441 - /* Update recent_cpu and thread priorities once per second. */
442 - if (timer_ticks () % TIMER_FREQ == 0)
444 - fixed_point_t twice_load = fix_scale (load_avg, 2);
445 - fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1));
446 - fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1);
448 - thread_foreach (adjust_recent_cpu, &load_factor);
452 - /* Switch threads if time slice has expired. */
453 - if (++thread_ticks >= TIME_SLICE)
456 - thread_recompute_priority (thread_current ());
457 - intr_yield_on_return ();
459 + /* Enforce preemption. */
460 + if (++thread_ticks >= TIME_SLICE)
461 + intr_yield_on_return ();
464 /* Prints thread statistics. */
465 @@ -215,7 +167,6 @@ tid_t
466 thread_create (const char *name, int priority,
467 thread_func *function, void *aux)
469 - struct thread *cur = thread_current ();
471 struct kernel_thread_frame *kf;
472 struct switch_entry_frame *ef;
473 @@ -230,10 +181,8 @@ thread_create (const char *name, int priority,
476 /* Initialize thread. */
477 - init_thread (t, name, thread_mlfqs ? cur->priority : priority);
478 - tid = t->tid = allocate_tid ();
479 - t->nice = cur->nice;
480 - t->recent_cpu = cur->recent_cpu;
481 + init_thread (t, name, priority, allocate_tid ());
484 /* Stack frame for kernel_thread(). */
485 kf = alloc_frame (t, sizeof *kf);
486 @@ -252,8 +201,6 @@ thread_create (const char *name, int priority,
488 /* Add to run queue. */
490 - if (priority > thread_get_priority ())
495 @@ -274,19 +221,6 @@ thread_block (void)
499 -/* Returns true if A has lower priority than B,
500 - within a list of threads. */
502 -thread_lower_priority (const struct list_elem *a_,
503 - const struct list_elem *b_,
506 - const struct thread *a = list_entry (a_, struct thread, elem);
507 - const struct thread *b = list_entry (b_, struct thread, elem);
509 - return a->priority < b->priority;
512 /* Transitions a blocked thread T to the ready-to-run state.
513 This is an error if T is not blocked. (Use thread_yield() to
514 make the running thread ready.)
515 @@ -349,11 +283,11 @@ thread_exit (void)
517 ASSERT (!intr_context ());
526 /* Remove thread from all threads list, set our status to dying,
527 and schedule another process. That process will destroy us
528 when it calls thread_schedule_tail(). */
529 @@ -399,26 +333,11 @@ thread_foreach (thread_action_func *func, void *aux)
534 -recompute_priority_chain (void)
536 - enum intr_level old_level = intr_disable ();
537 - thread_recompute_priority (thread_current ());
538 - thread_yield_to_higher_priority ();
539 - intr_set_level (old_level);
542 -/* Sets the current thread's priority to PRIORITY. */
543 +/* Sets the current thread's priority to NEW_PRIORITY. */
545 -thread_set_priority (int priority)
546 +thread_set_priority (int new_priority)
550 - struct thread *t = thread_current ();
552 - t->normal_priority = priority;
553 - recompute_priority_chain ();
555 + thread_current ()->priority = new_priority;
558 /* Returns the current thread's priority. */
559 @@ -430,98 +349,33 @@ thread_get_priority (void)
561 /* Sets the current thread's nice value to NICE. */
563 -thread_set_nice (int nice)
564 +thread_set_nice (int nice UNUSED)
566 - thread_current ()->nice = nice;
567 - recompute_priority_chain ();
568 + /* Not yet implemented. */
571 /* Returns the current thread's nice value. */
573 thread_get_nice (void)
575 - return thread_current ()->nice;
576 + /* Not yet implemented. */
580 +/* Returns 100 times the system load average. */
582 thread_get_load_avg (void)
585 - enum intr_level level = intr_disable ();
586 - load_avg_int = fix_round (fix_scale (load_avg, 100));
587 - intr_set_level (level);
588 - return load_avg_int;
589 + /* Not yet implemented. */
593 +/* Returns 100 times the current thread's recent_cpu value. */
595 thread_get_recent_cpu (void)
597 - int recent_cpu_int;
598 - enum intr_level level = intr_disable ();
599 - recent_cpu_int = fix_round (fix_scale (thread_current ()->recent_cpu, 100));
600 - intr_set_level (level);
601 - return recent_cpu_int;
604 -/* Returns true if thread A has lower priority than thread B,
605 - within a list of donors. */
607 -donated_lower_priority (const struct list_elem *a_,
608 - const struct list_elem *b_,
611 - const struct thread *a = list_entry (a_, struct thread, donor_elem);
612 - const struct thread *b = list_entry (b_, struct thread, donor_elem);
614 - return a->priority < b->priority;
617 -/* Recomputes T's priority in terms of its normal priority and
618 - its donors' priorities, if any,
619 - and cascades the donation as necessary. */
621 -thread_recompute_priority (struct thread *t)
623 - int old_priority = t->priority;
624 - int default_priority = t->normal_priority;
625 - int donation = PRI_MIN;
628 - default_priority = PRI_MAX - fix_round (t->recent_cpu) / 4 - t->nice * 2;
629 - if (default_priority < PRI_MIN)
630 - default_priority = PRI_MIN;
631 - else if (default_priority > PRI_MAX)
632 - default_priority = PRI_MAX;
634 - if (!list_empty (&t->donors))
635 - donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
636 - struct thread, donor_elem)->priority;
637 - t->priority = donation > default_priority ? donation : default_priority;
638 - if (t->priority > old_priority && t->donee != NULL)
639 - thread_recompute_priority (t->donee);
642 -/* If the ready list contains a thread with a higher priority,
645 -thread_yield_to_higher_priority (void)
647 - enum intr_level old_level = intr_disable ();
648 - if (!list_empty (&ready_list))
650 - struct thread *cur = thread_current ();
651 - struct thread *max = list_entry (list_max (&ready_list,
652 - thread_lower_priority, NULL),
653 - struct thread, elem);
654 - if (max->priority > cur->priority)
656 - if (intr_context ())
657 - intr_yield_on_return ();
662 - intr_set_level (old_level);
663 + /* Not yet implemented. */
667 /* Idle thread. Executes when no other thread is ready to run.
668 @@ -597,7 +451,7 @@ is_thread (struct thread *t)
669 /* Does basic initialization of T as a blocked thread named
672 -init_thread (struct thread *t, const char *name, int priority)
673 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
675 enum intr_level old_level;
677 @@ -606,17 +460,22 @@ init_thread (struct thread *t, const char *name, int priority)
678 ASSERT (name != NULL);
680 memset (t, 0, sizeof *t);
682 t->status = THREAD_BLOCKED;
683 strlcpy (t->name, name, sizeof t->name);
684 t->stack = (uint8_t *) t + PGSIZE;
685 - t->priority = t->normal_priority = priority;
686 - list_init (&t->children);
687 + t->priority = priority;
689 t->wait_status = NULL;
690 + list_init (&t->children);
691 + sema_init (&t->timer_sema, 0);
694 + t->bin_file = NULL;
696 + list_init (&t->mappings);
698 t->magic = THREAD_MAGIC;
699 - sema_init (&t->timer_sema, 0);
700 - list_init (&t->donors);
701 old_level = intr_disable ();
702 list_push_back (&all_list, &t->allelem);
703 intr_set_level (old_level);
704 @@ -645,14 +504,8 @@ next_thread_to_run (void)
706 if (list_empty (&ready_list))
711 - = list_entry (list_max (&ready_list, thread_lower_priority, NULL),
712 - struct thread, elem);
713 - list_remove (&max->elem);
717 + return list_entry (list_pop_front (&ready_list), struct thread, elem);
720 /* Completes a thread switch by activating the new thread's page
721 diff --git a/src/threads/thread.h b/src/threads/thread.h
722 index 2c85d88..b9e7b0c 100644
723 --- a/src/threads/thread.h
724 +++ b/src/threads/thread.h
726 #define THREADS_THREAD_H
732 #include "threads/synch.h"
733 -#include "threads/fixed-point.h"
735 /* States in a thread's life cycle. */
737 @@ -89,19 +89,11 @@ struct thread
738 enum thread_status status; /* Thread state. */
739 char name[16]; /* Name (for debugging purposes). */
740 uint8_t *stack; /* Saved stack pointer. */
742 - /* Scheduler data. */
743 - int priority; /* Priority, including donations. */
744 - int normal_priority; /* Priority, without donations. */
745 - struct list donors; /* Threads donating priority to us. */
746 - struct list_elem donor_elem; /* Element in donors list. */
747 - struct thread *donee; /* Thread we're donating to. */
748 - struct lock *want_lock; /* Lock we're waiting to acquire. */
749 - int nice; /* Niceness. */
750 - fixed_point_t recent_cpu; /* Recent amount of CPU time. */
751 + int priority; /* Priority. */
752 struct list_elem allelem; /* List element for all threads list. */
754 /* Owned by process.c. */
755 + int exit_code; /* Exit code. */
756 struct wait_status *wait_status; /* This process's completion status. */
757 struct list children; /* Completion status of children. */
759 @@ -110,18 +102,19 @@ struct thread
762 int64_t wakeup_time; /* Time to wake this thread up. */
763 - struct list_elem timer_elem; /* Element in wait_list. */
764 + struct list_elem timer_elem; /* Element in timer_wait_list. */
765 struct semaphore timer_sema; /* Semaphore. */
769 /* Owned by userprog/process.c. */
770 uint32_t *pagedir; /* Page directory. */
772 - struct file *bin_file; /* Executable. */
773 + struct hash *pages; /* Page table. */
774 + struct file *bin_file; /* The binary executable. */
776 /* Owned by syscall.c. */
777 struct list fds; /* List of file descriptors. */
778 + struct list mappings; /* Memory-mapped files. */
779 int next_handle; /* Next handle value. */
780 + void *user_esp; /* User's stack pointer. */
782 /* Owned by thread.c. */
783 unsigned magic; /* Detects stack overflow. */
784 @@ -165,10 +158,6 @@ const char *thread_name (void);
786 void thread_exit (void) NO_RETURN;
787 void thread_yield (void);
788 -void thread_yield_to_higher_priority (void);
789 -void thread_recompute_priority (struct thread *);
790 -bool thread_lower_priority (const struct list_elem *, const struct list_elem *,
793 /* Performs some operation on thread t, given auxiliary data AUX. */
794 typedef void thread_action_func (struct thread *t, void *aux);
795 diff --git a/src/userprog/exception.c b/src/userprog/exception.c
796 index 3682478..9cfcf93 100644
797 --- a/src/userprog/exception.c
798 +++ b/src/userprog/exception.c
800 #include "userprog/gdt.h"
801 #include "threads/interrupt.h"
802 #include "threads/thread.h"
803 +#include "vm/page.h"
805 /* Number of page faults processed. */
806 static long long page_fault_cnt;
807 @@ -148,17 +149,14 @@ page_fault (struct intr_frame *f)
808 write = (f->error_code & PF_W) != 0;
809 user = (f->error_code & PF_U) != 0;
811 - /* Handle bad dereferences from system call implementations. */
813 + /* Allow the pager to try to handle it. */
814 + if (user && not_present)
816 - f->eip = (void (*) (void)) f->eax;
818 + if (!page_in (fault_addr))
823 - /* To implement virtual memory, delete the rest of the function
824 - body, and replace it with code that brings in the page to
825 - which fault_addr refers. */
826 printf ("Page fault at %p: %s error %s page in %s context.\n",
828 not_present ? "not present" : "rights violation",
829 diff --git a/src/userprog/pagedir.c b/src/userprog/pagedir.c
830 index a6a87b8..eed41b5 100644
831 --- a/src/userprog/pagedir.c
832 +++ b/src/userprog/pagedir.c
833 @@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd)
834 ASSERT (pd != init_page_dir);
835 for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
838 - uint32_t *pt = pde_get_pt (*pde);
841 - for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
843 - palloc_free_page (pte_get_page (*pte));
844 - palloc_free_page (pt);
846 + palloc_free_page (pde_get_pt (*pde));
847 palloc_free_page (pd);
850 diff --git a/src/userprog/process.c b/src/userprog/process.c
851 index 06ff27e..7a15814 100644
852 --- a/src/userprog/process.c
853 +++ b/src/userprog/process.c
855 #include "threads/palloc.h"
856 #include "threads/thread.h"
857 #include "threads/vaddr.h"
858 +#include "vm/page.h"
859 +#include "vm/frame.h"
861 static thread_func start_process NO_RETURN;
862 static bool load (const char *cmd_line, void (**eip) (void), void **esp);
863 @@ -58,7 +60,7 @@ process_execute (const char *file_name)
864 sema_down (&exec.load_done);
866 list_push_back (&thread_current ()->children, &exec.wait_status->elem);
872 @@ -95,7 +97,6 @@ start_process (void *exec_)
873 lock_init (&exec->wait_status->lock);
874 exec->wait_status->ref_cnt = 2;
875 exec->wait_status->tid = thread_current ()->tid;
876 - exec->wait_status->exit_code = -1;
877 sema_init (&exec->wait_status->dead, 0);
880 @@ -167,14 +168,13 @@ process_exit (void)
881 struct list_elem *e, *next;
884 - /* Close executable (and allow writes). */
885 - file_close (cur->bin_file);
886 + printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
888 /* Notify parent that we're dead. */
889 if (cur->wait_status != NULL)
891 struct wait_status *cs = cur->wait_status;
892 - printf ("%s: exit(%d)\n", cur->name, cs->exit_code);
893 + cs->exit_code = cur->exit_code;
897 @@ -187,7 +187,13 @@ process_exit (void)
898 next = list_remove (e);
902 + /* Destroy the page hash table. */
905 + /* Close executable (and allow writes). */
906 + file_close (cur->bin_file);
908 /* Destroy the current process's page directory and switch back
909 to the kernel-only page directory. */
911 @@ -313,6 +319,12 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
915 + /* Create page hash table. */
916 + t->pages = malloc (sizeof *t->pages);
917 + if (t->pages == NULL)
919 + hash_init (t->pages, page_hash, page_less, NULL);
921 /* Extract file_name from command line. */
922 while (*cmd_line == ' ')
924 @@ -328,7 +340,7 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
925 printf ("load: %s: open failed\n", file_name);
928 - file_deny_write (file);
929 + file_deny_write (t->bin_file);
931 /* Read and verify executable header. */
932 if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
933 @@ -418,8 +430,6 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
935 /* load() helpers. */
937 -static bool install_page (void *upage, void *kpage, bool writable);
939 /* Checks whether PHDR describes a valid, loadable segment in
940 FILE and returns true if so, false otherwise. */
942 @@ -487,38 +497,22 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
943 ASSERT (pg_ofs (upage) == 0);
944 ASSERT (ofs % PGSIZE == 0);
946 - file_seek (file, ofs);
947 while (read_bytes > 0 || zero_bytes > 0)
949 - /* Calculate how to fill this page.
950 - We will read PAGE_READ_BYTES bytes from FILE
951 - and zero the final PAGE_ZERO_BYTES bytes. */
952 size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
953 size_t page_zero_bytes = PGSIZE - page_read_bytes;
955 - /* Get a page of memory. */
956 - uint8_t *kpage = palloc_get_page (PAL_USER);
958 + struct page *p = page_allocate (upage, !writable);
962 - /* Load this page. */
963 - if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
965 - palloc_free_page (kpage);
968 - memset (kpage + page_read_bytes, 0, page_zero_bytes);
970 - /* Add the page to the process's address space. */
971 - if (!install_page (upage, kpage, writable))
972 + if (page_read_bytes > 0)
974 - palloc_free_page (kpage);
977 + p->file_offset = ofs;
978 + p->file_bytes = page_read_bytes;
982 read_bytes -= page_read_bytes;
983 zero_bytes -= page_zero_bytes;
984 + ofs += page_read_bytes;
988 @@ -535,7 +529,7 @@ reverse (int argc, char **argv)
989 argv[argc - 1] = tmp;
994 /* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
995 page-relative stack pointer is *OFS, and then adjusts *OFS
996 appropriately. The bytes pushed are rounded to a 32-bit
997 @@ -611,37 +605,19 @@ init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
999 setup_stack (const char *cmd_line, void **esp)
1002 - bool success = false;
1004 - kpage = palloc_get_page (PAL_USER | PAL_ZERO);
1005 - if (kpage != NULL)
1006 + struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
1009 - uint8_t *upage = ((uint8_t *) PHYS_BASE) - PGSIZE;
1010 - if (install_page (upage, kpage, true))
1011 - success = init_cmd_line (kpage, upage, cmd_line, esp);
1013 - palloc_free_page (kpage);
1014 + page->frame = frame_alloc_and_lock (page);
1015 + if (page->frame != NULL)
1018 + page->read_only = false;
1019 + page->private = false;
1020 + ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
1021 + frame_unlock (page->frame);
1028 -/* Adds a mapping from user virtual address UPAGE to kernel
1029 - virtual address KPAGE to the page table.
1030 - If WRITABLE is true, the user process may modify the page;
1031 - otherwise, it is read-only.
1032 - UPAGE must not already be mapped.
1033 - KPAGE should probably be a page obtained from the user pool
1034 - with palloc_get_page().
1035 - Returns true on success, false if UPAGE is already mapped or
1036 - if memory allocation fails. */
1038 -install_page (void *upage, void *kpage, bool writable)
1040 - struct thread *t = thread_current ();
1042 - /* Verify that there's not already a page at that virtual
1043 - address, then map our page there. */
1044 - return (pagedir_get_page (t->pagedir, upage) == NULL
1045 - && pagedir_set_page (t->pagedir, upage, kpage, writable));
1048 diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c
1049 index ef31316..e6be702 100644
1050 --- a/src/userprog/syscall.c
1051 +++ b/src/userprog/syscall.c
1053 #include "userprog/pagedir.h"
1054 #include "devices/input.h"
1055 #include "devices/shutdown.h"
1056 +#include "filesys/directory.h"
1057 #include "filesys/filesys.h"
1058 #include "filesys/file.h"
1059 #include "threads/interrupt.h"
1061 #include "threads/palloc.h"
1062 #include "threads/thread.h"
1063 #include "threads/vaddr.h"
1064 +#include "vm/page.h"
1067 static int sys_halt (void);
1068 @@ -28,11 +30,12 @@ static int sys_write (int handle, void *usrc_, unsigned size);
1069 static int sys_seek (int handle, unsigned position);
1070 static int sys_tell (int handle);
1071 static int sys_close (int handle);
1072 +static int sys_mmap (int handle, void *addr);
1073 +static int sys_munmap (int mapping);
1075 static void syscall_handler (struct intr_frame *);
1076 static void copy_in (void *, const void *, size_t);
1078 -/* Serializes file system operations. */
1080 static struct lock fs_lock;
1083 @@ -71,6 +74,8 @@ syscall_handler (struct intr_frame *f)
1084 {2, (syscall_function *) sys_seek},
1085 {1, (syscall_function *) sys_tell},
1086 {1, (syscall_function *) sys_close},
1087 + {2, (syscall_function *) sys_mmap},
1088 + {1, (syscall_function *) sys_munmap},
1091 const struct syscall *sc;
1092 @@ -93,39 +98,6 @@ syscall_handler (struct intr_frame *f)
1093 f->eax = sc->func (args[0], args[1], args[2]);
1096 -/* Returns true if UADDR is a valid, mapped user address,
1097 - false otherwise. */
1099 -verify_user (const void *uaddr)
1101 - return (uaddr < PHYS_BASE
1102 - && pagedir_get_page (thread_current ()->pagedir, uaddr) != NULL);
1105 -/* Copies a byte from user address USRC to kernel address DST.
1106 - USRC must be below PHYS_BASE.
1107 - Returns true if successful, false if a segfault occurred. */
1109 -get_user (uint8_t *dst, const uint8_t *usrc)
1112 - asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
1113 - : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
1117 -/* Writes BYTE to user address UDST.
1118 - UDST must be below PHYS_BASE.
1119 - Returns true if successful, false if a segfault occurred. */
1121 -put_user (uint8_t *udst, uint8_t byte)
1124 - asm ("movl $1f, %%eax; movb %b2, %0; 1:"
1125 - : "=m" (*udst), "=&a" (eax) : "q" (byte));
1129 /* Copies SIZE bytes from user address USRC to kernel address
1131 Call thread_exit() if any of the user accesses are invalid. */
1132 @@ -134,10 +106,22 @@ copy_in (void *dst_, const void *usrc_, size_t size)
1134 uint8_t *dst = dst_;
1135 const uint8_t *usrc = usrc_;
1137 - for (; size > 0; size--, dst++, usrc++)
1138 - if (usrc >= (uint8_t *) PHYS_BASE || !get_user (dst, usrc))
1143 + size_t chunk_size = PGSIZE - pg_ofs (usrc);
1144 + if (chunk_size > size)
1145 + chunk_size = size;
1147 + if (!page_lock (usrc, false))
1149 + memcpy (dst, usrc, chunk_size);
1150 + page_unlock (usrc);
1152 + dst += chunk_size;
1153 + usrc += chunk_size;
1154 + size -= chunk_size;
1158 /* Creates a copy of user string US in kernel memory
1159 @@ -149,25 +133,40 @@ static char *
1160 copy_in_string (const char *us)
1166 ks = palloc_get_page (0);
1170 - for (length = 0; length < PGSIZE; length++)
1175 - if (us >= (char *) PHYS_BASE || !get_user (ks + length, us++))
1176 + upage = pg_round_down (us);
1177 + if (!page_lock (upage, false))
1180 + for (; us < upage + PGSIZE; us++)
1182 - palloc_free_page (ks);
1184 + ks[length++] = *us;
1187 + page_unlock (upage);
1190 + else if (length >= PGSIZE)
1191 + goto too_long_error;
1194 - if (ks[length] == '\0')
1197 + page_unlock (upage);
1199 - ks[PGSIZE - 1] = '\0';
1203 + page_unlock (upage);
1205 + palloc_free_page (ks);
1209 /* Halt system call. */
1210 @@ -181,7 +180,7 @@ sys_halt (void)
1212 sys_exit (int exit_code)
1214 - thread_current ()->wait_status->exit_code = exit_code;
1215 + thread_current ()->exit_code = exit_code;
1219 @@ -192,7 +191,7 @@ sys_exec (const char *ufile)
1222 char *kfile = copy_in_string (ufile);
1225 lock_acquire (&fs_lock);
1226 tid = process_execute (kfile);
1227 lock_release (&fs_lock);
1228 @@ -215,11 +214,11 @@ sys_create (const char *ufile, unsigned initial_size)
1230 char *kfile = copy_in_string (ufile);
1234 lock_acquire (&fs_lock);
1235 ok = filesys_create (kfile, initial_size);
1236 lock_release (&fs_lock);
1239 palloc_free_page (kfile);
1242 @@ -231,16 +230,16 @@ sys_remove (const char *ufile)
1244 char *kfile = copy_in_string (ufile);
1248 lock_acquire (&fs_lock);
1249 ok = filesys_remove (kfile);
1250 lock_release (&fs_lock);
1253 palloc_free_page (kfile);
1259 /* A file descriptor, for binding a file handle to a file. */
1260 struct file_descriptor
1262 @@ -320,18 +319,7 @@ sys_read (int handle, void *udst_, unsigned size)
1263 struct file_descriptor *fd;
1266 - /* Handle keyboard reads. */
1267 - if (handle == STDIN_FILENO)
1269 - for (bytes_read = 0; (size_t) bytes_read < size; bytes_read++)
1270 - if (udst >= (uint8_t *) PHYS_BASE || !put_user (udst++, input_getc ()))
1272 - return bytes_read;
1275 - /* Handle all other reads. */
1276 fd = lookup_fd (handle);
1277 - lock_acquire (&fs_lock);
1280 /* How much to read into this page? */
1281 @@ -339,32 +327,49 @@ sys_read (int handle, void *udst_, unsigned size)
1282 size_t read_amt = size < page_left ? size : page_left;
1285 - /* Check that touching this page is okay. */
1286 - if (!verify_user (udst))
1287 + /* Read from file into page. */
1288 + if (handle != STDIN_FILENO)
1290 + if (!page_lock (udst, true))
1292 + lock_acquire (&fs_lock);
1293 + retval = file_read (fd->file, udst, read_amt);
1294 lock_release (&fs_lock);
1296 + page_unlock (udst);
1299 - /* Read from file into page. */
1300 - retval = file_read (fd->file, udst, read_amt);
1305 + for (i = 0; i < read_amt; i++)
1307 + char c = input_getc ();
1308 + if (!page_lock (udst, true))
1311 + page_unlock (udst);
1313 + bytes_read = read_amt;
1316 + /* Check success. */
1319 if (bytes_read == 0)
1323 - bytes_read += retval;
1325 - /* If it was a short read we're done. */
1326 - if (retval != (off_t) read_amt)
1328 + bytes_read += retval;
1329 + if (retval != (off_t) read_amt)
1331 + /* Short read, so we're done. */
1339 - lock_release (&fs_lock);
1343 @@ -381,7 +386,6 @@ sys_write (int handle, void *usrc_, unsigned size)
1344 if (handle != STDOUT_FILENO)
1345 fd = lookup_fd (handle);
1347 - lock_acquire (&fs_lock);
1350 /* How much bytes to write to this page? */
1351 @@ -389,21 +393,21 @@ sys_write (int handle, void *usrc_, unsigned size)
1352 size_t write_amt = size < page_left ? size : page_left;
1355 - /* Check that we can touch this user page. */
1356 - if (!verify_user (usrc))
1358 - lock_release (&fs_lock);
1362 - /* Do the write. */
1363 + /* Write from page into file. */
1364 + if (!page_lock (usrc, false))
1366 + lock_acquire (&fs_lock);
1367 if (handle == STDOUT_FILENO)
1369 - putbuf (usrc, write_amt);
1370 + putbuf ((char *) usrc, write_amt);
1374 retval = file_write (fd->file, usrc, write_amt);
1375 + lock_release (&fs_lock);
1376 + page_unlock (usrc);
1378 + /* Handle return value. */
1381 if (bytes_written == 0)
1382 @@ -420,7 +424,6 @@ sys_write (int handle, void *usrc_, unsigned size)
1386 - lock_release (&fs_lock);
1388 return bytes_written;
1390 @@ -435,7 +438,7 @@ sys_seek (int handle, unsigned position)
1391 if ((off_t) position >= 0)
1392 file_seek (fd->file, position);
1393 lock_release (&fs_lock);
1399 @@ -449,7 +452,7 @@ sys_tell (int handle)
1400 lock_acquire (&fs_lock);
1401 position = file_tell (fd->file);
1402 lock_release (&fs_lock);
1408 @@ -465,8 +468,110 @@ sys_close (int handle)
1413 +/* Binds a mapping id to a region of memory and a file. */
1416 + struct list_elem elem; /* List element. */
1417 + int handle; /* Mapping id. */
1418 + struct file *file; /* File. */
1419 + uint8_t *base; /* Start of memory mapping. */
1420 + size_t page_cnt; /* Number of pages mapped. */
1423 +/* Returns the file descriptor associated with the given handle.
1424 + Terminates the process if HANDLE is not associated with a
1425 + memory mapping. */
1426 +static struct mapping *
1427 +lookup_mapping (int handle)
1429 + struct thread *cur = thread_current ();
1430 + struct list_elem *e;
1432 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1433 + e = list_next (e))
1435 + struct mapping *m = list_entry (e, struct mapping, elem);
1436 + if (m->handle == handle)
1443 +/* Remove mapping M from the virtual address space,
1444 + writing back any pages that have changed. */
1446 +unmap (struct mapping *m)
1448 + list_remove (&m->elem);
1449 + while (m->page_cnt-- > 0)
1451 + page_deallocate (m->base);
1452 + m->base += PGSIZE;
1454 + file_close (m->file);
1458 -/* On thread exit, close all open files. */
1459 +/* Mmap system call. */
1461 +sys_mmap (int handle, void *addr)
1463 + struct file_descriptor *fd = lookup_fd (handle);
1464 + struct mapping *m = malloc (sizeof *m);
1468 + if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
1471 + m->handle = thread_current ()->next_handle++;
1472 + lock_acquire (&fs_lock);
1473 + m->file = file_reopen (fd->file);
1474 + lock_release (&fs_lock);
1475 + if (m->file == NULL)
1482 + list_push_front (&thread_current ()->mappings, &m->elem);
1485 + lock_acquire (&fs_lock);
1486 + length = file_length (m->file);
1487 + lock_release (&fs_lock);
1488 + while (length > 0)
1490 + struct page *p = page_allocate ((uint8_t *) addr + offset, false);
1496 + p->private = false;
1497 + p->file = m->file;
1498 + p->file_offset = offset;
1499 + p->file_bytes = length >= PGSIZE ? PGSIZE : length;
1500 + offset += p->file_bytes;
1501 + length -= p->file_bytes;
1508 +/* Munmap system call. */
1510 +sys_munmap (int mapping)
1512 + unmap (lookup_mapping (mapping));
1516 +/* On thread exit, close all open files and unmap all mappings. */
1520 @@ -475,12 +580,19 @@ syscall_exit (void)
1522 for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
1524 - struct file_descriptor *fd;
1525 - fd = list_entry (e, struct file_descriptor, elem);
1526 + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
1527 next = list_next (e);
1528 lock_acquire (&fs_lock);
1529 file_close (fd->file);
1530 lock_release (&fs_lock);
1534 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1537 + struct mapping *m = list_entry (e, struct mapping, elem);
1538 + next = list_next (e);
1542 diff --git a/src/vm/frame.c b/src/vm/frame.c
1543 new file mode 100644
1544 index 0000000..ef55376
1546 +++ b/src/vm/frame.c
1548 +#include "vm/frame.h"
1550 +#include "vm/page.h"
1551 +#include "devices/timer.h"
1552 +#include "threads/init.h"
1553 +#include "threads/malloc.h"
1554 +#include "threads/palloc.h"
1555 +#include "threads/synch.h"
1556 +#include "threads/vaddr.h"
1558 +static struct frame *frames;
1559 +static size_t frame_cnt;
1561 +static struct lock scan_lock;
1562 +static size_t hand;
1564 +/* Initialize the frame manager. */
1570 + lock_init (&scan_lock);
1572 + frames = malloc (sizeof *frames * init_ram_pages);
1573 + if (frames == NULL)
1574 + PANIC ("out of memory allocating page frames");
1576 + while ((base = palloc_get_page (PAL_USER)) != NULL)
1578 + struct frame *f = &frames[frame_cnt++];
1579 + lock_init (&f->lock);
1585 +/* Tries to allocate and lock a frame for PAGE.
1586 + Returns the frame if successful, false on failure. */
1587 +static struct frame *
1588 +try_frame_alloc_and_lock (struct page *page)
1592 + lock_acquire (&scan_lock);
1594 + /* Find a free frame. */
1595 + for (i = 0; i < frame_cnt; i++)
1597 + struct frame *f = &frames[i];
1598 + if (!lock_try_acquire (&f->lock))
1600 + if (f->page == NULL)
1603 + lock_release (&scan_lock);
1606 + lock_release (&f->lock);
1609 + /* No free frame. Find a frame to evict. */
1610 + for (i = 0; i < frame_cnt * 2; i++)
1612 + /* Get a frame. */
1613 + struct frame *f = &frames[hand];
1614 + if (++hand >= frame_cnt)
1617 + if (!lock_try_acquire (&f->lock))
1620 + if (f->page == NULL)
1623 + lock_release (&scan_lock);
1627 + if (page_accessed_recently (f->page))
1629 + lock_release (&f->lock);
1633 + lock_release (&scan_lock);
1635 + /* Evict this frame. */
1636 + if (!page_out (f->page))
1638 + lock_release (&f->lock);
1646 + lock_release (&scan_lock);
1651 +/* Tries really hard to allocate and lock a frame for PAGE.
1652 + Returns the frame if successful, false on failure. */
1654 +frame_alloc_and_lock (struct page *page)
1658 + for (try = 0; try < 3; try++)
1660 + struct frame *f = try_frame_alloc_and_lock (page);
1663 + ASSERT (lock_held_by_current_thread (&f->lock));
1666 + timer_msleep (1000);
1672 +/* Locks P's frame into memory, if it has one.
1673 + Upon return, p->frame will not change until P is unlocked. */
1675 +frame_lock (struct page *p)
1677 + /* A frame can be asynchronously removed, but never inserted. */
1678 + struct frame *f = p->frame;
1681 + lock_acquire (&f->lock);
1682 + if (f != p->frame)
1684 + lock_release (&f->lock);
1685 + ASSERT (p->frame == NULL);
1690 +/* Releases frame F for use by another page.
1691 + F must be locked for use by the current process.
1692 + Any data in F is lost. */
1694 +frame_free (struct frame *f)
1696 + ASSERT (lock_held_by_current_thread (&f->lock));
1699 + lock_release (&f->lock);
1702 +/* Unlocks frame F, allowing it to be evicted.
1703 + F must be locked for use by the current process. */
1705 +frame_unlock (struct frame *f)
1707 + ASSERT (lock_held_by_current_thread (&f->lock));
1708 + lock_release (&f->lock);
1710 diff --git a/src/vm/frame.h b/src/vm/frame.h
1711 new file mode 100644
1712 index 0000000..496f623
1714 +++ b/src/vm/frame.h
1719 +#include <stdbool.h>
1720 +#include "threads/synch.h"
1722 +/* A physical frame. */
1725 + struct lock lock; /* Prevent simultaneous access. */
1726 + void *base; /* Kernel virtual base address. */
1727 + struct page *page; /* Mapped process page, if any. */
1730 +void frame_init (void);
1732 +struct frame *frame_alloc_and_lock (struct page *);
1733 +void frame_lock (struct page *);
1735 +void frame_free (struct frame *);
1736 +void frame_unlock (struct frame *);
1738 +#endif /* vm/frame.h */
1739 diff --git a/src/vm/page.c b/src/vm/page.c
1740 new file mode 100644
1741 index 0000000..f08bcf8
1745 +#include "vm/page.h"
1747 +#include <string.h>
1748 +#include "vm/frame.h"
1749 +#include "vm/swap.h"
1750 +#include "filesys/file.h"
1751 +#include "threads/malloc.h"
1752 +#include "threads/thread.h"
1753 +#include "userprog/pagedir.h"
1754 +#include "threads/vaddr.h"
1756 +/* Maximum size of process stack, in bytes. */
1757 +#define STACK_MAX (1024 * 1024)
1759 +/* Destroys a page, which must be in the current process's
1760 + page table. Used as a callback for hash_destroy(). */
1762 +destroy_page (struct hash_elem *p_, void *aux UNUSED)
1764 + struct page *p = hash_entry (p_, struct page, hash_elem);
1767 + frame_free (p->frame);
1771 +/* Destroys the current process's page table. */
1775 + struct hash *h = thread_current ()->pages;
1777 + hash_destroy (h, destroy_page);
1780 +/* Returns the page containing the given virtual ADDRESS,
1781 + or a null pointer if no such page exists.
1782 + Allocates stack pages as necessary. */
1783 +static struct page *
1784 +page_for_addr (const void *address)
1786 + if (address < PHYS_BASE)
1789 + struct hash_elem *e;
1791 + /* Find existing page. */
1792 + p.addr = (void *) pg_round_down (address);
1793 + e = hash_find (thread_current ()->pages, &p.hash_elem);
1795 + return hash_entry (e, struct page, hash_elem);
1797 + /* No page. Expand stack? */
1798 + if (address >= PHYS_BASE - STACK_MAX
1799 + && address >= thread_current ()->user_esp - 32)
1800 + return page_allocate ((void *) address, false);
1805 +/* Locks a frame for page P and pages it in.
1806 + Returns true if successful, false on failure. */
1808 +do_page_in (struct page *p)
1810 + /* Get a frame for the page. */
1811 + p->frame = frame_alloc_and_lock (p);
1812 + if (p->frame == NULL)
1815 + /* Copy data into the frame. */
1816 + if (p->sector != (block_sector_t) -1)
1818 + /* Get data from swap. */
1821 + else if (p->file != NULL)
1823 + /* Get data from file. */
1824 + off_t read_bytes = file_read_at (p->file, p->frame->base,
1825 + p->file_bytes, p->file_offset);
1826 + off_t zero_bytes = PGSIZE - read_bytes;
1827 + memset (p->frame->base + read_bytes, 0, zero_bytes);
1828 + if (read_bytes != p->file_bytes)
1829 + printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
1830 + read_bytes, p->file_bytes);
1834 + /* Provide all-zero page. */
1835 + memset (p->frame->base, 0, PGSIZE);
1841 +/* Faults in the page containing FAULT_ADDR.
1842 + Returns true if successful, false on failure. */
1844 +page_in (void *fault_addr)
1849 + /* Can't handle page faults without a hash table. */
1850 + if (thread_current ()->pages == NULL)
1853 + p = page_for_addr (fault_addr);
1858 + if (p->frame == NULL)
1860 + if (!do_page_in (p))
1863 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1865 + /* Install frame into page table. */
1866 + success = pagedir_set_page (thread_current ()->pagedir, p->addr,
1867 + p->frame->base, !p->read_only);
1869 + /* Release frame. */
1870 + frame_unlock (p->frame);
1876 + P must have a locked frame.
1877 + Return true if successful, false on failure. */
1879 +page_out (struct page *p)
1884 + ASSERT (p->frame != NULL);
1885 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1887 + /* Mark page not present in page table, forcing accesses by the
1888 + process to fault. This must happen before checking the
1889 + dirty bit, to prevent a race with the process dirtying the
1891 + pagedir_clear_page (p->thread->pagedir, p->addr);
1893 + /* Has the frame been modified? */
1894 + dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
1896 + /* Write frame contents to disk if necessary. */
1897 + if (p->file != NULL)
1902 + ok = swap_out (p);
1904 + ok = file_write_at (p->file, p->frame->base, p->file_bytes,
1905 + p->file_offset) == p->file_bytes;
1911 + ok = swap_out (p);
1914 + //memset (p->frame->base, 0xcc, PGSIZE);
1920 +/* Returns true if page P's data has been accessed recently,
1922 + P must have a frame locked into memory. */
1924 +page_accessed_recently (struct page *p)
1926 + bool was_accessed;
1928 + ASSERT (p->frame != NULL);
1929 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1931 + was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
1933 + pagedir_set_accessed (p->thread->pagedir, p->addr, false);
1934 + return was_accessed;
1937 +/* Adds a mapping for user virtual address VADDR to the page hash
1938 + table. Fails if VADDR is already mapped or if memory
1939 + allocation fails. */
1941 +page_allocate (void *vaddr, bool read_only)
1943 + struct thread *t = thread_current ();
1944 + struct page *p = malloc (sizeof *p);
1947 + p->addr = pg_round_down (vaddr);
1949 + p->read_only = read_only;
1950 + p->private = !read_only;
1954 + p->sector = (block_sector_t) -1;
1957 + p->file_offset = 0;
1958 + p->file_bytes = 0;
1960 + p->thread = thread_current ();
1962 + if (hash_insert (t->pages, &p->hash_elem) != NULL)
1964 + /* Already mapped. */
1972 +/* Evicts the page containing address VADDR
1973 + and removes it from the page table. */
1975 +page_deallocate (void *vaddr)
1977 + struct page *p = page_for_addr (vaddr);
1978 + ASSERT (p != NULL);
1982 + struct frame *f = p->frame;
1983 + if (p->file && !p->private)
1987 + hash_delete (thread_current ()->pages, &p->hash_elem);
1991 +/* Returns a hash value for the page that E refers to. */
1993 +page_hash (const struct hash_elem *e, void *aux UNUSED)
1995 + const struct page *p = hash_entry (e, struct page, hash_elem);
1996 + return ((uintptr_t) p->addr) >> PGBITS;
1999 +/* Returns true if page A precedes page B. */
2001 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2004 + const struct page *a = hash_entry (a_, struct page, hash_elem);
2005 + const struct page *b = hash_entry (b_, struct page, hash_elem);
2007 + return a->addr < b->addr;
2010 +/* Tries to lock the page containing ADDR into physical memory.
2011 + If WILL_WRITE is true, the page must be writeable;
2012 + otherwise it may be read-only.
2013 + Returns true if successful, false on failure. */
2015 +page_lock (const void *addr, bool will_write)
2017 + struct page *p = page_for_addr (addr);
2018 + if (p == NULL || (p->read_only && will_write))
2022 + if (p->frame == NULL)
2023 + return (do_page_in (p)
2024 + && pagedir_set_page (thread_current ()->pagedir, p->addr,
2025 + p->frame->base, !p->read_only));
2030 +/* Unlocks a page locked with page_lock(). */
2032 +page_unlock (const void *addr)
2034 + struct page *p = page_for_addr (addr);
2035 + ASSERT (p != NULL);
2036 + frame_unlock (p->frame);
2038 diff --git a/src/vm/page.h b/src/vm/page.h
2039 new file mode 100644
2040 index 0000000..b71b9da
2048 +#include "devices/block.h"
2049 +#include "filesys/off_t.h"
2050 +#include "threads/synch.h"
2052 +/* Virtual page. */
2055 + /* Immutable members. */
2056 + void *addr; /* User virtual address. */
2057 + bool read_only; /* Read-only page? */
2058 + struct thread *thread; /* Owning thread. */
2060 + /* Accessed only in owning process context. */
2061 + struct hash_elem hash_elem; /* struct thread `pages' hash element. */
2063 + /* Set only in owning process context with frame->frame_lock held.
2064 + Cleared only with scan_lock and frame->frame_lock held. */
2065 + struct frame *frame; /* Page frame. */
2067 + /* Swap information, protected by frame->frame_lock. */
2068 + block_sector_t sector; /* Starting sector of swap area, or -1. */
2070 + /* Memory-mapped file information, protected by frame->frame_lock. */
2071 + bool private; /* False to write back to file,
2072 + true to write back to swap. */
2073 + struct file *file; /* File. */
2074 + off_t file_offset; /* Offset in file. */
2075 + off_t file_bytes; /* Bytes to read/write, 1...PGSIZE. */
2078 +void page_exit (void);
2080 +struct page *page_allocate (void *, bool read_only);
2081 +void page_deallocate (void *vaddr);
2083 +bool page_in (void *fault_addr);
2084 +bool page_out (struct page *);
2085 +bool page_accessed_recently (struct page *);
2087 +bool page_lock (const void *, bool will_write);
2088 +void page_unlock (const void *);
2090 +hash_hash_func page_hash;
2091 +hash_less_func page_less;
2093 +#endif /* vm/page.h */
2094 diff --git a/src/vm/swap.c b/src/vm/swap.c
2095 new file mode 100644
2096 index 0000000..76fcf71
2100 +#include "vm/swap.h"
2101 +#include <bitmap.h>
2104 +#include "vm/frame.h"
2105 +#include "vm/page.h"
2106 +#include "threads/synch.h"
2107 +#include "threads/vaddr.h"
2109 +/* The swap device. */
2110 +static struct block *swap_device;
2112 +/* Used swap pages. */
2113 +static struct bitmap *swap_bitmap;
2115 +/* Protects swap_bitmap. */
2116 +static struct lock swap_lock;
2118 +/* Number of sectors per page. */
2119 +#define PAGE_SECTORS (PGSIZE / BLOCK_SECTOR_SIZE)
2121 +/* Sets up swap. */
2125 + swap_device = block_get_role (BLOCK_SWAP);
2126 + if (swap_device == NULL)
2128 + printf ("no swap device--swap disabled\n");
2129 + swap_bitmap = bitmap_create (0);
2132 + swap_bitmap = bitmap_create (block_size (swap_device)
2134 + if (swap_bitmap == NULL)
2135 + PANIC ("couldn't create swap bitmap");
2136 + lock_init (&swap_lock);
2139 +/* Swaps in page P, which must have a locked frame
2140 + (and be swapped out). */
2142 +swap_in (struct page *p)
2146 + ASSERT (p->frame != NULL);
2147 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
2148 + ASSERT (p->sector != (block_sector_t) -1);
2150 + for (i = 0; i < PAGE_SECTORS; i++)
2151 + block_read (swap_device, p->sector + i,
2152 + p->frame->base + i * BLOCK_SECTOR_SIZE);
2153 + bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
2154 + p->sector = (block_sector_t) -1;
2157 +/* Swaps out page P, which must have a locked frame. */
2159 +swap_out (struct page *p)
2164 + ASSERT (p->frame != NULL);
2165 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
2167 + lock_acquire (&swap_lock);
2168 + slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
2169 + lock_release (&swap_lock);
2170 + if (slot == BITMAP_ERROR)
2173 + p->sector = slot * PAGE_SECTORS;
2174 + for (i = 0; i < PAGE_SECTORS; i++)
2175 + block_write (swap_device, p->sector + i,
2176 + p->frame->base + i * BLOCK_SECTOR_SIZE);
2178 + p->private = false;
2180 + p->file_offset = 0;
2181 + p->file_bytes = 0;
2185 diff --git a/src/vm/swap.h b/src/vm/swap.h
2186 new file mode 100644
2187 index 0000000..34d5d51
2192 +#define VM_SWAP_H 1
2194 +#include <stdbool.h>
2197 +void swap_init (void);
2198 +void swap_in (struct page *);
2199 +bool swap_out (struct page *);
2201 +#endif /* vm/swap.h */