diff options
| -rw-r--r-- | Makefile.am | 9 | ||||
| -rw-r--r-- | configure.ac | 3 | ||||
| -rw-r--r-- | include/erasurecode/erasurecode.h | 13 | ||||
| -rw-r--r-- | include/rs_vand/rs_galois.h | 45 | ||||
| -rw-r--r-- | include/rs_vand/rs_vand_internal.h | 44 | ||||
| -rw-r--r-- | src/Makefile.am | 14 | ||||
| -rw-r--r-- | src/backends/rs_vand/rs_vand.c | 312 | ||||
| -rw-r--r-- | src/builtin/rs_vand/Makefile.am | 10 | ||||
| -rw-r--r-- | src/builtin/rs_vand/rs_galois.c | 101 | ||||
| -rw-r--r-- | src/builtin/rs_vand/rs_vand_internal.c | 553 | ||||
| -rw-r--r-- | src/erasurecode.c | 2 | ||||
| -rw-r--r-- | test/Makefile.am | 12 | ||||
| -rw-r--r-- | test/builtin/rs_vand/rs_galois_test.c | 64 | ||||
| -rw-r--r-- | test/builtin/rs_vand/rs_vand_internal_test.c | 334 | ||||
| -rw-r--r-- | test/liberasurecode_test.c | 109 |
15 files changed, 1605 insertions, 20 deletions
diff --git a/Makefile.am b/Makefile.am index c18622e..24a3da6 100644 --- a/Makefile.am +++ b/Makefile.am @@ -12,7 +12,8 @@ AM_CPPFLAGS += -Werror -Wall AM_CFLAGS = -fPIC $(AM_CPPFLAGS) @GCOV_FLAGS@ -L/usr/local/lib -include_HEADERS = \ +thisincludedir = $(includedir)/liberasurecode +thisinclude_HEADERS = \ include/erasurecode/alg_sig.h \ include/erasurecode/erasurecode.h \ include/erasurecode/erasurecode_backend.h \ @@ -30,9 +31,9 @@ include_HEADERS = \ test: check $(eval SONAMES := $(shell find $(abs_top_builddir) -name '*.so')) $(eval SODIRS := $(dir $(SONAMES))) - $(eval LD_LIBRARY_PATH := LD_LIBRARY_PATH="$(subst / ,/:,$(SODIRS))") - $(eval DYLD_LIBRARY_PATH := DYLD_LIBRARY_PATH="$(subst / ,/:,$(SODIRS))") - $(eval DYLD_FALLBACK_LIBRARY_PATH := DYLD_FALLBACK_LIBRARY_PATH="$(subst / ,/:,$(SODIRS))") + $(eval LD_LIBRARY_PATH := LD_LIBRARY_PATH="$(LD_LIBRARY_PATH):$(subst / ,/:,$(SODIRS))") + $(eval DYLD_LIBRARY_PATH := DYLD_LIBRARY_PATH="$(DYLD_LIBRARY_PATH):$(subst / ,/:,$(SODIRS))") + $(eval DYLD_FALLBACK_LIBRARY_PATH := DYLD_FALLBACK_LIBRARY_PATH=$(DYLD_FALLBACK_LIBRARY_PATH):"$(subst / ,/:,$(SODIRS))") @$(LD_LIBRARY_PATH) $(DYLD_LIBRARY_PATH) $(DYLD_FALLBACK_LIBRARY_PATH) \ ./test/liberasurecode_test @$(LD_LIBRARY_PATH) $(DYLD_LIBRARY_PATH) $(DYLD_FALLBACK_LIBRARY_PATH) \ diff --git a/configure.ac b/configure.ac index 4a9923d..5029960 100644 --- a/configure.ac +++ b/configure.ac @@ -161,8 +161,10 @@ CFLAGS="$CFLAGS $SIMD_FLAGS" AC_CHECK_SIZEOF([long]) if test "$ac_cv_sizeof_long" -eq 8; then CFLAGS="$CFLAGS -DARCH_64" + AC_MSG_RESULT([Adding -DARCH_64 to CFLAGS]) fi + ################################################################################# # Doxygen Documentation ################################################################################# @@ -193,6 +195,7 @@ AM_CONDITIONAL(ENABLE_DOXYGEN, test x$enable_doxygen = xyes) AC_CONFIG_FILES([\ src/builtin/null_code/Makefile \ src/builtin/xor_codes/Makefile \ + src/builtin/rs_vand/Makefile \ src/Makefile \ test/Makefile \ doc/Makefile \ diff --git a/include/erasurecode/erasurecode.h b/include/erasurecode/erasurecode.h index 4604c2a..e40c164 100644 --- a/include/erasurecode/erasurecode.h +++ b/include/erasurecode/erasurecode.h @@ -40,12 +40,13 @@ extern "C" { /* =~=*=~==~=*=~==~=*=~= Supported EC backends =~=*=~==~=*=~==~=*=~==~=*=~== */ typedef enum { - EC_BACKEND_NULL = 0, - EC_BACKEND_JERASURE_RS_VAND = 1, - EC_BACKEND_JERASURE_RS_CAUCHY = 2, - EC_BACKEND_FLAT_XOR_HD = 3, - EC_BACKEND_ISA_L_RS_VAND = 4, - EC_BACKEND_SHSS = 5, + EC_BACKEND_NULL = 0, + EC_BACKEND_JERASURE_RS_VAND = 1, + EC_BACKEND_JERASURE_RS_CAUCHY = 2, + EC_BACKEND_FLAT_XOR_HD = 3, + EC_BACKEND_ISA_L_RS_VAND = 4, + EC_BACKEND_SHSS = 5, + EC_BACKEND_INTERNAL_RS_VAND = 6, EC_BACKENDS_MAX, } ec_backend_id_t; diff --git a/include/rs_vand/rs_galois.h b/include/rs_vand/rs_galois.h new file mode 100644 index 0000000..f17bbd3 --- /dev/null +++ b/include/rs_vand/rs_galois.h @@ -0,0 +1,45 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +// DISCLAIMER: This is a totally basic implementation of RS used if a user does not +// want to install one of the supported backends, such as Jerasure and ISA-L. +// This is not expected to perform as well as the other supported backends, +// but does not make any assumptions about the host system. Using a library +// like Jerasure with GF-Complete will give users the ability to tune to their +// architecture (Intel or ARM), CPU and memory (lots of options). + +// We are only implementing w=16 here. If you want to use something +// else, then use Jerasure with GF-Complete or ISA-L. +#define PRIM_POLY 0x1100b +#define FIELD_SIZE (1 << 16) +#define GROUP_SIZE (FIELD_SIZE - 1) + +void rs_galois_init_tables(); +void rs_galois_deinit_tables(); +int rs_galois_mult(int x, int y); +int rs_galois_div(int x, int y); +int rs_galois_inverse(int x); + diff --git a/include/rs_vand/rs_vand_internal.h b/include/rs_vand/rs_vand_internal.h new file mode 100644 index 0000000..c545333 --- /dev/null +++ b/include/rs_vand/rs_vand_internal.h @@ -0,0 +1,44 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +int* create_non_systematic_vand_matrix(int k, int m); +void free_systematic_matrix(int *matrix); +int* make_systematic_matrix(int k, int m); +int is_missing(int *missing_idxs, int index_to_check); +int gaussj_inversion(int *matrix, int *inverse, int n); +int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols); +int rs_galois_div(int x, int y); +int rs_galois_inverse(int x); +int rs_galois_mult(int x, int y); +void init_rs_vand(int k, int m); +void deinit_rs_vand(); +void print_matrix(int *matrix, int rows, int cols); +void square_matrix_multiply(int *m1, int *m2, int *prod, int n); +int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m); +int is_identity_matrix(int *matrix, int n); +int internal_rs_vand_encode(int *generator_matrix, char **data, char **parity, int k, int m, int blocksize); +int internal_rs_vand_decode(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int blocksize, int rebuild_parity); +int internal_rs_vand_reconstruct(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int destination_idx, int blocksize); diff --git a/src/Makefile.am b/src/Makefile.am index c80621b..9c90b30 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,10 +1,11 @@ -SUBDIRS = builtin/xor_codes builtin/null_code +SUBDIRS = builtin/xor_codes builtin/null_code builtin/rs_vand lib_LTLIBRARIES = liberasurecode.la INCLUDES = \ -I$(top_srcdir)/include/erasurecode \ -I$(top_srcdir)/include/xor_codes \ + -I$(top_srcdir)/include/rs_vand \ -I$(top_srcdir)/include/shss # liberasurecode params @@ -20,17 +21,14 @@ liberasurecode_la_SOURCES = \ backends/jerasure/jerasure_rs_vand.c \ backends/jerasure/jerasure_rs_cauchy.c \ backends/isa-l/isa_l_rs_vand.c \ + backends/rs_vand/rs_vand.c \ backends/shss/shss.c -# Install additional header files -liberasurecodeincludedir = $(includedir) -liberasurecodeinclude_HEADERS = \ - ../include/erasurecode/erasurecode.h \ - ../include/erasurecode/erasurecode_helpers.h - liberasurecode_la_CPPFLAGS = -Werror @GCOV_FLAGS@ liberasurecode_la_LIBADD = \ - builtin/xor_codes/libXorcode.la -lpthread -lm @GCOV_LDFLAGS@ + builtin/null_code/libnullcode.la -lpthread -lm @GCOV_LDFLAGS@ \ + builtin/xor_codes/libXorcode.la -lpthread -lm @GCOV_LDFLAGS@ \ + builtin/rs_vand/liberasurecode_rsvand.la -lpthread -lm @GCOV_LDFLAGS@ # Version format (C - A).(A).(R) for C:R:A input liberasurecode_la_LDFLAGS = -rpath '$(libdir)' -version-info 1:7:0 diff --git a/src/backends/rs_vand/rs_vand.c b/src/backends/rs_vand/rs_vand.c new file mode 100644 index 0000000..e39564f --- /dev/null +++ b/src/backends/rs_vand/rs_vand.c @@ -0,0 +1,312 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * 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" + +#define INTERNAL_RS_VAND_LIB_MAJOR 1 +#define INTERNAL_RS_VAND_LIB_MINOR 0 +#define INTERNAL_RS_VAND_LIB_REV 0 +#define INTERNAL_RS_VAND_LIB_VER_STR "1.0" +#define INTERNAL_RS_VAND_LIB_NAME "liberasurecode_rsvand" +#if defined(__MACOS__) || defined(__MACOSX__) || defined(__OSX__) || defined(__APPLE__) +#define INTERNAL_RS_VAND_SO_NAME "liberasurecode_rsvand.dylib" +#else +#define INTERNAL_RS_VAND_SO_NAME "liberasurecode_rsvand.so" +#endif + +/* Forward declarations */ +struct ec_backend_op_stubs internal_rs_vand_ops; +struct ec_backend internal_rs_vand; +struct ec_backend_common backend_internal_rs_vand; + +typedef int (*internal_rs_vand_encode_func)(int *, char **, char **, int, int, int); +typedef int (*internal_rs_vand_decode_func)(int *, char **, char **, int, int, int *, int, int); +typedef int (*internal_rs_vand_reconstruct_func)(int *, char **, char **, int, int, int *, int, int); +typedef void (*init_rs_vand_func)(int, int); +typedef void (*deinit_rs_vand_func)(); +typedef void (*free_systematic_matrix_func)(int *); +typedef int* (*make_systematic_matrix_func)(int, int); + + +struct internal_rs_vand_descriptor { + /* calls required for init */ + init_rs_vand_func init_rs_vand; + deinit_rs_vand_func deinit_rs_vand; + free_systematic_matrix_func free_systematic_matrix; + make_systematic_matrix_func make_systematic_matrix; + + /* calls required for encode */ + internal_rs_vand_encode_func internal_rs_vand_encode; + + /* calls required for decode */ + internal_rs_vand_decode_func internal_rs_vand_decode; + + /* calls required for reconstruct */ + internal_rs_vand_reconstruct_func internal_rs_vand_reconstruct; + + /* fields needed to hold state */ + int *matrix; + int k; + int m; + int w; +}; + +static int internal_rs_vand_encode(void *desc, char **data, char **parity, + int blocksize) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = + (struct internal_rs_vand_descriptor*) desc; + + /* FIXME: Should this return something? */ + rs_vand_desc->internal_rs_vand_encode(rs_vand_desc->matrix, data, parity, + rs_vand_desc->k, rs_vand_desc->m, blocksize); + return 0; +} + +static int internal_rs_vand_decode(void *desc, char **data, char **parity, + int *missing_idxs, int blocksize) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = + (struct internal_rs_vand_descriptor*) desc; + + /* FIXME: Should this return something? */ + rs_vand_desc->internal_rs_vand_decode(rs_vand_desc->matrix, data, parity, + rs_vand_desc->k, rs_vand_desc->m, missing_idxs, blocksize, 1); + + return 0; +} + +static int internal_rs_vand_reconstruct(void *desc, char **data, char **parity, + int *missing_idxs, int destination_idx, int blocksize) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = + (struct internal_rs_vand_descriptor*) desc; + + /* FIXME: Should this return something? */ + rs_vand_desc->internal_rs_vand_reconstruct(rs_vand_desc->matrix, data, parity, + rs_vand_desc->k, rs_vand_desc->m, missing_idxs, destination_idx, blocksize); + + return 0; +} + +static int internal_rs_vand_min_fragments(void *desc, int *missing_idxs, + int *fragments_to_exclude, int *fragments_needed) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = + (struct internal_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 < (rs_vand_desc->k + rs_vand_desc->m); i++) { + if (!(missing_bm & (1 << i))) { + fragments_needed[j] = i; + j++; + } + if (j == rs_vand_desc->k) { + ret = 0; + fragments_needed[j] = -1; + break; + } + } + + return ret; +} + +static void * internal_rs_vand_init(struct ec_backend_args *args, + void *backend_sohandle) +{ + struct internal_rs_vand_descriptor *desc = NULL; + + desc = (struct internal_rs_vand_descriptor *) + malloc(sizeof(struct internal_rs_vand_descriptor)); + if (NULL == desc) { + return NULL; + } + + desc->k = args->uargs.k; + desc->m = args->uargs.m; + + /* store w back in args so upper layer can get to it */ + args->uargs.w = desc->w = 16; // w is currently hard-coded at 16 + + // This check should not matter, since 64K is way higher + // than anyone should ever use + if ((desc->k + desc->m) > 65536) { + 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 { + init_rs_vand_func initp; + deinit_rs_vand_func deinitp; + free_systematic_matrix_func freematrixp; + make_systematic_matrix_func makematrixp; + internal_rs_vand_encode_func encodep; + internal_rs_vand_decode_func decodep; + internal_rs_vand_reconstruct_func reconstructp; + void *vptr; + } func_handle = {.vptr = NULL}; + + + /* fill in function addresses */ + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "init_rs_vand"); + desc->init_rs_vand = func_handle.initp; + if (NULL == desc->init_rs_vand) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "deinit_rs_vand"); + desc->deinit_rs_vand = func_handle.deinitp; + if (NULL == desc->deinit_rs_vand) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "make_systematic_matrix"); + desc->make_systematic_matrix = func_handle.makematrixp; + if (NULL == desc->make_systematic_matrix) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "free_systematic_matrix"); + desc->free_systematic_matrix = func_handle.freematrixp; + if (NULL == desc->free_systematic_matrix) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "internal_rs_vand_encode"); + desc->internal_rs_vand_encode = func_handle.encodep; + if (NULL == desc->internal_rs_vand_encode) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "internal_rs_vand_decode"); + desc->internal_rs_vand_decode = func_handle.decodep; + if (NULL == desc->internal_rs_vand_decode) { + goto error; + } + + func_handle.vptr = NULL; + func_handle.vptr = dlsym(backend_sohandle, "internal_rs_vand_reconstruct"); + desc->internal_rs_vand_reconstruct = func_handle.reconstructp; + if (NULL == desc->internal_rs_vand_reconstruct) { + goto error; + } + + desc->init_rs_vand(desc->k, desc->m); + + desc->matrix = desc->make_systematic_matrix(desc->k, desc->m); + + if (NULL == desc->matrix) { + goto error; + } + + return desc; + +error: + free(desc); + + return NULL; +} + +/** + * Return the element-size, which is the number of bits stored + * on a given device, per codeword. For Vandermonde, this is + * 'w'. For somthing like cauchy, this is packetsize * w. + * + * Returns the size in bits! + */ +static int +internal_rs_vand_element_size(void* desc) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = NULL; + + rs_vand_desc = (struct internal_rs_vand_descriptor*) desc; + + return rs_vand_desc->w; +} + +static int internal_rs_vand_exit(void *desc) +{ + struct internal_rs_vand_descriptor *rs_vand_desc = NULL; + + rs_vand_desc = (struct internal_rs_vand_descriptor*) desc; + + rs_vand_desc->free_systematic_matrix(rs_vand_desc->matrix); + rs_vand_desc->deinit_rs_vand(); + free(rs_vand_desc); + + return 0; +} + +/* + * For the time being, we only claim compatibility with versions that + * match exactly + */ +static bool internal_rs_vand_is_compatible_with(uint32_t version) { + return version == backend_internal_rs_vand.ec_backend_version; +} + +struct ec_backend_op_stubs internal_rs_vand_op_stubs = { + .INIT = internal_rs_vand_init, + .EXIT = internal_rs_vand_exit, + .ENCODE = internal_rs_vand_encode, + .DECODE = internal_rs_vand_decode, + .FRAGSNEEDED = internal_rs_vand_min_fragments, + .RECONSTRUCT = internal_rs_vand_reconstruct, + .ELEMENTSIZE = internal_rs_vand_element_size, + .ISCOMPATIBLEWITH = internal_rs_vand_is_compatible_with, +}; + +struct ec_backend_common backend_internal_rs_vand = { + .id = EC_BACKEND_INTERNAL_RS_VAND, + .name = INTERNAL_RS_VAND_LIB_NAME, + .soname = INTERNAL_RS_VAND_SO_NAME, + .soversion = INTERNAL_RS_VAND_LIB_VER_STR, + .ops = &internal_rs_vand_op_stubs, + .backend_metadata_size = 0, + .ec_backend_version = _VERSION(INTERNAL_RS_VAND_LIB_MAJOR, + INTERNAL_RS_VAND_LIB_MINOR, + INTERNAL_RS_VAND_LIB_REV), +}; diff --git a/src/builtin/rs_vand/Makefile.am b/src/builtin/rs_vand/Makefile.am new file mode 100644 index 0000000..de6f802 --- /dev/null +++ b/src/builtin/rs_vand/Makefile.am @@ -0,0 +1,10 @@ +lib_LTLIBRARIES = liberasurecode_rsvand.la + +# liberasurecode_rsvand params +liberasurecode_rsvand_la_SOURCES = rs_galois.c rs_vand_internal.c +liberasurecode_rsvand_la_CPPFLAGS = -I$(top_srcdir)/include/rs_vand @GCOV_FLAGS@ + +# Version format (C - A).(A).(R) for C:R:A input +liberasurecode_rsvand_la_LDFLAGS = @GCOV_LDFLAGS@ -rpath '$(libdir)' -version-info 1:1:0 + +MOSTLYCLEANFILES = *.gcda *.gcno *.gcov diff --git a/src/builtin/rs_vand/rs_galois.c b/src/builtin/rs_vand/rs_galois.c new file mode 100644 index 0000000..c709116 --- /dev/null +++ b/src/builtin/rs_vand/rs_galois.c @@ -0,0 +1,101 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +// DISCLAIMER: This is a totally basic implementation of RS used if a user does not +// want to install one of the supported backends, such as Jerasure and ISA-L. +// This is not expected to perform as well as the other supported backends, +// but does not make any assumptions about the host system. Using a library +// like Jerasure with GF-Complete will give users the ability to tune to their +// architecture (Intel or ARM), CPU and memory (lots of options). + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +// We are only implementing w=16 here. If you want to use something +// else, then use Jerasure with GF-Complete or ISA-L. +#define PRIM_POLY 0x1100b +#define FIELD_SIZE (1 << 16) +#define GROUP_SIZE (FIELD_SIZE - 1) + +int *log_table = NULL; +int *ilog_table = NULL; +int *ilog_table_begin = NULL; + +void rs_galois_init_tables() +{ + log_table = (int*)malloc(sizeof(int)*FIELD_SIZE); + ilog_table_begin = (int*)malloc(sizeof(int)*FIELD_SIZE*3); + int i = 0; + int x = 1; + + for (i = 0; i < GROUP_SIZE; i++) { + log_table[x] = i; + ilog_table_begin[i] = x; + ilog_table_begin[i + GROUP_SIZE] = x; + ilog_table_begin[i + (GROUP_SIZE*2)] = x; + x = x << 1; + if (x & FIELD_SIZE) { + x ^= PRIM_POLY; + } + } + ilog_table = &ilog_table_begin[GROUP_SIZE]; +} + +void rs_galois_deinit_tables() +{ + free(log_table); + free(ilog_table_begin); +} + +int rs_galois_mult(int x, int y) +{ + int sum; + if (x == 0 || y == 0) return 0; + // This can 'overflow' beyond 255. This is + // handled by positive overflow of ilog_table + sum = log_table[x] + log_table[y]; + + return ilog_table[sum]; +} + +int rs_galois_div(int x, int y) +{ + int diff; + if (x == 0) return 0; + if (y == 0) return -1; + + // This can 'underflow'. This is handled + // by negative overflow of ilog_table + diff = log_table[x] - log_table[y]; + + return ilog_table[diff]; +} + +int rs_galois_inverse(int x) +{ + return rs_galois_div(1, x); +} diff --git a/src/builtin/rs_vand/rs_vand_internal.c b/src/builtin/rs_vand/rs_vand_internal.c new file mode 100644 index 0000000..2770908 --- /dev/null +++ b/src/builtin/rs_vand/rs_vand_internal.c @@ -0,0 +1,553 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +// DISCLAIMER: This is a totally basic implementation of RS used if a user does not +// want to install one of the supported backends, such as Jerasure and ISA-L. +// This is not expected to perform as well as the other supported backends, +// but does not make any assumptions about the host system. Using a library +// like Jerasure with GF-Complete will give users the ability to tune to their +// architecture (Intel or ARM), CPU and memory (lots of options). + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdint.h> +#include <rs_galois.h> +#include <rs_vand_internal.h> + +#include <unistd.h> +#include <fcntl.h> + +void print_matrix(int *matrix, int rows, int cols) +{ + int i, j; + + printf("\n"); + for (i = 0; i < rows; i++) { + for (j = 0; j < cols; j++) { + printf("%d ", matrix[(i * cols) + j]); + } + printf("\n"); + } + printf("\n"); +} + +void square_matrix_multiply(int *m1, int *m2, int *prod, int n) +{ + int i, j, k; + + for (i = 0; i < n; i++) { + for (j = 0; j < n; j++) { + int p = 0; + for (k = 0; k < n; k++) { + p ^= rs_galois_mult(m1[(j*n)+k], m2[(k*n)+i]); + } + prod[(j*n)+i] = p; + } + } +} + +int is_identity_matrix(int *matrix, int n) +{ + int i, j; + + for (i = 0; i < n; i++) { + for (j = 0; j < n; j++) { + int val = matrix[(i*n) + j]; + if (i != j) { + if (val != 0) { + return 0; + } + } else { + if (val != 1) { + return 0; + } + } + } + } + return 1; +} + +int* get_matrix_row(int *matrix, int row_idx, int num_cols) +{ + return &matrix[row_idx * num_cols]; +} + +void copy_row(int *from_matrix, int *to_matrix, int from_row_idx, int to_row_idx, int num_cols) +{ + int *from_row = get_matrix_row(from_matrix, from_row_idx, num_cols); + int *to_row = get_matrix_row(to_matrix, to_row_idx, num_cols); + + memcpy(to_row, from_row, sizeof(int)*num_cols); +} + +int is_missing(int *missing_idxs, int index_to_check) +{ + int i = 0; + while (missing_idxs[i] > -1) { + if (missing_idxs[i] == index_to_check) { + return 1; + } + i++; + } + return 0; +} + +int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m) +{ + int i, j; + int n = k+m; + + for (i = 0, j = 0; i < n && j < k; i++) { + if (!is_missing(missing_idxs, i)) { + copy_row(gen_matrix, dec_matrix, i, j, k); + j++; + } + } + + return j == k; +} + + +void init_rs_vand(int k, int m) +{ + rs_galois_init_tables(); +} + +void deinit_rs_vand(int k, int m) +{ + rs_galois_deinit_tables(); +} + +int * create_non_systematic_vand_matrix(int k, int m) +{ + int rows = k + m; + int cols = k; + int i, j, acc; + int *matrix = (int*)malloc(sizeof(int)*rows*cols); + + if (NULL == matrix) return NULL; + + // First row is 1, 0, 0, ..., 0 + matrix[0] = 1; + for (i = 1; i < cols; i++) matrix[i] = 0; + + // Other rows are: + // i^0 (=1), i^1, i^2, ..., i^(cols-1) + for (i = 1; i < rows; i++) { + acc = 1; + for (j = 0; j < cols; j++) { + matrix[i * cols + j] = acc; + acc = rs_galois_mult(acc, i); + } + } + + return matrix; +} + +// Swap the entries of two rows in a matrix +void swap_matrix_rows(int *r1, int *r2, int num_cols) +{ + int i; + int tmp; + + for (i = 0; i < num_cols; i++) { + tmp = r1[i]; + r1[i] = r2[i]; + r2[i] = tmp; + } +} + +void col_mult(int *matrix, int elem, int col_idx, int num_rows, int num_cols) +{ + int i; + + for (i = 0; i < num_rows; i++) { + matrix[col_idx] = rs_galois_mult(matrix[col_idx], elem); + col_idx += num_cols; + } +} + +void row_mult(int *matrix, int elem, int row_idx, int num_rows, int num_cols) +{ + int i, to_row = row_idx * num_cols; + + for (i = 0; i < num_cols; i++) { + matrix[to_row] = rs_galois_mult(matrix[to_row], elem); + to_row++; + } +} + +void col_mult_and_add(int *matrix, int elem, int from_col, int to_col, int num_rows, int num_cols) +{ + int i; + + for (i = 0; i < num_rows; i++) { + matrix[to_col] = matrix[to_col] ^ rs_galois_mult(matrix[from_col], elem); + from_col += num_cols; + to_col += num_cols; + } +} + +void row_mult_and_add(int *matrix, int elem, int from_row, int to_row, int num_rows, int num_cols) +{ + int i; + from_row = from_row * num_cols; + to_row = to_row * num_cols; + for (i = 0; i < num_cols; i++) { + matrix[to_row] = matrix[to_row] ^ rs_galois_mult(matrix[from_row], elem); + to_row++; + from_row++; + } +} + +int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols) +{ + int i, row_idx; + + row_idx = (num_cols * row) + row; + for (i = row; i < num_rows; i++) { + if (matrix[row_idx] != 0) { + return i; + } + row_idx += num_cols; + } + + return -1; +} + +int * make_systematic_matrix(int k, int m) +{ + int rows = k + m; + int cols = k; + int i, j; + int *matrix = create_non_systematic_vand_matrix(k, m); + + if (NULL == matrix) return NULL; + + // The first row is already 1, 0, 0, ..., 0 + for (i = 1; i < cols; i++) { + int diag_idx = ((cols*i) + i); + // Get next row candidate, whose diagonal entry @ i,i != 0 + int next_row = get_non_zero_diagonal(matrix, i, rows, cols); + + // Swap candidate row with row i, if needed + if (next_row != i) { + swap_matrix_rows(&matrix[next_row*cols], &matrix[i*cols], cols); + } + + // Ensure the leading entry of row i is 1 by multiplying the + // column by the inverse of matrix[diag_idx] + if (matrix[diag_idx] != 1) { + col_mult(matrix, rs_galois_inverse(matrix[diag_idx]), i, rows, cols); + } + + // Zero-out all non-zero, non-diagonal entries in row i + // by multiplying the corresponding columns by col-i*<row_value> + for (j = 0; j < cols; j++) { + int row_val = matrix[(i * cols) + j]; + if (i != j && row_val != 0) { + col_mult_and_add(matrix, row_val, i, j, rows, cols); + } + } + } + + // Create all-XOR parity as first row of parity submatrix + for (i = 0; i < cols; i++) { + int row_val = matrix[(cols * cols) + i]; + if (row_val != 1) { + // Multiply the parity sub-column by the inverse of row_val + // We then implicitly multuply row i by the inverse of row_val + // (not explicitly necessary, since all other entries are 0) + col_mult(&matrix[cols*cols], rs_galois_inverse(row_val), i, rows - cols, cols); + } + } + + return matrix; +} + +void free_systematic_matrix(int *matrix) +{ + free(matrix); +} + +int gaussj_inversion(int *matrix, int *inverse, int n) +{ + int i, j; + + // Zero out the inverse matrix + memset(inverse, 0, sizeof(int)*n*n); + + // Make the inverse matrix an identity matrix + for (i = 0; i < n; i++) { + int diag_idx = ((n*i) + i); + inverse[diag_idx] = 1; + } + + for (i = 0; i < n; i++) { + int diag_idx = ((n*i) + i); + // Get next row candidate, whose diagonal entry @ i,i != 0 + int next_row = get_non_zero_diagonal(matrix, i, n, n); + + // Swap candidate row with row i, if needed + if (next_row != i) { + swap_matrix_rows(&matrix[next_row*n], &matrix[i*n], n); + swap_matrix_rows(&inverse[next_row*n], &inverse[i*n], n); + } + + // Make the leading entry a '1' + if (matrix[diag_idx] != 1) { + int leading_val_inv = rs_galois_inverse(matrix[diag_idx]); + row_mult(matrix, leading_val_inv, i, n, n); + row_mult(inverse, leading_val_inv, i, n, n); + } + + // Zero-out all other entries in column i + for (j = 0; j < n; j++) { + if (i != j) { + int val = matrix[(j * n) + i]; + row_mult_and_add(matrix, val, i, j, n, n); + row_mult_and_add(inverse, val, i, j, n, n); + } + } + } + return 0; +} + +void region_xor(char *from_buf, char *to_buf, int blocksize) +{ + int i; + + uint32_t *_from_buf = (uint32_t*)from_buf; + uint32_t *_to_buf = (uint32_t*)to_buf; + int adj_blocksize = blocksize / 4; + int trailing_bytes = blocksize % 4; + + for (i = 0; i < adj_blocksize; i++) { + _to_buf[i] = _to_buf[i] ^ _from_buf[i]; + } + + for (i = blocksize-trailing_bytes; i < blocksize; i++) { + to_buf[i] = to_buf[i] ^ from_buf[i]; + } +} + +void region_multiply(char *from_buf, char *to_buf, int mult, int xor, int blocksize) +{ + int i; + uint16_t *_from_buf = (uint16_t*)from_buf; + uint16_t *_to_buf = (uint16_t*)to_buf; + int adj_blocksize = blocksize / 2; + int trailing_bytes = blocksize % 2; + + if (xor) { + for (i = 0; i < adj_blocksize; i++) { + _to_buf[i] = _to_buf[i] ^ (uint16_t)rs_galois_mult(_from_buf[i], mult); + } + + if (trailing_bytes == 1) { + i = blocksize - 1; + to_buf[i] = to_buf[i] ^ (char)rs_galois_mult(from_buf[i], mult); + } + } else { + for (i = 0; i < adj_blocksize; i++) { + _to_buf[i] = (uint16_t)rs_galois_mult(_from_buf[i], mult); + } + + if (trailing_bytes == 1) { + i = blocksize - 1; + to_buf[i] = (char)rs_galois_mult(from_buf[i], mult); + } + } +} + +void region_dot_product(char **from_bufs, char *to_buf, int *matrix_row, int num_entries, int blocksize) +{ + int i; + + for (i = 0; i < num_entries; i++) { + int mult = matrix_row[i]; + if (mult == 1) { + region_xor(from_bufs[i], to_buf, blocksize); + } else { + region_multiply(from_bufs[i], to_buf, mult, 1, blocksize); + } + } +} + +int internal_rs_vand_encode(int *generator_matrix, char **data, char **parity, int k, int m, int blocksize) +{ + int i; + int n = k + m; + + for (i = k; i < n; i++) { + memset(parity[i - k], 0, blocksize); + region_dot_product(data, parity[i - k], &generator_matrix[(i * k)], k, blocksize); + } + + return 0; +} + +char **get_first_k_available(char **data, char **parity, int *missing, int k) +{ + int i, j; + char **first_k_available = (char**)malloc(sizeof(char*)*k); + + for (i = 0, j = 0; j < k; i++) { + if (!missing[i]) { + first_k_available[j] = i < k ? data[i] : parity[i - k]; + j++; + } + } + return first_k_available; +} + +int internal_rs_vand_decode(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int blocksize, int rebuild_parity) +{ + int *decoding_matrix = NULL; + int *inverse_decoding_matrix = NULL; + char **first_k_available = NULL; + int n = m + k; + int *_missing = (int*)malloc(sizeof(int)*n); + int i = 0; + int num_missing = 0; + + memset(_missing, 0, sizeof(int)*n); + + while (missing[num_missing] > -1) { + _missing[missing[num_missing]] = 1; + num_missing++; + } + + if (num_missing > m) { + free(_missing); + return -1; + } + + decoding_matrix = (int*)malloc(sizeof(int)*k*k); + inverse_decoding_matrix = (int*)malloc(sizeof(int)*k*k); + first_k_available = get_first_k_available(data, parity, _missing, k); + + create_decoding_matrix(generator_matrix, decoding_matrix, missing, k, m); + gaussj_inversion(decoding_matrix, inverse_decoding_matrix, k); + + // Rebuild data fragments + for (i = 0; i < k; i++) { + // Data fragment i is missing, recover it + if (_missing[i]) { + region_dot_product(first_k_available, data[i], &inverse_decoding_matrix[(i * k)], k, blocksize); + } + } + + // Rebuild parity fragments + if (rebuild_parity) { + for (i = k; i < n; i++) { + // Parity fragment i is missing, recover it + if (_missing[i]) { + region_dot_product(data, parity[i - k], &generator_matrix[(i * k)], k, blocksize); + } + } + } + + free(decoding_matrix); + free(inverse_decoding_matrix); + free(first_k_available); + free(_missing); + + return 0; +} + +int internal_rs_vand_reconstruct(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int destination_idx, int blocksize) +{ + int *decoding_matrix = NULL; + int *inverse_decoding_matrix = NULL; + char **first_k_available = NULL; + int *parity_row = NULL; + int n = k + m; + int *_missing = (int*)malloc(sizeof(int)*n); + int i, j; + int num_missing = 0; + + memset(_missing, 0, sizeof(int)*n); + + while (missing[num_missing] > -1) { + _missing[missing[num_missing]] = 1; + num_missing++; + } + + if (num_missing > m) { + free(_missing); + return -1; + } + + decoding_matrix = (int*)malloc(sizeof(int)*k*k); + inverse_decoding_matrix = (int*)malloc(sizeof(int)*k*k); + first_k_available = get_first_k_available(data, parity, _missing, k); + + create_decoding_matrix(generator_matrix, decoding_matrix, missing, k, m); + gaussj_inversion(decoding_matrix, inverse_decoding_matrix, k); + + // Rebuilding data is easy, just do a dot product using the inverted decoding + // matrix + if (destination_idx < k) { + region_dot_product(first_k_available, data[destination_idx], &inverse_decoding_matrix[(destination_idx * k)], k, blocksize); + } else { + // Rebuilding parity is a little tricker, we first copy the corresp. parity row + // and update it to reconstruct the parity with the first k available elements + + // Copy the parity entries for available data elements + // from the original generator matrix + parity_row = (int*)malloc(sizeof(int)*k); + memset(parity_row, 0, sizeof(int)*k); + j = 0; + for (i = 0; i < k; i++) { + if (!_missing[i]) { + parity_row[j] = generator_matrix[(destination_idx * k) + i]; + j++; + } + } + + i = 0; + // For each missing data element, we substitute in the row (equation) for the data element into the + // the parity row. + while (missing[i] > -1) { + if (missing[i] < k) { + for (j = 0; j < k; j++) { + parity_row[j] ^= rs_galois_mult(generator_matrix[(destination_idx * k) + missing[i]], inverse_decoding_matrix[(missing[i] * k) + j]); + } + } + i++; + } + region_dot_product(first_k_available, parity[destination_idx - k], parity_row, k, blocksize); + } + + free(decoding_matrix); + free(inverse_decoding_matrix); + free(first_k_available); + free(_missing); + + return 0; +} diff --git a/src/erasurecode.c b/src/erasurecode.c index d9a868c..3c9e123 100644 --- a/src/erasurecode.c +++ b/src/erasurecode.c @@ -44,6 +44,7 @@ extern struct ec_backend_common backend_jerasure_rs_vand; 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_internal_rs_vand; ec_backend_t ec_backends_supported[] = { (ec_backend_t) &backend_null, @@ -52,6 +53,7 @@ ec_backend_t ec_backends_supported[] = { (ec_backend_t) &backend_flat_xor_hd, (ec_backend_t) &backend_isa_l_rs_vand, (ec_backend_t) &backend_shss, + (ec_backend_t) &backend_internal_rs_vand, NULL, }; diff --git a/test/Makefile.am b/test/Makefile.am index f625ec9..e45d400 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -1,5 +1,5 @@ noinst_HEADERS = builtin/xor_codes/test_xor_hd_code.h -noinst_PROGRAMS = test_xor_hd_code alg_sig_test liberasurecode_test libec_slap +noinst_PROGRAMS = test_xor_hd_code alg_sig_test liberasurecode_test libec_slap rs_galois_test rs_vand_internal_test test_xor_hd_code_SOURCES = \ builtin/xor_codes/test_xor_hd_code.c \ @@ -23,6 +23,16 @@ libec_slap_CPPFLAGS = -I. -I$(top_srcdir)/include -I$(top_srcdir)/include/erasur libec_slap_LDFLAGS = @GCOV_LDFLAGS@ $(top_srcdir)/src/liberasurecode.la -ldl -lpthread check_PROGRAMS += libec_slap +rs_galois_test_SOURCES = builtin/rs_vand/rs_galois_test.c +rs_galois_test_CPPFLAGS = -I$(top_srcdir)/include -I$(top_srcdir)/include/rs_vand @GCOV_FLAGS@ +rs_galois_test_LDFLAGS = @GCOV_LDFLAGS@ -static-libtool-libs $(top_srcdir)/src/builtin/rs_vand/liberasurecode_rsvand.la +check_PROGRAMS += rs_galois_test + +rs_vand_internal_test_SOURCES = builtin/rs_vand/rs_vand_internal_test.c +rs_vand_internal_test_CPPFLAGS = -I$(top_srcdir)/include -I$(top_srcdir)/include/rs_vand @GCOV_FLAGS@ +rs_vand_internal_test_LDFLAGS = @GCOV_LDFLAGS@ -static-libtool-libs $(top_srcdir)/src/builtin/rs_vand/liberasurecode_rsvand.la +check_PROGRAMS += rs_vand_internal_test + MOSTLYCLEANFILES = *.gcda *.gcno *.gcov \ ./builtin/xor_codes/*.gcda ./builtin/xor_codes/*.gcno ./builtin/xor_codes/*.gcov \ ./utils/chksum/*.gcda ./utils/chksum/*.gcno ./utils/chksum/*.gcov diff --git a/test/builtin/rs_vand/rs_galois_test.c b/test/builtin/rs_vand/rs_galois_test.c new file mode 100644 index 0000000..b727755 --- /dev/null +++ b/test/builtin/rs_vand/rs_galois_test.c @@ -0,0 +1,64 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <rs_galois.h> + +int test_inverse() +{ + int *uniq = (int*)malloc(sizeof(int)*FIELD_SIZE); + int i = 0; + + memset(uniq, 0, sizeof(int)*FIELD_SIZE); + + rs_galois_init_tables(); + + for (i = 1; i < FIELD_SIZE; i++) { + if (uniq[i] != 0) { + fprintf(stderr, "Duplicate %d: %d , %d \n", i, uniq[i], rs_galois_inverse(i)); + return 1; + } + uniq[i] = rs_galois_inverse(i); + int one = rs_galois_mult(rs_galois_inverse(i), i); + if (one != 1) { + fprintf(stderr, "%d is not the inverse of %d = %d\n", rs_galois_inverse(i), i, one); + return 1; + } + } + return 0; +} + +int main(int argc, char **argv) +{ + int ret = 0; + if (test_inverse() != 0) { + fprintf(stderr, "test_inverse() failed\n"); + ret = 1; + } + return ret; +} diff --git a/test/builtin/rs_vand/rs_vand_internal_test.c b/test/builtin/rs_vand/rs_vand_internal_test.c new file mode 100644 index 0000000..139c91f --- /dev/null +++ b/test/builtin/rs_vand/rs_vand_internal_test.c @@ -0,0 +1,334 @@ +/* + * Copyright 2015 Kevin M Greenan + * + * 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. + * + * vi: set noai tw=79 ts=4 sw=4: + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <fcntl.h> +#include <time.h> +#include <rs_vand_internal.h> + +int test_make_systematic_matrix(int k, int m) +{ + int *matrix = make_systematic_matrix(k, m); + int is_identity = is_identity_matrix(matrix, k); + + if (!is_identity) { + printf("Generating systematic matrix did not work!\n"); + printf("Generator matrix: \n\n"); + print_matrix(matrix, m+k, k); + } + + free_systematic_matrix(matrix); + + return is_identity; +} + +void dump_buffer(char *buf, int size, const char* filename) +{ + int fd = open(filename, O_RDWR | O_CREAT); + write(fd, buf, size); + close(fd); +} + +int test_invert_systematic_matrix(int k, int m, int num_missing) +{ + int *inverse = (int*)malloc(sizeof(int)*k*k); + int *prod = (int*)malloc(sizeof(int)*k*k); + int *missing = (int*)malloc(sizeof(int)*(num_missing+1)); + int *matrix = make_systematic_matrix(k, m); + int *decoding_matrix = (int*)malloc(sizeof(int)*k*k); + int *decoding_matrix_cpy = (int*)malloc(sizeof(int)*k*k); + int n = k+m; + int i, res; + + srand((unsigned int)time(0)); + + for (i = 0;i < num_missing+1; i++) { + missing[i] = -1; + } + + for (i = 0;i < num_missing; i++) { + int idx = rand() % n; + while (is_missing(missing, idx)) { + idx = rand() % n; + } + missing[i] = idx; + } + + create_decoding_matrix(matrix, decoding_matrix, missing, k, m); + create_decoding_matrix(matrix, decoding_matrix_cpy, missing, k, m); + + gaussj_inversion(decoding_matrix, inverse, k); + + square_matrix_multiply(decoding_matrix_cpy, inverse, prod, k); + + res = is_identity_matrix(prod, k); + + if (!res) { + printf("Inverting decoding matrix did not work!\n"); + printf("Generator matrix: \n\n"); + print_matrix(matrix, n, k); + printf("Decoding matrix: \n\n"); + print_matrix(decoding_matrix_cpy, k, k); + printf("Inverse Decoding matrix: \n\n"); + print_matrix(inverse, k, k); + printf("Missing: \n\n"); + print_matrix(missing, 1, num_missing); + } + + free(inverse); + free(prod); + free(missing); + free(decoding_matrix); + free(decoding_matrix_cpy); + free_systematic_matrix(matrix); + + return res; +} + +char* gen_random_buffer(int blocksize) +{ + int i; + char *buf = (char*)malloc(blocksize); + + for (i = 0; i < blocksize; i++) { + buf[i] = (char)(rand() % 255); + } + + return buf; +} + +int test_encode_decode(int k, int m, int num_missing, int blocksize) +{ + char **data = (char**)malloc(sizeof(char*)*k); + char **parity = (char**)malloc(sizeof(char*)*m); + char **missing_bufs = (char**)malloc(sizeof(char*)*num_missing); + int *missing = (int*)malloc(sizeof(int)*(num_missing+1)); + int *matrix = make_systematic_matrix(k, m); + int n = k + m; + int i; + int ret = 1; + + srand((unsigned int)time(0)); + + for (i = 0; i < k; i++) { + data[i] = gen_random_buffer(blocksize); + } + + for (i = 0; i < m; i++) { + parity[i] = (char*)malloc(blocksize); + } + + for (i = 0;i < num_missing+1; i++) { + missing[i] = -1; + } + + // Encode + internal_rs_vand_encode(matrix, data, parity, k, m, blocksize); + + // Copy data and parity + for (i = 0;i < num_missing; i++) { + int idx = rand() % n; + while (is_missing(missing, idx)) { + idx = rand() % n; + } + missing_bufs[i] = (char*)malloc(blocksize); + memcpy(missing_bufs[i], idx < k ? data[idx] : parity[idx - k], blocksize); + missing[i] = idx; + } + + // Zero missing bufs + for (i = 0;i < num_missing; i++) { + if (missing[i] < k) { + memset(data[missing[i]], 0, blocksize); + } else { + memset(parity[missing[i] - k], 0, blocksize); + } + } + + // Decode and check + internal_rs_vand_decode(matrix, data, parity, k, m, missing, blocksize, 1); + + for (i = 0; i < num_missing; i++) { + int idx = missing[i]; + if (idx < k) { + if (memcmp(data[idx], missing_bufs[i], blocksize)) { + dump_buffer(data[idx], blocksize, "decoded_buffer"); + dump_buffer(missing_bufs[i], blocksize, "orig_buffer"); + ret = 0; + } + } else if (memcmp(parity[idx - k], missing_bufs[i], blocksize)) { + ret = 0; + } + } + + for (i = 0; i < k; i++) { + free(data[i]); + } + free(data); + for (i = 0; i < m; i++) { + free(parity[i]); + } + free(parity); + for (i = 0; i < num_missing; i++) { + free(missing_bufs[i]); + } + free(missing_bufs); + free(missing); + free(matrix); + + return ret; +} + +int test_reconstruct(int k, int m, int num_missing, int blocksize) +{ + char **data = (char**)malloc(sizeof(char*)*k); + char **parity = (char**)malloc(sizeof(char*)*m); + char **missing_bufs = (char**)malloc(sizeof(char*)*num_missing); + int *missing = (int*)malloc(sizeof(int)*(num_missing+1)); + int *matrix = make_systematic_matrix(k, m); + int destination_idx; + int n = k + m; + int i; + int ret = 1; + + srand((unsigned int)time(0)); + + for (i = 0; i < k; i++) { + data[i] = gen_random_buffer(blocksize); + } + + for (i = 0; i < m; i++) { + parity[i] = (char*)malloc(blocksize); + } + + for (i = 0;i < num_missing+1; i++) { + missing[i] = -1; + } + + // Encode + internal_rs_vand_encode(matrix, data, parity, k, m, blocksize); + + // Copy data and parity + for (i = 0; i < num_missing; i++) { + int idx = rand() % n; + while (is_missing(missing, idx)) { + idx = rand() % n; + } + missing_bufs[i] = (char*)malloc(blocksize); + memcpy(missing_bufs[i], idx < k ? data[idx] : parity[idx - k], blocksize); + missing[i] = idx; + if (i == 0) { + destination_idx = missing[i]; + } + } + + // Zero missing bufs + for (i = 0;i < num_missing; i++) { + if (missing[i] < k) { + memset(data[missing[i]], 0, blocksize); + } else { + memset(parity[missing[i] - k], 0, blocksize); + } + } + + // Reconstruct and check destination buffer + internal_rs_vand_reconstruct(matrix, data, parity, k, m, missing, destination_idx, blocksize); + + // The original copy of the destination buffer is in the 0th buffer (see above) + if (destination_idx < k) { + if (memcmp(data[destination_idx], missing_bufs[0], blocksize)) { + dump_buffer(data[destination_idx], blocksize, "decoded_buffer"); + dump_buffer(missing_bufs[0], blocksize, "orig_buffer"); + ret = 0; + } + } else if (memcmp(parity[destination_idx - k], missing_bufs[0], blocksize)) { + ret = 0; + } + + for (i = 0; i < k; i++) { + free(data[i]); + } + free(data); + for (i = 0; i < m; i++) { + free(parity[i]); + } + free(parity); + for (i = 0; i < num_missing; i++) { + free(missing_bufs[i]); + } + free(missing_bufs); + free(missing); + free(matrix); + + return ret; +} + +int matrix_dimensions[][2] = { {12, 6}, {12, 3}, {12, 2}, {12, 1}, {5, 3}, {5, 2}, {5, 1}, {1, 1}, {-1, -1} }; + +int main() +{ + int i = 0; + int blocksize = 4096; + + while (matrix_dimensions[i][0] >= 0) { + int k = matrix_dimensions[i][0], m = matrix_dimensions[i][1]; + + init_rs_vand(k, m); + + int make_systematic_res = test_make_systematic_matrix(k, m); + if (!make_systematic_res) { + fprintf(stderr, "Error running make systematic matrix for k=%d, m=%d\n", k, m); + return 1; + } + + int invert_res = test_invert_systematic_matrix(k, m, m); + if (!invert_res) { + fprintf(stderr, "Error running inversion test for k=%d, m=%d\n", k, m); + return 1; + } + + int enc_dec_res = test_encode_decode(k, m, m, blocksize); + if (!enc_dec_res) { + fprintf(stderr, "Error running encode/decode test for k=%d, m=%d, bs=%d\n", k, m, blocksize); + return 1; + } + + int reconstr_res = test_reconstruct(k, m, m, blocksize); + if (!reconstr_res) { + fprintf(stderr, "Error running reconstruction test for k=%d, m=%d, bs=%d\n", k, m, blocksize); + return 1; + } + + + deinit_rs_vand(k, m); + i++; + } + + return 0; +} diff --git a/test/liberasurecode_test.c b/test/liberasurecode_test.c index c9d67af..9f1ad9d 100644 --- a/test/liberasurecode_test.c +++ b/test/liberasurecode_test.c @@ -39,6 +39,7 @@ #define JERASURE_RS_CAUCHY_BACKEND "jerasure_rs_cauchy" #define ISA_L_RS_VAND_BACKEND "isa_l_rs_vand" #define SHSS_BACKEND "shss" +#define RS_VAND_BACKEND "rs_vand" typedef void (*TEST_FUNC)(); @@ -180,12 +181,52 @@ struct ec_args shss_args = { struct ec_args *shss_test_args[] = { &shss_args, NULL }; +struct ec_args internal_rs_vand_args = { + .k = 10, + .m = 4, + .w = 16, + .hd = 5, + .ct = CHKSUM_NONE, +}; + +struct ec_args internal_rs_vand_44_args = { + .k = 4, + .m = 4, + .w = 16, + .hd = 5, + .ct = CHKSUM_NONE, +}; + +struct ec_args internal_rs_vand_48_args = { + .k = 4, + .m = 8, + .w = 16, + .hd = 9, + .ct = CHKSUM_NONE, +}; + +struct ec_args internal_rs_vand_1010_args = { + .k = 10, + .m = 10, + .w = 16, + .hd = 11, + .ct = CHKSUM_NONE, +}; + +struct ec_args *internal_rs_vand_test_args[] = { &internal_rs_vand_args, + &internal_rs_vand_44_args, + &internal_rs_vand_1010_args, + &internal_rs_vand_48_args, + NULL }; + struct ec_args **all_backend_tests[] = { null_test_args, flat_xor_test_args, jerasure_rs_vand_test_args, jerasure_rs_cauchy_test_args, isa_l_test_args, - shss_test_args , NULL}; + shss_test_args, + internal_rs_vand_test_args, + NULL}; int num_backends() { @@ -237,6 +278,8 @@ char * get_name_from_backend_id(ec_backend_id_t be) { return ISA_L_RS_VAND_BACKEND; case EC_BACKEND_SHSS: return SHSS_BACKEND; + case EC_BACKEND_INTERNAL_RS_VAND: + return RS_VAND_BACKEND; default: return "UNKNOWN"; } @@ -259,6 +302,9 @@ struct ec_args *create_ec_args(ec_backend_id_t be, ec_checksum_type_t ct, int ba case EC_BACKEND_JERASURE_RS_CAUCHY: backend_args_array = jerasure_rs_cauchy_test_args; break; + case EC_BACKEND_INTERNAL_RS_VAND: + backend_args_array = internal_rs_vand_test_args; + break; case EC_BACKEND_FLAT_XOR_HD: backend_args_array = flat_xor_test_args; break; @@ -1782,6 +1828,67 @@ struct testcase testcases[] = { test_verify_stripe_metadata_be_ver_mismatch, EC_BACKEND_SHSS, CHKSUM_CRC32, .skip = false}, + // Internal RS Vand backend tests + {"create_and_destroy_backend", + test_create_and_destroy_backend, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"simple_encode_internal_rs_vand", + test_simple_encode_decode, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"decode_with_missing_data_internal_rs_vand", + test_decode_with_missing_data, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"decode_with_missing_multi_data_internal_rs_vand", + test_decode_with_missing_multi_data, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"decode_with_missing_multi_parity_internal_rs_vand", + test_decode_with_missing_multi_parity, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"test_decode_with_missing_multi_data_parity_internal_rs_vand", + test_decode_with_missing_multi_data_parity, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"simple_reconstruct_internal_rs_vand", + test_simple_reconstruct, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"test_fragments_needed_internal_rs_vand", + test_fragments_needed, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"test_get_fragment_metadata_internal_rs_vand", + test_get_fragment_metadata, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_NONE, + .skip = false}, + {"test_get_fragment_metadata_internal_rs_vand_crc32", + test_get_fragment_metadata, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, + {"test_verify_stripe_metadata", + test_verify_stripe_metadata, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, + {"test_verify_stripe_metadata_libec_mismatch", + test_verify_stripe_metadata_libec_mismatch, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, + {"test_verify_stripe_metadata_magic_mismatch", + test_verify_stripe_metadata_magic_mismatch, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, + {"test_verify_stripe_metadata_be_id_mismatch", + test_verify_stripe_metadata_be_id_mismatch, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, + {"test_verify_stripe_metadata_be_ver_mismatch", + test_verify_stripe_metadata_be_ver_mismatch, + EC_BACKEND_INTERNAL_RS_VAND, CHKSUM_CRC32, + .skip = false}, { NULL, NULL, 0, 0, false }, }; |