]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
31f18b77 FG |
26 | using namespace std; |
27 | ||
7c673cae FG |
28 | #include "common/debug.h" |
29 | #include "ErasureCodeShec.h" | |
7c673cae FG |
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 | ||
7c673cae FG |
48 | int ErasureCodeShec::init(ErasureCodeProfile &profile, |
49 | ostream *ss) | |
50 | { | |
51 | int err = 0; | |
7c673cae FG |
52 | err |= parse(profile); |
53 | if (err) | |
54 | return err; | |
55 | prepare(); | |
224ce89b | 56 | return ErasureCode::init(profile, ss); |
7c673cae FG |
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 | } |