ErasureCodeJerasure: base class for jerasure ErasureCodeInterface

The ErasureCodeJerasure class is derived from ErasureCodeInterface and
is meant to be derived to implement each jerasure technique (
Reed-Solomon, Cauchy ... ).

The parameters K ( number of data chunks ), M ( number of coding chunks
) and W ( word size ) are data members common to all techniques. The
technique data member is expected to be set to a string describing the
technique for debugging purposes.

minimum_to_decode_with_cost ignores the cost and calls minimum_to_decode.

minimum_to_decode returns the first K chunks or an error if there are
not enough. Since all codes are systematic, when all chunks are
available returning the first K allows for concatenation and is the best
choice.

The encode method converts bufferlist into char* as expected by the
jerasure functions. The padding of the incoming buffer depends on the
technique and is computed by the pad_in_length method. Encoding is done
with the jerasure_encode method.

The decode method converts the char* returned by the jerasure functions
into bufferlists to be consumed by the caller. The decoding is done by
the jerasure_decode method.

The to_int convenience method is used to convert parameters. The
is_prime convenience method will be used by some techniques to validate
parameters.

Immediately after creating an ErasureCodeJerasure derived object, the
init method must be called. It will call the parse method to interpret
the parameters required by the technique and set the k, m and w data
members. The prepare method is expected to compute the matrix ( and
schedule if necessary ) and store it in a data member. The init method
will be called while holding the ErasureCodePluginRegistry mutex. The
encode and decode methods will not be protected by a mutex and may be
called by different threads for the benefit of different placement
groups. They will not have any side effect on the object.

https://github.com/dachary/ceph/tree/wip-5879 refs #5879

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

3 files changed, 234 insertions, 1 deletions

diff --git a/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.cc b/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.cc
new file mode 100644
index 00000000000..5a5c4ce4e59
--- /dev/null
+++ b/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.cc
@@ -0,0 +1,163 @@
+// -*- 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 <errno.h>
+#include "common/debug.h"
+#include "ErasureCodeJerasure.h"
+extern "C" {
+#include "jerasure.h"
+#include "reed_sol.h"
+#include "galois.h"
+#include "cauchy.h"
+#include "liberation.h"
+}
+
+#define dout_subsys ceph_subsys_osd
+#undef dout_prefix
+#define dout_prefix _prefix(_dout)
+
+static ostream& _prefix(std::ostream* _dout)
+{
+  return *_dout << "ErasureCodeJerasure: ";
+}
+
+void ErasureCodeJerasure::init(const map<std::string,std::string> &parameters) {
+  dout(10) << "technique=" << technique << dendl;
+  parse(parameters);
+  prepare();
+}
+
+int ErasureCodeJerasure::minimum_to_decode(const set<int> &want_to_read,
+                                           const set<int> &available_chunks,
+                                           set<int> *minimum) {
+  if (available_chunks.size() < (unsigned)k)
+    return -EIO;
+  set<int>::iterator i;
+  unsigned j;
+  for (i = available_chunks.begin(), j = 0; j < (unsigned)k; i++, j++)
+    minimum->insert(*i);
+  return 0;
+}
+
+int ErasureCodeJerasure::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);
+}
+
+int ErasureCodeJerasure::encode(const set<int> &want_to_encode,
+                                const bufferlist &in,
+                                map<int, bufferlist> *encoded) {
+  unsigned in_length = pad_in_length(in.length());
+  dout(10) << "encode adjusted buffer length from " << in.length() << " to " << in_length << dendl;
+  assert(in_length % k == 0);
+  unsigned blocksize = in_length / k;
+  unsigned length = blocksize * ( k + m );
+  bufferlist out(in);
+  bufferptr pad(length - in.length());
+  pad.zero(0, k);
+  out.push_back(pad);
+  char *p = out.c_str();
+  char *data[k];
+  for (int i = 0; i < k; i++) {
+    data[i] = p + i * blocksize;
+  }
+  char *coding[m];
+  for (int i = 0; i < m; i++) {
+    coding[i] = p + ( k + i ) * blocksize;
+  }
+  jerasure_encode(data, coding, blocksize);
+  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) * blocksize, blocksize);
+    (*encoded)[*j].push_front(chunk);
+  }
+  return 0;
+}
+
+int ErasureCodeJerasure::decode(const set<int> &want_to_read,
+                                const map<int, bufferlist> &chunks,
+                                map<int, bufferlist> *decoded) {
+  unsigned blocksize = (*chunks.begin()).second.length();
+  int erasures[k + m + 1];
+  int erasures_count = 0;
+  char *data[k];
+  char *coding[m];
+  for (int i =  0; i < k + m; i++) {
+    if (chunks.find(i) == chunks.end()) {
+      erasures[erasures_count] = i;
+      erasures_count++;
+      bufferptr ptr(blocksize);
+      (*decoded)[i].push_front(ptr);
+    } else {
+      (*decoded)[i] = chunks.find(i)->second;
+    }
+    if (i < k)
+      data[i] = (*decoded)[i].c_str();
+    else
+      coding[i - k] = (*decoded)[i].c_str();
+  }
+  erasures[erasures_count] = -1;
+
+  if (erasures_count > 0)
+    return jerasure_decode(erasures, data, coding, blocksize);
+  else
+    return 0;
+}
+
+int ErasureCodeJerasure::to_int(const std::string &name,
+                                const map<std::string,std::string> &parameters,
+                                int default_value) {
+  if (parameters.find(name) == parameters.end() ||
+      parameters.find(name)->second.size() == 0) {
+    dout(10) << name << " defaults to " << default_value << dendl;
+    return default_value;
+  }
+  const std::string value = parameters.find(name)->second;
+  std::string p = value;
+  std::string err;
+  int r = strict_strtol(p.c_str(), 10, &err);
+  if (!err.empty()) {
+    derr << "could not convert " << name << "=" << value
+         << " to int because " << err
+         << ", set to default " << default_value << dendl;
+    return default_value;
+  }
+  dout(10) << name << " set to " << r << dendl;
+  return r;
+}
+
+bool ErasureCodeJerasure::is_prime(int value) {
+  int prime55[] = {
+    2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
+    73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,
+    151,157,163,167,173,179,
+    181,191,193,197,199,211,223,227,229,233,239,241,251,257
+  };
+  int i;
+  for (i = 0; i < 55; i++)
+    if (value == prime55[i])
+      return true;
+  return false;
+}
+
diff --git a/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.h b/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.h
new file mode 100644
index 00000000000..2a8ed268f8a
--- /dev/null
+++ b/src/osd/ErasureCodePluginJerasure/ErasureCodeJerasure.h
@@ -0,0 +1,68 @@
+// -*- 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_JERASURE_H
+#define CEPH_ERASURE_CODE_JERASURE_H
+
+#include "osd/ErasureCodeInterface.h"
+
+class ErasureCodeJerasure : public ErasureCodeInterface {
+public:
+  int k;
+  int m;
+  int w;
+  const char *technique;
+
+  ErasureCodeJerasure(const char *_technique) :
+    technique(_technique)
+  {}
+
+  virtual ~ErasureCodeJerasure() {}
+  
+  virtual int minimum_to_decode(const set<int> &want_to_read,
+                                const set<int> &available_chunks,
+                                set<int> *minimum);
+
+  virtual int minimum_to_decode_with_cost(const set<int> &want_to_read,
+                                          const map<int, int> &available,
+                                          set<int> *minimum);
+
+  virtual int encode(const set<int> &want_to_encode,
+                     const bufferlist &in,
+                     map<int, bufferlist> *encoded);
+
+  virtual int decode(const set<int> &want_to_read,
+                     const map<int, bufferlist> &chunks,
+                     map<int, bufferlist> *decoded);
+
+  void init(const map<std::string,std::string> &parameters);
+  virtual void jerasure_encode(char **data,
+                               char **coding,
+                               int blocksize) = 0;
+  virtual int jerasure_decode(int *erasures,
+                               char **data,
+                               char **coding,
+                               int blocksize) = 0;
+  virtual unsigned pad_in_length(unsigned in_length) = 0;
+  virtual void parse(const map<std::string,std::string> &parameters) = 0;
+  virtual void prepare() = 0;
+  static int to_int(const std::string &name,
+                    const map<std::string,std::string> &parameters,
+                    int default_value);
+  static bool is_prime(int value);
+};
+
+#endif
diff --git a/src/osd/ErasureCodePluginJerasure/Makefile.am b/src/osd/ErasureCodePluginJerasure/Makefile.am
index e599bb811b1..8549d91a886 100644
--- a/src/osd/ErasureCodePluginJerasure/Makefile.am
+++ b/src/osd/ErasureCodePluginJerasure/Makefile.am
@@ -1,11 +1,13 @@
 # jerasure plugin
 libec_jerasure_la_SOURCES = \
+  osd/ErasureCodePluginJerasure/ErasureCodeJerasure.cc \
   osd/ErasureCodePluginJerasure/cauchy.c \
   osd/ErasureCodePluginJerasure/galois.c \
   osd/ErasureCodePluginJerasure/jerasure.c \
   osd/ErasureCodePluginJerasure/liberation.c \
   osd/ErasureCodePluginJerasure/reed_sol.c
 noinst_HEADERS += \
+  osd/ErasureCodePluginJerasure/ErasureCodeJerasure.h \
   osd/ErasureCodePluginJerasure/cauchy.h \
   osd/ErasureCodePluginJerasure/galois.h \
   osd/ErasureCodePluginJerasure/jerasure.h \
@@ -14,6 +16,6 @@ noinst_HEADERS += \
 libec_jerasure_la_CFLAGS = ${AM_CFLAGS} 
 libec_jerasure_la_CXXFLAGS= ${AM_CXXFLAGS} 
 libec_jerasure_la_LIBADD = $(PTHREAD_LIBS) $(EXTRALIBS)
-libec_jerasure_la_LDFLAGS = ${AM_LDFLAGS} -version-info 1:0:0
+libec_jerasure_la_LDFLAGS = ${AM_LDFLAGS} -version-info 1:0:0 -export-symbols-regex '.*__erasure_code_.*'
 
 erasure_codelib_LTLIBRARIES += libec_jerasure.la