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