Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : // Copyright (C) 2013 Andrea Mazzoleni
3 :
4 : #include "internal.h"
5 : #include "cpu.h"
6 : #include "combo.h"
7 : #include "memory.h"
8 :
9 : /**
10 : * Binomial coefficient of n over r.
11 : */
12 120 : static int ibc(int n, int r)
13 : {
14 120 : if (r == 0 || n == r)
15 63 : return 1;
16 : else
17 57 : return ibc(n - 1, r - 1) + ibc(n - 1, r);
18 : }
19 :
20 : /**
21 : * Power n ^ r;
22 : */
23 6 : static int ipow(int n, int r)
24 : {
25 6 : int v = 1;
26 :
27 27 : while (r) {
28 21 : v *= n;
29 21 : --r;
30 : }
31 6 : return v;
32 : }
33 :
34 1 : int raid_test_combo(void)
35 : {
36 : int r;
37 : int count;
38 : int p[RAID_PARITY_MAX];
39 :
40 7 : for (r = 1; r <= RAID_PARITY_MAX; ++r) {
41 : /* count combination (r of RAID_PARITY_MAX) elements */
42 6 : count = 0;
43 : combination_first(r, RAID_PARITY_MAX, p);
44 :
45 : do {
46 63 : ++count;
47 63 : } while (combination_next(r, RAID_PARITY_MAX, p));
48 :
49 6 : if (count != ibc(RAID_PARITY_MAX, r)) {
50 : /* LCOV_EXCL_START */
51 : return -1;
52 : /* LCOV_EXCL_STOP */
53 : }
54 : }
55 :
56 7 : for (r = 1; r <= RAID_PARITY_MAX; ++r) {
57 : /* count permutation (r of RAID_PARITY_MAX) elements */
58 6 : count = 0;
59 : permutation_first(r, RAID_PARITY_MAX, p);
60 :
61 : do {
62 55986 : ++count;
63 55986 : } while (permutation_next(r, RAID_PARITY_MAX, p));
64 :
65 6 : if (count != ipow(RAID_PARITY_MAX, r)) {
66 : /* LCOV_EXCL_START */
67 : return -1;
68 : /* LCOV_EXCL_STOP */
69 : }
70 : }
71 :
72 1 : return 0;
73 : }
74 :
75 1 : int raid_test_insert(void)
76 : {
77 : int p[RAID_PARITY_MAX];
78 : int r;
79 :
80 7 : for (r = 1; r <= RAID_PARITY_MAX; ++r) {
81 : permutation_first(r, RAID_PARITY_MAX, p);
82 : do {
83 : int i[RAID_PARITY_MAX];
84 : int j;
85 :
86 : /* insert in order */
87 380712 : for (j = 0; j < r; ++j)
88 324726 : raid_insert(j, i, p[j]);
89 :
90 : /* check order */
91 324726 : for (j = 1; j < r; ++j) {
92 268740 : if (i[j - 1] > i[j]) {
93 : /* LCOV_EXCL_START */
94 : return -1;
95 : /* LCOV_EXCL_STOP */
96 : }
97 : }
98 55986 : } while (permutation_next(r, RAID_PARITY_MAX, p));
99 : }
100 :
101 1 : return 0;
102 : }
103 :
104 1 : int raid_test_sort(void)
105 : {
106 : int p[RAID_PARITY_MAX];
107 : int r;
108 :
109 7 : for (r = 1; r <= RAID_PARITY_MAX; ++r) {
110 : permutation_first(r, RAID_PARITY_MAX, p);
111 : do {
112 : int i[RAID_PARITY_MAX];
113 : int j;
114 :
115 : /* make a copy */
116 380712 : for (j = 0; j < r; ++j)
117 324726 : i[j] = p[j];
118 :
119 55986 : raid_sort(r, i);
120 :
121 : /* check order */
122 324726 : for (j = 1; j < r; ++j) {
123 268740 : if (i[j - 1] > i[j]) {
124 : /* LCOV_EXCL_START */
125 : return -1;
126 : /* LCOV_EXCL_STOP */
127 : }
128 : }
129 55986 : } while (permutation_next(r, RAID_PARITY_MAX, p));
130 : }
131 :
132 1 : return 0;
133 : }
134 :
135 2 : int raid_test_rec(int mode, int nd, size_t size)
136 : {
137 : void (*f[RAID_PARITY_MAX][4])(
138 : int nr, int *id, int *ip, int nd, size_t size, void **vbuf);
139 : void *v_alloc;
140 : void **v;
141 : void **data;
142 : void **parity;
143 : void **test;
144 : void *data_save[RAID_PARITY_MAX];
145 : void *parity_save[RAID_PARITY_MAX];
146 : void *waste;
147 : int nv;
148 : int id[RAID_PARITY_MAX];
149 : int ip[RAID_PARITY_MAX];
150 : int i;
151 : int j;
152 : int nr;
153 : int nf[RAID_PARITY_MAX];
154 : int np;
155 :
156 2 : raid_mode(mode);
157 2 : if (mode == RAID_MODE_CAUCHY)
158 1 : np = RAID_PARITY_MAX;
159 : else
160 1 : np = 3;
161 :
162 2 : nv = nd + np * 2 + 2;
163 :
164 2 : v = raid_malloc_vector(nd, nv, size, &v_alloc);
165 2 : if (!v) {
166 : /* LCOV_EXCL_START */
167 : return -1;
168 : /* LCOV_EXCL_STOP */
169 : }
170 :
171 2 : data = v;
172 2 : parity = v + nd;
173 2 : test = v + nd + np;
174 :
175 11 : for (i = 0; i < np; ++i)
176 9 : parity_save[i] = parity[i];
177 :
178 2 : memset(v[nv - 2], 0, size);
179 2 : raid_zero(v[nv - 2]);
180 :
181 2 : waste = v[nv - 1];
182 :
183 : /* fill with pseudo-random data with the arbitrary seed "1" */
184 2 : raid_mrand_vector(1, nd, size, v);
185 :
186 : /* setup recov functions */
187 11 : for (i = 0; i < np; ++i) {
188 9 : nf[i] = 0;
189 9 : if (i == 0) {
190 2 : f[i][nf[i]++] = raid_rec1_int8;
191 : #ifdef CONFIG_X86
192 : #ifdef CONFIG_SSSE3
193 2 : if (raid_cpu_has_ssse3())
194 2 : f[i][nf[i]++] = raid_rec1_ssse3;
195 : #endif
196 : #ifdef CONFIG_AVX2
197 2 : if (raid_cpu_has_avx2())
198 2 : f[i][nf[i]++] = raid_rec1_avx2;
199 : #endif
200 : #endif
201 : #ifdef CONFIG_X86_64
202 : #ifdef CONFIG_AVX512BW
203 2 : if (raid_cpu_has_avx512bw())
204 2 : f[i][nf[i]++] = raid_rec1_avx512bw;
205 : #endif
206 : #endif
207 7 : } else if (i == 1) {
208 2 : f[i][nf[i]++] = raid_rec2_int8;
209 : #ifdef CONFIG_X86
210 : #ifdef CONFIG_SSSE3
211 2 : if (raid_cpu_has_ssse3())
212 2 : f[i][nf[i]++] = raid_rec2_ssse3;
213 : #endif
214 : #ifdef CONFIG_AVX2
215 2 : if (raid_cpu_has_avx2())
216 2 : f[i][nf[i]++] = raid_rec2_avx2;
217 : #endif
218 : #endif
219 : #ifdef CONFIG_X86_64
220 : #ifdef CONFIG_AVX512BW
221 2 : if (raid_cpu_has_avx512bw())
222 2 : f[i][nf[i]++] = raid_rec2_avx512bw;
223 : #endif
224 : #endif
225 : } else {
226 5 : f[i][nf[i]++] = raid_recX_int8;
227 : #ifdef CONFIG_X86
228 : #ifdef CONFIG_SSSE3
229 5 : if (raid_cpu_has_ssse3())
230 5 : f[i][nf[i]++] = raid_recX_ssse3;
231 : #endif
232 : #ifdef CONFIG_AVX2
233 5 : if (raid_cpu_has_avx2())
234 5 : f[i][nf[i]++] = raid_recX_avx2;
235 : #endif
236 : #endif
237 : #ifdef CONFIG_X86_64
238 : #ifdef CONFIG_AVX512BW
239 5 : if (raid_cpu_has_avx512bw())
240 5 : f[i][nf[i]++] = raid_recX_avx512bw;
241 : #endif
242 : #endif
243 : }
244 : }
245 :
246 : /* compute the parity */
247 2 : raid_gen_ref(nd, np, size, v);
248 :
249 : /* set all the parity to the waste v */
250 11 : for (i = 0; i < np; ++i)
251 9 : parity[i] = waste;
252 :
253 : /* all parity levels */
254 11 : for (nr = 1; nr <= np; ++nr) {
255 : /* all combinations (nr of nd) disks */
256 : combination_first(nr, nd, id);
257 : do {
258 : /* all combinations (nr of np) parities */
259 : combination_first(nr, np, ip);
260 : do {
261 : /* for each recover function */
262 95085 : for (j = 0; j < nf[nr - 1]; ++j) {
263 : /* set */
264 377460 : for (i = 0; i < nr; ++i) {
265 : /* remove the missing data */
266 301392 : data_save[i] = data[id[i]];
267 301392 : data[id[i]] = test[i];
268 : /* set the parity to use */
269 301392 : parity[ip[i]] = parity_save[ip[i]];
270 : }
271 :
272 : /* recover */
273 76068 : f[nr - 1][j](nr, id, ip, nd, size, v);
274 :
275 : /* check */
276 377460 : for (i = 0; i < nr; ++i) {
277 301392 : if (memcmp(test[i], data_save[i], size) != 0) {
278 : /* LCOV_EXCL_START */
279 : goto bail;
280 : /* LCOV_EXCL_STOP */
281 : }
282 : }
283 :
284 : /* restore */
285 377460 : for (i = 0; i < nr; ++i) {
286 : /* restore the data */
287 301392 : data[id[i]] = data_save[i];
288 : /* restore the parity */
289 301392 : parity[ip[i]] = waste;
290 : }
291 : }
292 19017 : } while (combination_next(nr, np, ip));
293 2807 : } while (combination_next(nr, nd, id));
294 : }
295 :
296 2 : free(v_alloc);
297 2 : free(v);
298 2 : return 0;
299 :
300 0 : bail:
301 : /* LCOV_EXCL_START */
302 : free(v_alloc);
303 : free(v);
304 : return -1;
305 : /* LCOV_EXCL_STOP */
306 : }
307 :
308 3 : int raid_test_par(int mode, int nd, size_t size)
309 : {
310 : void (*f[64])(int nd, size_t size, void **vbuf);
311 : void *v_alloc;
312 : void **v;
313 : int nv;
314 : int i, j;
315 : int nf;
316 : int np;
317 :
318 3 : raid_mode(mode);
319 3 : if (mode == RAID_MODE_CAUCHY)
320 2 : np = RAID_PARITY_MAX;
321 : else
322 1 : np = 3;
323 :
324 3 : nv = nd + np * 2;
325 :
326 3 : v = raid_malloc_vector(nd, nv, size, &v_alloc);
327 3 : if (!v) {
328 : /* LCOV_EXCL_START */
329 : return -1;
330 : /* LCOV_EXCL_STOP */
331 : }
332 :
333 : /* check memory */
334 3 : if (raid_mtest_vector(nv, size, v) != 0) {
335 : /* LCOV_EXCL_START */
336 : goto bail;
337 : /* LCOV_EXCL_STOP */
338 : }
339 :
340 : /* fill with pseudo-random data with the arbitrary seed "2" */
341 3 : raid_mrand_vector(2, nv, size, v);
342 :
343 : /* compute the parity */
344 3 : raid_gen_ref(nd, np, size, v);
345 :
346 : /* copy in back buffers */
347 18 : for (i = 0; i < np; ++i)
348 15 : memcpy(v[nd + np + i], v[nd + i], size);
349 :
350 : /* load all the available functions */
351 3 : nf = 0;
352 :
353 3 : f[nf++] = raid_gen1_int32;
354 3 : f[nf++] = raid_gen1_int64;
355 3 : f[nf++] = raid_gen2_int32;
356 3 : f[nf++] = raid_gen2_int64;
357 :
358 : #ifdef CONFIG_X86
359 : #ifdef CONFIG_SSE2
360 3 : if (raid_cpu_has_sse2()) {
361 3 : f[nf++] = raid_gen1_sse2;
362 3 : f[nf++] = raid_gen2_sse2;
363 : #ifdef CONFIG_X86_64
364 3 : f[nf++] = raid_gen2_sse2ext;
365 : #endif
366 : }
367 : #endif
368 :
369 : #ifdef CONFIG_AVX2
370 3 : if (raid_cpu_has_avx2()) {
371 3 : f[nf++] = raid_gen1_avx2;
372 3 : f[nf++] = raid_gen2_avx2;
373 : }
374 : #endif
375 :
376 : #ifdef CONFIG_AVX512BW
377 : #ifdef CONFIG_X86_64
378 3 : if (raid_cpu_has_avx512bw()) {
379 3 : f[nf++] = raid_gen1_avx512bw;
380 3 : f[nf++] = raid_gen2_avx512bw;
381 : }
382 : #endif
383 : #endif
384 : #endif /* CONFIG_X86 */
385 :
386 3 : if (mode == RAID_MODE_CAUCHY) {
387 2 : f[nf++] = raid_gen3_int8;
388 2 : f[nf++] = raid_gen4_int8;
389 2 : f[nf++] = raid_gen5_int8;
390 2 : f[nf++] = raid_gen6_int8;
391 :
392 : #ifdef CONFIG_X86
393 : #ifdef CONFIG_SSSE3
394 2 : if (raid_cpu_has_ssse3()) {
395 2 : f[nf++] = raid_gen3_ssse3;
396 2 : f[nf++] = raid_gen4_ssse3;
397 2 : f[nf++] = raid_gen5_ssse3;
398 2 : f[nf++] = raid_gen6_ssse3;
399 : #ifdef CONFIG_X86_64
400 2 : f[nf++] = raid_gen3_ssse3ext;
401 2 : f[nf++] = raid_gen4_ssse3ext;
402 2 : f[nf++] = raid_gen5_ssse3ext;
403 2 : f[nf++] = raid_gen6_ssse3ext;
404 : #endif
405 : }
406 : #endif
407 :
408 : #ifdef CONFIG_AVX2
409 : #ifdef CONFIG_X86_64
410 2 : if (raid_cpu_has_avx2()) {
411 2 : f[nf++] = raid_gen3_avx2ext;
412 2 : f[nf++] = raid_gen4_avx2ext;
413 2 : f[nf++] = raid_gen5_avx2ext;
414 2 : f[nf++] = raid_gen6_avx2ext;
415 : }
416 : #endif
417 : #endif
418 :
419 : #ifdef CONFIG_AVX512BW
420 : #ifdef CONFIG_X86_64
421 2 : if (raid_cpu_has_avx512bw()) {
422 2 : f[nf++] = raid_gen3_avx512bw;
423 2 : f[nf++] = raid_gen4_avx512bw;
424 2 : f[nf++] = raid_gen5_avx512bw;
425 2 : f[nf++] = raid_gen6_avx512bw;
426 : }
427 : #endif
428 : #endif
429 :
430 : #endif /* CONFIG_X86 */
431 : } else {
432 1 : f[nf++] = raid_genz_int32;
433 1 : f[nf++] = raid_genz_int64;
434 :
435 : #ifdef CONFIG_X86
436 : #ifdef CONFIG_SSE2
437 1 : if (raid_cpu_has_sse2()) {
438 1 : f[nf++] = raid_genz_sse2;
439 : #ifdef CONFIG_X86_64
440 1 : f[nf++] = raid_genz_sse2ext;
441 : #endif
442 : }
443 : #endif
444 :
445 : #ifdef CONFIG_AVX2
446 : #ifdef CONFIG_X86_64
447 1 : if (raid_cpu_has_avx2())
448 1 : f[nf++] = raid_genz_avx2ext;
449 : #endif
450 : #endif
451 : #endif /* CONFIG_X86 */
452 : }
453 :
454 : /* check all the functions */
455 81 : for (j = 0; j < nf; ++j) {
456 : /* compute parity */
457 78 : f[j](nd, size, v);
458 :
459 : /* check it */
460 498 : for (i = 0; i < np; ++i) {
461 420 : if (memcmp(v[nd + np + i], v[nd + i], size) != 0) {
462 : /* LCOV_EXCL_START */
463 : goto bail;
464 : /* LCOV_EXCL_STOP */
465 : }
466 : }
467 : }
468 :
469 3 : free(v_alloc);
470 3 : free(v);
471 3 : return 0;
472 :
473 0 : bail:
474 : /* LCOV_EXCL_START */
475 : free(v_alloc);
476 : free(v);
477 : return -1;
478 : /* LCOV_EXCL_STOP */
479 : }
480 :
|
