super-simple file system for flash memory

[Garth]

Does anyone here know of a super-simple file system for flash memory that has already been worked out? I can use a search engine as well as anyone, but reading a ton of web pages takes a lot of time, and I was hoping someone here was already familiar with one or more and could give quick recommendations for or against. With thoughts of coming up with my own, I've been listing criteria and drawing diagrams of how file headers might be constructed, but so far I'm not very satisfied with what I come up with.

Ideally I'd just use SD cards; but I have found the details of handling the various densities, block and sector sizes, CRC error-detection methods, security methods, fragmenting, wear-leveling (if any), FAT systems and subdirectory structures, and so on, to be daunting. I'm not going to try anymore unless there's a really simple explanation somewhere. I think the things I need to transfer between the home-made workbench computer and the PC could all go over RS-232, including with the FTDI RS232-to-USB adapter if it's on the newer PC that doesn't have an RS-232 port.

I want something that takes very little code to run it. How did the C64 and other home computers of its era handle the files on floppy discs? (I know the C64 disc drives had their own microprocessor in them.) I tentatively plan on starting with 4MB SPI flash memories in tiny SO-8 packages that I have built onto postage-stamp-sized plug-in cards, then maybe moving up to 16MB, or remotely possibly even 64MB, but definitely not more. This is not for photos, videos, music, bloatware, or any of the other things that take up a lot of storage, but rather for workbench-control source code, assembled or compiled programs, measurements taken, etc.. I'm thinking of something like this (although these are not set in concrete):

• up to dozens, maybe hundreds of files, max (256?), not tens of thousands
• no directories (everything in root)
• no fragmentation. If an edited file doesn't fit where it came from, a longer available area is found for it. If there is none, one or more other files are moved to get enough contiguous blank space
• not necessarily having a FAT. I can imagine various ways to do this.
• names can be long enough to be meaningful, unlike DOS's 8.3. A 31-character limit is reasonable. (Is that what C64 had?)

Ideas?

[Garth]

Going totally without a file system might be something like the cassette tapes of the home computers of the early 80's when disc drives sometimes cost more than the computer, except that the flash memory would be around a million times as fast as tape for "record" and "play" and perhaps a billion times as fast for "fast forward" and "rewind." On the cassettes, you wrote the names of your "files" (usually programs) on the label, and if there was more than one on the tape, you wrote the tape counter's value where each "file" started, and optionally where it ended. Leaving safety space between programs was fine, but there was no safety catch if you accidentally let one program overwrite the beginning or end of another. You kept track of it by hand.

Certainly there's an in-between step that could be implemented to ease the job of file management with minimal code.

[brad]

Sorry but I can't help out at all with this one Garth. I do however like how you brought up the tape days of the 80's. I was actually experimenting with an Amstrad CPC464 just the other week which had an inbuilt tape drive.

A tape type memory system would certainly seem to be the easiest way to go in terms of circuitry and coding I would think but of course if you were to delete files you would need to manually shift things around to avoid fragmentation should you want to load new larger files.

It's been a few days since you first posted this - have you been able to find anything ideas on the internet?

[Garth]

It's been a few days since you first posted this - have you been able to find anything ideas on the internet?

Here's something a friend sent, which I'm sure he wouldn't mind my posting:

I guess it will depend on how fancy you want to get. You could emulate the relatively simple filesystem found on Commodore floppy disks, although the general structure and operation are not real efficient when applied to high capacity storage media. The layout of a Commodore floppy filesystem is as follows:

• "Super block." This is a single disk block (256 byte blocks on all Commodore floppy drives) that carries some basic information about the filesystem, such as its name, the total number of data blocks, the number of data blocks that are free, the number of data blocks in used, etc. The super block also has a 16 bit ID field to uniquely identify each disk. That field is used in the Commodore DOS to recognize when one disk is removed from the drive and a different one is inserted.
• BAM. The block allocation map (BAM) is a multi-block bitmap that indicates the status of the data blocks that are part of the filesystem. There is a one-for-one correspondence between each bit in the BAM and a data block, hence there are as many bits in the BAM as data blocks in the filesystem. If a bit is set, the corresponding data block is free, otherwise the block is in use. As a file is written, the BAM is consulted when a data block is needed. When a file is deleted the corresponding data blocks must be freed.
• Directory. This is a list of the files in the filesystem. The Commodore directory structure is a sequential list of 32 byte slots. Sixteen bytes are reserved for the filename (padded with trailing nulls), a byte is used for the file type (with $00 meaning the slot is free and may be claimed for cataloging a new file), a pair of bytes is used to maintain a count of the data blocks consumed by the file and a pair of bytes is used to point to the track and sector address of the file's first data block.
• Data blocks. These blocks contain whatever data has been written to a file. Bytes $00 and $01 in each block are pointer bytes, whose function depends on whether or not the current data block is the final block in the file:
  
  • If another data block follows the current block, bytes $00 and $01 point to the track and sector address of the next data block.
  • If the current block is the final data block in the file, bytes $00 and $01 indicate how many data bytes are in the current block. As Commodore disks were formatted to 256 bytes, byte $01 always contained $00.
  Track and sector addresses are expressed as single byte integers, with the first track being $00 and the first sector in each track also being $00.

You could readily adapt the above, changing track and sector pointers into absolute block addresses, and using 32 bit fields to accommodate the full extent of the storage medium. It's probably about as simple as you are going to get and still achieve organized storage.

That said, I'm sure you can see some obvious problems. If you want to append data to a file you have to read the chain of data blocks to get the address of the last block. Similarly, if you want to delete a file, you have to read the chain of blocks in order to find out which blocks to free up. Random access likewise requires sequential reading of the chain of blocks to get to the desired data.

These limitations are why simple filesystems are not appropriate as storage gets more capacious. When Fiscal Information developed the Lt. Kernal hard drive subsystem for the Commodore 64 and 128, they basically had to throw out the Commodore methods and adopt minicomputer operating system storage model. You will probably have to do something similar, unless you don't care about flexibility and performance. As programming exercises go on a scale of 1 to 10, I'd give it a 7 or 8 in difficulty.

I was thinking along similar lines, so to hear that they did it this way is a little bit assuring (although I hope I can make it simpler). This definitely gives me more to think about though.

In a later email, he said,

• Fragmentation is supported, but fragmentation isn't much of an issue in low-capacity floppy discs.
• The Commodore DOS, which runs in the drive itself, not the computer, had a validate command that would try to fix up disk errors. It was nothing like moden filesystem checkers like fsck on Linux or chkdsk on Windows.

[brad]

I'm now realising just how complicated it must be to program a good file system. There are so many things to think about - not just storing files but all the other variables that go along with it.

I'm quite interested to see what you end up going with here. I smiled at the end of the post where he mentioned it was about a 7 or 8 on the difficulty scale!

[BigEd]

Might be worth looking at Acorn's Rom Filing System - it uses a data layout very like their cassette filing system, but with links from one file to the next to allow a rapid scan. The official format officially allows names up to 10 chars, but they are zero-terminated so no fundamental name length limit. It is of course a read-only file system, but it must be easy to append to it, and if you adopt a convention of deleting files by mangling their names or flagging them in some way, you have something where you can write a new file. Random access for read/write might be another matter, but each file is a list of data blocks, so maybe not so bad.

See page 14 of http://www.sprow.co.uk/bbc/library/sidewrom.pdf
and page 349 of http://stardot.org.uk/mirrors/www.bbcdo ... 0Guide.pdf

Edit: also this design document for a different flash file system might have useful information:
https://github.com/pellepl/spiffs/blob/ ... /TECH_SPEC

[Garth]

This 12-minute video is relevant. It's not a "super-simple file system" (like this forum topic title calls for), but it does describe folders and fragmentation rather simply.
https://www.youtube.com/watch?v=KN8YgJn ... o&index=22

This is in a sequence of videos. The next one after it is about data compression to reduce file size.