OnDeviceStructures

Structure Layout 5 (SL5; STS/K2 V1, STS/K2 V2, FSE/L, FSE/DX)

SL5 once was a read-only filing system intended to help bootstrap STS into a usable, self-hosting operating system. Four previous iterations of the SL-family of filing systems once existed; their details, however, are lost to history.

Today, SL5 is a read-write capable filing system. It has received compatible extensions since the initial development of STS, and now includes the following features:

• It properly tracks free space using a linked list.
• Files may now have up to five extents: a primary extent created upon file allocation, and up to four secondary extents which are created on-demand.
• The Volume Label VTOC entry now maintains the head of the free-space list, and includes the volume's total size.

Overall Structure

SL5's primary purpose is to get the Kestrel-2 platform to be minimally self-hosting. It's expected that reads from storage will far out-number writes. Since SL5 remains optimized for read-only access, its on-device structure is thus very simple.

Note. It is explicitly a non-goal that SL5 be fast, efficient, or robust against failures. It must only be functionally sufficient, even if not exactly correct.

Sectors 0 and 1 hold a 1024-byte bootstrap program. Together, these two sectors serve the same purpose as the MBR in a disk formatted for use with IBM PC-compatible computers. The primary exception being, of course, there is no partition table. It's assumed that SL5 will reside inside a GUID Partition Table (GPT) if desired; otherwise, it assumes flat access to the storage medium.

Sectors 2 through 31 hold a 15KiB program which serves either as a 2nd-stage bootstrap routine, or as a kernel image. STS/K2 fits entirely in 12KiB, and so doesn't require a 2nd-stage bootstrap. It remains to be seen how big FSE/DX will be; however, I strongly suspect it will also fit within the 15KB allotment.

Starting at sector 32, we find the Volume Table of Contents (VTOC). This structure serves the role of a root directory, mapping filenames to regions of storage. It's composed of a vector of sectors, each in turn, holding a vector of eight mappings.

The first sector of the VTOC holds some significance. In it, we find four special entries:

• A volume label, naming this volume explicitly, and providing information on volume size and free space.
• $IPL provides a mapping for sectors 0 and 1, thus reserving those sectors against accidental overwrite.
• $SYS provides a mapping for sectors 2 through at most 31, thus reserving the 2nd-stage bootstrap and/or kernel space against accidental overwrite.
• $DIR provides a mapping for sectors 32 through however many is reserved for the VTOC. This prevents the VTOC itself from being accidentally overwritten.

These four files need not appear in any special order; SL5 merely requires that the volume label and $DIR appears in the first VTOC sector. $IPL and $SYS can appear anywhere in the VTOC.

Note. This differs from the STS implementation of SL5, which required $IPL and $SYS to reside in the first sector as well. The original intent was to support OS/2-style micro-filesystem drivers (or uFSDs), and loading a single sector would have made it easy for a uFSD to locate and bootstrap the OS kernel. As it turns out, this assumption proved false, and so the rules have been relaxed somewhat. However, $DIR is required to be in the first sector, so that a uFSD has enough information to scan the rest of the VTOC for other files it might need while booting.

Note. The STS/K2 implementation of SL5 did not require the volume label to be present. STS/K2 always referred to the SD/MMC card in the only supported slot simply as volume "SYS:", since it was definitely the boot volume. FSE/DX may support multiple slots in the future, as well as non-SD/MMC mass storage. Additionally, STS/K2 kind of assumed a volume was always at least 32MB in size. Again, this may not always be the case when you have multiple kinds of supported devices. For this reason, all new SL5 volumes must include a volume label entry in the first VTOC sector.

After the VTOC, space may be used as required to hold files. Free space is maintained in linked lists, with the volume label containing the head of the list.

VTOC Directory Entries

A single directory entry consumes 64 bytes of space. Since 512 bytes comprises a sector, it follows that a single VTOC sector holds 8 entries.

SL5 supports filenames up to 47 characters long. The first byte of the directory entry holds the filename length. Unused filename bytes remain undefined; for future compatibility, ignore them when reading, but write NULs ($00) when creating new entries.

The final 16 bytes of a directory entry holds administrative information for the file.

Empty Slots

Offset	Size	Subfields	Description
0	1		Unused.
1	47		Unused.
48	2	.... .... .... 0000	VTOC entry type.
		0000 0000 0000 ....	Zero.
50	2		Zero.
52	2		Zero.
54	2		Zero.
56	2		Zero.
58	2		Zero.
60	2		Zero.
62	2		Zero.

The size of a VTOC is typically fixed. However, it's not likely that all available VTOC entries will be used up. Empty slots are used to indicate when a slot may be taken by a new file.

Volume Labels

Offset	Size	Subfields	Description
0	1		Name length. Must fall between 0 and 47 inclusive.
1	47		Name, stored in UTF-8.
48	2	.... .... .... 0010	VTOC entry type.
		0000 0000 0000 ....	Zero.
50	2		Sector of first node in free-list.
52	2		Last sector of the volume as a whole.
54	2		Zero.
56	2		Zero.
58	2		Zero.
60	2		Zero.
62	2		Zero.

STS/K2 currently doesn't do anything with volume labels; I originally wanted to use them for volume names on the command-line interface (e.g., WorkDisk:), a la Tripos. Volume labels in FSE/DX now take on additional importance. They not only name the volume for the human user; but, they also help the filing system implementation keep track of free space.

Files

Offset	Size	Subfields	Description
0	1		Name length. Must fall between 0 and 47, inclusive.
1	47		Name, in UTF-8.
48	2	.... .... .... 0001	VTOC entry type.
		0000 0000 0000 ....	Zero.
50	2		Starting sector of the primary extent.
52	2		Last sector of the primary extent. The length (in sectors) of the extent is start-last+1.
54	2		Secondary extent length (in sectors). 0 means no secondary extents are permitted.
56	2		If non-zero, the starting sector of a secondary extent.
58	2		If non-zero, the starting sector of a secondary extent.
60	2		If non-zero, the starting sector of a secondary extent.
62	2		If non-zero, the starting sector of a secondary extent.