ceph/src/erasure-code/shec/ErasureCodeShec.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 - scalable distributed file system
   5  *
   6  * Copyright (C) 2014 FUJITSU LIMITED
   7  * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com>
   8  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   9  *
  10  * Author: Takanori Nakao <nakao.takanori@jp.fujitsu.com>
  11  * Author: Takeshi Miyamae <miyamae.takeshi@jp.fujitsu.com>
  12  * Author: Loic Dachary <loic@dachary.org>
  13  *
  14  *  This library is free software; you can redistribute it and/or
  15  *  modify it under the terms of the GNU Lesser General Public
  16  *  License as published by the Free Software Foundation; either
  17  *  version 2.1 of the License, or (at your option) any later version.
  18  *
  19  */
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <algorithm>
  26 using namespace std;
  27
  28 #include "common/debug.h"
  29 #include "ErasureCodeShec.h"
  30 #include "crush/CrushWrapper.h"
  31 #include "osd/osd_types.h"
  32 extern "C" {
  33 #include "jerasure/include/jerasure.h"
  34 #include "jerasure/include/galois.h"
  35
  36 extern int calc_determinant(int *matrix, int dim);
  37 extern int* reed_sol_vandermonde_coding_matrix(int k, int m, int w);
  38 }
  39
  40 #define dout_context g_ceph_context
  41 #define dout_subsys ceph_subsys_osd
  42 #undef dout_prefix
  43 #define dout_prefix _prefix(_dout)
  44
  45 static ostream& _prefix(std::ostream* _dout)
  46 {
  47   return *_dout << "ErasureCodeShec: ";
  48 }
  49
  50 int ErasureCodeShec::create_ruleset(const string &name,
  51                                     CrushWrapper &crush,
  52                                     ostream *ss) const
  53 {
  54   int ruleid = crush.add_simple_rule(
  55     name, ruleset_root, ruleset_failure_domain,
  56     "indep", pg_pool_t::TYPE_ERASURE, ss);
  57   if (ruleid < 0) {
  58     return ruleid;
  59   } else {
  60     crush.set_rule_mask_max_size(ruleid, get_chunk_count());
  61     return crush.get_rule_mask_ruleset(ruleid);
  62   }
  63 }
  64
  65 int ErasureCodeShec::init(ErasureCodeProfile &profile,
  66                           ostream *ss)
  67 {
  68   int err = 0;
  69   err |= ErasureCode::to_string("ruleset-root", profile,
  70                    &ruleset_root,
  71                    DEFAULT_RULESET_ROOT, ss);
  72   err |= ErasureCode::to_string("ruleset-failure-domain", profile,
  73                    &ruleset_failure_domain,
  74                    DEFAULT_RULESET_FAILURE_DOMAIN, ss);
  75   err |= parse(profile);
  76   if (err)
  77     return err;
  78   prepare();
  79   ErasureCode::init(profile, ss);
  80   return err;
  81 }
  82
  83 unsigned int ErasureCodeShec::get_chunk_size(unsigned int object_size) const
  84 {
  85   unsigned alignment = get_alignment();
  86   unsigned tail = object_size % alignment;
  87   unsigned padded_length = object_size + ( tail ?  ( alignment - tail ) : 0 );
  88
  89   assert(padded_length % k == 0);
  90   return padded_length / k;
  91 }
  92
  93 int ErasureCodeShec::minimum_to_decode(const set<int> &want_to_read,
  94                                        const set<int> &available_chunks,
  95                                        set<int> *minimum_chunks)
  96 {
  97   if (!minimum_chunks) return -EINVAL;
  98
  99   for (set<int>::iterator it = available_chunks.begin(); it != available_chunks.end(); ++it){
 100     if (*it < 0 || k+m <= *it) return -EINVAL;
 101   }
 102
 103   for (set<int>::iterator it = want_to_read.begin(); it != want_to_read.end(); ++it){
 104     if (*it < 0 || k+m <= *it) return -EINVAL;
 105   }
 106
 107   int want[k + m];
 108   int avails[k + m];
 109   int minimum[k + m];
 110
 111   memset(want, 0, sizeof(want));
 112   memset(avails, 0, sizeof(avails));
 113   memset(minimum, 0, sizeof(minimum));
 114   (*minimum_chunks).clear();
 115
 116   for (set<int>::const_iterator i = want_to_read.begin();
 117        i != want_to_read.end();
 118        ++i) {
 119     want[*i] = 1;
 120   }
 121
 122   for (set<int>::const_iterator i = available_chunks.begin();
 123        i != available_chunks.end();
 124        ++i) {
 125     avails[*i] = 1;
 126   }
 127
 128   {
 129     int decoding_matrix[k*k];
 130     int dm_row[k];
 131     int dm_column[k];
 132     memset(decoding_matrix, 0, sizeof(decoding_matrix));
 133     memset(dm_row, 0, sizeof(dm_row));
 134     memset(dm_column, 0, sizeof(dm_column));
 135     if (shec_make_decoding_matrix(true, want, avails, decoding_matrix, dm_row, dm_column, minimum) < 0) {
 136       return -EIO;
 137     }
 138   }
 139
 140   for (int i = 0; i < k + m; i++) {
 141     if (minimum[i] == 1) minimum_chunks->insert(i);
 142   }
 143
 144   return 0;
 145 }
 146
 147 int ErasureCodeShec::minimum_to_decode_with_cost(const set<int> &want_to_read,
 148                                                  const map<int, int> &available,
 149                                                  set<int> *minimum_chunks)
 150 {
 151   set <int> available_chunks;
 152
 153   for (map<int, int>::const_iterator i = available.begin();
 154        i != available.end();
 155        ++i)
 156     available_chunks.insert(i->first);
 157
 158   return minimum_to_decode(want_to_read, available_chunks, minimum_chunks);
 159 }
 160
 161 int ErasureCodeShec::encode(const set<int> &want_to_encode,
 162                             const bufferlist &in,
 163                             map<int, bufferlist> *encoded)
 164 {
 165   unsigned int k = get_data_chunk_count();
 166   unsigned int m = get_chunk_count() - k;
 167   bufferlist out;
 168
 169   if (!encoded || !encoded->empty()){
 170     return -EINVAL;
 171   }
 172
 173   int err = encode_prepare(in, *encoded);
 174   if (err)
 175     return err;
 176   encode_chunks(want_to_encode, encoded);
 177   for (unsigned int i = 0; i < k + m; i++) {
 178     if (want_to_encode.count(i) == 0)
 179       encoded->erase(i);
 180   }
 181   return 0;
 182 }
 183
 184 int ErasureCodeShec::encode_chunks(const set<int> &want_to_encode,
 185                                    map<int, bufferlist> *encoded)
 186 {
 187   char *chunks[k + m];
 188   for (int i = 0; i < k + m; i++){
 189     chunks[i] = (*encoded)[i].c_str();
 190   }
 191   shec_encode(&chunks[0], &chunks[k], (*encoded)[0].length());
 192   return 0;
 193 }
 194
 195 int ErasureCodeShec::decode(const set<int> &want_to_read,
 196                             const map<int, bufferlist> &chunks,
 197                             map<int, bufferlist> *decoded)
 198 {
 199   vector<int> have;
 200
 201   if (!decoded || !decoded->empty()){
 202     return -EINVAL;
 203   }
 204
 205   have.reserve(chunks.size());
 206   for (map<int, bufferlist>::const_iterator i = chunks.begin();
 207        i != chunks.end();
 208        ++i) {
 209     have.push_back(i->first);
 210   }
 211   if (includes(
 212         have.begin(), have.end(), want_to_read.begin(), want_to_read.end())) {
 213     for (set<int>::iterator i = want_to_read.begin();
 214          i != want_to_read.end();
 215          ++i) {
 216       (*decoded)[*i] = chunks.find(*i)->second;
 217     }
 218     return 0;
 219   }
 220   unsigned int k = get_data_chunk_count();
 221   unsigned int m = get_chunk_count() - k;
 222   unsigned blocksize = (*chunks.begin()).second.length();
 223   for (unsigned int i =  0; i < k + m; i++) {
 224     if (chunks.find(i) == chunks.end()) {
 225       bufferptr ptr(buffer::create_aligned(blocksize, SIMD_ALIGN));
 226       (*decoded)[i].push_front(ptr);
 227     } else {
 228       (*decoded)[i] = chunks.find(i)->second;
 229       (*decoded)[i].rebuild_aligned(SIMD_ALIGN);
 230     }
 231   }
 232   return decode_chunks(want_to_read, chunks, decoded);
 233 }
 234
 235 int ErasureCodeShec::decode_chunks(const set<int> &want_to_read,
 236                                    const map<int, bufferlist> &chunks,
 237                                    map<int, bufferlist> *decoded)
 238 {
 239   unsigned blocksize = (*chunks.begin()).second.length();
 240   int erased[k + m];
 241   int erased_count = 0;
 242   int avails[k + m];
 243   char *data[k];
 244   char *coding[m];
 245
 246   for (int i = 0; i < k + m; i++) {
 247     erased[i] = 0;
 248     if (chunks.find(i) == chunks.end()) {
 249       if (want_to_read.count(i) > 0) {
 250         erased[i] = 1;
 251         erased_count++;
 252       }
 253       avails[i] = 0;
 254     } else {
 255       avails[i] = 1;
 256     }
 257     if (i < k)
 258       data[i] = (*decoded)[i].c_str();
 259     else
 260       coding[i - k] = (*decoded)[i].c_str();
 261   }
 262
 263   if (erased_count > 0) {
 264     return shec_decode(erased, avails, data, coding, blocksize);
 265   } else {
 266     return 0;
 267   }
 268 }
 269
 270 //
 271 // ErasureCodeShecReedSolomonVandermonde
 272 //
 273
 274 void ErasureCodeShecReedSolomonVandermonde::shec_encode(char **data,
 275                                              char **coding,
 276                                              int blocksize)
 277 {
 278   jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize);
 279 }
 280
 281 int ErasureCodeShecReedSolomonVandermonde::shec_decode(int *erased,
 282                                             int *avails,
 283                                             char **data,
 284                                             char **coding,
 285                                             int blocksize)
 286 {
 287   return shec_matrix_decode(erased, avails, data, coding, blocksize);
 288 }
 289
 290 unsigned ErasureCodeShecReedSolomonVandermonde::get_alignment() const
 291 {
 292   return k*w*sizeof(int);
 293 }
 294
 295 int ErasureCodeShecReedSolomonVandermonde::parse(const ErasureCodeProfile &profile)
 296 {
 297   int err = 0;
 298   // k, m, c
 299   if (profile.find("k") == profile.end() &&
 300       profile.find("m") == profile.end() &&
 301       profile.find("c") == profile.end()){
 302     dout(10) << "(k, m, c) default to " << "(" << DEFAULT_K
 303              << ", " << DEFAULT_M << ", " << DEFAULT_C << ")" << dendl;
 304     k = DEFAULT_K; m = DEFAULT_M; c = DEFAULT_C;
 305   } else if (profile.find("k") == profile.end() ||
 306              profile.find("m") == profile.end() ||
 307              profile.find("c") == profile.end()){
 308     dout(10) << "(k, m, c) must be chosen" << dendl;
 309     err = -EINVAL;
 310   } else {
 311     std::string err_k, err_m, err_c, value_k, value_m, value_c;
 312     value_k = profile.find("k")->second;
 313     value_m = profile.find("m")->second;
 314     value_c = profile.find("c")->second;
 315     k = strict_strtol(value_k.c_str(), 10, &err_k);
 316     m = strict_strtol(value_m.c_str(), 10, &err_m);
 317     c = strict_strtol(value_c.c_str(), 10, &err_c);
 318
 319     if (!err_k.empty() || !err_m.empty() || !err_c.empty()){
 320       if (!err_k.empty()){
 321         derr << "could not convert k=" << value_k << "to int" << dendl;
 322       } else if (!err_m.empty()){
 323         derr << "could not convert m=" << value_m << "to int" << dendl;
 324       } else if (!err_c.empty()){
 325         derr << "could not convert c=" << value_c << "to int" << dendl;
 326       }
 327       err = -EINVAL;
 328     } else if (k <= 0){
 329       derr << "k=" << k
 330            << " must be a positive number" << dendl;
 331       err = -EINVAL;
 332     } else if (m <= 0){
 333       derr << "m=" << m
 334            << " must be a positive number" << dendl;
 335       err = -EINVAL;
 336     } else if (c <= 0){
 337       derr << "c=" << c
 338            << " must be a positive number" << dendl;
 339       err = -EINVAL;
 340     } else if (m < c){
 341       derr << "c=" << c
 342            << " must be less than or equal to m=" << m << dendl;
 343       err = -EINVAL;
 344     } else if (k > 12){
 345       derr << "k=" << k
 346            << " must be less than or equal to 12" << dendl;
 347       err = -EINVAL;
 348     } else if (k+m > 20){
 349       derr << "k+m=" << k+m
 350            << " must be less than or equal to 20" << dendl;
 351       err = -EINVAL;
 352     } else if (k<m){
 353       derr << "m=" << m
 354            << " must be less than or equal to k=" << k << dendl;
 355       err = -EINVAL;
 356     }
 357   }
 358
 359   if (err) {
 360     derr << "(k, m, c)=(" << k << ", " << m << ", " << c
 361          << ") is not a valid parameter." << dendl;
 362     return err;
 363   }
 364
 365   dout(10) << "(k, m, c) set to " << "(" << k << ", " << m << ", "
 366            << c << ")"<< dendl;
 367
 368   // w
 369   if (profile.find("w") == profile.end()){
 370     dout(10) << "w default to " << DEFAULT_W << dendl;
 371     w = DEFAULT_W;
 372   } else {
 373     std::string err_w, value_w;
 374     value_w = profile.find("w")->second;
 375     w = strict_strtol(value_w.c_str(), 10, &err_w);
 376
 377     if (!err_w.empty()){
 378       derr << "could not convert w=" << value_w << "to int" << dendl;
 379       dout(10) << "w default to " << DEFAULT_W << dendl;
 380       w = DEFAULT_W;
 381
 382     } else if (w != 8 && w != 16 && w != 32) {
 383       derr << "w=" << w
 384            << " must be one of {8, 16, 32}" << dendl;
 385       dout(10) << "w default to " << DEFAULT_W << dendl;
 386       w = DEFAULT_W;
 387
 388     } else {
 389       dout(10) << "w set to " << w << dendl;
 390     }
 391   }
 392   return 0;
 393 }
 394
 395 void ErasureCodeShecReedSolomonVandermonde::prepare()
 396 {
 397   // setup shared encoding table
 398   int** p_enc_table =
 399     tcache.getEncodingTable(technique, k, m, c, w);
 400
 401   if (!*p_enc_table) {
 402     dout(10) << "[ cache tables ] creating coeff for k=" <<
 403       k << " m=" << m << " c=" << c << " w=" << w << dendl;
 404
 405     matrix = shec_reedsolomon_coding_matrix(technique);
 406
 407     // either our new created table is stored or if it has been
 408     // created in the meanwhile the locally allocated table will be
 409     // freed by setEncodingTable
 410     matrix = tcache.setEncodingTable(technique, k, m, c, w, matrix);
 411
 412     dout(10) << "matrix = " << dendl;
 413     for (int i=0; i<m; i++) {
 414       char mat[k+1];
 415       for (int j=0; j<k; j++) {
 416         if (matrix[i*k+j] > 0) {
 417           mat[j] = '1';
 418         } else {
 419           mat[j] = '0';
 420         }
 421       }
 422       mat[k] = '\0';
 423       dout(10) << mat << dendl;
 424     }
 425   } else {
 426     matrix = *p_enc_table;
 427   }
 428
 429   dout(10) << " [ technique ] = " <<
 430     ((technique == MULTIPLE) ? "multiple" : "single") << dendl;
 431
 432   assert((technique == SINGLE) || (technique == MULTIPLE));
 433
 434 }
 435
 436 // ErasureCodeShec::
 437 // Mearged from shec.cc.
 438
 439 double ErasureCodeShec::shec_calc_recovery_efficiency1(int k, int m1, int m2, int c1, int c2){
 440   int r_eff_k[k];
 441   double r_e1;
 442   int i, rr, cc, start, end;
 443   int first_flag;
 444
 445   if (m1 < c1 || m2 < c2) return -1;
 446   if ((m1 == 0 && c1 != 0) || (m2 == 0 && c2 != 0)) return -1;
 447
 448   for (i=0; i<k; i++) r_eff_k[i] = 100000000;
 449   r_e1 = 0;
 450
 451   for (rr=0; rr<m1; rr++){
 452     start = ((rr*k)/m1) % k;
 453     end = (((rr+c1)*k)/m1) % k;
 454     for (cc=start, first_flag=1; first_flag || cc!=end; cc=(cc+1)%k){
 455       first_flag = 0;
 456       r_eff_k[cc] = std::min(r_eff_k[cc], ((rr+c1)*k)/m1 - (rr*k)/m1);
 457     }
 458     r_e1 += ((rr+c1)*k)/m1 - (rr*k)/m1;
 459   }
 460
 461   for (rr=0; rr<m2; rr++){
 462     start = ((rr*k)/m2) % k;
 463     end = (((rr+c2)*k)/m2) % k;
 464     for (cc=start, first_flag=1; first_flag || cc!=end; cc=(cc+1)%k){
 465       first_flag = 0;
 466       r_eff_k[cc] = std::min(r_eff_k[cc], ((rr+c2)*k)/m2 - (rr*k)/m2);
 467     }
 468     r_e1 += ((rr+c2)*k)/m2 - (rr*k)/m2;
 469   }
 470
 471   for (i=0; i<k; i++){
 472     r_e1 += r_eff_k[i];
 473   }
 474
 475   r_e1 /= (k+m1+m2);
 476
 477   return r_e1;
 478 }
 479
 480 int* ErasureCodeShec::shec_reedsolomon_coding_matrix(int is_single)
 481 {
 482   int *matrix;
 483   int rr, cc, start, end;
 484   int m1, m2, c1, c2;
 485
 486   if (w != 8 && w != 16 && w != 32) return NULL;
 487
 488   if (!is_single){
 489     int c1_best = -1, m1_best = -1;
 490     double min_r_e1 = 100.0;
 491
 492     // create all multiple shec pattern and choose best.
 493
 494     for (c1=0; c1 <= c/2; c1++){
 495       for (m1=0; m1 <= m; m1++){
 496         c2 = c-c1;
 497         m2 = m-m1;
 498
 499         if (m1 < c1 || m2 < c2) continue;
 500         if ((m1 == 0 && c1 != 0) || (m2 == 0 && c2 != 0)) continue;
 501         if ((m1 != 0 && c1 == 0) || (m2 != 0 && c2 == 0)) continue;
 502
 503         // minimize r_e1
 504
 505         if (true) {
 506           double r_e1;
 507           r_e1 = shec_calc_recovery_efficiency1(k, m1, m2, c1, c2);
 508           if (min_r_e1 - r_e1 > std::numeric_limits<double>::epsilon() &&
 509               r_e1 < min_r_e1) {
 510             min_r_e1 = r_e1;
 511             c1_best = c1;
 512             m1_best = m1;
 513           }
 514         }
 515       }
 516     }
 517     m1 = m1_best;
 518     c1 = c1_best;
 519     m2 = m - m1_best;
 520     c2 = c - c1_best;
 521   } else {
 522     m1 = 0;
 523     c1 = 0;
 524     m2 = m;
 525     c2 = c;
 526   }
 527
 528   // create matrix
 529   matrix = reed_sol_vandermonde_coding_matrix(k, m, w);
 530
 531   for (rr=0; rr<m1; rr++){
 532     end = ((rr*k)/m1) % k;
 533     start = (((rr+c1)*k)/m1) % k;
 534     for (cc=start; cc!=end; cc=(cc+1)%k){
 535       matrix[cc + rr*k] = 0;
 536     }
 537   }
 538
 539   for (rr=0; rr<m2; rr++){
 540     end = ((rr*k)/m2) % k;
 541     start = (((rr+c2)*k)/m2) % k;
 542     for (cc=start; cc!=end; cc=(cc+1)%k){
 543       matrix[cc + (rr+m1)*k] = 0;
 544     }
 545   }
 546
 547   return matrix;
 548 }
 549
 550 int ErasureCodeShec::shec_make_decoding_matrix(bool prepare, int *want_, int *avails,
 551                                                int *decoding_matrix, int *dm_row, int *dm_column,
 552                                                int *minimum)
 553 {
 554   int mindup = k+1, minp = k+1;
 555   int want[k + m];
 556
 557   memset(want, 0, sizeof(want));
 558
 559   for (int i = 0; i < k + m; ++i) {
 560     want[i] = want_[i];
 561   }
 562
 563   for (int i = 0; i < m; ++i) {
 564     if (want[i + k] && !avails[i + k]) {
 565       for (int j=0; j < k; ++j) {
 566         if (matrix[i * k + j] > 0) {
 567           want[j] = 1;
 568         }
 569       }
 570     }
 571   }
 572
 573   if (tcache.getDecodingTableFromCache(decoding_matrix,
 574                                        dm_row, dm_column, minimum,
 575                                        technique,
 576                                        k, m, c, w,
 577                                        want, avails)) {
 578     return 0;
 579   }
 580
 581   for (unsigned long long pp = 0; pp < (1ull << m); ++pp) {
 582
 583     // select parity chunks
 584     int ek = 0;
 585     int p[m];
 586     for (int i=0; i < m; ++i) {
 587       if (pp & (1ull << i)) {
 588         p[ek++] = i;
 589       }
 590     }
 591     if (ek > minp) {
 592       continue;
 593     }
 594
 595     // Are selected parity chunks avail?
 596     bool ok = true;
 597     for (int i = 0; i < ek && ok; i++) {
 598       if (!avails[k+p[i]]) {
 599         ok = false;
 600         break;
 601       }
 602     }
 603
 604     if (!ok) {
 605       continue;
 606     }
 607
 608     int tmprow[k + m];
 609     int tmpcolumn[k];
 610     for (int i = 0; i < k + m; i++) {
 611       tmprow[i] = 0;
 612     }
 613     for (int i = 0; i < k; i++) {
 614       tmpcolumn[i] = 0;
 615     }
 616
 617     for (int i=0; i < k; i++) {
 618       if (want[i] && !avails[i]) {
 619         tmpcolumn[i] = 1;
 620       }
 621     }
 622
 623     // Parity chunks which are used to recovery erased data chunks, are added to tmprow.
 624     for (int i = 0; i < ek; i++) {
 625       tmprow[k + p[i]] = 1;
 626       for (int j = 0; j < k; j++) {
 627         int element = matrix[(p[i]) * k + j];
 628         if (element != 0) {
 629           tmpcolumn[j] = 1;
 630         }
 631         if (element != 0 && avails[j] == 1) {
 632           tmprow[j] = 1;
 633         }
 634       }
 635     }
 636
 637     int dup_row = 0, dup_column = 0, dup = 0;
 638     for (int i = 0; i < k + m; i++) {
 639       if (tmprow[i]) {
 640         dup_row++;
 641       }
 642     }
 643
 644     for (int i = 0; i < k; i++) {
 645       if (tmpcolumn[i]) {
 646         dup_column++;
 647       }
 648     }
 649
 650     if (dup_row != dup_column) {
 651       continue;
 652     }
 653     dup = dup_row;
 654     if (dup == 0) {
 655       mindup = dup;
 656       for (int i = 0; i < k; i++) {
 657         dm_row[i] = -1;
 658       }
 659       for (int i = 0; i < k; i++) {
 660         dm_column[i] = -1;
 661       }
 662       break;
 663     }
 664
 665     // minimum is updated.
 666     if (dup < mindup) {
 667       int tmpmat[dup * dup];
 668       {
 669         for (int i = 0, row = 0; i < k + m; i++) {
 670           if (tmprow[i]) {
 671             for (int j = 0, column = 0; j < k; j++) {
 672               if (tmpcolumn[j]) {
 673                 if (i < k) {
 674                   tmpmat[row * dup + column] = (i == j ? 1 : 0);
 675                 } else {
 676                   tmpmat[row * dup + column] = matrix[(i - k) * k + j];
 677                 }
 678                 column++;
 679               }
 680             }
 681             row++;
 682           }
 683         }
 684       }
 685       int det = calc_determinant(tmpmat, dup);
 686
 687       if (det != 0) {
 688         int row_id = 0;
 689         int column_id = 0;
 690         for (int i = 0; i < k; i++) {
 691           dm_row[i] = -1;
 692         }
 693         for (int i = 0; i < k; i++) {
 694           dm_column[i] = -1;
 695         }
 696
 697         mindup = dup;
 698         for (int i=0; i < k + m; i++) {
 699           if (tmprow[i]) {
 700             dm_row[row_id++] = i;
 701           }
 702         }
 703         for (int i=0; i < k; i++) {
 704           if (tmpcolumn[i]) {
 705             dm_column[column_id++] = i;
 706           }
 707         }
 708         minp = ek;
 709       }
 710     }
 711   }
 712
 713
 714   if (mindup == k+1) {
 715     fprintf(stderr, "shec_make_decoding_matrix(): can't find recover matrix.\n");
 716     return -1;
 717   }
 718
 719   for (int i = 0; i < k + m; i++) {
 720     minimum[i] = 0;
 721   }
 722
 723   for (int i=0; i < k && dm_row[i] != -1; i++) {
 724     minimum[dm_row[i]] = 1;
 725   }
 726
 727   for (int i = 0; i < k; ++i) {
 728     if (want[i] && avails[i]) {
 729       minimum[i] = 1;
 730     }
 731   }
 732
 733   for (int i = 0; i < m; ++i) {
 734     if (want[k + i] && avails[k + i] && !minimum[k + i]) {
 735       for (int j = 0; j < k; ++j) {
 736         if (matrix[i * k + j] > 0 && !want[j]) {
 737           minimum[k + i] = 1;
 738           break;
 739         }
 740       }
 741     }
 742   }
 743
 744   if (mindup == 0) {
 745     return 0;
 746   }
 747
 748   int tmpmat[mindup * mindup];
 749   for (int i=0; i < mindup; i++) {
 750     for (int j=0; j < mindup; j++) {
 751       if (dm_row[i] < k) {
 752         tmpmat[i * mindup + j] = (dm_row[i] == dm_column[j] ? 1 : 0);
 753       } else {
 754         tmpmat[i * mindup + j] = matrix[(dm_row[i] - k) * k + dm_column[j]];
 755       }
 756     }
 757     if (dm_row[i] < k) {
 758       for (int j = 0; j < mindup; j++) {
 759         if (dm_row[i] == dm_column[j]) {
 760           dm_row[i] = j;
 761         }
 762       }
 763     } else {
 764       dm_row[i] -= (k - mindup);
 765     }
 766   }
 767
 768   if (prepare) {
 769     return 0;
 770   }
 771
 772   int ret = jerasure_invert_matrix(tmpmat, decoding_matrix, mindup, w);
 773
 774   tcache.putDecodingTableToCache(decoding_matrix, dm_row, dm_column, minimum, technique,
 775                                  k, m, c, w, want, avails);
 776
 777   return ret;
 778 }
 779
 780 int ErasureCodeShec::shec_matrix_decode(int *want, int *avails, char **data_ptrs,
 781                                         char **coding_ptrs, int size)
 782 {
 783   int decoding_matrix[k*k];
 784   int dm_row[k], dm_column[k];
 785   int minimum[k + m];
 786
 787   memset(decoding_matrix, 0, sizeof(decoding_matrix));
 788   memset(dm_row, -1, sizeof(dm_row));
 789   memset(dm_column, -1, sizeof(dm_column));
 790   memset(minimum, -1, sizeof(minimum));
 791
 792   if (w != 8 && w != 16 && w != 32) return -1;
 793
 794   if (shec_make_decoding_matrix(false, want, avails, decoding_matrix,
 795                                 dm_row, dm_column, minimum) < 0) {
 796     return -1;
 797   }
 798
 799   // Get decoding matrix size
 800   int dm_size = 0;
 801   for (int i = 0; i < k; i++) {
 802     if (dm_row[i] == -1) {
 803       break;
 804     }
 805     dm_size++;
 806   }
 807
 808   char *dm_data_ptrs[dm_size];
 809   for (int i = 0; i < dm_size; i++) {
 810     dm_data_ptrs[i] = data_ptrs[dm_column[i]];
 811   }
 812
 813   // Decode the data drives
 814   for (int i = 0; i < dm_size; i++) {
 815     if (!avails[dm_column[i]]) {
 816       jerasure_matrix_dotprod(dm_size, w, decoding_matrix + (i * dm_size),
 817                               dm_row, i, dm_data_ptrs, coding_ptrs, size);
 818     }
 819   }
 820
 821   // Re-encode any erased coding devices
 822   for (int i = 0; i < m; i++) {
 823     if (want[k+i] && !avails[k+i]) {
 824       jerasure_matrix_dotprod(k, w, matrix + (i * k), NULL, i+k,
 825                               data_ptrs, coding_ptrs, size);
 826     }
 827   }
 828
 829   return 0;
 830 }