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