From 231c0fe688b855130c474dc2f89d83632ecd3e3c Mon Sep 17 00:00:00 2001 From: Patrick Williams Date: Fri, 3 May 2013 16:52:54 -0500 Subject: PNOR ECC algorithms RTC: 70686 Change-Id: I977bbabf99d57cdf28ef2c0a79d1f10f6b1c201c Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/4364 Tested-by: Jenkins Server Reviewed-by: ADAM R. MUHLE Reviewed-by: Daniel M. Crowell Reviewed-by: A. Patrick Williams III --- src/include/usr/pnor/ecc.H | 84 ++++++++++++++++ src/usr/pnor/ecc.C | 237 ++++++++++++++++++++++++++++++++++++++++++++ src/usr/pnor/makefile | 30 +++--- src/usr/pnor/test/ecctest.H | 144 +++++++++++++++++++++++++++ 4 files changed, 480 insertions(+), 15 deletions(-) create mode 100644 src/include/usr/pnor/ecc.H create mode 100644 src/usr/pnor/ecc.C create mode 100644 src/usr/pnor/test/ecctest.H diff --git a/src/include/usr/pnor/ecc.H b/src/include/usr/pnor/ecc.H new file mode 100644 index 000000000..079339aa2 --- /dev/null +++ b/src/include/usr/pnor/ecc.H @@ -0,0 +1,84 @@ +/* IBM_PROLOG_BEGIN_TAG */ +/* This is an automatically generated prolog. */ +/* */ +/* $Source: src/usr/pnor/ecc.H $ */ +/* */ +/* IBM CONFIDENTIAL */ +/* */ +/* COPYRIGHT International Business Machines Corp. 2013 */ +/* */ +/* p1 */ +/* */ +/* Object Code Only (OCO) source materials */ +/* Licensed Internal Code Source Materials */ +/* IBM HostBoot Licensed Internal Code */ +/* */ +/* The source code for this program is not published or otherwise */ +/* divested of its trade secrets, irrespective of what has been */ +/* deposited with the U.S. Copyright Office. */ +/* */ +/* Origin: 30 */ +/* */ +/* IBM_PROLOG_END_TAG */ +#ifndef __PNOR_ECC_H +#define __PNOR_ECC_H + +#include + +/** @file ecc.H + * @brief Interfaces for the P8 8-byte ECC algorithm. + */ + +namespace PNOR +{ +namespace ECC +{ + /** Status for the ECC removal function. */ + enum eccStatus + { + CLEAN, //< No ECC Error was detected. + CORRECTED, //< ECC error detected and corrected. + UNCORRECTABLE //< ECC error detected and uncorrectable. + }; + + /** Bit field identifiers for syndrome calculations. */ + enum eccBitfields + { + GD = 0xff, //< Good, ECC matches. + UE = 0xfe, //< Uncorrectable. + E0 = 71, //< Error in ECC bit 0 + E1 = 70, //< Error in ECC bit 1 + E2 = 69, //< Error in ECC bit 2 + E3 = 68, //< Error in ECC bit 3 + E4 = 67, //< Error in ECC bit 4 + E5 = 66, //< Error in ECC bit 5 + E6 = 65, //< Error in ECC bit 6 + E7 = 64 //< Error in ECC bit 7 + }; + + /** Inject ECC into a data stream. + * + * @param[in] i_src - Source data to create ECC on. + * @param[in] i_srcSz - Size in bytes of source data. + * @param[out] o_dst - Destination buffer of data+ECC. + * + * @note i_srcSz must be a multiple of 8 bytes. + */ + void injectECC(const uint8_t* i_src, size_t i_srcSz, + uint8_t* o_dst); + + /** Remove ECC from a data stream. + * + * @param[in,out] io_src - Source data+ECC stream. + * @param[out] o_dst - Destination buffer for data only. + * @param[in] i_dstSz - Size in bytes of destination ((srcSz / 9) * 8). + * + * @note i_dstSz must be a multiple of 8 bytes. + */ + eccStatus removeECC(uint8_t* io_src, + uint8_t* o_dst, size_t i_dstSz); + +} +} + +#endif diff --git a/src/usr/pnor/ecc.C b/src/usr/pnor/ecc.C new file mode 100644 index 000000000..275a5d4fe --- /dev/null +++ b/src/usr/pnor/ecc.C @@ -0,0 +1,237 @@ +/* IBM_PROLOG_BEGIN_TAG */ +/* This is an automatically generated prolog. */ +/* */ +/* $Source: src/usr/pnor/ecc.C $ */ +/* */ +/* IBM CONFIDENTIAL */ +/* */ +/* COPYRIGHT International Business Machines Corp. 2013 */ +/* */ +/* p1 */ +/* */ +/* Object Code Only (OCO) source materials */ +/* Licensed Internal Code Source Materials */ +/* IBM HostBoot Licensed Internal Code */ +/* */ +/* The source code for this program is not published or otherwise */ +/* divested of its trade secrets, irrespective of what has been */ +/* deposited with the U.S. Copyright Office. */ +/* */ +/* Origin: 30 */ +/* */ +/* IBM_PROLOG_END_TAG */ +#include +#include +#include + +#include + +namespace PNOR +{ +namespace ECC +{ + /** Matrix used for ECC calculation. + * + * Each row of this is the set of data word bits that are used for + * the calculation of the corresponding ECC bit. The parity of the + * bitset is the value of the ECC bit. + * + * ie. ECC[n] = eccMatrix[n] & data + * + * Note: To make the math easier (and less shifts in resulting code), + * row0 = ECC7. HW numbering is MSB, order here is LSB. + * + * These values come from the HW design of the ECC algorithm. + */ + static uint64_t eccMatrix[] = { + //0000000000000000111010000100001000111100000011111001100111111111 + 0x0000e8423c0f99ff, + //0000000011101000010000100011110000001111100110011111111100000000 + 0x00e8423c0f99ff00, + //1110100001000010001111000000111110011001111111110000000000000000 + 0xe8423c0f99ff0000, + //0100001000111100000011111001100111111111000000000000000011101000 + 0x423c0f99ff0000e8, + //0011110000001111100110011111111100000000000000001110100001000010 + 0x3c0f99ff0000e842, + //0000111110011001111111110000000000000000111010000100001000111100 + 0x0f99ff0000e8423c, + //1001100111111111000000000000000011101000010000100011110000001111 + 0x99ff0000e8423c0f, + //1111111100000000000000001110100001000010001111000000111110011001 + 0xff0000e8423c0f99 + }; + + /** Syndrome calculation matrix. + * + * Maps syndrome to flipped bit. + * + * To perform ECC correction, this matrix is a look-up of the bit + * that is bad based on the binary difference of the good and bad + * ECC. This difference is called the "syndrome". + * + * When a particular bit is on in the data, it cause a column from + * eccMatrix being XOR'd into the ECC field. This column is the + * "effect" of each bit. If a bit is flipped in the data then its + * "effect" is missing from the ECC. You can calculate ECC on unknown + * quality data and compare the ECC field between the calculated + * value and the stored value. If the difference is zero, then the + * data is clean. If the difference is non-zero, you look up the + * difference in the syndrome table to identify the "effect" that + * is missing, which is the bit that is flipped. + * + * Notice that ECC bit flips are recorded by a single "effect" + * bit (ie. 0x1, 0x2, 0x4, 0x8 ...) and double bit flips are identified + * by the UE status in the table. + * + * Bits are in MSB order. + */ + static uint8_t syndromeMatrix[] = { + GD, E7, E6, UE, E5, UE, UE, 47, E4, UE, UE, 37, UE, 35, 39, UE, + E3, UE, UE, 48, UE, 30, 29, UE, UE, 57, 27, UE, 31, UE, UE, UE, + E2, UE, UE, 17, UE, 18, 40, UE, UE, 58, 22, UE, 21, UE, UE, UE, + UE, 16, 49, UE, 19, UE, UE, UE, 23, UE, UE, UE, UE, 20, UE, UE, + E1, UE, UE, 51, UE, 46, 9, UE, UE, 34, 10, UE, 32, UE, UE, 36, + UE, 62, 50, UE, 14, UE, UE, UE, 13, UE, UE, UE, UE, UE, UE, UE, + UE, 61, 8, UE, 41, UE, UE, UE, 11, UE, UE, UE, UE, UE, UE, UE, + 15, UE, UE, UE, UE, UE, UE, UE, UE, UE, 12, UE, UE, UE, UE, UE, + E0, UE, UE, 55, UE, 45, 43, UE, UE, 56, 38, UE, 1, UE, UE, UE, + UE, 25, 26, UE, 2, UE, UE, UE, 24, UE, UE, UE, UE, UE, 28, UE, + UE, 59, 54, UE, 42, UE, UE, 44, 6, UE, UE, UE, UE, UE, UE, UE, + 5, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, + UE, 63, 53, UE, 0, UE, UE, UE, 33, UE, UE, UE, UE, UE, UE, UE, + 3, UE, UE, 52, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, + 7, UE, UE, UE, UE, UE, UE, UE, UE, 60, UE, UE, UE, UE, UE, UE, + UE, UE, UE, UE, 4, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, + }; + + /** Create the ECC field corresponding to a 8-byte data field + * + * @param[in] i_data - The 8 byte data to generate ECC for. + * @return The 1 byte ECC corresponding to the data. + */ + uint8_t generateECC(uint64_t i_data) + { + uint8_t result = 0; + + for (int i = 0; i < 8; i++) + { + result |= __builtin_parityl(eccMatrix[i] & i_data) << i; + } + + return result; + } + + /** Verify the data and ECC match or indicate how they are wrong. + * + * @param[in] i_data - The data to check ECC on. + * @param[in] i_ecc - The [supposed] ECC for the data. + * + * @return eccBitfield or 0-64. + * + * @retval GD - Indicates the data is good (matches ECC). + * @retval UE - Indicates the data is uncorrectable. + * @retval all others - Indication of which bit is incorrect. + */ + uint8_t verifyECC(uint64_t i_data, uint8_t i_ecc) + { + return syndromeMatrix[generateECC(i_data) ^ i_ecc]; + } + + /** Correct the data and/or ECC. + * + * @param[in,out] io_data - Data to check / correct. + * @param[in,out] io_ecc - ECC to check / correct. + * + * @return eccBitfield or 0-64. + * + * @retval GD - Data is good. + * @retval UE - Data is uncorrectable. + * @retval all others - which bit was corrected. + */ + uint8_t correctECC(uint64_t& io_data, uint8_t& io_ecc) + { + uint8_t badBit = verifyECC(io_data, io_ecc); + + if ((badBit != GD) && (badBit != UE)) // Good is done, UE is hopeless. + { + // Determine if the ECC or data part is bad, do bit flip. + if (badBit >= E7) + { + io_ecc ^= (1 << (badBit - E7)); + } + else + { + io_data ^= (1ul << (63 - badBit)); + } + } + return badBit; + } + + void injectECC(const uint8_t* i_src, size_t i_srcSz, + uint8_t* o_dst) + { + assert(0 == (i_srcSz % sizeof(uint64_t))); + + for(size_t i = 0, o = 0; + i < i_srcSz; + i += sizeof(uint64_t), o += sizeof(uint64_t) + sizeof(uint8_t)) + { + // Read data word, copy to destination. + uint64_t data = *reinterpret_cast(&i_src[i]); + *reinterpret_cast(&o_dst[o]) = data; + data = be64toh(data); + + // Calculate ECC, copy to destination. + uint8_t ecc = generateECC(data); + o_dst[o + sizeof(uint64_t)] = ecc; + } + } + + eccStatus removeECC(uint8_t* io_src, + uint8_t* o_dst, size_t i_dstSz) + { + assert(0 == (i_dstSz % sizeof(uint64_t))); + + eccStatus rc = CLEAN; + + for(size_t i = 0, o = 0; + o < i_dstSz; + i += sizeof(uint64_t) + sizeof(uint8_t), o += sizeof(uint64_t)) + { + // Read data and ECC parts. + uint64_t data = *reinterpret_cast(&io_src[i]); + data = be64toh(data); + uint8_t ecc = io_src[i + sizeof(uint64_t)]; + + // Calculate failing bit and fix data. + uint8_t badBit = correctECC(data, ecc); + + // Return data to big endian. + data = htobe64(data); + + // Perform correction and status update. + if (badBit == UE) + { + rc = UNCORRECTABLE; + } + else if (badBit != GD) + { + if (rc != UNCORRECTABLE) + { + rc = CORRECTED; + } + *reinterpret_cast(&io_src[i]) = data; + io_src[i + sizeof(uint64_t)] = ecc; + } + + // Copy fixed data to destination buffer. + *reinterpret_cast(&o_dst[o]) = data; + } + + return rc; + } + +} +} + diff --git a/src/usr/pnor/makefile b/src/usr/pnor/makefile index 9a16dae5d..445c61739 100644 --- a/src/usr/pnor/makefile +++ b/src/usr/pnor/makefile @@ -1,29 +1,29 @@ -# IBM_PROLOG_BEGIN_TAG -# This is an automatically generated prolog. +# IBM_PROLOG_BEGIN_TAG +# This is an automatically generated prolog. # -# $Source: src/usr/pnor/makefile $ +# $Source: src/usr/pnor/makefile $ # -# IBM CONFIDENTIAL +# IBM CONFIDENTIAL # -# COPYRIGHT International Business Machines Corp. 2011 +# COPYRIGHT International Business Machines Corp. 2011,2013 # -# p1 +# p1 # -# Object Code Only (OCO) source materials -# Licensed Internal Code Source Materials -# IBM HostBoot Licensed Internal Code +# Object Code Only (OCO) source materials +# Licensed Internal Code Source Materials +# IBM HostBoot Licensed Internal Code # -# The source code for this program is not published or other- -# wise divested of its trade secrets, irrespective of what has -# been deposited with the U.S. Copyright Office. +# The source code for this program is not published or otherwise +# divested of its trade secrets, irrespective of what has been +# deposited with the U.S. Copyright Office. # -# Origin: 30 +# Origin: 30 # -# IBM_PROLOG_END +# IBM_PROLOG_END_TAG ROOTPATH = ../../.. MODULE = pnor -OBJS = pnorrp.o pnordd.o +OBJS = pnorrp.o pnordd.o ecc.o SUBDIRS = test.d diff --git a/src/usr/pnor/test/ecctest.H b/src/usr/pnor/test/ecctest.H new file mode 100644 index 000000000..5a559b528 --- /dev/null +++ b/src/usr/pnor/test/ecctest.H @@ -0,0 +1,144 @@ +/* IBM_PROLOG_BEGIN_TAG */ +/* This is an automatically generated prolog. */ +/* */ +/* $Source: src/usr/pnor/test/ecctest.H $ */ +/* */ +/* IBM CONFIDENTIAL */ +/* */ +/* COPYRIGHT International Business Machines Corp. 2013 */ +/* */ +/* p1 */ +/* */ +/* Object Code Only (OCO) source materials */ +/* Licensed Internal Code Source Materials */ +/* IBM HostBoot Licensed Internal Code */ +/* */ +/* The source code for this program is not published or otherwise */ +/* divested of its trade secrets, irrespective of what has been */ +/* deposited with the U.S. Copyright Office. */ +/* */ +/* Origin: 30 */ +/* */ +/* IBM_PROLOG_END_TAG */ +#include +#include +#include + +// Forward declarations, see ecc.C +namespace PNOR +{ + namespace ECC + { + uint8_t generateECC(uint64_t i_data); + uint8_t verifyECC(uint64_t i_data, uint8_t i_ecc); + uint8_t correctECC(uint64_t& io_data, uint8_t& io_ecc); + } +} + +class ECCTest : public CxxTest::TestSuite +{ + public: + + void testConsistency() + { + uint64_t data = 0x8d8aeff460bd2fc8; // <-- random data. + uint8_t ecc = PNOR::ECC::generateECC(data); + + uint8_t result = PNOR::ECC::verifyECC(data, ecc); + if (PNOR::ECC::GD != result) + { + TS_FAIL("ECCTest::testConsistency: Inconsistent results: " + "0x%16x 0x%2x: %d", + data, ecc, result); + } + } + + void testCorrection() + { + uint64_t data = 0x8d8aeff460bd2fc8; // <-- random data. + uint8_t ecc = PNOR::ECC::generateECC(data); + + for (int i = 0; i < 64; i++) + { + uint64_t bad_data = data ^ (1ul << (63 - i)); + uint8_t result = PNOR::ECC::verifyECC(bad_data, ecc); + + if (i != result) + { + TS_FAIL("ECCTest::testCorrection: Incorrect correct data: " + "0x%16x 0x%2x: %d %d", + data, ecc, i, result); + } + } + + for (int i = 0; i < 8; i++) + { + uint8_t bad_ecc = ecc ^ (1 << i); + uint8_t result = PNOR::ECC::verifyECC(data, bad_ecc); + + if (i != (result - PNOR::ECC::E7)) + { + TS_FAIL("ECCTest::testCorrection: Incorrect correct ecc: " + "0x%16x 0x%2x: %d %d", + data, ecc, i, result); + } + } + } + + void testUncorrectable() + { + uint64_t data = 0x8d8aeff460bd2fc8; // <-- random data. + uint8_t ecc = PNOR::ECC::generateECC(data); + + for (int i = 0; i < 64; i++) + { + for (int j = 0; j < 64; j++) + { + if (i == j) + { + continue; + } + + uint64_t bad_data = data ^ (1ul << i) ^ (1ul << j); + uint8_t result = PNOR::ECC::verifyECC(bad_data, ecc); + + if (PNOR::ECC::UE != result) + { + TS_FAIL("ECCTest::testUncorrectable: Non-UE: " + "0x%16x 0x%2x : %d %d", + data, ecc, i, j); + } + } + } + } + + void testInject() + { + uint64_t data = 0x8d8aeff460bd2fc8; // <-- random data. + size_t s = sizeof(data); + + // Allocate buffers. + uint8_t* in_data = new uint8_t[s]; + memcpy(in_data, &data, s); + uint8_t* out_data = new uint8_t[(s * 9) / 8]; + + // Inject ECC. + PNOR::ECC::injectECC(in_data, s, out_data); + + // Clear source. + memset(in_data, '\0', s); + + // Remove ECC. + PNOR::ECC::removeECC(out_data, in_data, s); + + // Ensure data matches. + if (0 != memcmp(in_data, &data, s)) + { + TS_FAIL("ECCTest::testInject: Data mismatch: %16x %16x\n", + data, *reinterpret_cast(in_data)); + } + + delete[] in_data; + delete[] out_data; + } +}; -- cgit v1.2.1