File system for small compact flash

[Atlantis]

Currently I am working on my homemade 6502 computer. EhBasic is already runing. Recently I was able to connect CF card to my system. Then plan is to integrate it with LOAD/SAVE commands of EhBasic. To to that I need some kind of file system. I have only 16kB of EPROM and I need to fit Basic, FS and I/O routines inside. So file system must be rather lightweight. Initially I thought about using some 6502 FAT16 implementation (if there is any). That way it would be possible to easily transfer files between homemade system and my PC. But it is not crucial feature, so some solution incompatible with modern computers will also be fine. In that case I simply add some xmodem file transfer possibility.

CF card is rather small (for modern standards). Currently I am using 32MB industrial version. Probably I won't be using anything bigger than 128MB in that system.

[GARTHWILSON]

I started a discussion on that at http://bradsprojects.com/forum/viewtopi ... =17&t=1233 titled "super-simple file system for flash memory," on the Brad's Projects forum because it was not specifically 6502-related. There are seven posts there. I probably should have just done it here. You are specifically looking to use it in your 6502 computer anyway; so it's definitely appropriate. I would like to see the discussion pick up. You could copy things out of there in the [quote]...[/quote] sections to comment on, and bring it all into a forum (this one) which will do it more justice.

[floobydust]

Last year I started working on an adapter for my recent (well, 2 years ago) C02 Pocket-SBC. The adapter integrates a DS1511Y RTC and a 16-bit transfer capable IDE port. The adapter has a 44-pin 2.5-inch IDE connector, so any smaller drives as well as flash cards can be used. I have an initial PCB layout completed, but need to finish the GAL logic, which decodes the I/O for both IDE and RTC and provides the control signals for the 16-bit data port.

Needless to say, I've been looking at implementing a filesystem for an attached IDE device as well. I've looked at a lot of different filesystems.... FAT, Minix, EXT2, etc., and even thought about creating one from scratch, but that's a lot of work. Overall, I think FAT makes the most sense logically, as you can always attach the device to a PC and run CHKDSK, Format media, transfer files, etc. with ease. One simply needs to get the FAT based filesystem running on the 6502... easier said than done.

Another possible option is to use Daryl's IDE adapter, which is based on an ATmega chip that holds the filesystem and provides an SPI interface. Perhaps one could take his code and implement an 8-bit parallel interface to attach via a port on a 6522. This would greatly reduce the 6502 amount of code required to get a filesystem implemented.

I think Commodore took their approach of a dedicated CPU simply because of the limited address space of the 6502 (64KB). The 1541 has 16KB of ROM and 2KB or RAM to implement their DOS. The 1581 drive has 32KB of ROM (around 24KB used) and 8KB RAM for the DOS. So depending on how complex your filesystem is, ROM usage could be larger than what you would prefer. My current ROM usage is just shy of 16KB for a high function Monitor (about 5KB), a BIOS for console and timer (less than 1KB with I/O space) and a CMOS version of Enhanced Basic (under 10K).

I'm still planning to get my RTC/IDE adapter finished by end of year.... then writing the BIOS to support will be next. After that, well... filesystem time.

[drogon]

Just some thoughts here ...

I've written a filesystem for my own 6502/65816 systems - however I have the luxury of running it on a separate processor (an ATmega) and it's written in C. It's based on a filesystem that was originally written on the 6502 - on the Apple II and that filesystem is Apple ProDOS.

ProDOS on the Apple needs about 16KB of RAM (or ROM) to run in (although at least 2KB of that is the very low-level read/write track sector stuff)

The other 6502 micro I used extensively "in the day" was the BBC Micro. This also had filing systems in ROM and they were from 8KB to 16KB depending on the filing system complexity.

So you're looking at up to 16KB of 6502 code to implement a filesystem - depending on the complexity.

FAT16 might be a good candidate - the filesystem layout is well known and documented.

In my own filesystem - I wanted more than the 12 character filename limit of ProDOS (up to 21 characters and 8+3 wasn't an option for me), so I expanded the directory structure from the ProDOS one. I also wanted the filesystem to reflect some of the Acorn MOS file attributes so I could more easily run BBC Micro software, although in the C realm it's unixy like, and that is extended to the 6502 side with 'shims' to translate the Acorn MOS calls (osFile, etc.) into the right open/read/write/close calls.

The main limitation is the size of the 'disk', or partition. 16 bit pointers with 512 byte sectors gives you a maximum disk/partition size of 32MB. For now, I have put a standard DOS MBR partition table on the SD card, so I have 4 partitions of 32MB each. For my systems with 64KB of RAM (the 6502) or 512KB RAM (The 65816) it's OK for now. When I need it, I'll use an extended partition table and have dozens of partitions of 32MB. (I never found the 130KB limit of the Apple II disks to be an issue, but maybe my expectations weren't high in those days)

The other advantage of using the ATmega 'host' processor is that I can use internal RAM (it's a 1284p with 16KB RAM) as a small RAM disk, as well as the FLASH (4KB) as a small disk too. I designed the filesystem code to work with variable sector sizes, so on the SD card it's 512 bytes (happens to be the 'native' sector size of an SD device), or down to 64 bytes for the RAM and Flash disks. 4KB isn't big, but it's handy for testing and storing configuration into.

Beware of simply making the sector size bigger - sure, go to 1K sectors and get 64MB disks, but then you need more RAM in the 6502 if you're buffering sectors or want more than one file open at a time. You may also want to cache other bits of the filesystem too for speed and efficiency. You could go to 24 or 64 bit block pointers, but then you need more on-disk storage space for the metadata blocks to store the pointers to data blocks (by whatever name you wish to call them). So there are tradeoffs everywhere.

I can't (yet) read the SD card on my desktop Linux system, although I can copy/backup the raw partitions. One day I'll write a FUSE driver for it, so I can mount them.....

If anyone wants more info just ask here.

Cheers,

-Gordon

[dmsc]

Hi!

In te Atari 8-bit family there are a few different DOS, with different on disk formats and memory requirements from 2kB to 10kB, but all sharing the same programming interface as all OS devices (open, close, read bytes, read record, write bytes, write record, seek, delete, rename, see at https://atariwiki.org/wiki/Wiki.jsp?pag ... %20Handler ). You can copy the on-disk formats for your own.

Most common DOS are:

- DOS 2.0 and DOS 2.5. The most common format, about 6kB for the resident area (file-system handling, OS interface and sector buffers), plus 5k command menu. Files are saved as a linked list, last three bytes of each sector hold a link to the next sector of the file and the size of the data in the sector. Empty space is kept in a bitmap for fast allocation. Limited to 1024 data sectors of 128 bytes each. Random access and deletion of files is slow as all the sectors needs to be read.

- SpartaDOS. Multiple versions available, original is from 6kB to 10kB for the resident area, including a resident command processor (similar to MS-DOS one), with support for internal and external commands. Files are stored with a at least one sector index that contains the number of each sector of the file, and a pointer to the next sector index if needed. Also keeps a used sector bitmap for fast allocation. Supports sub-directories that are stored like regular files, and 8 devices with up to 65535 sectors of up to 256 bytes each. Random access is fast as you can use the sector index to jump to any byte of a file, deletion is fast, only the index needs to be read.

- BW-DOS: Uses same on-disk format as SpartaDOS but is only 6kB for all the buffers and resident area including the command processor with support for batch files. To keep the size small, it expresses operations using a simple byte-code, with 16 bit arithmetic and single byte commands to read or write sectors. Also supports up to 8 devices with up to 65535 sectors of 256 bytes max.

- MyDOS: Extends the on-disk format of DOS 2.0 to add sub-directories and up to 8 devices with 65535 sectors of 256 bytes max. About 6.5kB for the fie-system handling , OS interface and sector buffers, plus a loadable menu of 6.5kB.

- SpartaDOS-X. Newer version of SpartaDOS, compatible on disk format but with support for loadable drivers (for hard drives or other devices), sectors of up to 512 bytes, partition tables, etc. Uses a bank-switched cartridge of 128kB with all internal and external commands (with a file-system in ROM), only about 2K resident in RAM (mainly buffers and thunks that call to the ROM).

- LiteDOS: Only 2kB for all the buffers and resident area, includes a very crude command line processor (only single-letter commands) and only one file open at a time. Can read DOS-2 and compatible disks. Uses clusters of up to 64 sectors, support devices with up to 512 clusters, limiting the on-disk bitmap to 64 bytes. Each cluster stores a link to the next in the last bytes, same as DOS-2.

Have Fun!

[dolomiah]

Atlantis wrote:

Currently I am working on my homemade 6502 computer. EhBasic is already runing. Recently I was able to connect CF card to my system. Then plan is to integrate it with LOAD/SAVE commands of EhBasic. To to that I need some kind of file system. I have only 16kB of EPROM and I need to fit Basic, FS and I/O routines inside. So file system must be rather lightweight. Initially I thought about using some 6502 FAT16 implementation (if there is any). That way it would be possible to easily transfer files between homemade system and my PC. But it is not crucial feature, so some solution incompatible with modern computers will also be fine. In that case I simply add some xmodem file transfer possibility.

CF card is rather small (for modern standards). Currently I am using 32MB industrial version. Probably I won't be using anything bigger than 128MB in that system.

Hi Atlantis. I also had a constraint of 16KB EPROM to fit in a bunch of stuff. In the end I managed to squeeze in an integer version of BASIC (my own design) and mass storage using SD Card formatted in FAT16. It should not be too hard to port the FAT16 code to your system, as long as it has a way to read and write 512 byte blocks. I have low level SD card routines which provide this, you just need to inject your CF card routines. There is a need for some zero page and other storage as well of course, the usual things you would expect. To keep it small, I opted to not support long filenames or sub directories. But it's good enough for me - if you would like to try and port it, happy to send the source code and provide assistance.

Cheers, Dolo

P.S.

Link to my project on hackaday with source code : https://hackaday.io/project/5789-6502-homebrew-computer

I really wanted FAT16 so that I could copy files between my system and PC easily, and it really has some in handy over time.

[cjs]

I was thinking about this earlier this year and reckoned that the easiest way to do it, if you were starting de novo, would be to do it as linked lists, much as you might allocate on an in-memory heap. Each sector or block starts with a length and address of the the next block (if there is one). The root block is just a "file" of directory type containing linked records each with the name of the file, address of the first block, and perhaps metadata such as the file type, length and date. A special file (or set of files) would link to free space which initially would be a linked list of all blocks in order.

Beyond this you could add various optimizations as needed for speed, but for a Flash filesystem you wouldn't need much since you need not worry about access time, which is the main performance issue with rotating drives.

[drogon]

cjs wrote:

I was thinking about this earlier this year and reckoned that the easiest way to do it, if you were starting de novo, would be to do it as linked lists, much as you might allocate on an in-memory heap. Each sector or block starts with a length and address of the the next block (if there is one). The root block is just a "file" of directory type containing linked records each with the name of the file, address of the first block, and perhaps metadata such as the file type, length and date. A special file (or set of files) would link to free space which initially would be a linked list of all blocks in order.

Beyond this you could add various optimizations as needed for speed, but for a Flash filesystem you wouldn't need much since you need not worry about access time, which is the main performance issue with rotating drives.

You may want to look at the Flex OS for the 6809 which did something very similar: https://en.wikipedia.org/wiki/FLEX_(operating_system)

The obvious down-side is that a 512 byte sector then becomes 512 minus the pointer overhead, so copies (from 'disk' to program data in & out) become slightly more complicated - and things like random access also becomes more complicated as you'd need to read each sector in-turn to find the sector containing the data you want to seek to.

If not sticking to a FAT style filesystem, then reading Beneath Apple DOS and Beneath Apple ProDOS (both online as PDFs) are well worth the time. Initially I implemented a crude version of Apple DOS before moving on.

-Gordon

[cjs]

Thanks for the mention of FLEX; I didn't realized it used this sort of linked list disk storage mechanism. You wouldn't happen to have a link to some technical documentation on the details of that, would you?

drogon wrote:

The obvious down-side is that a 512 byte sector then becomes 512 minus the pointer overhead, so copies (from 'disk' to program data in & out) become slightly more complicated - and things like random access also becomes more complicated as you'd need to read each sector in-turn to find the sector containing the data you want to seek to.

Neither case is more complex, AFICS. Reading 512 bytes but copying only 508 (or however many) of those to the appropriate spot in memory seems about the same as doing all 512, and seek() is actually simpler code, though obviously a lot less efficient than if you are maintaining an index. (Which you could do instead with a binary tree instead of a linked list, if you wanted to add that sort of complexity.)

Another option that occurs to me is to do it CP/M style: drop the idea of a FAT and just keep lists (fixed-length or otherwise) of blocks in the directory itelf. This is again mainly an efficiency vs. simplicity trade-off; in fact the big advantage of the original MS-DOS over CP/M was adding a FAT.

Another thing that just occurred to me is that nobody has yet mentioned resilience to and recovery from interrupted writes (e.g., someone turns off the power in the middle of writing a file). Depending on both the filesystem itself and how you do your operations, interrupted writes can result in anything from "you don't see data recently written, but otherwise everything else is ok" to "the disk is trashed." How important it is that the disk not be trashed in these situations is probably something you want to keep in mind.

[drogon]

cjs wrote:

Thanks for the mention of FLEX; I didn't realized it used this sort of linked list disk storage mechanism. You wouldn't happen to have a link to some technical documentation on the details of that, would you?

Not without some more online searching which I'll leave as an exercise to the user

cjs wrote:

drogon wrote:

The obvious down-side is that a 512 byte sector then becomes 512 minus the pointer overhead, so copies (from 'disk' to program data in & out) become slightly more complicated - and things like random access also becomes more complicated as you'd need to read each sector in-turn to find the sector containing the data you want to seek to.

Neither case is more complex, AFICS. Reading 512 bytes but copying only 508 (or however many) of those to the appropriate spot in memory seems about the same as doing all 512, and seek() is actually simpler code, though obviously a lot less efficient than if you are maintaining an index. (Which you could do instead with a binary tree instead of a linked list, if you wanted to add that sort of complexity.)

OK, but copying a nice power of 2 can be easie in 6502 land..

Once you take the pointers out of the data blocks and into a separate block, you have an "i-node" style and a hierarchy, so you get to look like ProDOS/UFS and it all just gets bigger from there... UFS (Unix File System) is a contender too (early versions). ProDOS can be quite efficient for very small files, so if your file is < 512 byes (strictly will fit into one disk block), then there is no overhead.

cjs wrote:

Another option that occurs to me is to do it CP/M style: drop the idea of a FAT and just keep lists (fixed-length or otherwise) of blocks in the directory itelf. This is again mainly an efficiency vs. simplicity trade-off; in fact the big advantage of the original MS-DOS over CP/M was adding a FAT.

Also look at the original Acorn/BBC Micro DFS - fixed number of files per disk (seemed ok when 400KB was a disk). A difficulty is extending files when there is no space after the file - then there's a need to compact, or re-arrange files, somehow...

cjs wrote:

Another thing that just occurred to me is that nobody has yet mentioned resilience to and recovery from interrupted writes (e.g., someone turns off the power in the middle of writing a file). Depending on both the filesystem itself and how you do your operations, interrupted writes can result in anything from "you don't see data recently written, but otherwise everything else is ok" to "the disk is trashed." How important it is that the disk not be trashed in these situations is probably something you want to keep in mind.

The Raspberry Pi world has highlighted a few drawbacks of SD card storage - the first being inferior quality SD cards, another being the power supply to the card and there's the issue of power fail during a write which can destroy a card although the Pi Foundation left a Pi running for 2 weeks being power cycled at random (via a relay controlled from another Pi) which didn't corrupt the card - not sure that proves much, but without a UPS/Batteries (and or lots of money to throw at more elegant solutions) all systems will be prone to that sort of failure. The other failure here might be a system crash, or someone hitting reset, but that's what 'fcsk' is for ...

-Gordon

[cjs]

drogon wrote:

cjs wrote:

Another option that occurs to me is to do it CP/M style: drop the idea of a FAT and just keep lists (fixed-length or otherwise) of blocks in the directory itelf....

Also look at the original Acorn/BBC Micro DFS - fixed number of files per disk (seemed ok when 400KB was a disk). A difficulty is extending files when there is no space after the file - then there's a need to compact, or re-arrange files, somehow...

Not a difficulty for CP/M, since a file's blocks need not be (and often aren't) contiguous and can be anywhere on the disk. The one issue is if the file expands to need another directory entry ("extent," in CP/M terms), since extents must be adjacent, but that's easy to deal with by simply moving that file's or another file's directory entry to a different location; the entries are small (32 byte) fixed size data structures. In most cases this will add zero or one extra sector write.

(BTW, CP/M does have a free block bitmap, it's just not stored on the disk; it's calculated during the first read from the disk and stored only in RAM.)

Quote:

...and there's the issue of power fail during a write which can destroy a card although the Pi Foundation left a Pi running for 2 weeks being power cycled at random (via a relay controlled from another Pi) which didn't corrupt the card - not sure that proves much, but without a UPS/Batteries (and or lots of money to throw at more elegant solutions) all systems will be prone to that sort of failure.

Well card destruction is quite a different thing from file system corruption! I'd probably just ignore the former since there's nothing a filesystem can do about that anyway.

Quote:

The other failure here might be a system crash, or someone hitting reset, but that's what 'fcsk' is for ...

That's exactly what I'm talking about, and an "fsck" or similar program's ability to recover is directly dependent on the file system design and the protocol used for writes. The result of powering off in the middle of an update can range from "nothing can ever go wrong, beyond you won't see the new data on the filesystem" to "filesystem unrecoverably corrupted."

Log-structured filesystems (which are typically incorruptable unless deliberately written wrong) are another option to consider, and constant-time random access storage wouldn't have the kinds of read performance issues that these can have on rotating disks. Hmm!

[drogon]

cjs wrote:

Quote:

The other failure here might be a system crash, or someone hitting reset, but that's what 'fcsk' is for ...

That's exactly what I'm talking about, and an "fsck" or similar program's ability to recover is directly dependent on the file system design and the protocol used for writes. The result of powering off in the middle of an update can range from "nothing can ever go wrong, beyond you won't see the new data on the filesystem" to "filesystem unrecoverably corrupted."

Log-structured filesystems (which are typically incorruptable unless deliberately written wrong) are another option to consider, and constant-time random access storage wouldn't have the kinds of read performance issues that these can have on rotating disks. Hmm!

In the case of RuFS (Ruby FS, my FS based on ProDOS), I allocate blocks which is a write operation, then write the data, then update the meta-date (bitmaps, file length in the catalog) so the bad things I have thought of include block loss (blocks allocated, then crash before data/metadata update), data loss - data written, but crash before meta data update), file size incorrect (as it's the last part of the metata to be updated - hopefully this should not result in total loss of the filesystem - just the file/data being written at the time of crash. The filesystem being recoverable via an fsck program. (which I've not yet written - eek - but so-far it's worked remarkably well. I did recover from one crash by simply copying files from one partition to another then reformatting the broken partition. I did a lot of testing of the FS with a RAM disk held in 8KB on the host ATmega.

Some modern filesystems try to prevent the fsck by keeping a journal, so all block writes go to the journal, then are "replayed" at a later date. (e.g. ext3/4 etc.) needs additional coding effort and some disk space for the journal.

What you're then up against (I reckon) is the resulting complexity of the FS vs. the code effort to implement it - on an 8-bit micro. If you code in ASM then you may end up with nice compact and fast code, but code that may be harder to test and debug, or bigger and possibly slower code if you write it in e.g. C.

I don't think there is an easy solution - it will always be a compromise here - more so in the 8-bit micro world.

So the Apple II: DOS was about 12K, ProDOS a bit bigger but took advantage of the "language card" which gave the Apple II's another 16KB of RAM. 2KB of that code is the low-level RWTS code (Read/Write track sector). It did include utilities like 'catalog' and 'init' though as well as a text parser which was how the Apple BASIC programs did file operations.

The BBC Micro (c1981) had the advantage of a 16KB paged ROM (called sideways ROM) where the 'language' (e.g. BASIC) shared the same address space as the filesystem, network, etc. utilities. The MOS (Machine OS) took care of all the ROM switching for you. The first FS was barely 8KB, but the Advanced DFS (supported directories and more files) was bigger, but they had up to 16KB of code space to play with.

I wonder what sort of read/write speeds people are seeing from directly connected CF devices? SD will mostly depend on SPI clock speed - it's 8Mhz in my system, so max. 1MB/sec. although I only see about 34KB/sec transfer rate between the ATmega host and the 6502 which is slower than I feel it ought to be, so there is probably room for improvement there.

Cheers,

-Gordon

[soci]

It was a quite a while ago but it may be interesting:
https://singularcrew.hu/idedos/cfs.html

This is what IDEDOS (6502/65816 operating system for the IDE64 card on C64) uses natively since 2005. There's partitioning/formatter and file system check/repair tool running on the host system of course. The file system check for 1GiB partition on a CF card with 147 MiB in 8199 files and 405 directories was 5 minutes at 985 KHz. Due to low clock speed and ATA PIO the raw transfer speed is around 90 KB/s which is plenty fast to fill up the whole 64 KiB RAM.

This was my take on the matter. I'd do it differently now but it stays as it is for stability and backwards compatibility.

One thing is sure, do something simple unless you've got plenty of time to burn and like the challenge of handling/debugging all the possible corner/failure cases

[cjb]

I've also implemented a filesystem from scratch for CF (and large IDE) storage.

It was very, very simple, but still quite functional, and the DOS wrapped around it fit into 1kB ROM space on a VIC-20. (source available on request...)

The storage is organized in 64kB blocks -- the first being the directory. The directory uses 32 bytes records with the usual elements (filename, size, load address, type..), with the record's index indicating which 64kB block the file is kept. It's very inefficient on storage naturally, but 2047 files should be good enough for any VIC-20...

[drogon]

cjb wrote:

I've also implemented a filesystem from scratch for CF (and large IDE) storage.

It was very, very simple, but still quite functional, and the DOS wrapped around it fit into 1kB ROM space on a VIC-20. (source available on request...)

The storage is organized in 64kB blocks -- the first being the directory. The directory uses 32 bytes records with the usual elements (filename, size, load address, type..), with the record's index indicating which 64kB block the file is kept. It's very inefficient on storage naturally, but 2047 files should be good enough for any VIC-20...

While, as you say, somewhat sub-optimal storage wise, this is brilliant in many way ways too. Almost too simple and given the cost (or lack of cost!) of storage in the capacities required for these old 8-bit systems, then who cares if it's not that efficient storage wise, but for programs... (and small text files?) You could almost treat each 64KB block in the same way you might mmap() a file into Unix virtual address space too.


-Gordon