From 9d6ad9a479ddae9628dc2d45862f9281986c430b Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 15 Dec 2004 00:53:11 +0000 Subject: [PATCH] Switch the base file system from direct-indexed inodes to extents. This has the direct effect of allowing arbitrarily large files, and the indirect effect that we don't need to strip debug symbols from userprog test programs anymore, which makes userspace backtraces easier to obtain. --- doc/debug.texi | 17 +------- doc/filesys.texi | 31 ++++++++------- doc/threads.texi | 9 ++--- doc/userprog.texi | 54 +++++++++++++++++++++++-- grading/vm/mmap-shuffle.c | 6 ++- grading/vm/page-merge-par.c | 5 ++- grading/vm/page-merge-seq.c | 5 ++- src/Makefile.userprog | 6 +-- src/filesys/filesys.c | 7 ++-- src/filesys/inode.c | 78 ++++++++++++++----------------------- 10 files changed, 120 insertions(+), 98 deletions(-) diff --git a/doc/debug.texi b/doc/debug.texi index 35e7c4a..a192a73 100644 --- a/doc/debug.texi +++ b/doc/debug.texi @@ -217,13 +217,8 @@ The fifth and sixth lines are the interrupt handler entry path. The remaining lines are for addresses below @code{PHYS_BASE}. This means that they refer to addresses in the user program, not in the kernel. If you know what user program was running when the kernel -panicked, you can re-run @command{backtrace} on the user program. You -need to have compiled the user program with debug symbols enabled for -this to be useful. Instructions for doing so are included in -@file{pintos/src/Makefile.userprog}. - -In this case, we rerun @command{backtrace} like so (typing the command -on a single line, of course): +panicked, you can re-run @command{backtrace} on the user program, like +so: (typing the command on a single line, of course): @example ~/cs140/pintos/src/utils/backtrace grow-too-big 0xc0106eff 0xc01102fb @@ -305,14 +300,6 @@ address. (Use a @samp{0x} prefix to specify an address in hex.) @end table -You might notice that @command{gdb} tends to show code being executed -in an order different from the order in the source. That is, the -current statement jumps around seemingly randomly. This is due to -GCC's optimizer, which does tend to reorder code. If it bothers you, -you can turn off optimization by editing -@file{pintos/src/Make.config}, removing @option{-O3} from the -@code{CFLAGS} definition. - If you notice other strange behavior while using @command{gdb}, there are three possibilities. The first is that there is a bug in your modified Pintos. The second is that there is a bug in Bochs's diff --git a/doc/filesys.texi b/doc/filesys.texi index 4d66391..b71974f 100644 --- a/doc/filesys.texi +++ b/doc/filesys.texi @@ -27,7 +27,7 @@ Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in @menu * File System New Code:: * File System Synchronization:: -* Problem 4-1 Large Files:: +* Problem 4-1 Indexed Files:: * Problem 4-2 File Growth:: * Problem 4-3 Subdirectories:: * Problem 4-4 Buffer Cache:: @@ -124,19 +124,22 @@ file system doesn't have to maintain full serialization as long as it follows the rules above. @end itemize -@node Problem 4-1 Large Files -@section Problem 4-1: Large Files - -Modify the file system to allow the maximum size of a file to be as -large as the disk. You can assume that the disk will not be larger -than 8 MB. In the basic file system, each file is limited to a file -size of just under 64 kB. Each file has a header called an index node -or @dfn{inode} (represented by @struct{inode}) that is a table of -direct pointers to the disk blocks for that file. Since the inode is -stored in one disk sector, the maximum size of a file is limited by -the number of pointers that will fit in one disk sector. Increasing -the limit to 8 MB will require you to implement doubly-indirect -blocks. +@node Problem 4-1 Indexed Files +@section Problem 4-1: Indexed Files + +The basic file system allocates files as a single extent, making it +vulnerable to external fragmentation. Eliminate this problem by +modifying the inode structure. In practice, this probably means using +an index structure with direct, indirect, and doubly indirect blocks. +(You are welcome to choose a different scheme as long as you explain the +rationale for it in your design documentation, and as long as it does +not suffer from external fragmentation.) + +You can assume that the disk will not be larger than 8 MB. You must +support files as large as the disk (minus metadata). Each inode is +stored in one disk sector, limiting the number of block pointers that it +can contain. Supporting 8 MB files will require you to implement +doubly-indirect blocks. @node Problem 4-2 File Growth @section Problem 4-2: File Growth diff --git a/doc/threads.texi b/doc/threads.texi index 49183be..ab355ad 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -77,10 +77,8 @@ single-step from there.@footnote{@command{gdb} might tell you that @func{schedule} doesn't exist, which is arguably a @command{gdb} bug. You can work around this by setting the breakpoint by filename and line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is -the line number of the first declaration in @func{schedule}. -Alternatively you can recompile with optimization turned off, by -removing @samp{-O3} from the @code{CFLAGS} line in -@file{Make.config}.} Be sure to keep track of each thread's address +the line number of the first declaration in @func{schedule}.} Be sure +to keep track of each thread's address and state, and what procedures are on the call stack for each thread. You will notice that when one thread calls @func{switch_threads}, another thread starts running, and the first thing the new thread does @@ -339,7 +337,8 @@ assignment. Furthermore, resist the temptation to directly disable interrupts in your solution by calling @func{intr_disable} or @func{intr_set_level}, although you may find doing so to be useful while debugging. Instead, use semaphores, locks and condition -variables to solve synchronization problems. Hint: read the comments +variables to solve synchronization problems. Read the tour section on +synchronization (@pxref{Synchronization}) or the comments in @file{threads/synch.h} if you're unsure what synchronization primitives may be used in what situations. diff --git a/doc/userprog.texi b/doc/userprog.texi index 78ef78d..62e29a6 100644 --- a/doc/userprog.texi +++ b/doc/userprog.texi @@ -125,7 +125,46 @@ interfaces to understand how to use the file system, and especially its many limitations. @strong{You should not modify the file system code for this project}. Proper use of the file system routines now will make life much easier for project 4, when you improve the file -system implementation. +system implementation. Until then, you will have to put up with the +following limitations: + +@itemize @bullet +@item +No synchronization. Concurrent accesses will interfere with one +another, so external synchronization is needed. @xref{Synchronizing +File Access}, for more details. + +@item +File size is fixed at creation time. Because the root directory is +represented as a file, the number of files that may be created is also +limited. + +@item +File data is allocated as a single extent, so that external +fragmentation can become a serious problem as a file system is used over +time. + +@item +No subdirectories. + +@item +File names are limited to 14 characters. + +@item +A system crash mid-operation may corrupt the disk in a way +that cannot be repaired automatically. No `fsck' tool is +provided in any case. +@end itemize + +However one important feature is included: + +@itemize @bullet +Unix-like semantics for filesys_remove() are implemented. +That is, if a file is open when it is removed, its blocks +are not deallocated and it may still be accessed by the +threads that have it open until the last one closes it. @xref{Removing +an Open File}, for more information. +@end itemize You need to be able to create and format simulated disks. The @command{pintos} program provides this functionality with its @@ -456,6 +495,7 @@ on the user's stack in the user's virtual address space. We recommend writing and testing this code before implementing any other system call functionality. +@anchor{Synchronizing File Access} You must make sure that system calls are properly synchronized so that any number of user processes can make them at once. In particular, it is not safe to call into the filesystem code provided in the @@ -507,14 +547,22 @@ Here are the most common causes: The disk hasn't yet been formatted (with @samp{pintos run -f}). @item -The filename specified is too long. The file system limits file names +The file name specified is too long. The file system limits file names to 14 characters. If you're using a command like @samp{pintos put ../../tests/userprog/echo}, that overflows the limit. Use @samp{pintos put ../../tests/userprog/echo echo} to put the file under the name @file{echo} instead. @item -The file is too big. The file system has a 63 kB limit. +The file system is full. + +@item +The file system already contains 10 files. (There's a 10-file limit for +the base Pintos file system.) + +@item +The file system is so fragmented that there's not enough contiguous +space for your file. @end itemize @item diff --git a/grading/vm/mmap-shuffle.c b/grading/vm/mmap-shuffle.c index 1eccc03..ae16f4a 100644 --- a/grading/vm/mmap-shuffle.c +++ b/grading/vm/mmap-shuffle.c @@ -8,7 +8,11 @@ #include "../lib/arc4.h" #include "../lib/cksum.h" -#define SIZE (63 * 1024) /* Max file size. */ +/* This is the max file size for an older version of the Pintos + file system that had 126 direct blocks each pointing to a + single disk sector. We could raise it now. */ +#define SIZE (126 * 512) + static char *buf = (char *) 0x10000000; static struct arc4 * diff --git a/grading/vm/page-merge-par.c b/grading/vm/page-merge-par.c index 5c5d62b..06209e8 100644 --- a/grading/vm/page-merge-par.c +++ b/grading/vm/page-merge-par.c @@ -7,7 +7,10 @@ #endif #include "../lib/arc4.h" -#define CHUNK_SIZE (63 * 1024) /* Max file size. */ +/* This is the max file size for an older version of the Pintos + file system that had 126 direct blocks each pointing to a + single disk sector. We could raise it now. */ +#define CHUNK_SIZE (126 * 512) #define CHUNK_CNT 8 /* Number of chunks. */ #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */ diff --git a/grading/vm/page-merge-seq.c b/grading/vm/page-merge-seq.c index f7ac14c..203ca9c 100644 --- a/grading/vm/page-merge-seq.c +++ b/grading/vm/page-merge-seq.c @@ -7,7 +7,10 @@ #endif #include "../lib/arc4.h" -#define CHUNK_SIZE (63 * 1024) /* Max file size. */ +/* This is the max file size for an older version of the Pintos + file system that had 126 direct blocks each pointing to a + single disk sector. We could raise it now. */ +#define CHUNK_SIZE (126 * 512) #define CHUNK_CNT 16 /* Number of chunks. */ #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */ diff --git a/src/Makefile.userprog b/src/Makefile.userprog index 90506a0..2e95f9b 100644 --- a/src/Makefile.userprog +++ b/src/Makefile.userprog @@ -10,11 +10,7 @@ DEFINES = -DPINTOS -DUSER CPPFLAGS = -nostdinc -I$(SRCDIR) -I- -I$(SRCDIR)/lib -I$(SRCDIR)/lib/user -I. # Linker flags. -# If you want to include debug symbols, comment out the STRIP assignment, -# or invoke `make' as `make STRIP='. -# Otherwise debug symbols will be omitted from executables to save space. -STRIP = -s -LDFLAGS = -nostdlib -static $(STRIP) +LDFLAGS = -nostdlib -static LDLIBS = $(shell $(CC) -print-libgcc-file-name) # C library sources linked into every test program. diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index 7b16438..6a763fe 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -74,10 +74,9 @@ directory is represented as a file, the number of files that may be created is also limited. - - No indirect blocks. This limits maximum file size to the - number of sector pointers that fit in a single inode - times the size of a sector, or 126 * 512 == 63 kB given - 32-bit sizes and 512-byte sectors. + - File data is allocated as a single extent, so that + external fragmentation can become a serious problem as a + file system is used over time. - No subdirectories. diff --git a/src/filesys/inode.c b/src/filesys/inode.c index 5ca91f1..16d1455 100644 --- a/src/filesys/inode.c +++ b/src/filesys/inode.c @@ -2,21 +2,18 @@ #include #include #include +#include #include #include "filesys/filesys.h" #include "threads/malloc.h" -/* Number of direct sector pointers in an inode. */ -#define DIRECT_CNT ((DISK_SECTOR_SIZE - sizeof (off_t) - sizeof (size_t)) \ - / sizeof (disk_sector_t)) - /* On-disk inode. - It is exactly DISK_SECTOR_SIZE bytes long. */ + Must be exactly DISK_SECTOR_SIZE bytes long. */ struct inode_disk { off_t length; /* File size in bytes. */ - size_t sector_cnt; /* File size in sectors. */ - disk_sector_t sectors[DIRECT_CNT]; /* Sectors allocated for file. */ + disk_sector_t first_sector; /* Starting sector. */ + uint32_t unused[126]; /* Unused padding. */ }; /* In-memory inode. */ @@ -58,39 +55,26 @@ inode_create (struct bitmap *b, disk_sector_t sector, off_t length) ASSERT (b != NULL); ASSERT (length >= 0); - /* Calculate number of sectors to allocate for file data. */ - sector_cnt = (length / DISK_SECTOR_SIZE) + (length % DISK_SECTOR_SIZE > 0); - if (sector_cnt > DIRECT_CNT) - return NULL; - /* Allocate inode. */ idx = alloc_inode (sector); if (idx == NULL) return NULL; /* Allocate disk sectors. */ + sector_cnt = DIV_ROUND_UP (length, DISK_SECTOR_SIZE); idx->data.length = length; - while (idx->data.sector_cnt < sector_cnt) - { - size_t sector = bitmap_scan_and_flip (b, 0, 1, false); - if (sector == BITMAP_ERROR) - goto error; - - idx->data.sectors[idx->data.sector_cnt++] = sector; - } + idx->data.first_sector = bitmap_scan_and_flip (b, 0, sector_cnt, false); + if (idx->data.first_sector == BITMAP_ERROR) + return NULL; /* Zero out the file contents. */ if (sector_cnt > 0) { - void *zero_sector; - size_t i; + static const char zero_sector[DISK_SECTOR_SIZE]; + disk_sector_t i; - zero_sector = calloc (1, DISK_SECTOR_SIZE); - if (zero_sector == NULL) - goto error; for (i = 0; i < sector_cnt; i++) - disk_write (filesys_disk, idx->data.sectors[i], zero_sector); - free (zero_sector); + disk_write (filesys_disk, idx->data.first_sector + i, zero_sector); } return idx; @@ -151,16 +135,21 @@ inode_close (struct inode *idx) if (idx->removed) { struct bitmap *free_map; - size_t i; free_map = bitmap_create (disk_size (filesys_disk)); if (free_map != NULL) { - bitmap_read (free_map, free_map_file); + disk_sector_t start, end; + bitmap_read (free_map, free_map_file); + + /* Reset inode sector bit. */ bitmap_reset (free_map, idx->sector); - for (i = 0; i < idx->data.sector_cnt; i++) - bitmap_reset (free_map, idx->data.sectors[i]); + + /* Reset inode data sector bits. */ + start = idx->data.first_sector; + end = start + DIV_ROUND_UP (idx->data.length, DISK_SECTOR_SIZE); + bitmap_set_multiple (free_map, start, end, false); bitmap_write (free_map, free_map_file); bitmap_destroy (free_map); @@ -198,12 +187,12 @@ inode_remove (struct inode *idx) disk_sector_t inode_byte_to_sector (const struct inode *idx, off_t pos) { - size_t i; - ASSERT (idx != NULL); - i = pos / DISK_SECTOR_SIZE; - return i < idx->data.sector_cnt ? idx->data.sectors[i] : (disk_sector_t) -1; + if (pos < idx->data.length) + return idx->data.first_sector + pos / DISK_SECTOR_SIZE; + else + return (disk_sector_t) -1; } /* Returns the length, in bytes, of the file with inode IDX. */ @@ -218,20 +207,11 @@ inode_length (const struct inode *idx) void inode_print (const struct inode *idx) { - size_t i; - - printf ("Inode %"PRDSNu": %"PRDSNu" bytes, %zu sectors (", - idx->sector, idx->data.length, idx->data.sector_cnt); - - /* This loop could be unsafe for large idx->data.sector_cnt, can - you see why? */ - for (i = 0; i < idx->data.sector_cnt; i++) - { - if (i != 0) - printf (", "); - printf ("%"PRDSNu, idx->data.sectors[i]); - } - printf (")\n"); + printf ("Inode %"PRDSNu": %"PRDSNu" bytes, " + "%zu sectors starting at %"PRDSNu"\n", + idx->sector, idx->data.length, + (size_t) DIV_ROUND_UP (idx->data.length, DISK_SECTOR_SIZE), + idx->data.first_sector); } /* Returns a newly allocated and initialized inode. */ -- 2.30.2