git.sesse.net Git - bcachefs-tools-debian/blob - raid/test.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 "cpu.h"
  17 #include "combo.h"
  18 #include "memory.h"
  19
  20 /**
  21  * Binomial coefficient of n over r.
  22  */
  23 static int ibc(int n, int r)
  24 {
  25         if (r == 0 || n == r)
  26                 return 1;
  27         else
  28                 return ibc(n - 1, r - 1) + ibc(n - 1, r);
  29 }
  30
  31 /**
  32  * Power n ^ r;
  33  */
  34 static int ipow(int n, int r)
  35 {
  36         int v = 1;
  37
  38         while (r) {
  39                 v *= n;
  40                 --r;
  41         }
  42         return v;
  43 }
  44
  45 int raid_test_combo(void)
  46 {
  47         int r;
  48         int count;
  49         int p[RAID_PARITY_MAX];
  50
  51         for (r = 1; r <= RAID_PARITY_MAX; ++r) {
  52                 /* count combination (r of RAID_PARITY_MAX) elements */
  53                 count = 0;
  54                 combination_first(r, RAID_PARITY_MAX, p);
  55
  56                 do {
  57                         ++count;
  58                 } while (combination_next(r, RAID_PARITY_MAX, p));
  59
  60                 if (count != ibc(RAID_PARITY_MAX, r)) {
  61                         /* LCOV_EXCL_START */
  62                         return -1;
  63                         /* LCOV_EXCL_STOP */
  64                 }
  65         }
  66
  67         for (r = 1; r <= RAID_PARITY_MAX; ++r) {
  68                 /* count permutation (r of RAID_PARITY_MAX) elements */
  69                 count = 0;
  70                 permutation_first(r, RAID_PARITY_MAX, p);
  71
  72                 do {
  73                         ++count;
  74                 } while (permutation_next(r, RAID_PARITY_MAX, p));
  75
  76                 if (count != ipow(RAID_PARITY_MAX, r)) {
  77                         /* LCOV_EXCL_START */
  78                         return -1;
  79                         /* LCOV_EXCL_STOP */
  80                 }
  81         }
  82
  83         return 0;
  84 }
  85
  86 int raid_test_insert(void)
  87 {
  88         int p[RAID_PARITY_MAX];
  89         int r;
  90
  91         for (r = 1; r <= RAID_PARITY_MAX; ++r) {
  92                 permutation_first(r, RAID_PARITY_MAX, p);
  93                 do {
  94                         int i[RAID_PARITY_MAX];
  95                         int j;
  96
  97                         /* insert in order */
  98                         for (j = 0; j < r; ++j)
  99                                 raid_insert(j, i, p[j]);
 100
 101                         /* check order */
 102                         for (j = 1; j < r; ++j) {
 103                                 if (i[j - 1] > i[j]) {
 104                                         /* LCOV_EXCL_START */
 105                                         return -1;
 106                                         /* LCOV_EXCL_STOP */
 107                                 }
 108                         }
 109                 } while (permutation_next(r, RAID_PARITY_MAX, p));
 110         }
 111
 112         return 0;
 113 }
 114
 115 int raid_test_sort(void)
 116 {
 117         int p[RAID_PARITY_MAX];
 118         int r;
 119
 120         for (r = 1; r <= RAID_PARITY_MAX; ++r) {
 121                 permutation_first(r, RAID_PARITY_MAX, p);
 122                 do {
 123                         int i[RAID_PARITY_MAX];
 124                         int j;
 125
 126                         /* make a copy */
 127                         for (j = 0; j < r; ++j)
 128                                 i[j] = p[j];
 129
 130                         raid_sort(r, i);
 131
 132                         /* check order */
 133                         for (j = 1; j < r; ++j) {
 134                                 if (i[j - 1] > i[j]) {
 135                                         /* LCOV_EXCL_START */
 136                                         return -1;
 137                                         /* LCOV_EXCL_STOP */
 138                                 }
 139                         }
 140                 } while (permutation_next(r, RAID_PARITY_MAX, p));
 141         }
 142
 143         return 0;
 144 }
 145
 146 int raid_test_rec(int mode, int nd, size_t size)
 147 {
 148         void (*f[RAID_PARITY_MAX][4])(
 149                 int nr, int *id, int *ip, int nd, size_t size, void **vbuf);
 150         void *v_alloc;
 151         void **v;
 152         void **data;
 153         void **parity;
 154         void **test;
 155         void *data_save[RAID_PARITY_MAX];
 156         void *parity_save[RAID_PARITY_MAX];
 157         void *waste;
 158         int nv;
 159         int id[RAID_PARITY_MAX];
 160         int ip[RAID_PARITY_MAX];
 161         int i;
 162         int j;
 163         int nr;
 164         int nf[RAID_PARITY_MAX];
 165         int np;
 166
 167         raid_mode(mode);
 168         if (mode == RAID_MODE_CAUCHY)
 169                 np = RAID_PARITY_MAX;
 170         else
 171                 np = 3;
 172
 173         nv = nd + np * 2 + 2;
 174
 175         v = raid_malloc_vector(nd, nv, size, &v_alloc);
 176         if (!v) {
 177                 /* LCOV_EXCL_START */
 178                 return -1;
 179                 /* LCOV_EXCL_STOP */
 180         }
 181
 182         data = v;
 183         parity = v + nd;
 184         test = v + nd + np;
 185
 186         for (i = 0; i < np; ++i)
 187                 parity_save[i] = parity[i];
 188
 189         memset(v[nv - 2], 0, size);
 190         raid_zero(v[nv - 2]);
 191
 192         waste = v[nv - 1];
 193
 194         /* fill with pseudo-random data with the arbitrary seed "1" */
 195         raid_mrand_vector(1, nd, size, v);
 196
 197         /* setup recov functions */
 198         for (i = 0; i < np; ++i) {
 199                 nf[i] = 0;
 200                 if (i == 0) {
 201                         f[i][nf[i]++] = raid_rec1_int8;
 202 #ifdef CONFIG_X86
 203 #ifdef CONFIG_SSSE3
 204                         if (raid_cpu_has_ssse3())
 205                                 f[i][nf[i]++] = raid_rec1_ssse3;
 206 #endif
 207 #ifdef CONFIG_AVX2
 208                         if (raid_cpu_has_avx2())
 209                                 f[i][nf[i]++] = raid_rec1_avx2;
 210 #endif
 211 #endif
 212                 } else if (i == 1) {
 213                         f[i][nf[i]++] = raid_rec2_int8;
 214 #ifdef CONFIG_X86
 215 #ifdef CONFIG_SSSE3
 216                         if (raid_cpu_has_ssse3())
 217                                 f[i][nf[i]++] = raid_rec2_ssse3;
 218 #endif
 219 #ifdef CONFIG_AVX2
 220                         if (raid_cpu_has_avx2())
 221                                 f[i][nf[i]++] = raid_rec2_avx2;
 222 #endif
 223 #endif
 224                 } else {
 225                         f[i][nf[i]++] = raid_recX_int8;
 226 #ifdef CONFIG_X86
 227 #ifdef CONFIG_SSSE3
 228                         if (raid_cpu_has_ssse3())
 229                                 f[i][nf[i]++] = raid_recX_ssse3;
 230 #endif
 231 #ifdef CONFIG_AVX2
 232                         if (raid_cpu_has_avx2())
 233                                 f[i][nf[i]++] = raid_recX_avx2;
 234 #endif
 235 #endif
 236                 }
 237         }
 238
 239         /* compute the parity */
 240         raid_gen_ref(nd, np, size, v);
 241
 242         /* set all the parity to the waste v */
 243         for (i = 0; i < np; ++i)
 244                 parity[i] = waste;
 245
 246         /* all parity levels */
 247         for (nr = 1; nr <= np; ++nr) {
 248                 /* all combinations (nr of nd) disks */
 249                 combination_first(nr, nd, id);
 250                 do {
 251                         /* all combinations (nr of np) parities */
 252                         combination_first(nr, np, ip);
 253                         do {
 254                                 /* for each recover function */
 255                                 for (j = 0; j < nf[nr - 1]; ++j) {
 256                                         /* set */
 257                                         for (i = 0; i < nr; ++i) {
 258                                                 /* remove the missing data */
 259                                                 data_save[i] = data[id[i]];
 260                                                 data[id[i]] = test[i];
 261                                                 /* set the parity to use */
 262                                                 parity[ip[i]] = parity_save[ip[i]];
 263                                         }
 264
 265                                         /* recover */
 266                                         f[nr - 1][j](nr, id, ip, nd, size, v);
 267
 268                                         /* check */
 269                                         for (i = 0; i < nr; ++i) {
 270                                                 if (memcmp(test[i], data_save[i], size) != 0) {
 271                                                         /* LCOV_EXCL_START */
 272                                                         goto bail;
 273                                                         /* LCOV_EXCL_STOP */
 274                                                 }
 275                                         }
 276
 277                                         /* restore */
 278                                         for (i = 0; i < nr; ++i) {
 279                                                 /* restore the data */
 280                                                 data[id[i]] = data_save[i];
 281                                                 /* restore the parity */
 282                                                 parity[ip[i]] = waste;
 283                                         }
 284                                 }
 285                         } while (combination_next(nr, np, ip));
 286                 } while (combination_next(nr, nd, id));
 287         }
 288
 289         free(v_alloc);
 290         free(v);
 291         return 0;
 292
 293 bail:
 294         /* LCOV_EXCL_START */
 295         free(v_alloc);
 296         free(v);
 297         return -1;
 298         /* LCOV_EXCL_STOP */
 299 }
 300
 301 int raid_test_par(int mode, int nd, size_t size)
 302 {
 303         void (*f[64])(int nd, size_t size, void **vbuf);
 304         void *v_alloc;
 305         void **v;
 306         int nv;
 307         int i, j;
 308         int nf;
 309         int np;
 310
 311         raid_mode(mode);
 312         if (mode == RAID_MODE_CAUCHY)
 313                 np = RAID_PARITY_MAX;
 314         else
 315                 np = 3;
 316
 317         nv = nd + np * 2;
 318
 319         v = raid_malloc_vector(nd, nv, size, &v_alloc);
 320         if (!v) {
 321                 /* LCOV_EXCL_START */
 322                 return -1;
 323                 /* LCOV_EXCL_STOP */
 324         }
 325
 326         /* check memory */
 327         if (raid_mtest_vector(nv, size, v) != 0) {
 328                 /* LCOV_EXCL_START */
 329                 goto bail;
 330                 /* LCOV_EXCL_STOP */
 331         }
 332
 333         /* fill with pseudo-random data with the arbitrary seed "2" */
 334         raid_mrand_vector(2, nv, size, v);
 335
 336         /* compute the parity */
 337         raid_gen_ref(nd, np, size, v);
 338
 339         /* copy in back buffers */
 340         for (i = 0; i < np; ++i)
 341                 memcpy(v[nd + np + i], v[nd + i], size);
 342
 343         /* load all the available functions */
 344         nf = 0;
 345
 346         f[nf++] = raid_gen1_int32;
 347         f[nf++] = raid_gen1_int64;
 348         f[nf++] = raid_gen2_int32;
 349         f[nf++] = raid_gen2_int64;
 350
 351 #ifdef CONFIG_X86
 352 #ifdef CONFIG_SSE2
 353         if (raid_cpu_has_sse2()) {
 354                 f[nf++] = raid_gen1_sse2;
 355                 f[nf++] = raid_gen2_sse2;
 356 #ifdef CONFIG_X86_64
 357                 f[nf++] = raid_gen2_sse2ext;
 358 #endif
 359         }
 360 #endif
 361
 362 #ifdef CONFIG_AVX2
 363         if (raid_cpu_has_avx2()) {
 364                 f[nf++] = raid_gen1_avx2;
 365                 f[nf++] = raid_gen2_avx2;
 366         }
 367 #endif
 368 #endif /* CONFIG_X86 */
 369
 370         if (mode == RAID_MODE_CAUCHY) {
 371                 f[nf++] = raid_gen3_int8;
 372                 f[nf++] = raid_gen4_int8;
 373                 f[nf++] = raid_gen5_int8;
 374                 f[nf++] = raid_gen6_int8;
 375
 376 #ifdef CONFIG_X86
 377 #ifdef CONFIG_SSSE3
 378                 if (raid_cpu_has_ssse3()) {
 379                         f[nf++] = raid_gen3_ssse3;
 380                         f[nf++] = raid_gen4_ssse3;
 381                         f[nf++] = raid_gen5_ssse3;
 382                         f[nf++] = raid_gen6_ssse3;
 383 #ifdef CONFIG_X86_64
 384                         f[nf++] = raid_gen3_ssse3ext;
 385                         f[nf++] = raid_gen4_ssse3ext;
 386                         f[nf++] = raid_gen5_ssse3ext;
 387                         f[nf++] = raid_gen6_ssse3ext;
 388 #endif
 389                 }
 390 #endif
 391
 392 #ifdef CONFIG_AVX2
 393 #ifdef CONFIG_X86_64
 394                 if (raid_cpu_has_avx2()) {
 395                         f[nf++] = raid_gen3_avx2ext;
 396                         f[nf++] = raid_gen4_avx2ext;
 397                         f[nf++] = raid_gen5_avx2ext;
 398                         f[nf++] = raid_gen6_avx2ext;
 399                 }
 400 #endif
 401 #endif
 402 #endif /* CONFIG_X86 */
 403         } else {
 404                 f[nf++] = raid_genz_int32;
 405                 f[nf++] = raid_genz_int64;
 406
 407 #ifdef CONFIG_X86
 408 #ifdef CONFIG_SSE2
 409                 if (raid_cpu_has_sse2()) {
 410                         f[nf++] = raid_genz_sse2;
 411 #ifdef CONFIG_X86_64
 412                         f[nf++] = raid_genz_sse2ext;
 413 #endif
 414                 }
 415 #endif
 416
 417 #ifdef CONFIG_AVX2
 418 #ifdef CONFIG_X86_64
 419                 if (raid_cpu_has_avx2())
 420                         f[nf++] = raid_genz_avx2ext;
 421 #endif
 422 #endif
 423 #endif /* CONFIG_X86 */
 424         }
 425
 426         /* check all the functions */
 427         for (j = 0; j < nf; ++j) {
 428                 /* compute parity */
 429                 f[j](nd, size, v);
 430
 431                 /* check it */
 432                 for (i = 0; i < np; ++i) {
 433                         if (memcmp(v[nd + np + i], v[nd + i], size) != 0) {
 434                                 /* LCOV_EXCL_START */
 435                                 goto bail;
 436                                 /* LCOV_EXCL_STOP */
 437                         }
 438                 }
 439         }
 440
 441         free(v_alloc);
 442         free(v);
 443         return 0;
 444
 445 bail:
 446         /* LCOV_EXCL_START */
 447         free(v_alloc);
 448         free(v);
 449         return -1;
 450         /* LCOV_EXCL_STOP */
 451 }
 452