]> git.proxmox.com Git - ceph.git/blob - ceph/src/spdk/isa-l/erasure_code/gf_vect_dot_prod_test.c
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
import 15.2.0 Octopus source
[ceph.git] / ceph / src / spdk / isa-l / erasure_code / gf_vect_dot_prod_test.c
1 /**********************************************************************
2 Copyright(c) 2011-2015 Intel Corporation All rights reserved.
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
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 #ifndef FUNCTION_UNDER_TEST
37 # define FUNCTION_UNDER_TEST gf_vect_dot_prod
38 #endif
39 #ifndef TEST_MIN_SIZE
40 # define TEST_MIN_SIZE 32
41 #endif
42
43 #define str(s) #s
44 #define xstr(s) str(s)
45
46 #define TEST_LEN 8192
47 #define TEST_SIZE (TEST_LEN/2)
48
49 #ifndef TEST_SOURCES
50 # define TEST_SOURCES 16
51 #endif
52 #ifndef RANDOMS
53 # define RANDOMS 20
54 #endif
55
56 #define MMAX TEST_SOURCES
57 #define KMAX TEST_SOURCES
58
59 #ifdef EC_ALIGNED_ADDR
60 // Define power of 2 range to check ptr, len alignment
61 # define PTR_ALIGN_CHK_B 0
62 # define LEN_ALIGN_CHK_B 0 // 0 for aligned only
63 #else
64 // Define power of 2 range to check ptr, len alignment
65 # define PTR_ALIGN_CHK_B 32
66 # define LEN_ALIGN_CHK_B 32 // 0 for aligned only
67 #endif
68
69 typedef unsigned char u8;
70
71 void dump(unsigned char *buf, int len)
72 {
73 int i;
74 for (i = 0; i < len;) {
75 printf(" %2x", 0xff & buf[i++]);
76 if (i % 32 == 0)
77 printf("\n");
78 }
79 printf("\n");
80 }
81
82 void dump_matrix(unsigned char **s, int k, int m)
83 {
84 int i, j;
85 for (i = 0; i < k; i++) {
86 for (j = 0; j < m; j++) {
87 printf(" %2x", s[i][j]);
88 }
89 printf("\n");
90 }
91 printf("\n");
92 }
93
94 void dump_u8xu8(unsigned char *s, int k, int m)
95 {
96 int i, j;
97 for (i = 0; i < k; i++) {
98 for (j = 0; j < m; j++) {
99 printf(" %2x", 0xff & s[j + (i * m)]);
100 }
101 printf("\n");
102 }
103 printf("\n");
104 }
105
106 int main(int argc, char *argv[])
107 {
108 int i, j, rtest, srcs, m, k, nerrs, r, err;
109 void *buf;
110 u8 g[TEST_SOURCES], g_tbls[TEST_SOURCES * 32], src_in_err[TEST_SOURCES];
111 u8 *dest, *dest_ref, *temp_buff, *buffs[TEST_SOURCES];
112 u8 a[MMAX * KMAX], b[MMAX * KMAX], d[MMAX * KMAX];
113 u8 src_err_list[TEST_SOURCES], *recov[TEST_SOURCES];
114
115 int align, size;
116 unsigned char *efence_buffs[TEST_SOURCES];
117 unsigned int offset;
118 u8 *ubuffs[TEST_SOURCES];
119 u8 *udest_ptr;
120
121 printf(xstr(FUNCTION_UNDER_TEST) ": %dx%d ", TEST_SOURCES, TEST_LEN);
122
123 // Allocate the arrays
124 for (i = 0; i < TEST_SOURCES; i++) {
125 if (posix_memalign(&buf, 64, TEST_LEN)) {
126 printf("alloc error: Fail");
127 return -1;
128 }
129 buffs[i] = buf;
130 }
131
132 if (posix_memalign(&buf, 64, TEST_LEN)) {
133 printf("alloc error: Fail");
134 return -1;
135 }
136 dest = buf;
137
138 if (posix_memalign(&buf, 64, TEST_LEN)) {
139 printf("alloc error: Fail");
140 return -1;
141 }
142 dest_ref = buf;
143
144 if (posix_memalign(&buf, 64, TEST_LEN)) {
145 printf("alloc error: Fail");
146 return -1;
147 }
148 temp_buff = buf;
149
150 // Test of all zeros
151 for (i = 0; i < TEST_SOURCES; i++)
152 memset(buffs[i], 0, TEST_LEN);
153
154 memset(dest, 0, TEST_LEN);
155 memset(temp_buff, 0, TEST_LEN);
156 memset(dest_ref, 0, TEST_LEN);
157 memset(g, 0, TEST_SOURCES);
158
159 for (i = 0; i < TEST_SOURCES; i++)
160 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
161
162 gf_vect_dot_prod_base(TEST_LEN, TEST_SOURCES, &g_tbls[0], buffs, dest_ref);
163
164 FUNCTION_UNDER_TEST(TEST_LEN, TEST_SOURCES, g_tbls, buffs, dest);
165
166 if (0 != memcmp(dest_ref, dest, TEST_LEN)) {
167 printf("Fail zero " xstr(FUNCTION_UNDER_TEST) " \n");
168 dump_matrix(buffs, 5, TEST_SOURCES);
169 printf("dprod_base:");
170 dump(dest_ref, 25);
171 printf("dprod:");
172 dump(dest, 25);
173 return -1;
174 } else
175 putchar('.');
176
177 // Rand data test
178 for (rtest = 0; rtest < RANDOMS; rtest++) {
179 for (i = 0; i < TEST_SOURCES; i++)
180 for (j = 0; j < TEST_LEN; j++)
181 buffs[i][j] = rand();
182
183 for (i = 0; i < TEST_SOURCES; i++)
184 g[i] = rand();
185
186 for (i = 0; i < TEST_SOURCES; i++)
187 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
188
189 gf_vect_dot_prod_base(TEST_LEN, TEST_SOURCES, &g_tbls[0], buffs, dest_ref);
190 FUNCTION_UNDER_TEST(TEST_LEN, TEST_SOURCES, g_tbls, buffs, dest);
191
192 if (0 != memcmp(dest_ref, dest, TEST_LEN)) {
193 printf("Fail rand " xstr(FUNCTION_UNDER_TEST) " 1\n");
194 dump_matrix(buffs, 5, TEST_SOURCES);
195 printf("dprod_base:");
196 dump(dest_ref, 25);
197 printf("dprod:");
198 dump(dest, 25);
199 return -1;
200 }
201
202 putchar('.');
203 }
204
205 // Rand data test with varied parameters
206 for (rtest = 0; rtest < RANDOMS; rtest++) {
207 for (srcs = TEST_SOURCES; srcs > 0; srcs--) {
208 for (i = 0; i < srcs; i++)
209 for (j = 0; j < TEST_LEN; j++)
210 buffs[i][j] = rand();
211
212 for (i = 0; i < srcs; i++)
213 g[i] = rand();
214
215 for (i = 0; i < srcs; i++)
216 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
217
218 gf_vect_dot_prod_base(TEST_LEN, srcs, &g_tbls[0], buffs, dest_ref);
219 FUNCTION_UNDER_TEST(TEST_LEN, srcs, g_tbls, buffs, dest);
220
221 if (0 != memcmp(dest_ref, dest, TEST_LEN)) {
222 printf("Fail rand " xstr(FUNCTION_UNDER_TEST) " test 2\n");
223 dump_matrix(buffs, 5, srcs);
224 printf("dprod_base:");
225 dump(dest_ref, 5);
226 printf("dprod:");
227 dump(dest, 5);
228 return -1;
229 }
230
231 putchar('.');
232 }
233 }
234
235 // Test erasure code using gf_vect_dot_prod
236
237 // Pick a first test
238 m = 9;
239 k = 5;
240 if (m > MMAX || k > KMAX)
241 return -1;
242
243 gf_gen_rs_matrix(a, m, k);
244
245 // Make random data
246 for (i = 0; i < k; i++)
247 for (j = 0; j < TEST_LEN; j++)
248 buffs[i][j] = rand();
249
250 // Make parity vects
251 for (i = k; i < m; i++) {
252 for (j = 0; j < k; j++)
253 gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]);
254 #ifndef USEREF
255 FUNCTION_UNDER_TEST(TEST_LEN, k, g_tbls, buffs, buffs[i]);
256 #else
257 gf_vect_dot_prod_base(TEST_LEN, k, &g_tbls[0], buffs, buffs[i]);
258 #endif
259 }
260
261 // Random buffers in erasure
262 memset(src_in_err, 0, TEST_SOURCES);
263 for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) {
264 err = 1 & rand();
265 src_in_err[i] = err;
266 if (err)
267 src_err_list[nerrs++] = i;
268 }
269
270 // construct b by removing error rows
271 for (i = 0, r = 0; i < k; i++, r++) {
272 while (src_in_err[r]) {
273 r++;
274 continue;
275 }
276 for (j = 0; j < k; j++)
277 b[k * i + j] = a[k * r + j];
278 }
279
280 if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0)
281 printf("BAD MATRIX\n");
282
283 for (i = 0, r = 0; i < k; i++, r++) {
284 while (src_in_err[r]) {
285 r++;
286 continue;
287 }
288 recov[i] = buffs[r];
289 }
290
291 // Recover data
292 for (i = 0; i < nerrs; i++) {
293 for (j = 0; j < k; j++)
294 gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]);
295 #ifndef USEREF
296 FUNCTION_UNDER_TEST(TEST_LEN, k, g_tbls, recov, temp_buff);
297 #else
298 gf_vect_dot_prod_base(TEST_LEN, k, &g_tbls[0], recov, temp_buff);
299 #endif
300
301 if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) {
302 printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs);
303 printf("recov %d:", src_err_list[i]);
304 dump(temp_buff, 25);
305 printf("orig :");
306 dump(buffs[src_err_list[i]], 25);
307 return -1;
308 }
309 }
310
311 // Do more random tests
312
313 for (rtest = 0; rtest < RANDOMS; rtest++) {
314 while ((m = (rand() % MMAX)) < 2) ;
315 while ((k = (rand() % KMAX)) >= m || k < 1) ;
316
317 if (m > MMAX || k > KMAX)
318 continue;
319
320 gf_gen_rs_matrix(a, m, k);
321
322 // Make random data
323 for (i = 0; i < k; i++)
324 for (j = 0; j < TEST_LEN; j++)
325 buffs[i][j] = rand();
326
327 // Make parity vects
328 for (i = k; i < m; i++) {
329 for (j = 0; j < k; j++)
330 gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]);
331 #ifndef USEREF
332 FUNCTION_UNDER_TEST(TEST_LEN, k, g_tbls, buffs, buffs[i]);
333 #else
334 gf_vect_dot_prod_base(TEST_LEN, k, &g_tbls[0], buffs, buffs[i]);
335 #endif
336 }
337
338 // Random errors
339 memset(src_in_err, 0, TEST_SOURCES);
340 for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) {
341 err = 1 & rand();
342 src_in_err[i] = err;
343 if (err)
344 src_err_list[nerrs++] = i;
345 }
346 if (nerrs == 0) { // should have at least one error
347 while ((err = (rand() % KMAX)) >= k) ;
348 src_err_list[nerrs++] = err;
349 src_in_err[err] = 1;
350 }
351 // construct b by removing error rows
352 for (i = 0, r = 0; i < k; i++, r++) {
353 while (src_in_err[r]) {
354 r++;
355 continue;
356 }
357 for (j = 0; j < k; j++)
358 b[k * i + j] = a[k * r + j];
359 }
360
361 if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0)
362 printf("BAD MATRIX\n");
363
364 for (i = 0, r = 0; i < k; i++, r++) {
365 while (src_in_err[r]) {
366 r++;
367 continue;
368 }
369 recov[i] = buffs[r];
370 }
371
372 // Recover data
373 for (i = 0; i < nerrs; i++) {
374 for (j = 0; j < k; j++)
375 gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]);
376 #ifndef USEREF
377 FUNCTION_UNDER_TEST(TEST_LEN, k, g_tbls, recov, temp_buff);
378 #else
379 gf_vect_dot_prod_base(TEST_LEN, k, &g_tbls[0], recov, temp_buff);
380 #endif
381 if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) {
382 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs);
383 printf(" - erase list = ");
384 for (i = 0; i < nerrs; i++)
385 printf(" %d", src_err_list[i]);
386 printf("\na:\n");
387 dump_u8xu8((u8 *) a, m, k);
388 printf("inv b:\n");
389 dump_u8xu8((u8 *) d, k, k);
390 printf("orig data:\n");
391 dump_matrix(buffs, m, 25);
392 printf("orig :");
393 dump(buffs[src_err_list[i]], 25);
394 printf("recov %d:", src_err_list[i]);
395 dump(temp_buff, 25);
396 return -1;
397 }
398 }
399 putchar('.');
400 }
401
402 // Run tests at end of buffer for Electric Fence
403 align = (LEN_ALIGN_CHK_B != 0) ? 1 : 16;
404 for (size = TEST_MIN_SIZE; size <= TEST_SIZE; size += align) {
405 for (i = 0; i < TEST_SOURCES; i++)
406 for (j = 0; j < TEST_LEN; j++)
407 buffs[i][j] = rand();
408
409 for (i = 0; i < TEST_SOURCES; i++) // Line up TEST_SIZE from end
410 efence_buffs[i] = buffs[i] + TEST_LEN - size;
411
412 for (i = 0; i < TEST_SOURCES; i++)
413 g[i] = rand();
414
415 for (i = 0; i < TEST_SOURCES; i++)
416 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
417
418 gf_vect_dot_prod_base(size, TEST_SOURCES, &g_tbls[0], efence_buffs, dest_ref);
419 FUNCTION_UNDER_TEST(size, TEST_SOURCES, g_tbls, efence_buffs, dest);
420
421 if (0 != memcmp(dest_ref, dest, size)) {
422 printf("Fail rand " xstr(FUNCTION_UNDER_TEST) " test 3\n");
423 dump_matrix(efence_buffs, 5, TEST_SOURCES);
424 printf("dprod_base:");
425 dump(dest_ref, align);
426 printf("dprod:");
427 dump(dest, align);
428 return -1;
429 }
430
431 putchar('.');
432 }
433
434 // Test rand ptr alignment if available
435
436 for (rtest = 0; rtest < RANDOMS; rtest++) {
437 size = (TEST_LEN - PTR_ALIGN_CHK_B) & ~(TEST_MIN_SIZE - 1);
438 srcs = rand() % TEST_SOURCES;
439 if (srcs == 0)
440 continue;
441
442 offset = (PTR_ALIGN_CHK_B != 0) ? 1 : PTR_ALIGN_CHK_B;
443 // Add random offsets
444 for (i = 0; i < srcs; i++)
445 ubuffs[i] = buffs[i] + (rand() & (PTR_ALIGN_CHK_B - offset));
446
447 udest_ptr = dest + (rand() & (PTR_ALIGN_CHK_B - offset));
448
449 memset(dest, 0, TEST_LEN); // zero pad to check write-over
450
451 for (i = 0; i < srcs; i++)
452 for (j = 0; j < size; j++)
453 ubuffs[i][j] = rand();
454
455 for (i = 0; i < srcs; i++)
456 g[i] = rand();
457
458 for (i = 0; i < srcs; i++)
459 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
460
461 gf_vect_dot_prod_base(size, srcs, &g_tbls[0], ubuffs, dest_ref);
462
463 FUNCTION_UNDER_TEST(size, srcs, g_tbls, ubuffs, udest_ptr);
464
465 if (memcmp(dest_ref, udest_ptr, size)) {
466 printf("Fail rand " xstr(FUNCTION_UNDER_TEST) " ualign srcs=%d\n",
467 srcs);
468 dump_matrix(ubuffs, 5, TEST_SOURCES);
469 printf("dprod_base:");
470 dump(dest_ref, 25);
471 printf("dprod:");
472 dump(udest_ptr, 25);
473 return -1;
474 }
475 // Confirm that padding around dests is unchanged
476 memset(dest_ref, 0, PTR_ALIGN_CHK_B); // Make reference zero buff
477 offset = udest_ptr - dest;
478
479 if (memcmp(dest, dest_ref, offset)) {
480 printf("Fail rand ualign pad start\n");
481 return -1;
482 }
483 if (memcmp(dest + offset + size, dest_ref, PTR_ALIGN_CHK_B - offset)) {
484 printf("Fail rand ualign pad end\n");
485 return -1;
486 }
487
488 putchar('.');
489 }
490
491 // Test all size alignment
492 align = (LEN_ALIGN_CHK_B != 0) ? 1 : 16;
493
494 for (size = TEST_LEN; size >= TEST_MIN_SIZE; size -= align) {
495 srcs = TEST_SOURCES;
496
497 for (i = 0; i < srcs; i++)
498 for (j = 0; j < size; j++)
499 buffs[i][j] = rand();
500
501 for (i = 0; i < srcs; i++)
502 g[i] = rand();
503
504 for (i = 0; i < srcs; i++)
505 gf_vect_mul_init(g[i], &g_tbls[i * 32]);
506
507 gf_vect_dot_prod_base(size, srcs, &g_tbls[0], buffs, dest_ref);
508
509 FUNCTION_UNDER_TEST(size, srcs, g_tbls, buffs, dest);
510
511 if (memcmp(dest_ref, dest, size)) {
512 printf("Fail rand " xstr(FUNCTION_UNDER_TEST) " ualign len=%d\n",
513 size);
514 dump_matrix(buffs, 5, TEST_SOURCES);
515 printf("dprod_base:");
516 dump(dest_ref, 25);
517 printf("dprod:");
518 dump(dest, 25);
519 return -1;
520 }
521 }
522
523 printf("done all: Pass\n");
524 return 0;
525 }
Ceph