Phoenix File System

Physical Media Abstraction Layer - This layer abstracts the physical format of the media into equal-sized logical allocation units called Logical Sectors using the following guidelines:

Logical Sectors are numbered consecutively beginning at 0.
Logical Sector 0 always refers to the Master Boot Record for the device, if bootable.
No Logical Sector number can be greater than 2⁶⁴-1.
Lower Logical Sector numbers are considered to be toward the 'beginning' of the device.
Logical Sector numbers are consistent.
All Logical Sectors are the same size, equal to the amount of physical storage represented.
The size of a Logical Sector is no less that 256 bytes.
The latency time seeking between any two consecutive Logical Sectors is minimum.
Logical Sectors cannot refer to overlapping regions of the physical media.

The Physical Media Abstraction Layer determines Logical Sector size, LogicalSectorSize, which is the number of 8-bit bytes each Logical Sector represents of the physical media. In addition, the Physical Media Abstraction layer determines the number of Logical Sectors used to represent the physical media, NumLogicalSectors ; it also determines the function which maps Logical Sectors to physical regions of the media.

It is the sole responsibility of this layer to translate Logical Sectors, used by all higher layer of abstraction and functionality, to physical regions of the media. This is the only layer that should have to concern itself with the details of accessing the physical media. All higher layers have no idea of the working of the hardware nor the physical layout of the media, but rather perform all operations in terms of Logical Sectors assuming the above guidelines for Logical Sector properties.

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 are used to determine whether a number of sectors are in use or available for use. This is done by using each bit in the Free Space Descriptor to represent whether a single successive logical sector is in use or not (0 indicates the respective logical sector is in use, 1 indicates it is not). The number of logical sectors accounted for per Free Space Descriptor depends on the size of a logical sector (since a Free Space Descriptor is exactly one logical sector in size), but can be determined using the formula

SectorsPerFSD = LogicalSectorSize * 8
Traditionally, PCs have used 512-byte sectors implying that 512*8, or 4096, sectors could be accounted for per Free Space Descriptor. In addition, it needs to be noted that the logical sectors which are used to hold Free Space Descriptors themselves have to be accounted for like any other logical sector. The number of Free Space Descriptors varies based on the number of logical sectors, NumLogicalSectors. Every logical sector MUST be accounted for using a Free Space Descriptor, and it is not possible for the sectors account for by Free Space Descriptors to overlap. 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.

The location of each of the Free Space Descriptors is stored as a series of 64-bit Logical Sector numbers in a consecutive series of sectors ideally stored near the beginning of the storage media. This series of sectors is called the Free Space Descriptor Location Table and each 64-bit entry is the Logical Sector number of the Free Space Descriptor which accounts for a successive series of logical sectors. For example, if LogicalSectorSize is equal to 512 bytes, SectorsPerFSD would then be 4096, as such the first entry in the Free Space Descriptor Location Table (FSDLT) would hold the Logical Sector number of the Free Space Descriptor accountable for the first 4096 sectors (numbered 0 through 4095) and the next entry would hol the Logical Sector number of the Free Space Descriptor accountable for the next 4096 sectors (numbered 4096 through 8091), etc.


      FSDLT         Free Space Descriptors (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

      `----'

Where N is the number of entries in the Free Space Descriptor table (equal to NumLogicalSectors / SectorsPerFSD, or in this example, NumLogicalSectors / 4096).

The Free Space Descriptor Location Table may span as many sectors as it needs in order to hold the location of all of the Free Space Descriptors, but the sectors must be contiguous. As shown in the table below, the Free Space Descriptor Location Table is very efficient at describing the media and therefore the FSDLT will be relatively small (for example, only 4 kilobytes per gigabyte of capacity given a LogicalSectorSize of 512 bytes). For this reason, it is suggested that any OS implementing the Phoenix File System load and store a copy of the entire Free Space Descriptor Location table in memory for quick reference.

LogicalSectorSize	SectorsPerFSD	Bytes accounted for per FSD	FSD location entries per sector of Free Space Descriptor Location Table	Sectors accountable per sector of Free Space Descriptor Location Table	Bytes accountable per sector of Free Space Descriptor Location Table
256 bytes	2048 sectors	16,384 bytes	32 entries	65,536 sectors	16,777,216 bytes
512 bytes	4096 sectors	32,768 bytes	64 entries	262,144 sectors	134,217,728 bytes
1024 bytes	8192 sectors	65,536 bytes	128 entries	1,048,576 sectors	1,073,741,824 bytes
2048 bytes	16384 sectors	131,072 bytes	256 entries	4,194,304 sectors	8,589,934,592 bytes
4096 bytes	32768 sectors	262,144 bytes	512 entries	16,777,216 sectors	68,719,476,736 bytes
8192 bytes	65536 sectors	524,288 bytes	1024 entries	67,108,864 sectors	549,755,813,888 bytes

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 and minimizes the distance, and thus the seek time, between Free Space descriptors and the data they describe. This is by no means the only way to arrange the Free Space Descriptors, Free Space Descriptors need not even reside in the region they describe, but whenever possible it would be considered desireable to place Free Space Descriptors near the sectors they account for in order to minimize access times.

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 formatting, 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 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).

File Allocation Layer - This layer exists to group logical sectors into units called files, a file is a collection of information that logically related. In the Phoenix File System, files are described using a tree structure where that tree leafs hold the actual file information. Each node and leaf of the data tree is described using a Tree Node Descriptor:


  Structure of a Tree Node Descriptor:

  Offset   Size         Field Name     Description

    0h     QWORD        

             bit     0: Type	       (1) Descriptor refers to SubTree block (internal node)

				       (0) Descriptor refers to data block (leaf)

             bits 1-63: Location       Logical Sector number for block location

    8h	   QWORD	Length	       If Type is 1, is total number of bytes described by SubTree

				       If Type is 0, is number of bytes in data block

  ----------------

  Total: 16 bytes

Where each block of information is exactly 1 logical sector in size and can hold information either about the files contents (a tree leaf) or about the location of additional blocks (a tree node). If a sector is a data block, Length bytes of the sector are considered to be part of the file's contents. If a sector is a SubTree block, it is simply a consecutive list of Tree Node Descriptors and the Length field represents the total number of bytes of the file's information that is described by all data blocks in or under the SubTree.

Sparse files: a region of a file is considered sparse if it contains no data. This can occur, for example, if a new file is created, then a seek if performed to 1000 bytes into the file, and then a single byte is written and the file is closed. The total length of the file would be 1001 bytes, even though only 1 byte of information is actually stored in the file; the first 1000 bytes are considered sparse. The Phoenix File System is efficient is storing files with sparse data by making note of the condition using a Tree Node Descriptor. The Type indicates the region of the file is a data block since it actually refers to the file's contents. The Length is the number of bytes in the sparse region, and the Location has the special reserved value of 0. (Location value 0 is considered reserved in the File Allocation Layer because logical sector 0 will always hold the Media Descriptor Block for the device). There cannot exist a sparse subtree as it would be illogical. Any information read from a sparse file region will always be 0. A sparse region 0 bytes in length is used to indicate a Tree Node Descriptor is not in use (entire Tree Node Descriptor is all zeros).

The basic properties of a file are described using a File Node with the following structure:


  Structure of a File Node:

  Offset   Size         Field Name     Description

   00h     DWORD	MagicNumber    Special number to help discern a File Node from other

				       data should the file system become corrupt, equal to

                                       31534650h

   04h	   DWORD	HardLinks      Number of references made from Directories to this file

   08h     DWORD	Flags	       Basic file attributes

             bit    0 : ArchiveFlag    Set whenever the LastModified field is updated

             bit    1 : SystemFlag     Indicates file is an operating-system related file

             bit    2 : HiddenFlag     Indicates file should not be listed in default file listings

	     bit    3 : ReadOnlyFlag   Indicates file cannot be written to or deleted

             bits 4-7 : (reserved)     must be 0

             bit    8 : ImmediatePurge Indicates whether file should be immediately purged on delete

           bits  9-15 : (reserved)     must be 0

           bits 16-18 : FileType       Type definition for file data

                                         000 = generic file

					 001 = directory

				         010 = symbolic link

           bits 19-21 : (reserved)     must be 0

	     bit   22 : DeletedFlag    Indicates whether or not this file has been deleted

	     bit   23 : PurgeFlag      Indicates whether or not this file is to be purged

           bits 24,25 : InternalFlag   Indicates what file information, if any, is stored

				       internally if the File Node

				          00 = no internal data

				          01 = internal rights information

				 	  10 = internal extended attributes

				 	  11 = internal file data

           bits 26,27 : (reserved)     must be 0

           bit     28 : NodeSize       Indicates whether or not the File Node occupies the full

				       logical sector

                                           0 = File Node is half the size of the logical sector

				           1 = File Node occupies the entire logical sector

           bits 29-31 : (reserved)     must be 0

   0Ch     DWORD        Owner	       Object ID of owner of this File Node

   10h	   DWORD	Creator        Object ID which created this File Node

   14h     DWORD        Modifier       Object ID of user who last modified File Node

   18h     DWORD        Created	       Date/Time File Node was created

   1Ch     DWORD        LastModified   Date/Time File Node was last modified

   20h     DWORD        DataAccessed   Date/Time file data last accessed

   24h     DWORD	DataModified   Date/Time file data last modified

   28h     QWORD	FileSize       Total length of file data

   30h     1 TND        Rights         Rights list data tree

   40h     2 TNDs       EAs            Extended Attributes data tree

   60h     7 TNDs       FileData       File contents data tree

   D0h     x BYTES      InternalData   minimum of 48 bytes of space specifically set aside for

				       storing small amounts of data inside the File Node

				       without using data trees. The InternalFlag determines

				       which information, if any, is stored internally.

A file node is always at most 1 logical sector in size and at least 256 bytes in size, as such, the amount of space reserved for internal data with a File Node can vary from 48 bytes to LogicalSectorSize-208 bytes in size. A File Node may occupy an entire sector or only half of a sector, the latter only being valid for LogicalSectorSizes of 512-bytes or more (since one half of 512 bytes is 256 bytes, the minimum size of a File Node). Furthermore, each File Node is identified using a File Node Number of which bits 1-63 indicate the logical sector number the File Node resides in, and bit 0 is clear if the File Node is in the first half of the sector and is 1 if the File Node is in the second half of the sector. The following table summarizes the minimum and maximum sizes of File Nodes and the amount of space reserved in each File Node for internal data, based on the size of a logical sector.

LogicalSectorSize	Supports halfing logical sector	Minimum File Node Size	Maximum File Node Size	Minimum Internal Data Reserve	Maximum Internal Data Reserve
256 bytes	No	256 bytes	256 bytes	48 bytes	48 bytes
512 bytes	Yes	256 bytes	512 bytes	48 bytes	304 bytes
1024 bytes	Yes	512 bytes	1024 bytes	304 bytes	816 bytes
2048 bytes	Yes	1024 bytes	2048 bytes	816 bytes	1840 bytes
4096 bytes	Yes	2048 bytes	4096 bytes	1840 bytes	3888 bytes
8192 bytes	Yes	4096 bytes	8192 bytes	3888 bytes	7984 bytes

When data is stored internally, the field(s) that would ordinarilly used to store Tree Node Descriptor(s) for the given data are instead overwritten with a portion of the internal data. This can be safely done since the InternalFlag identifies which data is stored internally, and if the data is being stored internally, then the external data Tree Node Descriptor field(s) are not used, thereby leaving them available to store additional internal data. The space normally reserved for the Tree Node Descriptors is first used in the storage of internal data before utilizing the space specifically reserved for internal data. If the Rights List or Extended Attributes are stored internally, the first two bytes of the internal data are the length of the remaining internal data in bytes; the remainder of the internal data is the actual information to be stored internally. In the case of internal file data, the FileSize field can be consulted to determine the amount of internal data, and as such two bytes are not prepended to the internal data. The following table shows the maximum amount of internal data that can be stored in a File Node utilizing this optimization; it should be noted that this efficient use of File Node space is not a feature that can be optionally implemented, but is a standard component of the Phoenix File System.

LogicalSectorSize	Maximum Internal Data Reserve	Maximum Internal Rights Info	Maximum Internal Extended Attributes	Maximum Internal File Data
256 bytes	48 bytes	62 bytes (64 total)	78 bytes (80 total)	160 bytes
512 bytes	304 bytes	318 bytes (320 total)	334 bytes (336 total)	416 bytes
1024 bytes	816 bytes	830 bytes (832 total)	846 bytes (848 total)	928 bytes
2048 bytes	1840 bytes	1854 bytes (1856 total)	1870 bytes (1872 total)	1952 bytes
4096 bytes	3888 bytes	3902 bytes (3904 total)	3918 bytes (3920 total)	4000 bytes
8192 bytes	7984 bytes	7998 bytes (8000 total)	8014 bytes (8016 total)	8096 bytes

Of the three sets of information stored per file, the Rights list and Extended Attributes formats are operating system defined and not directly visible to user software, however the file data is not operating system defined. This makes sense since the primary purpose of a file is to store information relavent to the user and therefore is not necessarilly of interest to the function of the operating system, such information can include executables, word processor documents, configuration files, etc. A Rights list is maintained to determine which users or groups of users have access to that information, and Extended Attributes are maintained to give system add-ons a storage area for additional file properties.

Rights list format:

The rights list will consist of an array of Rights List Entries, where each entry specifies the rights for the file node for one user or group Object ID. To determine the number of entries in the Rights List, we have two methods to pick from as the one we will use: A) have the last entry be for user 0 with 0 rights, or B) let the first entry contain basic information about the rights (including the number of entries). I prefer B) because user 0 should be either the system or the root user. Also, I just thought of a *big* problem: For rights, we have no way of knowing which path to follow to determine rights for a user if they do not have specific rights to this file. For instance: suppose we have file /foo/bar/file.dat and file /bar/foo.dat both having the same file node, then if a user tries to access it, and they don't have specific rights, do we use the rights they have in /foo/bar/ or /bar/? I guess we could use the current path and resolve that to the path given for the file (i.e. if they are in /foo/ and the path for the file is bar/file.dat then we would come up with /foo/bar/file.dat as the fully qualified path and use that path to handle rights inheritance. But that means that the same file can have different rights (via inheritance) in one location than in another. I guess that'll work. Another solution I was thinking of was to have a "primary path" that was always used to determine the rights information by having the file node number of the parent directory of the primary path stored with the number of rights list entries at the start of the rights list. That would be complicated, and I think I prefer my first idea. What do you think?)

  Structure of a Rights List Entry:

  Offset   Size         Field Name     Description
   00h     DWORD        User           Object ID of user or group to whom the rights pertain
   04h     DWORD        Rights         Determines what rights the User has to this file node
             bit    0 : Find           user may see file node
             bit    1 : Read           user may read file data
             bit    2 : Write          user may write to file data/change link location for
                                       soft links/modify directory information for directories
                                       (e.g. creating a new link)
             bit    3 : Modify         user may change information in the file node (note:
                                       since writing data to the file node changes three
                                       fields in the file node, we need to decide if those
                                       are exceptions to this rule, or if a user must have
                                       both write and modify to actually write to a file.)
             bit    4 : Delete         user may unlink the file from a single link
             bit    5 : Purge          user may purge file (unlinks all hard links at once)
             bit    6 : Change access  user may change the rights for the file 
             bit    7 : Change EA's    user may change the Extended Attributes for the file
             bit    8 : Change owner   user may change the owner of the file
            bits 9-31 : Reserved       (0)  

  ----------------

  Total: 8 bytes

Extended Attributes format: blah blah blah