Backend changes needed to honor "excluded fragments".

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");