I am currently working on a project that involves rapid, continual logging of a rather application specific metric over a long lifetime. To do this I ended up using an NXP M0 and a 32MiB SPI flash chip. The logging is continual and needs to last many years in the field (10+), and is periodically checked by a human for trend spotting. Eventually the buffer fills up and starts overwritting old data which is perfectly fine. I came up with a simple algorithm to walk the whole flash device to find the current head after a power-up (the device is powered down rather frequently outside of my control) so logging can just continue where it left off. I can just brute force through this walk and do it with ~4s as worst case scenario.
This got me thinking, are there any log structured filesystems that are catered to flash devices and microcontrollers? JFFS and all the other well known Log Structured FSs I imagine would be a little heavy for a simple microcontroller (depends on the application of course). To be more specific, I would like to know of any algorithms that are designed to specifically be a circular log with fast head seek time and/or any that are designed for a "traditional" filesystem on a flash device that can be run on a microcontroller. Traditional in this sense being on-par with something like JFFS where there is a data structure that represents a collection of mutable random-access files in a hierarchical name space.
Best Answer
rope data structure
I am fascinated by the rope data structure. I have a hobby project trying to adapt it it to a microcontroller with only a few bytes of RAM hooked to a huge Flash memory, so that I can insert and delete and otherwise arbitrarily edit variable-length text in huge text files. Text files far too large to fit into the RAM. Erasing the last half of the file and re-write it to flash, shifted by one byte, every time I insert or delete a character in the middle of a multi-megabyte text file, would be far too slow, but the rope data structure can do this much faster. Since the rope data structure can represent such mutable random-access variable-length files as immutable fixed-length pieces, it seems to be a good match for flash memory -- all edits are written in a circular-log-like fashion. Alas, all the bugs are not yet worked out in my code. :-(
fixed-length chronological logs
I did get a similar circular log system working, for a product I helped develop.
I simply wrote fixed-length records one after another, filling up flash as a circular array.
(With a completely blank flash, I started writing records about 3 blocks before the end of the array, so I could test the circular wrap-around after only a few records of data were stored, rather than starting at record zero and waiting for a month's worth of data to be written before finding out that there was a bug in my wrap-around code).
I made sure there were always at least 2 erased "erase blocks" ready to be written to. After writing a record, if there was only 2 "erased blocks" after it that were empty, I unconditionally erased the oldest block of data -- the 3rd block of oldest data after the 2 "erased blocks". (Near the end of the flash memory, "after" means "wrap around to the beginning of flash memory). (Perhaps a single erased block would have been adequate -- I forget why I thought I needed at least 2 and sometimes 3).
I forget exactly how many records I put in each "erase block", but I made sure I never had a record straddle two erase blocks -- the first 2 bytes of every erase block of flash was either the "erased" value 0xFFFF, or the first two bytes of a Fletcher-16 checksum (which is never 0xFFFF) in the header of each record.
That made it quick to scan the next time it powered-up and find the head of the circular log -- I only had to look at the first two bytes of each erase block to distinguish between "erased" and "data" blocks. (I was a little worried about "power failure in the middle of erasing a block" causing the first two bytes to be erased to 0xFFFF but leaving non-erased bytes in the middle of the block, so I wrote code for the microcontroller to check for this and restart the "erase a block" process).
Please tell me if you find other flash-friendly data structures or file systems.