1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* -*- linux-c -*- ------------------------------------------------------- * 3 * 4 * Copyright 2002 H. Peter Anvin - All Rights Reserved 5 * 6 * ----------------------------------------------------------------------- */ 7 8 /* 9 * raid6/algos.c 10 * 11 * Algorithm list and algorithm selection for RAID-6 12 */ 13 14 #include <linux/raid/pq.h> 15 #include <linux/module.h> 16 #include <linux/gfp.h> 17 #include <kunit/visibility.h> 18 19 static const struct raid6_recov_calls *raid6_recov_algo; 20 21 /* Selected algorithm */ 22 static struct raid6_calls raid6_call; 23 24 /** 25 * raid6_gen_syndrome - generate RAID6 P/Q parity 26 * @disks: number of "disks" to operate on including parity 27 * @bytes: length in bytes of each vector 28 * @ptrs: @disks size array of memory pointers 29 * 30 * Generate @bytes worth of RAID6 P and Q parity in @ptrs[@disks - 2] and 31 * @ptrs[@disks - 1] respectively from the memory pointed to by @ptrs[0] to 32 * @ptrs[@disks - 3]. 33 * 34 * @disks must be at least 4, and the memory pointed to by each member of @ptrs 35 * must be at least 64-byte aligned. @bytes must be non-zero and a multiple of 36 * 512. 37 * 38 * See https://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf for underlying 39 * algorithm. 40 */ 41 void raid6_gen_syndrome(int disks, size_t bytes, void **ptrs) 42 { 43 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 44 WARN_ON_ONCE(bytes & 511); 45 WARN_ON_ONCE(disks < RAID6_MIN_DISKS); 46 47 raid6_call.gen_syndrome(disks, bytes, ptrs); 48 } 49 EXPORT_SYMBOL_GPL(raid6_gen_syndrome); 50 51 /** 52 * raid6_xor_syndrome - update RAID6 P/Q parity 53 * @disks: number of "disks" to operate on including parity 54 * @start: first index into @disk to update 55 * @stop: last index into @disk to update 56 * @bytes: length in bytes of each vector 57 * @ptrs: @disks size array of memory pointers 58 * 59 * Update @bytes worth of RAID6 P and Q parity in @ptrs[@disks - 2] and 60 * @ptrs[@disks - 1] respectively for the memory pointed to by 61 * @ptrs[@start..@stop]. 62 * 63 * This is used to update parity in place using the following sequence: 64 * 65 * 1) call raid6_xor_syndrome(disk, start, stop, ...) for the existing data. 66 * 2) update the the data in @ptrs[@start..@stop]. 67 * 3) call raid6_xor_syndrome(disk, start, stop, ...) for the new data. 68 * 69 * Data between @start and @stop that is not changed should be filled 70 * with a pointer to the kernel zero page. 71 * 72 * @disks must be at least 4, and the memory pointed to by each member of @ptrs 73 * must be at least 64-byte aligned. @bytes must be non-zero and a multiple of 74 * 512. @stop must be larger or equal to @start. 75 */ 76 void raid6_xor_syndrome(int disks, int start, int stop, size_t bytes, 77 void **ptrs) 78 { 79 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 80 WARN_ON_ONCE(bytes & 511); 81 WARN_ON_ONCE(disks < RAID6_MIN_DISKS); 82 WARN_ON_ONCE(stop < start); 83 84 raid6_call.xor_syndrome(disks, start, stop, bytes, ptrs); 85 } 86 EXPORT_SYMBOL_GPL(raid6_xor_syndrome); 87 88 /* 89 * raid6_can_xor_syndrome - check if raid6_xor_syndrome() can be used 90 * 91 * Returns %true if raid6_can_xor_syndrome() can be used, else %false. 92 */ 93 bool raid6_can_xor_syndrome(void) 94 { 95 return !!raid6_call.xor_syndrome; 96 } 97 EXPORT_SYMBOL_GPL(raid6_can_xor_syndrome); 98 99 const struct raid6_calls * const raid6_algos[] = { 100 #if defined(__i386__) && !defined(__arch_um__) 101 &raid6_avx512x2, 102 &raid6_avx512x1, 103 &raid6_avx2x2, 104 &raid6_avx2x1, 105 &raid6_sse2x2, 106 &raid6_sse2x1, 107 &raid6_sse1x2, 108 &raid6_sse1x1, 109 &raid6_mmxx2, 110 &raid6_mmxx1, 111 #endif 112 #if defined(__x86_64__) && !defined(__arch_um__) 113 &raid6_avx512x4, 114 &raid6_avx512x2, 115 &raid6_avx512x1, 116 &raid6_avx2x4, 117 &raid6_avx2x2, 118 &raid6_avx2x1, 119 &raid6_sse2x4, 120 &raid6_sse2x2, 121 &raid6_sse2x1, 122 #endif 123 #ifdef CONFIG_ALTIVEC 124 &raid6_vpermxor8, 125 &raid6_vpermxor4, 126 &raid6_vpermxor2, 127 &raid6_vpermxor1, 128 &raid6_altivec8, 129 &raid6_altivec4, 130 &raid6_altivec2, 131 &raid6_altivec1, 132 #endif 133 #if defined(CONFIG_S390) 134 &raid6_s390vx8, 135 #endif 136 #ifdef CONFIG_KERNEL_MODE_NEON 137 &raid6_neonx8, 138 &raid6_neonx4, 139 &raid6_neonx2, 140 &raid6_neonx1, 141 #endif 142 #ifdef CONFIG_LOONGARCH 143 #ifdef CONFIG_CPU_HAS_LASX 144 &raid6_lasx, 145 #endif 146 #ifdef CONFIG_CPU_HAS_LSX 147 &raid6_lsx, 148 #endif 149 #endif 150 #ifdef CONFIG_RISCV_ISA_V 151 &raid6_rvvx1, 152 &raid6_rvvx2, 153 &raid6_rvvx4, 154 &raid6_rvvx8, 155 #endif 156 &raid6_intx8, 157 &raid6_intx4, 158 &raid6_intx2, 159 &raid6_intx1, 160 NULL 161 }; 162 EXPORT_SYMBOL_IF_KUNIT(raid6_algos); 163 164 /** 165 * raid6_recov_2data - recover two missing data disks 166 * @disks: number of "disks" to operate on including parity 167 * @bytes: length in bytes of each vector 168 * @faila: first failed data disk index 169 * @failb: second failed data disk index 170 * @ptrs: @disks size array of memory pointers 171 * 172 * Rebuild @bytes of missing data in @ptrs[@faila] and @ptrs[@failb] from the 173 * data in the remaining disks and the two parities pointed to by the other 174 * indices between 0 and @disks - 1 in @ptrs. @disks includes the data disks 175 * and the two parities. @faila must be smaller than @failb. 176 * 177 * Memory pointed to by each pointer in @ptrs must be page aligned and is 178 * limited to %PAGE_SIZE. 179 */ 180 void raid6_recov_2data(int disks, size_t bytes, int faila, int failb, 181 void **ptrs) 182 { 183 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 184 WARN_ON_ONCE(bytes & 511); 185 WARN_ON_ONCE(bytes > PAGE_SIZE); 186 WARN_ON_ONCE(failb <= faila); 187 188 raid6_recov_algo->data2(disks, bytes, faila, failb, ptrs); 189 } 190 EXPORT_SYMBOL_GPL(raid6_recov_2data); 191 192 /** 193 * raid6_recov_datap - recover a missing data disk and missing P-parity 194 * @disks: number of "disks" to operate on including parity 195 * @bytes: length in bytes of each vector 196 * @faila: failed data disk index 197 * @ptrs: @disks size array of memory pointers 198 * 199 * Rebuild @bytes of missing data in @ptrs[@faila] and the missing P-parity in 200 * @ptrs[@disks - 2] from the data in the remaining disks and the Q-parity 201 * pointed to by the other indices between 0 and @disks - 1 in @ptrs. @disks 202 * includes the data disks and the two parities. 203 * 204 * Memory pointed to by each pointer in @ptrs must be page aligned and is 205 * limited to %PAGE_SIZE. 206 */ 207 void raid6_recov_datap(int disks, size_t bytes, int faila, void **ptrs) 208 { 209 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 210 WARN_ON_ONCE(bytes & 511); 211 WARN_ON_ONCE(bytes > PAGE_SIZE); 212 213 raid6_recov_algo->datap(disks, bytes, faila, ptrs); 214 } 215 EXPORT_SYMBOL_GPL(raid6_recov_datap); 216 217 const struct raid6_recov_calls *const raid6_recov_algos[] = { 218 #ifdef CONFIG_X86 219 &raid6_recov_avx512, 220 &raid6_recov_avx2, 221 &raid6_recov_ssse3, 222 #endif 223 #ifdef CONFIG_S390 224 &raid6_recov_s390xc, 225 #endif 226 #if defined(CONFIG_KERNEL_MODE_NEON) 227 &raid6_recov_neon, 228 #endif 229 #ifdef CONFIG_LOONGARCH 230 #ifdef CONFIG_CPU_HAS_LASX 231 &raid6_recov_lasx, 232 #endif 233 #ifdef CONFIG_CPU_HAS_LSX 234 &raid6_recov_lsx, 235 #endif 236 #endif 237 #ifdef CONFIG_RISCV_ISA_V 238 &raid6_recov_rvv, 239 #endif 240 &raid6_recov_intx1, 241 NULL 242 }; 243 EXPORT_SYMBOL_IF_KUNIT(raid6_recov_algos); 244 245 #define RAID6_TIME_JIFFIES_LG2 4 246 #define RAID6_TEST_DISKS 8 247 #define RAID6_TEST_DISKS_ORDER 3 248 249 static inline const struct raid6_recov_calls *raid6_choose_recov(void) 250 { 251 const struct raid6_recov_calls *const *algo; 252 const struct raid6_recov_calls *best; 253 254 for (best = NULL, algo = raid6_recov_algos; *algo; algo++) 255 if (!best || (*algo)->priority > best->priority) 256 if (!(*algo)->valid || (*algo)->valid()) 257 best = *algo; 258 259 if (best) { 260 raid6_recov_algo = best; 261 262 pr_info("raid6: using %s recovery algorithm\n", best->name); 263 } else 264 pr_err("raid6: Yikes! No recovery algorithm found!\n"); 265 266 return best; 267 } 268 269 static inline const struct raid6_calls *raid6_choose_gen( 270 void *(*const dptrs)[RAID6_TEST_DISKS], const int disks) 271 { 272 unsigned long perf, bestgenperf, j0, j1; 273 int start = (disks>>1)-1, stop = disks-3; /* work on the second half of the disks */ 274 const struct raid6_calls *const *algo; 275 const struct raid6_calls *best; 276 277 for (bestgenperf = 0, best = NULL, algo = raid6_algos; *algo; algo++) { 278 if (!best || (*algo)->priority >= best->priority) { 279 if ((*algo)->valid && !(*algo)->valid()) 280 continue; 281 282 if (!IS_ENABLED(CONFIG_RAID6_PQ_BENCHMARK)) { 283 best = *algo; 284 break; 285 } 286 287 perf = 0; 288 289 preempt_disable(); 290 j0 = jiffies; 291 while ((j1 = jiffies) == j0) 292 cpu_relax(); 293 while (time_before(jiffies, 294 j1 + (1<<RAID6_TIME_JIFFIES_LG2))) { 295 (*algo)->gen_syndrome(disks, PAGE_SIZE, *dptrs); 296 perf++; 297 } 298 preempt_enable(); 299 300 if (perf > bestgenperf) { 301 bestgenperf = perf; 302 best = *algo; 303 } 304 pr_info("raid6: %-8s gen() %5ld MB/s\n", (*algo)->name, 305 (perf * HZ * (disks-2)) >> 306 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2)); 307 } 308 } 309 310 if (!best) { 311 pr_err("raid6: Yikes! No algorithm found!\n"); 312 goto out; 313 } 314 315 raid6_call = *best; 316 317 if (!IS_ENABLED(CONFIG_RAID6_PQ_BENCHMARK)) { 318 pr_info("raid6: skipped pq benchmark and selected %s\n", 319 best->name); 320 goto out; 321 } 322 323 pr_info("raid6: using algorithm %s gen() %ld MB/s\n", 324 best->name, 325 (bestgenperf * HZ * (disks - 2)) >> 326 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2)); 327 328 if (best->xor_syndrome) { 329 perf = 0; 330 331 preempt_disable(); 332 j0 = jiffies; 333 while ((j1 = jiffies) == j0) 334 cpu_relax(); 335 while (time_before(jiffies, 336 j1 + (1 << RAID6_TIME_JIFFIES_LG2))) { 337 best->xor_syndrome(disks, start, stop, 338 PAGE_SIZE, *dptrs); 339 perf++; 340 } 341 preempt_enable(); 342 343 pr_info("raid6: .... xor() %ld MB/s, rmw enabled\n", 344 (perf * HZ * (disks - 2)) >> 345 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2 + 1)); 346 } 347 348 out: 349 return best; 350 } 351 352 353 /* Try to pick the best algorithm */ 354 /* This code uses the gfmul table as convenient data set to abuse */ 355 356 static int __init raid6_select_algo(void) 357 { 358 const int disks = RAID6_TEST_DISKS; 359 360 const struct raid6_calls *gen_best; 361 const struct raid6_recov_calls *rec_best; 362 char *disk_ptr, *p; 363 void *dptrs[RAID6_TEST_DISKS]; 364 int i, cycle; 365 366 /* prepare the buffer and fill it circularly with gfmul table */ 367 disk_ptr = (char *)__get_free_pages(GFP_KERNEL, RAID6_TEST_DISKS_ORDER); 368 if (!disk_ptr) { 369 pr_err("raid6: Yikes! No memory available.\n"); 370 return -ENOMEM; 371 } 372 373 p = disk_ptr; 374 for (i = 0; i < disks; i++) 375 dptrs[i] = p + PAGE_SIZE * i; 376 377 cycle = ((disks - 2) * PAGE_SIZE) / 65536; 378 for (i = 0; i < cycle; i++) { 379 memcpy(p, raid6_gfmul, 65536); 380 p += 65536; 381 } 382 383 if ((disks - 2) * PAGE_SIZE % 65536) 384 memcpy(p, raid6_gfmul, (disks - 2) * PAGE_SIZE % 65536); 385 386 /* select raid gen_syndrome function */ 387 gen_best = raid6_choose_gen(&dptrs, disks); 388 389 /* select raid recover functions */ 390 rec_best = raid6_choose_recov(); 391 392 free_pages((unsigned long)disk_ptr, RAID6_TEST_DISKS_ORDER); 393 394 return gen_best && rec_best ? 0 : -EINVAL; 395 } 396 397 static void raid6_exit(void) 398 { 399 do { } while (0); 400 } 401 402 subsys_initcall(raid6_select_algo); 403 module_exit(raid6_exit); 404 MODULE_LICENSE("GPL"); 405 MODULE_DESCRIPTION("RAID6 Q-syndrome calculations"); 406