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