+++ /dev/null
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2014 CERN (Switzerland)
- *
- * Author: Andreas-Joachim Peters <Andreas.Joachim.Peters@cern.ch>
- *
- * 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 <algorithm>
-#include <errno.h>
-// -----------------------------------------------------------------------------
-#include "common/debug.h"
-#include "ErasureCodeIsa.h"
-#include "xor_op.h"
-#include "include/assert.h"
-using namespace std;
-
-// -----------------------------------------------------------------------------
-extern "C" {
-#include "isa-l/include/erasure_code.h"
-}
-// -----------------------------------------------------------------------------
-#define dout_context g_ceph_context
-#define dout_subsys ceph_subsys_osd
-#undef dout_prefix
-#define dout_prefix _prefix(_dout)
-// -----------------------------------------------------------------------------
-
-// -----------------------------------------------------------------------------
-
-static ostream&
-_prefix(std::ostream* _dout)
-{
- return *_dout << "ErasureCodeIsa: ";
-}
-// -----------------------------------------------------------------------------
-
-const std::string ErasureCodeIsaDefault::DEFAULT_K("7");
-const std::string ErasureCodeIsaDefault::DEFAULT_M("3");
-
-
-// -----------------------------------------------------------------------------
-
-int
-ErasureCodeIsa::init(ErasureCodeProfile &profile, ostream *ss)
-{
- int err = 0;
- err |= parse(profile, ss);
- if (err)
- return err;
- prepare();
- return ErasureCode::init(profile, ss);
-}
-
-// -----------------------------------------------------------------------------
-
-unsigned int
-ErasureCodeIsa::get_chunk_size(unsigned int object_size) const
-{
- unsigned alignment = get_alignment();
- unsigned chunk_size = ( object_size + k - 1 ) / k;
- dout(20) << "get_chunk_size: chunk_size " << chunk_size
- << " must be modulo " << alignment << dendl;
- unsigned modulo = chunk_size % alignment;
- if (modulo) {
- dout(10) << "get_chunk_size: " << chunk_size
- << " padded to " << chunk_size + alignment - modulo << dendl;
- chunk_size += alignment - modulo;
- }
- return chunk_size;
-}
-
-// -----------------------------------------------------------------------------
-
-int ErasureCodeIsa::encode_chunks(const set<int> &want_to_encode,
- map<int, bufferlist> *encoded)
-{
- char *chunks[k + m];
- for (int i = 0; i < k + m; i++)
- chunks[i] = (*encoded)[i].c_str();
- isa_encode(&chunks[0], &chunks[k], (*encoded)[0].length());
- return 0;
-}
-
-int ErasureCodeIsa::decode_chunks(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++;
- }
- if (i < k)
- data[i] = (*decoded)[i].c_str();
- else
- coding[i - k] = (*decoded)[i].c_str();
- }
- erasures[erasures_count] = -1;
- assert(erasures_count > 0);
- return isa_decode(erasures, data, coding, blocksize);
-}
-
-// -----------------------------------------------------------------------------
-
-void
-ErasureCodeIsaDefault::isa_encode(char **data,
- char **coding,
- int blocksize)
-{
-
- if (m == 1)
- // single parity stripe
- region_xor((unsigned char**) data, (unsigned char*) coding[0], k, blocksize);
- else
- ec_encode_data(blocksize, k, m, encode_tbls,
- (unsigned char**) data, (unsigned char**) coding);
-}
-
-// -----------------------------------------------------------------------------
-
-bool
-ErasureCodeIsaDefault::erasure_contains(int *erasures, int i)
-{
- for (int l = 0; erasures[l] != -1; l++) {
- if (erasures[l] == i)
- return true;
- }
- return false;
-}
-
-// -----------------------------------------------------------------------------
-
-
-
-// -----------------------------------------------------------------------------
-
-int
-ErasureCodeIsaDefault::isa_decode(int *erasures,
- char **data,
- char **coding,
- int blocksize)
-{
- int nerrs = 0;
- int i, r, s;
-
- // count the errors
- for (int l = 0; erasures[l] != -1; l++) {
- nerrs++;
- }
-
- unsigned char *recover_source[k];
- unsigned char *recover_target[m];
-
- memset(recover_source, 0, sizeof (recover_source));
- memset(recover_target, 0, sizeof (recover_target));
-
- // ---------------------------------------------
- // Assign source and target buffers
- // ---------------------------------------------
- for (i = 0, s = 0, r = 0; ((r < k) || (s < nerrs)) && (i < (k + m)); i++) {
- if (!erasure_contains(erasures, i)) {
- if (r < k) {
- if (i < k) {
- recover_source[r] = (unsigned char*) data[i];
- } else {
- recover_source[r] = (unsigned char*) coding[i - k];
- }
- r++;
- }
- } else {
- if (s < m) {
- if (i < k) {
- recover_target[s] = (unsigned char*) data[i];
- } else {
- recover_target[s] = (unsigned char*) coding[i - k];
- }
- s++;
- }
- }
- }
-
- if (m == 1) {
- // single parity decoding
- assert(1 == nerrs);
- dout(20) << "isa_decode: reconstruct using region xor [" <<
- erasures[0] << "]" << dendl;
- region_xor(recover_source, recover_target[0], k, blocksize);
- return 0;
- }
-
-
- if ((matrixtype == kVandermonde) &&
- (nerrs == 1) &&
- (erasures[0] < (k + 1))) {
- // use xor decoding if a data chunk is missing or the first coding chunk
- dout(20) << "isa_decode: reconstruct using region xor [" <<
- erasures[0] << "]" << dendl;
- assert(1 == s);
- assert(k == r);
- region_xor(recover_source, recover_target[0], k, blocksize);
- return 0;
- }
-
- unsigned char d[k * (m + k)];
- unsigned char decode_tbls[k * (m + k)*32];
- unsigned char *p_tbls = decode_tbls;
-
- int decode_index[k];
-
- if (nerrs > m)
- return -1;
-
- std::string erasure_signature; // describes a matrix configuration for caching
-
- // ---------------------------------------------
- // Construct b by removing error rows
- // ---------------------------------------------
-
- for (i = 0, r = 0; i < k; i++, r++) {
- char id[128];
- while (erasure_contains(erasures, r))
- r++;
-
- decode_index[i] = r;
-
- snprintf(id, sizeof (id), "+%d", r);
- erasure_signature += id;
- }
-
- for (int p = 0; p < nerrs; p++) {
- char id[128];
- snprintf(id, sizeof (id), "-%d", erasures[p]);
- erasure_signature += id;
- }
-
- // ---------------------------------------------
- // Try to get an already computed matrix
- // ---------------------------------------------
- if (!tcache.getDecodingTableFromCache(erasure_signature, p_tbls, matrixtype, k, m)) {
- int j;
- unsigned char b[k * (m + k)];
- unsigned char c[k * (m + k)];
-
- for (i = 0; i < k; i++) {
- r = decode_index[i];
- for (j = 0; j < k; j++)
- b[k * i + j] = encode_coeff[k * r + j];
- }
- // ---------------------------------------------
- // Compute inverted matrix
- // ---------------------------------------------
-
- // --------------------------------------------------------
- // Remark: this may fail for certain Vandermonde matrices !
- // There is an advanced way trying to use different
- // source chunks to get an invertible matrix, however
- // there are also (k,m) combinations which cannot be
- // inverted when m chunks are lost and this optimizations
- // does not help. Therefor we keep the code simpler.
- // --------------------------------------------------------
- if (gf_invert_matrix(b, d, k) < 0) {
- dout(0) << "isa_decode: bad matrix" << dendl;
- return -1;
- }
-
- for (int p = 0; p < nerrs; p++) {
- if (erasures[p] < k) {
- // decoding matrix elements for data chunks
- for (j = 0; j < k; j++) {
- c[k * p + j] = d[k * erasures[p] + j];
- }
- } else {
- // decoding matrix element for coding chunks
- for (i = 0; i < k; i++) {
- int s = 0;
- for (j = 0; j < k; j++)
- s ^= gf_mul(d[j * k + i],
- encode_coeff[k * erasures[p] + j]);
-
- c[k * p + i] = s;
- }
- }
- }
-
- // ---------------------------------------------
- // Initialize Decoding Table
- // ---------------------------------------------
- ec_init_tables(k, nerrs, c, decode_tbls);
- tcache.putDecodingTableToCache(erasure_signature, p_tbls, matrixtype, k, m);
- }
- // Recover data sources
- ec_encode_data(blocksize,
- k, nerrs, decode_tbls, recover_source, recover_target);
-
-
- return 0;
-}
-
-// -----------------------------------------------------------------------------
-
-unsigned
-ErasureCodeIsaDefault::get_alignment() const
-{
- return EC_ISA_ADDRESS_ALIGNMENT;
-}
-
-// -----------------------------------------------------------------------------
-
-int ErasureCodeIsaDefault::parse(ErasureCodeProfile &profile,
- ostream *ss)
-{
- int err = ErasureCode::parse(profile, ss);
- err |= to_int("k", profile, &k, DEFAULT_K, ss);
- err |= to_int("m", profile, &m, DEFAULT_M, ss);
- err |= sanity_check_k(k, ss);
-
- if (matrixtype == kVandermonde) {
- // these are verified safe values evaluated using the
- // benchmarktool and 10*(combinatoric for maximum loss) random
- // full erasures
- if (k > 32) {
- *ss << "Vandermonde: m=" << m
- << " should be less/equal than 32 : revert to k=32" << std::endl;
- k = 32;
- err = -EINVAL;
- }
-
- if (m > 4) {
- *ss << "Vandermonde: m=" << m
- << " should be less than 5 to guarantee an MDS codec:"
- << " revert to m=4" << std::endl;
- m = 4;
- err = -EINVAL;
- }
- switch (m) {
- case 4:
- if (k > 21) {
- *ss << "Vandermonde: k=" << k
- << " should be less than 22 to guarantee an MDS"
- << " codec with m=4: revert to k=21" << std::endl;
- k = 21;
- err = -EINVAL;
- }
- break;
- default:
- ;
- }
- }
- return err;
-}
-
-// -----------------------------------------------------------------------------
-
-void
-ErasureCodeIsaDefault::prepare()
-{
- // setup shared encoding table and coefficients
- unsigned char** p_enc_table =
- tcache.getEncodingTable(matrixtype, k, m);
-
- unsigned char** p_enc_coeff =
- tcache.getEncodingCoefficient(matrixtype, k, m);
-
- if (!*p_enc_coeff) {
- dout(10) << "[ cache tables ] creating coeff for k=" <<
- k << " m=" << m << dendl;
- // build encoding coefficients which need to be computed once for each (k,m)
- encode_coeff = (unsigned char*) malloc(k * (m + k));
-
- if (matrixtype == kVandermonde)
- gf_gen_rs_matrix(encode_coeff, k + m, k);
- if (matrixtype == kCauchy)
- gf_gen_cauchy1_matrix(encode_coeff, k + m, k);
-
- // either our new created coefficients are stored or if they have been
- // created in the meanwhile the locally allocated coefficients will be
- // freed by setEncodingCoefficient
- encode_coeff = tcache.setEncodingCoefficient(matrixtype, k, m, encode_coeff);
- } else {
- encode_coeff = *p_enc_coeff;
- }
-
- if (!*p_enc_table) {
- dout(10) << "[ cache tables ] creating tables for k=" <<
- k << " m=" << m << dendl;
- // build encoding table which needs to be computed once for each (k,m)
- encode_tbls = (unsigned char*) malloc(k * (m + k)*32);
- ec_init_tables(k, m, &encode_coeff[k * k], encode_tbls);
-
- // either our new created table is stored or if it has been
- // created in the meanwhile the locally allocated table will be
- // freed by setEncodingTable
- encode_tbls = tcache.setEncodingTable(matrixtype, k, m, encode_tbls);
- } else {
- encode_tbls = *p_enc_table;
- }
-
- unsigned memory_lru_cache =
- k * (m + k) * 32 * tcache.decoding_tables_lru_length;
-
- dout(10) << "[ cache memory ] = " << memory_lru_cache << " bytes" <<
- " [ matrix ] = " <<
- ((matrixtype == kVandermonde) ? "Vandermonde" : "Cauchy") << dendl;
-
- assert((matrixtype == kVandermonde) || (matrixtype == kCauchy));
-
-}
-// -----------------------------------------------------------------------------
Code Review / stor4nfv.git / blobdiff