7 ms·
The design of littlefs: A fail-safe filesystem designed for microcontrollers
- heyiforgotmypwd 7y agoWhy not TFAT or TexFAT?
- pjc50 7y agoIs that license-encumbered? Also, as it points out, they don't include their own wear levelling.
- compressedgas 7y agoNeither of those are bare flash file systems. They both require a flash translation layer.
- delfinom 7y agoThis is meant to run even on low-end micros without need for memory allocation. And support small SPI memory chips where you need to roll your own wear leveling across different size blocks of memory depending on chip vendor.
- the8472 7y agoAfaict checksums only cover metadata and it doesn't do any read integrity checking, isn't that bad when talking to raw flash devices since it relies on them accurately reporting errors?
- OnACoffeeBreak 7y agoI wonder if that was intended to be done by the user at file level.
- geky 7y agoYou could as a sanity check, it would be useful to insure no corrupted data gets passed into your system. Though this wouldn't protect the filesystem completely.
- evancox100 7y agoMicrocontrollers almost always use NOR flash, which is much less error prone than the NAND flash in your ssd. Still, if you need ECC (maybe it's a medical application), the company designing the MCU would build it directly in to the embedded flash. The foundry might have a standard 128-bit word size option, and an extended 144-bit word size option, giving you 16 extra bits per word for whatever ECC or secded code you want to put in. From there, it's on you to build in the right error reporting mechanisms. It's certainly worth checking whether or not littleFS property bubbles errors up if a read operation flags the data as bad. All this is assuming internal flash, I'm not sure whether external SPI flash offer similar extended word size options. I don't recall seeing any but maybe they are out there.
- the8472 7y agoI was talking about checksumming, not error correction. Since the meta-data blocks are already covered by CRC32 I wonder why the data blocks aren't.
- geky 7y agoError correction provides the same value as a checksum, but better. (the tradeoff is ECC codes are much larger and more expensive to compute) It's also worth noting the CRC is used for power-loss and doesn't actually provide error detection for metadata-blocks. Checksumming data is a bit complicated in a file system, mostly because of random file writes. If you write to the middle of a file, you will need to update a CRC, but updating that CRC may require reading quite a bit of additional data to build the CRC back up. To make random writes efficient, you could slice up the files, but then that raises the question of how large to make the slices. Too large and random file writes are expensive, too small and the overhead of the CRCs gets costly. You could make these slices configurable, but at this point we've kinda recreated the concept of a block device. The block device representing the underlying storage already has configuration for this type of geometry: erase size/program size/read size. If we checksum (or ECC) at the block device level we also get the added benefit of also protecting metadata blocks. Most NAND flash components already have hardware ECC for this specific purpose. TLDR: It's simpler and more effective to checksum at the block device level. And for MCU development, simpler == less code cost.
- Majromax 7y agoThat's mentioned towards the end of the link: > littlefs by itself does not provide ECC. The block nature and relatively large footprint of ECC does not work well with the dynamically sized data of filesystems, correcting errors without RAM is complicated, and ECC fits better with the geometry of block devices. That is, ECC and read-integrity checking is determined at the block level, not the filesystem level. The filesystem assumes that it's dealing with a block device that either succeeds or reports an error.
- geky 7y agoThere's also some cases where you don't care about the devices that develop errors. Wear-leveling delays wear errors until the end of the device's life. Once these start to develop you will eventually have storage that's unusable. The cheapest option may be to just let the device crash when it has reached end-of-life.
- technothrasher 7y ago"Usually, microcontroller code is simple and reactive, with no concept of a shutdown routine." Really? Nobody uses brownout interrupts to lock down on power loss? I almost always do a few things as the power is fading, flagging the situation at the very least in order to clean up when power is restored.
- kartoffelwaffel 7y agoAlso why not chuck a capacitor in the mix to provide a little power buffer to shutdown the filesystem gracefully.
- pantalaimon 7y agoIt adds quite some space and probably costs as much as the MCU.
- keithnz 7y agonot as simple either, you still need to detect that the power is gone or fading independent of the capacitor...which all adds up
- deleted 7y ago[deleted]
- kabdib 7y agoYeah, paying thirty cents for a capacitor to coddle a ten-cent MCU doesn't make a bunch of sense. Much cheaper to teach your software folks how to write transactional updates to that flash. Typically you pay a small speed penalty to get update atomicity (in addition to having a more complicated implementation).
- delfinom 7y agoMany MCUs do not appreciate slow rise-times when using their internal regulators. Then you start oversizing your regulator or providing them replacement regulators. Which then opens more cans of worms, etc, etc.
- keithnz 7y agothis is what we use for our filesystem on our low power embedded device. It works well!
- aquabeagle 7y agoIt's worth pointing out this was written by engineers at ARM.
- geocar 7y ago> and the unfortunate fact is you can't traverse a tree with constant RAM This is not true. See Knuth, The Art of Computer Programming Vol.1, § 2.3.5). Generally I wouldn't recommend naive SDW as a good strategy for filesystems, but if you have a fixed number of processes (common in microcontroller applications) it might be worth trying.
- geky 7y agoReading through 2.3.5 (Lists and Garbage Collection), it looks like it's describing a tree where the leaf nodes also contain references to the root of the next tree. This wouldn't work as a copy-on-write tree, as the root node is changed every write. Copy-on-write behavior requires very strict trees, and this gets in the way of adding extra structures for traversal.
- fanf2 7y agoPointer swizzling tree traversal requires writes to the tree which isn’t possible in this case.
- jorangreef 7y ago> Logging filesystem are beautifully elegant. With a checksum, we can easily detect power-loss and fall back to the previous state by ignoring failed appends. An edge case when designing a log-structured file system is that a corrupt checksum in a log entry could actually mean one of three things: power loss while writing the last transaction, a misdirected write or bitrot, or a misdirected read. If you simply read the log up until the corrupt checksum, assuming this can only mean one thing, then you might fall too far back and lose data that has been acknowledged to the user as synced. This could in turn then break the guarantees required for implementing things like Paxos, which could ultimately wreak havoc with a distributed system. To detect power-loss, you need more than just a checksum. You need a checksum, but you also need a way to "snap" the new log tail onto the old log tail in a two-phase commit. So you write out all your data, then you write out your new log tail, then you sync, then you snap your new log tail on using two atomic sector writes, one of which needs to be synced. The number of syncs are the same as before, you haven't actually added any additional syncs, but this way you ensure that your log references data which exists, and you can now tell the difference between a power failure and a corrupt log entry. A power failure is recoverable (roll back), but a corrupt log entry is unrecoverable (assuming no log entry replicas) and means the file system is unmountable.
- geky 7y agoI'm not sure I'm following this snap operation. What is a "log tail" in this context? Does this the snap operation still work if we are copying over entries of the log lazily and we don't have a definite end-of-log? You are right though, a checksum used this way provides no protection over bit errors or misdirected write/reads. But, if you assume no bit errors, a checksum can provide power-loss protection as long as there's a fallback. But doesn't this just move the problem somewhere else? Yes. In this case it moves error detection onto the block device. But it turns out performing error detection/correction at the block device level is simpler and more effective. Most NAND flash components even have built-in ECC hardware for this specific purpose.
- devwastaken 7y agoIsn't that essentially sqlite?
- benlwalker 7y agoAll of the flash SSDs I am familiar with have no fixed relationship between a logical block and the actual NAND media backing it. In other words, the device automatically wear levels internally and the only control the user has over wear is the total number of writes they perform. Given that, I don't understand the discussion of wear leveling in this FS. Maybe someone can explain further.
- blattimwind 7y agoMCUs are often still used with plain flash memory over SPI.
- kabdib 7y agoNo SSDs here, this is raw flash. This is the wear leveling layer.
- benlwalker 7y agoI assumed so, but then why all the comparisons to file systems that are designed to run on top of a flash translation layer? I would have expected something in big bold letters at the top saying this is designed to run without an FTL, whereas the other filesystems rely on one to wear level. For example, this is right at the top: "Writing to flash is destructive. If a filesystem repeatedly writes to the same block, eventually that block will wear out. Filesystems that don't take wear into account can easily burn through blocks used to store frequently updated metadata and cause a device's early death." This isn't true. It's only true for filesystems that aren't running on a regular block storage device. It's even more egregious to use the word block because almost everyone assumes that means a logical block. They must be using it to mean a NAND page, which has entirely different behavior and does wear out.
- kabdib 7y agoThe word "block" is extremely generic and the semantics and sizes of "blocks" vary widely across different storage technologies, platforms and specific parts. It's like saying "packet" -- there are a gazillion packet types, sizes and formats, and when I use the word "packet" I don't expect everyone to assume I'm just talking about ethernet framing, even though that's a really popular packet format.
- ranger207 7y agoWow, this is pretty cool to read. I'm in college for CS right now and this uses most of the stuff I've learned so far. It's neat to see all of it come together.
- im_down_w_otp 7y agoIt would be nice for a thing calling itself "fail-safe" to have some amount of formal evidence of its fail-safe properties by way of both checked abstract models & verified source/binary level implementation (I also think the same thing about everything posted here related to security too). I browsed through the repo and didn't see anything other than what amounted to narrowly targeted unit & integration tests. The test scripts are mostly in Python, so even just some Hypothesis tests (property-based testing framework for Python) would be nice to try to quasi-brute force some more empirical assurance that this filesystem behaves as claimed and expected. That said, this is likely to come in very handy, and seems definitely worth taking a look at.
- PaulHoule 7y agoI like the doubled-up metadata records. It is like the mechanism used in transactional exFAT, but covers more of the metadata and is more scalable. At first I worried about the overhead but is is nothing compared to the other overheads in filesystems unless you have a crazy number of files. I am not sure about the system that generates "random" offsets. It seems that it is based on XOR and linear checksums and I've personally used that kind of method to hash things and had wildly imbalanced bucket use. It's a disaster if you are carving work to thousands of nodes based on the hash but might not be so bad for the intended use.
- mbar84 7y agoI made a print version if you're into that sorta thing: https://www.dropbox.com/sh/g46fo30rnwt6lah/AABTQAlrXXoCvR-8abnywAjKa?dl=0 https://www.dropbox.com/sh/g46fo30rnwt6lah/AABTQAlrXXoCvR-8a...
- xmichael999 7y agoI did enjoy the first 20% of the post explaining the difference in file system types, however beyond that I was pretty much lost :)