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 14 MODULE_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 23 static struct rnd_state rng; 24 static void *test_buffers[RAID6_KUNIT_MAX_BUFFERS]; 25 static void *aligned_buffers[RAID6_KUNIT_MAX_BUFFERS]; 26 static void *test_recov_buffers[RAID6_KUNIT_MAX_FAILURES]; 27 static size_t test_buflen; 28 29 struct 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 36 static struct test_args args; 37 38 static u32 rand32(void) 39 { 40 return prandom_u32_state(&rng); 41 } 42 43 /* Generate a random length that is a multiple of 512. */ 44 static unsigned int random_length(unsigned int max_length) 45 { 46 return round_up((rand32() % max_length) + 1, 512); 47 } 48 49 static 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. */ 56 static 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 63 static 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 71 static 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 80 static 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 129 static 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 */ 160 static 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 171 static 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 186 static 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 225 static 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 233 static 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 295 static const void *raid6_gen_params(struct kunit *test, const void *prev, 296 char *desc) 297 { 298 if (!prev) { 299 memset(&args, 0, sizeof(args)); 300 next_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 320 static struct kunit_case raid6_test_cases[] = { 321 KUNIT_CASE_PARAM(raid6_test, raid6_gen_params), 322 KUNIT_CASE(raid6_benchmark), 323 {}, 324 }; 325 326 static 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 353 out_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)); 357 out_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 364 static 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 376 static 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 }; 382 kunit_test_suite(raid6_test_suite); 383 384 MODULE_DESCRIPTION("Unit test for the RAID P/Q library functions"); 385 MODULE_LICENSE("GPL"); 386