ceph/src/erasure-code/jerasure/ErasureCodeJerasure.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph distributed storage system
   5  *
   6  * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com>
   7  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   8  *
   9  * Author: Loic Dachary <loic@dachary.org>
  10  *
  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.
  15  *
  16  */
  17
  18 #include "common/debug.h"
  19 #include "ErasureCodeJerasure.h"
  20
  21 using namespace std;
  22
  23 extern "C" {
  24 #include "jerasure.h"
  25 #include "reed_sol.h"
  26 #include "galois.h"
  27 #include "cauchy.h"
  28 #include "liberation.h"
  29 }
  30
  31 #define LARGEST_VECTOR_WORDSIZE 16
  32
  33 #define dout_context g_ceph_context
  34 #define dout_subsys ceph_subsys_osd
  35 #undef dout_prefix
  36 #define dout_prefix _prefix(_dout)
  37
  38 static ostream& _prefix(std::ostream* _dout)
  39 {
  40   return *_dout << "ErasureCodeJerasure: ";
  41 }
  42
  43
  44 int ErasureCodeJerasure::init(ErasureCodeProfile& profile, ostream *ss)
  45 {
  46   int err = 0;
  47   dout(10) << "technique=" << technique << dendl;
  48   profile["technique"] = technique;
  49   err |= parse(profile, ss);
  50   if (err)
  51     return err;
  52   prepare();
  53   return ErasureCode::init(profile, ss);
  54 }
  55
  56 int ErasureCodeJerasure::parse(ErasureCodeProfile &profile,
  57                                ostream *ss)
  58 {
  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();
  68     err = -EINVAL;
  69   }
  70   err |= sanity_check_k(k, ss);
  71   return err;
  72 }
  73
  74 unsigned int ErasureCodeJerasure::get_chunk_size(unsigned int object_size) const
  75 {
  76   unsigned alignment = get_alignment();
  77   if (per_chunk_alignment) {
  78     unsigned chunk_size = object_size / k;
  79     if (object_size % k)
  80       chunk_size++;
  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;
  85     if (modulo) {
  86       dout(10) << "get_chunk_size: " << chunk_size
  87                << " padded to " << chunk_size + alignment - modulo << dendl;
  88       chunk_size += alignment - modulo;
  89     }
  90     return chunk_size;
  91   } else {
  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;
  96   }
  97 }
  98
  99 int ErasureCodeJerasure::encode_chunks(const set<int> &want_to_encode,
 100                                        map<int, bufferlist> *encoded)
 101 {
 102   char *chunks[k + m];
 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());
 106   return 0;
 107 }
 108
 109 int ErasureCodeJerasure::decode_chunks(const set<int> &want_to_read,
 110                                        const map<int, bufferlist> &chunks,
 111                                        map<int, bufferlist> *decoded)
 112 {
 113   unsigned blocksize = (*chunks.begin()).second.length();
 114   int erasures[k + m + 1];
 115   int erasures_count = 0;
 116   char *data[k];
 117   char *coding[m];
 118   for (int i =  0; i < k + m; i++) {
 119     if (chunks.find(i) == chunks.end()) {
 120       erasures[erasures_count] = i;
 121       erasures_count++;
 122     }
 123     if (i < k)
 124       data[i] = (*decoded)[i].c_str();
 125     else
 126       coding[i - k] = (*decoded)[i].c_str();
 127   }
 128   erasures[erasures_count] = -1;
 129
 130   assert(erasures_count > 0);
 131   return jerasure_decode(erasures, data, coding, blocksize);
 132 }
 133
 134 bool ErasureCodeJerasure::is_prime(int value)
 135 {
 136   int prime55[] = {
 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
 141   };
 142   int i;
 143   for (i = 0; i < 55; i++)
 144     if (value == prime55[i])
 145       return true;
 146   return false;
 147 }
 148
 149 //
 150 // ErasureCodeJerasureReedSolomonVandermonde
 151 //
 152 void ErasureCodeJerasureReedSolomonVandermonde::jerasure_encode(char **data,
 153                                                                 char **coding,
 154                                                                 int blocksize)
 155 {
 156   jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize);
 157 }
 158
 159 int ErasureCodeJerasureReedSolomonVandermonde::jerasure_decode(int *erasures,
 160                                                                 char **data,
 161                                                                 char **coding,
 162                                                                 int blocksize)
 163 {
 164   return jerasure_matrix_decode(k, m, w, matrix, 1,
 165                                 erasures, data, coding, blocksize);
 166 }
 167
 168 unsigned ErasureCodeJerasureReedSolomonVandermonde::get_alignment() const
 169 {
 170   if (per_chunk_alignment) {
 171     return w * LARGEST_VECTOR_WORDSIZE;
 172   } else {
 173     unsigned alignment = k*w*sizeof(int);
 174     if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 175       alignment = k*w*LARGEST_VECTOR_WORDSIZE;
 176     return alignment;
 177   }
 178 }
 179
 180 int ErasureCodeJerasureReedSolomonVandermonde::parse(ErasureCodeProfile &profile,
 181                                                      ostream *ss)
 182 {
 183   int err = 0;
 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;
 188     profile["w"] = "8";
 189     err |= to_int("w", profile, &w, DEFAULT_W, ss);
 190     err = -EINVAL;
 191   }
 192   err |= to_bool("jerasure-per-chunk-alignment", profile,
 193                  &per_chunk_alignment, "false", ss);
 194   return err;
 195 }
 196
 197 void ErasureCodeJerasureReedSolomonVandermonde::prepare()
 198 {
 199   matrix = reed_sol_vandermonde_coding_matrix(k, m, w);
 200 }
 201
 202 //
 203 // ErasureCodeJerasureReedSolomonRAID6
 204 //
 205 void ErasureCodeJerasureReedSolomonRAID6::jerasure_encode(char **data,
 206                                                                 char **coding,
 207                                                                 int blocksize)
 208 {
 209   reed_sol_r6_encode(k, w, data, coding, blocksize);
 210 }
 211
 212 int ErasureCodeJerasureReedSolomonRAID6::jerasure_decode(int *erasures,
 213                                                          char **data,
 214                                                          char **coding,
 215                                                          int blocksize)
 216 {
 217   return jerasure_matrix_decode(k, m, w, matrix, 1, erasures, data, coding, blocksize);
 218 }
 219
 220 unsigned ErasureCodeJerasureReedSolomonRAID6::get_alignment() const
 221 {
 222   if (per_chunk_alignment) {
 223     return w * LARGEST_VECTOR_WORDSIZE;
 224   } else {
 225     unsigned alignment = k*w*sizeof(int);
 226     if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 227       alignment = k*w*LARGEST_VECTOR_WORDSIZE;
 228     return alignment;
 229   }
 230 }
 231
 232 int ErasureCodeJerasureReedSolomonRAID6::parse(ErasureCodeProfile &profile,
 233                                                ostream *ss)
 234 {
 235   int err = ErasureCodeJerasure::parse(profile, ss);
 236   profile.erase("m");
 237   m = 2;
 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;
 241     profile["w"] = "8";
 242     err |= to_int("w", profile, &w, DEFAULT_W, ss);
 243     err = -EINVAL;
 244   }
 245   return err;
 246 }
 247
 248 void ErasureCodeJerasureReedSolomonRAID6::prepare()
 249 {
 250   matrix = reed_sol_r6_coding_matrix(k, w);
 251 }
 252
 253 //
 254 // ErasureCodeJerasureCauchy
 255 //
 256 void ErasureCodeJerasureCauchy::jerasure_encode(char **data,
 257                                                 char **coding,
 258                                                 int blocksize)
 259 {
 260   jerasure_schedule_encode(k, m, w, schedule,
 261                            data, coding, blocksize, packetsize);
 262 }
 263
 264 int ErasureCodeJerasureCauchy::jerasure_decode(int *erasures,
 265                                                char **data,
 266                                                char **coding,
 267                                                int blocksize)
 268 {
 269   return jerasure_schedule_decode_lazy(k, m, w, bitmatrix,
 270                                        erasures, data, coding, blocksize, packetsize, 1);
 271 }
 272
 273 unsigned ErasureCodeJerasureCauchy::get_alignment() const
 274 {
 275   if (per_chunk_alignment) {
 276     unsigned alignment = w * packetsize;
 277     unsigned modulo = alignment % LARGEST_VECTOR_WORDSIZE;
 278     if (modulo)
 279       alignment += LARGEST_VECTOR_WORDSIZE - modulo;
 280     return alignment;
 281   } else {
 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;
 285     return alignment;
 286   }
 287 }
 288
 289 int ErasureCodeJerasureCauchy::parse(ErasureCodeProfile &profile,
 290                                      ostream *ss)
 291 {
 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);
 296   return err;
 297 }
 298
 299 void ErasureCodeJerasureCauchy::prepare_schedule(int *matrix)
 300 {
 301   bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
 302   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 303 }
 304
 305 //
 306 // ErasureCodeJerasureCauchyOrig
 307 //
 308 void ErasureCodeJerasureCauchyOrig::prepare()
 309 {
 310   int *matrix = cauchy_original_coding_matrix(k, m, w);
 311   prepare_schedule(matrix);
 312   free(matrix);
 313 }
 314
 315 //
 316 // ErasureCodeJerasureCauchyGood
 317 //
 318 void ErasureCodeJerasureCauchyGood::prepare()
 319 {
 320   int *matrix = cauchy_good_general_coding_matrix(k, m, w);
 321   prepare_schedule(matrix);
 322   free(matrix);
 323 }
 324
 325 //
 326 // ErasureCodeJerasureLiberation
 327 //
 328 ErasureCodeJerasureLiberation::~ErasureCodeJerasureLiberation()
 329 {
 330   if (bitmatrix)
 331     free(bitmatrix);
 332   if (schedule)
 333     jerasure_free_schedule(schedule);
 334 }
 335
 336 void ErasureCodeJerasureLiberation::jerasure_encode(char **data,
 337                                                     char **coding,
 338                                                     int blocksize)
 339 {
 340   jerasure_schedule_encode(k, m, w, schedule, data,
 341                            coding, blocksize, packetsize);
 342 }
 343
 344 int ErasureCodeJerasureLiberation::jerasure_decode(int *erasures,
 345                                                     char **data,
 346                                                     char **coding,
 347                                                     int blocksize)
 348 {
 349   return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data,
 350                                        coding, blocksize, packetsize, 1);
 351 }
 352
 353 unsigned ErasureCodeJerasureLiberation::get_alignment() const
 354 {
 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;
 358   return alignment;
 359 }
 360
 361 bool ErasureCodeJerasureLiberation::check_k(ostream *ss) const
 362 {
 363   if (k > w) {
 364     *ss << "k=" << k << " must be less than or equal to w=" << w << std::endl;
 365     return false;
 366   } else {
 367     return true;
 368   }
 369 }
 370
 371 bool ErasureCodeJerasureLiberation::check_w(ostream *ss) const
 372 {
 373   if (w <= 2 || !is_prime(w)) {
 374     *ss <<  "w=" << w << " must be greater than two and be prime" << std::endl;
 375     return false;
 376   } else {
 377     return true;
 378   }
 379 }
 380
 381 bool ErasureCodeJerasureLiberation::check_packetsize_set(ostream *ss) const
 382 {
 383   if (packetsize == 0) {
 384     *ss << "packetsize=" << packetsize << " must be set" << std::endl;
 385     return false;
 386   } else {
 387     return true;
 388   }
 389 }
 390
 391 bool ErasureCodeJerasureLiberation::check_packetsize(ostream *ss) const
 392 {
 393   if ((packetsize%(sizeof(int))) != 0) {
 394     *ss << "packetsize=" << packetsize
 395         << " must be a multiple of sizeof(int) = " << sizeof(int) << std::endl;
 396     return false;
 397   } else {
 398     return true;
 399   }
 400 }
 401
 402 int ErasureCodeJerasureLiberation::revert_to_default(ErasureCodeProfile &profile,
 403                                                      ostream *ss)
 404 {
 405   int err = 0;
 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);
 414   return err;
 415 }
 416
 417 int ErasureCodeJerasureLiberation::parse(ErasureCodeProfile &profile,
 418                                          ostream *ss)
 419 {
 420   int err = ErasureCodeJerasure::parse(profile, ss);
 421   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 422
 423   bool error = false;
 424   if (!check_k(ss))
 425     error = true;
 426   if (!check_w(ss))
 427     error = true;
 428   if (!check_packetsize_set(ss) || !check_packetsize(ss))
 429     error = true;
 430   if (error) {
 431     revert_to_default(profile, ss);
 432     err = -EINVAL;
 433   }
 434   return err;
 435 }
 436
 437 void ErasureCodeJerasureLiberation::prepare()
 438 {
 439   bitmatrix = liberation_coding_bitmatrix(k, w);
 440   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 441 }
 442
 443 //
 444 // ErasureCodeJerasureBlaumRoth
 445 //
 446 bool ErasureCodeJerasureBlaumRoth::check_w(ostream *ss) const
 447 {
 448   // back in Firefly, w = 7 was the default and produced useable
 449   // chunks. Tolerate this value for backward compatibility.
 450   if (w == 7)
 451     return true;
 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;
 455     return false;
 456   } else {
 457     return true;
 458   }
 459 }
 460
 461 void ErasureCodeJerasureBlaumRoth::prepare()
 462 {
 463   bitmatrix = blaum_roth_coding_bitmatrix(k, w);
 464   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 465 }
 466
 467 //
 468 // ErasureCodeJerasureLiber8tion
 469 //
 470 int ErasureCodeJerasureLiber8tion::parse(ErasureCodeProfile &profile,
 471                                          ostream *ss)
 472 {
 473   int err = ErasureCodeJerasure::parse(profile, ss);
 474   profile.erase("m");
 475   err |= to_int("m", profile, &m, DEFAULT_M, ss);
 476   profile.erase("w");
 477   err |= to_int("w", profile, &w, DEFAULT_W, ss);
 478   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 479
 480   bool error = false;
 481   if (!check_k(ss))
 482     error = true;
 483   if (!check_packetsize_set(ss))
 484     error = true;
 485   if (error) {
 486     revert_to_default(profile, ss);
 487     err = -EINVAL;
 488   }
 489   return err;
 490 }
 491
 492 void ErasureCodeJerasureLiber8tion::prepare()
 493 {
 494   bitmatrix = liber8tion_coding_bitmatrix(k);
 495   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 496 }