Files and FNodes

An Fnode is always stored near the file or directory that it represents. The allocation structure in the Fnode can take several forms depending on the size and degree of contiguity of the file or directory. The HPFS views a file as a collection of one or more runs or extents of one or more contiguous sectors. Each run is symbolized by a pair of double-words--a 32-bit starting sector number and a 32-bit length in sectors (this is referred to as run length encoding). From an application program's point of view the extents are invisible; the file appears as a seamless stream of bytes. The space reserved for allocation information in an Fnode can hold pointers to as many aseight runs of sectors of up to 16Mb each . (This maximum run size is a result of the band size and free space bitmap placement only; it is not an inherent limitation of the file system.) Reasonably small files or highly contiguous files can therefore be described completely within the Fnode (Figure 3).

HPFS uses a new method to represent the location of files that are too large or too frag-mented for the Fnode and consist of more than eight runs. The Fnode's allocation structure becomes the root for a B+ Tree of allocation sectors which in turn contain the actual pointers to the file's sector runs (see Figure 4 and the sidebar, "B-Trees and B+ Trees"). The Fnode's root has room for 12 elements. Each allocation sector can contain, in addition to various control information, as many as 40 pointers to sector runs. Therefore a two-level allocation B+ Tree can describe a file of 480 (12x40) sector runs with a theoretical maximum size of 7.68Gb (12x40x16Mb) in the current implementation (although the 32-bit signed offset parameter for DosChgFilePtr effectively limits the sizes to 2Gb). In the unlikely event that a two-level B+ Tree is not sufficient to describe the highly fragmented file the file system will introduce additional levels in the tree as needed. Allocation sectors in the intermediate levels can hold as many as 60 intemal (nonterminal) B+ Tree nodes which means that the descriptive ability of this structure rapidly grows to numbers that are nearly beyond comprehension. For example a three level allocation B+ tree can describe a file with as many as 28 800 (12x60x40) sector runs. Run-length encoding and B+ Trees of allocation sectors are a memory-efficient way to specify a file's size and location but they have other s significant advantages. Translating a logical file offset into a sector number is extremely fast: the file system just needs to traverse the list (or B+ Tree of lists) of run pointers until it finds the correct range. It can then identify the sector within the run with a simple calculation. Run-length encoding also makes it trivial to extend the file logically if the newly assigned sector iscontiguous with the file's previous last sector the file system merely needs to increment the size double word of the file's last run pointer and clear the sector's bit in the appropriate freespace bitmap.

FIGURE 2: This figure shows the overall structure of an Fnode. The Fnode is the fundamental object in an HPFS volume and is the first sector allocated to a file or directory. it contains control and access history information used by the file system, cached EAs and ACLs or pointers to same, a truncated copy of the file or directory name (to aid disk repair programs, and an allocation structure which defines the size and location of the file's storage.

FIGURE 3: The simplest form of tracking for the sectors owned by a file is shown. The Fnode s allocation structure points directly to as many as eight sector runs. Each run pointer consists of a pair of 32-bit doublewords: a starting sector number and a length !n sectors.

FIGURE 4: This figure demonstrates the technique used to track the sectors owned by a file with 9-480 sector runs. The allocation structure in the Fnode holds the roots for a B+ Tree of allocation sectors. Each allocation sector can describe as many as 40 sector runs. If the file requires more than 480 sector runs, additional intermediate levels are added to the B+ Tree, which increases the number of possible sector runs by a factor of sixty for each new level.