liberasurecode  1.6.1
Erasure Code API library
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 = 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 
54 static 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 
79 static 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 
90 static 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  */
107 static 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 
179 int 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 
272 out:
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 
283 int 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;
385 out:
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 
395 int 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 
427 int isa_l_element_size(void* desc)
428 {
429  return 8;
430 }
431 
432 int 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 
446 void * 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 
547 error_free:
548  free(desc->matrix);
549 error:
550  free(desc);
551 
552  return NULL;
553 }
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:107
int isa_l_encode(void *desc, char **data, char **parity, int blocksize)
Definition: isa_l_common.c:39
static int get_num_missing_elements(int *missing_idxs)
Definition: isa_l_common.c:79
int isa_l_exit(void *desc)
Definition: isa_l_common.c:432
static unsigned char * isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
Definition: isa_l_common.c:54
int isa_l_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
Definition: isa_l_common.c:179
int isa_l_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
Definition: isa_l_common.c:283
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:90
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:427
void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle, const char *gen_matrix_func_name)
Definition: isa_l_common.c:446
int isa_l_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
Definition: isa_l_common.c:395