2 * Copyright (C) 2013 Andrea Mazzoleni
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
21 * Binomial coefficient of n over r.
23 static int ibc(int n, int r)
28 return ibc(n - 1, r - 1) + ibc(n - 1, r);
34 static int ipow(int n, int r)
45 int raid_test_combo(void)
49 int p[RAID_PARITY_MAX];
51 for (r = 1; r <= RAID_PARITY_MAX; ++r) {
52 /* count combination (r of RAID_PARITY_MAX) elements */
54 combination_first(r, RAID_PARITY_MAX, p);
58 } while (combination_next(r, RAID_PARITY_MAX, p));
60 if (count != ibc(RAID_PARITY_MAX, r)) {
67 for (r = 1; r <= RAID_PARITY_MAX; ++r) {
68 /* count permutation (r of RAID_PARITY_MAX) elements */
70 permutation_first(r, RAID_PARITY_MAX, p);
74 } while (permutation_next(r, RAID_PARITY_MAX, p));
76 if (count != ipow(RAID_PARITY_MAX, r)) {
86 int raid_test_insert(void)
88 int p[RAID_PARITY_MAX];
91 for (r = 1; r <= RAID_PARITY_MAX; ++r) {
92 permutation_first(r, RAID_PARITY_MAX, p);
94 int i[RAID_PARITY_MAX];
98 for (j = 0; j < r; ++j)
99 raid_insert(j, i, p[j]);
102 for (j = 1; j < r; ++j) {
103 if (i[j - 1] > i[j]) {
104 /* LCOV_EXCL_START */
109 } while (permutation_next(r, RAID_PARITY_MAX, p));
115 int raid_test_sort(void)
117 int p[RAID_PARITY_MAX];
120 for (r = 1; r <= RAID_PARITY_MAX; ++r) {
121 permutation_first(r, RAID_PARITY_MAX, p);
123 int i[RAID_PARITY_MAX];
127 for (j = 0; j < r; ++j)
133 for (j = 1; j < r; ++j) {
134 if (i[j - 1] > i[j]) {
135 /* LCOV_EXCL_START */
140 } while (permutation_next(r, RAID_PARITY_MAX, p));
146 int raid_test_rec(int mode, int nd, size_t size)
148 void (*f[RAID_PARITY_MAX][4])(
149 int nr, int *id, int *ip, int nd, size_t size, void **vbuf);
155 void *data_save[RAID_PARITY_MAX];
156 void *parity_save[RAID_PARITY_MAX];
159 int id[RAID_PARITY_MAX];
160 int ip[RAID_PARITY_MAX];
164 int nf[RAID_PARITY_MAX];
168 if (mode == RAID_MODE_CAUCHY)
169 np = RAID_PARITY_MAX;
173 nv = nd + np * 2 + 2;
175 v = raid_malloc_vector(nd, nv, size, &v_alloc);
177 /* LCOV_EXCL_START */
186 for (i = 0; i < np; ++i)
187 parity_save[i] = parity[i];
189 memset(v[nv - 2], 0, size);
190 raid_zero(v[nv - 2]);
194 /* fill with pseudo-random data with the arbitrary seed "1" */
195 raid_mrand_vector(1, nd, size, v);
197 /* setup recov functions */
198 for (i = 0; i < np; ++i) {
201 f[i][nf[i]++] = raid_rec1_int8;
204 if (raid_cpu_has_ssse3())
205 f[i][nf[i]++] = raid_rec1_ssse3;
208 if (raid_cpu_has_avx2())
209 f[i][nf[i]++] = raid_rec1_avx2;
213 f[i][nf[i]++] = raid_rec2_int8;
216 if (raid_cpu_has_ssse3())
217 f[i][nf[i]++] = raid_rec2_ssse3;
220 if (raid_cpu_has_avx2())
221 f[i][nf[i]++] = raid_rec2_avx2;
225 f[i][nf[i]++] = raid_recX_int8;
228 if (raid_cpu_has_ssse3())
229 f[i][nf[i]++] = raid_recX_ssse3;
232 if (raid_cpu_has_avx2())
233 f[i][nf[i]++] = raid_recX_avx2;
239 /* compute the parity */
240 raid_gen_ref(nd, np, size, v);
242 /* set all the parity to the waste v */
243 for (i = 0; i < np; ++i)
246 /* all parity levels */
247 for (nr = 1; nr <= np; ++nr) {
248 /* all combinations (nr of nd) disks */
249 combination_first(nr, nd, id);
251 /* all combinations (nr of np) parities */
252 combination_first(nr, np, ip);
254 /* for each recover function */
255 for (j = 0; j < nf[nr - 1]; ++j) {
257 for (i = 0; i < nr; ++i) {
258 /* remove the missing data */
259 data_save[i] = data[id[i]];
260 data[id[i]] = test[i];
261 /* set the parity to use */
262 parity[ip[i]] = parity_save[ip[i]];
266 f[nr - 1][j](nr, id, ip, nd, size, v);
269 for (i = 0; i < nr; ++i) {
270 if (memcmp(test[i], data_save[i], size) != 0) {
271 /* LCOV_EXCL_START */
278 for (i = 0; i < nr; ++i) {
279 /* restore the data */
280 data[id[i]] = data_save[i];
281 /* restore the parity */
282 parity[ip[i]] = waste;
285 } while (combination_next(nr, np, ip));
286 } while (combination_next(nr, nd, id));
294 /* LCOV_EXCL_START */
301 int raid_test_par(int mode, int nd, size_t size)
303 void (*f[64])(int nd, size_t size, void **vbuf);
312 if (mode == RAID_MODE_CAUCHY)
313 np = RAID_PARITY_MAX;
319 v = raid_malloc_vector(nd, nv, size, &v_alloc);
321 /* LCOV_EXCL_START */
327 if (raid_mtest_vector(nv, size, v) != 0) {
328 /* LCOV_EXCL_START */
333 /* fill with pseudo-random data with the arbitrary seed "2" */
334 raid_mrand_vector(2, nv, size, v);
336 /* compute the parity */
337 raid_gen_ref(nd, np, size, v);
339 /* copy in back buffers */
340 for (i = 0; i < np; ++i)
341 memcpy(v[nd + np + i], v[nd + i], size);
343 /* load all the available functions */
346 f[nf++] = raid_gen1_int32;
347 f[nf++] = raid_gen1_int64;
348 f[nf++] = raid_gen2_int32;
349 f[nf++] = raid_gen2_int64;
353 if (raid_cpu_has_sse2()) {
354 f[nf++] = raid_gen1_sse2;
355 f[nf++] = raid_gen2_sse2;
357 f[nf++] = raid_gen2_sse2ext;
363 if (raid_cpu_has_avx2()) {
364 f[nf++] = raid_gen1_avx2;
365 f[nf++] = raid_gen2_avx2;
368 #endif /* CONFIG_X86 */
370 if (mode == RAID_MODE_CAUCHY) {
371 f[nf++] = raid_gen3_int8;
372 f[nf++] = raid_gen4_int8;
373 f[nf++] = raid_gen5_int8;
374 f[nf++] = raid_gen6_int8;
378 if (raid_cpu_has_ssse3()) {
379 f[nf++] = raid_gen3_ssse3;
380 f[nf++] = raid_gen4_ssse3;
381 f[nf++] = raid_gen5_ssse3;
382 f[nf++] = raid_gen6_ssse3;
384 f[nf++] = raid_gen3_ssse3ext;
385 f[nf++] = raid_gen4_ssse3ext;
386 f[nf++] = raid_gen5_ssse3ext;
387 f[nf++] = raid_gen6_ssse3ext;
394 if (raid_cpu_has_avx2()) {
395 f[nf++] = raid_gen3_avx2ext;
396 f[nf++] = raid_gen4_avx2ext;
397 f[nf++] = raid_gen5_avx2ext;
398 f[nf++] = raid_gen6_avx2ext;
402 #endif /* CONFIG_X86 */
404 f[nf++] = raid_genz_int32;
405 f[nf++] = raid_genz_int64;
409 if (raid_cpu_has_sse2()) {
410 f[nf++] = raid_genz_sse2;
412 f[nf++] = raid_genz_sse2ext;
419 if (raid_cpu_has_avx2())
420 f[nf++] = raid_genz_avx2ext;
423 #endif /* CONFIG_X86 */
426 /* check all the functions */
427 for (j = 0; j < nf; ++j) {
432 for (i = 0; i < np; ++i) {
433 if (memcmp(v[nd + np + i], v[nd + i], size) != 0) {
434 /* LCOV_EXCL_START */
446 /* LCOV_EXCL_START */