enum verify_status {corrupt = 0, okay = 1, healed = 2};

Calculates the single error correcting double error detecting (SECDED) Hamming Error Correcting Code for a blocksize block of bytes. For example, a secdec_ecc<8> would be the very common 72,64 Hamming code used in ECC RAM, or secdec_ecc<4096> would be for a 32784,32768 Hamming code.

Description

Did you know that some non-ECC RAM systems can see 1e-12 flips/bit/hour, which is 3.3 bits flipped in a 16Gb RAM system per 24 hours). See Schroeder, Pinheiro and Weber (2009) 'DRAM Errors in the Wild: A Large-Scale Field Study'.

After construction during which lookup tables are built, no state is modified and therefore this class is safe for static storage (indeed if C++ 14 is available, the constructor is constexpr). The maximum number of bits in a code is a good four billion, I did try limiting it to 65536 for performance but it wasn't worth it, and one might want > 8Kb blocks maybe. As with all SECDED ECC, undefined behaviour occurs when more than two bits of error are present or the ECC supplied is incorrect. You should combine this SECDED with a robust hash which can tell you definitively if a buffer is error free or not rather than relying on this to correctly do so.

The main intended use case for this routine is calculating the ECC on data being written to disc, and hence that is where performance has been maximised. It is not expected that this routine will be frequently called on data being read from disc i.e. only when its hash doesn't match its contents which should be very rare, and then a single bit heal using this routine is attempted before trying again with the hash. Care was taken that really enormous SECDEDs are fast, in fact tuning was mostly done for the 32784,32768 code which can heal one bad bit per 4Kb page as the main thing we have in mind is achieving reliable filing system code on computers without ECC RAM and in which sustained large quantities of random disc i/o produce a worrying number of flipped bits in a 24 hour period (anywhere between 0 and 3 on my hardware here, average is about 0.8).

Performance of the fixed block size routine where you supply whole chunks of blocksize is therefore particularly excellent as I spent a lot of time tuning it for Ivy Bridge and later out of order architectures: an amazing 22 cycles per byte for the 32784,32768 code, which is a testament to modern out of order CPUs (remember SECDED inherently must work a bit at a time, so that's just 2.75 amortised CPU cycles per bit which includes a table load, a bit test, and a conditional XOR) i.e. it's pushing about 1.5 ops per clock cycle. On my 3.9Ghz i7-3770K here, I see about 170Mb/sec per CPU core.

The variable length routine is necessarily much slower as it must work in single bytes, and achieves 72 cycles per byte, or 9 cycles per bit (64Mb/sec per CPU core).

Synopsis

template<size_t blocksize>
class utils::secded_ecc
{
  // ...
};

Template parameter(s)

Constructor(s)

secded_ecc()

Member Function(s)

constexpr result_type result_bits_valid()

result_type operator()(result_type ecc, const char * buffer)

result_type operator()(const char * buffer)

result_type operator()(result_type ecc, const char * buffer, size_t length)

result_type operator()(const char * buffer, size_t length)

result_type find_bad_bit(result_type good_ecc, result_type bad_ecc)

verify_status verify(char * buffer, result_type good_ecc)

Header

#include <boost/afio/v2/afio.hpp>

Complexity

O(N) where N is the blocksize

Exception Model

Throws constexpr exceptions in constructor only, otherwise entirely noexcept.