2 * Copyright (C) 2015 Andrea Mazzoleni
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.
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.
20 * Validate the provided failed blocks.
22 * This function checks if the specified failed blocks satisfy the redundancy
23 * information using the data from the known valid parity blocks.
25 * It's similar at raid_check(), just with a different format for arguments.
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.
30 * No data or parity blocks are modified.
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.
46 static int raid_validate(int nr, int *id, int nv, int *ip, int nd, size_t size, void **vv)
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];
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]);
62 /* invert it to solve the system of linear equations */
63 raid_invert(G, V, nr);
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]);
70 /* check all positions */
71 for (i = 0; i < size; ++i) {
72 uint8_t p[RAID_PARITY_MAX];
75 for (j = 0; j < nv; ++j)
76 p[j] = v[nd + ip[j]][i];
78 /* compute delta parity, skipping broken disks */
79 for (j = 0, k = 0; j < nd; ++j) {
82 /* skip broken disks */
83 if (k < nr && id[k] == j) {
89 for (l = 0; l < nv; ++l)
90 p[l] ^= gfmul[b][gfgen[ip[l]][j]];
93 /* reconstruct data */
94 for (j = 0; j < nr; ++j) {
98 /* recompute the data */
99 for (k = 0; k < nr; ++k)
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]];
107 /* check that the final parity is 0 */
108 for (l = nr; l < nv; ++l)
116 int raid_check(int nr, int *ir, int nd, int np, size_t size, void **v)
118 /* valid parity index */
119 int ip[RAID_PARITY_MAX];
124 /* enforce limit on size */
125 BUG_ON(size % 64 != 0);
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);
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]);
138 /* enforce limit on index vector */
139 BUG_ON(nr > 0 && ir[nr-1] >= nd + np);
141 /* count failed data disk */
143 while (rd < nr && ir[rd] < nd)
146 /* put valid parities into ip[] */
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 */
154 /* store valid parity */
160 return raid_validate(rd, ir, vp, ip, nd, size, v);
163 int raid_scan(int *ir, int nd, int np, size_t size, void **v)
167 /* check the special case of no failure */
168 if (np != 0 && raid_check(0, 0, nd, np, size, v) == 0)
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);
176 /* verify if the combination is a valid one */
177 if (raid_check(r, ir, nd, np, size, v) == 0)
179 } while (combination_next(r, nd + np, ir));
182 /* no solution found */