Libsecded

-rw-r--r-- 3964 libsecded-20220828/README raw

---

Data stored in DRAM sometimes flips bits. A study of Google servers
found that each gigabyte of DRAM flips a bit every few hours on average:
https://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf

Servers typically protect against DRAM errors using "SECDED ECC DRAM",
which is slightly more expensive than conventional DRAM. "SECDED" means
"single error correction, double error detection". Each 64-bit chunk of
data is stored in 72 physical bits; the extra 8 bits are used for
checksums that allow any single bit flip to be automatically corrected
and any double bit flip to be detected. Operating systems report
"correctable errors" ("CE") and "uncorrectable errors" ("UE") to warn
system administrators to replace failing DRAM.

However, typical desktops, laptops, and smartphones use conventional
DRAM, with no protection against bit flips. Usually a bit flip doesn't
matter (would you notice a pixel occasionally changing in a movie?), but
sometimes it does matter.

libsecded is a software library aimed at programmers who would like to
reduce the risk of data corruption. The library stores an array as a
slightly longer array, using extra bits to automatically correct single
errors and detect double errors. The API is straightforward (with
lengths represented as long long, not size_t):

   secded_encode(x,&xlen): encode bytes x[0...xlen-1] as bytes
   x[0...newxlen-1], changing xlen to newxlen, which is at most xlen+64

   secded_decode(x,&xlen): change x[...] and xlen back to what they
   were, while correcting any single error

Notes follow on optional aspects of the API.

There's a secded_clean(x,xlen) that you can use to correct errors in
encoded data while leaving the data in encoded form. This is essentially
the same as secded_decode(x,&xlen) followed by secded_encode(x,&xlen),
but simpler and faster. (Periodically sweeping through encoded data to
correct errors is typically called "scrubbing" for SECDED ECC DRAM.)

Both secded_decode() and secded_clean() return an unsigned int, namely 0
for no errors, 1 through 255 for correctable errors, 256 through 65535
for uncorrectable errors. This lets you measure how often problems occur
and decide what action to take.

Some values of xlen are never produced by secded_encode(). For example,
xlen=120 turns into newxlen=128, xlen=121 turns into newxlen=130, and
nothing turns into newxlen=129. In case you're worried about what
happens with invalid lengths such as 129:

   * Invalid lengths are accepted by decode(), essentially as if they
     were truncated down to the next valid length, so they won't crash
     your program.

   * If you're worried about data from an untrustworthy source, you
     shouldn't think that rejecting invalid lengths is a solution. The
     source will still be able to produce arbitrary results from decode().

   * If you're trying to recognize repeated events, you shouldn't be
     merely checking for repeated _encodings_ of those events. Even
     outside the error-correction context, it's usually wrong to assume
     that only one string can decode to a particular piece of data.

   * If for some reason you want to recognize invalid lengths, one way is
     to see that decode() followed by encode() _doesn't_ produce the
     original length. You can pass a 0 pointer to decode() and encode()
     to just do length computations without touching the array. You can
     also more directly recognize the invalid lengths (1, 2, 3, 5, 9,
     17, 33, etc.) as nonzero xlen such that (xlen-1)&(xlen-2) == 0.

The software is designed to work for array lengths as large as an
exabyte (2^60 bytes). However, obviously bugs for large array sizes
could have slipped past tests for smaller array sizes, and being able to
correct just one error is insufficient for large arrays. Large arrays
should be split into smaller arrays with separate error correction. For
even higher reliability, SECDED should be replaced with multiple-error
correction.

from Hacker News https://ift.tt/Rv3TGFL