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 #define RAID6_MAX_ALGOS 16 21 static const struct raid6_calls *raid6_algos[RAID6_MAX_ALGOS]; 22 static unsigned int raid6_nr_algos; 23 static const struct raid6_recov_calls *raid6_recov_algo; 24 25 /* Selected algorithm */ 26 static struct raid6_calls raid6_call; 27 28 /** 29 * raid6_gen_syndrome - generate RAID6 P/Q parity 30 * @disks: number of "disks" to operate on including parity 31 * @bytes: length in bytes of each vector 32 * @ptrs: @disks size array of memory pointers 33 * 34 * Generate @bytes worth of RAID6 P and Q parity in @ptrs[@disks - 2] and 35 * @ptrs[@disks - 1] respectively from the memory pointed to by @ptrs[0] to 36 * @ptrs[@disks - 3]. 37 * 38 * @disks must be at least 4, and the memory pointed to by each member of @ptrs 39 * must be at least 64-byte aligned. @bytes must be non-zero and a multiple of 40 * 512. 41 * 42 * See https://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf for underlying 43 * algorithm. 44 */ 45 void raid6_gen_syndrome(int disks, size_t bytes, void **ptrs) 46 { 47 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 48 WARN_ON_ONCE(bytes & 511); 49 WARN_ON_ONCE(disks < RAID6_MIN_DISKS); 50 51 raid6_call.gen_syndrome(disks, bytes, ptrs); 52 } 53 EXPORT_SYMBOL_GPL(raid6_gen_syndrome); 54 55 /** 56 * raid6_xor_syndrome - update RAID6 P/Q parity 57 * @disks: number of "disks" to operate on including parity 58 * @start: first index into @disk to update 59 * @stop: last index into @disk to update 60 * @bytes: length in bytes of each vector 61 * @ptrs: @disks size array of memory pointers 62 * 63 * Update @bytes worth of RAID6 P and Q parity in @ptrs[@disks - 2] and 64 * @ptrs[@disks - 1] respectively for the memory pointed to by 65 * @ptrs[@start..@stop]. 66 * 67 * This is used to update parity in place using the following sequence: 68 * 69 * 1) call raid6_xor_syndrome(disk, start, stop, ...) for the existing data. 70 * 2) update the the data in @ptrs[@start..@stop]. 71 * 3) call raid6_xor_syndrome(disk, start, stop, ...) for the new data. 72 * 73 * Data between @start and @stop that is not changed should be filled 74 * with a pointer to the kernel zero page. 75 * 76 * @disks must be at least 4, and the memory pointed to by each member of @ptrs 77 * must be at least 64-byte aligned. @bytes must be non-zero and a multiple of 78 * 512. @stop must be larger or equal to @start. 79 */ 80 void raid6_xor_syndrome(int disks, int start, int stop, size_t bytes, 81 void **ptrs) 82 { 83 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 84 WARN_ON_ONCE(bytes & 511); 85 WARN_ON_ONCE(disks < RAID6_MIN_DISKS); 86 WARN_ON_ONCE(stop < start); 87 88 raid6_call.xor_syndrome(disks, start, stop, bytes, ptrs); 89 } 90 EXPORT_SYMBOL_GPL(raid6_xor_syndrome); 91 92 /* 93 * raid6_can_xor_syndrome - check if raid6_xor_syndrome() can be used 94 * 95 * Returns %true if raid6_can_xor_syndrome() can be used, else %false. 96 */ 97 bool raid6_can_xor_syndrome(void) 98 { 99 return !!raid6_call.xor_syndrome; 100 } 101 EXPORT_SYMBOL_GPL(raid6_can_xor_syndrome); 102 103 /** 104 * raid6_recov_2data - recover two missing data disks 105 * @disks: number of "disks" to operate on including parity 106 * @bytes: length in bytes of each vector 107 * @faila: first failed data disk index 108 * @failb: second failed data disk index 109 * @ptrs: @disks size array of memory pointers 110 * 111 * Rebuild @bytes of missing data in @ptrs[@faila] and @ptrs[@failb] from the 112 * data in the remaining disks and the two parities pointed to by the other 113 * indices between 0 and @disks - 1 in @ptrs. @disks includes the data disks 114 * and the two parities. @faila must be smaller than @failb. 115 * 116 * Memory pointed to by each pointer in @ptrs must be page aligned and is 117 * limited to %PAGE_SIZE. 118 */ 119 void raid6_recov_2data(int disks, size_t bytes, int faila, int failb, 120 void **ptrs) 121 { 122 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 123 WARN_ON_ONCE(bytes & 511); 124 WARN_ON_ONCE(bytes > PAGE_SIZE); 125 WARN_ON_ONCE(failb <= faila); 126 127 raid6_recov_algo->data2(disks, bytes, faila, failb, ptrs); 128 } 129 EXPORT_SYMBOL_GPL(raid6_recov_2data); 130 131 /** 132 * raid6_recov_datap - recover a missing data disk and missing P-parity 133 * @disks: number of "disks" to operate on including parity 134 * @bytes: length in bytes of each vector 135 * @faila: failed data disk index 136 * @ptrs: @disks size array of memory pointers 137 * 138 * Rebuild @bytes of missing data in @ptrs[@faila] and the missing P-parity in 139 * @ptrs[@disks - 2] from the data in the remaining disks and the Q-parity 140 * pointed to by the other indices between 0 and @disks - 1 in @ptrs. @disks 141 * includes the data disks and the two parities. 142 * 143 * Memory pointed to by each pointer in @ptrs must be page aligned and is 144 * limited to %PAGE_SIZE. 145 */ 146 void raid6_recov_datap(int disks, size_t bytes, int faila, void **ptrs) 147 { 148 WARN_ON_ONCE(!in_task() || irqs_disabled() || softirq_count()); 149 WARN_ON_ONCE(bytes & 511); 150 WARN_ON_ONCE(bytes > PAGE_SIZE); 151 152 raid6_recov_algo->datap(disks, bytes, faila, ptrs); 153 } 154 EXPORT_SYMBOL_GPL(raid6_recov_datap); 155 156 #define RAID6_TIME_JIFFIES_LG2 4 157 #define RAID6_TEST_DISKS 8 158 #define RAID6_TEST_DISKS_ORDER 3 159 160 static int raid6_choose_gen(void *(*const dptrs)[RAID6_TEST_DISKS], 161 const int disks) 162 { 163 /* work on the second half of the disks */ 164 int start = (disks >> 1) - 1, stop = disks - 3; 165 const struct raid6_calls *best = NULL; 166 unsigned long bestgenperf = 0; 167 unsigned int i; 168 169 for (i = 0; i < raid6_nr_algos; i++) { 170 const struct raid6_calls *algo = raid6_algos[i]; 171 unsigned long perf = 0, j0, j1; 172 173 preempt_disable(); 174 j0 = jiffies; 175 while ((j1 = jiffies) == j0) 176 cpu_relax(); 177 while (time_before(jiffies, 178 j1 + (1<<RAID6_TIME_JIFFIES_LG2))) { 179 algo->gen_syndrome(disks, PAGE_SIZE, *dptrs); 180 perf++; 181 } 182 preempt_enable(); 183 184 if (perf > bestgenperf) { 185 bestgenperf = perf; 186 best = algo; 187 } 188 pr_info("raid6: %-8s gen() %5ld MB/s\n", algo->name, 189 (perf * HZ * (disks-2)) >> 190 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2)); 191 } 192 193 if (!best) { 194 pr_err("raid6: Yikes! No algorithm found!\n"); 195 return -EINVAL; 196 } 197 198 raid6_call = *best; 199 200 pr_info("raid6: using algorithm %s gen() %ld MB/s\n", 201 best->name, 202 (bestgenperf * HZ * (disks - 2)) >> 203 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2)); 204 205 if (best->xor_syndrome) { 206 unsigned long perf = 0, j0, j1; 207 208 preempt_disable(); 209 j0 = jiffies; 210 while ((j1 = jiffies) == j0) 211 cpu_relax(); 212 while (time_before(jiffies, 213 j1 + (1 << RAID6_TIME_JIFFIES_LG2))) { 214 best->xor_syndrome(disks, start, stop, 215 PAGE_SIZE, *dptrs); 216 perf++; 217 } 218 preempt_enable(); 219 220 pr_info("raid6: .... xor() %ld MB/s, rmw enabled\n", 221 (perf * HZ * (disks - 2)) >> 222 (20 - PAGE_SHIFT + RAID6_TIME_JIFFIES_LG2 + 1)); 223 } 224 225 return 0; 226 } 227 228 229 /* Try to pick the best algorithm */ 230 /* This code uses the gfmul table as convenient data set to abuse */ 231 232 static int __init raid6_select_algo(void) 233 { 234 const int disks = RAID6_TEST_DISKS; 235 char *disk_ptr, *p; 236 void *dptrs[RAID6_TEST_DISKS]; 237 int i, cycle; 238 int error; 239 240 if (!IS_ENABLED(CONFIG_RAID6_PQ_BENCHMARK) || raid6_nr_algos == 1) { 241 pr_info("raid6: skipped pq benchmark and selected %s\n", 242 raid6_algos[raid6_nr_algos - 1]->name); 243 raid6_call = *raid6_algos[raid6_nr_algos - 1]; 244 return 0; 245 } 246 247 /* prepare the buffer and fill it circularly with gfmul table */ 248 disk_ptr = (char *)__get_free_pages(GFP_KERNEL, RAID6_TEST_DISKS_ORDER); 249 if (!disk_ptr) { 250 pr_err("raid6: Yikes! No memory available.\n"); 251 return -ENOMEM; 252 } 253 254 p = disk_ptr; 255 for (i = 0; i < disks; i++) 256 dptrs[i] = p + PAGE_SIZE * i; 257 258 cycle = ((disks - 2) * PAGE_SIZE) / 65536; 259 for (i = 0; i < cycle; i++) { 260 memcpy(p, raid6_gfmul, 65536); 261 p += 65536; 262 } 263 264 if ((disks - 2) * PAGE_SIZE % 65536) 265 memcpy(p, raid6_gfmul, (disks - 2) * PAGE_SIZE % 65536); 266 267 /* select raid gen_syndrome function */ 268 error = raid6_choose_gen(&dptrs, disks); 269 270 free_pages((unsigned long)disk_ptr, RAID6_TEST_DISKS_ORDER); 271 272 return error; 273 } 274 275 /* 276 * Register a RAID6 P/Q generation algorithm. The most optimized/unrolled 277 * implementation should be registered last so it will be selected when the 278 * boot-time benchmark is disabled. 279 */ 280 void __init raid6_algo_add(const struct raid6_calls *algo) 281 { 282 if (WARN_ON_ONCE(raid6_nr_algos == RAID6_MAX_ALGOS)) 283 return; 284 raid6_algos[raid6_nr_algos++] = algo; 285 } 286 287 void __init raid6_algo_add_default(void) 288 { 289 raid6_algo_add(&raid6_intx1); 290 raid6_algo_add(&raid6_intx2); 291 raid6_algo_add(&raid6_intx4); 292 raid6_algo_add(&raid6_intx8); 293 } 294 295 void __init raid6_recov_algo_add(const struct raid6_recov_calls *algo) 296 { 297 if (WARN_ON_ONCE(raid6_recov_algo)) 298 return; 299 raid6_recov_algo = algo; 300 } 301 302 #ifdef CONFIG_RAID6_PQ_ARCH 303 #include "pq_arch.h" 304 #else 305 static inline void arch_raid6_init(void) 306 { 307 raid6_algo_add_default(); 308 } 309 #endif /* CONFIG_RAID6_PQ_ARCH */ 310 311 static int __init raid6_init(void) 312 { 313 /* 314 * Architectures providing arch_raid6_init must add all PQ generation 315 * algorithms they want to consider in arch_raid6_init(), including 316 * the generic ones using raid6_algo_add_default() if wanted. 317 */ 318 arch_raid6_init(); 319 320 /* 321 * Architectures don't have to set a recovery algorithm, we'll just pick 322 * the generic integer one if none was set. 323 */ 324 if (!raid6_recov_algo) 325 raid6_recov_algo = &raid6_recov_intx1; 326 pr_info("raid6: using %s recovery algorithm\n", raid6_recov_algo->name); 327 328 return raid6_select_algo(); 329 } 330 331 static void __exit raid6_exit(void) 332 { 333 } 334 335 subsys_initcall(raid6_init); 336 module_exit(raid6_exit); 337 MODULE_LICENSE("GPL"); 338 MODULE_DESCRIPTION("RAID6 Q-syndrome calculations"); 339 340 #if IS_ENABLED(CONFIG_RAID6_PQ_KUNIT_TEST) 341 const struct raid6_calls *raid6_algo_find(unsigned int idx) 342 { 343 if (idx >= raid6_nr_algos) { 344 /* 345 * Always include the simplest generic integer implementation in 346 * the unit tests as a baseline. 347 */ 348 if (idx == raid6_nr_algos && 349 raid6_algos[0] != &raid6_intx1) 350 return &raid6_intx1; 351 return NULL; 352 } 353 return raid6_algos[idx]; 354 } 355 EXPORT_SYMBOL_IF_KUNIT(raid6_algo_find); 356 357 const struct raid6_recov_calls *raid6_recov_algo_find(unsigned int idx) 358 { 359 switch (idx) { 360 case 0: 361 /* always test the generic integer implementation */ 362 return &raid6_recov_intx1; 363 case 1: 364 /* test the optimized implementation if there is one */ 365 if (raid6_recov_algo != &raid6_recov_intx1) 366 return raid6_recov_algo; 367 return NULL; 368 default: 369 return NULL; 370 } 371 } 372 EXPORT_SYMBOL_IF_KUNIT(raid6_recov_algo_find); 373 #endif /* CONFIG_RAID6_PQ_KUNIT_TEST */ 374