Directories

Directories like files are anchored on Fnodes. A pointer to the Fnode for the root directory is found in the Super Block The Anodes for directories other than the root are reached through subdirectory entries in their parent directories. Directories can grow to any size and are built up from 2Kb directory blocks, which are allocated as four consecutive sectors on the disk. The file system attempts to allocate directory blocks in the directory band, which is located at or near the seek center of the disk. Once the directory band is full, the directory blocks are allocated wherever space is available. Each 2Kb directory block contains from one to many directory entries. A directory entry contains several fields, including time and date stamps, an Fnode pointer, a usage count for use by disk maintenance programs, the length of the file or directory name, the name itself, and a B-Tree pointer. Each entry begins with a word that contains the length of the entry. This provides for a variable amount of flex space at the end of each entry, which can be used by special versions of the file system and allows the directory block to be traversed very quickly (Figure 5). The number of entries in a directory block varies with the length of names. If the average filename length is 13 characters, an average directory block will hold about 40 entries.

The entries in a directory block are sorted by the binary lexical order of their name fields (this happens to put them in alphabetical order for the US. alphabet). The last entry in a directory block is a dummy record that marks the end of the block. When a directory gets too large to be stored in one block, it increases in size by the addition of 2Kb blocks that are organized as a B-Tree (see B-T tees and B+ Trees ). When searching for a specific name, the file system traverses a directory block until it either finds a match or finds a name that is lexically greater than the target. In the latter case, the file system extracts the Tree pointer from the entry. If there is no pointer, the search failed otherwise the file system follows the pointer to the next directory block in the tree and continues the search. A little back-of-the-envelope arithmetic yields some impressive statistics. Assuming 40 entries per block, a two-level tree of directory blocks can hold 1640 directory entries and a three-level tree can hold an astonishing 65,640 entries. In other words, a particular file can be found (or shown not to exist) in a typical directory of 65,640 files with a maximum of three disk hits--the actual number of disk accesses depending on cache contents and the location of the file's name in the directory blockB-Tree.That's quite a contrast to the FAT file system, where in the worst case more than 4000 sectors would have to be read to establish that a filewas or was not present in a directory containing the same number of files. The B-Tree directory structure has interesting implications beyond its effect on open and find operations. A file creation, renaming, or deletion may result in a cascade of complex operations, as directory blocks are added or freed or names are moved from one block to the other to keep the tree balanced. In fact, a rename operation could theoretically fail for lack of disk space even though the file itself is not growing. In order to avoid this sort of disaster, the HPFS maintains a small pool of free blocks that can be drawn from in a directory emergency; a pointer to this pool of free blocks is stored in the Spare Block.

FIGURE 5: Here directories are anchored on an Fnode and are built up from 2Kb directory blocks. The number of entries in a directory block varies because the length of the entries depends on the filename. When a directory requires more than one block the blocks are organized as a B-Tree. This allows a filename to be located very quickly with a small number of disk accesses even when the directory grows very large.

< [Files and Fnodes] | < [Files and Fnodes/PNG] | [HPFS Home] | [Extended Attributes] >

Html'ed by Hartmut Frommert