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 22 static struct rnd_state rng; 23 static void *test_buffers[RAID6_KUNIT_MAX_BUFFERS]; 24 static void *aligned_buffers[RAID6_KUNIT_MAX_BUFFERS]; 25 static void *test_recov_buffers[RAID6_KUNIT_MAX_FAILURES]; 26 static size_t test_buflen; 27 28 struct test_args { 29 unsigned int recov_idx; 30 const struct raid6_recov_calls *recov; 31 unsigned int gen_idx; 32 const struct raid6_calls *gen; 33 }; 34 35 static struct test_args args; 36 37 static u32 rand32(void) 38 { 39 return prandom_u32_state(&rng); 40 } 41 42 /* Generate a random length that is a multiple of 512. */ 43 static unsigned int random_length(unsigned int max_length) 44 { 45 return round_up((rand32() % max_length) + 1, 512); 46 } 47 48 static unsigned int random_nr_buffers(void) 49 { 50 return (rand32() % (RAID6_KUNIT_MAX_BUFFERS - (RAID6_MIN_DISKS - 1))) + 51 RAID6_MIN_DISKS; 52 } 53 54 /* Generate a random alignment that is a multiple of 64. */ 55 static unsigned int random_alignment(unsigned int max_alignment) 56 { 57 if (max_alignment == 0) 58 return 0; 59 return (rand32() % (max_alignment + 1)) & ~63; 60 } 61 62 static void makedata(int start, int stop) 63 { 64 int i; 65 66 for (i = start; i <= stop; i++) 67 prandom_bytes_state(&rng, test_buffers[i], test_buflen); 68 } 69 70 static char member_type(unsigned int nr_buffers, int d) 71 { 72 if (d == nr_buffers - 2) 73 return 'P'; 74 if (d == nr_buffers - 1) 75 return 'Q'; 76 return 'D'; 77 } 78 79 static void test_recover_one(struct kunit *test, unsigned int nr_buffers, 80 unsigned int len, int faila, int failb) 81 { 82 const struct test_args *ta = test->param_value; 83 void *dataptrs[RAID6_KUNIT_MAX_BUFFERS]; 84 int i; 85 86 if (faila > failb) 87 swap(faila, failb); 88 89 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++) 90 memset(test_recov_buffers[i], 0xf0, test_buflen); 91 92 memcpy(dataptrs, aligned_buffers, sizeof(dataptrs)); 93 dataptrs[faila] = test_recov_buffers[0]; 94 dataptrs[failb] = test_recov_buffers[1]; 95 96 if (failb == nr_buffers - 1) { 97 /* 98 * We don't implement the data+Q failure scenario, since it 99 * is equivalent to a RAID-5 failure (XOR, then recompute Q). 100 */ 101 if (WARN_ON_ONCE(faila != nr_buffers - 2)) 102 return; 103 104 /* P+Q failure. Just rebuild the syndrome. */ 105 ta->gen->gen_syndrome(nr_buffers, len, dataptrs); 106 } else if (failb == nr_buffers - 2) { 107 /* data+P failure. */ 108 ta->recov->datap(nr_buffers, len, faila, dataptrs); 109 } else { 110 /* data+data failure. */ 111 ta->recov->data2(nr_buffers, len, faila, failb, dataptrs); 112 } 113 114 KUNIT_EXPECT_MEMEQ_MSG(test, aligned_buffers[faila], dataptrs[faila], 115 len, 116 "faila miscompared: %3d[%c] buffers %u len %u (failb=%3d[%c])\n", 117 faila, member_type(nr_buffers, faila), 118 nr_buffers, len, 119 failb, member_type(nr_buffers, failb)); 120 KUNIT_EXPECT_MEMEQ_MSG(test, aligned_buffers[failb], dataptrs[failb], 121 len, 122 "failb miscompared: %3d[%c] buffers %u len %u (faila=%3d[%c])\n", 123 failb, member_type(nr_buffers, failb), 124 nr_buffers, len, 125 faila, member_type(nr_buffers, faila)); 126 } 127 128 static void test_recover(struct kunit *test, unsigned int nr_buffers, 129 unsigned int len) 130 { 131 unsigned int nr_data = nr_buffers - 2; 132 int iterations, i; 133 134 /* Test P+Q recovery */ 135 test_recover_one(test, nr_buffers, len, nr_data, nr_buffers - 1); 136 137 /* Test data+P recovery */ 138 for (i = 0; i < nr_buffers - 2; i++) 139 test_recover_one(test, nr_buffers, len, i, nr_data); 140 141 /* Double data failure is impossible with a single data disk */ 142 if (nr_data == 1) 143 return; 144 145 /* Test data+data recovery using random sampling */ 146 iterations = nr_buffers * 2; /* should provide good enough coverage */ 147 for (i = 0; i < iterations; i++) { 148 int faila = rand32() % nr_data, failb; 149 150 do { 151 failb = rand32() % nr_data; 152 } while (failb == faila); 153 154 test_recover_one(test, nr_buffers, len, faila, failb); 155 } 156 } 157 158 /* Simulate rmw run */ 159 static void test_rmw_one(struct kunit *test, unsigned int nr_buffers, 160 unsigned int len, int p1, int p2) 161 { 162 const struct test_args *ta = test->param_value; 163 164 ta->gen->xor_syndrome(nr_buffers, p1, p2, len, aligned_buffers); 165 makedata(p1, p2); 166 ta->gen->xor_syndrome(nr_buffers, p1, p2, len, aligned_buffers); 167 test_recover(test, nr_buffers, len); 168 } 169 170 static void test_rmw(struct kunit *test, unsigned int nr_buffers, 171 unsigned int len) 172 { 173 int iterations = nr_buffers / 2, i; 174 175 for (i = 0; i < iterations; i++) { 176 int p1 = rand32() % (nr_buffers - 2); 177 int p2 = rand32() % (nr_buffers - 2); 178 179 if (p2 < p1) 180 swap(p1, p2); 181 test_rmw_one(test, nr_buffers, len, p1, p2); 182 } 183 } 184 185 static void raid6_test_one(struct kunit *test) 186 { 187 const struct test_args *ta = test->param_value; 188 unsigned int nr_buffers = random_nr_buffers(); 189 unsigned int len = random_length(RAID6_KUNIT_MAX_BYTES); 190 unsigned int max_alignment; 191 int i; 192 193 /* Nuke syndromes */ 194 memset(test_buffers[nr_buffers - 2], 0xee, test_buflen); 195 memset(test_buffers[nr_buffers - 1], 0xee, test_buflen); 196 197 /* 198 * If we're not using the entire buffer size, inject randomize alignment 199 * into the buffer. 200 */ 201 max_alignment = RAID6_KUNIT_MAX_BYTES - len; 202 if (rand32() % 2 == 0) { 203 /* Use random alignments mod 64 */ 204 for (i = 0; i < nr_buffers; i++) 205 aligned_buffers[i] = test_buffers[i] + 206 random_alignment(max_alignment); 207 } else { 208 /* Go up to the guard page, to catch buffer overreads */ 209 unsigned int align = test_buflen - len; 210 211 for (i = 0; i < nr_buffers; i++) 212 aligned_buffers[i] = test_buffers[i] + align; 213 } 214 215 /* Generate assumed good syndrome */ 216 ta->gen->gen_syndrome(nr_buffers, len, aligned_buffers); 217 218 test_recover(test, nr_buffers, len); 219 220 if (ta->gen->xor_syndrome) 221 test_rmw(test, nr_buffers, len); 222 } 223 224 static void raid6_test(struct kunit *test) 225 { 226 int i; 227 228 for (i = 0; i < RAID6_KUNIT_NUM_TEST_ITERS; i++) 229 raid6_test_one(test); 230 } 231 232 static const void *raid6_gen_params(struct kunit *test, const void *prev, 233 char *desc) 234 { 235 if (!prev) { 236 memset(&args, 0, sizeof(args)); 237 next_algo: 238 args.recov_idx = 0; 239 args.gen = raid6_algo_find(args.gen_idx); 240 if (!args.gen) 241 return NULL; 242 } 243 244 if (args.recov) 245 args.recov_idx++; 246 args.recov = raid6_recov_algo_find(args.recov_idx); 247 if (!args.recov) { 248 args.gen_idx++; 249 goto next_algo; 250 } 251 252 snprintf(desc, KUNIT_PARAM_DESC_SIZE, "gen=%s recov=%s", 253 args.gen->name, args.recov->name); 254 return &args; 255 } 256 257 static struct kunit_case raid6_test_cases[] = { 258 KUNIT_CASE_PARAM(raid6_test, raid6_gen_params), 259 {}, 260 }; 261 262 static int raid6_suite_init(struct kunit_suite *suite) 263 { 264 int i; 265 266 prandom_seed_state(&rng, RAID6_KUNIT_SEED); 267 268 /* 269 * Allocate the test buffer using vmalloc() with a page-aligned length 270 * so that it is immediately followed by a guard page. This allows 271 * buffer overreads to be detected, even in assembly code. 272 */ 273 test_buflen = round_up(RAID6_KUNIT_MAX_BYTES, PAGE_SIZE); 274 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++) { 275 test_recov_buffers[i] = vmalloc(test_buflen); 276 if (!test_recov_buffers[i]) 277 goto out_free_recov_buffers; 278 } 279 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++) { 280 test_buffers[i] = vmalloc(test_buflen); 281 if (!test_buffers[i]) 282 goto out_free_buffers; 283 } 284 285 makedata(0, RAID6_KUNIT_MAX_BUFFERS - 1); 286 287 return 0; 288 289 out_free_buffers: 290 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++) 291 vfree(test_buffers[i]); 292 memset(test_buffers, 0, sizeof(test_buffers)); 293 out_free_recov_buffers: 294 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++) 295 vfree(test_recov_buffers[i]); 296 memset(test_recov_buffers, 0, sizeof(test_recov_buffers)); 297 return -ENOMEM; 298 } 299 300 static void raid6_suite_exit(struct kunit_suite *suite) 301 { 302 int i; 303 304 for (i = 0; i < RAID6_KUNIT_MAX_BUFFERS; i++) 305 vfree(test_buffers[i]); 306 memset(test_buffers, 0, sizeof(test_buffers)); 307 for (i = 0; i < RAID6_KUNIT_MAX_FAILURES; i++) 308 vfree(test_recov_buffers[i]); 309 memset(test_recov_buffers, 0, sizeof(test_recov_buffers)); 310 } 311 312 static struct kunit_suite raid6_test_suite = { 313 .name = "raid6", 314 .test_cases = raid6_test_cases, 315 .suite_init = raid6_suite_init, 316 .suite_exit = raid6_suite_exit, 317 }; 318 kunit_test_suite(raid6_test_suite); 319 320 MODULE_DESCRIPTION("Unit test for the RAID P/Q library functions"); 321 MODULE_LICENSE("GPL"); 322