git.sesse.net Git - bcachefs-tools-debian/blob - raid/int.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 "gf.h"
  17
  18 /*
  19  * GEN1 (RAID5 with xor) 32bit C implementation
  20  */
  21 void raid_gen1_int32(int nd, size_t size, void **vv)
  22 {
  23         uint8_t **v = (uint8_t **)vv;
  24         uint8_t *p;
  25         int d, l;
  26         size_t i;
  27
  28         uint32_t p0;
  29         uint32_t p1;
  30
  31         l = nd - 1;
  32         p = v[nd];
  33
  34         for (i = 0; i < size; i += 8) {
  35                 p0 = v_32(v[l][i]);
  36                 p1 = v_32(v[l][i + 4]);
  37                 for (d = l - 1; d >= 0; --d) {
  38                         p0 ^= v_32(v[d][i]);
  39                         p1 ^= v_32(v[d][i + 4]);
  40                 }
  41                 v_32(p[i]) = p0;
  42                 v_32(p[i + 4]) = p1;
  43         }
  44 }
  45
  46 /*
  47  * GEN1 (RAID5 with xor) 64bit C implementation
  48  */
  49 void raid_gen1_int64(int nd, size_t size, void **vv)
  50 {
  51         uint8_t **v = (uint8_t **)vv;
  52         uint8_t *p;
  53         int d, l;
  54         size_t i;
  55
  56         uint64_t p0;
  57         uint64_t p1;
  58
  59         l = nd - 1;
  60         p = v[nd];
  61
  62         for (i = 0; i < size; i += 16) {
  63                 p0 = v_64(v[l][i]);
  64                 p1 = v_64(v[l][i + 8]);
  65                 for (d = l - 1; d >= 0; --d) {
  66                         p0 ^= v_64(v[d][i]);
  67                         p1 ^= v_64(v[d][i + 8]);
  68                 }
  69                 v_64(p[i]) = p0;
  70                 v_64(p[i + 8]) = p1;
  71         }
  72 }
  73
  74 /*
  75  * GEN2 (RAID6 with powers of 2) 32bit C implementation
  76  */
  77 void raid_gen2_int32(int nd, size_t size, void **vv)
  78 {
  79         uint8_t **v = (uint8_t **)vv;
  80         uint8_t *p;
  81         uint8_t *q;
  82         int d, l;
  83         size_t i;
  84
  85         uint32_t d0, q0, p0;
  86         uint32_t d1, q1, p1;
  87
  88         l = nd - 1;
  89         p = v[nd];
  90         q = v[nd + 1];
  91
  92         for (i = 0; i < size; i += 8) {
  93                 q0 = p0 = v_32(v[l][i]);
  94                 q1 = p1 = v_32(v[l][i + 4]);
  95                 for (d = l - 1; d >= 0; --d) {
  96                         d0 = v_32(v[d][i]);
  97                         d1 = v_32(v[d][i + 4]);
  98
  99                         p0 ^= d0;
 100                         p1 ^= d1;
 101
 102                         q0 = x2_32(q0);
 103                         q1 = x2_32(q1);
 104
 105                         q0 ^= d0;
 106                         q1 ^= d1;
 107                 }
 108                 v_32(p[i]) = p0;
 109                 v_32(p[i + 4]) = p1;
 110                 v_32(q[i]) = q0;
 111                 v_32(q[i + 4]) = q1;
 112         }
 113 }
 114
 115 /*
 116  * GEN2 (RAID6 with powers of 2) 64bit C implementation
 117  */
 118 void raid_gen2_int64(int nd, size_t size, void **vv)
 119 {
 120         uint8_t **v = (uint8_t **)vv;
 121         uint8_t *p;
 122         uint8_t *q;
 123         int d, l;
 124         size_t i;
 125
 126         uint64_t d0, q0, p0;
 127         uint64_t d1, q1, p1;
 128
 129         l = nd - 1;
 130         p = v[nd];
 131         q = v[nd + 1];
 132
 133         for (i = 0; i < size; i += 16) {
 134                 q0 = p0 = v_64(v[l][i]);
 135                 q1 = p1 = v_64(v[l][i + 8]);
 136                 for (d = l - 1; d >= 0; --d) {
 137                         d0 = v_64(v[d][i]);
 138                         d1 = v_64(v[d][i + 8]);
 139
 140                         p0 ^= d0;
 141                         p1 ^= d1;
 142
 143                         q0 = x2_64(q0);
 144                         q1 = x2_64(q1);
 145
 146                         q0 ^= d0;
 147                         q1 ^= d1;
 148                 }
 149                 v_64(p[i]) = p0;
 150                 v_64(p[i + 8]) = p1;
 151                 v_64(q[i]) = q0;
 152                 v_64(q[i + 8]) = q1;
 153         }
 154 }
 155
 156 /*
 157  * GEN3 (triple parity with Cauchy matrix) 8bit C implementation
 158  *
 159  * Note that instead of a generic multiplication table, likely resulting
 160  * in multiple cache misses, a precomputed table could be used.
 161  * But this is only a kind of reference function, and we are not really
 162  * interested in speed.
 163  */
 164 void raid_gen3_int8(int nd, size_t size, void **vv)
 165 {
 166         uint8_t **v = (uint8_t **)vv;
 167         uint8_t *p;
 168         uint8_t *q;
 169         uint8_t *r;
 170         int d, l;
 171         size_t i;
 172
 173         uint8_t d0, r0, q0, p0;
 174
 175         l = nd - 1;
 176         p = v[nd];
 177         q = v[nd + 1];
 178         r = v[nd + 2];
 179
 180         for (i = 0; i < size; i += 1) {
 181                 p0 = q0 = r0 = 0;
 182                 for (d = l; d > 0; --d) {
 183                         d0 = v_8(v[d][i]);
 184
 185                         p0 ^= d0;
 186                         q0 ^= gfmul[d0][gfgen[1][d]];
 187                         r0 ^= gfmul[d0][gfgen[2][d]];
 188                 }
 189
 190                 /* first disk with all coefficients at 1 */
 191                 d0 = v_8(v[0][i]);
 192
 193                 p0 ^= d0;
 194                 q0 ^= d0;
 195                 r0 ^= d0;
 196
 197                 v_8(p[i]) = p0;
 198                 v_8(q[i]) = q0;
 199                 v_8(r[i]) = r0;
 200         }
 201 }
 202
 203 /*
 204  * GEN4 (quad parity with Cauchy matrix) 8bit C implementation
 205  *
 206  * Note that instead of a generic multiplication table, likely resulting
 207  * in multiple cache misses, a precomputed table could be used.
 208  * But this is only a kind of reference function, and we are not really
 209  * interested in speed.
 210  */
 211 void raid_gen4_int8(int nd, size_t size, void **vv)
 212 {
 213         uint8_t **v = (uint8_t **)vv;
 214         uint8_t *p;
 215         uint8_t *q;
 216         uint8_t *r;
 217         uint8_t *s;
 218         int d, l;
 219         size_t i;
 220
 221         uint8_t d0, s0, r0, q0, p0;
 222
 223         l = nd - 1;
 224         p = v[nd];
 225         q = v[nd + 1];
 226         r = v[nd + 2];
 227         s = v[nd + 3];
 228
 229         for (i = 0; i < size; i += 1) {
 230                 p0 = q0 = r0 = s0 = 0;
 231                 for (d = l; d > 0; --d) {
 232                         d0 = v_8(v[d][i]);
 233
 234                         p0 ^= d0;
 235                         q0 ^= gfmul[d0][gfgen[1][d]];
 236                         r0 ^= gfmul[d0][gfgen[2][d]];
 237                         s0 ^= gfmul[d0][gfgen[3][d]];
 238                 }
 239
 240                 /* first disk with all coefficients at 1 */
 241                 d0 = v_8(v[0][i]);
 242
 243                 p0 ^= d0;
 244                 q0 ^= d0;
 245                 r0 ^= d0;
 246                 s0 ^= d0;
 247
 248                 v_8(p[i]) = p0;
 249                 v_8(q[i]) = q0;
 250                 v_8(r[i]) = r0;
 251                 v_8(s[i]) = s0;
 252         }
 253 }
 254
 255 /*
 256  * GEN5 (penta parity with Cauchy matrix) 8bit C implementation
 257  *
 258  * Note that instead of a generic multiplication table, likely resulting
 259  * in multiple cache misses, a precomputed table could be used.
 260  * But this is only a kind of reference function, and we are not really
 261  * interested in speed.
 262  */
 263 void raid_gen5_int8(int nd, size_t size, void **vv)
 264 {
 265         uint8_t **v = (uint8_t **)vv;
 266         uint8_t *p;
 267         uint8_t *q;
 268         uint8_t *r;
 269         uint8_t *s;
 270         uint8_t *t;
 271         int d, l;
 272         size_t i;
 273
 274         uint8_t d0, t0, s0, r0, q0, p0;
 275
 276         l = nd - 1;
 277         p = v[nd];
 278         q = v[nd + 1];
 279         r = v[nd + 2];
 280         s = v[nd + 3];
 281         t = v[nd + 4];
 282
 283         for (i = 0; i < size; i += 1) {
 284                 p0 = q0 = r0 = s0 = t0 = 0;
 285                 for (d = l; d > 0; --d) {
 286                         d0 = v_8(v[d][i]);
 287
 288                         p0 ^= d0;
 289                         q0 ^= gfmul[d0][gfgen[1][d]];
 290                         r0 ^= gfmul[d0][gfgen[2][d]];
 291                         s0 ^= gfmul[d0][gfgen[3][d]];
 292                         t0 ^= gfmul[d0][gfgen[4][d]];
 293                 }
 294
 295                 /* first disk with all coefficients at 1 */
 296                 d0 = v_8(v[0][i]);
 297
 298                 p0 ^= d0;
 299                 q0 ^= d0;
 300                 r0 ^= d0;
 301                 s0 ^= d0;
 302                 t0 ^= d0;
 303
 304                 v_8(p[i]) = p0;
 305                 v_8(q[i]) = q0;
 306                 v_8(r[i]) = r0;
 307                 v_8(s[i]) = s0;
 308                 v_8(t[i]) = t0;
 309         }
 310 }
 311
 312 /*
 313  * GEN6 (hexa parity with Cauchy matrix) 8bit C implementation
 314  *
 315  * Note that instead of a generic multiplication table, likely resulting
 316  * in multiple cache misses, a precomputed table could be used.
 317  * But this is only a kind of reference function, and we are not really
 318  * interested in speed.
 319  */
 320 void raid_gen6_int8(int nd, size_t size, void **vv)
 321 {
 322         uint8_t **v = (uint8_t **)vv;
 323         uint8_t *p;
 324         uint8_t *q;
 325         uint8_t *r;
 326         uint8_t *s;
 327         uint8_t *t;
 328         uint8_t *u;
 329         int d, l;
 330         size_t i;
 331
 332         uint8_t d0, u0, t0, s0, r0, q0, p0;
 333
 334         l = nd - 1;
 335         p = v[nd];
 336         q = v[nd + 1];
 337         r = v[nd + 2];
 338         s = v[nd + 3];
 339         t = v[nd + 4];
 340         u = v[nd + 5];
 341
 342         for (i = 0; i < size; i += 1) {
 343                 p0 = q0 = r0 = s0 = t0 = u0 = 0;
 344                 for (d = l; d > 0; --d) {
 345                         d0 = v_8(v[d][i]);
 346
 347                         p0 ^= d0;
 348                         q0 ^= gfmul[d0][gfgen[1][d]];
 349                         r0 ^= gfmul[d0][gfgen[2][d]];
 350                         s0 ^= gfmul[d0][gfgen[3][d]];
 351                         t0 ^= gfmul[d0][gfgen[4][d]];
 352                         u0 ^= gfmul[d0][gfgen[5][d]];
 353                 }
 354
 355                 /* first disk with all coefficients at 1 */
 356                 d0 = v_8(v[0][i]);
 357
 358                 p0 ^= d0;
 359                 q0 ^= d0;
 360                 r0 ^= d0;
 361                 s0 ^= d0;
 362                 t0 ^= d0;
 363                 u0 ^= d0;
 364
 365                 v_8(p[i]) = p0;
 366                 v_8(q[i]) = q0;
 367                 v_8(r[i]) = r0;
 368                 v_8(s[i]) = s0;
 369                 v_8(t[i]) = t0;
 370                 v_8(u[i]) = u0;
 371         }
 372 }
 373
 374 /*
 375  * Recover failure of one data block at index id[0] using parity at index
 376  * ip[0] for any RAID level.
 377  *
 378  * Starting from the equation:
 379  *
 380  * Pd = A[ip[0],id[0]] * Dx
 381  *
 382  * and solving we get:
 383  *
 384  * Dx = A[ip[0],id[0]]^-1 * Pd
 385  */
 386 void raid_rec1_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
 387 {
 388         uint8_t **v = (uint8_t **)vv;
 389         uint8_t *p;
 390         uint8_t *pa;
 391         const uint8_t *T;
 392         uint8_t G;
 393         uint8_t V;
 394         size_t i;
 395
 396         (void)nr; /* unused, it's always 1 */
 397
 398         /* if it's RAID5 uses the faster function */
 399         if (ip[0] == 0) {
 400                 raid_rec1of1(id, nd, size, vv);
 401                 return;
 402         }
 403
 404         /* setup the coefficients matrix */
 405         G = A(ip[0], id[0]);
 406
 407         /* invert it to solve the system of linear equations */
 408         V = inv(G);
 409
 410         /* get multiplication tables */
 411         T = table(V);
 412
 413         /* compute delta parity */
 414         raid_delta_gen(1, id, ip, nd, size, vv);
 415
 416         p = v[nd + ip[0]];
 417         pa = v[id[0]];
 418
 419         for (i = 0; i < size; ++i) {
 420                 /* delta */
 421                 uint8_t Pd = p[i] ^ pa[i];
 422
 423                 /* reconstruct */
 424                 pa[i] = T[Pd];
 425         }
 426 }
 427
 428 /*
 429  * Recover failure of two data blocks at indexes id[0],id[1] using parity at
 430  * indexes ip[0],ip[1] for any RAID level.
 431  *
 432  * Starting from the equations:
 433  *
 434  * Pd = A[ip[0],id[0]] * Dx + A[ip[0],id[1]] * Dy
 435  * Qd = A[ip[1],id[0]] * Dx + A[ip[1],id[1]] * Dy
 436  *
 437  * we solve inverting the coefficients matrix.
 438  */
 439 void raid_rec2_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
 440 {
 441         uint8_t **v = (uint8_t **)vv;
 442         uint8_t *p;
 443         uint8_t *pa;
 444         uint8_t *q;
 445         uint8_t *qa;
 446         const int N = 2;
 447         const uint8_t *T[N][N];
 448         uint8_t G[N * N];
 449         uint8_t V[N * N];
 450         size_t i;
 451         int j, k;
 452
 453         (void)nr; /* unused, it's always 2 */
 454
 455         /* if it's RAID6 recovering with P and Q uses the faster function */
 456         if (ip[0] == 0 && ip[1] == 1) {
 457                 raid_rec2of2_int8(id, ip, nd, size, vv);
 458                 return;
 459         }
 460
 461         /* setup the coefficients matrix */
 462         for (j = 0; j < N; ++j)
 463                 for (k = 0; k < N; ++k)
 464                         G[j * N + k] = A(ip[j], id[k]);
 465
 466         /* invert it to solve the system of linear equations */
 467         raid_invert(G, V, N);
 468
 469         /* get multiplication tables */
 470         for (j = 0; j < N; ++j)
 471                 for (k = 0; k < N; ++k)
 472                         T[j][k] = table(V[j * N + k]);
 473
 474         /* compute delta parity */
 475         raid_delta_gen(2, id, ip, nd, size, vv);
 476
 477         p = v[nd + ip[0]];
 478         q = v[nd + ip[1]];
 479         pa = v[id[0]];
 480         qa = v[id[1]];
 481
 482         for (i = 0; i < size; ++i) {
 483                 /* delta */
 484                 uint8_t Pd = p[i] ^ pa[i];
 485                 uint8_t Qd = q[i] ^ qa[i];
 486
 487                 /* reconstruct */
 488                 pa[i] = T[0][0][Pd] ^ T[0][1][Qd];
 489                 qa[i] = T[1][0][Pd] ^ T[1][1][Qd];
 490         }
 491 }
 492
 493 /*
 494  * Recover failure of N data blocks at indexes id[N] using parity at indexes
 495  * ip[N] for any RAID level.
 496  *
 497  * Starting from the N equations, with 0<=i<N :
 498  *
 499  * PD[i] = sum(A[ip[i],id[j]] * D[i]) 0<=j<N
 500  *
 501  * we solve inverting the coefficients matrix.
 502  *
 503  * Note that referring at previous equations you have:
 504  * PD[0] = Pd, PD[1] = Qd, PD[2] = Rd, ...
 505  * D[0] = Dx, D[1] = Dy, D[2] = Dz, ...
 506  */
 507 void raid_recX_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
 508 {
 509         uint8_t **v = (uint8_t **)vv;
 510         uint8_t *p[RAID_PARITY_MAX];
 511         uint8_t *pa[RAID_PARITY_MAX];
 512         const uint8_t *T[RAID_PARITY_MAX][RAID_PARITY_MAX];
 513         uint8_t G[RAID_PARITY_MAX * RAID_PARITY_MAX];
 514         uint8_t V[RAID_PARITY_MAX * RAID_PARITY_MAX];
 515         size_t i;
 516         int j, k;
 517
 518         /* setup the coefficients matrix */
 519         for (j = 0; j < nr; ++j)
 520                 for (k = 0; k < nr; ++k)
 521                         G[j * nr + k] = A(ip[j], id[k]);
 522
 523         /* invert it to solve the system of linear equations */
 524         raid_invert(G, V, nr);
 525
 526         /* get multiplication tables */
 527         for (j = 0; j < nr; ++j)
 528                 for (k = 0; k < nr; ++k)
 529                         T[j][k] = table(V[j * nr + k]);
 530
 531         /* compute delta parity */
 532         raid_delta_gen(nr, id, ip, nd, size, vv);
 533
 534         for (j = 0; j < nr; ++j) {
 535                 p[j] = v[nd + ip[j]];
 536                 pa[j] = v[id[j]];
 537         }
 538
 539         for (i = 0; i < size; ++i) {
 540                 uint8_t PD[RAID_PARITY_MAX];
 541
 542                 /* delta */
 543                 for (j = 0; j < nr; ++j)
 544                         PD[j] = p[j][i] ^ pa[j][i];
 545
 546                 /* reconstruct */
 547                 for (j = 0; j < nr; ++j) {
 548                         uint8_t b = 0;
 549
 550                         for (k = 0; k < nr; ++k)
 551                                 b ^= T[j][k][PD[k]];
 552                         pa[j][i] = b;
 553                 }
 554         }
 555 }
 556