From 993c1d9f4452e2edd851f3175dfdf317f18bdb9f Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 13 Sep 2004 03:02:50 +0000 Subject: [PATCH] Rewrite filesystem to support Unix "delete" semantics. Also, make objects responsible for their own allocation for better abstraction. Rename filehdr to inode. Zero out files at creation time. Introduce "kernel" and "user" pools as a band-aid for user memory pressure on kernel. --- src/Makefile.build | 2 +- src/filesys/directory.c | 81 +++++---- src/filesys/directory.h | 18 +- src/filesys/file.c | 78 +++++++-- src/filesys/file.h | 12 +- src/filesys/filehdr.c | 137 --------------- src/filesys/filehdr.h | 32 ---- src/filesys/filesys.c | 351 +++++++++++++++++++++------------------ src/filesys/filesys.h | 8 +- src/filesys/fsutil.c | 18 +- src/filesys/inode.c | 250 ++++++++++++++++++++++++++++ src/filesys/inode.h | 19 +++ src/userprog/addrspace.c | 22 ++- 13 files changed, 606 insertions(+), 422 deletions(-) delete mode 100644 src/filesys/filehdr.c delete mode 100644 src/filesys/filehdr.h create mode 100644 src/filesys/inode.c create mode 100644 src/filesys/inode.h diff --git a/src/Makefile.build b/src/Makefile.build index 0293a0f..017267f 100644 --- a/src/Makefile.build +++ b/src/Makefile.build @@ -52,7 +52,7 @@ lib_kernel_SRC += lib/kernel/console.c # printf(), putchar(). filesys_SRC = filesys/filesys.c # Filesystem core. filesys_SRC += filesys/file.c # Files. filesys_SRC += filesys/directory.c # Directories. -filesys_SRC += filesys/filehdr.c # File headers (inodes). +filesys_SRC += filesys/inode.c # File headers. filesys_SRC += filesys/fsutil.c # Utilities. # User process code. diff --git a/src/filesys/directory.c b/src/filesys/directory.c index fba32f0..ec6ecd9 100644 --- a/src/filesys/directory.c +++ b/src/filesys/directory.c @@ -5,14 +5,44 @@ #include "filesys/fsutil.h" #include "threads/malloc.h" -/* Initializes D as a directory that holds ENTRY_CNT entries. */ -bool -dir_init (struct dir *d, size_t entry_cnt) +/* A directory. */ +struct dir + { + size_t entry_cnt; /* Number of entries. */ + struct dir_entry *entries; /* Array of entries. */ + }; + +/* A single directory entry. */ +struct dir_entry + { + bool in_use; /* In use or free? */ + char name[NAME_MAX + 1]; /* Null terminated file name. */ + disk_sector_t inode_sector; /* Sector number of header. */ + }; + +/* Returns a new directory that holds ENTRY_CNT entries, if + successful, or a null pointer if memory is unavailable. */ +struct dir * +dir_create (size_t entry_cnt) { - ASSERT (d != NULL); - d->entry_cnt = entry_cnt; - d->entries = calloc (1, sizeof *d->entries * entry_cnt); - return d->entries != NULL; + struct dir *d = malloc (sizeof *d); + if (d != NULL) + { + d->entry_cnt = entry_cnt; + d->entries = calloc (1, sizeof *d->entries * entry_cnt); + if (d->entries != NULL) + return d; + free (d); + } + return NULL; +} + +/* Returns the size, in bytes, of a directory with ENTRY_CNT + entries. */ +size_t +dir_size (size_t entry_cnt) +{ + return entry_cnt * sizeof (struct dir_entry); } /* Destroys D and frees associated resources. */ @@ -20,15 +50,10 @@ void dir_destroy (struct dir *d) { if (d != NULL) - free (d->entries); -} - -/* Returns the size of D in bytes. */ -static off_t -dir_size (struct dir *d) -{ - ASSERT (d != NULL); - return d->entry_cnt * sizeof *d->entries; + { + free (d->entries); + free (d); + } } /* Reads D from FILE. @@ -39,9 +64,9 @@ dir_read (struct dir *d, struct file *file) { ASSERT (d != NULL); ASSERT (file != NULL); - ASSERT (file_length (file) >= dir_size (d)); + ASSERT (file_length (file) >= (off_t) dir_size (d->entry_cnt)); - file_read_at (file, d->entries, dir_size (d), 0); + file_read_at (file, d->entries, dir_size (d->entry_cnt), 0); } /* Writes D to FILE. @@ -50,7 +75,7 @@ dir_read (struct dir *d, struct file *file) void dir_write (struct dir *d, struct file *file) { - file_write_at (file, d->entries, dir_size (d), 0); + file_write_at (file, d->entries, dir_size (d->entry_cnt), 0); } /* Searches D for a file named NAME. @@ -78,11 +103,11 @@ lookup (const struct dir *d, const char *name) /* Searches D for a file named NAME and returns true if one exists, false otherwise. - If FILEHDR_SECTOR is nonnull, then on success *FILEHDR_SECTOR - is set to the sector that contains the file's header. */ + If INODE_SECTOR is nonnull, then on success *INODE_SECTOR + is set to the sector that contains the file's inode. */ bool dir_lookup (const struct dir *d, const char *name, - disk_sector_t *filehdr_sector) + disk_sector_t *inode_sector) { const struct dir_entry *e; @@ -92,8 +117,8 @@ dir_lookup (const struct dir *d, const char *name, e = lookup (d, name); if (e != NULL) { - if (filehdr_sector != NULL) - *filehdr_sector = e->filehdr_sector; + if (inode_sector != NULL) + *inode_sector = e->inode_sector; return true; } else @@ -101,13 +126,13 @@ dir_lookup (const struct dir *d, const char *name, } /* Adds a file named NAME to D, which must not already contain a - file by that name. The file's header is in sector - FILEHDR_SECTOR. + file by that name. The file's inode is in sector + INODE_SECTOR. Returns true if successful, false on failure. Fails if NAME is invalid (i.e. too long) or if D has no free directory entries. */ bool -dir_add (struct dir *d, const char *name, disk_sector_t filehdr_sector) +dir_add (struct dir *d, const char *name, disk_sector_t inode_sector) { size_t i; @@ -125,7 +150,7 @@ dir_add (struct dir *d, const char *name, disk_sector_t filehdr_sector) { e->in_use = true; strlcpy (e->name, name, sizeof e->name); - e->filehdr_sector = filehdr_sector; + e->inode_sector = inode_sector; return true; } } diff --git a/src/filesys/directory.h b/src/filesys/directory.h index 4464d46..6503a30 100644 --- a/src/filesys/directory.h +++ b/src/filesys/directory.h @@ -10,23 +10,9 @@ (This macro name comes from POSIX.1.) */ #define NAME_MAX 14 -/* A directory. */ -struct dir - { - size_t entry_cnt; /* Number of entries. */ - struct dir_entry *entries; /* Array of entries. */ - }; - -/* A single directory entry. */ -struct dir_entry - { - bool in_use; /* In use or free? */ - char name[NAME_MAX + 1]; /* Null terminated file name. */ - disk_sector_t filehdr_sector; /* Sector number of header. */ - }; - struct file; -bool dir_init (struct dir *, size_t entry_cnt); +struct dir *dir_create (size_t entry_cnt); +size_t dir_size (size_t entry_cnt); void dir_destroy (struct dir *); void dir_read (struct dir *, struct file *); void dir_write (struct dir *, struct file *); diff --git a/src/filesys/file.c b/src/filesys/file.c index e1a70f3..d059f37 100644 --- a/src/filesys/file.c +++ b/src/filesys/file.c @@ -2,32 +2,56 @@ #include #include #include "filesys/directory.h" -#include "filesys/filehdr.h" +#include "filesys/inode.h" #include "filesys/filesys.h" #include "threads/malloc.h" -bool -file_open (struct file *file, disk_sector_t hdr_sector) +/* An open file. */ +struct file + { + struct inode *inode; /* File's inode. */ + uint8_t *bounce; /* Bounce buffer for reads and writes. */ + off_t pos; /* Current position. */ + }; + +/* Opens and returns the file whose inode is in sector + INODE_SECTOR. Returns a null pointer if unsuccessful. */ +struct file * +file_open (disk_sector_t inode_sector) { - file->hdr = filehdr_read (hdr_sector); + struct file *file = calloc (1, sizeof *file); + if (file == NULL) + return NULL; + + file->inode = inode_open (inode_sector); file->bounce = malloc (DISK_SECTOR_SIZE); file->pos = 0; - if (file->hdr != NULL && file->bounce != NULL) - return true; - else + if (file->inode == NULL || file->bounce == NULL) { - filehdr_destroy (file->hdr); + inode_close (file->inode); free (file->bounce); - return false; + return NULL; } + + return file; } +/* Closes FILE. */ void file_close (struct file *file) { - filehdr_destroy (file->hdr); + if (file == NULL) + return; + + inode_close (file->inode); + free (file->bounce); } +/* Reads SIZE bytes from FILE into BUFFER, + starting at the file's current position, + and advances the current position. + Returns the number of bytes actually read, + which may be less than SIZE if end of file is reached. */ off_t file_read (struct file *file, void *buffer, off_t size) { @@ -36,6 +60,11 @@ file_read (struct file *file, void *buffer, off_t size) return bytes_read; } +/* Reads SIZE bytes from FILE into BUFFER, + starting at offset FILE_OFS in the file. + The file's current position is unaffected + Returns the number of bytes actually read, + which may be less than SIZE if end of file is reached. */ off_t file_read_at (struct file *file, void *buffer_, off_t size, off_t file_ofs) @@ -46,11 +75,11 @@ file_read_at (struct file *file, void *buffer_, off_t size, while (size > 0) { /* Disk sector to read, starting byte offset within sector. */ - off_t sector_idx = filehdr_byte_to_sector (file->hdr, file_ofs); + off_t sector_idx = inode_byte_to_sector (file->inode, file_ofs); int sector_ofs = file_ofs % DISK_SECTOR_SIZE; /* Bytes left in file, bytes left in sector, lesser of the two. */ - off_t file_left = filehdr_length (file->hdr) - file_ofs; + off_t file_left = inode_length (file->inode) - file_ofs; int sector_left = DISK_SECTOR_SIZE - sector_ofs; int min_left = file_left < sector_left ? file_left : sector_left; @@ -73,6 +102,13 @@ file_read_at (struct file *file, void *buffer_, off_t size, return bytes_read; } +/* Writes SIZE bytes from BUFFER into FILE, + starting at the file's current position, + and advances the current position. + Returns the number of bytes actually written, + which may be less than SIZE if end of file is reached. + (Normally we'd grow the file in that case, but file growth is + not yet implemented.) */ off_t file_write (struct file *file, const void *buffer, off_t size) { @@ -81,6 +117,13 @@ file_write (struct file *file, const void *buffer, off_t size) return bytes_written; } +/* Writes SIZE bytes from BUFFER into FILE, + starting at offset FILE_OFS in the file. + The file's current position is unaffected + Returns the number of bytes actually written, + which may be less than SIZE if end of file is reached. + (Normally we'd grow the file in that case, but file growth is + not yet implemented.) */ off_t file_write_at (struct file *file, const void *buffer_, off_t size, off_t file_ofs) @@ -91,11 +134,11 @@ file_write_at (struct file *file, const void *buffer_, off_t size, while (size > 0) { /* Starting byte offset within sector to read. */ - off_t sector_idx = filehdr_byte_to_sector (file->hdr, file_ofs); + off_t sector_idx = inode_byte_to_sector (file->inode, file_ofs); int sector_ofs = file_ofs % DISK_SECTOR_SIZE; /* Bytes left in file, bytes left in sector, lesser of the two. */ - off_t file_left = filehdr_length (file->hdr) - file_ofs; + off_t file_left = inode_length (file->inode) - file_ofs; int sector_left = DISK_SECTOR_SIZE - sector_ofs; int min_left = file_left < sector_left ? file_left : sector_left; @@ -123,13 +166,16 @@ file_write_at (struct file *file, const void *buffer_, off_t size, return bytes_written; } +/* Returns the size of FILE in bytes. */ off_t file_length (struct file *file) { ASSERT (file != NULL); - return filehdr_length (file->hdr); + return inode_length (file->inode); } +/* Sets the current position in FILE to an offset of FILE_OFS + bytes from the start of the file. */ void file_seek (struct file *file, off_t file_ofs) { @@ -138,6 +184,8 @@ file_seek (struct file *file, off_t file_ofs) file->pos = file_ofs; } +/* Returns the current position in FILE as a byte offset from the + start of the file. */ off_t file_tell (struct file *file) { diff --git a/src/filesys/file.h b/src/filesys/file.h index ea716aa..c28201d 100644 --- a/src/filesys/file.h +++ b/src/filesys/file.h @@ -1,20 +1,11 @@ #ifndef FILESYS_FILE_H #define FILESYS_FILE_H -#include -#include #include #include "devices/disk.h" #include "filesys/off_t.h" -struct file - { - struct filehdr *hdr; - void *bounce; - off_t pos; - }; - -bool file_open (struct file *, disk_sector_t); +struct file *file_open (disk_sector_t); void file_close (struct file *); off_t file_read (struct file *, void *, off_t); off_t file_read_at (struct file *, void *, off_t size, off_t start); @@ -23,5 +14,6 @@ off_t file_write_at (struct file *, const void *, off_t size, off_t start); off_t file_length (struct file *); void file_seek (struct file *, off_t); off_t file_tell (struct file *); +void file_remove (struct file *); #endif /* filesys/file.h */ diff --git a/src/filesys/filehdr.c b/src/filesys/filehdr.c deleted file mode 100644 index 5817912..0000000 --- a/src/filesys/filehdr.c +++ /dev/null @@ -1,137 +0,0 @@ -#include "filesys/filehdr.h" -#include -#include -#include -#include "filesys/filesys.h" -#include "threads/malloc.h" - -/* Allocates sectors from bitmap B for the content of a file - whose size is LENGTH bytes, and returns a new `struct filehdr' - properly initialized for the file. - It is the caller's responsible to allocate a sector for the - file header itself, and to write the file header and bitmap - to disk. - If memory or disk allocation fails, returns a null pointer, - leaving bitmap B is unchanged. */ -struct filehdr * -filehdr_allocate (struct bitmap *b, off_t length) -{ - struct filehdr *h; - size_t sector_cnt; - - ASSERT (b != NULL); - ASSERT (length >= 0); - - sector_cnt = (length / DISK_SECTOR_SIZE) + (length % DISK_SECTOR_SIZE > 0); - if (sector_cnt > DIRECT_CNT) - return false; - - h = calloc (1, sizeof *h); - if (h == NULL) - return NULL; - - h->length = length; - while (h->sector_cnt < sector_cnt) - { - size_t sector = bitmap_find_and_set (b); - if (sector == BITMAP_ERROR) - { - filehdr_deallocate (h, b); - free (h); - return NULL; - } - h->sectors[h->sector_cnt++] = sector; - } - - return h; -} - -/* Marks the sectors for H's content as free in bitmap B. - Neither H's own disk sector nor its memory are freed. */ -void -filehdr_deallocate (struct filehdr *h, struct bitmap *b) -{ - size_t i; - - ASSERT (h != NULL); - ASSERT (b != NULL); - - for (i = 0; i < h->sector_cnt; i++) - bitmap_reset (b, h->sectors[i]); -} - -/* Reads a file header from FILEHDR_SECTOR - and returns a new `struct filehdr' that contains it. - Returns a null pointer fi memory allocation fails. */ -struct filehdr * -filehdr_read (disk_sector_t filehdr_sector) -{ - struct filehdr *h = calloc (1, sizeof *h); - if (h == NULL) - return NULL; - - ASSERT (sizeof *h == DISK_SECTOR_SIZE); - disk_read (filesys_disk, filehdr_sector, h); - - return h; -} - -/* Writes H to disk in sector FILEHDR_SECTOR. */ -void -filehdr_write (const struct filehdr *h, disk_sector_t filehdr_sector) -{ - ASSERT (h != NULL); - ASSERT (sizeof *h == DISK_SECTOR_SIZE); - disk_write (filesys_disk, filehdr_sector, h); -} - -/* Frees the memory (but not the on-disk sector) associated with - H. */ -void -filehdr_destroy (struct filehdr *h) -{ - free (h); -} - -/* Returns the disk sector that contains byte offset POS within - the file with header H. - Returns -1 if H does not contain data for a byte at offset - POS. */ -disk_sector_t -filehdr_byte_to_sector (const struct filehdr *h, off_t pos) -{ - size_t idx; - - ASSERT (h != NULL); - - idx = pos / DISK_SECTOR_SIZE; - return idx < h->sector_cnt ? h->sectors[idx] : (disk_sector_t) -1; -} - -/* Returns the length, in bytes, of the file with header H, */ -off_t -filehdr_length (const struct filehdr *h) -{ - ASSERT (h != NULL); - return h->length; -} - -/* Prints a representation of H to the system console. */ -void -filehdr_print (const struct filehdr *h) -{ - size_t i; - - printf ("File header: %jd bytes, %zd sectors (", - (intmax_t) h->length, h->sector_cnt); - - /* This loop could be unsafe for large h->sector_cnt, can you - see why? */ - for (i = 0; i < h->sector_cnt; i++) - { - if (i != 0) - printf (", "); - printf ("%jd", (intmax_t) h->sectors[i]); - } - printf (")\n"); -} diff --git a/src/filesys/filehdr.h b/src/filesys/filehdr.h deleted file mode 100644 index 60bca96..0000000 --- a/src/filesys/filehdr.h +++ /dev/null @@ -1,32 +0,0 @@ -#ifndef FILESYS_FILEHDR_H -#define FILESYS_FILEHDR_H - -#include -#include -#include "filesys/off_t.h" -#include "devices/disk.h" - -/* Number of direct sector pointers in a file header. */ -#define DIRECT_CNT ((DISK_SECTOR_SIZE - sizeof (off_t) * 2) \ - / sizeof (disk_sector_t)) - -/* File header. - This is both an in-memory and on-disk structure. */ -struct filehdr - { - 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. */ - }; - -struct bitmap; -struct filehdr *filehdr_allocate (struct bitmap *, off_t length); -void filehdr_deallocate (struct filehdr *, struct bitmap *); -struct filehdr *filehdr_read (disk_sector_t); -void filehdr_write (const struct filehdr *, disk_sector_t); -void filehdr_destroy (struct filehdr *); -disk_sector_t filehdr_byte_to_sector (const struct filehdr *, off_t); -off_t filehdr_length (const struct filehdr *); -void filehdr_print (const struct filehdr *); - -#endif /* filesys/filehdr.h */ diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index c0e3938..8bd39e8 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -32,47 +32,53 @@ #include #include #include "filesys/file.h" -#include "filesys/filehdr.h" +#include "filesys/inode.h" #include "filesys/directory.h" #include "devices/disk.h" /* Filesystem. + For the purposes of the "user processes" assignment (project + 2), please treat all the code in the filesys directory as a + black box. No changes should be needed. For that project, a + single lock external to the filesystem code suffices. + The filesystem consists of a set of files. Each file has a - header, represented by struct filehdr, that is stored by - itself in a single sector (see filehdr.h). The header - contains the file's length in bytes and an array that lists - the sector numbers for the file's contents. + header called an `index node' or `inode', represented by + struct inode, that is stored by itself in a single sector (see + inode.h). The header contains the file's length in bytes and + an array that lists the sector numbers for the file's + contents. Two files are special. The first special file is the free - map, whose header is always stored in sector 0 + map, whose inode is always stored in sector 0 (FREE_MAP_SECTOR). The free map stores a bitmap (see lib/bitmap.h) that contains one bit for each sector on the disk. Each bit that corresponds to a sector within a file is set to true, and the other bits, which are not part of any file, are set to false. - The second special file is the root directory, whose header is + The second special file is the root directory, whose inode is always stored in sector 1 (ROOT_DIR_SECTOR). The root directory file stores an array of `struct dir_entry' (see directory.h), each of which, if it is in use, associates a - filename with the sector of the file's header. + filename with the sector of the file's inode. The filesystem implemented here has the following limitations: - No synchronization. Concurrent accesses will interfere - with one another. + with one another, so external synchronization is needed. - 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. - No indirect blocks. This limits maximum file size to the - number of sector pointers that fit in a single sector + 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. - - No nested subdirectories. + - No subdirectories. - Filenames limited to 14 characters. @@ -80,27 +86,26 @@ that cannot be repaired automatically. No `fsck' tool is provided in any case. - Note: for the purposes of the "user processes" assignment - (project 2), please treat all the code in the filesys - directory as a black box. No changes should be needed. For - that project, a single lock external to the filesystem code - suffices. */ + However one important feature is included: + + - 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. */ -/* File header sectors for system files. */ -#define FREE_MAP_SECTOR 0 /* Free map file header sector. */ -#define ROOT_DIR_SECTOR 1 /* Root directory file header sector. */ +/* Sectors of system file inodes. */ +#define FREE_MAP_SECTOR 0 /* Free map file inode sector. */ +#define ROOT_DIR_SECTOR 1 /* Root directory file inode sector. */ /* Root directory. */ #define NUM_DIR_ENTRIES 10 /* Maximum number of directory entries. */ -#define ROOT_DIR_FILE_SIZE /* Root directory file size in bytes. */ \ - (sizeof (struct dir_entry) * NUM_DIR_ENTRIES) /* The disk that contains the filesystem. */ struct disk *filesys_disk; /* The free map and root directory files. These files are opened by filesys_init() and never closed. */ -static struct file free_map_file, root_dir_file; +struct file *free_map_file, *root_dir_file; static void do_format (void); @@ -109,6 +114,8 @@ static void do_format (void); void filesys_init (bool format) { + inode_init (); + filesys_disk = disk_get (0, 1); if (filesys_disk == NULL) PANIC ("hd0:1 (hdb) not present, filesystem initialization failed"); @@ -116,9 +123,11 @@ filesys_init (bool format) if (format) do_format (); - if (!file_open (&free_map_file, FREE_MAP_SECTOR)) + free_map_file = file_open (FREE_MAP_SECTOR); + if (free_map_file == NULL) PANIC ("can't open free map file"); - if (!file_open (&root_dir_file, ROOT_DIR_SECTOR)) + root_dir_file = file_open (ROOT_DIR_SECTOR); + if (root_dir_file == NULL) PANIC ("can't open root dir file"); } @@ -129,49 +138,50 @@ filesys_init (bool format) bool filesys_create (const char *name, off_t initial_size) { - struct dir dir; - struct bitmap free_map; - disk_sector_t hdr_sector; - struct filehdr *filehdr; + struct dir *dir = NULL; + struct bitmap *free_map = NULL; + struct inode *inode = NULL; + disk_sector_t inode_sector; bool success = false; /* Read the root directory. */ - if (!dir_init (&dir, NUM_DIR_ENTRIES)) - return false; - dir_read (&dir, &root_dir_file); - if (dir_lookup (&dir, name, NULL)) - goto exit1; - - /* Allocate a block for the file header. */ - if (!bitmap_init (&free_map, disk_size (filesys_disk))) - goto exit1; - bitmap_read (&free_map, &free_map_file); - hdr_sector = bitmap_find_and_set (&free_map); - if (hdr_sector == BITMAP_ERROR) - goto exit2; + dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) + goto done; + dir_read (dir, root_dir_file); + if (dir_lookup (dir, name, NULL)) + goto done; + + /* Allocate a block for the inode. */ + free_map = bitmap_create (disk_size (filesys_disk)); + if (free_map == NULL) + goto done; + bitmap_read (free_map, free_map_file); + inode_sector = bitmap_find_and_set (free_map); + if (inode_sector == BITMAP_ERROR) + goto done; /* Add the file to the directory. */ - if (!dir_add (&dir, name, hdr_sector)) - goto exit2; + if (!dir_add (dir, name, inode_sector)) + goto done; /* Allocate space for the file. */ - filehdr = filehdr_allocate (&free_map, initial_size); - if (filehdr == NULL) - goto exit2; + inode = inode_create (free_map, inode_sector, initial_size); + if (inode == NULL) + goto done; /* Write everything back. */ - filehdr_write (filehdr, hdr_sector); - dir_write (&dir, &root_dir_file); - bitmap_write (&free_map, &free_map_file); + inode_commit (inode); + dir_write (dir, root_dir_file); + bitmap_write (free_map, free_map_file); success = true; /* Clean up. */ - filehdr_destroy (filehdr); - exit2: - bitmap_destroy (&free_map); - exit1: - dir_destroy (&dir); + done: + inode_close (inode); + bitmap_destroy (free_map); + dir_destroy (dir); return success; } @@ -181,21 +191,25 @@ filesys_create (const char *name, off_t initial_size) Returns true if successful, false on failure. Fails if no file named NAME exists, or if an internal memory allocation fails. */ -bool -filesys_open (const char *name, struct file *file) +struct file * +filesys_open (const char *name) { - struct dir dir; - disk_sector_t hdr_sector; - bool success = false; + struct dir *dir = NULL; + struct file *file = NULL; + disk_sector_t inode_sector; - if (!dir_init (&dir, NUM_DIR_ENTRIES)) - return false; - dir_read (&dir, &root_dir_file); - if (dir_lookup (&dir, name, &hdr_sector)) - success = file_open (file, hdr_sector); - - dir_destroy (&dir); - return success; + dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) + goto done; + + dir_read (dir, root_dir_file); + if (dir_lookup (dir, name, &inode_sector)) + file = file_open (inode_sector); + + done: + dir_destroy (dir); + + return file; } /* Deletes the file named NAME. @@ -205,46 +219,36 @@ filesys_open (const char *name, struct file *file) bool filesys_remove (const char *name) { - struct dir dir; - disk_sector_t hdr_sector; - struct filehdr *filehdr; - struct bitmap free_map; + struct dir *dir = NULL; + struct inode *inode; + disk_sector_t inode_sector; bool success = false; /* Read the root directory. */ - if (!dir_init (&dir, NUM_DIR_ENTRIES)) - return false; - dir_read (&dir, &root_dir_file); - if (!dir_lookup (&dir, name, &hdr_sector)) - goto exit1; - - /* Read the file header. */ - filehdr = filehdr_read (hdr_sector); - if (filehdr == NULL) - goto exit1; - - /* Allocate a block for the file header. */ - if (!bitmap_init (&free_map, disk_size (filesys_disk))) - goto exit2; - bitmap_read (&free_map, &free_map_file); - - /* Deallocate. */ - filehdr_deallocate (filehdr, &free_map); - bitmap_reset (&free_map, hdr_sector); - dir_remove (&dir, name); - - /* Write everything back. */ - bitmap_write (&free_map, &free_map_file); - dir_write (&dir, &root_dir_file); + dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) + goto done; + dir_read (dir, root_dir_file); + if (!dir_lookup (dir, name, &inode_sector)) + goto done; + + /* Open the inode and delete it it. */ + inode = inode_open (inode_sector); + if (inode == NULL) + goto done; + inode_remove (inode); + inode_close (inode); + + /* Remove file from root directory and write directory back to + disk. */ + dir_remove (dir, name); + dir_write (dir, root_dir_file); success = true; /* Clean up. */ - bitmap_destroy (&free_map); - exit2: - filehdr_destroy (filehdr); - exit1: - dir_destroy (&dir); + done: + dir_destroy (dir); return success; } @@ -256,13 +260,12 @@ filesys_remove (const char *name) bool filesys_list (void) { - struct dir dir; - - if (!dir_init (&dir, NUM_DIR_ENTRIES)) + struct dir *dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) return false; - dir_read (&dir, &root_dir_file); - dir_list (&dir); - dir_destroy (&dir); + dir_read (dir, root_dir_file); + dir_list (dir); + dir_destroy (dir); return true; } @@ -274,22 +277,24 @@ filesys_list (void) bool filesys_dump (void) { - struct bitmap free_map; - struct dir dir; + struct bitmap *free_map; + struct dir *dir; printf ("Free map:\n"); - if (!bitmap_init (&free_map, disk_size (filesys_disk))) + free_map = bitmap_create (disk_size (filesys_disk)); + if (free_map == NULL) return false; - bitmap_read (&free_map, &free_map_file); - bitmap_dump (&free_map); - bitmap_destroy (&free_map); + bitmap_read (free_map, free_map_file); + bitmap_dump (free_map); + bitmap_destroy (free_map); printf ("\n"); - if (!dir_init (&dir, NUM_DIR_ENTRIES)) + dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) return false; - dir_read (&dir, &root_dir_file); - dir_dump (&dir); - dir_destroy (&dir); + dir_read (dir, root_dir_file); + dir_dump (dir); + dir_destroy (dir); return true; } @@ -304,25 +309,45 @@ void filesys_self_test (void) { static const char s[] = "This is a test string."; - struct file file; + static const char zeros[sizeof s] = {0}; + struct file *file; char s2[sizeof s]; - - MUST_SUCCEED (filesys_create ("foo", sizeof s)); - MUST_SUCCEED (filesys_open ("foo", &file)); - MUST_SUCCEED (file_write (&file, s, sizeof s) == sizeof s); - MUST_SUCCEED (file_tell (&file) == sizeof s); - MUST_SUCCEED (file_length (&file) == sizeof s); - file_close (&file); - - MUST_SUCCEED (filesys_open ("foo", &file)); - MUST_SUCCEED (file_read (&file, s2, sizeof s2) == sizeof s2); - MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0); - MUST_SUCCEED (file_tell (&file) == sizeof s2); - MUST_SUCCEED (file_length (&file) == sizeof s2); - file_close (&file); - - MUST_SUCCEED (filesys_remove ("foo")); - + int i; + + filesys_remove ("foo"); + for (i = 0; i < 2; i++) + { + /* Create file and check that it contains zeros + throughout the created length. */ + MUST_SUCCEED (filesys_create ("foo", sizeof s)); + MUST_SUCCEED ((file = filesys_open ("foo")) != NULL); + MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2); + MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0); + MUST_SUCCEED (file_tell (file) == sizeof s); + MUST_SUCCEED (file_length (file) == sizeof s); + file_close (file); + + /* Reopen file and write to it. */ + MUST_SUCCEED ((file = filesys_open ("foo")) != NULL); + MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s); + MUST_SUCCEED (file_tell (file) == sizeof s); + MUST_SUCCEED (file_length (file) == sizeof s); + file_close (file); + + /* Reopen file and verify that it reads back correctly. + Delete file while open to check proper semantics. */ + MUST_SUCCEED ((file = filesys_open ("foo")) != NULL); + MUST_SUCCEED (filesys_remove ("foo")); + MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s); + MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0); + MUST_SUCCEED (file_tell (file) == sizeof s); + MUST_SUCCEED (file_length (file) == sizeof s); + file_close (file); + + /* Make sure file is deleted. */ + MUST_SUCCEED ((file = filesys_open ("foo")) == NULL); + } + printf ("filesys: self test ok\n"); } @@ -330,51 +355,57 @@ filesys_self_test (void) static void do_format (void) { - struct bitmap free_map; - struct filehdr *map_hdr, *dir_hdr; - struct dir dir; + struct bitmap *free_map; + struct inode *map_inode, *dir_inode; + struct dir *dir; printf ("Formatting filesystem..."); /* Create the initial bitmap and reserve sectors for the - free map and root directory file headers. */ - if (!bitmap_init (&free_map, disk_size (filesys_disk))) + free map and root directory inodes. */ + free_map = bitmap_create (disk_size (filesys_disk)); + if (free_map == NULL) PANIC ("bitmap creation failed--disk is too large"); - bitmap_mark (&free_map, FREE_MAP_SECTOR); - bitmap_mark (&free_map, ROOT_DIR_SECTOR); + bitmap_mark (free_map, FREE_MAP_SECTOR); + bitmap_mark (free_map, ROOT_DIR_SECTOR); /* Allocate data sector(s) for the free map file - and write its file header to disk. */ - map_hdr = filehdr_allocate (&free_map, bitmap_file_size (&free_map)); - if (map_hdr == NULL) + and write its inode to disk. */ + map_inode = inode_create (free_map, FREE_MAP_SECTOR, + bitmap_file_size (free_map)); + if (map_inode == NULL) PANIC ("free map creation failed--disk is too large"); - filehdr_write (map_hdr, FREE_MAP_SECTOR); - filehdr_destroy (map_hdr); + inode_commit (map_inode); + inode_close (map_inode); /* Allocate data sector(s) for the root directory file - and write its file header to disk. */ - dir_hdr = filehdr_allocate (&free_map, ROOT_DIR_FILE_SIZE); - if (dir_hdr == NULL) + and write its inodes to disk. */ + dir_inode = inode_create (free_map, ROOT_DIR_SECTOR, + dir_size (NUM_DIR_ENTRIES)); + if (dir_inode == NULL) PANIC ("root directory creation failed"); - filehdr_write (dir_hdr, ROOT_DIR_SECTOR); - filehdr_destroy (dir_hdr); + inode_commit (dir_inode); + inode_close (dir_inode); /* Write out the free map now that we have space reserved for it. */ - if (!file_open (&free_map_file, FREE_MAP_SECTOR)) + free_map_file = file_open (FREE_MAP_SECTOR); + if (free_map_file == NULL) PANIC ("can't open free map file"); - bitmap_write (&free_map, &free_map_file); - bitmap_destroy (&free_map); - file_close (&free_map_file); + bitmap_write (free_map, free_map_file); + bitmap_destroy (free_map); + file_close (free_map_file); /* Write out the root directory in the same way. */ - if (!file_open (&root_dir_file, ROOT_DIR_SECTOR)) + root_dir_file = file_open (ROOT_DIR_SECTOR); + if (root_dir_file == NULL) PANIC ("can't open root directory"); - if (!dir_init (&dir, NUM_DIR_ENTRIES)) + dir = dir_create (NUM_DIR_ENTRIES); + if (dir == NULL) PANIC ("can't initialize root directory"); - dir_write (&dir, &root_dir_file); - dir_destroy (&dir); - file_close (&free_map_file); + dir_write (dir, root_dir_file); + dir_destroy (dir); + file_close (root_dir_file); printf ("done.\n"); } diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h index 44c89f4..0105101 100644 --- a/src/filesys/filesys.h +++ b/src/filesys/filesys.h @@ -2,16 +2,18 @@ #define FILESYS_FILESYS_H #include -#include #include "filesys/off_t.h" /* Disk used for filesystem. */ extern struct disk *filesys_disk; -struct file; +/* The free map file, opened by filesys_init() and never + closed. */ +extern struct file *free_map_file; + void filesys_init (bool format); bool filesys_create (const char *name, off_t initial_size); -bool filesys_open (const char *name, struct file *); +struct file *filesys_open (const char *name); bool filesys_remove (const char *name); bool filesys_list (void); bool filesys_dump (void); diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c index a51fac6..3876ee9 100644 --- a/src/filesys/fsutil.c +++ b/src/filesys/fsutil.c @@ -32,7 +32,7 @@ static void copy (const char *filename, off_t size) { struct disk *src; - struct file dst; + struct file *dst; disk_sector_t sector; void *buffer; @@ -47,7 +47,8 @@ copy (const char *filename, off_t size) /* Create destination file. */ if (!filesys_create (filename, size)) PANIC ("%s: create failed", filename); - if (!filesys_open (filename, &dst)) + dst = filesys_open (filename); + if (dst == NULL) PANIC ("%s: open failed", filename); /* Do copy. */ @@ -57,14 +58,14 @@ copy (const char *filename, off_t size) { int chunk_size = size > DISK_SECTOR_SIZE ? DISK_SECTOR_SIZE : size; disk_read (src, sector++, buffer); - if (file_write (&dst, buffer, chunk_size) != chunk_size) + if (file_write (dst, buffer, chunk_size) != chunk_size) PANIC ("%s: write failed with %lld bytes unwritten", filename, (unsigned long long) size); size -= chunk_size; } palloc_free (buffer); - file_close (&dst); + file_close (dst); } /* Executes the filesystem operations described by the variables @@ -107,20 +108,21 @@ fsutil_run (void) void fsutil_print (const char *filename) { - struct file file; + struct file *file; char *buffer; - if (!filesys_open (filename, &file)) + file = filesys_open (filename); + if (file == NULL) PANIC ("%s: open failed", filename); buffer = palloc_get (PAL_ASSERT); for (;;) { - off_t n = file_read (&file, buffer, PGSIZE); + off_t n = file_read (file, buffer, PGSIZE); if (n == 0) break; hex_dump (buffer, n, true); } palloc_free (buffer); - file_close (&file); + file_close (file); } diff --git a/src/filesys/inode.c b/src/filesys/inode.c new file mode 100644 index 0000000..dbec4b9 --- /dev/null +++ b/src/filesys/inode.c @@ -0,0 +1,250 @@ +#include "filesys/inode.h" +#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. */ +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. */ + }; + +/* In-memory inode. */ +struct inode + { + 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. */ + struct inode_disk data; /* On-disk data. */ + }; + +/* List of open inodes, so that opening a single inode twice + returns the same `struct inode'. */ +struct list open_inodes; + +static struct inode *alloc_inode (disk_sector_t); + +/* Initializes the inode module. */ +void +inode_init (void) +{ + list_init (&open_inodes); +} + +/* Allocates sectors from bitmap B for the content of a file + whose size is LENGTH bytes, and returns a new `struct inode' + properly initialized for the file. + It is the caller's responsible to write the inode to disk with + inode_commit(), as well as the bitmap. + If memory or disk allocation fails, returns a null pointer, + leaving bitmap B is unchanged. */ +struct inode * +inode_create (struct bitmap *b, disk_sector_t sector, off_t length) +{ + struct inode *idx; + size_t sector_cnt; + + 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. */ + idx->data.length = length; + while (idx->data.sector_cnt < sector_cnt) + { + size_t sector = bitmap_find_and_set (b); + if (sector == BITMAP_ERROR) + goto error; + + idx->data.sectors[idx->data.sector_cnt++] = sector; + } + + /* Zero out the file contents. */ + if (sector_cnt > 0) + { + void *zero_sector; + size_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); + } + + return idx; + + error: + inode_remove (idx); + inode_close (idx); + return NULL; +} + +/* Reads an inode from SECTOR + and returns a `struct inode' that contains it. + Returns a null pointer if memory allocation fails. */ +struct inode * +inode_open (disk_sector_t sector) +{ + list_elem *e; + struct inode *idx; + + /* Check whether this inode is already open. */ + for (e = list_begin (&open_inodes); e != list_end (&open_inodes); + e = list_next (e)) + { + idx = list_entry (e, struct inode, elem); + if (idx->sector == sector) + { + idx->open_cnt++; + return idx; + } + } + + /* Allocate inode. */ + idx = alloc_inode (sector); + if (idx == NULL) + return NULL; + + /* Read from disk. */ + ASSERT (sizeof idx->data == DISK_SECTOR_SIZE); + disk_read (filesys_disk, sector, &idx->data); + + return idx; +} + +/* Closes inode IDX and writes it to disk. + If this was the last reference to IDX, frees its memory. + If IDX was also a removed inode, frees its blocks. */ +void +inode_close (struct inode *idx) +{ + if (idx == NULL) + return; + + if (--idx->open_cnt == 0) + { + 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); + + bitmap_reset (free_map, idx->sector); + for (i = 0; i < idx->data.sector_cnt; i++) + bitmap_reset (free_map, idx->data.sectors[i]); + + bitmap_write (free_map, free_map_file); + bitmap_destroy (free_map); + } + else + printf ("inode_close(): can't free blocks"); + } + list_remove (&idx->elem); + free (idx); + } +} + +/* Writes IDX to disk. */ +void +inode_commit (const struct inode *idx) +{ + ASSERT (idx != NULL); + ASSERT (sizeof idx->data == DISK_SECTOR_SIZE); + disk_write (filesys_disk, idx->sector, &idx->data); +} + +/* Marks IDX to be deleted when it is closed by the last caller who + has it open. */ +void +inode_remove (struct inode *idx) +{ + ASSERT (idx != NULL); + idx->removed = true; +} + +/* Returns the disk sector that contains byte offset POS within + the file with inode IDX. + Returns -1 if IDX does not contain data for a byte at offset + POS. */ +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; +} + +/* Returns the length, in bytes, of the file with inode IDX. */ +off_t +inode_length (const struct inode *idx) +{ + ASSERT (idx != NULL); + return idx->data.length; +} + +/* Prints a representation of IDX to the system console. */ +void +inode_print (const struct inode *idx) +{ + size_t i; + + printf ("Inode %"PRDSNu": %"PRDSNu" bytes, %zd 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"); +} + +/* Returns a newly allocated and initialized inode. */ +static struct inode * +alloc_inode (disk_sector_t sector) +{ + /* Allocate memory. */ + struct inode *idx = calloc (1, sizeof *idx); + if (idx == NULL) + return NULL; + + /* Initialize. */ + list_push_front (&open_inodes, &idx->elem); + idx->sector = sector; + idx->open_cnt = 1; + idx->removed = false; + + return idx; +} diff --git a/src/filesys/inode.h b/src/filesys/inode.h new file mode 100644 index 0000000..d7fe86b --- /dev/null +++ b/src/filesys/inode.h @@ -0,0 +1,19 @@ +#ifndef FILESYS_INODE_H +#define FILESYS_INODE_H + +#include "filesys/off_t.h" +#include "devices/disk.h" + +struct bitmap; + +void inode_init (void); +struct inode *inode_create (struct bitmap *, disk_sector_t, off_t); +struct inode *inode_open (disk_sector_t); +void inode_close (struct inode *); +void inode_commit (const struct inode *); +void inode_remove (struct inode *); +disk_sector_t inode_byte_to_sector (const struct inode *, off_t); +off_t inode_length (const struct inode *); +void inode_print (const struct inode *); + +#endif /* filesys/inode.h */ diff --git a/src/userprog/addrspace.c b/src/userprog/addrspace.c index ea8767c..65c09e4 100644 --- a/src/userprog/addrspace.c +++ b/src/userprog/addrspace.c @@ -96,8 +96,7 @@ bool addrspace_load (struct thread *t, const char *filename, void (**start) (void)) { struct Elf32_Ehdr ehdr; - struct file file; - bool file_open = false; + struct file *file = NULL; off_t file_ofs; bool success = false; int i; @@ -108,12 +107,12 @@ addrspace_load (struct thread *t, const char *filename, void (**start) (void)) LOAD_ERROR (("page directory allocation failed")); /* Open executable file. */ - file_open = filesys_open (filename, &file); - if (!file_open) + file = filesys_open (filename); + if (file == NULL) LOAD_ERROR (("open failed")); /* Read and verify executable header. */ - if (file_read (&file, &ehdr, sizeof ehdr) != sizeof ehdr) + if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr) LOAD_ERROR (("error reading executable header")); if (memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7) != 0) LOAD_ERROR (("file is not ELF")); @@ -135,8 +134,8 @@ addrspace_load (struct thread *t, const char *filename, void (**start) (void)) { struct Elf32_Phdr phdr; - file_seek (&file, file_ofs); - if (file_read (&file, &phdr, sizeof phdr) != sizeof phdr) + file_seek (file, file_ofs); + if (file_read (file, &phdr, sizeof phdr) != sizeof phdr) LOAD_ERROR (("error reading program header")); file_ofs += sizeof phdr; switch (phdr.p_type) @@ -157,7 +156,7 @@ addrspace_load (struct thread *t, const char *filename, void (**start) (void)) printf ("unknown ELF segment type %08x\n", phdr.p_type); break; case PT_LOAD: - if (!load_segment (t, &file, &phdr)) + if (!load_segment (t, file, &phdr)) goto done; break; } @@ -175,8 +174,7 @@ addrspace_load (struct thread *t, const char *filename, void (**start) (void)) done: /* We arrive here whether the load is successful or not. We can distinguish based on `success'. */ - if (file_open) - file_close (&file); + file_close (file); if (!success) addrspace_destroy (t); return success; @@ -274,7 +272,7 @@ load_segment (struct thread *t, struct file *file, file into the page and zero the rest. */ size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left; size_t zero_bytes = PGSIZE - read_bytes; - uint8_t *kpage = palloc_get (0); + uint8_t *kpage = palloc_get (PAL_USER); if (kpage == NULL) return false; @@ -306,7 +304,7 @@ setup_stack (struct thread *t) uint8_t *kpage; bool success = false; - kpage = palloc_get (PAL_ZERO); + kpage = palloc_get (PAL_USER | PAL_ZERO); if (kpage != NULL) { success = install_page (t, ((uint8_t *) PHYS_BASE) - PGSIZE, kpage); -- 2.30.2