Merge "ISA-L Cauchy support"

This commit is contained in:
Jenkins 2016-12-07 02:34:03 +00:00 committed by Gerrit Code Review
commit 4c8f8a65d2
8 changed files with 782 additions and 546 deletions

View File

@ -48,6 +48,7 @@ typedef enum {
EC_BACKEND_ISA_L_RS_VAND = 4,
EC_BACKEND_SHSS = 5,
EC_BACKEND_LIBERASURECODE_RS_VAND = 6,
EC_BACKEND_ISA_L_RS_CAUCHY = 7,
EC_BACKENDS_MAX,
} ec_backend_id_t;

View File

@ -0,0 +1,70 @@
/*
* 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:
*/
#define ISA_L_W 8
/* Forward declarations */
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_encoding_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);
typedef struct {
/* calls required for init */
ec_init_tables_func ec_init_tables;
gf_gen_encoding_matrix_func gf_gen_encoding_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;
} isa_l_descriptor;
int isa_l_encode(void *desc, char **data, char **parity, int blocksize);
int isa_l_decode(void *desc, char **data, char **parity, int *missing_idxs,
int blocksize);
int isa_l_reconstruct(void *desc, char **data, char **parity,
int *missing_idxs, int destination_idx, int blocksize);
int isa_l_min_fragments(void *desc, int *missing_idxs,
int *fragments_to_exclude, int *fragments_needed);
int isa_l_element_size(void* desc);
int isa_l_exit(void *desc);
void * isa_l_common_init(struct ec_backend_args *args, void *backend_sohandle,
const char* gen_matrix_func_name);

View File

@ -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

View File

@ -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 <stdio.h>
#include <stdlib.h>
#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;
}

View File

@ -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 <stdlib.h>
#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),
};

View File

@ -27,13 +27,9 @@
* vi: set noai tw=79 ts=4 sw=4:
*/
#include <stdio.h>
#include <stdlib.h>
#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,
};

View File

@ -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,
};

View File

@ -39,6 +39,7 @@
#define JERASURE_RS_VAND_BACKEND "jerasure_rs_vand"
#define JERASURE_RS_CAUCHY_BACKEND "jerasure_rs_cauchy"
#define ISA_L_RS_VAND_BACKEND "isa_l_rs_vand"
#define ISA_L_RS_CAUCHY_BACKEND "isa_l_rs_cauchy"
#define SHSS_BACKEND "shss"
#define RS_VAND_BACKEND "liberasurecode_rs_vand"
@ -281,6 +282,8 @@ char * get_name_from_backend_id(ec_backend_id_t be) {
return FLAT_XOR_HD_BACKEND;
case EC_BACKEND_ISA_L_RS_VAND:
return ISA_L_RS_VAND_BACKEND;
case EC_BACKEND_ISA_L_RS_CAUCHY:
return ISA_L_RS_CAUCHY_BACKEND;
case EC_BACKEND_SHSS:
return SHSS_BACKEND;
case EC_BACKEND_LIBERASURECODE_RS_VAND:
@ -316,6 +319,9 @@ struct ec_args *create_ec_args(ec_backend_id_t be, ec_checksum_type_t ct, int ba
case EC_BACKEND_ISA_L_RS_VAND:
backend_args_array = isa_l_test_args;
break;
case EC_BACKEND_ISA_L_RS_CAUCHY:
backend_args_array = isa_l_test_args;
break;
case EC_BACKEND_SHSS:
backend_args_array = shss_test_args;
break;
@ -1910,7 +1916,7 @@ struct testcase testcases[] = {
test_verify_stripe_metadata_frag_idx_invalid,
EC_BACKEND_JERASURE_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
// ISA-L tests
// ISA-L rs_vand tests
{"create_and_destroy_backend",
test_create_and_destroy_backend,
EC_BACKEND_ISA_L_RS_VAND, CHKSUM_NONE,
@ -1974,6 +1980,67 @@ struct testcase testcases[] = {
{"test_isa_l_decode_reconstruct_specific_error_case",
test_decode_reconstruct_specific_error_case,
EC_BACKENDS_MAX, 0, // note this test is using ISA-L in hard coded
.skip = false},
// ISA-L rs cauchy tests
{"create_and_destroy_backend",
test_create_and_destroy_backend,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"simple_encode_isa_l",
test_simple_encode_decode,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"decode_with_missing_data_isa_l",
test_decode_with_missing_data,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"decode_with_missing_multi_data_isa_l",
test_decode_with_missing_multi_data,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"decode_with_missing_multi_parity_isa_l",
test_decode_with_missing_multi_parity,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"test_decode_with_missing_multi_data_parity_isa_l",
test_decode_with_missing_multi_data_parity,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"simple_reconstruct_isa_l",
test_simple_reconstruct,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"test_fragments_needed_isa_l",
test_fragments_needed,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"test_get_fragment_metadata_isa_l",
test_get_fragment_metadata,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_NONE,
.skip = false},
{"test_verify_stripe_metadata",
test_verify_stripe_metadata,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
{"test_verify_stripe_metadata_libec_mismatch",
test_verify_stripe_metadata_libec_mismatch,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
{"test_verify_stripe_metadata_magic_mismatch",
test_verify_stripe_metadata_magic_mismatch,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
{"test_verify_stripe_metadata_be_id_mismatch",
test_verify_stripe_metadata_be_id_mismatch,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
{"test_verify_stripe_metadata_be_ver_mismatch",
test_verify_stripe_metadata_be_ver_mismatch,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
{"test_verify_stripe_metadata_frag_idx_invalid",
test_verify_stripe_metadata_frag_idx_invalid,
EC_BACKEND_ISA_L_RS_CAUCHY, CHKSUM_CRC32,
.skip = false},
// shss tests
{"create_and_destroy_backend",