NAND Error-correction Code
docs.kernel.org
docs.kernel.org
On an embedded device, you might have a piece of NAND flash directly attached to the CPU e.g. via a parallel bus or SPI. Usually with a controller somewhere in between, or integrated in the SoCs.
In Linux, there is a subsystem called MTD (memory technology devices) for dealing with not-quite-block storage that provides a thin hardware abstraction layer with an internal driver framework for NAND flash and backends for all sorts of controllers.
Some particularly cheap flash chips/controller do not support hardware bit-error correction. There are IIRC 2 software engines that a driver can use as a fallback: hamming and BCH[1] based (the former is documented here).
The MTD subsystem is really just a thin abstraction layer tough and provides a uniform API for e.g. page read/write & block erase for the flash chip it talks to. There is another subsystem called UBI (Unsorted Block Images) that can be stacked on top of MTD. It takes care of wear-leveling, bad block management and implements LVM-style logical volume partitioning. It also does not emulate a block device, but acts more like a flash device with idealized properties.
There are 2 filesystems in Linux which are designed to deal with the weirdness of those devices: the older JFFS2, which stacks directly on top of MTD, and UBIFS on top of UBI.
Raw NAND has a number of characteristics which are incredibly unpleasant for a traditional filesystem to deal with, including:
1) No small writes. You usually have to program a whole page at a time, which is often larger than a sector on a hard disk (~16 KiB). Filesystems which are accustomed to being able to flush single-byte writes to disk will be very disappointed by this.
2) No overwriting. Once a page has been written to, you can't write to it again until it's been erased. This makes even emulating small writes difficult.
3) Erase is a big hammer. It operates on a large (32 - 128 MiB) group of pages and erases them all at once.
4) Bad sectors. Sometimes an erase block is just bad on chip and you have to work around it. And, as flash wears out, blocks can go bad, and you'll just have to hope there's a spare available.
Bottom line is -- if you want to write a filesystem that works with flash directly, you have to write it to work that way from the start. Modifying a traditional filesystem like ext4 to run on flash would effectively be a complete rewrite.
I mean that’s patently incorrect though… All modern PCs are running on raw NAND with a flash controller mediating things to present as a legacy block device and ext/xfs/nags etc runs just fine this way. Heck, even Apple OSes, which actually afaik do have their own in-house flash controller, had HFS running on top of the translation layer rather than baking those requirements into the FS (I think this is also true for APFS but not 100% certain).
So while everything you wrote about the complexities of raw NAND are true, it doesn’t follow that the filesystem MUST handle all that complexity itself. Something designed to take full advantage might perform better, but that’s always true and seeing cheaper storage solutions with reliable fsync might be a worthwhile trade off (+ you can always run a filesystem that’s better designed to accommodate the underlying HW details)
"Unfortunately it is a rather difficult task to create a good FTL layer and nobody still managed to implement one for Linux."
You forgot yaffs2 which was commonly used in the early days of android and runs on top of MTD
Typical algorithms work like:
* 1 bad bit is corrected
* 2 bad bits produce an error. Since there's nothing else meaningful to do, this can only propagate to the higher layer.
* 3 or more bad bits may produce wrong data or an error
so we wouldn't expect to hit case 3 without hitting case 2.
Now that's a name I hadn't heard in a long long time.
The post is from 2008 anyway, I wonder what would happen if one were to put this code (or the earlier, non-unrolled-loop versions) to the test with modern compilers that can do all sorts of black magic for performance, or if it could be extended to take advantage of modern CPU features.
Looking at the naive code from Analysis 1 and comparing GCC 4.1.2 to GCC 13.2 there's a huge difference. Even when forcing both to generate code for the same old architecture (k8) so its more fair.
GCC 4.1 generates code which is a pretty direct translation of the source: branchy, operates on bytes.
GCC 13.2 does a ton of optimization. There's only a single jump/loop. It uses prefetch. It uses SSE instructions to operate on 128-bits at a time. It looks like all the instructions are duplicated as well to operate on a pair of registers, too. I'm not exactly sure.
This was all pretty straightforward, and probably increased reliability, but it introduced new complexity into our build, install and upgrade process, because now I had to take into account the different flash layout in otherwise almost identical devices.
Since then I learned it's much easier to use eMMC. You don't need software block management and wear leveling, you just read the specs and let the manufacturer handle everything for you.
I wouldn't really expect controller-less NAND flash to ever meaningfully compete with what we have now. There is a lot more specialized hardware in a typical SoC than just a microprocessor and NAND flash chips
if ((i & 0x1) == 0) rp12 ^= tmppar;
Seems like it's ripe for something like:
rp12 ^= tmppar & ~(0 - (i & 0x1));
If my logic is functioning ;-) this eliminates the branch, but many modern CPUs running linux probably have a conditional mov which should be faster with the straightforward version.
Edit: Except RISC-V, there are no conditionals other than branch. Maybe this will help on that arch.