From 8d067ab2f631b147745e5eb3cf85056042c1439e Mon Sep 17 00:00:00 2001 From: Kota Tsuyuzaki Date: Thu, 3 Nov 2016 04:54:19 -0700 Subject: ISA-L Cauchy support This is for supporting ISA-L cauchy based matrix. The difference from isa_l_rs_vand is only the matrix to use the encode/decode calculation. As a known issue, isa_l_rs_vand backend has constraint for the combinations of the available fragment to be able to decode/reconstuct. (See related change in detail) To avoid the constraint, this patch adds another isa-l backend to use cauchy matrix and keep the backward compatibility, this is in another isa_l_rs_cauchy namespace. For implementation consieration, the code is almost same except the matrix generation fucntion so that this patch makes isa_l_common.c file for gathering common fucntions like init/encode/decode/reconstruct. And then the common init funciton takes an extra args "gen_matrix_func_name" for entry point to load the fucntion by dlsym from isa-l .so file. Co-Authored-By: Clay Gerrard Related-Change: Icee788a0931fe692fe0de31fabc4ba450e338a87 Change-Id: I6eb150d9d0c3febf233570fa7729f9f72df2e9be --- src/Makefile.am | 3 + src/backends/isa-l/isa_l_common.c | 544 ++++++++++++++++++++++++++++++++++ src/backends/isa-l/isa_l_rs_cauchy.c | 86 ++++++ src/backends/isa-l/isa_l_rs_vand.c | 553 +---------------------------------- src/erasurecode.c | 2 + 5 files changed, 643 insertions(+), 545 deletions(-) create mode 100644 src/backends/isa-l/isa_l_common.c create mode 100644 src/backends/isa-l/isa_l_rs_cauchy.c (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am index 2566f74..eb2f89f 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -6,6 +6,7 @@ INCLUDES = \ -I$(top_srcdir)/include/erasurecode \ -I$(top_srcdir)/include/xor_codes \ -I$(top_srcdir)/include/rs_vand \ + -I$(top_srcdir)/include/isa_l \ -I$(top_srcdir)/include/shss # liberasurecode params @@ -20,7 +21,9 @@ liberasurecode_la_SOURCES = \ backends/xor/flat_xor_hd.c \ backends/jerasure/jerasure_rs_vand.c \ backends/jerasure/jerasure_rs_cauchy.c \ + backends/isa-l/isa_l_common.c \ backends/isa-l/isa_l_rs_vand.c \ + backends/isa-l/isa_l_rs_cauchy.c \ backends/rs_vand/liberasurecode_rs_vand.c \ builtin/rs_vand/rs_galois.c \ backends/shss/shss.c diff --git a/src/backends/isa-l/isa_l_common.c b/src/backends/isa-l/isa_l_common.c new file mode 100644 index 0000000..07deb13 --- /dev/null +++ b/src/backends/isa-l/isa_l_common.c @@ -0,0 +1,544 @@ +/* + * Copyright 2014 Kevin M Greenan + * Copyright 2014 Tushar Gohad + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, this + * list of conditions and the following disclaimer in the documentation and/or + * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY + * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE + * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * isa_l_rs_vand backend implementation + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +#include +#include + +#include "erasurecode.h" +#include "erasurecode_backend.h" +#include "erasurecode_helpers.h" +#include "erasurecode_helpers_ext.h" +#include "isa_l_common.h" + +int isa_l_encode(void *desc, char **data, char **parity, + int blocksize) +{ + isa_l_descriptor *isa_l_desc = (isa_l_descriptor*) desc; + + unsigned char *g_tbls = NULL; + int k = isa_l_desc->k; + int m = isa_l_desc->m; + + // Generate g_tbls from encode matrix encode_matrix + g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); + if (NULL == g_tbls) { + return -1; + } + + isa_l_desc->ec_init_tables(k, m, &isa_l_desc->matrix[k * k], g_tbls); + + /* FIXME - make ec_encode_data return a value */ + isa_l_desc->ec_encode_data(blocksize, k, m, g_tbls, (unsigned char**)data, + (unsigned char**)parity); + free(g_tbls); + return 0; +} + +static unsigned char* isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs) +{ + int i = 0, j = 0, l = 0; + int n = k + m; + unsigned char *decode_matrix = malloc(sizeof(unsigned char) * k * k); + uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + + while (i < k && l < n) { + if (((1 << l) & missing_bm) == 0) { + for (j = 0; j < k; j++) { + decode_matrix[(k * i) + j] = encode_matrix[(k * l) + j]; + } + i++; + } + l++; + } + + if (i != k) { + free(decode_matrix); + decode_matrix = NULL; + } + + return decode_matrix; +} + +static int get_num_missing_elements(int *missing_idxs) +{ + int i = 0; + + while (missing_idxs[i] > -1) { + i++; + } + + return i; +} + +static void mult_and_xor_row(unsigned char *to_row, + unsigned char *from_row, + unsigned char val, + int num_elems, + gf_mul_func gf_mul) +{ + int i; + + for (i = 0; i < num_elems; i++) { + to_row[i] ^= gf_mul(val, from_row[i]); + } +} + +/* + * TODO: Add in missing parity rows and adjust the inverse_rows to + * be used for parity. + */ +static unsigned char* get_inverse_rows(int k, + int m, + unsigned char *decode_inverse, + unsigned char* encode_matrix, + int *missing_idxs, + gf_mul_func gf_mul) +{ + uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + int num_missing_elements = get_num_missing_elements(missing_idxs); + unsigned char *inverse_rows = (unsigned char*)malloc(sizeof(unsigned + char*) * k * num_missing_elements); + int i, j, l = 0; + int n = k + m; + + if (NULL == inverse_rows) { + return NULL; + } + + memset(inverse_rows, 0, sizeof(unsigned + char*) * k * num_missing_elements); + + /* + * Fill in rows for missing data + */ + for (i = 0; i < k; i++) { + if ((1 << i) & missing_bm) { + for (j = 0; j < k; j++) { + inverse_rows[(l * k) + j] = decode_inverse[(i * k) + j]; + } + l++; + } + } + + /* + * Process missing parity. + * + * Start with an all-zero row. + * + * For each data element, if the data element is: + * + * Available: XOR the corresponding coefficient from the + * encoding matrix. + * + * Unavailable: multiply corresponding coefficient with + * the row that corresponds to the missing data in inverse_rows + * and XOR the resulting row with this row. + */ + for (i = k; i < n; i++) { + // Parity is missing + if ((1 << i) & missing_bm) { + int d_idx_avail = 0; + int d_idx_unavail = 0; + for (j = 0; j < k; j++) { + // This data is available, so we can use the encode matrix + if (((1 << j) & missing_bm) == 0) { + inverse_rows[(l * k) + d_idx_avail] ^= encode_matrix[(i * k) + j]; + d_idx_avail++; + } else { + mult_and_xor_row(&inverse_rows[l * k], + &inverse_rows[d_idx_unavail * k], + encode_matrix[(i * k) + j], + k, + gf_mul); + d_idx_unavail++; + } + } + l++; + } + } + return inverse_rows; +} + +int isa_l_decode(void *desc, char **data, char **parity, + int *missing_idxs, int blocksize) +{ + isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc; + + unsigned char *g_tbls = NULL; + unsigned char *decode_matrix = NULL; + unsigned char *decode_inverse = NULL; + unsigned char *inverse_rows = NULL; + unsigned char **decoded_elements = NULL; + unsigned char **available_fragments = NULL; + int k = isa_l_desc->k; + int m = isa_l_desc->m; + int n = k + m; + int ret = -1; + int i, j; + + int num_missing_elements = get_num_missing_elements(missing_idxs); + uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + + decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs); + + if (NULL == decode_matrix) { + goto out; + } + + decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k); + + if (NULL == decode_inverse) { + goto out; + } + + int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k); + if (im_ret < 0) { + goto out; + } + + // Generate g_tbls from computed decode matrix (k x k) matrix + g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); + if (NULL == g_tbls) { + goto out; + } + + inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul); + + decoded_elements = (unsigned char**)malloc(sizeof(unsigned char*)*num_missing_elements); + if (NULL == decoded_elements) { + goto out; + } + + available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k); + if (NULL == available_fragments) { + goto out; + } + + j = 0; + for (i = 0; i < n; i++) { + if (missing_bm & (1 << i)) { + continue; + } + if (j == k) { + break; + } + if (i < k) { + available_fragments[j] = (unsigned char*)data[i]; + } else { + available_fragments[j] = (unsigned char*)parity[i-k]; + } + j++; + } + + // Grab pointers to memory needed for missing data fragments + j = 0; + for (i = 0; i < k; i++) { + if (missing_bm & (1 << i)) { + decoded_elements[j] = (unsigned char*)data[i]; + j++; + } + } + for (i = k; i < n; i++) { + if (missing_bm & (1 << i)) { + decoded_elements[j] = (unsigned char*)parity[i - k]; + j++; + } + } + + isa_l_desc->ec_init_tables(k, num_missing_elements, inverse_rows, g_tbls); + + isa_l_desc->ec_encode_data(blocksize, k, num_missing_elements, g_tbls, (unsigned char**)available_fragments, + (unsigned char**)decoded_elements); + + ret = 0; + +out: + free(g_tbls); + free(decode_matrix); + free(decode_inverse); + free(inverse_rows); + free(decoded_elements); + free(available_fragments); + + return ret; +} + +int isa_l_reconstruct(void *desc, char **data, char **parity, + int *missing_idxs, int destination_idx, int blocksize) +{ + isa_l_descriptor *isa_l_desc = (isa_l_descriptor*) desc; + unsigned char *g_tbls = NULL; + unsigned char *decode_matrix = NULL; + unsigned char *decode_inverse = NULL; + unsigned char *inverse_rows = NULL; + unsigned char *reconstruct_buf = NULL; + unsigned char **available_fragments = NULL; + int k = isa_l_desc->k; + int m = isa_l_desc->m; + int n = k + m; + int ret = -1; + int i, j; + uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + int inverse_row = -1; + + /** + * Get available elements and compute the inverse of their + * corresponding rows. + */ + decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs); + + if (NULL == decode_matrix) { + goto out; + } + + decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k); + + if (NULL == decode_inverse) { + goto out; + } + + int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k); + if (im_ret < 0) { + goto out; + } + + /** + * Get the row needed to reconstruct + */ + inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul); + + // Generate g_tbls from computed decode matrix (k x k) matrix + g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); + if (NULL == g_tbls) { + goto out; + } + + /** + * Fill in the available elements + */ + available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k); + if (NULL == available_fragments) { + goto out; + } + + j = 0; + for (i = 0; i < n; i++) { + if (missing_bm & (1 << i)) { + continue; + } + if (j == k) { + break; + } + if (i < k) { + available_fragments[j] = (unsigned char*)data[i]; + } else { + available_fragments[j] = (unsigned char*)parity[i-k]; + } + j++; + } + + /** + * Copy pointer of buffer to reconstruct + */ + j = 0; + for (i = 0; i < n; i++) { + if (missing_bm & (1 << i)) { + if (i == destination_idx) { + if (i < k) { + reconstruct_buf = (unsigned char*)data[i]; + } else { + reconstruct_buf = (unsigned char*)parity[i-k]; + } + inverse_row = j; + break; + } + j++; + } + } + + /** + * Do the reconstruction + */ + isa_l_desc->ec_init_tables(k, 1, &inverse_rows[inverse_row * k], g_tbls); + + isa_l_desc->ec_encode_data(blocksize, k, 1, g_tbls, (unsigned char**)available_fragments, + (unsigned char**)&reconstruct_buf); + + ret = 0; +out: + free(g_tbls); + free(decode_matrix); + free(decode_inverse); + free(inverse_rows); + free(available_fragments); + + return ret; +} + +int isa_l_min_fragments(void *desc, int *missing_idxs, + int *fragments_to_exclude, int *fragments_needed) +{ + isa_l_descriptor *isa_l_desc = (isa_l_descriptor*)desc; + + uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude); + uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm; + int i; + int j = 0; + int ret = -1; + + for (i = 0; i < (isa_l_desc->k + isa_l_desc->m); i++) { + if (!(missing_bm & (1 << i))) { + fragments_needed[j] = i; + j++; + } + if (j == isa_l_desc->k) { + ret = 0; + fragments_needed[j] = -1; + break; + } + } + + return ret; +} + +/** + * Return the element-size, which is the number of bits stored + * on a given device, per codeword. This is always 8 in ISA-L + * + * Returns the size in bits! + */ +int isa_l_element_size(void* desc) +{ + return 8; +} + +int isa_l_exit(void *desc) +{ + isa_l_descriptor *isa_l_desc = NULL; + + isa_l_desc = (isa_l_descriptor*) desc; + + free(isa_l_desc); + + return 0; +} + + +void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle, + const char* gen_matrix_func_name) +{ + isa_l_descriptor *desc = NULL; + + desc = (isa_l_descriptor *)malloc(sizeof(isa_l_descriptor)); + if (NULL == desc) { + return NULL; + } + + desc->k = args->uargs.k; + desc->m = args->uargs.m; + if (args->uargs.w <= 0) + args->uargs.w = ISA_L_W; + desc->w = args->uargs.w; + + /* validate EC arguments */ + { + long long max_symbols = 1LL << desc->w; + if ((desc->k + desc->m) > max_symbols) { + goto error; + } + } + + /* + * ISO C forbids casting a void* to a function pointer. + * Since dlsym return returns a void*, we use this union to + * "transform" the void* to a function pointer. + */ + union { + ec_encode_data_func encodep; + ec_init_tables_func init_tablesp; + gf_gen_encoding_matrix_func gen_matrixp; + gf_invert_matrix_func invert_matrixp; + gf_mul_func gf_mulp; + void *vptr; + } func_handle = {.vptr = NULL}; + + /* fill in function addresses */ + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "ec_encode_data"); + desc->ec_encode_data = func_handle.encodep; + if (NULL == desc->ec_encode_data) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "ec_init_tables"); + desc->ec_init_tables = func_handle.init_tablesp; + if (NULL == desc->ec_init_tables) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, gen_matrix_func_name); + desc->gf_gen_encoding_matrix = func_handle.gen_matrixp; + if (NULL == desc->gf_gen_encoding_matrix) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "gf_invert_matrix"); + desc->gf_invert_matrix = func_handle.invert_matrixp; + if (NULL == desc->gf_invert_matrix) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "gf_mul"); + desc->gf_mul = func_handle.gf_mulp; + if (NULL == desc->gf_mul) { + goto error; + } + + desc->matrix = malloc(sizeof(char) * desc->k * (desc->k + desc->m)); + if (NULL == desc->matrix) { + goto error; + } + + /** + * Generate ISA-L encoding matrix + * Note that this is an abstract func from each backend + */ + desc->gf_gen_encoding_matrix(desc->matrix, desc->k + desc->m, desc->k); + + return desc; + +error: + free(desc); + + return NULL; +} diff --git a/src/backends/isa-l/isa_l_rs_cauchy.c b/src/backends/isa-l/isa_l_rs_cauchy.c new file mode 100644 index 0000000..11bac53 --- /dev/null +++ b/src/backends/isa-l/isa_l_rs_cauchy.c @@ -0,0 +1,86 @@ +/* + * Copyright 2014 Kevin M Greenan + * Copyright 2014 Tushar Gohad + * Copyright 2016 Kota Tsuyuzaki + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, this + * list of conditions and the following disclaimer in the documentation and/or + * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY + * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE + * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * isa_l_rs_cauchy backend implementation + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +#include +#include "erasurecode_backend.h" +#include "isa_l_common.h" + +#define ISA_L_RS_CAUCHY_LIB_MAJOR 2 +#define ISA_L_RS_CAUCHY_LIB_MINOR 14 +#define ISA_L_RS_CAUCHY_LIB_REV 1 +#define ISA_L_RS_CAUCHY_LIB_VER_STR "2.14" +#define ISA_L_RS_CAUCHY_LIB_NAME "isa_l_rs_cauchy" +#if defined(__MACOS__) || defined(__MACOSX__) || defined(__OSX__) || defined(__APPLE__) +#define ISA_L_RS_CAUCHY_SO_NAME "libisal.dylib" +#else +#define ISA_L_RS_CAUCHY_SO_NAME "libisal.so.2" +#endif + +/* Forward declarations */ +struct ec_backend_op_stubs isa_l_rs_cauchy_ops; +struct ec_backend isa_l_rs_cauchy; +struct ec_backend_common backend_isa_l_rs_cauchy; + +static void * isa_l_rs_cauchy_init(struct ec_backend_args *args, + void *backend_sohandle) +{ + return isa_l_common_init(args, backend_sohandle, "gf_gen_cauchy1_matrix"); +} + +/* + * For the time being, we only claim compatibility with versions that + * match exactly + */ +static bool isa_l_rs_cauchy_is_compatible_with(uint32_t version) { + return version == backend_isa_l_rs_cauchy.ec_backend_version; +} + +struct ec_backend_op_stubs isa_l_rs_cauchy_op_stubs = { + .INIT = isa_l_rs_cauchy_init, + .EXIT = isa_l_exit, + .ENCODE = isa_l_encode, + .DECODE = isa_l_decode, + .FRAGSNEEDED = isa_l_min_fragments, + .RECONSTRUCT = isa_l_reconstruct, + .ELEMENTSIZE = isa_l_element_size, + .ISCOMPATIBLEWITH = isa_l_rs_cauchy_is_compatible_with, +}; + +struct ec_backend_common backend_isa_l_rs_cauchy = { + .id = EC_BACKEND_ISA_L_RS_CAUCHY, + .name = ISA_L_RS_CAUCHY_LIB_NAME, + .soname = ISA_L_RS_CAUCHY_SO_NAME, + .soversion = ISA_L_RS_CAUCHY_LIB_VER_STR, + .ops = &isa_l_rs_cauchy_op_stubs, + .backend_metadata_size = 0, + .ec_backend_version = _VERSION(ISA_L_RS_CAUCHY_LIB_MAJOR, + ISA_L_RS_CAUCHY_LIB_MINOR, + ISA_L_RS_CAUCHY_LIB_REV), +}; diff --git a/src/backends/isa-l/isa_l_rs_vand.c b/src/backends/isa-l/isa_l_rs_vand.c index ebce441..a084beb 100644 --- a/src/backends/isa-l/isa_l_rs_vand.c +++ b/src/backends/isa-l/isa_l_rs_vand.c @@ -27,13 +27,9 @@ * vi: set noai tw=79 ts=4 sw=4: */ -#include #include - -#include "erasurecode.h" #include "erasurecode_backend.h" -#include "erasurecode_helpers.h" -#include "erasurecode_helpers_ext.h" +#include "isa_l_common.h" #define ISA_L_RS_VAND_LIB_MAJOR 2 #define ISA_L_RS_VAND_LIB_MINOR 13 @@ -51,543 +47,10 @@ struct ec_backend_op_stubs isa_l_rs_vand_ops; struct ec_backend isa_l_rs_vand; struct ec_backend_common backend_isa_l_rs_vand; -typedef void (*ec_encode_data_func)(int, int, int, unsigned char*, unsigned char **, unsigned char **); -typedef void (*ec_init_tables_func)(int, int, unsigned char*, unsigned char *); -typedef void (*gf_gen_rs_matrix_func)(unsigned char*, int, int); -typedef int (*gf_invert_matrix_func)(unsigned char*, unsigned char*, const int); -typedef unsigned char (*gf_mul_func)(unsigned char, unsigned char); - -struct isa_l_rs_vand_descriptor { - /* calls required for init */ - ec_init_tables_func ec_init_tables; - gf_gen_rs_matrix_func gf_gen_rs_matrix; - - /* calls required for encode */ - ec_encode_data_func ec_encode_data; - - /* calls required for decode and reconstruct */ - gf_invert_matrix_func gf_invert_matrix; - - /* multiplication function used by ISA-L */ - gf_mul_func gf_mul; - - /* fields needed to hold state */ - unsigned char *matrix; - int k; - int m; - int w; -}; - -static int isa_l_rs_vand_encode(void *desc, char **data, char **parity, - int blocksize) -{ - struct isa_l_rs_vand_descriptor *isa_l_desc = - (struct isa_l_rs_vand_descriptor*) desc; - - unsigned char *g_tbls = NULL; - int k = isa_l_desc->k; - int m = isa_l_desc->m; - - // Generate g_tbls from encode matrix encode_matrix - g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); - if (NULL == g_tbls) { - return -1; - } - - isa_l_desc->ec_init_tables(k, m, &isa_l_desc->matrix[k * k], g_tbls); - - /* FIXME - make ec_encode_data return a value */ - isa_l_desc->ec_encode_data(blocksize, k, m, g_tbls, (unsigned char**)data, - (unsigned char**)parity); - free(g_tbls); - return 0; -} - -static unsigned char* isa_l_get_decode_matrix(int k, int m, unsigned char *encode_matrix, int *missing_idxs) -{ - int i = 0, j = 0, l = 0; - int n = k + m; - unsigned char *decode_matrix = malloc(sizeof(unsigned char) * k * k); - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); - - while (i < k && l < n) { - if (((1 << l) & missing_bm) == 0) { - for (j = 0; j < k; j++) { - decode_matrix[(k * i) + j] = encode_matrix[(k * l) + j]; - } - i++; - } - l++; - } - - if (i != k) { - free(decode_matrix); - decode_matrix = NULL; - } - - return decode_matrix; -} - -static int get_num_missing_elements(int *missing_idxs) -{ - int i = 0; - - while (missing_idxs[i] > -1) { - i++; - } - - return i; -} - -static void mult_and_xor_row(unsigned char *to_row, - unsigned char *from_row, - unsigned char val, - int num_elems, - gf_mul_func gf_mul) -{ - int i; - - for (i = 0; i < num_elems; i++) { - to_row[i] ^= gf_mul(val, from_row[i]); - } -} - -/* - * TODO: Add in missing parity rows and adjust the inverse_rows to - * be used for parity. - */ -static unsigned char* get_inverse_rows(int k, - int m, - unsigned char *decode_inverse, - unsigned char* encode_matrix, - int *missing_idxs, - gf_mul_func gf_mul) -{ - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); - int num_missing_elements = get_num_missing_elements(missing_idxs); - unsigned char *inverse_rows = (unsigned char*)malloc(sizeof(unsigned - char*) * k * num_missing_elements); - int i, j, l = 0; - int n = k + m; - - if (NULL == inverse_rows) { - return NULL; - } - - memset(inverse_rows, 0, sizeof(unsigned - char*) * k * num_missing_elements); - - /* - * Fill in rows for missing data - */ - for (i = 0; i < k; i++) { - if ((1 << i) & missing_bm) { - for (j = 0; j < k; j++) { - inverse_rows[(l * k) + j] = decode_inverse[(i * k) + j]; - } - l++; - } - } - - /* - * Process missing parity. - * - * Start with an all-zero row. - * - * For each data element, if the data element is: - * - * Available: XOR the corresponding coefficient from the - * encoding matrix. - * - * Unavailable: multiply corresponding coefficient with - * the row that corresponds to the missing data in inverse_rows - * and XOR the resulting row with this row. - */ - for (i = k; i < n; i++) { - // Parity is missing - if ((1 << i) & missing_bm) { - int d_idx_avail = 0; - int d_idx_unavail = 0; - for (j = 0; j < k; j++) { - // This data is available, so we can use the encode matrix - if (((1 << j) & missing_bm) == 0) { - inverse_rows[(l * k) + d_idx_avail] ^= encode_matrix[(i * k) + j]; - d_idx_avail++; - } else { - mult_and_xor_row(&inverse_rows[l * k], - &inverse_rows[d_idx_unavail * k], - encode_matrix[(i * k) + j], - k, - gf_mul); - d_idx_unavail++; - } - } - l++; - } - } - return inverse_rows; -} - -static int isa_l_rs_vand_decode(void *desc, char **data, char **parity, - int *missing_idxs, int blocksize) -{ - struct isa_l_rs_vand_descriptor *isa_l_desc = - (struct isa_l_rs_vand_descriptor*)desc; - - unsigned char *g_tbls = NULL; - unsigned char *decode_matrix = NULL; - unsigned char *decode_inverse = NULL; - unsigned char *inverse_rows = NULL; - unsigned char **decoded_elements = NULL; - unsigned char **available_fragments = NULL; - int k = isa_l_desc->k; - int m = isa_l_desc->m; - int n = k + m; - int ret = -1; - int i, j; - - int num_missing_elements = get_num_missing_elements(missing_idxs); - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); - - decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs); - - if (NULL == decode_matrix) { - goto out; - } - - decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k); - - if (NULL == decode_inverse) { - goto out; - } - - int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k); - if (im_ret < 0) { - goto out; - } - - // Generate g_tbls from computed decode matrix (k x k) matrix - g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); - if (NULL == g_tbls) { - goto out; - } - - inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul); - - decoded_elements = (unsigned char**)malloc(sizeof(unsigned char*)*num_missing_elements); - if (NULL == decoded_elements) { - goto out; - } - - available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k); - if (NULL == available_fragments) { - goto out; - } - - j = 0; - for (i = 0; i < n; i++) { - if (missing_bm & (1 << i)) { - continue; - } - if (j == k) { - break; - } - if (i < k) { - available_fragments[j] = (unsigned char*)data[i]; - } else { - available_fragments[j] = (unsigned char*)parity[i-k]; - } - j++; - } - - // Grab pointers to memory needed for missing data fragments - j = 0; - for (i = 0; i < k; i++) { - if (missing_bm & (1 << i)) { - decoded_elements[j] = (unsigned char*)data[i]; - j++; - } - } - for (i = k; i < n; i++) { - if (missing_bm & (1 << i)) { - decoded_elements[j] = (unsigned char*)parity[i - k]; - j++; - } - } - - isa_l_desc->ec_init_tables(k, num_missing_elements, inverse_rows, g_tbls); - - isa_l_desc->ec_encode_data(blocksize, k, num_missing_elements, g_tbls, (unsigned char**)available_fragments, - (unsigned char**)decoded_elements); - - ret = 0; - -out: - free(g_tbls); - free(decode_matrix); - free(decode_inverse); - free(inverse_rows); - free(decoded_elements); - free(available_fragments); - - return ret; -} - -static int isa_l_rs_vand_reconstruct(void *desc, char **data, char **parity, - int *missing_idxs, int destination_idx, int blocksize) -{ - struct isa_l_rs_vand_descriptor *isa_l_desc = - (struct isa_l_rs_vand_descriptor*) desc; - unsigned char *g_tbls = NULL; - unsigned char *decode_matrix = NULL; - unsigned char *decode_inverse = NULL; - unsigned char *inverse_rows = NULL; - unsigned char *reconstruct_buf = NULL; - unsigned char **available_fragments = NULL; - int k = isa_l_desc->k; - int m = isa_l_desc->m; - int n = k + m; - int ret = -1; - int i, j; - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); - int inverse_row = -1; - - /** - * Get available elements and compute the inverse of their - * corresponding rows. - */ - decode_matrix = isa_l_get_decode_matrix(k, m, isa_l_desc->matrix, missing_idxs); - - if (NULL == decode_matrix) { - goto out; - } - - decode_inverse = (unsigned char*)malloc(sizeof(unsigned char) * k * k); - - if (NULL == decode_inverse) { - goto out; - } - - int im_ret = isa_l_desc->gf_invert_matrix(decode_matrix, decode_inverse, k); - if (im_ret < 0) { - goto out; - } - - /** - * Get the row needed to reconstruct - */ - inverse_rows = get_inverse_rows(k, m, decode_inverse, isa_l_desc->matrix, missing_idxs, isa_l_desc->gf_mul); - - // Generate g_tbls from computed decode matrix (k x k) matrix - g_tbls = malloc(sizeof(unsigned char) * (k * m * 32)); - if (NULL == g_tbls) { - goto out; - } - - /** - * Fill in the available elements - */ - available_fragments = (unsigned char**)malloc(sizeof(unsigned char*)*k); - if (NULL == available_fragments) { - goto out; - } - - j = 0; - for (i = 0; i < n; i++) { - if (missing_bm & (1 << i)) { - continue; - } - if (j == k) { - break; - } - if (i < k) { - available_fragments[j] = (unsigned char*)data[i]; - } else { - available_fragments[j] = (unsigned char*)parity[i-k]; - } - j++; - } - - /** - * Copy pointer of buffer to reconstruct - */ - j = 0; - for (i = 0; i < n; i++) { - if (missing_bm & (1 << i)) { - if (i == destination_idx) { - if (i < k) { - reconstruct_buf = (unsigned char*)data[i]; - } else { - reconstruct_buf = (unsigned char*)parity[i-k]; - } - inverse_row = j; - break; - } - j++; - } - } - - /** - * Do the reconstruction - */ - isa_l_desc->ec_init_tables(k, 1, &inverse_rows[inverse_row * k], g_tbls); - - isa_l_desc->ec_encode_data(blocksize, k, 1, g_tbls, (unsigned char**)available_fragments, - (unsigned char**)&reconstruct_buf); - - ret = 0; -out: - free(g_tbls); - free(decode_matrix); - free(decode_inverse); - free(inverse_rows); - free(available_fragments); - - return ret; -} - -static int isa_l_rs_vand_min_fragments(void *desc, int *missing_idxs, - int *fragments_to_exclude, int *fragments_needed) -{ - struct isa_l_rs_vand_descriptor *isa_l_desc = - (struct isa_l_rs_vand_descriptor*)desc; - - uint64_t exclude_bm = convert_list_to_bitmap(fragments_to_exclude); - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs) | exclude_bm; - int i; - int j = 0; - int ret = -1; - - for (i = 0; i < (isa_l_desc->k + isa_l_desc->m); i++) { - if (!(missing_bm & (1 << i))) { - fragments_needed[j] = i; - j++; - } - if (j == isa_l_desc->k) { - ret = 0; - fragments_needed[j] = -1; - break; - } - } - - return ret; -} - -#define ISA_L_W 8 static void * isa_l_rs_vand_init(struct ec_backend_args *args, void *backend_sohandle) { - struct isa_l_rs_vand_descriptor *desc = NULL; - - desc = (struct isa_l_rs_vand_descriptor *) - malloc(sizeof(struct isa_l_rs_vand_descriptor)); - if (NULL == desc) { - return NULL; - } - - desc->k = args->uargs.k; - desc->m = args->uargs.m; - if (args->uargs.w <= 0) - args->uargs.w = ISA_L_W; - desc->w = args->uargs.w; - - /* validate EC arguments */ - { - long long max_symbols = 1LL << desc->w; - if ((desc->k + desc->m) > max_symbols) { - goto error; - } - } - - /* - * ISO C forbids casting a void* to a function pointer. - * Since dlsym return returns a void*, we use this union to - * "transform" the void* to a function pointer. - */ - union { - ec_encode_data_func encodep; - ec_init_tables_func init_tablesp; - gf_gen_rs_matrix_func gen_matrixp; - gf_invert_matrix_func invert_matrixp; - gf_mul_func gf_mulp; - void *vptr; - } func_handle = {.vptr = NULL}; - - /* fill in function addresses */ - func_handle.vptr = NULL; - func_handle.vptr = dlsym(backend_sohandle, "ec_encode_data"); - desc->ec_encode_data = func_handle.encodep; - if (NULL == desc->ec_encode_data) { - goto error; - } - - func_handle.vptr = NULL; - func_handle.vptr = dlsym(backend_sohandle, "ec_init_tables"); - desc->ec_init_tables = func_handle.init_tablesp; - if (NULL == desc->ec_init_tables) { - goto error; - } - - func_handle.vptr = NULL; - func_handle.vptr = dlsym(backend_sohandle, "gf_gen_rs_matrix"); - desc->gf_gen_rs_matrix = func_handle.gen_matrixp; - if (NULL == desc->gf_gen_rs_matrix) { - goto error; - } - - func_handle.vptr = NULL; - func_handle.vptr = dlsym(backend_sohandle, "gf_invert_matrix"); - desc->gf_invert_matrix = func_handle.invert_matrixp; - if (NULL == desc->gf_invert_matrix) { - goto error; - } - - func_handle.vptr = NULL; - func_handle.vptr = dlsym(backend_sohandle, "gf_mul"); - desc->gf_mul = func_handle.gf_mulp; - if (NULL == desc->gf_mul) { - goto error; - } - - desc->matrix = malloc(sizeof(char) * desc->k * (desc->k + desc->m)); - if (NULL == desc->matrix) { - goto error; - } - - /** - * Generate ISA-L encoding matrix - */ - desc->gf_gen_rs_matrix(desc->matrix, desc->k + desc->m, desc->k); - - return desc; - -error: - free(desc); - - return NULL; -} - -/** - * Return the element-size, which is the number of bits stored - * on a given device, per codeword. This is always 8 in ISA-L - * - * Returns the size in bits! - */ -static int -isa_l_rs_vand_element_size(void* desc) -{ - return 8; -} - -static int isa_l_rs_vand_exit(void *desc) -{ - struct isa_l_rs_vand_descriptor *isa_l_desc = NULL; - - isa_l_desc = (struct isa_l_rs_vand_descriptor*) desc; - - free(isa_l_desc); - - return 0; + return isa_l_common_init(args, backend_sohandle, "gf_gen_rs_matrix"); } /* @@ -600,12 +63,12 @@ static bool isa_l_rs_vand_is_compatible_with(uint32_t version) { struct ec_backend_op_stubs isa_l_rs_vand_op_stubs = { .INIT = isa_l_rs_vand_init, - .EXIT = isa_l_rs_vand_exit, - .ENCODE = isa_l_rs_vand_encode, - .DECODE = isa_l_rs_vand_decode, - .FRAGSNEEDED = isa_l_rs_vand_min_fragments, - .RECONSTRUCT = isa_l_rs_vand_reconstruct, - .ELEMENTSIZE = isa_l_rs_vand_element_size, + .EXIT = isa_l_exit, + .ENCODE = isa_l_encode, + .DECODE = isa_l_decode, + .FRAGSNEEDED = isa_l_min_fragments, + .RECONSTRUCT = isa_l_reconstruct, + .ELEMENTSIZE = isa_l_element_size, .ISCOMPATIBLEWITH = isa_l_rs_vand_is_compatible_with, }; diff --git a/src/erasurecode.c b/src/erasurecode.c index d3b3cea..58c577a 100644 --- a/src/erasurecode.c +++ b/src/erasurecode.c @@ -49,6 +49,7 @@ extern struct ec_backend_common backend_jerasure_rs_cauchy; extern struct ec_backend_common backend_isa_l_rs_vand; extern struct ec_backend_common backend_shss; extern struct ec_backend_common backend_liberasurecode_rs_vand; +extern struct ec_backend_common backend_isa_l_rs_cauchy; ec_backend_t ec_backends_supported[] = { (ec_backend_t) &backend_null, @@ -58,6 +59,7 @@ ec_backend_t ec_backends_supported[] = { (ec_backend_t) &backend_isa_l_rs_vand, (ec_backend_t) &backend_shss, (ec_backend_t) &backend_liberasurecode_rs_vand, + (ec_backend_t) &backend_isa_l_rs_cauchy, NULL, }; -- cgit v1.2.1