From 07ee003af55dc3aab779e95ef2a4f095f6b65964 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 15 Dec 2004 06:08:55 +0000 Subject: [PATCH] Clean up inode code: - Change inode_byte_to_sector() to insist that its argument be a valid file offset, and change file_read_at() and file_write_at() to always call it with one. - Change inode_create() to just create the inode on disk without returning a struct inode. Change return value to bool. Update callers to understand. - Integrate alloc_inode() into its one remaining caller. - Break inode deallocation into new static function deallocate_inode(). Change bitmap code from using (start...end) to indicate ranges to using (start, cnt). Update all callers. Other minor internal bitmap cleanups. --- src/filesys/file.c | 8 +- src/filesys/filesys.c | 29 ++----- src/filesys/inode.c | 171 +++++++++++++++++----------------------- src/filesys/inode.h | 4 +- src/lib/kernel/bitmap.c | 100 ++++++++++++----------- src/lib/kernel/bitmap.h | 10 +-- src/threads/palloc.c | 4 +- 7 files changed, 142 insertions(+), 184 deletions(-) diff --git a/src/filesys/file.c b/src/filesys/file.c index cd5fe3e..27e907f 100644 --- a/src/filesys/file.c +++ b/src/filesys/file.c @@ -75,7 +75,7 @@ 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 = inode_byte_to_sector (file->inode, file_ofs); + disk_sector_t sector_idx; int sector_ofs = file_ofs % DISK_SECTOR_SIZE; /* Bytes left in file, bytes left in sector, lesser of the two. */ @@ -90,6 +90,7 @@ file_read_at (struct file *file, void *buffer_, off_t size, /* Read sector into bounce buffer, then copy into caller's buffer. */ + sector_idx = inode_byte_to_sector (file->inode, file_ofs); disk_read (filesys_disk, sector_idx, file->bounce); memcpy (buffer + bytes_read, file->bounce + sector_ofs, chunk_size); @@ -133,8 +134,8 @@ 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 = inode_byte_to_sector (file->inode, file_ofs); + /* Sector to write, starting byte offset within sector. */ + off_t sector_idx; int sector_ofs = file_ofs % DISK_SECTOR_SIZE; /* Bytes left in file, bytes left in sector, lesser of the two. */ @@ -150,6 +151,7 @@ file_write_at (struct file *file, const void *buffer_, off_t size, /* If the sector contains data before or after the chunk we're writing, then we need to read in the sector first. Otherwise we start with a sector of all zeros. */ + sector_idx = inode_byte_to_sector (file->inode, file_ofs); if (sector_ofs > 0 || chunk_size < sector_left) disk_read (filesys_disk, sector_idx, file->bounce); else diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index 6a763fe..7989890 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -149,7 +149,6 @@ filesys_create (const char *name, off_t initial_size) { struct dir *dir = NULL; struct bitmap *free_map = NULL; - struct inode *inode = NULL; disk_sector_t inode_sector; bool success = false; @@ -175,12 +174,10 @@ filesys_create (const char *name, off_t initial_size) goto done; /* Allocate space for the file. */ - inode = inode_create (free_map, inode_sector, initial_size); - if (inode == NULL) + if (!inode_create (free_map, inode_sector, initial_size)) goto done; /* Write everything back. */ - inode_commit (inode); dir_write (dir, root_dir_file); bitmap_write (free_map, free_map_file); @@ -188,7 +185,6 @@ filesys_create (const char *name, off_t initial_size) /* Clean up. */ done: - inode_close (inode); bitmap_destroy (free_map); dir_destroy (dir); @@ -348,14 +344,12 @@ filesys_self_test (void) Delete file while open to check proper semantics. */ MUST_SUCCEED ((file = filesys_open ("foo")) != NULL); MUST_SUCCEED (filesys_remove ("foo")); + MUST_SUCCEED (filesys_open ("foo") == NULL); 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"); @@ -366,7 +360,6 @@ static void do_format (void) { struct bitmap *free_map; - struct inode *map_inode, *dir_inode; struct dir *dir; printf ("Formatting filesystem..."); @@ -379,23 +372,11 @@ do_format (void) 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 inode to disk. */ - map_inode = inode_create (free_map, FREE_MAP_SECTOR, - bitmap_file_size (free_map)); - if (map_inode == NULL) + /* Allocate free map and root dir files. */ + if (!inode_create (free_map, FREE_MAP_SECTOR, bitmap_file_size (free_map))) PANIC ("free map creation failed--disk is too large"); - inode_commit (map_inode); - inode_close (map_inode); - - /* Allocate data sector(s) for the root directory file - and write its inodes to disk. */ - dir_inode = inode_create (free_map, ROOT_DIR_SECTOR, - dir_size (NUM_DIR_ENTRIES)); - if (dir_inode == NULL) + if (!inode_create (free_map, ROOT_DIR_SECTOR, dir_size (NUM_DIR_ENTRIES))) PANIC ("root directory creation failed"); - inode_commit (dir_inode); - inode_close (dir_inode); /* Write out the free map now that we have space reserved for it. */ diff --git a/src/filesys/inode.c b/src/filesys/inode.c index 16d1455..be1df57 100644 --- a/src/filesys/inode.c +++ b/src/filesys/inode.c @@ -12,10 +12,18 @@ struct inode_disk { off_t length; /* File size in bytes. */ - disk_sector_t first_sector; /* Starting sector. */ + disk_sector_t start; /* Starting sector. */ uint32_t unused[126]; /* Unused padding. */ }; +/* Returns the number of sectors to allocate for a file SIZE + bytes long. */ +static inline size_t +bytes_to_sectors (off_t size) +{ + return DIV_ROUND_UP (size, DISK_SECTOR_SIZE); +} + /* In-memory inode. */ struct inode { @@ -28,9 +36,9 @@ struct inode /* List of open inodes, so that opening a single inode twice returns the same `struct inode'. */ -struct list open_inodes; +static struct list open_inodes; -static struct inode *alloc_inode (disk_sector_t); +static void deallocate_inode (const struct inode *); /* Initializes the inode module. */ void @@ -39,50 +47,42 @@ 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) +/* Initializes an inode for a file LENGTH bytes in size and + writes the new inode to sector SECTOR on the file system + disk. Allocates sectors for the file from FREE_MAP. + Returns true if successful. + Returns false if memory or disk allocation fails. FREE_MAP + may be modified regardless. */ +bool +inode_create (struct bitmap *free_map, disk_sector_t sector, off_t length) { - struct inode *idx; - size_t sector_cnt; + static const char zero_sector[DISK_SECTOR_SIZE]; + struct inode_disk *idx; + size_t start; + size_t i; - ASSERT (b != NULL); + ASSERT (free_map != NULL); ASSERT (length >= 0); - /* Allocate inode. */ - idx = alloc_inode (sector); - if (idx == NULL) - return NULL; + /* Allocate sectors. */ + start = bitmap_scan_and_flip (free_map, 0, bytes_to_sectors (length), false); + if (start == BITMAP_ERROR) + return false; - /* Allocate disk sectors. */ - sector_cnt = DIV_ROUND_UP (length, DISK_SECTOR_SIZE); - idx->data.length = length; - idx->data.first_sector = bitmap_scan_and_flip (b, 0, sector_cnt, false); - if (idx->data.first_sector == BITMAP_ERROR) - return NULL; + /* Create inode. */ + idx = calloc (sizeof *idx, 1); + if (idx == NULL) + return false; + idx->length = length; + idx->start = start; - /* Zero out the file contents. */ - if (sector_cnt > 0) - { - static const char zero_sector[DISK_SECTOR_SIZE]; - disk_sector_t i; - - for (i = 0; i < sector_cnt; i++) - disk_write (filesys_disk, idx->data.first_sector + i, zero_sector); - } + /* Commit to disk. */ + disk_write (filesys_disk, sector, idx); + for (i = 0; i < bytes_to_sectors (length); i++) + disk_write (filesys_disk, idx->start + i, zero_sector); - return idx; - - error: - inode_remove (idx); - inode_close (idx); - return NULL; + free (idx); + return true; } /* Reads an inode from SECTOR @@ -109,11 +109,17 @@ inode_open (disk_sector_t sector) } } - /* Allocate inode. */ - idx = alloc_inode (sector); + /* Allocate memory. */ + 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; + /* Read from disk. */ ASSERT (sizeof idx->data == DISK_SECTOR_SIZE); disk_read (filesys_disk, sector, &idx->data); @@ -127,48 +133,39 @@ inode_open (disk_sector_t sector) void inode_close (struct inode *idx) { + /* Ignore null pointer. */ if (idx == NULL) return; + /* Release resources if this was the last opener. */ if (--idx->open_cnt == 0) { - if (idx->removed) - { - struct bitmap *free_map; - - free_map = bitmap_create (disk_size (filesys_disk)); - if (free_map != NULL) - { - disk_sector_t start, end; - - bitmap_read (free_map, free_map_file); - - /* Reset inode sector bit. */ - bitmap_reset (free_map, idx->sector); - - /* 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); - } - else - printf ("inode_close(): can't free blocks"); - } + /* Deallocate blocks if removed. */ + if (idx->removed) + deallocate_inode (idx); + + /* Remove from inode list and free memory. */ list_remove (&idx->elem); free (idx); } } -/* Writes IDX to disk. */ -void -inode_commit (const struct inode *idx) +/* Deallocates the blocks allocated for IDX. */ +static void +deallocate_inode (const struct inode *idx) { - ASSERT (idx != NULL); - ASSERT (sizeof idx->data == DISK_SECTOR_SIZE); - disk_write (filesys_disk, idx->sector, &idx->data); + struct bitmap *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); + bitmap_set_multiple (free_map, idx->data.start, + bytes_to_sectors (idx->data.length), false); + bitmap_write (free_map, free_map_file); + bitmap_destroy (free_map); + } + else + printf ("inode_close(): can't free blocks"); } /* Marks IDX to be deleted when it is closed by the last caller who @@ -188,11 +185,8 @@ disk_sector_t inode_byte_to_sector (const struct inode *idx, off_t pos) { ASSERT (idx != NULL); - - if (pos < idx->data.length) - return idx->data.first_sector + pos / DISK_SECTOR_SIZE; - else - return (disk_sector_t) -1; + ASSERT (pos < idx->data.length); + return idx->data.start + pos / DISK_SECTOR_SIZE; } /* Returns the length, in bytes, of the file with inode IDX. */ @@ -207,27 +201,10 @@ inode_length (const struct inode *idx) void inode_print (const struct inode *idx) { + ASSERT (idx != NULL); 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. */ -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; + idx->data.start); } diff --git a/src/filesys/inode.h b/src/filesys/inode.h index d7fe86b..296ffd1 100644 --- a/src/filesys/inode.h +++ b/src/filesys/inode.h @@ -1,16 +1,16 @@ #ifndef FILESYS_INODE_H #define FILESYS_INODE_H +#include #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); +bool 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 *); diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c index ea6ce5f..009482d 100644 --- a/src/lib/kernel/bitmap.c +++ b/src/lib/kernel/bitmap.c @@ -46,18 +46,18 @@ bit_mask (size_t bit_idx) return (elem_type) 1 << (bit_idx % ELEM_BITS); } -/* Returns the number of elements required for B's bits. */ +/* Returns the number of elements required for BIT_CNT bits. */ static inline size_t -elem_cnt (const struct bitmap *b) +elem_cnt (size_t bit_cnt) { - return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS); + return DIV_ROUND_UP (bit_cnt, ELEM_BITS); } -/* Returns the number of bytes required by B's elements. */ +/* Returns the number of bytes required for BIT_CNT bits. */ static inline size_t -byte_cnt (const struct bitmap *b) +byte_cnt (size_t bit_cnt) { - return sizeof (elem_type) * elem_cnt (b); + return sizeof (elem_type) * elem_cnt (bit_cnt); } /* Returns a bit mask in which the bits actually used in the last @@ -80,7 +80,7 @@ bitmap_create (size_t bit_cnt) if (b != NULL) { b->bit_cnt = bit_cnt; - b->bits = malloc (byte_cnt (b)); + b->bits = malloc (byte_cnt (bit_cnt)); if (b->bits != NULL || bit_cnt == 0) { bitmap_set_all (b, false); @@ -132,19 +132,18 @@ bitmap_set_all (struct bitmap *b, bool value) bitmap_set_multiple (b, 0, bitmap_size (b), value); } -/* Sets the bits numbered START through END, exclusive, in B to - VALUE. */ +/* Sets the CNT bits starting at START in B to VALUE. */ void -bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value) +bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value) { - size_t idx; + size_t i; ASSERT (b != NULL); - ASSERT (start <= end); - ASSERT (end <= b->bit_cnt); + ASSERT (start <= b->bit_cnt); + ASSERT (start + cnt <= b->bit_cnt); - for (idx = start; idx < end; idx++) - bitmap_set (b, idx, value); + for (i = 0; i < cnt; i++) + bitmap_set (b, start + i, value); } /* Atomically sets the bit numbered IDX in B to true. */ @@ -187,19 +186,19 @@ bitmap_test (const struct bitmap *b, size_t idx) return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0; } -/* Returns true if any bit from START to END, exclusive, is set +/* Returns true if any of the CNT bits starting at START is set to VALUE. */ static bool -contains (const struct bitmap *b, size_t start, size_t end, bool value) +contains (const struct bitmap *b, size_t start, size_t cnt, bool value) { - size_t idx; + size_t i; ASSERT (b != NULL); - ASSERT (start <= end); - ASSERT (end <= b->bit_cnt); + ASSERT (start <= b->bit_cnt); + ASSERT (start + cnt <= b->bit_cnt); - for (idx = start; idx < end; idx++) - if (bitmap_test (b, idx) == value) + for (i = 0; i < cnt; i++) + if (bitmap_test (b, start + i) == value) return true; return false; } @@ -218,7 +217,7 @@ bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value) if (cnt <= b->bit_cnt) for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++) - if (!contains (b, idx, idx + cnt, !value)) + if (!contains (b, idx, cnt, !value)) return idx; return BITMAP_ERROR; } @@ -235,49 +234,50 @@ bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value) { size_t idx = bitmap_scan (b, start, cnt, value); if (idx != BITMAP_ERROR) - bitmap_set_multiple (b, idx, idx + cnt, !value); + bitmap_set_multiple (b, idx, cnt, !value); return idx; } -/* Returns the number of bits in B between START and END, +/* Returns the number of bits in B between START and START + CNT, exclusive, that are set to VALUE. */ size_t -bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value) +bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value) { - size_t idx, cnt; + size_t i, value_cnt; ASSERT (b != NULL); - ASSERT (start <= end); - ASSERT (end <= b->bit_cnt); + ASSERT (start <= b->bit_cnt); + ASSERT (start + cnt <= b->bit_cnt); - cnt = 0; - for (idx = start; idx < end; idx++) - cnt += bitmap_test (b, idx) == value; - return cnt; + value_cnt = 0; + for (i = 0; i < cnt; i++) + if (bitmap_test (b, start + i) == value) + value_cnt++; + return value_cnt; } -/* Returns true if any bits in B between START and END, +/* Returns true if any bits in B between START and START + CNT, exclusive, are set to true, and false otherwise.*/ bool -bitmap_any (const struct bitmap *b, size_t start, size_t end) +bitmap_any (const struct bitmap *b, size_t start, size_t cnt) { - return contains (b, start, end, true); + return contains (b, start, cnt, true); } -/* Returns true if no bits in B between START and END, exclusive, - are set to true, and false otherwise.*/ +/* Returns true if no bits in B between START and START + CNT, + exclusive, are set to true, and false otherwise.*/ bool -bitmap_none (const struct bitmap *b, size_t start, size_t end) +bitmap_none (const struct bitmap *b, size_t start, size_t cnt) { - return !contains (b, start, end, true); + return !contains (b, start, cnt, true); } -/* Returns true if every bit in B between START and END, +/* Returns true if every bit in B between START and START + CNT, exclusive, is set to true, and false otherwise. */ bool -bitmap_all (const struct bitmap *b, size_t start, size_t end) +bitmap_all (const struct bitmap *b, size_t start, size_t cnt) { - return !contains (b, start, end, false); + return !contains (b, start, cnt, false); } #ifdef FILESYS @@ -285,7 +285,7 @@ bitmap_all (const struct bitmap *b, size_t start, size_t end) size_t bitmap_file_size (const struct bitmap *b) { - return byte_cnt (b); + return byte_cnt (b->bit_cnt); } /* Reads FILE into B, ignoring errors. */ @@ -294,8 +294,8 @@ bitmap_read (struct bitmap *b, struct file *file) { if (b->bit_cnt > 0) { - file_read_at (file, b->bits, byte_cnt (b), 0); - b->bits[elem_cnt (b) - 1] &= last_mask (b); + file_read_at (file, b->bits, byte_cnt (b->bit_cnt), 0); + b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b); } } @@ -303,7 +303,7 @@ bitmap_read (struct bitmap *b, struct file *file) void bitmap_write (const struct bitmap *b, struct file *file) { - file_write_at (file, b->bits, byte_cnt (b), 0); + file_write_at (file, b->bits, byte_cnt (b->bit_cnt), 0); } #endif /* FILESYS */ @@ -311,7 +311,7 @@ bitmap_write (const struct bitmap *b, struct file *file) void bitmap_dump (const struct bitmap *b) { - hex_dump (0, b->bits, byte_cnt (b), false); + hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false); } /* Returns the number of bytes required to accomodate a bitmap @@ -319,9 +319,7 @@ bitmap_dump (const struct bitmap *b) size_t bitmap_needed_bytes (size_t bit_cnt) { - struct bitmap b; - b.bit_cnt = bit_cnt; - return byte_cnt (&b) + sizeof b; + return sizeof (struct bitmap) + byte_cnt (bit_cnt); } /* Creates and returns a bitmap with BIT_CNT bits in the diff --git a/src/lib/kernel/bitmap.h b/src/lib/kernel/bitmap.h index dbb7004..1c66c2a 100644 --- a/src/lib/kernel/bitmap.h +++ b/src/lib/kernel/bitmap.h @@ -13,7 +13,7 @@ size_t bitmap_size (const struct bitmap *); void bitmap_set (struct bitmap *, size_t idx, bool); void bitmap_set_all (struct bitmap *, bool); -void bitmap_set_multiple (struct bitmap *, size_t start, size_t end, bool); +void bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool); void bitmap_mark (struct bitmap *, size_t idx); void bitmap_reset (struct bitmap *, size_t idx); @@ -26,10 +26,10 @@ size_t bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool); size_t bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool); -size_t bitmap_count (const struct bitmap *, size_t start, size_t end, bool); -bool bitmap_any (const struct bitmap *, size_t start, size_t end); -bool bitmap_none (const struct bitmap *, size_t start, size_t end); -bool bitmap_all (const struct bitmap *, size_t start, size_t end); +size_t bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool); +bool bitmap_any (const struct bitmap *, size_t start, size_t cnt); +bool bitmap_none (const struct bitmap *, size_t start, size_t cnt); +bool bitmap_all (const struct bitmap *, size_t start, size_t cnt); #ifdef FILESYS struct file; diff --git a/src/threads/palloc.c b/src/threads/palloc.c index 7e6a967..545a7d4 100644 --- a/src/threads/palloc.c +++ b/src/threads/palloc.c @@ -143,8 +143,8 @@ palloc_free_multiple (void *pages, size_t page_cnt) memset (pages, 0xcc, PGSIZE * page_cnt); #endif - ASSERT (bitmap_all (pool->used_map, page_idx, page_idx + page_cnt)); - bitmap_set_multiple (pool->used_map, page_idx, page_idx + page_cnt, false); + ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt)); + bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false); } /* Frees the page at PAGE. */ -- 2.30.2