liberasurecode  1.6.2
Erasure Code API library
jerasure_rs_vand.c
Go to the documentation of this file.
1 /*
2  * Copyright 2014 Kevin M Greenan
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * Redistributions of source code must retain the above copyright notice, this
8  * list of conditions and the following disclaimer.
9  *
10  * Redistributions in binary form must reproduce the above copyright notice, this
11  * list of conditions and the following disclaimer in the documentation and/or
12  * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
13  * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
14  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16  * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
18  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
21  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23  *
24  * jerasure_rs_vand backend implementation
25  *
26  * vi: set noai tw=79 ts=4 sw=4:
27  */
28 
29 #include <stdio.h>
30 #include <stdlib.h>
31 
32 #include "erasurecode.h"
33 #include "erasurecode_backend.h"
34 #include "erasurecode_helpers.h"
35 #include "erasurecode_helpers_ext.h"
36 
37 #define JERASURE_RS_VAND_LIB_MAJOR 2
38 #define JERASURE_RS_VAND_LIB_MINOR 0
39 #define JERASURE_RS_VAND_LIB_REV 0
40 #define JERASURE_RS_VAND_LIB_VER_STR "2.0"
41 #define JERASURE_RS_VAND_LIB_NAME "jerasure_rs_vand"
42 #if defined(__MACOS__) || defined(__MACOSX__) || defined(__OSX__) || defined(__APPLE__)
43 #define JERASURE_RS_VAND_SO_NAME "libJerasure.dylib"
44 #else
45 #define JERASURE_RS_VAND_SO_NAME "libJerasure.so.2"
46 #endif
47 
48 /* Forward declarations */
49 struct ec_backend_op_stubs jerasure_rs_vand_ops;
50 struct ec_backend jerasure_rs_vand;
51 struct ec_backend_common backend_jerasure_rs_vand;
52 
53 typedef int* (*reed_sol_vandermonde_coding_matrix_func)(int, int, int);
54 typedef void (*jerasure_matrix_encode_func)(int, int, int, int*, char **, char **, int);
55 typedef int (*jerasure_matrix_decode_func)(int, int, int, int *, int, int*, char **, char **, int);
56 typedef int (*jerasure_make_decoding_matrix_func)(int, int, int, int *, int *, int *, int *);
57 typedef int * (*jerasure_erasures_to_erased_func)(int, int, int *);
58 typedef void (*jerasure_matrix_dotprod_func)(int, int, int *,int *, int,char **, char **, int);
59 typedef void (*galois_uninit_field_func)(int);
60 
62  /* calls required for init */
64 
65  /* calls required for free */
67 
68  /* calls required for encode */
70 
71  /* calls required for decode */
73 
74  /* calls required for reconstruct */
78 
79  /* fields needed to hold state */
80  int *matrix;
81  int k;
82  int m;
83  int w;
84 };
85 
86 static int jerasure_rs_vand_encode(void *desc, char **data, char **parity,
87  int blocksize)
88 {
89  struct jerasure_rs_vand_descriptor *jerasure_desc =
90  (struct jerasure_rs_vand_descriptor*) desc;
91 
92  /* FIXME - make jerasure_matrix_encode return a value */
93  jerasure_desc->jerasure_matrix_encode(jerasure_desc->k, jerasure_desc->m,
94  jerasure_desc->w, jerasure_desc->matrix, data, parity, blocksize);
95 
96  return 0;
97 }
98 
99 static int jerasure_rs_vand_decode(void *desc, char **data, char **parity,
100  int *missing_idxs, int blocksize)
101 {
102  struct jerasure_rs_vand_descriptor *jerasure_desc =
103  (struct jerasure_rs_vand_descriptor*)desc;
104 
105  /* FIXME - make jerasure_matrix_decode return a value */
106  jerasure_desc->jerasure_matrix_decode(jerasure_desc->k,
107  jerasure_desc->m, jerasure_desc->w,
108  jerasure_desc->matrix, 1, missing_idxs, data, parity, blocksize);
109 
110  return 0;
111 }
112 
113 static int jerasure_rs_vand_reconstruct(void *desc, char **data, char **parity,
114  int *missing_idxs, int destination_idx, int blocksize)
115 {
116  int ret = 0; /* return code */
117  int *decoding_row; /* decoding matrix row for decode */
118  int *erased = NULL; /* k+m length list of erased frag ids */
119  int *dm_ids = NULL; /* k length list of frag ids */
120  int *decoding_matrix = NULL; /* matrix for decoding */
121 
122  struct jerasure_rs_vand_descriptor *jerasure_desc =
123  (struct jerasure_rs_vand_descriptor*) desc;
124 
125  if (destination_idx < jerasure_desc->k) {
126  dm_ids = (int *) alloc_zeroed_buffer(sizeof(int) * jerasure_desc->k);
127  decoding_matrix = (int *)
128  alloc_zeroed_buffer(sizeof(int*) * jerasure_desc->k * jerasure_desc->k);
129  erased = jerasure_desc->jerasure_erasures_to_erased(jerasure_desc->k,
130  jerasure_desc->m, missing_idxs);
131  if (NULL == decoding_matrix || NULL == dm_ids || NULL == erased) {
132  goto out;
133  }
134 
135  ret = jerasure_desc->jerasure_make_decoding_matrix(jerasure_desc->k,
136  jerasure_desc->m, jerasure_desc->w, jerasure_desc->matrix,
137  erased, decoding_matrix, dm_ids);
138 
139  decoding_row = decoding_matrix + (destination_idx * jerasure_desc->k);
140 
141  if (ret == 0) {
142  jerasure_desc->jerasure_matrix_dotprod(jerasure_desc->k,
143  jerasure_desc->w, decoding_row, dm_ids, destination_idx,
144  data, parity, blocksize);
145  } else {
146  /*
147  * ToDo (KMG) I know this is not needed, but keeping to prevent future
148  * memory leaks, as this function will be better optimized for decoding
149  * missing parity
150  */
151  goto out;
152  }
153  } else {
154  /*
155  * If it is parity we are reconstructing, then just call decode.
156  * ToDo (KMG): We can do better than this, but this should perform just
157  * fine for most cases. We can adjust the decoding matrix like we
158  * did with ISA-L.
159  */
160  jerasure_desc->jerasure_matrix_decode(jerasure_desc->k,
161  jerasure_desc->m, jerasure_desc->w,
162  jerasure_desc->matrix, 1, missing_idxs, data, parity, blocksize);
163  goto parity_reconstr_out;
164  }
165 
166 out:
167  free(erased);
168  free(decoding_matrix);
169  free(dm_ids);
170 
171 parity_reconstr_out:
172  return ret;
173 }
174 
175 static int jerasure_rs_vand_min_fragments(void *desc, int *missing_idxs,
176  int *fragments_to_exclude, int *fragments_needed)
177 {
178  struct jerasure_rs_vand_descriptor *jerasure_desc =
179  (struct jerasure_rs_vand_descriptor*)desc;
180 
181  uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
182  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
183  int i;
184  int j = 0;
185  int ret = -1;
186 
187  for (i = 0; i < (jerasure_desc->k + jerasure_desc->m); i++) {
188  if (!(missing_bm & (1 << i))) {
189  fragments_needed[j] = i;
190  j++;
191  }
192  if (j == jerasure_desc->k) {
193  ret = 0;
194  fragments_needed[j] = -1;
195  break;
196  }
197  }
198 
199  return ret;
200 }
201 
202 #define DEFAULT_W 16
203 static void * jerasure_rs_vand_init(struct ec_backend_args *args,
204  void *backend_sohandle)
205 {
206  struct jerasure_rs_vand_descriptor *desc = NULL;
207 
208  desc = (struct jerasure_rs_vand_descriptor *)
209  malloc(sizeof(struct jerasure_rs_vand_descriptor));
210  if (NULL == desc) {
211  return NULL;
212  }
213 
214  desc->k = args->uargs.k;
215  desc->m = args->uargs.m;
216 
217  if (args->uargs.w <= 0)
218  args->uargs.w = DEFAULT_W;
219 
220  /* store w back in args so upper layer can get to it */
221  desc->w = args->uargs.w;
222 
223  /* validate EC arguments */
224  {
225  long long max_symbols;
226  if (desc->w != 8 && desc->w != 16 && desc->w != 32) {
227  goto error;
228  }
229  max_symbols = 1LL << desc->w;
230  if ((desc->k + desc->m) > max_symbols) {
231  goto error;
232  }
233  }
234 
235  /*
236  * ISO C forbids casting a void* to a function pointer.
237  * Since dlsym return returns a void*, we use this union to
238  * "transform" the void* to a function pointer.
239  */
240  union {
242  galois_uninit_field_func uninitp;
248  void *vptr;
249  } func_handle = {.vptr = NULL};
250 
251 
252  /* fill in function addresses */
253  func_handle.vptr = NULL;
254  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_encode");
255  desc->jerasure_matrix_encode = func_handle.encodep;
256  if (NULL == desc->jerasure_matrix_encode) {
257  goto error;
258  }
259 
260  func_handle.vptr = NULL;
261  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_decode");
262  desc->jerasure_matrix_decode = func_handle.decodep;
263  if (NULL == desc->jerasure_matrix_decode) {
264  goto error;
265  }
266 
267  func_handle.vptr = NULL;
268  func_handle.vptr = dlsym(backend_sohandle, "jerasure_make_decoding_matrix");
269  desc->jerasure_make_decoding_matrix = func_handle.decodematrixp;
270  if (NULL == desc->jerasure_make_decoding_matrix) {
271  goto error;
272  }
273 
274  func_handle.vptr = NULL;
275  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_dotprod");
276  desc->jerasure_matrix_dotprod = func_handle.dotprodp;
277  if (NULL == desc->jerasure_matrix_dotprod) {
278  goto error;
279  }
280 
281  func_handle.vptr = NULL;
282  func_handle.vptr = dlsym(backend_sohandle, "jerasure_erasures_to_erased");
283  desc->jerasure_erasures_to_erased = func_handle.erasep;
284  if (NULL == desc->jerasure_erasures_to_erased) {
285  goto error;
286  }
287 
288  func_handle.vptr = NULL;
289  func_handle.vptr = dlsym(backend_sohandle, "reed_sol_vandermonde_coding_matrix");
290  desc->reed_sol_vandermonde_coding_matrix = func_handle.initp;
291  if (NULL == desc->reed_sol_vandermonde_coding_matrix) {
292  goto error;
293  }
294 
295  func_handle.vptr = NULL;
296  func_handle.vptr = dlsym(backend_sohandle, "galois_uninit_field");
297  desc->galois_uninit_field = func_handle.uninitp;
298  if (NULL == desc->galois_uninit_field) {
299  goto error;
300  }
301 
303  desc->k, desc->m, desc->w);
304  if (NULL == desc->matrix) {
305  goto error;
306  }
307 
308  return desc;
309 
310 error:
311  free(desc);
312 
313  return NULL;
314 }
315 
323 static int
325 {
326  struct jerasure_rs_vand_descriptor *jerasure_desc =
327  (struct jerasure_rs_vand_descriptor*)desc;
328 
329  /* Note that cauchy will return pyeclib_handle->w * PYECC_CAUCHY_PACKETSIZE * 8 */
330  return jerasure_desc->w;
331 }
332 
333 static int jerasure_rs_vand_exit(void *desc)
334 {
335  struct jerasure_rs_vand_descriptor *jerasure_desc = NULL;
336 
337  jerasure_desc = (struct jerasure_rs_vand_descriptor*) desc;
338 
339  /*
340  * jerasure allocates some internal data structures for caching
341  * fields. It will allocate one for w, and if we do anything that
342  * needs to xor a region >= 16 bytes, it will also allocate one
343  * for 32. Fortunately we can safely uninit any value; if it
344  * wasn't inited it will be ignored.
345  */
346  jerasure_desc->galois_uninit_field(jerasure_desc->w);
347  jerasure_desc->galois_uninit_field(32);
348  free(jerasure_desc->matrix);
349  free(jerasure_desc);
350 
351  return 0;
352 }
353 
354 /*
355  * For the time being, we only claim compatibility with versions that
356  * match exactly
357  */
358 static bool jerasure_rs_vand_is_compatible_with(uint32_t version) {
359  return version == backend_jerasure_rs_vand.ec_backend_version;
360 }
361 
362 struct ec_backend_op_stubs jerasure_rs_vand_op_stubs = {
363  .INIT = jerasure_rs_vand_init,
364  .EXIT = jerasure_rs_vand_exit,
365  .ENCODE = jerasure_rs_vand_encode,
366  .DECODE = jerasure_rs_vand_decode,
367  .FRAGSNEEDED = jerasure_rs_vand_min_fragments,
368  .RECONSTRUCT = jerasure_rs_vand_reconstruct,
369  .ELEMENTSIZE = jerasure_rs_vand_element_size,
370  .ISCOMPATIBLEWITH = jerasure_rs_vand_is_compatible_with,
371  .GETMETADATASIZE = get_backend_metadata_size_zero,
372  .GETENCODEOFFSET = get_encode_offset_zero,
373 };
374 
375 struct ec_backend_common backend_jerasure_rs_vand = {
376  .id = EC_BACKEND_JERASURE_RS_VAND,
378  .soname = JERASURE_RS_VAND_SO_NAME,
379  .soversion = JERASURE_RS_VAND_LIB_VER_STR,
381  .ec_backend_version = _VERSION(JERASURE_RS_VAND_LIB_MAJOR,
384 };
jerasure_rs_vand_min_fragments
static int jerasure_rs_vand_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
Definition: jerasure_rs_vand.c:175
jerasure_matrix_decode_func
int(* jerasure_matrix_decode_func)(int, int, int, int *, int, int *, char **, char **, int)
Definition: jerasure_rs_vand.c:55
jerasure_rs_vand_descriptor::jerasure_make_decoding_matrix
jerasure_make_decoding_matrix_func jerasure_make_decoding_matrix
Definition: jerasure_rs_vand.c:75
jerasure_rs_vand_reconstruct
static int jerasure_rs_vand_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
Definition: jerasure_rs_vand.c:113
jerasure_rs_vand_ops
struct ec_backend_op_stubs jerasure_rs_vand_ops
Definition: jerasure_rs_vand.c:49
galois_uninit_field_func
void(* galois_uninit_field_func)(int)
Definition: jerasure_rs_vand.c:59
jerasure_rs_vand_descriptor::reed_sol_vandermonde_coding_matrix
reed_sol_vandermonde_coding_matrix_func reed_sol_vandermonde_coding_matrix
Definition: jerasure_rs_vand.c:63
jerasure_rs_vand_encode
static int jerasure_rs_vand_encode(void *desc, char **data, char **parity, int blocksize)
Definition: jerasure_rs_vand.c:86
JERASURE_RS_VAND_LIB_MAJOR
#define JERASURE_RS_VAND_LIB_MAJOR
Definition: jerasure_rs_vand.c:37
jerasure_matrix_dotprod_func
void(* jerasure_matrix_dotprod_func)(int, int, int *, int *, int, char **, char **, int)
Definition: jerasure_rs_vand.c:58
JERASURE_RS_VAND_LIB_VER_STR
#define JERASURE_RS_VAND_LIB_VER_STR
Definition: jerasure_rs_vand.c:40
JERASURE_RS_VAND_LIB_MINOR
#define JERASURE_RS_VAND_LIB_MINOR
Definition: jerasure_rs_vand.c:38
jerasure_rs_vand_descriptor::jerasure_matrix_decode
jerasure_matrix_decode_func jerasure_matrix_decode
Definition: jerasure_rs_vand.c:72
jerasure_matrix_encode_func
void(* jerasure_matrix_encode_func)(int, int, int, int *, char **, char **, int)
Definition: jerasure_rs_vand.c:54
jerasure_rs_vand_descriptor
Definition: jerasure_rs_vand.c:61
jerasure_make_decoding_matrix_func
int(* jerasure_make_decoding_matrix_func)(int, int, int, int *, int *, int *, int *)
Definition: jerasure_rs_vand.c:56
jerasure_rs_vand_descriptor::jerasure_erasures_to_erased
jerasure_erasures_to_erased_func jerasure_erasures_to_erased
Definition: jerasure_rs_vand.c:76
jerasure_rs_vand_descriptor::jerasure_matrix_encode
jerasure_matrix_encode_func jerasure_matrix_encode
Definition: jerasure_rs_vand.c:69
jerasure_rs_vand
struct ec_backend jerasure_rs_vand
Definition: jerasure_rs_vand.c:50
DEFAULT_W
#define DEFAULT_W
Definition: jerasure_rs_vand.c:202
jerasure_rs_vand_descriptor::w
int w
Definition: jerasure_rs_vand.c:83
JERASURE_RS_VAND_LIB_NAME
#define JERASURE_RS_VAND_LIB_NAME
Definition: jerasure_rs_vand.c:41
jerasure_rs_vand_element_size
static int jerasure_rs_vand_element_size(void *desc)
Return the element-size, which is the number of bits stored on a given device, per codeword.
Definition: jerasure_rs_vand.c:324
jerasure_rs_vand_init
static void * jerasure_rs_vand_init(struct ec_backend_args *args, void *backend_sohandle)
Definition: jerasure_rs_vand.c:203
alloc_zeroed_buffer
void * alloc_zeroed_buffer(int size)
Allocate a zero-ed buffer of a specific size.
Definition: erasurecode_helpers.c:84
jerasure_rs_vand_descriptor::k
int k
Definition: jerasure_rs_vand.c:81
jerasure_rs_vand_descriptor::jerasure_matrix_dotprod
jerasure_matrix_dotprod_func jerasure_matrix_dotprod
Definition: jerasure_rs_vand.c:77
jerasure_rs_vand_is_compatible_with
static bool jerasure_rs_vand_is_compatible_with(uint32_t version)
Definition: jerasure_rs_vand.c:358
jerasure_rs_vand_decode
static int jerasure_rs_vand_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
Definition: jerasure_rs_vand.c:99
jerasure_rs_vand_descriptor::m
int m
Definition: jerasure_rs_vand.c:82
JERASURE_RS_VAND_SO_NAME
#define JERASURE_RS_VAND_SO_NAME
Definition: jerasure_rs_vand.c:45
backend_jerasure_rs_vand
struct ec_backend_common backend_jerasure_rs_vand
Definition: jerasure_rs_vand.c:51
JERASURE_RS_VAND_LIB_REV
#define JERASURE_RS_VAND_LIB_REV
Definition: jerasure_rs_vand.c:39
reed_sol_vandermonde_coding_matrix_func
int *(* reed_sol_vandermonde_coding_matrix_func)(int, int, int)
Definition: jerasure_rs_vand.c:53
jerasure_erasures_to_erased_func
int *(* jerasure_erasures_to_erased_func)(int, int, int *)
Definition: jerasure_rs_vand.c:57
jerasure_rs_vand_descriptor::galois_uninit_field
galois_uninit_field_func galois_uninit_field
Definition: jerasure_rs_vand.c:66
jerasure_rs_vand_op_stubs
struct ec_backend_op_stubs jerasure_rs_vand_op_stubs
Definition: jerasure_rs_vand.c:362
jerasure_rs_vand_descriptor::matrix
int * matrix
Definition: jerasure_rs_vand.c:80
jerasure_rs_vand_exit
static int jerasure_rs_vand_exit(void *desc)
Definition: jerasure_rs_vand.c:333