git.sesse.net Git - bcachefs-tools-debian/blob - c_src/raid/module.c

   1 /*
   2  * Copyright (C) 2013 Andrea Mazzoleni
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  */
  14
  15 #include "internal.h"
  16 #include "memory.h"
  17 #include "cpu.h"
  18
  19 /*
  20  * Initializes and selects the best algorithm.
  21  */
  22 void raid_init(void)
  23 {
  24         raid_gen3_ptr = raid_gen3_int8;
  25         raid_gen_ptr[3] = raid_gen4_int8;
  26         raid_gen_ptr[4] = raid_gen5_int8;
  27         raid_gen_ptr[5] = raid_gen6_int8;
  28
  29         if (sizeof(void *) == 4) {
  30                 raid_gen_ptr[0] = raid_gen1_int32;
  31                 raid_gen_ptr[1] = raid_gen2_int32;
  32                 raid_genz_ptr = raid_genz_int32;
  33         } else {
  34                 raid_gen_ptr[0] = raid_gen1_int64;
  35                 raid_gen_ptr[1] = raid_gen2_int64;
  36                 raid_genz_ptr = raid_genz_int64;
  37         }
  38
  39         raid_rec_ptr[0] = raid_rec1_int8;
  40         raid_rec_ptr[1] = raid_rec2_int8;
  41         raid_rec_ptr[2] = raid_recX_int8;
  42         raid_rec_ptr[3] = raid_recX_int8;
  43         raid_rec_ptr[4] = raid_recX_int8;
  44         raid_rec_ptr[5] = raid_recX_int8;
  45
  46 #ifdef CONFIG_X86
  47 #ifdef CONFIG_SSE2
  48         if (raid_cpu_has_sse2()) {
  49                 raid_gen_ptr[0] = raid_gen1_sse2;
  50 #ifdef CONFIG_X86_64
  51                 if (raid_cpu_has_slowextendedreg()) {
  52                         raid_gen_ptr[1] = raid_gen2_sse2;
  53                 } else {
  54                         raid_gen_ptr[1] = raid_gen2_sse2ext;
  55                 }
  56                 /* note that raid_cpu_has_slowextendedreg() doesn't affect parz */
  57                 raid_genz_ptr = raid_genz_sse2ext;
  58 #else
  59                 raid_gen_ptr[1] = raid_gen2_sse2;
  60                 raid_genz_ptr = raid_genz_sse2;
  61 #endif
  62         }
  63 #endif
  64
  65 #ifdef CONFIG_SSSE3
  66         if (raid_cpu_has_ssse3()) {
  67 #ifdef CONFIG_X86_64
  68                 if (raid_cpu_has_slowextendedreg()) {
  69                         raid_gen3_ptr = raid_gen3_ssse3;
  70                         raid_gen_ptr[3] = raid_gen4_ssse3;
  71                         raid_gen_ptr[4] = raid_gen5_ssse3;
  72                         raid_gen_ptr[5] = raid_gen6_ssse3;
  73                 } else {
  74                         raid_gen3_ptr = raid_gen3_ssse3ext;
  75                         raid_gen_ptr[3] = raid_gen4_ssse3ext;
  76                         raid_gen_ptr[4] = raid_gen5_ssse3ext;
  77                         raid_gen_ptr[5] = raid_gen6_ssse3ext;
  78                 }
  79 #else
  80                 raid_gen3_ptr = raid_gen3_ssse3;
  81                 raid_gen_ptr[3] = raid_gen4_ssse3;
  82                 raid_gen_ptr[4] = raid_gen5_ssse3;
  83                 raid_gen_ptr[5] = raid_gen6_ssse3;
  84 #endif
  85                 raid_rec_ptr[0] = raid_rec1_ssse3;
  86                 raid_rec_ptr[1] = raid_rec2_ssse3;
  87                 raid_rec_ptr[2] = raid_recX_ssse3;
  88                 raid_rec_ptr[3] = raid_recX_ssse3;
  89                 raid_rec_ptr[4] = raid_recX_ssse3;
  90                 raid_rec_ptr[5] = raid_recX_ssse3;
  91         }
  92 #endif
  93
  94 #ifdef CONFIG_AVX2
  95         if (raid_cpu_has_avx2()) {
  96                 raid_gen_ptr[0] = raid_gen1_avx2;
  97                 raid_gen_ptr[1] = raid_gen2_avx2;
  98 #ifdef CONFIG_X86_64
  99                 raid_gen3_ptr = raid_gen3_avx2ext;
 100                 raid_genz_ptr = raid_genz_avx2ext;
 101                 raid_gen_ptr[3] = raid_gen4_avx2ext;
 102                 raid_gen_ptr[4] = raid_gen5_avx2ext;
 103                 raid_gen_ptr[5] = raid_gen6_avx2ext;
 104 #endif
 105                 raid_rec_ptr[0] = raid_rec1_avx2;
 106                 raid_rec_ptr[1] = raid_rec2_avx2;
 107                 raid_rec_ptr[2] = raid_recX_avx2;
 108                 raid_rec_ptr[3] = raid_recX_avx2;
 109                 raid_rec_ptr[4] = raid_recX_avx2;
 110                 raid_rec_ptr[5] = raid_recX_avx2;
 111         }
 112 #endif
 113 #endif /* CONFIG_X86 */
 114
 115         /* set the default mode */
 116         raid_mode(RAID_MODE_CAUCHY);
 117 }
 118
 119 /*
 120  * Reference parity computation.
 121  */
 122 void raid_gen_ref(int nd, int np, size_t size, void **vv)
 123 {
 124         uint8_t **v = (uint8_t **)vv;
 125         size_t i;
 126
 127         for (i = 0; i < size; ++i) {
 128                 uint8_t p[RAID_PARITY_MAX];
 129                 int j, d;
 130
 131                 for (j = 0; j < np; ++j)
 132                         p[j] = 0;
 133
 134                 for (d = 0; d < nd; ++d) {
 135                         uint8_t b = v[d][i];
 136
 137                         for (j = 0; j < np; ++j)
 138                                 p[j] ^= gfmul[b][gfgen[j][d]];
 139                 }
 140
 141                 for (j = 0; j < np; ++j)
 142                         v[nd + j][i] = p[j];
 143         }
 144 }
 145
 146 /*
 147  * Size of the blocks to test.
 148  */
 149 #define TEST_SIZE 4096
 150
 151 /*
 152  * Number of data blocks to test.
 153  */
 154 #define TEST_COUNT (65536 / TEST_SIZE)
 155
 156 /*
 157  * Parity generation test.
 158  */
 159 static int raid_test_par(int nd, int np, size_t size, void **v, void **ref)
 160 {
 161         int i;
 162         void *t[TEST_COUNT + RAID_PARITY_MAX];
 163
 164         /* setup data */
 165         for (i = 0; i < nd; ++i)
 166                 t[i] = ref[i];
 167
 168         /* setup parity */
 169         for (i = 0; i < np; ++i)
 170                 t[nd + i] = v[nd + i];
 171
 172         raid_gen(nd, np, size, t);
 173
 174         /* compare parity */
 175         for (i = 0; i < np; ++i) {
 176                 if (memcmp(t[nd + i], ref[nd + i], size) != 0) {
 177                         /* LCOV_EXCL_START */
 178                         return -1;
 179                         /* LCOV_EXCL_STOP */
 180                 }
 181         }
 182
 183         return 0;
 184 }
 185
 186 /*
 187  * Recovering test.
 188  */
 189 static int raid_test_rec(int nr, int *ir, int nd, int np, size_t size, void **v, void **ref)
 190 {
 191         int i, j;
 192         void *t[TEST_COUNT + RAID_PARITY_MAX];
 193
 194         /* setup data and parity vector */
 195         for (i = 0, j = 0; i < nd + np; ++i) {
 196                 if (j < nr && ir[j] == i) {
 197                         /* this block has to be recovered */
 198                         t[i] = v[i];
 199                         ++j;
 200                 } else {
 201                         /* this block is used for recovering */
 202                         t[i] = ref[i];
 203                 }
 204         }
 205
 206         raid_rec(nr, ir, nd, np, size, t);
 207
 208         /* compare all data and parity */
 209         for (i = 0; i < nd + np; ++i) {
 210                 if (t[i] != ref[i]
 211                         && memcmp(t[i], ref[i], size) != 0) {
 212                         /* LCOV_EXCL_START */
 213                         return -1;
 214                         /* LCOV_EXCL_STOP */
 215                 }
 216         }
 217
 218         return 0;
 219 }
 220
 221 /*
 222  * Recovering test for data.
 223  */
 224 static int raid_test_data(int nr, int *id, int *ip, int nd, int np, size_t size, void **v, void **ref)
 225 {
 226         int i, j;
 227         void *t[TEST_COUNT + RAID_PARITY_MAX];
 228
 229         /* setup data vector */
 230         for (i = 0, j = 0; i < nd; ++i) {
 231                 if (j < nr && id[j] == i) {
 232                         /* this block has to be recovered */
 233                         t[i] = v[i];
 234                         ++j;
 235                 } else {
 236                         /* this block is left unchanged */
 237                         t[i] = ref[i];
 238                 }
 239         }
 240
 241         /* setup parity vector */
 242         for (i = 0, j = 0; i < np; ++i) {
 243                 if (j < nr && ip[j] == i) {
 244                         /* this block is used for recovering */
 245                         t[nd + i] = ref[nd + i];
 246                         ++j;
 247                 } else {
 248                         /* this block should not be read or written */
 249                         t[nd + i] = 0;
 250                 }
 251         }
 252
 253         raid_data(nr, id, ip, nd, size, t);
 254
 255         /* compare all data and parity */
 256         for (i = 0; i < nd; ++i) {
 257                 if (t[i] != ref[i]
 258                         && t[i] != 0
 259                         && memcmp(t[i], ref[i], size) != 0) {
 260                         /* LCOV_EXCL_START */
 261                         return -1;
 262                         /* LCOV_EXCL_STOP */
 263                 }
 264         }
 265
 266         return 0;
 267 }
 268
 269 /*
 270  * Scan test.
 271  */
 272 static int raid_test_scan(int nr, int *ir, int nd, int np, size_t size, void **v, void **ref)
 273 {
 274         int i, j, ret;
 275         void *t[TEST_COUNT + RAID_PARITY_MAX];
 276         int is[RAID_PARITY_MAX];
 277
 278         /* setup data and parity vector */
 279         for (i = 0, j = 0; i < nd + np; ++i) {
 280                 if (j < nr && ir[j] == i) {
 281                         /* this block is bad */
 282                         t[i] = v[i];
 283                         ++j;
 284                 } else {
 285                         /* this block is used for recovering */
 286                         t[i] = ref[i];
 287                 }
 288         }
 289
 290         ret = raid_scan(is, nd, np, size, t);
 291
 292         /* compare identified bad blocks */
 293         if (ret != nr)
 294                 return -1;
 295         for (i = 0; i < nr; ++i) {
 296                 if (ir[i] != is[i]) {
 297                         /* LCOV_EXCL_START */
 298                         return -1;
 299                         /* LCOV_EXCL_STOP */
 300                 }
 301         }
 302
 303         return 0;
 304 }
 305
 306 /*
 307  * Basic functionality self test.
 308  */
 309 int raid_selftest(void)
 310 {
 311         const int nd = TEST_COUNT;
 312         const size_t size = TEST_SIZE;
 313         const int nv = nd + RAID_PARITY_MAX * 2 + 1;
 314         void *v_alloc;
 315         void **v;
 316         void *ref[nd + RAID_PARITY_MAX];
 317         int ir[RAID_PARITY_MAX];
 318         int ip[RAID_PARITY_MAX];
 319         int i, np;
 320         int ret = 0;
 321
 322         /* ensure to have enough space for data */
 323         BUG_ON(nd * size > 65536);
 324
 325         v = raid_malloc_vector(nd, nv, size, &v_alloc);
 326         if (!v) {
 327                 /* LCOV_EXCL_START */
 328                 return -1;
 329                 /* LCOV_EXCL_STOP */
 330         }
 331
 332         memset(v[nv - 1], 0, size);
 333         raid_zero(v[nv - 1]);
 334
 335         /* use the multiplication table as data */
 336         for (i = 0; i < nd; ++i)
 337                 ref[i] = ((uint8_t *)gfmul) + size * i;
 338
 339         /* setup reference parity */
 340         for (i = 0; i < RAID_PARITY_MAX; ++i)
 341                 ref[nd + i] = v[nd + RAID_PARITY_MAX + i];
 342
 343         /* compute reference parity */
 344         raid_gen_ref(nd, RAID_PARITY_MAX, size, ref);
 345
 346         /* test for each parity level */
 347         for (np = 1; np <= RAID_PARITY_MAX; ++np) {
 348                 /* test parity generation */
 349                 ret = raid_test_par(nd, np, size, v, ref);
 350                 if (ret != 0) {
 351                         /* LCOV_EXCL_START */
 352                         goto bail;
 353                         /* LCOV_EXCL_STOP */
 354                 }
 355
 356                 /* test recovering with broken ending data disks */
 357                 for (i = 0; i < np; ++i) {
 358                         /* bad data */
 359                         ir[i] = nd - np + i;
 360
 361                         /* good parity */
 362                         ip[i] = i;
 363                 }
 364
 365                 ret = raid_test_rec(np, ir, nd, np, size, v, ref);
 366                 if (ret != 0) {
 367                         /* LCOV_EXCL_START */
 368                         goto bail;
 369                         /* LCOV_EXCL_STOP */
 370                 }
 371
 372                 ret = raid_test_data(np, ir, ip, nd, np, size, v, ref);
 373                 if (ret != 0) {
 374                         /* LCOV_EXCL_START */
 375                         goto bail;
 376                         /* LCOV_EXCL_STOP */
 377                 }
 378
 379                 /* test recovering with broken leading data and broken leading parity */
 380                 for (i = 0; i < np / 2; ++i) {
 381                         /* bad data */
 382                         ir[i] = i;
 383
 384                         /* good parity */
 385                         ip[i] = (np + 1) / 2 + i;
 386                 }
 387
 388                 /* bad parity */
 389                 for (i = 0; i < (np + 1) / 2; ++i)
 390                         ir[np / 2 + i] = nd + i;
 391
 392                 ret = raid_test_rec(np, ir, nd, np, size, v, ref);
 393                 if (ret != 0) {
 394                         /* LCOV_EXCL_START */
 395                         goto bail;
 396                         /* LCOV_EXCL_STOP */
 397                 }
 398
 399                 ret = raid_test_data(np / 2, ir, ip, nd, np, size, v, ref);
 400                 if (ret != 0) {
 401                         /* LCOV_EXCL_START */
 402                         goto bail;
 403                         /* LCOV_EXCL_STOP */
 404                 }
 405
 406                 /* test recovering with broken leading data and broken ending parity */
 407                 for (i = 0; i < np / 2; ++i) {
 408                         /* bad data */
 409                         ir[i] = i;
 410
 411                         /* good parity */
 412                         ip[i] = i;
 413                 }
 414
 415                 /* bad parity */
 416                 for (i = 0; i < (np + 1) / 2; ++i)
 417                         ir[np / 2 + i] = nd + np - (np + 1) / 2 + i;
 418
 419                 ret = raid_test_rec(np, ir, nd, np, size, v, ref);
 420                 if (ret != 0) {
 421                         /* LCOV_EXCL_START */
 422                         goto bail;
 423                         /* LCOV_EXCL_STOP */
 424                 }
 425
 426                 ret = raid_test_data(np / 2, ir, ip, nd, np, size, v, ref);
 427                 if (ret != 0) {
 428                         /* LCOV_EXCL_START */
 429                         goto bail;
 430                         /* LCOV_EXCL_STOP */
 431                 }
 432
 433                 /* scan test with broken data and parity */
 434                 for (i = 0; i < np / 2; ++i) {
 435                         /* bad data */
 436                         ir[i] = i;
 437                 }
 438                 for (i = 0; i < (np - 1) / 2; ++i) {
 439                         /* bad parity */
 440                         ir[np / 2 + i] = nd + i;
 441                 }
 442                 for (i = 0; i < np - 1; ++i) {
 443                         /* make blocks bad */
 444                         /* we cannot fill them with 0, because the original */
 445                         /* data may be already filled with 0 */
 446                         memset(v[ir[i]], 0x55, size);
 447                 }
 448
 449                 ret = raid_test_scan(np - 1, ir, nd, np, size, v, ref);
 450                 if (ret != 0) {
 451                         /* LCOV_EXCL_START */
 452                         goto bail;
 453                         /* LCOV_EXCL_STOP */
 454                 }
 455         }
 456
 457         /* scan test with no parity */
 458         ret = raid_test_scan(0, 0, nd, 0, size, v, ref);
 459         if (ret != -1) {
 460                 /* LCOV_EXCL_START */
 461                 goto bail;
 462                 /* LCOV_EXCL_STOP */
 463         }
 464
 465         ret = 0;
 466
 467 bail:
 468         free(v);
 469         free(v_alloc);
 470
 471         return ret;
 472 }
 473