The design of littlefs: A fail-safe filesystem designed for microcontrollers

https://github.com/ARMmbed/littlefs/blob/master/DESIGN.md

by ingve • 7 years ago

278 72 7 years ago

github.com

heyiforgotmypwd• 7 years ago

Why not TFAT or TexFAT?

pjc50• 7 years ago

Is that license-encumbered? Also, as it points out, they don't include their own wear levelling.

compressedgas• 7 years ago

Neither of those are bare flash file systems. They both require a flash translation layer.

delfinom3• 7 years ago

This 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.

the84723• 7 years ago

Afaict 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• 7 years ago

I wonder if that was intended to be done by the user at file level.

geky6• 7 years ago

You 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• 7 years ago

Microcontrollers 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.

the84723• 7 years ago

I 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.

Majromax• 7 years ago

That'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.

geky6• 7 years ago

There'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• 7 years 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• 7 years ago

Also why not chuck a capacitor in the mix to provide a little power buffer to shutdown the filesystem gracefully.

pantalaimon• 7 years ago

It adds quite some space and probably costs as much as the MCU.

delfinom3• 7 years ago

Many 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.

Nokinside• 7 years ago

Really. It's best not to trust on shutdown procedures for fail-safe persistence if that really is important. Use log-structured file-system and do cleanup and verification when the power is restored. When microcontrollers have brownouts, it's best to assume that you may have already garbage in the memory bus.

Of course, when improved fail-safety exist just to improve reliability measured in hours and fail-safety is not critical function, all what I said is irrelevant.

rnestler• 7 years ago

In one project I worked on we monitored the 24V rail and when it was dropping, the MCU had enough time to do cleanup /shutdown work until the 3.3V supply dropped.

adamweld• 7 years ago

anything with a 24v rail has much more power budget/bulk capacitance than most small embedded devices... so what worked there may not work well in other more common cases

delfinom3• 7 years ago

Nope. Because brown-out detectors on micros are meant for momentary glitches and unreliable. The detectors can preserve a brown out detected bit in their reset cause registers. However, they don't guarantee the micro's core will get the interrupt in time before losing power. And if the brown-out goes down to POR levels, you won't even get the brown out cause bit and instead POR.

The best you can do for file systems is track a "dirty flag". You keep it set unless you power down willingly yourself.

londons_explore3• 7 years ago

You design the circuit... You can decide exactly how many microseconds of power you'll get between the brownout interrupt occurring and the lowest operating voltage. Your job as designer is to write the code to guarantee completion in that time.

Microcontrollers don't have to suffer the same issues as app/web developers. They can know exactly how many clock cycles something will take.

kabdib5• 7 years ago

Brownout detection isn't sufficient. There are many other sources of "instant stop", from simple hard-crash bugs to bit-flips in RAM that either cause a crash or multiple-bit ECC fault, take your pick because they will all turn out the lights without warning.

For consumer devices there's ESD testing, where devices are subjected to several kilovolts of zap in certification tests and are required to survive. Typically this means the device will reset and recover, but it needs to be in usable condition afterwards. If a surprise reset results in a toasted file system and a brick, you won't be able to sell the device in markets that require this testing, which is most of Europe and (I think) the US.

The right way to do a persistent store is to expect the lights to go out on any arbitrary bus cycle and design around that.

I've written a few of these. They're fun.

varjag2• 7 years ago

My understanding was if the function is interrupted on discharge, you fail the test. At least that's how our equipment was tested by an independent lab.

garganzol• 7 years ago

My usual design is to monitor AC powerline with opto-coupler and then enter the brownout procedure in MCU when the power loss is detected. The remaining energy stored in AC/DC converter capacitors are then used for a graceful shutdown purposes.

The usual brownout procedure actions are: a) flush the current state to MCU flash memory (EEPROM) so that the work can be automatically resumed; b) wait for a power-on condition.

In this way, the device is able to significantly reduce flash memory wearing. It turns to be a significant winning factor in cheaper MCUs, as they only allow about 100,000 EEPROM write cycles max.

And it comes for cheap, as the only thing you need is an opto-coupler plus a bit of software wizardry.

keithnz2• 7 years ago

this is what we use for our filesystem on our low power embedded device. It works well!

aquabeagle• 7 years ago

It's worth pointing out this was written by engineers at ARM.

geocar• 7 years 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.

geky6• 7 years ago

Reading 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• 7 years ago

Pointer swizzling tree traversal requires writes to the tree which isn’t possible in this case.

_urga• 7 years 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.

geky6• 7 years ago

I'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• 7 years ago

Isn't that essentially sqlite?

IA21• 7 years ago

I don't think sqlite would fit inside the microcontrollers this post is about.

oscargrouch• 7 years ago

This is not my field of expertise, so forgive me if im mistaken, but isnt 'Ohad Rodeh B-trees'[1] a simple and more elegant solution than a journal/WAL?

As far as i know its already used in Linux Btrfs and in LMDB, and i wonder why, if they were designing this from scratch, why they didnt go for this in the first place. Familiarity perhaps?

By the way i have code that deals with the SQLite Btree directly and by reading your comment now i understand why theres a need for a two-phase commit as expressed in:

BtreeCommitPhaseOne()

BtreeCommitPhaseTwo()

[1] https://liw.fi/larch/ohad-btrees-shadowing-clones.pdf

jdub• 7 years ago

The article explains why tree structures were inappropriate for the use case.

benlwalker2• 7 years ago

All 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• 7 years ago

MCUs are often still used with plain flash memory over SPI.

kabdib5• 7 years ago

No SSDs here, this is raw flash. This is the wear leveling layer.

benlwalker2• 7 years ago

I 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.

Unklejoe• 7 years ago

This is probably meant for interfacing directly with flash ICs, which have no real abstraction.

ranger207• 7 years ago

Wow, 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• 7 years ago

It 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• 7 years ago

I 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• 7 years ago

I made a print version if you're into that sorta thing: https://www.dropbox.com/sh/g46fo30rnwt6lah/AABTQAlrXXoCvR-8a...

xmichael999• 7 years ago

I did enjoy the first 20% of the post explaining the difference in file system types, however beyond that I was pretty much lost :)

The design of littlefs: A fail-safe filesystem designed for microcontrollers

Related Stories