Solved CPSC–410/611/613 Machine Problem 7 Vanilla File System

Introduction In this machine problem you will implement a simple file system. Files support sequential access only, and the file name space is very simple (files are identified by unsigned integers; no multilevel directories are supported). The file system is to be implemented in classes FileSystem and File, respectively. Class FileSystem (a) controls the mapping from the file name space to files and (b) handles file allocation, free-block management on the disk, and other issues. Its interface is defined as follows (for more details check out the provided file file system.H): class FileSystem { /* -- your file system data structures here ... */ public : FileSystem () ; /* Just initializes local data structures . Does not connect to disk yet. */ bool Mount ( SimpleDisk * _disk ) ; /* Associates this file system with a disk . Limit to at most one file system per disk . Returns true if operation successful (i.e. there is indeed a file system on the disk .) */ static bool Format ( SimpleDisk * _disk , unsigned int _size ) ; /* Wipes any file system from the disk and installs an empty file system of given size . */ Inode * LookupFile (int _file_id ) ; /* Find file with given id in file system . If found , return the initialized file object . Otherwise , return null . */ bool CreateFile ( int _file_id ) ; /* Create file with given id in the file system . If file exists already , abort and return false . Otherwise , return true . */ bool DeleteFile ( int _file_id ) ; /* Delete file with given id in the file system ; free any disk block occupied by the file . */ }; This file system is just a proof-of-concept, and the interface is not indicative of industrial-strength code. A few points if you are perplexed about the class definition: • You may be tempted to ask why we don’t pass the disk to the FileSystem constructor. The reason for separating the construction from the mounting of the file system is that it is difficult to cleanly handle errors that occur in constructors. Therefore, you should keep the operations in the constructor simple, and leave the complicated stuff to the Mount function, where you return an error code (not here, but in a more serious implementation). • Why do we have to specify the file system size in the Format() function? This is to make your life simple: by specifying the size parameter you don’t need to find out how the big the disk is. Feel free to ignore the size parameter and use the entire disk; you will have to query the size of the disk on your own. Class File implements sequential read/write operations on an individual file (for details check out file.C): class File { /* -- your file data structures here ... */ public : Page 1 CPSC–410/611/613 Machine Problem 7 File ( FileSystem * _fs , int _id) ; /* Constructor for the file handle . Set the current position to be at the beginning of the file . */ ~ File () ; /* Closes the file . Deletes any data structures associated with the file handle . */ int Read ( unsigned int _n , char * _buf ) ; /* Read _n characters from the file starting at the current position and copy them in _buf . Return the number of characters read . Do not read beyond the end of the file . */ int Write ( unsigned int _n , const char * _buf ) ; /* Write _n characters to the file starting at the current position . If the write extends over the end of the file , extend the length of the file until all data is written or until the maximum file size is reached . Do not write beyond the maximum length of the file . Return the number of characters written . */ void Reset () ; /* Set the current position to the beginning of the file . */ bool EoF () ; /* Is the current position for the file at the end of the file ? */ }; Notice that we don’t do much error checking. This is not industrial-strength code! Why Separate File and File System? We want to separate the different aspects of file management into different classes. Class FileSystem manages the reading/writing from/to disk. It also manages the storing of the inode list in the INODES block and the free-block list (in the FREELIST block, depending on your implementation). Class File, on the other hand, handles the sequential read and write of sequences of bytes from and to the file. In order to do this, it maintains a current position in the file. The information about files and how they are stored in the file system is stored in objects of class Inode (check file system.H for details): class Inode { friend class FileSystem ; // The inode is in an uncomfortable position between friend class File ; // File System and File . We give both full access // to the Inode . private : long id; // File " name " /* You will need additional information in the inode , such as allocation information . */ FileSystem *fs; // It may be handy to have a pointer to the File system . // For example when you need a new block or when you want // to load or save the inode list . ( Depends on your // implementation .) /* You may need a few additional functions to help read and store the inodes from and to disk . */ };  Page 2 CPSC–410/611/613 Machine Problem 7 An Entire File System? That’s soo much Work! This MP is not asking you to write a full-fledged file system, but rather a simple proof of concept. To make life easier, we add a few constraints to the functionality of the file system: 1. Implement a single-level directory. The file system can manage a collection of files, but no directories. This means that you don’t need to implement directory files or even a separate directory to look up files. Instead, you can store the file names in the inodes and use the inode list as directory to find files. 2. Limit the length of files to at most one block! This greatly simplifies the implementation of the file allocation. Simply store the single block number of the file in the inode. 3. Keep the free-block list as simple as possible. Feel free to store the state of each block (used or free) as a character in a free-block array, which you store in the FREELIST block on the disk. Implementation Hints Unless you want to, don’t get carried away with this machine problem. In particular, don’t try to imitate existing file systems. This would be too much work. We list a few hints to make your life easier. First, it will help to designate one block to store the inode list; call it the INODES block. This can be Block 0 on the disk. (We won’t need a super block.) Use the next block to store the free-block list; call it the FREELIST block. Implement the free-block list as a “bitmap” (of chars, not of bits, if you want to keep it simple). Whenever you create a file, find a free block and assign it to the file. Store its block number in the inode. This block number will be the entire allocation information for this file, as files are at most one block long. Implement four functions to read and write the inode list and the free-block list from and to disk. The sequential operations on files are implemented in class File. Whenever you open the file, you copy the content of the block to a 512 Byte cache. (You write the cache back to disk when you close the file.) You keep a ‘current position’, which indicates where the next character will be read/written from/to the file. As you, say, read a string from the file, you start copying characters one-by-one from the cache to the buffer. As you do that, you make sure that you don’t overshoot the end-of-file, i.e. your current position does not go beyond the length of the file (store in the inode). When you write, you do the opposite: you copy character-by-character from the buffer to the cache, starting from the current position. If you exceed the length of the file, you simply extend the end of the file by incrementing the file length in the inode as you keep writing. In both cases make sure that you don’t overshoot the maximum file size, which is one block. Opportunities for Bonus Points The maximum file size of maximum one block (512 Byte) is a major limitation of the file system described above. If you are interested, you can propose how you would improve the file system to allow for larger file sized.  Page 3 CPSC–410/611/613 Machine Problem 7 OPTION 1: DESIGN of an extension to the basic file system to allow for files that are up to 64kB long. (This option carries 6 bonus points.) How would you extend the implementation above to allow for files that are up to 64kB long? Describe in detail how you would implement the allocation of files. What functions would have to be added, which functions would have to be modified, how? How would the data structures change? (Be precise. Points will not be given for general hand waving.) Separate the changes to the file allocation to changes in the read and write operations in class File. OPTION 2: IMPLEMENTATION of the extensions proposed in Option 1. (This option carries 6 bonus points.) For this option you are to implement the approach proposed in Option 1. Note: Work on this option only after your basic implementation works and after you have addressed Option 1. A Note about the Main File kernel.C The main file for this MP is greatly simplified compared to previous MP’s. In particular, it does not contain threads. • At this point the code in kernel.C instantiates a copy of a SimpleDisk. Feel free to replace the disk by your implementation of BlockingDisk if you are confident enough that it works. (not recommended) • The main thread exercises the file system as follows: 1. First, it formats disk “C” to contain a 128 KB file system. 2. Independently from the formatting, it creates a new file system. 3. It then mounts the file system. 4. It then goes into an infinite loop, where it calls the function exercise file system() repeatedly. 5. The function exercise file system() creates two empty files, with identifier 1 and 2. It then opens the two files and writes a string into each. It then closes the two files. It then opens them again and reads the content of the two files. It then checks whether the content is correct. It then deletes the two files again. (Note that this is a very simple test and is intended to only very superficially test the correctness and completeness of your file system implementation.) • File kernel.C is “scheduler-free”. If you want to bring in your implementation of Blocking Disk you will have to add a scheduler to the kernel. A Note about the Configuration Similarly to MP6, the underlying machine will have access to two hard drives, in addition to the floppy drive that you have been using earlier. The configuration of these hard drives is defined in File bochsrc.bxrc. You will notice the following lines: # hard disks ata0: enabled=1, ioaddr1=0x1f0, ioaddr2=0x3f0, irq=14 ata0-master: type=disk, path="c.img", cylinders=306, heads=4, spt=17 ata0-slave: type=disk, path="d.img", cylinders=306, heads=4, spt=17  Page 4 CPSC–410/611/613 Machine Problem 7 This portion of the configuration file defines an the ATA controller to respond to interrupt 14, and connects two hard disks, one as master and the other as slave to the controller. The disk images are given in files ”c.img” and ”d.img”, respectively, similarly to the floppy drive image in all the previous machine problems. Note: There is no need for you to modify the bochsrc.bxrc file. Note: If you use a different emulator or a virtual machine monitor (such as VirtualBox) you will be using a different mechanism to mount the hard drive image as a hard drive on the virtual machine. If so, follow the documentation for your emulator or virtual machine monitor. A Note about Stack Memory As you write your code, keep in mind that the kernel “thread” (i.e. the thread that start all the other threads and then dies) has 8kB of stack. We don’t have other threads in this MP. If you plan to store lots of data locally, make sure that you don’t overrun the stack. Use the heap instead. The Assignment 1. Implement the file system as described in the three classes FileSystem, File, and Inode above. 2. For this, use the provided code in file.H/C and file system.H/C, which contain definition and a dummy implementation of classes File, Inode, and FileSystem, respectively. 3. Check that the test function exercise file system() generates the correct results. (Basically, the goal is to not make it throw assertion errors.) 4. If you have time and interest, pick one or more options and improve your file-system design and implementation. What to Hand In You are to hand in a ZIP file, with name mp7.zip, containing the following files: 1. A design document, called design.pdf (in PDF format) that describes your design and the implementation of your File and File System. If you have selected any options, likewise describe the design and implementation for each option. Clearly identify in your design document and in your submitted code what options you have selected, if any. 2. All the source files and the makefile needed to compile the code. 3. Clearly identify and comment changes to existing code. 4. Grading of these MPs is a very tedious chore. These handin instructions are meant to mitigate the difficulty of grading, and to ensure that the grader does not overlook any of your efforts. Note: Pay attention to the capitalization in file names. For example, if we request a file called file.H, we want the file name to end with a capital H, not a lower-case one. While Windows does not care about capitalization in file names, other operating systems do. This then causes all kinds of problems when the TA grades the submission. Failure to follow the handin instructions will result in lost points.