Proposed Phoenix File System The file system will be composed of a number of layers of abstraction as follows: Logical Sector to Physical Media mapping - This lowest layer would be implemented by the storage device hardware driver. It would convert the device-dependant physical representation of the storage device to logical 512-byte sectors each numbered starting from 0 and continuing based on the storage capacity of the device. Numbering is such that the seek time between any two consecutively numbered sectors is minimum. Logical sector numbers are stored as 64-bit values. The "beginning" of the storage device is considered where the logical sector numbers are low; the "end" of the storage device is considered where the logical sector numbers are high. Logical Sector Allocation - This layer exists to keep track of which logical sectors have been allocated to hold data, which are available, and which are unusable (bad). Single logical sectors called Free Space Descriptors will be used to indicate whether up to 4096 sectors each are in use or available for use. This is done by using each bit in the 512-byte Free Space Descriptor to represent whether a single sector is in use or not (0 indicates the respective logical sector is in use, 1 indicates it is not). The number of Free Space Descriptors varies based on the storage capacity of the device. The location of each of the Free Space Descriptors is stored as a series of Logical Sector Numbers in a series of sectors toward the beginning of the storage device. The first logical sector number would hold the location of the first free space descriptor (which would describe the first 4096 sectors), the second logical sector number would hold the location of the second free space descriptor (which would describe logical sectors 4096 through 8191), etc. This table would be called the Free Space Descriptor Location Table and would consist of enough consectutive 512-byte sectors to hold as many 64-bit logical sector numbers as are required to locate enough Free Space Descriptors to describe the entire meida. Each sector of the Free Space Descriptor Location Table could hold the location of up to 64 Free Space Descriptors, with each Free Space Descriptor indicating whether or not each of up to 4096 sectors is available for use, for a total of 262144 sectors accounted for per sector of the Free Space Descriptor Location Table, or 128 megabytes of storage capacity. The Free Space Descriptor Location Table may span as many sectors at it needs, but the sectors MUST be contiguous. Logical sectors used by the Free Space Descriptor Location Table and by the Free Space Descriptors are considered in use and therefore are not available for allocation. It is not possible for portions of the logical sector mapping to not be accounted for by Free Space Descriptors nor for them to overlap. FSDLT FSDs .----. 1 | o--------->|100010010...100101| Allocation map for sectors 0 - 4095 |----| 2 | o--------->|000010101...110001| Allocation map for sectors 4096 - 8091 |----| 3 | o--------->|100100101...001000| Allocation map for sectors 8092 - 12287 |----| . . . . |----| N | o--------->|001001000...001001| Allocation map for sectors 4096*N - 4096*(N-1)-1 `----' It is suggested the OS load and store the entire Free Space Descriptor Location Table in memory for quick reference. The suggested arangement for the Free Space Descriptors in relation to the logical sectors they describe is that for even indexed Free Space Descriptors the Free Space Descriptor is located in the first sector it describes and for odd indexed Free Space Descriptor the Free Space Descriptor is located in the last sector it describes; this maximizes the number of contiguous sectors for allocation (8190) and minimizes the distance, and thus the seek time, between Free Space descriptors and the data they describe. Bad Sector Recovery: when a given media is first formatted, the Free Space Descriptors are located only in "good" sectors (ie. not bad) and bad sectors are marked as used and recorded in a special Bad Sector List described below. Should a sector be found to be bad after format the given sector should be marked as in use in the appropriate Free Space Descriptor and added to the Bad Sector List. However, if the bad sector is detected at the location of a Free Space Descriptor then major error recovery methods need to be employed (as described below) resulting in the sector being added to the Bad Sector List and the Free Space Descriptor being moved to the a free good sector (or possibly moving data from a used sector to a free sector and then locating the Free Space Descriptor there so as to minimize the distance between the Free Space Descriptor and the data it describes). Data Chain Layer - This layer exists to group a number of logical sectors into an ordered list which can completely describe a series of bytes of any length up to 2^64-1 bytes long. This can be thought of as a simplistic file mechanism. This layer is intended to bring order to the data stored on the media. Data Chains are described using Data Chain Descriptor Blocks which each 1 logical sector in size. Each Data Chain Descriptor Block has the following format: 42 x Data Chain Descriptor Entry (12 bytes each) ----------. | 8 bytes - Start sector of data chain segment | | 4 bytes - Number of sectors in data chain segment | `----------------------------------------------------' 8 bytes - Sector number of next Data Chain Descriptor in chain (or 0 if is last descriptor in chain) * first Data Chain Descriptor Block in chain has the following special definitions for the first fields of the first Data Chain Descriptor Entry: 8 bytes - Total size of chain in bytes. 4 bytes - Initial Data Chain Descriptor Block flag (value = 0) * empty Data Chain Descriptor Entries have both fields equal to 0. if all Data Chain Descriptor Entries have their length field (the 4 byte field) equal to 0, then the chain is considered empty. File Layer - This layer actually creates the user model of the file system. It describes files from the user perspective and is therefore the highest layer of file description. Directory structure is currently the only higher layer and is implemented within files. Files and their attributes are described using File Nodes which have the following format: Offset Size Description 0 4 Magic Number (used to help locate File Nodes in a corrupt file system) 4 4 Date/Time File Node Created 8 4 Date/Time File Node data last accessed C 4 Date/Time File Node data last modified 10 4 Date/Time File Node last modified 14 4 Link count (hard links) 18 8 Location of data chain 20 8 Location of extended attributes chain 28 8 Location of rights list chain 30 8 Extended Node sector location 38 4 Flags System Archive Hidden Read-Only Purge on delete Deleted Internal Data Internal Extended Attributes Internal Rights List 3C 1 Type 3D 1 (reserved - must be 0) 3E 2 Length of filename (must be between 1 and ???) 40 x Filename (in Unicode) File Nodes are usually 1 logical sector in size (512 bytes) although may be as large as 1024 bytes through the use of the Extended Node sector. Field descriptions: Magic Number - some arbitrary 32-bit number which is used in file system error recovery to help indicate the presence of a file node. The repair utility can scan for this value in the first 4 bytes of a sector, and if matched can then begin analyzing the rest of the sector. Date/Time fields - 32-bit encoded date/time identifiers. Link count - Number of references to this File Node from the Directory Structure. If 0, file has no references from the Directory Structure and is therefore in accessible. Type - Indicates what type of file this is. Currently valid values include: 0 (reserved) 1 File 2 Directory 3 Symbolic Link System Flag - Only can be deleted by the super-user and they are prompted if they are sure they want to delete a system file. Archive Flag - Set whenever the Date/Time File Node last modified field changes Hidden Flag - Simply indicates whether or not file should be displayed in basic file listings (does not indicate the ability to see the file, but only the default behavior of file listings...see rights list information on making files invisible to certain users) Read-Only Flag - Simply provides an extra safeguard against accidently overwrite or deletion of a file. See rights list for denying write ability for certain users. Purge Flag - Indicates whether or not the file should be immediately purged when deleted. Deleted Flag - Indicates whether or not the file has been deleted and is waiting for purge. Internal flags - Location fields -