diff options
| -rw-r--r-- | src/.gitignore | 1 | ||||
| -rw-r--r-- | src/Make.config | 4 | ||||
| -rw-r--r-- | src/devices/timer.c | 49 | ||||
| -rw-r--r-- | src/examples/Makefile | 10 | ||||
| -rw-r--r-- | src/examples/args.c | 12 | ||||
| -rw-r--r-- | src/examples/create.c | 29 | ||||
| -rw-r--r-- | src/examples/read.c | 22 | ||||
| -rw-r--r-- | src/examples/wait.c | 13 | ||||
| -rw-r--r-- | src/filesys/file.c | 7 | ||||
| -rw-r--r-- | src/filesys/filesys.c | 19 | ||||
| -rw-r--r-- | src/filesys/free-map.c | 10 | ||||
| -rw-r--r-- | src/filesys/inode.c | 45 | ||||
| -rw-r--r-- | src/lib/pid_t.h | 15 | ||||
| -rw-r--r-- | src/lib/user/syscall.h | 4 | ||||
| -rw-r--r-- | src/tests/Make.tests | 2 | ||||
| -rw-r--r-- | src/tests/userprog/Make.tests | 28 | ||||
| -rw-r--r-- | src/threads/synch.c | 40 | ||||
| -rw-r--r-- | src/threads/synch.h | 17 | ||||
| -rw-r--r-- | src/threads/thread.c | 4 | ||||
| -rw-r--r-- | src/threads/thread.h | 26 | ||||
| -rw-r--r-- | src/userprog/Make.vars | 2 | ||||
| -rw-r--r-- | src/userprog/process.c | 177 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/userprog/start_pfs.sh | 4 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/userprog/start_recursor.sh | 10 | ||||
| -rw-r--r-- | src/userprog/syscall.c | 334 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/utils/backtrace | 0 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/utils/pintos-gdb | 0 | ||||
| -rwxr-xr-x[-rw-r--r--] | src/utils/pintos-mkdisk | 0 |
28 files changed, 822 insertions, 62 deletions
diff --git a/src/.gitignore b/src/.gitignore index bea5755..89ff8ee 100644 --- a/src/.gitignore +++ b/src/.gitignore @@ -1 +1,2 @@ TAGS +*.o diff --git a/src/Make.config b/src/Make.config index f5c6705..1301180 100644 --- a/src/Make.config +++ b/src/Make.config @@ -11,12 +11,12 @@ VPATH = $(SRCDIR) X86 = i.86\|pentium.*\|[pk][56]\|nexgen\|viac3\|6x86\|athlon.*\|i86pc X86_64 = x86_64 ifneq (0, $(shell expr `uname -m` : '$(X86)')) - CC = gcc + CC = gcc-4.8 LD = ld OBJCOPY = objcopy else ifneq (0, $(shell expr `uname -m` : '$(X86_64)')) - CC = gcc -m32 + CC = gcc-4.8 -m32 LD = ld -melf_i386 OBJCOPY = objcopy else diff --git a/src/devices/timer.c b/src/devices/timer.c index a4521de..aea6aa2 100644 --- a/src/devices/timer.c +++ b/src/devices/timer.c @@ -1,6 +1,7 @@ #include "devices/timer.h" #include <debug.h> #include <inttypes.h> +#include <list.h> #include <round.h> #include <stdio.h> #include "threads/interrupt.h" @@ -17,6 +18,13 @@ #error TIMER_FREQ <= 1000 recommended #endif +struct waiting_thread + { + struct list_elem elem; + struct semaphore sema; + int64_t tick_target; + }; + /* Number of timer ticks since OS booted. */ static int64_t ticks; @@ -24,6 +32,8 @@ static int64_t ticks; Initialized by timer_calibrate(). */ static unsigned loops_per_tick; +static struct list waiting_threads; + static intr_handler_func timer_interrupt; static bool too_many_loops (unsigned loops); static void busy_wait (int64_t loops); @@ -43,6 +53,8 @@ timer_init (void) outb (0x40, count & 0xff); outb (0x40, count >> 8); + list_init (&waiting_threads); + intr_register_ext (0x20, timer_interrupt, "8254 Timer"); } @@ -98,9 +110,27 @@ timer_sleep (int64_t ticks) { int64_t start = timer_ticks (); - ASSERT (intr_get_level () == INTR_ON); - while (timer_elapsed (start) < ticks) - thread_yield (); + struct waiting_thread new_waiting_thread; + new_waiting_thread.tick_target = start + ticks; + sema_init (&new_waiting_thread.sema, 0); + + // disable interrupts so the timer interrupt handler can't modify the list + enum intr_level old_level = intr_disable (); + + struct list_elem *before = list_begin (&waiting_threads); + while (before != list_end (&waiting_threads)) { + struct list_elem *next = list_next (before); + struct waiting_thread *waiting_thread = list_entry (before, struct waiting_thread, elem); + if (new_waiting_thread.tick_target < waiting_thread->tick_target) { + break; + } + before = next; + } + list_insert (before, &new_waiting_thread.elem); + + intr_set_level (old_level); + + sema_down (&new_waiting_thread.sema); } /* Suspends execution for approximately MS milliseconds. */ @@ -137,6 +167,19 @@ timer_interrupt (struct intr_frame *args UNUSED) { ticks++; thread_tick (); + + struct list_elem *e = list_begin (&waiting_threads); + while (e != list_end (&waiting_threads)) { + struct list_elem *next = list_next (e); + struct waiting_thread *waiting_thread = list_entry (e, struct waiting_thread, elem); + if (ticks >= waiting_thread->tick_target) { + sema_up (&waiting_thread->sema); + list_remove (e); + e = next; + } else { + break; + } + } } /* Returns true if LOOPS iterations waits for more than one timer diff --git a/src/examples/Makefile b/src/examples/Makefile index 8bd6ed2..6c7c09d 100644 --- a/src/examples/Makefile +++ b/src/examples/Makefile @@ -8,6 +8,16 @@ PROGS = cat cmp cp echo halt hex-dump ls mcat mcp mkdir pwd rm shell \ sumargv lab2test lab1test lab1test2 pfs pfs_reader pfs_writer dummy longrun \ child parent create-bad printf lab3test1 lab3test2 lab4test1 +PROGS += create read lab3test1 lab4test1 lab3test2 args wait + +create_SRC = create.c +read_SRC = read.c +lab3test1_SRC = lab3test1.c +lab4test1_SRC = lab4test1.c +lab3test2_SRC = lab3test2.c +args_SRC = args.c +wait_SRC = wait.c + # Added test programs printf_SRC = printf.c sumargv_SRC = sumargv.c diff --git a/src/examples/args.c b/src/examples/args.c new file mode 100644 index 0000000..643fb01 --- /dev/null +++ b/src/examples/args.c @@ -0,0 +1,12 @@ +#include <stdio.h> + +int +main (int argc, char **argv) +{ + printf ("hello\n"); + printf ("argc %p: %d\n", &argc, argc); + printf ("argv %p: %p\n", &argv, argv); + for (int i = 0; i < argc; i++) { + printf ("%d: %s\n", i, argv[i]); + } +} diff --git a/src/examples/create.c b/src/examples/create.c new file mode 100644 index 0000000..65be47d --- /dev/null +++ b/src/examples/create.c @@ -0,0 +1,29 @@ +#include <stdio.h> +#include <syscall.h> + +int +main (int argc, char *argv[]) +{ + if (create ("test", 1)) { + printf ("created file\n"); + } else { + printf ("couldn't create file\n"); + } + int fd = open ("test"); // open 2 + printf ("opened file with fd %d\n", fd); + int fd2 = open ("test"); // open 3 + printf ("opened file with fd %d\n", fd2); + close(fd); // close 2 + int fd3 = open ("test"); // open 2 + printf ("opened file with fd %d\n", fd3); + close(fd2); // close 3 + int fd4 = open ("test"); // open 3 + printf ("opened file with fd %d\n", fd4); + close(fd4); // close 3, valid + close(fd3); // close 2, valid + close(fd); // close closed 2, invalid + int fd5 = open ("test"); // open 2 + printf ("opened file with fd %d\n", fd5); + + halt (); +} diff --git a/src/examples/read.c b/src/examples/read.c new file mode 100644 index 0000000..4b50bd8 --- /dev/null +++ b/src/examples/read.c @@ -0,0 +1,22 @@ +#include <stdio.h> +#include <syscall.h> + +int +main (int argc, char *argv[]) +{ + char read_buf[16] = {}; + + int fd = open ("readme"); + if (fd == -1) { + halt (); + } + printf("opened file with fd %d\n", fd); + + int n = read (fd, read_buf, 16); + printf("read %d bytes:\n", n); + printf("###############\n"); + printf("%s\n", read_buf); + + halt(); + return 0; +} diff --git a/src/examples/wait.c b/src/examples/wait.c new file mode 100644 index 0000000..ab0ea90 --- /dev/null +++ b/src/examples/wait.c @@ -0,0 +1,13 @@ +#include <stdio.h> +#include <syscall.h> + +int +main (int argc, char **argv) +{ + printf ("hello\n"); + if (argc != 1) { + int child = exec("wait"); + printf("%d: %d\n", child, wait(child)); + } + exit(1); +} diff --git a/src/filesys/file.c b/src/filesys/file.c index d5fc10d..238806a 100644 --- a/src/filesys/file.c +++ b/src/filesys/file.c @@ -155,7 +155,12 @@ file_seek (struct file *file, off_t new_pos) { ASSERT (file != NULL); ASSERT (new_pos >= 0); - file->pos = new_pos; + off_t size = inode_length (file->inode); + if (new_pos < size) { + file->pos = new_pos; + } else { + file->pos = size; + } } /* Returns the current position in FILE as a byte offset from the diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index fedda08..d30f728 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -7,6 +7,11 @@ #include "filesys/inode.h" #include "filesys/directory.h" #include "devices/disk.h" +#include "threads/synch.h" + +/* Locks filesys_create so the same file isn't + created twice with the same name. */ +static struct lock create_lock; /* The disk that contains the file system. */ struct disk *filesys_disk; @@ -22,6 +27,8 @@ filesys_init (bool format) if (filesys_disk == NULL) PANIC ("hd0:1 (hdb) not present, file system initialization failed"); + lock_init (&create_lock); + inode_init (); free_map_init (); @@ -48,12 +55,14 @@ filesys_create (const char *name, off_t initial_size) { disk_sector_t inode_sector = 0; struct dir *dir = dir_open_root (); + lock_acquire (&create_lock); bool success = (dir != NULL - && free_map_allocate (1, &inode_sector) - && inode_create (inode_sector, initial_size) - && dir_add (dir, name, inode_sector)); - if (!success && inode_sector != 0) - free_map_release (inode_sector, 1); + && free_map_allocate (1, &inode_sector) // find sector + && inode_create (inode_sector, initial_size) // create inode pointing to sector + && dir_add (dir, name, inode_sector)); // add dir entry pointing to inode + lock_release (&create_lock); + if (!success && inode_sector != 0) // oops, we got a sector but file creation failed + free_map_release (inode_sector, 1); // so deallocate the sector dir_close (dir); return success; diff --git a/src/filesys/free-map.c b/src/filesys/free-map.c index 1cd9175..8b8aeae 100644 --- a/src/filesys/free-map.c +++ b/src/filesys/free-map.c @@ -4,8 +4,11 @@ #include "filesys/file.h" #include "filesys/filesys.h" #include "filesys/inode.h" +#include "threads/synch.h" static struct file *free_map_file; /* Free map file. */ + +static struct lock free_map_lock; static struct bitmap *free_map; /* Free map, one bit per disk sector. */ /* Initializes the free map. */ @@ -15,6 +18,7 @@ free_map_init (void) free_map = bitmap_create (disk_size (filesys_disk)); if (free_map == NULL) PANIC ("bitmap creation failed--disk is too large"); + lock_init (&free_map_lock); bitmap_mark (free_map, FREE_MAP_SECTOR); bitmap_mark (free_map, ROOT_DIR_SECTOR); } @@ -26,6 +30,7 @@ free_map_init (void) bool free_map_allocate (size_t cnt, disk_sector_t *sectorp) { + lock_acquire (&free_map_lock); disk_sector_t sector = bitmap_scan_and_flip (free_map, 0, cnt, false); if (sector != BITMAP_ERROR && free_map_file != NULL @@ -34,6 +39,7 @@ free_map_allocate (size_t cnt, disk_sector_t *sectorp) bitmap_set_multiple (free_map, sector, cnt, false); sector = BITMAP_ERROR; } + lock_release (&free_map_lock); if (sector != BITMAP_ERROR) *sectorp = sector; return sector != BITMAP_ERROR; @@ -43,9 +49,11 @@ free_map_allocate (size_t cnt, disk_sector_t *sectorp) void free_map_release (disk_sector_t sector, size_t cnt) { + lock_acquire (&free_map_lock); ASSERT (bitmap_all (free_map, sector, cnt)); bitmap_set_multiple (free_map, sector, cnt, false); bitmap_write (free_map, free_map_file); + lock_release (&free_map_lock); } /* Opens the free map file and reads it from disk. */ @@ -55,8 +63,10 @@ free_map_open (void) free_map_file = file_open (inode_open (FREE_MAP_SECTOR)); if (free_map_file == NULL) PANIC ("can't open free map"); + lock_acquire (&free_map_lock); if (!bitmap_read (free_map, free_map_file)) PANIC ("can't read free map"); + lock_release (&free_map_lock); } /* Writes the free map to disk and closes the free map file. */ diff --git a/src/filesys/inode.c b/src/filesys/inode.c index cfdcb7b..dca5432 100644 --- a/src/filesys/inode.c +++ b/src/filesys/inode.c @@ -6,6 +6,7 @@ #include "filesys/filesys.h" #include "filesys/free-map.h" #include "threads/malloc.h" +#include "threads/synch.h" /* Identifies an inode. */ #define INODE_MAGIC 0x494e4f44 @@ -31,11 +32,14 @@ bytes_to_sectors (off_t size) /* In-memory inode. */ struct inode { + struct lock lock; /* Lock for inode metadata. */ struct list_elem elem; /* Element in inode list. */ disk_sector_t sector; /* Sector number of disk location. */ int open_cnt; /* Number of openers. */ bool removed; /* True if deleted, false otherwise. */ int deny_write_cnt; /* 0: writes ok, >0: deny writes. */ + + struct rwlock rwlock; /* RwLock for inode_disk data. */ struct inode_disk data; /* Inode content. */ }; @@ -53,6 +57,9 @@ byte_to_sector (const struct inode *inode, off_t pos) return -1; } +/* Lock the open inode list since so inode_open doesn't race. */ +struct lock open_inodes_lock; + /* List of open inodes, so that opening a single inode twice returns the same `struct inode'. */ static struct list open_inodes; @@ -62,6 +69,7 @@ void inode_init (void) { list_init (&open_inodes); + lock_init (&open_inodes_lock); } /* Initializes an inode with LENGTH bytes of data and @@ -114,6 +122,7 @@ inode_open (disk_sector_t sector) struct list_elem *e; struct inode *inode; + lock_acquire (&open_inodes_lock); /* Check whether this inode is already open. */ for (e = list_begin (&open_inodes); e != list_end (&open_inodes); e = list_next (e)) @@ -122,22 +131,30 @@ inode_open (disk_sector_t sector) if (inode->sector == sector) { inode_reopen (inode); + lock_release (&open_inodes_lock); return inode; } } /* Allocate memory. */ inode = malloc (sizeof *inode); - if (inode == NULL) + if (inode == NULL) { + lock_release (&open_inodes_lock); return NULL; + } /* Initialize. */ + lock_init (&inode->lock); + lock_acquire (&inode->lock); list_push_front (&open_inodes, &inode->elem); + lock_release (&open_inodes_lock); inode->sector = sector; inode->open_cnt = 1; inode->deny_write_cnt = 0; inode->removed = false; + rwlock_init (&inode->rwlock); disk_read (filesys_disk, inode->sector, &inode->data); + lock_release (&inode->lock); return inode; } @@ -147,8 +164,10 @@ inode_reopen (struct inode *inode) { if (inode != NULL) { + lock_acquire (&inode->lock); ASSERT(inode->open_cnt != 0); inode->open_cnt++; + lock_release (&inode->lock); } return inode; } @@ -170,11 +189,17 @@ inode_close (struct inode *inode) if (inode == NULL) return; + lock_acquire (&inode->lock); + /* Release resources if this was the last opener. */ - if (--inode->open_cnt == 0) + if (--inode->open_cnt > 0) { - /* Remove from inode list and release lock. */ + lock_release (&inode->lock); + } else { + /* Remove from inode list. */ + lock_acquire (&open_inodes_lock); list_remove (&inode->elem); + lock_release (&open_inodes_lock); /* Deallocate blocks if removed. */ if (inode->removed) @@ -194,7 +219,9 @@ void inode_remove (struct inode *inode) { ASSERT (inode != NULL); + lock_acquire (&inode->lock); inode->removed = true; + lock_release (&inode->lock); } /* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET. @@ -207,6 +234,8 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) off_t bytes_read = 0; uint8_t *bounce = NULL; + rwlock_read_p (&inode->rwlock); + while (size > 0) { /* Disk sector to read, starting byte offset within sector. */ @@ -247,6 +276,8 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) offset += chunk_size; bytes_read += chunk_size; } + + rwlock_read_v (&inode->rwlock); free (bounce); return bytes_read; @@ -268,6 +299,8 @@ inode_write_at (struct inode *inode, const void *buffer_, off_t size, if (inode->deny_write_cnt) return 0; + rwlock_write_p (&inode->rwlock); + while (size > 0) { /* Sector to write, starting byte offset within sector. */ @@ -315,6 +348,8 @@ inode_write_at (struct inode *inode, const void *buffer_, off_t size, offset += chunk_size; bytes_written += chunk_size; } + + rwlock_write_v (&inode->rwlock); free (bounce); return bytes_written; @@ -325,8 +360,10 @@ inode_write_at (struct inode *inode, const void *buffer_, off_t size, void inode_deny_write (struct inode *inode) { + lock_acquire (&inode->lock); inode->deny_write_cnt++; ASSERT (inode->deny_write_cnt <= inode->open_cnt); + lock_release (&inode->lock); } /* Re-enables writes to INODE. @@ -335,9 +372,11 @@ inode_deny_write (struct inode *inode) void inode_allow_write (struct inode *inode) { + lock_acquire (&inode->lock); ASSERT (inode->deny_write_cnt > 0); ASSERT (inode->deny_write_cnt <= inode->open_cnt); inode->deny_write_cnt--; + lock_release (&inode->lock); } /* Returns the length, in bytes, of INODE's data. */ diff --git a/src/lib/pid_t.h b/src/lib/pid_t.h new file mode 100644 index 0000000..c6d8e31 --- /dev/null +++ b/src/lib/pid_t.h @@ -0,0 +1,15 @@ +#ifndef LIB_PID_T_H +#define LIB_PID_T_H + +/* Process identifier. + Moved from lib/user/syscall.h since both kernel- + and user-space want the same definition. */ +typedef int pid_t; + +#define PID_ERROR ((pid_t) -1) + +/* Format specifier for printf(), e.g.: + printf ("pid=%"PRPTd"\n", pid); */ +#define PRPTd d + +#endif /* lib/pid_t.h */ diff --git a/src/lib/user/syscall.h b/src/lib/user/syscall.h index 8a9e0c0..a152dd1 100644 --- a/src/lib/user/syscall.h +++ b/src/lib/user/syscall.h @@ -4,9 +4,7 @@ #include <stdbool.h> #include <debug.h> -/* Process identifier. */ -typedef int pid_t; -#define PID_ERROR ((pid_t) -1) +#include "lib/pid_t.h" /* Map region identifier. */ typedef int mapid_t; diff --git a/src/tests/Make.tests b/src/tests/Make.tests index 76d63f6..60f2c2d 100644 --- a/src/tests/Make.tests +++ b/src/tests/Make.tests @@ -14,7 +14,7 @@ ifdef PROGS include ../../Makefile.userprog endif -TIMEOUT = 60 +TIMEOUT = 5 clean:: rm -f $(OUTPUTS) $(ERRORS) $(RESULTS) diff --git a/src/tests/userprog/Make.tests b/src/tests/userprog/Make.tests index c762af3..427f538 100644 --- a/src/tests/userprog/Make.tests +++ b/src/tests/userprog/Make.tests @@ -8,16 +8,18 @@ args-single args-multiple args-many args-dbl-space sc-bad-sp \ sc-bad-arg sc-boundary sc-boundary-2 halt exit create-normal \ create-empty create-null create-bad-ptr create-long create-exists \ create-bound open-normal open-missing open-boundary open-empty \ -open-null open-bad-ptr open-twice close-normal close-stdin \ -close-stdout close-bad-fd read-bad-ptr read-boundary \ +open-null open-bad-ptr open-twice close-normal close-twice close-stdin \ +close-stdout close-bad-fd read-normal read-bad-ptr read-boundary \ read-zero read-stdout read-bad-fd write-normal write-bad-ptr \ write-boundary write-zero write-stdin write-bad-fd exec-once exec-arg \ exec-multiple exec-missing exec-bad-ptr wait-simple wait-twice \ -wait-killed wait-bad-pid multi-recurse \ -) +wait-killed wait-bad-pid multi-recurse multi-child-fd) + + tests/userprog_PROGS = $(tests/userprog_TESTS) $(addprefix \ -tests/userprog/,child-simple child-args child-bad child-close child-rox) +tests/userprog/,child-simple child-args child-bad child-close) + tests/userprog/args-none_SRC = tests/userprog/args.c tests/userprog/args-single_SRC = tests/userprog/args.c @@ -26,12 +28,7 @@ tests/userprog/args-many_SRC = tests/userprog/args.c tests/userprog/args-dbl-space_SRC = tests/userprog/args.c tests/userprog/sc-bad-sp_SRC = tests/userprog/sc-bad-sp.c tests/main.c tests/userprog/sc-bad-arg_SRC = tests/userprog/sc-bad-arg.c tests/main.c -tests/userprog/bad-read_SRC = tests/userprog/bad-read.c tests/main.c -tests/userprog/bad-write_SRC = tests/userprog/bad-write.c tests/main.c -tests/userprog/bad-jump_SRC = tests/userprog/bad-jump.c tests/main.c -tests/userprog/bad-read2_SRC = tests/userprog/bad-read2.c tests/main.c -tests/userprog/bad-write2_SRC = tests/userprog/bad-write2.c tests/main.c -tests/userprog/bad-jump2_SRC = tests/userprog/bad-jump2.c tests/main.c + tests/userprog/sc-boundary_SRC = tests/userprog/sc-boundary.c \ tests/userprog/boundary.c tests/main.c tests/userprog/sc-boundary-2_SRC = tests/userprog/sc-boundary-2.c \ @@ -86,16 +83,13 @@ tests/userprog/wait-bad-pid_SRC = tests/userprog/wait-bad-pid.c tests/main.c tests/userprog/multi-recurse_SRC = tests/userprog/multi-recurse.c tests/userprog/multi-child-fd_SRC = tests/userprog/multi-child-fd.c \ tests/main.c -tests/userprog/rox-simple_SRC = tests/userprog/rox-simple.c tests/main.c -tests/userprog/rox-child_SRC = tests/userprog/rox-child.c tests/main.c -tests/userprog/rox-multichild_SRC = tests/userprog/rox-multichild.c \ -tests/main.c + tests/userprog/child-simple_SRC = tests/userprog/child-simple.c tests/userprog/child-args_SRC = tests/userprog/args.c tests/userprog/child-bad_SRC = tests/userprog/child-bad.c tests/main.c tests/userprog/child-close_SRC = tests/userprog/child-close.c -tests/userprog/child-rox_SRC = tests/userprog/child-rox.c + $(foreach prog,$(tests/userprog_PROGS),$(eval $(prog)_SRC += tests/lib.c)) @@ -128,5 +122,3 @@ tests/userprog/wait-twice_PUTFILES += tests/userprog/child-simple tests/userprog/exec-arg_PUTFILES += tests/userprog/child-args tests/userprog/multi-child-fd_PUTFILES += tests/userprog/child-close tests/userprog/wait-killed_PUTFILES += tests/userprog/child-bad -tests/userprog/rox-child_PUTFILES += tests/userprog/child-rox -tests/userprog/rox-multichild_PUTFILES += tests/userprog/child-rox diff --git a/src/threads/synch.c b/src/threads/synch.c index 317c68a..e714ce0 100644 --- a/src/threads/synch.c +++ b/src/threads/synch.c @@ -336,3 +336,43 @@ cond_broadcast (struct condition *cond, struct lock *lock) while (!list_empty (&cond->waiters)) cond_signal (cond, lock); } + +void +rwlock_init (struct rwlock *rwlock) +{ + sema_init (&rwlock->resource, 1); + lock_init (&rwlock->rmutex); + rwlock->readcount = 0; +} + +void +rwlock_write_p (struct rwlock *rwlock) +{ + sema_down (&rwlock->resource); +} + +void +rwlock_write_v (struct rwlock *rwlock) +{ + sema_up (&rwlock->resource); +} + +void +rwlock_read_p (struct rwlock *rwlock) +{ + lock_acquire (&rwlock->rmutex); + rwlock->readcount ++; + if (rwlock->readcount == 1) + sema_down (&rwlock->resource); + lock_release (&rwlock->rmutex); +} + +void +rwlock_read_v (struct rwlock *rwlock) +{ + lock_acquire (&rwlock->rmutex); + rwlock->readcount --; + if (rwlock->readcount == 0) + sema_up (&rwlock->resource); + lock_release (&rwlock->rmutex); +} diff --git a/src/threads/synch.h b/src/threads/synch.h index a19e88b..a76eecc 100644 --- a/src/threads/synch.h +++ b/src/threads/synch.h @@ -41,6 +41,23 @@ void cond_wait (struct condition *, struct lock *); void cond_signal (struct condition *, struct lock *); void cond_broadcast (struct condition *, struct lock *); +/* Readers-writers lock. + + Implementation of "First readers-writers problem" from + https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem. */ +struct rwlock + { + struct semaphore resource; + struct lock rmutex; + unsigned readcount; + }; + +void rwlock_init (struct rwlock *); +void rwlock_write_p (struct rwlock *); +void rwlock_write_v (struct rwlock *); +void rwlock_read_p (struct rwlock *); +void rwlock_read_v (struct rwlock *); + /* Optimization barrier. The compiler will not reorder operations across an diff --git a/src/threads/thread.c b/src/threads/thread.c index 92d1aa8..3112a71 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -13,6 +13,7 @@ #include "threads/vaddr.h" #ifdef USERPROG #include "userprog/process.h" +#include "threads/malloc.h" #endif /* Random value for struct thread's `magic' member. @@ -435,6 +436,9 @@ init_thread (struct thread *t, const char *name, int priority) strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; t->priority = priority; +#ifdef USERPROG + list_init (&t->children); +#endif t->magic = THREAD_MAGIC; } diff --git a/src/threads/thread.h b/src/threads/thread.h index 0039560..a3bc814 100644 --- a/src/threads/thread.h +++ b/src/threads/thread.h @@ -4,6 +4,9 @@ #include <debug.h> #include <list.h> #include <stdint.h> +#include "threads/synch.h" + +#define MAX_FDS 128 /* Max number of file descriptors per thread */ /* States in a thread's life cycle. */ enum thread_status @@ -19,6 +22,23 @@ enum thread_status typedef int tid_t; #define TID_ERROR ((tid_t) -1) /* Error value for tid_t. */ +/* The relationship between a parent and child process. + The child reports its exit status by setting exit_status. + The parent places the parent_child element in its list of children. +*/ +struct parent_child + { + struct list_elem elem; // owned by the parent + + // exit_status is readable by the parent + struct semaphore exit_sema; + int exit_status; + + struct lock l; + int alive_count; + tid_t child_tid; + }; + /* Thread priorities. */ #define PRI_MIN 0 /* Lowest priority. */ #define PRI_DEFAULT 31 /* Default priority. */ @@ -80,6 +100,7 @@ typedef int tid_t; only because they are mutually exclusive: only a thread in the ready state is on the run queue, whereas only a thread in the blocked state is on a semaphore wait list. */ + struct thread { /* Owned by thread.c. */ @@ -95,6 +116,11 @@ struct thread #ifdef USERPROG /* Owned by userprog/process.c. */ uint32_t *pagedir; /* Page directory. */ + struct file **fds; /* Pointer to array of file descriptors. */ + bool load_success; + + struct parent_child *parent; // one parent + struct list children; // multiple children #endif /* Owned by thread.c. */ diff --git a/src/userprog/Make.vars b/src/userprog/Make.vars index eebac65..22aec79 100644 --- a/src/userprog/Make.vars +++ b/src/userprog/Make.vars @@ -2,6 +2,6 @@ os.dsk: DEFINES = -DUSERPROG -DFILESYS KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys -TEST_SUBDIRS = tests/userprog #tests/userprog/no-vm tests/filesys/base +TEST_SUBDIRS = tests/userprog tests/filesys/base GRADING_FILE = $(SRCDIR)/tests/userprog/Grading SIMULATOR = --qemu diff --git a/src/userprog/process.c b/src/userprog/process.c index b3e16bb..6170b53 100644 --- a/src/userprog/process.c +++ b/src/userprog/process.c @@ -14,10 +14,24 @@ #include "threads/flags.h" #include "threads/init.h" #include "threads/interrupt.h" +#include "threads/malloc.h" #include "threads/palloc.h" +#include "threads/synch.h" #include "threads/thread.h" #include "threads/vaddr.h" +struct start_process_args + { + struct semaphore sema; + + // parent -> child + char *file_name; + + // child -> parent + bool success; + struct parent_child *child; + }; + static thread_func start_process NO_RETURN; static bool load (const char *cmdline, void (**eip) (void), void **esp); @@ -28,42 +42,75 @@ static bool load (const char *cmdline, void (**eip) (void), void **esp); tid_t process_execute (const char *file_name) { - char *fn_copy; + struct start_process_args args; // stack allocated since we know we wait for thread_create to finish reading tid_t tid; + sema_init (&args.sema, 0); + /* Make a copy of FILE_NAME. Otherwise there's a race between the caller and load(). */ - fn_copy = palloc_get_page (0); - if (fn_copy == NULL) + args.file_name = palloc_get_page (0); + if (args.file_name == NULL) return TID_ERROR; - strlcpy (fn_copy, file_name, PGSIZE); - - /* Create a new thread to execute FILE_NAME. */ - tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy); - if (tid == TID_ERROR) - palloc_free_page (fn_copy); + strlcpy (args.file_name, file_name, PGSIZE); + + /* Create a new thread to execute FILE_NAME. + If thread_create fails we free and return immediately since we know + that the thread didn't start. + Otherwise, the child thread can be scheduled freely so we explicitly + wait for the child to signal that it has read from and written to + the args. Only then can we free resources and return the tid. */ + tid = thread_create (file_name, PRI_DEFAULT, start_process, &args); + if (tid != TID_ERROR) { + sema_down (&args.sema); + + if (args.success) { + list_push_back (&thread_current ()->children, &args.child->elem); + } else { + tid = -1; + } + } + palloc_free_page (args.file_name); return tid; } /* A thread function that loads a user process and starts it running. */ static void -start_process (void *file_name_) +start_process (void *args_) { - char *file_name = file_name_; + struct start_process_args *args = args_; struct intr_frame if_; + struct thread *t; bool success; + t = thread_current (); + /* Initialize interrupt frame and load executable. */ memset (&if_, 0, sizeof if_); if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; if_.cs = SEL_UCSEG; if_.eflags = FLAG_IF | FLAG_MBS; - success = load (file_name, &if_.eip, &if_.esp); + success = load (args->file_name, &if_.eip, &if_.esp); + args->success = success; + t->load_success = success; + + if (success) { + t->parent = malloc (sizeof (struct parent_child)); + + sema_init (&t->parent->exit_sema, 0); + lock_init (&t->parent->l); + + t->parent->child_tid = t->tid; + t->parent->alive_count = 2; + + args->child = t->parent; + } + + sema_up (&args->sema); /* If load failed, quit. */ - palloc_free_page (file_name); - if (!success) + if (!success) thread_exit (); /* Start the user process by simulating a return from an @@ -86,11 +133,39 @@ start_process (void *file_name_) This function will be implemented in problem 2-2. For now, it does nothing. */ int -process_wait (tid_t child_tid UNUSED) +process_wait (tid_t child_tid) { + struct thread *t = thread_current (); + struct list_elem *e; + for (e = list_begin (&t->children); e != list_end (&t->children); + e = list_next (e)) + { + struct parent_child *pc = list_entry (e, struct parent_child, elem); + if (child_tid == pc->child_tid) { + sema_down (&pc->exit_sema); + int exit_status = pc->exit_status; + pc->exit_status = -1; + sema_up (&pc->exit_sema); // a bit of a hack + // the child is killed so we can read again if we want to + return exit_status; + } + } return -1; } +static void +free_pc (struct parent_child *pc) +{ + lock_acquire (&pc->l); + + pc->alive_count--; + if (pc->alive_count == 0) { + free (pc); + } else { + lock_release (&pc->l); + } +} + /* Free the current process's resources. */ void process_exit (void) @@ -98,6 +173,20 @@ process_exit (void) struct thread *cur = thread_current (); uint32_t *pd; + if (cur->load_success) { + sema_up (&cur->parent->exit_sema); + free_pc (cur->parent); + printf("%s: exit(%d)\n", cur->name, cur->parent->exit_status); + + struct list_elem *e; + struct parent_child *child; + while (!list_empty (&cur->children)) { + e = list_pop_front (&cur->children); + child = list_entry (e, struct parent_child, elem); + free_pc (child); + } + } + /* Destroy the current process's page directory and switch back to the kernel-only page directory. */ pd = cur->pagedir; @@ -226,10 +315,66 @@ load (const char *file_name, void (**eip) (void), void **esp) goto done; } + size_t cmd_len, word_alignment; + char *esp_cmd, **esp_argv_first, **esp_argv_entry, ***esp_argv; + int *esp_argc, argc = 0; + + /* Copy passed command to start of user stack. */ + cmd_len = strlen (file_name); + esp_cmd = *esp; + esp_cmd -= cmd_len + 1; // +1 makes room for '\0' + for (i = 0; i < cmd_len; i++) { + esp_cmd[i] = file_name[i]; + } + esp_cmd[cmd_len] = '\0'; + + /* Tokenize passed command in-place. */ + // esp_cmd still points to first character of passed command + char *token, *save_ptr; + for (token = strtok_r (esp_cmd, " ", &save_ptr); token != NULL; + token = strtok_r (NULL, " ", &save_ptr)) + { + argc++; + } + + file_name = esp_cmd; + strlcpy (thread_current ()->name, file_name, 16); + + /* argv entries are pointers so they need to be aligned to the pointer size. */ + size_t psize = sizeof (char *); + word_alignment = (cmd_len + psize) / psize; + + /* Write argv entries. */ + esp_argv_entry = *esp; + esp_argv_entry -= word_alignment + argc + 1; // +1 makes room for argv[argc] = NULL + esp_argv_first = esp_argv_entry; // save for later + + // esp_cmd points to first entry so write directly + *esp_argv_entry = esp_cmd; + esp_argv_entry++; + + for (i = 0; i < argc - 1; i++) { + // step until a \0 is found + while (*(++esp_cmd) != '\0') {} + // step over any ' ' + while (*(++esp_cmd) == ' ') {} + *esp_argv_entry = esp_cmd; // point to next character + esp_argv_entry++; + } + + esp_argv = esp_argv_first - 1; + + *esp_argv = esp_argv_first; + + esp_argc = esp_argv - 1; + *esp_argc = argc; + + *esp = esp_argc - 1; // return address + /* Uncomment the following line to print some debug information. This will be useful when you debug the program stack.*/ -/*#define STACK_DEBUG*/ +// #define STACK_DEBUG #ifdef STACK_DEBUG printf("*esp is %p\nstack contents:\n", *esp); diff --git a/src/userprog/start_pfs.sh b/src/userprog/start_pfs.sh index 6ae76ad..26b9eb9 100644..100755 --- a/src/userprog/start_pfs.sh +++ b/src/userprog/start_pfs.sh @@ -1,4 +1,4 @@ -make -j4 +make -j12 cd build pintos-mkdisk fs.dsk 800 dd if=/dev/urandom of=random bs=1 count=100 @@ -7,4 +7,4 @@ pintos --qemu -v -p random -a random -- -q pintos --qemu -v -p ../../examples/pfs -a pfs -- -q pintos --qemu -v -p ../../examples/pfs_writer -a pfs_writer -- -q pintos --qemu -v -p ../../examples/pfs_reader -a pfs_reader -- -q -pintos --qemu -v -- run pfs +pintos --qemu -v -- -q run pfs diff --git a/src/userprog/start_recursor.sh b/src/userprog/start_recursor.sh index 22a69ac..6f5e99b 100644..100755 --- a/src/userprog/start_recursor.sh +++ b/src/userprog/start_recursor.sh @@ -1,6 +1,6 @@ -make -j4 -cd build +make -j12 +cd build pintos-mkdisk fs.dsk 400 -pintos --qemu -v -- -f -q -pintos --qemu -v -p ../../examples/recursor_ng -a recursor_ng -- -q -pintos --qemu -v -m 128 -- run "recursor_ng pintosmaster 6 1" +pintos -v --qemu -- -f -q +pintos -v --qemu -p ../../examples/recursor_ng -a recursor_ng -- -q +pintos -v --qemu -m 128 -- run "recursor_ng pintosmaster 6 1" diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c index 370c89b..c1308ca 100644 --- a/src/userprog/syscall.c +++ b/src/userprog/syscall.c @@ -4,6 +4,17 @@ #include "threads/interrupt.h" #include "threads/thread.h" +#include "devices/input.h" +#include "filesys/file.h" +#include "filesys/filesys.h" +#include "filesys/off_t.h" +#include "lib/pid_t.h" +#include "userprog/pagedir.h" +#include "userprog/process.h" +#include "threads/init.h" +#include "threads/malloc.h" +#include "threads/vaddr.h" + static void syscall_handler (struct intr_frame *); void @@ -13,8 +24,327 @@ syscall_init (void) } static void -syscall_handler (struct intr_frame *f UNUSED) +halt (void) +{ + power_off(); +} + +static bool +create (const char *filename, off_t initial_size) +{ + return filesys_create (filename, initial_size); +} + +static bool +remove (const char *filename) +{ + return filesys_remove (filename); +} + +static int +open (const char *filename) +{ + struct thread *t = thread_current (); + + if (!t->fds) { + t->fds = (struct file **) calloc (MAX_FDS, sizeof (struct file *)); + } + + struct file *file = filesys_open (filename); + if (!file) { + return -1; + } + + for (int i = 0; i < MAX_FDS; i++) { + struct file **fd = t->fds + i; + if (*fd == NULL) { + *fd = file; + return i + 2; // 0 and 1 are reserved for stdin and stdout + } + } + free (file); + return -1; +} + +static struct file ** +get_fd (struct thread *thread, int fd_i) +{ + if (!thread->fds) { + return NULL; + } + + return thread->fds + fd_i - 2; // -2 since 0 and 1 are reserved and not present in the array +} + +static void +exit (int status) { - printf ("system call!\n"); + struct thread *thread = thread_current (); + + if (thread->fds) { + for (int i = 0; i < MAX_FDS; i++) { + struct file **fd = thread->fds + i; + if (fd && *fd) { + file_close (*fd); + *fd = NULL; + } + } + free (thread->fds); + } + + lock_acquire (&thread->parent->l); + thread->parent->exit_status = status; + lock_release (&thread->parent->l); + thread_exit (); } + +static int +wait (tid_t child_tid) +{ + return process_wait (child_tid); +} + +static int +read (int fd_i, void *buf, unsigned size) +{ + struct thread *thread = thread_current (); + + if (fd_i == 0) { + // stdin + unsigned i; + for (i = 0; i < size; i++) { + ((char *)buf)[i] = input_getc (); + } + return i; + } else if (fd_i == 1) { + // can't read from stdout + return -1; + } + + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + return file_read (*fd, buf, size); + } else { + return -1; + } +} + +static int +write (int fd_i, const void *buf, unsigned size) +{ + struct thread *thread = thread_current (); + + if (fd_i == 1) { + // stdout + putbuf ((const char *)buf, size); + return size; + } else if (fd_i == 0) { + // can't write to stdout + return -1; + } + + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + return file_write (*fd, buf, size); + } else { + return -1; + } +} + +static int +filesize (int fd_i) +{ + struct thread *thread = thread_current (); + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + return file_length (*fd); + } + return -1; +} + +static void +seek (int fd_i, unsigned position) +{ + struct thread *thread = thread_current (); + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + file_seek (*fd, position); + } +} + +static unsigned +tell (int fd_i) +{ + struct thread *thread = thread_current (); + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + return file_tell (*fd); + } + return 0; +} + + +static void +close (int fd_i) +{ + struct thread *thread = thread_current (); + + struct file **fd = get_fd (thread, fd_i); + if (fd && *fd) { + file_close (*fd); + *fd = NULL; + } +} + +static pid_t +exec (const char *filename) +{ + return process_execute (filename); +} + +static bool +ptr_is_valid (const void *ptr) +{ + // uintptr_t ptr = _ptr; + if (!is_user_vaddr (ptr)) + return false; + + struct thread *t = thread_current (); + + if (pagedir_get_page (t->pagedir, ptr) == NULL) + return false; + + return true; +} + +// cast argument N from f->esp to TYPE without dereferencing +#define INTR_ESP(N, TYPE) (TYPE *)(f->esp+(4*(N))) + +#define CHECK_PTR_AND_MAYBE_EXIT(PTR) \ + do { \ + if (!ptr_is_valid (PTR)) { \ + exit (-1); \ + return; \ + } \ + } while (0) + + +static void +syscall_handler (struct intr_frame *f UNUSED) +{ + // check esp + int *syscall_number = INTR_ESP (0, int); + + CHECK_PTR_AND_MAYBE_EXIT (syscall_number); + + char **filename; + int *status, *fd_i; + off_t *initial_size; + tid_t *child_tid; + unsigned *size, *position; + void **buf; + + switch (*syscall_number) { + case 0: + // halt + halt (); + break; + case 1: + // exit + status = INTR_ESP (1, int); + CHECK_PTR_AND_MAYBE_EXIT (status); + exit (*status); + break; + case 2: + // exec + filename = INTR_ESP (1, char *); + CHECK_PTR_AND_MAYBE_EXIT (filename); + CHECK_PTR_AND_MAYBE_EXIT (*filename); + f->eax = exec (*filename); + break; + case 3: + // wait + child_tid = INTR_ESP (1, tid_t); + CHECK_PTR_AND_MAYBE_EXIT (child_tid); + f->eax = wait (*child_tid); + break; + case 4: + // create + filename = INTR_ESP (1, char *); + initial_size = INTR_ESP (2, off_t); + CHECK_PTR_AND_MAYBE_EXIT (filename); + CHECK_PTR_AND_MAYBE_EXIT (*filename); + CHECK_PTR_AND_MAYBE_EXIT (initial_size); + f->eax = create (*filename, *initial_size); + break; + case 5: + // remove + filename = INTR_ESP (1, char *); + CHECK_PTR_AND_MAYBE_EXIT (filename); + CHECK_PTR_AND_MAYBE_EXIT (*filename); + f->eax = remove (*filename); + break; + case 6: + // open + filename = INTR_ESP (1, char *); + CHECK_PTR_AND_MAYBE_EXIT (filename); + CHECK_PTR_AND_MAYBE_EXIT (*filename); + f->eax = open (*filename); + break; + case 7: + // filesize + fd_i = INTR_ESP (1, int); + CHECK_PTR_AND_MAYBE_EXIT (fd_i); + f->eax = filesize (*fd_i); + break; + case 8: + // read + fd_i = INTR_ESP (1, int); + buf = INTR_ESP (2, void *); + size = INTR_ESP (3, unsigned); + CHECK_PTR_AND_MAYBE_EXIT (fd_i); + CHECK_PTR_AND_MAYBE_EXIT (buf); + CHECK_PTR_AND_MAYBE_EXIT (*buf); + CHECK_PTR_AND_MAYBE_EXIT (size); + CHECK_PTR_AND_MAYBE_EXIT (*buf + *size); + f->eax = read (*fd_i, *buf, *size); + break; + case 9: + // write + fd_i = INTR_ESP (1, int); + buf = INTR_ESP (2, void *); + size = INTR_ESP (3, unsigned); + CHECK_PTR_AND_MAYBE_EXIT (fd_i); + CHECK_PTR_AND_MAYBE_EXIT (buf); + CHECK_PTR_AND_MAYBE_EXIT (*buf); + CHECK_PTR_AND_MAYBE_EXIT (size); + CHECK_PTR_AND_MAYBE_EXIT (*buf + *size); + f->eax = write (*fd_i, *buf, *size); + break; + case 10: + // seek + fd_i = INTR_ESP (1, int); + position = INTR_ESP (2, unsigned); + CHECK_PTR_AND_MAYBE_EXIT (fd_i); + CHECK_PTR_AND_MAYBE_EXIT (position); + seek (*fd_i, *position); + break; + case 11: + // tell + fd_i = INTR_ESP (1, int); + CHECK_PTR_AND_MAYBE_EXIT (fd_i); + f->eax = tell (*fd_i); + break; + case 12: + // close + fd_i = INTR_ESP (1, int); + close (*fd_i); + break; + default: + printf ("kernel: unknown syscall '%d'\n", *syscall_number); + break; + } +} + +#undef INTR_ESP diff --git a/src/utils/backtrace b/src/utils/backtrace index 95e422f..95e422f 100644..100755 --- a/src/utils/backtrace +++ b/src/utils/backtrace diff --git a/src/utils/pintos-gdb b/src/utils/pintos-gdb index 4ef38d3..4ef38d3 100644..100755 --- a/src/utils/pintos-gdb +++ b/src/utils/pintos-gdb diff --git a/src/utils/pintos-mkdisk b/src/utils/pintos-mkdisk index 662b2e5..662b2e5 100644..100755 --- a/src/utils/pintos-mkdisk +++ b/src/utils/pintos-mkdisk |