diff options
author | Kevin Greenan <kmgreen2@gmail.com> | 2014-08-21 12:15:32 -0700 |
---|---|---|
committer | Kevin Greenan <kmgreen2@gmail.com> | 2014-08-21 13:05:59 -0700 |
commit | c9af505400382a3117e2249acf308a08e97d48a9 (patch) | |
tree | ef1975921dbf311c600a535ed611c6a4abb1d464 | |
parent | c48eae68e3a9f0ca79e8a4bc1ff837f1d6db5b3a (diff) | |
download | liberasurecode-c9af505400382a3117e2249acf308a08e97d48a9.tar.gz |
Backend changes needed to honor "excluded fragments".
-rw-r--r-- | include/erasurecode/erasurecode_backend.h | 2 | ||||
-rw-r--r-- | include/xor_codes/xor_code.h | 4 | ||||
-rw-r--r-- | src/backends/jerasure/jerasure_rs_cauchy.c | 5 | ||||
-rw-r--r-- | src/backends/jerasure/jerasure_rs_vand.c | 5 | ||||
-rw-r--r-- | src/backends/null/null.c | 4 | ||||
-rw-r--r-- | src/backends/xor/flat_xor_hd.c | 7 | ||||
-rw-r--r-- | src/builtin/xor_codes/xor_hd_code.c | 309 | ||||
-rw-r--r-- | src/erasurecode.c | 4 | ||||
-rw-r--r-- | test/builtin/xor_codes/test_xor_hd_code.c | 5 |
9 files changed, 213 insertions, 132 deletions
diff --git a/include/erasurecode/erasurecode_backend.h b/include/erasurecode/erasurecode_backend.h index 2d30371..a6e4440 100644 --- a/include/erasurecode/erasurecode_backend.h +++ b/include/erasurecode/erasurecode_backend.h @@ -83,7 +83,7 @@ struct ec_backend_op_stubs { int (*DECODE)(void *desc, char **data, char **parity, int *missing_idxs, int blocksize); int (*FRAGSNEEDED)(void *desc, - int *missing_idxs, int *fragments_needed); + int *missing_idxs, int * fragments_to_exclude, int *fragments_needed); int (*RECONSTRUCT)(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize); diff --git a/include/xor_codes/xor_code.h b/include/xor_codes/xor_code.h index 912dcde..8a4a528 100644 --- a/include/xor_codes/xor_code.h +++ b/include/xor_codes/xor_code.h @@ -58,7 +58,7 @@ typedef struct xor_code_s int *data_bms; int (*decode)(struct xor_code_s *code_desc, char **data, char **parity, int *missing_idxs, int blocksize, int decode_parity); void (*encode)(struct xor_code_s *code_desc, char **data, char **parity, int blocksize); - int (*fragments_needed)(struct xor_code_s *code_desc, int *missing_idxs, int *fragments_needed); + int (*fragments_needed)(struct xor_code_s *code_desc, int *missing_idxs, int *fragments_to_exclude, int *fragments_needed); } xor_code_t; int is_data_in_parity(int data_idx, unsigned int parity_bm); @@ -91,7 +91,7 @@ int index_of_connected_parity(xor_code_t *code_desc, int data_index, int *missin void remove_from_missing_list(int element, int *missing_list); -int* get_symbols_needed(xor_code_t *code_desc, int *missing_list); +int* get_symbols_needed(xor_code_t *code_desc, int *missing_list, int *fragments_to_exclude); void xor_reconstruct_one(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int index_to_reconstruct, int blocksize); diff --git a/src/backends/jerasure/jerasure_rs_cauchy.c b/src/backends/jerasure/jerasure_rs_cauchy.c index b06ff6d..af37f76 100644 --- a/src/backends/jerasure/jerasure_rs_cauchy.c +++ b/src/backends/jerasure/jerasure_rs_cauchy.c @@ -160,11 +160,12 @@ out: * */ static int jerasure_rs_cauchy_min_fragments(void *desc, int *missing_idxs, - int *fragments_needed) + int *fragments_to_exclude, int *fragments_needed) { struct jerasure_rs_cauchy_descriptor *jerasure_desc = (struct jerasure_rs_cauchy_descriptor*)desc; - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + 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; diff --git a/src/backends/jerasure/jerasure_rs_vand.c b/src/backends/jerasure/jerasure_rs_vand.c index 970d205..05cbfda 100644 --- a/src/backends/jerasure/jerasure_rs_vand.c +++ b/src/backends/jerasure/jerasure_rs_vand.c @@ -139,12 +139,13 @@ out: } static int jerasure_rs_vand_min_fragments(void *desc, int *missing_idxs, - int *fragments_needed) + int *fragments_to_exclude, int *fragments_needed) { struct jerasure_rs_vand_descriptor *jerasure_desc = (struct jerasure_rs_vand_descriptor*)desc; - uint64_t missing_bm = convert_list_to_bitmap(missing_idxs); + 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; diff --git a/src/backends/null/null.c b/src/backends/null/null.c index b04cd99..23e8901 100644 --- a/src/backends/null/null.c +++ b/src/backends/null/null.c @@ -54,7 +54,7 @@ struct null_descriptor { /* set of fragments needed to reconstruct at a minimum */ int (*null_code_fragments_needed)(void *code_desc, int *missing_idxs, - int *fragments_needed); + int *fragments_to_exclude, int *fragments_needed); /* fields needed to hold state */ int *matrix; @@ -94,7 +94,7 @@ static int null_reconstruct(void *desc, char **data, char **parity, } static int null_min_fragments(void *desc, int *missing_idxs, - int *fragments_needed) + int *fragments_to_exclude, int *fragments_needed) { struct null_descriptor *xdesc = (struct null_descriptor *) desc; diff --git a/src/backends/xor/flat_xor_hd.c b/src/backends/xor/flat_xor_hd.c index 23e0281..9b87314 100644 --- a/src/backends/xor/flat_xor_hd.c +++ b/src/backends/xor/flat_xor_hd.c @@ -46,7 +46,7 @@ struct flat_xor_hd_descriptor { int (*xor_hd_decode)(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int blocksize, int decode_parity); int (*xor_hd_fragments_needed)(xor_code_t *code_desc, int *missing_idxs, - int *fragments_needed); + int *fragments_to_exclude, int *fragments_needed); }; #define DEFAULT_W 32 @@ -86,13 +86,14 @@ static int flat_xor_hd_reconstruct(void *desc, } static int flat_xor_hd_min_fragments(void *desc, - int *missing_idxs, int *fragments_needed) + int *missing_idxs, int *fragments_to_exclude, + int *fragments_needed) { struct flat_xor_hd_descriptor *xdesc = (struct flat_xor_hd_descriptor *) desc; xor_code_t *xor_desc = (xor_code_t *) xdesc->xor_desc; - xor_desc->fragments_needed(xor_desc, missing_idxs, fragments_needed); + xor_desc->fragments_needed(xor_desc, missing_idxs, fragments_to_exclude, fragments_needed); return 0; } diff --git a/src/builtin/xor_codes/xor_hd_code.c b/src/builtin/xor_codes/xor_hd_code.c index 087efcb..9407c75 100644 --- a/src/builtin/xor_codes/xor_hd_code.c +++ b/src/builtin/xor_codes/xor_hd_code.c @@ -174,129 +174,201 @@ static int fragments_needed_three_data(xor_code_t *code_desc, int *missing_data, return ret; } +static int fragments_needed_one_data_local(xor_code_t *code_desc, + int fragment_to_reconstruct, + int *fragments_to_exclude, + unsigned int *data_bm, + unsigned int *parity_bm) +{ + int *missing_data = get_missing_data(code_desc, fragments_to_exclude); + int *missing_parity = get_missing_parity(code_desc, fragments_to_exclude); + int parity_index = index_of_connected_parity(code_desc, fragment_to_reconstruct, missing_parity, missing_data); + + if (parity_index < 0) { + return -1; + } + + // Include all data elements except for this one + *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]); + + // Include this parity element + *parity_bm |= (1 << (parity_index-code_desc->k)); + *data_bm &= ~((unsigned int)1 << fragment_to_reconstruct); + return 0; +} -int xor_hd_fragments_needed(xor_code_t *code_desc, int *missing_idxs, int *fragments_needed) +int xor_hd_fragments_needed(xor_code_t *code_desc, int *fragments_to_reconstruct, int *fragments_to_exclude, int *fragments_needed) { - failure_pattern_t pattern = get_failure_pattern(code_desc, missing_idxs); + failure_pattern_t pattern = get_failure_pattern(code_desc, fragments_to_reconstruct); unsigned int data_bm = 0, parity_bm = 0; - int ret = 0; + int ret = -1; + int *missing_idxs = NULL; int i, j; - switch(pattern) { - case FAIL_PATTERN_0D_0P: - break; - case FAIL_PATTERN_1D_0P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - ret = fragments_needed_one_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); - free(missing_data); - break; - } - case FAIL_PATTERN_2D_0P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - ret = fragments_needed_two_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); - free(missing_data); - break; - } - case FAIL_PATTERN_3D_0P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - ret = fragments_needed_three_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); - free(missing_data); - break; - } - case FAIL_PATTERN_1D_1P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); - ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); - // OR all parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - data_bm &= ~(missing_data_bm); - i++; - } - free(missing_parity); - free(missing_data); - break; - } - case FAIL_PATTERN_1D_2P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); - ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); - // OR all parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - data_bm &= ~(missing_data_bm); - i++; - } - free(missing_parity); - free(missing_data); - break; - } - case FAIL_PATTERN_2D_1P: - { - int *missing_data = get_missing_data(code_desc, missing_idxs); - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); - ret = fragments_needed_two_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); - // OR all parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - data_bm &= ~(missing_data_bm); - i++; - } - free(missing_parity); - free(missing_data); - break; - } - case FAIL_PATTERN_0D_1P: - { - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - // OR all of the parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - i++; - } - free(missing_parity); - break; - } - case FAIL_PATTERN_0D_2P: - { - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - // OR all of the parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - i++; - } - free(missing_parity); - break; - } - case FAIL_PATTERN_0D_3P: - { - int *missing_parity = get_missing_parity(code_desc, missing_idxs); - // OR all of the parities - i=0; - while (missing_parity[i] > -1) { - data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; - i++; - } - free(missing_parity); - break; + /** + * Re-visit this decision (KMG): This is non-optimal, but good enough in most cases. + * If there is a single data item to reconstruct, then try to find a connected parity + * with no items in fragments_to_exclude. If there is a single parity item to reconsturct + * or more than 1 data/parity element missing, then just work fragments_to_exclude into + * missing_idxs. + */ + + if (pattern == FAIL_PATTERN_1D_0P) { + // Since we have landed on this failure pattern, fragments_to_reconstruct[0] is defined. + ret = fragments_needed_one_data_local(code_desc, fragments_to_reconstruct[0], fragments_to_exclude, &data_bm, &parity_bm); + } + + /** + * There is either more than one failed element, a failed parity element or + * we were unable to return the fragments needed for a simple reconstruction. + */ + if (ret == -1) { + /** + * Add everything to missing_idxs (basically, give up on optimizing). + */ + missing_idxs = (int*)malloc(sizeof(int)*(code_desc->k + code_desc->m)); + if (NULL == missing_idxs) { + ret = -1; + goto out; + } + + i = 0; + j = 0; + while (fragments_to_reconstruct[i] > -1) { + missing_idxs[j] = fragments_to_reconstruct[i]; + i++; + j++; } - case FAIL_PATTERN_GE_HD: - default: - break; + i = 0; + while (fragments_to_exclude[i] > -1) { + missing_idxs[j] = fragments_to_exclude[i]; + i++; + j++; + } + // End of list + missing_idxs[j] = -1; + + pattern = get_failure_pattern(code_desc, missing_idxs); + + switch(pattern) { + case FAIL_PATTERN_0D_0P: + break; + case FAIL_PATTERN_1D_0P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + ret = fragments_needed_one_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); + free(missing_data); + break; + } + case FAIL_PATTERN_2D_0P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + ret = fragments_needed_two_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); + free(missing_data); + break; + } + case FAIL_PATTERN_3D_0P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + ret = fragments_needed_three_data(code_desc, missing_data, NULL, &data_bm, &parity_bm); + free(missing_data); + break; + } + case FAIL_PATTERN_1D_1P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); + ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); + // OR all parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + data_bm &= ~(missing_data_bm); + i++; + } + free(missing_parity); + free(missing_data); + break; + } + case FAIL_PATTERN_1D_2P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); + ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); + // OR all parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + data_bm &= ~(missing_data_bm); + i++; + } + free(missing_parity); + free(missing_data); + break; + } + case FAIL_PATTERN_2D_1P: + { + int *missing_data = get_missing_data(code_desc, missing_idxs); + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup); + ret = fragments_needed_two_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm); + // OR all parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + data_bm &= ~(missing_data_bm); + i++; + } + free(missing_parity); + free(missing_data); + break; + } + case FAIL_PATTERN_0D_1P: + { + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + // OR all of the parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + i++; + } + free(missing_parity); + ret = 0; + break; + } + case FAIL_PATTERN_0D_2P: + { + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + // OR all of the parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + i++; + } + free(missing_parity); + ret = 0; + break; + } + case FAIL_PATTERN_0D_3P: + { + int *missing_parity = get_missing_parity(code_desc, missing_idxs); + // OR all of the parities + i=0; + while (missing_parity[i] > -1) { + data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k]; + i++; + } + free(missing_parity); + ret = 0; + break; + } + case FAIL_PATTERN_GE_HD: + default: + break; + } } if (ret >= 0) { @@ -324,6 +396,11 @@ int xor_hd_fragments_needed(xor_code_t *code_desc, int *missing_idxs, int *fragm fragments_needed[j] = -1; } +out: + if (NULL != missing_idxs) { + free(missing_idxs); + } + return ret; } diff --git a/src/erasurecode.c b/src/erasurecode.c index c9bf0ad..b86f38e 100644 --- a/src/erasurecode.c +++ b/src/erasurecode.c @@ -858,12 +858,10 @@ int liberasurecode_fragments_needed(int desc, /* FIXME preprocessing */ - /* FIXME use fragments_to_exclude */ - /* call the backend fragments_needed function passing it desc instance */ ret = instance->common.ops->fragments_needed( instance->desc.backend_desc, - fragments_to_reconstruct, fragments_needed); + fragments_to_reconstruct, fragments_to_exclude, fragments_needed); out_error: return ret; diff --git a/test/builtin/xor_codes/test_xor_hd_code.c b/test/builtin/xor_codes/test_xor_hd_code.c index e5fcae8..f6d9db2 100644 --- a/test/builtin/xor_codes/test_xor_hd_code.c +++ b/test/builtin/xor_codes/test_xor_hd_code.c @@ -70,6 +70,9 @@ int test_hd_code(xor_code_t *code_desc, int num_failure_combs, int failure_combs clock_t start_time, end_time; int *fragments_needed; + /* FIXME: This should actually exclude fragments once XOR codes fully supports the feature */ + int fragments_to_exclude[2] = { -1 }; + srand(time(NULL)); data = (char**)malloc(code_desc->k * sizeof(char*)); @@ -150,7 +153,7 @@ int test_hd_code(xor_code_t *code_desc, int num_failure_combs, int failure_combs * Spot check to ensure missing elements are not included in * list of fragments needed and that decode is 'doable' */ - ret = code_desc->fragments_needed(code_desc, missing_idxs, fragments_needed); + ret = code_desc->fragments_needed(code_desc, missing_idxs, fragments_to_exclude, fragments_needed); if (ret < 0) { fprintf(stderr, "xor_hd_fragments_needed thinks reconstruction not possible, when it is!\n"); |