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   ceph_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       bufferlist tmp;
 202       bufferptr ptr(buffer::create_aligned(blocksize, SIMD_ALIGN));
 203       tmp.push_back(ptr);
 204       tmp.claim_append((*decoded)[i]);
 205       (*decoded)[i].swap(tmp);
 206     } else {
 207       (*decoded)[i] = chunks.find(i)->second;
 208       (*decoded)[i].rebuild_aligned(SIMD_ALIGN);
 209     }
 210   }
 211   return decode_chunks(want_to_read, chunks, decoded);
 212 }
 213
 214 int ErasureCodeShec::decode_chunks(const set<int> &want_to_read,
 215                                    const map<int, bufferlist> &chunks,
 216                                    map<int, bufferlist> *decoded)
 217 {
 218   unsigned blocksize = (*chunks.begin()).second.length();
 219   int erased[k + m];
 220   int erased_count = 0;
 221   int avails[k + m];
 222   char *data[k];
 223   char *coding[m];
 224
 225   for (int i = 0; i < k + m; i++) {
 226     erased[i] = 0;
 227     if (chunks.find(i) == chunks.end()) {
 228       if (want_to_read.count(i) > 0) {
 229         erased[i] = 1;
 230         erased_count++;
 231       }
 232       avails[i] = 0;
 233     } else {
 234       avails[i] = 1;
 235     }
 236     if (i < k)
 237       data[i] = (*decoded)[i].c_str();
 238     else
 239       coding[i - k] = (*decoded)[i].c_str();
 240   }
 241
 242   if (erased_count > 0) {
 243     return shec_decode(erased, avails, data, coding, blocksize);
 244   } else {
 245     return 0;
 246   }
 247 }
 248
 249 //
 250 // ErasureCodeShecReedSolomonVandermonde
 251 //
 252
 253 void ErasureCodeShecReedSolomonVandermonde::shec_encode(char **data,
 254                                              char **coding,
 255                                              int blocksize)
 256 {
 257   jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize);
 258 }
 259
 260 int ErasureCodeShecReedSolomonVandermonde::shec_decode(int *erased,
 261                                             int *avails,
 262                                             char **data,
 263                                             char **coding,
 264                                             int blocksize)
 265 {
 266   return shec_matrix_decode(erased, avails, data, coding, blocksize);
 267 }
 268
 269 unsigned ErasureCodeShecReedSolomonVandermonde::get_alignment() const
 270 {
 271   return k*w*sizeof(int);
 272 }
 273
 274 int ErasureCodeShecReedSolomonVandermonde::parse(const ErasureCodeProfile &profile)
 275 {
 276   int err = 0;
 277   // k, m, c
 278   if (profile.find("k") == profile.end() &&
 279       profile.find("m") == profile.end() &&
 280       profile.find("c") == profile.end()){
 281     dout(10) << "(k, m, c) default to " << "(" << DEFAULT_K
 282              << ", " << DEFAULT_M << ", " << DEFAULT_C << ")" << dendl;
 283     k = DEFAULT_K; m = DEFAULT_M; c = DEFAULT_C;
 284   } else if (profile.find("k") == profile.end() ||
 285              profile.find("m") == profile.end() ||
 286              profile.find("c") == profile.end()){
 287     dout(10) << "(k, m, c) must be chosen" << dendl;
 288     err = -EINVAL;
 289   } else {
 290     std::string err_k, err_m, err_c, value_k, value_m, value_c;
 291     value_k = profile.find("k")->second;
 292     value_m = profile.find("m")->second;
 293     value_c = profile.find("c")->second;
 294     k = strict_strtol(value_k.c_str(), 10, &err_k);
 295     m = strict_strtol(value_m.c_str(), 10, &err_m);
 296     c = strict_strtol(value_c.c_str(), 10, &err_c);
 297
 298     if (!err_k.empty() || !err_m.empty() || !err_c.empty()){
 299       if (!err_k.empty()){
 300         derr << "could not convert k=" << value_k << "to int" << dendl;
 301       } else if (!err_m.empty()){
 302         derr << "could not convert m=" << value_m << "to int" << dendl;
 303       } else if (!err_c.empty()){
 304         derr << "could not convert c=" << value_c << "to int" << dendl;
 305       }
 306       err = -EINVAL;
 307     } else if (k <= 0){
 308       derr << "k=" << k
 309            << " must be a positive number" << dendl;
 310       err = -EINVAL;
 311     } else if (m <= 0){
 312       derr << "m=" << m
 313            << " must be a positive number" << dendl;
 314       err = -EINVAL;
 315     } else if (c <= 0){
 316       derr << "c=" << c
 317            << " must be a positive number" << dendl;
 318       err = -EINVAL;
 319     } else if (m < c){
 320       derr << "c=" << c
 321            << " must be less than or equal to m=" << m << dendl;
 322       err = -EINVAL;
 323     } else if (k > 12){
 324       derr << "k=" << k
 325            << " must be less than or equal to 12" << dendl;
 326       err = -EINVAL;
 327     } else if (k+m > 20){
 328       derr << "k+m=" << k+m
 329            << " must be less than or equal to 20" << dendl;
 330       err = -EINVAL;
 331     } else if (k<m){
 332       derr << "m=" << m
 333            << " must be less than or equal to k=" << k << dendl;
 334       err = -EINVAL;
 335     }
 336   }
 337
 338   if (err) {
 339     derr << "(k, m, c)=(" << k << ", " << m << ", " << c
 340          << ") is not a valid parameter." << dendl;
 341     return err;
 342   }
 343
 344   dout(10) << "(k, m, c) set to " << "(" << k << ", " << m << ", "
 345            << c << ")"<< dendl;
 346
 347   // w
 348   if (profile.find("w") == profile.end()){
 349     dout(10) << "w default to " << DEFAULT_W << dendl;
 350     w = DEFAULT_W;
 351   } else {
 352     std::string err_w, value_w;
 353     value_w = profile.find("w")->second;
 354     w = strict_strtol(value_w.c_str(), 10, &err_w);
 355
 356     if (!err_w.empty()){
 357       derr << "could not convert w=" << value_w << "to int" << dendl;
 358       dout(10) << "w default to " << DEFAULT_W << dendl;
 359       w = DEFAULT_W;
 360
 361     } else if (w != 8 && w != 16 && w != 32) {
 362       derr << "w=" << w
 363            << " must be one of {8, 16, 32}" << dendl;
 364       dout(10) << "w default to " << DEFAULT_W << dendl;
 365       w = DEFAULT_W;
 366
 367     } else {
 368       dout(10) << "w set to " << w << dendl;
 369     }
 370   }
 371   return 0;
 372 }
 373
 374 void ErasureCodeShecReedSolomonVandermonde::prepare()
 375 {
 376   // setup shared encoding table
 377   int** p_enc_table =
 378     tcache.getEncodingTable(technique, k, m, c, w);
 379
 380   if (!*p_enc_table) {
 381     dout(10) << "[ cache tables ] creating coeff for k=" <<
 382       k << " m=" << m << " c=" << c << " w=" << w << dendl;
 383
 384     matrix = shec_reedsolomon_coding_matrix(technique);
 385
 386     // either our new created table is stored or if it has been
 387     // created in the meanwhile the locally allocated table will be
 388     // freed by setEncodingTable
 389     matrix = tcache.setEncodingTable(technique, k, m, c, w, matrix);
 390
 391     dout(10) << "matrix = " << dendl;
 392     for (int i=0; i<m; i++) {
 393       char mat[k+1];
 394       for (int j=0; j<k; j++) {
 395         if (matrix[i*k+j] > 0) {
 396           mat[j] = '1';
 397         } else {
 398           mat[j] = '0';
 399         }
 400       }
 401       mat[k] = '\0';
 402       dout(10) << mat << dendl;
 403     }
 404   } else {
 405     matrix = *p_enc_table;
 406   }
 407
 408   dout(10) << " [ technique ] = " <<
 409     ((technique == MULTIPLE) ? "multiple" : "single") << dendl;
 410
 411   ceph_assert((technique == SINGLE) || (technique == MULTIPLE));
 412
 413 }
 414
 415 // ErasureCodeShec::
 416 // Mearged from shec.cc.
 417
 418 double ErasureCodeShec::shec_calc_recovery_efficiency1(int k, int m1, int m2, int c1, int c2){
 419   int r_eff_k[k];
 420   double r_e1;
 421   int i, rr, cc, start, end;
 422   int first_flag;
 423
 424   if (m1 < c1 || m2 < c2) return -1;
 425   if ((m1 == 0 && c1 != 0) || (m2 == 0 && c2 != 0)) return -1;
 426
 427   for (i=0; i<k; i++) r_eff_k[i] = 100000000;
 428   r_e1 = 0;
 429
 430   for (rr=0; rr<m1; rr++){
 431     start = ((rr*k)/m1) % k;
 432     end = (((rr+c1)*k)/m1) % k;
 433     for (cc=start, first_flag=1; first_flag || cc!=end; cc=(cc+1)%k){
 434       first_flag = 0;
 435       r_eff_k[cc] = std::min(r_eff_k[cc], ((rr+c1)*k)/m1 - (rr*k)/m1);
 436     }
 437     r_e1 += ((rr+c1)*k)/m1 - (rr*k)/m1;
 438   }
 439
 440   for (rr=0; rr<m2; rr++){
 441     start = ((rr*k)/m2) % k;
 442     end = (((rr+c2)*k)/m2) % k;
 443     for (cc=start, first_flag=1; first_flag || cc!=end; cc=(cc+1)%k){
 444       first_flag = 0;
 445       r_eff_k[cc] = std::min(r_eff_k[cc], ((rr+c2)*k)/m2 - (rr*k)/m2);
 446     }
 447     r_e1 += ((rr+c2)*k)/m2 - (rr*k)/m2;
 448   }
 449
 450   for (i=0; i<k; i++){
 451     r_e1 += r_eff_k[i];
 452   }
 453
 454   r_e1 /= (k+m1+m2);
 455
 456   return r_e1;
 457 }
 458
 459 int* ErasureCodeShec::shec_reedsolomon_coding_matrix(int is_single)
 460 {
 461   int *matrix;
 462   int rr, cc, start, end;
 463   int m1, m2, c1, c2;
 464
 465   if (w != 8 && w != 16 && w != 32) return NULL;
 466
 467   if (!is_single){
 468     int c1_best = -1, m1_best = -1;
 469     double min_r_e1 = 100.0;
 470
 471     // create all multiple shec pattern and choose best.
 472
 473     for (c1=0; c1 <= c/2; c1++){
 474       for (m1=0; m1 <= m; m1++){
 475         c2 = c-c1;
 476         m2 = m-m1;
 477
 478         if (m1 < c1 || m2 < c2) continue;
 479         if ((m1 == 0 && c1 != 0) || (m2 == 0 && c2 != 0)) continue;
 480         if ((m1 != 0 && c1 == 0) || (m2 != 0 && c2 == 0)) continue;
 481
 482         // minimize r_e1
 483
 484         if (true) {
 485           double r_e1;
 486           r_e1 = shec_calc_recovery_efficiency1(k, m1, m2, c1, c2);
 487           if (min_r_e1 - r_e1 > std::numeric_limits<double>::epsilon() &&
 488               r_e1 < min_r_e1) {
 489             min_r_e1 = r_e1;
 490             c1_best = c1;
 491             m1_best = m1;
 492           }
 493         }
 494       }
 495     }
 496     m1 = m1_best;
 497     c1 = c1_best;
 498     m2 = m - m1_best;
 499     c2 = c - c1_best;
 500   } else {
 501     m1 = 0;
 502     c1 = 0;
 503     m2 = m;
 504     c2 = c;
 505   }
 506
 507   // create matrix
 508   matrix = reed_sol_vandermonde_coding_matrix(k, m, w);
 509
 510   for (rr=0; rr<m1; rr++){
 511     end = ((rr*k)/m1) % k;
 512     start = (((rr+c1)*k)/m1) % k;
 513     for (cc=start; cc!=end; cc=(cc+1)%k){
 514       matrix[cc + rr*k] = 0;
 515     }
 516   }
 517
 518   for (rr=0; rr<m2; rr++){
 519     end = ((rr*k)/m2) % k;
 520     start = (((rr+c2)*k)/m2) % k;
 521     for (cc=start; cc!=end; cc=(cc+1)%k){
 522       matrix[cc + (rr+m1)*k] = 0;
 523     }
 524   }
 525
 526   return matrix;
 527 }
 528
 529 int ErasureCodeShec::shec_make_decoding_matrix(bool prepare, int *want_, int *avails,
 530                                                int *decoding_matrix, int *dm_row, int *dm_column,
 531                                                int *minimum)
 532 {
 533   int mindup = k+1, minp = k+1;
 534   int want[k + m];
 535
 536   memset(want, 0, sizeof(want));
 537
 538   for (int i = 0; i < k + m; ++i) {
 539     want[i] = want_[i];
 540   }
 541
 542   for (int i = 0; i < m; ++i) {
 543     if (want[i + k] && !avails[i + k]) {
 544       for (int j=0; j < k; ++j) {
 545         if (matrix[i * k + j] > 0) {
 546           want[j] = 1;
 547         }
 548       }
 549     }
 550   }
 551
 552   if (tcache.getDecodingTableFromCache(decoding_matrix,
 553                                        dm_row, dm_column, minimum,
 554                                        technique,
 555                                        k, m, c, w,
 556                                        want, avails)) {
 557     return 0;
 558   }
 559
 560   for (unsigned long long pp = 0; pp < (1ull << m); ++pp) {
 561
 562     // select parity chunks
 563     int ek = 0;
 564     int p[m];
 565     for (int i=0; i < m; ++i) {
 566       if (pp & (1ull << i)) {
 567         p[ek++] = i;
 568       }
 569     }
 570     if (ek > minp) {
 571       continue;
 572     }
 573
 574     // Are selected parity chunks avail?
 575     bool ok = true;
 576     for (int i = 0; i < ek && ok; i++) {
 577       if (!avails[k+p[i]]) {
 578         ok = false;
 579         break;
 580       }
 581     }
 582
 583     if (!ok) {
 584       continue;
 585     }
 586
 587     int tmprow[k + m];
 588     int tmpcolumn[k];
 589     for (int i = 0; i < k + m; i++) {
 590       tmprow[i] = 0;
 591     }
 592     for (int i = 0; i < k; i++) {
 593       tmpcolumn[i] = 0;
 594     }
 595
 596     for (int i=0; i < k; i++) {
 597       if (want[i] && !avails[i]) {
 598         tmpcolumn[i] = 1;
 599       }
 600     }
 601
 602     // Parity chunks which are used to recovery erased data chunks, are added to tmprow.
 603     for (int i = 0; i < ek; i++) {
 604       tmprow[k + p[i]] = 1;
 605       for (int j = 0; j < k; j++) {
 606         int element = matrix[(p[i]) * k + j];
 607         if (element != 0) {
 608           tmpcolumn[j] = 1;
 609         }
 610         if (element != 0 && avails[j] == 1) {
 611           tmprow[j] = 1;
 612         }
 613       }
 614     }
 615
 616     int dup_row = 0, dup_column = 0, dup = 0;
 617     for (int i = 0; i < k + m; i++) {
 618       if (tmprow[i]) {
 619         dup_row++;
 620       }
 621     }
 622
 623     for (int i = 0; i < k; i++) {
 624       if (tmpcolumn[i]) {
 625         dup_column++;
 626       }
 627     }
 628
 629     if (dup_row != dup_column) {
 630       continue;
 631     }
 632     dup = dup_row;
 633     if (dup == 0) {
 634       mindup = dup;
 635       for (int i = 0; i < k; i++) {
 636         dm_row[i] = -1;
 637       }
 638       for (int i = 0; i < k; i++) {
 639         dm_column[i] = -1;
 640       }
 641       break;
 642     }
 643
 644     // minimum is updated.
 645     if (dup < mindup) {
 646       int tmpmat[dup * dup];
 647       {
 648         for (int i = 0, row = 0; i < k + m; i++) {
 649           if (tmprow[i]) {
 650             for (int j = 0, column = 0; j < k; j++) {
 651               if (tmpcolumn[j]) {
 652                 if (i < k) {
 653                   tmpmat[row * dup + column] = (i == j ? 1 : 0);
 654                 } else {
 655                   tmpmat[row * dup + column] = matrix[(i - k) * k + j];
 656                 }
 657                 column++;
 658               }
 659             }
 660             row++;
 661           }
 662         }
 663       }
 664       int det = calc_determinant(tmpmat, dup);
 665
 666       if (det != 0) {
 667         int row_id = 0;
 668         int column_id = 0;
 669         for (int i = 0; i < k; i++) {
 670           dm_row[i] = -1;
 671         }
 672         for (int i = 0; i < k; i++) {
 673           dm_column[i] = -1;
 674         }
 675
 676         mindup = dup;
 677         for (int i=0; i < k + m; i++) {
 678           if (tmprow[i]) {
 679             dm_row[row_id++] = i;
 680           }
 681         }
 682         for (int i=0; i < k; i++) {
 683           if (tmpcolumn[i]) {
 684             dm_column[column_id++] = i;
 685           }
 686         }
 687         minp = ek;
 688       }
 689     }
 690   }
 691
 692
 693   if (mindup == k+1) {
 694     fprintf(stderr, "shec_make_decoding_matrix(): can't find recover matrix.\n");
 695     return -1;
 696   }
 697
 698   for (int i = 0; i < k + m; i++) {
 699     minimum[i] = 0;
 700   }
 701
 702   for (int i=0; i < k && dm_row[i] != -1; i++) {
 703     minimum[dm_row[i]] = 1;
 704   }
 705
 706   for (int i = 0; i < k; ++i) {
 707     if (want[i] && avails[i]) {
 708       minimum[i] = 1;
 709     }
 710   }
 711
 712   for (int i = 0; i < m; ++i) {
 713     if (want[k + i] && avails[k + i] && !minimum[k + i]) {
 714       for (int j = 0; j < k; ++j) {
 715         if (matrix[i * k + j] > 0 && !want[j]) {
 716           minimum[k + i] = 1;
 717           break;
 718         }
 719       }
 720     }
 721   }
 722
 723   if (mindup == 0) {
 724     return 0;
 725   }
 726
 727   int tmpmat[mindup * mindup];
 728   for (int i=0; i < mindup; i++) {
 729     for (int j=0; j < mindup; j++) {
 730       if (dm_row[i] < k) {
 731         tmpmat[i * mindup + j] = (dm_row[i] == dm_column[j] ? 1 : 0);
 732       } else {
 733         tmpmat[i * mindup + j] = matrix[(dm_row[i] - k) * k + dm_column[j]];
 734       }
 735     }
 736     if (dm_row[i] < k) {
 737       for (int j = 0; j < mindup; j++) {
 738         if (dm_row[i] == dm_column[j]) {
 739           dm_row[i] = j;
 740         }
 741       }
 742     } else {
 743       dm_row[i] -= (k - mindup);
 744     }
 745   }
 746
 747   if (prepare) {
 748     return 0;
 749   }
 750
 751   int ret = jerasure_invert_matrix(tmpmat, decoding_matrix, mindup, w);
 752
 753   tcache.putDecodingTableToCache(decoding_matrix, dm_row, dm_column, minimum, technique,
 754                                  k, m, c, w, want, avails);
 755
 756   return ret;
 757 }
 758
 759 int ErasureCodeShec::shec_matrix_decode(int *want, int *avails, char **data_ptrs,
 760                                         char **coding_ptrs, int size)
 761 {
 762   int decoding_matrix[k*k];
 763   int dm_row[k], dm_column[k];
 764   int minimum[k + m];
 765
 766   memset(decoding_matrix, 0, sizeof(decoding_matrix));
 767   memset(dm_row, -1, sizeof(dm_row));
 768   memset(dm_column, -1, sizeof(dm_column));
 769   memset(minimum, -1, sizeof(minimum));
 770
 771   if (w != 8 && w != 16 && w != 32) return -1;
 772
 773   if (shec_make_decoding_matrix(false, want, avails, decoding_matrix,
 774                                 dm_row, dm_column, minimum) < 0) {
 775     return -1;
 776   }
 777
 778   // Get decoding matrix size
 779   int dm_size = 0;
 780   for (int i = 0; i < k; i++) {
 781     if (dm_row[i] == -1) {
 782       break;
 783     }
 784     dm_size++;
 785   }
 786
 787   char *dm_data_ptrs[dm_size];
 788   for (int i = 0; i < dm_size; i++) {
 789     dm_data_ptrs[i] = data_ptrs[dm_column[i]];
 790   }
 791
 792   // Decode the data drives
 793   for (int i = 0; i < dm_size; i++) {
 794     if (!avails[dm_column[i]]) {
 795       jerasure_matrix_dotprod(dm_size, w, decoding_matrix + (i * dm_size),
 796                               dm_row, i, dm_data_ptrs, coding_ptrs, size);
 797     }
 798   }
 799
 800   // Re-encode any erased coding devices
 801   for (int i = 0; i < m; i++) {
 802     if (want[k+i] && !avails[k+i]) {
 803       jerasure_matrix_dotprod(k, w, matrix + (i * k), NULL, i+k,
 804                               data_ptrs, coding_ptrs, size);
 805     }
 806   }
 807
 808   return 0;
 809 }