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