liberasurecode  1.4.0
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 
61  /* calls required for init */
63 
64  /* calls required for encode */
66 
67  /* calls required for decode */
69 
70  /* calls required for reconstruct */
74 
75  /* fields needed to hold state */
76  int *matrix;
77  int k;
78  int m;
79  int w;
80 };
81 
82 static int jerasure_rs_vand_encode(void *desc, char **data, char **parity,
83  int blocksize)
84 {
85  struct jerasure_rs_vand_descriptor *jerasure_desc =
86  (struct jerasure_rs_vand_descriptor*) desc;
87 
88  /* FIXME - make jerasure_matrix_encode return a value */
89  jerasure_desc->jerasure_matrix_encode(jerasure_desc->k, jerasure_desc->m,
90  jerasure_desc->w, jerasure_desc->matrix, data, parity, blocksize);
91 
92  return 0;
93 }
94 
95 static int jerasure_rs_vand_decode(void *desc, char **data, char **parity,
96  int *missing_idxs, int blocksize)
97 {
98  struct jerasure_rs_vand_descriptor *jerasure_desc =
99  (struct jerasure_rs_vand_descriptor*)desc;
100 
101  /* FIXME - make jerasure_matrix_decode return a value */
102  jerasure_desc->jerasure_matrix_decode(jerasure_desc->k,
103  jerasure_desc->m, jerasure_desc->w,
104  jerasure_desc->matrix, 1, missing_idxs, data, parity, blocksize);
105 
106  return 0;
107 }
108 
109 static int jerasure_rs_vand_reconstruct(void *desc, char **data, char **parity,
110  int *missing_idxs, int destination_idx, int blocksize)
111 {
112  int ret = 0; /* return code */
113  int *decoding_row; /* decoding matrix row for decode */
114  int *erased = NULL; /* k+m length list of erased frag ids */
115  int *dm_ids = NULL; /* k length list of frag ids */
116  int *decoding_matrix = NULL; /* matrix for decoding */
117 
118  struct jerasure_rs_vand_descriptor *jerasure_desc =
119  (struct jerasure_rs_vand_descriptor*) desc;
120 
121  if (destination_idx < jerasure_desc->k) {
122  dm_ids = (int *) alloc_zeroed_buffer(sizeof(int) * jerasure_desc->k);
123  decoding_matrix = (int *)
124  alloc_zeroed_buffer(sizeof(int*) * jerasure_desc->k * jerasure_desc->k);
125  erased = jerasure_desc->jerasure_erasures_to_erased(jerasure_desc->k,
126  jerasure_desc->m, missing_idxs);
127  if (NULL == decoding_matrix || NULL == dm_ids || NULL == erased) {
128  goto out;
129  }
130 
131  ret = jerasure_desc->jerasure_make_decoding_matrix(jerasure_desc->k,
132  jerasure_desc->m, jerasure_desc->w, jerasure_desc->matrix,
133  erased, decoding_matrix, dm_ids);
134 
135  decoding_row = decoding_matrix + (destination_idx * jerasure_desc->k);
136 
137  if (ret == 0) {
138  jerasure_desc->jerasure_matrix_dotprod(jerasure_desc->k,
139  jerasure_desc->w, decoding_row, dm_ids, destination_idx,
140  data, parity, blocksize);
141  } else {
142  /*
143  * ToDo (KMG) I know this is not needed, but keeping to prevent future
144  * memory leaks, as this function will be better optimized for decoding
145  * missing parity
146  */
147  goto out;
148  }
149  } else {
150  /*
151  * If it is parity we are reconstructing, then just call decode.
152  * ToDo (KMG): We can do better than this, but this should perform just
153  * fine for most cases. We can adjust the decoding matrix like we
154  * did with ISA-L.
155  */
156  jerasure_desc->jerasure_matrix_decode(jerasure_desc->k,
157  jerasure_desc->m, jerasure_desc->w,
158  jerasure_desc->matrix, 1, missing_idxs, data, parity, blocksize);
159  goto parity_reconstr_out;
160  }
161 
162 out:
163  free(erased);
164  free(decoding_matrix);
165  free(dm_ids);
166 
167 parity_reconstr_out:
168  return ret;
169 }
170 
171 static int jerasure_rs_vand_min_fragments(void *desc, int *missing_idxs,
172  int *fragments_to_exclude, int *fragments_needed)
173 {
174  struct jerasure_rs_vand_descriptor *jerasure_desc =
175  (struct jerasure_rs_vand_descriptor*)desc;
176 
177  uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
178  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
179  int i;
180  int j = 0;
181  int ret = -1;
182 
183  for (i = 0; i < (jerasure_desc->k + jerasure_desc->m); i++) {
184  if (!(missing_bm & (1 << i))) {
185  fragments_needed[j] = i;
186  j++;
187  }
188  if (j == jerasure_desc->k) {
189  ret = 0;
190  fragments_needed[j] = -1;
191  break;
192  }
193  }
194 
195  return ret;
196 }
197 
198 #define DEFAULT_W 16
199 static void * jerasure_rs_vand_init(struct ec_backend_args *args,
200  void *backend_sohandle)
201 {
202  struct jerasure_rs_vand_descriptor *desc = NULL;
203 
204  desc = (struct jerasure_rs_vand_descriptor *)
205  malloc(sizeof(struct jerasure_rs_vand_descriptor));
206  if (NULL == desc) {
207  return NULL;
208  }
209 
210  desc->k = args->uargs.k;
211  desc->m = args->uargs.m;
212 
213  if (args->uargs.w <= 0)
214  args->uargs.w = DEFAULT_W;
215 
216  /* store w back in args so upper layer can get to it */
217  desc->w = args->uargs.w;
218 
219  /* validate EC arguments */
220  {
221  long long max_symbols;
222  if (desc->w != 8 && desc->w != 16 && desc->w != 32) {
223  goto error;
224  }
225  max_symbols = 1LL << desc->w;
226  if ((desc->k + desc->m) > max_symbols) {
227  goto error;
228  }
229  }
230 
231  /*
232  * ISO C forbids casting a void* to a function pointer.
233  * Since dlsym return returns a void*, we use this union to
234  * "transform" the void* to a function pointer.
235  */
236  union {
243  void *vptr;
244  } func_handle = {.vptr = NULL};
245 
246 
247  /* fill in function addresses */
248  func_handle.vptr = NULL;
249  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_encode");
250  desc->jerasure_matrix_encode = func_handle.encodep;
251  if (NULL == desc->jerasure_matrix_encode) {
252  goto error;
253  }
254 
255  func_handle.vptr = NULL;
256  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_decode");
257  desc->jerasure_matrix_decode = func_handle.decodep;
258  if (NULL == desc->jerasure_matrix_decode) {
259  goto error;
260  }
261 
262  func_handle.vptr = NULL;
263  func_handle.vptr = dlsym(backend_sohandle, "jerasure_make_decoding_matrix");
264  desc->jerasure_make_decoding_matrix = func_handle.decodematrixp;
265  if (NULL == desc->jerasure_make_decoding_matrix) {
266  goto error;
267  }
268 
269  func_handle.vptr = NULL;
270  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_dotprod");
271  desc->jerasure_matrix_dotprod = func_handle.dotprodp;
272  if (NULL == desc->jerasure_matrix_dotprod) {
273  goto error;
274  }
275 
276  func_handle.vptr = NULL;
277  func_handle.vptr = dlsym(backend_sohandle, "jerasure_erasures_to_erased");
278  desc->jerasure_erasures_to_erased = func_handle.erasep;
279  if (NULL == desc->jerasure_erasures_to_erased) {
280  goto error;
281  }
282 
283  func_handle.vptr = NULL;
284  func_handle.vptr = dlsym(backend_sohandle, "reed_sol_vandermonde_coding_matrix");
285  desc->reed_sol_vandermonde_coding_matrix = func_handle.initp;
286  if (NULL == desc->reed_sol_vandermonde_coding_matrix) {
287  goto error;
288  }
289 
291  desc->k, desc->m, desc->w);
292  if (NULL == desc->matrix) {
293  goto error;
294  }
295 
296  return desc;
297 
298 error:
299  free(desc);
300 
301  return NULL;
302 }
303 
311 static int
313 {
314  struct jerasure_rs_vand_descriptor *jerasure_desc =
315  (struct jerasure_rs_vand_descriptor*)desc;
316 
317  /* Note that cauchy will return pyeclib_handle->w * PYECC_CAUCHY_PACKETSIZE * 8 */
318  return jerasure_desc->w;
319 }
320 
321 static int jerasure_rs_vand_exit(void *desc)
322 {
323  struct jerasure_rs_vand_descriptor *jerasure_desc = NULL;
324 
325  jerasure_desc = (struct jerasure_rs_vand_descriptor*) desc;
326  free(jerasure_desc->matrix);
327  free(jerasure_desc);
328 
329  return 0;
330 }
331 
332 /*
333  * For the time being, we only claim compatibility with versions that
334  * match exactly
335  */
336 static bool jerasure_rs_vand_is_compatible_with(uint32_t version) {
337  return version == backend_jerasure_rs_vand.ec_backend_version;
338 }
339 
340 struct ec_backend_op_stubs jerasure_rs_vand_op_stubs = {
341  .INIT = jerasure_rs_vand_init,
342  .EXIT = jerasure_rs_vand_exit,
343  .ENCODE = jerasure_rs_vand_encode,
344  .DECODE = jerasure_rs_vand_decode,
345  .FRAGSNEEDED = jerasure_rs_vand_min_fragments,
346  .RECONSTRUCT = jerasure_rs_vand_reconstruct,
347  .ELEMENTSIZE = jerasure_rs_vand_element_size,
348  .ISCOMPATIBLEWITH = jerasure_rs_vand_is_compatible_with,
349 };
350 
351 struct ec_backend_common backend_jerasure_rs_vand = {
352  .id = EC_BACKEND_JERASURE_RS_VAND,
354  .soname = JERASURE_RS_VAND_SO_NAME,
355  .soversion = JERASURE_RS_VAND_LIB_VER_STR,
357  .backend_metadata_size = 0,
358  .ec_backend_version = _VERSION(JERASURE_RS_VAND_LIB_MAJOR,
361 };
jerasure_matrix_decode_func jerasure_matrix_decode
void(* jerasure_matrix_encode_func)(int, int, int, int *, char **, char **, int)
int *(* reed_sol_vandermonde_coding_matrix_func)(int, int, int)
struct ec_backend_common backend_jerasure_rs_vand
int(* jerasure_make_decoding_matrix_func)(int, int, int, int *, int *, int *, int *)
struct ec_backend_op_stubs jerasure_rs_vand_op_stubs
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...
void * alloc_zeroed_buffer(int size)
Allocate a zero-ed buffer of a specific size.
int(* jerasure_matrix_decode_func)(int, int, int, int *, int, int *, char **, char **, int)
struct ec_backend_op_stubs jerasure_rs_vand_ops
jerasure_make_decoding_matrix_func jerasure_make_decoding_matrix
static int jerasure_rs_vand_encode(void *desc, char **data, char **parity, int blocksize)
static int jerasure_rs_vand_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
reed_sol_vandermonde_coding_matrix_func reed_sol_vandermonde_coding_matrix
#define JERASURE_RS_VAND_LIB_REV
jerasure_matrix_dotprod_func jerasure_matrix_dotprod
#define JERASURE_RS_VAND_LIB_MAJOR
int *(* jerasure_erasures_to_erased_func)(int, int, int *)
static int jerasure_rs_vand_exit(void *desc)
static int jerasure_rs_vand_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
static int jerasure_rs_vand_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
jerasure_erasures_to_erased_func jerasure_erasures_to_erased
#define JERASURE_RS_VAND_LIB_NAME
struct ec_backend jerasure_rs_vand
static void * jerasure_rs_vand_init(struct ec_backend_args *args, void *backend_sohandle)
#define DEFAULT_W
#define JERASURE_RS_VAND_LIB_VER_STR
#define JERASURE_RS_VAND_LIB_MINOR
static bool jerasure_rs_vand_is_compatible_with(uint32_t version)
#define JERASURE_RS_VAND_SO_NAME
void(* jerasure_matrix_dotprod_func)(int, int, int *, int *, int, char **, char **, int)
jerasure_matrix_encode_func jerasure_matrix_encode