Re: [IDEA RFC] Forward error correction (FEC) / Error correction code (ECC) for BTRFS

[Zhang Boyang <zhangboyang.id@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 92 bytes --]

Hi,

Here are runnable example programs of first two approaches.

Best Regards,
Zhang Boyang

[-- Attachment #2: 1.c --]
[-- Type: text/x-csrc, Size: 2174 bytes --]

// gcc -O2 -Wall 1.c -lssl -lcrypto && ./a.out

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <openssl/evp.h>

void digest(void *out, size_t out_len, void *in, size_t in_len)
{
    unsigned char md_value[EVP_MAX_MD_SIZE];
    EVP_MD_CTX *mdctx;
    const EVP_MD *md = EVP_blake2b512();
    mdctx = EVP_MD_CTX_new();
    EVP_DigestInit_ex(mdctx, md, NULL);
    EVP_DigestUpdate(mdctx, in, in_len);
    EVP_DigestFinal_ex(mdctx, md_value, NULL);
    EVP_MD_CTX_free(mdctx);
    memcpy(out, md_value, out_len);
}

void hexdump(void *p, size_t n)
{
    unsigned char *uc = p;
    for (size_t i = 0; i < n; i++)
        printf("%02x", uc[i]);
}

#define FAIL 0
#define SUCCESS 1

///////////////////////////////////////////////////////////////////////////

#define N 4096

void checksum(void *out, void *in)
{
    digest(out, 32, in, N);
}

char data[N];  // data on disk, assume only one byte in it is corrupted
char csum[32]; // checksum in ctree
int repair()
{
    for (int i = 0; i < N; i++) // brute-force error location
      for (int j = 0; j < 0x100; j++) { // brute-force byte value at location i
        char buf[N];
        memcpy(buf, data, N);
        buf[i] = j;
        char new_csum[32];
        checksum(new_csum, buf);
        if (memcmp(csum, new_csum, 32) == 0) {
          memcpy(data, buf, N);
          return SUCCESS; // data in buf[] are good data, repair succeeded
        }
      }
    return FAIL; // search space exhausted, failed to repair
}

int main()
{
    // get random data
    FILE *fp = fopen("/dev/urandom", "r");
    assert(fp);
    fread(data, 1, N, fp);
    fclose(fp);

    // calc checksum of good data
    checksum(csum, data);
    printf("good\t"); hexdump(csum, 32); printf("\n");

    // corrupt some data
    data[N-1] = 200;
    //data[101] = 200;

    // calc checksum of bad data
    char bad_csum[32];
    checksum(bad_csum, data);
    printf("bad\t"); hexdump(bad_csum, 32); printf("\n");

    // try repair
    int result = repair();
    printf("%s\t", result ? "SUCCESS" : "FAIL");
    char repair_csum[32];
    checksum(repair_csum, data);
    hexdump(repair_csum, 32); printf("\n");

    return 0;
}

[-- Attachment #3: 2.c --]
[-- Type: text/x-csrc, Size: 2593 bytes --]

// gcc -O2 -Wall 2.c -lssl -lcrypto && ./a.out

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <openssl/evp.h>

void digest(void *out, size_t out_len, void *in, size_t in_len)
{
    unsigned char md_value[EVP_MAX_MD_SIZE];
    EVP_MD_CTX *mdctx;
    const EVP_MD *md = EVP_blake2b512();
    mdctx = EVP_MD_CTX_new();
    EVP_DigestInit_ex(mdctx, md, NULL);
    EVP_DigestUpdate(mdctx, in, in_len);
    EVP_DigestFinal_ex(mdctx, md_value, NULL);
    EVP_MD_CTX_free(mdctx);
    memcpy(out, md_value, out_len);
}

void hexdump(void *p, size_t n)
{
    unsigned char *uc = p;
    for (size_t i = 0; i < n; i++)
        printf("%02x", uc[i]);
}

#define FAIL 0
#define SUCCESS 1

///////////////////////////////////////////////////////////////////////////

#define N 4096
#define T 8

void checksum(void *out, void *in)
{
    char *xv = (char *)out + 32 - T;
    memset(xv, 0, T);
    for (int i = 0; i < N; i++)
      xv[i % T] ^= ((char *)in)[i];
    digest(out, 32 - T, in, N);
}

char data[N];  // data on disk, assume at most T consecutive bad bytes
char csum[32]; // checksum in ctree, 32-T bytes hash and T bytes xv[]
int repair()
{
    char *xv = csum + 32 - T;
    for (int i = 0; i <= N - T; i++) { // brute-force the begin of error location
      char buf[N];
      memcpy(buf, data, N);

      // calculate values in error location using xv[]
      char repair[T];
      memcpy(repair, xv, T);
      for (int j = 0; j < N; j++)
        if (j < i || j >= i + T)
          repair[j % T] ^= buf[j];
      for (int j = 0; j < T; j++)
        buf[i + j] = repair[(i + j) % T];

      char new_csum[32];
      checksum(new_csum, buf);
      if (memcmp(csum, new_csum, 32 - T) == 0) {
        memcpy(data, buf, N);
        return SUCCESS; // data in buf[] are good data, repair succeeded
      }
    }
    return FAIL; // search space exhausted, failed to repair
}

int main()
{
    // get random data
    FILE *fp = fopen("/dev/urandom", "r");
    assert(fp);
    fread(data, 1, N, fp);
    fclose(fp);

    // calc checksum of good data
    checksum(csum, data);
    printf("good\t"); hexdump(csum, 32); printf("\n");

    // corrupt some data
    data[N-1] = 200;
    data[N-8] = 200;
    //data[N-9] = 200;

    // calc checksum of bad data
    char bad_csum[32];
    checksum(bad_csum, data);
    printf("bad\t"); hexdump(bad_csum, 32); printf("\n");

    // try repair
    int result = repair();
    printf("%s\t", result ? "SUCCESS" : "FAIL");
    char repair_csum[32];
    checksum(repair_csum, data);
    hexdump(repair_csum, 32); printf("\n");

    return 0;
}