1 diff -u src/Makefile.build~ src/Makefile.build
2 --- src/Makefile.build~ 2005-06-02 17:24:02.000000000 -0700
3 +++ src/Makefile.build 2005-06-08 14:10:54.000000000 -0700
4 @@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c # GDT in
5 userprog_SRC += userprog/tss.c # TSS management.
7 # No virtual memory code yet.
8 -#vm_SRC = vm/filename.c # Some file.
14 filesys_SRC = filesys/filesys.c # Filesystem core.
15 diff -u src/devices/timer.c~ src/devices/timer.c
16 --- src/devices/timer.c~ 2005-05-24 15:52:43.000000000 -0700
17 +++ src/devices/timer.c 2005-06-08 14:10:54.000000000 -0700
18 @@ -23,6 +23,9 @@ static volatile int64_t ticks;
19 Initialized by timer_calibrate(). */
20 static unsigned loops_per_tick;
22 +/* Threads waiting in timer_sleep(). */
23 +static struct list wait_list;
25 static intr_handler_func timer_interrupt;
26 static bool too_many_loops (unsigned loops);
27 static void busy_wait (int64_t loops);
28 @@ -43,6 +46,8 @@ timer_init (void)
29 outb (0x40, count >> 8);
31 intr_register_ext (0x20, timer_interrupt, "8254 Timer");
33 + list_init (&wait_list);
36 /* Calibrates loops_per_tick, used to implement brief delays. */
37 @@ -87,15 +92,36 @@ timer_elapsed (int64_t then)
38 return timer_ticks () - then;
41 +/* Compares two threads based on their wake-up times. */
43 +compare_threads_by_wakeup_time (const struct list_elem *a_,
44 + const struct list_elem *b_,
47 + const struct thread *a = list_entry (a_, struct thread, timer_elem);
48 + const struct thread *b = list_entry (b_, struct thread, timer_elem);
50 + return a->wakeup_time < b->wakeup_time;
53 /* Suspends execution for approximately TICKS timer ticks. */
55 timer_sleep (int64_t ticks)
57 - int64_t start = timer_ticks ();
58 + struct thread *t = thread_current ();
60 + /* Schedule our wake-up time. */
61 + t->wakeup_time = timer_ticks () + ticks;
63 + /* Atomically insert the current thread into the wait list. */
64 ASSERT (intr_get_level () == INTR_ON);
65 - while (timer_elapsed (start) < ticks)
68 + list_insert_ordered (&wait_list, &t->timer_elem,
69 + compare_threads_by_wakeup_time, NULL);
73 + sema_down (&t->timer_sema);
76 /* Suspends execution for approximately MS milliseconds. */
77 @@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
82 + while (!list_empty (&wait_list))
84 + struct thread *t = list_entry (list_front (&wait_list),
85 + struct thread, timer_elem);
86 + if (ticks < t->wakeup_time)
88 + sema_up (&t->timer_sema);
89 + list_pop_front (&wait_list);
93 /* Returns true if LOOPS iterations waits for more than one timer
94 diff -u src/threads/init.c~ src/threads/init.c
95 --- src/threads/init.c~ 2005-06-02 15:43:44.000000000 -0700
96 +++ src/threads/init.c 2005-06-08 14:10:54.000000000 -0700
98 #include "filesys/filesys.h"
99 #include "filesys/fsutil.h"
101 +#include "vm/frame.h"
102 +#include "vm/swap.h"
104 /* Amount of physical memory, in 4 kB pages. */
106 @@ -131,6 +133,9 @@ main (void)
107 filesys_init (format_filesys);
113 printf ("Boot complete.\n");
115 /* Run actions specified on kernel command line. */
116 diff -u src/threads/interrupt.c~ src/threads/interrupt.c
117 --- src/threads/interrupt.c~ 2005-01-21 13:43:16.000000000 -0800
118 +++ src/threads/interrupt.c 2005-06-08 14:10:54.000000000 -0700
119 @@ -331,6 +331,8 @@ intr_handler (struct intr_frame *frame)
120 in_external_intr = true;
121 yield_on_return = false;
124 + thread_current ()->user_esp = frame->esp;
126 /* Invoke the interrupt's handler.
127 If there is no handler, invoke the unexpected interrupt
128 diff -u src/threads/thread.c~ src/threads/thread.c
129 --- src/threads/thread.c~ 2005-06-02 14:35:12.000000000 -0700
130 +++ src/threads/thread.c 2005-06-08 14:10:54.000000000 -0700
132 #include "threads/synch.h"
134 #include "userprog/process.h"
135 +#include "userprog/syscall.h"
138 /* Random value for struct thread's `magic' member.
139 @@ -55,7 +56,8 @@ static void kernel_thread (thread_func *
140 static void idle (void *aux UNUSED);
141 static struct thread *running_thread (void);
142 static struct thread *next_thread_to_run (void);
143 -static void init_thread (struct thread *, const char *name, int priority);
144 +static void init_thread (struct thread *, const char *name, int priority,
146 static bool is_thread (struct thread *) UNUSED;
147 static void *alloc_frame (struct thread *, size_t size);
148 static void schedule (void);
149 @@ -82,9 +84,8 @@ thread_init (void)
151 /* Set up a thread structure for the running thread. */
152 initial_thread = running_thread ();
153 - init_thread (initial_thread, "main", PRI_DEFAULT);
154 + init_thread (initial_thread, "main", PRI_DEFAULT, 0);
155 initial_thread->status = THREAD_RUNNING;
156 - initial_thread->tid = allocate_tid ();
159 /* Starts preemptive thread scheduling by enabling interrupts.
160 @@ -157,8 +158,8 @@ thread_create (const char *name, int pri
163 /* Initialize thread. */
164 - init_thread (t, name, priority);
165 - tid = t->tid = allocate_tid ();
166 + init_thread (t, name, priority, allocate_tid ());
169 /* Stack frame for kernel_thread(). */
170 kf = alloc_frame (t, sizeof *kf);
171 @@ -251,16 +252,19 @@ thread_tid (void)
175 + struct thread *t = thread_current ();
177 ASSERT (!intr_context ());
185 /* Just set our status to dying and schedule another process.
186 We will be destroyed during the call to schedule_tail(). */
188 - thread_current ()->status = THREAD_DYING;
189 + t->status = THREAD_DYING;
193 @@ -389,17 +393,28 @@ is_thread (struct thread *t)
194 /* Does basic initialization of T as a blocked thread named
197 -init_thread (struct thread *t, const char *name, int priority)
198 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
201 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
202 ASSERT (name != NULL);
204 memset (t, 0, sizeof *t);
206 t->status = THREAD_BLOCKED;
207 strlcpy (t->name, name, sizeof t->name);
208 t->stack = (uint8_t *) t + PGSIZE;
209 t->priority = priority;
211 + t->wait_status = NULL;
212 + list_init (&t->children);
213 + sema_init (&t->timer_sema, 0);
216 + t->bin_file = NULL;
217 + list_init (&t->fds);
218 + list_init (&t->mappings);
219 + t->next_handle = 2;
220 t->magic = THREAD_MAGIC;
223 diff -u src/threads/thread.h~ src/threads/thread.h
224 --- src/threads/thread.h~ 2005-06-02 14:32:36.000000000 -0700
225 +++ src/threads/thread.h 2005-06-08 14:10:54.000000000 -0700
227 #define THREADS_THREAD_H
233 +#include "threads/synch.h"
235 /* States in a thread's life cycle. */
237 @@ -89,18 +91,49 @@ struct thread
238 uint8_t *stack; /* Saved stack pointer. */
239 int priority; /* Priority. */
241 + /* Owned by process.c. */
242 + int exit_code; /* Exit code. */
243 + struct wait_status *wait_status; /* This process's completion status. */
244 + struct list children; /* Completion status of children. */
246 /* Shared between thread.c and synch.c. */
247 struct list_elem elem; /* List element. */
251 + int64_t wakeup_time; /* Time to wake this thread up. */
252 + struct list_elem timer_elem; /* Element in timer_wait_list. */
253 + struct semaphore timer_sema; /* Semaphore. */
255 /* Owned by userprog/process.c. */
256 uint32_t *pagedir; /* Page directory. */
258 + struct hash *pages; /* Page table. */
259 + struct file *bin_file; /* The binary executable. */
261 + /* Owned by syscall.c. */
262 + struct list fds; /* List of file descriptors. */
263 + struct list mappings; /* Memory-mapped files. */
264 + int next_handle; /* Next handle value. */
265 + void *user_esp; /* User's stack pointer. */
267 /* Owned by thread.c. */
268 unsigned magic; /* Detects stack overflow. */
271 +/* Tracks the completion of a process.
272 + Reference held by both the parent, in its `children' list,
273 + and by the child, in its `wait_status' pointer. */
276 + struct list_elem elem; /* `children' list element. */
277 + struct lock lock; /* Protects ref_cnt. */
278 + int ref_cnt; /* 2=child and parent both alive,
279 + 1=either child or parent alive,
280 + 0=child and parent both dead. */
281 + tid_t tid; /* Child thread id. */
282 + int exit_code; /* Child exit code, if dead. */
283 + struct semaphore dead; /* 1=child alive, 0=child dead. */
286 void thread_init (void);
287 void thread_start (void);
288 void thread_tick (void);
289 diff -u src/userprog/exception.c~ src/userprog/exception.c
290 --- src/userprog/exception.c~ 2005-01-01 18:09:59.000000000 -0800
291 +++ src/userprog/exception.c 2005-06-08 14:10:54.000000000 -0700
293 #include "userprog/gdt.h"
294 #include "threads/interrupt.h"
295 #include "threads/thread.h"
296 +#include "vm/page.h"
298 /* Number of page faults processed. */
299 static long long page_fault_cnt;
300 @@ -150,9 +151,14 @@ page_fault (struct intr_frame *f)
301 write = (f->error_code & PF_W) != 0;
302 user = (f->error_code & PF_U) != 0;
304 - /* To implement virtual memory, delete the rest of the function
305 - body, and replace it with code that brings in the page to
306 - which fault_addr refers. */
307 + /* Allow the pager to try to handle it. */
308 + if (user && not_present)
310 + if (!page_in (fault_addr))
315 printf ("Page fault at %p: %s error %s page in %s context.\n",
317 not_present ? "not present" : "rights violation",
318 diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c
319 --- src/userprog/pagedir.c~ 2005-05-20 15:44:13.000000000 -0700
320 +++ src/userprog/pagedir.c 2005-06-08 14:10:54.000000000 -0700
321 @@ -34,15 +34,7 @@ pagedir_destroy (uint32_t *pd)
322 ASSERT (pd != base_page_dir);
323 for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
326 - uint32_t *pt = pde_get_pt (*pde);
329 - for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
331 - palloc_free_page (pte_get_page (*pte));
332 - palloc_free_page (pt);
334 + palloc_free_page (pde_get_pt (*pde));
335 palloc_free_page (pd);
338 diff -u src/userprog/process.c~ src/userprog/process.c
339 --- src/userprog/process.c~ 2005-05-26 13:19:48.000000000 -0700
340 +++ src/userprog/process.c 2005-06-08 14:13:25.000000000 -0700
342 #include "threads/init.h"
343 #include "threads/interrupt.h"
344 #include "threads/mmu.h"
345 +#include "threads/malloc.h"
346 #include "threads/palloc.h"
347 #include "threads/thread.h"
348 +#include "vm/page.h"
349 +#include "vm/frame.h"
351 static thread_func execute_thread NO_RETURN;
352 -static bool load (const char *cmdline, void (**eip) (void), void **esp);
353 +static bool load (const char *cmd_line, void (**eip) (void), void **esp);
355 +/* Data structure shared between process_execute() in the
356 + invoking thread and execute_thread() in the newly invoked
360 + const char *filename; /* Program to load. */
361 + struct semaphore load_done; /* "Up"ed when loading complete. */
362 + struct wait_status *wait_status; /* Child process. */
363 + bool success; /* Program successfully loaded? */
366 /* Starts a new thread running a user program loaded from
367 FILENAME. The new thread may be scheduled (and may even exit)
368 @@ -27,29 +41,37 @@ static bool load (const char *cmdline, v
370 process_execute (const char *filename)
373 + struct exec_info exec;
374 + char thread_name[16];
378 - /* Make a copy of FILENAME.
379 - Otherwise there's a race between the caller and load(). */
380 - fn_copy = palloc_get_page (0);
381 - if (fn_copy == NULL)
383 - strlcpy (fn_copy, filename, PGSIZE);
384 + /* Initialize exec_info. */
385 + exec.filename = filename;
386 + sema_init (&exec.load_done, 0);
388 /* Create a new thread to execute FILENAME. */
389 - tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy);
390 - if (tid == TID_ERROR)
391 - palloc_free_page (fn_copy);
392 + strlcpy (thread_name, filename, sizeof thread_name);
393 + strtok_r (thread_name, " ", &save_ptr);
394 + tid = thread_create (thread_name, PRI_DEFAULT, execute_thread, &exec);
395 + if (tid != TID_ERROR)
397 + sema_down (&exec.load_done);
399 + list_push_back (&thread_current ()->children, &exec.wait_status->elem);
407 /* A thread function that loads a user process and starts it
410 -execute_thread (void *filename_)
411 +execute_thread (void *exec_)
413 - char *filename = filename_;
414 + struct exec_info *exec = exec_;
415 struct intr_frame if_;
418 @@ -58,10 +80,28 @@ execute_thread (void *filename_)
419 if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
421 if_.eflags = FLAG_IF | FLAG_MBS;
422 - success = load (filename, &if_.eip, &if_.esp);
423 + success = load (exec->filename, &if_.eip, &if_.esp);
425 - /* If load failed, quit. */
426 - palloc_free_page (filename);
427 + /* Allocate wait_status. */
430 + exec->wait_status = thread_current ()->wait_status
431 + = malloc (sizeof *exec->wait_status);
432 + success = exec->wait_status != NULL;
435 + /* Initialize wait_status. */
438 + lock_init (&exec->wait_status->lock);
439 + exec->wait_status->ref_cnt = 2;
440 + exec->wait_status->tid = thread_current ()->tid;
441 + sema_init (&exec->wait_status->dead, 0);
444 + /* Notify parent thread and clean up. */
445 + exec->success = success;
446 + sema_up (&exec->load_done);
450 @@ -75,18 +115,47 @@ execute_thread (void *filename_)
454 +/* Releases one reference to CS and, if it is now unreferenced,
457 +release_child (struct wait_status *cs)
461 + lock_acquire (&cs->lock);
462 + new_ref_cnt = --cs->ref_cnt;
463 + lock_release (&cs->lock);
465 + if (new_ref_cnt == 0)
469 /* Waits for thread TID to die and returns its exit status. If
470 it was terminated by the kernel (i.e. killed due to an
471 exception), returns -1. If TID is invalid or if it was not a
472 child of the calling process, or if process_wait() has already
473 been successfully called for the given TID, returns -1
474 - immediately, without waiting.
476 - This function will be implemented in problem 2-2. For now, it
478 + immediately, without waiting. */
480 -process_wait (tid_t child_tid UNUSED)
481 +process_wait (tid_t child_tid)
483 + struct thread *cur = thread_current ();
484 + struct list_elem *e;
486 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
489 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
490 + if (cs->tid == child_tid)
494 + sema_down (&cs->dead);
495 + exit_code = cs->exit_code;
496 + release_child (cs);
503 @@ -95,8 +164,35 @@ void
506 struct thread *cur = thread_current ();
507 + struct list_elem *e, *next;
510 + printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
512 + /* Notify parent that we're dead. */
513 + if (cur->wait_status != NULL)
515 + struct wait_status *cs = cur->wait_status;
516 + cs->exit_code = cur->exit_code;
517 + sema_up (&cs->dead);
518 + release_child (cs);
521 + /* Free entries of children list. */
522 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
525 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
526 + next = list_remove (e);
527 + release_child (cs);
530 + /* Destroy the page hash table. */
533 + /* Close executable (and allow writes). */
534 + file_close (cur->bin_file);
536 /* Destroy the current process's page directory and switch back
537 to the kernel-only page directory. */
539 @@ -193,7 +289,7 @@ struct Elf32_Phdr
540 #define PF_R 4 /* Readable. */
542 static bool load_segment (struct file *, const struct Elf32_Phdr *);
543 -static bool setup_stack (void **esp);
544 +static bool setup_stack (const char *cmd_line, void **esp);
546 /* Loads an ELF executable from FILENAME into the current thread.
547 Stores the executable's entry point into *EIP
548 @@ -209,13 +305,15 @@ static bool setup_stack (void **esp);
549 and its initial stack pointer into *ESP.
550 Returns true if successful, false otherwise. */
552 -load (const char *filename, void (**eip) (void), void **esp)
553 +load (const char *cmd_line, void (**eip) (void), void **esp)
555 struct thread *t = thread_current ();
556 + char filename[NAME_MAX + 2];
557 struct Elf32_Ehdr ehdr;
558 struct file *file = NULL;
560 bool success = false;
564 /* Allocate and activate page directory. */
565 @@ -224,13 +322,28 @@ load (const char *filename, void (**eip)
569 + /* Create page hash table. */
570 + t->pages = malloc (sizeof *t->pages);
571 + if (t->pages == NULL)
573 + hash_init (t->pages, page_hash, page_less, NULL);
575 + /* Extract filename from command line. */
576 + while (*cmd_line == ' ')
578 + strlcpy (filename, cmd_line, sizeof filename);
579 + cp = strchr (filename, ' ');
583 /* Open executable file. */
584 - file = filesys_open (filename);
585 + t->bin_file = file = filesys_open (filename);
588 printf ("load: %s: open failed\n", filename);
591 + file_deny_write (t->bin_file);
593 /* Read and verify executable header. */
594 if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
595 @@ -284,7 +397,7 @@ load (const char *filename, void (**eip)
599 - if (!setup_stack (esp))
600 + if (!setup_stack (cmd_line, esp))
604 @@ -294,14 +407,11 @@ load (const char *filename, void (**eip)
607 /* We arrive here whether the load is successful or not. */
612 /* load() helpers. */
614 -static bool install_page (void *upage, void *kpage);
616 /* Loads the segment described by PHDR from FILE into user
617 address space. Return true if successful, false otherwise. */
619 @@ -309,6 +419,7 @@ load_segment (struct file *file, const s
621 void *start, *end; /* Page-rounded segment start and end. */
622 uint8_t *upage; /* Iterator from start to end. */
623 + off_t file_offset; /* Offset into file. */
624 off_t filesz_left; /* Bytes left of file data (as opposed to
625 zero-initialized bytes). */
627 @@ -316,7 +427,7 @@ load_segment (struct file *file, const s
628 commented out. You'll want to use it when implementing VM
629 to decide whether to page the segment from its executable or
631 - //bool read_only = (phdr->p_flags & PF_W) == 0;
632 + bool read_only = (phdr->p_flags & PF_W) == 0;
634 ASSERT (file != NULL);
635 ASSERT (phdr != NULL);
636 @@ -360,69 +471,129 @@ load_segment (struct file *file, const s
640 - /* Load the segment page-by-page into memory. */
641 + /* Add the segment page-by-page to the hash table. */
642 filesz_left = phdr->p_filesz + (phdr->p_vaddr & PGMASK);
643 - file_seek (file, ROUND_DOWN (phdr->p_offset, PGSIZE));
644 + file_offset = ROUND_DOWN (phdr->p_offset, PGSIZE);
645 for (upage = start; upage < (uint8_t *) end; upage += PGSIZE)
647 - /* We want to read min(PGSIZE, filesz_left) bytes from the
648 - file into the page and zero the rest. */
649 - size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
650 - size_t zero_bytes = PGSIZE - read_bytes;
651 - uint8_t *kpage = palloc_get_page (PAL_USER);
653 + struct page *p = page_allocate (upage, read_only);
657 - /* Do the reading and zeroing. */
658 - if (file_read (file, kpage, read_bytes) != (int) read_bytes)
660 - palloc_free_page (kpage);
663 - memset (kpage + read_bytes, 0, zero_bytes);
664 - filesz_left -= read_bytes;
666 - /* Add the page to the process's address space. */
667 - if (!install_page (upage, kpage))
668 + if (filesz_left > 0)
670 - palloc_free_page (kpage);
672 + size_t file_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
674 + p->file_offset = file_offset;
675 + p->file_bytes = file_bytes;
676 + filesz_left -= file_bytes;
677 + file_offset += file_bytes;
684 -/* Create a minimal stack by mapping a zeroed page at the top of
685 - user virtual memory. */
687 -setup_stack (void **esp)
688 +/* Reverse the order of the ARGC pointers to char in ARGV. */
690 +reverse (int argc, char **argv)
693 - bool success = false;
695 - kpage = palloc_get_page (PAL_USER | PAL_ZERO);
697 + for (; argc > 1; argc -= 2, argv++)
699 - success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage);
703 - palloc_free_page (kpage);
704 + char *tmp = argv[0];
705 + argv[0] = argv[argc - 1];
706 + argv[argc - 1] = tmp;
711 +/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
712 + page-relative stack pointer is *OFS, and then adjusts *OFS
713 + appropriately. The bytes pushed are rounded to a 32-bit
716 + If successful, returns a pointer to the newly pushed object.
717 + On failure, returns a null pointer. */
719 +push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size)
721 + size_t padsize = ROUND_UP (size, sizeof (uint32_t));
722 + if (*ofs < padsize)
726 + memcpy (kpage + *ofs + (padsize - size), buf, size);
727 + return kpage + *ofs + (padsize - size);
730 -/* Adds a mapping from user virtual address UPAGE to kernel
731 - virtual address KPAGE to the page table. Fails if UPAGE is
732 - already mapped or if memory allocation fails. */
733 +/* Sets up command line arguments in KPAGE, which will be mapped
734 + to UPAGE in user space. The command line arguments are taken
735 + from CMD_LINE, separated by spaces. Sets *ESP to the initial
736 + stack pointer for the process. */
738 -install_page (void *upage, void *kpage)
739 +init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
742 - struct thread *t = thread_current ();
743 + size_t ofs = PGSIZE;
744 + char *const null = NULL;
745 + char *cmd_line_copy;
746 + char *karg, *saveptr;
750 + /* Push command line string. */
751 + cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1);
752 + if (cmd_line_copy == NULL)
755 + if (push (kpage, &ofs, &null, sizeof null) == NULL)
758 + /* Parse command line into arguments
759 + and push them in reverse order. */
761 + for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL;
762 + karg = strtok_r (NULL, " ", &saveptr))
764 + char *uarg = upage + (karg - (char *) kpage);
765 + if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
770 + /* Reverse the order of the command line arguments. */
771 + argv = (char **) (upage + ofs);
772 + reverse (argc, (char **) (kpage + ofs));
774 + /* Push argv, argc, "return address". */
775 + if (push (kpage, &ofs, &argv, sizeof argv) == NULL
776 + || push (kpage, &ofs, &argc, sizeof argc) == NULL
777 + || push (kpage, &ofs, &null, sizeof null) == NULL)
780 + /* Set initial stack pointer. */
781 + *esp = upage + ofs;
785 - /* Verify that there's not already a page at that virtual
786 - address, then map our page there. */
787 - return (pagedir_get_page (t->pagedir, upage) == NULL
788 - && pagedir_set_page (t->pagedir, upage, kpage, true));
789 +/* Create a minimal stack for T by mapping a page at the
790 + top of user virtual memory. Fills in the page using CMD_LINE
791 + and sets *ESP to the stack pointer. */
793 +setup_stack (const char *cmd_line, void **esp)
795 + struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
798 + page->frame = frame_alloc_and_lock (page);
799 + if (page->frame != NULL)
802 + page->read_only = false;
803 + page->private = false;
804 + ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
805 + frame_unlock (page->frame);
811 diff -u src/userprog/syscall.c~ src/userprog/syscall.c
812 --- src/userprog/syscall.c~ 2004-09-26 14:15:17.000000000 -0700
813 +++ src/userprog/syscall.c 2005-06-08 14:10:54.000000000 -0700
815 #include "userprog/syscall.h"
818 #include <syscall-nr.h>
819 +#include "userprog/process.h"
820 +#include "userprog/pagedir.h"
821 +#include "devices/kbd.h"
822 +#include "filesys/directory.h"
823 +#include "filesys/filesys.h"
824 +#include "filesys/file.h"
825 +#include "threads/init.h"
826 #include "threads/interrupt.h"
827 +#include "threads/malloc.h"
828 +#include "threads/mmu.h"
829 +#include "threads/palloc.h"
830 #include "threads/thread.h"
832 +#include "vm/page.h"
835 +static int sys_halt (void);
836 +static int sys_exit (int status);
837 +static int sys_exec (const char *ufile);
838 +static int sys_wait (tid_t);
839 +static int sys_create (const char *ufile, unsigned initial_size);
840 +static int sys_remove (const char *ufile);
841 +static int sys_open (const char *ufile);
842 +static int sys_filesize (int handle);
843 +static int sys_read (int handle, void *udst_, unsigned size);
844 +static int sys_write (int handle, void *usrc_, unsigned size);
845 +static int sys_seek (int handle, unsigned position);
846 +static int sys_tell (int handle);
847 +static int sys_close (int handle);
848 +static int sys_mmap (int handle, void *addr);
849 +static int sys_munmap (int mapping);
851 static void syscall_handler (struct intr_frame *);
853 +static void copy_in (void *, const void *, size_t);
858 intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
861 +/* System call handler. */
863 +syscall_handler (struct intr_frame *f)
865 + typedef int syscall_function (int, int, int);
867 + /* A system call. */
870 + size_t arg_cnt; /* Number of arguments. */
871 + syscall_function *func; /* Implementation. */
874 + /* Table of system calls. */
875 + static const struct syscall syscall_table[] =
877 + {0, (syscall_function *) sys_halt},
878 + {1, (syscall_function *) sys_exit},
879 + {1, (syscall_function *) sys_exec},
880 + {1, (syscall_function *) sys_wait},
881 + {2, (syscall_function *) sys_create},
882 + {1, (syscall_function *) sys_remove},
883 + {1, (syscall_function *) sys_open},
884 + {1, (syscall_function *) sys_filesize},
885 + {3, (syscall_function *) sys_read},
886 + {3, (syscall_function *) sys_write},
887 + {2, (syscall_function *) sys_seek},
888 + {1, (syscall_function *) sys_tell},
889 + {1, (syscall_function *) sys_close},
890 + {2, (syscall_function *) sys_mmap},
891 + {1, (syscall_function *) sys_munmap},
894 + const struct syscall *sc;
898 + /* Get the system call. */
899 + copy_in (&call_nr, f->esp, sizeof call_nr);
900 + if (call_nr >= sizeof syscall_table / sizeof *syscall_table)
902 + sc = syscall_table + call_nr;
904 + /* Get the system call arguments. */
905 + ASSERT (sc->arg_cnt <= sizeof args / sizeof *args);
906 + memset (args, 0, sizeof args);
907 + copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt);
909 + /* Execute the system call,
910 + and set the return value. */
911 + f->eax = sc->func (args[0], args[1], args[2]);
914 +/* Copies SIZE bytes from user address USRC to kernel address
916 + Call thread_exit() if any of the user accesses are invalid. */
918 -syscall_handler (struct intr_frame *f UNUSED)
919 +copy_in (void *dst_, const void *usrc_, size_t size)
921 + uint8_t *dst = dst_;
922 + const uint8_t *usrc = usrc_;
926 + size_t chunk_size = PGSIZE - pg_ofs (usrc);
927 + if (chunk_size > size)
930 + if (!page_lock (usrc, false))
932 + memcpy (dst, usrc, chunk_size);
933 + page_unlock (usrc);
936 + usrc += chunk_size;
937 + size -= chunk_size;
941 +/* Creates a copy of user string US in kernel memory
942 + and returns it as a page that must be freed with
943 + palloc_free_page().
944 + Truncates the string at PGSIZE bytes in size.
945 + Call thread_exit() if any of the user accesses are invalid. */
947 +copy_in_string (const char *us)
953 + ks = palloc_get_page (0);
960 + upage = pg_round_down (us);
961 + if (!page_lock (upage, false))
964 + for (; us < upage + PGSIZE; us++)
966 + ks[length++] = *us;
969 + page_unlock (upage);
972 + else if (length >= PGSIZE)
973 + goto too_long_error;
976 + page_unlock (upage);
980 + page_unlock (upage);
982 + palloc_free_page (ks);
986 +/* Halt system call. */
990 - printf ("system call!\n");
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 + tid = process_execute (kfile);
1012 + palloc_free_page (kfile);
1017 +/* Wait system call. */
1019 +sys_wait (tid_t child)
1021 + return process_wait (child);
1024 +/* Create system call. */
1026 +sys_create (const char *ufile, unsigned initial_size)
1028 + char *kfile = copy_in_string (ufile);
1029 + bool ok = filesys_create (kfile, initial_size);
1030 + palloc_free_page (kfile);
1035 +/* Remove system call. */
1037 +sys_remove (const char *ufile)
1039 + char *kfile = copy_in_string (ufile);
1040 + bool ok = filesys_remove (kfile);
1041 + palloc_free_page (kfile);
1046 +/* A file descriptor, for binding a file handle to a file. */
1047 +struct file_descriptor
1049 + struct list_elem elem; /* List element. */
1050 + struct file *file; /* File. */
1051 + int handle; /* File handle. */
1054 +/* Open system call. */
1056 +sys_open (const char *ufile)
1058 + char *kfile = copy_in_string (ufile);
1059 + struct file_descriptor *fd;
1062 + fd = malloc (sizeof *fd);
1065 + fd->file = filesys_open (kfile);
1066 + if (fd->file != NULL)
1068 + struct thread *cur = thread_current ();
1069 + handle = fd->handle = cur->next_handle++;
1070 + list_push_front (&cur->fds, &fd->elem);
1076 + palloc_free_page (kfile);
1080 +/* Returns the file descriptor associated with the given handle.
1081 + Terminates the process if HANDLE is not associated with an
1083 +static struct file_descriptor *
1084 +lookup_fd (int handle)
1086 + struct thread *cur = thread_current ();
1087 + struct list_elem *e;
1089 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
1090 + e = list_next (e))
1092 + struct file_descriptor *fd;
1093 + fd = list_entry (e, struct file_descriptor, elem);
1094 + if (fd->handle == handle)
1101 +/* Filesize system call. */
1103 +sys_filesize (int handle)
1105 + struct file_descriptor *fd = lookup_fd (handle);
1108 + size = file_length (fd->file);
1113 +/* Read system call. */
1115 +sys_read (int handle, void *udst_, unsigned size)
1117 + uint8_t *udst = udst_;
1118 + struct file_descriptor *fd;
1119 + int bytes_read = 0;
1121 + /* Look up file descriptor. */
1122 + if (handle != STDIN_FILENO)
1123 + fd = lookup_fd (handle);
1127 + /* How much to read into this page? */
1128 + size_t page_left = PGSIZE - pg_ofs (udst);
1129 + size_t read_amt = size < page_left ? size : page_left;
1132 + /* Check that touching this page is okay. */
1133 + if (!page_lock (udst, true))
1136 + /* Read from file into page. */
1137 + if (handle != STDIN_FILENO)
1139 + retval = file_read (fd->file, udst, read_amt);
1142 + if (bytes_read == 0)
1146 + bytes_read += retval;
1152 + for (i = 0; i < read_amt; i++)
1153 + udst[i] = kbd_getc ();
1154 + bytes_read = read_amt;
1157 + /* Release page. */
1158 + page_unlock (udst);
1160 + /* If it was a short read we're done. */
1161 + if (retval != (off_t) read_amt)
1169 + return bytes_read;
1172 +/* Write system call. */
1174 +sys_write (int handle, void *usrc_, unsigned size)
1176 + uint8_t *usrc = usrc_;
1177 + struct file_descriptor *fd = NULL;
1178 + int bytes_written = 0;
1180 + /* Lookup up file descriptor. */
1181 + if (handle != STDOUT_FILENO)
1182 + fd = lookup_fd (handle);
1186 + /* How much bytes to write to this page? */
1187 + size_t page_left = PGSIZE - pg_ofs (usrc);
1188 + size_t write_amt = size < page_left ? size : page_left;
1191 + /* Check that we can touch this user page. */
1192 + if (!page_lock (usrc, false))
1195 + /* Do the write. */
1196 + if (handle == STDOUT_FILENO)
1198 + putbuf (usrc, write_amt);
1199 + retval = write_amt;
1202 + retval = file_write (fd->file, usrc, write_amt);
1204 + /* Release user page. */
1205 + page_unlock (usrc);
1207 + /* Handle return value. */
1210 + if (bytes_written == 0)
1211 + bytes_written = -1;
1214 + bytes_written += retval;
1216 + /* If it was a short write we're done. */
1217 + if (retval != (off_t) write_amt)
1225 + return bytes_written;
1228 +/* Seek system call. */
1230 +sys_seek (int handle, unsigned position)
1232 + if ((off_t) position >= 0)
1233 + file_seek (lookup_fd (handle)->file, position);
1237 +/* Tell system call. */
1239 +sys_tell (int handle)
1241 + return file_tell (lookup_fd (handle)->file);
1244 +/* Close system call. */
1246 +sys_close (int handle)
1248 + struct file_descriptor *fd = lookup_fd (handle);
1249 + file_close (fd->file);
1250 + list_remove (&fd->elem);
1255 +/* Binds a mapping id to a region of memory and a file. */
1258 + struct list_elem elem; /* List element. */
1259 + int handle; /* Mapping id. */
1260 + struct file *file; /* File. */
1261 + uint8_t *base; /* Start of memory mapping. */
1262 + size_t page_cnt; /* Number of pages mapped. */
1265 +/* Returns the file descriptor associated with the given handle.
1266 + Terminates the process if HANDLE is not associated with a
1267 + memory mapping. */
1268 +static struct mapping *
1269 +lookup_mapping (int handle)
1271 + struct thread *cur = thread_current ();
1272 + struct list_elem *e;
1274 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1275 + e = list_next (e))
1277 + struct mapping *m = list_entry (e, struct mapping, elem);
1278 + if (m->handle == handle)
1285 +/* Remove mapping M from the virtual address space,
1286 + writing back any pages that have changed. */
1288 +unmap (struct mapping *m)
1290 + list_remove (&m->elem);
1291 + while (m->page_cnt-- > 0)
1293 + page_deallocate (m->base);
1294 + m->base += PGSIZE;
1296 + file_close (m->file);
1300 +/* Mmap system call. */
1302 +sys_mmap (int handle, void *addr)
1304 + struct file_descriptor *fd = lookup_fd (handle);
1305 + struct mapping *m = malloc (sizeof *m);
1309 + if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
1312 + m->handle = thread_current ()->next_handle++;
1313 + m->file = file_reopen (fd->file);
1314 + if (m->file == NULL)
1321 + list_push_front (&thread_current ()->mappings, &m->elem);
1324 + length = file_length (m->file);
1325 + while (length > 0)
1327 + struct page *p = page_allocate ((uint8_t *) addr + offset, false);
1333 + p->private = false;
1334 + p->file = m->file;
1335 + p->file_offset = offset;
1336 + p->file_bytes = length >= PGSIZE ? PGSIZE : length;
1337 + offset += p->file_bytes;
1338 + length -= p->file_bytes;
1345 +/* Munmap system call. */
1347 +sys_munmap (int mapping)
1349 + unmap (lookup_mapping (mapping));
1353 +/* On thread exit, close all open files and unmap all mappings. */
1355 +syscall_exit (void)
1357 + struct thread *cur = thread_current ();
1358 + struct list_elem *e, *next;
1360 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
1362 + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
1363 + next = list_next (e);
1364 + file_close (fd->file);
1368 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1371 + struct mapping *m = list_entry (e, struct mapping, elem);
1372 + next = list_next (e);
1376 diff -u src/userprog/syscall.h~ src/userprog/syscall.h
1377 --- src/userprog/syscall.h~ 2004-09-05 22:38:45.000000000 -0700
1378 +++ src/userprog/syscall.h 2005-06-08 14:10:54.000000000 -0700
1380 #define USERPROG_SYSCALL_H
1382 void syscall_init (void);
1383 +void syscall_exit (void);
1385 #endif /* userprog/syscall.h */
1386 diff -u src/vm/frame.c~ src/vm/frame.c
1387 --- src/vm/frame.c~ 1969-12-31 16:00:00.000000000 -0800
1388 +++ src/vm/frame.c 2005-06-08 14:10:54.000000000 -0700
1390 +#include "vm/frame.h"
1392 +#include "vm/page.h"
1393 +#include "devices/timer.h"
1394 +#include "threads/init.h"
1395 +#include "threads/malloc.h"
1396 +#include "threads/mmu.h"
1397 +#include "threads/palloc.h"
1398 +#include "threads/synch.h"
1400 +static struct frame *frames;
1401 +static size_t frame_cnt;
1403 +static struct lock scan_lock;
1404 +static size_t hand;
1406 +/* Initialize the frame manager. */
1412 + lock_init (&scan_lock);
1414 + frames = malloc (sizeof *frames * ram_pages);
1415 + if (frames == NULL)
1416 + PANIC ("out of memory allocating page frames");
1418 + while ((base = palloc_get_page (PAL_USER)) != NULL)
1420 + struct frame *f = &frames[frame_cnt++];
1421 + lock_init (&f->lock);
1427 +/* Tries to allocate and lock a frame for PAGE.
1428 + Returns the frame if successful, false on failure. */
1429 +static struct frame *
1430 +try_frame_alloc_and_lock (struct page *page)
1434 + lock_acquire (&scan_lock);
1436 + /* Find a free frame. */
1437 + for (i = 0; i < frame_cnt; i++)
1439 + struct frame *f = &frames[i];
1440 + if (!lock_try_acquire (&f->lock))
1442 + if (f->page == NULL)
1445 + lock_release (&scan_lock);
1448 + lock_release (&f->lock);
1451 + /* No free frame. Find a frame to evict. */
1452 + for (i = 0; i < frame_cnt * 2; i++)
1454 + /* Get a frame. */
1455 + struct frame *f = &frames[hand];
1456 + if (++hand >= frame_cnt)
1459 + if (!lock_try_acquire (&f->lock))
1462 + if (f->page == NULL)
1465 + lock_release (&scan_lock);
1469 + if (page_accessed_recently (f->page))
1471 + lock_release (&f->lock);
1475 + lock_release (&scan_lock);
1477 + /* Evict this frame. */
1478 + if (!page_out (f->page))
1480 + lock_release (&f->lock);
1488 + lock_release (&scan_lock);
1493 +/* Tries really hard to allocate and lock a frame for PAGE.
1494 + Returns the frame if successful, false on failure. */
1496 +frame_alloc_and_lock (struct page *page)
1500 + for (try = 0; try < 3; try++)
1502 + struct frame *f = try_frame_alloc_and_lock (page);
1505 + ASSERT (lock_held_by_current_thread (&f->lock));
1508 + timer_msleep (1000);
1514 +/* Locks P's frame into memory, if it has one.
1515 + Upon return, p->frame will not change until P is unlocked. */
1517 +frame_lock (struct page *p)
1519 + /* A frame can be asynchronously removed, but never inserted. */
1520 + struct frame *f = p->frame;
1523 + lock_acquire (&f->lock);
1524 + if (f != p->frame)
1526 + lock_release (&f->lock);
1527 + ASSERT (p->frame == NULL);
1532 +/* Releases frame F for use by another page.
1533 + F must be locked for use by the current process.
1534 + Any data in F is lost. */
1536 +frame_free (struct frame *f)
1538 + ASSERT (lock_held_by_current_thread (&f->lock));
1541 + lock_release (&f->lock);
1544 +/* Unlocks frame F, allowing it to be evicted.
1545 + F must be locked for use by the current process. */
1547 +frame_unlock (struct frame *f)
1549 + ASSERT (lock_held_by_current_thread (&f->lock));
1550 + lock_release (&f->lock);
1552 diff -u src/vm/frame.h~ src/vm/frame.h
1553 --- src/vm/frame.h~ 1969-12-31 16:00:00.000000000 -0800
1554 +++ src/vm/frame.h 2005-06-08 14:10:54.000000000 -0700
1559 +#include <stdbool.h>
1560 +#include "threads/synch.h"
1562 +/* A physical frame. */
1565 + struct lock lock; /* Prevent simultaneous access. */
1566 + void *base; /* Kernel virtual base address. */
1567 + struct page *page; /* Mapped process page, if any. */
1570 +void frame_init (void);
1572 +struct frame *frame_alloc_and_lock (struct page *);
1573 +void frame_lock (struct page *);
1575 +void frame_free (struct frame *);
1576 +void frame_unlock (struct frame *);
1578 +#endif /* vm/frame.h */
1579 diff -u src/vm/page.c~ src/vm/page.c
1580 --- src/vm/page.c~ 1969-12-31 16:00:00.000000000 -0800
1581 +++ src/vm/page.c 2005-06-08 14:10:54.000000000 -0700
1583 +#include "vm/page.h"
1585 +#include <string.h>
1586 +#include "vm/frame.h"
1587 +#include "vm/swap.h"
1588 +#include "filesys/file.h"
1589 +#include "threads/malloc.h"
1590 +#include "threads/mmu.h"
1591 +#include "threads/thread.h"
1592 +#include "userprog/pagedir.h"
1594 +/* Maximum size of process stack, in bytes. */
1595 +#define STACK_MAX (1024 * 1024)
1597 +/* Destroys a page, which must be in the current process's
1598 + page table. Used as a callback for hash_destroy(). */
1600 +destroy_page (struct hash_elem *p_, void *aux UNUSED)
1602 + struct page *p = hash_entry (p_, struct page, hash_elem);
1605 + frame_free (p->frame);
1609 +/* Destroys the current process's page table. */
1613 + struct hash *h = thread_current ()->pages;
1615 + hash_destroy (h, destroy_page);
1618 +/* Returns the page containing the given virtual ADDRESS,
1619 + or a null pointer if no such page exists.
1620 + Allocates stack pages as necessary. */
1621 +static struct page *
1622 +page_for_addr (const void *address)
1624 + if (address < PHYS_BASE)
1627 + struct hash_elem *e;
1629 + /* Find existing page. */
1630 + p.addr = (void *) pg_round_down (address);
1631 + e = hash_find (thread_current ()->pages, &p.hash_elem);
1633 + return hash_entry (e, struct page, hash_elem);
1635 + /* No page. Expand stack? */
1636 + if (address >= PHYS_BASE - STACK_MAX
1637 + && address >= thread_current ()->user_esp - 32)
1638 + return page_allocate ((void *) address, false);
1643 +/* Locks a frame for page P and pages it in.
1644 + Returns true if successful, false on failure. */
1646 +do_page_in (struct page *p)
1648 + /* Get a frame for the page. */
1649 + p->frame = frame_alloc_and_lock (p);
1650 + if (p->frame == NULL)
1653 + /* Copy data into the frame. */
1654 + if (p->sector != (disk_sector_t) -1)
1656 + /* Get data from swap. */
1659 + else if (p->file != NULL)
1661 + /* Get data from file. */
1662 + off_t read_bytes = file_read_at (p->file, p->frame->base,
1663 + p->file_bytes, p->file_offset);
1664 + off_t zero_bytes = PGSIZE - read_bytes;
1665 + memset (p->frame->base + read_bytes, 0, zero_bytes);
1666 + if (read_bytes != p->file_bytes)
1667 + printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
1668 + read_bytes, p->file_bytes);
1672 + /* Provide all-zero page. */
1673 + memset (p->frame->base, 0, PGSIZE);
1679 +/* Faults in the page containing FAULT_ADDR.
1680 + Returns true if successful, false on failure. */
1682 +page_in (void *fault_addr)
1687 + /* Can't handle page faults without a hash table. */
1688 + if (thread_current ()->pages == NULL)
1691 + p = page_for_addr (fault_addr);
1696 + if (p->frame == NULL)
1698 + if (!do_page_in (p))
1701 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1703 + /* Install frame into page table. */
1704 + success = pagedir_set_page (thread_current ()->pagedir, p->addr,
1705 + p->frame->base, !p->read_only);
1707 + /* Release frame. */
1708 + frame_unlock (p->frame);
1714 + P must have a locked frame.
1715 + Return true if successful, false on failure. */
1717 +page_out (struct page *p)
1722 + ASSERT (p->frame != NULL);
1723 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1725 + /* Mark page not present in page table, forcing accesses by the
1726 + process to fault. This must happen before checking the
1727 + dirty bit, to prevent a race with the process dirtying the
1729 + pagedir_clear_page (p->thread->pagedir, p->addr);
1731 + /* Has the frame been modified? */
1732 + dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
1734 + /* Write frame contents to disk if necessary. */
1735 + if (p->file != NULL)
1740 + ok = swap_out (p);
1742 + ok = file_write_at (p->file, p->frame->base, p->file_bytes,
1743 + p->file_offset) == p->file_bytes;
1749 + ok = swap_out (p);
1752 + //memset (p->frame->base, 0xcc, PGSIZE);
1758 +/* Returns true if page P's data has been accessed recently,
1760 + P must have a frame locked into memory. */
1762 +page_accessed_recently (struct page *p)
1764 + bool was_accessed;
1766 + ASSERT (p->frame != NULL);
1767 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1769 + was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
1771 + pagedir_set_accessed (p->thread->pagedir, p->addr, false);
1772 + return was_accessed;
1775 +/* Adds a mapping for user virtual address VADDR to the page hash
1776 + table. Fails if VADDR is already mapped or if memory
1777 + allocation fails. */
1779 +page_allocate (void *vaddr, bool read_only)
1781 + struct thread *t = thread_current ();
1782 + struct page *p = malloc (sizeof *p);
1785 + p->addr = pg_round_down (vaddr);
1787 + p->read_only = read_only;
1788 + p->private = !read_only;
1792 + p->sector = (disk_sector_t) -1;
1795 + p->file_offset = 0;
1796 + p->file_bytes = 0;
1798 + p->thread = thread_current ();
1800 + if (hash_insert (t->pages, &p->hash_elem) != NULL)
1802 + /* Already mapped. */
1810 +/* Evicts the page containing address VADDR
1811 + and removes it from the page table. */
1813 +page_deallocate (void *vaddr)
1815 + struct page *p = page_for_addr (vaddr);
1816 + ASSERT (p != NULL);
1820 + struct frame *f = p->frame;
1821 + if (p->file && !p->private)
1825 + hash_delete (thread_current ()->pages, &p->hash_elem);
1829 +/* Returns a hash value for the page that E refers to. */
1831 +page_hash (const struct hash_elem *e, void *aux UNUSED)
1833 + const struct page *p = hash_entry (e, struct page, hash_elem);
1834 + return ((uintptr_t) p->addr) >> PGBITS;
1837 +/* Returns true if page A precedes page B. */
1839 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
1842 + const struct page *a = hash_entry (a_, struct page, hash_elem);
1843 + const struct page *b = hash_entry (b_, struct page, hash_elem);
1845 + return a->addr < b->addr;
1848 +/* Tries to lock the page containing ADDR into physical memory.
1849 + If WILL_WRITE is true, the page must be writeable;
1850 + otherwise it may be read-only.
1851 + Returns true if successful, false on failure. */
1853 +page_lock (const void *addr, bool will_write)
1855 + struct page *p = page_for_addr (addr);
1856 + if (p == NULL || (p->read_only && will_write))
1860 + if (p->frame == NULL)
1861 + return (do_page_in (p)
1862 + && pagedir_set_page (thread_current ()->pagedir, p->addr,
1863 + p->frame->base, !p->read_only));
1868 +/* Unlocks a page locked with page_lock(). */
1870 +page_unlock (const void *addr)
1872 + struct page *p = page_for_addr (addr);
1873 + ASSERT (p != NULL);
1874 + frame_unlock (p->frame);
1876 diff -u src/vm/page.h~ src/vm/page.h
1877 --- src/vm/page.h~ 1969-12-31 16:00:00.000000000 -0800
1878 +++ src/vm/page.h 2005-06-08 14:10:54.000000000 -0700
1884 +#include "devices/disk.h"
1885 +#include "filesys/off_t.h"
1886 +#include "threads/synch.h"
1888 +/* Virtual page. */
1891 + /* Immutable members. */
1892 + void *addr; /* User virtual address. */
1893 + bool read_only; /* Read-only page? */
1894 + struct thread *thread; /* Owning thread. */
1896 + /* Accessed only in owning process context. */
1897 + struct hash_elem hash_elem; /* struct thread `pages' hash element. */
1899 + /* Set only in owning process context with frame->frame_lock held.
1900 + Cleared only with scan_lock and frame->frame_lock held. */
1901 + struct frame *frame; /* Page frame. */
1903 + /* Swap information, protected by frame->frame_lock. */
1904 + disk_sector_t sector; /* Starting sector of swap area, or -1. */
1906 + /* Memory-mapped file information, protected by frame->frame_lock. */
1907 + bool private; /* False to write back to file,
1908 + true to write back to swap. */
1909 + struct file *file; /* File. */
1910 + off_t file_offset; /* Offset in file. */
1911 + off_t file_bytes; /* Bytes to read/write, 1...PGSIZE. */
1914 +void page_exit (void);
1916 +struct page *page_allocate (void *, bool read_only);
1917 +void page_deallocate (void *vaddr);
1919 +bool page_in (void *fault_addr);
1920 +bool page_out (struct page *);
1921 +bool page_accessed_recently (struct page *);
1923 +bool page_lock (const void *, bool will_write);
1924 +void page_unlock (const void *);
1926 +hash_hash_func page_hash;
1927 +hash_less_func page_less;
1929 +#endif /* vm/page.h */
1930 diff -u src/vm/swap.c~ src/vm/swap.c
1931 --- src/vm/swap.c~ 1969-12-31 16:00:00.000000000 -0800
1932 +++ src/vm/swap.c 2005-06-08 14:10:54.000000000 -0700
1934 +#include "vm/swap.h"
1935 +#include <bitmap.h>
1938 +#include "vm/frame.h"
1939 +#include "vm/page.h"
1940 +#include "devices/disk.h"
1941 +#include "threads/mmu.h"
1942 +#include "threads/synch.h"
1944 +/* The swap disk. */
1945 +static struct disk *swap_disk;
1947 +/* Used swap pages. */
1948 +static struct bitmap *swap_bitmap;
1950 +/* Protects swap_bitmap. */
1951 +static struct lock swap_lock;
1953 +/* Number of sectors per page. */
1954 +#define PAGE_SECTORS (PGSIZE / DISK_SECTOR_SIZE)
1956 +/* Sets up swap. */
1960 + swap_disk = disk_get (1, 1);
1961 + if (swap_disk == NULL)
1963 + printf ("no swap disk--swap disabled\n");
1964 + swap_bitmap = bitmap_create (0);
1967 + swap_bitmap = bitmap_create (disk_size (swap_disk) / PAGE_SECTORS);
1968 + if (swap_bitmap == NULL)
1969 + PANIC ("couldn't create swap bitmap");
1970 + lock_init (&swap_lock);
1973 +/* Swaps in page P, which must have a locked frame
1974 + (and be swapped out). */
1976 +swap_in (struct page *p)
1980 + ASSERT (p->frame != NULL);
1981 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
1982 + ASSERT (p->sector != (disk_sector_t) -1);
1984 + for (i = 0; i < PAGE_SECTORS; i++)
1985 + disk_read (swap_disk, p->sector + i,
1986 + p->frame->base + i * DISK_SECTOR_SIZE);
1987 + bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
1988 + p->sector = (disk_sector_t) -1;
1991 +/* Swaps out page P, which must have a locked frame. */
1993 +swap_out (struct page *p)
1998 + ASSERT (p->frame != NULL);
1999 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
2001 + lock_acquire (&swap_lock);
2002 + slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
2003 + lock_release (&swap_lock);
2004 + if (slot == BITMAP_ERROR)
2007 + p->sector = slot * PAGE_SECTORS;
2008 + for (i = 0; i < PAGE_SECTORS; i++)
2009 + disk_write (swap_disk, p->sector + i,
2010 + p->frame->base + i * DISK_SECTOR_SIZE);
2012 + p->private = false;
2014 + p->file_offset = 0;
2015 + p->file_bytes = 0;
2019 diff -u src/vm/swap.h~ src/vm/swap.h
2020 --- src/vm/swap.h~ 1969-12-31 16:00:00.000000000 -0800
2021 +++ src/vm/swap.h 2005-06-08 14:10:54.000000000 -0700
2024 +#define VM_SWAP_H 1
2026 +#include <stdbool.h>
2029 +void swap_init (void);
2030 +void swap_in (struct page *);
2031 +bool swap_out (struct page *);
2033 +#endif /* vm/swap.h */