]> CyberLeo.Net >> Repos - FreeBSD/stable/9.git/blob - sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_raidz.c
MFC r247187,247265,247348,247398,247540,247585,247852,248265,248267
[FreeBSD/stable/9.git] / sys / cddl / contrib / opensolaris / uts / common / fs / zfs / vdev_raidz.c
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21
22 /*
23  * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24  * Copyright (c) 2012 by Delphix. All rights reserved.
25  */
26
27 #include <sys/zfs_context.h>
28 #include <sys/spa.h>
29 #include <sys/vdev_impl.h>
30 #include <sys/zio.h>
31 #include <sys/zio_checksum.h>
32 #include <sys/fs/zfs.h>
33 #include <sys/fm/fs/zfs.h>
34
35 /*
36  * Virtual device vector for RAID-Z.
37  *
38  * This vdev supports single, double, and triple parity. For single parity,
39  * we use a simple XOR of all the data columns. For double or triple parity,
40  * we use a special case of Reed-Solomon coding. This extends the
41  * technique described in "The mathematics of RAID-6" by H. Peter Anvin by
42  * drawing on the system described in "A Tutorial on Reed-Solomon Coding for
43  * Fault-Tolerance in RAID-like Systems" by James S. Plank on which the
44  * former is also based. The latter is designed to provide higher performance
45  * for writes.
46  *
47  * Note that the Plank paper claimed to support arbitrary N+M, but was then
48  * amended six years later identifying a critical flaw that invalidates its
49  * claims. Nevertheless, the technique can be adapted to work for up to
50  * triple parity. For additional parity, the amendment "Note: Correction to
51  * the 1997 Tutorial on Reed-Solomon Coding" by James S. Plank and Ying Ding
52  * is viable, but the additional complexity means that write performance will
53  * suffer.
54  *
55  * All of the methods above operate on a Galois field, defined over the
56  * integers mod 2^N. In our case we choose N=8 for GF(8) so that all elements
57  * can be expressed with a single byte. Briefly, the operations on the
58  * field are defined as follows:
59  *
60  *   o addition (+) is represented by a bitwise XOR
61  *   o subtraction (-) is therefore identical to addition: A + B = A - B
62  *   o multiplication of A by 2 is defined by the following bitwise expression:
63  *      (A * 2)_7 = A_6
64  *      (A * 2)_6 = A_5
65  *      (A * 2)_5 = A_4
66  *      (A * 2)_4 = A_3 + A_7
67  *      (A * 2)_3 = A_2 + A_7
68  *      (A * 2)_2 = A_1 + A_7
69  *      (A * 2)_1 = A_0
70  *      (A * 2)_0 = A_7
71  *
72  * In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).
73  * As an aside, this multiplication is derived from the error correcting
74  * primitive polynomial x^8 + x^4 + x^3 + x^2 + 1.
75  *
76  * Observe that any number in the field (except for 0) can be expressed as a
77  * power of 2 -- a generator for the field. We store a table of the powers of
78  * 2 and logs base 2 for quick look ups, and exploit the fact that A * B can
79  * be rewritten as 2^(log_2(A) + log_2(B)) (where '+' is normal addition rather
80  * than field addition). The inverse of a field element A (A^-1) is therefore
81  * A ^ (255 - 1) = A^254.
82  *
83  * The up-to-three parity columns, P, Q, R over several data columns,
84  * D_0, ... D_n-1, can be expressed by field operations:
85  *
86  *      P = D_0 + D_1 + ... + D_n-2 + D_n-1
87  *      Q = 2^n-1 * D_0 + 2^n-2 * D_1 + ... + 2^1 * D_n-2 + 2^0 * D_n-1
88  *        = ((...((D_0) * 2 + D_1) * 2 + ...) * 2 + D_n-2) * 2 + D_n-1
89  *      R = 4^n-1 * D_0 + 4^n-2 * D_1 + ... + 4^1 * D_n-2 + 4^0 * D_n-1
90  *        = ((...((D_0) * 4 + D_1) * 4 + ...) * 4 + D_n-2) * 4 + D_n-1
91  *
92  * We chose 1, 2, and 4 as our generators because 1 corresponds to the trival
93  * XOR operation, and 2 and 4 can be computed quickly and generate linearly-
94  * independent coefficients. (There are no additional coefficients that have
95  * this property which is why the uncorrected Plank method breaks down.)
96  *
97  * See the reconstruction code below for how P, Q and R can used individually
98  * or in concert to recover missing data columns.
99  */
100
101 typedef struct raidz_col {
102         uint64_t rc_devidx;             /* child device index for I/O */
103         uint64_t rc_offset;             /* device offset */
104         uint64_t rc_size;               /* I/O size */
105         void *rc_data;                  /* I/O data */
106         void *rc_gdata;                 /* used to store the "good" version */
107         int rc_error;                   /* I/O error for this device */
108         uint8_t rc_tried;               /* Did we attempt this I/O column? */
109         uint8_t rc_skipped;             /* Did we skip this I/O column? */
110 } raidz_col_t;
111
112 typedef struct raidz_map {
113         uint64_t rm_cols;               /* Regular column count */
114         uint64_t rm_scols;              /* Count including skipped columns */
115         uint64_t rm_bigcols;            /* Number of oversized columns */
116         uint64_t rm_asize;              /* Actual total I/O size */
117         uint64_t rm_missingdata;        /* Count of missing data devices */
118         uint64_t rm_missingparity;      /* Count of missing parity devices */
119         uint64_t rm_firstdatacol;       /* First data column/parity count */
120         uint64_t rm_nskip;              /* Skipped sectors for padding */
121         uint64_t rm_skipstart;  /* Column index of padding start */
122         void *rm_datacopy;              /* rm_asize-buffer of copied data */
123         uintptr_t rm_reports;           /* # of referencing checksum reports */
124         uint8_t rm_freed;               /* map no longer has referencing ZIO */
125         uint8_t rm_ecksuminjected;      /* checksum error was injected */
126         raidz_col_t rm_col[1];          /* Flexible array of I/O columns */
127 } raidz_map_t;
128
129 #define VDEV_RAIDZ_P            0
130 #define VDEV_RAIDZ_Q            1
131 #define VDEV_RAIDZ_R            2
132
133 #define VDEV_RAIDZ_MUL_2(x)     (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
134 #define VDEV_RAIDZ_MUL_4(x)     (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
135
136 /*
137  * We provide a mechanism to perform the field multiplication operation on a
138  * 64-bit value all at once rather than a byte at a time. This works by
139  * creating a mask from the top bit in each byte and using that to
140  * conditionally apply the XOR of 0x1d.
141  */
142 #define VDEV_RAIDZ_64MUL_2(x, mask) \
143 { \
144         (mask) = (x) & 0x8080808080808080ULL; \
145         (mask) = ((mask) << 1) - ((mask) >> 7); \
146         (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
147             ((mask) & 0x1d1d1d1d1d1d1d1d); \
148 }
149
150 #define VDEV_RAIDZ_64MUL_4(x, mask) \
151 { \
152         VDEV_RAIDZ_64MUL_2((x), mask); \
153         VDEV_RAIDZ_64MUL_2((x), mask); \
154 }
155
156 /*
157  * Force reconstruction to use the general purpose method.
158  */
159 int vdev_raidz_default_to_general;
160
161 /*
162  * These two tables represent powers and logs of 2 in the Galois field defined
163  * above. These values were computed by repeatedly multiplying by 2 as above.
164  */
165 static const uint8_t vdev_raidz_pow2[256] = {
166         0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
167         0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
168         0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9,
169         0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
170         0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35,
171         0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
172         0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0,
173         0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
174         0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc,
175         0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
176         0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f,
177         0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
178         0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88,
179         0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
180         0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93,
181         0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
182         0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9,
183         0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
184         0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa,
185         0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
186         0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e,
187         0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
188         0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4,
189         0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
190         0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e,
191         0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
192         0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef,
193         0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
194         0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5,
195         0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
196         0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83,
197         0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01
198 };
199 static const uint8_t vdev_raidz_log2[256] = {
200         0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6,
201         0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
202         0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81,
203         0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
204         0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21,
205         0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
206         0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9,
207         0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
208         0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd,
209         0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
210         0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd,
211         0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
212         0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e,
213         0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
214         0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b,
215         0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
216         0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d,
217         0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
218         0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c,
219         0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
220         0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd,
221         0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
222         0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e,
223         0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
224         0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76,
225         0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
226         0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa,
227         0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
228         0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51,
229         0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
230         0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8,
231         0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
232 };
233
234 static void vdev_raidz_generate_parity(raidz_map_t *rm);
235
236 /*
237  * Multiply a given number by 2 raised to the given power.
238  */
239 static uint8_t
240 vdev_raidz_exp2(uint_t a, int exp)
241 {
242         if (a == 0)
243                 return (0);
244
245         ASSERT(exp >= 0);
246         ASSERT(vdev_raidz_log2[a] > 0 || a == 1);
247
248         exp += vdev_raidz_log2[a];
249         if (exp > 255)
250                 exp -= 255;
251
252         return (vdev_raidz_pow2[exp]);
253 }
254
255 static void
256 vdev_raidz_map_free(raidz_map_t *rm)
257 {
258         int c;
259         size_t size;
260
261         for (c = 0; c < rm->rm_firstdatacol; c++) {
262                 zio_buf_free(rm->rm_col[c].rc_data, rm->rm_col[c].rc_size);
263
264                 if (rm->rm_col[c].rc_gdata != NULL)
265                         zio_buf_free(rm->rm_col[c].rc_gdata,
266                             rm->rm_col[c].rc_size);
267         }
268
269         size = 0;
270         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++)
271                 size += rm->rm_col[c].rc_size;
272
273         if (rm->rm_datacopy != NULL)
274                 zio_buf_free(rm->rm_datacopy, size);
275
276         kmem_free(rm, offsetof(raidz_map_t, rm_col[rm->rm_scols]));
277 }
278
279 static void
280 vdev_raidz_map_free_vsd(zio_t *zio)
281 {
282         raidz_map_t *rm = zio->io_vsd;
283
284         ASSERT0(rm->rm_freed);
285         rm->rm_freed = 1;
286
287         if (rm->rm_reports == 0)
288                 vdev_raidz_map_free(rm);
289 }
290
291 /*ARGSUSED*/
292 static void
293 vdev_raidz_cksum_free(void *arg, size_t ignored)
294 {
295         raidz_map_t *rm = arg;
296
297         ASSERT3U(rm->rm_reports, >, 0);
298
299         if (--rm->rm_reports == 0 && rm->rm_freed != 0)
300                 vdev_raidz_map_free(rm);
301 }
302
303 static void
304 vdev_raidz_cksum_finish(zio_cksum_report_t *zcr, const void *good_data)
305 {
306         raidz_map_t *rm = zcr->zcr_cbdata;
307         size_t c = zcr->zcr_cbinfo;
308         size_t x;
309
310         const char *good = NULL;
311         const char *bad = rm->rm_col[c].rc_data;
312
313         if (good_data == NULL) {
314                 zfs_ereport_finish_checksum(zcr, NULL, NULL, B_FALSE);
315                 return;
316         }
317
318         if (c < rm->rm_firstdatacol) {
319                 /*
320                  * The first time through, calculate the parity blocks for
321                  * the good data (this relies on the fact that the good
322                  * data never changes for a given logical ZIO)
323                  */
324                 if (rm->rm_col[0].rc_gdata == NULL) {
325                         char *bad_parity[VDEV_RAIDZ_MAXPARITY];
326                         char *buf;
327
328                         /*
329                          * Set up the rm_col[]s to generate the parity for
330                          * good_data, first saving the parity bufs and
331                          * replacing them with buffers to hold the result.
332                          */
333                         for (x = 0; x < rm->rm_firstdatacol; x++) {
334                                 bad_parity[x] = rm->rm_col[x].rc_data;
335                                 rm->rm_col[x].rc_data = rm->rm_col[x].rc_gdata =
336                                     zio_buf_alloc(rm->rm_col[x].rc_size);
337                         }
338
339                         /* fill in the data columns from good_data */
340                         buf = (char *)good_data;
341                         for (; x < rm->rm_cols; x++) {
342                                 rm->rm_col[x].rc_data = buf;
343                                 buf += rm->rm_col[x].rc_size;
344                         }
345
346                         /*
347                          * Construct the parity from the good data.
348                          */
349                         vdev_raidz_generate_parity(rm);
350
351                         /* restore everything back to its original state */
352                         for (x = 0; x < rm->rm_firstdatacol; x++)
353                                 rm->rm_col[x].rc_data = bad_parity[x];
354
355                         buf = rm->rm_datacopy;
356                         for (x = rm->rm_firstdatacol; x < rm->rm_cols; x++) {
357                                 rm->rm_col[x].rc_data = buf;
358                                 buf += rm->rm_col[x].rc_size;
359                         }
360                 }
361
362                 ASSERT3P(rm->rm_col[c].rc_gdata, !=, NULL);
363                 good = rm->rm_col[c].rc_gdata;
364         } else {
365                 /* adjust good_data to point at the start of our column */
366                 good = good_data;
367
368                 for (x = rm->rm_firstdatacol; x < c; x++)
369                         good += rm->rm_col[x].rc_size;
370         }
371
372         /* we drop the ereport if it ends up that the data was good */
373         zfs_ereport_finish_checksum(zcr, good, bad, B_TRUE);
374 }
375
376 /*
377  * Invoked indirectly by zfs_ereport_start_checksum(), called
378  * below when our read operation fails completely.  The main point
379  * is to keep a copy of everything we read from disk, so that at
380  * vdev_raidz_cksum_finish() time we can compare it with the good data.
381  */
382 static void
383 vdev_raidz_cksum_report(zio_t *zio, zio_cksum_report_t *zcr, void *arg)
384 {
385         size_t c = (size_t)(uintptr_t)arg;
386         caddr_t buf;
387
388         raidz_map_t *rm = zio->io_vsd;
389         size_t size;
390
391         /* set up the report and bump the refcount  */
392         zcr->zcr_cbdata = rm;
393         zcr->zcr_cbinfo = c;
394         zcr->zcr_finish = vdev_raidz_cksum_finish;
395         zcr->zcr_free = vdev_raidz_cksum_free;
396
397         rm->rm_reports++;
398         ASSERT3U(rm->rm_reports, >, 0);
399
400         if (rm->rm_datacopy != NULL)
401                 return;
402
403         /*
404          * It's the first time we're called for this raidz_map_t, so we need
405          * to copy the data aside; there's no guarantee that our zio's buffer
406          * won't be re-used for something else.
407          *
408          * Our parity data is already in separate buffers, so there's no need
409          * to copy them.
410          */
411
412         size = 0;
413         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++)
414                 size += rm->rm_col[c].rc_size;
415
416         buf = rm->rm_datacopy = zio_buf_alloc(size);
417
418         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
419                 raidz_col_t *col = &rm->rm_col[c];
420
421                 bcopy(col->rc_data, buf, col->rc_size);
422                 col->rc_data = buf;
423
424                 buf += col->rc_size;
425         }
426         ASSERT3P(buf - (caddr_t)rm->rm_datacopy, ==, size);
427 }
428
429 static const zio_vsd_ops_t vdev_raidz_vsd_ops = {
430         vdev_raidz_map_free_vsd,
431         vdev_raidz_cksum_report
432 };
433
434 static raidz_map_t *
435 vdev_raidz_map_alloc(zio_t *zio, uint64_t unit_shift, uint64_t dcols,
436     uint64_t nparity)
437 {
438         raidz_map_t *rm;
439         uint64_t b = zio->io_offset >> unit_shift;
440         uint64_t s = zio->io_size >> unit_shift;
441         uint64_t f = b % dcols;
442         uint64_t o = (b / dcols) << unit_shift;
443         uint64_t q, r, c, bc, col, acols, scols, coff, devidx, asize, tot;
444
445         q = s / (dcols - nparity);
446         r = s - q * (dcols - nparity);
447         bc = (r == 0 ? 0 : r + nparity);
448         tot = s + nparity * (q + (r == 0 ? 0 : 1));
449
450         if (q == 0) {
451                 acols = bc;
452                 scols = MIN(dcols, roundup(bc, nparity + 1));
453         } else {
454                 acols = dcols;
455                 scols = dcols;
456         }
457
458         ASSERT3U(acols, <=, scols);
459
460         rm = kmem_alloc(offsetof(raidz_map_t, rm_col[scols]), KM_SLEEP);
461
462         rm->rm_cols = acols;
463         rm->rm_scols = scols;
464         rm->rm_bigcols = bc;
465         rm->rm_skipstart = bc;
466         rm->rm_missingdata = 0;
467         rm->rm_missingparity = 0;
468         rm->rm_firstdatacol = nparity;
469         rm->rm_datacopy = NULL;
470         rm->rm_reports = 0;
471         rm->rm_freed = 0;
472         rm->rm_ecksuminjected = 0;
473
474         asize = 0;
475
476         for (c = 0; c < scols; c++) {
477                 col = f + c;
478                 coff = o;
479                 if (col >= dcols) {
480                         col -= dcols;
481                         coff += 1ULL << unit_shift;
482                 }
483                 rm->rm_col[c].rc_devidx = col;
484                 rm->rm_col[c].rc_offset = coff;
485                 rm->rm_col[c].rc_data = NULL;
486                 rm->rm_col[c].rc_gdata = NULL;
487                 rm->rm_col[c].rc_error = 0;
488                 rm->rm_col[c].rc_tried = 0;
489                 rm->rm_col[c].rc_skipped = 0;
490
491                 if (c >= acols)
492                         rm->rm_col[c].rc_size = 0;
493                 else if (c < bc)
494                         rm->rm_col[c].rc_size = (q + 1) << unit_shift;
495                 else
496                         rm->rm_col[c].rc_size = q << unit_shift;
497
498                 asize += rm->rm_col[c].rc_size;
499         }
500
501         ASSERT3U(asize, ==, tot << unit_shift);
502         rm->rm_asize = roundup(asize, (nparity + 1) << unit_shift);
503         rm->rm_nskip = roundup(tot, nparity + 1) - tot;
504         ASSERT3U(rm->rm_asize - asize, ==, rm->rm_nskip << unit_shift);
505         ASSERT3U(rm->rm_nskip, <=, nparity);
506
507         for (c = 0; c < rm->rm_firstdatacol; c++)
508                 rm->rm_col[c].rc_data = zio_buf_alloc(rm->rm_col[c].rc_size);
509
510         rm->rm_col[c].rc_data = zio->io_data;
511
512         for (c = c + 1; c < acols; c++)
513                 rm->rm_col[c].rc_data = (char *)rm->rm_col[c - 1].rc_data +
514                     rm->rm_col[c - 1].rc_size;
515
516         /*
517          * If all data stored spans all columns, there's a danger that parity
518          * will always be on the same device and, since parity isn't read
519          * during normal operation, that that device's I/O bandwidth won't be
520          * used effectively. We therefore switch the parity every 1MB.
521          *
522          * ... at least that was, ostensibly, the theory. As a practical
523          * matter unless we juggle the parity between all devices evenly, we
524          * won't see any benefit. Further, occasional writes that aren't a
525          * multiple of the LCM of the number of children and the minimum
526          * stripe width are sufficient to avoid pessimal behavior.
527          * Unfortunately, this decision created an implicit on-disk format
528          * requirement that we need to support for all eternity, but only
529          * for single-parity RAID-Z.
530          *
531          * If we intend to skip a sector in the zeroth column for padding
532          * we must make sure to note this swap. We will never intend to
533          * skip the first column since at least one data and one parity
534          * column must appear in each row.
535          */
536         ASSERT(rm->rm_cols >= 2);
537         ASSERT(rm->rm_col[0].rc_size == rm->rm_col[1].rc_size);
538
539         if (rm->rm_firstdatacol == 1 && (zio->io_offset & (1ULL << 20))) {
540                 devidx = rm->rm_col[0].rc_devidx;
541                 o = rm->rm_col[0].rc_offset;
542                 rm->rm_col[0].rc_devidx = rm->rm_col[1].rc_devidx;
543                 rm->rm_col[0].rc_offset = rm->rm_col[1].rc_offset;
544                 rm->rm_col[1].rc_devidx = devidx;
545                 rm->rm_col[1].rc_offset = o;
546
547                 if (rm->rm_skipstart == 0)
548                         rm->rm_skipstart = 1;
549         }
550
551         zio->io_vsd = rm;
552         zio->io_vsd_ops = &vdev_raidz_vsd_ops;
553         return (rm);
554 }
555
556 static void
557 vdev_raidz_generate_parity_p(raidz_map_t *rm)
558 {
559         uint64_t *p, *src, pcount, ccount, i;
560         int c;
561
562         pcount = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
563
564         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
565                 src = rm->rm_col[c].rc_data;
566                 p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
567                 ccount = rm->rm_col[c].rc_size / sizeof (src[0]);
568
569                 if (c == rm->rm_firstdatacol) {
570                         ASSERT(ccount == pcount);
571                         for (i = 0; i < ccount; i++, src++, p++) {
572                                 *p = *src;
573                         }
574                 } else {
575                         ASSERT(ccount <= pcount);
576                         for (i = 0; i < ccount; i++, src++, p++) {
577                                 *p ^= *src;
578                         }
579                 }
580         }
581 }
582
583 static void
584 vdev_raidz_generate_parity_pq(raidz_map_t *rm)
585 {
586         uint64_t *p, *q, *src, pcnt, ccnt, mask, i;
587         int c;
588
589         pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
590         ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
591             rm->rm_col[VDEV_RAIDZ_Q].rc_size);
592
593         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
594                 src = rm->rm_col[c].rc_data;
595                 p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
596                 q = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
597
598                 ccnt = rm->rm_col[c].rc_size / sizeof (src[0]);
599
600                 if (c == rm->rm_firstdatacol) {
601                         ASSERT(ccnt == pcnt || ccnt == 0);
602                         for (i = 0; i < ccnt; i++, src++, p++, q++) {
603                                 *p = *src;
604                                 *q = *src;
605                         }
606                         for (; i < pcnt; i++, src++, p++, q++) {
607                                 *p = 0;
608                                 *q = 0;
609                         }
610                 } else {
611                         ASSERT(ccnt <= pcnt);
612
613                         /*
614                          * Apply the algorithm described above by multiplying
615                          * the previous result and adding in the new value.
616                          */
617                         for (i = 0; i < ccnt; i++, src++, p++, q++) {
618                                 *p ^= *src;
619
620                                 VDEV_RAIDZ_64MUL_2(*q, mask);
621                                 *q ^= *src;
622                         }
623
624                         /*
625                          * Treat short columns as though they are full of 0s.
626                          * Note that there's therefore nothing needed for P.
627                          */
628                         for (; i < pcnt; i++, q++) {
629                                 VDEV_RAIDZ_64MUL_2(*q, mask);
630                         }
631                 }
632         }
633 }
634
635 static void
636 vdev_raidz_generate_parity_pqr(raidz_map_t *rm)
637 {
638         uint64_t *p, *q, *r, *src, pcnt, ccnt, mask, i;
639         int c;
640
641         pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
642         ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
643             rm->rm_col[VDEV_RAIDZ_Q].rc_size);
644         ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
645             rm->rm_col[VDEV_RAIDZ_R].rc_size);
646
647         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
648                 src = rm->rm_col[c].rc_data;
649                 p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
650                 q = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
651                 r = rm->rm_col[VDEV_RAIDZ_R].rc_data;
652
653                 ccnt = rm->rm_col[c].rc_size / sizeof (src[0]);
654
655                 if (c == rm->rm_firstdatacol) {
656                         ASSERT(ccnt == pcnt || ccnt == 0);
657                         for (i = 0; i < ccnt; i++, src++, p++, q++, r++) {
658                                 *p = *src;
659                                 *q = *src;
660                                 *r = *src;
661                         }
662                         for (; i < pcnt; i++, src++, p++, q++, r++) {
663                                 *p = 0;
664                                 *q = 0;
665                                 *r = 0;
666                         }
667                 } else {
668                         ASSERT(ccnt <= pcnt);
669
670                         /*
671                          * Apply the algorithm described above by multiplying
672                          * the previous result and adding in the new value.
673                          */
674                         for (i = 0; i < ccnt; i++, src++, p++, q++, r++) {
675                                 *p ^= *src;
676
677                                 VDEV_RAIDZ_64MUL_2(*q, mask);
678                                 *q ^= *src;
679
680                                 VDEV_RAIDZ_64MUL_4(*r, mask);
681                                 *r ^= *src;
682                         }
683
684                         /*
685                          * Treat short columns as though they are full of 0s.
686                          * Note that there's therefore nothing needed for P.
687                          */
688                         for (; i < pcnt; i++, q++, r++) {
689                                 VDEV_RAIDZ_64MUL_2(*q, mask);
690                                 VDEV_RAIDZ_64MUL_4(*r, mask);
691                         }
692                 }
693         }
694 }
695
696 /*
697  * Generate RAID parity in the first virtual columns according to the number of
698  * parity columns available.
699  */
700 static void
701 vdev_raidz_generate_parity(raidz_map_t *rm)
702 {
703         switch (rm->rm_firstdatacol) {
704         case 1:
705                 vdev_raidz_generate_parity_p(rm);
706                 break;
707         case 2:
708                 vdev_raidz_generate_parity_pq(rm);
709                 break;
710         case 3:
711                 vdev_raidz_generate_parity_pqr(rm);
712                 break;
713         default:
714                 cmn_err(CE_PANIC, "invalid RAID-Z configuration");
715         }
716 }
717
718 static int
719 vdev_raidz_reconstruct_p(raidz_map_t *rm, int *tgts, int ntgts)
720 {
721         uint64_t *dst, *src, xcount, ccount, count, i;
722         int x = tgts[0];
723         int c;
724
725         ASSERT(ntgts == 1);
726         ASSERT(x >= rm->rm_firstdatacol);
727         ASSERT(x < rm->rm_cols);
728
729         xcount = rm->rm_col[x].rc_size / sizeof (src[0]);
730         ASSERT(xcount <= rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]));
731         ASSERT(xcount > 0);
732
733         src = rm->rm_col[VDEV_RAIDZ_P].rc_data;
734         dst = rm->rm_col[x].rc_data;
735         for (i = 0; i < xcount; i++, dst++, src++) {
736                 *dst = *src;
737         }
738
739         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
740                 src = rm->rm_col[c].rc_data;
741                 dst = rm->rm_col[x].rc_data;
742
743                 if (c == x)
744                         continue;
745
746                 ccount = rm->rm_col[c].rc_size / sizeof (src[0]);
747                 count = MIN(ccount, xcount);
748
749                 for (i = 0; i < count; i++, dst++, src++) {
750                         *dst ^= *src;
751                 }
752         }
753
754         return (1 << VDEV_RAIDZ_P);
755 }
756
757 static int
758 vdev_raidz_reconstruct_q(raidz_map_t *rm, int *tgts, int ntgts)
759 {
760         uint64_t *dst, *src, xcount, ccount, count, mask, i;
761         uint8_t *b;
762         int x = tgts[0];
763         int c, j, exp;
764
765         ASSERT(ntgts == 1);
766
767         xcount = rm->rm_col[x].rc_size / sizeof (src[0]);
768         ASSERT(xcount <= rm->rm_col[VDEV_RAIDZ_Q].rc_size / sizeof (src[0]));
769
770         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
771                 src = rm->rm_col[c].rc_data;
772                 dst = rm->rm_col[x].rc_data;
773
774                 if (c == x)
775                         ccount = 0;
776                 else
777                         ccount = rm->rm_col[c].rc_size / sizeof (src[0]);
778
779                 count = MIN(ccount, xcount);
780
781                 if (c == rm->rm_firstdatacol) {
782                         for (i = 0; i < count; i++, dst++, src++) {
783                                 *dst = *src;
784                         }
785                         for (; i < xcount; i++, dst++) {
786                                 *dst = 0;
787                         }
788
789                 } else {
790                         for (i = 0; i < count; i++, dst++, src++) {
791                                 VDEV_RAIDZ_64MUL_2(*dst, mask);
792                                 *dst ^= *src;
793                         }
794
795                         for (; i < xcount; i++, dst++) {
796                                 VDEV_RAIDZ_64MUL_2(*dst, mask);
797                         }
798                 }
799         }
800
801         src = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
802         dst = rm->rm_col[x].rc_data;
803         exp = 255 - (rm->rm_cols - 1 - x);
804
805         for (i = 0; i < xcount; i++, dst++, src++) {
806                 *dst ^= *src;
807                 for (j = 0, b = (uint8_t *)dst; j < 8; j++, b++) {
808                         *b = vdev_raidz_exp2(*b, exp);
809                 }
810         }
811
812         return (1 << VDEV_RAIDZ_Q);
813 }
814
815 static int
816 vdev_raidz_reconstruct_pq(raidz_map_t *rm, int *tgts, int ntgts)
817 {
818         uint8_t *p, *q, *pxy, *qxy, *xd, *yd, tmp, a, b, aexp, bexp;
819         void *pdata, *qdata;
820         uint64_t xsize, ysize, i;
821         int x = tgts[0];
822         int y = tgts[1];
823
824         ASSERT(ntgts == 2);
825         ASSERT(x < y);
826         ASSERT(x >= rm->rm_firstdatacol);
827         ASSERT(y < rm->rm_cols);
828
829         ASSERT(rm->rm_col[x].rc_size >= rm->rm_col[y].rc_size);
830
831         /*
832          * Move the parity data aside -- we're going to compute parity as
833          * though columns x and y were full of zeros -- Pxy and Qxy. We want to
834          * reuse the parity generation mechanism without trashing the actual
835          * parity so we make those columns appear to be full of zeros by
836          * setting their lengths to zero.
837          */
838         pdata = rm->rm_col[VDEV_RAIDZ_P].rc_data;
839         qdata = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
840         xsize = rm->rm_col[x].rc_size;
841         ysize = rm->rm_col[y].rc_size;
842
843         rm->rm_col[VDEV_RAIDZ_P].rc_data =
844             zio_buf_alloc(rm->rm_col[VDEV_RAIDZ_P].rc_size);
845         rm->rm_col[VDEV_RAIDZ_Q].rc_data =
846             zio_buf_alloc(rm->rm_col[VDEV_RAIDZ_Q].rc_size);
847         rm->rm_col[x].rc_size = 0;
848         rm->rm_col[y].rc_size = 0;
849
850         vdev_raidz_generate_parity_pq(rm);
851
852         rm->rm_col[x].rc_size = xsize;
853         rm->rm_col[y].rc_size = ysize;
854
855         p = pdata;
856         q = qdata;
857         pxy = rm->rm_col[VDEV_RAIDZ_P].rc_data;
858         qxy = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
859         xd = rm->rm_col[x].rc_data;
860         yd = rm->rm_col[y].rc_data;
861
862         /*
863          * We now have:
864          *      Pxy = P + D_x + D_y
865          *      Qxy = Q + 2^(ndevs - 1 - x) * D_x + 2^(ndevs - 1 - y) * D_y
866          *
867          * We can then solve for D_x:
868          *      D_x = A * (P + Pxy) + B * (Q + Qxy)
869          * where
870          *      A = 2^(x - y) * (2^(x - y) + 1)^-1
871          *      B = 2^(ndevs - 1 - x) * (2^(x - y) + 1)^-1
872          *
873          * With D_x in hand, we can easily solve for D_y:
874          *      D_y = P + Pxy + D_x
875          */
876
877         a = vdev_raidz_pow2[255 + x - y];
878         b = vdev_raidz_pow2[255 - (rm->rm_cols - 1 - x)];
879         tmp = 255 - vdev_raidz_log2[a ^ 1];
880
881         aexp = vdev_raidz_log2[vdev_raidz_exp2(a, tmp)];
882         bexp = vdev_raidz_log2[vdev_raidz_exp2(b, tmp)];
883
884         for (i = 0; i < xsize; i++, p++, q++, pxy++, qxy++, xd++, yd++) {
885                 *xd = vdev_raidz_exp2(*p ^ *pxy, aexp) ^
886                     vdev_raidz_exp2(*q ^ *qxy, bexp);
887
888                 if (i < ysize)
889                         *yd = *p ^ *pxy ^ *xd;
890         }
891
892         zio_buf_free(rm->rm_col[VDEV_RAIDZ_P].rc_data,
893             rm->rm_col[VDEV_RAIDZ_P].rc_size);
894         zio_buf_free(rm->rm_col[VDEV_RAIDZ_Q].rc_data,
895             rm->rm_col[VDEV_RAIDZ_Q].rc_size);
896
897         /*
898          * Restore the saved parity data.
899          */
900         rm->rm_col[VDEV_RAIDZ_P].rc_data = pdata;
901         rm->rm_col[VDEV_RAIDZ_Q].rc_data = qdata;
902
903         return ((1 << VDEV_RAIDZ_P) | (1 << VDEV_RAIDZ_Q));
904 }
905
906 /* BEGIN CSTYLED */
907 /*
908  * In the general case of reconstruction, we must solve the system of linear
909  * equations defined by the coeffecients used to generate parity as well as
910  * the contents of the data and parity disks. This can be expressed with
911  * vectors for the original data (D) and the actual data (d) and parity (p)
912  * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
913  *
914  *            __   __                     __     __
915  *            |     |         __     __   |  p_0  |
916  *            |  V  |         |  D_0  |   | p_m-1 |
917  *            |     |    x    |   :   | = |  d_0  |
918  *            |  I  |         | D_n-1 |   |   :   |
919  *            |     |         ~~     ~~   | d_n-1 |
920  *            ~~   ~~                     ~~     ~~
921  *
922  * I is simply a square identity matrix of size n, and V is a vandermonde
923  * matrix defined by the coeffecients we chose for the various parity columns
924  * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
925  * computation as well as linear separability.
926  *
927  *      __               __               __     __
928  *      |   1   ..  1 1 1 |               |  p_0  |
929  *      | 2^n-1 ..  4 2 1 |   __     __   |   :   |
930  *      | 4^n-1 .. 16 4 1 |   |  D_0  |   | p_m-1 |
931  *      |   1   ..  0 0 0 |   |  D_1  |   |  d_0  |
932  *      |   0   ..  0 0 0 | x |  D_2  | = |  d_1  |
933  *      |   :       : : : |   |   :   |   |  d_2  |
934  *      |   0   ..  1 0 0 |   | D_n-1 |   |   :   |
935  *      |   0   ..  0 1 0 |   ~~     ~~   |   :   |
936  *      |   0   ..  0 0 1 |               | d_n-1 |
937  *      ~~               ~~               ~~     ~~
938  *
939  * Note that I, V, d, and p are known. To compute D, we must invert the
940  * matrix and use the known data and parity values to reconstruct the unknown
941  * data values. We begin by removing the rows in V|I and d|p that correspond
942  * to failed or missing columns; we then make V|I square (n x n) and d|p
943  * sized n by removing rows corresponding to unused parity from the bottom up
944  * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
945  * using Gauss-Jordan elimination. In the example below we use m=3 parity
946  * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
947  *           __                               __
948  *           |  1   1   1   1   1   1   1   1  |
949  *           | 128  64  32  16  8   4   2   1  | <-----+-+-- missing disks
950  *           |  19 205 116  29  64  16  4   1  |      / /
951  *           |  1   0   0   0   0   0   0   0  |     / /
952  *           |  0   1   0   0   0   0   0   0  | <--' /
953  *  (V|I)  = |  0   0   1   0   0   0   0   0  | <---'
954  *           |  0   0   0   1   0   0   0   0  |
955  *           |  0   0   0   0   1   0   0   0  |
956  *           |  0   0   0   0   0   1   0   0  |
957  *           |  0   0   0   0   0   0   1   0  |
958  *           |  0   0   0   0   0   0   0   1  |
959  *           ~~                               ~~
960  *           __                               __
961  *           |  1   1   1   1   1   1   1   1  |
962  *           | 128  64  32  16  8   4   2   1  |
963  *           |  19 205 116  29  64  16  4   1  |
964  *           |  1   0   0   0   0   0   0   0  |
965  *           |  0   1   0   0   0   0   0   0  |
966  *  (V|I)' = |  0   0   1   0   0   0   0   0  |
967  *           |  0   0   0   1   0   0   0   0  |
968  *           |  0   0   0   0   1   0   0   0  |
969  *           |  0   0   0   0   0   1   0   0  |
970  *           |  0   0   0   0   0   0   1   0  |
971  *           |  0   0   0   0   0   0   0   1  |
972  *           ~~                               ~~
973  *
974  * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
975  * have carefully chosen the seed values 1, 2, and 4 to ensure that this
976  * matrix is not singular.
977  * __                                                                 __
978  * |  1   1   1   1   1   1   1   1     1   0   0   0   0   0   0   0  |
979  * |  19 205 116  29  64  16  4   1     0   1   0   0   0   0   0   0  |
980  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
981  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
982  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
983  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
984  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
985  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
986  * ~~                                                                 ~~
987  * __                                                                 __
988  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
989  * |  1   1   1   1   1   1   1   1     1   0   0   0   0   0   0   0  |
990  * |  19 205 116  29  64  16  4   1     0   1   0   0   0   0   0   0  |
991  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
992  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
993  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
994  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
995  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
996  * ~~                                                                 ~~
997  * __                                                                 __
998  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
999  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
1000  * |  0  205 116  0   0   0   0   0     0   1   19  29  64  16  4   1  |
1001  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
1002  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
1003  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
1004  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
1005  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
1006  * ~~                                                                 ~~
1007  * __                                                                 __
1008  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
1009  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
1010  * |  0   0  185  0   0   0   0   0    205  1  222 208 141 221 201 204 |
1011  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
1012  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
1013  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
1014  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
1015  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
1016  * ~~                                                                 ~~
1017  * __                                                                 __
1018  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
1019  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
1020  * |  0   0   1   0   0   0   0   0    166 100  4   40 158 168 216 209 |
1021  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
1022  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
1023  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
1024  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
1025  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
1026  * ~~                                                                 ~~
1027  * __                                                                 __
1028  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
1029  * |  0   1   0   0   0   0   0   0    167 100  5   41 159 169 217 208 |
1030  * |  0   0   1   0   0   0   0   0    166 100  4   40 158 168 216 209 |
1031  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
1032  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
1033  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
1034  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
1035  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
1036  * ~~                                                                 ~~
1037  *                   __                               __
1038  *                   |  0   0   1   0   0   0   0   0  |
1039  *                   | 167 100  5   41 159 169 217 208 |
1040  *                   | 166 100  4   40 158 168 216 209 |
1041  *       (V|I)'^-1 = |  0   0   0   1   0   0   0   0  |
1042  *                   |  0   0   0   0   1   0   0   0  |
1043  *                   |  0   0   0   0   0   1   0   0  |
1044  *                   |  0   0   0   0   0   0   1   0  |
1045  *                   |  0   0   0   0   0   0   0   1  |
1046  *                   ~~                               ~~
1047  *
1048  * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values
1049  * of the missing data.
1050  *
1051  * As is apparent from the example above, the only non-trivial rows in the
1052  * inverse matrix correspond to the data disks that we're trying to
1053  * reconstruct. Indeed, those are the only rows we need as the others would
1054  * only be useful for reconstructing data known or assumed to be valid. For
1055  * that reason, we only build the coefficients in the rows that correspond to
1056  * targeted columns.
1057  */
1058 /* END CSTYLED */
1059
1060 static void
1061 vdev_raidz_matrix_init(raidz_map_t *rm, int n, int nmap, int *map,
1062     uint8_t **rows)
1063 {
1064         int i, j;
1065         int pow;
1066
1067         ASSERT(n == rm->rm_cols - rm->rm_firstdatacol);
1068
1069         /*
1070          * Fill in the missing rows of interest.
1071          */
1072         for (i = 0; i < nmap; i++) {
1073                 ASSERT3S(0, <=, map[i]);
1074                 ASSERT3S(map[i], <=, 2);
1075
1076                 pow = map[i] * n;
1077                 if (pow > 255)
1078                         pow -= 255;
1079                 ASSERT(pow <= 255);
1080
1081                 for (j = 0; j < n; j++) {
1082                         pow -= map[i];
1083                         if (pow < 0)
1084                                 pow += 255;
1085                         rows[i][j] = vdev_raidz_pow2[pow];
1086                 }
1087         }
1088 }
1089
1090 static void
1091 vdev_raidz_matrix_invert(raidz_map_t *rm, int n, int nmissing, int *missing,
1092     uint8_t **rows, uint8_t **invrows, const uint8_t *used)
1093 {
1094         int i, j, ii, jj;
1095         uint8_t log;
1096
1097         /*
1098          * Assert that the first nmissing entries from the array of used
1099          * columns correspond to parity columns and that subsequent entries
1100          * correspond to data columns.
1101          */
1102         for (i = 0; i < nmissing; i++) {
1103                 ASSERT3S(used[i], <, rm->rm_firstdatacol);
1104         }
1105         for (; i < n; i++) {
1106                 ASSERT3S(used[i], >=, rm->rm_firstdatacol);
1107         }
1108
1109         /*
1110          * First initialize the storage where we'll compute the inverse rows.
1111          */
1112         for (i = 0; i < nmissing; i++) {
1113                 for (j = 0; j < n; j++) {
1114                         invrows[i][j] = (i == j) ? 1 : 0;
1115                 }
1116         }
1117
1118         /*
1119          * Subtract all trivial rows from the rows of consequence.
1120          */
1121         for (i = 0; i < nmissing; i++) {
1122                 for (j = nmissing; j < n; j++) {
1123                         ASSERT3U(used[j], >=, rm->rm_firstdatacol);
1124                         jj = used[j] - rm->rm_firstdatacol;
1125                         ASSERT3S(jj, <, n);
1126                         invrows[i][j] = rows[i][jj];
1127                         rows[i][jj] = 0;
1128                 }
1129         }
1130
1131         /*
1132          * For each of the rows of interest, we must normalize it and subtract
1133          * a multiple of it from the other rows.
1134          */
1135         for (i = 0; i < nmissing; i++) {
1136                 for (j = 0; j < missing[i]; j++) {
1137                         ASSERT0(rows[i][j]);
1138                 }
1139                 ASSERT3U(rows[i][missing[i]], !=, 0);
1140
1141                 /*
1142                  * Compute the inverse of the first element and multiply each
1143                  * element in the row by that value.
1144                  */
1145                 log = 255 - vdev_raidz_log2[rows[i][missing[i]]];
1146
1147                 for (j = 0; j < n; j++) {
1148                         rows[i][j] = vdev_raidz_exp2(rows[i][j], log);
1149                         invrows[i][j] = vdev_raidz_exp2(invrows[i][j], log);
1150                 }
1151
1152                 for (ii = 0; ii < nmissing; ii++) {
1153                         if (i == ii)
1154                                 continue;
1155
1156                         ASSERT3U(rows[ii][missing[i]], !=, 0);
1157
1158                         log = vdev_raidz_log2[rows[ii][missing[i]]];
1159
1160                         for (j = 0; j < n; j++) {
1161                                 rows[ii][j] ^=
1162                                     vdev_raidz_exp2(rows[i][j], log);
1163                                 invrows[ii][j] ^=
1164                                     vdev_raidz_exp2(invrows[i][j], log);
1165                         }
1166                 }
1167         }
1168
1169         /*
1170          * Verify that the data that is left in the rows are properly part of
1171          * an identity matrix.
1172          */
1173         for (i = 0; i < nmissing; i++) {
1174                 for (j = 0; j < n; j++) {
1175                         if (j == missing[i]) {
1176                                 ASSERT3U(rows[i][j], ==, 1);
1177                         } else {
1178                                 ASSERT0(rows[i][j]);
1179                         }
1180                 }
1181         }
1182 }
1183
1184 static void
1185 vdev_raidz_matrix_reconstruct(raidz_map_t *rm, int n, int nmissing,
1186     int *missing, uint8_t **invrows, const uint8_t *used)
1187 {
1188         int i, j, x, cc, c;
1189         uint8_t *src;
1190         uint64_t ccount;
1191         uint8_t *dst[VDEV_RAIDZ_MAXPARITY];
1192         uint64_t dcount[VDEV_RAIDZ_MAXPARITY];
1193         uint8_t log = 0;
1194         uint8_t val;
1195         int ll;
1196         uint8_t *invlog[VDEV_RAIDZ_MAXPARITY];
1197         uint8_t *p, *pp;
1198         size_t psize;
1199
1200         psize = sizeof (invlog[0][0]) * n * nmissing;
1201         p = kmem_alloc(psize, KM_SLEEP);
1202
1203         for (pp = p, i = 0; i < nmissing; i++) {
1204                 invlog[i] = pp;
1205                 pp += n;
1206         }
1207
1208         for (i = 0; i < nmissing; i++) {
1209                 for (j = 0; j < n; j++) {
1210                         ASSERT3U(invrows[i][j], !=, 0);
1211                         invlog[i][j] = vdev_raidz_log2[invrows[i][j]];
1212                 }
1213         }
1214
1215         for (i = 0; i < n; i++) {
1216                 c = used[i];
1217                 ASSERT3U(c, <, rm->rm_cols);
1218
1219                 src = rm->rm_col[c].rc_data;
1220                 ccount = rm->rm_col[c].rc_size;
1221                 for (j = 0; j < nmissing; j++) {
1222                         cc = missing[j] + rm->rm_firstdatacol;
1223                         ASSERT3U(cc, >=, rm->rm_firstdatacol);
1224                         ASSERT3U(cc, <, rm->rm_cols);
1225                         ASSERT3U(cc, !=, c);
1226
1227                         dst[j] = rm->rm_col[cc].rc_data;
1228                         dcount[j] = rm->rm_col[cc].rc_size;
1229                 }
1230
1231                 ASSERT(ccount >= rm->rm_col[missing[0]].rc_size || i > 0);
1232
1233                 for (x = 0; x < ccount; x++, src++) {
1234                         if (*src != 0)
1235                                 log = vdev_raidz_log2[*src];
1236
1237                         for (cc = 0; cc < nmissing; cc++) {
1238                                 if (x >= dcount[cc])
1239                                         continue;
1240
1241                                 if (*src == 0) {
1242                                         val = 0;
1243                                 } else {
1244                                         if ((ll = log + invlog[cc][i]) >= 255)
1245                                                 ll -= 255;
1246                                         val = vdev_raidz_pow2[ll];
1247                                 }
1248
1249                                 if (i == 0)
1250                                         dst[cc][x] = val;
1251                                 else
1252                                         dst[cc][x] ^= val;
1253                         }
1254                 }
1255         }
1256
1257         kmem_free(p, psize);
1258 }
1259
1260 static int
1261 vdev_raidz_reconstruct_general(raidz_map_t *rm, int *tgts, int ntgts)
1262 {
1263         int n, i, c, t, tt;
1264         int nmissing_rows;
1265         int missing_rows[VDEV_RAIDZ_MAXPARITY];
1266         int parity_map[VDEV_RAIDZ_MAXPARITY];
1267
1268         uint8_t *p, *pp;
1269         size_t psize;
1270
1271         uint8_t *rows[VDEV_RAIDZ_MAXPARITY];
1272         uint8_t *invrows[VDEV_RAIDZ_MAXPARITY];
1273         uint8_t *used;
1274
1275         int code = 0;
1276
1277
1278         n = rm->rm_cols - rm->rm_firstdatacol;
1279
1280         /*
1281          * Figure out which data columns are missing.
1282          */
1283         nmissing_rows = 0;
1284         for (t = 0; t < ntgts; t++) {
1285                 if (tgts[t] >= rm->rm_firstdatacol) {
1286                         missing_rows[nmissing_rows++] =
1287                             tgts[t] - rm->rm_firstdatacol;
1288                 }
1289         }
1290
1291         /*
1292          * Figure out which parity columns to use to help generate the missing
1293          * data columns.
1294          */
1295         for (tt = 0, c = 0, i = 0; i < nmissing_rows; c++) {
1296                 ASSERT(tt < ntgts);
1297                 ASSERT(c < rm->rm_firstdatacol);
1298
1299                 /*
1300                  * Skip any targeted parity columns.
1301                  */
1302                 if (c == tgts[tt]) {
1303                         tt++;
1304                         continue;
1305                 }
1306
1307                 code |= 1 << c;
1308
1309                 parity_map[i] = c;
1310                 i++;
1311         }
1312
1313         ASSERT(code != 0);
1314         ASSERT3U(code, <, 1 << VDEV_RAIDZ_MAXPARITY);
1315
1316         psize = (sizeof (rows[0][0]) + sizeof (invrows[0][0])) *
1317             nmissing_rows * n + sizeof (used[0]) * n;
1318         p = kmem_alloc(psize, KM_SLEEP);
1319
1320         for (pp = p, i = 0; i < nmissing_rows; i++) {
1321                 rows[i] = pp;
1322                 pp += n;
1323                 invrows[i] = pp;
1324                 pp += n;
1325         }
1326         used = pp;
1327
1328         for (i = 0; i < nmissing_rows; i++) {
1329                 used[i] = parity_map[i];
1330         }
1331
1332         for (tt = 0, c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
1333                 if (tt < nmissing_rows &&
1334                     c == missing_rows[tt] + rm->rm_firstdatacol) {
1335                         tt++;
1336                         continue;
1337                 }
1338
1339                 ASSERT3S(i, <, n);
1340                 used[i] = c;
1341                 i++;
1342         }
1343
1344         /*
1345          * Initialize the interesting rows of the matrix.
1346          */
1347         vdev_raidz_matrix_init(rm, n, nmissing_rows, parity_map, rows);
1348
1349         /*
1350          * Invert the matrix.
1351          */
1352         vdev_raidz_matrix_invert(rm, n, nmissing_rows, missing_rows, rows,
1353             invrows, used);
1354
1355         /*
1356          * Reconstruct the missing data using the generated matrix.
1357          */
1358         vdev_raidz_matrix_reconstruct(rm, n, nmissing_rows, missing_rows,
1359             invrows, used);
1360
1361         kmem_free(p, psize);
1362
1363         return (code);
1364 }
1365
1366 static int
1367 vdev_raidz_reconstruct(raidz_map_t *rm, int *t, int nt)
1368 {
1369         int tgts[VDEV_RAIDZ_MAXPARITY], *dt;
1370         int ntgts;
1371         int i, c;
1372         int code;
1373         int nbadparity, nbaddata;
1374         int parity_valid[VDEV_RAIDZ_MAXPARITY];
1375
1376         /*
1377          * The tgts list must already be sorted.
1378          */
1379         for (i = 1; i < nt; i++) {
1380                 ASSERT(t[i] > t[i - 1]);
1381         }
1382
1383         nbadparity = rm->rm_firstdatacol;
1384         nbaddata = rm->rm_cols - nbadparity;
1385         ntgts = 0;
1386         for (i = 0, c = 0; c < rm->rm_cols; c++) {
1387                 if (c < rm->rm_firstdatacol)
1388                         parity_valid[c] = B_FALSE;
1389
1390                 if (i < nt && c == t[i]) {
1391                         tgts[ntgts++] = c;
1392                         i++;
1393                 } else if (rm->rm_col[c].rc_error != 0) {
1394                         tgts[ntgts++] = c;
1395                 } else if (c >= rm->rm_firstdatacol) {
1396                         nbaddata--;
1397                 } else {
1398                         parity_valid[c] = B_TRUE;
1399                         nbadparity--;
1400                 }
1401         }
1402
1403         ASSERT(ntgts >= nt);
1404         ASSERT(nbaddata >= 0);
1405         ASSERT(nbaddata + nbadparity == ntgts);
1406
1407         dt = &tgts[nbadparity];
1408
1409         /*
1410          * See if we can use any of our optimized reconstruction routines.
1411          */
1412         if (!vdev_raidz_default_to_general) {
1413                 switch (nbaddata) {
1414                 case 1:
1415                         if (parity_valid[VDEV_RAIDZ_P])
1416                                 return (vdev_raidz_reconstruct_p(rm, dt, 1));
1417
1418                         ASSERT(rm->rm_firstdatacol > 1);
1419
1420                         if (parity_valid[VDEV_RAIDZ_Q])
1421                                 return (vdev_raidz_reconstruct_q(rm, dt, 1));
1422
1423                         ASSERT(rm->rm_firstdatacol > 2);
1424                         break;
1425
1426                 case 2:
1427                         ASSERT(rm->rm_firstdatacol > 1);
1428
1429                         if (parity_valid[VDEV_RAIDZ_P] &&
1430                             parity_valid[VDEV_RAIDZ_Q])
1431                                 return (vdev_raidz_reconstruct_pq(rm, dt, 2));
1432
1433                         ASSERT(rm->rm_firstdatacol > 2);
1434
1435                         break;
1436                 }
1437         }
1438
1439         code = vdev_raidz_reconstruct_general(rm, tgts, ntgts);
1440         ASSERT(code < (1 << VDEV_RAIDZ_MAXPARITY));
1441         ASSERT(code > 0);
1442         return (code);
1443 }
1444
1445 static int
1446 vdev_raidz_open(vdev_t *vd, uint64_t *asize, uint64_t *max_asize,
1447     uint64_t *ashift)
1448 {
1449         vdev_t *cvd;
1450         uint64_t nparity = vd->vdev_nparity;
1451         int c;
1452         int lasterror = 0;
1453         int numerrors = 0;
1454
1455         ASSERT(nparity > 0);
1456
1457         if (nparity > VDEV_RAIDZ_MAXPARITY ||
1458             vd->vdev_children < nparity + 1) {
1459                 vd->vdev_stat.vs_aux = VDEV_AUX_BAD_LABEL;
1460                 return (EINVAL);
1461         }
1462
1463         vdev_open_children(vd);
1464
1465         for (c = 0; c < vd->vdev_children; c++) {
1466                 cvd = vd->vdev_child[c];
1467
1468                 if (cvd->vdev_open_error != 0) {
1469                         lasterror = cvd->vdev_open_error;
1470                         numerrors++;
1471                         continue;
1472                 }
1473
1474                 *asize = MIN(*asize - 1, cvd->vdev_asize - 1) + 1;
1475                 *max_asize = MIN(*max_asize - 1, cvd->vdev_max_asize - 1) + 1;
1476                 *ashift = MAX(*ashift, cvd->vdev_ashift);
1477         }
1478
1479         *asize *= vd->vdev_children;
1480         *max_asize *= vd->vdev_children;
1481
1482         if (numerrors > nparity) {
1483                 vd->vdev_stat.vs_aux = VDEV_AUX_NO_REPLICAS;
1484                 return (lasterror);
1485         }
1486
1487         return (0);
1488 }
1489
1490 static void
1491 vdev_raidz_close(vdev_t *vd)
1492 {
1493         int c;
1494
1495         for (c = 0; c < vd->vdev_children; c++)
1496                 vdev_close(vd->vdev_child[c]);
1497 }
1498
1499 static uint64_t
1500 vdev_raidz_asize(vdev_t *vd, uint64_t psize)
1501 {
1502         uint64_t asize;
1503         uint64_t ashift = vd->vdev_top->vdev_ashift;
1504         uint64_t cols = vd->vdev_children;
1505         uint64_t nparity = vd->vdev_nparity;
1506
1507         asize = ((psize - 1) >> ashift) + 1;
1508         asize += nparity * ((asize + cols - nparity - 1) / (cols - nparity));
1509         asize = roundup(asize, nparity + 1) << ashift;
1510
1511         return (asize);
1512 }
1513
1514 static void
1515 vdev_raidz_child_done(zio_t *zio)
1516 {
1517         raidz_col_t *rc = zio->io_private;
1518
1519         rc->rc_error = zio->io_error;
1520         rc->rc_tried = 1;
1521         rc->rc_skipped = 0;
1522 }
1523
1524 static int
1525 vdev_raidz_io_start(zio_t *zio)
1526 {
1527         vdev_t *vd = zio->io_vd;
1528         vdev_t *tvd = vd->vdev_top;
1529         vdev_t *cvd;
1530         raidz_map_t *rm;
1531         raidz_col_t *rc;
1532         int c, i;
1533
1534         rm = vdev_raidz_map_alloc(zio, tvd->vdev_ashift, vd->vdev_children,
1535             vd->vdev_nparity);
1536
1537         ASSERT3U(rm->rm_asize, ==, vdev_psize_to_asize(vd, zio->io_size));
1538
1539         if (zio->io_type == ZIO_TYPE_WRITE) {
1540                 vdev_raidz_generate_parity(rm);
1541
1542                 for (c = 0; c < rm->rm_cols; c++) {
1543                         rc = &rm->rm_col[c];
1544                         cvd = vd->vdev_child[rc->rc_devidx];
1545                         zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1546                             rc->rc_offset, rc->rc_data, rc->rc_size,
1547                             zio->io_type, zio->io_priority, 0,
1548                             vdev_raidz_child_done, rc));
1549                 }
1550
1551                 /*
1552                  * Generate optional I/Os for any skipped sectors to improve
1553                  * aggregation contiguity.
1554                  */
1555                 for (c = rm->rm_skipstart, i = 0; i < rm->rm_nskip; c++, i++) {
1556                         ASSERT(c <= rm->rm_scols);
1557                         if (c == rm->rm_scols)
1558                                 c = 0;
1559                         rc = &rm->rm_col[c];
1560                         cvd = vd->vdev_child[rc->rc_devidx];
1561                         zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1562                             rc->rc_offset + rc->rc_size, NULL,
1563                             1 << tvd->vdev_ashift,
1564                             zio->io_type, zio->io_priority,
1565                             ZIO_FLAG_NODATA | ZIO_FLAG_OPTIONAL, NULL, NULL));
1566                 }
1567
1568                 return (ZIO_PIPELINE_CONTINUE);
1569         }
1570
1571         ASSERT(zio->io_type == ZIO_TYPE_READ);
1572
1573         /*
1574          * Iterate over the columns in reverse order so that we hit the parity
1575          * last -- any errors along the way will force us to read the parity.
1576          */
1577         for (c = rm->rm_cols - 1; c >= 0; c--) {
1578                 rc = &rm->rm_col[c];
1579                 cvd = vd->vdev_child[rc->rc_devidx];
1580                 if (!vdev_readable(cvd)) {
1581                         if (c >= rm->rm_firstdatacol)
1582                                 rm->rm_missingdata++;
1583                         else
1584                                 rm->rm_missingparity++;
1585                         rc->rc_error = ENXIO;
1586                         rc->rc_tried = 1;       /* don't even try */
1587                         rc->rc_skipped = 1;
1588                         continue;
1589                 }
1590                 if (vdev_dtl_contains(cvd, DTL_MISSING, zio->io_txg, 1)) {
1591                         if (c >= rm->rm_firstdatacol)
1592                                 rm->rm_missingdata++;
1593                         else
1594                                 rm->rm_missingparity++;
1595                         rc->rc_error = ESTALE;
1596                         rc->rc_skipped = 1;
1597                         continue;
1598                 }
1599                 if (c >= rm->rm_firstdatacol || rm->rm_missingdata > 0 ||
1600                     (zio->io_flags & (ZIO_FLAG_SCRUB | ZIO_FLAG_RESILVER))) {
1601                         zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1602                             rc->rc_offset, rc->rc_data, rc->rc_size,
1603                             zio->io_type, zio->io_priority, 0,
1604                             vdev_raidz_child_done, rc));
1605                 }
1606         }
1607
1608         return (ZIO_PIPELINE_CONTINUE);
1609 }
1610
1611
1612 /*
1613  * Report a checksum error for a child of a RAID-Z device.
1614  */
1615 static void
1616 raidz_checksum_error(zio_t *zio, raidz_col_t *rc, void *bad_data)
1617 {
1618         vdev_t *vd = zio->io_vd->vdev_child[rc->rc_devidx];
1619
1620         if (!(zio->io_flags & ZIO_FLAG_SPECULATIVE)) {
1621                 zio_bad_cksum_t zbc;
1622                 raidz_map_t *rm = zio->io_vsd;
1623
1624                 mutex_enter(&vd->vdev_stat_lock);
1625                 vd->vdev_stat.vs_checksum_errors++;
1626                 mutex_exit(&vd->vdev_stat_lock);
1627
1628                 zbc.zbc_has_cksum = 0;
1629                 zbc.zbc_injected = rm->rm_ecksuminjected;
1630
1631                 zfs_ereport_post_checksum(zio->io_spa, vd, zio,
1632                     rc->rc_offset, rc->rc_size, rc->rc_data, bad_data,
1633                     &zbc);
1634         }
1635 }
1636
1637 /*
1638  * We keep track of whether or not there were any injected errors, so that
1639  * any ereports we generate can note it.
1640  */
1641 static int
1642 raidz_checksum_verify(zio_t *zio)
1643 {
1644         zio_bad_cksum_t zbc;
1645         raidz_map_t *rm = zio->io_vsd;
1646
1647         int ret = zio_checksum_error(zio, &zbc);
1648         if (ret != 0 && zbc.zbc_injected != 0)
1649                 rm->rm_ecksuminjected = 1;
1650
1651         return (ret);
1652 }
1653
1654 /*
1655  * Generate the parity from the data columns. If we tried and were able to
1656  * read the parity without error, verify that the generated parity matches the
1657  * data we read. If it doesn't, we fire off a checksum error. Return the
1658  * number such failures.
1659  */
1660 static int
1661 raidz_parity_verify(zio_t *zio, raidz_map_t *rm)
1662 {
1663         void *orig[VDEV_RAIDZ_MAXPARITY];
1664         int c, ret = 0;
1665         raidz_col_t *rc;
1666
1667         for (c = 0; c < rm->rm_firstdatacol; c++) {
1668                 rc = &rm->rm_col[c];
1669                 if (!rc->rc_tried || rc->rc_error != 0)
1670                         continue;
1671                 orig[c] = zio_buf_alloc(rc->rc_size);
1672                 bcopy(rc->rc_data, orig[c], rc->rc_size);
1673         }
1674
1675         vdev_raidz_generate_parity(rm);
1676
1677         for (c = 0; c < rm->rm_firstdatacol; c++) {
1678                 rc = &rm->rm_col[c];
1679                 if (!rc->rc_tried || rc->rc_error != 0)
1680                         continue;
1681                 if (bcmp(orig[c], rc->rc_data, rc->rc_size) != 0) {
1682                         raidz_checksum_error(zio, rc, orig[c]);
1683                         rc->rc_error = ECKSUM;
1684                         ret++;
1685                 }
1686                 zio_buf_free(orig[c], rc->rc_size);
1687         }
1688
1689         return (ret);
1690 }
1691
1692 /*
1693  * Keep statistics on all the ways that we used parity to correct data.
1694  */
1695 static uint64_t raidz_corrected[1 << VDEV_RAIDZ_MAXPARITY];
1696
1697 static int
1698 vdev_raidz_worst_error(raidz_map_t *rm)
1699 {
1700         int error = 0;
1701
1702         for (int c = 0; c < rm->rm_cols; c++)
1703                 error = zio_worst_error(error, rm->rm_col[c].rc_error);
1704
1705         return (error);
1706 }
1707
1708 /*
1709  * Iterate over all combinations of bad data and attempt a reconstruction.
1710  * Note that the algorithm below is non-optimal because it doesn't take into
1711  * account how reconstruction is actually performed. For example, with
1712  * triple-parity RAID-Z the reconstruction procedure is the same if column 4
1713  * is targeted as invalid as if columns 1 and 4 are targeted since in both
1714  * cases we'd only use parity information in column 0.
1715  */
1716 static int
1717 vdev_raidz_combrec(zio_t *zio, int total_errors, int data_errors)
1718 {
1719         raidz_map_t *rm = zio->io_vsd;
1720         raidz_col_t *rc;
1721         void *orig[VDEV_RAIDZ_MAXPARITY];
1722         int tstore[VDEV_RAIDZ_MAXPARITY + 2];
1723         int *tgts = &tstore[1];
1724         int current, next, i, c, n;
1725         int code, ret = 0;
1726
1727         ASSERT(total_errors < rm->rm_firstdatacol);
1728
1729         /*
1730          * This simplifies one edge condition.
1731          */
1732         tgts[-1] = -1;
1733
1734         for (n = 1; n <= rm->rm_firstdatacol - total_errors; n++) {
1735                 /*
1736                  * Initialize the targets array by finding the first n columns
1737                  * that contain no error.
1738                  *
1739                  * If there were no data errors, we need to ensure that we're
1740                  * always explicitly attempting to reconstruct at least one
1741                  * data column. To do this, we simply push the highest target
1742                  * up into the data columns.
1743                  */
1744                 for (c = 0, i = 0; i < n; i++) {
1745                         if (i == n - 1 && data_errors == 0 &&
1746                             c < rm->rm_firstdatacol) {
1747                                 c = rm->rm_firstdatacol;
1748                         }
1749
1750                         while (rm->rm_col[c].rc_error != 0) {
1751                                 c++;
1752                                 ASSERT3S(c, <, rm->rm_cols);
1753                         }
1754
1755                         tgts[i] = c++;
1756                 }
1757
1758                 /*
1759                  * Setting tgts[n] simplifies the other edge condition.
1760                  */
1761                 tgts[n] = rm->rm_cols;
1762
1763                 /*
1764                  * These buffers were allocated in previous iterations.
1765                  */
1766                 for (i = 0; i < n - 1; i++) {
1767                         ASSERT(orig[i] != NULL);
1768                 }
1769
1770                 orig[n - 1] = zio_buf_alloc(rm->rm_col[0].rc_size);
1771
1772                 current = 0;
1773                 next = tgts[current];
1774
1775                 while (current != n) {
1776                         tgts[current] = next;
1777                         current = 0;
1778
1779                         /*
1780                          * Save off the original data that we're going to
1781                          * attempt to reconstruct.
1782                          */
1783                         for (i = 0; i < n; i++) {
1784                                 ASSERT(orig[i] != NULL);
1785                                 c = tgts[i];
1786                                 ASSERT3S(c, >=, 0);
1787                                 ASSERT3S(c, <, rm->rm_cols);
1788                                 rc = &rm->rm_col[c];
1789                                 bcopy(rc->rc_data, orig[i], rc->rc_size);
1790                         }
1791
1792                         /*
1793                          * Attempt a reconstruction and exit the outer loop on
1794                          * success.
1795                          */
1796                         code = vdev_raidz_reconstruct(rm, tgts, n);
1797                         if (raidz_checksum_verify(zio) == 0) {
1798                                 atomic_inc_64(&raidz_corrected[code]);
1799
1800                                 for (i = 0; i < n; i++) {
1801                                         c = tgts[i];
1802                                         rc = &rm->rm_col[c];
1803                                         ASSERT(rc->rc_error == 0);
1804                                         if (rc->rc_tried)
1805                                                 raidz_checksum_error(zio, rc,
1806                                                     orig[i]);
1807                                         rc->rc_error = ECKSUM;
1808                                 }
1809
1810                                 ret = code;
1811                                 goto done;
1812                         }
1813
1814                         /*
1815                          * Restore the original data.
1816                          */
1817                         for (i = 0; i < n; i++) {
1818                                 c = tgts[i];
1819                                 rc = &rm->rm_col[c];
1820                                 bcopy(orig[i], rc->rc_data, rc->rc_size);
1821                         }
1822
1823                         do {
1824                                 /*
1825                                  * Find the next valid column after the current
1826                                  * position..
1827                                  */
1828                                 for (next = tgts[current] + 1;
1829                                     next < rm->rm_cols &&
1830                                     rm->rm_col[next].rc_error != 0; next++)
1831                                         continue;
1832
1833                                 ASSERT(next <= tgts[current + 1]);
1834
1835                                 /*
1836                                  * If that spot is available, we're done here.
1837                                  */
1838                                 if (next != tgts[current + 1])
1839                                         break;
1840
1841                                 /*
1842                                  * Otherwise, find the next valid column after
1843                                  * the previous position.
1844                                  */
1845                                 for (c = tgts[current - 1] + 1;
1846                                     rm->rm_col[c].rc_error != 0; c++)
1847                                         continue;
1848
1849                                 tgts[current] = c;
1850                                 current++;
1851
1852                         } while (current != n);
1853                 }
1854         }
1855         n--;
1856 done:
1857         for (i = 0; i < n; i++) {
1858                 zio_buf_free(orig[i], rm->rm_col[0].rc_size);
1859         }
1860
1861         return (ret);
1862 }
1863
1864 static void
1865 vdev_raidz_io_done(zio_t *zio)
1866 {
1867         vdev_t *vd = zio->io_vd;
1868         vdev_t *cvd;
1869         raidz_map_t *rm = zio->io_vsd;
1870         raidz_col_t *rc;
1871         int unexpected_errors = 0;
1872         int parity_errors = 0;
1873         int parity_untried = 0;
1874         int data_errors = 0;
1875         int total_errors = 0;
1876         int n, c;
1877         int tgts[VDEV_RAIDZ_MAXPARITY];
1878         int code;
1879
1880         ASSERT(zio->io_bp != NULL);  /* XXX need to add code to enforce this */
1881
1882         ASSERT(rm->rm_missingparity <= rm->rm_firstdatacol);
1883         ASSERT(rm->rm_missingdata <= rm->rm_cols - rm->rm_firstdatacol);
1884
1885         for (c = 0; c < rm->rm_cols; c++) {
1886                 rc = &rm->rm_col[c];
1887
1888                 if (rc->rc_error) {
1889                         ASSERT(rc->rc_error != ECKSUM); /* child has no bp */
1890
1891                         if (c < rm->rm_firstdatacol)
1892                                 parity_errors++;
1893                         else
1894                                 data_errors++;
1895
1896                         if (!rc->rc_skipped)
1897                                 unexpected_errors++;
1898
1899                         total_errors++;
1900                 } else if (c < rm->rm_firstdatacol && !rc->rc_tried) {
1901                         parity_untried++;
1902                 }
1903         }
1904
1905         if (zio->io_type == ZIO_TYPE_WRITE) {
1906                 /*
1907                  * XXX -- for now, treat partial writes as a success.
1908                  * (If we couldn't write enough columns to reconstruct
1909                  * the data, the I/O failed.  Otherwise, good enough.)
1910                  *
1911                  * Now that we support write reallocation, it would be better
1912                  * to treat partial failure as real failure unless there are
1913                  * no non-degraded top-level vdevs left, and not update DTLs
1914                  * if we intend to reallocate.
1915                  */
1916                 /* XXPOLICY */
1917                 if (total_errors > rm->rm_firstdatacol)
1918                         zio->io_error = vdev_raidz_worst_error(rm);
1919
1920                 return;
1921         }
1922
1923         ASSERT(zio->io_type == ZIO_TYPE_READ);
1924         /*
1925          * There are three potential phases for a read:
1926          *      1. produce valid data from the columns read
1927          *      2. read all disks and try again
1928          *      3. perform combinatorial reconstruction
1929          *
1930          * Each phase is progressively both more expensive and less likely to
1931          * occur. If we encounter more errors than we can repair or all phases
1932          * fail, we have no choice but to return an error.
1933          */
1934
1935         /*
1936          * If the number of errors we saw was correctable -- less than or equal
1937          * to the number of parity disks read -- attempt to produce data that
1938          * has a valid checksum. Naturally, this case applies in the absence of
1939          * any errors.
1940          */
1941         if (total_errors <= rm->rm_firstdatacol - parity_untried) {
1942                 if (data_errors == 0) {
1943                         if (raidz_checksum_verify(zio) == 0) {
1944                                 /*
1945                                  * If we read parity information (unnecessarily
1946                                  * as it happens since no reconstruction was
1947                                  * needed) regenerate and verify the parity.
1948                                  * We also regenerate parity when resilvering
1949                                  * so we can write it out to the failed device
1950                                  * later.
1951                                  */
1952                                 if (parity_errors + parity_untried <
1953                                     rm->rm_firstdatacol ||
1954                                     (zio->io_flags & ZIO_FLAG_RESILVER)) {
1955                                         n = raidz_parity_verify(zio, rm);
1956                                         unexpected_errors += n;
1957                                         ASSERT(parity_errors + n <=
1958                                             rm->rm_firstdatacol);
1959                                 }
1960                                 goto done;
1961                         }
1962                 } else {
1963                         /*
1964                          * We either attempt to read all the parity columns or
1965                          * none of them. If we didn't try to read parity, we
1966                          * wouldn't be here in the correctable case. There must
1967                          * also have been fewer parity errors than parity
1968                          * columns or, again, we wouldn't be in this code path.
1969                          */
1970                         ASSERT(parity_untried == 0);
1971                         ASSERT(parity_errors < rm->rm_firstdatacol);
1972
1973                         /*
1974                          * Identify the data columns that reported an error.
1975                          */
1976                         n = 0;
1977                         for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
1978                                 rc = &rm->rm_col[c];
1979                                 if (rc->rc_error != 0) {
1980                                         ASSERT(n < VDEV_RAIDZ_MAXPARITY);
1981                                         tgts[n++] = c;
1982                                 }
1983                         }
1984
1985                         ASSERT(rm->rm_firstdatacol >= n);
1986
1987                         code = vdev_raidz_reconstruct(rm, tgts, n);
1988
1989                         if (raidz_checksum_verify(zio) == 0) {
1990                                 atomic_inc_64(&raidz_corrected[code]);
1991
1992                                 /*
1993                                  * If we read more parity disks than were used
1994                                  * for reconstruction, confirm that the other
1995                                  * parity disks produced correct data. This
1996                                  * routine is suboptimal in that it regenerates
1997                                  * the parity that we already used in addition
1998                                  * to the parity that we're attempting to
1999                                  * verify, but this should be a relatively
2000                                  * uncommon case, and can be optimized if it
2001                                  * becomes a problem. Note that we regenerate
2002                                  * parity when resilvering so we can write it
2003                                  * out to failed devices later.
2004                                  */
2005                                 if (parity_errors < rm->rm_firstdatacol - n ||
2006                                     (zio->io_flags & ZIO_FLAG_RESILVER)) {
2007                                         n = raidz_parity_verify(zio, rm);
2008                                         unexpected_errors += n;
2009                                         ASSERT(parity_errors + n <=
2010                                             rm->rm_firstdatacol);
2011                                 }
2012
2013                                 goto done;
2014                         }
2015                 }
2016         }
2017
2018         /*
2019          * This isn't a typical situation -- either we got a read error or
2020          * a child silently returned bad data. Read every block so we can
2021          * try again with as much data and parity as we can track down. If
2022          * we've already been through once before, all children will be marked
2023          * as tried so we'll proceed to combinatorial reconstruction.
2024          */
2025         unexpected_errors = 1;
2026         rm->rm_missingdata = 0;
2027         rm->rm_missingparity = 0;
2028
2029         for (c = 0; c < rm->rm_cols; c++) {
2030                 if (rm->rm_col[c].rc_tried)
2031                         continue;
2032
2033                 zio_vdev_io_redone(zio);
2034                 do {
2035                         rc = &rm->rm_col[c];
2036                         if (rc->rc_tried)
2037                                 continue;
2038                         zio_nowait(zio_vdev_child_io(zio, NULL,
2039                             vd->vdev_child[rc->rc_devidx],
2040                             rc->rc_offset, rc->rc_data, rc->rc_size,
2041                             zio->io_type, zio->io_priority, 0,
2042                             vdev_raidz_child_done, rc));
2043                 } while (++c < rm->rm_cols);
2044
2045                 return;
2046         }
2047
2048         /*
2049          * At this point we've attempted to reconstruct the data given the
2050          * errors we detected, and we've attempted to read all columns. There
2051          * must, therefore, be one or more additional problems -- silent errors
2052          * resulting in invalid data rather than explicit I/O errors resulting
2053          * in absent data. We check if there is enough additional data to
2054          * possibly reconstruct the data and then perform combinatorial
2055          * reconstruction over all possible combinations. If that fails,
2056          * we're cooked.
2057          */
2058         if (total_errors > rm->rm_firstdatacol) {
2059                 zio->io_error = vdev_raidz_worst_error(rm);
2060
2061         } else if (total_errors < rm->rm_firstdatacol &&
2062             (code = vdev_raidz_combrec(zio, total_errors, data_errors)) != 0) {
2063                 /*
2064                  * If we didn't use all the available parity for the
2065                  * combinatorial reconstruction, verify that the remaining
2066                  * parity is correct.
2067                  */
2068                 if (code != (1 << rm->rm_firstdatacol) - 1)
2069                         (void) raidz_parity_verify(zio, rm);
2070         } else {
2071                 /*
2072                  * We're here because either:
2073                  *
2074                  *      total_errors == rm_first_datacol, or
2075                  *      vdev_raidz_combrec() failed
2076                  *
2077                  * In either case, there is enough bad data to prevent
2078                  * reconstruction.
2079                  *
2080                  * Start checksum ereports for all children which haven't
2081                  * failed, and the IO wasn't speculative.
2082                  */
2083                 zio->io_error = ECKSUM;
2084
2085                 if (!(zio->io_flags & ZIO_FLAG_SPECULATIVE)) {
2086                         for (c = 0; c < rm->rm_cols; c++) {
2087                                 rc = &rm->rm_col[c];
2088                                 if (rc->rc_error == 0) {
2089                                         zio_bad_cksum_t zbc;
2090                                         zbc.zbc_has_cksum = 0;
2091                                         zbc.zbc_injected =
2092                                             rm->rm_ecksuminjected;
2093
2094                                         zfs_ereport_start_checksum(
2095                                             zio->io_spa,
2096                                             vd->vdev_child[rc->rc_devidx],
2097                                             zio, rc->rc_offset, rc->rc_size,
2098                                             (void *)(uintptr_t)c, &zbc);
2099                                 }
2100                         }
2101                 }
2102         }
2103
2104 done:
2105         zio_checksum_verified(zio);
2106
2107         if (zio->io_error == 0 && spa_writeable(zio->io_spa) &&
2108             (unexpected_errors || (zio->io_flags & ZIO_FLAG_RESILVER))) {
2109                 /*
2110                  * Use the good data we have in hand to repair damaged children.
2111                  */
2112                 for (c = 0; c < rm->rm_cols; c++) {
2113                         rc = &rm->rm_col[c];
2114                         cvd = vd->vdev_child[rc->rc_devidx];
2115
2116                         if (rc->rc_error == 0)
2117                                 continue;
2118
2119                         zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
2120                             rc->rc_offset, rc->rc_data, rc->rc_size,
2121                             ZIO_TYPE_WRITE, zio->io_priority,
2122                             ZIO_FLAG_IO_REPAIR | (unexpected_errors ?
2123                             ZIO_FLAG_SELF_HEAL : 0), NULL, NULL));
2124                 }
2125         }
2126 }
2127
2128 static void
2129 vdev_raidz_state_change(vdev_t *vd, int faulted, int degraded)
2130 {
2131         if (faulted > vd->vdev_nparity)
2132                 vdev_set_state(vd, B_FALSE, VDEV_STATE_CANT_OPEN,
2133                     VDEV_AUX_NO_REPLICAS);
2134         else if (degraded + faulted != 0)
2135                 vdev_set_state(vd, B_FALSE, VDEV_STATE_DEGRADED, VDEV_AUX_NONE);
2136         else
2137                 vdev_set_state(vd, B_FALSE, VDEV_STATE_HEALTHY, VDEV_AUX_NONE);
2138 }
2139
2140 vdev_ops_t vdev_raidz_ops = {
2141         vdev_raidz_open,
2142         vdev_raidz_close,
2143         vdev_raidz_asize,
2144         vdev_raidz_io_start,
2145         vdev_raidz_io_done,
2146         vdev_raidz_state_change,
2147         NULL,
2148         NULL,
2149         VDEV_TYPE_RAIDZ,        /* name of this vdev type */
2150         B_FALSE                 /* not a leaf vdev */
2151 };