4 ms·

NAND Error-correction Code

93 points by signa11 3y ago

mschuster91 3y ago
> On a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor 5 (big endian mode, gcc 4.1.2, -O3) 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.
- mastax 3y ago
  https://godbolt.org/z/szMvnTT63 https://godbolt.org/z/szMvnTT63 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.
  - ack_complete 3y ago
    GCC is just vectorizing the code literally. It's doing multiple bytes in each loop iteration, but the vectorized code is still bit-testing the index to conditionally XOR into each accumulator. This is still much less efficient than taking advantage of the regular patterns as in the latter parts of the article. It also runs with a lot less lanes than it could, because it uses 32-bit lanes instead of 8-bit for some reason.
reqo 3y ago
No directly related, but I wish there was a 'standard' linux documentation that look more like Python docs.
- corbet 3y ago
  The kernel docs are generated with Sphinx, just like the Python docs are. Are you saying you wish we used the Python theme?
  - reqo 3y ago
    No, I was referring to the structure of Python docs. More specifically, I want there to be something like the 'Library Reference'. It starts from the basics and moves to more abstract/advanced topics. I guess the current docs are optimized for many different use cases, but as a beginner, it is very hard for me to gen an 'Overview' of linux from the official docs. There should better categorization IMO!
    - billfruit 3y ago
      There is the Linux Programming Environment book, which covers most of the library.
    - deleted 3y ago
      [deleted]
st_goliath 3y ago
A small remark for the casual readers: This is not about SSDs, this is for raw NAND flash access. 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. [1] https://en.wikipedia.org/wiki/BCH_code https://en.wikipedia.org/wiki/BCH_code
- anthk 3y ago
  This was used in the PocketCHIP for instance. They changed SLC to MLC and they error ratio got much smaller. AKA shit happened if you let the device shutdown by hardware due to low battery usage, you would loss lots of files.
- vlovich123 3y ago
  It’s interesting to me that Linux doesn’t have support for putting ext/xfs/… on top of MTD/UBI devices (i.e. making wear leveling more independent). I imagine many people installing on normal SSDs with built-in controllers use XFS. Not sure why we don’t see more raw NAND w/ a basic PCI-e controller with Linux doing all the wear leveling & whatnot given the problems vendors have flushing. You could even have an attached M3 that Linux could load companion software on for accelerating performance to make it even more on par with traditional SSDs
pedrocr 3y ago
Is there an NVMe manufacturer that sells their product as just naked flash? The first rule of hardware is that hardware providers don't know how to write software. It would be nice if we could get rid of the proprietary and buggy embedded operating systems running our storage as an opaque abstraction layer. Things like lying about flush that was recently on HN would stop being a problem.
- acquacow 3y ago
  Well, by definition, naked flash wouldn't be NVMe... so no.
  - FirmwareBurner 3y ago
    It would just be flash
- cesarb 3y ago
  While not going as far as you want, one movement in that direction is NVMe Zoned Namespaces (https://www.anandtech.com/show/15959/nvme-zoned-namespaces-explained https://www.anandtech.com/show/15959/nvme-zoned-namespaces-e...).
  - loeg 3y ago
    Flexible Data Placement is another interesting development in the NVMe space.
- BitBanging 3y ago
  The NAND flash manufacturers usually have no software involvement unless they are in the business of also selling SSD controller SoCs. They will typically sell FDKs/SDKs that are heaping piles of garbage written overseas for their SoCs that provide minimum functionality for interfacing with all of the components. 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
- 3y ago
o11c 3y ago
I expected discussion of __builtin_parity and cmov at least.
- thomasmg 3y ago
  Me too. Reading the article, there seems to be no attempt to replace the two remaining "if" statements, and so, avoid branches. It doesn't even need to be CMOV: possibly introducing tmppar1 and tmppar2 = tmppar & (an operation that is either 0 or -1). And then always rp12 ^= tmppar1; rp14 ^= tmppar2; -- it might not be faster, but that's what I would try at least.
- xxpor 3y ago
  This article references gcc 4.1, __builtin_parity is likely newer than that.
loeg 3y ago
(2008) (Note the reference to gcc 4.2.)
phkahler 3y ago
One more... Any benefit would be CPU specific: 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.
jdblair 3y ago
I encountered NAND ECC about 10 years ago. We wanted to increase the size of the NAND flash on our embedded device (a data logger and gateway used to monitor and control solar power systems). The larger NAND parts didn't have built in error correction. Enabling software error correction meant we had to move the kernel onto a small SPI-flash part. 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.

93 points by signa11 3y ago

> On a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor 5 (big endian mode, gcc 4.1.2, -O3) 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.

mastax 3y ago
https://godbolt.org/z/szMvnTT63 https://godbolt.org/z/szMvnTT63 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.
- ack_complete 3y ago
  GCC is just vectorizing the code literally. It's doing multiple bytes in each loop iteration, but the vectorized code is still bit-testing the index to conditionally XOR into each accumulator. This is still much less efficient than taking advantage of the regular patterns as in the latter parts of the article. It also runs with a lot less lanes than it could, because it uses 32-bit lanes instead of 8-bit for some reason.

reqo 3y ago

No directly related, but I wish there was a 'standard' linux documentation that look more like Python docs.

corbet 3y ago
The kernel docs are generated with Sphinx, just like the Python docs are. Are you saying you wish we used the Python theme?
- reqo 3y ago
  No, I was referring to the structure of Python docs. More specifically, I want there to be something like the 'Library Reference'. It starts from the basics and moves to more abstract/advanced topics. I guess the current docs are optimized for many different use cases, but as a beginner, it is very hard for me to gen an 'Overview' of linux from the official docs. There should better categorization IMO!
  - billfruit 3y ago
    There is the Linux Programming Environment book, which covers most of the library.
  - deleted 3y ago
    [deleted]

st_goliath 3y ago

A small remark for the casual readers: This is not about SSDs, this is for raw NAND flash access. 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. [1] https://en.wikipedia.org/wiki/BCH_code https://en.wikipedia.org/wiki/BCH_code

anthk 3y ago
This was used in the PocketCHIP for instance. They changed SLC to MLC and they error ratio got much smaller. AKA shit happened if you let the device shutdown by hardware due to low battery usage, you would loss lots of files.
vlovich123 3y ago
It’s interesting to me that Linux doesn’t have support for putting ext/xfs/… on top of MTD/UBI devices (i.e. making wear leveling more independent). I imagine many people installing on normal SSDs with built-in controllers use XFS. Not sure why we don’t see more raw NAND w/ a basic PCI-e controller with Linux doing all the wear leveling & whatnot given the problems vendors have flushing. You could even have an attached M3 that Linux could load companion software on for accelerating performance to make it even more on par with traditional SSDs

pedrocr 3y ago

Is there an NVMe manufacturer that sells their product as just naked flash? The first rule of hardware is that hardware providers don't know how to write software. It would be nice if we could get rid of the proprietary and buggy embedded operating systems running our storage as an opaque abstraction layer. Things like lying about flush that was recently on HN would stop being a problem.

acquacow 3y ago
Well, by definition, naked flash wouldn't be NVMe... so no.
- FirmwareBurner 3y ago
  It would just be flash
cesarb 3y ago
While not going as far as you want, one movement in that direction is NVMe Zoned Namespaces (https://www.anandtech.com/show/15959/nvme-zoned-namespaces-explained https://www.anandtech.com/show/15959/nvme-zoned-namespaces-e...).
- loeg 3y ago
  Flexible Data Placement is another interesting development in the NVMe space.
BitBanging 3y ago
The NAND flash manufacturers usually have no software involvement unless they are in the business of also selling SSD controller SoCs. They will typically sell FDKs/SDKs that are heaping piles of garbage written overseas for their SoCs that provide minimum functionality for interfacing with all of the components. 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
3y ago

o11c 3y ago

I expected discussion of __builtin_parity and cmov at least.

thomasmg 3y ago
Me too. Reading the article, there seems to be no attempt to replace the two remaining "if" statements, and so, avoid branches. It doesn't even need to be CMOV: possibly introducing tmppar1 and tmppar2 = tmppar & (an operation that is either 0 or -1). And then always rp12 ^= tmppar1; rp14 ^= tmppar2; -- it might not be faster, but that's what I would try at least.
xxpor 3y ago
This article references gcc 4.1, __builtin_parity is likely newer than that.

loeg 3y ago

(2008) (Note the reference to gcc 4.2.)

phkahler 3y ago

One more... Any benefit would be CPU specific: 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.

jdblair 3y ago

I encountered NAND ECC about 10 years ago. We wanted to increase the size of the NAND flash on our embedded device (a data logger and gateway used to monitor and control solar power systems). The larger NAND parts didn't have built in error correction. Enabling software error correction meant we had to move the kernel onto a small SPI-flash part. 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.