1 /*
2 * Copyright 2014 Tushar Gohad, Kevin M Greenan, Eric Lambert, Mark Storer
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 * liberasurecode API implementation
25 *
26 * vi: set noai tw=79 ts=4 sw=4:
27 */
28
29 #include "assert.h"
30 #include "list.h"
31 #include "erasurecode.h"
32 #include "erasurecode_backend.h"
33 #include "erasurecode_helpers.h"
34 #include "erasurecode_helpers_ext.h"
35 #include "erasurecode_preprocessing.h"
36 #include "erasurecode_postprocessing.h"
37 #include "erasurecode_stdinc.h"
38
39 #include "alg_sig.h"
40 #include "erasurecode_log.h"
41
42 /* =~=*=~==~=*=~==~=*=~= Supported EC backends =~=*=~==~=*=~==~=*=~==~=*=~== */
43
44 /* EC backend references */
45 extern struct ec_backend_common backend_null;
46 extern struct ec_backend_common backend_flat_xor_hd;
47 extern struct ec_backend_common backend_jerasure_rs_vand;
48 extern struct ec_backend_common backend_jerasure_rs_cauchy;
49 extern struct ec_backend_common backend_isa_l_rs_vand;
50 extern struct ec_backend_common backend_shss;
51 extern struct ec_backend_common backend_liberasurecode_rs_vand;
52 extern struct ec_backend_common backend_isa_l_rs_cauchy;
53
54 ec_backend_t ec_backends_supported[] = {
55 (ec_backend_t) &backend_null,
56 (ec_backend_t) &backend_jerasure_rs_vand,
57 (ec_backend_t) &backend_jerasure_rs_cauchy,
58 (ec_backend_t) &backend_flat_xor_hd,
59 (ec_backend_t) &backend_isa_l_rs_vand,
60 (ec_backend_t) &backend_shss,
61 (ec_backend_t) &backend_liberasurecode_rs_vand,
62 (ec_backend_t) &backend_isa_l_rs_cauchy,
63 NULL,
64 };
65
66 /* backend list to return to the caller */
67 int num_supported_backends = 0;
68 char *ec_backends_supported_str[EC_BACKENDS_MAX];
69
70 /* =~=*=~==~=*=~==~=*=~= EC backend instance management =~=*=~==~=*=~==~=*= */
71
72 /* Registered erasure code backend instances */
73 SLIST_HEAD(backend_list, ec_backend) active_instances =
74 SLIST_HEAD_INITIALIZER(active_instances);
75 rwlock_t active_instances_rwlock = RWLOCK_INITIALIZER;
76
77 /* Backend instance id */
78 int next_backend_desc = 0;
79
80 /**
81 * Look up a backend instance by descriptor
82 *
83 * @returns pointer to a registered liberasurecode instance
84 * The caller must hold active_instances_rwlock
85 */
liberasurecode_backend_instance_get_by_desc(int desc)86 ec_backend_t liberasurecode_backend_instance_get_by_desc(int desc)
87 {
88 struct ec_backend *b = NULL;
89 SLIST_FOREACH(b, &active_instances, link) {
90 if (b->idesc == desc)
91 break;
92 }
93 return b;
94 }
95
96 /**
97 * Allocated backend instance descriptor
98 *
99 * Returns a unique descriptor for a new backend.
100 * The caller must hold active_instances_rwlock
101 */
liberasurecode_backend_alloc_desc(void)102 int liberasurecode_backend_alloc_desc(void)
103 {
104 for (;;) {
105 if (++next_backend_desc <= 0)
106 next_backend_desc = 1;
107 if (!liberasurecode_backend_instance_get_by_desc(next_backend_desc))
108 return next_backend_desc;
109 }
110 }
111
112 /**
113 * Register a backend instance with liberasurecode
114 *
115 * @param instance - backend enum
116 *
117 * @returns new backend descriptor
118 */
liberasurecode_backend_instance_register(ec_backend_t instance)119 int liberasurecode_backend_instance_register(ec_backend_t instance)
120 {
121 int desc = -1; /* descriptor to return */
122 int rc = 0; /* return call value */
123
124 rc = rwlock_wrlock(&active_instances_rwlock);
125 if (rc == 0) {
126 SLIST_INSERT_HEAD(&active_instances, instance, link);
127 desc = liberasurecode_backend_alloc_desc();
128 if (desc <= 0)
129 goto register_out;
130 instance->idesc = desc;
131 } else {
132 goto exit;
133 }
134
135 register_out:
136 rwlock_unlock(&active_instances_rwlock);
137 exit:
138 return desc;
139 }
140
141 /**
142 * Unregister a backend instance
143 *
144 * @returns 0 on success, non-0 on error
145 */
liberasurecode_backend_instance_unregister(ec_backend_t instance)146 int liberasurecode_backend_instance_unregister(ec_backend_t instance)
147 {
148 int rc = 0; /* return call value */
149
150 rc = rwlock_wrlock(&active_instances_rwlock);
151 if (rc == 0) {
152 SLIST_REMOVE(&active_instances, instance, ec_backend, link);
153 } else {
154 goto exit;
155 }
156 rwlock_unlock(&active_instances_rwlock);
157
158 exit:
159 return rc;
160 }
161
162 /* =~=*=~==~=*=~== liberasurecode backend API helpers =~=*=~==~=*=~== */
163
print_dlerror(const char * caller)164 static void print_dlerror(const char *caller)
165 {
166 char *msg = dlerror();
167 if (NULL == msg)
168 log_error("%s: unknown dynamic linking error\n", caller);
169 else
170 log_error("%s: dynamic linking error %s\n", caller, msg);
171 }
172
173 /* Generic dlopen/dlclose routines */
liberasurecode_backend_open(ec_backend_t instance)174 void* liberasurecode_backend_open(ec_backend_t instance)
175 {
176 if (NULL == instance)
177 return NULL;
178 /* Use RTLD_LOCAL to avoid symbol collisions */
179 return dlopen(instance->common.soname, RTLD_LAZY | RTLD_LOCAL);
180 }
181
liberasurecode_backend_close(ec_backend_t instance)182 int liberasurecode_backend_close(ec_backend_t instance)
183 {
184 if (NULL == instance || NULL == instance->desc.backend_sohandle)
185 return 0;
186
187 dlclose(instance->desc.backend_sohandle);
188 dlerror(); /* Clear any existing errors */
189
190 instance->desc.backend_sohandle = NULL;
191 return 0;
192 }
193
194 /* =*=~==~=*=~==~=*=~= liberasurecode init/exit routines =~=*=~==~=*=~==~=*= */
195
196 void __attribute__ ((constructor))
liberasurecode_init(void)197 liberasurecode_init(void) {
198 /* init logging */
199 openlog("liberasurecode", LOG_PID | LOG_CONS, LOG_USER);
200
201 /* populate supported backends list as a string */
202 {
203 int i;
204 for (i = 0; ec_backends_supported[i]; ++i) {
205 ec_backends_supported_str[i] = strdup(
206 ec_backends_supported[i]->common.name);
207 }
208 num_supported_backends = i;
209 }
210 }
211
212 void __attribute__ ((destructor))
liberasurecode_exit(void)213 liberasurecode_exit(void) {
214 int i;
215 for (i = 0; i < num_supported_backends; ++i)
216 free(ec_backends_supported_str[i]);
217 closelog();
218 }
219
220 /* =~=*=~==~=*=~= liberasurecode frontend API implementation =~=*=~==~=*=~== */
221
222 /**
223 * Checks if a given backend is available.
224 *
225 * @param backend_id - one of the supported backends.
226 *
227 * @returns 1 if a backend is available; 0 otherwise
228 */
liberasurecode_backend_available(const ec_backend_id_t backend_id)229 int liberasurecode_backend_available(const ec_backend_id_t backend_id) {
230 struct ec_backend backend;
231 if (backend_id >= EC_BACKENDS_MAX)
232 return 0;
233
234 backend.desc.backend_sohandle = liberasurecode_backend_open(
235 ec_backends_supported[backend_id]);
236 if (!backend.desc.backend_sohandle) {
237 return 0;
238 }
239
240 liberasurecode_backend_close(&backend);
241 return 1;
242 }
243
244 /**
245 * Create a liberasurecode instance and return a descriptor
246 * for use with EC operations (encode, decode, reconstruct)
247 *
248 * @param id - one of the supported backends as
249 * defined by ec_backend_id_t
250 * @param ec_args - arguments to the EC backend
251 * arguments common to all backends
252 * k - number of data fragments
253 * m - number of parity fragments
254 * w - word size, in bits
255 * hd - hamming distance (=m for Reed-Solomon)
256 * ct - fragment checksum type (stored with the fragment metadata)
257 * backend-specific arguments
258 * null_args - arguments for the null backend
259 * flat_xor_hd, jerasure do not require any special args
260 *
261 * @returns liberasurecode instance descriptor (int > 0)
262 */
liberasurecode_instance_create(const ec_backend_id_t id,struct ec_args * args)263 int liberasurecode_instance_create(const ec_backend_id_t id,
264 struct ec_args *args)
265 {
266 ec_backend_t instance = NULL;
267 struct ec_backend_args bargs;
268 if (!args)
269 return -EINVALIDPARAMS;
270
271 if (id >= EC_BACKENDS_MAX)
272 return -EBACKENDNOTSUPP;
273
274 if ((args->k + args->m) > EC_MAX_FRAGMENTS) {
275 log_error("Total number of fragments (k + m) must be less than %d\n",
276 EC_MAX_FRAGMENTS);
277 return -EINVALIDPARAMS;
278 }
279
280 /* Allocate memory for ec_backend instance */
281 instance = calloc(1, sizeof(*instance));
282 if (NULL == instance)
283 return -ENOMEM;
284
285 /* Copy common backend, args struct */
286 instance->common = ec_backends_supported[id]->common;
287 memcpy(&(bargs.uargs), args, sizeof (struct ec_args));
288 instance->args = bargs;
289
290 /* Open backend .so if not already open */
291 /* .so handle is returned in instance->desc.backend_sohandle */
292 if (!instance->desc.backend_sohandle) {
293 instance->desc.backend_sohandle = liberasurecode_backend_open(instance);
294 if (!instance->desc.backend_sohandle) {
295 /* ignore during init, return the same handle */
296 print_dlerror(__func__);
297 free(instance);
298 return -EBACKENDNOTAVAIL;
299 }
300 }
301
302 /* Call private init() for the backend */
303 instance->desc.backend_desc = instance->common.ops->init(
304 &instance->args, instance->desc.backend_sohandle);
305 if (NULL == instance->desc.backend_desc) {
306 free (instance);
307 return -EBACKENDINITERR;
308 }
309
310 /* Register instance and return a descriptor/instance id */
311 instance->idesc = liberasurecode_backend_instance_register(instance);
312
313 return instance->idesc;
314 }
315
316 /**
317 * Close a liberasurecode instance
318 *
319 * @param liberasurecode descriptor to close
320 */
liberasurecode_instance_destroy(int desc)321 int liberasurecode_instance_destroy(int desc)
322 {
323 ec_backend_t instance = NULL; /* instance to destroy */
324 int rc = 0; /* return code */
325
326 instance = liberasurecode_backend_instance_get_by_desc(desc);
327 if (NULL == instance)
328 return -EBACKENDNOTAVAIL;
329
330 /* Call private exit() for the backend */
331 instance->common.ops->exit(instance->desc.backend_desc);
332
333 /* dlclose() backend library */
334 liberasurecode_backend_close(instance);
335
336 /* Remove instance from registry */
337 rc = liberasurecode_backend_instance_unregister(instance);
338 if (rc == 0) {
339 free(instance);
340 }
341
342 return rc;
343 }
344
345 /**
346 * Cleanup structures allocated by librasurecode_encode
347 *
348 * The caller has no context, so cannot safely free memory
349 * allocated by liberasurecode, so it must pass the
350 * deallocation responsibility back to liberasurecode.
351 *
352 * @param desc - liberasurecode descriptor/handle
353 * from liberasurecode_instance_create()
354 * @param encoded_data - (char **) array of k data
355 * fragments (char *), allocated by liberasurecode_encode
356 * @param encoded_parity - (char **) array of m parity
357 * fragments (char *), allocated by liberasurecode_encode
358 * @return 0 in success; -error otherwise
359 */
liberasurecode_encode_cleanup(int desc,char ** encoded_data,char ** encoded_parity)360 int liberasurecode_encode_cleanup(int desc,
361 char **encoded_data,
362 char **encoded_parity)
363 {
364 int i, k, m;
365
366 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
367 if (NULL == instance) {
368 return -EBACKENDNOTAVAIL;
369 }
370
371 k = instance->args.uargs.k;
372 m = instance->args.uargs.m;
373
374 if (encoded_data) {
375 for (i = 0; i < k; i++) {
376 free(encoded_data[i]);
377 }
378
379 free(encoded_data);
380 }
381
382 if (encoded_parity) {
383 for (i = 0; i < m; i++) {
384 free(encoded_parity[i]);
385 }
386 free(encoded_parity);
387 }
388
389 return 0;
390 }
391
392 /**
393 * Erasure encode a data buffer
394 *
395 * @param desc - liberasurecode descriptor/handle
396 * from liberasurecode_instance_create()
397 * @param orig_data - data to encode
398 * @param orig_data_size - length of data to encode
399 * @param encoded_data - pointer to _output_ array (char **) of k data
400 * fragments (char *), allocated by the callee
401 * @param encoded_parity - pointer to _output_ array (char **) of m parity
402 * fragments (char *), allocated by the callee
403 * @param fragment_len - pointer to _output_ length of each fragment, assuming
404 * all fragments are the same length
405 *
406 * @return 0 on success, -error code otherwise
407 */
liberasurecode_encode(int desc,const char * orig_data,uint64_t orig_data_size,char *** encoded_data,char *** encoded_parity,uint64_t * fragment_len)408 int liberasurecode_encode(int desc,
409 const char *orig_data, uint64_t orig_data_size, /* input */
410 char ***encoded_data, char ***encoded_parity, /* output */
411 uint64_t *fragment_len) /* output */
412 {
413 int k, m;
414 int ret = 0; /* return code */
415
416 int blocksize = 0; /* length of each of k data elements */
417
418 if (orig_data == NULL) {
419 log_error("Pointer to data buffer is null!");
420 ret = -EINVALIDPARAMS;
421 goto out;
422 }
423
424 if (encoded_data == NULL) {
425 log_error("Pointer to encoded data buffers is null!");
426 return -EINVALIDPARAMS;
427 }
428
429 if (encoded_parity == NULL) {
430 log_error("Pointer to encoded parity buffers is null!");
431 return -EINVALIDPARAMS;
432 }
433
434 if (fragment_len == NULL) {
435 log_error("Pointer to fragment length is null!");
436 ret = -EINVALIDPARAMS;
437 goto out;
438 }
439
440 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
441 if (NULL == instance) {
442 ret = -EBACKENDNOTAVAIL;
443 goto out;
444 }
445
446 k = instance->args.uargs.k;
447 m = instance->args.uargs.m;
448
449 /*
450 * Allocate arrays for data, parity and missing_idxs
451 */
452 *encoded_data = (char **) alloc_zeroed_buffer(sizeof(char *) * k);
453 if (NULL == *encoded_data) {
454 log_error("Could not allocate data buffer!");
455 goto out;
456 }
457
458 *encoded_parity = (char **) alloc_zeroed_buffer(sizeof(char *) * m);
459 if (NULL == *encoded_parity) {
460 log_error("Could not allocate parity buffer!");
461 goto out;
462 }
463
464 ret = prepare_fragments_for_encode(instance, k, m, orig_data, orig_data_size,
465 *encoded_data, *encoded_parity, &blocksize);
466 if (ret < 0) {
467 // ensure encoded_data/parity point the head of fragment_ptr
468 get_fragment_ptr_array_from_data(*encoded_data, *encoded_data, k);
469 get_fragment_ptr_array_from_data(*encoded_parity, *encoded_parity, m);
470 goto out;
471 }
472
473 /* call the backend encode function passing it desc instance */
474 ret = instance->common.ops->encode(instance->desc.backend_desc,
475 *encoded_data, *encoded_parity, blocksize);
476 if (ret < 0) {
477 // ensure encoded_data/parity point the head of fragment_ptr
478 get_fragment_ptr_array_from_data(*encoded_data, *encoded_data, k);
479 get_fragment_ptr_array_from_data(*encoded_parity, *encoded_parity, m);
480 goto out;
481 }
482
483 ret = finalize_fragments_after_encode(instance, k, m, blocksize, orig_data_size,
484 *encoded_data, *encoded_parity);
485
486 *fragment_len = get_fragment_size((*encoded_data)[0]);
487
488 out:
489 if (ret) {
490 /* Cleanup the allocations we have done */
491 liberasurecode_encode_cleanup(desc, *encoded_data, *encoded_parity);
492 log_error("Error in liberasurecode_encode %d", ret);
493 }
494 return ret;
495 }
496
497 /**
498 * Cleanup structures allocated by librasurecode_decode
499 *
500 * The caller has no context, so cannot safely free memory
501 * allocated by liberasurecode, so it must pass the
502 * deallocation responsibility back to liberasurecode.
503 *
504 * @param desc - liberasurecode descriptor/handle
505 * from liberasurecode_instance_create()
506 * @param data - (char *) buffer of data decoded by
507 * librasurecode_decode
508 * @return 0 in success; -error otherwise
509 */
liberasurecode_decode_cleanup(int desc,char * data)510 int liberasurecode_decode_cleanup(int desc, char *data)
511 {
512 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
513 if (NULL == instance) {
514 return -EBACKENDNOTAVAIL;
515 }
516
517 free(data);
518
519 return 0;
520 }
521
522 /**
523 * Reconstruct original data from a set of k encoded fragments
524 *
525 * @param desc - liberasurecode descriptor/handle
526 * from liberasurecode_instance_create()
527 * @param fragments - erasure encoded fragments (> = k)
528 * @param num_fragments - number of fragments being passed in
529 * @param fragment_len - length of each fragment (assume they are the same)
530 * @param force_metadata_checks - force fragment metadata checks (default: 0)
531 * @param out_data - _output_ pointer to decoded data
532 * @param out_data_len - _output_ length of decoded output
533 * @return 0 on success, -error code otherwise
534 */
liberasurecode_decode(int desc,char ** available_fragments,int num_fragments,uint64_t fragment_len,int force_metadata_checks,char ** out_data,uint64_t * out_data_len)535 int liberasurecode_decode(int desc,
536 char **available_fragments, /* input */
537 int num_fragments, uint64_t fragment_len, /* input */
538 int force_metadata_checks, /* input */
539 char **out_data, uint64_t *out_data_len) /* output */
540 {
541 int i, j;
542 int ret = 0;
543
544 int k = -1, m = -1;
545 int orig_data_size = 0;
546
547 int blocksize = 0;
548 char **data = NULL;
549 char **parity = NULL;
550 char **data_segments = NULL;
551 char **parity_segments = NULL;
552 int *missing_idxs = NULL;
553
554 uint64_t realloc_bm = 0;
555
556 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
557 if (NULL == instance) {
558 ret = -EBACKENDNOTAVAIL;
559 goto out;
560 }
561
562 if (NULL == available_fragments) {
563 log_error("Pointer to encoded fragments buffer is null!");
564 ret = -EINVALIDPARAMS;
565 goto out;
566 }
567
568 if (NULL == out_data) {
569 log_error("Pointer to decoded data buffer is null!");
570 ret = -EINVALIDPARAMS;
571 goto out;
572 }
573
574 if (NULL == out_data_len) {
575 log_error("Pointer to decoded data length variable is null!");
576 ret = -EINVALIDPARAMS;
577 goto out;
578 }
579
580 k = instance->args.uargs.k;
581 m = instance->args.uargs.m;
582
583 if (num_fragments < k) {
584 log_error("Not enough fragments to decode, got %d, need %d!",
585 num_fragments, k);
586 ret = -EINSUFFFRAGS;
587 goto out;
588 }
589
590 for (i = 0; i < num_fragments; ++i) {
591 /* Verify metadata checksum */
592 if (is_invalid_fragment_header(
593 (fragment_header_t *) available_fragments[i])) {
594 log_error("Invalid fragment header information!");
595 ret = -EBADHEADER;
596 goto out;
597 }
598 }
599
600 if (instance->common.id != EC_BACKEND_SHSS) {
601 /* shss (ntt_backend) must force to decode */
602 // TODO: Add a frag and function to handle whether the backend want to decode or not.
603 /*
604 * Try to re-assebmle the original data before attempting a decode
605 */
606 ret = fragments_to_string(k, m,
607 available_fragments, num_fragments,
608 out_data, out_data_len);
609
610 if (ret == 0) {
611 /* We were able to get the original data without decoding! */
612 goto out;
613 }
614 }
615
616 /*
617 * Allocate arrays for data, parity and missing_idxs
618 */
619 data = alloc_zeroed_buffer(sizeof(char*) * k);
620 if (NULL == data) {
621 log_error("Could not allocate data buffer!");
622 goto out;
623 }
624
625 parity = alloc_zeroed_buffer(sizeof(char*) * m);
626 if (NULL == parity) {
627 log_error("Could not allocate parity buffer!");
628 goto out;
629 }
630
631 missing_idxs = alloc_and_set_buffer(sizeof(char*) * (k + m), -1);
632 if (NULL == missing_idxs) {
633 log_error("Could not allocate missing_idxs buffer!");
634 goto out;
635 }
636
637 /* If metadata checks requested, check fragment integrity upfront */
638 if (force_metadata_checks) {
639 int num_invalid_fragments = 0;
640 for (i = 0; i < num_fragments; ++i) {
641 if (is_invalid_fragment(desc, available_fragments[i])) {
642 ++num_invalid_fragments;
643 }
644 }
645 if ((num_fragments - num_invalid_fragments) < k) {
646 ret = -EINSUFFFRAGS;
647 log_error("Not enough valid fragments available for decode!");
648 goto out;
649 }
650 }
651
652 /*
653 * Separate the fragments into data and parity. Also determine which
654 * pieces are missing.
655 */
656 ret = get_fragment_partition(k, m, available_fragments, num_fragments,
657 data, parity, missing_idxs);
658
659 if (ret < 0) {
660 log_error("Could not properly partition the fragments!");
661 goto out;
662 }
663
664 /*
665 * Preparing the fragments for decode. This will alloc aligned buffers
666 * when unaligned buffers were passed in available_fragments. It passes
667 * back a bitmap telling us which buffers need to be freed by us
668 * (realloc_bm).
669 *
670 */
671 ret = prepare_fragments_for_decode(k, m,
672 data, parity, missing_idxs,
673 &orig_data_size, &blocksize,
674 fragment_len, &realloc_bm);
675 if (ret < 0) {
676 log_error("Could not prepare fragments for decode!");
677 goto out;
678 }
679
680 data_segments = alloc_zeroed_buffer(k * sizeof(char *));
681 parity_segments = alloc_zeroed_buffer(m * sizeof(char *));
682 get_data_ptr_array_from_fragments(data_segments, data, k);
683 get_data_ptr_array_from_fragments(parity_segments, parity, m);
684
685 /* call the backend decode function passing it desc instance */
686 ret = instance->common.ops->decode(instance->desc.backend_desc,
687 data_segments, parity_segments,
688 missing_idxs, blocksize);
689
690 if (ret < 0) {
691 log_error("Encountered error in backend decode function!");
692 goto out;
693 }
694
695 /*
696 * Need to fill in the missing data headers so we can generate
697 * the original string.
698 */
699 j = 0;
700 while (missing_idxs[j] >= 0) {
701 int set_chksum = 1;
702 int missing_idx = missing_idxs[j];
703 if (missing_idx < k) {
704 /* Generate headers */
705 char *fragment_ptr = data[missing_idx];
706 init_fragment_header(fragment_ptr);
707 add_fragment_metadata(instance, fragment_ptr, missing_idx,
708 orig_data_size, blocksize, instance->args.uargs.ct,
709 !set_chksum);
710 }
711 j++;
712 }
713
714 /* Try to generate the original string */
715 ret = fragments_to_string(k, m, data, k, out_data, out_data_len);
716
717 if (ret < 0) {
718 log_error("Could not convert decoded fragments to a string!");
719 }
720
721 out:
722 /* Free the buffers allocated in prepare_fragments_for_decode */
723 if (realloc_bm != 0) {
724 for (i = 0; i < k; i++) {
725 if (realloc_bm & (1 << i)) {
726 free(data[i]);
727 }
728 }
729
730 for (i = 0; i < m; i++) {
731 if (realloc_bm & (1 << (i + k))) {
732 free(parity[i]);
733 }
734 }
735 }
736
737 free(data);
738 free(parity);
739 free(missing_idxs);
740 free(data_segments);
741 free(parity_segments);
742
743 return ret;
744 }
745
746 /**
747 * Reconstruct a missing fragment from a subset of available fragments
748 *
749 * @param desc - liberasurecode descriptor/handle
750 * from liberasurecode_instance_create()
751 * @param fragment_len - size in bytes of the fragments
752 * @param available_fragments - erasure encoded fragments
753 * @param num_fragments - number of fragments being passed in
754 * @param destination_idx - missing idx to reconstruct
755 * @param out_fragment - output of reconstruct
756 * @return 0 on success, -error code otherwise
757 */
liberasurecode_reconstruct_fragment(int desc,char ** available_fragments,int num_fragments,uint64_t fragment_len,int destination_idx,char * out_fragment)758 int liberasurecode_reconstruct_fragment(int desc,
759 char **available_fragments, /* input */
760 int num_fragments, uint64_t fragment_len, /* input */
761 int destination_idx, /* input */
762 char* out_fragment) /* output */
763 {
764 int ret = 0;
765 int blocksize = 0;
766 int orig_data_size = 0;
767 char **data = NULL;
768 char **parity = NULL;
769 int *missing_idxs = NULL;
770 char *fragment_ptr = NULL;
771 int is_destination_missing = 0;
772 int k = -1;
773 int m = -1;
774 int i;
775 uint64_t realloc_bm = 0;
776 char **data_segments = NULL;
777 char **parity_segments = NULL;
778 int set_chksum = 1;
779
780 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
781 if (NULL == instance) {
782 ret = -EBACKENDNOTAVAIL;
783 goto out;
784 }
785
786 if (NULL == available_fragments) {
787 log_error("Can not reconstruct fragment, available fragments pointer is NULL");
788 ret = -EINVALIDPARAMS;
789 goto out;
790 }
791
792 if (NULL == out_fragment) {
793 log_error("Can not reconstruct fragment, output fragment pointer is NULL");
794 ret = -EINVALIDPARAMS;
795 goto out;
796 }
797
798 k = instance->args.uargs.k;
799 m = instance->args.uargs.m;
800
801 for (i = 0; i < num_fragments; i++) {
802 /* Verify metadata checksum */
803 if (is_invalid_fragment_header(
804 (fragment_header_t *) available_fragments[i])) {
805 log_error("Invalid fragment header information!");
806 ret = -EBADHEADER;
807 goto out;
808 }
809 }
810
811 /*
812 * Allocate arrays for data, parity and missing_idxs
813 */
814 data = alloc_zeroed_buffer(sizeof(char*) * k);
815 if (NULL == data) {
816 log_error("Could not allocate data buffer!");
817 ret = -ENOMEM;
818 goto out;
819 }
820
821 parity = alloc_zeroed_buffer(sizeof(char*) * m);
822 if (NULL == parity) {
823 log_error("Could not allocate parity buffer!");
824 ret = -ENOMEM;
825 goto out;
826 }
827
828 missing_idxs = alloc_and_set_buffer(sizeof(int*) * (k + m), -1);
829 if (NULL == missing_idxs) {
830 log_error("Could not allocate missing_idxs buffer!");
831 ret = -ENOMEM;
832 goto out;
833 }
834
835 /*
836 * Separate the fragments into data and parity. Also determine which
837 * pieces are missing.
838 */
839 ret = get_fragment_partition(k, m, available_fragments, num_fragments,
840 data, parity, missing_idxs);
841
842 if (ret < 0) {
843 log_error("Could not properly partition the fragments!");
844 goto out;
845 }
846
847 /*
848 * Odd corner-case: If the caller passes in a destination_idx that
849 * is also included in the available fragments list, we should *not*
850 * try to reconstruct.
851 *
852 * For now, we will log a warning and do nothing. In the future, we
853 * should probably log and return an error.
854 *
855 */
856 i = 0;
857 while (missing_idxs[i] > -1) {
858 if (missing_idxs[i] == destination_idx) {
859 is_destination_missing = 1;
860 }
861 i++;
862 }
863
864 if (!is_destination_missing) {
865 if (destination_idx < k) {
866 fragment_ptr = data[destination_idx];
867 } else {
868 fragment_ptr = parity[destination_idx - k];
869 }
870 log_warn("Dest idx for reconstruction was supplied as available buffer!");
871 goto destination_available;
872 }
873
874 /*
875 * Preparing the fragments for reconstruction. This will alloc aligned
876 * buffers when unaligned buffers were passed in available_fragments.
877 * It passes back a bitmap telling us which buffers need to be freed by
878 * us (realloc_bm).
879 */
880 ret = prepare_fragments_for_decode(k, m, data, parity, missing_idxs,
881 &orig_data_size, &blocksize,
882 fragment_len, &realloc_bm);
883 if (ret < 0) {
884 log_error("Could not prepare fragments for reconstruction!");
885 goto out;
886 }
887 data_segments = alloc_zeroed_buffer(k * sizeof(char *));
888 parity_segments = alloc_zeroed_buffer(m * sizeof(char *));
889 get_data_ptr_array_from_fragments(data_segments, data, k);
890 get_data_ptr_array_from_fragments(parity_segments, parity, m);
891
892
893 /* call the backend reconstruct function passing it desc instance */
894 ret = instance->common.ops->reconstruct(instance->desc.backend_desc,
895 data_segments, parity_segments,
896 missing_idxs, destination_idx,
897 blocksize);
898 if (ret < 0) {
899 log_error("Could not reconstruct fragment!");
900 goto out;
901 }
902
903 /*
904 * Update the header to reflect the newly constructed fragment
905 */
906 if (destination_idx < k) {
907 fragment_ptr = data[destination_idx];
908 } else {
909 fragment_ptr = parity[destination_idx - k];
910 }
911 init_fragment_header(fragment_ptr);
912 add_fragment_metadata(instance, fragment_ptr, destination_idx,
913 orig_data_size, blocksize, instance->args.uargs.ct,
914 set_chksum);
915
916 destination_available:
917 /*
918 * Copy the reconstructed fragment to the output buffer
919 *
920 * Note: the address stored in fragment_ptr will be freed below
921 */
922 memcpy(out_fragment, fragment_ptr, fragment_len);
923
924 out:
925 /* Free the buffers allocated in prepare_fragments_for_decode */
926 if (realloc_bm != 0) {
927 for (i = 0; i < k; i++) {
928 if (realloc_bm & (1 << i)) {
929 free(data[i]);
930 }
931 }
932
933 for (i = 0; i < m; i++) {
934 if (realloc_bm & (1 << (i + k))) {
935 free(parity[i]);
936 }
937 }
938 }
939
940 free(data);
941 free(parity);
942 free(missing_idxs);
943 free(data_segments);
944 free(parity_segments);
945
946 return ret;
947 }
948
949 /**
950 * Return a list of lists with valid rebuild indexes given
951 * a list of missing indexes.
952 *
953 * @desc: liberasurecode instance descriptor (obtained with
954 * liberasurecode_instance_create)
955 * @fragments_to_reconstruct list of indexes to reconstruct
956 * @fragments_to_exclude list of indexes to exclude from
957 reconstruction equation
958 * @fragments_needed list of fragments needed to reconstruct
959 fragments in fragments_to_reconstruct
960 *
961 * @return a list of lists (bitmaps) of indexes to rebuild data
962 * from (in 'fragments_needed')
963 */
liberasurecode_fragments_needed(int desc,int * fragments_to_reconstruct,int * fragments_to_exclude,int * fragments_needed)964 int liberasurecode_fragments_needed(int desc,
965 int *fragments_to_reconstruct,
966 int *fragments_to_exclude,
967 int *fragments_needed)
968 {
969 int ret = 0;
970
971 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
972 if (NULL == instance) {
973 ret = -EBACKENDNOTAVAIL;
974 goto out_error;
975 }
976 if (NULL == fragments_to_reconstruct) {
977 log_error("Unable to determine list of fragments needed, pointer to list of indexes to reconstruct is NULL.");
978 ret = -EINVALIDPARAMS;
979 goto out_error;
980 }
981
982 if (NULL == fragments_to_exclude) {
983 log_error("Unable to determine list of fragments needed, pointer to list of fragments to exclude is NULL.");
984 ret = -EINVALIDPARAMS;
985 goto out_error;
986 }
987
988 if (NULL == fragments_needed) {
989 log_error("Unable to determine list of fragments needed, pointer to list of fragments to reconstruct is NULL.");
990 ret = -EINVALIDPARAMS;
991 goto out_error;
992 }
993
994 /* FIXME preprocessing */
995
996 /* call the backend fragments_needed function passing it desc instance */
997 ret = instance->common.ops->fragments_needed(
998 instance->desc.backend_desc,
999 fragments_to_reconstruct, fragments_to_exclude, fragments_needed);
1000
1001 out_error:
1002 return ret;
1003 }
1004
1005 /* =~=*=~==~=*=~==~=*=~==~=*=~===~=*=~==~=*=~===~=*=~==~=*=~===~=*=~==~=*=~= */
1006
1007 /**
1008 * Get opaque metadata for a fragment. The metadata is opaque to the
1009 * client, but meaningful to the underlying library. It is used to verify
1010 * stripes in verify_stripe_metadata().
1011 *
1012 * @param fragment - fragment pointer
1013 *
1014 * @param fragment_metadata - pointer to output fragment metadata struct
1015 * (reference passed by the user)
1016 */
liberasurecode_get_fragment_metadata(char * fragment,fragment_metadata_t * fragment_metadata)1017 int liberasurecode_get_fragment_metadata(char *fragment,
1018 fragment_metadata_t *fragment_metadata)
1019 {
1020 int ret = 0;
1021 fragment_header_t *fragment_hdr = NULL;
1022
1023 if (NULL == fragment) {
1024 log_error("Need valid fragment object to get metadata for");
1025 ret = -EINVALIDPARAMS;
1026 goto out;
1027 }
1028
1029 if (NULL == fragment_metadata) {
1030 log_error("Need valid fragment_metadata object for return value");
1031 ret = -EINVALIDPARAMS;
1032 goto out;
1033 }
1034
1035 /* Verify metadata checksum */
1036 if (is_invalid_fragment_header(
1037 (fragment_header_t *) fragment)) {
1038 log_error("Invalid fragment header information!");
1039 ret = -EBADHEADER;
1040 goto out;
1041 }
1042
1043 memcpy(fragment_metadata, fragment, sizeof(struct fragment_metadata));
1044 fragment_hdr = (fragment_header_t *) fragment;
1045 if (LIBERASURECODE_FRAG_HEADER_MAGIC != fragment_hdr->magic) {
1046 log_error("Invalid fragment, illegal magic value");
1047 ret = -EINVALIDPARAMS;
1048 goto out;
1049 }
1050
1051 switch(fragment_hdr->meta.chksum_type) {
1052 case CHKSUM_CRC32: {
1053 uint32_t computed_chksum = 0;
1054 uint32_t stored_chksum = fragment_hdr->meta.chksum[0];
1055 char *fragment_data = get_data_ptr_from_fragment(fragment);
1056 uint64_t fragment_size = fragment_hdr->meta.size;
1057 computed_chksum = crc32(0, fragment_data, fragment_size);
1058 if (stored_chksum != computed_chksum) {
1059 fragment_metadata->chksum_mismatch = 1;
1060 } else {
1061 fragment_metadata->chksum_mismatch = 0;
1062 }
1063 break;
1064 }
1065 case CHKSUM_MD5:
1066 break;
1067 case CHKSUM_NONE:
1068 default:
1069 break;
1070 }
1071
1072 out:
1073 return ret;
1074 }
1075
is_invalid_fragment_header(fragment_header_t * header)1076 int is_invalid_fragment_header(fragment_header_t *header)
1077 {
1078 uint32_t *stored_csum = NULL, csum = 0;
1079 assert (NULL != header);
1080 if (header->libec_version == 0)
1081 /* libec_version must be bigger than 0 */
1082 return 1;
1083 if (header->libec_version < _VERSION(1,2,0))
1084 /* no metadata checksum support */
1085 return 0;
1086 stored_csum = get_metadata_chksum((char *) header);
1087 if (NULL == stored_csum)
1088 return 1; /* can't verify, possibly crc32 call error */
1089 csum = crc32(0, &header->meta, sizeof(fragment_metadata_t));
1090 return (*stored_csum != csum);
1091 }
1092
liberasurecode_verify_fragment_metadata(ec_backend_t be,fragment_metadata_t * md)1093 int liberasurecode_verify_fragment_metadata(ec_backend_t be,
1094 fragment_metadata_t *md)
1095 {
1096 int k = be->args.uargs.k;
1097 int m = be->args.uargs.m;
1098 if (md->idx > (k + m)) {
1099 return 1;
1100 }
1101 if (md->backend_id != be->common.id) {
1102 return 1;
1103 }
1104 if (!be->common.ops->is_compatible_with(md->backend_version)) {
1105 return 1;
1106 }
1107 return 0;
1108 }
1109
is_invalid_fragment_metadata(int desc,fragment_metadata_t * fragment_metadata)1110 int is_invalid_fragment_metadata(int desc, fragment_metadata_t *fragment_metadata)
1111 {
1112 ec_backend_t be = liberasurecode_backend_instance_get_by_desc(desc);
1113 if (!be) {
1114 log_error("Unable to verify fragment metadata: invalid backend id %d.",
1115 desc);
1116 return -EINVALIDPARAMS;
1117 }
1118 if (liberasurecode_verify_fragment_metadata(be,
1119 fragment_metadata) != 0) {
1120 return -EBADHEADER;
1121 }
1122 if (!be->common.ops->is_compatible_with(fragment_metadata->backend_version)) {
1123 return -EBADHEADER;
1124 }
1125 if (fragment_metadata->chksum_mismatch == 1) {
1126 return -EBADCHKSUM;
1127 }
1128 return 0;
1129 }
1130
is_invalid_fragment(int desc,char * fragment)1131 int is_invalid_fragment(int desc, char *fragment)
1132 {
1133 uint32_t ver = 0;
1134 fragment_metadata_t fragment_metadata;
1135 ec_backend_t be = liberasurecode_backend_instance_get_by_desc(desc);
1136 if (!be) {
1137 log_error("Unable to verify fragment metadata: invalid backend id %d.",
1138 desc);
1139 return 1;
1140 }
1141 if (!fragment) {
1142 log_error("Unable to verify fragment validity: fragments missing.");
1143 return 1;
1144 }
1145 if (get_libec_version(fragment, &ver) != 0 ||
1146 ver > LIBERASURECODE_VERSION) {
1147 return 1;
1148 }
1149 if (liberasurecode_get_fragment_metadata(fragment, &fragment_metadata) != 0) {
1150 return 1;
1151 }
1152 if (is_invalid_fragment_metadata(desc, &fragment_metadata) != 0) {
1153 return 1;
1154 }
1155 return 0;
1156 }
1157
liberasurecode_verify_stripe_metadata(int desc,char ** fragments,int num_fragments)1158 int liberasurecode_verify_stripe_metadata(int desc,
1159 char **fragments, int num_fragments)
1160 {
1161 int i = 0;
1162 if (!fragments) {
1163 log_error("Unable to verify stripe metadata: fragments missing.");
1164 return -EINVALIDPARAMS;
1165 }
1166 if (num_fragments <= 0) {
1167 log_error("Unable to verify stripe metadata: "
1168 "number of fragments must be greater than 0.");
1169 return -EINVALIDPARAMS;
1170 }
1171
1172 for (i = 0; i < num_fragments; i++) {
1173 fragment_metadata_t *fragment_metadata = (fragment_metadata_t*)fragments[i];
1174 int ret = is_invalid_fragment_metadata(desc, fragment_metadata);
1175 if (ret < 0) {
1176 return ret;
1177 }
1178 }
1179
1180 return 0;
1181 }
1182
1183 /* =~=*=~==~=*=~==~=*=~==~=*=~===~=*=~==~=*=~===~=*=~==~=*=~===~=*=~==~=*=~= */
1184
1185 /**
1186 * This computes the aligned size of a buffer passed into
1187 * the encode function. The encode function must pad fragments
1188 * to be algined with the word size (w) and the last fragment also
1189 * needs to be aligned. This computes the sum of the algined fragment
1190 * sizes for a given buffer to encode.
1191 */
liberasurecode_get_aligned_data_size(int desc,uint64_t data_len)1192 int liberasurecode_get_aligned_data_size(int desc, uint64_t data_len)
1193 {
1194 int k;
1195 int ret = 0;
1196 int word_size;
1197 int alignment_multiple;
1198
1199 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
1200 if (NULL == instance) {
1201 ret = -EBACKENDNOTAVAIL;
1202 goto out;
1203 }
1204
1205 k = instance->args.uargs.k;
1206
1207 word_size = instance->common.ops->element_size(
1208 instance->desc.backend_desc) / 8;
1209
1210 alignment_multiple = k * word_size;
1211
1212 ret = (int) ceill( (double)
1213 data_len / alignment_multiple) * alignment_multiple;
1214
1215 out:
1216 return ret;
1217 }
1218
1219 /**
1220 * This will return the minumum encode size, which is the minimum
1221 * buffer size that can be encoded.
1222 */
liberasurecode_get_minimum_encode_size(int desc)1223 int liberasurecode_get_minimum_encode_size(int desc)
1224 {
1225 return liberasurecode_get_aligned_data_size(desc, 1);
1226 }
1227
liberasurecode_get_fragment_size(int desc,int data_len)1228 int liberasurecode_get_fragment_size(int desc, int data_len)
1229 {
1230 ec_backend_t instance = liberasurecode_backend_instance_get_by_desc(desc);
1231 // TODO: Create a common function to calculate fragment size also for preprocessing
1232 if (NULL == instance)
1233 return -EBACKENDNOTAVAIL;
1234 int aligned_data_len = get_aligned_data_size(instance, data_len);
1235 int size = (aligned_data_len / instance->args.uargs.k) + instance->common.backend_metadata_size;
1236
1237 return size;
1238 }
1239
1240
1241 /**
1242 * This will return the liberasurecode version for the descriptor
1243 */
1244
liberasurecode_get_version()1245 uint32_t liberasurecode_get_version()
1246 {
1247 return LIBERASURECODE_VERSION;
1248 }
1249
1250 /* ==~=*=~==~=*=~==~=*=~==~=*=~==~=* misc *=~==~=*=~==~=*=~==~=*=~==~=*=~== */
1251
1252 #if 0
1253 /* Validate backend before calling init */
1254 int liberasurecode_backend_validate(ec_backend_t backend)
1255 {
1256 /* Verify that the backend implements all required methods */
1257 }
1258
1259 /* FIXME - do we need to use reference counts if we are creating
1260 * a new instance per user */
1261
1262 /* Get a reference to an EC backend */
1263 ec_backend_t liberasurecode_backend_get(const char *name)
1264 {
1265 ec_backend_t b = liberasurecode_backend_lookup_by_name(name);
1266 if (NULL != b)
1267 ++b->users;
1268 return b;
1269 }
1270
1271 /* Drop an EC backend reference held */
1272 void liberasurecode_backend_put(ec_backend_t backend)
1273 {
1274 if (backend->users > 0)
1275 --backend->users;
1276 }
1277
1278 /* Query interface for active instances */
1279 ec_backend_t liberasurecode_backend_instance_active(ec_backend_t instance)
1280 {
1281 ec_backend_t b;
1282
1283 SLIST_FOREACH(b, &active_instances, link) {
1284 if (strcmp(b->name, name) == 0)
1285 return b;
1286 }
1287
1288 return NULL;
1289 }
1290
1291 ec_backend_t liberasurecode_backend_lookup_by_soname(const char *soname)
1292 {
1293 ec_backend_t b;
1294
1295 SLIST_FOREACH(b, &active_instances, link) {
1296 if (strcmp(b->soname, soname) == 0)
1297 return b;
1298 }
1299
1300 return NULL;
1301 }
1302 #endif
1303
1304 /* ==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~==~=*=~== */
1305