projects/linux·blob master · refs

385 lines · 9.9 KiB

1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * Copyright 2002-2007 H. Peter Anvin - All Rights Reserved
4 *
5 * Test RAID-6 recovery algorithms.
6 */
7
8#include <kunit/test.h>
9#include <linux/prandom.h>
10#include <linux/vmalloc.h>
11#include <linux/raid/pq.h>
12#include "../algos.h"
13
14MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
15
16#define RAID6_KUNIT_SEED 42
17#define RAID6_KUNIT_NUM_TEST_ITERS 10
18#define RAID6_KUNIT_MAX_BUFFERS 64 /* Including P and Q */
19#define RAID6_KUNIT_MAX_FAILURES 2
20#define RAID6_KUNIT_MAX_BYTES PAGE_SIZE
21#define RAID6_KUNIT_ALLOC_BYTES SZ_16K
22
23static struct rnd_state rng;
24static void *test_buffers[RAID6_KUNIT_MAX_BUFFERS];
25static void *aligned_buffers[RAID6_KUNIT_MAX_BUFFERS];
26static void *test_recov_buffers[RAID6_KUNIT_MAX_FAILURES];
27static size_t test_buflen;
28
29struct test_args {
30 unsigned int recov_idx;
31 const struct raid6_recov_calls *recov;
32 unsigned int gen_idx;
33 const struct raid6_calls *gen;
34};
35
36static struct test_args args;
37
38static u32 rand32(void)
39{
40 return prandom_u32_state(&rng);
41}
42
43/* Generate a random length that is a multiple of 512. */
44static unsigned int random_length(unsigned int max_length)
45{
46 return round_up((rand32() % max_length) + 1, 512);
47}
48
49static unsigned int random_nr_buffers(void)
50{
51 return (rand32() % (RAID6_KUNIT_MAX_BUFFERS - (RAID6_MIN_DISKS - 1))) +
52 RAID6_MIN_DISKS;
53}
54
55/* Generate a random alignment that is a multiple of 64. */
56static unsigned int random_alignment(unsigned int max_alignment)
57{
58 if (max_alignment == 0)
59 return 0;
60 return (rand32() % (max_alignment + 1)) & ~63;
61}
62
63static void makedata(int start, int stop)
64{
65 int i;
66
67 for (i = start; i <= stop; i++)
68 prandom_bytes_state(&rng, test_buffers[i], test_buflen);
69}
70
71static char member_type(unsigned int nr_buffers, int d)
72{
73 if (d == nr_buffers - 2)
74 return 'P';
75 if (d == nr_buffers - 1)
76 return 'Q';
77 return 'D';
78}
79
80static void test_recover_one(struct kunit *test, unsigned int nr_buffers,
81 unsigned int len, int faila, int failb)
82{
83 const struct test_args *ta = test->param_value;
84 void *dataptrs[RAID6_KUNIT_MAX_BUFFERS];
85 int i;
86
87 if (faila > failb)
88 swap(faila, failb);
89
90 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++)
91 memset(test_recov_buffers[i], 0xf0, test_buflen);
92
93 memcpy(dataptrs, aligned_buffers, sizeof(dataptrs));
94 dataptrs[faila] = test_recov_buffers[0];
95 dataptrs[failb] = test_recov_buffers[1];
96
97 if (failb == nr_buffers - 1) {
98 /*
99 * We don't implement the data+Q failure scenario, since it
100 * is equivalent to a RAID-5 failure (XOR, then recompute Q).
101 */
102 if (WARN_ON_ONCE(faila != nr_buffers - 2))
103 return;
104
105 /* P+Q failure. Just rebuild the syndrome. */
106 ta->gen->gen_syndrome(nr_buffers, len, dataptrs);
107 } else if (failb == nr_buffers - 2) {
108 /* data+P failure. */
109 ta->recov->datap(nr_buffers, len, faila, dataptrs);
110 } else {
111 /* data+data failure. */
112 ta->recov->data2(nr_buffers, len, faila, failb, dataptrs);
113 }
114
115 KUNIT_EXPECT_MEMEQ_MSG(test, aligned_buffers[faila], dataptrs[faila],
116 len,
117 "faila miscompared: %3d[%c] buffers %u len %u (failb=%3d[%c])\n",
118 faila, member_type(nr_buffers, faila),
119 nr_buffers, len,
120 failb, member_type(nr_buffers, failb));
121 KUNIT_EXPECT_MEMEQ_MSG(test, aligned_buffers[failb], dataptrs[failb],
122 len,
123 "failb miscompared: %3d[%c] buffers %u len %u (faila=%3d[%c])\n",
124 failb, member_type(nr_buffers, failb),
125 nr_buffers, len,
126 faila, member_type(nr_buffers, faila));
127}
128
129static void test_recover(struct kunit *test, unsigned int nr_buffers,
130 unsigned int len)
131{
132 unsigned int nr_data = nr_buffers - 2;
133 int iterations, i;
134
135 /* Test P+Q recovery */
136 test_recover_one(test, nr_buffers, len, nr_data, nr_buffers - 1);
137
138 /* Test data+P recovery */
139 for (i = 0; i < nr_buffers - 2; i++)
140 test_recover_one(test, nr_buffers, len, i, nr_data);
141
142 /* Double data failure is impossible with a single data disk */
143 if (nr_data == 1)
144 return;
145
146 /* Test data+data recovery using random sampling */
147 iterations = nr_buffers * 2; /* should provide good enough coverage */
148 for (i = 0; i < iterations; i++) {
149 int faila = rand32() % nr_data, failb;
150
151 do {
152 failb = rand32() % nr_data;
153 } while (failb == faila);
154
155 test_recover_one(test, nr_buffers, len, faila, failb);
156 }
157}
158
159/* Simulate rmw run */
160static void test_rmw_one(struct kunit *test, unsigned int nr_buffers,
161 unsigned int len, int p1, int p2)
162{
163 const struct test_args *ta = test->param_value;
164
165 ta->gen->xor_syndrome(nr_buffers, p1, p2, len, aligned_buffers);
166 makedata(p1, p2);
167 ta->gen->xor_syndrome(nr_buffers, p1, p2, len, aligned_buffers);
168 test_recover(test, nr_buffers, len);
169}
170
171static void test_rmw(struct kunit *test, unsigned int nr_buffers,
172 unsigned int len)
173{
174 int iterations = nr_buffers / 2, i;
175
176 for (i = 0; i < iterations; i++) {
177 int p1 = rand32() % (nr_buffers - 2);
178 int p2 = rand32() % (nr_buffers - 2);
179
180 if (p2 < p1)
181 swap(p1, p2);
182 test_rmw_one(test, nr_buffers, len, p1, p2);
183 }
184}
185
186static void raid6_test_one(struct kunit *test)
187{
188 const struct test_args *ta = test->param_value;
189 unsigned int nr_buffers = random_nr_buffers();
190 unsigned int len = random_length(RAID6_KUNIT_MAX_BYTES);
191 unsigned int max_alignment;
192 int i;
193
194 /* Nuke syndromes */
195 memset(test_buffers[nr_buffers - 2], 0xee, test_buflen);
196 memset(test_buffers[nr_buffers - 1], 0xee, test_buflen);
197
198 /*
199 * If we're not using the entire buffer size, inject randomize alignment
200 * into the buffer.
201 */
202 max_alignment = RAID6_KUNIT_MAX_BYTES - len;
203 if (rand32() % 2 == 0) {
204 /* Use random alignments mod 64 */
205 for (i = 0; i < nr_buffers; i++)
206 aligned_buffers[i] = test_buffers[i] +
207 random_alignment(max_alignment);
208 } else {
209 /* Go up to the guard page, to catch buffer overreads */
210 unsigned int align = test_buflen - len;
211
212 for (i = 0; i < nr_buffers; i++)
213 aligned_buffers[i] = test_buffers[i] + align;
214 }
215
216 /* Generate assumed good syndrome */
217 ta->gen->gen_syndrome(nr_buffers, len, aligned_buffers);
218
219 test_recover(test, nr_buffers, len);
220
221 if (ta->gen->xor_syndrome)
222 test_rmw(test, nr_buffers, len);
223}
224
225static void raid6_test(struct kunit *test)
226{
227 int i;
228
229 for (i = 0; i < RAID6_KUNIT_NUM_TEST_ITERS; i++)
230 raid6_test_one(test);
231}
232
233static void raid6_benchmark(struct kunit *test)
234{
235 static const unsigned int nr_to_test[] = {
236 4, 5, 6, 7, 8, 10, 12, 15, 16, 32,
237 };
238 static const unsigned int len_to_test[] = {
239 SZ_4K, SZ_16K,
240 };
241 unsigned int i, j, l;
242 u64 t;
243
244 if (!IS_ENABLED(CONFIG_RAID6_PQ_KUNIT_BENCHMARK))
245 kunit_skip(test, "not enabled");
246
247 /* warm-up */
248 for (i = 0; i < ARRAY_SIZE(nr_to_test); i++) {
249 for (j = 0; j < ARRAY_SIZE(len_to_test); j++) {
250 for (l = 0; l < 10; l++) {
251 raid6_gen_syndrome(nr_to_test[i],
252 len_to_test[j], test_buffers);
253 }
254 }
255 }
256
257 /*
258 * Preferably this would be a loop over len_to_test, but the kunit
259 * logging always adds a newline to each logged format string.
260 */
261 static_assert(ARRAY_SIZE(len_to_test) == 2);
262 kunit_info(test, " \t%5u bytes\t%5u bytes\n",
263 len_to_test[0], len_to_test[1]);
264
265 for (i = 0; i < ARRAY_SIZE(nr_to_test); i++) {
266 unsigned int nr = nr_to_test[i];
267 u64 speed[ARRAY_SIZE(len_to_test)];
268
269 KUNIT_ASSERT_LE(test, nr, RAID6_KUNIT_MAX_BUFFERS);
270
271 for (j = 0; j < ARRAY_SIZE(len_to_test); j++) {
272 unsigned int len = len_to_test[j];
273 const unsigned long num_iters = 1000;
274
275 KUNIT_ASSERT_GT(test, len, 0);
276 KUNIT_ASSERT_LE(test, len, RAID6_KUNIT_ALLOC_BYTES);
277
278 preempt_disable();
279 t = ktime_get_ns();
280 for (l = 0; l < num_iters; l++)
281 raid6_gen_syndrome(nr_to_test[i],
282 len_to_test[j], test_buffers);
283 t = max(ktime_get_ns() - t, 1);
284 preempt_enable();
285
286 speed[j] = div64_u64((u64)len * num_iters * nr, t);
287 }
288
289 static_assert(ARRAY_SIZE(len_to_test) == 2);
290 kunit_info(test, "%3u disks:\t%5llu GB/s\t%5llu GB/s\n",
291 nr, speed[0], speed[1]);
292 }
293}
294
295static const void *raid6_gen_params(struct kunit *test, const void *prev,
296 char *desc)
297{
298 if (!prev) {
299 memset(&args, 0, sizeof(args));
300next_algo:
301 args.recov_idx = 0;
302 args.gen = raid6_algo_find(args.gen_idx);
303 if (!args.gen)
304 return NULL;
305 }
306
307 if (args.recov)
308 args.recov_idx++;
309 args.recov = raid6_recov_algo_find(args.recov_idx);
310 if (!args.recov) {
311 args.gen_idx++;
312 goto next_algo;
313 }
314
315 snprintf(desc, KUNIT_PARAM_DESC_SIZE, "gen=%s recov=%s",
316 args.gen->name, args.recov->name);
317 return &args;
318}
319
320static struct kunit_case raid6_test_cases[] = {
321 KUNIT_CASE_PARAM(raid6_test, raid6_gen_params),
322 KUNIT_CASE(raid6_benchmark),
323 {},
324};
325
326static int raid6_suite_init(struct kunit_suite *suite)
327{
328 int i;
329
330 prandom_seed_state(&rng, RAID6_KUNIT_SEED);
331
332 /*
333 * Allocate the test buffer using vmalloc() with a page-aligned length
334 * so that it is immediately followed by a guard page. This allows
335 * buffer overreads to be detected, even in assembly code.
336 */
337 test_buflen = round_up(RAID6_KUNIT_ALLOC_BYTES, PAGE_SIZE);
338 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++) {
339 test_recov_buffers[i] = vmalloc(test_buflen);
340 if (!test_recov_buffers[i])
341 goto out_free_recov_buffers;
342 }
343 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++) {
344 test_buffers[i] = vmalloc(test_buflen);
345 if (!test_buffers[i])
346 goto out_free_buffers;
347 }
348
349 makedata(0, RAID6_KUNIT_MAX_BUFFERS - 1);
350
351 return 0;
352
353out_free_buffers:
354 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++)
355 vfree(test_buffers[i]);
356 memset(test_buffers, 0, sizeof(test_buffers));
357out_free_recov_buffers:
358 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++)
359 vfree(test_recov_buffers[i]);
360 memset(test_recov_buffers, 0, sizeof(test_recov_buffers));
361 return -ENOMEM;
362}
363
364static void raid6_suite_exit(struct kunit_suite *suite)
365{
366 int i;
367
368 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++)
369 vfree(test_buffers[i]);
370 memset(test_buffers, 0, sizeof(test_buffers));
371 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++)
372 vfree(test_recov_buffers[i]);
373 memset(test_recov_buffers, 0, sizeof(test_recov_buffers));
374}
375
376static struct kunit_suite raid6_test_suite = {
377 .name = "raid6",
378 .test_cases = raid6_test_cases,
379 .suite_init = raid6_suite_init,
380 .suite_exit = raid6_suite_exit,
381};
382kunit_test_suite(raid6_test_suite);
383
384MODULE_DESCRIPTION("Unit test for the RAID P/Q library functions");
385MODULE_LICENSE("GPL");