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

   1 /*
   2  * Copyright (C) 2015 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 "combo.h"
  17 #include "gf.h"
  18
  19 /**
  20  * Validate the provided failed blocks.
  21  *
  22  * This function checks if the specified failed blocks satisfy the redundancy
  23  * information using the data from the known valid parity blocks.
  24  *
  25  * It's similar at raid_check(), just with a different format for arguments.
  26  *
  27  * The number of failed blocks @nr must be strictly less than the number of
  28  * parities @nv, because you need one more parity to validate the recovering.
  29  *
  30  * No data or parity blocks are modified.
  31  *
  32  * @nr Number of failed data blocks.
  33  * @id[] Vector of @nr indexes of the failed data blocks.
  34  *   The indexes start from 0. They must be in order.
  35  * @nv Number of valid parity blocks.
  36  * @ip[] Vector of @nv indexes of the valid parity blocks.
  37  *   The indexes start from 0. They must be in order.
  38  * @nd Number of data blocks.
  39  * @size Size of the blocks pointed by @v. It must be a multipler of 64.
  40  * @v Vector of pointers to the blocks of data and parity.
  41  *   It has (@nd + @ip[@nv - 1] + 1) elements. The starting elements are the
  42  *   blocks for data, following with the parity blocks.
  43  *   Each block has @size bytes.
  44  * @return 0 if the check is satisfied. -1 otherwise.
  45  */
  46 static int raid_validate(int nr, int *id, int nv, int *ip, int nd, size_t size, void **vv)
  47 {
  48         uint8_t **v = (uint8_t **)vv;
  49         const uint8_t *T[RAID_PARITY_MAX][RAID_PARITY_MAX];
  50         uint8_t G[RAID_PARITY_MAX * RAID_PARITY_MAX];
  51         uint8_t V[RAID_PARITY_MAX * RAID_PARITY_MAX];
  52         size_t i;
  53         int j, k, l;
  54
  55         BUG_ON(nr >= nv);
  56
  57         /* setup the coefficients matrix */
  58         for (j = 0; j < nr; ++j)
  59                 for (k = 0; k < nr; ++k)
  60                         G[j * nr + k] = A(ip[j], id[k]);
  61
  62         /* invert it to solve the system of linear equations */
  63         raid_invert(G, V, nr);
  64
  65         /* get multiplication tables */
  66         for (j = 0; j < nr; ++j)
  67                 for (k = 0; k < nr; ++k)
  68                         T[j][k] = table(V[j * nr + k]);
  69
  70         /* check all positions */
  71         for (i = 0; i < size; ++i) {
  72                 uint8_t p[RAID_PARITY_MAX];
  73
  74                 /* get parity */
  75                 for (j = 0; j < nv; ++j)
  76                         p[j] = v[nd + ip[j]][i];
  77
  78                 /* compute delta parity, skipping broken disks */
  79                 for (j = 0, k = 0; j < nd; ++j) {
  80                         uint8_t b;
  81
  82                         /* skip broken disks */
  83                         if (k < nr && id[k] == j) {
  84                                 ++k;
  85                                 continue;
  86                         }
  87
  88                         b = v[j][i];
  89                         for (l = 0; l < nv; ++l)
  90                                 p[l] ^= gfmul[b][gfgen[ip[l]][j]];
  91                 }
  92
  93                 /* reconstruct data */
  94                 for (j = 0; j < nr; ++j) {
  95                         uint8_t b = 0;
  96                         int idj = id[j];
  97
  98                         /* recompute the data */
  99                         for (k = 0; k < nr; ++k)
 100                                 b ^= T[j][k][p[k]];
 101
 102                         /* add the parity contribution of the reconstructed data */
 103                         for (l = nr; l < nv; ++l)
 104                                 p[l] ^= gfmul[b][gfgen[ip[l]][idj]];
 105                 }
 106
 107                 /* check that the final parity is 0 */
 108                 for (l = nr; l < nv; ++l)
 109                         if (p[l] != 0)
 110                                 return -1;
 111         }
 112
 113         return 0;
 114 }
 115
 116 int raid_check(int nr, int *ir, int nd, int np, size_t size, void **v)
 117 {
 118         /* valid parity index */
 119         int ip[RAID_PARITY_MAX];
 120         int vp;
 121         int rd;
 122         int i, j;
 123
 124         /* enforce limit on size */
 125         BUG_ON(size % 64 != 0);
 126
 127         /* enforce limit on number of failures */
 128         BUG_ON(nr >= np); /* >= because we check with extra parity */
 129         BUG_ON(np > RAID_PARITY_MAX);
 130
 131         /* enforce order in index vector */
 132         BUG_ON(nr >= 2 && ir[0] >= ir[1]);
 133         BUG_ON(nr >= 3 && ir[1] >= ir[2]);
 134         BUG_ON(nr >= 4 && ir[2] >= ir[3]);
 135         BUG_ON(nr >= 5 && ir[3] >= ir[4]);
 136         BUG_ON(nr >= 6 && ir[4] >= ir[5]);
 137
 138         /* enforce limit on index vector */
 139         BUG_ON(nr > 0 && ir[nr-1] >= nd + np);
 140
 141         /* count failed data disk */
 142         rd = 0;
 143         while (rd < nr && ir[rd] < nd)
 144                 ++rd;
 145
 146         /* put valid parities into ip[] */
 147         vp = 0;
 148         for (i = rd, j = 0; j < np; ++j) {
 149                 /* if parity is failed */
 150                 if (i < nr && ir[i] == nd + j) {
 151                         /* skip broken parity */
 152                         ++i;
 153                 } else {
 154                         /* store valid parity */
 155                         ip[vp] = j;
 156                         ++vp;
 157                 }
 158         }
 159
 160         return raid_validate(rd, ir, vp, ip, nd, size, v);
 161 }
 162
 163 int raid_scan(int *ir, int nd, int np, size_t size, void **v)
 164 {
 165         int r;
 166
 167         /* check the special case of no failure */
 168         if (np != 0 && raid_check(0, 0, nd, np, size, v) == 0)
 169                 return 0;
 170
 171         /* for each number of possible failures */
 172         for (r = 1; r < np; ++r) {
 173                 /* try all combinations of r failures on n disks */
 174                 combination_first(r, nd + np, ir);
 175                 do {
 176                         /* verify if the combination is a valid one */
 177                         if (raid_check(r, ir, nd, np, size, v) == 0)
 178                                 return r;
 179                 } while (combination_next(r, nd + np, ir));
 180         }
 181
 182         /* no solution found */
 183         return -1;
 184 }
 185