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