From 97dcefb4742e13df9eb22c3aa00bb802bdc55c60 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sun, 5 Sep 2004 07:56:32 +0000 Subject: [PATCH] Add comments. Add assertions. Make dir_destroy() do nothing on null pointer. Rename FILENAME_LEN_MAX to NAME_MAX. Make dir_add() fail too-long names. Free structure on failure in filehdr_allocate(). Implement filehdr_print(). Add copyright notice to filesys.c. Change %L to %ll--it's standard! --- src/filesys/directory.c | 42 +++++++- src/filesys/directory.h | 17 +-- src/filesys/filehdr.c | 42 +++++++- src/filesys/filehdr.h | 9 +- src/filesys/filesys.c | 232 ++++++++++++++++++++++++++++++---------- src/filesys/filesys.h | 3 +- src/filesys/fsutil.c | 21 +++- src/filesys/off_t.h | 4 + 8 files changed, 295 insertions(+), 75 deletions(-) diff --git a/src/filesys/directory.c b/src/filesys/directory.c index 353260f..1384d8d 100644 --- a/src/filesys/directory.c +++ b/src/filesys/directory.c @@ -4,38 +4,57 @@ #include "lib.h" #include "malloc.h" +/* Initializes D as a directory that holds ENTRY_CNT entries. */ bool dir_init (struct dir *d, 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; } +/* Destroys D and frees associated resources. */ void dir_destroy (struct dir *d) { - free (d->entries); + 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; } +/* Reads D from FILE. + D must have already been initialized, to the correct number of + entries, with dir_init(). */ void dir_read (struct dir *d, struct file *file) { + ASSERT (d != NULL); + ASSERT (file != NULL); + ASSERT (file_length (file) >= dir_size (d)); + file_read_at (file, d->entries, dir_size (d), 0); } +/* Writes D to FILE. + D must have already been initialized, to the correct number of + entries, with dir_init(). */ void dir_write (struct dir *d, struct file *file) { file_write_at (file, d->entries, dir_size (d), 0); } +/* Searches D for a file named NAME. + If successful, returns the file's entry; + otherwise, returns a null pointer. */ static struct dir_entry * lookup (const struct dir *d, const char *name) { @@ -44,7 +63,7 @@ lookup (const struct dir *d, const char *name) ASSERT (d != NULL); ASSERT (name != NULL); - if (strlen (name) > FILENAME_LEN_MAX) + if (strlen (name) > NAME_MAX) return NULL; for (i = 0; i < d->entry_cnt; i++) @@ -56,6 +75,10 @@ lookup (const struct dir *d, const char *name) return NULL; } +/* 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. */ bool dir_lookup (const struct dir *d, const char *name, disk_sector_t *filehdr_sector) @@ -76,6 +99,12 @@ dir_lookup (const struct dir *d, const char *name, return false; } +/* 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. + 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) { @@ -85,6 +114,9 @@ dir_add (struct dir *d, const char *name, disk_sector_t filehdr_sector) ASSERT (name != NULL); ASSERT (lookup (d, name) == NULL); + if (strlen (name) > NAME_MAX) + return false; + for (i = 0; i < d->entry_cnt; i++) { struct dir_entry *e = &d->entries[i]; @@ -99,6 +131,9 @@ dir_add (struct dir *d, const char *name, disk_sector_t filehdr_sector) return false; } +/* Removes any entry for NAME in D. + Returns true if successful, false on failure, + which occurs only if there is no file with the given NAME. */ bool dir_remove (struct dir *d, const char *name) { @@ -117,6 +152,7 @@ dir_remove (struct dir *d, const char *name) return false; } +/* Prints the names of the files in D to the system console. */ void dir_list (const struct dir *d) { @@ -127,6 +163,8 @@ dir_list (const struct dir *d) printk ("%s\n", e->name); } +/* Dumps the contents of D, including its files' names and their + contents, to the system console. */ void dir_dump (const struct dir *d) { diff --git a/src/filesys/directory.h b/src/filesys/directory.h index 8e4ed47..f5f5ebd 100644 --- a/src/filesys/directory.h +++ b/src/filesys/directory.h @@ -6,20 +6,23 @@ #include "disk.h" /* Maximum length of a filename. - This is the traditional UNIX maximum. */ -#define FILENAME_LEN_MAX 14 + This is the traditional UNIX maximum. + (This macro name comes from POSIX.1.) */ +#define NAME_MAX 14 +/* A directory. */ struct dir { - size_t entry_cnt; - struct dir_entry *entries; + size_t entry_cnt; /* Number of entries. */ + struct dir_entry *entries; /* Array of entries. */ }; +/* A single directory entry. */ struct dir_entry { - bool in_use; - char name[FILENAME_LEN_MAX + 1]; - disk_sector_t filehdr_sector; + 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; diff --git a/src/filesys/filehdr.c b/src/filesys/filehdr.c index 2f24d3b..1f35946 100644 --- a/src/filesys/filehdr.c +++ b/src/filesys/filehdr.c @@ -5,6 +5,14 @@ #include "filesys.h" #include "lib.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) { @@ -26,6 +34,7 @@ filehdr_allocate (struct bitmap *b, off_t length) if (sector == BITMAP_ERROR) { filehdr_deallocate (h, b); + free (h); return NULL; } h->sectors[h->sector_cnt++] = sector; @@ -34,6 +43,8 @@ filehdr_allocate (struct bitmap *b, off_t length) 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) { @@ -46,6 +57,9 @@ filehdr_deallocate (struct filehdr *h, struct bitmap *b) 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) { @@ -59,6 +73,7 @@ filehdr_read (disk_sector_t filehdr_sector) return h; } +/* Writes H to disk in sector FILEHDR_SECTOR. */ void filehdr_write (const struct filehdr *h, disk_sector_t filehdr_sector) { @@ -67,12 +82,18 @@ filehdr_write (const struct filehdr *h, disk_sector_t filehdr_sector) 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) { @@ -84,6 +105,7 @@ filehdr_byte_to_sector (const struct filehdr *h, off_t pos) 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) { @@ -91,4 +113,22 @@ filehdr_length (const struct filehdr *h) return h->length; } -void filehdr_print (const struct filehdr *); +/* Prints a representation of H to the system console. */ +void +filehdr_print (const struct filehdr *h) +{ + size_t i; + + printk ("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) + printk (", "); + printk ("%jd", (intmax_t) h->sectors[i]); + } + printk (")\n"); +} diff --git a/src/filesys/filehdr.h b/src/filesys/filehdr.h index 32792df..235a1e6 100644 --- a/src/filesys/filehdr.h +++ b/src/filesys/filehdr.h @@ -6,14 +6,17 @@ #include "disk.h" #include "off_t.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; - size_t sector_cnt; - disk_sector_t sectors[DIRECT_CNT]; + 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; diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index 37ea078..57dab76 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -1,3 +1,31 @@ +/* This file is derived from source code for the Nachos + instructional operating system. The Nachos copyright notice + is reproduced in full below. */ + +/* Copyright (c) 1992-1996 The Regents of the University of California. + All rights reserved. + + Permission to use, copy, modify, and distribute this software + and its documentation for any purpose, without fee, and + without written agreement is hereby granted, provided that the + above copyright notice and the following two paragraphs appear + in all copies of this software. + + IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO + ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR + CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE + AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA + HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY + WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" + BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO + PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR + MODIFICATIONS. +*/ + #include "filesys.h" #include "bitmap.h" #include "debug.h" @@ -7,68 +35,76 @@ #include "filehdr.h" #include "lib.h" -#define FREE_MAP_SECTOR 0 -#define ROOT_DIR_SECTOR 1 +/* Filesystem. -#define NUM_DIR_ENTRIES 10 -#define ROOT_DIR_FILE_SIZE (sizeof (struct dir_entry) * NUM_DIR_ENTRIES) + 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. -struct disk *filesys_disk; + Two files are special. The first special file is the free + map, whose header 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. -static struct file free_map_file, root_dir_file; + The second special file is the root directory, whose header 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. -static void -do_format (void) -{ - struct bitmap free_map; - struct filehdr *map_hdr, *dir_hdr; - struct dir dir; + The filesystem implemented here has the following limitations: - printk ("Formatting filesystem..."); + - No synchronization. Concurrent accesses will interfere + with one another. - /* 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))) - PANIC ("bitmap creation failed--disk is too large"); - bitmap_mark (&free_map, FREE_MAP_SECTOR); - bitmap_mark (&free_map, ROOT_DIR_SECTOR); + - 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. - /* 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) - PANIC ("free map creation failed--disk is too large"); - filehdr_write (map_hdr, FREE_MAP_SECTOR); - filehdr_destroy (map_hdr); + - No indirect blocks. This limits maximum file size to the + number of sector pointers that fit in a single sector + times the size of a sector, or 126 * 512 == 63 kB given + 32-bit sizes and 512-byte sectors. - /* 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) - PANIC ("root directory creation failed"); - filehdr_write (dir_hdr, ROOT_DIR_SECTOR); - filehdr_destroy (dir_hdr); + - No nested subdirectories. - /* Write out the free map now that we have space reserved - for it. */ - if (!file_open (&free_map_file, FREE_MAP_SECTOR)) - PANIC ("can't open free map file"); - bitmap_write (&free_map, &free_map_file); - bitmap_destroy (&free_map); - file_close (&free_map_file); + - Filenames limited to 14 characters. - /* Write out the root directory in the same way. */ - if (!file_open (&root_dir_file, ROOT_DIR_SECTOR)) - PANIC ("can't open root directory"); - if (!dir_init (&dir, NUM_DIR_ENTRIES)) - PANIC ("can't initialize root directory"); - dir_write (&dir, &root_dir_file); - dir_destroy (&dir); - file_close (&free_map_file); + - 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. - printk ("done.\n"); -} + 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. */ + +/* 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. */ + +/* 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; + +static void do_format (void); +/* Initializes the filesystem module. + If FORMAT is true, reformats the filesystem. */ void filesys_init (bool format) { @@ -85,6 +121,10 @@ filesys_init (bool format) PANIC ("can't open root dir file"); } +/* Creates a file named NAME with the given INITIAL_SIZE. + Returns true if successful, false otherwise. + Fails if a file named NAME already exists, + or if internal memory allocation fails. */ bool filesys_create (const char *name, off_t initial_size) { @@ -135,6 +175,11 @@ filesys_create (const char *name, off_t initial_size) return success; } +/* Opens a file named NAME and initializes FILE for usage with + the file_*() functions declared in file.h. + 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) { @@ -152,6 +197,10 @@ filesys_open (const char *name, struct file *file) return success; } +/* Deletes the file named NAME. + Returns true if successful, false on failure. + Fails if no file named NAME exists, + or if an internal memory allocation fails. */ bool filesys_remove (const char *name) { @@ -199,6 +248,10 @@ filesys_remove (const char *name) return success; } +/* Prints a list of files in the filesystem to the system + console. + Returns true if successful, false on failure, + which occurs only if an internal memory allocation fails. */ bool filesys_list (void) { @@ -213,6 +266,10 @@ filesys_list (void) return true; } +/* Dumps the filesystem state to the system console, + including the free map, the list of files, and file contents. + Returns true if successful, false on failure, + which occurs only if an internal memory allocation fails. */ bool filesys_dump (void) { @@ -236,17 +293,12 @@ filesys_dump (void) return true; } -static void must_succeed_function (int, int) NO_INLINE; - -static void -must_succeed_function (int line_no, int success) -{ - if (!success) - PANIC ("filesys_self_test: operation failed on line %d", line_no); -} - +static void must_succeed_function (int, bool) NO_INLINE; #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR) +/* Performs basic sanity checks on the filesystem. + The filesystem should not contain a file named `foo' when + called. */ void filesys_self_test (void) { @@ -272,3 +324,65 @@ filesys_self_test (void) printk ("filesys: self test ok\n"); } + +/* Formats the filesystem. */ +static void +do_format (void) +{ + struct bitmap free_map; + struct filehdr *map_hdr, *dir_hdr; + struct dir dir; + + printk ("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))) + PANIC ("bitmap creation failed--disk is too large"); + 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) + PANIC ("free map creation failed--disk is too large"); + filehdr_write (map_hdr, FREE_MAP_SECTOR); + filehdr_destroy (map_hdr); + + /* 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) + PANIC ("root directory creation failed"); + filehdr_write (dir_hdr, ROOT_DIR_SECTOR); + filehdr_destroy (dir_hdr); + + /* Write out the free map now that we have space reserved + for it. */ + if (!file_open (&free_map_file, FREE_MAP_SECTOR)) + PANIC ("can't open 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)) + PANIC ("can't open root directory"); + if (!dir_init (&dir, NUM_DIR_ENTRIES)) + PANIC ("can't initialize root directory"); + dir_write (&dir, &root_dir_file); + dir_destroy (&dir); + file_close (&free_map_file); + + printk ("done.\n"); +} + +/* If SUCCESS is false, panics with an error complaining about + LINE_NO. */ +static void +must_succeed_function (int line_no, bool success) +{ + if (!success) + PANIC ("filesys_self_test: operation failed on line %d", line_no); +} diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h index a54a347..1f06c34 100644 --- a/src/filesys/filesys.h +++ b/src/filesys/filesys.h @@ -5,7 +5,8 @@ #include #include "off_t.h" -struct disk *filesys_disk; +/* Disk used for filesystem. */ +extern struct disk *filesys_disk; struct file; void filesys_init (bool format); diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c index fb9a81b..67dab6f 100644 --- a/src/filesys/fsutil.c +++ b/src/filesys/fsutil.c @@ -7,12 +7,25 @@ #include "mmu.h" #include "palloc.h" +/* Filename and file size to use for copy operations, + as "filename:size". */ char *fsutil_copy_arg; + +/* Name of a file print to print to console. */ char *fsutil_print_file; + +/* Name of a file to delete. */ char *fsutil_remove_file; + +/* List all files in the filesystem to the system console? */ bool fsutil_list_files; + +/* Dump full contents of filesystem to the system console? */ bool fsutil_dump_filesys; +/* Copies from the "scratch" disk, hdc or hd1:0, + to a file named FILENAME in the filesystem. + The file will be SIZE bytes in length. */ static void copy (const char *filename, off_t size) { @@ -26,7 +39,7 @@ copy (const char *filename, off_t size) if (src == NULL) PANIC ("couldn't open source disk (hdc or hd1:0)"); if (size > (off_t) disk_size (src) * DISK_SECTOR_SIZE) - PANIC ("source disk is too small for %Ld-byte file", + PANIC ("source disk is too small for %lld-byte file", (unsigned long long) size); /* Create destination file. */ @@ -43,7 +56,7 @@ 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) - PANIC ("%s: write failed with %Ld bytes unwritten", + PANIC ("%s: write failed with %lld bytes unwritten", filename, (unsigned long long) size); size -= chunk_size; } @@ -52,6 +65,8 @@ copy (const char *filename, off_t size) file_close (&dst); } +/* Executes the filesystem operations described by the variables + declared in fsutil.h. */ void fsutil_run (void) { @@ -85,6 +100,8 @@ fsutil_run (void) filesys_dump (); } +/* Prints the contents of file FILENAME to the system console as + hex and ASCII. */ void fsutil_print (const char *filename) { diff --git a/src/filesys/off_t.h b/src/filesys/off_t.h index 2b97bca..84475e1 100644 --- a/src/filesys/off_t.h +++ b/src/filesys/off_t.h @@ -2,6 +2,10 @@ #define HEADER_OFF_T_H 1 #include + +/* An offset within a file. + This is a separate header because multiple headers want this + definition but not any others. */ typedef int32_t off_t; #endif /* off_t.h */ -- 2.30.2