liberasurecode 1.6.3
Erasure Code API library
Loading...
Searching...
No Matches
isa_l_common.c
Go to the documentation of this file.
1/*
2 * Copyright 2014 Kevin M Greenan
3 * Copyright 2014 Tushar Gohad
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * Redistributions in binary form must reproduce the above copyright notice, this
12 * list of conditions and the following disclaimer in the documentation and/or
13 * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
14 * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
15 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
17 * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
21 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
22 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
23 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * isa_l_rs_vand backend implementation
26 *
27 * vi: set noai tw=79 ts=4 sw=4:
28 */
29
30#include <stdio.h>
31#include <stdlib.h>
32
33#include "erasurecode.h"
34#include "erasurecode_backend.h"
35#include "erasurecode_helpers.h"
36#include "erasurecode_helpers_ext.h"
37#include "isa_l_common.h"
38
39int isa_l_encode(void *desc, char **data, char **parity,
40 int blocksize)
41{
42 isa_l_descriptor *isa_l_desc = (isa_l_descriptor*) desc;
43
44 unsigned char *g_tbls = isa_l_desc->encode_tables;
45 int k = isa_l_desc->k;
46 int m = isa_l_desc->m;
47
48 /* FIXME - make ec_encode_data return a value */
49 isa_l_desc->ec_encode_data(blocksize, k, m, g_tbls, (unsigned char**)data,
50 (unsigned char**)parity);
51 return 0;
52}
53
54static unsigned char* isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
55{
56 int i = 0, j = 0, l = 0;
57 int n = k + m;
58 unsigned char *decode_matrix = malloc(sizeof(unsigned char) * k * k);
59 uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
60
61 while (i < k && l < n) {
62 if (((1 << l) & missing_bm) == 0) {
63 for (j = 0; j < k; j++) {
64 decode_matrix[(k * i) + j] = encode_matrix[(k * l) + j];
65 }
66 i++;
67 }
68 l++;
69 }
70
71 if (i != k) {
72 free(decode_matrix);
73 decode_matrix = NULL;
74 }
75
76 return decode_matrix;
77}
78
79static int get_num_missing_elements(int *missing_idxs)
80{
81 int i = 0;
82
83 while (missing_idxs[i] > -1) {
84 i++;
85 }
86
87 return i;
88}
89
90static void mult_and_xor_row(unsigned char *to_row,
91 unsigned char *from_row,
92 unsigned char val,
93 int num_elems,
94 gf_mul_func gf_mul)
95{
96 int i;
97
98 for (i = 0; i < num_elems; i++) {
99 to_row[i] ^= gf_mul(val, from_row[i]);
100 }
101}
102
103/*
104 * TODO: Add in missing parity rows and adjust the inverse_rows to
105 * be used for parity.
106 */
107static unsigned char* get_inverse_rows(int k,
108 int m,
109 unsigned char *decode_inverse,
110 unsigned char* encode_matrix,
111 int *missing_idxs,
112 gf_mul_func gf_mul)
113{
114 uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
115 int num_missing_elements = get_num_missing_elements(missing_idxs);
116 unsigned char *inverse_rows = (unsigned char*)malloc(sizeof(unsigned
117 char*) * k * num_missing_elements);
118 int i, j, l = 0;
119 int n = k + m;
120
121 if (NULL == inverse_rows) {
122 return NULL;
123 }
124
125 memset(inverse_rows, 0, sizeof(unsigned
126 char*) * k * num_missing_elements);
127
128 /*
129 * Fill in rows for missing data
130 */
131 for (i = 0; i < k; i++) {
132 if ((1 << i) & missing_bm) {
133 for (j = 0; j < k; j++) {
134 inverse_rows[(l * k) + j] = decode_inverse[(i * k) + j];
135 }
136 l++;
137 }
138 }
139
140 /*
141 * Process missing parity.
142 *
143 * Start with an all-zero row.
144 *
145 * For each data element, if the data element is:
146 *
147 * Available: XOR the corresponding coefficient from the
148 * encoding matrix.
149 *
150 * Unavailable: multiply corresponding coefficient with
151 * the row that corresponds to the missing data in inverse_rows
152 * and XOR the resulting row with this row.
153 */
154 for (i = k; i < n; i++) {
155 // Parity is missing
156 if ((1 << i) & missing_bm) {
157 int d_idx_avail = 0;
158 int d_idx_unavail = 0;
159 for (j = 0; j < k; j++) {
160 // This data is available, so we can use the encode matrix
161 if (((1 << j) & missing_bm) == 0) {
162 inverse_rows[(l * k) + d_idx_avail] ^= encode_matrix[(i * k) + j];
163 d_idx_avail++;
164 } else {
165 mult_and_xor_row(&inverse_rows[l * k],
166 &inverse_rows[d_idx_unavail * k],
167 encode_matrix[(i * k) + j],
168 k,
169 gf_mul);
170 d_idx_unavail++;
171 }
172 }
173 l++;
174 }
175 }
176 return inverse_rows;
177}
178
179int isa_l_decode(void *desc, char **data, char **parity,
180 int *missing_idxs, int blocksize)
181{
182 isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc;
183
184 unsigned char *g_tbls = NULL;
185 unsigned char *decode_matrix = NULL;
186 unsigned char *decode_inverse = NULL;
187 unsigned char *inverse_rows = NULL;
188 unsigned char **decoded_elements = NULL;
189 unsigned char **available_fragments = NULL;
190 int k = isa_l_desc->k;
191 int m = isa_l_desc->m;
192 int n = k + m;
193 int ret = -1;
194 int i, j;
195
196 int num_missing_elements = get_num_missing_elements(missing_idxs);
197 uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
198
199 decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
200
201 if (NULL == decode_matrix) {
202 goto out;
203 }
204
205 decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
206
207 if (NULL == decode_inverse) {
208 goto out;
209 }
210
211 int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
212 if (im_ret < 0) {
213 goto out;
214 }
215
216 // Generate g_tbls from computed decode matrix (k x k) matrix
217 g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
218 if (NULL == g_tbls) {
219 goto out;
220 }
221
222 inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
223
224 decoded_elements = (unsigned char**)malloc(sizeof(unsigned char*)*num_missing_elements);
225 if (NULL == decoded_elements) {
226 goto out;
227 }
228
229 available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
230 if (NULL == available_fragments) {
231 goto out;
232 }
233
234 j = 0;
235 for (i = 0; i < n; i++) {
236 if (missing_bm & (1 << i)) {
237 continue;
238 }
239 if (j == k) {
240 break;
241 }
242 if (i < k) {
243 available_fragments[j] = (unsigned char*)data[i];
244 } else {
245 available_fragments[j] = (unsigned char*)parity[i-k];
246 }
247 j++;
248 }
249
250 // Grab pointers to memory needed for missing data fragments
251 j = 0;
252 for (i = 0; i < k; i++) {
253 if (missing_bm & (1 << i)) {
254 decoded_elements[j] = (unsigned char*)data[i];
255 j++;
256 }
257 }
258 for (i = k; i < n; i++) {
259 if (missing_bm & (1 << i)) {
260 decoded_elements[j] = (unsigned char*)parity[i - k];
261 j++;
262 }
263 }
264
265 isa_l_desc->ec_init_tables(k, num_missing_elements, inverse_rows, g_tbls);
266
267 isa_l_desc->ec_encode_data(blocksize, k, num_missing_elements, g_tbls, (unsigned char**)available_fragments,
268 (unsigned char**)decoded_elements);
269
270 ret = 0;
271
272out:
273 free(g_tbls);
274 free(decode_matrix);
275 free(decode_inverse);
276 free(inverse_rows);
277 free(decoded_elements);
278 free(available_fragments);
279
280 return ret;
281}
282
283int isa_l_reconstruct(void *desc, char **data, char **parity,
284 int *missing_idxs, int destination_idx, int blocksize)
285{
286 isa_l_descriptor *isa_l_desc = (isa_l_descriptor*) desc;
287 unsigned char *g_tbls = NULL;
288 unsigned char *decode_matrix = NULL;
289 unsigned char *decode_inverse = NULL;
290 unsigned char *inverse_rows = NULL;
291 unsigned char *reconstruct_buf = NULL;
292 unsigned char **available_fragments = NULL;
293 int k = isa_l_desc->k;
294 int m = isa_l_desc->m;
295 int n = k + m;
296 int ret = -1;
297 int i, j;
298 uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
299 int inverse_row = -1;
300
305 decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
306
307 if (NULL == decode_matrix) {
308 goto out;
309 }
310
311 decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
312
313 if (NULL == decode_inverse) {
314 goto out;
315 }
316
317 int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
318 if (im_ret < 0) {
319 goto out;
320 }
321
325 inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
326
327 // Generate g_tbls from computed decode matrix (k x k) matrix
328 g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
329 if (NULL == g_tbls) {
330 goto out;
331 }
332
336 available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
337 if (NULL == available_fragments) {
338 goto out;
339 }
340
341 j = 0;
342 for (i = 0; i < n; i++) {
343 if (missing_bm & (1 << i)) {
344 continue;
345 }
346 if (j == k) {
347 break;
348 }
349 if (i < k) {
350 available_fragments[j] = (unsigned char*)data[i];
351 } else {
352 available_fragments[j] = (unsigned char*)parity[i-k];
353 }
354 j++;
355 }
356
360 j = 0;
361 for (i = 0; i < n; i++) {
362 if (missing_bm & (1 << i)) {
363 if (i == destination_idx) {
364 if (i < k) {
365 reconstruct_buf = (unsigned char*)data[i];
366 } else {
367 reconstruct_buf = (unsigned char*)parity[i-k];
368 }
369 inverse_row = j;
370 break;
371 }
372 j++;
373 }
374 }
375
379 isa_l_desc->ec_init_tables(k, 1, &inverse_rows[inverse_row * k], g_tbls);
380
381 isa_l_desc->ec_encode_data(blocksize, k, 1, g_tbls, (unsigned char**)available_fragments,
382 (unsigned char**)&reconstruct_buf);
383
384 ret = 0;
385out:
386 free(g_tbls);
387 free(decode_matrix);
388 free(decode_inverse);
389 free(inverse_rows);
390 free(available_fragments);
391
392 return ret;
393}
394
395int isa_l_min_fragments(void *desc, int *missing_idxs,
396 int *fragments_to_exclude, int *fragments_needed)
397{
398 isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc;
399
400 uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
401 uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
402 int i;
403 int j = 0;
404 int ret = -1;
405
406 for (i = 0; i < (isa_l_desc->k + isa_l_desc->m); i++) {
407 if (!(missing_bm & (1 << i))) {
408 fragments_needed[j] = i;
409 j++;
410 }
411 if (j == isa_l_desc->k) {
412 ret = 0;
413 fragments_needed[j] = -1;
414 break;
415 }
416 }
417
418 return ret;
419}
420
427int isa_l_element_size(void* desc)
428{
429 return 8;
430}
431
432int isa_l_exit(void *desc)
433{
434 isa_l_descriptor *isa_l_desc = NULL;
435
436 isa_l_desc = (isa_l_descriptor*) desc;
437
438 free(isa_l_desc->encode_tables);
439 free(isa_l_desc->matrix);
440 free(isa_l_desc);
441
442 return 0;
443}
444
445
446void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle,
447 const char* gen_matrix_func_name)
448{
449 isa_l_descriptor *desc = NULL;
450
451 desc = (isa_l_descriptor *)malloc(sizeof(isa_l_descriptor));
452 if (NULL == desc) {
453 return NULL;
454 }
455
456 desc->k = args->uargs.k;
457 desc->m = args->uargs.m;
458 if (args->uargs.w <= 0)
459 args->uargs.w = ISA_L_W;
460 desc->w = args->uargs.w;
461
462 /* validate EC arguments */
463 {
464 long long max_symbols = 1LL << desc->w;
465 if ((desc->k + desc->m) > max_symbols) {
466 goto error;
467 }
468 }
469
470 /*
471 * ISO C forbids casting a void* to a function pointer.
472 * Since dlsym return returns a void*, we use this union to
473 * "transform" the void* to a function pointer.
474 */
475 union {
476 ec_encode_data_func encodep;
477 ec_init_tables_func init_tablesp;
478 gf_gen_encoding_matrix_func gen_matrixp;
479 gf_invert_matrix_func invert_matrixp;
480 gf_mul_func gf_mulp;
481 void *vptr;
482 } func_handle = {.vptr = NULL};
483
484 /* fill in function addresses */
485 func_handle.vptr = NULL;
486 func_handle.vptr = dlsym(backend_sohandle, "ec_encode_data");
487 desc->ec_encode_data = func_handle.encodep;
488 if (NULL == desc->ec_encode_data) {
489 goto error;
490 }
491
492 func_handle.vptr = NULL;
493 func_handle.vptr = dlsym(backend_sohandle, "ec_init_tables");
494 desc->ec_init_tables = func_handle.init_tablesp;
495 if (NULL == desc->ec_init_tables) {
496 goto error;
497 }
498
499 func_handle.vptr = NULL;
500 func_handle.vptr = dlsym(backend_sohandle, gen_matrix_func_name);
501 desc->gf_gen_encoding_matrix = func_handle.gen_matrixp;
502 if (NULL == desc->gf_gen_encoding_matrix) {
503 goto error;
504 }
505
506 func_handle.vptr = NULL;
507 func_handle.vptr = dlsym(backend_sohandle, "gf_invert_matrix");
508 desc->gf_invert_matrix = func_handle.invert_matrixp;
509 if (NULL == desc->gf_invert_matrix) {
510 goto error;
511 }
512
513 func_handle.vptr = NULL;
514 func_handle.vptr = dlsym(backend_sohandle, "gf_mul");
515 desc->gf_mul = func_handle.gf_mulp;
516 if (NULL == desc->gf_mul) {
517 goto error;
518 }
519
520 desc->matrix = malloc(sizeof(char) * desc->k * (desc->k + desc->m));
521 if (NULL == desc->matrix) {
522 goto error;
523 }
524
529 desc->gf_gen_encoding_matrix(desc->matrix, desc->k + desc->m, desc->k);
530
531
535 desc->encode_tables = malloc(sizeof(unsigned char) *
536 (desc->k * desc->m * 32));
537 if (NULL == desc->encode_tables) {
538 goto error_free;
539 }
540
541 desc->ec_init_tables(desc->k, desc->m,
542 &desc->matrix[desc->k * desc->k],
543 desc->encode_tables);
544
545 return desc;
546
547error_free:
548 free(desc->matrix);
549error:
550 free(desc);
551
552 return NULL;
553}
int isa_l_encode(void *desc, char **data, char **parity, int blocksize)
static int get_num_missing_elements(int *missing_idxs)
int isa_l_exit(void *desc)
static unsigned char * isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
int isa_l_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
int isa_l_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
static void mult_and_xor_row(unsigned char *to_row, unsigned char *from_row, unsigned char val, int num_elems, gf_mul_func gf_mul)
int isa_l_element_size(void *desc)
Return the element-size, which is the number of bits stored on a given device, per codeword.
static unsigned char * get_inverse_rows(int k, int m, unsigned char *decode_inverse, unsigned char *encode_matrix, int *missing_idxs, gf_mul_func gf_mul)
void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle, const char *gen_matrix_func_name)
int isa_l_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)