ErasureCodeJerasure: import jerasure-1.2A

The files are copied verbatim from
http://web.eecs.utk.edu/~plank/plank/papers/Jerasure-1.2A.tar and a
section is added to the top level COPYING file to reflect the BSD
license.

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: fix jerasure compilation

Add the imported jerasure-1.2A to the Makefile.am and fix the
compilation warnings.

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

Signed-off-by: Loic Dachary <loic@dachary.org>
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>
ErasureCodeJerasure: unit test common to all techniques

A typed unit test is defined and must run regardless of the technique.
When a new technique is derived from ErasureCodeJerasure, it is added
to the JerasureTypes typedef and the test will validate that:

  * it provides reasonable defaults for the technique specific
    parameters
  * it modifies the k, m and w to reasonable defaults depending
    on the imposed constraints ( for instance Liber8tion requires
    that w == 8 but the test sets it to 7 )
  * the encoding of K=2, M=2 produces 4 chunks, the first two
    of which contains the original buffer data showing the
    code is systematic
  * decoding when all 4 chunks are available indeed retrieves
    the original buffer content
  * decoding when the two data chunks are are missing indeed
    retrieves the original buffer content

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define technique ReedSolomonVandermonde

technique == reed_sol_van

parse : default to K=7, M=3 and W=8 . If W is not 8, 16 or 32, it
reverts to 8.

pad_in_length : pad to a multiple of k*w*sizeof(int)

prepare, jerasure_encode, jerasure_decode map directly to the matching
jerasure functions

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define technique ReedSolomonRAID6

technique == reed_sol_r6_op

parse : default to K=7 and W=8 . If W is not 8, 16 or 32, it
reverts to 8.

pad_in_length : pad to a multiple of k*w*sizeof(int)

prepare, jerasure_encode, jerasure_decode map directly to the matching
jerasure functions

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define techniques CauchyOrig and CauchyGood

The technique Cauchy has two variants:

       ErasureCodeInterface (abstract)
       |
       -> ErasureCodeJerasure (abstract)
          |
          -> ErasureCodeJerasureCauchy (abstract)
          |  |
          |  -> ErasureCodeJerasureCauchyOrig
          |     | == cauchy_orig
          |  -> ErasureCodeJerasureCauchyGood
          |     | == cauchy_good

ErasureCodeJerasureCauchy defines the prepare_schedule method to be used
by prepare method, which is the only one overloaded by
ErasureCodeJerasureCauchyOrig (calling cauchy_original_coding_matrix)
and ErasureCodeJerasureCauchyGood ( calling
cauchy_good_general_coding_matrix).

The schedule is retained for encoding and the bitmatrix for decoding.

parse : default to K=7, M=3, W=8 and packetsize = 8.

pad_in_length : pad to a multiple of k*w*packetsize*sizeof(int)

jerasure_encode, jerasure_decode map directly to the matching
jerasure functions

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define technique Liberation

technique == "liberation"

parse : default to K=7, M=2 and W=7 and packetsize = 8.
If any of the following constraints is not satisfied, revert to the
default:

 * K > W
 * W > 2
 * W is a prime number
 * packetsize must not be zero
 * packetsize must be a multiple of sizeof(int)

pad_in_length : pad to a multiple of k*w*packetsize*sizeof(int)

prepare, jerasure_encode, jerasure_decode map directly to the matching
jerasure functions

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define technique BlaumRoth

technique == "blaum_roth"

       ErasureCodeInterface (abstract)
       |
       -> ErasureCodeJerasure (abstract)
          |
          -> ErasureCodeJerasureLiberation
             |
             -> ErasureCodeJerasureBlaumRoth
                | == blaum_roth

Derived from Liberation it only overloads the prepare method to use
blaum_roth_coding_bitmatrix.

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

Signed-off-by: Loic Dachary <loic@dachary.org>
ErasureCodeJerasure: define technique Liber8tion

technique == "liber8tion"

       ErasureCodeInterface (abstract)
       |
       -> ErasureCodeJerasure (abstract)
          |
          -> ErasureCodeJerasureLiberation
             |
             -> ErasureCodeJerasureLiber8tion
                | == liber8tion

Derived from Liberation it overloads the parse and prepare methods.

parse : default to K=2 and packetsize = 8.
If any of the following constraints is not satisfied, revert to the
default:

  * K <= 8
  * packetsize must not be zero

prepare uses liber8tion_coding_bitmatrix

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

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

Create the class matching the string found in the
erasure-code-technique parameter, using the same strings are the
original {encoder,decoder}.c examples from Jerasure-1.2A. Registers
the plugin in ErasureCodePluginRegistry.

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

Signed-off-by: Loic Dachary <loic@dachary.org>
Merge pull request #538 from dachary/wip-5879

jerasure-1.2A plugin

Reviewed-by: Samuel Just <sam.just@inktank.com>