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.
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.
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.
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.
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