1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph distributed storage system
6 * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com>
7 * Copyright (C) 2014 Red Hat <contact@redhat.com>
9 * Author: Loic Dachary <loic@dachary.org>
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public
13 * License as published by the Free Software Foundation; either
14 * version 2.1 of the License, or (at your option) any later version.
18 #include "common/debug.h"
19 #include "ErasureCodeJerasure.h"
28 #include "liberation.h"
31 #define LARGEST_VECTOR_WORDSIZE 16
33 #define dout_context g_ceph_context
34 #define dout_subsys ceph_subsys_osd
36 #define dout_prefix _prefix(_dout)
38 static ostream& _prefix(std::ostream* _dout)
40 return *_dout << "ErasureCodeJerasure: ";
44 int ErasureCodeJerasure::init(ErasureCodeProfile& profile, ostream *ss)
47 dout(10) << "technique=" << technique << dendl;
48 profile["technique"] = technique;
49 err |= parse(profile, ss);
53 return ErasureCode::init(profile, ss);
56 int ErasureCodeJerasure::parse(ErasureCodeProfile &profile,
59 int err = ErasureCode::parse(profile, ss);
60 err |= to_int("k", profile, &k, DEFAULT_K, ss);
61 err |= to_int("m", profile, &m, DEFAULT_M, ss);
62 err |= to_int("w", profile, &w, DEFAULT_W, ss);
63 if (chunk_mapping.size() > 0 && (int)chunk_mapping.size() != k + m) {
64 *ss << "mapping " << profile.find("mapping")->second
65 << " maps " << chunk_mapping.size() << " chunks instead of"
66 << " the expected " << k + m << " and will be ignored" << std::endl;
67 chunk_mapping.clear();
70 err |= sanity_check_k(k, ss);
74 unsigned int ErasureCodeJerasure::get_chunk_size(unsigned int object_size) const
76 unsigned alignment = get_alignment();
77 if (per_chunk_alignment) {
78 unsigned chunk_size = object_size / k;
81 dout(20) << "get_chunk_size: chunk_size " << chunk_size
82 << " must be modulo " << alignment << dendl;
83 assert(alignment <= chunk_size);
84 unsigned modulo = chunk_size % alignment;
86 dout(10) << "get_chunk_size: " << chunk_size
87 << " padded to " << chunk_size + alignment - modulo << dendl;
88 chunk_size += alignment - modulo;
92 unsigned tail = object_size % alignment;
93 unsigned padded_length = object_size + ( tail ? ( alignment - tail ) : 0 );
94 assert(padded_length % k == 0);
95 return padded_length / k;
99 int ErasureCodeJerasure::encode_chunks(const set<int> &want_to_encode,
100 map<int, bufferlist> *encoded)
103 for (int i = 0; i < k + m; i++)
104 chunks[i] = (*encoded)[i].c_str();
105 jerasure_encode(&chunks[0], &chunks[k], (*encoded)[0].length());
109 int ErasureCodeJerasure::decode_chunks(const set<int> &want_to_read,
110 const map<int, bufferlist> &chunks,
111 map<int, bufferlist> *decoded)
113 unsigned blocksize = (*chunks.begin()).second.length();
114 int erasures[k + m + 1];
115 int erasures_count = 0;
118 for (int i = 0; i < k + m; i++) {
119 if (chunks.find(i) == chunks.end()) {
120 erasures[erasures_count] = i;
124 data[i] = (*decoded)[i].c_str();
126 coding[i - k] = (*decoded)[i].c_str();
128 erasures[erasures_count] = -1;
130 assert(erasures_count > 0);
131 return jerasure_decode(erasures, data, coding, blocksize);
134 bool ErasureCodeJerasure::is_prime(int value)
137 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
138 73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,
139 151,157,163,167,173,179,
140 181,191,193,197,199,211,223,227,229,233,239,241,251,257
143 for (i = 0; i < 55; i++)
144 if (value == prime55[i])
150 // ErasureCodeJerasureReedSolomonVandermonde
152 void ErasureCodeJerasureReedSolomonVandermonde::jerasure_encode(char **data,
156 jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize);
159 int ErasureCodeJerasureReedSolomonVandermonde::jerasure_decode(int *erasures,
164 return jerasure_matrix_decode(k, m, w, matrix, 1,
165 erasures, data, coding, blocksize);
168 unsigned ErasureCodeJerasureReedSolomonVandermonde::get_alignment() const
170 if (per_chunk_alignment) {
171 return w * LARGEST_VECTOR_WORDSIZE;
173 unsigned alignment = k*w*sizeof(int);
174 if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
175 alignment = k*w*LARGEST_VECTOR_WORDSIZE;
180 int ErasureCodeJerasureReedSolomonVandermonde::parse(ErasureCodeProfile &profile,
184 err |= ErasureCodeJerasure::parse(profile, ss);
185 if (w != 8 && w != 16 && w != 32) {
186 *ss << "ReedSolomonVandermonde: w=" << w
187 << " must be one of {8, 16, 32} : revert to " << DEFAULT_W << std::endl;
189 err |= to_int("w", profile, &w, DEFAULT_W, ss);
192 err |= to_bool("jerasure-per-chunk-alignment", profile,
193 &per_chunk_alignment, "false", ss);
197 void ErasureCodeJerasureReedSolomonVandermonde::prepare()
199 matrix = reed_sol_vandermonde_coding_matrix(k, m, w);
203 // ErasureCodeJerasureReedSolomonRAID6
205 void ErasureCodeJerasureReedSolomonRAID6::jerasure_encode(char **data,
209 reed_sol_r6_encode(k, w, data, coding, blocksize);
212 int ErasureCodeJerasureReedSolomonRAID6::jerasure_decode(int *erasures,
217 return jerasure_matrix_decode(k, m, w, matrix, 1, erasures, data, coding, blocksize);
220 unsigned ErasureCodeJerasureReedSolomonRAID6::get_alignment() const
222 if (per_chunk_alignment) {
223 return w * LARGEST_VECTOR_WORDSIZE;
225 unsigned alignment = k*w*sizeof(int);
226 if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
227 alignment = k*w*LARGEST_VECTOR_WORDSIZE;
232 int ErasureCodeJerasureReedSolomonRAID6::parse(ErasureCodeProfile &profile,
235 int err = ErasureCodeJerasure::parse(profile, ss);
238 if (w != 8 && w != 16 && w != 32) {
239 *ss << "ReedSolomonRAID6: w=" << w
240 << " must be one of {8, 16, 32} : revert to 8 " << std::endl;
242 err |= to_int("w", profile, &w, DEFAULT_W, ss);
248 void ErasureCodeJerasureReedSolomonRAID6::prepare()
250 matrix = reed_sol_r6_coding_matrix(k, w);
254 // ErasureCodeJerasureCauchy
256 void ErasureCodeJerasureCauchy::jerasure_encode(char **data,
260 jerasure_schedule_encode(k, m, w, schedule,
261 data, coding, blocksize, packetsize);
264 int ErasureCodeJerasureCauchy::jerasure_decode(int *erasures,
269 return jerasure_schedule_decode_lazy(k, m, w, bitmatrix,
270 erasures, data, coding, blocksize, packetsize, 1);
273 unsigned ErasureCodeJerasureCauchy::get_alignment() const
275 if (per_chunk_alignment) {
276 unsigned alignment = w * packetsize;
277 unsigned modulo = alignment % LARGEST_VECTOR_WORDSIZE;
279 alignment += LARGEST_VECTOR_WORDSIZE - modulo;
282 unsigned alignment = k*w*packetsize*sizeof(int);
283 if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
284 alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE;
289 int ErasureCodeJerasureCauchy::parse(ErasureCodeProfile &profile,
292 int err = ErasureCodeJerasure::parse(profile, ss);
293 err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
294 err |= to_bool("jerasure-per-chunk-alignment", profile,
295 &per_chunk_alignment, "false", ss);
299 void ErasureCodeJerasureCauchy::prepare_schedule(int *matrix)
301 bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
302 schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
306 // ErasureCodeJerasureCauchyOrig
308 void ErasureCodeJerasureCauchyOrig::prepare()
310 int *matrix = cauchy_original_coding_matrix(k, m, w);
311 prepare_schedule(matrix);
316 // ErasureCodeJerasureCauchyGood
318 void ErasureCodeJerasureCauchyGood::prepare()
320 int *matrix = cauchy_good_general_coding_matrix(k, m, w);
321 prepare_schedule(matrix);
326 // ErasureCodeJerasureLiberation
328 ErasureCodeJerasureLiberation::~ErasureCodeJerasureLiberation()
333 jerasure_free_schedule(schedule);
336 void ErasureCodeJerasureLiberation::jerasure_encode(char **data,
340 jerasure_schedule_encode(k, m, w, schedule, data,
341 coding, blocksize, packetsize);
344 int ErasureCodeJerasureLiberation::jerasure_decode(int *erasures,
349 return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data,
350 coding, blocksize, packetsize, 1);
353 unsigned ErasureCodeJerasureLiberation::get_alignment() const
355 unsigned alignment = k*w*packetsize*sizeof(int);
356 if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
357 alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE;
361 bool ErasureCodeJerasureLiberation::check_k(ostream *ss) const
364 *ss << "k=" << k << " must be less than or equal to w=" << w << std::endl;
371 bool ErasureCodeJerasureLiberation::check_w(ostream *ss) const
373 if (w <= 2 || !is_prime(w)) {
374 *ss << "w=" << w << " must be greater than two and be prime" << std::endl;
381 bool ErasureCodeJerasureLiberation::check_packetsize_set(ostream *ss) const
383 if (packetsize == 0) {
384 *ss << "packetsize=" << packetsize << " must be set" << std::endl;
391 bool ErasureCodeJerasureLiberation::check_packetsize(ostream *ss) const
393 if ((packetsize%(sizeof(int))) != 0) {
394 *ss << "packetsize=" << packetsize
395 << " must be a multiple of sizeof(int) = " << sizeof(int) << std::endl;
402 int ErasureCodeJerasureLiberation::revert_to_default(ErasureCodeProfile &profile,
406 *ss << "reverting to k=" << DEFAULT_K << ", w="
407 << DEFAULT_W << ", packetsize=" << DEFAULT_PACKETSIZE << std::endl;
408 profile["k"] = DEFAULT_K;
409 err |= to_int("k", profile, &k, DEFAULT_K, ss);
410 profile["w"] = DEFAULT_W;
411 err |= to_int("w", profile, &w, DEFAULT_W, ss);
412 profile["packetsize"] = DEFAULT_PACKETSIZE;
413 err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
417 int ErasureCodeJerasureLiberation::parse(ErasureCodeProfile &profile,
420 int err = ErasureCodeJerasure::parse(profile, ss);
421 err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
428 if (!check_packetsize_set(ss) || !check_packetsize(ss))
431 revert_to_default(profile, ss);
437 void ErasureCodeJerasureLiberation::prepare()
439 bitmatrix = liberation_coding_bitmatrix(k, w);
440 schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
444 // ErasureCodeJerasureBlaumRoth
446 bool ErasureCodeJerasureBlaumRoth::check_w(ostream *ss) const
448 // back in Firefly, w = 7 was the default and produced useable
449 // chunks. Tolerate this value for backward compatibility.
452 if (w <= 2 || !is_prime(w+1)) {
453 *ss << "w=" << w << " must be greater than two and "
454 << "w+1 must be prime" << std::endl;
461 void ErasureCodeJerasureBlaumRoth::prepare()
463 bitmatrix = blaum_roth_coding_bitmatrix(k, w);
464 schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
468 // ErasureCodeJerasureLiber8tion
470 int ErasureCodeJerasureLiber8tion::parse(ErasureCodeProfile &profile,
473 int err = ErasureCodeJerasure::parse(profile, ss);
475 err |= to_int("m", profile, &m, DEFAULT_M, ss);
477 err |= to_int("w", profile, &w, DEFAULT_W, ss);
478 err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
483 if (!check_packetsize_set(ss))
486 revert_to_default(profile, ss);
492 void ErasureCodeJerasureLiber8tion::prepare()
494 bitmatrix = liber8tion_coding_bitmatrix(k);
495 schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);