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