-- Leo's gemini proxy
-- Connecting to gemini.f4grx.net:1965...
-- Connected
-- Sending request
-- Meta line: 20 text/gemini
This page describes NRFS, the fifteenth filesystem for retro machines that will unify the 14 previous ones.
While playing with my 68hc11 boards, I noticed that there is so much I can do with just a monitor ROM. If I want to imagine more complex systems, I will need to elaborate a mass storage system using compatible storage devices, in order to store executable programs, load operating system modules, and store application data. I also need this if I want an assembler and, maybe, a compiler for some higher level language.
So I started looking around, to evaluate what storage devices I can use. I found two directions:
CompactFlash cards can be used as a parallel 8-bit devices
SPI EEPROMs can be easily connected to my 68HC11, which has an integrated SPI bus.
Banked parallel flashs
However, these peripheral have different block sizes.
After procrastinating a bit and rotating ideas in my head, and after looking at a video that presented a filesystem for a modern Z80 SBC (ZealFS), I determined that I had to elaborate my own filesystem to fit my diverse requirements:
flexibility of block size, and diversity of storage devices
simplicity of code and data structures
No other machine has that flexibility. Most of the systems I saw use a fixed block size of 512 bytes, or are closely related to a single machine.
And last but not least, I want to build a filesystem from scratch for study purpose.
And so I started drafting specifications for a filesystem.
The filesystem uses a block layer that allows me to read and write blocks in a transparent way. A block driver can be implemented to use SPI EEPROM, IO mapped CompactFlash, or just system RAM/ROM.
I decided that I would be able to store just files and directories, with future options not forbidding symbolic links. The file entries also store a date, a read only flag, there is provision for a future executable flag.
The filesystem starts with a superblock, that holds a signature and FS parameters including block size and block index size, and the block index of the root directory.
The rest of the disk is made of chainable blocks, the first four bytes of the block holds the link pointer, the rest is data. So a disk block is not able to hold a power-of-two number of bytes, but that is not really important.
Directories are special files that contain 30-bytes directory entries (16 of them for a 512-byte block). Each entry has a data pointer, data size, flags, and date field. As of now, there is no file owner, and only one date field, that defaults to creation date.
If dir entries are extended to 31 bytes, then one byte can hold a user identifier, and the flags have room for owner/other acess flags. The date could also be redefined as a modification date instead of creation.
Dates are packed in 5-byte arrays to avoid year-2038 restrictions. All date fields are packed in the minimum amount of bits.
Sure, some features are still missing, but I can send you the last code I have.
just drop me an email (my call @ same domain as this web site) or ask me about that on the fediverse. There is only one @f4grx over there, on the mastodon.social instance.
As extracted from source code:
/*
nrfs new retro filesystem
Intended to store files on various retro computers.
Constraints
===========
Can be used for several ranges of devices from floppy disks to compact flash
cards to serial eeproms. This means we have to support different block sizes.
No attempt is made at wear leveling, so it's only suitable for magnetic disks,
EEPROMs, and SSDs that contain an FTL, like CompactFlash.
There is no provision for user ID or access rights, except for a read only flag.
Only one date is managed for each entry. This can be set to be a "creation" or
a "modification" date.
Disk Format
===========
General
-------
Multi-byte values are stored in little endian.
The number and indexes of blocks is always stored in 4 byte fields, of wich it
is allowable to only manage a part: the number of bytes actually used for block
indexes is indicated in the superblock.
8 bits of indexes can manage 256 blocks.
16 bits of indexes can manage 65535 blocks.
24 bits of indexes can manage 16777216 blocks.
32 bits of indexes can manage 4294967296 blocks.
Any implementation not supporting this size can refuse to mount a volume that
uses indices too large, but if a filesystem has a small enough number of blocks
it can be mounted by any implementation supporting this index size.
Super block format
------------------
offset len description
0 4 signature 'NRFS'
4 1 version, currently 01h
5 1 power of two of the block size. 7:128, 8:256, 9:512
6 1 number of bytes in block indexes
7 1 reserved
8 4 number of blocks
12 4 index of root directory (usually 1)
16 5 UTC compact date of the volume creation
This specification describes version 1 of the data structures. A future
implementation may choose to use this field for backwards compatibility.
The block size is configurable to match the underlying block device and
allow compromises in buffer space. Only one block needs to be buffered. This
has impacts on performance, but it should not matter on the intended platforms.
Block size 7 (128b) is only expected for very tiny systems, 8 (256) matches I2C
EEPROMs, 9 (512) is for standard IDE/CompactFlash and floppy storage.
12 (4096) could be used on usual serial NOR flash devices, but this is not
recommended without an additional wear leveling layer which is not provided.
For extreme systems, an absolute minimum block size is 64 bytes, to store 2
directory entries per block. 32 bytes can't fit a directory entry in a block.
Info: Max volume size according to block size and number of bytes in block
indexes:
indexbytes 1 2 3 4
indexbits 8 16 24 32
maxblocks 256 64k 16M 4G
blocksize / maxvolumesize
128 32k 8M 2G 512G
256 64k 16M 4G 1T
512 128k 32M 8G 2T
4 bytes indexes are much larger that would be needed by any storage device
usable on any retro class computer.
Implementations supporting 3 bytes are expected to cover much of the use cases
except the largest CompactFlash cards.
Storage blocks
--------------
All blocks on the disk except the super block are for storage of data.
All blocks have the same structure: the first 4 bytes of a block are a link
pointer, and the rest of the block is used to store data.
link pointer 00000000h indicating no link
link pointer ffffffffh indicating a free block
Data elements to be stored are fragmented in a chain of blocks, each holding
(blocksize-4) bytes after the forward link to the next block.
Directories
-----------
Directories are stored the same as regular files. They contain 30-byte sized
directory entries.
Entries do not span across two directory pages.
The first entry of a directory is a .. entry to the parent directory.
There is no . entry for the current directory.
There is no .. entry for the root directory, eg executing cd .. in the root will
result in a "ENOENT" error.
Here is the number of entries that can fit in each block size:
64: 60 bytes available, 2 entries (none lost)
128: 124 bytes available, 4 entries (120 bytes + 4 lost, ideal size 31b/entry)
256: 252 bytes available, 8 entries (240 bytes + 12 lost, ideal 31.5b/entry)
512: 508 bytes available, 16 entries (480 bytes + 28 lost, ideal 31.75b/entry)
The free bytes shall NOT be used to store any useful data.
Directory entries
-----------------
offset len description
0 4 Block index holding the first data block for this entry. This
value is 00000000h for deleted/unused entries.
4 4 For regular files, file size in bytes. for directories, number
of entries in directory pointed by this entry.
8 1 Entry flags: 0x01 directory, 0x10 read-only, 0x20 executable
9 5 UTC Compact date, binary format as described below.
14 16 entry name, zero padded. No padding when max name length is used
Total: 30 bytes per entry
Date storage: binary compact format of UTC date
2 bytes: year (12 bits, up to 4095) and month (4 bits)
2 bytes: day (5 bits), hour (5 bits) and min (6 bits)
1 byte: seconds (in bits 0-5)
Total 5 bytes per date, including 2 spare bits
Date example: 7E 73 AD CF 06
year = 0x7E7 = 2023
month = 0x03 = 3
day = (0xad>>3) = 0x15 = 21
hour = ((0xad & 0x07) << 2) + (0xCF>>6) = 0x5<<2 + 0x3 = 0x14+0x3 = 0x17 = 23
min = (0xcf & 0x3F) = 0x0f = 15
sec = 0x06 = 6
Date "7E 73 AD CF 06" is "2023-03-21 23:15:06 UTC"
Operations
==========
data required to access the filesystem
--------------------------------------
buffer space for one block
one nrfs_t structure
one nrfs_file_t for each opened file
formatting
----------
-set the 4 first bytes of each block to FFFFFFFFh (making them available)
-allocate a free block (usually block number one) as root directory
-write superblock fields including link to root directory
FS Operations
-------------
The algorithms to implement the actual file operations are not specified.
Any implementation making sure that the above structure is maintained is fine.
When building an implementation, please take care of error conditions and make
sure that the FS is as consistent as possible in case an error condition or
power loss event happens.
Below is a reference C implementation. This implementation requires external
access functions to read/write a block and get a system date. The formatting
routine needs to know the number and size of blocks.
*/
-- Response ended
-- Page fetched on Fri May 10 10:21:18 2024