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