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