This lab goes through a basic file system implementation and develops tools for manipulating such a file system. The tools will do formatting, directory listing, and file copying, but files will not be directly accessible. The file system will be implemented on a floppy disk.
The real way a file system is implemented in UNIX is to have a file system driver in the kernel. When the file IO system calls such as open(), read(), etc. are used, the kernel consults a table of currently mounted file systems, works out what type of file system the file is on, and uses the code it has for that file system. The file system being `mounted' means that it is mapped into some directory on the system, and can be used of by accessing that directory. A set of such mappings is the typical way to access a variety of file systems.
Since on most machines it is not possible for the average user to modify the kernel, or even to mount filesystems, it is much easier in this lab to write some specialised utilities that access a device directly and are programmed for a particular file system implementation. The mtools utilities are a perfect example of this, allowing access to the MS-DOS FAT file system with the commands mdir, mcopy, mformat, etc. Before doing the programming for this lab you might like to experiment with these utilities to see what kind of thing you will be writing.
The idea of formatting a disk is in fact ambiguous, and there are two levels at which a format can occur, corresponding to two levels of driver code that is in use when accessing a file system. The lower level is for the device driver, and lays down the most basic structure of the disk that is required to read and write any kind of data at all. This formatting is more of a hardware consideration and you are not required to understand it.
For hard drives, a device format is performed at manufacture, and is usually never done again because hard drives don't easily lose the information that's been encoded as part of this format. Floppies, however, are fragile and subject to much harsher treatment as they are carried around, and often need a new device level format. Windows and DOS default to doing a device format as part of a `normal' format, but on other systems it must be specifically asked for. In Linux it is done with the command fdformat. You won't need to do this if the floppy you use in this lab is in good condition, but is worth seeing the formatting process run once.
The formatting we will be interested in corresponds to the file system driver, and is formatting that writes data for an empty file system. This kind of formatting is sometimes called disk initialisation, which is probably a better name because it effectively initialises data on the disk. To know what is required for the formatting we have to know what data the file system implementation needs, and so the formatting utility is something that will be built up as the others requirements are developed. The most obvious requirement to start with is keeping track of free space on the disk.
A disk is a form of storage, just like physical memory, and to use it we also need to keep track of which parts of the disk are currently free, so that when we write new data we know which parts can be used. To emphasise this, we will use the same data structure to keep track of free disk blocks. The start of the disk will contain numbers, with the first number being the current number of free blocks, and the numbers after that being a stack of free blocks, referred to by number.
Each block on a floppy is 512 bytes, and with 80 cylinders, 2 heads, and 18 sectors per track, we have 2880 blocks. The first block is block 0, the last block is block 2879, and so a char is not enough to store these numbers. An int is 4 bytes, which means that to store potentially 2880 block numbers we will need more than one block for the stack itself.
Calculate the number of blocks that you will need and write a formatting utility which initialises the data in these blocks. Don't forget that the number of free blocks, which is the first number on the disk, is not going to be 2880 since some blocks are now reserved for keeping track of free blocks. The disk should be accessed as /dev/fd0 with the functions open(), read(), write(), close() and lseek() should be used to move to a particular block.
To test that the initialisation happened correctly, hexdump /dev/fd0. You should do this to test future stages of the lab also.
Write a program which reads in a normal UNIX file, one block at a time. For each block select a free block on the floppy from the top of the free block stack, and write that data to the free block. Examine the floppy with hexdump to make sure this worked.
If we wanted to read this data back at a later time (which we would), there is a problem - we don't know which blocks the data is in. One way to track this information is using an index block which, much like the free block stack, is a list of block numbers, in order, that contain the data for the file.
Reserve the first block after the free block stack to contain an index block for a file, and modify your copying program to write the file size into the first place of this block, followed by the block numbers of the data blocks for the file. The reason that the file size is needed is that the last block will only be partially filled. It is recommended that you calculate the file size from the data blocks as they are copied across so that you can double check the amount of data written, and also so that you know what type is being used to store the file size (the one used by stat() may not work when written out to disk).
Write another program, just for test purposes, which reads in the reserved block to get the file size and the numbers of the data blocks and then copies the contents of the data blocks to a UNIX file. The destination file will need to be truncated and may need to be created. Use the file size to figure out how many data blocks you should be copying (and how far along the index blocks you should go), and don't forget that the last data block will probably not be full. Copy a file to and then from the floppy and compare the copy with the original using cmp to make sure everything works.
Try copying larger and larger files back and forth until you have a problem with a file which is smaller than the floppy. What size was it?
The reason this has happened is that one index block is not big enough to contain all the block numbers for a large file, just like one block was not big enough for the entire free block stack and the block numbers for indexing start to overwrite another block. It is too inefficient, however, to just reserve more blocks for indexing, and so the only thing to do is use a dynamic allocation mechanism - a linked list.
Modify your two copying programs so that the last number in the index block is not treated as a data block number, but rather as the number for another index block. As you loop through the positions in the current index block you will need to check if you've reached the end and, if so, go to the next index block. When copying a file to the floppy you will need to get a free block off the stack every time the index reaches the end of the current index block. To do this it is easiest to convert the code that gets the free block into a function that takes no arguments and returns the number of the block that has been allocated.
So far we have everything needed to transfer data to and from a disk, but there's no way to know the name of the file or in fact a way to store multiple files. This is what directories are for, and in many ways they are a third driver layer, providing an abstract listing of files on the system. The only difference is that this third layer is not worked with by the Operating System; rather, it is what users interact with when manipulating files. In other words, the user is the driver at this level.
On some file systems, such as FAT, the directory is stored in a special way. On UNIX, however, "everything is a file". Devices, such as /dev/fd0, can be accessed as files, and directories can too. The only thing that's required is for the files to marked with a type. One reason this is easy to implement is that UNIX provides a good interface, using file descriptors, for working with files, and the same interface can be used to update the directories. We don't have such an interface, so our directories will be simpler, and more like FAT.
In our system, the index block that is reserved will be the root directory. The contents of this block will be a string followed by an int followed by a string followed by an int, and so on. Each pair is the filename (string including terminating zero) and the number of the index block for the file (the int). The end of the array will be marked with an empty string for the filename.
Change your initialisation program to make sure the root directory starts empty, i.e. the first character in the block is zero. Then change your copying program to select a free block for the first index block of a file, instead of the reserved block. Then update the directory once the file has been copied across by scanning through the reserved block until an empty filename is found. In that place, write the name of the file just copied, followed by the number of the first index block used for the file.
Write a program to list the directory. This program should go to the reserved block and, for each string and int, print them out. Copy a few files to the disk and run your listing program to see if the directory looks right. You should attempt to manually calculate the block numbers the files should have gone into to see if they are right.
The concept and output of this listing program is very similar to ls -i, which lists UNIX files and gives the inode numbers for them, where the inode is UNIX's equivalent of the index block.
Now modify the program which copies files from the floppy so that it searches the directory for the name of a file entered by the user. When it finds the file it should go to the index block indicated by that directory entry, and then proceed from there as it did before when starting from the reserved block with only one file. Don't forget to check for the situation where the search reaches an empty filename, which means that the file entered by the user does not exist on the disk.
Test everything you've done so far by copying a few files to the disk and trying to copy some of the back, comparing the copies with the originals. Your code will not cope with duplicate filenames, but do not worry about this.
File metadata is information associated with a file other than the data the file actually contains. This includes, ownership, permissions, access times, etc. In UNIX, and in our system, file metadata is stored with the actual file itself rather than as part of the directory entry. This is why, in UNIX, stat(), and particularly fstat(), does not access the directory, only the file.
File size is metadata, and this is already stored in our implementation. At the moment your listing program is only going through the directory entries, but all listing programs show things like file size. Modify your program so that, for each entry, it goes to the index block indicated in the directory entry and retrieves just the file size for printing out with that directory entry. You can `save' where you were up to in the directory block using lseek() with arguments that keep it standing still.
Since the file size is in that first index block, it is not really an index block but a file control block. To add more metadata we only need to add another entry to the start of that block, and make the data block numbers start a bit later.
A good example is time. In UNIX three times are maintained for a file: data modification time, metadata modification time, and access time. We will only keep one time - the time that the file was copied to the disk.
Modify your listing and copying programs so that they leave space in the file control block for a variable of type time_t, which is the time type in UNIX. When copying a file to the disk, call time() to get the current time and record the value in this place. When copying from the disk you only need to skip this variable to get to the first data block number. For the listing program, read in the number and convert it to a nicely formatted string using ctime(), and output this along with the filename, file control block number, and file size.
You have now sketched out the basics of one possible file system implementation, but if you were to make it usable some important matters need to be resolved. Duplicate filenames are a problem, but easily checked for when copying to the disk. A bigger issue is deleting files since it involves `walking' across the index blocks, returning each data block to the free block stack as well as the index blocks themselves, and finally deleting the directory entry. The update of the directory is probably the most painful since we have used an array with variable size elements, and removing an element from the middle requires shifting all elements after it back so that the gap is closed.
The largest issues, however, involve the directory implementation itself. No way has been provided for subdirectories yet, although two options stand out. One is to reimplement the directory as a file, as UNIX has. The other is to have directory entries which are tagged as being subdirectories, and interpret the filename as being the name of the subdirectory and the block number as being the block for the subdirectory. Note that this tagging is something UNIX must do also, to distinguish a file from a directory.
If the directory implementation we already have is to be kept, there is a further problem. Just like the first index block (file control block) of the file can fill up and must link across to another index block, so can a directory block. Although it would work to use the same solution of having the last 4 bytes in the directory block be the number of the block where the directory continues, this is more difficult in the case of a directory because it is more than likely that an entry would be split across two blocks and would have to be `assembled' in memory before it could be processed.