]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2015 Intel Corporation All rights reserved. | |
3 | ||
4 | Redistribution and use in source and binary forms, with or without | |
f91f0fd5 | 5 | modification, are permitted provided that the following conditions |
7c673cae FG |
6 | are met: |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | **********************************************************************/ | |
29 | ||
30 | #include <stdio.h> | |
31 | #include <stdlib.h> | |
32 | #include <string.h> // for memset, memcmp | |
33 | #include "erasure_code.h" | |
34 | #include "types.h" | |
35 | ||
36 | #define TEST_LEN 8192 | |
37 | #define TEST_SIZE (TEST_LEN/2) | |
38 | ||
39 | #ifndef TEST_SOURCES | |
40 | # define TEST_SOURCES 127 | |
41 | #endif | |
42 | #ifndef RANDOMS | |
43 | # define RANDOMS 200 | |
44 | #endif | |
45 | ||
46 | #define MMAX TEST_SOURCES | |
47 | #define KMAX TEST_SOURCES | |
48 | ||
49 | #define EFENCE_TEST_MIN_SIZE 16 | |
f91f0fd5 | 50 | #define EFENCE_TEST_MAX_SIZE EFENCE_TEST_MIN_SIZE + 0x100 |
7c673cae FG |
51 | |
52 | #ifdef EC_ALIGNED_ADDR | |
53 | // Define power of 2 range to check ptr, len alignment | |
54 | # define PTR_ALIGN_CHK_B 0 | |
55 | # define LEN_ALIGN_CHK_B 0 // 0 for aligned only | |
56 | #else | |
57 | // Define power of 2 range to check ptr, len alignment | |
58 | # define PTR_ALIGN_CHK_B 32 | |
59 | # define LEN_ALIGN_CHK_B 32 // 0 for aligned only | |
60 | #endif | |
61 | ||
62 | #ifndef TEST_SEED | |
63 | #define TEST_SEED 11 | |
64 | #endif | |
65 | ||
66 | typedef unsigned char u8; | |
67 | ||
68 | void dump(unsigned char *buf, int len) | |
69 | { | |
70 | int i; | |
71 | for (i = 0; i < len;) { | |
72 | printf(" %2x", 0xff & buf[i++]); | |
73 | if (i % 32 == 0) | |
74 | printf("\n"); | |
75 | } | |
76 | printf("\n"); | |
77 | } | |
78 | ||
79 | void dump_matrix(unsigned char **s, int k, int m) | |
80 | { | |
81 | int i, j; | |
82 | for (i = 0; i < k; i++) { | |
83 | for (j = 0; j < m; j++) { | |
84 | printf(" %2x", s[i][j]); | |
85 | } | |
86 | printf("\n"); | |
87 | } | |
88 | printf("\n"); | |
89 | } | |
90 | ||
91 | void dump_u8xu8(unsigned char *s, int k, int m) | |
92 | { | |
93 | int i, j; | |
94 | for (i = 0; i < k; i++) { | |
95 | for (j = 0; j < m; j++) { | |
96 | printf(" %2x", 0xff & s[j + (i * m)]); | |
97 | } | |
98 | printf("\n"); | |
99 | } | |
100 | printf("\n"); | |
101 | } | |
102 | ||
103 | // Generate Random errors | |
104 | static void gen_err_list(unsigned char *src_err_list, | |
105 | unsigned char *src_in_err, int *pnerrs, int *pnsrcerrs, int k, int m) | |
106 | { | |
107 | int i, err; | |
108 | int nerrs = 0, nsrcerrs = 0; | |
109 | ||
110 | for (i = 0, nerrs = 0, nsrcerrs = 0; i < m && nerrs < m - k; i++) { | |
111 | err = 1 & rand(); | |
112 | src_in_err[i] = err; | |
113 | if (err) { | |
114 | src_err_list[nerrs++] = i; | |
115 | if (i < k) { | |
116 | nsrcerrs++; | |
117 | } | |
118 | } | |
119 | } | |
120 | if (nerrs == 0) { // should have at least one error | |
121 | while ((err = (rand() % KMAX)) >= m) ; | |
122 | src_err_list[nerrs++] = err; | |
123 | src_in_err[err] = 1; | |
124 | if (err < k) | |
125 | nsrcerrs = 1; | |
126 | } | |
127 | *pnerrs = nerrs; | |
128 | *pnsrcerrs = nsrcerrs; | |
129 | return; | |
130 | } | |
131 | ||
132 | #define NO_INVERT_MATRIX -2 | |
133 | // Generate decode matrix from encode matrix | |
134 | static int gf_gen_decode_matrix(unsigned char *encode_matrix, | |
135 | unsigned char *decode_matrix, | |
136 | unsigned char *invert_matrix, | |
137 | unsigned int *decode_index, | |
138 | unsigned char *src_err_list, | |
139 | unsigned char *src_in_err, | |
140 | int nerrs, int nsrcerrs, int k, int m) | |
141 | { | |
142 | int i, j, p; | |
143 | int r; | |
144 | unsigned char *backup, *b, s; | |
145 | int incr = 0; | |
146 | ||
147 | b = malloc(MMAX * KMAX); | |
148 | backup = malloc(MMAX * KMAX); | |
149 | ||
150 | if (b == NULL || backup == NULL) { | |
151 | printf("Test failure! Error with malloc\n"); | |
152 | free(b); | |
153 | free(backup); | |
154 | return -1; | |
155 | } | |
156 | // Construct matrix b by removing error rows | |
157 | for (i = 0, r = 0; i < k; i++, r++) { | |
158 | while (src_in_err[r]) | |
159 | r++; | |
160 | for (j = 0; j < k; j++) { | |
161 | b[k * i + j] = encode_matrix[k * r + j]; | |
162 | backup[k * i + j] = encode_matrix[k * r + j]; | |
163 | } | |
164 | decode_index[i] = r; | |
165 | } | |
166 | incr = 0; | |
167 | while (gf_invert_matrix(b, invert_matrix, k) < 0) { | |
168 | if (nerrs == (m - k)) { | |
169 | free(b); | |
170 | free(backup); | |
171 | printf("BAD MATRIX\n"); | |
172 | return NO_INVERT_MATRIX; | |
173 | } | |
174 | incr++; | |
175 | memcpy(b, backup, MMAX * KMAX); | |
176 | for (i = nsrcerrs; i < nerrs - nsrcerrs; i++) { | |
177 | if (src_err_list[i] == (decode_index[k - 1] + incr)) { | |
178 | // skip the erased parity line | |
179 | incr++; | |
180 | continue; | |
181 | } | |
182 | } | |
183 | if (decode_index[k - 1] + incr >= m) { | |
184 | free(b); | |
185 | free(backup); | |
186 | printf("BAD MATRIX\n"); | |
187 | return NO_INVERT_MATRIX; | |
188 | } | |
189 | decode_index[k - 1] += incr; | |
190 | for (j = 0; j < k; j++) | |
191 | b[k * (k - 1) + j] = encode_matrix[k * decode_index[k - 1] + j]; | |
192 | ||
193 | }; | |
194 | ||
195 | for (i = 0; i < nsrcerrs; i++) { | |
196 | for (j = 0; j < k; j++) { | |
197 | decode_matrix[k * i + j] = invert_matrix[k * src_err_list[i] + j]; | |
198 | } | |
199 | } | |
200 | /* src_err_list from encode_matrix * invert of b for parity decoding */ | |
201 | for (p = nsrcerrs; p < nerrs; p++) { | |
202 | for (i = 0; i < k; i++) { | |
203 | s = 0; | |
204 | for (j = 0; j < k; j++) | |
205 | s ^= gf_mul(invert_matrix[j * k + i], | |
206 | encode_matrix[k * src_err_list[p] + j]); | |
207 | ||
208 | decode_matrix[k * p + i] = s; | |
209 | } | |
210 | } | |
211 | free(b); | |
212 | free(backup); | |
213 | return 0; | |
214 | } | |
215 | ||
216 | int main(int argc, char *argv[]) | |
217 | { | |
218 | int re = 0; | |
219 | int i, j, p, rtest, m, k; | |
220 | int nerrs, nsrcerrs; | |
221 | void *buf; | |
222 | unsigned int decode_index[MMAX]; | |
223 | unsigned char *temp_buffs[TEST_SOURCES], *buffs[TEST_SOURCES]; | |
224 | unsigned char *encode_matrix, *decode_matrix, *invert_matrix, *g_tbls; | |
225 | unsigned char src_in_err[TEST_SOURCES], src_err_list[TEST_SOURCES]; | |
226 | unsigned char *recov[TEST_SOURCES]; | |
227 | ||
228 | int rows, align, size; | |
229 | unsigned char *efence_buffs[TEST_SOURCES]; | |
230 | unsigned int offset; | |
231 | u8 *ubuffs[TEST_SOURCES]; | |
232 | u8 *temp_ubuffs[TEST_SOURCES]; | |
233 | ||
234 | printf("erasure_code_test: %dx%d ", TEST_SOURCES, TEST_LEN); | |
235 | srand(TEST_SEED); | |
236 | ||
237 | // Allocate the arrays | |
238 | for (i = 0; i < TEST_SOURCES; i++) { | |
239 | if (posix_memalign(&buf, 64, TEST_LEN)) { | |
240 | printf("alloc error: Fail"); | |
241 | return -1; | |
242 | } | |
243 | buffs[i] = buf; | |
244 | } | |
245 | ||
246 | for (i = 0; i < TEST_SOURCES; i++) { | |
247 | if (posix_memalign(&buf, 64, TEST_LEN)) { | |
248 | printf("alloc error: Fail"); | |
249 | return -1; | |
250 | } | |
251 | temp_buffs[i] = buf; | |
252 | } | |
253 | ||
254 | // Test erasure code by encode and recovery | |
255 | ||
256 | encode_matrix = malloc(MMAX * KMAX); | |
257 | decode_matrix = malloc(MMAX * KMAX); | |
258 | invert_matrix = malloc(MMAX * KMAX); | |
259 | g_tbls = malloc(KMAX * TEST_SOURCES * 32); | |
260 | if (encode_matrix == NULL || decode_matrix == NULL | |
261 | || invert_matrix == NULL || g_tbls == NULL) { | |
262 | printf("Test failure! Error with malloc\n"); | |
263 | return -1; | |
264 | } | |
265 | // Pick a first test | |
266 | m = 9; | |
267 | k = 5; | |
268 | if (m > MMAX || k > KMAX) | |
269 | return -1; | |
270 | ||
271 | // Make random data | |
272 | for (i = 0; i < k; i++) | |
273 | for (j = 0; j < TEST_LEN; j++) | |
274 | buffs[i][j] = rand(); | |
275 | ||
276 | // Generate encode matrix encode_matrix | |
277 | // The matrix generated by gf_gen_rs_matrix | |
278 | // is not always invertable. | |
279 | gf_gen_rs_matrix(encode_matrix, m, k); | |
280 | ||
281 | // Generate g_tbls from encode matrix encode_matrix | |
282 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
283 | ||
284 | // Perform matrix dot_prod for EC encoding | |
285 | // using g_tbls from encode matrix encode_matrix | |
286 | ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]); | |
287 | ||
288 | // Choose random buffers to be in erasure | |
289 | memset(src_in_err, 0, TEST_SOURCES); | |
290 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
291 | ||
292 | // Generate decode matrix | |
293 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
294 | invert_matrix, decode_index, src_err_list, src_in_err, | |
295 | nerrs, nsrcerrs, k, m); | |
296 | if (re != 0) { | |
297 | printf("Fail to gf_gen_decode_matrix\n"); | |
298 | return -1; | |
299 | } | |
300 | // Pack recovery array as list of valid sources | |
301 | // Its order must be the same as the order | |
302 | // to generate matrix b in gf_gen_decode_matrix | |
303 | for (i = 0; i < k; i++) { | |
304 | recov[i] = buffs[decode_index[i]]; | |
305 | } | |
306 | ||
307 | // Recover data | |
308 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
309 | ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]); | |
310 | for (i = 0; i < nerrs; i++) { | |
311 | ||
312 | if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) { | |
313 | printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs); | |
314 | printf(" - erase list = "); | |
315 | for (j = 0; j < nerrs; j++) | |
316 | printf(" %d", src_err_list[j]); | |
317 | printf(" - Index = "); | |
318 | for (p = 0; p < k; p++) | |
319 | printf(" %d", decode_index[p]); | |
320 | printf("\nencode_matrix:\n"); | |
321 | dump_u8xu8((u8 *) encode_matrix, m, k); | |
322 | printf("inv b:\n"); | |
323 | dump_u8xu8((u8 *) invert_matrix, k, k); | |
324 | printf("\ndecode_matrix:\n"); | |
325 | dump_u8xu8((u8 *) decode_matrix, m, k); | |
326 | printf("recov %d:", src_err_list[i]); | |
327 | dump(temp_buffs[k + i], 25); | |
328 | printf("orig :"); | |
329 | dump(buffs[src_err_list[i]], 25); | |
330 | return -1; | |
331 | } | |
332 | } | |
333 | ||
334 | // Pick a first test | |
335 | m = 9; | |
336 | k = 5; | |
337 | if (m > MMAX || k > KMAX) | |
338 | return -1; | |
339 | ||
340 | // Make random data | |
341 | for (i = 0; i < k; i++) | |
342 | for (j = 0; j < TEST_LEN; j++) | |
343 | buffs[i][j] = rand(); | |
344 | ||
345 | // The matrix generated by gf_gen_cauchy1_matrix | |
346 | // is always invertable. | |
347 | gf_gen_cauchy1_matrix(encode_matrix, m, k); | |
348 | ||
349 | // Generate g_tbls from encode matrix encode_matrix | |
350 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
351 | ||
352 | // Perform matrix dot_prod for EC encoding | |
353 | // using g_tbls from encode matrix encode_matrix | |
354 | ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]); | |
355 | ||
356 | // Choose random buffers to be in erasure | |
357 | memset(src_in_err, 0, TEST_SOURCES); | |
358 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
359 | ||
360 | // Generate decode matrix | |
361 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
362 | invert_matrix, decode_index, src_err_list, src_in_err, | |
363 | nerrs, nsrcerrs, k, m); | |
364 | if (re != 0) { | |
365 | printf("Fail to gf_gen_decode_matrix\n"); | |
366 | return -1; | |
367 | } | |
368 | // Pack recovery array as list of valid sources | |
369 | // Its order must be the same as the order | |
370 | // to generate matrix b in gf_gen_decode_matrix | |
371 | for (i = 0; i < k; i++) { | |
372 | recov[i] = buffs[decode_index[i]]; | |
373 | } | |
374 | ||
375 | // Recover data | |
376 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
377 | ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]); | |
378 | for (i = 0; i < nerrs; i++) { | |
379 | ||
380 | if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) { | |
381 | printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs); | |
382 | printf(" - erase list = "); | |
383 | for (j = 0; j < nerrs; j++) | |
384 | printf(" %d", src_err_list[j]); | |
385 | printf(" - Index = "); | |
386 | for (p = 0; p < k; p++) | |
387 | printf(" %d", decode_index[p]); | |
388 | printf("\nencode_matrix:\n"); | |
389 | dump_u8xu8((u8 *) encode_matrix, m, k); | |
390 | printf("inv b:\n"); | |
391 | dump_u8xu8((u8 *) invert_matrix, k, k); | |
392 | printf("\ndecode_matrix:\n"); | |
393 | dump_u8xu8((u8 *) decode_matrix, m, k); | |
394 | printf("recov %d:", src_err_list[i]); | |
395 | dump(temp_buffs[k + i], 25); | |
396 | printf("orig :"); | |
397 | dump(buffs[src_err_list[i]], 25); | |
398 | return -1; | |
399 | } | |
400 | } | |
401 | ||
402 | // Do more random tests | |
403 | for (rtest = 0; rtest < RANDOMS; rtest++) { | |
404 | while ((m = (rand() % MMAX)) < 2) ; | |
405 | while ((k = (rand() % KMAX)) >= m || k < 1) ; | |
406 | ||
407 | if (m > MMAX || k > KMAX) | |
408 | continue; | |
409 | ||
410 | // Make random data | |
411 | for (i = 0; i < k; i++) | |
412 | for (j = 0; j < TEST_LEN; j++) | |
413 | buffs[i][j] = rand(); | |
414 | ||
415 | // The matrix generated by gf_gen_cauchy1_matrix | |
416 | // is always invertable. | |
417 | gf_gen_cauchy1_matrix(encode_matrix, m, k); | |
418 | ||
419 | // Make parity vects | |
420 | // Generate g_tbls from encode matrix a | |
421 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
422 | // Perform matrix dot_prod for EC encoding | |
423 | // using g_tbls from encode matrix a | |
424 | ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]); | |
425 | ||
426 | // Random errors | |
427 | memset(src_in_err, 0, TEST_SOURCES); | |
428 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
429 | ||
430 | // Generate decode matrix | |
431 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
432 | invert_matrix, decode_index, src_err_list, | |
433 | src_in_err, nerrs, nsrcerrs, k, m); | |
434 | if (re != 0) { | |
435 | printf("Fail to gf_gen_decode_matrix\n"); | |
436 | return -1; | |
437 | } | |
438 | // Pack recovery array as list of valid sources | |
439 | // Its order must be the same as the order | |
440 | // to generate matrix b in gf_gen_decode_matrix | |
441 | for (i = 0; i < k; i++) { | |
442 | recov[i] = buffs[decode_index[i]]; | |
443 | } | |
444 | ||
445 | // Recover data | |
446 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
447 | ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]); | |
448 | ||
449 | for (i = 0; i < nerrs; i++) { | |
450 | ||
451 | if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) { | |
452 | printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs); | |
453 | printf(" - erase list = "); | |
454 | for (j = 0; j < nerrs; j++) | |
455 | printf(" %d", src_err_list[j]); | |
456 | printf(" - Index = "); | |
457 | for (p = 0; p < k; p++) | |
458 | printf(" %d", decode_index[p]); | |
459 | printf("\nencode_matrix:\n"); | |
460 | dump_u8xu8((u8 *) encode_matrix, m, k); | |
461 | printf("inv b:\n"); | |
462 | dump_u8xu8((u8 *) invert_matrix, k, k); | |
463 | printf("\ndecode_matrix:\n"); | |
464 | dump_u8xu8((u8 *) decode_matrix, m, k); | |
465 | printf("orig data:\n"); | |
466 | dump_matrix(buffs, m, 25); | |
467 | printf("orig :"); | |
468 | dump(buffs[src_err_list[i]], 25); | |
469 | printf("recov %d:", src_err_list[i]); | |
470 | dump(temp_buffs[k + i], 25); | |
471 | return -1; | |
472 | } | |
473 | } | |
474 | putchar('.'); | |
475 | } | |
476 | ||
477 | // Run tests at end of buffer for Electric Fence | |
478 | k = 16; | |
479 | align = (LEN_ALIGN_CHK_B != 0) ? 1 : 16; | |
480 | if (k > KMAX) | |
481 | return -1; | |
482 | ||
483 | for (rows = 1; rows <= 16; rows++) { | |
484 | m = k + rows; | |
485 | if (m > MMAX) | |
486 | return -1; | |
487 | ||
488 | // Make random data | |
489 | for (i = 0; i < k; i++) | |
490 | for (j = 0; j < TEST_LEN; j++) | |
491 | buffs[i][j] = rand(); | |
492 | ||
f91f0fd5 | 493 | for (size = EFENCE_TEST_MIN_SIZE; size <= EFENCE_TEST_MAX_SIZE; size += align) { |
7c673cae FG |
494 | for (i = 0; i < m; i++) { // Line up TEST_SIZE from end |
495 | efence_buffs[i] = buffs[i] + TEST_LEN - size; | |
496 | } | |
497 | ||
498 | // The matrix generated by gf_gen_cauchy1_matrix | |
499 | // is always invertable. | |
500 | gf_gen_cauchy1_matrix(encode_matrix, m, k); | |
501 | ||
502 | // Make parity vects | |
503 | // Generate g_tbls from encode matrix a | |
504 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
505 | // Perform matrix dot_prod for EC encoding | |
506 | // using g_tbls from encode matrix a | |
507 | ec_encode_data(size, k, m - k, g_tbls, efence_buffs, &efence_buffs[k]); | |
508 | ||
509 | // Random errors | |
510 | memset(src_in_err, 0, TEST_SOURCES); | |
511 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
512 | ||
513 | // Generate decode matrix | |
514 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
515 | invert_matrix, decode_index, src_err_list, | |
516 | src_in_err, nerrs, nsrcerrs, k, m); | |
517 | if (re != 0) { | |
518 | printf("Fail to gf_gen_decode_matrix\n"); | |
519 | return -1; | |
520 | } | |
521 | // Pack recovery array as list of valid sources | |
522 | // Its order must be the same as the order | |
523 | // to generate matrix b in gf_gen_decode_matrix | |
524 | for (i = 0; i < k; i++) { | |
525 | recov[i] = efence_buffs[decode_index[i]]; | |
526 | } | |
527 | ||
528 | // Recover data | |
529 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
530 | ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_buffs[k]); | |
531 | ||
532 | for (i = 0; i < nerrs; i++) { | |
533 | ||
534 | if (0 != | |
535 | memcmp(temp_buffs[k + i], efence_buffs[src_err_list[i]], | |
536 | size)) { | |
537 | printf("Efence: Fail error recovery (%d, %d, %d)\n", m, | |
538 | k, nerrs); | |
539 | ||
540 | printf("size = %d\n", size); | |
541 | ||
542 | printf("Test erase list = "); | |
543 | for (j = 0; j < nerrs; j++) | |
544 | printf(" %d", src_err_list[j]); | |
545 | printf(" - Index = "); | |
546 | for (p = 0; p < k; p++) | |
547 | printf(" %d", decode_index[p]); | |
548 | printf("\nencode_matrix:\n"); | |
549 | dump_u8xu8((u8 *) encode_matrix, m, k); | |
550 | printf("inv b:\n"); | |
551 | dump_u8xu8((u8 *) invert_matrix, k, k); | |
552 | printf("\ndecode_matrix:\n"); | |
553 | dump_u8xu8((u8 *) decode_matrix, m, k); | |
554 | ||
555 | printf("recov %d:", src_err_list[i]); | |
556 | dump(temp_buffs[k + i], align); | |
557 | printf("orig :"); | |
558 | dump(efence_buffs[src_err_list[i]], align); | |
559 | return -1; | |
560 | } | |
561 | } | |
562 | } | |
563 | ||
564 | } | |
565 | ||
566 | // Test rand ptr alignment if available | |
567 | ||
568 | for (rtest = 0; rtest < RANDOMS; rtest++) { | |
569 | while ((m = (rand() % MMAX)) < 2) ; | |
570 | while ((k = (rand() % KMAX)) >= m || k < 1) ; | |
571 | ||
572 | if (m > MMAX || k > KMAX) | |
573 | continue; | |
574 | ||
575 | size = (TEST_LEN - PTR_ALIGN_CHK_B) & ~15; | |
576 | ||
577 | offset = (PTR_ALIGN_CHK_B != 0) ? 1 : PTR_ALIGN_CHK_B; | |
578 | // Add random offsets | |
579 | for (i = 0; i < m; i++) { | |
580 | memset(buffs[i], 0, TEST_LEN); // zero pad to check write-over | |
581 | memset(temp_buffs[i], 0, TEST_LEN); // zero pad to check write-over | |
582 | ubuffs[i] = buffs[i] + (rand() & (PTR_ALIGN_CHK_B - offset)); | |
583 | temp_ubuffs[i] = temp_buffs[i] + (rand() & (PTR_ALIGN_CHK_B - offset)); | |
584 | } | |
585 | ||
586 | for (i = 0; i < k; i++) | |
587 | for (j = 0; j < size; j++) | |
588 | ubuffs[i][j] = rand(); | |
589 | ||
590 | // The matrix generated by gf_gen_cauchy1_matrix | |
591 | // is always invertable. | |
592 | gf_gen_cauchy1_matrix(encode_matrix, m, k); | |
593 | ||
594 | // Make parity vects | |
595 | // Generate g_tbls from encode matrix a | |
596 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
597 | // Perform matrix dot_prod for EC encoding | |
598 | // using g_tbls from encode matrix a | |
599 | ec_encode_data(size, k, m - k, g_tbls, ubuffs, &ubuffs[k]); | |
600 | ||
601 | // Random errors | |
602 | memset(src_in_err, 0, TEST_SOURCES); | |
603 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
604 | ||
605 | // Generate decode matrix | |
606 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
607 | invert_matrix, decode_index, src_err_list, | |
608 | src_in_err, nerrs, nsrcerrs, k, m); | |
609 | if (re != 0) { | |
610 | printf("Fail to gf_gen_decode_matrix\n"); | |
611 | return -1; | |
612 | } | |
613 | // Pack recovery array as list of valid sources | |
614 | // Its order must be the same as the order | |
615 | // to generate matrix b in gf_gen_decode_matrix | |
616 | for (i = 0; i < k; i++) { | |
617 | recov[i] = ubuffs[decode_index[i]]; | |
618 | } | |
619 | ||
620 | // Recover data | |
621 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
622 | ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_ubuffs[k]); | |
623 | ||
624 | for (i = 0; i < nerrs; i++) { | |
625 | ||
626 | if (0 != memcmp(temp_ubuffs[k + i], ubuffs[src_err_list[i]], size)) { | |
627 | printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs); | |
628 | printf(" - erase list = "); | |
629 | for (j = 0; j < nerrs; j++) | |
630 | printf(" %d", src_err_list[j]); | |
631 | printf(" - Index = "); | |
632 | for (p = 0; p < k; p++) | |
633 | printf(" %d", decode_index[p]); | |
634 | printf("\nencode_matrix:\n"); | |
635 | dump_u8xu8((unsigned char *)encode_matrix, m, k); | |
636 | printf("inv b:\n"); | |
637 | dump_u8xu8((unsigned char *)invert_matrix, k, k); | |
638 | printf("\ndecode_matrix:\n"); | |
639 | dump_u8xu8((unsigned char *)decode_matrix, m, k); | |
640 | printf("orig data:\n"); | |
641 | dump_matrix(ubuffs, m, 25); | |
642 | printf("orig :"); | |
643 | dump(ubuffs[src_err_list[i]], 25); | |
644 | printf("recov %d:", src_err_list[i]); | |
645 | dump(temp_ubuffs[k + i], 25); | |
646 | return -1; | |
647 | } | |
648 | } | |
649 | ||
650 | // Confirm that padding around dests is unchanged | |
651 | memset(temp_buffs[0], 0, PTR_ALIGN_CHK_B); // Make reference zero buff | |
652 | ||
653 | for (i = 0; i < m; i++) { | |
654 | ||
655 | offset = ubuffs[i] - buffs[i]; | |
656 | ||
657 | if (memcmp(buffs[i], temp_buffs[0], offset)) { | |
658 | printf("Fail rand ualign encode pad start\n"); | |
659 | return -1; | |
660 | } | |
661 | if (memcmp | |
662 | (buffs[i] + offset + size, temp_buffs[0], | |
663 | PTR_ALIGN_CHK_B - offset)) { | |
664 | printf("Fail rand ualign encode pad end\n"); | |
665 | return -1; | |
666 | } | |
667 | } | |
668 | ||
669 | for (i = 0; i < nerrs; i++) { | |
670 | ||
671 | offset = temp_ubuffs[k + i] - temp_buffs[k + i]; | |
672 | if (memcmp(temp_buffs[k + i], temp_buffs[0], offset)) { | |
673 | printf("Fail rand ualign decode pad start\n"); | |
674 | return -1; | |
675 | } | |
676 | if (memcmp | |
677 | (temp_buffs[k + i] + offset + size, temp_buffs[0], | |
678 | PTR_ALIGN_CHK_B - offset)) { | |
679 | printf("Fail rand ualign decode pad end\n"); | |
680 | return -1; | |
681 | } | |
682 | } | |
683 | ||
684 | putchar('.'); | |
685 | } | |
686 | ||
687 | // Test size alignment | |
688 | ||
689 | align = (LEN_ALIGN_CHK_B != 0) ? 13 : 16; | |
690 | ||
691 | for (size = TEST_LEN; size > 0; size -= align) { | |
692 | while ((m = (rand() % MMAX)) < 2) ; | |
693 | while ((k = (rand() % KMAX)) >= m || k < 1) ; | |
694 | ||
695 | if (m > MMAX || k > KMAX) | |
696 | continue; | |
697 | ||
698 | for (i = 0; i < k; i++) | |
699 | for (j = 0; j < size; j++) | |
700 | buffs[i][j] = rand(); | |
701 | ||
702 | // The matrix generated by gf_gen_cauchy1_matrix | |
703 | // is always invertable. | |
704 | gf_gen_cauchy1_matrix(encode_matrix, m, k); | |
705 | ||
706 | // Make parity vects | |
707 | // Generate g_tbls from encode matrix a | |
708 | ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls); | |
709 | // Perform matrix dot_prod for EC encoding | |
710 | // using g_tbls from encode matrix a | |
711 | ec_encode_data(size, k, m - k, g_tbls, buffs, &buffs[k]); | |
712 | ||
713 | // Random errors | |
714 | memset(src_in_err, 0, TEST_SOURCES); | |
715 | gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m); | |
716 | // Generate decode matrix | |
717 | re = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
718 | invert_matrix, decode_index, src_err_list, | |
719 | src_in_err, nerrs, nsrcerrs, k, m); | |
720 | if (re != 0) { | |
721 | printf("Fail to gf_gen_decode_matrix\n"); | |
722 | return -1; | |
723 | } | |
724 | // Pack recovery array as list of valid sources | |
725 | // Its order must be the same as the order | |
726 | // to generate matrix b in gf_gen_decode_matrix | |
727 | for (i = 0; i < k; i++) { | |
728 | recov[i] = buffs[decode_index[i]]; | |
729 | } | |
730 | ||
731 | // Recover data | |
732 | ec_init_tables(k, nerrs, decode_matrix, g_tbls); | |
733 | ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_buffs[k]); | |
734 | ||
735 | for (i = 0; i < nerrs; i++) { | |
736 | ||
737 | if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], size)) { | |
738 | printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs); | |
739 | printf(" - erase list = "); | |
740 | for (j = 0; j < nerrs; j++) | |
741 | printf(" %d", src_err_list[j]); | |
742 | printf(" - Index = "); | |
743 | for (p = 0; p < k; p++) | |
744 | printf(" %d", decode_index[p]); | |
745 | printf("\nencode_matrix:\n"); | |
746 | dump_u8xu8((unsigned char *)encode_matrix, m, k); | |
747 | printf("inv b:\n"); | |
748 | dump_u8xu8((unsigned char *)invert_matrix, k, k); | |
749 | printf("\ndecode_matrix:\n"); | |
750 | dump_u8xu8((unsigned char *)decode_matrix, m, k); | |
751 | printf("orig data:\n"); | |
752 | dump_matrix(buffs, m, 25); | |
753 | printf("orig :"); | |
754 | dump(buffs[src_err_list[i]], 25); | |
755 | printf("recov %d:", src_err_list[i]); | |
756 | dump(temp_buffs[k + i], 25); | |
757 | return -1; | |
758 | } | |
759 | } | |
760 | } | |
761 | ||
762 | printf("done EC tests: Pass\n"); | |
763 | return 0; | |
764 | } |