liberasurecode  1.4.0
Erasure Code API library
 All Data Structures Files Functions Variables Typedefs Macros
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 
39 int 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 = NULL;
45  int k = isa_l_desc->k;
46  int m = isa_l_desc->m;
47 
48  // Generate g_tbls from encode matrix encode_matrix
49  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
50  if (NULL == g_tbls) {
51  return -1;
52  }
53 
54  isa_l_desc->ec_init_tables(k, m, &isa_l_desc->matrix[k * k], g_tbls);
55 
56  /* FIXME - make ec_encode_data return a value */
57  isa_l_desc->ec_encode_data(blocksize, k, m, g_tbls, (unsigned char**)data,
58  (unsigned char**)parity);
59  free(g_tbls);
60  return 0;
61 }
62 
63 static unsigned char* isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
64 {
65  int i = 0, j = 0, l = 0;
66  int n = k + m;
67  unsigned char *decode_matrix = malloc(sizeof(unsigned char) * k * k);
68  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
69 
70  while (i < k && l < n) {
71  if (((1 << l) & missing_bm) == 0) {
72  for (j = 0; j < k; j++) {
73  decode_matrix[(k * i) + j] = encode_matrix[(k * l) + j];
74  }
75  i++;
76  }
77  l++;
78  }
79 
80  if (i != k) {
81  free(decode_matrix);
82  decode_matrix = NULL;
83  }
84 
85  return decode_matrix;
86 }
87 
88 static int get_num_missing_elements(int *missing_idxs)
89 {
90  int i = 0;
91 
92  while (missing_idxs[i] > -1) {
93  i++;
94  }
95 
96  return i;
97 }
98 
99 static void mult_and_xor_row(unsigned char *to_row,
100  unsigned char *from_row,
101  unsigned char val,
102  int num_elems,
103  gf_mul_func gf_mul)
104 {
105  int i;
106 
107  for (i = 0; i < num_elems; i++) {
108  to_row[i] ^= gf_mul(val, from_row[i]);
109  }
110 }
111 
112 /*
113  * TODO: Add in missing parity rows and adjust the inverse_rows to
114  * be used for parity.
115  */
116 static unsigned char* get_inverse_rows(int k,
117  int m,
118  unsigned char *decode_inverse,
119  unsigned char* encode_matrix,
120  int *missing_idxs,
121  gf_mul_func gf_mul)
122 {
123  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
124  int num_missing_elements = get_num_missing_elements(missing_idxs);
125  unsigned char *inverse_rows = (unsigned char*)malloc(sizeof(unsigned
126  char*) * k * num_missing_elements);
127  int i, j, l = 0;
128  int n = k + m;
129 
130  if (NULL == inverse_rows) {
131  return NULL;
132  }
133 
134  memset(inverse_rows, 0, sizeof(unsigned
135  char*) * k * num_missing_elements);
136 
137  /*
138  * Fill in rows for missing data
139  */
140  for (i = 0; i < k; i++) {
141  if ((1 << i) & missing_bm) {
142  for (j = 0; j < k; j++) {
143  inverse_rows[(l * k) + j] = decode_inverse[(i * k) + j];
144  }
145  l++;
146  }
147  }
148 
149  /*
150  * Process missing parity.
151  *
152  * Start with an all-zero row.
153  *
154  * For each data element, if the data element is:
155  *
156  * Available: XOR the corresponding coefficient from the
157  * encoding matrix.
158  *
159  * Unavailable: multiply corresponding coefficient with
160  * the row that corresponds to the missing data in inverse_rows
161  * and XOR the resulting row with this row.
162  */
163  for (i = k; i < n; i++) {
164  // Parity is missing
165  if ((1 << i) & missing_bm) {
166  int d_idx_avail = 0;
167  int d_idx_unavail = 0;
168  for (j = 0; j < k; j++) {
169  // This data is available, so we can use the encode matrix
170  if (((1 << j) & missing_bm) == 0) {
171  inverse_rows[(l * k) + d_idx_avail] ^= encode_matrix[(i * k) + j];
172  d_idx_avail++;
173  } else {
174  mult_and_xor_row(&inverse_rows[l * k],
175  &inverse_rows[d_idx_unavail * k],
176  encode_matrix[(i * k) + j],
177  k,
178  gf_mul);
179  d_idx_unavail++;
180  }
181  }
182  l++;
183  }
184  }
185  return inverse_rows;
186 }
187 
188 int isa_l_decode(void *desc, char **data, char **parity,
189  int *missing_idxs, int blocksize)
190 {
191  isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc;
192 
193  unsigned char *g_tbls = NULL;
194  unsigned char *decode_matrix = NULL;
195  unsigned char *decode_inverse = NULL;
196  unsigned char *inverse_rows = NULL;
197  unsigned char **decoded_elements = NULL;
198  unsigned char **available_fragments = NULL;
199  int k = isa_l_desc->k;
200  int m = isa_l_desc->m;
201  int n = k + m;
202  int ret = -1;
203  int i, j;
204 
205  int num_missing_elements = get_num_missing_elements(missing_idxs);
206  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
207 
208  decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
209 
210  if (NULL == decode_matrix) {
211  goto out;
212  }
213 
214  decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
215 
216  if (NULL == decode_inverse) {
217  goto out;
218  }
219 
220  int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
221  if (im_ret < 0) {
222  goto out;
223  }
224 
225  // Generate g_tbls from computed decode matrix (k x k) matrix
226  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
227  if (NULL == g_tbls) {
228  goto out;
229  }
230 
231  inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
232 
233  decoded_elements = (unsigned char**)malloc(sizeof(unsigned char*)*num_missing_elements);
234  if (NULL == decoded_elements) {
235  goto out;
236  }
237 
238  available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
239  if (NULL == available_fragments) {
240  goto out;
241  }
242 
243  j = 0;
244  for (i = 0; i < n; i++) {
245  if (missing_bm & (1 << i)) {
246  continue;
247  }
248  if (j == k) {
249  break;
250  }
251  if (i < k) {
252  available_fragments[j] = (unsigned char*)data[i];
253  } else {
254  available_fragments[j] = (unsigned char*)parity[i-k];
255  }
256  j++;
257  }
258 
259  // Grab pointers to memory needed for missing data fragments
260  j = 0;
261  for (i = 0; i < k; i++) {
262  if (missing_bm & (1 << i)) {
263  decoded_elements[j] = (unsigned char*)data[i];
264  j++;
265  }
266  }
267  for (i = k; i < n; i++) {
268  if (missing_bm & (1 << i)) {
269  decoded_elements[j] = (unsigned char*)parity[i - k];
270  j++;
271  }
272  }
273 
274  isa_l_desc->ec_init_tables(k, num_missing_elements, inverse_rows, g_tbls);
275 
276  isa_l_desc->ec_encode_data(blocksize, k, num_missing_elements, g_tbls, (unsigned char**)available_fragments,
277  (unsigned char**)decoded_elements);
278 
279  ret = 0;
280 
281 out:
282  free(g_tbls);
283  free(decode_matrix);
284  free(decode_inverse);
285  free(inverse_rows);
286  free(decoded_elements);
287  free(available_fragments);
288 
289  return ret;
290 }
291 
292 int isa_l_reconstruct(void *desc, char **data, char **parity,
293  int *missing_idxs, int destination_idx, int blocksize)
294 {
295  isa_l_descriptor *isa_l_desc = (isa_l_descriptor*) desc;
296  unsigned char *g_tbls = NULL;
297  unsigned char *decode_matrix = NULL;
298  unsigned char *decode_inverse = NULL;
299  unsigned char *inverse_rows = NULL;
300  unsigned char *reconstruct_buf = NULL;
301  unsigned char **available_fragments = NULL;
302  int k = isa_l_desc->k;
303  int m = isa_l_desc->m;
304  int n = k + m;
305  int ret = -1;
306  int i, j;
307  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
308  int inverse_row = -1;
309 
314  decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
315 
316  if (NULL == decode_matrix) {
317  goto out;
318  }
319 
320  decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
321 
322  if (NULL == decode_inverse) {
323  goto out;
324  }
325 
326  int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
327  if (im_ret < 0) {
328  goto out;
329  }
330 
334  inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
335 
336  // Generate g_tbls from computed decode matrix (k x k) matrix
337  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
338  if (NULL == g_tbls) {
339  goto out;
340  }
341 
345  available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
346  if (NULL == available_fragments) {
347  goto out;
348  }
349 
350  j = 0;
351  for (i = 0; i < n; i++) {
352  if (missing_bm & (1 << i)) {
353  continue;
354  }
355  if (j == k) {
356  break;
357  }
358  if (i < k) {
359  available_fragments[j] = (unsigned char*)data[i];
360  } else {
361  available_fragments[j] = (unsigned char*)parity[i-k];
362  }
363  j++;
364  }
365 
369  j = 0;
370  for (i = 0; i < n; i++) {
371  if (missing_bm & (1 << i)) {
372  if (i == destination_idx) {
373  if (i < k) {
374  reconstruct_buf = (unsigned char*)data[i];
375  } else {
376  reconstruct_buf = (unsigned char*)parity[i-k];
377  }
378  inverse_row = j;
379  break;
380  }
381  j++;
382  }
383  }
384 
388  isa_l_desc->ec_init_tables(k, 1, &inverse_rows[inverse_row * k], g_tbls);
389 
390  isa_l_desc->ec_encode_data(blocksize, k, 1, g_tbls, (unsigned char**)available_fragments,
391  (unsigned char**)&reconstruct_buf);
392 
393  ret = 0;
394 out:
395  free(g_tbls);
396  free(decode_matrix);
397  free(decode_inverse);
398  free(inverse_rows);
399  free(available_fragments);
400 
401  return ret;
402 }
403 
404 int isa_l_min_fragments(void *desc, int *missing_idxs,
405  int *fragments_to_exclude, int *fragments_needed)
406 {
407  isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc;
408 
409  uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
410  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
411  int i;
412  int j = 0;
413  int ret = -1;
414 
415  for (i = 0; i < (isa_l_desc->k + isa_l_desc->m); i++) {
416  if (!(missing_bm & (1 << i))) {
417  fragments_needed[j] = i;
418  j++;
419  }
420  if (j == isa_l_desc->k) {
421  ret = 0;
422  fragments_needed[j] = -1;
423  break;
424  }
425  }
426 
427  return ret;
428 }
429 
436 int isa_l_element_size(void* desc)
437 {
438  return 8;
439 }
440 
441 int isa_l_exit(void *desc)
442 {
443  isa_l_descriptor *isa_l_desc = NULL;
444 
445  isa_l_desc = (isa_l_descriptor*) desc;
446 
447  free(isa_l_desc);
448 
449  return 0;
450 }
451 
452 
453 void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle,
454  const char* gen_matrix_func_name)
455 {
456  isa_l_descriptor *desc = NULL;
457 
458  desc = (isa_l_descriptor *)malloc(sizeof(isa_l_descriptor));
459  if (NULL == desc) {
460  return NULL;
461  }
462 
463  desc->k = args->uargs.k;
464  desc->m = args->uargs.m;
465  if (args->uargs.w <= 0)
466  args->uargs.w = ISA_L_W;
467  desc->w = args->uargs.w;
468 
469  /* validate EC arguments */
470  {
471  long long max_symbols = 1LL << desc->w;
472  if ((desc->k + desc->m) > max_symbols) {
473  goto error;
474  }
475  }
476 
477  /*
478  * ISO C forbids casting a void* to a function pointer.
479  * Since dlsym return returns a void*, we use this union to
480  * "transform" the void* to a function pointer.
481  */
482  union {
483  ec_encode_data_func encodep;
484  ec_init_tables_func init_tablesp;
485  gf_gen_encoding_matrix_func gen_matrixp;
486  gf_invert_matrix_func invert_matrixp;
487  gf_mul_func gf_mulp;
488  void *vptr;
489  } func_handle = {.vptr = NULL};
490 
491  /* fill in function addresses */
492  func_handle.vptr = NULL;
493  func_handle.vptr = dlsym(backend_sohandle, "ec_encode_data");
494  desc->ec_encode_data = func_handle.encodep;
495  if (NULL == desc->ec_encode_data) {
496  goto error;
497  }
498 
499  func_handle.vptr = NULL;
500  func_handle.vptr = dlsym(backend_sohandle, "ec_init_tables");
501  desc->ec_init_tables = func_handle.init_tablesp;
502  if (NULL == desc->ec_init_tables) {
503  goto error;
504  }
505 
506  func_handle.vptr = NULL;
507  func_handle.vptr = dlsym(backend_sohandle, gen_matrix_func_name);
508  desc->gf_gen_encoding_matrix = func_handle.gen_matrixp;
509  if (NULL == desc->gf_gen_encoding_matrix) {
510  goto error;
511  }
512 
513  func_handle.vptr = NULL;
514  func_handle.vptr = dlsym(backend_sohandle, "gf_invert_matrix");
515  desc->gf_invert_matrix = func_handle.invert_matrixp;
516  if (NULL == desc->gf_invert_matrix) {
517  goto error;
518  }
519 
520  func_handle.vptr = NULL;
521  func_handle.vptr = dlsym(backend_sohandle, "gf_mul");
522  desc->gf_mul = func_handle.gf_mulp;
523  if (NULL == desc->gf_mul) {
524  goto error;
525  }
526 
527  desc->matrix = malloc(sizeof(char) * desc->k * (desc->k + desc->m));
528  if (NULL == desc->matrix) {
529  goto error;
530  }
531 
536  desc->gf_gen_encoding_matrix(desc->matrix, desc->k + desc->m, desc->k);
537 
538  return desc;
539 
540 error:
541  free(desc);
542 
543  return NULL;
544 }
static unsigned char * isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
Definition: isa_l_common.c:63
int isa_l_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
Definition: isa_l_common.c:292
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)
Definition: isa_l_common.c:116
int isa_l_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
Definition: isa_l_common.c:404
void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle, const char *gen_matrix_func_name)
Definition: isa_l_common.c:453
int isa_l_exit(void *desc)
Definition: isa_l_common.c:441
int isa_l_encode(void *desc, char **data, char **parity, int blocksize)
Definition: isa_l_common.c:39
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)
Definition: isa_l_common.c:99
int isa_l_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
Definition: isa_l_common.c:188
int isa_l_element_size(void *desc)
Return the element-size, which is the number of bits stored on a given device, per codeword...
Definition: isa_l_common.c:436
static int get_num_missing_elements(int *missing_idxs)
Definition: isa_l_common.c:88