2.1 Block Allocation Structure
Each block contains a block allocation structure. The structure is made up of several fixed length members and a variable length array of allocation structures. The block allocation structure is located at the end of a block in order to accommodate this variable length array of structures. Each Allocation structure in the array contains an offset, relative to the beginning of the block, and length of the allocated space. The beginning of free space within a block is determined by finding the allocation structure with the largest offset, and then adding that structure's length field to its offset. Bit fields within the Allocation structure are used to indicate whether the region described by the offset and length have been allocated, deallocated, or freed.
The remainder of space in the block is used for directory & file control structures and file data. Space for directory, file control structures, and file data is allocated starting at the beginning of the block.
This placement allows the space allocated for directory and file structures and file data to grow 'downwards' toward the block allocation structure while new entries in it grow 'upwards' toward the file system structures and data.
This scheme was selected to maximize utilization of the block by avoiding large reserved areas within the block for a block allocation structure that may, in practice, be unused. Blocks containing relatively large extents will have few entries in the Allocation structure array. Blocks containing small extents will have many more Allocation structure array entries.
Note that the Offset field in the Alloc structure is 24-bits long. This results in a maximum supported block size of 16 Mbytes. The pointers used in the directory and file structures (DirEntry and FileEntry) use the upper 16 bits to point to a specific block and the lower 16 bits to point to a specific allocation entry within each block. This limits the total number of allocations supported in this design to 2^32. This number includes allocations made for directory and file data structures as well as allocations made for file data. The maximum size of a single allocation made for a single file extent is (2^16 - 1) bytes.
For purposes of determining whether this scheme is robust enough to support future media growth, consider Flash memory media packaged in a PCMCIA memory card. Flash media that will be available in the near term, packaged in a PCMCIA memory card, results in media with a maximum of 128 blocks. Current block sizes in a PCMCIA memory card package range between 32 Kbytes and 256 Kbytes. The theoretical maximum media size for PCMCIA memory cards is 64 Mbytes based on the size of its address bus. There should be ample room for future media expansion given the current data structure design.
struct Block
{
struct
{
byte Status
byte Offset[3]
word Len
} Alloc[]
dword BootRecordPtr
dword EraseCount
word BlockSeq
word BlockSeqChecksum
word Status
}