_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I am hoping to hear some thoughts about simple file system. I have a goodish number of DT28F320 (4meg x8 or 2meg x16) Intel Strataflash. It is has 32 128KB erase blocks, so my thought on simple file system is having 32 files such that each file contains up to 128KB contiguous data. The first file is directory contains the names of the 31 remaining files and their true size. I can add a file name/size to directory without erasure, I can delete a file name by writing all zero; I can update file size by zeroed out previous size and write new size, but to erase and update directory I need to save its content else where, sector erase, then restore the directory.

It turns out 128KB file size also works very well with equivalent simple file system for compact flash disk. CF has 512byte erasable block, so updating is even easier.

This is just a thought experiment, I haven't done anything else.
Bill

I've thought about this a bit in the past but not really moved forward because I decided I cared more about ease of writing from modern PCs, so I implemented 6502 exfat and FAT drivers for SD cards and used those.

One thing I had thought about though, and was tempted by, was that given that the size of modern media dwarfs the capabilities of the average 6502-based system, we could easily use fixed size records for file storage, accept a hard limit on file size, and do away with any real need for fragmentation and complex allocation tables. If you are willing to limit the total file count to 256, you can still allow a maximum file size of many megabytes on even the smallest SD card. I think this is similar to Bill's suggestion.

Acorn's DFS format essentially stores an alphabetically-sorted list of filenames in the first 256-byte sector, with corresponding metadata in the second sector. The metadata includes a start sector and size in bytes, and this is enough to manage the rest of the disc surface. Searching for an empty space requires a little work, but is a rare operation; and if in our case all files take up exactly one (very large) cluster, it's just a matter of finding the first unused cluster.

If you're willing to accept a limit of 256 files on the device, cluster numbers are just bytes, which is great for a 6502, and it would be easy to use the "empty" directory entries to track unused cluster numbers.

I agree CF or SD have so much storage, filing system can be greatly simplified by trading space for complexity. A 1GB CF/SD is not much more expensive than 32MB CF/SD (if 32MB can even be found). 32MB CF can store 256 contiguous 128K files and 1GB 4096 such files. We really don't need complicated filing system when such abundance of storage space are cheaply available.
Bill

I have written filing systems for various systems in the past - it's never been my main thing, but has been needed for stuff I've worked on - mostly experimental/prototype that never saw the light of day, and the one on my Ruby boards which is somewhat full-featured but written in C... however...

So something simple - where a cassette tape is usable, so one file per SD card (wasteful of resources) to full-blown like a classic Unix-style filesystem with superblocks, inodes and whatnot (huge software complexity, especially in ASM) what does that leave us with ...

So how about this in a thinking out loud sort of way...

In a typical operating system there is a memory allocator. C users will be familiar with the malloc() function for example. My BCPL system has something similar called getvec(). (And I wrote one in Sweet16 a while back too for another project that didn't get too far)...

Behind the system call is the actual allocator - ranging from utterly trivial to hugely complex - the more RAM you have and the more CPU cycles you have at your disposal, the more complex algorithm you can use which maximises available RAM and more efficiently merges free blocks and so on. There is no fragmentation in that if you allocate a block of memory then that's it. If you want it bigger you need to allocate a bigger block and copy the data over (see the realloc() system call in Unix)

The simplest (usable!) allocator is called "First Fit" and I'm thinking this would work well for SD cards (and other media like an SPI EEPROM where seek and access times are not a factor)

(It can also work on spinning rust, just might be slower)

So how to use this on an SD card as a filing system?

Carrying on thinking out loud here...

You "format" the disc (and I'll use the term 'disc' here because...) as one big free chunk. There are markers at the start and end of each chunk as well as a pointer to the length. My BCPL implementation looks like:



Then, as part of the format procedure, you allocate a chunk big enough to hold filename and pointers to each allocated file. so if you though you might want 100 files of 31 character length then you'll need 32 bytes per filename and 4 bytes per pointer, lets say 4 bytes for a timestamp (although the world has moved to a 64-bit time_t) and 4 bytes for 'attributes' (locked, text/binary/owner/etc.) then you need 40 bytes per entry or 400 bytes.

If you ignore the "PID" field then you have 31-bits for the chunk size, that's 2GB, so that limits the size of the device (or partition) to 2GB, as well as the maximum file size to 2GB.

Personally, I feel that's more than enough for our little 8-bit systems (and even 16-bit 816's - my Ruby filing system can only handle 32MB per partition and I feel that's more than I'll ever need in the lifetime of this project)

The 'guard' words are there to protect, or at least warn of chunk overwrite, so a consistency check can quickly tell if it's corrupt or not...

In my BCPL OS, I perform a heap merge (ie concatenate adjacent free chunks) operation at the end of every program execution - some implementations will do the merge operation at every free() function. I keep a pointer to the end of the last chunk allocated to speed up searches, but if/when it doesn't find a free chunk, then I reset the point to the start and traverse the list until it finds a free chunk large enough. Chunks that are large enough get split into smaller chunks.

The upshot of that in a filing system is that you would need to pre-allocate the file size in advance if you wanted to sequentially write a file - otherwise you'll run out of space. My guess is that almost all operations will be simple "load a file" or "store a file" to and from RAM, however if you create a large enough file in the first place, then the usual read/write/seek/append type operations would be possible within the length of that pre-allocated file.

Writing a "compact" type routine should be fairly straightforward, should the system become too fragmented, but I've found that I can run my BCPL OS for days/weeks compiling, running, testing code and never have issues with running out of RAM or not being able to find a free chunk of RAM big enough to use.

Is it prone to corruption? Yes. This does happen when I have an errant program that scribbles all over RAM, the guard words are checked at free() and merge() times - in a filing system? I feel overrunning the end of a chunk should never happen as the underlying code should be checking the bytes written into that chunk vs. the actual size.

Other issues? It may not actually be possible to know how much data is actually written. ie. how big a file is? For a whole-file (e.g. a BASIC program) save operation this won't be an issue as the chunk will be an exact size, but creating a big file for random access? Hard to know.

Then there will be file data vs. the underlying block nature of the device - SD cards are block devices with a fixed block size of 512 bytes, so using this scheme you'll need some sort of way to translate a 32-bit word offset to a block number plus offset - that's not hard though and at one level you can say it actually maximizes usage, but on the other hard try buying an SD card < 8GB now...

In practical terms? There is the read/modify/write operation needed when a chunk splits a block boundary - this is perhaps sub-optimal, so the easy thing is to round UP all file allocations so that they fit inside an exact number of media blocks (which for SD card is 512 bytes) Then I'm thinking I'd add an extra word into the header to say the exact size - when known - of the saved data..

So you type in your little BASIC program and hit SAVE "work of art" and ... The BASIC builds a block of data - pointer to a filename, start in RAM, end in RAM (or length) and calls the operating system (This is how OSFILE works in Acorn and my Ruby OS), the OS searches for a free chunk big enough, rounded up to an even size for the media, the header now has an extra word with the real size, as well as the whole chunk size, writes the data, updates the directory and that's that. (And the search might just be a matter of returning the current 'end' pointer without doing the list traverse, so very fast. At boot time (and file delete and merge time), you search the disc to find the last chunk but that also ought to be relatively fast, then you know where you are

And so on.

This really ought to be easy to code up in 6502/816 ASM - I'd hope in under 4K plus the underlying block read/write code and off you go...

I might actually give it a go, but in BCPL as a bit of a proof of concept as I really do not think I'll be writing any more '816 code now that I can do everything in BCPL

Cheers,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I think many of us have considered a small filesystem for the 8-bit CPUs. The ones that exist from long ago may, or may not be something you want to use. As far as the storage media goes, I think you could simply ignore the concept of a flash device and just focus on some storage device that has some number of blocks that can be randomly accessed using a block number, hence LBA. That would be the preferred level of the (or any) filesystem to work at. BDD's "black box" approach would make the filesystem usable with a wider range of devices.

Next would be defining and validating a set of requirements. This would range from functional requirements such as API calls, e.g., load/save, rename/delete, create/open/close, record level access, search, etc. Other (non-functional) requirements would include things like, how much memory (ROM and RAM) should the filesystem be limited to, supported storage size, allocated block size, how many directory entries (and how large they are), maximum number of files, flat model, number of supported drives/devices, etc.

As simple as the above appears, it won't be (simple) to come up with a set of either that a larger number of folks will agree upon. Still, I think this becomes a useful discussion and perhaps might result in something tangible at some point. For a starting point, I would suggest looking at an existing of set of function calls... as I have it handy, I'll just list the PEM calls in DOS/65:



A total of 37, which include console calls: reader/punch and user, which could likely be deleted from a simple filesystem. There are likely other calls that can be eliminated as well. I'm not saying to use the DOS/65 in a heavily modified manner, but just to get an idea if the PEM calls are logical for a starting point.

If not, perhaps Daryl's CF flash storage system might be a starting point:
https://sbc.rictor.org/ide.html



Gotta start somewhere...

_________________
Regards, KM
https://github.com/floobydust

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I've spent too long working on filing systems. SheepFS1 is unsuitable for your purposes because it is intended to be packed with a virtual machine into 32KB or less. The highlight of this system is that directory entries may be five bytes: one byte for block pointer and four bytes for Radix 40, six character file name. 40 * 40 * 40 = 64000 and therefore it is possible to store three characters in two bytes. I adapted this from DEC Radix 50 encoding where 50 * 50 * 50 = 125000. I subsequently discovered that a 6502 disassembler uses a similar encoding and that it was copied by two or more other disassemblers. I am perplexed that a common algorithm has not been shared with a filing system.

Anyhow, I believe that SheepFS2 meets your specification. It is suitable for 16MB-1TB of storage. It is very loosely based on Acorn DFS and the Eris 2010 filing system. This arrangement assumes compatibility with primary partition tables and therefore all sector references will be offset by 64 or significantly more.



Divide a partition into buckets of 64KB or larger. Bucket size determines maximum file size. So, nominally, maximum file size is 64KB. There is a 1:1 mapping between file content and bucket. There is also a 1:1 mapping between bucket number and meta-data. Specifically, bucket zero is special and contains 255 (or more) pages of 256 bytes. Each page has the meta-data for one bucket/file. No fragmentation. No FAT. No BAM. Furthermore, you may note the similarity with 65816 where bank zero is special. This is intentional to aid understanding. The major difference is that bucket size >= bank size for the purpose of using more than 16MB storage.

The first half of each meta-data page is file name in Radix 40 encoding. (Hey, I like Radix 40 encoding.) This allows 192 character names to be stored in 128 bytes. The second half of each meta-data page is 32 bit fields or thereabouts. This includes 32 bits for house-keeping, 32 bits for optional fragment number, 32 bits for optional previous record, 32 bits for optional next record, 32 bits for optional payload checksum, 32 bits for optional meta-data checksum, 24 bits for flags, 40 bits for optional time-stamp, 32 bits for optional user number, 32 bits for optional group number, 32 bits for file length, 32 bits for optional load address and 32 bits for optional execute address. (I hope these meta-data fields are sufficent for BigDumbDinosaur and drogon.) Obviously, all fields are in little-endian order.

If meta-data entry M describes negative length then the name is not valid and bucket M does not contain useful data. If meta-data entry M describes zero length then the name is valid and the file has zero length. If meta-data entry M has positive length then the name is valid and bucket M contains useful data. If length exceeds bucket size then meta-data is corrupted.

Meta-data entry zero maps to bucket zero and this bucket is the meta-data table itself. Therefore, page zero of bucket zero has meta-meta-data which includes a unique "magic number" to identify the class of filing system, a unique number to identify the instance of filing system, version number for the filing system format and bucket size (in bits where 16 means 64KB).

In the default case, where buckets are 64KB, 256 buckets * 64KB per bucket = 16MB. This fits on many small, crufty CF cards. When bucket size is doubled, maximum file size is doubled. However, when bucket size doubles, this includes meta-data bucket zero. Therefore, the number of bucket references also doubles. Overall, each additional bit of bucket address adds two additional bits to filing system size. For example, 512 buckets * 128KB per bucket = 64MB. 1024 buckets * 256KB per bucket = 256MB. Most squanderously, 65536 buckets * 16MB per bucket = 1TB. This covers a wide range of volume sizes with relative efficiency.

In the default case, actions such as directory listing, file creation or file deletion may require a linear scan of 64KB. For larger filing systems, this may increase significantly. This may be a problem if alphabetical listings are required. It is for this reason that the meta-data includes non-critical previous/next fields. This allows ordering of the records to be maintained for display. However, it is not critical if this chain is corrupted or absent.

In the case of smaller volumes, I suggest an optional extension where 16MB of text may be stored between bucket zero and bucket one. This would allow lines of repetitive text to be stored with 3 byte references. In the most trivial case, where 85 pointers do not span a page boundary, 21760 references may be made to lines of any length without exceeding a 64KB file limit. This would be incredibly useful for source code where the majority of text does not change between versions. Furthermore, it is possible to implement this in a manner which remains compatible with a GETCHR/PUTCHR interface. Unfortunately, insertions are O(n^2) and this will slow as storage increases. However, unless we collectively intend to type more than 16MB of unique lines, we will never exhaust this area. This also means we never have to compact it.

I previously implemented 3 byte line references on Commodore Amiga for the purpose of saving space on 880KB floppy disks. The trivial implementation was unbelievably slow. This could be significantly improved by computing an 8 bit hash of a line and reducing the problem by a factor of 256. Specifically, this would guarantee that each linear scan is 64KB or less.

Despite this being a trivial filing system, there are multiple places where an integrity check may be performed. For example, sequential write to file may occur in parallel to a rigorous, 32 bit checksum calculation. Likewise, the optional line reference extension stores lines by hash value. Therefore, any line with a mis-matched hash is obviously in error.

I don't think that any read operation requires more than four sectors to be resident in memory. In particular, files may be statelessly accessed by numerical reference to protocol multiplex, device number, partition number, file number and file offset. This allows all files on all volumes to be "open" simultaneously without increasing the minimum number of sectors resident in memory.

If this filing system is of interest and we can decide the final arrangement for meta-data fields, I can write an archiving utility to collate or extract files. I don't expect an archiver to be a command line script larger than 10KB.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!

I have a technique to implement optional LDPC on random access files. It requires significant space for the checksum. This wouldn't be a problem if a file name is restricted to 96 characters or less.

I also have a technique for optional sub-directories. One bucket contains a name-space of files with corresponding buckets for file content. One bucket contains a name-space of directory names without corresponding buckets. Directories have numbers. Directories belong to other directories and directory zero indicates membership of the top level directory. Files also have directory numbers where zero indicates inclusion in the root directory.

Assuming that none of the file names clash (and assuming that directory names do not clash with file names), a simple system will see all of the file names collapsed down to one flat directory. Whereas, a more advanced system will see the optional directory structure. Overall, it is possible to migrate a filing system from a flat table of contents to a hierarchical scheme via named inodes.

Anyhow, this scheme requires one optional bucket. It might be worthwhile to define a set of optional buckets. This would provide upward/downward compatibility and allow simple systems to skip optional, advanced features.



SheepFS1 has CAFEFACE. I previously worked in an Internet cafe. It it also a variant of Boaty McBoatface or, my favorite, Floaty McFloatface.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!

I forgot to apply network principles to filing systems. Specifically, it is possible to implement an optional parity check on sequential files and random access files by using a Hamming code and its dual. For 2^N words of storage, it requires 2N+1 words of checksum. 16MB buckets require 49 byte checksum. This is quite verbose but file names could be reduced to 64 bytes or so. If you want to add fancy features in the future, the checksum is compatible with sparse files, de-duplicated files and encrypted filing systems.

I also considered a Radix101 encoding where it is possible to store six Roman, Greek or Cyrillic characters within five bytes. I know that's a marginal saving but I considered it.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!