liberasurecode  1.2.0
Erasure Code API library
 All Data Structures Files Functions Variables Typedefs Macros
jerasure_rs_cauchy.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_cauchy 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_CAUCHY_LIB_MAJOR 2
38 #define JERASURE_RS_CAUCHY_LIB_MINOR 0
39 #define JERASURE_RS_CAUCHY_LIB_REV 0
40 #define JERASURE_RS_CAUCHY_LIB_VER_STR "2.0"
41 #define JERASURE_RS_CAUCHY_LIB_NAME "jerasure_rs_cauchy"
42 #if defined(__MACOS__) || defined(__MACOSX__) || defined(__OSX__) || defined(__APPLE__)
43 #define JERASURE_RS_CAUCHY_SO_NAME "libJerasure.dylib"
44 #else
45 #define JERASURE_RS_CAUCHY_SO_NAME "libJerasure.so.2"
46 #endif
47 
48 /* Forward declarations */
49 struct ec_backend_op_stubs jerasure_rs_cauchy_ops;
50 struct ec_backend jerasure_rs_cauchy;
51 struct ec_backend_common backend_jerasure_rs_cauchy;
52 
53 typedef int* (*cauchy_original_coding_matrix_func)(int, int, int);
54 typedef int* (*jerasure_matrix_to_bitmatrix_func)(int, int, int, int *);
55 typedef int** (*jerasure_smart_bitmatrix_to_schedule_func)
56  (int, int, int, int *);
57 typedef void (*jerasure_bitmatrix_encode_func)
58  (int, int, int, int *, char **, char **, int, int);
59 typedef int (*jerasure_bitmatrix_decode_func)
60  (int, int, int, int *, int, int *,char **, char **, int, int);
61 typedef int * (*jerasure_erasures_to_erased_func)(int, int, int *);
63  (int, int, int, int *, int *, int *, int *);
64 typedef void (*jerasure_bitmatrix_dotprod_func)
65  (int, int, int *, int *, int,char **, char **, int, int);
66 
67 /*
68  * ToDo (KMG): Should we make this a parameter, or is that
69  * exposing too much b.s. to the client?
70  */
71 #define PYECC_CAUCHY_PACKETSIZE sizeof(long) * 128
72 
74  /* calls required for init */
78 
79  /* calls required for encode */
81 
82 
83  /* calls required for decode */
85 
86 
87  /* calls required for reconstruct */
91 
92  /* fields needed to hold state */
93  int *matrix;
94  int *bitmatrix;
95  int **schedule;
96  int k;
97  int m;
98  int w;
99 };
100 static void free_rs_cauchy_desc(
101  struct jerasure_rs_cauchy_descriptor *jerasure_desc );
102 
103 
104 static int jerasure_rs_cauchy_encode(void *desc, char **data, char **parity,
105  int blocksize)
106 {
107  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
108  (struct jerasure_rs_cauchy_descriptor*) desc;
109 
110  /* FIXME - make jerasure_bitmatrix_encode return a value */
111  jerasure_desc->jerasure_bitmatrix_encode(jerasure_desc->k, jerasure_desc->m,
112  jerasure_desc->w, jerasure_desc->bitmatrix,
113  data, parity, blocksize,
115 
116  return 0;
117 }
118 
119 static int jerasure_rs_cauchy_decode(void *desc, char **data, char **parity,
120  int *missing_idxs, int blocksize)
121 {
122  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
123  (struct jerasure_rs_cauchy_descriptor*)desc;
124 
125  return jerasure_desc->jerasure_bitmatrix_decode(jerasure_desc->k,
126  jerasure_desc->m,
127  jerasure_desc->w,
128  jerasure_desc->bitmatrix,
129  0,
130  missing_idxs,
131  data,
132  parity,
133  blocksize,
135 }
136 
137 static int jerasure_rs_cauchy_reconstruct(void *desc, char **data, char **parity,
138  int *missing_idxs, int destination_idx, int blocksize)
139 {
140  int k, m, w; /* erasure code paramters */
141  int ret = 0; /* return code */
142  int *decoding_row = NULL; /* decoding matrix row for decode */
143  int *erased = NULL; /* k+m length list of erased frag ids */
144  int *dm_ids = NULL; /* k length list of fragment ids */
145  int *decoding_matrix = NULL; /* matrix for decoding */
146 
147  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
148  (struct jerasure_rs_cauchy_descriptor*) desc;
149  k = jerasure_desc->k;
150  m = jerasure_desc->m;
151  w = jerasure_desc->w;
152 
153  if (destination_idx < k) {
154  dm_ids = (int *) alloc_zeroed_buffer(sizeof(int) * k);
155  decoding_matrix = (int *) alloc_zeroed_buffer(sizeof(int *) * k * k * w * w);
156  erased = jerasure_desc->jerasure_erasures_to_erased(k, m, missing_idxs);
157  if (NULL == decoding_matrix || NULL == dm_ids || NULL == erased) {
158  goto out;
159  }
160 
161  ret = jerasure_desc->jerasure_make_decoding_bitmatrix(k, m, w,
162  jerasure_desc->bitmatrix,
163  erased, decoding_matrix, dm_ids);
164  if (ret == 0) {
165  decoding_row = decoding_matrix + (destination_idx * k * w * w);
166 
167  jerasure_desc->jerasure_bitmatrix_dotprod(jerasure_desc->k, jerasure_desc->w,
168  decoding_row, dm_ids, destination_idx,
169  data, parity, blocksize, PYECC_CAUCHY_PACKETSIZE);
170  } else {
171  /*
172  * ToDo (KMG) I know this is not needed, but keeping to prevent future
173  * memory leaks, as this function will be better optimized for decoding
174  * missing parity
175  */
176  goto out;
177  }
178  } else {
179  /*
180  * If it is parity we are reconstructing, then just call decode.
181  * ToDo (KMG): We can do better than this, but this should perform just
182  * fine for most cases. We can adjust the decoding matrix like we
183  * did with ISA-L.
184  */
185  jerasure_desc->jerasure_bitmatrix_decode(k, m, w,
186  jerasure_desc->bitmatrix,
187  0,
188  missing_idxs,
189  data,
190  parity,
191  blocksize,
193  }
194 
195 out:
196  free(erased);
197  free(decoding_matrix);
198  free(dm_ids);
199 
200  return ret;
201 }
202 
203 /*
204  * Caller will allocate an array of size k for fragments_needed
205  *
206  */
207 static int jerasure_rs_cauchy_min_fragments(void *desc, int *missing_idxs,
208  int *fragments_to_exclude, int *fragments_needed)
209 {
210  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
211  (struct jerasure_rs_cauchy_descriptor*)desc;
212  uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude);
213  uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm;
214  int i;
215  int j = 0;
216  int ret = -1;
217 
218  for (i = 0; i < (jerasure_desc->k + jerasure_desc->m); i++) {
219  if (!(missing_bm & (1 << i))) {
220  fragments_needed[j] = i;
221  j++;
222  }
223  if (j == jerasure_desc->k) {
224  ret = 0;
225  fragments_needed[j] = -1;
226  break;
227  }
228  }
229 
230  return ret;
231 }
232 
233 #define DEFAULT_W 4
234 static void * jerasure_rs_cauchy_init(struct ec_backend_args *args,
235  void *backend_sohandle)
236 {
237  struct jerasure_rs_cauchy_descriptor *desc = NULL;
238  int k, m, w;
239 
240  desc = (struct jerasure_rs_cauchy_descriptor *)
241  malloc(sizeof(struct jerasure_rs_cauchy_descriptor));
242  if (NULL == desc) {
243  return NULL;
244  }
245 
246  /* validate the base EC arguments */
247  k = args->uargs.k;
248  m = args->uargs.m;
249  if (args->uargs.w <= 0)
250  args->uargs.w = DEFAULT_W;
251  w = args->uargs.w;
252 
253  /* store the base EC arguments in the descriptor */
254  desc->k = k;
255  desc->m = m;
256  desc->w = w;
257 
258  /* validate EC arguments */
259  {
260  long long max_symbols;
261  max_symbols = 1LL << w;
262  if ((k + m) > max_symbols) {
263  goto error;
264  }
265  }
266 
267  /*
268  * ISO C forbids casting a void* to a function pointer.
269  * Since dlsym return returns a void*, we use this union to
270  * "transform" the void* to a function pointer.
271  */
272  union {
274  jerasure_matrix_to_bitmatrix_func matrixtobitmatrixp;
281  void *vptr;
282  } func_handle = {.vptr = NULL};
283 
284  /* fill in function addresses */
285  func_handle.vptr = NULL;
286  func_handle.vptr = dlsym(backend_sohandle, "jerasure_bitmatrix_encode");
287  desc->jerasure_bitmatrix_encode = func_handle.encodep;
288  if (NULL == desc->jerasure_bitmatrix_encode) {
289  goto error;
290  }
291 
292  func_handle.vptr = NULL;
293  func_handle.vptr = dlsym(backend_sohandle, "jerasure_bitmatrix_decode");
294  desc->jerasure_bitmatrix_decode = func_handle.decodep;
295  if (NULL == desc->jerasure_bitmatrix_decode) {
296  goto error;
297  }
298 
299  func_handle.vptr = NULL;
300  func_handle.vptr = dlsym(backend_sohandle, "cauchy_original_coding_matrix");
301  desc->cauchy_original_coding_matrix = func_handle.initp;
302  if (NULL == desc->cauchy_original_coding_matrix) {
303  goto error;
304  }
305 
306  func_handle.vptr = NULL;
307  func_handle.vptr = dlsym(backend_sohandle, "jerasure_matrix_to_bitmatrix");
308  desc->jerasure_matrix_to_bitmatrix = func_handle.matrixtobitmatrixp;
309  if (NULL == desc->jerasure_matrix_to_bitmatrix) {
310  goto error;
311  }
312 
313  func_handle.vptr = NULL;
314  func_handle.vptr = dlsym(backend_sohandle, "jerasure_smart_bitmatrix_to_schedule");
315  desc->jerasure_smart_bitmatrix_to_schedule = func_handle.matrixschedulep;
316  if (NULL == desc->jerasure_smart_bitmatrix_to_schedule) {
317  goto error;
318  }
319 
320  func_handle.vptr = NULL;
321  func_handle.vptr = dlsym(backend_sohandle, "jerasure_make_decoding_bitmatrix");
322  desc->jerasure_make_decoding_bitmatrix = func_handle.decodematrixp;
323  if (NULL == desc->jerasure_make_decoding_bitmatrix) {
324  goto error;
325  }
326 
327  func_handle.vptr = NULL;
328  func_handle.vptr = dlsym(backend_sohandle, "jerasure_bitmatrix_dotprod");
329  desc->jerasure_bitmatrix_dotprod = func_handle.dotprodp;
330  if (NULL == desc->jerasure_bitmatrix_dotprod) {
331  goto error;
332  }
333 
334  func_handle.vptr = NULL;
335  func_handle.vptr = dlsym(backend_sohandle, "jerasure_erasures_to_erased");
336  desc->jerasure_erasures_to_erased = func_handle.erasedp;
337  if (NULL == desc->jerasure_erasures_to_erased) {
338  goto error;
339  }
340 
341  /* setup the Cauchy matrices and schedules */
342  desc->matrix = desc->cauchy_original_coding_matrix(k, m, w);
343  if (NULL == desc->matrix) {
344  goto error;
345  }
346  desc->bitmatrix = desc->jerasure_matrix_to_bitmatrix(k, m, w, desc->matrix);
347  if (NULL == desc->bitmatrix) {
348  goto error;
349  }
350  desc->schedule = desc->jerasure_smart_bitmatrix_to_schedule(k, m, w, desc->bitmatrix);
351  if (NULL == desc->schedule) {
352  goto error;
353  }
354 
355  return desc;
356 
357 error:
358  free_rs_cauchy_desc(desc);
359  return NULL;
360 }
361 
368 static int
370 {
371  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
372  (struct jerasure_rs_cauchy_descriptor*)desc;
373 
374  return jerasure_desc->w * PYECC_CAUCHY_PACKETSIZE * 8;
375 }
376 
378  struct jerasure_rs_cauchy_descriptor *jerasure_desc )
379 {
380  int i = 0;
381  int **schedule = NULL;
382  bool end_of_array = false;
383 
384  if (jerasure_desc == NULL) {
385  return;
386  }
387 
388  free(jerasure_desc->matrix);
389  free(jerasure_desc->bitmatrix);
390 
391  // NOTE, based on an inspection of the jerasure code used to build the
392  // the schedule array, it appears that the sentinal used to signal the end
393  // of the array is a value of -1 in the first int field in the dereferenced
394  // value. We use this determine when to stop free-ing elements. See the
395  // jerasure_smart_bitmatrix_to_schedule and
396  // jerasure_dumb_bitmatrix_to_schedule functions in jerasure.c for the
397  // details.
398  schedule = jerasure_desc->schedule;
399  if (schedule != NULL) {
400  while (!end_of_array) {
401  if (schedule[i] == NULL || schedule[i][0] == -1) {
402  end_of_array = true;
403  }
404  free(schedule[i]);
405  i++;
406  }
407  }
408 
409  free(schedule);
410  free(jerasure_desc);
411 }
412 
413 static int jerasure_rs_cauchy_exit(void *desc)
414 {
415  struct jerasure_rs_cauchy_descriptor *jerasure_desc =
416  (struct jerasure_rs_cauchy_descriptor*)desc;
417  free_rs_cauchy_desc(jerasure_desc);
418  return 0;
419 }
420 
421 /*
422  * For the time being, we only claim compatibility with versions that
423  * match exactly
424  */
425 static bool jerasure_rs_cauchy_is_compatible_with(uint32_t version) {
426  return version == backend_jerasure_rs_cauchy.ec_backend_version;
427 }
428 
429 
430 struct ec_backend_op_stubs jerasure_rs_cauchy_op_stubs = {
431  .INIT = jerasure_rs_cauchy_init,
432  .EXIT = jerasure_rs_cauchy_exit,
433  .ENCODE = jerasure_rs_cauchy_encode,
434  .DECODE = jerasure_rs_cauchy_decode,
435  .FRAGSNEEDED = jerasure_rs_cauchy_min_fragments,
436  .RECONSTRUCT = jerasure_rs_cauchy_reconstruct,
437  .ELEMENTSIZE = jerasure_rs_cauchy_element_size,
438  .ISCOMPATIBLEWITH = jerasure_rs_cauchy_is_compatible_with,
439 
440 };
441 
442 struct ec_backend_common backend_jerasure_rs_cauchy = {
443  .id = EC_BACKEND_JERASURE_RS_CAUCHY,
445  .soname = JERASURE_RS_CAUCHY_SO_NAME,
446  .soversion = JERASURE_RS_CAUCHY_LIB_VER_STR,
448  .backend_metadata_size = 0,
449  .ec_backend_version = _VERSION(JERASURE_RS_CAUCHY_LIB_MAJOR,
452 };
#define DEFAULT_W
#define JERASURE_RS_CAUCHY_LIB_MINOR
#define JERASURE_RS_CAUCHY_LIB_VER_STR
struct ec_backend jerasure_rs_cauchy
int **(* jerasure_smart_bitmatrix_to_schedule_func)(int, int, int, int *)
jerasure_bitmatrix_encode_func jerasure_bitmatrix_encode
static bool jerasure_rs_cauchy_is_compatible_with(uint32_t version)
static int jerasure_rs_cauchy_encode(void *desc, char **data, char **parity, int blocksize)
#define JERASURE_RS_CAUCHY_LIB_REV
void * alloc_zeroed_buffer(int size)
Allocate a zero-ed buffer of a specific size.
void(* jerasure_bitmatrix_encode_func)(int, int, int, int *, char **, char **, int, int)
int *(* jerasure_erasures_to_erased_func)(int, int, int *)
struct ec_backend_op_stubs jerasure_rs_cauchy_op_stubs
#define JERASURE_RS_CAUCHY_LIB_NAME
jerasure_make_decoding_bitmatrix_func jerasure_make_decoding_bitmatrix
static void * jerasure_rs_cauchy_init(struct ec_backend_args *args, void *backend_sohandle)
static int jerasure_rs_cauchy_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
int *(* jerasure_matrix_to_bitmatrix_func)(int, int, int, int *)
jerasure_bitmatrix_dotprod_func jerasure_bitmatrix_dotprod
static int jerasure_rs_cauchy_min_fragments(void *desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed)
static void free_rs_cauchy_desc(struct jerasure_rs_cauchy_descriptor *jerasure_desc)
#define JERASURE_RS_CAUCHY_LIB_MAJOR
int(* jerasure_bitmatrix_decode_func)(int, int, int, int *, int, int *, char **, char **, int, int)
struct ec_backend_common backend_jerasure_rs_cauchy
jerasure_bitmatrix_decode_func jerasure_bitmatrix_decode
jerasure_erasures_to_erased_func jerasure_erasures_to_erased
static int jerasure_rs_cauchy_exit(void *desc)
cauchy_original_coding_matrix_func cauchy_original_coding_matrix
int(* jerasure_make_decoding_bitmatrix_func)(int, int, int, int *, int *, int *, int *)
#define JERASURE_RS_CAUCHY_SO_NAME
#define PYECC_CAUCHY_PACKETSIZE
jerasure_matrix_to_bitmatrix_func jerasure_matrix_to_bitmatrix
jerasure_smart_bitmatrix_to_schedule_func jerasure_smart_bitmatrix_to_schedule
void(* jerasure_bitmatrix_dotprod_func)(int, int, int *, int *, int, char **, char **, int, int)
static int jerasure_rs_cauchy_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
int *(* cauchy_original_coding_matrix_func)(int, int, int)
static int jerasure_rs_cauchy_element_size(void *desc)
Return the element-size, which is the number of bits stored on a given device, per codeword...
struct ec_backend_op_stubs jerasure_rs_cauchy_ops