8
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ is FAT32 or FAT16 on an SD card too slow? \$\endgroup\$
    – vicatcu
    Commented Feb 24, 2012 at 13:16
  • 2
    \$\begingroup\$ This question is fully on topic here, but if you don't get any great responses StackOverflow can probably help. Lets hope we can get some good answers here though! \$\endgroup\$
    – Kellenjb
    Commented Feb 24, 2012 at 14:39
  • \$\begingroup\$ @vicatcu Its not that its too slow, for my application SD card plus connector is more costly and SD cards can be less reliable. Kellenjb I wasn't sure where to put it. Like a lot of embedded design questions this sort of falls in the middle. If it doesn't go well here I would gladly move it. \$\endgroup\$
    – Kris Bahnsen
    Commented Feb 24, 2012 at 15:37
  • \$\begingroup\$ Is it a raw flash chip? If so, how do you handle dead blocks? Quite a big part of the flash FS implementation deal with dead blocks. If you feel JFFS/JFFS2 is too heavyweight, you might want to check out YAFFS. It feels like a very simple file system at least, so it should be quite lightweight. \$\endgroup\$
    – Leo
    Commented Mar 13, 2012 at 20:07
  • \$\begingroup\$ Yes it is. Bad blocks are not a terrible in this particular application since its so long term that the data pulled out is just a rough trend, and in most cases I doubt the logging will be used at all. \$\endgroup\$
    – Kris Bahnsen
    Commented Mar 13, 2012 at 21:49

2 Answers 2

Reset to default
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Your approach sounds somewhat similar to mine. I would suggest adding another slight twist, though: reserve a couple bytes in each block to indicate that it's been "started" and that it's "full". All blocks except the erased blocks should have the "started" bits programmed. When it's time to erase a block, set the "full" byte on the last byte of data, then erase the block, and then immediately set the "started" bit of the oldest erased block. On startup, if you see that the "last" block is "full", rather than "started", redo the erase. \$\endgroup\$
    – supercat
    Commented Mar 13, 2012 at 19:01
  • \$\begingroup\$ Such an approach may seem like overkill, but if a flash block is partially erased, it's possible for bytes to arbitrarily decide to read FF or something else. The fact that a block appears blank is no guarantee that bits won't spontaneously "appear" there. If you lose power while an erase is in progress, wait a little while on the next startup and then repeat the the erase even if the block appears blank. \$\endgroup\$
    – supercat
    Commented Mar 13, 2012 at 19:05
  • \$\begingroup\$ Thanks for the info, I will look in to it a little deeper when I actually hit the code for the flash storage and let you know what happens. \$\endgroup\$
    – Kris Bahnsen
    Commented Mar 13, 2012 at 19:52
  • \$\begingroup\$ @supercat: Thank you, that sounds like a great idea. \$\endgroup\$
    – davidcary
    Commented Mar 17, 2012 at 3:11
  • \$\begingroup\$ @davidcary: I've don't know that I've ever had a block which appeared totally blank and wasn't, but I have had a block which would yield different results on consecutive reads. It's possible that the block was incorrectly read as blank my code tried to program it anyhow, resulting in an odd mishmosh of new programmed data and old interrupted-erase garbage. In any case, a scenario where a block would sometimes appear blank is hardly unrealistic. \$\endgroup\$
    – supercat
    Commented Mar 17, 2012 at 13:56
1
\$\begingroup\$

It's been quite a few years but I wanted to follow up on this in case anyone else wandered by. It looks like there are a few projects these days, which are actively maintained (as of Jan 2020) that are filesystems intended for microcontrollers targetted at NOR SPI flash.

Note that I've not tested these in any capacity, but they do exactly what the original question was looking for: "...data structure that represents a collection of mutable random-access files..."

https://github.com/ARMmbed/littlefs - Created by ARM, BSD licensed

https://github.com/joembedded/JesFs - Doesn't really appear to be licensed, but was very specifically designed for SPI NOR flash.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.