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.
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.
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]
23 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Copyright (c) 2012, 2014 by Delphix. All rights reserved.
25 * Copyright (c) 2016 Gvozden Nešković. All rights reserved.
28 #include <sys/zfs_context.h>
30 #include <sys/vdev_impl.h>
32 #include <sys/zio_checksum.h>
34 #include <sys/fs/zfs.h>
35 #include <sys/fm/fs/zfs.h>
36 #include <sys/vdev_raidz.h>
37 #include <sys/vdev_raidz_impl.h>
40 * Virtual device vector for RAID-Z.
42 * This vdev supports single, double, and triple parity. For single parity,
43 * we use a simple XOR of all the data columns. For double or triple parity,
44 * we use a special case of Reed-Solomon coding. This extends the
45 * technique described in "The mathematics of RAID-6" by H. Peter Anvin by
46 * drawing on the system described in "A Tutorial on Reed-Solomon Coding for
47 * Fault-Tolerance in RAID-like Systems" by James S. Plank on which the
48 * former is also based. The latter is designed to provide higher performance
51 * Note that the Plank paper claimed to support arbitrary N+M, but was then
52 * amended six years later identifying a critical flaw that invalidates its
53 * claims. Nevertheless, the technique can be adapted to work for up to
54 * triple parity. For additional parity, the amendment "Note: Correction to
55 * the 1997 Tutorial on Reed-Solomon Coding" by James S. Plank and Ying Ding
56 * is viable, but the additional complexity means that write performance will
59 * All of the methods above operate on a Galois field, defined over the
60 * integers mod 2^N. In our case we choose N=8 for GF(8) so that all elements
61 * can be expressed with a single byte. Briefly, the operations on the
62 * field are defined as follows:
64 * o addition (+) is represented by a bitwise XOR
65 * o subtraction (-) is therefore identical to addition: A + B = A - B
66 * o multiplication of A by 2 is defined by the following bitwise expression:
71 * (A * 2)_4 = A_3 + A_7
72 * (A * 2)_3 = A_2 + A_7
73 * (A * 2)_2 = A_1 + A_7
77 * In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).
78 * As an aside, this multiplication is derived from the error correcting
79 * primitive polynomial x^8 + x^4 + x^3 + x^2 + 1.
81 * Observe that any number in the field (except for 0) can be expressed as a
82 * power of 2 -- a generator for the field. We store a table of the powers of
83 * 2 and logs base 2 for quick look ups, and exploit the fact that A * B can
84 * be rewritten as 2^(log_2(A) + log_2(B)) (where '+' is normal addition rather
85 * than field addition). The inverse of a field element A (A^-1) is therefore
86 * A ^ (255 - 1) = A^254.
88 * The up-to-three parity columns, P, Q, R over several data columns,
89 * D_0, ... D_n-1, can be expressed by field operations:
91 * P = D_0 + D_1 + ... + D_n-2 + D_n-1
92 * Q = 2^n-1 * D_0 + 2^n-2 * D_1 + ... + 2^1 * D_n-2 + 2^0 * D_n-1
93 * = ((...((D_0) * 2 + D_1) * 2 + ...) * 2 + D_n-2) * 2 + D_n-1
94 * R = 4^n-1 * D_0 + 4^n-2 * D_1 + ... + 4^1 * D_n-2 + 4^0 * D_n-1
95 * = ((...((D_0) * 4 + D_1) * 4 + ...) * 4 + D_n-2) * 4 + D_n-1
97 * We chose 1, 2, and 4 as our generators because 1 corresponds to the trival
98 * XOR operation, and 2 and 4 can be computed quickly and generate linearly-
99 * independent coefficients. (There are no additional coefficients that have
100 * this property which is why the uncorrected Plank method breaks down.)
102 * See the reconstruction code below for how P, Q and R can used individually
103 * or in concert to recover missing data columns.
106 #define VDEV_RAIDZ_P 0
107 #define VDEV_RAIDZ_Q 1
108 #define VDEV_RAIDZ_R 2
110 #define VDEV_RAIDZ_MUL_2(x) (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
111 #define VDEV_RAIDZ_MUL_4(x) (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
114 * We provide a mechanism to perform the field multiplication operation on a
115 * 64-bit value all at once rather than a byte at a time. This works by
116 * creating a mask from the top bit in each byte and using that to
117 * conditionally apply the XOR of 0x1d.
119 #define VDEV_RAIDZ_64MUL_2(x, mask) \
121 (mask) = (x) & 0x8080808080808080ULL; \
122 (mask) = ((mask) << 1) - ((mask) >> 7); \
123 (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
124 ((mask) & 0x1d1d1d1d1d1d1d1dULL); \
127 #define VDEV_RAIDZ_64MUL_4(x, mask) \
129 VDEV_RAIDZ_64MUL_2((x), mask); \
130 VDEV_RAIDZ_64MUL_2((x), mask); \
134 vdev_raidz_map_free(raidz_map_t
*rm
)
138 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
139 abd_free(rm
->rm_col
[c
].rc_abd
);
141 if (rm
->rm_col
[c
].rc_gdata
!= NULL
)
142 abd_free(rm
->rm_col
[c
].rc_gdata
);
145 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++)
146 abd_put(rm
->rm_col
[c
].rc_abd
);
148 if (rm
->rm_abd_copy
!= NULL
)
149 abd_free(rm
->rm_abd_copy
);
151 kmem_free(rm
, offsetof(raidz_map_t
, rm_col
[rm
->rm_scols
]));
155 vdev_raidz_map_free_vsd(zio_t
*zio
)
157 raidz_map_t
*rm
= zio
->io_vsd
;
159 ASSERT0(rm
->rm_freed
);
162 if (rm
->rm_reports
== 0)
163 vdev_raidz_map_free(rm
);
168 vdev_raidz_cksum_free(void *arg
, size_t ignored
)
170 raidz_map_t
*rm
= arg
;
172 ASSERT3U(rm
->rm_reports
, >, 0);
174 if (--rm
->rm_reports
== 0 && rm
->rm_freed
!= 0)
175 vdev_raidz_map_free(rm
);
179 vdev_raidz_cksum_finish(zio_cksum_report_t
*zcr
, const abd_t
*good_data
)
181 raidz_map_t
*rm
= zcr
->zcr_cbdata
;
182 const size_t c
= zcr
->zcr_cbinfo
;
185 const abd_t
*good
= NULL
;
186 const abd_t
*bad
= rm
->rm_col
[c
].rc_abd
;
188 if (good_data
== NULL
) {
189 zfs_ereport_finish_checksum(zcr
, NULL
, NULL
, B_FALSE
);
193 if (c
< rm
->rm_firstdatacol
) {
195 * The first time through, calculate the parity blocks for
196 * the good data (this relies on the fact that the good
197 * data never changes for a given logical ZIO)
199 if (rm
->rm_col
[0].rc_gdata
== NULL
) {
200 abd_t
*bad_parity
[VDEV_RAIDZ_MAXPARITY
];
203 * Set up the rm_col[]s to generate the parity for
204 * good_data, first saving the parity bufs and
205 * replacing them with buffers to hold the result.
207 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++) {
208 bad_parity
[x
] = rm
->rm_col
[x
].rc_abd
;
209 rm
->rm_col
[x
].rc_abd
=
210 rm
->rm_col
[x
].rc_gdata
=
211 abd_alloc_sametype(rm
->rm_col
[x
].rc_abd
,
212 rm
->rm_col
[x
].rc_size
);
215 /* fill in the data columns from good_data */
217 for (; x
< rm
->rm_cols
; x
++) {
218 abd_put(rm
->rm_col
[x
].rc_abd
);
220 rm
->rm_col
[x
].rc_abd
=
221 abd_get_offset_size((abd_t
*)good_data
,
222 offset
, rm
->rm_col
[x
].rc_size
);
223 offset
+= rm
->rm_col
[x
].rc_size
;
227 * Construct the parity from the good data.
229 vdev_raidz_generate_parity(rm
);
231 /* restore everything back to its original state */
232 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++)
233 rm
->rm_col
[x
].rc_abd
= bad_parity
[x
];
236 for (x
= rm
->rm_firstdatacol
; x
< rm
->rm_cols
; x
++) {
237 abd_put(rm
->rm_col
[x
].rc_abd
);
238 rm
->rm_col
[x
].rc_abd
= abd_get_offset_size(
239 rm
->rm_abd_copy
, offset
,
240 rm
->rm_col
[x
].rc_size
);
241 offset
+= rm
->rm_col
[x
].rc_size
;
245 ASSERT3P(rm
->rm_col
[c
].rc_gdata
, !=, NULL
);
246 good
= abd_get_offset_size(rm
->rm_col
[c
].rc_gdata
, 0,
247 rm
->rm_col
[c
].rc_size
);
249 /* adjust good_data to point at the start of our column */
251 for (x
= rm
->rm_firstdatacol
; x
< c
; x
++)
252 offset
+= rm
->rm_col
[x
].rc_size
;
254 good
= abd_get_offset_size((abd_t
*)good_data
, offset
,
255 rm
->rm_col
[c
].rc_size
);
258 /* we drop the ereport if it ends up that the data was good */
259 zfs_ereport_finish_checksum(zcr
, good
, bad
, B_TRUE
);
260 abd_put((abd_t
*)good
);
264 * Invoked indirectly by zfs_ereport_start_checksum(), called
265 * below when our read operation fails completely. The main point
266 * is to keep a copy of everything we read from disk, so that at
267 * vdev_raidz_cksum_finish() time we can compare it with the good data.
270 vdev_raidz_cksum_report(zio_t
*zio
, zio_cksum_report_t
*zcr
, void *arg
)
272 size_t c
= (size_t)(uintptr_t)arg
;
275 raidz_map_t
*rm
= zio
->io_vsd
;
278 /* set up the report and bump the refcount */
279 zcr
->zcr_cbdata
= rm
;
281 zcr
->zcr_finish
= vdev_raidz_cksum_finish
;
282 zcr
->zcr_free
= vdev_raidz_cksum_free
;
285 ASSERT3U(rm
->rm_reports
, >, 0);
287 if (rm
->rm_abd_copy
!= NULL
)
291 * It's the first time we're called for this raidz_map_t, so we need
292 * to copy the data aside; there's no guarantee that our zio's buffer
293 * won't be re-used for something else.
295 * Our parity data is already in separate buffers, so there's no need
300 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++)
301 size
+= rm
->rm_col
[c
].rc_size
;
303 rm
->rm_abd_copy
= abd_alloc_for_io(size
, B_FALSE
);
305 for (offset
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
306 raidz_col_t
*col
= &rm
->rm_col
[c
];
307 abd_t
*tmp
= abd_get_offset_size(rm
->rm_abd_copy
, offset
,
310 abd_copy(tmp
, col
->rc_abd
, col
->rc_size
);
312 abd_put(col
->rc_abd
);
315 offset
+= col
->rc_size
;
317 ASSERT3U(offset
, ==, size
);
320 static const zio_vsd_ops_t vdev_raidz_vsd_ops
= {
321 .vsd_free
= vdev_raidz_map_free_vsd
,
322 .vsd_cksum_report
= vdev_raidz_cksum_report
326 * Divides the IO evenly across all child vdevs; usually, dcols is
327 * the number of children in the target vdev.
329 * Avoid inlining the function to keep vdev_raidz_io_start(), which
330 * is this functions only caller, as small as possible on the stack.
332 noinline raidz_map_t
*
333 vdev_raidz_map_alloc(zio_t
*zio
, uint64_t ashift
, uint64_t dcols
,
337 /* The starting RAIDZ (parent) vdev sector of the block. */
338 uint64_t b
= zio
->io_offset
>> ashift
;
339 /* The zio's size in units of the vdev's minimum sector size. */
340 uint64_t s
= zio
->io_size
>> ashift
;
341 /* The first column for this stripe. */
342 uint64_t f
= b
% dcols
;
343 /* The starting byte offset on each child vdev. */
344 uint64_t o
= (b
/ dcols
) << ashift
;
345 uint64_t q
, r
, c
, bc
, col
, acols
, scols
, coff
, devidx
, asize
, tot
;
349 * "Quotient": The number of data sectors for this stripe on all but
350 * the "big column" child vdevs that also contain "remainder" data.
352 q
= s
/ (dcols
- nparity
);
355 * "Remainder": The number of partial stripe data sectors in this I/O.
356 * This will add a sector to some, but not all, child vdevs.
358 r
= s
- q
* (dcols
- nparity
);
360 /* The number of "big columns" - those which contain remainder data. */
361 bc
= (r
== 0 ? 0 : r
+ nparity
);
364 * The total number of data and parity sectors associated with
367 tot
= s
+ nparity
* (q
+ (r
== 0 ? 0 : 1));
369 /* acols: The columns that will be accessed. */
370 /* scols: The columns that will be accessed or skipped. */
372 /* Our I/O request doesn't span all child vdevs. */
374 scols
= MIN(dcols
, roundup(bc
, nparity
+ 1));
380 ASSERT3U(acols
, <=, scols
);
382 rm
= kmem_alloc(offsetof(raidz_map_t
, rm_col
[scols
]), KM_SLEEP
);
385 rm
->rm_scols
= scols
;
387 rm
->rm_skipstart
= bc
;
388 rm
->rm_missingdata
= 0;
389 rm
->rm_missingparity
= 0;
390 rm
->rm_firstdatacol
= nparity
;
391 rm
->rm_abd_copy
= NULL
;
394 rm
->rm_ecksuminjected
= 0;
398 for (c
= 0; c
< scols
; c
++) {
403 coff
+= 1ULL << ashift
;
405 rm
->rm_col
[c
].rc_devidx
= col
;
406 rm
->rm_col
[c
].rc_offset
= coff
;
407 rm
->rm_col
[c
].rc_abd
= NULL
;
408 rm
->rm_col
[c
].rc_gdata
= NULL
;
409 rm
->rm_col
[c
].rc_error
= 0;
410 rm
->rm_col
[c
].rc_tried
= 0;
411 rm
->rm_col
[c
].rc_skipped
= 0;
414 rm
->rm_col
[c
].rc_size
= 0;
416 rm
->rm_col
[c
].rc_size
= (q
+ 1) << ashift
;
418 rm
->rm_col
[c
].rc_size
= q
<< ashift
;
420 asize
+= rm
->rm_col
[c
].rc_size
;
423 ASSERT3U(asize
, ==, tot
<< ashift
);
424 rm
->rm_asize
= roundup(asize
, (nparity
+ 1) << ashift
);
425 rm
->rm_nskip
= roundup(tot
, nparity
+ 1) - tot
;
426 ASSERT3U(rm
->rm_asize
- asize
, ==, rm
->rm_nskip
<< ashift
);
427 ASSERT3U(rm
->rm_nskip
, <=, nparity
);
429 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++)
430 rm
->rm_col
[c
].rc_abd
=
431 abd_alloc_linear(rm
->rm_col
[c
].rc_size
, B_FALSE
);
433 rm
->rm_col
[c
].rc_abd
= abd_get_offset_size(zio
->io_abd
, 0,
434 rm
->rm_col
[c
].rc_size
);
435 off
= rm
->rm_col
[c
].rc_size
;
437 for (c
= c
+ 1; c
< acols
; c
++) {
438 rm
->rm_col
[c
].rc_abd
= abd_get_offset_size(zio
->io_abd
, off
,
439 rm
->rm_col
[c
].rc_size
);
440 off
+= rm
->rm_col
[c
].rc_size
;
444 * If all data stored spans all columns, there's a danger that parity
445 * will always be on the same device and, since parity isn't read
446 * during normal operation, that that device's I/O bandwidth won't be
447 * used effectively. We therefore switch the parity every 1MB.
449 * ... at least that was, ostensibly, the theory. As a practical
450 * matter unless we juggle the parity between all devices evenly, we
451 * won't see any benefit. Further, occasional writes that aren't a
452 * multiple of the LCM of the number of children and the minimum
453 * stripe width are sufficient to avoid pessimal behavior.
454 * Unfortunately, this decision created an implicit on-disk format
455 * requirement that we need to support for all eternity, but only
456 * for single-parity RAID-Z.
458 * If we intend to skip a sector in the zeroth column for padding
459 * we must make sure to note this swap. We will never intend to
460 * skip the first column since at least one data and one parity
461 * column must appear in each row.
463 ASSERT(rm
->rm_cols
>= 2);
464 ASSERT(rm
->rm_col
[0].rc_size
== rm
->rm_col
[1].rc_size
);
466 if (rm
->rm_firstdatacol
== 1 && (zio
->io_offset
& (1ULL << 20))) {
467 devidx
= rm
->rm_col
[0].rc_devidx
;
468 o
= rm
->rm_col
[0].rc_offset
;
469 rm
->rm_col
[0].rc_devidx
= rm
->rm_col
[1].rc_devidx
;
470 rm
->rm_col
[0].rc_offset
= rm
->rm_col
[1].rc_offset
;
471 rm
->rm_col
[1].rc_devidx
= devidx
;
472 rm
->rm_col
[1].rc_offset
= o
;
474 if (rm
->rm_skipstart
== 0)
475 rm
->rm_skipstart
= 1;
479 zio
->io_vsd_ops
= &vdev_raidz_vsd_ops
;
481 /* init RAIDZ parity ops */
482 rm
->rm_ops
= vdev_raidz_math_get_ops();
494 vdev_raidz_p_func(void *buf
, size_t size
, void *private)
496 struct pqr_struct
*pqr
= private;
497 const uint64_t *src
= buf
;
498 int i
, cnt
= size
/ sizeof (src
[0]);
500 ASSERT(pqr
->p
&& !pqr
->q
&& !pqr
->r
);
502 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++)
509 vdev_raidz_pq_func(void *buf
, size_t size
, void *private)
511 struct pqr_struct
*pqr
= private;
512 const uint64_t *src
= buf
;
514 int i
, cnt
= size
/ sizeof (src
[0]);
516 ASSERT(pqr
->p
&& pqr
->q
&& !pqr
->r
);
518 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++) {
520 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
528 vdev_raidz_pqr_func(void *buf
, size_t size
, void *private)
530 struct pqr_struct
*pqr
= private;
531 const uint64_t *src
= buf
;
533 int i
, cnt
= size
/ sizeof (src
[0]);
535 ASSERT(pqr
->p
&& pqr
->q
&& pqr
->r
);
537 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++, pqr
->r
++) {
539 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
541 VDEV_RAIDZ_64MUL_4(*pqr
->r
, mask
);
549 vdev_raidz_generate_parity_p(raidz_map_t
*rm
)
555 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
556 src
= rm
->rm_col
[c
].rc_abd
;
557 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
559 if (c
== rm
->rm_firstdatacol
) {
560 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
562 struct pqr_struct pqr
= { p
, NULL
, NULL
};
563 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
564 vdev_raidz_p_func
, &pqr
);
570 vdev_raidz_generate_parity_pq(raidz_map_t
*rm
)
572 uint64_t *p
, *q
, pcnt
, ccnt
, mask
, i
;
576 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
577 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
578 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
580 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
581 src
= rm
->rm_col
[c
].rc_abd
;
582 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
583 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
585 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
587 if (c
== rm
->rm_firstdatacol
) {
588 ASSERT(ccnt
== pcnt
|| ccnt
== 0);
589 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
590 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
592 for (i
= ccnt
; i
< pcnt
; i
++) {
597 struct pqr_struct pqr
= { p
, q
, NULL
};
599 ASSERT(ccnt
<= pcnt
);
600 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
601 vdev_raidz_pq_func
, &pqr
);
604 * Treat short columns as though they are full of 0s.
605 * Note that there's therefore nothing needed for P.
607 for (i
= ccnt
; i
< pcnt
; i
++) {
608 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
615 vdev_raidz_generate_parity_pqr(raidz_map_t
*rm
)
617 uint64_t *p
, *q
, *r
, pcnt
, ccnt
, mask
, i
;
621 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
622 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
623 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
624 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
625 rm
->rm_col
[VDEV_RAIDZ_R
].rc_size
);
627 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
628 src
= rm
->rm_col
[c
].rc_abd
;
629 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
630 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
631 r
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_R
].rc_abd
);
633 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
635 if (c
== rm
->rm_firstdatacol
) {
636 ASSERT(ccnt
== pcnt
|| ccnt
== 0);
637 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
638 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
639 (void) memcpy(r
, p
, rm
->rm_col
[c
].rc_size
);
641 for (i
= ccnt
; i
< pcnt
; i
++) {
647 struct pqr_struct pqr
= { p
, q
, r
};
649 ASSERT(ccnt
<= pcnt
);
650 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
651 vdev_raidz_pqr_func
, &pqr
);
654 * Treat short columns as though they are full of 0s.
655 * Note that there's therefore nothing needed for P.
657 for (i
= ccnt
; i
< pcnt
; i
++) {
658 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
659 VDEV_RAIDZ_64MUL_4(r
[i
], mask
);
666 * Generate RAID parity in the first virtual columns according to the number of
667 * parity columns available.
670 vdev_raidz_generate_parity(raidz_map_t
*rm
)
672 /* Generate using the new math implementation */
673 if (vdev_raidz_math_generate(rm
) != RAIDZ_ORIGINAL_IMPL
)
676 switch (rm
->rm_firstdatacol
) {
678 vdev_raidz_generate_parity_p(rm
);
681 vdev_raidz_generate_parity_pq(rm
);
684 vdev_raidz_generate_parity_pqr(rm
);
687 cmn_err(CE_PANIC
, "invalid RAID-Z configuration");
693 vdev_raidz_reconst_p_func(void *dbuf
, void *sbuf
, size_t size
, void *private)
695 uint64_t *dst
= dbuf
;
696 uint64_t *src
= sbuf
;
697 int cnt
= size
/ sizeof (src
[0]);
700 for (i
= 0; i
< cnt
; i
++) {
709 vdev_raidz_reconst_q_pre_func(void *dbuf
, void *sbuf
, size_t size
,
712 uint64_t *dst
= dbuf
;
713 uint64_t *src
= sbuf
;
715 int cnt
= size
/ sizeof (dst
[0]);
718 for (i
= 0; i
< cnt
; i
++, dst
++, src
++) {
719 VDEV_RAIDZ_64MUL_2(*dst
, mask
);
728 vdev_raidz_reconst_q_pre_tail_func(void *buf
, size_t size
, void *private)
732 int cnt
= size
/ sizeof (dst
[0]);
735 for (i
= 0; i
< cnt
; i
++, dst
++) {
736 /* same operation as vdev_raidz_reconst_q_pre_func() on dst */
737 VDEV_RAIDZ_64MUL_2(*dst
, mask
);
743 struct reconst_q_struct
{
749 vdev_raidz_reconst_q_post_func(void *buf
, size_t size
, void *private)
751 struct reconst_q_struct
*rq
= private;
753 int cnt
= size
/ sizeof (dst
[0]);
756 for (i
= 0; i
< cnt
; i
++, dst
++, rq
->q
++) {
761 for (j
= 0, b
= (uint8_t *)dst
; j
< 8; j
++, b
++) {
762 *b
= vdev_raidz_exp2(*b
, rq
->exp
);
769 struct reconst_pq_struct
{
779 vdev_raidz_reconst_pq_func(void *xbuf
, void *ybuf
, size_t size
, void *private)
781 struct reconst_pq_struct
*rpq
= private;
786 for (i
= 0; i
< size
;
787 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++, yd
++) {
788 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
789 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
790 *yd
= *rpq
->p
^ *rpq
->pxy
^ *xd
;
797 vdev_raidz_reconst_pq_tail_func(void *xbuf
, size_t size
, void *private)
799 struct reconst_pq_struct
*rpq
= private;
803 for (i
= 0; i
< size
;
804 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++) {
805 /* same operation as vdev_raidz_reconst_pq_func() on xd */
806 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
807 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
814 vdev_raidz_reconstruct_p(raidz_map_t
*rm
, int *tgts
, int ntgts
)
821 ASSERT(x
>= rm
->rm_firstdatacol
);
822 ASSERT(x
< rm
->rm_cols
);
824 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
);
825 ASSERT(rm
->rm_col
[x
].rc_size
> 0);
827 src
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
828 dst
= rm
->rm_col
[x
].rc_abd
;
830 abd_copy_from_buf(dst
, abd_to_buf(src
), rm
->rm_col
[x
].rc_size
);
832 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
833 uint64_t size
= MIN(rm
->rm_col
[x
].rc_size
,
834 rm
->rm_col
[c
].rc_size
);
836 src
= rm
->rm_col
[c
].rc_abd
;
837 dst
= rm
->rm_col
[x
].rc_abd
;
842 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
843 vdev_raidz_reconst_p_func
, NULL
);
846 return (1 << VDEV_RAIDZ_P
);
850 vdev_raidz_reconstruct_q(raidz_map_t
*rm
, int *tgts
, int ntgts
)
855 struct reconst_q_struct rq
;
859 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
861 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
862 uint64_t size
= (c
== x
) ? 0 : MIN(rm
->rm_col
[x
].rc_size
,
863 rm
->rm_col
[c
].rc_size
);
865 src
= rm
->rm_col
[c
].rc_abd
;
866 dst
= rm
->rm_col
[x
].rc_abd
;
868 if (c
== rm
->rm_firstdatacol
) {
869 abd_copy(dst
, src
, size
);
870 if (rm
->rm_col
[x
].rc_size
> size
)
871 abd_zero_off(dst
, size
,
872 rm
->rm_col
[x
].rc_size
- size
);
875 ASSERT3U(size
, <=, rm
->rm_col
[x
].rc_size
);
876 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
877 vdev_raidz_reconst_q_pre_func
, NULL
);
878 (void) abd_iterate_func(dst
,
879 size
, rm
->rm_col
[x
].rc_size
- size
,
880 vdev_raidz_reconst_q_pre_tail_func
, NULL
);
884 src
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
885 dst
= rm
->rm_col
[x
].rc_abd
;
886 exp
= 255 - (rm
->rm_cols
- 1 - x
);
887 rq
.q
= abd_to_buf(src
);
890 (void) abd_iterate_func(dst
, 0, rm
->rm_col
[x
].rc_size
,
891 vdev_raidz_reconst_q_post_func
, &rq
);
893 return (1 << VDEV_RAIDZ_Q
);
897 vdev_raidz_reconstruct_pq(raidz_map_t
*rm
, int *tgts
, int ntgts
)
899 uint8_t *p
, *q
, *pxy
, *qxy
, tmp
, a
, b
, aexp
, bexp
;
900 abd_t
*pdata
, *qdata
;
901 uint64_t xsize
, ysize
;
905 struct reconst_pq_struct rpq
;
909 ASSERT(x
>= rm
->rm_firstdatacol
);
910 ASSERT(y
< rm
->rm_cols
);
912 ASSERT(rm
->rm_col
[x
].rc_size
>= rm
->rm_col
[y
].rc_size
);
915 * Move the parity data aside -- we're going to compute parity as
916 * though columns x and y were full of zeros -- Pxy and Qxy. We want to
917 * reuse the parity generation mechanism without trashing the actual
918 * parity so we make those columns appear to be full of zeros by
919 * setting their lengths to zero.
921 pdata
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
922 qdata
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
923 xsize
= rm
->rm_col
[x
].rc_size
;
924 ysize
= rm
->rm_col
[y
].rc_size
;
926 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
=
927 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
, B_TRUE
);
928 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
=
929 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
, B_TRUE
);
930 rm
->rm_col
[x
].rc_size
= 0;
931 rm
->rm_col
[y
].rc_size
= 0;
933 vdev_raidz_generate_parity_pq(rm
);
935 rm
->rm_col
[x
].rc_size
= xsize
;
936 rm
->rm_col
[y
].rc_size
= ysize
;
938 p
= abd_to_buf(pdata
);
939 q
= abd_to_buf(qdata
);
940 pxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
941 qxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
942 xd
= rm
->rm_col
[x
].rc_abd
;
943 yd
= rm
->rm_col
[y
].rc_abd
;
947 * Pxy = P + D_x + D_y
948 * Qxy = Q + 2^(ndevs - 1 - x) * D_x + 2^(ndevs - 1 - y) * D_y
950 * We can then solve for D_x:
951 * D_x = A * (P + Pxy) + B * (Q + Qxy)
953 * A = 2^(x - y) * (2^(x - y) + 1)^-1
954 * B = 2^(ndevs - 1 - x) * (2^(x - y) + 1)^-1
956 * With D_x in hand, we can easily solve for D_y:
957 * D_y = P + Pxy + D_x
960 a
= vdev_raidz_pow2
[255 + x
- y
];
961 b
= vdev_raidz_pow2
[255 - (rm
->rm_cols
- 1 - x
)];
962 tmp
= 255 - vdev_raidz_log2
[a
^ 1];
964 aexp
= vdev_raidz_log2
[vdev_raidz_exp2(a
, tmp
)];
965 bexp
= vdev_raidz_log2
[vdev_raidz_exp2(b
, tmp
)];
967 ASSERT3U(xsize
, >=, ysize
);
975 (void) abd_iterate_func2(xd
, yd
, 0, 0, ysize
,
976 vdev_raidz_reconst_pq_func
, &rpq
);
977 (void) abd_iterate_func(xd
, ysize
, xsize
- ysize
,
978 vdev_raidz_reconst_pq_tail_func
, &rpq
);
980 abd_free(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
981 abd_free(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
984 * Restore the saved parity data.
986 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
= pdata
;
987 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
= qdata
;
989 return ((1 << VDEV_RAIDZ_P
) | (1 << VDEV_RAIDZ_Q
));
994 * In the general case of reconstruction, we must solve the system of linear
995 * equations defined by the coeffecients used to generate parity as well as
996 * the contents of the data and parity disks. This can be expressed with
997 * vectors for the original data (D) and the actual data (d) and parity (p)
998 * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
1002 * | V | | D_0 | | p_m-1 |
1003 * | | x | : | = | d_0 |
1004 * | I | | D_n-1 | | : |
1005 * | | ~~ ~~ | d_n-1 |
1008 * I is simply a square identity matrix of size n, and V is a vandermonde
1009 * matrix defined by the coeffecients we chose for the various parity columns
1010 * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
1011 * computation as well as linear separability.
1014 * | 1 .. 1 1 1 | | p_0 |
1015 * | 2^n-1 .. 4 2 1 | __ __ | : |
1016 * | 4^n-1 .. 16 4 1 | | D_0 | | p_m-1 |
1017 * | 1 .. 0 0 0 | | D_1 | | d_0 |
1018 * | 0 .. 0 0 0 | x | D_2 | = | d_1 |
1019 * | : : : : | | : | | d_2 |
1020 * | 0 .. 1 0 0 | | D_n-1 | | : |
1021 * | 0 .. 0 1 0 | ~~ ~~ | : |
1022 * | 0 .. 0 0 1 | | d_n-1 |
1025 * Note that I, V, d, and p are known. To compute D, we must invert the
1026 * matrix and use the known data and parity values to reconstruct the unknown
1027 * data values. We begin by removing the rows in V|I and d|p that correspond
1028 * to failed or missing columns; we then make V|I square (n x n) and d|p
1029 * sized n by removing rows corresponding to unused parity from the bottom up
1030 * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
1031 * using Gauss-Jordan elimination. In the example below we use m=3 parity
1032 * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
1034 * | 1 1 1 1 1 1 1 1 |
1035 * | 128 64 32 16 8 4 2 1 | <-----+-+-- missing disks
1036 * | 19 205 116 29 64 16 4 1 | / /
1037 * | 1 0 0 0 0 0 0 0 | / /
1038 * | 0 1 0 0 0 0 0 0 | <--' /
1039 * (V|I) = | 0 0 1 0 0 0 0 0 | <---'
1040 * | 0 0 0 1 0 0 0 0 |
1041 * | 0 0 0 0 1 0 0 0 |
1042 * | 0 0 0 0 0 1 0 0 |
1043 * | 0 0 0 0 0 0 1 0 |
1044 * | 0 0 0 0 0 0 0 1 |
1047 * | 1 1 1 1 1 1 1 1 |
1048 * | 128 64 32 16 8 4 2 1 |
1049 * | 19 205 116 29 64 16 4 1 |
1050 * | 1 0 0 0 0 0 0 0 |
1051 * | 0 1 0 0 0 0 0 0 |
1052 * (V|I)' = | 0 0 1 0 0 0 0 0 |
1053 * | 0 0 0 1 0 0 0 0 |
1054 * | 0 0 0 0 1 0 0 0 |
1055 * | 0 0 0 0 0 1 0 0 |
1056 * | 0 0 0 0 0 0 1 0 |
1057 * | 0 0 0 0 0 0 0 1 |
1060 * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
1061 * have carefully chosen the seed values 1, 2, and 4 to ensure that this
1062 * matrix is not singular.
1064 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1065 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1066 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1067 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1068 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1069 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1070 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1071 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1074 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1075 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1076 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1077 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1078 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1079 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1080 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1081 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1084 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1085 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1086 * | 0 205 116 0 0 0 0 0 0 1 19 29 64 16 4 1 |
1087 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1088 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1089 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1090 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1091 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1094 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1095 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1096 * | 0 0 185 0 0 0 0 0 205 1 222 208 141 221 201 204 |
1097 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1098 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1099 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1100 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1101 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1104 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1105 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1106 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1107 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1108 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1109 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1110 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1111 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1114 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1115 * | 0 1 0 0 0 0 0 0 167 100 5 41 159 169 217 208 |
1116 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1117 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1118 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1119 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1120 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1121 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1124 * | 0 0 1 0 0 0 0 0 |
1125 * | 167 100 5 41 159 169 217 208 |
1126 * | 166 100 4 40 158 168 216 209 |
1127 * (V|I)'^-1 = | 0 0 0 1 0 0 0 0 |
1128 * | 0 0 0 0 1 0 0 0 |
1129 * | 0 0 0 0 0 1 0 0 |
1130 * | 0 0 0 0 0 0 1 0 |
1131 * | 0 0 0 0 0 0 0 1 |
1134 * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values
1135 * of the missing data.
1137 * As is apparent from the example above, the only non-trivial rows in the
1138 * inverse matrix correspond to the data disks that we're trying to
1139 * reconstruct. Indeed, those are the only rows we need as the others would
1140 * only be useful for reconstructing data known or assumed to be valid. For
1141 * that reason, we only build the coefficients in the rows that correspond to
1147 vdev_raidz_matrix_init(raidz_map_t
*rm
, int n
, int nmap
, int *map
,
1153 ASSERT(n
== rm
->rm_cols
- rm
->rm_firstdatacol
);
1156 * Fill in the missing rows of interest.
1158 for (i
= 0; i
< nmap
; i
++) {
1159 ASSERT3S(0, <=, map
[i
]);
1160 ASSERT3S(map
[i
], <=, 2);
1167 for (j
= 0; j
< n
; j
++) {
1171 rows
[i
][j
] = vdev_raidz_pow2
[pow
];
1177 vdev_raidz_matrix_invert(raidz_map_t
*rm
, int n
, int nmissing
, int *missing
,
1178 uint8_t **rows
, uint8_t **invrows
, const uint8_t *used
)
1184 * Assert that the first nmissing entries from the array of used
1185 * columns correspond to parity columns and that subsequent entries
1186 * correspond to data columns.
1188 for (i
= 0; i
< nmissing
; i
++) {
1189 ASSERT3S(used
[i
], <, rm
->rm_firstdatacol
);
1191 for (; i
< n
; i
++) {
1192 ASSERT3S(used
[i
], >=, rm
->rm_firstdatacol
);
1196 * First initialize the storage where we'll compute the inverse rows.
1198 for (i
= 0; i
< nmissing
; i
++) {
1199 for (j
= 0; j
< n
; j
++) {
1200 invrows
[i
][j
] = (i
== j
) ? 1 : 0;
1205 * Subtract all trivial rows from the rows of consequence.
1207 for (i
= 0; i
< nmissing
; i
++) {
1208 for (j
= nmissing
; j
< n
; j
++) {
1209 ASSERT3U(used
[j
], >=, rm
->rm_firstdatacol
);
1210 jj
= used
[j
] - rm
->rm_firstdatacol
;
1212 invrows
[i
][j
] = rows
[i
][jj
];
1218 * For each of the rows of interest, we must normalize it and subtract
1219 * a multiple of it from the other rows.
1221 for (i
= 0; i
< nmissing
; i
++) {
1222 for (j
= 0; j
< missing
[i
]; j
++) {
1223 ASSERT0(rows
[i
][j
]);
1225 ASSERT3U(rows
[i
][missing
[i
]], !=, 0);
1228 * Compute the inverse of the first element and multiply each
1229 * element in the row by that value.
1231 log
= 255 - vdev_raidz_log2
[rows
[i
][missing
[i
]]];
1233 for (j
= 0; j
< n
; j
++) {
1234 rows
[i
][j
] = vdev_raidz_exp2(rows
[i
][j
], log
);
1235 invrows
[i
][j
] = vdev_raidz_exp2(invrows
[i
][j
], log
);
1238 for (ii
= 0; ii
< nmissing
; ii
++) {
1242 ASSERT3U(rows
[ii
][missing
[i
]], !=, 0);
1244 log
= vdev_raidz_log2
[rows
[ii
][missing
[i
]]];
1246 for (j
= 0; j
< n
; j
++) {
1248 vdev_raidz_exp2(rows
[i
][j
], log
);
1250 vdev_raidz_exp2(invrows
[i
][j
], log
);
1256 * Verify that the data that is left in the rows are properly part of
1257 * an identity matrix.
1259 for (i
= 0; i
< nmissing
; i
++) {
1260 for (j
= 0; j
< n
; j
++) {
1261 if (j
== missing
[i
]) {
1262 ASSERT3U(rows
[i
][j
], ==, 1);
1264 ASSERT0(rows
[i
][j
]);
1271 vdev_raidz_matrix_reconstruct(raidz_map_t
*rm
, int n
, int nmissing
,
1272 int *missing
, uint8_t **invrows
, const uint8_t *used
)
1277 uint8_t *dst
[VDEV_RAIDZ_MAXPARITY
] = { NULL
};
1278 uint64_t dcount
[VDEV_RAIDZ_MAXPARITY
] = { 0 };
1282 uint8_t *invlog
[VDEV_RAIDZ_MAXPARITY
];
1286 psize
= sizeof (invlog
[0][0]) * n
* nmissing
;
1287 p
= kmem_alloc(psize
, KM_SLEEP
);
1289 for (pp
= p
, i
= 0; i
< nmissing
; i
++) {
1294 for (i
= 0; i
< nmissing
; i
++) {
1295 for (j
= 0; j
< n
; j
++) {
1296 ASSERT3U(invrows
[i
][j
], !=, 0);
1297 invlog
[i
][j
] = vdev_raidz_log2
[invrows
[i
][j
]];
1301 for (i
= 0; i
< n
; i
++) {
1303 ASSERT3U(c
, <, rm
->rm_cols
);
1305 src
= abd_to_buf(rm
->rm_col
[c
].rc_abd
);
1306 ccount
= rm
->rm_col
[c
].rc_size
;
1307 for (j
= 0; j
< nmissing
; j
++) {
1308 cc
= missing
[j
] + rm
->rm_firstdatacol
;
1309 ASSERT3U(cc
, >=, rm
->rm_firstdatacol
);
1310 ASSERT3U(cc
, <, rm
->rm_cols
);
1311 ASSERT3U(cc
, !=, c
);
1313 dst
[j
] = abd_to_buf(rm
->rm_col
[cc
].rc_abd
);
1314 dcount
[j
] = rm
->rm_col
[cc
].rc_size
;
1317 ASSERT(ccount
>= rm
->rm_col
[missing
[0]].rc_size
|| i
> 0);
1319 for (x
= 0; x
< ccount
; x
++, src
++) {
1321 log
= vdev_raidz_log2
[*src
];
1323 for (cc
= 0; cc
< nmissing
; cc
++) {
1324 if (x
>= dcount
[cc
])
1330 if ((ll
= log
+ invlog
[cc
][i
]) >= 255)
1332 val
= vdev_raidz_pow2
[ll
];
1343 kmem_free(p
, psize
);
1347 vdev_raidz_reconstruct_general(raidz_map_t
*rm
, int *tgts
, int ntgts
)
1351 int missing_rows
[VDEV_RAIDZ_MAXPARITY
];
1352 int parity_map
[VDEV_RAIDZ_MAXPARITY
];
1357 uint8_t *rows
[VDEV_RAIDZ_MAXPARITY
];
1358 uint8_t *invrows
[VDEV_RAIDZ_MAXPARITY
];
1361 abd_t
**bufs
= NULL
;
1366 * Matrix reconstruction can't use scatter ABDs yet, so we allocate
1367 * temporary linear ABDs.
1369 if (!abd_is_linear(rm
->rm_col
[rm
->rm_firstdatacol
].rc_abd
)) {
1370 bufs
= kmem_alloc(rm
->rm_cols
* sizeof (abd_t
*), KM_PUSHPAGE
);
1372 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1373 raidz_col_t
*col
= &rm
->rm_col
[c
];
1375 bufs
[c
] = col
->rc_abd
;
1376 col
->rc_abd
= abd_alloc_linear(col
->rc_size
, B_TRUE
);
1377 abd_copy(col
->rc_abd
, bufs
[c
], col
->rc_size
);
1381 n
= rm
->rm_cols
- rm
->rm_firstdatacol
;
1384 * Figure out which data columns are missing.
1387 for (t
= 0; t
< ntgts
; t
++) {
1388 if (tgts
[t
] >= rm
->rm_firstdatacol
) {
1389 missing_rows
[nmissing_rows
++] =
1390 tgts
[t
] - rm
->rm_firstdatacol
;
1395 * Figure out which parity columns to use to help generate the missing
1398 for (tt
= 0, c
= 0, i
= 0; i
< nmissing_rows
; c
++) {
1400 ASSERT(c
< rm
->rm_firstdatacol
);
1403 * Skip any targeted parity columns.
1405 if (c
== tgts
[tt
]) {
1417 ASSERT3U(code
, <, 1 << VDEV_RAIDZ_MAXPARITY
);
1419 psize
= (sizeof (rows
[0][0]) + sizeof (invrows
[0][0])) *
1420 nmissing_rows
* n
+ sizeof (used
[0]) * n
;
1421 p
= kmem_alloc(psize
, KM_SLEEP
);
1423 for (pp
= p
, i
= 0; i
< nmissing_rows
; i
++) {
1431 for (i
= 0; i
< nmissing_rows
; i
++) {
1432 used
[i
] = parity_map
[i
];
1435 for (tt
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1436 if (tt
< nmissing_rows
&&
1437 c
== missing_rows
[tt
] + rm
->rm_firstdatacol
) {
1448 * Initialize the interesting rows of the matrix.
1450 vdev_raidz_matrix_init(rm
, n
, nmissing_rows
, parity_map
, rows
);
1453 * Invert the matrix.
1455 vdev_raidz_matrix_invert(rm
, n
, nmissing_rows
, missing_rows
, rows
,
1459 * Reconstruct the missing data using the generated matrix.
1461 vdev_raidz_matrix_reconstruct(rm
, n
, nmissing_rows
, missing_rows
,
1464 kmem_free(p
, psize
);
1467 * copy back from temporary linear abds and free them
1470 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1471 raidz_col_t
*col
= &rm
->rm_col
[c
];
1473 abd_copy(bufs
[c
], col
->rc_abd
, col
->rc_size
);
1474 abd_free(col
->rc_abd
);
1475 col
->rc_abd
= bufs
[c
];
1477 kmem_free(bufs
, rm
->rm_cols
* sizeof (abd_t
*));
1484 vdev_raidz_reconstruct(raidz_map_t
*rm
, const int *t
, int nt
)
1486 int tgts
[VDEV_RAIDZ_MAXPARITY
], *dt
;
1490 int nbadparity
, nbaddata
;
1491 int parity_valid
[VDEV_RAIDZ_MAXPARITY
];
1494 * The tgts list must already be sorted.
1496 for (i
= 1; i
< nt
; i
++) {
1497 ASSERT(t
[i
] > t
[i
- 1]);
1500 nbadparity
= rm
->rm_firstdatacol
;
1501 nbaddata
= rm
->rm_cols
- nbadparity
;
1503 for (i
= 0, c
= 0; c
< rm
->rm_cols
; c
++) {
1504 if (c
< rm
->rm_firstdatacol
)
1505 parity_valid
[c
] = B_FALSE
;
1507 if (i
< nt
&& c
== t
[i
]) {
1510 } else if (rm
->rm_col
[c
].rc_error
!= 0) {
1512 } else if (c
>= rm
->rm_firstdatacol
) {
1515 parity_valid
[c
] = B_TRUE
;
1520 ASSERT(ntgts
>= nt
);
1521 ASSERT(nbaddata
>= 0);
1522 ASSERT(nbaddata
+ nbadparity
== ntgts
);
1524 dt
= &tgts
[nbadparity
];
1526 /* Reconstruct using the new math implementation */
1527 ret
= vdev_raidz_math_reconstruct(rm
, parity_valid
, dt
, nbaddata
);
1528 if (ret
!= RAIDZ_ORIGINAL_IMPL
)
1532 * See if we can use any of our optimized reconstruction routines.
1536 if (parity_valid
[VDEV_RAIDZ_P
])
1537 return (vdev_raidz_reconstruct_p(rm
, dt
, 1));
1539 ASSERT(rm
->rm_firstdatacol
> 1);
1541 if (parity_valid
[VDEV_RAIDZ_Q
])
1542 return (vdev_raidz_reconstruct_q(rm
, dt
, 1));
1544 ASSERT(rm
->rm_firstdatacol
> 2);
1548 ASSERT(rm
->rm_firstdatacol
> 1);
1550 if (parity_valid
[VDEV_RAIDZ_P
] &&
1551 parity_valid
[VDEV_RAIDZ_Q
])
1552 return (vdev_raidz_reconstruct_pq(rm
, dt
, 2));
1554 ASSERT(rm
->rm_firstdatacol
> 2);
1559 code
= vdev_raidz_reconstruct_general(rm
, tgts
, ntgts
);
1560 ASSERT(code
< (1 << VDEV_RAIDZ_MAXPARITY
));
1566 vdev_raidz_open(vdev_t
*vd
, uint64_t *asize
, uint64_t *max_asize
,
1570 uint64_t nparity
= vd
->vdev_nparity
;
1575 ASSERT(nparity
> 0);
1577 if (nparity
> VDEV_RAIDZ_MAXPARITY
||
1578 vd
->vdev_children
< nparity
+ 1) {
1579 vd
->vdev_stat
.vs_aux
= VDEV_AUX_BAD_LABEL
;
1580 return (SET_ERROR(EINVAL
));
1583 vdev_open_children(vd
);
1585 for (c
= 0; c
< vd
->vdev_children
; c
++) {
1586 cvd
= vd
->vdev_child
[c
];
1588 if (cvd
->vdev_open_error
!= 0) {
1589 lasterror
= cvd
->vdev_open_error
;
1594 *asize
= MIN(*asize
- 1, cvd
->vdev_asize
- 1) + 1;
1595 *max_asize
= MIN(*max_asize
- 1, cvd
->vdev_max_asize
- 1) + 1;
1596 *ashift
= MAX(*ashift
, cvd
->vdev_ashift
);
1599 *asize
*= vd
->vdev_children
;
1600 *max_asize
*= vd
->vdev_children
;
1602 if (numerrors
> nparity
) {
1603 vd
->vdev_stat
.vs_aux
= VDEV_AUX_NO_REPLICAS
;
1611 vdev_raidz_close(vdev_t
*vd
)
1615 for (c
= 0; c
< vd
->vdev_children
; c
++)
1616 vdev_close(vd
->vdev_child
[c
]);
1620 vdev_raidz_asize(vdev_t
*vd
, uint64_t psize
)
1623 uint64_t ashift
= vd
->vdev_top
->vdev_ashift
;
1624 uint64_t cols
= vd
->vdev_children
;
1625 uint64_t nparity
= vd
->vdev_nparity
;
1627 asize
= ((psize
- 1) >> ashift
) + 1;
1628 asize
+= nparity
* ((asize
+ cols
- nparity
- 1) / (cols
- nparity
));
1629 asize
= roundup(asize
, nparity
+ 1) << ashift
;
1635 vdev_raidz_child_done(zio_t
*zio
)
1637 raidz_col_t
*rc
= zio
->io_private
;
1639 rc
->rc_error
= zio
->io_error
;
1645 * Start an IO operation on a RAIDZ VDev
1648 * - For write operations:
1649 * 1. Generate the parity data
1650 * 2. Create child zio write operations to each column's vdev, for both
1652 * 3. If the column skips any sectors for padding, create optional dummy
1653 * write zio children for those areas to improve aggregation continuity.
1654 * - For read operations:
1655 * 1. Create child zio read operations to each data column's vdev to read
1656 * the range of data required for zio.
1657 * 2. If this is a scrub or resilver operation, or if any of the data
1658 * vdevs have had errors, then create zio read operations to the parity
1659 * columns' VDevs as well.
1662 vdev_raidz_io_start(zio_t
*zio
)
1664 vdev_t
*vd
= zio
->io_vd
;
1665 vdev_t
*tvd
= vd
->vdev_top
;
1671 rm
= vdev_raidz_map_alloc(zio
, tvd
->vdev_ashift
, vd
->vdev_children
,
1674 ASSERT3U(rm
->rm_asize
, ==, vdev_psize_to_asize(vd
, zio
->io_size
));
1676 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
1677 vdev_raidz_generate_parity(rm
);
1679 for (c
= 0; c
< rm
->rm_cols
; c
++) {
1680 rc
= &rm
->rm_col
[c
];
1681 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1682 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1683 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1684 zio
->io_type
, zio
->io_priority
, 0,
1685 vdev_raidz_child_done
, rc
));
1689 * Generate optional I/Os for any skipped sectors to improve
1690 * aggregation contiguity.
1692 for (c
= rm
->rm_skipstart
, i
= 0; i
< rm
->rm_nskip
; c
++, i
++) {
1693 ASSERT(c
<= rm
->rm_scols
);
1694 if (c
== rm
->rm_scols
)
1696 rc
= &rm
->rm_col
[c
];
1697 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1698 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1699 rc
->rc_offset
+ rc
->rc_size
, NULL
,
1700 1 << tvd
->vdev_ashift
,
1701 zio
->io_type
, zio
->io_priority
,
1702 ZIO_FLAG_NODATA
| ZIO_FLAG_OPTIONAL
, NULL
, NULL
));
1709 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
1712 * Iterate over the columns in reverse order so that we hit the parity
1713 * last -- any errors along the way will force us to read the parity.
1715 for (c
= rm
->rm_cols
- 1; c
>= 0; c
--) {
1716 rc
= &rm
->rm_col
[c
];
1717 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1718 if (!vdev_readable(cvd
)) {
1719 if (c
>= rm
->rm_firstdatacol
)
1720 rm
->rm_missingdata
++;
1722 rm
->rm_missingparity
++;
1723 rc
->rc_error
= SET_ERROR(ENXIO
);
1724 rc
->rc_tried
= 1; /* don't even try */
1728 if (vdev_dtl_contains(cvd
, DTL_MISSING
, zio
->io_txg
, 1)) {
1729 if (c
>= rm
->rm_firstdatacol
)
1730 rm
->rm_missingdata
++;
1732 rm
->rm_missingparity
++;
1733 rc
->rc_error
= SET_ERROR(ESTALE
);
1737 if (c
>= rm
->rm_firstdatacol
|| rm
->rm_missingdata
> 0 ||
1738 (zio
->io_flags
& (ZIO_FLAG_SCRUB
| ZIO_FLAG_RESILVER
))) {
1739 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1740 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1741 zio
->io_type
, zio
->io_priority
, 0,
1742 vdev_raidz_child_done
, rc
));
1751 * Report a checksum error for a child of a RAID-Z device.
1754 raidz_checksum_error(zio_t
*zio
, raidz_col_t
*rc
, abd_t
*bad_data
)
1756 vdev_t
*vd
= zio
->io_vd
->vdev_child
[rc
->rc_devidx
];
1758 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
1759 zio_bad_cksum_t zbc
;
1760 raidz_map_t
*rm
= zio
->io_vsd
;
1762 mutex_enter(&vd
->vdev_stat_lock
);
1763 vd
->vdev_stat
.vs_checksum_errors
++;
1764 mutex_exit(&vd
->vdev_stat_lock
);
1766 zbc
.zbc_has_cksum
= 0;
1767 zbc
.zbc_injected
= rm
->rm_ecksuminjected
;
1769 zfs_ereport_post_checksum(zio
->io_spa
, vd
, zio
,
1770 rc
->rc_offset
, rc
->rc_size
, rc
->rc_abd
, bad_data
,
1776 * We keep track of whether or not there were any injected errors, so that
1777 * any ereports we generate can note it.
1780 raidz_checksum_verify(zio_t
*zio
)
1782 zio_bad_cksum_t zbc
;
1783 raidz_map_t
*rm
= zio
->io_vsd
;
1786 bzero(&zbc
, sizeof (zio_bad_cksum_t
));
1788 ret
= zio_checksum_error(zio
, &zbc
);
1789 if (ret
!= 0 && zbc
.zbc_injected
!= 0)
1790 rm
->rm_ecksuminjected
= 1;
1796 * Generate the parity from the data columns. If we tried and were able to
1797 * read the parity without error, verify that the generated parity matches the
1798 * data we read. If it doesn't, we fire off a checksum error. Return the
1799 * number such failures.
1802 raidz_parity_verify(zio_t
*zio
, raidz_map_t
*rm
)
1804 abd_t
*orig
[VDEV_RAIDZ_MAXPARITY
];
1808 blkptr_t
*bp
= zio
->io_bp
;
1809 enum zio_checksum checksum
= (bp
== NULL
? zio
->io_prop
.zp_checksum
:
1810 (BP_IS_GANG(bp
) ? ZIO_CHECKSUM_GANG_HEADER
: BP_GET_CHECKSUM(bp
)));
1812 if (checksum
== ZIO_CHECKSUM_NOPARITY
)
1815 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1816 rc
= &rm
->rm_col
[c
];
1817 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1820 orig
[c
] = abd_alloc_sametype(rc
->rc_abd
, rc
->rc_size
);
1821 abd_copy(orig
[c
], rc
->rc_abd
, rc
->rc_size
);
1824 vdev_raidz_generate_parity(rm
);
1826 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1827 rc
= &rm
->rm_col
[c
];
1828 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1830 if (abd_cmp(orig
[c
], rc
->rc_abd
) != 0) {
1831 raidz_checksum_error(zio
, rc
, orig
[c
]);
1832 rc
->rc_error
= SET_ERROR(ECKSUM
);
1842 vdev_raidz_worst_error(raidz_map_t
*rm
)
1846 for (c
= 0; c
< rm
->rm_cols
; c
++)
1847 error
= zio_worst_error(error
, rm
->rm_col
[c
].rc_error
);
1853 * Iterate over all combinations of bad data and attempt a reconstruction.
1854 * Note that the algorithm below is non-optimal because it doesn't take into
1855 * account how reconstruction is actually performed. For example, with
1856 * triple-parity RAID-Z the reconstruction procedure is the same if column 4
1857 * is targeted as invalid as if columns 1 and 4 are targeted since in both
1858 * cases we'd only use parity information in column 0.
1861 vdev_raidz_combrec(zio_t
*zio
, int total_errors
, int data_errors
)
1863 raidz_map_t
*rm
= zio
->io_vsd
;
1865 abd_t
*orig
[VDEV_RAIDZ_MAXPARITY
];
1866 int tstore
[VDEV_RAIDZ_MAXPARITY
+ 2];
1867 int *tgts
= &tstore
[1];
1868 int curr
, next
, i
, c
, n
;
1871 ASSERT(total_errors
< rm
->rm_firstdatacol
);
1874 * This simplifies one edge condition.
1878 for (n
= 1; n
<= rm
->rm_firstdatacol
- total_errors
; n
++) {
1880 * Initialize the targets array by finding the first n columns
1881 * that contain no error.
1883 * If there were no data errors, we need to ensure that we're
1884 * always explicitly attempting to reconstruct at least one
1885 * data column. To do this, we simply push the highest target
1886 * up into the data columns.
1888 for (c
= 0, i
= 0; i
< n
; i
++) {
1889 if (i
== n
- 1 && data_errors
== 0 &&
1890 c
< rm
->rm_firstdatacol
) {
1891 c
= rm
->rm_firstdatacol
;
1894 while (rm
->rm_col
[c
].rc_error
!= 0) {
1896 ASSERT3S(c
, <, rm
->rm_cols
);
1903 * Setting tgts[n] simplifies the other edge condition.
1905 tgts
[n
] = rm
->rm_cols
;
1908 * These buffers were allocated in previous iterations.
1910 for (i
= 0; i
< n
- 1; i
++) {
1911 ASSERT(orig
[i
] != NULL
);
1914 orig
[n
- 1] = abd_alloc_sametype(rm
->rm_col
[0].rc_abd
,
1915 rm
->rm_col
[0].rc_size
);
1925 * Save off the original data that we're going to
1926 * attempt to reconstruct.
1928 for (i
= 0; i
< n
; i
++) {
1929 ASSERT(orig
[i
] != NULL
);
1932 ASSERT3S(c
, <, rm
->rm_cols
);
1933 rc
= &rm
->rm_col
[c
];
1934 abd_copy(orig
[i
], rc
->rc_abd
, rc
->rc_size
);
1938 * Attempt a reconstruction and exit the outer loop on
1941 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
1942 if (raidz_checksum_verify(zio
) == 0) {
1944 for (i
= 0; i
< n
; i
++) {
1946 rc
= &rm
->rm_col
[c
];
1947 ASSERT(rc
->rc_error
== 0);
1949 raidz_checksum_error(zio
, rc
,
1951 rc
->rc_error
= SET_ERROR(ECKSUM
);
1959 * Restore the original data.
1961 for (i
= 0; i
< n
; i
++) {
1963 rc
= &rm
->rm_col
[c
];
1964 abd_copy(rc
->rc_abd
, orig
[i
], rc
->rc_size
);
1969 * Find the next valid column after the curr
1972 for (next
= tgts
[curr
] + 1;
1973 next
< rm
->rm_cols
&&
1974 rm
->rm_col
[next
].rc_error
!= 0; next
++)
1977 ASSERT(next
<= tgts
[curr
+ 1]);
1980 * If that spot is available, we're done here.
1982 if (next
!= tgts
[curr
+ 1])
1986 * Otherwise, find the next valid column after
1987 * the previous position.
1989 for (c
= tgts
[curr
- 1] + 1;
1990 rm
->rm_col
[c
].rc_error
!= 0; c
++)
1996 } while (curr
!= n
);
2001 for (i
= 0; i
< n
; i
++)
2008 * Complete an IO operation on a RAIDZ VDev
2011 * - For write operations:
2012 * 1. Check for errors on the child IOs.
2013 * 2. Return, setting an error code if too few child VDevs were written
2014 * to reconstruct the data later. Note that partial writes are
2015 * considered successful if they can be reconstructed at all.
2016 * - For read operations:
2017 * 1. Check for errors on the child IOs.
2018 * 2. If data errors occurred:
2019 * a. Try to reassemble the data from the parity available.
2020 * b. If we haven't yet read the parity drives, read them now.
2021 * c. If all parity drives have been read but the data still doesn't
2022 * reassemble with a correct checksum, then try combinatorial
2024 * d. If that doesn't work, return an error.
2025 * 3. If there were unexpected errors or this is a resilver operation,
2026 * rewrite the vdevs that had errors.
2029 vdev_raidz_io_done(zio_t
*zio
)
2031 vdev_t
*vd
= zio
->io_vd
;
2033 raidz_map_t
*rm
= zio
->io_vsd
;
2034 raidz_col_t
*rc
= NULL
;
2035 int unexpected_errors
= 0;
2036 int parity_errors
= 0;
2037 int parity_untried
= 0;
2038 int data_errors
= 0;
2039 int total_errors
= 0;
2041 int tgts
[VDEV_RAIDZ_MAXPARITY
];
2044 ASSERT(zio
->io_bp
!= NULL
); /* XXX need to add code to enforce this */
2046 ASSERT(rm
->rm_missingparity
<= rm
->rm_firstdatacol
);
2047 ASSERT(rm
->rm_missingdata
<= rm
->rm_cols
- rm
->rm_firstdatacol
);
2049 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2050 rc
= &rm
->rm_col
[c
];
2053 ASSERT(rc
->rc_error
!= ECKSUM
); /* child has no bp */
2055 if (c
< rm
->rm_firstdatacol
)
2060 if (!rc
->rc_skipped
)
2061 unexpected_errors
++;
2064 } else if (c
< rm
->rm_firstdatacol
&& !rc
->rc_tried
) {
2069 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
2071 * XXX -- for now, treat partial writes as a success.
2072 * (If we couldn't write enough columns to reconstruct
2073 * the data, the I/O failed. Otherwise, good enough.)
2075 * Now that we support write reallocation, it would be better
2076 * to treat partial failure as real failure unless there are
2077 * no non-degraded top-level vdevs left, and not update DTLs
2078 * if we intend to reallocate.
2081 if (total_errors
> rm
->rm_firstdatacol
)
2082 zio
->io_error
= vdev_raidz_worst_error(rm
);
2087 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
2089 * There are three potential phases for a read:
2090 * 1. produce valid data from the columns read
2091 * 2. read all disks and try again
2092 * 3. perform combinatorial reconstruction
2094 * Each phase is progressively both more expensive and less likely to
2095 * occur. If we encounter more errors than we can repair or all phases
2096 * fail, we have no choice but to return an error.
2100 * If the number of errors we saw was correctable -- less than or equal
2101 * to the number of parity disks read -- attempt to produce data that
2102 * has a valid checksum. Naturally, this case applies in the absence of
2105 if (total_errors
<= rm
->rm_firstdatacol
- parity_untried
) {
2106 if (data_errors
== 0) {
2107 if (raidz_checksum_verify(zio
) == 0) {
2109 * If we read parity information (unnecessarily
2110 * as it happens since no reconstruction was
2111 * needed) regenerate and verify the parity.
2112 * We also regenerate parity when resilvering
2113 * so we can write it out to the failed device
2116 if (parity_errors
+ parity_untried
<
2117 rm
->rm_firstdatacol
||
2118 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2119 n
= raidz_parity_verify(zio
, rm
);
2120 unexpected_errors
+= n
;
2121 ASSERT(parity_errors
+ n
<=
2122 rm
->rm_firstdatacol
);
2128 * We either attempt to read all the parity columns or
2129 * none of them. If we didn't try to read parity, we
2130 * wouldn't be here in the correctable case. There must
2131 * also have been fewer parity errors than parity
2132 * columns or, again, we wouldn't be in this code path.
2134 ASSERT(parity_untried
== 0);
2135 ASSERT(parity_errors
< rm
->rm_firstdatacol
);
2138 * Identify the data columns that reported an error.
2141 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
2142 rc
= &rm
->rm_col
[c
];
2143 if (rc
->rc_error
!= 0) {
2144 ASSERT(n
< VDEV_RAIDZ_MAXPARITY
);
2149 ASSERT(rm
->rm_firstdatacol
>= n
);
2151 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
2153 if (raidz_checksum_verify(zio
) == 0) {
2155 * If we read more parity disks than were used
2156 * for reconstruction, confirm that the other
2157 * parity disks produced correct data. This
2158 * routine is suboptimal in that it regenerates
2159 * the parity that we already used in addition
2160 * to the parity that we're attempting to
2161 * verify, but this should be a relatively
2162 * uncommon case, and can be optimized if it
2163 * becomes a problem. Note that we regenerate
2164 * parity when resilvering so we can write it
2165 * out to failed devices later.
2167 if (parity_errors
< rm
->rm_firstdatacol
- n
||
2168 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2169 n
= raidz_parity_verify(zio
, rm
);
2170 unexpected_errors
+= n
;
2171 ASSERT(parity_errors
+ n
<=
2172 rm
->rm_firstdatacol
);
2181 * This isn't a typical situation -- either we got a read error or
2182 * a child silently returned bad data. Read every block so we can
2183 * try again with as much data and parity as we can track down. If
2184 * we've already been through once before, all children will be marked
2185 * as tried so we'll proceed to combinatorial reconstruction.
2187 unexpected_errors
= 1;
2188 rm
->rm_missingdata
= 0;
2189 rm
->rm_missingparity
= 0;
2191 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2192 if (rm
->rm_col
[c
].rc_tried
)
2195 zio_vdev_io_redone(zio
);
2197 rc
= &rm
->rm_col
[c
];
2200 zio_nowait(zio_vdev_child_io(zio
, NULL
,
2201 vd
->vdev_child
[rc
->rc_devidx
],
2202 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2203 zio
->io_type
, zio
->io_priority
, 0,
2204 vdev_raidz_child_done
, rc
));
2205 } while (++c
< rm
->rm_cols
);
2211 * At this point we've attempted to reconstruct the data given the
2212 * errors we detected, and we've attempted to read all columns. There
2213 * must, therefore, be one or more additional problems -- silent errors
2214 * resulting in invalid data rather than explicit I/O errors resulting
2215 * in absent data. We check if there is enough additional data to
2216 * possibly reconstruct the data and then perform combinatorial
2217 * reconstruction over all possible combinations. If that fails,
2220 if (total_errors
> rm
->rm_firstdatacol
) {
2221 zio
->io_error
= vdev_raidz_worst_error(rm
);
2223 } else if (total_errors
< rm
->rm_firstdatacol
&&
2224 (code
= vdev_raidz_combrec(zio
, total_errors
, data_errors
)) != 0) {
2226 * If we didn't use all the available parity for the
2227 * combinatorial reconstruction, verify that the remaining
2228 * parity is correct.
2230 if (code
!= (1 << rm
->rm_firstdatacol
) - 1)
2231 (void) raidz_parity_verify(zio
, rm
);
2234 * We're here because either:
2236 * total_errors == rm_first_datacol, or
2237 * vdev_raidz_combrec() failed
2239 * In either case, there is enough bad data to prevent
2242 * Start checksum ereports for all children which haven't
2243 * failed, and the IO wasn't speculative.
2245 zio
->io_error
= SET_ERROR(ECKSUM
);
2247 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
2248 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2249 rc
= &rm
->rm_col
[c
];
2250 if (rc
->rc_error
== 0) {
2251 zio_bad_cksum_t zbc
;
2252 zbc
.zbc_has_cksum
= 0;
2254 rm
->rm_ecksuminjected
;
2256 zfs_ereport_start_checksum(
2258 vd
->vdev_child
[rc
->rc_devidx
],
2259 zio
, rc
->rc_offset
, rc
->rc_size
,
2260 (void *)(uintptr_t)c
, &zbc
);
2267 zio_checksum_verified(zio
);
2269 if (zio
->io_error
== 0 && spa_writeable(zio
->io_spa
) &&
2270 (unexpected_errors
|| (zio
->io_flags
& ZIO_FLAG_RESILVER
))) {
2272 * Use the good data we have in hand to repair damaged children.
2274 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2275 rc
= &rm
->rm_col
[c
];
2276 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
2278 if (rc
->rc_error
== 0)
2281 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
2282 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2283 ZIO_TYPE_WRITE
, ZIO_PRIORITY_ASYNC_WRITE
,
2284 ZIO_FLAG_IO_REPAIR
| (unexpected_errors
?
2285 ZIO_FLAG_SELF_HEAL
: 0), NULL
, NULL
));
2291 vdev_raidz_state_change(vdev_t
*vd
, int faulted
, int degraded
)
2293 if (faulted
> vd
->vdev_nparity
)
2294 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_CANT_OPEN
,
2295 VDEV_AUX_NO_REPLICAS
);
2296 else if (degraded
+ faulted
!= 0)
2297 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_DEGRADED
, VDEV_AUX_NONE
);
2299 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_HEALTHY
, VDEV_AUX_NONE
);
2303 * Determine if any portion of the provided block resides on a child vdev
2304 * with a dirty DTL and therefore needs to be resilvered. The function
2305 * assumes that at least one DTL is dirty which imples that full stripe
2306 * width blocks must be resilvered.
2309 vdev_raidz_need_resilver(vdev_t
*vd
, uint64_t offset
, size_t psize
)
2311 uint64_t dcols
= vd
->vdev_children
;
2312 uint64_t nparity
= vd
->vdev_nparity
;
2313 uint64_t ashift
= vd
->vdev_top
->vdev_ashift
;
2314 /* The starting RAIDZ (parent) vdev sector of the block. */
2315 uint64_t b
= offset
>> ashift
;
2316 /* The zio's size in units of the vdev's minimum sector size. */
2317 uint64_t s
= ((psize
- 1) >> ashift
) + 1;
2318 /* The first column for this stripe. */
2319 uint64_t f
= b
% dcols
;
2321 if (s
+ nparity
>= dcols
)
2324 for (uint64_t c
= 0; c
< s
+ nparity
; c
++) {
2325 uint64_t devidx
= (f
+ c
) % dcols
;
2326 vdev_t
*cvd
= vd
->vdev_child
[devidx
];
2329 * dsl_scan_need_resilver() already checked vd with
2330 * vdev_dtl_contains(). So here just check cvd with
2331 * vdev_dtl_empty(), cheaper and a good approximation.
2333 if (!vdev_dtl_empty(cvd
, DTL_PARTIAL
))
2340 vdev_ops_t vdev_raidz_ops
= {
2344 vdev_raidz_io_start
,
2346 vdev_raidz_state_change
,
2347 vdev_raidz_need_resilver
,
2350 VDEV_TYPE_RAIDZ
, /* name of this vdev type */
2351 B_FALSE
/* not a leaf vdev */