diff options
Diffstat (limited to 'src/erasure-code/jerasure/ErasureCodeJerasure.cc')
| -rw-r--r-- | src/erasure-code/jerasure/ErasureCodeJerasure.cc | 515 |
1 files changed, 515 insertions, 0 deletions
diff --git a/src/erasure-code/jerasure/ErasureCodeJerasure.cc b/src/erasure-code/jerasure/ErasureCodeJerasure.cc new file mode 100644 index 000000000..3a780de81 --- /dev/null +++ b/src/erasure-code/jerasure/ErasureCodeJerasure.cc @@ -0,0 +1,515 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Ceph distributed storage system + * + * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com> + * Copyright (C) 2014 Red Hat <contact@redhat.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 "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 LARGEST_VECTOR_WORDSIZE 16 + +#define dout_context g_ceph_context +#define dout_subsys ceph_subsys_osd +#undef dout_prefix +#define dout_prefix _prefix(_dout) + +using std::ostream; +using std::map; +using std::set; + +using ceph::bufferlist; +using ceph::ErasureCodeProfile; + +static ostream& _prefix(std::ostream* _dout) +{ + return *_dout << "ErasureCodeJerasure: "; +} + + +int ErasureCodeJerasure::init(ErasureCodeProfile& profile, ostream *ss) +{ + int err = 0; + dout(10) << "technique=" << technique << dendl; + profile["technique"] = technique; + err |= parse(profile, ss); + if (err) + return err; + prepare(); + return ErasureCode::init(profile, ss); +} + +int ErasureCodeJerasure::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 |= to_int("w", profile, &w, DEFAULT_W, ss); + if (chunk_mapping.size() > 0 && (int)chunk_mapping.size() != k + m) { + *ss << "mapping " << profile.find("mapping")->second + << " maps " << chunk_mapping.size() << " chunks instead of" + << " the expected " << k + m << " and will be ignored" << std::endl; + chunk_mapping.clear(); + err = -EINVAL; + } + err |= sanity_check_k_m(k, m, ss); + return err; +} + +unsigned int ErasureCodeJerasure::get_chunk_size(unsigned int object_size) const +{ + unsigned alignment = get_alignment(); + if (per_chunk_alignment) { + unsigned chunk_size = object_size / k; + if (object_size % k) + chunk_size++; + dout(20) << "get_chunk_size: chunk_size " << chunk_size + << " must be modulo " << alignment << dendl; + ceph_assert(alignment <= chunk_size); + 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; + } else { + unsigned tail = object_size % alignment; + unsigned padded_length = object_size + ( tail ? ( alignment - tail ) : 0 ); + ceph_assert(padded_length % k == 0); + return padded_length / k; + } +} + +int ErasureCodeJerasure::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(); + jerasure_encode(&chunks[0], &chunks[k], (*encoded)[0].length()); + return 0; +} + +int ErasureCodeJerasure::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; + + ceph_assert(erasures_count > 0); + return jerasure_decode(erasures, data, coding, blocksize); +} + +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; +} + +// +// ErasureCodeJerasureReedSolomonVandermonde +// +void ErasureCodeJerasureReedSolomonVandermonde::jerasure_encode(char **data, + char **coding, + int blocksize) +{ + jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize); +} + +int ErasureCodeJerasureReedSolomonVandermonde::jerasure_decode(int *erasures, + char **data, + char **coding, + int blocksize) +{ + return jerasure_matrix_decode(k, m, w, matrix, 1, + erasures, data, coding, blocksize); +} + +unsigned ErasureCodeJerasureReedSolomonVandermonde::get_alignment() const +{ + if (per_chunk_alignment) { + return w * LARGEST_VECTOR_WORDSIZE; + } else { + unsigned alignment = k*w*sizeof(int); + if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) + alignment = k*w*LARGEST_VECTOR_WORDSIZE; + return alignment; + } +} + +int ErasureCodeJerasureReedSolomonVandermonde::parse(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = 0; + err |= ErasureCodeJerasure::parse(profile, ss); + if (w != 8 && w != 16 && w != 32) { + *ss << "ReedSolomonVandermonde: w=" << w + << " must be one of {8, 16, 32} : revert to " << DEFAULT_W << std::endl; + err = -EINVAL; + } + err |= to_bool("jerasure-per-chunk-alignment", profile, + &per_chunk_alignment, "false", ss); + return err; +} + +void ErasureCodeJerasureReedSolomonVandermonde::prepare() +{ + matrix = reed_sol_vandermonde_coding_matrix(k, m, w); +} + +// +// ErasureCodeJerasureReedSolomonRAID6 +// +void ErasureCodeJerasureReedSolomonRAID6::jerasure_encode(char **data, + char **coding, + int blocksize) +{ + reed_sol_r6_encode(k, w, data, coding, blocksize); +} + +int ErasureCodeJerasureReedSolomonRAID6::jerasure_decode(int *erasures, + char **data, + char **coding, + int blocksize) +{ + return jerasure_matrix_decode(k, m, w, matrix, 1, erasures, data, coding, blocksize); +} + +unsigned ErasureCodeJerasureReedSolomonRAID6::get_alignment() const +{ + if (per_chunk_alignment) { + return w * LARGEST_VECTOR_WORDSIZE; + } else { + unsigned alignment = k*w*sizeof(int); + if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) + alignment = k*w*LARGEST_VECTOR_WORDSIZE; + return alignment; + } +} + +int ErasureCodeJerasureReedSolomonRAID6::parse(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = ErasureCodeJerasure::parse(profile, ss); + if (m != stoi(DEFAULT_M)) { + *ss << "ReedSolomonRAID6: m=" << m + << " must be 2 for RAID6: revert to 2" << std::endl; + err = -EINVAL; + } + if (w != 8 && w != 16 && w != 32) { + *ss << "ReedSolomonRAID6: w=" << w + << " must be one of {8, 16, 32} : revert to 8 " << std::endl; + err = -EINVAL; + } + return err; +} + +void ErasureCodeJerasureReedSolomonRAID6::prepare() +{ + matrix = reed_sol_r6_coding_matrix(k, w); +} + +// +// ErasureCodeJerasureCauchy +// +void ErasureCodeJerasureCauchy::jerasure_encode(char **data, + char **coding, + int blocksize) +{ + jerasure_schedule_encode(k, m, w, schedule, + data, coding, blocksize, packetsize); +} + +int ErasureCodeJerasureCauchy::jerasure_decode(int *erasures, + char **data, + char **coding, + int blocksize) +{ + return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, + erasures, data, coding, blocksize, packetsize, 1); +} + +unsigned ErasureCodeJerasureCauchy::get_alignment() const +{ + if (per_chunk_alignment) { + unsigned alignment = w * packetsize; + unsigned modulo = alignment % LARGEST_VECTOR_WORDSIZE; + if (modulo) + alignment += LARGEST_VECTOR_WORDSIZE - modulo; + return alignment; + } else { + unsigned alignment = k*w*packetsize*sizeof(int); + if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) + alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE; + return alignment; + } +} + +int ErasureCodeJerasureCauchy::parse(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = ErasureCodeJerasure::parse(profile, ss); + err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); + err |= to_bool("jerasure-per-chunk-alignment", profile, + &per_chunk_alignment, "false", ss); + return err; +} + +void ErasureCodeJerasureCauchy::prepare_schedule(int *matrix) +{ + bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix); + schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); +} + +ErasureCodeJerasureCauchy::~ErasureCodeJerasureCauchy() +{ + if (bitmatrix) + free(bitmatrix); + if (schedule) + jerasure_free_schedule(schedule); +} + +// +// ErasureCodeJerasureCauchyOrig +// +void ErasureCodeJerasureCauchyOrig::prepare() +{ + int *matrix = cauchy_original_coding_matrix(k, m, w); + prepare_schedule(matrix); + free(matrix); +} + +// +// ErasureCodeJerasureCauchyGood +// +void ErasureCodeJerasureCauchyGood::prepare() +{ + int *matrix = cauchy_good_general_coding_matrix(k, m, w); + prepare_schedule(matrix); + free(matrix); +} + +// +// ErasureCodeJerasureLiberation +// +ErasureCodeJerasureLiberation::~ErasureCodeJerasureLiberation() +{ + if (bitmatrix) + free(bitmatrix); + if (schedule) + jerasure_free_schedule(schedule); +} + +void ErasureCodeJerasureLiberation::jerasure_encode(char **data, + char **coding, + int blocksize) +{ + jerasure_schedule_encode(k, m, w, schedule, data, + coding, blocksize, packetsize); +} + +int ErasureCodeJerasureLiberation::jerasure_decode(int *erasures, + char **data, + char **coding, + int blocksize) +{ + return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, + coding, blocksize, packetsize, 1); +} + +unsigned ErasureCodeJerasureLiberation::get_alignment() const +{ + unsigned alignment = k*w*packetsize*sizeof(int); + if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) + alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE; + return alignment; +} + +bool ErasureCodeJerasureLiberation::check_k(ostream *ss) const +{ + if (k > w) { + *ss << "k=" << k << " must be less than or equal to w=" << w << std::endl; + return false; + } else { + return true; + } +} + +bool ErasureCodeJerasureLiberation::check_w(ostream *ss) const +{ + if (w <= 2 || !is_prime(w)) { + *ss << "w=" << w << " must be greater than two and be prime" << std::endl; + return false; + } else { + return true; + } +} + +bool ErasureCodeJerasureLiberation::check_packetsize_set(ostream *ss) const +{ + if (packetsize == 0) { + *ss << "packetsize=" << packetsize << " must be set" << std::endl; + return false; + } else { + return true; + } +} + +bool ErasureCodeJerasureLiberation::check_packetsize(ostream *ss) const +{ + if ((packetsize%(sizeof(int))) != 0) { + *ss << "packetsize=" << packetsize + << " must be a multiple of sizeof(int) = " << sizeof(int) << std::endl; + return false; + } else { + return true; + } +} + +int ErasureCodeJerasureLiberation::revert_to_default(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = 0; + *ss << "reverting to k=" << DEFAULT_K << ", w=" + << DEFAULT_W << ", packetsize=" << DEFAULT_PACKETSIZE << std::endl; + profile["k"] = DEFAULT_K; + err |= to_int("k", profile, &k, DEFAULT_K, ss); + profile["w"] = DEFAULT_W; + err |= to_int("w", profile, &w, DEFAULT_W, ss); + profile["packetsize"] = DEFAULT_PACKETSIZE; + err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); + return err; +} + +int ErasureCodeJerasureLiberation::parse(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = ErasureCodeJerasure::parse(profile, ss); + err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); + + bool error = false; + if (!check_k(ss)) + error = true; + if (!check_w(ss)) + error = true; + if (!check_packetsize_set(ss) || !check_packetsize(ss)) + error = true; + if (error) { + revert_to_default(profile, ss); + err = -EINVAL; + } + return err; +} + +void ErasureCodeJerasureLiberation::prepare() +{ + bitmatrix = liberation_coding_bitmatrix(k, w); + schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); +} + +// +// ErasureCodeJerasureBlaumRoth +// +bool ErasureCodeJerasureBlaumRoth::check_w(ostream *ss) const +{ + // back in Firefly, w = 7 was the default and produced usable + // chunks. Tolerate this value for backward compatibility. + if (w == 7) + return true; + if (w <= 2 || !is_prime(w+1)) { + *ss << "w=" << w << " must be greater than two and " + << "w+1 must be prime" << std::endl; + return false; + } else { + return true; + } +} + +void ErasureCodeJerasureBlaumRoth::prepare() +{ + bitmatrix = blaum_roth_coding_bitmatrix(k, w); + schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); +} + +// +// ErasureCodeJerasureLiber8tion +// +int ErasureCodeJerasureLiber8tion::parse(ErasureCodeProfile &profile, + ostream *ss) +{ + int err = ErasureCodeJerasure::parse(profile, ss); + if (m != stoi(DEFAULT_M)) { + *ss << "liber8tion: m=" << m << " must be " << DEFAULT_M + << " for liber8tion: revert to " << DEFAULT_M << std::endl; + err = -EINVAL; + } + if (w != stoi(DEFAULT_W)) { + *ss << "liber8tion: w=" << w << " must be " << DEFAULT_W + << " for liber8tion: revert to " << DEFAULT_W << std::endl; + err = -EINVAL; + } + err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); + + bool error = false; + if (!check_k(ss)) + error = true; + if (!check_packetsize_set(ss)) + error = true; + if (error) { + revert_to_default(profile, ss); + err = -EINVAL; + } + return err; +} + +void ErasureCodeJerasureLiber8tion::prepare() +{ + bitmatrix = liber8tion_coding_bitmatrix(k); + schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); +} |