1 Index: src/Makefile.build
2 diff -u src/Makefile.build~ src/Makefile.build
3 --- src/Makefile.build~ 2005-06-18 20:20:47.000000000 -0700
4 +++ src/Makefile.build 2006-05-16 13:44:56.000000000 -0700
5 @@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c # GDT in
6 userprog_SRC += userprog/tss.c # TSS management.
8 # No virtual memory code yet.
9 -#vm_SRC = vm/filename.c # Some file.
15 filesys_SRC = filesys/filesys.c # Filesystem core.
16 Index: src/devices/timer.c
17 diff -u src/devices/timer.c~ src/devices/timer.c
18 --- src/devices/timer.c~ 2005-07-06 13:45:36.000000000 -0700
19 +++ src/devices/timer.c 2006-05-16 13:44:56.000000000 -0700
20 @@ -23,6 +23,9 @@ static volatile int64_t ticks;
21 Initialized by timer_calibrate(). */
22 static unsigned loops_per_tick;
24 +/* Threads waiting in timer_sleep(). */
25 +static struct list wait_list;
27 static intr_handler_func timer_interrupt;
28 static bool too_many_loops (unsigned loops);
29 static void busy_wait (int64_t loops);
30 @@ -43,6 +46,8 @@ timer_init (void)
31 outb (0x40, count >> 8);
33 intr_register_ext (0x20, timer_interrupt, "8254 Timer");
35 + list_init (&wait_list);
38 /* Calibrates loops_per_tick, used to implement brief delays. */
39 @@ -87,15 +92,36 @@ timer_elapsed (int64_t then)
40 return timer_ticks () - then;
43 +/* Compares two threads based on their wake-up times. */
45 +compare_threads_by_wakeup_time (const struct list_elem *a_,
46 + const struct list_elem *b_,
49 + const struct thread *a = list_entry (a_, struct thread, timer_elem);
50 + const struct thread *b = list_entry (b_, struct thread, timer_elem);
52 + return a->wakeup_time < b->wakeup_time;
55 /* Suspends execution for approximately TICKS timer ticks. */
57 timer_sleep (int64_t ticks)
59 - int64_t start = timer_ticks ();
60 + struct thread *t = thread_current ();
62 + /* Schedule our wake-up time. */
63 + t->wakeup_time = timer_ticks () + ticks;
65 + /* Atomically insert the current thread into the wait list. */
66 ASSERT (intr_get_level () == INTR_ON);
67 - while (timer_elapsed (start) < ticks)
70 + list_insert_ordered (&wait_list, &t->timer_elem,
71 + compare_threads_by_wakeup_time, NULL);
75 + sema_down (&t->timer_sema);
78 /* Suspends execution for approximately MS milliseconds. */
79 @@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
84 + while (!list_empty (&wait_list))
86 + struct thread *t = list_entry (list_front (&wait_list),
87 + struct thread, timer_elem);
88 + if (ticks < t->wakeup_time)
90 + sema_up (&t->timer_sema);
91 + list_pop_front (&wait_list);
95 /* Returns true if LOOPS iterations waits for more than one timer
96 Index: src/threads/init.c
97 diff -u src/threads/init.c~ src/threads/init.c
98 --- src/threads/init.c~ 2006-04-25 11:35:56.000000000 -0700
99 +++ src/threads/init.c 2006-05-16 13:44:56.000000000 -0700
101 #include "filesys/filesys.h"
102 #include "filesys/fsutil.h"
104 +#include "vm/frame.h"
105 +#include "vm/swap.h"
107 /* Amount of physical memory, in 4 kB pages. */
109 @@ -124,6 +126,9 @@ main (void)
110 filesys_init (format_filesys);
116 printf ("Boot complete.\n");
118 /* Run actions specified on kernel command line. */
119 Index: src/threads/interrupt.c
120 diff -u src/threads/interrupt.c~ src/threads/interrupt.c
121 --- src/threads/interrupt.c~ 2006-04-25 11:35:56.000000000 -0700
122 +++ src/threads/interrupt.c 2006-05-16 13:44:56.000000000 -0700
123 @@ -354,6 +354,8 @@ intr_handler (struct intr_frame *frame)
124 in_external_intr = true;
125 yield_on_return = false;
128 + thread_current ()->user_esp = frame->esp;
130 /* Invoke the interrupt's handler.
131 If there is no handler, invoke the unexpected interrupt
132 Index: src/threads/thread.c
133 diff -u src/threads/thread.c~ src/threads/thread.c
134 --- src/threads/thread.c~ 2006-04-25 11:35:57.000000000 -0700
135 +++ src/threads/thread.c 2006-05-16 13:44:56.000000000 -0700
137 #include "threads/vaddr.h"
139 #include "userprog/process.h"
140 +#include "userprog/syscall.h"
143 /* Random value for struct thread's `magic' member.
144 @@ -55,7 +56,8 @@ static void kernel_thread (thread_func *
145 static void idle (void *aux UNUSED);
146 static struct thread *running_thread (void);
147 static struct thread *next_thread_to_run (void);
148 -static void init_thread (struct thread *, const char *name, int priority);
149 +static void init_thread (struct thread *, const char *name, int priority,
151 static bool is_thread (struct thread *) UNUSED;
152 static void *alloc_frame (struct thread *, size_t size);
153 static void schedule (void);
154 @@ -82,9 +84,8 @@ thread_init (void)
156 /* Set up a thread structure for the running thread. */
157 initial_thread = running_thread ();
158 - init_thread (initial_thread, "main", PRI_DEFAULT);
159 + init_thread (initial_thread, "main", PRI_DEFAULT, 0);
160 initial_thread->status = THREAD_RUNNING;
161 - initial_thread->tid = allocate_tid ();
164 /* Starts preemptive thread scheduling by enabling interrupts.
165 @@ -159,8 +160,8 @@ thread_create (const char *name, int pri
168 /* Initialize thread. */
169 - init_thread (t, name, priority);
170 - tid = t->tid = allocate_tid ();
171 + init_thread (t, name, priority, allocate_tid ());
174 /* Stack frame for kernel_thread(). */
175 kf = alloc_frame (t, sizeof *kf);
176 @@ -253,16 +254,19 @@ thread_tid (void)
180 + struct thread *t = thread_current ();
182 ASSERT (!intr_context ());
190 /* Just set our status to dying and schedule another process.
191 We will be destroyed during the call to schedule_tail(). */
193 - thread_current ()->status = THREAD_DYING;
194 + t->status = THREAD_DYING;
198 @@ -406,17 +410,28 @@ is_thread (struct thread *t)
199 /* Does basic initialization of T as a blocked thread named
202 -init_thread (struct thread *t, const char *name, int priority)
203 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
206 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
207 ASSERT (name != NULL);
209 memset (t, 0, sizeof *t);
211 t->status = THREAD_BLOCKED;
212 strlcpy (t->name, name, sizeof t->name);
213 t->stack = (uint8_t *) t + PGSIZE;
214 t->priority = priority;
216 + t->wait_status = NULL;
217 + list_init (&t->children);
218 + sema_init (&t->timer_sema, 0);
221 + t->bin_file = NULL;
222 + list_init (&t->fds);
223 + list_init (&t->mappings);
224 + t->next_handle = 2;
225 t->magic = THREAD_MAGIC;
228 Index: src/threads/thread.h
229 diff -u src/threads/thread.h~ src/threads/thread.h
230 --- src/threads/thread.h~ 2006-04-13 13:53:34.000000000 -0700
231 +++ src/threads/thread.h 2006-05-16 13:44:56.000000000 -0700
233 #define THREADS_THREAD_H
239 +#include "threads/synch.h"
241 /* States in a thread's life cycle. */
243 @@ -89,18 +91,49 @@ struct thread
244 uint8_t *stack; /* Saved stack pointer. */
245 int priority; /* Priority. */
247 + /* Owned by process.c. */
248 + int exit_code; /* Exit code. */
249 + struct wait_status *wait_status; /* This process's completion status. */
250 + struct list children; /* Completion status of children. */
252 /* Shared between thread.c and synch.c. */
253 struct list_elem elem; /* List element. */
257 + int64_t wakeup_time; /* Time to wake this thread up. */
258 + struct list_elem timer_elem; /* Element in timer_wait_list. */
259 + struct semaphore timer_sema; /* Semaphore. */
261 /* Owned by userprog/process.c. */
262 uint32_t *pagedir; /* Page directory. */
264 + struct hash *pages; /* Page table. */
265 + struct file *bin_file; /* The binary executable. */
267 + /* Owned by syscall.c. */
268 + struct list fds; /* List of file descriptors. */
269 + struct list mappings; /* Memory-mapped files. */
270 + int next_handle; /* Next handle value. */
271 + void *user_esp; /* User's stack pointer. */
273 /* Owned by thread.c. */
274 unsigned magic; /* Detects stack overflow. */
277 +/* Tracks the completion of a process.
278 + Reference held by both the parent, in its `children' list,
279 + and by the child, in its `wait_status' pointer. */
282 + struct list_elem elem; /* `children' list element. */
283 + struct lock lock; /* Protects ref_cnt. */
284 + int ref_cnt; /* 2=child and parent both alive,
285 + 1=either child or parent alive,
286 + 0=child and parent both dead. */
287 + tid_t tid; /* Child thread id. */
288 + int exit_code; /* Child exit code, if dead. */
289 + struct semaphore dead; /* 1=child alive, 0=child dead. */
292 void thread_init (void);
293 void thread_start (void);
295 Index: src/userprog/exception.c
296 diff -u src/userprog/exception.c~ src/userprog/exception.c
297 --- src/userprog/exception.c~ 2006-01-29 13:32:56.000000000 -0800
298 +++ src/userprog/exception.c 2006-05-16 13:44:56.000000000 -0700
300 #include "userprog/gdt.h"
301 #include "threads/interrupt.h"
302 #include "threads/thread.h"
303 +#include "vm/page.h"
305 /* Number of page faults processed. */
306 static long long page_fault_cnt;
307 @@ -148,9 +149,14 @@ page_fault (struct intr_frame *f)
308 write = (f->error_code & PF_W) != 0;
309 user = (f->error_code & PF_U) != 0;
311 - /* To implement virtual memory, delete the rest of the function
312 - body, and replace it with code that brings in the page to
313 - which fault_addr refers. */
314 + /* Allow the pager to try to handle it. */
315 + if (user && not_present)
317 + if (!page_in (fault_addr))
322 printf ("Page fault at %p: %s error %s page in %s context.\n",
324 not_present ? "not present" : "rights violation",
325 Index: src/userprog/pagedir.c
326 diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c
327 --- src/userprog/pagedir.c~ 2006-04-25 11:35:58.000000000 -0700
328 +++ src/userprog/pagedir.c 2006-05-16 13:44:56.000000000 -0700
329 @@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd)
330 ASSERT (pd != base_page_dir);
331 for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
334 - uint32_t *pt = pde_get_pt (*pde);
337 - for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
339 - palloc_free_page (pte_get_page (*pte));
340 - palloc_free_page (pt);
342 + palloc_free_page (pde_get_pt (*pde));
343 palloc_free_page (pd);
346 Index: src/userprog/process.c
347 diff -u src/userprog/process.c~ src/userprog/process.c
348 --- src/userprog/process.c~ 2006-04-25 11:35:58.000000000 -0700
349 +++ src/userprog/process.c 2006-05-16 13:44:56.000000000 -0700
351 #include "threads/flags.h"
352 #include "threads/init.h"
353 #include "threads/interrupt.h"
354 +#include "threads/malloc.h"
355 #include "threads/palloc.h"
356 #include "threads/thread.h"
357 #include "threads/vaddr.h"
358 +#include "vm/page.h"
359 +#include "vm/frame.h"
361 static thread_func execute_thread NO_RETURN;
362 -static bool load (const char *cmdline, void (**eip) (void), void **esp);
363 +static bool load (const char *cmd_line, void (**eip) (void), void **esp);
365 +/* Data structure shared between process_execute() in the
366 + invoking thread and execute_thread() in the newly invoked
370 + const char *filename; /* Program to load. */
371 + struct semaphore load_done; /* "Up"ed when loading complete. */
372 + struct wait_status *wait_status; /* Child process. */
373 + bool success; /* Program successfully loaded? */
376 /* Starts a new thread running a user program loaded from
377 FILENAME. The new thread may be scheduled (and may even exit)
378 @@ -28,29 +42,37 @@ static bool load (const char *cmdline, v
380 process_execute (const char *filename)
383 + struct exec_info exec;
384 + char thread_name[16];
388 - /* Make a copy of FILENAME.
389 - Otherwise there's a race between the caller and load(). */
390 - fn_copy = palloc_get_page (0);
391 - if (fn_copy == NULL)
393 - strlcpy (fn_copy, filename, PGSIZE);
394 + /* Initialize exec_info. */
395 + exec.filename = filename;
396 + sema_init (&exec.load_done, 0);
398 /* Create a new thread to execute FILENAME. */
399 - tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy);
400 - if (tid == TID_ERROR)
401 - palloc_free_page (fn_copy);
402 + strlcpy (thread_name, filename, sizeof thread_name);
403 + strtok_r (thread_name, " ", &save_ptr);
404 + tid = thread_create (thread_name, PRI_DEFAULT, execute_thread, &exec);
405 + if (tid != TID_ERROR)
407 + sema_down (&exec.load_done);
409 + list_push_back (&thread_current ()->children, &exec.wait_status->elem);
417 /* A thread function that loads a user process and starts it
420 -execute_thread (void *filename_)
421 +execute_thread (void *exec_)
423 - char *filename = filename_;
424 + struct exec_info *exec = exec_;
425 struct intr_frame if_;
428 @@ -59,10 +81,28 @@ execute_thread (void *filename_)
429 if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
431 if_.eflags = FLAG_IF | FLAG_MBS;
432 - success = load (filename, &if_.eip, &if_.esp);
433 + success = load (exec->filename, &if_.eip, &if_.esp);
435 + /* Allocate wait_status. */
438 + exec->wait_status = thread_current ()->wait_status
439 + = malloc (sizeof *exec->wait_status);
440 + success = exec->wait_status != NULL;
443 - /* If load failed, quit. */
444 - palloc_free_page (filename);
445 + /* Initialize wait_status. */
448 + lock_init (&exec->wait_status->lock);
449 + exec->wait_status->ref_cnt = 2;
450 + exec->wait_status->tid = thread_current ()->tid;
451 + sema_init (&exec->wait_status->dead, 0);
454 + /* Notify parent thread and clean up. */
455 + exec->success = success;
456 + sema_up (&exec->load_done);
460 @@ -76,18 +116,47 @@ execute_thread (void *filename_)
464 +/* Releases one reference to CS and, if it is now unreferenced,
467 +release_child (struct wait_status *cs)
471 + lock_acquire (&cs->lock);
472 + new_ref_cnt = --cs->ref_cnt;
473 + lock_release (&cs->lock);
475 + if (new_ref_cnt == 0)
479 /* Waits for thread TID to die and returns its exit status. If
480 it was terminated by the kernel (i.e. killed due to an
481 exception), returns -1. If TID is invalid or if it was not a
482 child of the calling process, or if process_wait() has already
483 been successfully called for the given TID, returns -1
484 - immediately, without waiting.
486 - This function will be implemented in problem 2-2. For now, it
488 + immediately, without waiting. */
490 -process_wait (tid_t child_tid UNUSED)
491 +process_wait (tid_t child_tid)
493 + struct thread *cur = thread_current ();
494 + struct list_elem *e;
496 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
499 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
500 + if (cs->tid == child_tid)
504 + sema_down (&cs->dead);
505 + exit_code = cs->exit_code;
506 + release_child (cs);
513 @@ -96,8 +165,35 @@ void
516 struct thread *cur = thread_current ();
517 + struct list_elem *e, *next;
520 + printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
522 + /* Notify parent that we're dead. */
523 + if (cur->wait_status != NULL)
525 + struct wait_status *cs = cur->wait_status;
526 + cs->exit_code = cur->exit_code;
527 + sema_up (&cs->dead);
528 + release_child (cs);
531 + /* Free entries of children list. */
532 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
535 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
536 + next = list_remove (e);
537 + release_child (cs);
540 + /* Destroy the page hash table. */
543 + /* Close executable (and allow writes). */
544 + file_close (cur->bin_file);
546 /* Destroy the current process's page directory and switch back
547 to the kernel-only page directory. */
549 @@ -194,7 +290,7 @@ struct Elf32_Phdr
550 #define PF_W 2 /* Writable. */
551 #define PF_R 4 /* Readable. */
553 -static bool setup_stack (void **esp);
554 +static bool setup_stack (const char *cmd_line, void **esp);
555 static bool validate_segment (const struct Elf32_Phdr *, struct file *);
556 static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
557 uint32_t read_bytes, uint32_t zero_bytes,
558 @@ -205,13 +301,15 @@ static bool load_segment (struct file *f
559 and its initial stack pointer into *ESP.
560 Returns true if successful, false otherwise. */
562 -load (const char *filename, void (**eip) (void), void **esp)
563 +load (const char *cmd_line, void (**eip) (void), void **esp)
565 struct thread *t = thread_current ();
566 + char filename[NAME_MAX + 2];
567 struct Elf32_Ehdr ehdr;
568 struct file *file = NULL;
570 bool success = false;
574 /* Allocate and activate page directory. */
575 @@ -220,13 +318,28 @@ load (const char *filename, void (**eip)
579 + /* Create page hash table. */
580 + t->pages = malloc (sizeof *t->pages);
581 + if (t->pages == NULL)
583 + hash_init (t->pages, page_hash, page_less, NULL);
585 + /* Extract filename from command line. */
586 + while (*cmd_line == ' ')
588 + strlcpy (filename, cmd_line, sizeof filename);
589 + cp = strchr (filename, ' ');
593 /* Open executable file. */
594 - file = filesys_open (filename);
595 + t->bin_file = file = filesys_open (filename);
598 printf ("load: %s: open failed\n", filename);
601 + file_deny_write (t->bin_file);
603 /* Read and verify executable header. */
604 if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
605 @@ -301,7 +414,7 @@ load (const char *filename, void (**eip)
609 - if (!setup_stack (esp))
610 + if (!setup_stack (cmd_line, esp))
614 @@ -311,14 +424,11 @@ load (const char *filename, void (**eip)
617 /* We arrive here whether the load is successful or not. */
622 /* load() helpers. */
624 -static bool install_page (void *upage, void *kpage, bool writable);
626 /* Checks whether PHDR describes a valid, loadable segment in
627 FILE and returns true if so, false otherwise. */
629 @@ -387,79 +497,127 @@ load_segment (struct file *file, off_t o
630 ASSERT (pg_ofs (upage) == 0);
631 ASSERT (ofs % PGSIZE == 0);
633 - file_seek (file, ofs);
634 while (read_bytes > 0 || zero_bytes > 0)
636 - /* Calculate how to fill this page.
637 - We will read PAGE_READ_BYTES bytes from FILE
638 - and zero the final PAGE_ZERO_BYTES bytes. */
639 size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
640 size_t page_zero_bytes = PGSIZE - page_read_bytes;
642 - /* Get a page of memory. */
643 - uint8_t *kpage = palloc_get_page (PAL_USER);
645 + struct page *p = page_allocate (upage, !writable);
649 - /* Load this page. */
650 - if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
652 - palloc_free_page (kpage);
655 - memset (kpage + page_read_bytes, 0, page_zero_bytes);
657 - /* Add the page to the process's address space. */
658 - if (!install_page (upage, kpage, writable))
659 + if (page_read_bytes > 0)
661 - palloc_free_page (kpage);
664 + p->file_offset = ofs;
665 + p->file_bytes = page_read_bytes;
669 read_bytes -= page_read_bytes;
670 zero_bytes -= page_zero_bytes;
671 + ofs += page_read_bytes;
677 -/* Create a minimal stack by mapping a zeroed page at the top of
678 - user virtual memory. */
679 +/* Reverse the order of the ARGC pointers to char in ARGV. */
681 +reverse (int argc, char **argv)
683 + for (; argc > 1; argc -= 2, argv++)
685 + char *tmp = argv[0];
686 + argv[0] = argv[argc - 1];
687 + argv[argc - 1] = tmp;
691 +/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
692 + page-relative stack pointer is *OFS, and then adjusts *OFS
693 + appropriately. The bytes pushed are rounded to a 32-bit
696 + If successful, returns a pointer to the newly pushed object.
697 + On failure, returns a null pointer. */
699 +push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size)
701 + size_t padsize = ROUND_UP (size, sizeof (uint32_t));
702 + if (*ofs < padsize)
706 + memcpy (kpage + *ofs + (padsize - size), buf, size);
707 + return kpage + *ofs + (padsize - size);
710 +/* Sets up command line arguments in KPAGE, which will be mapped
711 + to UPAGE in user space. The command line arguments are taken
712 + from CMD_LINE, separated by spaces. Sets *ESP to the initial
713 + stack pointer for the process. */
715 -setup_stack (void **esp)
716 +init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
720 - bool success = false;
721 + size_t ofs = PGSIZE;
722 + char *const null = NULL;
723 + char *cmd_line_copy;
724 + char *karg, *saveptr;
728 + /* Push command line string. */
729 + cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1);
730 + if (cmd_line_copy == NULL)
733 + if (push (kpage, &ofs, &null, sizeof null) == NULL)
736 - kpage = palloc_get_page (PAL_USER | PAL_ZERO);
738 + /* Parse command line into arguments
739 + and push them in reverse order. */
741 + for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL;
742 + karg = strtok_r (NULL, " ", &saveptr))
744 - success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
748 - palloc_free_page (kpage);
749 + void *uarg = upage + (karg - (char *) kpage);
750 + if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
756 + /* Reverse the order of the command line arguments. */
757 + argv = (char **) (upage + ofs);
758 + reverse (argc, (char **) (kpage + ofs));
760 + /* Push argv, argc, "return address". */
761 + if (push (kpage, &ofs, &argv, sizeof argv) == NULL
762 + || push (kpage, &ofs, &argc, sizeof argc) == NULL
763 + || push (kpage, &ofs, &null, sizeof null) == NULL)
766 + /* Set initial stack pointer. */
767 + *esp = upage + ofs;
771 -/* Adds a mapping from user virtual address UPAGE to kernel
772 - virtual address KPAGE to the page table.
773 - If WRITABLE is true, the user process may modify the page;
774 - otherwise, it is read-only.
775 - UPAGE must not already be mapped.
776 - KPAGE should probably be a page obtained from the user pool
777 - with palloc_get_page().
778 - Returns true on success, false if UPAGE is already mapped or
779 - if memory allocation fails. */
780 +/* Create a minimal stack for T by mapping a page at the
781 + top of user virtual memory. Fills in the page using CMD_LINE
782 + and sets *ESP to the stack pointer. */
784 -install_page (void *upage, void *kpage, bool writable)
785 +setup_stack (const char *cmd_line, void **esp)
787 - struct thread *t = thread_current ();
789 - /* Verify that there's not already a page at that virtual
790 - address, then map our page there. */
791 - return (pagedir_get_page (t->pagedir, upage) == NULL
792 - && pagedir_set_page (t->pagedir, upage, kpage, writable));
793 + struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
796 + page->frame = frame_alloc_and_lock (page);
797 + if (page->frame != NULL)
800 + page->read_only = false;
801 + page->private = false;
802 + ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
803 + frame_unlock (page->frame);
809 Index: src/userprog/syscall.c
810 diff -u src/userprog/syscall.c~ src/userprog/syscall.c
811 --- src/userprog/syscall.c~ 2005-06-18 20:21:21.000000000 -0700
812 +++ src/userprog/syscall.c 2006-05-16 14:17:02.000000000 -0700
814 #include "userprog/syscall.h"
817 #include <syscall-nr.h>
818 +#include "userprog/process.h"
819 +#include "userprog/pagedir.h"
820 +#include "devices/kbd.h"
821 +#include "filesys/directory.h"
822 +#include "filesys/filesys.h"
823 +#include "filesys/file.h"
824 +#include "threads/init.h"
825 #include "threads/interrupt.h"
826 +#include "threads/malloc.h"
827 +#include "threads/palloc.h"
828 #include "threads/thread.h"
830 +#include "threads/vaddr.h"
831 +#include "vm/page.h"
834 +static int sys_halt (void);
835 +static int sys_exit (int status);
836 +static int sys_exec (const char *ufile);
837 +static int sys_wait (tid_t);
838 +static int sys_create (const char *ufile, unsigned initial_size);
839 +static int sys_remove (const char *ufile);
840 +static int sys_open (const char *ufile);
841 +static int sys_filesize (int handle);
842 +static int sys_read (int handle, void *udst_, unsigned size);
843 +static int sys_write (int handle, void *usrc_, unsigned size);
844 +static int sys_seek (int handle, unsigned position);
845 +static int sys_tell (int handle);
846 +static int sys_close (int handle);
847 +static int sys_mmap (int handle, void *addr);
848 +static int sys_munmap (int mapping);
850 static void syscall_handler (struct intr_frame *);
851 +static void copy_in (void *, const void *, size_t);
853 +static struct lock fs_lock;
858 intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
859 + lock_init (&fs_lock);
862 +/* System call handler. */
864 +syscall_handler (struct intr_frame *f)
866 + typedef int syscall_function (int, int, int);
868 + /* A system call. */
871 + size_t arg_cnt; /* Number of arguments. */
872 + syscall_function *func; /* Implementation. */
875 + /* Table of system calls. */
876 + static const struct syscall syscall_table[] =
878 + {0, (syscall_function *) sys_halt},
879 + {1, (syscall_function *) sys_exit},
880 + {1, (syscall_function *) sys_exec},
881 + {1, (syscall_function *) sys_wait},
882 + {2, (syscall_function *) sys_create},
883 + {1, (syscall_function *) sys_remove},
884 + {1, (syscall_function *) sys_open},
885 + {1, (syscall_function *) sys_filesize},
886 + {3, (syscall_function *) sys_read},
887 + {3, (syscall_function *) sys_write},
888 + {2, (syscall_function *) sys_seek},
889 + {1, (syscall_function *) sys_tell},
890 + {1, (syscall_function *) sys_close},
891 + {2, (syscall_function *) sys_mmap},
892 + {1, (syscall_function *) sys_munmap},
895 + const struct syscall *sc;
899 + /* Get the system call. */
900 + copy_in (&call_nr, f->esp, sizeof call_nr);
901 + if (call_nr >= sizeof syscall_table / sizeof *syscall_table)
903 + sc = syscall_table + call_nr;
905 + /* Get the system call arguments. */
906 + ASSERT (sc->arg_cnt <= sizeof args / sizeof *args);
907 + memset (args, 0, sizeof args);
908 + copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt);
910 + /* Execute the system call,
911 + and set the return value. */
912 + f->eax = sc->func (args[0], args[1], args[2]);
915 +/* Copies SIZE bytes from user address USRC to kernel address
917 + Call thread_exit() if any of the user accesses are invalid. */
919 -syscall_handler (struct intr_frame *f UNUSED)
920 +copy_in (void *dst_, const void *usrc_, size_t size)
922 + uint8_t *dst = dst_;
923 + const uint8_t *usrc = usrc_;
927 + size_t chunk_size = PGSIZE - pg_ofs (usrc);
928 + if (chunk_size > size)
931 + if (!page_lock (usrc, false))
933 + memcpy (dst, usrc, chunk_size);
934 + page_unlock (usrc);
937 + usrc += chunk_size;
938 + size -= chunk_size;
942 +/* Creates a copy of user string US in kernel memory
943 + and returns it as a page that must be freed with
944 + palloc_free_page().
945 + Truncates the string at PGSIZE bytes in size.
946 + Call thread_exit() if any of the user accesses are invalid. */
948 +copy_in_string (const char *us)
954 + ks = palloc_get_page (0);
961 + upage = pg_round_down (us);
962 + if (!page_lock (upage, false))
965 + for (; us < upage + PGSIZE; us++)
967 + ks[length++] = *us;
970 + page_unlock (upage);
973 + else if (length >= PGSIZE)
974 + goto too_long_error;
977 + page_unlock (upage);
981 + page_unlock (upage);
983 + palloc_free_page (ks);
987 +/* Halt system call. */
994 +/* Exit system call. */
996 +sys_exit (int exit_code)
998 + thread_current ()->exit_code = exit_code;
1003 +/* Exec system call. */
1005 +sys_exec (const char *ufile)
1008 + char *kfile = copy_in_string (ufile);
1010 + lock_acquire (&fs_lock);
1011 + tid = process_execute (kfile);
1012 + lock_release (&fs_lock);
1014 + palloc_free_page (kfile);
1019 +/* Wait system call. */
1021 +sys_wait (tid_t child)
1023 + return process_wait (child);
1026 +/* Create system call. */
1028 +sys_create (const char *ufile, unsigned initial_size)
1030 + char *kfile = copy_in_string (ufile);
1033 + lock_acquire (&fs_lock);
1034 + ok = filesys_create (kfile, initial_size);
1035 + lock_release (&fs_lock);
1037 + palloc_free_page (kfile);
1042 +/* Remove system call. */
1044 +sys_remove (const char *ufile)
1046 + char *kfile = copy_in_string (ufile);
1049 + lock_acquire (&fs_lock);
1050 + ok = filesys_remove (kfile);
1051 + lock_release (&fs_lock);
1053 + palloc_free_page (kfile);
1058 +/* A file descriptor, for binding a file handle to a file. */
1059 +struct file_descriptor
1061 + struct list_elem elem; /* List element. */
1062 + struct file *file; /* File. */
1063 + int handle; /* File handle. */
1066 +/* Open system call. */
1068 +sys_open (const char *ufile)
1070 + char *kfile = copy_in_string (ufile);
1071 + struct file_descriptor *fd;
1074 + fd = malloc (sizeof *fd);
1077 + lock_acquire (&fs_lock);
1078 + fd->file = filesys_open (kfile);
1079 + if (fd->file != NULL)
1081 + struct thread *cur = thread_current ();
1082 + handle = fd->handle = cur->next_handle++;
1083 + list_push_front (&cur->fds, &fd->elem);
1087 + lock_release (&fs_lock);
1090 + palloc_free_page (kfile);
1094 +/* Returns the file descriptor associated with the given handle.
1095 + Terminates the process if HANDLE is not associated with an
1097 +static struct file_descriptor *
1098 +lookup_fd (int handle)
1100 + struct thread *cur = thread_current ();
1101 + struct list_elem *e;
1103 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
1104 + e = list_next (e))
1106 + struct file_descriptor *fd;
1107 + fd = list_entry (e, struct file_descriptor, elem);
1108 + if (fd->handle == handle)
1115 +/* Filesize system call. */
1117 +sys_filesize (int handle)
1119 + struct file_descriptor *fd = lookup_fd (handle);
1122 + lock_acquire (&fs_lock);
1123 + size = file_length (fd->file);
1124 + lock_release (&fs_lock);
1129 +/* Read system call. */
1131 +sys_read (int handle, void *udst_, unsigned size)
1133 - printf ("system call!\n");
1134 + uint8_t *udst = udst_;
1135 + struct file_descriptor *fd;
1136 + int bytes_read = 0;
1138 + fd = lookup_fd (handle);
1141 + /* How much to read into this page? */
1142 + size_t page_left = PGSIZE - pg_ofs (udst);
1143 + size_t read_amt = size < page_left ? size : page_left;
1146 + /* Read from file into page. */
1147 + if (handle != STDIN_FILENO)
1149 + if (!page_lock (udst, true))
1151 + lock_acquire (&fs_lock);
1152 + retval = file_read (fd->file, udst, read_amt);
1153 + lock_release (&fs_lock);
1154 + page_unlock (udst);
1160 + for (i = 0; i < read_amt; i++)
1162 + char c = kbd_getc ();
1163 + if (!page_lock (udst, true))
1166 + page_unlock (udst);
1168 + bytes_read = read_amt;
1171 + /* Check success. */
1174 + if (bytes_read == 0)
1178 + bytes_read += retval;
1179 + if (retval != (off_t) read_amt)
1181 + /* Short read, so we're done. */
1190 + return bytes_read;
1193 +/* Write system call. */
1195 +sys_write (int handle, void *usrc_, unsigned size)
1197 + uint8_t *usrc = usrc_;
1198 + struct file_descriptor *fd = NULL;
1199 + int bytes_written = 0;
1201 + /* Lookup up file descriptor. */
1202 + if (handle != STDOUT_FILENO)
1203 + fd = lookup_fd (handle);
1207 + /* How much bytes to write to this page? */
1208 + size_t page_left = PGSIZE - pg_ofs (usrc);
1209 + size_t write_amt = size < page_left ? size : page_left;
1212 + /* Write from page into file. */
1213 + if (!page_lock (usrc, false))
1215 + lock_acquire (&fs_lock);
1216 + if (handle == STDOUT_FILENO)
1218 + putbuf ((char *) usrc, write_amt);
1219 + retval = write_amt;
1222 + retval = file_write (fd->file, usrc, write_amt);
1223 + lock_release (&fs_lock);
1224 + page_unlock (usrc);
1226 + /* Handle return value. */
1229 + if (bytes_written == 0)
1230 + bytes_written = -1;
1233 + bytes_written += retval;
1235 + /* If it was a short write we're done. */
1236 + if (retval != (off_t) write_amt)
1244 + return bytes_written;
1247 +/* Seek system call. */
1249 +sys_seek (int handle, unsigned position)
1251 + struct file_descriptor *fd = lookup_fd (handle);
1253 + lock_acquire (&fs_lock);
1254 + if ((off_t) position >= 0)
1255 + file_seek (fd->file, position);
1256 + lock_release (&fs_lock);
1261 +/* Tell system call. */
1263 +sys_tell (int handle)
1265 + struct file_descriptor *fd = lookup_fd (handle);
1266 + unsigned position;
1268 + lock_acquire (&fs_lock);
1269 + position = file_tell (fd->file);
1270 + lock_release (&fs_lock);
1275 +/* Close system call. */
1277 +sys_close (int handle)
1279 + struct file_descriptor *fd = lookup_fd (handle);
1280 + lock_acquire (&fs_lock);
1281 + file_close (fd->file);
1282 + lock_release (&fs_lock);
1283 + list_remove (&fd->elem);
1288 +/* Binds a mapping id to a region of memory and a file. */
1291 + struct list_elem elem; /* List element. */
1292 + int handle; /* Mapping id. */
1293 + struct file *file; /* File. */
1294 + uint8_t *base; /* Start of memory mapping. */
1295 + size_t page_cnt; /* Number of pages mapped. */
1298 +/* Returns the file descriptor associated with the given handle.
1299 + Terminates the process if HANDLE is not associated with a
1300 + memory mapping. */
1301 +static struct mapping *
1302 +lookup_mapping (int handle)
1304 + struct thread *cur = thread_current ();
1305 + struct list_elem *e;
1307 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1308 + e = list_next (e))
1310 + struct mapping *m = list_entry (e, struct mapping, elem);
1311 + if (m->handle == handle)
1318 +/* Remove mapping M from the virtual address space,
1319 + writing back any pages that have changed. */
1321 +unmap (struct mapping *m)
1323 + list_remove (&m->elem);
1324 + while (m->page_cnt-- > 0)
1326 + page_deallocate (m->base);
1327 + m->base += PGSIZE;
1329 + file_close (m->file);
1333 +/* Mmap system call. */
1335 +sys_mmap (int handle, void *addr)
1337 + struct file_descriptor *fd = lookup_fd (handle);
1338 + struct mapping *m = malloc (sizeof *m);
1342 + if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
1345 + m->handle = thread_current ()->next_handle++;
1346 + lock_acquire (&fs_lock);
1347 + m->file = file_reopen (fd->file);
1348 + lock_release (&fs_lock);
1349 + if (m->file == NULL)
1356 + list_push_front (&thread_current ()->mappings, &m->elem);
1359 + lock_acquire (&fs_lock);
1360 + length = file_length (m->file);
1361 + lock_release (&fs_lock);
1362 + while (length > 0)
1364 + struct page *p = page_allocate ((uint8_t *) addr + offset, false);
1370 + p->private = false;
1371 + p->file = m->file;
1372 + p->file_offset = offset;
1373 + p->file_bytes = length >= PGSIZE ? PGSIZE : length;
1374 + offset += p->file_bytes;
1375 + length -= p->file_bytes;
1382 +/* Munmap system call. */
1384 +sys_munmap (int mapping)
1386 + unmap (lookup_mapping (mapping));
1390 +/* On thread exit, close all open files and unmap all mappings. */
1392 +syscall_exit (void)
1394 + struct thread *cur = thread_current ();
1395 + struct list_elem *e, *next;
1397 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
1399 + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
1400 + next = list_next (e);
1401 + lock_acquire (&fs_lock);
1402 + file_close (fd->file);
1403 + lock_release (&fs_lock);
1407 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1410 + struct mapping *m = list_entry (e, struct mapping, elem);
1411 + next = list_next (e);
1415 Index: src/userprog/syscall.h
1416 diff -u src/userprog/syscall.h~ src/userprog/syscall.h
1417 --- src/userprog/syscall.h~ 2004-09-05 22:38:45.000000000 -0700
1418 +++ src/userprog/syscall.h 2006-05-16 13:44:56.000000000 -0700
1420 #define USERPROG_SYSCALL_H
1422 void syscall_init (void);
1423 +void syscall_exit (void);
1425 #endif /* userprog/syscall.h */
1426 Index: src/vm/frame.c
1427 diff -u src/vm/frame.c~ src/vm/frame.c
1428 --- src/vm/frame.c~ 1969-12-31 16:00:00.000000000 -0800
1429 +++ src/vm/frame.c 2006-05-16 13:44:56.000000000 -0700
1431 +#include "vm/frame.h"
1433 +#include "vm/page.h"
1434 +#include "devices/timer.h"
1435 +#include "threads/init.h"
1436 +#include "threads/malloc.h"
1437 +#include "threads/palloc.h"
1438 +#include "threads/synch.h"
1439 +#include "threads/vaddr.h"
1441 +static struct frame *frames;
1442 +static size_t frame_cnt;
1444 +static struct lock scan_lock;
1445 +static size_t hand;
1447 +/* Initialize the frame manager. */
1453 + lock_init (&scan_lock);
1455 + frames = malloc (sizeof *frames * ram_pages);
1456 + if (frames == NULL)
1457 + PANIC ("out of memory allocating page frames");
1459 + while ((base = palloc_get_page (PAL_USER)) != NULL)
1461 + struct frame *f = &frames[frame_cnt++];
1462 + lock_init (&f->lock);
1468 +/* Tries to allocate and lock a frame for PAGE.
1469 + Returns the frame if successful, false on failure. */
1470 +static struct frame *
1471 +try_frame_alloc_and_lock (struct page *page)
1475 + lock_acquire (&scan_lock);
1477 + /* Find a free frame. */
1478 + for (i = 0; i < frame_cnt; i++)
1480 + struct frame *f = &frames[i];
1481 + if (!lock_try_acquire (&f->lock))
1483 + if (f->page == NULL)
1486 + lock_release (&scan_lock);
1489 + lock_release (&f->lock);
1492 + /* No free frame. Find a frame to evict. */
1493 + for (i = 0; i < frame_cnt * 2; i++)
1495 + /* Get a frame. */
1496 + struct frame *f = &frames[hand];
1497 + if (++hand >= frame_cnt)
1500 + if (!lock_try_acquire (&f->lock))
1503 + if (f->page == NULL)
1506 + lock_release (&scan_lock);
1510 + if (page_accessed_recently (f->page))
1512 + lock_release (&f->lock);
1516 + lock_release (&scan_lock);
1518 + /* Evict this frame. */
1519 + if (!page_out (f->page))
1521 + lock_release (&f->lock);
1529 + lock_release (&scan_lock);
1534 +/* Tries really hard to allocate and lock a frame for PAGE.
1535 + Returns the frame if successful, false on failure. */
1537 +frame_alloc_and_lock (struct page *page)
1541 + for (try = 0; try < 3; try++)
1543 + struct frame *f = try_frame_alloc_and_lock (page);
1546 + ASSERT (lock_held_by_current_thread (&f->lock));
1549 + timer_msleep (1000);
1555 +/* Locks P's frame into memory, if it has one.
1556 + Upon return, p->frame will not change until P is unlocked. */
1558 +frame_lock (struct page *p)
1560 + /* A frame can be asynchronously removed, but never inserted. */
1561 + struct frame *f = p->frame;
1564 + lock_acquire (&f->lock);
1565 + if (f != p->frame)
1567 + lock_release (&f->lock);
1568 + ASSERT (p->frame == NULL);
1573 +/* Releases frame F for use by another page.
1574 + F must be locked for use by the current process.
1575 + Any data in F is lost. */
1577 +frame_free (struct frame *f)
1579 + ASSERT (lock_held_by_current_thread (&f->lock));
1582 + lock_release (&f->lock);
1585 +/* Unlocks frame F, allowing it to be evicted.
1586 + F must be locked for use by the current process. */
1588 +frame_unlock (struct frame *f)
1590 + ASSERT (lock_held_by_current_thread (&f->lock));
1591 + lock_release (&f->lock);
1593 Index: src/vm/frame.h
1594 diff -u src/vm/frame.h~ src/vm/frame.h
1595 --- src/vm/frame.h~ 1969-12-31 16:00:00.000000000 -0800
1596 +++ src/vm/frame.h 2006-05-16 13:44:56.000000000 -0700
1601 +#include <stdbool.h>
1602 +#include "threads/synch.h"
1604 +/* A physical frame. */
1607 + struct lock lock; /* Prevent simultaneous access. */
1608 + void *base; /* Kernel virtual base address. */
1609 + struct page *page; /* Mapped process page, if any. */
1612 +void frame_init (void);
1614 +struct frame *frame_alloc_and_lock (struct page *);
1615 +void frame_lock (struct page *);
1617 +void frame_free (struct frame *);
1618 +void frame_unlock (struct frame *);
1620 +#endif /* vm/frame.h */
1621 Index: src/vm/page.c
1622 diff -u src/vm/page.c~ src/vm/page.c
1623 --- src/vm/page.c~ 1969-12-31 16:00:00.000000000 -0800
1624 +++ src/vm/page.c 2006-05-16 13:44:56.000000000 -0700
1626 +#include "vm/page.h"
1628 +#include <string.h>
1629 +#include "vm/frame.h"
1630 +#include "vm/swap.h"
1631 +#include "filesys/file.h"
1632 +#include "threads/malloc.h"
1633 +#include "threads/thread.h"
1634 +#include "userprog/pagedir.h"
1635 +#include "threads/vaddr.h"
1637 +/* Maximum size of process stack, in bytes. */
1638 +#define STACK_MAX (1024 * 1024)
1640 +/* Destroys a page, which must be in the current process's
1641 + page table. Used as a callback for hash_destroy(). */
1643 +destroy_page (struct hash_elem *p_, void *aux UNUSED)
1645 + struct page *p = hash_entry (p_, struct page, hash_elem);
1648 + frame_free (p->frame);
1652 +/* Destroys the current process's page table. */
1656 + struct hash *h = thread_current ()->pages;
1658 + hash_destroy (h, destroy_page);
1661 +/* Returns the page containing the given virtual ADDRESS,
1662 + or a null pointer if no such page exists.
1663 + Allocates stack pages as necessary. */
1664 +static struct page *
1665 +page_for_addr (const void *address)
1667 + if (address < PHYS_BASE)
1670 + struct hash_elem *e;
1672 + /* Find existing page. */
1673 + p.addr = (void *) pg_round_down (address);
1674 + e = hash_find (thread_current ()->pages, &p.hash_elem);
1676 + return hash_entry (e, struct page, hash_elem);
1678 + /* No page. Expand stack? */
1679 + if (address >= PHYS_BASE - STACK_MAX
1680 + && address >= thread_current ()->user_esp - 32)
1681 + return page_allocate ((void *) address, false);
1686 +/* Locks a frame for page P and pages it in.
1687 + Returns true if successful, false on failure. */
1689 +do_page_in (struct page *p)
1691 + /* Get a frame for the page. */
1692 + p->frame = frame_alloc_and_lock (p);
1693 + if (p->frame == NULL)
1696 + /* Copy data into the frame. */
1697 + if (p->sector != (disk_sector_t) -1)
1699 + /* Get data from swap. */
1702 + else if (p->file != NULL)
1704 + /* Get data from file. */
1705 + off_t read_bytes = file_read_at (p->file, p->frame->base,
1706 + p->file_bytes, p->file_offset);
1707 + off_t zero_bytes = PGSIZE - read_bytes;
1708 + memset (p->frame->base + read_bytes, 0, zero_bytes);
1709 + if (read_bytes != p->file_bytes)
1710 + printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
1711 + read_bytes, p->file_bytes);
1715 + /* Provide all-zero page. */
1716 + memset (p->frame->base, 0, PGSIZE);
1722 +/* Faults in the page containing FAULT_ADDR.
1723 + Returns true if successful, false on failure. */
1725 +page_in (void *fault_addr)
1730 + /* Can't handle page faults without a hash table. */
1731 + if (thread_current ()->pages == NULL)
1734 + p = page_for_addr (fault_addr);
1739 + if (p->frame == NULL)
1741 + if (!do_page_in (p))
1744 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1746 + /* Install frame into page table. */
1747 + success = pagedir_set_page (thread_current ()->pagedir, p->addr,
1748 + p->frame->base, !p->read_only);
1750 + /* Release frame. */
1751 + frame_unlock (p->frame);
1757 + P must have a locked frame.
1758 + Return true if successful, false on failure. */
1760 +page_out (struct page *p)
1765 + ASSERT (p->frame != NULL);
1766 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1768 + /* Mark page not present in page table, forcing accesses by the
1769 + process to fault. This must happen before checking the
1770 + dirty bit, to prevent a race with the process dirtying the
1772 + pagedir_clear_page (p->thread->pagedir, p->addr);
1774 + /* Has the frame been modified? */
1775 + dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
1777 + /* Write frame contents to disk if necessary. */
1778 + if (p->file != NULL)
1783 + ok = swap_out (p);
1785 + ok = file_write_at (p->file, p->frame->base, p->file_bytes,
1786 + p->file_offset) == p->file_bytes;
1792 + ok = swap_out (p);
1795 + //memset (p->frame->base, 0xcc, PGSIZE);
1801 +/* Returns true if page P's data has been accessed recently,
1803 + P must have a frame locked into memory. */
1805 +page_accessed_recently (struct page *p)
1807 + bool was_accessed;
1809 + ASSERT (p->frame != NULL);
1810 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1812 + was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
1814 + pagedir_set_accessed (p->thread->pagedir, p->addr, false);
1815 + return was_accessed;
1818 +/* Adds a mapping for user virtual address VADDR to the page hash
1819 + table. Fails if VADDR is already mapped or if memory
1820 + allocation fails. */
1822 +page_allocate (void *vaddr, bool read_only)
1824 + struct thread *t = thread_current ();
1825 + struct page *p = malloc (sizeof *p);
1828 + p->addr = pg_round_down (vaddr);
1830 + p->read_only = read_only;
1831 + p->private = !read_only;
1835 + p->sector = (disk_sector_t) -1;
1838 + p->file_offset = 0;
1839 + p->file_bytes = 0;
1841 + p->thread = thread_current ();
1843 + if (hash_insert (t->pages, &p->hash_elem) != NULL)
1845 + /* Already mapped. */
1853 +/* Evicts the page containing address VADDR
1854 + and removes it from the page table. */
1856 +page_deallocate (void *vaddr)
1858 + struct page *p = page_for_addr (vaddr);
1859 + ASSERT (p != NULL);
1863 + struct frame *f = p->frame;
1864 + if (p->file && !p->private)
1868 + hash_delete (thread_current ()->pages, &p->hash_elem);
1872 +/* Returns a hash value for the page that E refers to. */
1874 +page_hash (const struct hash_elem *e, void *aux UNUSED)
1876 + const struct page *p = hash_entry (e, struct page, hash_elem);
1877 + return ((uintptr_t) p->addr) >> PGBITS;
1880 +/* Returns true if page A precedes page B. */
1882 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
1885 + const struct page *a = hash_entry (a_, struct page, hash_elem);
1886 + const struct page *b = hash_entry (b_, struct page, hash_elem);
1888 + return a->addr < b->addr;
1891 +/* Tries to lock the page containing ADDR into physical memory.
1892 + If WILL_WRITE is true, the page must be writeable;
1893 + otherwise it may be read-only.
1894 + Returns true if successful, false on failure. */
1896 +page_lock (const void *addr, bool will_write)
1898 + struct page *p = page_for_addr (addr);
1899 + if (p == NULL || (p->read_only && will_write))
1903 + if (p->frame == NULL)
1904 + return (do_page_in (p)
1905 + && pagedir_set_page (thread_current ()->pagedir, p->addr,
1906 + p->frame->base, !p->read_only));
1911 +/* Unlocks a page locked with page_lock(). */
1913 +page_unlock (const void *addr)
1915 + struct page *p = page_for_addr (addr);
1916 + ASSERT (p != NULL);
1917 + frame_unlock (p->frame);
1919 Index: src/vm/page.h
1920 diff -u src/vm/page.h~ src/vm/page.h
1921 --- src/vm/page.h~ 1969-12-31 16:00:00.000000000 -0800
1922 +++ src/vm/page.h 2006-05-16 13:44:56.000000000 -0700
1928 +#include "devices/disk.h"
1929 +#include "filesys/off_t.h"
1930 +#include "threads/synch.h"
1932 +/* Virtual page. */
1935 + /* Immutable members. */
1936 + void *addr; /* User virtual address. */
1937 + bool read_only; /* Read-only page? */
1938 + struct thread *thread; /* Owning thread. */
1940 + /* Accessed only in owning process context. */
1941 + struct hash_elem hash_elem; /* struct thread `pages' hash element. */
1943 + /* Set only in owning process context with frame->frame_lock held.
1944 + Cleared only with scan_lock and frame->frame_lock held. */
1945 + struct frame *frame; /* Page frame. */
1947 + /* Swap information, protected by frame->frame_lock. */
1948 + disk_sector_t sector; /* Starting sector of swap area, or -1. */
1950 + /* Memory-mapped file information, protected by frame->frame_lock. */
1951 + bool private; /* False to write back to file,
1952 + true to write back to swap. */
1953 + struct file *file; /* File. */
1954 + off_t file_offset; /* Offset in file. */
1955 + off_t file_bytes; /* Bytes to read/write, 1...PGSIZE. */
1958 +void page_exit (void);
1960 +struct page *page_allocate (void *, bool read_only);
1961 +void page_deallocate (void *vaddr);
1963 +bool page_in (void *fault_addr);
1964 +bool page_out (struct page *);
1965 +bool page_accessed_recently (struct page *);
1967 +bool page_lock (const void *, bool will_write);
1968 +void page_unlock (const void *);
1970 +hash_hash_func page_hash;
1971 +hash_less_func page_less;
1973 +#endif /* vm/page.h */
1974 Index: src/vm/swap.c
1975 diff -u src/vm/swap.c~ src/vm/swap.c
1976 --- src/vm/swap.c~ 1969-12-31 16:00:00.000000000 -0800
1977 +++ src/vm/swap.c 2006-05-16 13:44:56.000000000 -0700
1979 +#include "vm/swap.h"
1980 +#include <bitmap.h>
1983 +#include "vm/frame.h"
1984 +#include "vm/page.h"
1985 +#include "devices/disk.h"
1986 +#include "threads/synch.h"
1987 +#include "threads/vaddr.h"
1989 +/* The swap disk. */
1990 +static struct disk *swap_disk;
1992 +/* Used swap pages. */
1993 +static struct bitmap *swap_bitmap;
1995 +/* Protects swap_bitmap. */
1996 +static struct lock swap_lock;
1998 +/* Number of sectors per page. */
1999 +#define PAGE_SECTORS (PGSIZE / DISK_SECTOR_SIZE)
2001 +/* Sets up swap. */
2005 + swap_disk = disk_get (1, 1);
2006 + if (swap_disk == NULL)
2008 + printf ("no swap disk--swap disabled\n");
2009 + swap_bitmap = bitmap_create (0);
2012 + swap_bitmap = bitmap_create (disk_size (swap_disk) / PAGE_SECTORS);
2013 + if (swap_bitmap == NULL)
2014 + PANIC ("couldn't create swap bitmap");
2015 + lock_init (&swap_lock);
2018 +/* Swaps in page P, which must have a locked frame
2019 + (and be swapped out). */
2021 +swap_in (struct page *p)
2025 + ASSERT (p->frame != NULL);
2026 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
2027 + ASSERT (p->sector != (disk_sector_t) -1);
2029 + for (i = 0; i < PAGE_SECTORS; i++)
2030 + disk_read (swap_disk, p->sector + i,
2031 + p->frame->base + i * DISK_SECTOR_SIZE);
2032 + bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
2033 + p->sector = (disk_sector_t) -1;
2036 +/* Swaps out page P, which must have a locked frame. */
2038 +swap_out (struct page *p)
2043 + ASSERT (p->frame != NULL);
2044 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
2046 + lock_acquire (&swap_lock);
2047 + slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
2048 + lock_release (&swap_lock);
2049 + if (slot == BITMAP_ERROR)
2052 + p->sector = slot * PAGE_SECTORS;
2053 + for (i = 0; i < PAGE_SECTORS; i++)
2054 + disk_write (swap_disk, p->sector + i,
2055 + p->frame->base + i * DISK_SECTOR_SIZE);
2057 + p->private = false;
2059 + p->file_offset = 0;
2060 + p->file_bytes = 0;
2064 Index: src/vm/swap.h
2065 diff -u src/vm/swap.h~ src/vm/swap.h
2066 --- src/vm/swap.h~ 1969-12-31 16:00:00.000000000 -0800
2067 +++ src/vm/swap.h 2006-05-16 13:44:56.000000000 -0700
2070 +#define VM_SWAP_H 1
2072 +#include <stdbool.h>
2075 +void swap_init (void);
2076 +void swap_in (struct page *);
2077 +bool swap_out (struct page *);
2079 +#endif /* vm/swap.h */