ErasureCode: example implementation : K=2 M=1

An erasure code implementation designed for tests. Although it is fully
functional and could be used on actual data, it is mainly provided for
testing purposes. It splits data in two, computes an XOR parity and
can sustain the loss of one chunk.

The constructor will usleep(3) for parameters["usleep"] microseconds
so that the caller can create race conditions.

http://tracker.ceph.com/issues/5878 refs #5878

Signed-off-by: Loic Dachary <loic@dachary.org>

3 files changed, 267 insertions, 0 deletions

diff --git a/src/test/Makefile.am b/src/test/Makefile.am
index abb14fbabd4..da42ea01468 100644
--- a/src/test/Makefile.am
+++ b/src/test/Makefile.am
@@ -313,6 +313,12 @@ unittest_ceph_argparse_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL)
 unittest_ceph_argparse_CXXFLAGS = $(UNITTEST_CXXFLAGS)
 check_PROGRAMS += unittest_ceph_argparse
 
+unittest_erasure_code_example_SOURCES = test/osd/TestErasureCodeExample.cc 
+noinst_HEADERS += test/osd/ErasureCodeExample.h
+unittest_erasure_code_example_CXXFLAGS = ${AM_CXXFLAGS} ${UNITTEST_CXXFLAGS}
+unittest_erasure_code_example_LDADD = libosd.a libcommon.la $(UNITTEST_LDADD) $(CEPH_GLOBAL)
+check_PROGRAMS += unittest_erasure_code_example
+
 unittest_osd_types_SOURCES = test/test_osd_types.cc
 unittest_osd_types_CXXFLAGS = $(UNITTEST_CXXFLAGS)
 unittest_osd_types_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) 
diff --git a/src/test/osd/ErasureCodeExample.h b/src/test/osd/ErasureCodeExample.h
new file mode 100644
index 00000000000..896e614c6b5
--- /dev/null
+++ b/src/test/osd/ErasureCodeExample.h
@@ -0,0 +1,115 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph - scalable distributed file system
+ *
+ * Copyright (C) 2013 Cloudwatt <libre.licensing@cloudwatt.com>
+ *
+ * Author: Loic Dachary <loic@dachary.org>
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2.1 of the License, or (at your option) any later version.
+ * 
+ */
+
+#ifndef CEPH_ERASURE_CODE_EXAMPLE_H
+#define CEPH_ERASURE_CODE_EXAMPLE_H
+
+#include <unistd.h>
+#include <errno.h>
+#include <sstream>
+#include "osd/ErasureCodeInterface.h"
+
+#define DATA_CHUNKS 2u
+#define CODING_CHUNKS 1u
+
+class ErasureCodeExample : public ErasureCodeInterface {
+public:
+  useconds_t delay;
+  ErasureCodeExample(const map<std::string,std::string> &parameters) :
+    delay(0)
+  {
+    if (parameters.find("usleep") != parameters.end()) {
+      std::istringstream ss(parameters.find("usleep")->second);
+      ss >> delay;
+      usleep(delay);
+    }
+  }
+
+  virtual ~ErasureCodeExample() {}
+  
+  virtual int minimum_to_decode(const set<int> &want_to_read,
+                                const set<int> &available_chunks,
+                                set<int> *minimum) {
+    if (available_chunks.size() < DATA_CHUNKS)
+      return -EIO;
+    set<int>::iterator i;
+    unsigned j;
+    for (i = available_chunks.begin(), j = 0; j < DATA_CHUNKS; i++, j++)
+      minimum->insert(*i);
+    return 0;
+  }
+
+  virtual int minimum_to_decode_with_cost(const set<int> &want_to_read,
+                                          const map<int, int> &available,
+                                          set<int> *minimum) {
+    set <int> available_chunks;
+    for (map<int, int>::const_iterator i = available.begin();
+	 i != available.end();
+	 i++)
+      available_chunks.insert(i->first);
+    return minimum_to_decode(want_to_read, available_chunks, minimum);
+  }
+
+  virtual int encode(const set<int> &want_to_encode,
+                     const bufferlist &in,
+                     map<int, bufferlist> *encoded) {
+    unsigned chunk_length = ( in.length() / DATA_CHUNKS ) + 1;
+    unsigned length = chunk_length * ( DATA_CHUNKS + CODING_CHUNKS );
+    bufferlist out(in);
+    bufferptr pad(length - in.length());
+    pad.zero(0, DATA_CHUNKS);
+    out.push_back(pad);
+    char *p = out.c_str();
+    for (unsigned i = 0; i < chunk_length * DATA_CHUNKS; i++)
+      p[i + 2 * chunk_length] =
+        p[i + 0 * chunk_length] ^ p[i + 1 * chunk_length];
+    const bufferptr ptr = out.buffers().front();
+    for (set<int>::iterator j = want_to_encode.begin();
+         j != want_to_encode.end();
+         j++) {
+      bufferptr chunk(ptr, (*j) * chunk_length, chunk_length);
+      (*encoded)[*j].push_front(chunk);
+    }
+    return 0;
+  }
+
+  virtual int decode(const set<int> &want_to_read,
+                     const map<int, bufferlist> &chunks,
+                     map<int, bufferlist> *decoded) {
+    
+    unsigned chunk_length = (*chunks.begin()).second.length();
+    for (set<int>::iterator i = want_to_read.begin();
+         i != want_to_read.end();
+         i++) {
+      if (chunks.find(*i) != chunks.end())
+        (*decoded)[*i] = chunks.find(*i)->second;
+      else {
+        bufferptr chunk(chunk_length);
+        map<int, bufferlist>::const_iterator k = chunks.begin();
+        const char *a = k->second.buffers().front().c_str();
+        k++;
+        const char *b = k->second.buffers().front().c_str();
+        for (unsigned j = 0; j < chunk_length; j++) {
+          chunk[j] = a[j] ^ b[j];
+        }
+        (*decoded)[*i].push_front(chunk);
+      }
+    }
+    return 0;
+  }
+};
+
+#endif
diff --git a/src/test/osd/TestErasureCodeExample.cc b/src/test/osd/TestErasureCodeExample.cc
new file mode 100644
index 00000000000..66f521d7863
--- /dev/null
+++ b/src/test/osd/TestErasureCodeExample.cc
@@ -0,0 +1,146 @@
+// -*- mode:C; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph - scalable distributed file system
+ *
+ * Copyright (C) 2013 Cloudwatt <libre.licensing@cloudwatt.com>
+ *
+ * Author: Loic Dachary <loic@dachary.org>
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2.1 of the License, or (at your option) any later version.
+ * 
+ */
+
+#include "global/global_init.h"
+#include "ErasureCodeExample.h"
+#include "common/ceph_argparse.h"
+#include "global/global_context.h"
+#include "gtest/gtest.h"
+
+TEST(ErasureCodeExample, constructor)
+{
+  map<std::string,std::string> parameters;
+  {
+    ErasureCodeExample example(parameters);
+    EXPECT_EQ(0u, example.delay);
+  }
+  parameters["usleep"] = "10";
+  {
+    ErasureCodeExample example(parameters);
+    EXPECT_EQ(10u, example.delay);
+  }
+}
+
+TEST(ErasureCodeExample, minimum_to_decode)
+{
+  map<std::string,std::string> parameters;
+  ErasureCodeExample example(parameters);
+  set<int> available_chunks;
+  set<int> want_to_read;
+  want_to_read.insert(1);
+  {
+    set<int> minimum;
+    EXPECT_EQ(-EIO, example.minimum_to_decode(want_to_read,
+                                              available_chunks,
+                                              &minimum));
+  }
+  available_chunks.insert(0);
+  available_chunks.insert(2);
+  {
+    set<int> minimum;
+    EXPECT_EQ(0, example.minimum_to_decode(want_to_read,
+                                           available_chunks,
+                                           &minimum));
+    EXPECT_EQ(available_chunks, minimum);
+    EXPECT_EQ(2u, minimum.size());
+    EXPECT_EQ(1u, minimum.count(0));
+    EXPECT_EQ(1u, minimum.count(2));
+  }
+  {
+    set<int> minimum;
+    available_chunks.insert(1);
+    EXPECT_EQ(0, example.minimum_to_decode(want_to_read,
+                                           available_chunks,
+                                           &minimum));
+    EXPECT_EQ(2u, minimum.size());
+    EXPECT_EQ(1u, minimum.count(0));
+    EXPECT_EQ(1u, minimum.count(1));
+  }
+}
+
+TEST(ErasureCodeExample, encode_decode)
+{
+  map<std::string,std::string> parameters;
+  ErasureCodeExample example(parameters);
+
+  bufferlist in;
+  in.append("ABCDE");
+  int want_to_encode[] = { 0, 1, 2 };
+  map<int, bufferlist> encoded;
+  EXPECT_EQ(0, example.encode(set<int>(want_to_encode, want_to_encode+3),
+                              in,
+                              &encoded));
+  EXPECT_EQ(3u, encoded.size());
+  EXPECT_EQ(3u, encoded[0].length());
+  EXPECT_EQ('A', encoded[0][0]);
+  EXPECT_EQ('B', encoded[0][1]);
+  EXPECT_EQ('C', encoded[0][2]);
+  EXPECT_EQ('D', encoded[1][0]);
+  EXPECT_EQ('E', encoded[1][1]);
+  EXPECT_EQ('A'^'D', encoded[2][0]);
+  EXPECT_EQ('B'^'E', encoded[2][1]);
+  EXPECT_EQ('C'^0, encoded[2][2]);
+
+  // all chunks are available
+  {
+    int want_to_decode[] = { 0, 1 };
+    map<int, bufferlist> decoded;
+    EXPECT_EQ(0, example.decode(set<int>(want_to_decode, want_to_decode+2),
+                                encoded,
+                                &decoded));
+    EXPECT_EQ(2u, decoded.size());
+    EXPECT_EQ(3u, decoded[0].length());
+    EXPECT_EQ('A', decoded[0][0]);
+    EXPECT_EQ('B', decoded[0][1]);
+    EXPECT_EQ('C', decoded[0][2]);
+    EXPECT_EQ('D', decoded[1][0]);
+    EXPECT_EQ('E', decoded[1][1]);
+  }
+
+  // one chunk is missing 
+  {
+    map<int, bufferlist> degraded = encoded;
+    degraded.erase(0);
+    EXPECT_EQ(2u, degraded.size());
+    int want_to_decode[] = { 0, 1 };
+    map<int, bufferlist> decoded;
+    EXPECT_EQ(0, example.decode(set<int>(want_to_decode, want_to_decode+2),
+                                degraded,
+                                &decoded));
+    EXPECT_EQ(2u, decoded.size());
+    EXPECT_EQ(3u, decoded[0].length());
+    EXPECT_EQ('A', decoded[0][0]);
+    EXPECT_EQ('B', decoded[0][1]);
+    EXPECT_EQ('C', decoded[0][2]);
+    EXPECT_EQ('D', decoded[1][0]);
+    EXPECT_EQ('E', decoded[1][1]);
+  }
+}
+
+int main(int argc, char **argv) {
+  vector<const char*> args;
+  argv_to_vec(argc, (const char **)argv, args);
+
+  global_init(NULL, args, CEPH_ENTITY_TYPE_CLIENT, CODE_ENVIRONMENT_UTILITY, 0);
+  common_init_finish(g_ceph_context);
+
+  ::testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}
+
+// Local Variables:
+// compile-command: "cd ../.. ; make -j4 && make unittest_erasure_code_example && ./unittest_erasure_code_example --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"
+// End: