Suggestion: Combine allocation table (BAM) and page chaining into a single map

[Kroc]

Just discovered your project, it's really nice! Regarding your recent video on ZealFS:

https://www.youtube.com/watch?v=eCBCXIuRWl8

Currently each file page begins with a byte that points to the next page in the chain. I believe that this is inherently inefficient when it comes to an i2c bus but there are many other benefits of switching to a combined allocation and chain map.

Instead of a byte at the beginning of each file page, a single page is reserved where each byte in order represents that same page number in the file-system.

This would function as both a block-allocation map and the page chain. For each page in the file system, the page map's byte would indicate $00 for unused, otherwise a value 2-255 that would indicate the page number of the next page in the chain.

There are a large number of benefits of doing things this way:

• The bitmap in the header is no longer needed:

  Page allocation can be seen by the byte value at the implied offset into the page map. A value of $00 indicates an un-allocated page. (It is understood that pages $00 & $01 are permanently reserved by the FS header and page map respectively). Reading a single byte in a 256 byte block is much faster and less code than extracting a single bit from a bitmap.

• The bitmap in the header is no longer required:

  Removal of the bitmap in the header leaves room for a 16 byte volume label, and potentially another directory entry.

• File pages now store exactly 256 bytes:

  A file block now mirrors original RAM contents, this means that walking RAM & disk at the same time doesn't require two out-of-sync counters, one looping 0-254 bytes and one looping 0-255 bytes. Everything about reading, writing, copying and comparing RAM <> disk is simplified, even register pressure is reduced.

• Unlimited directories:

  Since every page in the page map can contain a pointer to another page, directory pages can use the page map to chain directories rather than relying on directory nesting. A directory page can contain 8 files and the page map can point to the next page of directory entries allowing for unlimited (except by FS size) files in each directory.

  Since byte 0 is the volume header, its byte in the page allocation map can point to the directory continuation page. In this way the root directory can have an unlimited number of files, without costing a byte in the header itself; the same continuation method is used as any directory.

• Client-side caching:

  Following a file chain requires reading many pages of the i2c device. With a single page for the entire page allocation map, this can be cached on the client side so that OS already knows everything it needs to know about the file system without having to go to the bus. The lengths of each file | directory chain can be followed without having to read from the file system and a file's data page does not need to be read just to fetch the next page. The CPU can pick a single data block from the middle of a file without having to read back the entire file chain from flash