Line data Source code
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 11255 : static int raid_validate(int nr, int *id, int nv, int *ip, int nd, size_t size, void **vv)
47 : {
48 11255 : 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 11255 : BUG_ON(nr >= nv);
56 :
57 : /* setup the coefficients matrix */
58 41316 : for (j = 0; j < nr; ++j)
59 119934 : for (k = 0; k < nr; ++k)
60 179746 : G[j * nr + k] = A(ip[j], id[k]);
61 :
62 : /* invert it to solve the system of linear equations */
63 11255 : raid_invert(G, V, nr);
64 :
65 : /* get multiplication tables */
66 41316 : for (j = 0; j < nr; ++j)
67 119934 : for (k = 0; k < nr; ++k)
68 179746 : T[j][k] = table(V[j * nr + k]);
69 :
70 : /* check all positions */
71 35831 : for (i = 0; i < size; ++i) {
72 : uint8_t p[RAID_PARITY_MAX];
73 :
74 : /* get parity */
75 151819 : for (j = 0; j < nv; ++j)
76 115994 : p[j] = v[nd + ip[j]][i];
77 :
78 : /* compute delta parity, skipping broken disks */
79 609025 : for (j = 0, k = 0; j < nd; ++j) {
80 : uint8_t b;
81 :
82 : /* skip broken disks */
83 573200 : if (k < nr && id[k] == j) {
84 66916 : ++k;
85 66916 : continue;
86 : }
87 :
88 506284 : b = v[j][i];
89 2094442 : for (l = 0; l < nv; ++l)
90 1588158 : p[l] ^= gfmul[b][gfgen[ip[l]][j]];
91 : }
92 :
93 : /* reconstruct data */
94 102741 : for (j = 0; j < nr; ++j) {
95 66916 : uint8_t b = 0;
96 66916 : int idj = id[j];
97 :
98 : /* recompute the data */
99 234594 : for (k = 0; k < nr; ++k)
100 167678 : b ^= T[j][k][p[k]];
101 :
102 : /* add the parity contribution of the reconstructed data */
103 166984 : for (l = nr; l < nv; ++l)
104 100068 : p[l] ^= gfmul[b][gfgen[ip[l]][idj]];
105 : }
106 :
107 : /* check that the final parity is 0 */
108 60482 : for (l = nr; l < nv; ++l)
109 35906 : if (p[l] != 0)
110 11249 : return -1;
111 : }
112 :
113 6 : return 0;
114 : }
115 :
116 11255 : 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 11255 : BUG_ON(size % 64 != 0);
126 :
127 : /* enforce limit on number of failures */
128 11255 : BUG_ON(nr >= np); /* >= because we check with extra parity */
129 11255 : BUG_ON(np > RAID_PARITY_MAX);
130 :
131 : /* enforce order in index vector */
132 11255 : BUG_ON(nr >= 2 && ir[0] >= ir[1]);
133 11255 : BUG_ON(nr >= 3 && ir[1] >= ir[2]);
134 11255 : BUG_ON(nr >= 4 && ir[2] >= ir[3]);
135 11255 : BUG_ON(nr >= 5 && ir[3] >= ir[4]);
136 11255 : BUG_ON(nr >= 6 && ir[4] >= ir[5]);
137 :
138 : /* enforce limit on index vector */
139 11255 : BUG_ON(nr > 0 && ir[nr-1] >= nd + np);
140 :
141 : /* count failed data disk */
142 11255 : rd = 0;
143 52571 : while (rd < nr && ir[rd] < nd)
144 30061 : ++rd;
145 :
146 : /* put valid parities into ip[] */
147 11255 : vp = 0;
148 76488 : for (i = rd, j = 0; j < np; ++j) {
149 : /* if parity is failed */
150 65233 : if (i < nr && ir[i] == nd + j) {
151 : /* skip broken parity */
152 10664 : ++i;
153 : } else {
154 : /* store valid parity */
155 54569 : ip[vp] = j;
156 54569 : ++vp;
157 : }
158 : }
159 :
160 11255 : return raid_validate(rd, ir, vp, ip, nd, size, v);
161 : }
162 :
163 7 : 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 7 : if (np != 0 && raid_check(0, 0, nd, np, size, v) == 0)
169 1 : return 0;
170 :
171 : /* for each number of possible failures */
172 16 : for (r = 1; r < np; ++r) {
173 : /* try all combinations of r failures on n disks */
174 15 : combination_first(r, nd + np, ir);
175 : do {
176 : /* verify if the combination is a valid one */
177 11249 : if (raid_check(r, ir, nd, np, size, v) == 0)
178 5 : return r;
179 22488 : } while (combination_next(r, nd + np, ir));
180 : }
181 :
182 : /* no solution found */
183 1 : return -1;
184 : }
185 :
|
