liberasurecode  1.2.0
Erasure Code API library
 All Data Structures Files Functions Variables Typedefs Macros
isa_l_rs_vand.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 
38 #define ISA_L_RS_VAND_LIB_MAJOR 2
39 #define ISA_L_RS_VAND_LIB_MINOR 13
40 #define ISA_L_RS_VAND_LIB_REV 0
41 #define ISA_L_RS_VAND_LIB_VER_STR "2.13"
42 #define ISA_L_RS_VAND_LIB_NAME "isa_l_rs_vand"
43 #if defined(__MACOS__) || defined(__MACOSX__) || defined(__OSX__) || defined(__APPLE__)
44 #define ISA_L_RS_VAND_SO_NAME "libisal.dylib"
45 #else
46 #define ISA_L_RS_VAND_SO_NAME "libisal.so.2"
47 #endif
48 
49 /* Forward declarations */
50 struct ec_backend_op_stubs isa_l_rs_vand_ops;
51 struct ec_backend isa_l_rs_vand;
52 struct ec_backend_common backend_isa_l_rs_vand;
53 
54 typedef void (*ec_encode_data_func)(int, int, int, unsigned char*, unsigned char **, unsigned char **);
55 typedef void (*ec_init_tables_func)(int, int, unsigned char*, unsigned char *);
56 typedef void (*gf_gen_rs_matrix_func)(unsigned char*, int, int);
57 typedef int (*gf_invert_matrix_func)(unsigned char*, unsigned char*, const int);
58 typedef unsigned char (*gf_mul_func)(unsigned char, unsigned char);
59 
61  /* calls required for init */
64 
65  /* calls required for encode */
67 
68  /* calls required for decode and reconstruct */
70 
71  /* multiplication function used by ISA-L */
73 
74  /* fields needed to hold state */
75  unsigned char *matrix;
76  int k;
77  int m;
78  int w;
79 };
80 
81 static int isa_l_rs_vand_encode(void *desc, char **data, char **parity,
82  int blocksize)
83 {
84  struct isa_l_rs_vand_descriptor *isa_l_desc =
85  (struct isa_l_rs_vand_descriptor*) desc;
86 
87  unsigned char *g_tbls = NULL;
88  int k = isa_l_desc->k;
89  int m = isa_l_desc->m;
90 
91  // Generate g_tbls from encode matrix encode_matrix
92  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
93  if (NULL == g_tbls) {
94  return -1;
95  }
96 
97  isa_l_desc->ec_init_tables(k, m, &isa_l_desc->matrix[k * k], g_tbls);
98 
99  /* FIXME - make ec_encode_data return a value */
100  isa_l_desc->ec_encode_data(blocksize, k, m, g_tbls, (unsigned char**)data,
101  (unsigned char**)parity);
102  free(g_tbls);
103  return 0;
104 }
105 
106 static unsigned char* isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
107 {
108  int i = 0, j = 0, l = 0;
109  int n = k + m;
110  unsigned char *decode_matrix = malloc(sizeof(unsigned char) * k * k);
111  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
112 
113  while (i < k && l < n) {
114  if (((1 << l) & missing_bm) == 0) {
115  for (j = 0; j < k; j++) {
116  decode_matrix[(k * i) + j] = encode_matrix[(k * l) + j];
117  }
118  i++;
119  }
120  l++;
121  }
122 
123  if (i != k) {
124  free(decode_matrix);
125  decode_matrix = NULL;
126  }
127 
128  return decode_matrix;
129 }
130 
131 static int get_num_missing_elements(int *missing_idxs)
132 {
133  int i = 0;
134 
135  while (missing_idxs[i] > -1) {
136  i++;
137  }
138 
139  return i;
140 }
141 
142 static void mult_and_xor_row(unsigned char *to_row,
143  unsigned char *from_row,
144  unsigned char val,
145  int num_elems,
147 {
148  int i;
149 
150  for (i = 0; i < num_elems; i++) {
151  to_row[i] ^= gf_mul(val, from_row[i]);
152  }
153 }
154 
155 /*
156  * TODO: Add in missing parity rows and adjust the inverse_rows to
157  * be used for parity.
158  */
159 static unsigned char* get_inverse_rows(int k,
160  int m,
161  unsigned char *decode_inverse,
162  unsigned char* encode_matrix,
163  int *missing_idxs,
165 {
166  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
167  int num_missing_elements = get_num_missing_elements(missing_idxs);
168  unsigned char *inverse_rows = (unsigned char*)malloc(sizeof(unsigned
169  char*) * k * num_missing_elements);
170  int i, j, l = 0;
171  int n = k + m;
172 
173  if (NULL == inverse_rows) {
174  return NULL;
175  }
176 
177  memset(inverse_rows, 0, sizeof(unsigned
178  char*) * k * num_missing_elements);
179 
180  /*
181  * Fill in rows for missing data
182  */
183  for (i = 0; i < k; i++) {
184  if ((1 << i) & missing_bm) {
185  for (j = 0; j < k; j++) {
186  inverse_rows[(l * k) + j] = decode_inverse[(i * k) + j];
187  }
188  l++;
189  }
190  }
191 
192  /*
193  * Process missing parity.
194  *
195  * Start with an all-zero row.
196  *
197  * For each data element, if the data element is:
198  *
199  * Available: XOR the corresponding coefficient from the
200  * encoding matrix.
201  *
202  * Unavailable: multiply corresponding coefficient with
203  * the row that corresponds to the missing data in inverse_rows
204  * and XOR the resulting row with this row.
205  */
206  for (i = k; i < n; i++) {
207  // Parity is missing
208  if ((1 << i) & missing_bm) {
209  int d_idx_avail = 0;
210  int d_idx_unavail = 0;
211  for (j = 0; j < k; j++) {
212  // This data is available, so we can use the encode matrix
213  if (((1 << j) & missing_bm) == 0) {
214  inverse_rows[(l * k) + d_idx_avail] ^= encode_matrix[(i * k) + j];
215  d_idx_avail++;
216  } else {
217  mult_and_xor_row(&inverse_rows[l * k],
218  &inverse_rows[d_idx_unavail * k],
219  encode_matrix[(i * k) + j],
220  k,
221  gf_mul);
222  d_idx_unavail++;
223  }
224  }
225  l++;
226  }
227  }
228  return inverse_rows;
229 }
230 
231 static int isa_l_rs_vand_decode(void *desc, char **data, char **parity,
232  int *missing_idxs, int blocksize)
233 {
234  struct isa_l_rs_vand_descriptor *isa_l_desc =
235  (struct isa_l_rs_vand_descriptor*)desc;
236 
237  unsigned char *g_tbls = NULL;
238  unsigned char *decode_matrix = NULL;
239  unsigned char *decode_inverse = NULL;
240  unsigned char *inverse_rows = NULL;
241  unsigned char **decoded_elements = NULL;
242  unsigned char **available_fragments = NULL;
243  int k = isa_l_desc->k;
244  int m = isa_l_desc->m;
245  int n = k + m;
246  int ret = -1;
247  int i, j;
248 
249  int num_missing_elements = get_num_missing_elements(missing_idxs);
250  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
251 
252  decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
253 
254  if (NULL == decode_matrix) {
255  goto out;
256  }
257 
258  decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
259 
260  if (NULL == decode_inverse) {
261  goto out;
262  }
263 
264  isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
265 
266  // Generate g_tbls from computed decode matrix (k x k) matrix
267  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
268  if (NULL == g_tbls) {
269  goto out;
270  }
271 
272  inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
273 
274  decoded_elements = (unsigned char**)malloc(sizeof(unsigned char*)*num_missing_elements);
275  if (NULL == decoded_elements) {
276  goto out;
277  }
278 
279  available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
280  if (NULL == available_fragments) {
281  goto out;
282  }
283 
284  j = 0;
285  for (i = 0; i < n; i++) {
286  if (missing_bm & (1 << i)) {
287  continue;
288  }
289  if (j == k) {
290  break;
291  }
292  if (i < k) {
293  available_fragments[j] = (unsigned char*)data[i];
294  } else {
295  available_fragments[j] = (unsigned char*)parity[i-k];
296  }
297  j++;
298  }
299 
300  // Grab pointers to memory needed for missing data fragments
301  j = 0;
302  for (i = 0; i < k; i++) {
303  if (missing_bm & (1 << i)) {
304  decoded_elements[j] = (unsigned char*)data[i];
305  j++;
306  }
307  }
308  for (i = k; i < n; i++) {
309  if (missing_bm & (1 << i)) {
310  decoded_elements[j] = (unsigned char*)parity[i - k];
311  j++;
312  }
313  }
314 
315  isa_l_desc->ec_init_tables(k, num_missing_elements, inverse_rows, g_tbls);
316 
317  isa_l_desc->ec_encode_data(blocksize, k, num_missing_elements, g_tbls, (unsigned char**)available_fragments,
318  (unsigned char**)decoded_elements);
319 
320  ret = 0;
321 
322 out:
323  free(g_tbls);
324  free(decode_matrix);
325  free(decode_inverse);
326  free(inverse_rows);
327  free(decoded_elements);
328  free(available_fragments);
329 
330  return ret;
331 }
332 
333 static int isa_l_rs_vand_reconstruct(void *desc, char **data, char **parity,
334  int *missing_idxs, int destination_idx, int blocksize)
335 {
336  struct isa_l_rs_vand_descriptor *isa_l_desc =
337  (struct isa_l_rs_vand_descriptor*) desc;
338  unsigned char *g_tbls = NULL;
339  unsigned char *decode_matrix = NULL;
340  unsigned char *decode_inverse = NULL;
341  unsigned char *inverse_rows = NULL;
342  unsigned char *reconstruct_buf = NULL;
343  unsigned char **available_fragments = NULL;
344  int k = isa_l_desc->k;
345  int m = isa_l_desc->m;
346  int n = k + m;
347  int ret = -1;
348  int i, j;
349  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs);
350  int inverse_row = -1;
351 
356  decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs);
357 
358  if (NULL == decode_matrix) {
359  goto out;
360  }
361 
362  decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k);
363 
364  if (NULL == decode_inverse) {
365  goto out;
366  }
367 
368  isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k);
369 
373  inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul);
374 
375  // Generate g_tbls from computed decode matrix (k x k) matrix
376  g_tbls = malloc(sizeof(unsigned char) * (k * m * 32));
377  if (NULL == g_tbls) {
378  goto out;
379  }
380 
384  available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k);
385  if (NULL == available_fragments) {
386  goto out;
387  }
388 
389  j = 0;
390  for (i = 0; i < n; i++) {
391  if (missing_bm & (1 << i)) {
392  continue;
393  }
394  if (j == k) {
395  break;
396  }
397  if (i < k) {
398  available_fragments[j] = (unsigned char*)data[i];
399  } else {
400  available_fragments[j] = (unsigned char*)parity[i-k];
401  }
402  j++;
403  }
404 
408  j = 0;
409  for (i = 0; i < n; i++) {
410  if (missing_bm & (1 << i)) {
411  if (i == destination_idx) {
412  if (i < k) {
413  reconstruct_buf = (unsigned char*)data[i];
414  } else {
415  reconstruct_buf = (unsigned char*)parity[i-k];
416  }
417  inverse_row = j;
418  break;
419  }
420  j++;
421  }
422  }
423 
427  isa_l_desc->ec_init_tables(k, 1, &inverse_rows[inverse_row * k], g_tbls);
428 
429  isa_l_desc->ec_encode_data(blocksize, k, 1, g_tbls, (unsigned char**)available_fragments,
430  (unsigned char**)&reconstruct_buf);
431 
432  ret = 0;
433 out:
434  free(g_tbls);
435  free(decode_matrix);
436  free(decode_inverse);
437  free(inverse_rows);
438  free(available_fragments);
439 
440  return ret;
441 }
442 
443 static int isa_l_rs_vand_min_fragments(void *desc, int *missing_idxs,
444  int *fragments_to_exclude, int *fragments_needed)
445 {
446  struct isa_l_rs_vand_descriptor *isa_l_desc =
447  (struct isa_l_rs_vand_descriptor*)desc;
448 
449  uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
450  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
451  int i;
452  int j = 0;
453  int ret = -1;
454 
455  for (i = 0; i < (isa_l_desc->k + isa_l_desc->m); i++) {
456  if (!(missing_bm & (1 << i))) {
457  fragments_needed[j] = i;
458  j++;
459  }
460  if (j == isa_l_desc->k) {
461  ret = 0;
462  fragments_needed[j] = -1;
463  break;
464  }
465  }
466 
467  return ret;
468 }
469 
470 #define ISA_L_W 8
471 static void * isa_l_rs_vand_init(struct ec_backend_args *args,
472  void *backend_sohandle)
473 {
474  struct isa_l_rs_vand_descriptor *desc = NULL;
475 
476  desc = (struct isa_l_rs_vand_descriptor *)
477  malloc(sizeof(struct isa_l_rs_vand_descriptor));
478  if (NULL == desc) {
479  return NULL;
480  }
481 
482  desc->k = args->uargs.k;
483  desc->m = args->uargs.m;
484  if (args->uargs.w <= 0)
485  args->uargs.w = ISA_L_W;
486  desc->w = args->uargs.w;
487 
488  /* validate EC arguments */
489  {
490  long long max_symbols = 1LL << desc->w;
491  if ((desc->k + desc->m) > max_symbols) {
492  goto error;
493  }
494  }
495 
496  /*
497  * ISO C forbids casting a void* to a function pointer.
498  * Since dlsym return returns a void*, we use this union to
499  * "transform" the void* to a function pointer.
500  */
501  union {
502  ec_encode_data_func encodep;
503  ec_init_tables_func init_tablesp;
504  gf_gen_rs_matrix_func gen_matrixp;
505  gf_invert_matrix_func invert_matrixp;
506  gf_mul_func gf_mulp;
507  void *vptr;
508  } func_handle = {.vptr = NULL};
509 
510  /* fill in function addresses */
511  func_handle.vptr = NULL;
512  func_handle.vptr = dlsym(backend_sohandle, "ec_encode_data");
513  desc->ec_encode_data = func_handle.encodep;
514  if (NULL == desc->ec_encode_data) {
515  goto error;
516  }
517 
518  func_handle.vptr = NULL;
519  func_handle.vptr = dlsym(backend_sohandle, "ec_init_tables");
520  desc->ec_init_tables = func_handle.init_tablesp;
521  if (NULL == desc->ec_init_tables) {
522  goto error;
523  }
524 
525  func_handle.vptr = NULL;
526  func_handle.vptr = dlsym(backend_sohandle, "gf_gen_rs_matrix");
527  desc->gf_gen_rs_matrix = func_handle.gen_matrixp;
528  if (NULL == desc->gf_gen_rs_matrix) {
529  goto error;
530  }
531 
532  func_handle.vptr = NULL;
533  func_handle.vptr = dlsym(backend_sohandle, "gf_invert_matrix");
534  desc->gf_invert_matrix = func_handle.invert_matrixp;
535  if (NULL == desc->gf_invert_matrix) {
536  goto error;
537  }
538 
539  func_handle.vptr = NULL;
540  func_handle.vptr = dlsym(backend_sohandle, "gf_mul");
541  desc->gf_mul = func_handle.gf_mulp;
542  if (NULL == desc->gf_mul) {
543  goto error;
544  }
545 
546  desc->matrix = malloc(sizeof(char) * desc->k * (desc->k + desc->m));
547  if (NULL == desc->matrix) {
548  goto error;
549  }
550 
554  desc->gf_gen_rs_matrix(desc->matrix, desc->k + desc->m, desc->k);
555 
556  return desc;
557 
558 error:
559  free(desc);
560 
561  return NULL;
562 }
563 
570 static int
572 {
573  return 8;
574 }
575 
576 static int isa_l_rs_vand_exit(void *desc)
577 {
578  struct isa_l_rs_vand_descriptor *isa_l_desc = NULL;
579 
580  isa_l_desc = (struct isa_l_rs_vand_descriptor*) desc;
581 
582  free(isa_l_desc);
583 
584  return 0;
585 }
586 
587 /*
588  * For the time being, we only claim compatibility with versions that
589  * match exactly
590  */
591 static bool isa_l_rs_vand_is_compatible_with(uint32_t version) {
592  return version == backend_isa_l_rs_vand.ec_backend_version;
593 }
594 
595 struct ec_backend_op_stubs isa_l_rs_vand_op_stubs = {
596  .INIT = isa_l_rs_vand_init,
597  .EXIT = isa_l_rs_vand_exit,
598  .ENCODE = isa_l_rs_vand_encode,
599  .DECODE = isa_l_rs_vand_decode,
600  .FRAGSNEEDED = isa_l_rs_vand_min_fragments,
601  .RECONSTRUCT = isa_l_rs_vand_reconstruct,
602  .ELEMENTSIZE = isa_l_rs_vand_element_size,
603  .ISCOMPATIBLEWITH = isa_l_rs_vand_is_compatible_with,
604 };
605 
606 struct ec_backend_common backend_isa_l_rs_vand = {
607  .id = EC_BACKEND_ISA_L_RS_VAND,
608  .name = ISA_L_RS_VAND_LIB_NAME,
609  .soname = ISA_L_RS_VAND_SO_NAME,
610  .soversion = ISA_L_RS_VAND_LIB_VER_STR,
611  .ops = &isa_l_rs_vand_op_stubs,
612  .backend_metadata_size = 0,
613  .ec_backend_version = _VERSION(ISA_L_RS_VAND_LIB_MAJOR,
616 };
static unsigned char * isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs)
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)
unsigned char * matrix
Definition: isa_l_rs_vand.c:75
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)
static int isa_l_rs_vand_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
#define ISA_L_RS_VAND_LIB_MINOR
Definition: isa_l_rs_vand.c:39
struct ec_backend_op_stubs isa_l_rs_vand_ops
Definition: isa_l_rs_vand.c:50
static bool isa_l_rs_vand_is_compatible_with(uint32_t version)
ec_init_tables_func ec_init_tables
Definition: isa_l_rs_vand.c:62
struct ec_backend isa_l_rs_vand
Definition: isa_l_rs_vand.c:51
#define ISA_L_RS_VAND_LIB_VER_STR
Definition: isa_l_rs_vand.c:41
static void * isa_l_rs_vand_init(struct ec_backend_args *args, void *backend_sohandle)
#define ISA_L_RS_VAND_LIB_NAME
Definition: isa_l_rs_vand.c:42
#define ISA_L_RS_VAND_SO_NAME
Definition: isa_l_rs_vand.c:46
static int get_num_missing_elements(int *missing_idxs)
static int isa_l_rs_vand_exit(void *desc)
static int isa_l_rs_vand_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
struct ec_backend_common backend_isa_l_rs_vand
Definition: isa_l_rs_vand.c:52
unsigned char(* gf_mul_func)(unsigned char, unsigned char)
Definition: isa_l_rs_vand.c:58
struct ec_backend_op_stubs isa_l_rs_vand_op_stubs
static int isa_l_rs_vand_encode(void *desc, char **data, char **parity, int blocksize)
Definition: isa_l_rs_vand.c:81
void(* ec_init_tables_func)(int, int, unsigned char *, unsigned char *)
Definition: isa_l_rs_vand.c:55
#define ISA_L_W
void(* gf_gen_rs_matrix_func)(unsigned char *, int, int)
Definition: isa_l_rs_vand.c:56
gf_gen_rs_matrix_func gf_gen_rs_matrix
Definition: isa_l_rs_vand.c:63
ec_encode_data_func ec_encode_data
Definition: isa_l_rs_vand.c:66
static int isa_l_rs_vand_element_size(void *desc)
Return the element-size, which is the number of bits stored on a given device, per codeword...
#define ISA_L_RS_VAND_LIB_MAJOR
Definition: isa_l_rs_vand.c:38
int(* gf_invert_matrix_func)(unsigned char *, unsigned char *, const int)
Definition: isa_l_rs_vand.c:57
void(* ec_encode_data_func)(int, int, int, unsigned char *, unsigned char **, unsigned char **)
Definition: isa_l_rs_vand.c:54
gf_invert_matrix_func gf_invert_matrix
Definition: isa_l_rs_vand.c:69
static int isa_l_rs_vand_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
#define ISA_L_RS_VAND_LIB_REV
Definition: isa_l_rs_vand.c:40