File System Design Criteria


This document discussion some of the file system design considerations, so to better help you decide how much functionality you want to implement in your operating system. First we identify the reasonably implementable features, then we discuss how I might try to implement those features.
 

Desirable Features

Variable length file name -- MiniOS currently supports names up to 27 characters long. DOS only handled 11-character  (8+3) names.

Hierarchical directories -- MiniOS only supports one fixed-length directory.

File attributes -- MiniOS has none. If you are doing hierarchical directories, you will need at least one bit to say "this is a directory, not a data file." Other bits might be used for file locking, or for the type of data (text/binary/executable), or for permissions. Larger chunks of attribute data can be used to record a creation/modification time+date and perhaps an owner program and an icon (although this could be keyed to the file type).

Resizeable files -- MiniOS files are fixed in size when they are first written. This is most awkward.

B-Tree directory structure -- for faster search. For the size of system you will be building and testing, this is probably not worth the trouble. It's only valuable when the number of files in a single directory commonly exceeds a few hundred.

Symbolic links -- Multiple directory names for the same actual file.
 

Implementation Issues

The first decision you need to make is how to structure your directories. MiniOS simply allocates 32 bytes for each entry, two each for start sector and size, and the rest for the name. If you are doing a variable-length file name, you might want to still store the name next to the rest of the directory entry, but that makes directory access awkward, because you can no longer simply calculate an index into the directory; you must sequentially step through each item, adding the name size to the index to advance to the next item. The alternative is to separate the names from the rest of the directory, and pack the names into a string table with an offset in the main part of the directory. This way access into the main directory is still a simple array index. In computer hardware with performance issues related to word alignment, the variable length strings make it necessary to deal with pad characters for names that don't exactly fill out a word, when they are intermixed. Note that when a file is deleted, you need to shift everything over to close the gap (new file entries can always be added at the end), or else leave the entry there marked as deleted. Deleting names from the string table is trickier, because you must also adjust all the offsets to the part of the string table that got moved.

Other file attributes would go into the main tabular part of the directory. The file size is another file attribute. It is important to store it separately from the sector list (see File Allocation Tables, below), because a file usually will not exactly fill the final sector. In some cases, if the file shrinks, it may be convenient to leave all its sectors allocated until the disk is rejuvenated (defragmented).

If you are going to allow for hierarchical directories, you need to think about how directories differ from regular data files (they needn't, except for a directory bit in the parent directory). A directory is just a structured file, for which the file system software knows what the structure is. Lay out your directory item as a record (class), organized into an array. If you have separated names from the main table, then you will also need an offset in a known place (such as the front of the directory) to that second part, so that as the directory grows, you can still find the parts.

In MiniOS, the first 32 bytes of the directory are reserved for disk-wide properties; this is the same idea. If you choose to make your file system backwards compatible with MiniOS, you could add another number to this preamble which is the sector where the root directory can be found.
 

File Allocation Tables

The biggest change you will need to design into an expanded file system is how to allocate disk sectors to files. MiniOS simply allocates them sequentially, with only the last file in the system being allowed room to grow. A simple improvement on that is to include in the directory entry a list of the extents, or blocks of sectors allocated to this file. Some file systems allow for a fixed number of extents, where each extent represents a sequential block of sectors of arbitrary size. Thus in the normal case where only one file is being written at a time, it will be allocated sequential sectors and only use up a single extent item in its directory, leaving the rest for when the file is rewritten and needs to grow. A fixed extent list still leaves open the possibility of overflow, so you must accomodate some extent overflow region in your directory, with an offset in the main entry. Like the string table section, deleting an entry in the overflow section may involve shifting everything down. An alternative would be to make the overflow items the same size as a main directory entry, then mark it deleted if it becomes unneded; a subsequent new file creation, or addition requiring more extents, can replace deleted items before growing the table.

A different way ofallowing for unbounded file size, but at the cost of random access time, is to store a link to the next allocated sector in each file sector (or block). Thus, for the SandBox hardware, you would have 254 bytes in a sector for data, and 2 bytes for the link to the next sector. The downside of this scheme is that a seek to the end of file must read every sector of the file in order to follow the links.

Somewhat independently of the question of where to store the allocated sectors is the problem of where to store the list of unallocated sectors. One common implementation is to build a bit string, one bit for each chunk of sectors (in fixed-size chunks), in a giant talbe written out to disk. A 1 in the bitstring represents a chunk in use, and a 0 a chunk that is available. the bit number is then stored in the extents for that file. If the table is small enough, it can be kept in memory and only written out to the disk at shutdown. File systems that use this technique may allocate a large number of sectors at a time, resulting in for example file sizes of 4K or 16K for a 2-byte file.
 

Symbolic Links

Unix file systems divide their directory structure into two layers, one (called "I-nodes") a non-hierarchical index of all data files, but without names, and then the directories you are used to seeing laid on top of that. This way, every I-node has its own attributes (notably including ownership and file permissions), and the directory structure can be an arbitrary acyclic graph, where each directory is a list of I-nodes representing files and other directories, whithout concern as to whether there might be duplications. Of course each I-node needs a reference count, so that when the last directory entry pointing to it is deleted, the I-node itself can be deleted.

A simpler way to do this is the way Apple implemented what they called "aliases", which is a special file with tracking information (full pathname, and perhaps a unique file number, similar to I-node number), so that if the file this linked to is deleted and another with the same name put in its place, the pathname finds it. If the pathname doesn't work, perhaps the file was moved and/or renamed, and its I-node number can find it. this has advantages and disadvantages, such as when an alias follows an obsolete file around and into an archival directory, instead of reconnecting itself to the new current file in the original directory.
 

First draft  2004 February 20