1 /*
2 * Copyright 2014 Eric Lambert
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9 *
10 * Redistributions in binary form must reproduce the above copyright notice, this
11 * list of conditions and the following disclaimer in the documentation and/or
12 * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
13 * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
14 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16 * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
18 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
21 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 */
24
25 /*
26 * EDL 8/26/2014: This test is based on the test/test_xor_hd_code. It runs
27 * through a similar set of conditions but instead uses the liberasurecode
28 * API as opposed to directly talking to xor implementation. In the original
29 * test_xor_hd_code, we measured the performance of a series of encode/decode
30 * ops. For the time being, I have "disabled" the performance measurement in
31 * this test ... the main reason for doing so was that we need to some more
32 * memory management when using the API and I did not want those management
33 * ops polluting the resutls. When I have some time I will renable address
34 * this (figure out how to make sure memory management does not affect perf
35 * numbers).
36 */
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <time.h>
42 #include <assert.h>
43 #include "erasurecode.h"
44 #include "erasurecode_helpers.h"
45 #include "erasurecode_helpers_ext.h"
46 #include "builtin/xor_codes/test_xor_hd_code.h"
47
48 struct frag_array_set {
49 unsigned int num_fragments;
50 char **array;
51 };
52
print_mask(unsigned long mask)53 void print_mask(unsigned long mask)
54 {
55 unsigned int i = 0;
56 long pos = 1;
57
58 if (mask == 0) {
59 fprintf(stderr," No Missing fragments");
60 return;
61 }
62 fprintf(stderr," Missing fragments = ");
63 for (i = 0; i < (sizeof(size_t) * 8) - 1; i++) {
64 if ((mask & (pos << i)) != 0) {
65 fprintf(stderr,"%d ",i);
66 }
67 }
68 }
69
missing_mask_to_array(long mask,int * missing)70 void missing_mask_to_array(long mask, int *missing)
71 {
72 unsigned int i = 0;
73 long pos = 1;
74
75 for (i = 0; i < (sizeof(size_t) * 8) - 1; i++) {
76 if ((mask & (pos << i)) != 0) {
77 *missing = i;
78 }
79 }
80 }
81
add_item_to_missing_mask(unsigned long mask,long pos)82 size_t add_item_to_missing_mask(unsigned long mask, long pos)
83 {
84 if (pos < 0) {
85 return mask;
86 }
87 unsigned long f = 1L << pos;
88 mask |= f;
89 return mask;
90 }
91
create_frags_array_set(struct frag_array_set * set,char ** data,unsigned int num_data_frags,char ** parity,unsigned int num_parity_frags,unsigned long missing_mask)92 static int create_frags_array_set(struct frag_array_set *set,
93 char **data,
94 unsigned int num_data_frags,
95 char **parity,
96 unsigned int num_parity_frags,
97 unsigned long missing_mask)
98 {
99 int rc =0;
100 unsigned int num_frags = 0;
101 unsigned long i = 0;
102 fragment_header_t *header = NULL;
103 size_t size = (num_data_frags + num_parity_frags) * sizeof(char *);
104 char **array = malloc(size);
105
106 if (array == NULL) {
107 rc = -1;
108 goto out;
109 }
110
111 //add data frags
112 memset(array, 0, size);
113 for (i = 0; i < num_data_frags; i++) {
114 if ( (missing_mask | 1L << i) == 1) {
115 continue;
116 }
117 header = (fragment_header_t*)data[i];
118 if (header == NULL ||
119 header->magic != LIBERASURECODE_FRAG_HEADER_MAGIC) {
120 continue;
121 }
122 array[num_frags++] = data[i];
123 }
124
125 //add parity frags
126 for (i = 0; i < num_parity_frags; i++) {
127 if ( (missing_mask | 1L << (i + num_data_frags)) == 1) {
128 continue;
129 }
130 header = (fragment_header_t*)parity[i];
131 if (header == NULL ||
132 header->magic != LIBERASURECODE_FRAG_HEADER_MAGIC) {
133 continue;
134 }
135 array[num_frags++] = parity[i];
136 }
137
138 set->num_fragments = num_frags;
139 set->array = array;
140 out:
141 return rc;
142 }
143
fill_buffer(char * buf,size_t size,int seed)144 static void fill_buffer(char *buf, size_t size, int seed)
145 {
146 size_t i;
147
148 for (i=0; i < size; i++) {
149 buf[i] = (seed += i);
150 }
151 }
152
test_hd_code(struct ec_args * args,int num_failure_combs,int failure_combs[][4])153 static int test_hd_code(struct ec_args *args,
154 int num_failure_combs,
155 int failure_combs[][4])
156 {
157 int i, j, err;
158 unsigned int num_iter = 1000;
159 size_t blocksize = 32768;
160 int missing_idxs[4] = { -1, -1, -1, -1 };
161 int excluded_idxs[4] = { -1, -1, -1, -1 };
162 int ret = 0;
163 char *data, **parity;
164 int *fragments_needed;
165 char **encoded_data = NULL;
166 char **encoded_parity = NULL;
167 uint64_t encoded_fragment_len = 0;
168 int rc = 0;
169 char *out_data = NULL;
170 uint64_t out_data_len = 0;
171 unsigned long mask = 0;
172 int desc = -1;
173 struct frag_array_set frags; //MOVE ME
174
175 srand(time(NULL));
176
177 /*
178 * Set up data and parity fragments.
179 */
180
181 fragments_needed = (int*)malloc(args->k*args->m*sizeof(int));
182 if (!fragments_needed) {
183 fprintf(stderr, "Could not allocate memory for fragments\n");
184 exit(2);
185 }
186 memset(fragments_needed, 0, args->k*args->m*sizeof(int));
187
188 err = posix_memalign((void **) &data, 16, blocksize * args->k);
189 if (err != 0 || !data) {
190 fprintf(stderr, "Could not allocate memory for data\n");
191 exit(1);
192 }
193 fill_buffer(data, blocksize * args->k, 0);
194
195 parity = (char**)malloc(args->m * sizeof(char*));
196 for (i=0; i < args->m; i++) {
197 err = posix_memalign((void **) &parity[i], 16, blocksize);
198 if (err != 0 || !parity[i]) {
199 fprintf(stderr, "Could not allocate memory for parity %d\n", i);
200 exit(1);
201 }
202 memset(parity[i], 0, blocksize);
203 }
204
205 /*
206 * Get handle
207 */
208 desc = liberasurecode_instance_create(EC_BACKEND_FLAT_XOR_HD, args);
209 if (desc <= 0) {
210 fprintf(stderr, "Could not create libec descriptor\n");
211 exit(1);
212 }
213
214 /*
215 * Run Encode test
216 */
217 for (i=0; i < num_iter-1; i++) {
218 rc = liberasurecode_encode(desc, data, blocksize * args->k,
219 &encoded_data, &encoded_parity,
220 &encoded_fragment_len);
221 //FIXME: this and the following free's taint the perf test
222 assert(0 == rc);
223 for (j = 0; j < args->k; j++) {
224 free(encoded_data[j]);
225 }
226 free(encoded_data);
227 for (j = 0; j < args->m; j++) {
228 free(encoded_parity[j]);
229 }
230 free(encoded_parity);
231 }
232 fprintf(stderr, " Encode: OK\n");
233
234 for (i=0; i < args->m; i++) {
235 memset(parity[i], 0, blocksize);
236 }
237 rc = liberasurecode_encode(desc, data, blocksize * args->k, &encoded_data,
238 &encoded_parity, &encoded_fragment_len);
239 assert(0 == rc);
240
241 /*
242 * Run Decode Test
243 */
244 for (i=0; i < num_failure_combs; i++) {
245 mask = 0;
246 for (j = 0; j < 3; j++) {
247 int idx = failure_combs[i][j];
248 if (idx == -1) {
249 continue;
250 }
251 mask = add_item_to_missing_mask(mask, idx);
252 }
253
254 /*
255 * Spot check to ensure missing elements are not included in
256 * list of fragments needed and that decode is 'doable'
257 */
258 missing_mask_to_array(mask, missing_idxs);
259 ret = liberasurecode_fragments_needed(desc, missing_idxs, excluded_idxs,
260 fragments_needed); //known leak
261 if (ret < 0) {
262 fprintf(stderr,"xor_hd_fragments_needed thinks reconstruction not possible, when it is!\n");
263 exit(2);
264 }
265
266 /*
267 * Make sure that none of the missig fragments are in the set of
268 * fragments needed to reconstruct the object.
269 */
270 j = 0;
271 while (fragments_needed[j] > -1) {
272 if (fragments_needed[j] == missing_idxs[0] ||
273 fragments_needed[j] == missing_idxs[1] ||
274 fragments_needed[j] == missing_idxs[2]) {
275 fprintf(stderr,
276 "fragments_needed[%d]=%d in missing index list: (%d %d %d)!\n",
277 j, fragments_needed[j], missing_idxs[0],
278 missing_idxs[1], missing_idxs[2]);
279 exit(2);
280 }
281 j++;
282 }
283 create_frags_array_set(&frags,encoded_data, args->k, encoded_parity,
284 args->m, mask);
285 rc = liberasurecode_decode(desc, frags.array, frags.num_fragments,
286 encoded_fragment_len, 1,
287 &out_data, &out_data_len);
288 assert(rc == 0);
289 assert(out_data_len == blocksize * args->k);
290 if (memcmp(data, out_data, out_data_len) != 0) {
291 fprintf(stderr, "Decode did not work: (%d %d %d)!\n",
292 missing_idxs[0], missing_idxs[1], missing_idxs[2]);
293 exit(2);
294 }
295 free(frags.array);
296 free(out_data);
297 }
298
299 for (i=0; i < num_iter; i++) {
300 mask = 0;
301 int mi = rand() % (args->k + args->m);
302
303 mask = add_item_to_missing_mask(mask, mi);
304 for (j=1; j < args->hd-1;j++) {
305 mi = mi + 1 % (args->k + args->m);
306 mask = add_item_to_missing_mask(mask, mi);
307 }
308 create_frags_array_set(&frags,encoded_data, args->k, encoded_parity,
309 args->m, mask);
310 rc = liberasurecode_decode(desc, frags.array, frags.num_fragments,
311 encoded_fragment_len, 1,
312 &out_data, &out_data_len);
313 free(frags.array);
314 free(out_data);
315
316 assert(rc == 0);
317 //print_mask(mask);
318 }
319 for (j = 0; j < args->k; j++) {
320 free(encoded_data[j]);
321 }
322 free(encoded_data);
323 for (j = 0; j < args->m; j++) {
324 free(encoded_parity[j]);
325 }
326 free(encoded_parity);
327 free(fragments_needed);
328 free(data);
329 for (i = 0; i < args->m; i++) {
330 free(parity[i]);
331 }
332 free(parity);
333
334 liberasurecode_instance_destroy(desc);
335 return 0;
336 }
337
run_test(int k,int m,int hd)338 static int run_test(int k, int m, int hd)
339 {
340 int ret = -1;
341 struct ec_args args = {
342 .k = k,
343 .m = m,
344 .hd = hd,
345 };
346
347 fprintf(stderr, "Running (%d, %d, %d):\n", k, m, hd);
348
349 switch(k+m)
350 {
351 case 10:
352 if (hd == 3) {
353 ret = test_hd_code(&args, NUM_10_3_COMBS, failure_combs_10_3);
354 } else {
355 ret = test_hd_code(&args, NUM_10_4_COMBS, failure_combs_10_4);
356 }
357 break;
358 case 11:
359 if (hd == 3) {
360 ret = test_hd_code(&args, NUM_11_3_COMBS, failure_combs_11_3);
361 } else {
362 ret = test_hd_code(&args, NUM_11_4_COMBS, failure_combs_11_4);
363 }
364 break;
365 case 12:
366 if (hd == 3) {
367 ret = test_hd_code(&args, NUM_12_3_COMBS, failure_combs_12_3);
368 } else {
369 ret = test_hd_code(&args, NUM_12_4_COMBS, failure_combs_12_4);
370 }
371 break;
372 case 13:
373 if (hd == 3) {
374 ret = test_hd_code(&args, NUM_13_3_COMBS, failure_combs_13_3);
375 } else {
376 ret = test_hd_code(&args, NUM_13_4_COMBS, failure_combs_13_4);
377 }
378 break;
379 case 14:
380 if (hd == 3) {
381 ret = test_hd_code(&args, NUM_14_3_COMBS, failure_combs_14_3);
382 } else {
383 ret = test_hd_code(&args, NUM_14_4_COMBS, failure_combs_14_4);
384 }
385 break;
386 case 15:
387 if (hd == 3) {
388 ret = test_hd_code(&args, NUM_15_3_COMBS, failure_combs_15_3);
389 } else {
390 ret = test_hd_code(&args, NUM_15_4_COMBS, failure_combs_15_4);
391 }
392 break;
393 case 16:
394 if (hd == 3) {
395 ret = test_hd_code(&args, NUM_16_3_COMBS, failure_combs_16_3);
396 } else {
397 ret = test_hd_code(&args, NUM_16_4_COMBS, failure_combs_16_4);
398 }
399 break;
400 case 17:
401 if (hd == 3) {
402 ret = test_hd_code(&args, NUM_17_3_COMBS, failure_combs_17_3);
403 } else {
404 ret = test_hd_code(&args, NUM_17_4_COMBS, failure_combs_17_4);
405 }
406 break;
407 case 18:
408 if (hd == 3) {
409 ret = test_hd_code(&args, NUM_18_3_COMBS, failure_combs_18_3);
410 } else {
411 ret = test_hd_code(&args, NUM_18_4_COMBS, failure_combs_18_4);
412 }
413 break;
414 case 19:
415 if (hd == 3) {
416 ret = test_hd_code(&args, NUM_19_3_COMBS, failure_combs_19_3);
417 } else {
418 ret = test_hd_code(&args, NUM_19_4_COMBS, failure_combs_19_4);
419 }
420 break;
421 case 20:
422 if (hd == 3) {
423 ret = test_hd_code(&args, NUM_20_3_COMBS, failure_combs_20_3);
424 } else {
425 ret = test_hd_code(&args, NUM_20_4_COMBS, failure_combs_20_4);
426 }
427 break;
428 case 21:
429 if (hd == 3) {
430 ret = test_hd_code(&args, NUM_21_3_COMBS, failure_combs_21_3);
431 } else {
432 ret = test_hd_code(&args, NUM_21_4_COMBS, failure_combs_21_4);
433 }
434 break;
435 case 22:
436 ret = test_hd_code(&args, NUM_22_4_COMBS, failure_combs_22_4);
437 break;
438 case 23:
439 ret = test_hd_code(&args, NUM_23_4_COMBS, failure_combs_23_4);
440 break;
441 case 24:
442 ret = test_hd_code(&args, NUM_24_4_COMBS, failure_combs_24_4);
443 break;
444 case 25:
445 ret = test_hd_code(&args, NUM_25_4_COMBS, failure_combs_25_4);
446 break;
447 case 26:
448 ret = test_hd_code(&args, NUM_26_4_COMBS, failure_combs_26_4);
449 break;
450 default:
451 ret = -1;
452 }
453 return ret;
454 }
455
main()456 int main()
457 {
458 int ret = 0;
459 int i;
460 for (i=6; i < 16; i++) {
461 ret = run_test(i, 6, 3);
462 if (ret != 0) {
463 return ret;
464 }
465 }
466
467 for (i=5; i < 11; i++) {
468 ret = run_test(i, 5, 3);
469 if (ret != 0) {
470 return ret;
471 }
472 }
473
474 for (i=6; i < 21; i++) {
475 ret = run_test(i, 6, 4);
476 if (ret != 0) {
477 return ret;
478 }
479 }
480 for (i=5; i < 11; i++) {
481 ret = run_test(i, 5, 4);
482 if (ret != 0) {
483 return ret;
484 }
485 }
486 exit(ret);
487 }
488
489