]>
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 distributed storage system | |
5 | * | |
6 | * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com> | |
7 | * Copyright (C) 2014 Red Hat <contact@redhat.com> | |
8 | * | |
9 | * Author: Loic Dachary <loic@dachary.org> | |
10 | * | |
11 | * This library is free software; you can redistribute it and/or | |
12 | * modify it under the terms of the GNU Lesser General Public | |
13 | * License as published by the Free Software Foundation; either | |
14 | * version 2.1 of the License, or (at your option) any later version. | |
15 | * | |
16 | */ | |
17 | ||
18 | #include "common/debug.h" | |
19 | #include "ErasureCodeJerasure.h" | |
31f18b77 | 20 | |
31f18b77 | 21 | |
7c673cae FG |
22 | extern "C" { |
23 | #include "jerasure.h" | |
24 | #include "reed_sol.h" | |
25 | #include "galois.h" | |
26 | #include "cauchy.h" | |
27 | #include "liberation.h" | |
28 | } | |
29 | ||
30 | #define LARGEST_VECTOR_WORDSIZE 16 | |
31 | ||
32 | #define dout_context g_ceph_context | |
33 | #define dout_subsys ceph_subsys_osd | |
34 | #undef dout_prefix | |
35 | #define dout_prefix _prefix(_dout) | |
36 | ||
9f95a23c TL |
37 | using std::ostream; |
38 | using std::map; | |
39 | using std::set; | |
40 | ||
41 | using ceph::bufferlist; | |
42 | using ceph::ErasureCodeProfile; | |
43 | ||
7c673cae FG |
44 | static ostream& _prefix(std::ostream* _dout) |
45 | { | |
46 | return *_dout << "ErasureCodeJerasure: "; | |
47 | } | |
48 | ||
7c673cae FG |
49 | |
50 | int ErasureCodeJerasure::init(ErasureCodeProfile& profile, ostream *ss) | |
51 | { | |
52 | int err = 0; | |
53 | dout(10) << "technique=" << technique << dendl; | |
54 | profile["technique"] = technique; | |
7c673cae FG |
55 | err |= parse(profile, ss); |
56 | if (err) | |
57 | return err; | |
58 | prepare(); | |
224ce89b | 59 | return ErasureCode::init(profile, ss); |
7c673cae FG |
60 | } |
61 | ||
62 | int ErasureCodeJerasure::parse(ErasureCodeProfile &profile, | |
63 | ostream *ss) | |
64 | { | |
65 | int err = ErasureCode::parse(profile, ss); | |
66 | err |= to_int("k", profile, &k, DEFAULT_K, ss); | |
67 | err |= to_int("m", profile, &m, DEFAULT_M, ss); | |
68 | err |= to_int("w", profile, &w, DEFAULT_W, ss); | |
69 | if (chunk_mapping.size() > 0 && (int)chunk_mapping.size() != k + m) { | |
70 | *ss << "mapping " << profile.find("mapping")->second | |
71 | << " maps " << chunk_mapping.size() << " chunks instead of" | |
72 | << " the expected " << k + m << " and will be ignored" << std::endl; | |
73 | chunk_mapping.clear(); | |
74 | err = -EINVAL; | |
75 | } | |
11fdf7f2 | 76 | err |= sanity_check_k_m(k, m, ss); |
7c673cae FG |
77 | return err; |
78 | } | |
79 | ||
80 | unsigned int ErasureCodeJerasure::get_chunk_size(unsigned int object_size) const | |
81 | { | |
82 | unsigned alignment = get_alignment(); | |
83 | if (per_chunk_alignment) { | |
84 | unsigned chunk_size = object_size / k; | |
85 | if (object_size % k) | |
86 | chunk_size++; | |
87 | dout(20) << "get_chunk_size: chunk_size " << chunk_size | |
88 | << " must be modulo " << alignment << dendl; | |
11fdf7f2 | 89 | ceph_assert(alignment <= chunk_size); |
7c673cae FG |
90 | unsigned modulo = chunk_size % alignment; |
91 | if (modulo) { | |
92 | dout(10) << "get_chunk_size: " << chunk_size | |
93 | << " padded to " << chunk_size + alignment - modulo << dendl; | |
94 | chunk_size += alignment - modulo; | |
95 | } | |
96 | return chunk_size; | |
97 | } else { | |
98 | unsigned tail = object_size % alignment; | |
99 | unsigned padded_length = object_size + ( tail ? ( alignment - tail ) : 0 ); | |
11fdf7f2 | 100 | ceph_assert(padded_length % k == 0); |
7c673cae FG |
101 | return padded_length / k; |
102 | } | |
103 | } | |
104 | ||
105 | int ErasureCodeJerasure::encode_chunks(const set<int> &want_to_encode, | |
106 | map<int, bufferlist> *encoded) | |
107 | { | |
108 | char *chunks[k + m]; | |
109 | for (int i = 0; i < k + m; i++) | |
110 | chunks[i] = (*encoded)[i].c_str(); | |
111 | jerasure_encode(&chunks[0], &chunks[k], (*encoded)[0].length()); | |
112 | return 0; | |
113 | } | |
114 | ||
115 | int ErasureCodeJerasure::decode_chunks(const set<int> &want_to_read, | |
116 | const map<int, bufferlist> &chunks, | |
117 | map<int, bufferlist> *decoded) | |
118 | { | |
119 | unsigned blocksize = (*chunks.begin()).second.length(); | |
120 | int erasures[k + m + 1]; | |
121 | int erasures_count = 0; | |
122 | char *data[k]; | |
123 | char *coding[m]; | |
124 | for (int i = 0; i < k + m; i++) { | |
125 | if (chunks.find(i) == chunks.end()) { | |
126 | erasures[erasures_count] = i; | |
127 | erasures_count++; | |
128 | } | |
129 | if (i < k) | |
130 | data[i] = (*decoded)[i].c_str(); | |
131 | else | |
132 | coding[i - k] = (*decoded)[i].c_str(); | |
133 | } | |
134 | erasures[erasures_count] = -1; | |
135 | ||
11fdf7f2 | 136 | ceph_assert(erasures_count > 0); |
7c673cae FG |
137 | return jerasure_decode(erasures, data, coding, blocksize); |
138 | } | |
139 | ||
140 | bool ErasureCodeJerasure::is_prime(int value) | |
141 | { | |
142 | int prime55[] = { | |
143 | 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, | |
144 | 73,79,83,89,97,101,103,107,109,113,127,131,137,139,149, | |
145 | 151,157,163,167,173,179, | |
146 | 181,191,193,197,199,211,223,227,229,233,239,241,251,257 | |
147 | }; | |
148 | int i; | |
149 | for (i = 0; i < 55; i++) | |
150 | if (value == prime55[i]) | |
151 | return true; | |
152 | return false; | |
153 | } | |
154 | ||
155 | // | |
156 | // ErasureCodeJerasureReedSolomonVandermonde | |
157 | // | |
158 | void ErasureCodeJerasureReedSolomonVandermonde::jerasure_encode(char **data, | |
159 | char **coding, | |
160 | int blocksize) | |
161 | { | |
162 | jerasure_matrix_encode(k, m, w, matrix, data, coding, blocksize); | |
163 | } | |
164 | ||
165 | int ErasureCodeJerasureReedSolomonVandermonde::jerasure_decode(int *erasures, | |
166 | char **data, | |
167 | char **coding, | |
168 | int blocksize) | |
169 | { | |
170 | return jerasure_matrix_decode(k, m, w, matrix, 1, | |
171 | erasures, data, coding, blocksize); | |
172 | } | |
173 | ||
174 | unsigned ErasureCodeJerasureReedSolomonVandermonde::get_alignment() const | |
175 | { | |
176 | if (per_chunk_alignment) { | |
177 | return w * LARGEST_VECTOR_WORDSIZE; | |
178 | } else { | |
179 | unsigned alignment = k*w*sizeof(int); | |
180 | if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) | |
181 | alignment = k*w*LARGEST_VECTOR_WORDSIZE; | |
182 | return alignment; | |
183 | } | |
184 | } | |
185 | ||
186 | int ErasureCodeJerasureReedSolomonVandermonde::parse(ErasureCodeProfile &profile, | |
187 | ostream *ss) | |
188 | { | |
189 | int err = 0; | |
190 | err |= ErasureCodeJerasure::parse(profile, ss); | |
191 | if (w != 8 && w != 16 && w != 32) { | |
192 | *ss << "ReedSolomonVandermonde: w=" << w | |
193 | << " must be one of {8, 16, 32} : revert to " << DEFAULT_W << std::endl; | |
7c673cae FG |
194 | err = -EINVAL; |
195 | } | |
196 | err |= to_bool("jerasure-per-chunk-alignment", profile, | |
197 | &per_chunk_alignment, "false", ss); | |
198 | return err; | |
199 | } | |
200 | ||
201 | void ErasureCodeJerasureReedSolomonVandermonde::prepare() | |
202 | { | |
203 | matrix = reed_sol_vandermonde_coding_matrix(k, m, w); | |
204 | } | |
205 | ||
206 | // | |
207 | // ErasureCodeJerasureReedSolomonRAID6 | |
208 | // | |
209 | void ErasureCodeJerasureReedSolomonRAID6::jerasure_encode(char **data, | |
210 | char **coding, | |
211 | int blocksize) | |
212 | { | |
213 | reed_sol_r6_encode(k, w, data, coding, blocksize); | |
214 | } | |
215 | ||
216 | int ErasureCodeJerasureReedSolomonRAID6::jerasure_decode(int *erasures, | |
217 | char **data, | |
218 | char **coding, | |
219 | int blocksize) | |
220 | { | |
221 | return jerasure_matrix_decode(k, m, w, matrix, 1, erasures, data, coding, blocksize); | |
222 | } | |
223 | ||
224 | unsigned ErasureCodeJerasureReedSolomonRAID6::get_alignment() const | |
225 | { | |
226 | if (per_chunk_alignment) { | |
227 | return w * LARGEST_VECTOR_WORDSIZE; | |
228 | } else { | |
229 | unsigned alignment = k*w*sizeof(int); | |
230 | if ( ((w*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) | |
231 | alignment = k*w*LARGEST_VECTOR_WORDSIZE; | |
232 | return alignment; | |
233 | } | |
234 | } | |
235 | ||
236 | int ErasureCodeJerasureReedSolomonRAID6::parse(ErasureCodeProfile &profile, | |
237 | ostream *ss) | |
238 | { | |
239 | int err = ErasureCodeJerasure::parse(profile, ss); | |
9f95a23c TL |
240 | if (m != stoi(DEFAULT_M)) { |
241 | *ss << "ReedSolomonRAID6: m=" << m | |
242 | << " must be 2 for RAID6: revert to 2" << std::endl; | |
243 | err = -EINVAL; | |
244 | } | |
7c673cae FG |
245 | if (w != 8 && w != 16 && w != 32) { |
246 | *ss << "ReedSolomonRAID6: w=" << w | |
247 | << " must be one of {8, 16, 32} : revert to 8 " << std::endl; | |
7c673cae FG |
248 | err = -EINVAL; |
249 | } | |
250 | return err; | |
251 | } | |
252 | ||
253 | void ErasureCodeJerasureReedSolomonRAID6::prepare() | |
254 | { | |
255 | matrix = reed_sol_r6_coding_matrix(k, w); | |
256 | } | |
257 | ||
258 | // | |
259 | // ErasureCodeJerasureCauchy | |
260 | // | |
261 | void ErasureCodeJerasureCauchy::jerasure_encode(char **data, | |
262 | char **coding, | |
263 | int blocksize) | |
264 | { | |
265 | jerasure_schedule_encode(k, m, w, schedule, | |
266 | data, coding, blocksize, packetsize); | |
267 | } | |
268 | ||
269 | int ErasureCodeJerasureCauchy::jerasure_decode(int *erasures, | |
270 | char **data, | |
271 | char **coding, | |
272 | int blocksize) | |
273 | { | |
274 | return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, | |
275 | erasures, data, coding, blocksize, packetsize, 1); | |
276 | } | |
277 | ||
278 | unsigned ErasureCodeJerasureCauchy::get_alignment() const | |
279 | { | |
280 | if (per_chunk_alignment) { | |
281 | unsigned alignment = w * packetsize; | |
282 | unsigned modulo = alignment % LARGEST_VECTOR_WORDSIZE; | |
283 | if (modulo) | |
284 | alignment += LARGEST_VECTOR_WORDSIZE - modulo; | |
285 | return alignment; | |
286 | } else { | |
287 | unsigned alignment = k*w*packetsize*sizeof(int); | |
288 | if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) | |
289 | alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE; | |
290 | return alignment; | |
291 | } | |
292 | } | |
293 | ||
294 | int ErasureCodeJerasureCauchy::parse(ErasureCodeProfile &profile, | |
295 | ostream *ss) | |
296 | { | |
297 | int err = ErasureCodeJerasure::parse(profile, ss); | |
298 | err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); | |
299 | err |= to_bool("jerasure-per-chunk-alignment", profile, | |
300 | &per_chunk_alignment, "false", ss); | |
301 | return err; | |
302 | } | |
303 | ||
304 | void ErasureCodeJerasureCauchy::prepare_schedule(int *matrix) | |
305 | { | |
306 | bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix); | |
307 | schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); | |
308 | } | |
309 | ||
b32b8144 FG |
310 | ErasureCodeJerasureCauchy::~ErasureCodeJerasureCauchy() |
311 | { | |
312 | if (bitmatrix) | |
313 | free(bitmatrix); | |
314 | if (schedule) | |
315 | jerasure_free_schedule(schedule); | |
316 | } | |
317 | ||
7c673cae FG |
318 | // |
319 | // ErasureCodeJerasureCauchyOrig | |
320 | // | |
321 | void ErasureCodeJerasureCauchyOrig::prepare() | |
322 | { | |
323 | int *matrix = cauchy_original_coding_matrix(k, m, w); | |
324 | prepare_schedule(matrix); | |
325 | free(matrix); | |
326 | } | |
327 | ||
328 | // | |
329 | // ErasureCodeJerasureCauchyGood | |
330 | // | |
331 | void ErasureCodeJerasureCauchyGood::prepare() | |
332 | { | |
333 | int *matrix = cauchy_good_general_coding_matrix(k, m, w); | |
334 | prepare_schedule(matrix); | |
335 | free(matrix); | |
336 | } | |
337 | ||
338 | // | |
339 | // ErasureCodeJerasureLiberation | |
340 | // | |
341 | ErasureCodeJerasureLiberation::~ErasureCodeJerasureLiberation() | |
342 | { | |
343 | if (bitmatrix) | |
344 | free(bitmatrix); | |
345 | if (schedule) | |
346 | jerasure_free_schedule(schedule); | |
347 | } | |
348 | ||
349 | void ErasureCodeJerasureLiberation::jerasure_encode(char **data, | |
350 | char **coding, | |
351 | int blocksize) | |
352 | { | |
353 | jerasure_schedule_encode(k, m, w, schedule, data, | |
354 | coding, blocksize, packetsize); | |
355 | } | |
356 | ||
357 | int ErasureCodeJerasureLiberation::jerasure_decode(int *erasures, | |
358 | char **data, | |
359 | char **coding, | |
360 | int blocksize) | |
361 | { | |
362 | return jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, | |
363 | coding, blocksize, packetsize, 1); | |
364 | } | |
365 | ||
366 | unsigned ErasureCodeJerasureLiberation::get_alignment() const | |
367 | { | |
368 | unsigned alignment = k*w*packetsize*sizeof(int); | |
369 | if ( ((w*packetsize*sizeof(int))%LARGEST_VECTOR_WORDSIZE) ) | |
370 | alignment = k*w*packetsize*LARGEST_VECTOR_WORDSIZE; | |
371 | return alignment; | |
372 | } | |
373 | ||
374 | bool ErasureCodeJerasureLiberation::check_k(ostream *ss) const | |
375 | { | |
376 | if (k > w) { | |
377 | *ss << "k=" << k << " must be less than or equal to w=" << w << std::endl; | |
378 | return false; | |
379 | } else { | |
380 | return true; | |
381 | } | |
382 | } | |
383 | ||
384 | bool ErasureCodeJerasureLiberation::check_w(ostream *ss) const | |
385 | { | |
386 | if (w <= 2 || !is_prime(w)) { | |
387 | *ss << "w=" << w << " must be greater than two and be prime" << std::endl; | |
388 | return false; | |
389 | } else { | |
390 | return true; | |
391 | } | |
392 | } | |
393 | ||
394 | bool ErasureCodeJerasureLiberation::check_packetsize_set(ostream *ss) const | |
395 | { | |
396 | if (packetsize == 0) { | |
397 | *ss << "packetsize=" << packetsize << " must be set" << std::endl; | |
398 | return false; | |
399 | } else { | |
400 | return true; | |
401 | } | |
402 | } | |
403 | ||
404 | bool ErasureCodeJerasureLiberation::check_packetsize(ostream *ss) const | |
405 | { | |
406 | if ((packetsize%(sizeof(int))) != 0) { | |
407 | *ss << "packetsize=" << packetsize | |
408 | << " must be a multiple of sizeof(int) = " << sizeof(int) << std::endl; | |
409 | return false; | |
410 | } else { | |
411 | return true; | |
412 | } | |
413 | } | |
414 | ||
415 | int ErasureCodeJerasureLiberation::revert_to_default(ErasureCodeProfile &profile, | |
416 | ostream *ss) | |
417 | { | |
418 | int err = 0; | |
419 | *ss << "reverting to k=" << DEFAULT_K << ", w=" | |
420 | << DEFAULT_W << ", packetsize=" << DEFAULT_PACKETSIZE << std::endl; | |
421 | profile["k"] = DEFAULT_K; | |
422 | err |= to_int("k", profile, &k, DEFAULT_K, ss); | |
423 | profile["w"] = DEFAULT_W; | |
424 | err |= to_int("w", profile, &w, DEFAULT_W, ss); | |
425 | profile["packetsize"] = DEFAULT_PACKETSIZE; | |
426 | err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); | |
427 | return err; | |
428 | } | |
429 | ||
430 | int ErasureCodeJerasureLiberation::parse(ErasureCodeProfile &profile, | |
431 | ostream *ss) | |
432 | { | |
433 | int err = ErasureCodeJerasure::parse(profile, ss); | |
434 | err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); | |
435 | ||
436 | bool error = false; | |
437 | if (!check_k(ss)) | |
438 | error = true; | |
439 | if (!check_w(ss)) | |
440 | error = true; | |
441 | if (!check_packetsize_set(ss) || !check_packetsize(ss)) | |
442 | error = true; | |
443 | if (error) { | |
444 | revert_to_default(profile, ss); | |
445 | err = -EINVAL; | |
446 | } | |
447 | return err; | |
448 | } | |
449 | ||
450 | void ErasureCodeJerasureLiberation::prepare() | |
451 | { | |
452 | bitmatrix = liberation_coding_bitmatrix(k, w); | |
453 | schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); | |
454 | } | |
455 | ||
456 | // | |
457 | // ErasureCodeJerasureBlaumRoth | |
458 | // | |
459 | bool ErasureCodeJerasureBlaumRoth::check_w(ostream *ss) const | |
460 | { | |
11fdf7f2 | 461 | // back in Firefly, w = 7 was the default and produced usable |
7c673cae FG |
462 | // chunks. Tolerate this value for backward compatibility. |
463 | if (w == 7) | |
464 | return true; | |
465 | if (w <= 2 || !is_prime(w+1)) { | |
466 | *ss << "w=" << w << " must be greater than two and " | |
467 | << "w+1 must be prime" << std::endl; | |
468 | return false; | |
469 | } else { | |
470 | return true; | |
471 | } | |
472 | } | |
473 | ||
474 | void ErasureCodeJerasureBlaumRoth::prepare() | |
475 | { | |
476 | bitmatrix = blaum_roth_coding_bitmatrix(k, w); | |
477 | schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); | |
478 | } | |
479 | ||
480 | // | |
481 | // ErasureCodeJerasureLiber8tion | |
482 | // | |
483 | int ErasureCodeJerasureLiber8tion::parse(ErasureCodeProfile &profile, | |
484 | ostream *ss) | |
485 | { | |
486 | int err = ErasureCodeJerasure::parse(profile, ss); | |
9f95a23c TL |
487 | if (m != stoi(DEFAULT_M)) { |
488 | *ss << "liber8tion: m=" << m << " must be " << DEFAULT_M | |
489 | << " for liber8tion: revert to " << DEFAULT_M << std::endl; | |
490 | err = -EINVAL; | |
491 | } | |
492 | if (w != stoi(DEFAULT_W)) { | |
493 | *ss << "liber8tion: w=" << w << " must be " << DEFAULT_W | |
494 | << " for liber8tion: revert to " << DEFAULT_W << std::endl; | |
495 | err = -EINVAL; | |
496 | } | |
7c673cae FG |
497 | err |= to_int("packetsize", profile, &packetsize, DEFAULT_PACKETSIZE, ss); |
498 | ||
499 | bool error = false; | |
500 | if (!check_k(ss)) | |
501 | error = true; | |
502 | if (!check_packetsize_set(ss)) | |
503 | error = true; | |
504 | if (error) { | |
505 | revert_to_default(profile, ss); | |
506 | err = -EINVAL; | |
507 | } | |
508 | return err; | |
509 | } | |
510 | ||
511 | void ErasureCodeJerasureLiber8tion::prepare() | |
512 | { | |
513 | bitmatrix = liber8tion_coding_bitmatrix(k); | |
514 | schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix); | |
515 | } |