CIS-4020, Homework #10: File System Layout

Due: Thursday, November 10, 2016

This homework covers file system implementation issues. You may find the GenericFS documentation a useful reference. Chapter 13 in the text might also be relevant although that chapter covers more about how Linux implements file system handling than about the specific layout of file systems. You will likely find Chapter 13 more useful for the upcoming GenericFS lab.

Consider a POSIX style file system that uses 1 Kbyte blocks (1024 bytes). Let the block numbers be 24 bits in size. Assume that, like GenericFS, each inode contains four block numbers, a first indirection pointer, and a second indirection pointer. What is the size of the largest possible file? Show your calculations.
Using the normal GenericFS layout (and not the layout defined in question #1 above), consider the problem of accessing byte number 15,823,597 of a particular file. Starting with the inode, which you can assume has already been loaded into memory, describe as specifically as possible what the kernel must do to locate the byte in question. How many blocks need to be read from the disk? Your answer should also include why the blocks are read, and the exact offsets (provide numbers) into the various blocks to the data that is used.
GenericFS uses a linked list of directory entries to represent a directory. However, more advanced data structures could also be used. Imagine a file system that initially allocated 64 Kbytes of disk space for each directory and then divided each directory into 16 "buckets" of equal size. To find a file, the system computes a hash of the file's name in the range 0 .. 15. Call this hash value H. The system then looks in bucket H of the directory where it finds a linked list of directory entries (similar to what GenericFS uses for the entire directory). It searches this list for the file.
1. What advantage does this approach have over the simpiler method used by GenericFS?
2. About how many directory entries can fit into each bucket (the directory entries are not allowed to overflow a bucket)? Assume the directory entries are formatted the same way as they are under GenericFS. You will need to assume something about the length of an average file name. Use any "reasonable" number.
3. What should the system do when a file is added to a bucket that is full? There are several possibilities.