FILE SYSTEM

Isetta has a 32MByte serial flash, and it is there because I want her to have a file system.

While making this file system, I also make a simple command shell, at first just for testing the file system functions but it will grow to get every command that is needed.

The serial flash is a W25Q256JV device. It has 8,192 erasable sectors of 4kByte each.

It would be cool to have a little wear-leveling. That almost rules out a FAT system, where an allocation table is written to the same sector, each time as one of the files changes (unless you write it on a different position each time).

What did I come up with ? The system has the following properties:
 - files (that consist of one or more sectors)
 - hierarchical directory structure
 - deleted or overwritten files stay available (but are normally not visible in the directory), until erased (after adjustable time).
 - supports hidden files

FILE STRUCTURE

The first sector of a file (or directory) has this structure:
At 0x0000:
 - (byte) flags
 - (word) sector of the directory that it belongs to
 - (byte) lsb of the properties address
 - (byte) hash of the name
 - (byte sequence) name (zero-terminated), max ca 100 chars.
At properties:
 - (word) number of the following sector
 - (word) reserved for more flags (unused yet)
 - (4 bytes) date (YYYYMMDD, so today is 20 24 05 14)
 - (4 bytes) time (HHMMSS00) (so it is zero-terminated).
 - (4 bytes) file size (little-endian)

At 0x0100:
 - maximal 0x0F00 bytes of data 

The first sector has a lot of space to define more properties. For the sectors that follow, only the flags and the number of the next following sector need to be present. For ease of programming, the data in these following sectors also start at 0x0100.

The flags at address 0 are these ( they are active low ):
 - bit0  if 0, sector is ready to be written
 - bit1  if 0, sector is in use
 - bit2  if 0, sector belongs to a file (but is not first sector)
 - bit3  if 0, this is a directory
 - bit4  if 0, this file was deleted (but still available)
 - bit5  unused
 - bit6  unused
 - bit7  if 0, this file is hidden

FLASH LAYOUT

Where are the files placed in the flash and how do we find them back ?
There are two rules:
  - The first sector of a file will be placed at a position that is based on  the directory that it belongs to, and on a hash function of it's name. If that position is occupied, it will start looking for an empty position in one of the following sectors.
  - The following sectors of a file can be placed anywhere, since they are all linked.

There is only one fixed position, and that is the ROOT directory at sector 1.

DIRECTORIES

The flash is divided in 8 compartments. The files of a certain directory will all be stored in the same compartment. A simple hash function, applied to the sector number of the directory, tells with compartment it belongs to.

FILES

In every compartment there are 1024 sectors. A hash function, calculated from the first and last character of the file name, determines the preferred position of the first sector in the compartment. If the preferred position is already occupied, the first free sector that follows this preferred position will be used. 

So, when the file name is known, it can be found very fast, because only the flags, directory, and name of a file have to be checked in each sector. In most cases it is not needed to check the full filename, because checking the hash is sufficient. In such cases only 5 bytes of the sector need to be read.

When the file name is not known (when asking a directory) only a single compartment has to be searched for valid files. Only the flags and the directory sector have to be checked. This is also very fast, when you type a "ls" command you don't notice any delay.

The bytes for date and time have the highest bit set, except the last byte of the time, that is zero. Now we can use the same sort algorithm for names and time/date.

REALIZATION

The file system was built (in Z80 assembler). It uses microcoded functions for reading/writing on the SPI bus. It works. Functions were made to find a file, and to read or write a sector.
Directories can be created (mkdir) and you can change directory (cd).
There is now also a TRANSFER command, that transfers a file from the Raspberry Pi to the Isetta filesystem (in the current directory). 

Very soon, the loader will, after reset, switch to the BOOT directory, and load a BOOT.BIN and execute it.

For the moment, the binary files will have the Intel-Hex file structure, as discussed in the previous log.