Copyright (c) Hyperion Entertainment and contributors.
DCFS and LNFS Low Level Data Structures
Low level data structures used by the Amiga DCFS (1992) and LNFS (2001) by Olaf Barthel
Copyright (c) 2015 Olaf Barthel.
How the Amiga file system stores its data on disk is well-documented as far as the original file system (1985) and the Fast File System (1988) are concerned. The changes made for the Directory Caching File System (DCFS) and Long Name File System (LNFS) modes have never been described in detail. The term 'mode' refers to the fact that the respective changes are integrated with the existing file system data structures and algorithms and augment rather than replace them altogether.
This text attempts to describe in detail which purpose each respective file system mode serves, how the on-disk data structures look like, how they are integrated with the existing file system, and which drawbacks the respective modes have.
In this text familiarity with the 'C' programming language syntax for data structures is assumed, using the Amiga data types described in the <exec/types.h> header file. In each example a disk block size is 512 bytes in size.
Directory Caching File System (DCFS)
History and purpose
The DCFS mode was added to the Amiga ROM file system in Kickstart 3.0 (1992) by Commodore engineer Randell Jesup. The intended purpose was to make reading directory contents faster.
The Amiga file system stores directory contents in linked lists. There are 72 such lists in a 512 byte directory block, but not all of them may contain directory data. All entries whose names share the same hash value are stored in the same list. Reading the directory contents involves walking through each of these 72 lists in turn, skipping empty lists as needed.
Because the Amiga file system stores each entry of a directory in an individual block, reading a directory involves processing 512 bytes (or more; block sizes can be a large as 65536 bytes) while only a small part of the block data is relevant for directory scanning. Of interest are the type (directory, file, soft link, hard link), name, comment, modification time and protection flags. Taken together, this information accounts for up to 132 bytes. Because file names are typically not 30 characters long and comments are rare, the information retrieved from a directory entry block can be as short as 20-40 bytes.
The Amiga file system has no built-in controls to minimize fragmentation and to place directory contents close to one another. Reading the contents of a directory can involve visiting directory entry blocks which are widely scattered across the volume.
The DCFS mode attempts to reduce the amount of data which needs to be retrieved when a directory is being scanned, and also to minimize the number of disk accesses that have to take place. This is achieved by introducing a new file system block type which stores a compact form of the directory contents. This new file system block type is the "Directory list block", which implements a "cache" of the directory contents. This is what gives the Directory Caching File System its name.
Data structure changes and new data structures
The DCFS mode reuses the Amiga file system data structures which are utilized in the original file system (OFS) and the Fast File System (FFS) and builds upon them by adding directory lists blocks. The directory list blocks are attached to the root directory and all user directories through a field which was, up to 1992, unused.
Standard root and user directory blocks (512 bytes) for OFS and FFS would look like this:
struct RootBlock { LONG Type; /* This is used to mark the type of this block and is set to TYPE_SHORT (2) */ ULONG OwnKey; /* Not used by root, must be set to 0 */ ULONG SeqNum; /* Not used by root, must be set to 0 */ ULONG HTSize; /* Size of the hash table in longwords, must be set to 72 */ ULONG Reserved1; /* reserved for future revs, must be 0 */ LONG Checksum; /* balance to 0 checksum. When all longs in the block are added (ignoring carry) the sum should be 0 */ ULONG HashTable[72]; /* hash table containing block numbers of files and directories in the root */ LONG BitmapFlag; /* flag to say whether the bitmap is valid or not. -1=valid. 0=invalid. If a partition is mounted (or uninhibited) with BitmapFlag = 0 then the validator will kick in to rebuild the bitmap */ ULONG BitmapKeys[25]; /* An array of block numbers for the bitmap on this partition. A block number of 0 indicates the end of the list. */ ULONG BitmapExtend; /* If all of the BitmapKeys have been used then this will contain the block number of a disk block containing more Bitmap- Keys. 0 means no extender block present. OLDFS has a bug where it assumes that the root has protection bits and attempts to set them. Since they coincide with this field, this is why there is a 53Meg limit on partition size under OLDFS */ ULONG DirAltered[3]; /* A DOS DateStamp indicating the date when the root block was last modified or a file in the root block was modified */ char Name[40]; /* Name of this volume as a BCPL string with number of bytes as the first character. Only 30 chars used */ ULONG DiskAltered[3]; /* A DOS DateStamp indicating the date when any file or section of the partition was modified. (FFS has a bug which prevents it from updating this correctly, the DirAltered date gets changed instead) */ ULONG DiskMade[3]; /* A DOS DateStamp indicating the date when this partition was first formatted and therefore created */ ULONG Reserved2; /* reserved for future revs, must be 0 */ ULONG Reserved3; /* reserved for future revs, must be 0 */ ULONG Reserved4; /* reserved for future revs, must be 0 */ LONG SecondaryType; /* Qualifier to Type. Will be set to ST_ROOT (1) */ };
struct UserDirectoryBlock { LONG Type; /* This is used to mark the type of this block and is set to TYPE_SHORT (2) */ ULONG OwnKey; /* Set to directory's own block number */ ULONG Reserved1; /* Not used, must be set to 0 */ ULONG Reserved2; /* Not used, must be set to 0 */ ULONG Reserved3; /* Not used, must be set to 0 */ LONG Checksum; /* balance to 0 checksum. When all longs in the block are added (ignoring carry) the sum should be 0 */ ULONG HashTable[72]; /* hash table containing block numbers of files and directories in this directory */ LONG Reserved4; /* Not used, must be set to 0 */ LONG OwnerXID; /* Owner UID/GID */ ULONG Protection; /* Protection bits for this directory */ LONG Reserved6; /* Not used, must be set to 0 */ char Comment[92]; /* Directory comment as a BCPL string, only 80 characters can be used including the length byte at the beginning */ ULONG Created[3]; /* DOS DateStamp struct indicating when this directory was created or modified */ char DirName[36]; /* name of this directory as a BCPL string. only 30 characters are used */ LONG Reserved7[7]; /* Not used, must be set to 0 */ ULONG HashChain; /* block number of the next file on the hashchain if there's a hashing collision. 0 means no next file or directory. */ ULONG Parent; /* Block number of the parent directory of this directory. */ ULONG Reserved8; /* Not used. must be set to 0 */ LONG SecondaryType; /* Qualifier to Type. Will be set to ST_USERDIR (2) */ };
In DCFS mode the RootBlock.Reserved4 and the UserDirectoryBlock.Reserved8 fields, respectively, contain the block number of the first directory list block for the directory.
Each directory list block begins with a header consisting of six fields, which is then followed by a variable number of list entries. The directory list block header looks as follows:
struct FileListBlock { LONG Type; /* This is used to mark the type of this block and is set to TYPE_DIRLIST_REV1 (33) */ ULONG OwnKey; /* Set to file list block's own block number */ ULONG Parent; /* Block number of the directory which this directory list block is associated with */ ULONG NumEntries; /* Number of directory entries in this block */ ULONG NextBlock; /* Block number of next block in the list, or 0 */ LONG Checksum; /* Balance to 0 checksum. When all longs in the block are added (ignoring carry) the sum should be 0 */ };
Each directory list entry begins with a header of constant size, which is followed by a variable number of bytes which contain the name and the comment text. The directory list entry is a "digest" of the directory/file/hard link/soft link block contents, which includes the name, comment and other metadata:
struct FileListEntry { ULONG Key; /* Number of the block which this entry is a "digest" of; this would be a file/directory/hard link/soft link header block */ ULONG DataSize; /* Number of bytes in this file; relevant only for files */ ULONG Protection; /* Protection bits for this file/directory */ LONG OwnerXID; /* Owner UID/GID */ UWORD Created[3]; /* Truncated DOS DateStamp struct indicating when this directory entry was created or modified */ BYTE Type; /* Directory entry type, e.g. ST_USERDIR (2), ST_FILE (-3), etc. */ UBYTE Name[]; /* Name as variable length BCPL string */ UBYTE Comment[]; /* Name as variable length BCPL string */ UBYTE Pad; /* Padding byte if needed */ };
How directory lists are constructed
The root directory and each user directory must contain a valid directory list. The RootBlock.Reserved4 and the UserDirectoryBlock.Reserved8 fields, respectively, contain the block number of the first directory list block for the root block/directory. This block number must never be 0.
The FileListBlock.Type field must be set to TYPE_DIRLIST_REV1 (33). While the Amiga file system for Kickstart 3.0 was under development, Commodore briefly supported a different type of directory list which can be identified as type TYPE_DIRLIST_REV0 (32). Details of the differences between TYPE_DIRLIST_REV1 and TYPE_DIRLIST_REV0 will be described later in the context of the directory list entry format.
Each directory list block is part of a chain, in which the FileListBlock.NextBlock field contains the block number of the next following entry in this chain, or 0 to indicate that no other directory list block follows.
The number of entries in this directory list block is stored in FileListBlock.NumEntries. A value of 0 indicates that this block has no directory entries stored.
How directory list entries are constructed for TYPE_DIRLIST_REV1 (33)
If the FileListBlock.Type field is set to TYPE_DIRLIST_REV1 (33) then you are dealing with the standard form of the directory list block. This is the only form which should be used in production code.
Directory list entries directly follow the directory list block header.
Each entry consists of a constant size portion (FileListEntry), followed by a name and comment string in BCPL format (i.e. a single length byte is followed by exactly as many characters as indicated by the contents of the length byte; there is no terminating NUL byte). If the total size of the constant part, the name and the comment string is an odd number, then a padding byte must be added to the entry. The padding byte should be set to 0.
Because the total size of the FileListEntry is not stored within itself, it must be calculated by looking at how long the name and comment data is, including the length byte which introduces each string. If the number obtained by adding the size of the FileListEntry and the name and comment strings (in BCPL format) is odd, 1 must be added to make it an even number (accounting for the required padding byte).
The number of directory list entries must match the value of the directory list block FileListBlock.NumEntries field.
If there is enough spare room left in the directory list block, then the list of directory list entries must be terminated by an ULONG value of 0. This looks like a partial FileListEntry with the Key field set to 0.
The contents of FileListEntry.Created field are a truncated form of the 'struct DateStamp' which can be found, for example in the UserDirectoryBlock.Created field. The seconds and microseconds fit completely within the truncated form, but the number of days does not. As such the date range is restricted to 179 years instead of 4 billion years.
How directory list entries are constructed for TYPE_DIRLIST_REV0 (32)
If the FileListBlock.Type field is set to TYPE_DIRLIST_REV0 (32) then you are dealing with a non-standard form of the directory list block which was the precursor to the standard form. Never use the TYPE_DIRLIST_REV0 (32) form in production code. The following documentation is provided for the sake of completeness only.
If the FileListBlock.Type field is set to TYPE_DIRLIST_REV0 then the format of the directory list entries is slightly different:
struct FileListEntry_Rev0 { ULONG Key; /* Number of the block which this entry is a "digest" of; this would be a file/directory/hard link/soft link header block */ ULONG DataSize; /* Number of bytes in this file; relevant only for files */ ULONG Protection; /* Protection bits for this file/directory */ UWORD Created[3]; /* Truncated DOS DateStamp struct indicating when this directory entry was created or modified */ BYTE Type; /* Directory entry type, e.g. ST_USERDIR (2), ST_FILE (-3), etc. */ UBYTE Name[]; /* Name as variable length BCPL string */ UBYTE Comment[]; /* Name as variable length BCPL string */ UBYTE Pad; /* Padding byte if needed */ };
In revision 0 the OwnerXID field is omitted from the constant size directory list entry header.
Limitations and drawbacks
Because a copy of the metadata of the directory contents is made, this copy needs to be updated whenever the original changes. This alone makes DCFS mode slower than the comparable OFS/FFS variant when directory contents are modified.
Additional complications may arise if a name or comment is changed so that the corresponding directory list entry becomes too large to fit into its directory list block. In this case additional storage space will need to be allocated for a new directory list block, the old block will have to be rewritten, the new block will have to be initialized and linked up. If no storage space is available, the rename/comment change operation will have to be undone. Both the successful case (new entry created) and the failing case (not enough store space, undoing the change) are making a directory update significantly more complex.
Maintaining the consistency of the directory cache is the responsibility of the file system validation process. If the volume needs to be rebuilt, two passes are necessary in order to first find out which data blocks are used, and then to rebuild the directory cache. This will easily double the total validation time.
Due to the complexity of maintaining the directory cache, any update takes significantly longer than in the comparable OFS/FFS variants of the file system, and it modifies more data structures. During this operation the file system data structures are not entirely consistent at all times, and if the system should crash or the power should fail, then a validation may stall because of inconsistencies. The file system will have to be repaired. The DCFS mode makes this case more likely to appear and then adds insult to injury by making the validation process at least twice as long as with the comparable OFS/FFS variants of the file system.
There is no "garbage" collection process for the directory cache. If most of the entries are removed from a directory list block no merging of neighbouring directory list blocks takes place. If all entries are removed from a directory list block, that block is not removed from the directory list and its storage space is not reclaimed. Only deleting the empty directory which contains the empty directory list chain will free that memory.
