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 #include "crush/CrushWrapper.h"
  21 #include "osd/osd_types.h"
  22 extern "C" {
  23 #include "jerasure.h"
  24 #include "reed_sol.h"
  25 #include "galois.h"
  26 #include "cauchy.h"
  27 #include "liberation.h"
  28 }
  29
  30 #define LARGEST_VECTOR_WORDSIZE 16
  31
  32 #define dout_context g_ceph_context
  33 #define dout_subsys ceph_subsys_osd
  34 #undef dout_prefix
  35 #define dout_prefix _prefix(_dout)
  36
  37 static ostream& _prefix(std::ostream* _dout)
  38 {
  39   return *_dout << "ErasureCodeJerasure: ";
  40 }
  41
  42 int ErasureCodeJerasure::create_ruleset(const string &name,
  43                                         CrushWrapper &crush,
  44                                         ostream *ss) const
  45 {
  46   int ruleid = crush.add_simple_ruleset(name, ruleset_root, ruleset_failure_domain,
  47                                         "indep", pg_pool_t::TYPE_ERASURE, ss);
  48   if (ruleid < 0)
  49     return ruleid;
  50   else {
  51     crush.set_rule_mask_max_size(ruleid, get_chunk_count());
  52     return crush.get_rule_mask_ruleset(ruleid);
  53   }
  54 }
  55
  56 int ErasureCodeJerasure::init(ErasureCodeProfile& profile, ostream *ss)
  57 {
  58   int err = 0;
  59   dout(10) << "technique=" << technique << dendl;
  60   profile["technique"] = technique;
  61   err |= to_string("ruleset-root", profile,
  62                    &ruleset_root,
  63                    DEFAULT_RULESET_ROOT, ss);
  64   err |= to_string("ruleset-failure-domain", profile,
  65                    &ruleset_failure_domain,
  66                    DEFAULT_RULESET_FAILURE_DOMAIN, ss);
  67   err |= parse(profile, ss);
  68   if (err)
  69     return err;
  70   prepare();
  71   ErasureCode::init(profile, ss);
  72   return err;
  73 }
  74
  75 int ErasureCodeJerasure::parse(ErasureCodeProfile &profile,
  76                                ostream *ss)
  77 {
  78   int err = ErasureCode::parse(profile, ss);
  79   err |= to_int("k", profile, &k, DEFAULT_K, ss);
  80   err |= to_int("m", profile, &m, DEFAULT_M, ss);
  81   err |= to_int("w", profile, &w, DEFAULT_W, ss);
  82   if (chunk_mapping.size() > 0 && (int)chunk_mapping.size() != k + m) {
  83     *ss << "mapping " << profile.find("mapping")->second
  84         << " maps " << chunk_mapping.size() << " chunks instead of"
  85         << " the expected " << k + m << " and will be ignored" << std::endl;
  86     chunk_mapping.clear();
  87     err = -EINVAL;
  88   }
  89   err |= sanity_check_k(k, ss);
  90   return err;
  91 }
  92
  93 unsigned int ErasureCodeJerasure::get_chunk_size(unsigned int object_size) const
  94 {
  95   unsigned alignment = get_alignment();
  96   if (per_chunk_alignment) {
  97     unsigned chunk_size = object_size / k;
  98     if (object_size % k)
  99       chunk_size++;
 100     dout(20) << "get_chunk_size: chunk_size " << chunk_size
 101              << " must be modulo " << alignment << dendl;
 102     assert(alignment <= chunk_size);
 103     unsigned modulo = chunk_size % alignment;
 104     if (modulo) {
 105       dout(10) << "get_chunk_size: " << chunk_size
 106                << " padded to " << chunk_size + alignment - modulo << dendl;
 107       chunk_size += alignment - modulo;
 108     }
 109     return chunk_size;
 110   } else {
 111     unsigned tail = object_size % alignment;
 112     unsigned padded_length = object_size + ( tail ?  ( alignment - tail ) : 0 );
 113     assert(padded_length % k == 0);
 114     return padded_length / k;
 115   }
 116 }
 117
 118 int ErasureCodeJerasure::encode_chunks(const set<int> &want_to_encode,
 119                                        map<int, bufferlist> *encoded)
 120 {
 121   char *chunks[k + m];
 122   for (int i = 0; i < k + m; i++)
 123     chunks[i] = (*encoded)[i].c_str();
 124   jerasure_encode(&chunks[0], &chunks[k], (*encoded)[0].length());
 125   return 0;
 126 }
 127
 128 int ErasureCodeJerasure::decode_chunks(const set<int> &want_to_read,
 129                                        const map<int, bufferlist> &chunks,
 130                                        map<int, bufferlist> *decoded)
 131 {
 132   unsigned blocksize = (*chunks.begin()).second.length();
 133   int erasures[k + m + 1];
 134   int erasures_count = 0;
 135   char *data[k];
 136   char *coding[m];
 137   for (int i =  0; i < k + m; i++) {
 138     if (chunks.find(i) == chunks.end()) {
 139       erasures[erasures_count] = i;
 140       erasures_count++;
 141     }
 142     if (i < k)
 143       data[i] = (*decoded)[i].c_str();
 144     else
 145       coding[i - k] = (*decoded)[i].c_str();
 146   }
 147   erasures[erasures_count] = -1;
 148
 149   assert(erasures_count > 0);
 150   return jerasure_decode(erasures, data, coding, blocksize);
 151 }
 152
 153 bool ErasureCodeJerasure::is_prime(int value)
 154 {
 155   int prime55[] = {
 156     2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
 157     73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,
 158     151,157,163,167,173,179,
 159     181,191,193,197,199,211,223,227,229,233,239,241,251,257
 160   };
 161   int i;
 162   for (i = 0; i < 55; i++)
 163     if (value == prime55[i])
 164       return true;
 165   return false;
 166 }
 167
 168 //
 169 // ErasureCodeJerasureReedSolomonVandermonde
 170 //
 171 void ErasureCodeJerasureReedSolomonVandermonde::jerasure_encode(char **data,
 172                                                                 char **coding,
 173                                                                 int blocksize)
 174 {
 175   jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize);
 176 }
 177
 178 int ErasureCodeJerasureReedSolomonVandermonde::jerasure_decode(int *erasures,
 179                                                                 char **data,
 180                                                                 char **coding,
 181                                                                 int blocksize)
 182 {
 183   return jerasure_matrix_decode(k, m, w, matrix, 1,
 184                                 erasures, data, coding, blocksize);
 185 }
 186
 187 unsigned ErasureCodeJerasureReedSolomonVandermonde::get_alignment() const
 188 {
 189   if (per_chunk_alignment) {
 190     return w * LARGEST_VECTOR_WORDSIZE;
 191   } else {
 192     unsigned alignment = k*w*sizeof(int);
 193     if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 194       alignment = k*w*LARGEST_VECTOR_WORDSIZE;
 195     return alignment;
 196   }
 197 }
 198
 199 int ErasureCodeJerasureReedSolomonVandermonde::parse(ErasureCodeProfile &profile,
 200                                                      ostream *ss)
 201 {
 202   int err = 0;
 203   err |= ErasureCodeJerasure::parse(profile, ss);
 204   if (w != 8 && w != 16 && w != 32) {
 205     *ss << "ReedSolomonVandermonde: w=" << w
 206         << " must be one of {8, 16, 32} : revert to " << DEFAULT_W << std::endl;
 207     profile["w"] = "8";
 208     err |= to_int("w", profile, &w, DEFAULT_W, ss);
 209     err = -EINVAL;
 210   }
 211   err |= to_bool("jerasure-per-chunk-alignment", profile,
 212                  &per_chunk_alignment, "false", ss);
 213   return err;
 214 }
 215
 216 void ErasureCodeJerasureReedSolomonVandermonde::prepare()
 217 {
 218   matrix = reed_sol_vandermonde_coding_matrix(k, m, w);
 219 }
 220
 221 //
 222 // ErasureCodeJerasureReedSolomonRAID6
 223 //
 224 void ErasureCodeJerasureReedSolomonRAID6::jerasure_encode(char **data,
 225                                                                 char **coding,
 226                                                                 int blocksize)
 227 {
 228   reed_sol_r6_encode(k, w, data, coding, blocksize);
 229 }
 230
 231 int ErasureCodeJerasureReedSolomonRAID6::jerasure_decode(int *erasures,
 232                                                          char **data,
 233                                                          char **coding,
 234                                                          int blocksize)
 235 {
 236   return jerasure_matrix_decode(k, m, w, matrix, 1, erasures, data, coding, blocksize);
 237 }
 238
 239 unsigned ErasureCodeJerasureReedSolomonRAID6::get_alignment() const
 240 {
 241   if (per_chunk_alignment) {
 242     return w * LARGEST_VECTOR_WORDSIZE;
 243   } else {
 244     unsigned alignment = k*w*sizeof(int);
 245     if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 246       alignment = k*w*LARGEST_VECTOR_WORDSIZE;
 247     return alignment;
 248   }
 249 }
 250
 251 int ErasureCodeJerasureReedSolomonRAID6::parse(ErasureCodeProfile &profile,
 252                                                ostream *ss)
 253 {
 254   int err = ErasureCodeJerasure::parse(profile, ss);
 255   profile.erase("m");
 256   m = 2;
 257   if (w != 8 && w != 16 && w != 32) {
 258     *ss << "ReedSolomonRAID6: w=" << w
 259         << " must be one of {8, 16, 32} : revert to 8 " << std::endl;
 260     profile["w"] = "8";
 261     err |= to_int("w", profile, &w, DEFAULT_W, ss);
 262     err = -EINVAL;
 263   }
 264   return err;
 265 }
 266
 267 void ErasureCodeJerasureReedSolomonRAID6::prepare()
 268 {
 269   matrix = reed_sol_r6_coding_matrix(k, w);
 270 }
 271
 272 //
 273 // ErasureCodeJerasureCauchy
 274 //
 275 void ErasureCodeJerasureCauchy::jerasure_encode(char **data,
 276                                                 char **coding,
 277                                                 int blocksize)
 278 {
 279   jerasure_schedule_encode(k, m, w, schedule,
 280                            data, coding, blocksize, packetsize);
 281 }
 282
 283 int ErasureCodeJerasureCauchy::jerasure_decode(int *erasures,
 284                                                char **data,
 285                                                char **coding,
 286                                                int blocksize)
 287 {
 288   return jerasure_schedule_decode_lazy(k, m, w, bitmatrix,
 289                                        erasures, data, coding, blocksize, packetsize, 1);
 290 }
 291
 292 unsigned ErasureCodeJerasureCauchy::get_alignment() const
 293 {
 294   if (per_chunk_alignment) {
 295     unsigned alignment = w * packetsize;
 296     unsigned modulo = alignment % LARGEST_VECTOR_WORDSIZE;
 297     if (modulo)
 298       alignment += LARGEST_VECTOR_WORDSIZE - modulo;
 299     return alignment;
 300   } else {
 301     unsigned alignment = k*w*packetsize*sizeof(int);
 302     if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 303       alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE;
 304     return alignment;
 305   }
 306 }
 307
 308 int ErasureCodeJerasureCauchy::parse(ErasureCodeProfile &profile,
 309                                      ostream *ss)
 310 {
 311   int err = ErasureCodeJerasure::parse(profile, ss);
 312   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 313   err |= to_bool("jerasure-per-chunk-alignment", profile,
 314                  &per_chunk_alignment, "false", ss);
 315   return err;
 316 }
 317
 318 void ErasureCodeJerasureCauchy::prepare_schedule(int *matrix)
 319 {
 320   bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
 321   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 322 }
 323
 324 //
 325 // ErasureCodeJerasureCauchyOrig
 326 //
 327 void ErasureCodeJerasureCauchyOrig::prepare()
 328 {
 329   int *matrix = cauchy_original_coding_matrix(k, m, w);
 330   prepare_schedule(matrix);
 331   free(matrix);
 332 }
 333
 334 //
 335 // ErasureCodeJerasureCauchyGood
 336 //
 337 void ErasureCodeJerasureCauchyGood::prepare()
 338 {
 339   int *matrix = cauchy_good_general_coding_matrix(k, m, w);
 340   prepare_schedule(matrix);
 341   free(matrix);
 342 }
 343
 344 //
 345 // ErasureCodeJerasureLiberation
 346 //
 347 ErasureCodeJerasureLiberation::~ErasureCodeJerasureLiberation()
 348 {
 349   if (bitmatrix)
 350     free(bitmatrix);
 351   if (schedule)
 352     jerasure_free_schedule(schedule);
 353 }
 354
 355 void ErasureCodeJerasureLiberation::jerasure_encode(char **data,
 356                                                     char **coding,
 357                                                     int blocksize)
 358 {
 359   jerasure_schedule_encode(k, m, w, schedule, data,
 360                            coding, blocksize, packetsize);
 361 }
 362
 363 int ErasureCodeJerasureLiberation::jerasure_decode(int *erasures,
 364                                                     char **data,
 365                                                     char **coding,
 366                                                     int blocksize)
 367 {
 368   return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data,
 369                                        coding, blocksize, packetsize, 1);
 370 }
 371
 372 unsigned ErasureCodeJerasureLiberation::get_alignment() const
 373 {
 374   unsigned alignment = k*w*packetsize*sizeof(int);
 375   if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) )
 376     alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE;
 377   return alignment;
 378 }
 379
 380 bool ErasureCodeJerasureLiberation::check_k(ostream *ss) const
 381 {
 382   if (k > w) {
 383     *ss << "k=" << k << " must be less than or equal to w=" << w << std::endl;
 384     return false;
 385   } else {
 386     return true;
 387   }
 388 }
 389
 390 bool ErasureCodeJerasureLiberation::check_w(ostream *ss) const
 391 {
 392   if (w <= 2 || !is_prime(w)) {
 393     *ss <<  "w=" << w << " must be greater than two and be prime" << std::endl;
 394     return false;
 395   } else {
 396     return true;
 397   }
 398 }
 399
 400 bool ErasureCodeJerasureLiberation::check_packetsize_set(ostream *ss) const
 401 {
 402   if (packetsize == 0) {
 403     *ss << "packetsize=" << packetsize << " must be set" << std::endl;
 404     return false;
 405   } else {
 406     return true;
 407   }
 408 }
 409
 410 bool ErasureCodeJerasureLiberation::check_packetsize(ostream *ss) const
 411 {
 412   if ((packetsize%(sizeof(int))) != 0) {
 413     *ss << "packetsize=" << packetsize
 414         << " must be a multiple of sizeof(int) = " << sizeof(int) << std::endl;
 415     return false;
 416   } else {
 417     return true;
 418   }
 419 }
 420
 421 int ErasureCodeJerasureLiberation::revert_to_default(ErasureCodeProfile &profile,
 422                                                      ostream *ss)
 423 {
 424   int err = 0;
 425   *ss << "reverting to k=" << DEFAULT_K << ", w="
 426       << DEFAULT_W << ", packetsize=" << DEFAULT_PACKETSIZE << std::endl;
 427   profile["k"] = DEFAULT_K;
 428   err |= to_int("k", profile, &k, DEFAULT_K, ss);
 429   profile["w"] = DEFAULT_W;
 430   err |= to_int("w", profile, &w, DEFAULT_W, ss);
 431   profile["packetsize"] = DEFAULT_PACKETSIZE;
 432   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 433   return err;
 434 }
 435
 436 int ErasureCodeJerasureLiberation::parse(ErasureCodeProfile &profile,
 437                                          ostream *ss)
 438 {
 439   int err = ErasureCodeJerasure::parse(profile, ss);
 440   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 441
 442   bool error = false;
 443   if (!check_k(ss))
 444     error = true;
 445   if (!check_w(ss))
 446     error = true;
 447   if (!check_packetsize_set(ss) || !check_packetsize(ss))
 448     error = true;
 449   if (error) {
 450     revert_to_default(profile, ss);
 451     err = -EINVAL;
 452   }
 453   return err;
 454 }
 455
 456 void ErasureCodeJerasureLiberation::prepare()
 457 {
 458   bitmatrix = liberation_coding_bitmatrix(k, w);
 459   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 460 }
 461
 462 //
 463 // ErasureCodeJerasureBlaumRoth
 464 //
 465 bool ErasureCodeJerasureBlaumRoth::check_w(ostream *ss) const
 466 {
 467   // back in Firefly, w = 7 was the default and produced useable
 468   // chunks. Tolerate this value for backward compatibility.
 469   if (w == 7)
 470     return true;
 471   if (w <= 2 || !is_prime(w+1)) {
 472     *ss <<  "w=" << w << " must be greater than two and "
 473         << "w+1 must be prime" << std::endl;
 474     return false;
 475   } else {
 476     return true;
 477   }
 478 }
 479
 480 void ErasureCodeJerasureBlaumRoth::prepare()
 481 {
 482   bitmatrix = blaum_roth_coding_bitmatrix(k, w);
 483   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 484 }
 485
 486 //
 487 // ErasureCodeJerasureLiber8tion
 488 //
 489 int ErasureCodeJerasureLiber8tion::parse(ErasureCodeProfile &profile,
 490                                          ostream *ss)
 491 {
 492   int err = ErasureCodeJerasure::parse(profile, ss);
 493   profile.erase("m");
 494   err |= to_int("m", profile, &m, DEFAULT_M, ss);
 495   profile.erase("w");
 496   err |= to_int("w", profile, &w, DEFAULT_W, ss);
 497   err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss);
 498
 499   bool error = false;
 500   if (!check_k(ss))
 501     error = true;
 502   if (!check_packetsize_set(ss))
 503     error = true;
 504   if (error) {
 505     revert_to_default(profile, ss);
 506     err = -EINVAL;
 507   }
 508   return err;
 509 }
 510
 511 void ErasureCodeJerasureLiber8tion::prepare()
 512 {
 513   bitmatrix = liber8tion_coding_bitmatrix(k);
 514   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 515 }