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 "memory.h"
17 : #include "cpu.h"
18 :
19 : /*
20 : * Initializes and selects the best algorithm.
21 : */
22 271 : void raid_init(void)
23 : {
24 271 : raid_gen3_ptr = raid_gen3_int8;
25 271 : raid_gen_ptr[3] = raid_gen4_int8;
26 271 : raid_gen_ptr[4] = raid_gen5_int8;
27 271 : raid_gen_ptr[5] = raid_gen6_int8;
28 :
29 : if (sizeof(void *) == 4) {
30 : raid_gen_ptr[0] = raid_gen1_int32;
31 : raid_gen_ptr[1] = raid_gen2_int32;
32 : raid_genz_ptr = raid_genz_int32;
33 : } else {
34 271 : raid_gen_ptr[0] = raid_gen1_int64;
35 271 : raid_gen_ptr[1] = raid_gen2_int64;
36 271 : raid_genz_ptr = raid_genz_int64;
37 : }
38 :
39 271 : raid_rec_ptr[0] = raid_rec1_int8;
40 271 : raid_rec_ptr[1] = raid_rec2_int8;
41 271 : raid_rec_ptr[2] = raid_recX_int8;
42 271 : raid_rec_ptr[3] = raid_recX_int8;
43 271 : raid_rec_ptr[4] = raid_recX_int8;
44 271 : raid_rec_ptr[5] = raid_recX_int8;
45 :
46 : #ifdef CONFIG_X86
47 : #ifdef CONFIG_SSE2
48 271 : if (raid_cpu_has_sse2()) {
49 271 : raid_gen_ptr[0] = raid_gen1_sse2;
50 : #ifdef CONFIG_X86_64
51 271 : if (raid_cpu_has_slowextendedreg()) {
52 0 : raid_gen_ptr[1] = raid_gen2_sse2;
53 : } else {
54 271 : raid_gen_ptr[1] = raid_gen2_sse2ext;
55 : }
56 : /* note that raid_cpu_has_slowextendedreg() doesn't affect parz */
57 271 : raid_genz_ptr = raid_genz_sse2ext;
58 : #else
59 : raid_gen_ptr[1] = raid_gen2_sse2;
60 : raid_genz_ptr = raid_genz_sse2;
61 : #endif
62 : }
63 : #endif
64 :
65 : #ifdef CONFIG_SSSE3
66 271 : if (raid_cpu_has_ssse3()) {
67 : #ifdef CONFIG_X86_64
68 270 : if (raid_cpu_has_slowextendedreg()) {
69 0 : raid_gen3_ptr = raid_gen3_ssse3;
70 0 : raid_gen_ptr[3] = raid_gen4_ssse3;
71 0 : raid_gen_ptr[4] = raid_gen5_ssse3;
72 0 : raid_gen_ptr[5] = raid_gen6_ssse3;
73 : } else {
74 270 : raid_gen3_ptr = raid_gen3_ssse3ext;
75 270 : raid_gen_ptr[3] = raid_gen4_ssse3ext;
76 270 : raid_gen_ptr[4] = raid_gen5_ssse3ext;
77 270 : raid_gen_ptr[5] = raid_gen6_ssse3ext;
78 : }
79 : #else
80 : raid_gen3_ptr = raid_gen3_ssse3;
81 : raid_gen_ptr[3] = raid_gen4_ssse3;
82 : raid_gen_ptr[4] = raid_gen5_ssse3;
83 : raid_gen_ptr[5] = raid_gen6_ssse3;
84 : #endif
85 270 : raid_rec_ptr[0] = raid_rec1_ssse3;
86 270 : raid_rec_ptr[1] = raid_rec2_ssse3;
87 270 : raid_rec_ptr[2] = raid_recX_ssse3;
88 270 : raid_rec_ptr[3] = raid_recX_ssse3;
89 270 : raid_rec_ptr[4] = raid_recX_ssse3;
90 270 : raid_rec_ptr[5] = raid_recX_ssse3;
91 : }
92 : #endif
93 :
94 : #ifdef CONFIG_AVX2
95 271 : if (raid_cpu_has_avx2()) {
96 2 : raid_gen_ptr[0] = raid_gen1_avx2;
97 2 : raid_gen_ptr[1] = raid_gen2_avx2;
98 : #ifdef CONFIG_X86_64
99 2 : raid_gen3_ptr = raid_gen3_avx2ext;
100 2 : raid_genz_ptr = raid_genz_avx2ext;
101 2 : raid_gen_ptr[3] = raid_gen4_avx2ext;
102 2 : raid_gen_ptr[4] = raid_gen5_avx2ext;
103 2 : raid_gen_ptr[5] = raid_gen6_avx2ext;
104 : #endif
105 2 : raid_rec_ptr[0] = raid_rec1_avx2;
106 2 : raid_rec_ptr[1] = raid_rec2_avx2;
107 2 : raid_rec_ptr[2] = raid_recX_avx2;
108 2 : raid_rec_ptr[3] = raid_recX_avx2;
109 2 : raid_rec_ptr[4] = raid_recX_avx2;
110 2 : raid_rec_ptr[5] = raid_recX_avx2;
111 : }
112 : #endif
113 : #endif /* CONFIG_X86 */
114 :
115 : /* set the default mode */
116 271 : raid_mode(RAID_MODE_CAUCHY);
117 271 : }
118 :
119 : /*
120 : * Reference parity computation.
121 : */
122 6 : void raid_gen_ref(int nd, int np, size_t size, void **vv)
123 : {
124 6 : uint8_t **v = (uint8_t **)vv;
125 : size_t i;
126 :
127 5382 : for (i = 0; i < size; ++i) {
128 : uint8_t p[RAID_PARITY_MAX];
129 : int j, d;
130 :
131 36096 : for (j = 0; j < np; ++j)
132 30720 : p[j] = 0;
133 :
134 93696 : for (d = 0; d < nd; ++d) {
135 88320 : uint8_t b = v[d][i];
136 :
137 584448 : for (j = 0; j < np; ++j)
138 496128 : p[j] ^= gfmul[b][gfgen[j][d]];
139 : }
140 :
141 36096 : for (j = 0; j < np; ++j)
142 30720 : v[nd + j][i] = p[j];
143 : }
144 6 : }
145 :
146 : /*
147 : * Size of the blocks to test.
148 : */
149 : #define TEST_SIZE 4096
150 :
151 : /*
152 : * Number of data blocks to test.
153 : */
154 : #define TEST_COUNT (65536 / TEST_SIZE)
155 :
156 : /*
157 : * Parity generation test.
158 : */
159 6 : static int raid_test_par(int nd, int np, size_t size, void **v, void **ref)
160 : {
161 : int i;
162 : void *t[TEST_COUNT + RAID_PARITY_MAX];
163 :
164 : /* setup data */
165 102 : for (i = 0; i < nd; ++i)
166 96 : t[i] = ref[i];
167 :
168 : /* setup parity */
169 27 : for (i = 0; i < np; ++i)
170 21 : t[nd + i] = v[nd + i];
171 :
172 6 : raid_gen(nd, np, size, t);
173 :
174 : /* compare parity */
175 27 : for (i = 0; i < np; ++i) {
176 21 : if (memcmp(t[nd + i], ref[nd + i], size) != 0) {
177 : /* LCOV_EXCL_START */
178 : return -1;
179 : /* LCOV_EXCL_STOP */
180 : }
181 : }
182 :
183 6 : return 0;
184 : }
185 :
186 : /*
187 : * Recovering test.
188 : */
189 18 : static int raid_test_rec(int nr, int *ir, int nd, int np, size_t size, void **v, void **ref)
190 : {
191 : int i, j;
192 : void *t[TEST_COUNT + RAID_PARITY_MAX];
193 :
194 : /* setup data and parity vector */
195 369 : for (i = 0, j = 0; i < nd + np; ++i) {
196 351 : if (j < nr && ir[j] == i) {
197 : /* this block has to be recovered */
198 63 : t[i] = v[i];
199 63 : ++j;
200 : } else {
201 : /* this block is used for recovering */
202 288 : t[i] = ref[i];
203 : }
204 : }
205 :
206 18 : raid_rec(nr, ir, nd, np, size, t);
207 :
208 : /* compare all data and parity */
209 369 : for (i = 0; i < nd + np; ++i) {
210 351 : if (t[i] != ref[i]
211 63 : && memcmp(t[i], ref[i], size) != 0) {
212 : /* LCOV_EXCL_START */
213 : return -1;
214 : /* LCOV_EXCL_STOP */
215 : }
216 : }
217 :
218 18 : return 0;
219 : }
220 :
221 : /*
222 : * Recovering test for data.
223 : */
224 18 : static int raid_test_data(int nr, int *id, int *ip, int nd, int np, size_t size, void **v, void **ref)
225 : {
226 : int i, j;
227 : void *t[TEST_COUNT + RAID_PARITY_MAX];
228 :
229 : /* setup data vector */
230 306 : for (i = 0, j = 0; i < nd; ++i) {
231 288 : if (j < nr && id[j] == i) {
232 : /* this block has to be recovered */
233 39 : t[i] = v[i];
234 39 : ++j;
235 : } else {
236 : /* this block is left unchanged */
237 249 : t[i] = ref[i];
238 : }
239 : }
240 :
241 : /* setup parity vector */
242 81 : for (i = 0, j = 0; i < np; ++i) {
243 63 : if (j < nr && ip[j] == i) {
244 : /* this block is used for recovering */
245 39 : t[nd + i] = ref[nd + i];
246 39 : ++j;
247 : } else {
248 : /* this block should not be read or written */
249 24 : t[nd + i] = 0;
250 : }
251 : }
252 :
253 18 : raid_data(nr, id, ip, nd, size, t);
254 :
255 : /* compare all data and parity */
256 306 : for (i = 0; i < nd; ++i) {
257 288 : if (t[i] != ref[i]
258 39 : && t[i] != 0
259 39 : && memcmp(t[i], ref[i], size) != 0) {
260 : /* LCOV_EXCL_START */
261 : return -1;
262 : /* LCOV_EXCL_STOP */
263 : }
264 : }
265 :
266 18 : return 0;
267 : }
268 :
269 : /*
270 : * Scan test.
271 : */
272 7 : static int raid_test_scan(int nr, int *ir, int nd, int np, size_t size, void **v, void **ref)
273 : {
274 : int i, j, ret;
275 : void *t[TEST_COUNT + RAID_PARITY_MAX];
276 : int is[RAID_PARITY_MAX];
277 :
278 : /* setup data and parity vector */
279 140 : for (i = 0, j = 0; i < nd + np; ++i) {
280 133 : if (j < nr && ir[j] == i) {
281 : /* this block is bad */
282 15 : t[i] = v[i];
283 15 : ++j;
284 : } else {
285 : /* this block is used for recovering */
286 118 : t[i] = ref[i];
287 : }
288 : }
289 :
290 7 : ret = raid_scan(is, nd, np, size, t);
291 :
292 : /* compare identified bad blocks */
293 7 : if (ret != nr)
294 1 : return -1;
295 21 : for (i = 0; i < nr; ++i) {
296 15 : if (ir[i] != is[i]) {
297 : /* LCOV_EXCL_START */
298 : return -1;
299 : /* LCOV_EXCL_STOP */
300 : }
301 : }
302 :
303 6 : return 0;
304 : }
305 :
306 : /*
307 : * Basic functionality self test.
308 : */
309 1 : int raid_selftest(void)
310 1 : {
311 1 : const int nd = TEST_COUNT;
312 1 : const size_t size = TEST_SIZE;
313 1 : const int nv = nd + RAID_PARITY_MAX * 2 + 1;
314 : void *v_alloc;
315 : void **v;
316 1 : void *ref[nd + RAID_PARITY_MAX];
317 : int ir[RAID_PARITY_MAX];
318 : int ip[RAID_PARITY_MAX];
319 : int i, np;
320 1 : int ret = 0;
321 :
322 : /* ensure to have enough space for data */
323 1 : BUG_ON(nd * size > 65536);
324 :
325 1 : v = raid_malloc_vector(nd, nv, size, &v_alloc);
326 1 : if (!v) {
327 : /* LCOV_EXCL_START */
328 : return -1;
329 : /* LCOV_EXCL_STOP */
330 : }
331 :
332 1 : memset(v[nv - 1], 0, size);
333 1 : raid_zero(v[nv - 1]);
334 :
335 : /* use the multiplication table as data */
336 17 : for (i = 0; i < nd; ++i)
337 16 : ref[i] = ((uint8_t *)gfmul) + size * i;
338 :
339 : /* setup reference parity */
340 7 : for (i = 0; i < RAID_PARITY_MAX; ++i)
341 6 : ref[nd + i] = v[nd + RAID_PARITY_MAX + i];
342 :
343 : /* compute reference parity */
344 1 : raid_gen_ref(nd, RAID_PARITY_MAX, size, ref);
345 :
346 : /* test for each parity level */
347 7 : for (np = 1; np <= RAID_PARITY_MAX; ++np) {
348 : /* test parity generation */
349 6 : ret = raid_test_par(nd, np, size, v, ref);
350 6 : if (ret != 0) {
351 : /* LCOV_EXCL_START */
352 : goto bail;
353 : /* LCOV_EXCL_STOP */
354 : }
355 :
356 : /* test recovering with broken ending data disks */
357 27 : for (i = 0; i < np; ++i) {
358 : /* bad data */
359 21 : ir[i] = nd - np + i;
360 :
361 : /* good parity */
362 21 : ip[i] = i;
363 : }
364 :
365 6 : ret = raid_test_rec(np, ir, nd, np, size, v, ref);
366 6 : if (ret != 0) {
367 : /* LCOV_EXCL_START */
368 : goto bail;
369 : /* LCOV_EXCL_STOP */
370 : }
371 :
372 6 : ret = raid_test_data(np, ir, ip, nd, np, size, v, ref);
373 6 : if (ret != 0) {
374 : /* LCOV_EXCL_START */
375 : goto bail;
376 : /* LCOV_EXCL_STOP */
377 : }
378 :
379 : /* test recovering with broken leading data and broken leading parity */
380 15 : for (i = 0; i < np / 2; ++i) {
381 : /* bad data */
382 9 : ir[i] = i;
383 :
384 : /* good parity */
385 9 : ip[i] = (np + 1) / 2 + i;
386 : }
387 :
388 : /* bad parity */
389 18 : for (i = 0; i < (np + 1) / 2; ++i)
390 12 : ir[np / 2 + i] = nd + i;
391 :
392 6 : ret = raid_test_rec(np, ir, nd, np, size, v, ref);
393 6 : if (ret != 0) {
394 : /* LCOV_EXCL_START */
395 : goto bail;
396 : /* LCOV_EXCL_STOP */
397 : }
398 :
399 6 : ret = raid_test_data(np / 2, ir, ip, nd, np, size, v, ref);
400 6 : if (ret != 0) {
401 : /* LCOV_EXCL_START */
402 : goto bail;
403 : /* LCOV_EXCL_STOP */
404 : }
405 :
406 : /* test recovering with broken leading data and broken ending parity */
407 15 : for (i = 0; i < np / 2; ++i) {
408 : /* bad data */
409 9 : ir[i] = i;
410 :
411 : /* good parity */
412 9 : ip[i] = i;
413 : }
414 :
415 : /* bad parity */
416 18 : for (i = 0; i < (np + 1) / 2; ++i)
417 12 : ir[np / 2 + i] = nd + np - (np + 1) / 2 + i;
418 :
419 6 : ret = raid_test_rec(np, ir, nd, np, size, v, ref);
420 6 : if (ret != 0) {
421 : /* LCOV_EXCL_START */
422 : goto bail;
423 : /* LCOV_EXCL_STOP */
424 : }
425 :
426 6 : ret = raid_test_data(np / 2, ir, ip, nd, np, size, v, ref);
427 6 : if (ret != 0) {
428 : /* LCOV_EXCL_START */
429 : goto bail;
430 : /* LCOV_EXCL_STOP */
431 : }
432 :
433 : /* scan test with broken data and parity */
434 15 : for (i = 0; i < np / 2; ++i) {
435 : /* bad data */
436 9 : ir[i] = i;
437 : }
438 12 : for (i = 0; i < (np - 1) / 2; ++i) {
439 : /* bad parity */
440 6 : ir[np / 2 + i] = nd + i;
441 : }
442 21 : for (i = 0; i < np - 1; ++i) {
443 : /* make blocks bad */
444 : /* we cannot fill them with 0, because the original */
445 : /* data may be already filled with 0 */
446 15 : memset(v[ir[i]], 0x55, size);
447 : }
448 :
449 6 : ret = raid_test_scan(np - 1, ir, nd, np, size, v, ref);
450 6 : if (ret != 0) {
451 : /* LCOV_EXCL_START */
452 : goto bail;
453 : /* LCOV_EXCL_STOP */
454 : }
455 : }
456 :
457 : /* scan test with no parity */
458 1 : ret = raid_test_scan(0, 0, nd, 0, size, v, ref);
459 1 : if (ret != -1) {
460 : /* LCOV_EXCL_START */
461 : goto bail;
462 : /* LCOV_EXCL_STOP */
463 : }
464 :
465 1 : ret = 0;
466 :
467 : bail:
468 1 : free(v);
469 1 : free(v_alloc);
470 :
471 1 : return ret;
472 : }
473 :
|
