1 Index: src/Makefile.build
2 diff -u src/Makefile.build~ src/Makefile.build
3 --- src/Makefile.build~
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/file.c # Some file.
15 filesys_SRC = filesys/filesys.c # Filesystem core.
16 @@ -62,6 +64,7 @@ filesys_SRC += filesys/file.c # Files.
17 filesys_SRC += filesys/directory.c # Directories.
18 filesys_SRC += filesys/inode.c # File headers.
19 filesys_SRC += filesys/fsutil.c # Utilities.
20 +filesys_SRC += filesys/cache.c # Cache.
22 SOURCES = $(foreach dir,$(KERNEL_SUBDIRS),$($(dir)_SRC))
23 OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES)))
24 Index: src/devices/timer.c
25 diff -u src/devices/timer.c~ src/devices/timer.c
26 --- src/devices/timer.c~
27 +++ src/devices/timer.c
28 @@ -23,6 +23,9 @@ static volatile int64_t ticks;
29 Initialized by timer_calibrate(). */
30 static unsigned loops_per_tick;
32 +/* Threads waiting in timer_sleep(). */
33 +static struct list wait_list;
35 static intr_handler_func timer_interrupt;
36 static bool too_many_loops (unsigned loops);
37 static void busy_wait (int64_t loops);
38 @@ -43,6 +46,8 @@ timer_init (void)
39 outb (0x40, count >> 8);
41 intr_register_ext (0x20, timer_interrupt, "8254 Timer");
43 + list_init (&wait_list);
46 /* Calibrates loops_per_tick, used to implement brief delays. */
47 @@ -87,15 +92,36 @@ timer_elapsed (int64_t then)
48 return timer_ticks () - then;
51 +/* Compares two threads based on their wake-up times. */
53 +compare_threads_by_wakeup_time (const struct list_elem *a_,
54 + const struct list_elem *b_,
57 + const struct thread *a = list_entry (a_, struct thread, timer_elem);
58 + const struct thread *b = list_entry (b_, struct thread, timer_elem);
60 + return a->wakeup_time < b->wakeup_time;
63 /* Suspends execution for approximately TICKS timer ticks. */
65 timer_sleep (int64_t ticks)
67 - int64_t start = timer_ticks ();
68 + struct thread *t = thread_current ();
70 + /* Schedule our wake-up time. */
71 + t->wakeup_time = timer_ticks () + ticks;
73 + /* Atomically insert the current thread into the wait list. */
74 ASSERT (intr_get_level () == INTR_ON);
75 - while (timer_elapsed (start) < ticks)
78 + list_insert_ordered (&wait_list, &t->timer_elem,
79 + compare_threads_by_wakeup_time, NULL);
83 + sema_down (&t->timer_sema);
86 /* Suspends execution for approximately MS milliseconds. */
87 @@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
92 + while (!list_empty (&wait_list))
94 + struct thread *t = list_entry (list_front (&wait_list),
95 + struct thread, timer_elem);
96 + if (ticks < t->wakeup_time)
98 + sema_up (&t->timer_sema);
99 + list_pop_front (&wait_list);
103 /* Returns true if LOOPS iterations waits for more than one timer
104 Index: src/filesys/Make.vars
105 diff -u src/filesys/Make.vars~ src/filesys/Make.vars
106 --- src/filesys/Make.vars~
107 +++ src/filesys/Make.vars
108 @@ -6,7 +6,7 @@ TEST_SUBDIRS = tests/userprog tests/file
109 GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm
111 # Uncomment the lines below to enable VM.
112 -#os.dsk: DEFINES += -DVM
113 -#KERNEL_SUBDIRS += vm
114 -#TEST_SUBDIRS += tests/vm
115 -#GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
116 +os.dsk: DEFINES += -DVM
117 +KERNEL_SUBDIRS += vm
118 +TEST_SUBDIRS += tests/vm
119 +GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
120 Index: src/filesys/cache.c
121 diff -u src/filesys/cache.c~ src/filesys/cache.c
122 --- src/filesys/cache.c~
123 +++ src/filesys/cache.c
125 +#include "filesys/cache.h"
128 +#include "filesys/filesys.h"
129 +#include "devices/disk.h"
130 +#include "devices/timer.h"
131 +#include "threads/malloc.h"
132 +#include "threads/synch.h"
133 +#include "threads/thread.h"
135 +#define INVALID_SECTOR ((disk_sector_t) -1)
137 +/* A cached block. */
140 + /* Locking to prevent eviction. */
141 + struct lock block_lock; /* Protects fields in group. */
142 + struct condition no_readers_or_writers; /* readers == 0 && writers == 0 */
143 + struct condition no_writers; /* writers == 0 */
144 + int readers, read_waiters; /* # of readers, # waiting to read. */
145 + int writers, write_waiters; /* # of writers (<= 1), # waiting to write. */
147 + /* Sector number. INVALID_SECTOR indicates a free cache block.
149 + Changing from free to allocated requires cache_sync.
151 + Changing from allocated to free requires block_lock, block
152 + must be up-to-date and not dirty, and no one may be
154 + disk_sector_t sector;
156 + /* Is data[] correct?
157 + Requires write lock or data_lock. */
160 + /* Does data[] need to be written back to disk?
161 + Valid only when up-to-date.
162 + Requires read lock or write lock or data_lock. */
166 + Access to data[] requires up-to-date and read or write lock.
167 + Bringing up-to-date requires write lock or data_lock. */
168 + struct lock data_lock; /* Protects fields in group. */
169 + uint8_t data[DISK_SECTOR_SIZE]; /* Disk data. */
173 +#define CACHE_CNT 64
174 +struct cache_block cache[CACHE_CNT];
178 + Required to allocate a cache block to a sector, to prevent a
179 + single sector being allocated two different cache blocks.
181 + Required to search the cache for a sector, to prevent the
182 + sector from being added while the search is ongoing.
185 +struct lock cache_sync;
187 +/* Cache eviction hand.
188 + Protected by cache_sync. */
189 +static int hand = 0;
191 +static void flushd_init (void);
192 +static void readaheadd_init (void);
193 +static void readaheadd_submit (disk_sector_t sector);
195 +/* Initializes cache. */
201 + lock_init (&cache_sync);
202 + for (i = 0; i < CACHE_CNT; i++)
204 + struct cache_block *b = &cache[i];
205 + lock_init (&b->block_lock);
206 + cond_init (&b->no_readers_or_writers);
207 + cond_init (&b->no_writers);
208 + b->readers = b->read_waiters = 0;
209 + b->writers = b->write_waiters = 0;
210 + b->sector = INVALID_SECTOR;
211 + lock_init (&b->data_lock);
215 + readaheadd_init ();
218 +/* Flushes cache to disk. */
224 + for (i = 0; i < CACHE_CNT; i++)
226 + struct cache_block *b = &cache[i];
227 + disk_sector_t sector;
229 + lock_acquire (&b->block_lock);
230 + sector = b->sector;
231 + lock_release (&b->block_lock);
233 + if (sector == INVALID_SECTOR)
236 + b = cache_lock (sector, EXCLUSIVE);
237 + if (b->up_to_date && b->dirty)
239 + disk_write (filesys_disk, b->sector, b->data);
246 +/* Locks the given SECTOR into the cache and returns the cache
248 + If TYPE is EXCLUSIVE, then the block returned will be locked
249 + only by the caller. The calling thread must not already
250 + have any lock on the block.
251 + If TYPE is NON_EXCLUSIVE, then block returned may be locked by
252 + any number of other callers. The calling thread may already
253 + have any number of non-exclusive locks on the block. */
254 +struct cache_block *
255 +cache_lock (disk_sector_t sector, enum lock_type type)
260 + lock_acquire (&cache_sync);
262 + /* Is the block already in-cache? */
263 + for (i = 0; i < CACHE_CNT; i++)
265 + /* Skip any blocks that don't hold SECTOR. */
266 + struct cache_block *b = &cache[i];
267 + lock_acquire (&b->block_lock);
268 + if (b->sector != sector)
270 + lock_release (&b->block_lock);
273 + lock_release (&cache_sync);
275 + /* Get read or write lock. */
276 + if (type == NON_EXCLUSIVE)
278 + /* Lock for read. */
280 + if (b->writers || b->write_waiters)
282 + cond_wait (&b->no_writers, &b->block_lock);
283 + } while (b->writers);
289 + /* Lock for write. */
290 + b->write_waiters++;
291 + if (b->readers || b->read_waiters || b->writers)
293 + cond_wait (&b->no_readers_or_writers, &b->block_lock);
294 + } while (b->readers || b->writers);
296 + b->write_waiters--;
298 + lock_release (&b->block_lock);
300 + /* Our sector should have been pinned in the cache while we
301 + were waiting. Make sure. */
302 + ASSERT (b->sector == sector);
307 + /* Not in cache. Find empty slot.
308 + We hold cache_sync. */
309 + for (i = 0; i < CACHE_CNT; i++)
311 + struct cache_block *b = &cache[i];
312 + lock_acquire (&b->block_lock);
313 + if (b->sector == INVALID_SECTOR)
315 + /* Drop block_lock, which is no longer needed because
316 + this is the only code that allocates free blocks,
317 + and we still have cache_sync.
319 + We can't drop cache_sync yet because someone else
320 + might try to allocate this same block (or read from
321 + it) while we're still initializing the block. */
322 + lock_release (&b->block_lock);
324 + b->sector = sector;
325 + b->up_to_date = false;
326 + ASSERT (b->readers == 0);
327 + ASSERT (b->writers == 0);
328 + if (type == NON_EXCLUSIVE)
332 + lock_release (&cache_sync);
335 + lock_release (&b->block_lock);
338 + /* No empty slots. Evict something.
339 + We hold cache_sync. */
340 + for (i = 0; i < CACHE_CNT; i++)
342 + struct cache_block *b = &cache[hand];
343 + if (++hand >= CACHE_CNT)
346 + /* Try to grab exclusive write access to block. */
347 + lock_acquire (&b->block_lock);
348 + if (b->readers || b->writers || b->read_waiters || b->write_waiters)
350 + lock_release (&b->block_lock);
354 + lock_release (&b->block_lock);
356 + lock_release (&cache_sync);
358 + /* Write block to disk if dirty. */
359 + if (b->up_to_date && b->dirty)
361 + disk_write (filesys_disk, b->sector, b->data);
365 + /* Remove block from cache, if possible: someone might have
366 + started waiting on it while the lock was released. */
367 + lock_acquire (&b->block_lock);
369 + if (!b->read_waiters && !b->write_waiters)
371 + /* No one is waiting for it, so we can free it. */
372 + b->sector = INVALID_SECTOR;
376 + /* There is a waiter. Give it the block. */
377 + if (b->read_waiters)
378 + cond_broadcast (&b->no_writers, &b->block_lock);
380 + cond_signal (&b->no_readers_or_writers, &b->block_lock);
382 + lock_release (&b->block_lock);
388 + /* Wait for cache contention to die down. */
389 + lock_release (&cache_sync);
390 + timer_msleep (1000);
394 +/* Bring block B up-to-date, by reading it from disk if
395 + necessary, and return a pointer to its data.
396 + The caller must have an exclusive or non-exclusive lock on
399 +cache_read (struct cache_block *b)
401 + lock_acquire (&b->data_lock);
402 + if (!b->up_to_date)
404 + disk_read (filesys_disk, b->sector, b->data);
405 + b->up_to_date = true;
408 + lock_release (&b->data_lock);
413 +/* Zero out block B, without reading it from disk, and return a
414 + pointer to the zeroed data.
415 + The caller must have an exclusive lock on B. */
417 +cache_zero (struct cache_block *b)
419 + ASSERT (b->writers);
420 + memset (b->data, 0, DISK_SECTOR_SIZE);
421 + b->up_to_date = true;
427 +/* Marks block B as dirty, so that it will be written back to
428 + disk before eviction.
429 + The caller must have a read or write lock on B,
430 + and B must be up-to-date. */
432 +cache_dirty (struct cache_block *b)
434 + ASSERT (b->up_to_date);
439 + If B is no longer locked by any thread, then it becomes a
440 + candidate for immediate eviction. */
442 +cache_unlock (struct cache_block *b)
444 + lock_acquire (&b->block_lock);
447 + ASSERT (b->writers == 0);
448 + if (--b->readers == 0)
449 + cond_signal (&b->no_readers_or_writers, &b->block_lock);
451 + else if (b->writers)
453 + ASSERT (b->readers == 0);
454 + ASSERT (b->writers == 1);
456 + if (b->read_waiters)
457 + cond_broadcast (&b->no_writers, &b->block_lock);
459 + cond_signal (&b->no_readers_or_writers, &b->block_lock);
463 + lock_release (&b->block_lock);
466 +/* If SECTOR is in the cache, evicts it immediately without
467 + writing it back to disk (even if dirty).
468 + The block must be entirely unused. */
470 +cache_free (disk_sector_t sector)
474 + lock_acquire (&cache_sync);
475 + for (i = 0; i < CACHE_CNT; i++)
477 + struct cache_block *b = &cache[i];
479 + lock_acquire (&b->block_lock);
480 + if (b->sector == sector)
482 + lock_release (&cache_sync);
484 + /* Only invalidate the block if it's unused. That
485 + should be the normal case, but it could be part of a
486 + read-ahead (in readaheadd()) or write-behind (in
488 + if (b->readers == 0 && b->read_waiters == 0
489 + && b->writers == 0 && b->write_waiters == 0)
490 + b->sector = INVALID_SECTOR;
492 + lock_release (&b->block_lock);
495 + lock_release (&b->block_lock);
497 + lock_release (&cache_sync);
501 +cache_readahead (disk_sector_t sector)
503 + readaheadd_submit (sector);
508 +static void flushd (void *aux);
510 +/* Initializes flush daemon. */
514 + thread_create ("flushd", PRI_MIN, flushd, NULL);
517 +/* Flush daemon thread. */
519 +flushd (void *aux UNUSED)
523 + timer_msleep (30 * 1000);
528 +/* A block to read ahead. */
529 +struct readahead_block
531 + struct list_elem list_elem; /* readahead_list element. */
532 + disk_sector_t sector; /* Sector to read. */
535 +/* Protects readahead_list.
536 + Monitor lock for readahead_list_nonempty. */
537 +static struct lock readahead_lock;
539 +/* Signaled when a block is added to readahead_list. */
540 +static struct condition readahead_list_nonempty;
542 +/* List of blocks for read-ahead. */
543 +static struct list readahead_list;
545 +static void readaheadd (void *aux);
547 +/* Initialize read-ahead daemon. */
549 +readaheadd_init (void)
551 + lock_init (&readahead_lock);
552 + cond_init (&readahead_list_nonempty);
553 + list_init (&readahead_list);
554 + thread_create ("readaheadd", PRI_MIN, readaheadd, NULL);
557 +/* Adds SECTOR to the read-ahead queue. */
559 +readaheadd_submit (disk_sector_t sector)
561 + /* Allocate readahead block. */
562 + struct readahead_block *block = malloc (sizeof *block);
565 + block->sector = sector;
567 + /* Add block to list. */
568 + lock_acquire (&readahead_lock);
569 + list_push_back (&readahead_list, &block->list_elem);
570 + cond_signal (&readahead_list_nonempty, &readahead_lock);
571 + lock_release (&readahead_lock);
574 +/* Read-ahead daemon. */
576 +readaheadd (void *aux UNUSED)
580 + struct readahead_block *ra_block;
581 + struct cache_block *cache_block;
583 + /* Get readahead block from list. */
584 + lock_acquire (&readahead_lock);
585 + while (list_empty (&readahead_list))
586 + cond_wait (&readahead_list_nonempty, &readahead_lock);
587 + ra_block = list_entry (list_pop_front (&readahead_list),
588 + struct readahead_block, list_elem);
589 + lock_release (&readahead_lock);
591 + /* Read block into cache. */
592 + cache_block = cache_lock (ra_block->sector, NON_EXCLUSIVE);
593 + cache_read (cache_block);
594 + cache_unlock (cache_block);
598 Index: src/filesys/cache.h
599 diff -u src/filesys/cache.h~ src/filesys/cache.h
600 --- src/filesys/cache.h~
601 +++ src/filesys/cache.h
603 +#ifndef FILESYS_CACHE_H
604 +#define FILESYS_CACHE_H
606 +#include "devices/disk.h"
608 +/* Type of block lock. */
611 + NON_EXCLUSIVE, /* Any number of lockers. */
612 + EXCLUSIVE /* Only one locker. */
615 +void cache_init (void);
616 +void cache_flush (void);
617 +struct cache_block *cache_lock (disk_sector_t, enum lock_type);
618 +void *cache_read (struct cache_block *);
619 +void *cache_zero (struct cache_block *);
620 +void cache_dirty (struct cache_block *);
621 +void cache_unlock (struct cache_block *);
622 +void cache_free (disk_sector_t);
623 +void cache_readahead (disk_sector_t);
625 +#endif /* filesys/cache.h */
626 Index: src/filesys/directory.c
627 diff -u src/filesys/directory.c~ src/filesys/directory.c
628 --- src/filesys/directory.c~
629 +++ src/filesys/directory.c
633 +#include "filesys/free-map.h"
634 #include "filesys/filesys.h"
635 #include "filesys/inode.h"
636 @@ -21,12 +21,39 @@ struct dir_entry
637 bool in_use; /* In use or free? */
640 -/* Creates a directory with space for ENTRY_CNT entries in the
641 - given SECTOR. Returns true if successful, false on failure. */
642 +/* Creates a directory in the given SECTOR.
643 + The directory's parent is in PARENT_SECTOR.
644 + Returns inode of created directory if successful,
645 + null pointer on faiilure.
646 + On failure, SECTOR is released in the free map. */
649 -dir_create (disk_sector_t sector, size_t entry_cnt)
650 +dir_create (disk_sector_t sector, disk_sector_t parent_sector)
652 - return inode_create (sector, entry_cnt * sizeof (struct dir_entry));
653 + struct inode *inode = inode_create (sector, DIR_INODE);
656 + struct dir_entry entries[2];
658 + memset (entries, 0, sizeof entries);
661 + entries[0].inode_sector = sector;
662 + strlcpy (entries[0].name, ".", sizeof entries[0].name);
663 + entries[0].in_use = true;
666 + entries[1].inode_sector = parent_sector;
667 + strlcpy (entries[1].name, "..", sizeof entries[1].name);
668 + entries[1].in_use = true;
670 + if (inode_write_at (inode, entries, sizeof entries, 0) != sizeof entries)
672 + inode_remove (inode);
673 + inode_close (inode);
680 /* Opens and returns the directory for the given INODE, of which
681 @@ -35,7 +59,7 @@ struct dir *
682 dir_open (struct inode *inode)
684 struct dir *dir = calloc (1, sizeof *dir);
685 - if (inode != NULL && dir != NULL)
686 + if (inode != NULL && dir != NULL && inode_get_type (inode) == DIR_INODE)
690 @@ -84,10 +108,8 @@ dir_get_inode (struct dir *dir)
693 /* Searches DIR for a file with the given NAME.
694 - If successful, returns true, sets *EP to the directory entry
695 - if EP is non-null, and sets *OFSP to the byte offset of the
696 - directory entry if OFSP is non-null.
697 - otherwise, returns false and ignores EP and OFSP. */
698 + If successful, returns the file's entry;
699 + otherwise, returns a null pointer. */
701 lookup (const struct dir *dir, const char *name,
702 struct dir_entry *ep, off_t *ofsp)
703 @@ -120,15 +142,16 @@ dir_lookup (const struct dir *dir, const
704 struct inode **inode)
709 ASSERT (dir != NULL);
710 ASSERT (name != NULL);
712 - if (lookup (dir, name, &e, NULL))
713 - *inode = inode_open (e.inode_sector);
716 + inode_lock (dir->inode);
717 + ok = lookup (dir, name, &e, NULL);
718 + inode_unlock (dir->inode);
720 + *inode = ok ? inode_open (e.inode_sector) : NULL;
721 return *inode != NULL;
724 @@ -149,10 +172,11 @@ dir_add (struct dir *dir, const char *na
725 ASSERT (name != NULL);
727 /* Check NAME for validity. */
728 - if (*name == '\0' || strlen (name) > NAME_MAX)
729 + if (*name == '\0' || strchr (name, '/') || strlen (name) > NAME_MAX)
732 /* Check that NAME is not in use. */
733 + inode_lock (dir->inode);
734 if (lookup (dir, name, NULL, NULL))
737 @@ -175,6 +199,7 @@ dir_add (struct dir *dir, const char *na
738 success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
741 + inode_unlock (dir->inode);
745 @@ -192,13 +217,37 @@ dir_remove (struct dir *dir, const char
746 ASSERT (dir != NULL);
747 ASSERT (name != NULL);
749 + if (!strcmp (name, ".") || !strcmp (name, ".."))
752 /* Find directory entry. */
753 + inode_lock (dir->inode);
754 if (!lookup (dir, name, &e, &ofs))
758 inode = inode_open (e.inode_sector);
762 + /* Verify that it is not an in-use or non-empty directory. */
763 + if (inode_get_type (inode) == DIR_INODE)
765 + struct dir_entry e2;
768 + if (inode_open_cnt (inode) != 1)
771 + inode_lock (inode);
772 + for (pos = 0; inode_read_at (inode, &e2, sizeof e2, pos) == sizeof e2;
774 + if (e2.in_use && strcmp (e2.name, ".") && strcmp (e2.name, ".."))
776 + inode_unlock (inode);
779 + inode_unlock (inode);
782 /* Erase directory entry. */
783 @@ -211,6 +241,7 @@ dir_remove (struct dir *dir, const char
787 + inode_unlock (dir->inode);
791 @@ -223,14 +254,17 @@ dir_readdir (struct dir *dir, char name[
795 + inode_lock (dir->inode);
796 while (inode_read_at (dir->inode, &e, sizeof e, dir->pos) == sizeof e)
798 dir->pos += sizeof e;
800 + if (e.in_use && strcmp (e.name, ".") && strcmp (e.name, ".."))
802 + inode_unlock (dir->inode);
803 strlcpy (name, e.name, NAME_MAX + 1);
807 + inode_unlock (dir->inode);
810 Index: src/filesys/directory.h
811 diff -u src/filesys/directory.h~ src/filesys/directory.h
812 --- src/filesys/directory.h~
813 +++ src/filesys/directory.h
817 /* Opening and closing directories. */
818 -bool dir_create (disk_sector_t sector, size_t entry_cnt);
819 +struct inode *dir_create (disk_sector_t sector, disk_sector_t parent_sector);
820 struct dir *dir_open (struct inode *);
821 struct dir *dir_open_root (void);
822 struct dir *dir_reopen (struct dir *);
823 Index: src/filesys/file.c
824 diff -u src/filesys/file.c~ src/filesys/file.c
825 --- src/filesys/file.c~
826 +++ src/filesys/file.c
828 #include "filesys/file.h"
830 +#include "filesys/free-map.h"
831 #include "filesys/inode.h"
832 #include "threads/malloc.h"
833 @@ -11,6 +11,24 @@ struct file
834 bool deny_write; /* Has file_deny_write() been called? */
837 +/* Creates a file in the given SECTOR,
838 + initially LENGTH bytes long.
839 + Returns inode for the file on success, null pointer on failure.
840 + On failure, SECTOR is released in the free map. */
842 +file_create (disk_sector_t sector, off_t length)
844 + struct inode *inode = inode_create (sector, FILE_INODE);
845 + if (inode != NULL && length > 0
846 + && inode_write_at (inode, "", 1, length - 1) != 1)
848 + inode_remove (inode);
849 + inode_close (inode);
855 /* Opens a file for the given INODE, of which it takes ownership,
856 and returns the new file. Returns a null pointer if an
857 allocation fails or if INODE is null. */
858 @@ -18,7 +34,7 @@ struct file *
859 file_open (struct inode *inode)
861 struct file *file = calloc (1, sizeof *file);
862 - if (inode != NULL && file != NULL)
863 + if (inode != NULL && file != NULL && inode_get_type (inode) == FILE_INODE)
867 Index: src/filesys/file.h
868 diff -u src/filesys/file.h~ src/filesys/file.h
869 --- src/filesys/file.h~
870 +++ src/filesys/file.h
872 #ifndef FILESYS_FILE_H
873 #define FILESYS_FILE_H
875 +#include <stdbool.h>
876 +#include "devices/disk.h"
877 #include "filesys/off_t.h"
881 /* Opening and closing files. */
882 +struct inode *file_create (disk_sector_t sector, off_t length);
883 struct file *file_open (struct inode *);
884 struct file *file_reopen (struct file *);
885 void file_close (struct file *);
886 Index: src/filesys/filesys.c
887 diff -u src/filesys/filesys.c~ src/filesys/filesys.c
888 --- src/filesys/filesys.c~
889 +++ src/filesys/filesys.c
894 +#include "filesys/cache.h"
895 #include "filesys/file.h"
896 #include "filesys/free-map.h"
897 #include "filesys/inode.h"
898 #include "filesys/directory.h"
899 #include "devices/disk.h"
900 +#include "threads/thread.h"
902 /* The disk that contains the file system. */
903 struct disk *filesys_disk;
904 @@ -23,6 +25,7 @@ filesys_init (bool format)
905 PANIC ("hd0:1 (hdb) not present, file system initialization failed");
912 @@ -37,6 +40,130 @@ void
919 +/* Extracts a file name part from *SRCP into PART,
920 + and updates *SRCP so that the next call will return the next
922 + Returns 1 if successful, 0 at end of string, -1 for a too-long
925 +get_next_part (char part[NAME_MAX], const char **srcp)
927 + const char *src = *srcp;
930 + /* Skip leading slashes.
931 + If it's all slashes, we're done. */
932 + while (*src == '/')
937 + /* Copy up to NAME_MAX character from SRC to DST.
938 + Add null terminator. */
939 + while (*src != '/' && *src != '\0')
941 + if (dst < part + NAME_MAX)
949 + /* Advance source pointer. */
954 +/* Resolves relative or absolute file NAME.
955 + Returns true if successful, false on failure.
956 + Stores the directory corresponding to the name into *DIRP,
957 + and the file name part into BASE_NAME. */
959 +resolve_name_to_entry (const char *name,
960 + struct dir **dirp, char base_name[NAME_MAX + 1])
962 + struct dir *dir = NULL;
963 + struct inode *inode;
965 + char part[NAME_MAX + 1], next_part[NAME_MAX + 1];
968 + /* Find starting directory. */
969 + if (name[0] == '/' || thread_current ()->wd == NULL)
970 + dir = dir_open_root ();
972 + dir = dir_reopen (thread_current ()->wd);
976 + /* Get first name part. */
978 + if (get_next_part (part, &cp) <= 0)
981 + /* As long as another part follows the current one,
982 + traverse down another directory. */
983 + while ((ok = get_next_part (next_part, &cp)) > 0)
985 + if (!dir_lookup (dir, part, &inode))
989 + dir = dir_open (inode);
993 + strlcpy (part, next_part, NAME_MAX + 1);
998 + /* Return our results. */
1000 + strlcpy (base_name, part, NAME_MAX + 1);
1004 + /* Return failure. */
1007 + base_name[0] = '\0';
1011 +/* Resolves relative or absolute file NAME to an inode.
1012 + Returns an inode if successful, or a null pointer on failure.
1013 + The caller is responsible for closing the returned inode. */
1014 +static struct inode *
1015 +resolve_name_to_inode (const char *name)
1017 + if (name[0] == '/' && name[strspn (name, "/")] == '\0')
1019 + /* The name represents the root directory.
1020 + There's no name part at all, so resolve_name_to_entry()
1021 + would reject it entirely.
1022 + Special case it. */
1023 + return inode_open (ROOT_DIR_SECTOR);
1028 + char base_name[NAME_MAX + 1];
1030 + if (resolve_name_to_entry (name, &dir, base_name))
1032 + struct inode *inode;
1033 + dir_lookup (dir, base_name, &inode);
1042 /* Creates a file named NAME with the given INITIAL_SIZE.
1043 @@ -44,16 +171,32 @@ filesys_done (void)
1044 Fails if a file named NAME already exists,
1045 or if internal memory allocation fails. */
1047 -filesys_create (const char *name, off_t initial_size)
1048 +filesys_create (const char *name, off_t initial_size, enum inode_type type)
1050 - disk_sector_t inode_sector = 0;
1051 - struct dir *dir = dir_open_root ();
1052 - bool success = (dir != NULL
1053 - && free_map_allocate (1, &inode_sector)
1054 - && inode_create (inode_sector, initial_size)
1055 - && dir_add (dir, name, inode_sector));
1056 - if (!success && inode_sector != 0)
1057 - free_map_release (inode_sector, 1);
1059 + char base_name[NAME_MAX + 1];
1060 + disk_sector_t inode_sector;
1062 + bool success = (resolve_name_to_entry (name, &dir, base_name)
1063 + && free_map_allocate (&inode_sector));
1066 + struct inode *inode;
1067 + if (type == FILE_INODE)
1068 + inode = file_create (inode_sector, initial_size);
1070 + inode = dir_create (inode_sector,
1071 + inode_get_inumber (dir_get_inode (dir)));
1072 + if (inode != NULL)
1074 + success = dir_add (dir, base_name, inode_sector);
1076 + inode_remove (inode);
1077 + inode_close (inode);
1085 @@ -64,17 +199,10 @@ filesys_create (const char *name, off_t
1087 Fails if no file named NAME exists,
1088 or if an internal memory allocation fails. */
1091 filesys_open (const char *name)
1093 - struct dir *dir = dir_open_root ();
1094 - struct inode *inode = NULL;
1097 - dir_lookup (dir, name, &inode);
1100 - return file_open (inode);
1101 + return resolve_name_to_inode (name);
1104 /* Deletes the file named NAME.
1105 @@ -84,12 +212,35 @@ filesys_open (const char *name)
1107 filesys_remove (const char *name)
1109 - struct dir *dir = dir_open_root ();
1110 - bool success = dir != NULL && dir_remove (dir, name);
1113 + char base_name[NAME_MAX + 1];
1116 + if (resolve_name_to_entry (name, &dir, base_name))
1118 + success = dir_remove (dir, base_name);
1126 +/* Change current directory to NAME.
1127 + Return true if successful, false on failure. */
1129 +filesys_chdir (const char *name)
1131 + struct dir *dir = dir_open (resolve_name_to_inode (name));
1134 + dir_close (thread_current ()->wd);
1135 + thread_current ()->wd = dir;
1142 static void must_succeed_function (int, bool) NO_INLINE;
1143 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
1144 @@ -155,9 +306,18 @@ static void
1147 + struct inode *inode;
1148 printf ("Formatting file system...");
1150 + /* Set up free map. */
1152 - if (!dir_create (ROOT_DIR_SECTOR, 16))
1154 + /* Set up root directory. */
1155 + inode = dir_create (ROOT_DIR_SECTOR, ROOT_DIR_SECTOR);
1156 + if (inode == NULL)
1157 PANIC ("root directory creation failed");
1158 + inode_close (inode);
1164 Index: src/filesys/filesys.h
1165 diff -u src/filesys/filesys.h~ src/filesys/filesys.h
1166 --- src/filesys/filesys.h~
1167 +++ src/filesys/filesys.h
1170 #include <stdbool.h>
1171 #include "filesys/off_t.h"
1172 +#include "filesys/inode.h"
1174 /* Sectors of system file inodes. */
1175 #define FREE_MAP_SECTOR 0 /* Free map file inode sector. */
1176 @@ -13,9 +14,10 @@ extern struct disk *filesys_disk;
1178 void filesys_init (bool format);
1179 void filesys_done (void);
1180 -bool filesys_create (const char *name, off_t initial_size);
1181 -struct file *filesys_open (const char *name);
1182 +bool filesys_create (const char *name, off_t initial_size, enum inode_type);
1183 +struct inode *filesys_open (const char *name);
1184 bool filesys_remove (const char *name);
1185 +bool filesys_chdir (const char *name);
1187 void filesys_self_test (void);
1189 Index: src/filesys/free-map.c
1190 diff -u src/filesys/free-map.c~ src/filesys/free-map.c
1191 --- src/filesys/free-map.c~
1192 +++ src/filesys/free-map.c
1195 #include "filesys/file.h"
1196 #include "filesys/filesys.h"
1197 -#include "filesys/inode.h"
1198 +#include "threads/synch.h"
1200 static struct file *free_map_file; /* Free map file. */
1201 static struct bitmap *free_map; /* Free map, one bit per disk sector. */
1202 +static struct lock free_map_lock; /* Mutual exclusion. */
1204 /* Initializes the free map. */
1206 free_map_init (void)
1208 + lock_init (&free_map_lock);
1210 free_map = bitmap_create (disk_size (filesys_disk));
1211 if (free_map == NULL)
1212 PANIC ("bitmap creation failed--disk is too large");
1213 @@ -19,33 +22,32 @@ free_map_init (void)
1214 bitmap_mark (free_map, ROOT_DIR_SECTOR);
1217 -/* Allocates CNT consecutive sectors from the free map and stores
1218 - the first into *SECTORP.
1219 - Returns true if successful, false if all sectors were
1220 +/* Allocates a sector from the free map and stores it into
1222 + Return true if successful, false if all sectors were
1225 -free_map_allocate (size_t cnt, disk_sector_t *sectorp)
1226 +free_map_allocate (disk_sector_t *sectorp)
1228 - disk_sector_t sector = bitmap_scan_and_flip (free_map, 0, cnt, false);
1229 - if (sector != BITMAP_ERROR
1230 - && free_map_file != NULL
1231 - && !bitmap_write (free_map, free_map_file))
1233 - bitmap_set_multiple (free_map, sector, cnt, false);
1234 - sector = BITMAP_ERROR;
1236 - if (sector != BITMAP_ERROR)
1239 + lock_acquire (&free_map_lock);
1240 + sector = bitmap_scan_and_flip (free_map, 0, 1, false);
1241 + lock_release (&free_map_lock);
1243 + if (sector != BITMAP_ERROR)
1245 return sector != BITMAP_ERROR;
1248 -/* Makes CNT sectors starting at SECTOR available for use. */
1249 +/* Makes SECTOR available for use. */
1251 -free_map_release (disk_sector_t sector, size_t cnt)
1252 +free_map_release (disk_sector_t sector)
1254 - ASSERT (bitmap_all (free_map, sector, cnt));
1255 - bitmap_set_multiple (free_map, sector, cnt, false);
1256 - bitmap_write (free_map, free_map_file);
1257 + lock_acquire (&free_map_lock);
1258 + ASSERT (bitmap_test (free_map, sector));
1259 + bitmap_reset (free_map, sector);
1260 + lock_release (&free_map_lock);
1263 /* Opens the free map file and reads it from disk. */
1264 @@ -63,6 +65,8 @@ free_map_open (void)
1266 free_map_close (void)
1268 + if (!bitmap_write (free_map, free_map_file))
1269 + PANIC ("can't write free map");
1270 file_close (free_map_file);
1273 @@ -72,5 +76,9 @@ void
1274 free_map_create (void)
1276 + struct inode *inode;
1279 - if (!inode_create (FREE_MAP_SECTOR, bitmap_file_size (free_map)))
1280 + inode = file_create (FREE_MAP_SECTOR, 0);
1281 + if (inode == NULL)
1282 PANIC ("free map creation failed");
1283 + inode_close (inode);
1285 /* Write bitmap to file. */
1286 Index: src/filesys/free-map.h
1287 diff -u src/filesys/free-map.h~ src/filesys/free-map.h
1288 --- src/filesys/free-map.h~
1289 +++ src/filesys/free-map.h
1290 @@ -11,7 +11,7 @@ void free_map_create (void);
1291 void free_map_open (void);
1292 void free_map_close (void);
1294 -bool free_map_allocate (size_t, disk_sector_t *);
1295 -void free_map_release (disk_sector_t, size_t);
1296 +bool free_map_allocate (disk_sector_t *);
1297 +void free_map_release (disk_sector_t);
1299 #endif /* filesys/free-map.h */
1300 Index: src/filesys/fsutil.c
1301 diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c
1302 --- src/filesys/fsutil.c~
1303 +++ src/filesys/fsutil.c
1304 @@ -38,7 +38,7 @@ fsutil_cat (char **argv)
1307 printf ("Printing '%s' to the console...\n", file_name);
1308 - file = filesys_open (file_name);
1309 + file = file_open (filesys_open (file_name));
1311 PANIC ("%s: open failed", file_name);
1312 buffer = palloc_get_page (PAL_ASSERT);
1313 @@ -110,9 +110,9 @@ fsutil_put (char **argv)
1314 PANIC ("%s: invalid file size %d", file_name, size);
1316 /* Create destination file. */
1317 - if (!filesys_create (file_name, size))
1318 + if (!filesys_create (file_name, size, FILE_INODE))
1319 PANIC ("%s: create failed", file_name);
1320 - dst = filesys_open (file_name);
1321 + dst = file_open (filesys_open (file_name));
1323 PANIC ("%s: open failed", file_name);
1325 @@ -162,7 +162,7 @@ fsutil_get (char **argv)
1326 PANIC ("couldn't allocate buffer");
1328 /* Open source file. */
1329 - src = filesys_open (file_name);
1330 + src = file_open (filesys_open (file_name));
1332 PANIC ("%s: open failed", file_name);
1333 size = file_length (src);
1334 Index: src/filesys/inode.c
1335 diff -u src/filesys/inode.c~ src/filesys/inode.c
1336 --- src/filesys/inode.c~
1337 +++ src/filesys/inode.c
1339 #include "filesys/inode.h"
1340 +#include <bitmap.h>
1346 +#include "filesys/cache.h"
1347 #include "filesys/filesys.h"
1348 #include "filesys/free-map.h"
1349 #include "threads/malloc.h"
1350 +#include "threads/synch.h"
1352 /* Identifies an inode. */
1353 #define INODE_MAGIC 0x494e4f44
1355 +#define DIRECT_CNT 123
1356 +#define INDIRECT_CNT 1
1357 +#define DBL_INDIRECT_CNT 1
1358 +#define SECTOR_CNT (DIRECT_CNT + INDIRECT_CNT + DBL_INDIRECT_CNT)
1360 +#define PTRS_PER_SECTOR ((off_t) (DISK_SECTOR_SIZE / sizeof (disk_sector_t)))
1361 +#define INODE_SPAN ((DIRECT_CNT \
1362 + + PTRS_PER_SECTOR * INDIRECT_CNT \
1363 + + PTRS_PER_SECTOR * PTRS_PER_SECTOR * DBL_INDIRECT_CNT) \
1364 + * DISK_SECTOR_SIZE)
1367 Must be exactly DISK_SECTOR_SIZE bytes long. */
1370 - disk_sector_t start; /* First data sector. */
1371 + disk_sector_t sectors[SECTOR_CNT]; /* Sectors. */
1372 + enum inode_type type; /* FILE_INODE or DIR_INODE. */
1373 off_t length; /* File size in bytes. */
1374 unsigned magic; /* Magic number. */
1375 - uint32_t unused[125]; /* Not used. */
1378 /* Returns the number of sectors to allocate for an inode SIZE
1379 @@ -35,74 +50,59 @@ struct inode
1380 disk_sector_t sector; /* Sector number of disk location. */
1381 int open_cnt; /* Number of openers. */
1382 bool removed; /* True if deleted, false otherwise. */
1383 + struct lock lock; /* Protects the inode. */
1385 + /* Denying writes. */
1386 + struct lock deny_write_lock; /* Protects members below. */
1387 + struct condition no_writers_cond; /* Signaled when no writers. */
1388 int deny_write_cnt; /* 0: writes ok, >0: deny writes. */
1389 - struct inode_disk data; /* Inode content. */
1390 + int writer_cnt; /* Number of writers. */
1393 -/* Returns the disk sector that contains byte offset POS within
1395 - Returns -1 if INODE does not contain data for a byte at offset
1397 -static disk_sector_t
1398 -byte_to_sector (const struct inode *inode, off_t pos)
1400 - ASSERT (inode != NULL);
1401 - if (pos < inode->data.length)
1402 - return inode->data.start + pos / DISK_SECTOR_SIZE;
1407 /* List of open inodes, so that opening a single inode twice
1408 returns the same `struct inode'. */
1409 static struct list open_inodes;
1411 +/* Controls access to open_inodes list. */
1412 +static struct lock open_inodes_lock;
1414 +static void deallocate_inode (const struct inode *);
1416 /* Initializes the inode module. */
1420 list_init (&open_inodes);
1421 + lock_init (&open_inodes_lock);
1424 -/* Initializes an inode with LENGTH bytes of data and
1425 - writes the new inode to sector SECTOR on the file system
1427 - Returns true if successful.
1428 - Returns false if memory or disk allocation fails. */
1430 -inode_create (disk_sector_t sector, off_t length)
1431 +/* Initializes an inode of the given TYPE, writes the new inode
1432 + to sector SECTOR on the file system disk, and returns the
1433 + inode thus created. Returns a null pointer if unsuccessful,
1434 + in which case SECTOR is released in the free map. */
1436 +inode_create (disk_sector_t sector, enum inode_type type)
1438 - struct inode_disk *disk_inode = NULL;
1439 - bool success = false;
1440 + struct cache_block *block;
1441 + struct inode_disk *disk_inode;
1442 + struct inode *inode;
1444 - ASSERT (length >= 0);
1445 + block = cache_lock (sector, EXCLUSIVE);
1447 /* If this assertion fails, the inode structure is not exactly
1448 one sector in size, and you should fix that. */
1449 ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);
1450 + disk_inode = cache_zero (block);
1451 + disk_inode->type = type;
1452 + disk_inode->length = 0;
1453 + disk_inode->magic = INODE_MAGIC;
1454 + cache_dirty (block);
1455 + cache_unlock (block);
1457 - disk_inode = calloc (1, sizeof *disk_inode);
1458 - if (disk_inode != NULL)
1460 - size_t sectors = bytes_to_sectors (length);
1461 - disk_inode->length = length;
1462 - disk_inode->magic = INODE_MAGIC;
1463 - if (free_map_allocate (sectors, &disk_inode->start))
1465 - disk_write (filesys_disk, sector, disk_inode);
1468 - static char zeros[DISK_SECTOR_SIZE];
1471 - for (i = 0; i < sectors; i++)
1472 - disk_write (filesys_disk, disk_inode->start + i, zeros);
1476 - free (disk_inode);
1479 + inode = inode_open (sector);
1480 + if (inode == NULL)
1481 + free_map_release (sector);
1485 /* Reads an inode from SECTOR
1486 @@ -115,29 +110,35 @@ inode_open (disk_sector_t sector)
1487 struct inode *inode;
1489 /* Check whether this inode is already open. */
1490 + lock_acquire (&open_inodes_lock);
1491 for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
1494 inode = list_entry (e, struct inode, elem);
1495 if (inode->sector == sector)
1497 - inode_reopen (inode);
1499 + inode->open_cnt++;
1504 /* Allocate memory. */
1505 inode = malloc (sizeof *inode);
1511 list_push_front (&open_inodes, &inode->elem);
1512 inode->sector = sector;
1513 inode->open_cnt = 1;
1514 + lock_init (&inode->lock);
1515 inode->deny_write_cnt = 0;
1516 + lock_init (&inode->deny_write_lock);
1517 + cond_init (&inode->no_writers_cond);
1518 inode->removed = false;
1519 - disk_read (filesys_disk, inode->sector, &inode->data);
1522 + lock_release (&open_inodes_lock);
1526 @@ -146,9 +147,24 @@ struct inode *
1527 inode_reopen (struct inode *inode)
1530 - inode->open_cnt++;
1532 + lock_acquire (&open_inodes_lock);
1533 + inode->open_cnt++;
1534 + lock_release (&open_inodes_lock);
1539 +/* Returns the type of INODE. */
1541 +inode_get_type (const struct inode *inode)
1543 + struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1544 + struct inode_disk *disk_inode = cache_read (inode_block);
1545 + enum inode_type type = disk_inode->type;
1546 + cache_unlock (inode_block);
1550 /* Returns INODE's inode number. */
1552 @@ -161,21 +183,60 @@ inode_close (struct inode *inode)
1555 /* Release resources if this was the last opener. */
1556 + lock_acquire (&open_inodes_lock);
1557 if (--inode->open_cnt == 0)
1559 /* Remove from inode list and release lock. */
1560 list_remove (&inode->elem);
1561 + lock_release (&open_inodes_lock);
1563 /* Deallocate blocks if removed. */
1566 - free_map_release (inode->sector, 1);
1567 - free_map_release (inode->data.start,
1568 - bytes_to_sectors (inode->data.length));
1570 + deallocate_inode (inode);
1575 + lock_release (&open_inodes_lock);
1578 +/* Deallocates SECTOR and anything it points to recursively.
1579 + LEVEL is 2 if SECTOR is doubly indirect,
1580 + or 1 if SECTOR is indirect,
1581 + or 0 if SECTOR is a data sector. */
1583 +deallocate_recursive (disk_sector_t sector, int level)
1587 + struct cache_block *block = cache_lock (sector, EXCLUSIVE);
1588 + disk_sector_t *pointers = cache_read (block);
1590 + for (i = 0; i < PTRS_PER_SECTOR; i++)
1592 + deallocate_recursive (sector, level - 1);
1593 + cache_unlock (block);
1596 + cache_free (sector);
1597 + free_map_release (sector);
1600 +/* Deallocates the blocks allocated for INODE. */
1602 +deallocate_inode (const struct inode *inode)
1604 + struct cache_block *block = cache_lock (inode->sector, EXCLUSIVE);
1605 + struct inode_disk *disk_inode = cache_read (block);
1607 + for (i = 0; i < SECTOR_CNT; i++)
1608 + if (disk_inode->sectors[i])
1610 + int level = (i >= DIRECT_CNT) + (i >= DIRECT_CNT + INDIRECT_CNT);
1611 + deallocate_recursive (disk_inode->sectors[i], level);
1613 + cache_unlock (block);
1614 + deallocate_recursive (inode->sector, 0);
1617 /* Marks INODE to be deleted when it is closed by the last caller who
1618 @@ -187,6 +248,156 @@ inode_remove (struct inode *inode)
1619 inode->removed = true;
1622 +/* Translates SECTOR_IDX into a sequence of block indexes in
1623 + OFFSETS and sets *OFFSET_CNT to the number of offsets. */
1625 +calculate_indices (off_t sector_idx, size_t offsets[], size_t *offset_cnt)
1627 + /* Handle direct blocks. */
1628 + if (sector_idx < DIRECT_CNT)
1630 + offsets[0] = sector_idx;
1634 + sector_idx -= DIRECT_CNT;
1636 + /* Handle indirect blocks. */
1637 + if (sector_idx < PTRS_PER_SECTOR * INDIRECT_CNT)
1639 + offsets[0] = DIRECT_CNT + sector_idx / PTRS_PER_SECTOR;
1640 + offsets[1] = sector_idx % PTRS_PER_SECTOR;
1644 + sector_idx -= PTRS_PER_SECTOR * INDIRECT_CNT;
1646 + /* Handle doubly indirect blocks. */
1647 + if (sector_idx < DBL_INDIRECT_CNT * PTRS_PER_SECTOR * PTRS_PER_SECTOR)
1649 + offsets[0] = (DIRECT_CNT + INDIRECT_CNT
1650 + + sector_idx / (PTRS_PER_SECTOR * PTRS_PER_SECTOR));
1651 + offsets[1] = sector_idx / PTRS_PER_SECTOR;
1652 + offsets[2] = sector_idx % PTRS_PER_SECTOR;
1659 +/* Retrieves the data block for the given byte OFFSET in INODE,
1660 + setting *DATA_BLOCK to the block.
1661 + Returns true if successful, false on failure.
1662 + If ALLOCATE is false, then missing blocks will be successful
1663 + with *DATA_BLOCk set to a null pointer.
1664 + If ALLOCATE is true, then missing blocks will be allocated.
1665 + The block returned will be locked, normally non-exclusively,
1666 + but a newly allocated block will have an exclusive lock. */
1668 +get_data_block (struct inode *inode, off_t offset, bool allocate,
1669 + struct cache_block **data_block)
1671 + disk_sector_t this_level_sector;
1672 + size_t offsets[3];
1673 + size_t offset_cnt;
1676 + ASSERT (offset >= 0);
1678 + calculate_indices (offset / DISK_SECTOR_SIZE, offsets, &offset_cnt);
1680 + this_level_sector = inode->sector;
1683 + struct cache_block *this_level_block;
1684 + uint32_t *this_level_data;
1686 + struct cache_block *next_level_block;
1688 + /* Check whether the block for the next level is allocated. */
1689 + this_level_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1690 + this_level_data = cache_read (this_level_block);
1691 + if (this_level_data[offsets[level]] != 0)
1693 + /* Yes, it's allocated. Advance to next level. */
1694 + this_level_sector = this_level_data[offsets[level]];
1696 + if (++level == offset_cnt)
1698 + /* We hit the data block.
1700 + if ((level == 0 && offsets[level] + 1 < DIRECT_CNT)
1701 + || (level > 0 && offsets[level] + 1 < PTRS_PER_SECTOR))
1703 + uint32_t next_sector = this_level_data[offsets[level] + 1];
1704 + if (next_sector && next_sector < disk_size (filesys_disk))
1705 + cache_readahead (next_sector);
1707 + cache_unlock (this_level_block);
1709 + /* Return block. */
1710 + *data_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1713 + cache_unlock (this_level_block);
1716 + cache_unlock (this_level_block);
1718 + /* No block is allocated. Nothing is locked.
1719 + If we're not allocating new blocks, then this is
1720 + "success" (with all-zero data). */
1723 + *data_block = NULL;
1727 + /* We need to allocate a new block.
1728 + Grab an exclusive lock on this level's block so we can
1729 + insert the new block. */
1730 + this_level_block = cache_lock (this_level_sector, EXCLUSIVE);
1731 + this_level_data = cache_read (this_level_block);
1733 + /* Since we released this level's block, someone else might
1734 + have allocated the block in the meantime. Recheck. */
1735 + if (this_level_data[offsets[level]] != 0)
1737 + cache_unlock (this_level_block);
1741 + /* Allocate the new block. */
1742 + if (!free_map_allocate (&this_level_data[offsets[level]]))
1744 + cache_unlock (this_level_block);
1745 + *data_block = NULL;
1748 + cache_dirty (this_level_block);
1750 + /* Lock and clear the new block. */
1751 + next_level_block = cache_lock (this_level_data[offsets[level]],
1753 + cache_zero (next_level_block);
1755 + /* Release this level's block. No one else can access the
1756 + new block yet, because we have an exclusive lock on it. */
1757 + cache_unlock (this_level_block);
1759 + /* If this is the final level, then return the new block. */
1760 + if (level == offset_cnt - 1)
1762 + *data_block = next_level_block;
1766 + /* Otherwise, release the new block and go around again to
1767 + follow the new pointer. */
1768 + cache_unlock (next_level_block);
1772 /* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
1773 Returns the number of bytes actually read, which may be less
1774 than SIZE if an error occurs or end of file is reached. */
1775 @@ -195,13 +406,12 @@ inode_read_at (struct inode *inode, void
1777 uint8_t *buffer = buffer_;
1778 off_t bytes_read = 0;
1779 - uint8_t *bounce = NULL;
1783 - /* Disk sector to read, starting byte offset within sector. */
1784 - disk_sector_t sector_idx = byte_to_sector (inode, offset);
1785 + /* Sector to read, starting byte offset within sector, sector data. */
1786 int sector_ofs = offset % DISK_SECTOR_SIZE;
1787 + struct cache_block *block;
1789 /* Bytes left in inode, bytes left in sector, lesser of the two. */
1790 off_t inode_left = inode_length (inode) - offset;
1791 @@ -210,26 +420,16 @@ inode_read_at (struct inode *inode, void
1793 /* Number of bytes to actually copy out of this sector. */
1794 int chunk_size = size < min_left ? size : min_left;
1795 - if (chunk_size <= 0)
1796 + if (chunk_size <= 0 || !get_data_block (inode, offset, false, &block))
1799 - if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
1801 - /* Read full sector directly into caller's buffer. */
1802 - disk_read (filesys_disk, sector_idx, buffer + bytes_read);
1804 + if (block == NULL)
1805 + memset (buffer + bytes_read, 0, chunk_size);
1808 - /* Read sector into bounce buffer, then partially copy
1809 - into caller's buffer. */
1810 - if (bounce == NULL)
1812 - bounce = malloc (DISK_SECTOR_SIZE);
1813 - if (bounce == NULL)
1816 - disk_read (filesys_disk, sector_idx, bounce);
1817 - memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
1818 + const uint8_t *sector_data = cache_read (block);
1819 + memcpy (buffer + bytes_read, sector_data + sector_ofs, chunk_size);
1820 + cache_unlock (block);
1824 @@ -237,75 +437,82 @@ inode_read_at (struct inode *inode, void
1825 offset += chunk_size;
1826 bytes_read += chunk_size;
1833 +/* Extends INODE to be at least LENGTH bytes long. */
1835 +extend_file (struct inode *inode, off_t length)
1837 + if (length > inode_length (inode))
1839 + struct cache_block *inode_block = cache_lock (inode->sector, EXCLUSIVE);
1840 + struct inode_disk *disk_inode = cache_read (inode_block);
1841 + if (length > disk_inode->length)
1843 + disk_inode->length = length;
1844 + cache_dirty (inode_block);
1846 + cache_unlock (inode_block);
1850 /* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
1851 Returns the number of bytes actually written, which may be
1852 - less than SIZE if end of file is reached or an error occurs.
1853 - (Normally a write at end of file would extend the inode, but
1854 - growth is not yet implemented.) */
1855 + less than SIZE if an error occurs. */
1857 inode_write_at (struct inode *inode, const void *buffer_, off_t size,
1860 const uint8_t *buffer = buffer_;
1861 off_t bytes_written = 0;
1862 - uint8_t *bounce = NULL;
1864 - if (inode->deny_write_cnt)
1866 + /* Don't write if writes are denied. */
1867 + lock_acquire (&inode->deny_write_lock);
1868 + if (inode->deny_write_cnt)
1870 + lock_release (&inode->deny_write_lock);
1873 + inode->writer_cnt++;
1874 + lock_release (&inode->deny_write_lock);
1878 - /* Sector to write, starting byte offset within sector. */
1879 - disk_sector_t sector_idx = byte_to_sector (inode, offset);
1880 + /* Sector to write, starting byte offset within sector, sector data. */
1881 int sector_ofs = offset % DISK_SECTOR_SIZE;
1882 + struct cache_block *block;
1883 + uint8_t *sector_data;
1885 - /* Bytes left in inode, bytes left in sector, lesser of the two. */
1886 - off_t inode_left = inode_length (inode) - offset;
1887 + /* Bytes to max inode size, bytes left in sector, lesser of the two. */
1888 + off_t inode_left = INODE_SPAN - offset;
1889 int sector_left = DISK_SECTOR_SIZE - sector_ofs;
1890 int min_left = inode_left < sector_left ? inode_left : sector_left;
1892 /* Number of bytes to actually write into this sector. */
1893 int chunk_size = size < min_left ? size : min_left;
1894 - if (chunk_size <= 0)
1897 - if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
1899 - /* Write full sector directly to disk. */
1900 - disk_write (filesys_disk, sector_idx, buffer + bytes_written);
1904 - /* We need a bounce buffer. */
1905 - if (bounce == NULL)
1907 - bounce = malloc (DISK_SECTOR_SIZE);
1908 - if (bounce == NULL)
1911 + if (chunk_size <= 0 || !get_data_block (inode, offset, true, &block))
1914 - /* If the sector contains data before or after the chunk
1915 - we're writing, then we need to read in the sector
1916 - first. Otherwise we start with a sector of all zeros. */
1917 - if (sector_ofs > 0 || chunk_size < sector_left)
1918 - disk_read (filesys_disk, sector_idx, bounce);
1920 - memset (bounce, 0, DISK_SECTOR_SIZE);
1921 - memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
1922 - disk_write (filesys_disk, sector_idx, bounce);
1924 + sector_data = cache_read (block);
1925 + memcpy (sector_data + sector_ofs, buffer + bytes_written, chunk_size);
1926 + cache_dirty (block);
1927 + cache_unlock (block);
1931 offset += chunk_size;
1932 bytes_written += chunk_size;
1936 + extend_file (inode, offset);
1938 + lock_acquire (&inode->deny_write_lock);
1939 + if (--inode->writer_cnt == 0)
1940 + cond_signal (&inode->no_writers_cond, &inode->deny_write_lock);
1941 + lock_release (&inode->deny_write_lock);
1943 return bytes_written;
1945 @@ -315,8 +522,12 @@ inode_write_at (struct inode *inode, con
1947 inode_deny_write (struct inode *inode)
1949 + lock_acquire (&inode->deny_write_lock);
1950 + while (inode->writer_cnt > 0)
1951 + cond_wait (&inode->no_writers_cond, &inode->deny_write_lock);
1952 + ASSERT (inode->deny_write_cnt < inode->open_cnt);
1953 inode->deny_write_cnt++;
1954 - ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1955 + lock_release (&inode->deny_write_lock);
1958 /* Re-enables writes to INODE.
1959 @@ -325,14 +536,47 @@ inode_deny_write (struct inode *inode)
1961 inode_allow_write (struct inode *inode)
1963 + lock_acquire (&inode->deny_write_lock);
1964 ASSERT (inode->deny_write_cnt > 0);
1965 ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1966 inode->deny_write_cnt--;
1967 + lock_release (&inode->deny_write_lock);
1970 /* Returns the length, in bytes, of INODE's data. */
1972 inode_length (const struct inode *inode)
1974 - return inode->data.length;
1975 + struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1976 + struct inode_disk *disk_inode = cache_read (inode_block);
1977 + off_t length = disk_inode->length;
1978 + cache_unlock (inode_block);
1982 +/* Returns the number of openers. */
1984 +inode_open_cnt (const struct inode *inode)
1988 + lock_acquire (&open_inodes_lock);
1989 + open_cnt = inode->open_cnt;
1990 + lock_release (&open_inodes_lock);
1997 +inode_lock (struct inode *inode)
1999 + lock_acquire (&inode->lock);
2002 +/* Releases INODE's lock. */
2004 +inode_unlock (struct inode *inode)
2006 + lock_release (&inode->lock);
2008 Index: src/filesys/inode.h
2009 diff -u src/filesys/inode.h~ src/filesys/inode.h
2010 --- src/filesys/inode.h~
2011 +++ src/filesys/inode.h
2016 +/* Type of an inode. */
2019 + FILE_INODE, /* Ordinary file. */
2020 + DIR_INODE /* Directory. */
2023 void inode_init (void);
2024 -bool inode_create (disk_sector_t, off_t);
2025 +struct inode *inode_create (disk_sector_t, enum inode_type);
2026 struct inode *inode_open (disk_sector_t);
2027 struct inode *inode_reopen (struct inode *);
2028 +enum inode_type inode_get_type (const struct inode *);
2029 disk_sector_t inode_get_inumber (const struct inode *);
2030 void inode_close (struct inode *);
2031 void inode_remove (struct inode *);
2032 off_t inode_read_at (struct inode *, void *, off_t size, off_t offset);
2033 @@ -18,5 +27,8 @@ off_t inode_write_at (struct inode *, co
2034 void inode_deny_write (struct inode *);
2035 void inode_allow_write (struct inode *);
2036 off_t inode_length (const struct inode *);
2037 +int inode_open_cnt (const struct inode *);
2038 +void inode_lock (struct inode *);
2039 +void inode_unlock (struct inode *);
2041 #endif /* filesys/inode.h */
2042 Index: src/threads/init.c
2043 diff -u src/threads/init.c~ src/threads/init.c
2044 --- src/threads/init.c~
2045 +++ src/threads/init.c
2047 #include "filesys/filesys.h"
2048 #include "filesys/fsutil.h"
2050 +#include "vm/frame.h"
2051 +#include "vm/swap.h"
2053 /* Amount of physical memory, in 4 kB pages. */
2055 @@ -124,6 +126,9 @@ main (void)
2056 filesys_init (format_filesys);
2062 printf ("Boot complete.\n");
2064 /* Run actions specified on kernel command line. */
2065 Index: src/threads/interrupt.c
2066 diff -u src/threads/interrupt.c~ src/threads/interrupt.c
2067 --- src/threads/interrupt.c~
2068 +++ src/threads/interrupt.c
2069 @@ -354,6 +354,8 @@ intr_handler (struct intr_frame *frame)
2070 in_external_intr = true;
2071 yield_on_return = false;
2074 + thread_current ()->user_esp = frame->esp;
2076 /* Invoke the interrupt's handler.
2077 If there is no handler, invoke the unexpected interrupt
2078 Index: src/threads/thread.c
2079 diff -u src/threads/thread.c~ src/threads/thread.c
2080 --- src/threads/thread.c~
2081 +++ src/threads/thread.c
2083 #include "threads/vaddr.h"
2085 #include "userprog/process.h"
2086 +#include "userprog/syscall.h"
2089 /* Random value for struct thread's `magic' member.
2090 @@ -55,7 +56,8 @@ static void kernel_thread (thread_func *
2091 static void idle (void *aux UNUSED);
2092 static struct thread *running_thread (void);
2093 static struct thread *next_thread_to_run (void);
2094 -static void init_thread (struct thread *, const char *name, int priority);
2095 +static void init_thread (struct thread *, const char *name, int priority,
2097 static bool is_thread (struct thread *) UNUSED;
2098 static void *alloc_frame (struct thread *, size_t size);
2099 static void schedule (void);
2100 @@ -82,9 +84,8 @@ thread_init (void)
2102 /* Set up a thread structure for the running thread. */
2103 initial_thread = running_thread ();
2104 - init_thread (initial_thread, "main", PRI_DEFAULT);
2105 + init_thread (initial_thread, "main", PRI_DEFAULT, 0);
2106 initial_thread->status = THREAD_RUNNING;
2107 - initial_thread->tid = allocate_tid ();
2110 /* Starts preemptive thread scheduling by enabling interrupts.
2111 @@ -159,8 +160,8 @@ thread_create (const char *name, int pri
2114 /* Initialize thread. */
2115 - init_thread (t, name, priority);
2116 - tid = t->tid = allocate_tid ();
2117 + init_thread (t, name, priority, allocate_tid ());
2120 /* Stack frame for kernel_thread(). */
2121 kf = alloc_frame (t, sizeof *kf);
2122 @@ -253,16 +254,19 @@ thread_tid (void)
2126 + struct thread *t = thread_current ();
2128 ASSERT (!intr_context ());
2135 /* Just set our status to dying and schedule another process.
2136 We will be destroyed during the call to schedule_tail(). */
2138 - thread_current ()->status = THREAD_DYING;
2139 + t->status = THREAD_DYING;
2143 @@ -406,17 +410,29 @@ is_thread (struct thread *t)
2144 /* Does basic initialization of T as a blocked thread named
2147 -init_thread (struct thread *t, const char *name, int priority)
2148 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
2151 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
2152 ASSERT (name != NULL);
2154 memset (t, 0, sizeof *t);
2156 t->status = THREAD_BLOCKED;
2157 strlcpy (t->name, name, sizeof t->name);
2158 t->stack = (uint8_t *) t + PGSIZE;
2159 t->priority = priority;
2160 + t->exit_code = -1;
2161 + t->wait_status = NULL;
2162 + list_init (&t->children);
2163 + sema_init (&t->timer_sema, 0);
2164 + t->pagedir = NULL;
2166 + t->bin_file = NULL;
2167 + list_init (&t->fds);
2168 + list_init (&t->mappings);
2169 + t->next_handle = 2;
2171 t->magic = THREAD_MAGIC;
2174 Index: src/threads/thread.h
2175 diff -u src/threads/thread.h~ src/threads/thread.h
2176 --- src/threads/thread.h~
2177 +++ src/threads/thread.h
2179 #define THREADS_THREAD_H
2185 +#include "threads/synch.h"
2187 /* States in a thread's life cycle. */
2189 @@ -89,18 +91,50 @@ struct thread
2190 uint8_t *stack; /* Saved stack pointer. */
2191 int priority; /* Priority. */
2193 + /* Owned by process.c. */
2194 + int exit_code; /* Exit code. */
2195 + struct wait_status *wait_status; /* This process's completion status. */
2196 + struct list children; /* Completion status of children. */
2198 /* Shared between thread.c and synch.c. */
2199 struct list_elem elem; /* List element. */
2202 + /* Alarm clock. */
2203 + int64_t wakeup_time; /* Time to wake this thread up. */
2204 + struct list_elem timer_elem; /* Element in timer_wait_list. */
2205 + struct semaphore timer_sema; /* Semaphore. */
2207 /* Owned by userprog/process.c. */
2208 uint32_t *pagedir; /* Page directory. */
2210 + struct hash *pages; /* Page table. */
2211 + struct file *bin_file; /* The binary executable. */
2213 + /* Owned by syscall.c. */
2214 + struct list fds; /* List of file descriptors. */
2215 + struct list mappings; /* Memory-mapped files. */
2216 + int next_handle; /* Next handle value. */
2217 + void *user_esp; /* User's stack pointer. */
2218 + struct dir *wd; /* Working directory. */
2220 /* Owned by thread.c. */
2221 unsigned magic; /* Detects stack overflow. */
2224 +/* Tracks the completion of a process.
2225 + Reference held by both the parent, in its `children' list,
2226 + and by the child, in its `wait_status' pointer. */
2229 + struct list_elem elem; /* `children' list element. */
2230 + struct lock lock; /* Protects ref_cnt. */
2231 + int ref_cnt; /* 2=child and parent both alive,
2232 + 1=either child or parent alive,
2233 + 0=child and parent both dead. */
2234 + tid_t tid; /* Child thread id. */
2235 + int exit_code; /* Child exit code, if dead. */
2236 + struct semaphore dead; /* 1=child alive, 0=child dead. */
2239 /* If false (default), use round-robin scheduler.
2240 If true, use multi-level feedback queue scheduler.
2241 Controlled by kernel command-line options "-o mlfqs".
2242 Index: src/userprog/exception.c
2243 diff -u src/userprog/exception.c~ src/userprog/exception.c
2244 --- src/userprog/exception.c~
2245 +++ src/userprog/exception.c
2247 #include "userprog/gdt.h"
2248 #include "threads/interrupt.h"
2249 #include "threads/thread.h"
2250 +#include "vm/page.h"
2252 /* Number of page faults processed. */
2253 static long long page_fault_cnt;
2254 @@ -148,9 +149,14 @@ page_fault (struct intr_frame *f)
2255 write = (f->error_code & PF_W) != 0;
2256 user = (f->error_code & PF_U) != 0;
2258 - /* To implement virtual memory, delete the rest of the function
2259 - body, and replace it with code that brings in the page to
2260 - which fault_addr refers. */
2261 + /* Allow the pager to try to handle it. */
2262 + if (user && not_present)
2264 + if (!page_in (fault_addr))
2269 printf ("Page fault at %p: %s error %s page in %s context.\n",
2271 not_present ? "not present" : "rights violation",
2272 Index: src/userprog/pagedir.c
2273 diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c
2274 --- src/userprog/pagedir.c~
2275 +++ src/userprog/pagedir.c
2276 @@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd)
2277 ASSERT (pd != base_page_dir);
2278 for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
2281 - uint32_t *pt = pde_get_pt (*pde);
2284 - for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
2286 - palloc_free_page (pte_get_page (*pte));
2287 - palloc_free_page (pt);
2289 + palloc_free_page (pde_get_pt (*pde));
2290 palloc_free_page (pd);
2293 Index: src/userprog/process.c
2294 diff -u src/userprog/process.c~ src/userprog/process.c
2295 --- src/userprog/process.c~
2296 +++ src/userprog/process.c
2298 #include "threads/flags.h"
2299 #include "threads/init.h"
2300 #include "threads/interrupt.h"
2301 +#include "threads/malloc.h"
2302 #include "threads/palloc.h"
2303 #include "threads/thread.h"
2304 #include "threads/vaddr.h"
2305 +#include "vm/page.h"
2306 +#include "vm/frame.h"
2308 static thread_func execute_thread NO_RETURN;
2309 -static bool load (const char *cmdline, void (**eip) (void), void **esp);
2310 +static bool load (const char *cmd_line, void (**eip) (void), void **esp);
2312 +/* Data structure shared between process_execute() in the
2313 + invoking thread and execute_thread() in the newly invoked
2317 + const char *file_name; /* Program to load. */
2318 + struct semaphore load_done; /* "Up"ed when loading complete. */
2319 + struct wait_status *wait_status; /* Child process. */
2320 + struct dir *wd; /* Working directory. */
2321 + bool success; /* Program successfully loaded? */
2324 /* Starts a new thread running a user program loaded from
2325 FILENAME. The new thread may be scheduled (and may even exit)
2326 @@ -28,41 +43,78 @@ static bool load (const char *cmdline, v
2328 process_execute (const char *file_name)
2331 + struct dir *wd = thread_current ()->wd;
2332 + struct exec_info exec;
2333 + char thread_name[16];
2337 - /* Make a copy of FILE_NAME.
2338 - Otherwise there's a race between the caller and load(). */
2339 - fn_copy = palloc_get_page (0);
2340 - if (fn_copy == NULL)
2341 + /* Initialize exec_info. */
2342 + exec.file_name = file_name;
2343 + exec.wd = wd != NULL ? dir_reopen (wd) : dir_open_root ();
2344 + if (exec.wd == NULL)
2346 - strlcpy (fn_copy, file_name, PGSIZE);
2347 + sema_init (&exec.load_done, 0);
2349 /* Create a new thread to execute FILE_NAME. */
2350 - tid = thread_create (file_name, PRI_DEFAULT, execute_thread, fn_copy);
2351 - if (tid == TID_ERROR)
2352 - palloc_free_page (fn_copy);
2353 + strlcpy (thread_name, file_name, sizeof thread_name);
2354 + strtok_r (thread_name, " ", &save_ptr);
2355 + tid = thread_create (thread_name, PRI_DEFAULT, execute_thread, &exec);
2356 + if (tid != TID_ERROR)
2358 + sema_down (&exec.load_done);
2360 + list_push_back (&thread_current ()->children, &exec.wait_status->elem);
2364 + /* Don't close exec.wd; child process will have done so. */
2368 + dir_close (exec.wd);
2373 /* A thread function that loads a user process and starts it
2376 -execute_thread (void *file_name_)
2377 +execute_thread (void *exec_)
2379 - char *file_name = file_name_;
2380 + struct exec_info *exec = exec_;
2381 struct intr_frame if_;
2384 + thread_current ()->wd = exec->wd;
2386 /* Initialize interrupt frame and load executable. */
2387 memset (&if_, 0, sizeof if_);
2388 if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
2390 if_.eflags = FLAG_IF | FLAG_MBS;
2391 - success = load (file_name, &if_.eip, &if_.esp);
2392 + success = load (exec->file_name, &if_.eip, &if_.esp);
2394 - /* If load failed, quit. */
2395 - palloc_free_page (file_name);
2396 + /* Allocate wait_status. */
2399 + exec->wait_status = thread_current ()->wait_status
2400 + = malloc (sizeof *exec->wait_status);
2401 + success = exec->wait_status != NULL;
2404 + /* Initialize wait_status. */
2407 + lock_init (&exec->wait_status->lock);
2408 + exec->wait_status->ref_cnt = 2;
2409 + exec->wait_status->tid = thread_current ()->tid;
2410 + sema_init (&exec->wait_status->dead, 0);
2413 + /* Notify parent thread and clean up. */
2414 + exec->success = success;
2415 + sema_up (&exec->load_done);
2419 @@ -76,18 +128,47 @@ execute_thread (void *file_name_)
2423 +/* Releases one reference to CS and, if it is now unreferenced,
2426 +release_child (struct wait_status *cs)
2430 + lock_acquire (&cs->lock);
2431 + new_ref_cnt = --cs->ref_cnt;
2432 + lock_release (&cs->lock);
2434 + if (new_ref_cnt == 0)
2438 /* Waits for thread TID to die and returns its exit status. If
2439 it was terminated by the kernel (i.e. killed due to an
2440 exception), returns -1. If TID is invalid or if it was not a
2441 child of the calling process, or if process_wait() has already
2442 been successfully called for the given TID, returns -1
2443 - immediately, without waiting.
2445 - This function will be implemented in problem 2-2. For now, it
2447 + immediately, without waiting. */
2449 -process_wait (tid_t child_tid UNUSED)
2450 +process_wait (tid_t child_tid)
2452 + struct thread *cur = thread_current ();
2453 + struct list_elem *e;
2455 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
2456 + e = list_next (e))
2458 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
2459 + if (cs->tid == child_tid)
2463 + sema_down (&cs->dead);
2464 + exit_code = cs->exit_code;
2465 + release_child (cs);
2472 @@ -96,8 +177,35 @@ void
2475 struct thread *cur = thread_current ();
2476 + struct list_elem *e, *next;
2479 + printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
2481 + /* Notify parent that we're dead. */
2482 + if (cur->wait_status != NULL)
2484 + struct wait_status *cs = cur->wait_status;
2485 + cs->exit_code = cur->exit_code;
2486 + sema_up (&cs->dead);
2487 + release_child (cs);
2490 + /* Free entries of children list. */
2491 + for (e = list_begin (&cur->children); e != list_end (&cur->children);
2494 + struct wait_status *cs = list_entry (e, struct wait_status, elem);
2495 + next = list_remove (e);
2496 + release_child (cs);
2499 + /* Destroy the page hash table. */
2502 + /* Close executable (and allow writes). */
2503 + file_close (cur->bin_file);
2505 /* Destroy the current process's page directory and switch back
2506 to the kernel-only page directory. */
2508 @@ -194,7 +302,7 @@ struct Elf32_Phdr
2509 #define PF_W 2 /* Writable. */
2510 #define PF_R 4 /* Readable. */
2512 -static bool setup_stack (void **esp);
2513 +static bool setup_stack (const char *cmd_line, void **esp);
2514 static bool validate_segment (const struct Elf32_Phdr *, struct file *);
2515 static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
2516 uint32_t read_bytes, uint32_t zero_bytes,
2517 @@ -205,13 +313,15 @@ static bool load_segment (struct file *f
2518 and its initial stack pointer into *ESP.
2519 Returns true if successful, false otherwise. */
2521 -load (const char *file_name, void (**eip) (void), void **esp)
2522 +load (const char *cmd_line, void (**eip) (void), void **esp)
2524 struct thread *t = thread_current ();
2525 + char file_name[NAME_MAX + 2];
2526 struct Elf32_Ehdr ehdr;
2527 struct file *file = NULL;
2529 bool success = false;
2533 /* Allocate and activate page directory. */
2534 @@ -220,13 +330,28 @@ load (const char *file_name, void (**eip
2536 process_activate ();
2538 + /* Create page hash table. */
2539 + t->pages = malloc (sizeof *t->pages);
2540 + if (t->pages == NULL)
2542 + hash_init (t->pages, page_hash, page_less, NULL);
2544 + /* Extract file_name from command line. */
2545 + while (*cmd_line == ' ')
2547 + strlcpy (file_name, cmd_line, sizeof file_name);
2548 + cp = strchr (file_name, ' ');
2552 /* Open executable file. */
2553 - file = filesys_open (file_name);
2554 + t->bin_file = file = file_open (filesys_open (file_name));
2557 printf ("load: %s: open failed\n", file_name);
2560 + file_deny_write (file);
2562 /* Read and verify executable header. */
2563 if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
2564 @@ -301,7 +426,7 @@ load (const char *file_name, void (**eip
2568 - if (!setup_stack (esp))
2569 + if (!setup_stack (cmd_line, esp))
2572 /* Start address. */
2573 @@ -311,14 +436,11 @@ load (const char *file_name, void (**eip
2576 /* We arrive here whether the load is successful or not. */
2577 - file_close (file);
2581 /* load() helpers. */
2583 -static bool install_page (void *upage, void *kpage, bool writable);
2585 /* Checks whether PHDR describes a valid, loadable segment in
2586 FILE and returns true if so, false otherwise. */
2588 @@ -386,79 +508,127 @@ load_segment (struct file *file, off_t o
2589 ASSERT (pg_ofs (upage) == 0);
2590 ASSERT (ofs % PGSIZE == 0);
2592 - file_seek (file, ofs);
2593 while (read_bytes > 0 || zero_bytes > 0)
2595 - /* Calculate how to fill this page.
2596 - We will read PAGE_READ_BYTES bytes from FILE
2597 - and zero the final PAGE_ZERO_BYTES bytes. */
2598 size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
2599 size_t page_zero_bytes = PGSIZE - page_read_bytes;
2601 - /* Get a page of memory. */
2602 - uint8_t *kpage = palloc_get_page (PAL_USER);
2603 - if (kpage == NULL)
2604 + struct page *p = page_allocate (upage, !writable);
2608 - /* Load this page. */
2609 - if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
2611 - palloc_free_page (kpage);
2614 - memset (kpage + page_read_bytes, 0, page_zero_bytes);
2616 - /* Add the page to the process's address space. */
2617 - if (!install_page (upage, kpage, writable))
2618 + if (page_read_bytes > 0)
2620 - palloc_free_page (kpage);
2623 + p->file_offset = ofs;
2624 + p->file_bytes = page_read_bytes;
2628 read_bytes -= page_read_bytes;
2629 zero_bytes -= page_zero_bytes;
2630 + ofs += page_read_bytes;
2636 -/* Create a minimal stack by mapping a zeroed page at the top of
2637 - user virtual memory. */
2638 +/* Reverse the order of the ARGC pointers to char in ARGV. */
2640 +reverse (int argc, char **argv)
2642 + for (; argc > 1; argc -= 2, argv++)
2644 + char *tmp = argv[0];
2645 + argv[0] = argv[argc - 1];
2646 + argv[argc - 1] = tmp;
2650 +/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
2651 + page-relative stack pointer is *OFS, and then adjusts *OFS
2652 + appropriately. The bytes pushed are rounded to a 32-bit
2655 + If successful, returns a pointer to the newly pushed object.
2656 + On failure, returns a null pointer. */
2658 +push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size)
2660 + size_t padsize = ROUND_UP (size, sizeof (uint32_t));
2661 + if (*ofs < padsize)
2665 + memcpy (kpage + *ofs + (padsize - size), buf, size);
2666 + return kpage + *ofs + (padsize - size);
2669 +/* Sets up command line arguments in KPAGE, which will be mapped
2670 + to UPAGE in user space. The command line arguments are taken
2671 + from CMD_LINE, separated by spaces. Sets *ESP to the initial
2672 + stack pointer for the process. */
2674 -setup_stack (void **esp)
2675 +init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
2679 - bool success = false;
2680 + size_t ofs = PGSIZE;
2681 + char *const null = NULL;
2682 + char *cmd_line_copy;
2683 + char *karg, *saveptr;
2687 + /* Push command line string. */
2688 + cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1);
2689 + if (cmd_line_copy == NULL)
2692 - kpage = palloc_get_page (PAL_USER | PAL_ZERO);
2693 - if (kpage != NULL)
2694 + if (push (kpage, &ofs, &null, sizeof null) == NULL)
2697 + /* Parse command line into arguments
2698 + and push them in reverse order. */
2700 + for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL;
2701 + karg = strtok_r (NULL, " ", &saveptr))
2703 - success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
2707 - palloc_free_page (kpage);
2708 + void *uarg = upage + (karg - (char *) kpage);
2709 + if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
2715 + /* Reverse the order of the command line arguments. */
2716 + argv = (char **) (upage + ofs);
2717 + reverse (argc, (char **) (kpage + ofs));
2719 + /* Push argv, argc, "return address". */
2720 + if (push (kpage, &ofs, &argv, sizeof argv) == NULL
2721 + || push (kpage, &ofs, &argc, sizeof argc) == NULL
2722 + || push (kpage, &ofs, &null, sizeof null) == NULL)
2725 + /* Set initial stack pointer. */
2726 + *esp = upage + ofs;
2730 -/* Adds a mapping from user virtual address UPAGE to kernel
2731 - virtual address KPAGE to the page table.
2732 - If WRITABLE is true, the user process may modify the page;
2733 - otherwise, it is read-only.
2734 - UPAGE must not already be mapped.
2735 - KPAGE should probably be a page obtained from the user pool
2736 - with palloc_get_page().
2737 - Returns true on success, false if UPAGE is already mapped or
2738 - if memory allocation fails. */
2739 +/* Create a minimal stack for T by mapping a page at the
2740 + top of user virtual memory. Fills in the page using CMD_LINE
2741 + and sets *ESP to the stack pointer. */
2743 -install_page (void *upage, void *kpage, bool writable)
2744 +setup_stack (const char *cmd_line, void **esp)
2746 - struct thread *t = thread_current ();
2748 - /* Verify that there's not already a page at that virtual
2749 - address, then map our page there. */
2750 - return (pagedir_get_page (t->pagedir, upage) == NULL
2751 - && pagedir_set_page (t->pagedir, upage, kpage, writable));
2752 + struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
2755 + page->frame = frame_alloc_and_lock (page);
2756 + if (page->frame != NULL)
2759 + page->read_only = false;
2760 + page->private = false;
2761 + ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
2762 + frame_unlock (page->frame);
2768 Index: src/userprog/syscall.c
2769 diff -u src/userprog/syscall.c~ src/userprog/syscall.c
2770 --- src/userprog/syscall.c~
2771 +++ src/userprog/syscall.c
2773 #include "userprog/syscall.h"
2775 +#include <string.h>
2776 #include <syscall-nr.h>
2777 +#include "userprog/process.h"
2778 +#include "userprog/pagedir.h"
2779 +#include "devices/input.h"
2780 +#include "filesys/directory.h"
2781 +#include "filesys/filesys.h"
2782 +#include "filesys/file.h"
2783 +#include "threads/init.h"
2784 #include "threads/interrupt.h"
2785 +#include "threads/malloc.h"
2786 +#include "threads/palloc.h"
2787 #include "threads/thread.h"
2789 +#include "threads/vaddr.h"
2790 +#include "vm/page.h"
2793 +static int sys_halt (void);
2794 +static int sys_exit (int status);
2795 +static int sys_exec (const char *ufile);
2796 +static int sys_wait (tid_t);
2797 +static int sys_create (const char *ufile, unsigned initial_size);
2798 +static int sys_remove (const char *ufile);
2799 +static int sys_open (const char *ufile);
2800 +static int sys_filesize (int handle);
2801 +static int sys_read (int handle, void *udst_, unsigned size);
2802 +static int sys_write (int handle, void *usrc_, unsigned size);
2803 +static int sys_seek (int handle, unsigned position);
2804 +static int sys_tell (int handle);
2805 +static int sys_close (int handle);
2806 +static int sys_mmap (int handle, void *addr);
2807 +static int sys_munmap (int mapping);
2808 +static int sys_chdir (const char *udir);
2809 +static int sys_mkdir (const char *udir);
2810 +static int sys_readdir (int handle, char *name);
2811 +static int sys_isdir (int handle);
2812 +static int sys_inumber (int handle);
2814 static void syscall_handler (struct intr_frame *);
2816 +static void copy_in (void *, const void *, size_t);
2821 intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
2824 +/* System call handler. */
2826 +syscall_handler (struct intr_frame *f)
2828 + typedef int syscall_function (int, int, int);
2830 + /* A system call. */
2833 + size_t arg_cnt; /* Number of arguments. */
2834 + syscall_function *func; /* Implementation. */
2837 + /* Table of system calls. */
2838 + static const struct syscall syscall_table[] =
2840 + {0, (syscall_function *) sys_halt},
2841 + {1, (syscall_function *) sys_exit},
2842 + {1, (syscall_function *) sys_exec},
2843 + {1, (syscall_function *) sys_wait},
2844 + {2, (syscall_function *) sys_create},
2845 + {1, (syscall_function *) sys_remove},
2846 + {1, (syscall_function *) sys_open},
2847 + {1, (syscall_function *) sys_filesize},
2848 + {3, (syscall_function *) sys_read},
2849 + {3, (syscall_function *) sys_write},
2850 + {2, (syscall_function *) sys_seek},
2851 + {1, (syscall_function *) sys_tell},
2852 + {1, (syscall_function *) sys_close},
2853 + {2, (syscall_function *) sys_mmap},
2854 + {1, (syscall_function *) sys_munmap},
2855 + {1, (syscall_function *) sys_chdir},
2856 + {1, (syscall_function *) sys_mkdir},
2857 + {2, (syscall_function *) sys_readdir},
2858 + {1, (syscall_function *) sys_isdir},
2859 + {1, (syscall_function *) sys_inumber},
2862 + const struct syscall *sc;
2866 + /* Get the system call. */
2867 + copy_in (&call_nr, f->esp, sizeof call_nr);
2868 + if (call_nr >= sizeof syscall_table / sizeof *syscall_table)
2870 + sc = syscall_table + call_nr;
2872 + /* Get the system call arguments. */
2873 + ASSERT (sc->arg_cnt <= sizeof args / sizeof *args);
2874 + memset (args, 0, sizeof args);
2875 + copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt);
2877 + /* Execute the system call,
2878 + and set the return value. */
2879 + f->eax = sc->func (args[0], args[1], args[2]);
2882 +/* Copies SIZE bytes from user address USRC to kernel address
2884 + Call thread_exit() if any of the user accesses are invalid. */
2886 -syscall_handler (struct intr_frame *f UNUSED)
2887 +copy_in (void *dst_, const void *usrc_, size_t size)
2889 - printf ("system call!\n");
2890 + uint8_t *dst = dst_;
2891 + const uint8_t *usrc = usrc_;
2895 + size_t chunk_size = PGSIZE - pg_ofs (usrc);
2896 + if (chunk_size > size)
2897 + chunk_size = size;
2899 + if (!page_lock (usrc, false))
2901 + memcpy (dst, usrc, chunk_size);
2902 + page_unlock (usrc);
2904 + dst += chunk_size;
2905 + usrc += chunk_size;
2906 + size -= chunk_size;
2910 +/* Copies SIZE bytes from kernel address SRC to user address
2912 + Call thread_exit() if any of the user accesses are invalid. */
2914 +copy_out (void *udst_, const void *src_, size_t size)
2916 + uint8_t *udst = udst_;
2917 + const uint8_t *src = src_;
2921 + size_t chunk_size = PGSIZE - pg_ofs (udst);
2922 + if (chunk_size > size)
2923 + chunk_size = size;
2925 + if (!page_lock (udst, false))
2927 + memcpy (udst, src, chunk_size);
2928 + page_unlock (udst);
2930 + udst += chunk_size;
2931 + src += chunk_size;
2932 + size -= chunk_size;
2936 +/* Creates a copy of user string US in kernel memory
2937 + and returns it as a page that must be freed with
2938 + palloc_free_page().
2939 + Truncates the string at PGSIZE bytes in size.
2940 + Call thread_exit() if any of the user accesses are invalid. */
2942 +copy_in_string (const char *us)
2948 + ks = palloc_get_page (0);
2955 + upage = pg_round_down (us);
2956 + if (!page_lock (upage, false))
2959 + for (; us < upage + PGSIZE; us++)
2961 + ks[length++] = *us;
2964 + page_unlock (upage);
2967 + else if (length >= PGSIZE)
2968 + goto too_long_error;
2971 + page_unlock (upage);
2975 + page_unlock (upage);
2977 + palloc_free_page (ks);
2981 +/* Halt system call. */
2988 +/* Exit system call. */
2990 +sys_exit (int exit_code)
2992 + thread_current ()->exit_code = exit_code;
2997 +/* Exec system call. */
2999 +sys_exec (const char *ufile)
3002 + char *kfile = copy_in_string (ufile);
3004 + tid = process_execute (kfile);
3006 + palloc_free_page (kfile);
3011 +/* Wait system call. */
3013 +sys_wait (tid_t child)
3015 + return process_wait (child);
3018 +/* Create system call. */
3020 +sys_create (const char *ufile, unsigned initial_size)
3022 + char *kfile = copy_in_string (ufile);
3023 + bool ok = filesys_create (kfile, initial_size, FILE_INODE);
3024 + palloc_free_page (kfile);
3029 +/* Remove system call. */
3031 +sys_remove (const char *ufile)
3033 + char *kfile = copy_in_string (ufile);
3034 + bool ok = filesys_remove (kfile);
3035 + palloc_free_page (kfile);
3040 +/* A file descriptor, for binding a file handle to a file. */
3041 +struct file_descriptor
3043 + struct list_elem elem; /* List element. */
3044 + struct file *file; /* File. */
3045 + struct dir *dir; /* Directory. */
3046 + int handle; /* File handle. */
3049 +/* Open system call. */
3051 +sys_open (const char *ufile)
3053 + char *kfile = copy_in_string (ufile);
3054 + struct file_descriptor *fd;
3057 + fd = calloc (1, sizeof *fd);
3060 + struct inode *inode = filesys_open (kfile);
3061 + if (inode != NULL)
3063 + if (inode_get_type (inode) == FILE_INODE)
3064 + fd->file = file_open (inode);
3066 + fd->dir = dir_open (inode);
3067 + if (fd->file != NULL || fd->dir != NULL)
3069 + struct thread *cur = thread_current ();
3070 + handle = fd->handle = cur->next_handle++;
3071 + list_push_front (&cur->fds, &fd->elem);
3076 + inode_close (inode);
3081 + palloc_free_page (kfile);
3085 +/* Returns the file descriptor associated with the given handle.
3086 + Terminates the process if HANDLE is not associated with an
3088 +static struct file_descriptor *
3089 +lookup_fd (int handle)
3091 + struct thread *cur = thread_current ();
3092 + struct list_elem *e;
3094 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
3095 + e = list_next (e))
3097 + struct file_descriptor *fd;
3098 + fd = list_entry (e, struct file_descriptor, elem);
3099 + if (fd->handle == handle)
3106 +/* Returns the file descriptor associated with the given handle.
3107 + Terminates the process if HANDLE is not associated with an
3108 + open ordinary file. */
3109 +static struct file_descriptor *
3110 +lookup_file_fd (int handle)
3112 + struct file_descriptor *fd = lookup_fd (handle);
3113 + if (fd->file == NULL)
3118 +/* Returns the file descriptor associated with the given handle.
3119 + Terminates the process if HANDLE is not associated with an
3120 + open directory. */
3121 +static struct file_descriptor *
3122 +lookup_dir_fd (int handle)
3124 + struct file_descriptor *fd = lookup_fd (handle);
3125 + if (fd->dir == NULL)
3130 +/* Filesize system call. */
3132 +sys_filesize (int handle)
3134 + struct file_descriptor *fd = lookup_file_fd (handle);
3137 + size = file_length (fd->file);
3142 +/* Read system call. */
3144 +sys_read (int handle, void *udst_, unsigned size)
3146 + uint8_t *udst = udst_;
3147 + struct file_descriptor *fd;
3148 + int bytes_read = 0;
3150 + /* Look up file descriptor. */
3151 + if (handle != STDIN_FILENO)
3152 + fd = lookup_file_fd (handle);
3156 + /* How much to read into this page? */
3157 + size_t page_left = PGSIZE - pg_ofs (udst);
3158 + size_t read_amt = size < page_left ? size : page_left;
3161 + /* Check that touching this page is okay. */
3162 + if (!page_lock (udst, true))
3165 + /* Read from file into page. */
3166 + if (handle != STDIN_FILENO)
3168 + retval = file_read (fd->file, udst, read_amt);
3171 + if (bytes_read == 0)
3175 + bytes_read += retval;
3181 + for (i = 0; i < read_amt; i++)
3182 + udst[i] = input_getc ();
3183 + bytes_read = read_amt;
3186 + /* Release page. */
3187 + page_unlock (udst);
3189 + /* If it was a short read we're done. */
3190 + if (retval != (off_t) read_amt)
3198 + return bytes_read;
3201 +/* Write system call. */
3203 +sys_write (int handle, void *usrc_, unsigned size)
3205 + uint8_t *usrc = usrc_;
3206 + struct file_descriptor *fd = NULL;
3207 + int bytes_written = 0;
3209 + /* Lookup up file descriptor. */
3210 + if (handle != STDOUT_FILENO)
3211 + fd = lookup_file_fd (handle);
3215 + /* How much bytes to write to this page? */
3216 + size_t page_left = PGSIZE - pg_ofs (usrc);
3217 + size_t write_amt = size < page_left ? size : page_left;
3220 + /* Check that we can touch this user page. */
3221 + if (!page_lock (usrc, false))
3224 + /* Do the write. */
3225 + if (handle == STDOUT_FILENO)
3227 + putbuf ((char *) usrc, write_amt);
3228 + retval = write_amt;
3231 + retval = file_write (fd->file, usrc, write_amt);
3233 + /* Release user page. */
3234 + page_unlock (usrc);
3236 + /* Handle return value. */
3239 + if (bytes_written == 0)
3240 + bytes_written = -1;
3243 + bytes_written += retval;
3245 + /* If it was a short write we're done. */
3246 + if (retval != (off_t) write_amt)
3254 + return bytes_written;
3257 +/* Seek system call. */
3259 +sys_seek (int handle, unsigned position)
3261 + if ((off_t) position >= 0)
3262 + file_seek (lookup_file_fd (handle)->file, position);
3266 +/* Tell system call. */
3268 +sys_tell (int handle)
3270 + return file_tell (lookup_file_fd (handle)->file);
3273 +/* Close system call. */
3275 +sys_close (int handle)
3277 + struct file_descriptor *fd = lookup_fd (handle);
3278 + file_close (fd->file);
3279 + dir_close (fd->dir);
3280 + list_remove (&fd->elem);
3285 +/* Binds a mapping id to a region of memory and a file. */
3288 + struct list_elem elem; /* List element. */
3289 + int handle; /* Mapping id. */
3290 + struct file *file; /* File. */
3291 + uint8_t *base; /* Start of memory mapping. */
3292 + size_t page_cnt; /* Number of pages mapped. */
3295 +/* Returns the file descriptor associated with the given handle.
3296 + Terminates the process if HANDLE is not associated with a
3297 + memory mapping. */
3298 +static struct mapping *
3299 +lookup_mapping (int handle)
3301 + struct thread *cur = thread_current ();
3302 + struct list_elem *e;
3304 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
3305 + e = list_next (e))
3307 + struct mapping *m = list_entry (e, struct mapping, elem);
3308 + if (m->handle == handle)
3315 +/* Remove mapping M from the virtual address space,
3316 + writing back any pages that have changed. */
3318 +unmap (struct mapping *m)
3320 + list_remove (&m->elem);
3321 + while (m->page_cnt-- > 0)
3323 + page_deallocate (m->base);
3324 + m->base += PGSIZE;
3326 + file_close (m->file);
3330 +/* Mmap system call. */
3332 +sys_mmap (int handle, void *addr)
3334 + struct file_descriptor *fd = lookup_file_fd (handle);
3335 + struct mapping *m = malloc (sizeof *m);
3339 + if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
3342 + m->handle = thread_current ()->next_handle++;
3343 + m->file = file_reopen (fd->file);
3344 + if (m->file == NULL)
3351 + list_push_front (&thread_current ()->mappings, &m->elem);
3354 + length = file_length (m->file);
3355 + while (length > 0)
3357 + struct page *p = page_allocate ((uint8_t *) addr + offset, false);
3363 + p->private = false;
3364 + p->file = m->file;
3365 + p->file_offset = offset;
3366 + p->file_bytes = length >= PGSIZE ? PGSIZE : length;
3367 + offset += p->file_bytes;
3368 + length -= p->file_bytes;
3375 +/* Munmap system call. */
3377 +sys_munmap (int mapping)
3379 + unmap (lookup_mapping (mapping));
3383 +/* Chdir system call. */
3385 +sys_chdir (const char *udir)
3387 + char *kdir = copy_in_string (udir);
3388 + bool ok = filesys_chdir (kdir);
3389 + palloc_free_page (kdir);
3393 +/* Mkdir system call. */
3395 +sys_mkdir (const char *udir)
3397 + char *kdir = copy_in_string (udir);
3398 + bool ok = filesys_create (kdir, 0, DIR_INODE);
3399 + palloc_free_page (kdir);
3404 +/* Readdir system call. */
3406 +sys_readdir (int handle, char *uname)
3408 + struct file_descriptor *fd = lookup_dir_fd (handle);
3409 + char name[NAME_MAX + 1];
3410 + bool ok = dir_readdir (fd->dir, name);
3412 + copy_out (uname, name, strlen (name) + 1);
3416 +/* Isdir system call. */
3418 +sys_isdir (int handle)
3420 + struct file_descriptor *fd = lookup_fd (handle);
3421 + return fd->dir != NULL;
3424 +/* Inumber system call. */
3426 +sys_inumber (int handle)
3428 + struct file_descriptor *fd = lookup_fd (handle);
3429 + struct inode *inode = (fd->file
3430 + ? file_get_inode (fd->file)
3431 + : dir_get_inode (fd->dir));
3432 + return inode_get_inumber (inode);
3435 +/* On thread exit, close all open files and unmap all mappings. */
3437 +syscall_exit (void)
3439 + struct thread *cur = thread_current ();
3440 + struct list_elem *e, *next;
3442 + for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
3444 + struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
3445 + next = list_next (e);
3446 + file_close (fd->file);
3447 + dir_close (fd->dir);
3451 + for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
3454 + struct mapping *m = list_entry (e, struct mapping, elem);
3455 + next = list_next (e);
3459 + dir_close (cur->wd);
3461 Index: src/userprog/syscall.h
3462 diff -u src/userprog/syscall.h~ src/userprog/syscall.h
3463 --- src/userprog/syscall.h~
3464 +++ src/userprog/syscall.h
3466 #define USERPROG_SYSCALL_H
3468 void syscall_init (void);
3469 +void syscall_exit (void);
3471 #endif /* userprog/syscall.h */
3472 Index: src/vm/frame.c
3473 diff -u src/vm/frame.c~ src/vm/frame.c
3477 +#include "vm/frame.h"
3479 +#include "vm/page.h"
3480 +#include "devices/timer.h"
3481 +#include "threads/init.h"
3482 +#include "threads/malloc.h"
3483 +#include "threads/palloc.h"
3484 +#include "threads/synch.h"
3485 +#include "threads/vaddr.h"
3487 +static struct frame *frames;
3488 +static size_t frame_cnt;
3490 +static struct lock scan_lock;
3491 +static size_t hand;
3493 +/* Initialize the frame manager. */
3499 + lock_init (&scan_lock);
3501 + frames = malloc (sizeof *frames * ram_pages);
3502 + if (frames == NULL)
3503 + PANIC ("out of memory allocating page frames");
3505 + while ((base = palloc_get_page (PAL_USER)) != NULL)
3507 + struct frame *f = &frames[frame_cnt++];
3508 + lock_init (&f->lock);
3514 +/* Tries to allocate and lock a frame for PAGE.
3515 + Returns the frame if successful, false on failure. */
3516 +static struct frame *
3517 +try_frame_alloc_and_lock (struct page *page)
3521 + lock_acquire (&scan_lock);
3523 + /* Find a free frame. */
3524 + for (i = 0; i < frame_cnt; i++)
3526 + struct frame *f = &frames[i];
3527 + if (!lock_try_acquire (&f->lock))
3529 + if (f->page == NULL)
3532 + lock_release (&scan_lock);
3535 + lock_release (&f->lock);
3538 + /* No free frame. Find a frame to evict. */
3539 + for (i = 0; i < frame_cnt * 2; i++)
3541 + /* Get a frame. */
3542 + struct frame *f = &frames[hand];
3543 + if (++hand >= frame_cnt)
3546 + if (!lock_try_acquire (&f->lock))
3549 + if (f->page == NULL)
3552 + lock_release (&scan_lock);
3556 + if (page_accessed_recently (f->page))
3558 + lock_release (&f->lock);
3562 + lock_release (&scan_lock);
3564 + /* Evict this frame. */
3565 + if (!page_out (f->page))
3567 + lock_release (&f->lock);
3575 + lock_release (&scan_lock);
3579 +/* Tries really hard to allocate and lock a frame for PAGE.
3580 + Returns the frame if successful, false on failure. */
3582 +frame_alloc_and_lock (struct page *page)
3586 + for (try = 0; try < 3; try++)
3588 + struct frame *f = try_frame_alloc_and_lock (page);
3591 + ASSERT (lock_held_by_current_thread (&f->lock));
3594 + timer_msleep (1000);
3600 +/* Locks P's frame into memory, if it has one.
3601 + Upon return, p->frame will not change until P is unlocked. */
3603 +frame_lock (struct page *p)
3605 + /* A frame can be asynchronously removed, but never inserted. */
3606 + struct frame *f = p->frame;
3609 + lock_acquire (&f->lock);
3610 + if (f != p->frame)
3612 + lock_release (&f->lock);
3613 + ASSERT (p->frame == NULL);
3618 +/* Releases frame F for use by another page.
3619 + F must be locked for use by the current process.
3620 + Any data in F is lost. */
3622 +frame_free (struct frame *f)
3624 + ASSERT (lock_held_by_current_thread (&f->lock));
3627 + lock_release (&f->lock);
3630 +/* Unlocks frame F, allowing it to be evicted.
3631 + F must be locked for use by the current process. */
3633 +frame_unlock (struct frame *f)
3635 + ASSERT (lock_held_by_current_thread (&f->lock));
3636 + lock_release (&f->lock);
3638 Index: src/vm/frame.h
3639 diff -u src/vm/frame.h~ src/vm/frame.h
3646 +#include <stdbool.h>
3647 +#include "threads/synch.h"
3649 +/* A physical frame. */
3652 + struct lock lock; /* Prevent simultaneous access. */
3653 + void *base; /* Kernel virtual base address. */
3654 + struct page *page; /* Mapped process page, if any. */
3657 +void frame_init (void);
3659 +struct frame *frame_alloc_and_lock (struct page *);
3660 +void frame_lock (struct page *);
3662 +void frame_free (struct frame *);
3663 +void frame_unlock (struct frame *);
3665 +#endif /* vm/frame.h */
3666 Index: src/vm/page.c
3667 diff -u src/vm/page.c~ src/vm/page.c
3671 +#include "vm/page.h"
3673 +#include <string.h>
3674 +#include "vm/frame.h"
3675 +#include "vm/swap.h"
3676 +#include "filesys/file.h"
3677 +#include "threads/malloc.h"
3678 +#include "threads/thread.h"
3679 +#include "userprog/pagedir.h"
3680 +#include "threads/vaddr.h"
3682 +/* Maximum size of process stack, in bytes. */
3683 +#define STACK_MAX (1024 * 1024)
3685 +/* Destroys a page, which must be in the current process's
3686 + page table. Used as a callback for hash_destroy(). */
3688 +destroy_page (struct hash_elem *p_, void *aux UNUSED)
3690 + struct page *p = hash_entry (p_, struct page, hash_elem);
3693 + frame_free (p->frame);
3698 +/* Destroys the current process's page table. */
3702 + struct hash *h = thread_current ()->pages;
3704 + hash_destroy (h, destroy_page);
3707 +/* Returns the page containing the given virtual ADDRESS,
3708 + or a null pointer if no such page exists.
3709 + Allocates stack pages as necessary. */
3710 +static struct page *
3711 +page_for_addr (const void *address)
3713 + if (address < PHYS_BASE)
3716 + struct hash_elem *e;
3718 + /* Find existing page. */
3719 + p.addr = (void *) pg_round_down (address);
3720 + e = hash_find (thread_current ()->pages, &p.hash_elem);
3722 + return hash_entry (e, struct page, hash_elem);
3724 + /* No page. Expand stack? */
3725 + if (address >= PHYS_BASE - STACK_MAX
3726 + && address >= thread_current ()->user_esp - 32)
3727 + return page_allocate ((void *) address, false);
3732 +/* Locks a frame for page P and pages it in.
3733 + Returns true if successful, false on failure. */
3735 +do_page_in (struct page *p)
3737 + /* Get a frame for the page. */
3738 + p->frame = frame_alloc_and_lock (p);
3739 + if (p->frame == NULL)
3742 + /* Copy data into the frame. */
3743 + if (p->sector != (disk_sector_t) -1)
3745 + /* Get data from swap. */
3748 + else if (p->file != NULL)
3750 + /* Get data from file. */
3751 + off_t read_bytes = file_read_at (p->file, p->frame->base,
3752 + p->file_bytes, p->file_offset);
3753 + off_t zero_bytes = PGSIZE - read_bytes;
3754 + memset (p->frame->base + read_bytes, 0, zero_bytes);
3755 + if (read_bytes != p->file_bytes)
3756 + printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
3757 + read_bytes, p->file_bytes);
3761 + /* Provide all-zero page. */
3762 + memset (p->frame->base, 0, PGSIZE);
3768 +/* Faults in the page containing FAULT_ADDR.
3769 + Returns true if successful, false on failure. */
3771 +page_in (void *fault_addr)
3776 + /* Can't handle page faults without a hash table. */
3777 + if (thread_current ()->pages == NULL)
3780 + p = page_for_addr (fault_addr);
3785 + if (p->frame == NULL)
3787 + if (!do_page_in (p))
3790 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
3792 + /* Install frame into page table. */
3793 + success = pagedir_set_page (thread_current ()->pagedir, p->addr,
3794 + p->frame->base, !p->read_only);
3796 + /* Release frame. */
3797 + frame_unlock (p->frame);
3803 + P must have a locked frame.
3804 + Return true if successful, false on failure. */
3806 +page_out (struct page *p)
3811 + ASSERT (p->frame != NULL);
3812 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
3814 + /* Mark page not present in page table, forcing accesses by the
3815 + process to fault. This must happen before checking the
3816 + dirty bit, to prevent a race with the process dirtying the
3818 + pagedir_clear_page (p->thread->pagedir, p->addr);
3820 + /* Has the frame been modified? */
3821 + dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
3823 + /* Write frame contents to disk if necessary. */
3824 + if (p->file != NULL)
3829 + ok = swap_out (p);
3831 + ok = file_write_at (p->file, p->frame->base, p->file_bytes,
3832 + p->file_offset) == p->file_bytes;
3838 + ok = swap_out (p);
3841 + //memset (p->frame->base, 0xcc, PGSIZE);
3847 +/* Returns true if page P's data has been accessed recently,
3849 + P must have a frame locked into memory. */
3851 +page_accessed_recently (struct page *p)
3853 + bool was_accessed;
3855 + ASSERT (p->frame != NULL);
3856 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
3858 + was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
3860 + pagedir_set_accessed (p->thread->pagedir, p->addr, false);
3861 + return was_accessed;
3864 +/* Adds a mapping for user virtual address VADDR to the page hash
3865 + table. Fails if VADDR is already mapped or if memory
3866 + allocation fails. */
3868 +page_allocate (void *vaddr, bool read_only)
3870 + struct thread *t = thread_current ();
3871 + struct page *p = malloc (sizeof *p);
3874 + p->addr = pg_round_down (vaddr);
3876 + p->read_only = read_only;
3877 + p->private = !read_only;
3881 + p->sector = (disk_sector_t) -1;
3884 + p->file_offset = 0;
3885 + p->file_bytes = 0;
3887 + p->thread = thread_current ();
3889 + if (hash_insert (t->pages, &p->hash_elem) != NULL)
3891 + /* Already mapped. */
3899 +/* Evicts the page containing address VADDR
3900 + and removes it from the page table. */
3902 +page_deallocate (void *vaddr)
3904 + struct page *p = page_for_addr (vaddr);
3905 + ASSERT (p != NULL);
3909 + struct frame *f = p->frame;
3910 + if (p->file && !p->private)
3914 + hash_delete (thread_current ()->pages, &p->hash_elem);
3918 +/* Returns a hash value for the page that E refers to. */
3920 +page_hash (const struct hash_elem *e, void *aux UNUSED)
3922 + const struct page *p = hash_entry (e, struct page, hash_elem);
3923 + return ((uintptr_t) p->addr) >> PGBITS;
3926 +/* Returns true if page A precedes page B. */
3928 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
3931 + const struct page *a = hash_entry (a_, struct page, hash_elem);
3932 + const struct page *b = hash_entry (b_, struct page, hash_elem);
3934 + return a->addr < b->addr;
3937 +/* Tries to lock the page containing ADDR into physical memory.
3938 + If WILL_WRITE is true, the page must be writeable;
3939 + otherwise it may be read-only.
3940 + Returns true if successful, false on failure. */
3942 +page_lock (const void *addr, bool will_write)
3944 + struct page *p = page_for_addr (addr);
3945 + if (p == NULL || (p->read_only && will_write))
3949 + if (p->frame == NULL)
3950 + return (do_page_in (p)
3951 + && pagedir_set_page (thread_current ()->pagedir, p->addr,
3952 + p->frame->base, !p->read_only));
3957 +/* Unlocks a page locked with page_lock(). */
3959 +page_unlock (const void *addr)
3961 + struct page *p = page_for_addr (addr);
3962 + ASSERT (p != NULL);
3963 + frame_unlock (p->frame);
3965 Index: src/vm/page.h
3966 diff -u src/vm/page.h~ src/vm/page.h
3974 +#include "devices/disk.h"
3975 +#include "filesys/off_t.h"
3976 +#include "threads/synch.h"
3978 +/* Virtual page. */
3981 + /* Immutable members. */
3982 + void *addr; /* User virtual address. */
3983 + bool read_only; /* Read-only page? */
3984 + struct thread *thread; /* Owning thread. */
3986 + /* Accessed only in owning process context. */
3987 + struct hash_elem hash_elem; /* struct thread `pages' hash element. */
3989 + /* Set only in owning process context with frame->frame_lock held.
3990 + Cleared only with scan_lock and frame->frame_lock held. */
3991 + struct frame *frame; /* Page frame. */
3993 + /* Swap information, protected by frame->frame_lock. */
3994 + disk_sector_t sector; /* Starting sector of swap area, or -1. */
3996 + /* Memory-mapped file information, protected by frame->frame_lock. */
3997 + bool private; /* False to write back to file,
3998 + true to write back to swap. */
3999 + struct file *file; /* File. */
4000 + off_t file_offset; /* Offset in file. */
4001 + off_t file_bytes; /* Bytes to read/write, 1...PGSIZE. */
4004 +void page_exit (void);
4006 +struct page *page_allocate (void *, bool read_only);
4007 +void page_deallocate (void *vaddr);
4009 +bool page_in (void *fault_addr);
4010 +bool page_out (struct page *);
4011 +bool page_accessed_recently (struct page *);
4013 +bool page_lock (const void *, bool will_write);
4014 +void page_unlock (const void *);
4016 +hash_hash_func page_hash;
4017 +hash_less_func page_less;
4019 +#endif /* vm/page.h */
4020 Index: src/vm/swap.c
4021 diff -u src/vm/swap.c~ src/vm/swap.c
4025 +#include "vm/swap.h"
4026 +#include <bitmap.h>
4029 +#include "vm/frame.h"
4030 +#include "vm/page.h"
4031 +#include "devices/disk.h"
4032 +#include "threads/synch.h"
4033 +#include "threads/vaddr.h"
4035 +/* The swap disk. */
4036 +static struct disk *swap_disk;
4038 +/* Used swap pages. */
4039 +static struct bitmap *swap_bitmap;
4041 +/* Protects swap_bitmap. */
4042 +static struct lock swap_lock;
4044 +/* Number of sectors per page. */
4045 +#define PAGE_SECTORS (PGSIZE / DISK_SECTOR_SIZE)
4047 +/* Sets up swap. */
4051 + swap_disk = disk_get (1, 1);
4052 + if (swap_disk == NULL)
4054 + printf ("no swap disk--swap disabled\n");
4055 + swap_bitmap = bitmap_create (0);
4058 + swap_bitmap = bitmap_create (disk_size (swap_disk) / PAGE_SECTORS);
4059 + if (swap_bitmap == NULL)
4060 + PANIC ("couldn't create swap bitmap");
4061 + lock_init (&swap_lock);
4064 +/* Swaps in page P, which must have a locked frame
4065 + (and be swapped out). */
4067 +swap_in (struct page *p)
4071 + ASSERT (p->frame != NULL);
4072 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
4073 + ASSERT (p->sector != (disk_sector_t) -1);
4075 + for (i = 0; i < PAGE_SECTORS; i++)
4076 + disk_read (swap_disk, p->sector + i,
4077 + p->frame->base + i * DISK_SECTOR_SIZE);
4078 + bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
4079 + p->sector = (disk_sector_t) -1;
4082 +/* Swaps out page P, which must have a locked frame. */
4084 +swap_out (struct page *p)
4089 + ASSERT (p->frame != NULL);
4090 + ASSERT (lock_held_by_current_thread (&p->frame->lock));
4092 + lock_acquire (&swap_lock);
4093 + slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
4094 + lock_release (&swap_lock);
4095 + if (slot == BITMAP_ERROR)
4098 + p->sector = slot * PAGE_SECTORS;
4099 + for (i = 0; i < PAGE_SECTORS; i++)
4100 + disk_write (swap_disk, p->sector + i,
4101 + p->frame->base + i * DISK_SECTOR_SIZE);
4103 + p->private = false;
4105 + p->file_offset = 0;
4106 + p->file_bytes = 0;
4110 Index: src/vm/swap.h
4111 diff -u src/vm/swap.h~ src/vm/swap.h
4116 +#define VM_SWAP_H 1
4118 +#include <stdbool.h>
4121 +void swap_init (void);
4122 +void swap_in (struct page *);
4123 +bool swap_out (struct page *);
4125 +#endif /* vm/swap.h */