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, 2020 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 #include <sys/vdev.h> /* For vdev_xlate() in vdev_raidz_io_verify() */
44 * Virtual device vector for RAID-Z.
46 * This vdev supports single, double, and triple parity. For single parity,
47 * we use a simple XOR of all the data columns. For double or triple parity,
48 * we use a special case of Reed-Solomon coding. This extends the
49 * technique described in "The mathematics of RAID-6" by H. Peter Anvin by
50 * drawing on the system described in "A Tutorial on Reed-Solomon Coding for
51 * Fault-Tolerance in RAID-like Systems" by James S. Plank on which the
52 * former is also based. The latter is designed to provide higher performance
55 * Note that the Plank paper claimed to support arbitrary N+M, but was then
56 * amended six years later identifying a critical flaw that invalidates its
57 * claims. Nevertheless, the technique can be adapted to work for up to
58 * triple parity. For additional parity, the amendment "Note: Correction to
59 * the 1997 Tutorial on Reed-Solomon Coding" by James S. Plank and Ying Ding
60 * is viable, but the additional complexity means that write performance will
63 * All of the methods above operate on a Galois field, defined over the
64 * integers mod 2^N. In our case we choose N=8 for GF(8) so that all elements
65 * can be expressed with a single byte. Briefly, the operations on the
66 * field are defined as follows:
68 * o addition (+) is represented by a bitwise XOR
69 * o subtraction (-) is therefore identical to addition: A + B = A - B
70 * o multiplication of A by 2 is defined by the following bitwise expression:
75 * (A * 2)_4 = A_3 + A_7
76 * (A * 2)_3 = A_2 + A_7
77 * (A * 2)_2 = A_1 + A_7
81 * In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).
82 * As an aside, this multiplication is derived from the error correcting
83 * primitive polynomial x^8 + x^4 + x^3 + x^2 + 1.
85 * Observe that any number in the field (except for 0) can be expressed as a
86 * power of 2 -- a generator for the field. We store a table of the powers of
87 * 2 and logs base 2 for quick look ups, and exploit the fact that A * B can
88 * be rewritten as 2^(log_2(A) + log_2(B)) (where '+' is normal addition rather
89 * than field addition). The inverse of a field element A (A^-1) is therefore
90 * A ^ (255 - 1) = A^254.
92 * The up-to-three parity columns, P, Q, R over several data columns,
93 * D_0, ... D_n-1, can be expressed by field operations:
95 * P = D_0 + D_1 + ... + D_n-2 + D_n-1
96 * Q = 2^n-1 * D_0 + 2^n-2 * D_1 + ... + 2^1 * D_n-2 + 2^0 * D_n-1
97 * = ((...((D_0) * 2 + D_1) * 2 + ...) * 2 + D_n-2) * 2 + D_n-1
98 * R = 4^n-1 * D_0 + 4^n-2 * D_1 + ... + 4^1 * D_n-2 + 4^0 * D_n-1
99 * = ((...((D_0) * 4 + D_1) * 4 + ...) * 4 + D_n-2) * 4 + D_n-1
101 * We chose 1, 2, and 4 as our generators because 1 corresponds to the trivial
102 * XOR operation, and 2 and 4 can be computed quickly and generate linearly-
103 * independent coefficients. (There are no additional coefficients that have
104 * this property which is why the uncorrected Plank method breaks down.)
106 * See the reconstruction code below for how P, Q and R can used individually
107 * or in concert to recover missing data columns.
110 #define VDEV_RAIDZ_P 0
111 #define VDEV_RAIDZ_Q 1
112 #define VDEV_RAIDZ_R 2
114 #define VDEV_RAIDZ_MUL_2(x) (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
115 #define VDEV_RAIDZ_MUL_4(x) (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
118 * We provide a mechanism to perform the field multiplication operation on a
119 * 64-bit value all at once rather than a byte at a time. This works by
120 * creating a mask from the top bit in each byte and using that to
121 * conditionally apply the XOR of 0x1d.
123 #define VDEV_RAIDZ_64MUL_2(x, mask) \
125 (mask) = (x) & 0x8080808080808080ULL; \
126 (mask) = ((mask) << 1) - ((mask) >> 7); \
127 (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
128 ((mask) & 0x1d1d1d1d1d1d1d1dULL); \
131 #define VDEV_RAIDZ_64MUL_4(x, mask) \
133 VDEV_RAIDZ_64MUL_2((x), mask); \
134 VDEV_RAIDZ_64MUL_2((x), mask); \
138 vdev_raidz_map_free(raidz_map_t
*rm
)
142 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
143 abd_free(rm
->rm_col
[c
].rc_abd
);
145 if (rm
->rm_col
[c
].rc_gdata
!= NULL
)
146 abd_free(rm
->rm_col
[c
].rc_gdata
);
149 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++)
150 abd_put(rm
->rm_col
[c
].rc_abd
);
152 if (rm
->rm_abd_copy
!= NULL
)
153 abd_free(rm
->rm_abd_copy
);
155 kmem_free(rm
, offsetof(raidz_map_t
, rm_col
[rm
->rm_scols
]));
159 vdev_raidz_map_free_vsd(zio_t
*zio
)
161 raidz_map_t
*rm
= zio
->io_vsd
;
163 ASSERT0(rm
->rm_freed
);
166 if (rm
->rm_reports
== 0)
167 vdev_raidz_map_free(rm
);
172 vdev_raidz_cksum_free(void *arg
, size_t ignored
)
174 raidz_map_t
*rm
= arg
;
176 ASSERT3U(rm
->rm_reports
, >, 0);
178 if (--rm
->rm_reports
== 0 && rm
->rm_freed
!= 0)
179 vdev_raidz_map_free(rm
);
183 vdev_raidz_cksum_finish(zio_cksum_report_t
*zcr
, const abd_t
*good_data
)
185 raidz_map_t
*rm
= zcr
->zcr_cbdata
;
186 const size_t c
= zcr
->zcr_cbinfo
;
189 const abd_t
*good
= NULL
;
190 const abd_t
*bad
= rm
->rm_col
[c
].rc_abd
;
192 if (good_data
== NULL
) {
193 zfs_ereport_finish_checksum(zcr
, NULL
, NULL
, B_FALSE
);
197 if (c
< rm
->rm_firstdatacol
) {
199 * The first time through, calculate the parity blocks for
200 * the good data (this relies on the fact that the good
201 * data never changes for a given logical ZIO)
203 if (rm
->rm_col
[0].rc_gdata
== NULL
) {
204 abd_t
*bad_parity
[VDEV_RAIDZ_MAXPARITY
];
207 * Set up the rm_col[]s to generate the parity for
208 * good_data, first saving the parity bufs and
209 * replacing them with buffers to hold the result.
211 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++) {
212 bad_parity
[x
] = rm
->rm_col
[x
].rc_abd
;
213 rm
->rm_col
[x
].rc_abd
=
214 rm
->rm_col
[x
].rc_gdata
=
215 abd_alloc_sametype(rm
->rm_col
[x
].rc_abd
,
216 rm
->rm_col
[x
].rc_size
);
219 /* fill in the data columns from good_data */
221 for (; x
< rm
->rm_cols
; x
++) {
222 abd_put(rm
->rm_col
[x
].rc_abd
);
224 rm
->rm_col
[x
].rc_abd
=
225 abd_get_offset_size((abd_t
*)good_data
,
226 offset
, rm
->rm_col
[x
].rc_size
);
227 offset
+= rm
->rm_col
[x
].rc_size
;
231 * Construct the parity from the good data.
233 vdev_raidz_generate_parity(rm
);
235 /* restore everything back to its original state */
236 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++)
237 rm
->rm_col
[x
].rc_abd
= bad_parity
[x
];
240 for (x
= rm
->rm_firstdatacol
; x
< rm
->rm_cols
; x
++) {
241 abd_put(rm
->rm_col
[x
].rc_abd
);
242 rm
->rm_col
[x
].rc_abd
= abd_get_offset_size(
243 rm
->rm_abd_copy
, offset
,
244 rm
->rm_col
[x
].rc_size
);
245 offset
+= rm
->rm_col
[x
].rc_size
;
249 ASSERT3P(rm
->rm_col
[c
].rc_gdata
, !=, NULL
);
250 good
= abd_get_offset_size(rm
->rm_col
[c
].rc_gdata
, 0,
251 rm
->rm_col
[c
].rc_size
);
253 /* adjust good_data to point at the start of our column */
255 for (x
= rm
->rm_firstdatacol
; x
< c
; x
++)
256 offset
+= rm
->rm_col
[x
].rc_size
;
258 good
= abd_get_offset_size((abd_t
*)good_data
, offset
,
259 rm
->rm_col
[c
].rc_size
);
262 /* we drop the ereport if it ends up that the data was good */
263 zfs_ereport_finish_checksum(zcr
, good
, bad
, B_TRUE
);
264 abd_put((abd_t
*)good
);
268 * Invoked indirectly by zfs_ereport_start_checksum(), called
269 * below when our read operation fails completely. The main point
270 * is to keep a copy of everything we read from disk, so that at
271 * vdev_raidz_cksum_finish() time we can compare it with the good data.
274 vdev_raidz_cksum_report(zio_t
*zio
, zio_cksum_report_t
*zcr
, void *arg
)
276 size_t c
= (size_t)(uintptr_t)arg
;
279 raidz_map_t
*rm
= zio
->io_vsd
;
282 /* set up the report and bump the refcount */
283 zcr
->zcr_cbdata
= rm
;
285 zcr
->zcr_finish
= vdev_raidz_cksum_finish
;
286 zcr
->zcr_free
= vdev_raidz_cksum_free
;
289 ASSERT3U(rm
->rm_reports
, >, 0);
291 if (rm
->rm_abd_copy
!= NULL
)
295 * It's the first time we're called for this raidz_map_t, so we need
296 * to copy the data aside; there's no guarantee that our zio's buffer
297 * won't be re-used for something else.
299 * Our parity data is already in separate buffers, so there's no need
304 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++)
305 size
+= rm
->rm_col
[c
].rc_size
;
307 rm
->rm_abd_copy
= abd_alloc_for_io(size
, B_FALSE
);
309 for (offset
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
310 raidz_col_t
*col
= &rm
->rm_col
[c
];
311 abd_t
*tmp
= abd_get_offset_size(rm
->rm_abd_copy
, offset
,
314 abd_copy(tmp
, col
->rc_abd
, col
->rc_size
);
316 abd_put(col
->rc_abd
);
319 offset
+= col
->rc_size
;
321 ASSERT3U(offset
, ==, size
);
324 static const zio_vsd_ops_t vdev_raidz_vsd_ops
= {
325 .vsd_free
= vdev_raidz_map_free_vsd
,
326 .vsd_cksum_report
= vdev_raidz_cksum_report
330 * Divides the IO evenly across all child vdevs; usually, dcols is
331 * the number of children in the target vdev.
333 * Avoid inlining the function to keep vdev_raidz_io_start(), which
334 * is this functions only caller, as small as possible on the stack.
336 noinline raidz_map_t
*
337 vdev_raidz_map_alloc(zio_t
*zio
, uint64_t ashift
, uint64_t dcols
,
341 /* The starting RAIDZ (parent) vdev sector of the block. */
342 uint64_t b
= zio
->io_offset
>> ashift
;
343 /* The zio's size in units of the vdev's minimum sector size. */
344 uint64_t s
= zio
->io_size
>> ashift
;
345 /* The first column for this stripe. */
346 uint64_t f
= b
% dcols
;
347 /* The starting byte offset on each child vdev. */
348 uint64_t o
= (b
/ dcols
) << ashift
;
349 uint64_t q
, r
, c
, bc
, col
, acols
, scols
, coff
, devidx
, asize
, tot
;
353 * "Quotient": The number of data sectors for this stripe on all but
354 * the "big column" child vdevs that also contain "remainder" data.
356 q
= s
/ (dcols
- nparity
);
359 * "Remainder": The number of partial stripe data sectors in this I/O.
360 * This will add a sector to some, but not all, child vdevs.
362 r
= s
- q
* (dcols
- nparity
);
364 /* The number of "big columns" - those which contain remainder data. */
365 bc
= (r
== 0 ? 0 : r
+ nparity
);
368 * The total number of data and parity sectors associated with
371 tot
= s
+ nparity
* (q
+ (r
== 0 ? 0 : 1));
373 /* acols: The columns that will be accessed. */
374 /* scols: The columns that will be accessed or skipped. */
376 /* Our I/O request doesn't span all child vdevs. */
378 scols
= MIN(dcols
, roundup(bc
, nparity
+ 1));
384 ASSERT3U(acols
, <=, scols
);
386 rm
= kmem_alloc(offsetof(raidz_map_t
, rm_col
[scols
]), KM_SLEEP
);
389 rm
->rm_scols
= scols
;
391 rm
->rm_skipstart
= bc
;
392 rm
->rm_missingdata
= 0;
393 rm
->rm_missingparity
= 0;
394 rm
->rm_firstdatacol
= nparity
;
395 rm
->rm_abd_copy
= NULL
;
398 rm
->rm_ecksuminjected
= 0;
402 for (c
= 0; c
< scols
; c
++) {
407 coff
+= 1ULL << ashift
;
409 rm
->rm_col
[c
].rc_devidx
= col
;
410 rm
->rm_col
[c
].rc_offset
= coff
;
411 rm
->rm_col
[c
].rc_abd
= NULL
;
412 rm
->rm_col
[c
].rc_gdata
= NULL
;
413 rm
->rm_col
[c
].rc_error
= 0;
414 rm
->rm_col
[c
].rc_tried
= 0;
415 rm
->rm_col
[c
].rc_skipped
= 0;
418 rm
->rm_col
[c
].rc_size
= 0;
420 rm
->rm_col
[c
].rc_size
= (q
+ 1) << ashift
;
422 rm
->rm_col
[c
].rc_size
= q
<< ashift
;
424 asize
+= rm
->rm_col
[c
].rc_size
;
427 ASSERT3U(asize
, ==, tot
<< ashift
);
428 rm
->rm_asize
= roundup(asize
, (nparity
+ 1) << ashift
);
429 rm
->rm_nskip
= roundup(tot
, nparity
+ 1) - tot
;
430 ASSERT3U(rm
->rm_asize
- asize
, ==, rm
->rm_nskip
<< ashift
);
431 ASSERT3U(rm
->rm_nskip
, <=, nparity
);
433 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++)
434 rm
->rm_col
[c
].rc_abd
=
435 abd_alloc_linear(rm
->rm_col
[c
].rc_size
, B_FALSE
);
437 rm
->rm_col
[c
].rc_abd
= abd_get_offset_size(zio
->io_abd
, 0,
438 rm
->rm_col
[c
].rc_size
);
439 off
= rm
->rm_col
[c
].rc_size
;
441 for (c
= c
+ 1; c
< acols
; c
++) {
442 rm
->rm_col
[c
].rc_abd
= abd_get_offset_size(zio
->io_abd
, off
,
443 rm
->rm_col
[c
].rc_size
);
444 off
+= rm
->rm_col
[c
].rc_size
;
448 * If all data stored spans all columns, there's a danger that parity
449 * will always be on the same device and, since parity isn't read
450 * during normal operation, that device's I/O bandwidth won't be
451 * used effectively. We therefore switch the parity every 1MB.
453 * ... at least that was, ostensibly, the theory. As a practical
454 * matter unless we juggle the parity between all devices evenly, we
455 * won't see any benefit. Further, occasional writes that aren't a
456 * multiple of the LCM of the number of children and the minimum
457 * stripe width are sufficient to avoid pessimal behavior.
458 * Unfortunately, this decision created an implicit on-disk format
459 * requirement that we need to support for all eternity, but only
460 * for single-parity RAID-Z.
462 * If we intend to skip a sector in the zeroth column for padding
463 * we must make sure to note this swap. We will never intend to
464 * skip the first column since at least one data and one parity
465 * column must appear in each row.
467 ASSERT(rm
->rm_cols
>= 2);
468 ASSERT(rm
->rm_col
[0].rc_size
== rm
->rm_col
[1].rc_size
);
470 if (rm
->rm_firstdatacol
== 1 && (zio
->io_offset
& (1ULL << 20))) {
471 devidx
= rm
->rm_col
[0].rc_devidx
;
472 o
= rm
->rm_col
[0].rc_offset
;
473 rm
->rm_col
[0].rc_devidx
= rm
->rm_col
[1].rc_devidx
;
474 rm
->rm_col
[0].rc_offset
= rm
->rm_col
[1].rc_offset
;
475 rm
->rm_col
[1].rc_devidx
= devidx
;
476 rm
->rm_col
[1].rc_offset
= o
;
478 if (rm
->rm_skipstart
== 0)
479 rm
->rm_skipstart
= 1;
483 zio
->io_vsd_ops
= &vdev_raidz_vsd_ops
;
485 /* init RAIDZ parity ops */
486 rm
->rm_ops
= vdev_raidz_math_get_ops();
498 vdev_raidz_p_func(void *buf
, size_t size
, void *private)
500 struct pqr_struct
*pqr
= private;
501 const uint64_t *src
= buf
;
502 int i
, cnt
= size
/ sizeof (src
[0]);
504 ASSERT(pqr
->p
&& !pqr
->q
&& !pqr
->r
);
506 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++)
513 vdev_raidz_pq_func(void *buf
, size_t size
, void *private)
515 struct pqr_struct
*pqr
= private;
516 const uint64_t *src
= buf
;
518 int i
, cnt
= size
/ sizeof (src
[0]);
520 ASSERT(pqr
->p
&& pqr
->q
&& !pqr
->r
);
522 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++) {
524 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
532 vdev_raidz_pqr_func(void *buf
, size_t size
, void *private)
534 struct pqr_struct
*pqr
= private;
535 const uint64_t *src
= buf
;
537 int i
, cnt
= size
/ sizeof (src
[0]);
539 ASSERT(pqr
->p
&& pqr
->q
&& pqr
->r
);
541 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++, pqr
->r
++) {
543 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
545 VDEV_RAIDZ_64MUL_4(*pqr
->r
, mask
);
553 vdev_raidz_generate_parity_p(raidz_map_t
*rm
)
559 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
560 src
= rm
->rm_col
[c
].rc_abd
;
561 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
563 if (c
== rm
->rm_firstdatacol
) {
564 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
566 struct pqr_struct pqr
= { p
, NULL
, NULL
};
567 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
568 vdev_raidz_p_func
, &pqr
);
574 vdev_raidz_generate_parity_pq(raidz_map_t
*rm
)
576 uint64_t *p
, *q
, pcnt
, ccnt
, mask
, i
;
580 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
581 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
582 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
584 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
585 src
= rm
->rm_col
[c
].rc_abd
;
586 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
587 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
589 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
591 if (c
== rm
->rm_firstdatacol
) {
592 ASSERT(ccnt
== pcnt
|| ccnt
== 0);
593 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
594 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
596 for (i
= ccnt
; i
< pcnt
; i
++) {
601 struct pqr_struct pqr
= { p
, q
, NULL
};
603 ASSERT(ccnt
<= pcnt
);
604 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
605 vdev_raidz_pq_func
, &pqr
);
608 * Treat short columns as though they are full of 0s.
609 * Note that there's therefore nothing needed for P.
611 for (i
= ccnt
; i
< pcnt
; i
++) {
612 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
619 vdev_raidz_generate_parity_pqr(raidz_map_t
*rm
)
621 uint64_t *p
, *q
, *r
, pcnt
, ccnt
, mask
, i
;
625 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
626 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
627 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
628 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
629 rm
->rm_col
[VDEV_RAIDZ_R
].rc_size
);
631 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
632 src
= rm
->rm_col
[c
].rc_abd
;
633 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
634 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
635 r
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_R
].rc_abd
);
637 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
639 if (c
== rm
->rm_firstdatacol
) {
640 ASSERT(ccnt
== pcnt
|| ccnt
== 0);
641 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
642 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
643 (void) memcpy(r
, p
, rm
->rm_col
[c
].rc_size
);
645 for (i
= ccnt
; i
< pcnt
; i
++) {
651 struct pqr_struct pqr
= { p
, q
, r
};
653 ASSERT(ccnt
<= pcnt
);
654 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
655 vdev_raidz_pqr_func
, &pqr
);
658 * Treat short columns as though they are full of 0s.
659 * Note that there's therefore nothing needed for P.
661 for (i
= ccnt
; i
< pcnt
; i
++) {
662 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
663 VDEV_RAIDZ_64MUL_4(r
[i
], mask
);
670 * Generate RAID parity in the first virtual columns according to the number of
671 * parity columns available.
674 vdev_raidz_generate_parity(raidz_map_t
*rm
)
676 /* Generate using the new math implementation */
677 if (vdev_raidz_math_generate(rm
) != RAIDZ_ORIGINAL_IMPL
)
680 switch (rm
->rm_firstdatacol
) {
682 vdev_raidz_generate_parity_p(rm
);
685 vdev_raidz_generate_parity_pq(rm
);
688 vdev_raidz_generate_parity_pqr(rm
);
691 cmn_err(CE_PANIC
, "invalid RAID-Z configuration");
697 vdev_raidz_reconst_p_func(void *dbuf
, void *sbuf
, size_t size
, void *private)
699 uint64_t *dst
= dbuf
;
700 uint64_t *src
= sbuf
;
701 int cnt
= size
/ sizeof (src
[0]);
703 for (int i
= 0; i
< cnt
; i
++) {
712 vdev_raidz_reconst_q_pre_func(void *dbuf
, void *sbuf
, size_t size
,
715 uint64_t *dst
= dbuf
;
716 uint64_t *src
= sbuf
;
718 int cnt
= size
/ sizeof (dst
[0]);
720 for (int i
= 0; i
< cnt
; i
++, dst
++, src
++) {
721 VDEV_RAIDZ_64MUL_2(*dst
, mask
);
730 vdev_raidz_reconst_q_pre_tail_func(void *buf
, size_t size
, void *private)
734 int cnt
= size
/ sizeof (dst
[0]);
736 for (int i
= 0; i
< cnt
; i
++, dst
++) {
737 /* same operation as vdev_raidz_reconst_q_pre_func() on dst */
738 VDEV_RAIDZ_64MUL_2(*dst
, mask
);
744 struct reconst_q_struct
{
750 vdev_raidz_reconst_q_post_func(void *buf
, size_t size
, void *private)
752 struct reconst_q_struct
*rq
= private;
754 int cnt
= size
/ sizeof (dst
[0]);
756 for (int 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;
785 for (int i
= 0; i
< size
;
786 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++, yd
++) {
787 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
788 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
789 *yd
= *rpq
->p
^ *rpq
->pxy
^ *xd
;
796 vdev_raidz_reconst_pq_tail_func(void *xbuf
, size_t size
, void *private)
798 struct reconst_pq_struct
*rpq
= private;
801 for (int i
= 0; i
< size
;
802 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++) {
803 /* same operation as vdev_raidz_reconst_pq_func() on xd */
804 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
805 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
812 vdev_raidz_reconstruct_p(raidz_map_t
*rm
, int *tgts
, int ntgts
)
819 ASSERT(x
>= rm
->rm_firstdatacol
);
820 ASSERT(x
< rm
->rm_cols
);
822 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
);
823 ASSERT(rm
->rm_col
[x
].rc_size
> 0);
825 src
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
826 dst
= rm
->rm_col
[x
].rc_abd
;
828 abd_copy_from_buf(dst
, abd_to_buf(src
), rm
->rm_col
[x
].rc_size
);
830 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
831 uint64_t size
= MIN(rm
->rm_col
[x
].rc_size
,
832 rm
->rm_col
[c
].rc_size
);
834 src
= rm
->rm_col
[c
].rc_abd
;
835 dst
= rm
->rm_col
[x
].rc_abd
;
840 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
841 vdev_raidz_reconst_p_func
, NULL
);
844 return (1 << VDEV_RAIDZ_P
);
848 vdev_raidz_reconstruct_q(raidz_map_t
*rm
, int *tgts
, int ntgts
)
856 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
858 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
859 uint64_t size
= (c
== x
) ? 0 : MIN(rm
->rm_col
[x
].rc_size
,
860 rm
->rm_col
[c
].rc_size
);
862 src
= rm
->rm_col
[c
].rc_abd
;
863 dst
= rm
->rm_col
[x
].rc_abd
;
865 if (c
== rm
->rm_firstdatacol
) {
866 abd_copy(dst
, src
, size
);
867 if (rm
->rm_col
[x
].rc_size
> size
)
868 abd_zero_off(dst
, size
,
869 rm
->rm_col
[x
].rc_size
- size
);
872 ASSERT3U(size
, <=, rm
->rm_col
[x
].rc_size
);
873 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
874 vdev_raidz_reconst_q_pre_func
, NULL
);
875 (void) abd_iterate_func(dst
,
876 size
, rm
->rm_col
[x
].rc_size
- size
,
877 vdev_raidz_reconst_q_pre_tail_func
, NULL
);
881 src
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
882 dst
= rm
->rm_col
[x
].rc_abd
;
883 exp
= 255 - (rm
->rm_cols
- 1 - x
);
885 struct reconst_q_struct rq
= { abd_to_buf(src
), exp
};
886 (void) abd_iterate_func(dst
, 0, rm
->rm_col
[x
].rc_size
,
887 vdev_raidz_reconst_q_post_func
, &rq
);
889 return (1 << VDEV_RAIDZ_Q
);
893 vdev_raidz_reconstruct_pq(raidz_map_t
*rm
, int *tgts
, int ntgts
)
895 uint8_t *p
, *q
, *pxy
, *qxy
, tmp
, a
, b
, aexp
, bexp
;
896 abd_t
*pdata
, *qdata
;
897 uint64_t xsize
, ysize
;
904 ASSERT(x
>= rm
->rm_firstdatacol
);
905 ASSERT(y
< rm
->rm_cols
);
907 ASSERT(rm
->rm_col
[x
].rc_size
>= rm
->rm_col
[y
].rc_size
);
910 * Move the parity data aside -- we're going to compute parity as
911 * though columns x and y were full of zeros -- Pxy and Qxy. We want to
912 * reuse the parity generation mechanism without trashing the actual
913 * parity so we make those columns appear to be full of zeros by
914 * setting their lengths to zero.
916 pdata
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
917 qdata
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
918 xsize
= rm
->rm_col
[x
].rc_size
;
919 ysize
= rm
->rm_col
[y
].rc_size
;
921 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
=
922 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
, B_TRUE
);
923 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
=
924 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
, B_TRUE
);
925 rm
->rm_col
[x
].rc_size
= 0;
926 rm
->rm_col
[y
].rc_size
= 0;
928 vdev_raidz_generate_parity_pq(rm
);
930 rm
->rm_col
[x
].rc_size
= xsize
;
931 rm
->rm_col
[y
].rc_size
= ysize
;
933 p
= abd_to_buf(pdata
);
934 q
= abd_to_buf(qdata
);
935 pxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
936 qxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
937 xd
= rm
->rm_col
[x
].rc_abd
;
938 yd
= rm
->rm_col
[y
].rc_abd
;
942 * Pxy = P + D_x + D_y
943 * Qxy = Q + 2^(ndevs - 1 - x) * D_x + 2^(ndevs - 1 - y) * D_y
945 * We can then solve for D_x:
946 * D_x = A * (P + Pxy) + B * (Q + Qxy)
948 * A = 2^(x - y) * (2^(x - y) + 1)^-1
949 * B = 2^(ndevs - 1 - x) * (2^(x - y) + 1)^-1
951 * With D_x in hand, we can easily solve for D_y:
952 * D_y = P + Pxy + D_x
955 a
= vdev_raidz_pow2
[255 + x
- y
];
956 b
= vdev_raidz_pow2
[255 - (rm
->rm_cols
- 1 - x
)];
957 tmp
= 255 - vdev_raidz_log2
[a
^ 1];
959 aexp
= vdev_raidz_log2
[vdev_raidz_exp2(a
, tmp
)];
960 bexp
= vdev_raidz_log2
[vdev_raidz_exp2(b
, tmp
)];
962 ASSERT3U(xsize
, >=, ysize
);
963 struct reconst_pq_struct rpq
= { p
, q
, pxy
, qxy
, aexp
, bexp
};
965 (void) abd_iterate_func2(xd
, yd
, 0, 0, ysize
,
966 vdev_raidz_reconst_pq_func
, &rpq
);
967 (void) abd_iterate_func(xd
, ysize
, xsize
- ysize
,
968 vdev_raidz_reconst_pq_tail_func
, &rpq
);
970 abd_free(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
971 abd_free(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
974 * Restore the saved parity data.
976 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
= pdata
;
977 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
= qdata
;
979 return ((1 << VDEV_RAIDZ_P
) | (1 << VDEV_RAIDZ_Q
));
984 * In the general case of reconstruction, we must solve the system of linear
985 * equations defined by the coefficients used to generate parity as well as
986 * the contents of the data and parity disks. This can be expressed with
987 * vectors for the original data (D) and the actual data (d) and parity (p)
988 * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
992 * | V | | D_0 | | p_m-1 |
993 * | | x | : | = | d_0 |
994 * | I | | D_n-1 | | : |
995 * | | ~~ ~~ | d_n-1 |
998 * I is simply a square identity matrix of size n, and V is a vandermonde
999 * matrix defined by the coefficients we chose for the various parity columns
1000 * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
1001 * computation as well as linear separability.
1004 * | 1 .. 1 1 1 | | p_0 |
1005 * | 2^n-1 .. 4 2 1 | __ __ | : |
1006 * | 4^n-1 .. 16 4 1 | | D_0 | | p_m-1 |
1007 * | 1 .. 0 0 0 | | D_1 | | d_0 |
1008 * | 0 .. 0 0 0 | x | D_2 | = | d_1 |
1009 * | : : : : | | : | | d_2 |
1010 * | 0 .. 1 0 0 | | D_n-1 | | : |
1011 * | 0 .. 0 1 0 | ~~ ~~ | : |
1012 * | 0 .. 0 0 1 | | d_n-1 |
1015 * Note that I, V, d, and p are known. To compute D, we must invert the
1016 * matrix and use the known data and parity values to reconstruct the unknown
1017 * data values. We begin by removing the rows in V|I and d|p that correspond
1018 * to failed or missing columns; we then make V|I square (n x n) and d|p
1019 * sized n by removing rows corresponding to unused parity from the bottom up
1020 * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
1021 * using Gauss-Jordan elimination. In the example below we use m=3 parity
1022 * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
1024 * | 1 1 1 1 1 1 1 1 |
1025 * | 128 64 32 16 8 4 2 1 | <-----+-+-- missing disks
1026 * | 19 205 116 29 64 16 4 1 | / /
1027 * | 1 0 0 0 0 0 0 0 | / /
1028 * | 0 1 0 0 0 0 0 0 | <--' /
1029 * (V|I) = | 0 0 1 0 0 0 0 0 | <---'
1030 * | 0 0 0 1 0 0 0 0 |
1031 * | 0 0 0 0 1 0 0 0 |
1032 * | 0 0 0 0 0 1 0 0 |
1033 * | 0 0 0 0 0 0 1 0 |
1034 * | 0 0 0 0 0 0 0 1 |
1037 * | 1 1 1 1 1 1 1 1 |
1038 * | 128 64 32 16 8 4 2 1 |
1039 * | 19 205 116 29 64 16 4 1 |
1040 * | 1 0 0 0 0 0 0 0 |
1041 * | 0 1 0 0 0 0 0 0 |
1042 * (V|I)' = | 0 0 1 0 0 0 0 0 |
1043 * | 0 0 0 1 0 0 0 0 |
1044 * | 0 0 0 0 1 0 0 0 |
1045 * | 0 0 0 0 0 1 0 0 |
1046 * | 0 0 0 0 0 0 1 0 |
1047 * | 0 0 0 0 0 0 0 1 |
1050 * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
1051 * have carefully chosen the seed values 1, 2, and 4 to ensure that this
1052 * matrix is not singular.
1054 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1055 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1056 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1057 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1058 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1059 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1060 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1061 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1064 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1065 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1066 * | 19 205 116 29 64 16 4 1 0 1 0 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 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1076 * | 0 205 116 0 0 0 0 0 0 1 19 29 64 16 4 1 |
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 0 185 0 0 0 0 0 205 1 222 208 141 221 201 204 |
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 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
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 0 0 0 0 0 0 167 100 5 41 159 169 217 208 |
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 * | 0 0 1 0 0 0 0 0 |
1115 * | 167 100 5 41 159 169 217 208 |
1116 * | 166 100 4 40 158 168 216 209 |
1117 * (V|I)'^-1 = | 0 0 0 1 0 0 0 0 |
1118 * | 0 0 0 0 1 0 0 0 |
1119 * | 0 0 0 0 0 1 0 0 |
1120 * | 0 0 0 0 0 0 1 0 |
1121 * | 0 0 0 0 0 0 0 1 |
1124 * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values
1125 * of the missing data.
1127 * As is apparent from the example above, the only non-trivial rows in the
1128 * inverse matrix correspond to the data disks that we're trying to
1129 * reconstruct. Indeed, those are the only rows we need as the others would
1130 * only be useful for reconstructing data known or assumed to be valid. For
1131 * that reason, we only build the coefficients in the rows that correspond to
1137 vdev_raidz_matrix_init(raidz_map_t
*rm
, int n
, int nmap
, int *map
,
1143 ASSERT(n
== rm
->rm_cols
- rm
->rm_firstdatacol
);
1146 * Fill in the missing rows of interest.
1148 for (i
= 0; i
< nmap
; i
++) {
1149 ASSERT3S(0, <=, map
[i
]);
1150 ASSERT3S(map
[i
], <=, 2);
1157 for (j
= 0; j
< n
; j
++) {
1161 rows
[i
][j
] = vdev_raidz_pow2
[pow
];
1167 vdev_raidz_matrix_invert(raidz_map_t
*rm
, int n
, int nmissing
, int *missing
,
1168 uint8_t **rows
, uint8_t **invrows
, const uint8_t *used
)
1174 * Assert that the first nmissing entries from the array of used
1175 * columns correspond to parity columns and that subsequent entries
1176 * correspond to data columns.
1178 for (i
= 0; i
< nmissing
; i
++) {
1179 ASSERT3S(used
[i
], <, rm
->rm_firstdatacol
);
1181 for (; i
< n
; i
++) {
1182 ASSERT3S(used
[i
], >=, rm
->rm_firstdatacol
);
1186 * First initialize the storage where we'll compute the inverse rows.
1188 for (i
= 0; i
< nmissing
; i
++) {
1189 for (j
= 0; j
< n
; j
++) {
1190 invrows
[i
][j
] = (i
== j
) ? 1 : 0;
1195 * Subtract all trivial rows from the rows of consequence.
1197 for (i
= 0; i
< nmissing
; i
++) {
1198 for (j
= nmissing
; j
< n
; j
++) {
1199 ASSERT3U(used
[j
], >=, rm
->rm_firstdatacol
);
1200 jj
= used
[j
] - rm
->rm_firstdatacol
;
1202 invrows
[i
][j
] = rows
[i
][jj
];
1208 * For each of the rows of interest, we must normalize it and subtract
1209 * a multiple of it from the other rows.
1211 for (i
= 0; i
< nmissing
; i
++) {
1212 for (j
= 0; j
< missing
[i
]; j
++) {
1213 ASSERT0(rows
[i
][j
]);
1215 ASSERT3U(rows
[i
][missing
[i
]], !=, 0);
1218 * Compute the inverse of the first element and multiply each
1219 * element in the row by that value.
1221 log
= 255 - vdev_raidz_log2
[rows
[i
][missing
[i
]]];
1223 for (j
= 0; j
< n
; j
++) {
1224 rows
[i
][j
] = vdev_raidz_exp2(rows
[i
][j
], log
);
1225 invrows
[i
][j
] = vdev_raidz_exp2(invrows
[i
][j
], log
);
1228 for (ii
= 0; ii
< nmissing
; ii
++) {
1232 ASSERT3U(rows
[ii
][missing
[i
]], !=, 0);
1234 log
= vdev_raidz_log2
[rows
[ii
][missing
[i
]]];
1236 for (j
= 0; j
< n
; j
++) {
1238 vdev_raidz_exp2(rows
[i
][j
], log
);
1240 vdev_raidz_exp2(invrows
[i
][j
], log
);
1246 * Verify that the data that is left in the rows are properly part of
1247 * an identity matrix.
1249 for (i
= 0; i
< nmissing
; i
++) {
1250 for (j
= 0; j
< n
; j
++) {
1251 if (j
== missing
[i
]) {
1252 ASSERT3U(rows
[i
][j
], ==, 1);
1254 ASSERT0(rows
[i
][j
]);
1261 vdev_raidz_matrix_reconstruct(raidz_map_t
*rm
, int n
, int nmissing
,
1262 int *missing
, uint8_t **invrows
, const uint8_t *used
)
1267 uint8_t *dst
[VDEV_RAIDZ_MAXPARITY
] = { NULL
};
1268 uint64_t dcount
[VDEV_RAIDZ_MAXPARITY
] = { 0 };
1272 uint8_t *invlog
[VDEV_RAIDZ_MAXPARITY
];
1276 psize
= sizeof (invlog
[0][0]) * n
* nmissing
;
1277 p
= kmem_alloc(psize
, KM_SLEEP
);
1279 for (pp
= p
, i
= 0; i
< nmissing
; i
++) {
1284 for (i
= 0; i
< nmissing
; i
++) {
1285 for (j
= 0; j
< n
; j
++) {
1286 ASSERT3U(invrows
[i
][j
], !=, 0);
1287 invlog
[i
][j
] = vdev_raidz_log2
[invrows
[i
][j
]];
1291 for (i
= 0; i
< n
; i
++) {
1293 ASSERT3U(c
, <, rm
->rm_cols
);
1295 src
= abd_to_buf(rm
->rm_col
[c
].rc_abd
);
1296 ccount
= rm
->rm_col
[c
].rc_size
;
1297 for (j
= 0; j
< nmissing
; j
++) {
1298 cc
= missing
[j
] + rm
->rm_firstdatacol
;
1299 ASSERT3U(cc
, >=, rm
->rm_firstdatacol
);
1300 ASSERT3U(cc
, <, rm
->rm_cols
);
1301 ASSERT3U(cc
, !=, c
);
1303 dst
[j
] = abd_to_buf(rm
->rm_col
[cc
].rc_abd
);
1304 dcount
[j
] = rm
->rm_col
[cc
].rc_size
;
1307 ASSERT(ccount
>= rm
->rm_col
[missing
[0]].rc_size
|| i
> 0);
1309 for (x
= 0; x
< ccount
; x
++, src
++) {
1311 log
= vdev_raidz_log2
[*src
];
1313 for (cc
= 0; cc
< nmissing
; cc
++) {
1314 if (x
>= dcount
[cc
])
1320 if ((ll
= log
+ invlog
[cc
][i
]) >= 255)
1322 val
= vdev_raidz_pow2
[ll
];
1333 kmem_free(p
, psize
);
1337 vdev_raidz_reconstruct_general(raidz_map_t
*rm
, int *tgts
, int ntgts
)
1341 int missing_rows
[VDEV_RAIDZ_MAXPARITY
];
1342 int parity_map
[VDEV_RAIDZ_MAXPARITY
];
1347 uint8_t *rows
[VDEV_RAIDZ_MAXPARITY
];
1348 uint8_t *invrows
[VDEV_RAIDZ_MAXPARITY
];
1351 abd_t
**bufs
= NULL
;
1356 * Matrix reconstruction can't use scatter ABDs yet, so we allocate
1357 * temporary linear ABDs.
1359 if (!abd_is_linear(rm
->rm_col
[rm
->rm_firstdatacol
].rc_abd
)) {
1360 bufs
= kmem_alloc(rm
->rm_cols
* sizeof (abd_t
*), KM_PUSHPAGE
);
1362 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1363 raidz_col_t
*col
= &rm
->rm_col
[c
];
1365 bufs
[c
] = col
->rc_abd
;
1366 col
->rc_abd
= abd_alloc_linear(col
->rc_size
, B_TRUE
);
1367 abd_copy(col
->rc_abd
, bufs
[c
], col
->rc_size
);
1371 n
= rm
->rm_cols
- rm
->rm_firstdatacol
;
1374 * Figure out which data columns are missing.
1377 for (t
= 0; t
< ntgts
; t
++) {
1378 if (tgts
[t
] >= rm
->rm_firstdatacol
) {
1379 missing_rows
[nmissing_rows
++] =
1380 tgts
[t
] - rm
->rm_firstdatacol
;
1385 * Figure out which parity columns to use to help generate the missing
1388 for (tt
= 0, c
= 0, i
= 0; i
< nmissing_rows
; c
++) {
1390 ASSERT(c
< rm
->rm_firstdatacol
);
1393 * Skip any targeted parity columns.
1395 if (c
== tgts
[tt
]) {
1407 ASSERT3U(code
, <, 1 << VDEV_RAIDZ_MAXPARITY
);
1409 psize
= (sizeof (rows
[0][0]) + sizeof (invrows
[0][0])) *
1410 nmissing_rows
* n
+ sizeof (used
[0]) * n
;
1411 p
= kmem_alloc(psize
, KM_SLEEP
);
1413 for (pp
= p
, i
= 0; i
< nmissing_rows
; i
++) {
1421 for (i
= 0; i
< nmissing_rows
; i
++) {
1422 used
[i
] = parity_map
[i
];
1425 for (tt
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1426 if (tt
< nmissing_rows
&&
1427 c
== missing_rows
[tt
] + rm
->rm_firstdatacol
) {
1438 * Initialize the interesting rows of the matrix.
1440 vdev_raidz_matrix_init(rm
, n
, nmissing_rows
, parity_map
, rows
);
1443 * Invert the matrix.
1445 vdev_raidz_matrix_invert(rm
, n
, nmissing_rows
, missing_rows
, rows
,
1449 * Reconstruct the missing data using the generated matrix.
1451 vdev_raidz_matrix_reconstruct(rm
, n
, nmissing_rows
, missing_rows
,
1454 kmem_free(p
, psize
);
1457 * copy back from temporary linear abds and free them
1460 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1461 raidz_col_t
*col
= &rm
->rm_col
[c
];
1463 abd_copy(bufs
[c
], col
->rc_abd
, col
->rc_size
);
1464 abd_free(col
->rc_abd
);
1465 col
->rc_abd
= bufs
[c
];
1467 kmem_free(bufs
, rm
->rm_cols
* sizeof (abd_t
*));
1474 vdev_raidz_reconstruct(raidz_map_t
*rm
, const int *t
, int nt
)
1476 int tgts
[VDEV_RAIDZ_MAXPARITY
], *dt
;
1480 int nbadparity
, nbaddata
;
1481 int parity_valid
[VDEV_RAIDZ_MAXPARITY
];
1484 * The tgts list must already be sorted.
1486 for (i
= 1; i
< nt
; i
++) {
1487 ASSERT(t
[i
] > t
[i
- 1]);
1490 nbadparity
= rm
->rm_firstdatacol
;
1491 nbaddata
= rm
->rm_cols
- nbadparity
;
1493 for (i
= 0, c
= 0; c
< rm
->rm_cols
; c
++) {
1494 if (c
< rm
->rm_firstdatacol
)
1495 parity_valid
[c
] = B_FALSE
;
1497 if (i
< nt
&& c
== t
[i
]) {
1500 } else if (rm
->rm_col
[c
].rc_error
!= 0) {
1502 } else if (c
>= rm
->rm_firstdatacol
) {
1505 parity_valid
[c
] = B_TRUE
;
1510 ASSERT(ntgts
>= nt
);
1511 ASSERT(nbaddata
>= 0);
1512 ASSERT(nbaddata
+ nbadparity
== ntgts
);
1514 dt
= &tgts
[nbadparity
];
1516 /* Reconstruct using the new math implementation */
1517 ret
= vdev_raidz_math_reconstruct(rm
, parity_valid
, dt
, nbaddata
);
1518 if (ret
!= RAIDZ_ORIGINAL_IMPL
)
1522 * See if we can use any of our optimized reconstruction routines.
1526 if (parity_valid
[VDEV_RAIDZ_P
])
1527 return (vdev_raidz_reconstruct_p(rm
, dt
, 1));
1529 ASSERT(rm
->rm_firstdatacol
> 1);
1531 if (parity_valid
[VDEV_RAIDZ_Q
])
1532 return (vdev_raidz_reconstruct_q(rm
, dt
, 1));
1534 ASSERT(rm
->rm_firstdatacol
> 2);
1538 ASSERT(rm
->rm_firstdatacol
> 1);
1540 if (parity_valid
[VDEV_RAIDZ_P
] &&
1541 parity_valid
[VDEV_RAIDZ_Q
])
1542 return (vdev_raidz_reconstruct_pq(rm
, dt
, 2));
1544 ASSERT(rm
->rm_firstdatacol
> 2);
1549 code
= vdev_raidz_reconstruct_general(rm
, tgts
, ntgts
);
1550 ASSERT(code
< (1 << VDEV_RAIDZ_MAXPARITY
));
1556 vdev_raidz_open(vdev_t
*vd
, uint64_t *asize
, uint64_t *max_asize
,
1557 uint64_t *logical_ashift
, uint64_t *physical_ashift
)
1560 uint64_t nparity
= vd
->vdev_nparity
;
1565 ASSERT(nparity
> 0);
1567 if (nparity
> VDEV_RAIDZ_MAXPARITY
||
1568 vd
->vdev_children
< nparity
+ 1) {
1569 vd
->vdev_stat
.vs_aux
= VDEV_AUX_BAD_LABEL
;
1570 return (SET_ERROR(EINVAL
));
1573 vdev_open_children(vd
);
1575 for (c
= 0; c
< vd
->vdev_children
; c
++) {
1576 cvd
= vd
->vdev_child
[c
];
1578 if (cvd
->vdev_open_error
!= 0) {
1579 lasterror
= cvd
->vdev_open_error
;
1584 *asize
= MIN(*asize
- 1, cvd
->vdev_asize
- 1) + 1;
1585 *max_asize
= MIN(*max_asize
- 1, cvd
->vdev_max_asize
- 1) + 1;
1586 *logical_ashift
= MAX(*logical_ashift
, cvd
->vdev_ashift
);
1587 *physical_ashift
= MAX(*physical_ashift
,
1588 cvd
->vdev_physical_ashift
);
1591 *asize
*= vd
->vdev_children
;
1592 *max_asize
*= vd
->vdev_children
;
1594 if (numerrors
> nparity
) {
1595 vd
->vdev_stat
.vs_aux
= VDEV_AUX_NO_REPLICAS
;
1603 vdev_raidz_close(vdev_t
*vd
)
1607 for (c
= 0; c
< vd
->vdev_children
; c
++)
1608 vdev_close(vd
->vdev_child
[c
]);
1612 vdev_raidz_asize(vdev_t
*vd
, uint64_t psize
)
1615 uint64_t ashift
= vd
->vdev_top
->vdev_ashift
;
1616 uint64_t cols
= vd
->vdev_children
;
1617 uint64_t nparity
= vd
->vdev_nparity
;
1619 asize
= ((psize
- 1) >> ashift
) + 1;
1620 asize
+= nparity
* ((asize
+ cols
- nparity
- 1) / (cols
- nparity
));
1621 asize
= roundup(asize
, nparity
+ 1) << ashift
;
1627 vdev_raidz_child_done(zio_t
*zio
)
1629 raidz_col_t
*rc
= zio
->io_private
;
1631 rc
->rc_error
= zio
->io_error
;
1637 vdev_raidz_io_verify(zio_t
*zio
, raidz_map_t
*rm
, int col
)
1640 vdev_t
*vd
= zio
->io_vd
;
1641 vdev_t
*tvd
= vd
->vdev_top
;
1643 range_seg64_t logical_rs
, physical_rs
;
1644 logical_rs
.rs_start
= zio
->io_offset
;
1645 logical_rs
.rs_end
= logical_rs
.rs_start
+
1646 vdev_raidz_asize(zio
->io_vd
, zio
->io_size
);
1648 raidz_col_t
*rc
= &rm
->rm_col
[col
];
1649 vdev_t
*cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1651 vdev_xlate(cvd
, &logical_rs
, &physical_rs
);
1652 ASSERT3U(rc
->rc_offset
, ==, physical_rs
.rs_start
);
1653 ASSERT3U(rc
->rc_offset
, <, physical_rs
.rs_end
);
1655 * It would be nice to assert that rs_end is equal
1656 * to rc_offset + rc_size but there might be an
1657 * optional I/O at the end that is not accounted in
1660 if (physical_rs
.rs_end
> rc
->rc_offset
+ rc
->rc_size
) {
1661 ASSERT3U(physical_rs
.rs_end
, ==, rc
->rc_offset
+
1662 rc
->rc_size
+ (1 << tvd
->vdev_ashift
));
1664 ASSERT3U(physical_rs
.rs_end
, ==, rc
->rc_offset
+ rc
->rc_size
);
1670 * Start an IO operation on a RAIDZ VDev
1673 * - For write operations:
1674 * 1. Generate the parity data
1675 * 2. Create child zio write operations to each column's vdev, for both
1677 * 3. If the column skips any sectors for padding, create optional dummy
1678 * write zio children for those areas to improve aggregation continuity.
1679 * - For read operations:
1680 * 1. Create child zio read operations to each data column's vdev to read
1681 * the range of data required for zio.
1682 * 2. If this is a scrub or resilver operation, or if any of the data
1683 * vdevs have had errors, then create zio read operations to the parity
1684 * columns' VDevs as well.
1687 vdev_raidz_io_start(zio_t
*zio
)
1689 vdev_t
*vd
= zio
->io_vd
;
1690 vdev_t
*tvd
= vd
->vdev_top
;
1696 rm
= vdev_raidz_map_alloc(zio
, tvd
->vdev_ashift
, vd
->vdev_children
,
1699 ASSERT3U(rm
->rm_asize
, ==, vdev_psize_to_asize(vd
, zio
->io_size
));
1701 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
1702 vdev_raidz_generate_parity(rm
);
1704 for (c
= 0; c
< rm
->rm_cols
; c
++) {
1705 rc
= &rm
->rm_col
[c
];
1706 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1709 * Verify physical to logical translation.
1711 vdev_raidz_io_verify(zio
, rm
, c
);
1713 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1714 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1715 zio
->io_type
, zio
->io_priority
, 0,
1716 vdev_raidz_child_done
, rc
));
1720 * Generate optional I/Os for any skipped sectors to improve
1721 * aggregation contiguity.
1723 for (c
= rm
->rm_skipstart
, i
= 0; i
< rm
->rm_nskip
; c
++, i
++) {
1724 ASSERT(c
<= rm
->rm_scols
);
1725 if (c
== rm
->rm_scols
)
1727 rc
= &rm
->rm_col
[c
];
1728 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1729 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1730 rc
->rc_offset
+ rc
->rc_size
, NULL
,
1731 1 << tvd
->vdev_ashift
,
1732 zio
->io_type
, zio
->io_priority
,
1733 ZIO_FLAG_NODATA
| ZIO_FLAG_OPTIONAL
, NULL
, NULL
));
1740 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
1743 * Iterate over the columns in reverse order so that we hit the parity
1744 * last -- any errors along the way will force us to read the parity.
1746 for (c
= rm
->rm_cols
- 1; c
>= 0; c
--) {
1747 rc
= &rm
->rm_col
[c
];
1748 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1749 if (!vdev_readable(cvd
)) {
1750 if (c
>= rm
->rm_firstdatacol
)
1751 rm
->rm_missingdata
++;
1753 rm
->rm_missingparity
++;
1754 rc
->rc_error
= SET_ERROR(ENXIO
);
1755 rc
->rc_tried
= 1; /* don't even try */
1759 if (vdev_dtl_contains(cvd
, DTL_MISSING
, zio
->io_txg
, 1)) {
1760 if (c
>= rm
->rm_firstdatacol
)
1761 rm
->rm_missingdata
++;
1763 rm
->rm_missingparity
++;
1764 rc
->rc_error
= SET_ERROR(ESTALE
);
1768 if (c
>= rm
->rm_firstdatacol
|| rm
->rm_missingdata
> 0 ||
1769 (zio
->io_flags
& (ZIO_FLAG_SCRUB
| ZIO_FLAG_RESILVER
))) {
1770 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1771 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1772 zio
->io_type
, zio
->io_priority
, 0,
1773 vdev_raidz_child_done
, rc
));
1782 * Report a checksum error for a child of a RAID-Z device.
1785 raidz_checksum_error(zio_t
*zio
, raidz_col_t
*rc
, abd_t
*bad_data
)
1787 vdev_t
*vd
= zio
->io_vd
->vdev_child
[rc
->rc_devidx
];
1789 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
1790 zio_bad_cksum_t zbc
;
1791 raidz_map_t
*rm
= zio
->io_vsd
;
1793 zbc
.zbc_has_cksum
= 0;
1794 zbc
.zbc_injected
= rm
->rm_ecksuminjected
;
1796 int ret
= zfs_ereport_post_checksum(zio
->io_spa
, vd
,
1797 &zio
->io_bookmark
, zio
, rc
->rc_offset
, rc
->rc_size
,
1798 rc
->rc_abd
, bad_data
, &zbc
);
1799 if (ret
!= EALREADY
) {
1800 mutex_enter(&vd
->vdev_stat_lock
);
1801 vd
->vdev_stat
.vs_checksum_errors
++;
1802 mutex_exit(&vd
->vdev_stat_lock
);
1808 * We keep track of whether or not there were any injected errors, so that
1809 * any ereports we generate can note it.
1812 raidz_checksum_verify(zio_t
*zio
)
1814 zio_bad_cksum_t zbc
;
1815 raidz_map_t
*rm
= zio
->io_vsd
;
1817 bzero(&zbc
, sizeof (zio_bad_cksum_t
));
1819 int ret
= zio_checksum_error(zio
, &zbc
);
1820 if (ret
!= 0 && zbc
.zbc_injected
!= 0)
1821 rm
->rm_ecksuminjected
= 1;
1827 * Generate the parity from the data columns. If we tried and were able to
1828 * read the parity without error, verify that the generated parity matches the
1829 * data we read. If it doesn't, we fire off a checksum error. Return the
1830 * number such failures.
1833 raidz_parity_verify(zio_t
*zio
, raidz_map_t
*rm
)
1835 abd_t
*orig
[VDEV_RAIDZ_MAXPARITY
];
1839 blkptr_t
*bp
= zio
->io_bp
;
1840 enum zio_checksum checksum
= (bp
== NULL
? zio
->io_prop
.zp_checksum
:
1841 (BP_IS_GANG(bp
) ? ZIO_CHECKSUM_GANG_HEADER
: BP_GET_CHECKSUM(bp
)));
1843 if (checksum
== ZIO_CHECKSUM_NOPARITY
)
1846 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1847 rc
= &rm
->rm_col
[c
];
1848 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1851 orig
[c
] = abd_alloc_sametype(rc
->rc_abd
, rc
->rc_size
);
1852 abd_copy(orig
[c
], rc
->rc_abd
, rc
->rc_size
);
1855 vdev_raidz_generate_parity(rm
);
1857 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1858 rc
= &rm
->rm_col
[c
];
1859 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1861 if (abd_cmp(orig
[c
], rc
->rc_abd
) != 0) {
1862 raidz_checksum_error(zio
, rc
, orig
[c
]);
1863 rc
->rc_error
= SET_ERROR(ECKSUM
);
1873 vdev_raidz_worst_error(raidz_map_t
*rm
)
1877 for (int c
= 0; c
< rm
->rm_cols
; c
++)
1878 error
= zio_worst_error(error
, rm
->rm_col
[c
].rc_error
);
1884 * Iterate over all combinations of bad data and attempt a reconstruction.
1885 * Note that the algorithm below is non-optimal because it doesn't take into
1886 * account how reconstruction is actually performed. For example, with
1887 * triple-parity RAID-Z the reconstruction procedure is the same if column 4
1888 * is targeted as invalid as if columns 1 and 4 are targeted since in both
1889 * cases we'd only use parity information in column 0.
1892 vdev_raidz_combrec(zio_t
*zio
, int total_errors
, int data_errors
)
1894 raidz_map_t
*rm
= zio
->io_vsd
;
1896 abd_t
*orig
[VDEV_RAIDZ_MAXPARITY
];
1897 int tstore
[VDEV_RAIDZ_MAXPARITY
+ 2];
1898 int *tgts
= &tstore
[1];
1899 int curr
, next
, i
, c
, n
;
1902 ASSERT(total_errors
< rm
->rm_firstdatacol
);
1905 * This simplifies one edge condition.
1909 for (n
= 1; n
<= rm
->rm_firstdatacol
- total_errors
; n
++) {
1911 * Initialize the targets array by finding the first n columns
1912 * that contain no error.
1914 * If there were no data errors, we need to ensure that we're
1915 * always explicitly attempting to reconstruct at least one
1916 * data column. To do this, we simply push the highest target
1917 * up into the data columns.
1919 for (c
= 0, i
= 0; i
< n
; i
++) {
1920 if (i
== n
- 1 && data_errors
== 0 &&
1921 c
< rm
->rm_firstdatacol
) {
1922 c
= rm
->rm_firstdatacol
;
1925 while (rm
->rm_col
[c
].rc_error
!= 0) {
1927 ASSERT3S(c
, <, rm
->rm_cols
);
1934 * Setting tgts[n] simplifies the other edge condition.
1936 tgts
[n
] = rm
->rm_cols
;
1939 * These buffers were allocated in previous iterations.
1941 for (i
= 0; i
< n
- 1; i
++) {
1942 ASSERT(orig
[i
] != NULL
);
1945 orig
[n
- 1] = abd_alloc_sametype(rm
->rm_col
[0].rc_abd
,
1946 rm
->rm_col
[0].rc_size
);
1956 * Save off the original data that we're going to
1957 * attempt to reconstruct.
1959 for (i
= 0; i
< n
; i
++) {
1960 ASSERT(orig
[i
] != NULL
);
1963 ASSERT3S(c
, <, rm
->rm_cols
);
1964 rc
= &rm
->rm_col
[c
];
1965 abd_copy(orig
[i
], rc
->rc_abd
, rc
->rc_size
);
1969 * Attempt a reconstruction and exit the outer loop on
1972 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
1973 if (raidz_checksum_verify(zio
) == 0) {
1975 for (i
= 0; i
< n
; i
++) {
1977 rc
= &rm
->rm_col
[c
];
1978 ASSERT(rc
->rc_error
== 0);
1980 raidz_checksum_error(zio
, rc
,
1982 rc
->rc_error
= SET_ERROR(ECKSUM
);
1990 * Restore the original data.
1992 for (i
= 0; i
< n
; i
++) {
1994 rc
= &rm
->rm_col
[c
];
1995 abd_copy(rc
->rc_abd
, orig
[i
], rc
->rc_size
);
2000 * Find the next valid column after the curr
2003 for (next
= tgts
[curr
] + 1;
2004 next
< rm
->rm_cols
&&
2005 rm
->rm_col
[next
].rc_error
!= 0; next
++)
2008 ASSERT(next
<= tgts
[curr
+ 1]);
2011 * If that spot is available, we're done here.
2013 if (next
!= tgts
[curr
+ 1])
2017 * Otherwise, find the next valid column after
2018 * the previous position.
2020 for (c
= tgts
[curr
- 1] + 1;
2021 rm
->rm_col
[c
].rc_error
!= 0; c
++)
2027 } while (curr
!= n
);
2032 for (i
= 0; i
< n
; i
++)
2039 * Complete an IO operation on a RAIDZ VDev
2042 * - For write operations:
2043 * 1. Check for errors on the child IOs.
2044 * 2. Return, setting an error code if too few child VDevs were written
2045 * to reconstruct the data later. Note that partial writes are
2046 * considered successful if they can be reconstructed at all.
2047 * - For read operations:
2048 * 1. Check for errors on the child IOs.
2049 * 2. If data errors occurred:
2050 * a. Try to reassemble the data from the parity available.
2051 * b. If we haven't yet read the parity drives, read them now.
2052 * c. If all parity drives have been read but the data still doesn't
2053 * reassemble with a correct checksum, then try combinatorial
2055 * d. If that doesn't work, return an error.
2056 * 3. If there were unexpected errors or this is a resilver operation,
2057 * rewrite the vdevs that had errors.
2060 vdev_raidz_io_done(zio_t
*zio
)
2062 vdev_t
*vd
= zio
->io_vd
;
2064 raidz_map_t
*rm
= zio
->io_vsd
;
2065 raidz_col_t
*rc
= NULL
;
2066 int unexpected_errors
= 0;
2067 int parity_errors
= 0;
2068 int parity_untried
= 0;
2069 int data_errors
= 0;
2070 int total_errors
= 0;
2072 int tgts
[VDEV_RAIDZ_MAXPARITY
];
2075 ASSERT(zio
->io_bp
!= NULL
); /* XXX need to add code to enforce this */
2077 ASSERT(rm
->rm_missingparity
<= rm
->rm_firstdatacol
);
2078 ASSERT(rm
->rm_missingdata
<= rm
->rm_cols
- rm
->rm_firstdatacol
);
2080 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2081 rc
= &rm
->rm_col
[c
];
2084 ASSERT(rc
->rc_error
!= ECKSUM
); /* child has no bp */
2086 if (c
< rm
->rm_firstdatacol
)
2091 if (!rc
->rc_skipped
)
2092 unexpected_errors
++;
2095 } else if (c
< rm
->rm_firstdatacol
&& !rc
->rc_tried
) {
2100 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
2102 * XXX -- for now, treat partial writes as a success.
2103 * (If we couldn't write enough columns to reconstruct
2104 * the data, the I/O failed. Otherwise, good enough.)
2106 * Now that we support write reallocation, it would be better
2107 * to treat partial failure as real failure unless there are
2108 * no non-degraded top-level vdevs left, and not update DTLs
2109 * if we intend to reallocate.
2112 if (total_errors
> rm
->rm_firstdatacol
)
2113 zio
->io_error
= vdev_raidz_worst_error(rm
);
2118 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
2120 * There are three potential phases for a read:
2121 * 1. produce valid data from the columns read
2122 * 2. read all disks and try again
2123 * 3. perform combinatorial reconstruction
2125 * Each phase is progressively both more expensive and less likely to
2126 * occur. If we encounter more errors than we can repair or all phases
2127 * fail, we have no choice but to return an error.
2131 * If the number of errors we saw was correctable -- less than or equal
2132 * to the number of parity disks read -- attempt to produce data that
2133 * has a valid checksum. Naturally, this case applies in the absence of
2136 if (total_errors
<= rm
->rm_firstdatacol
- parity_untried
) {
2137 if (data_errors
== 0) {
2138 if (raidz_checksum_verify(zio
) == 0) {
2140 * If we read parity information (unnecessarily
2141 * as it happens since no reconstruction was
2142 * needed) regenerate and verify the parity.
2143 * We also regenerate parity when resilvering
2144 * so we can write it out to the failed device
2147 if (parity_errors
+ parity_untried
<
2148 rm
->rm_firstdatacol
||
2149 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2150 n
= raidz_parity_verify(zio
, rm
);
2151 unexpected_errors
+= n
;
2152 ASSERT(parity_errors
+ n
<=
2153 rm
->rm_firstdatacol
);
2159 * We either attempt to read all the parity columns or
2160 * none of them. If we didn't try to read parity, we
2161 * wouldn't be here in the correctable case. There must
2162 * also have been fewer parity errors than parity
2163 * columns or, again, we wouldn't be in this code path.
2165 ASSERT(parity_untried
== 0);
2166 ASSERT(parity_errors
< rm
->rm_firstdatacol
);
2169 * Identify the data columns that reported an error.
2172 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
2173 rc
= &rm
->rm_col
[c
];
2174 if (rc
->rc_error
!= 0) {
2175 ASSERT(n
< VDEV_RAIDZ_MAXPARITY
);
2180 ASSERT(rm
->rm_firstdatacol
>= n
);
2182 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
2184 if (raidz_checksum_verify(zio
) == 0) {
2186 * If we read more parity disks than were used
2187 * for reconstruction, confirm that the other
2188 * parity disks produced correct data. This
2189 * routine is suboptimal in that it regenerates
2190 * the parity that we already used in addition
2191 * to the parity that we're attempting to
2192 * verify, but this should be a relatively
2193 * uncommon case, and can be optimized if it
2194 * becomes a problem. Note that we regenerate
2195 * parity when resilvering so we can write it
2196 * out to failed devices later.
2198 if (parity_errors
< rm
->rm_firstdatacol
- n
||
2199 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2200 n
= raidz_parity_verify(zio
, rm
);
2201 unexpected_errors
+= n
;
2202 ASSERT(parity_errors
+ n
<=
2203 rm
->rm_firstdatacol
);
2212 * This isn't a typical situation -- either we got a read error or
2213 * a child silently returned bad data. Read every block so we can
2214 * try again with as much data and parity as we can track down. If
2215 * we've already been through once before, all children will be marked
2216 * as tried so we'll proceed to combinatorial reconstruction.
2218 unexpected_errors
= 1;
2219 rm
->rm_missingdata
= 0;
2220 rm
->rm_missingparity
= 0;
2222 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2223 if (rm
->rm_col
[c
].rc_tried
)
2226 zio_vdev_io_redone(zio
);
2228 rc
= &rm
->rm_col
[c
];
2231 zio_nowait(zio_vdev_child_io(zio
, NULL
,
2232 vd
->vdev_child
[rc
->rc_devidx
],
2233 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2234 zio
->io_type
, zio
->io_priority
, 0,
2235 vdev_raidz_child_done
, rc
));
2236 } while (++c
< rm
->rm_cols
);
2242 * At this point we've attempted to reconstruct the data given the
2243 * errors we detected, and we've attempted to read all columns. There
2244 * must, therefore, be one or more additional problems -- silent errors
2245 * resulting in invalid data rather than explicit I/O errors resulting
2246 * in absent data. We check if there is enough additional data to
2247 * possibly reconstruct the data and then perform combinatorial
2248 * reconstruction over all possible combinations. If that fails,
2251 if (total_errors
> rm
->rm_firstdatacol
) {
2252 zio
->io_error
= vdev_raidz_worst_error(rm
);
2254 } else if (total_errors
< rm
->rm_firstdatacol
&&
2255 (code
= vdev_raidz_combrec(zio
, total_errors
, data_errors
)) != 0) {
2257 * If we didn't use all the available parity for the
2258 * combinatorial reconstruction, verify that the remaining
2259 * parity is correct.
2261 if (code
!= (1 << rm
->rm_firstdatacol
) - 1)
2262 (void) raidz_parity_verify(zio
, rm
);
2265 * We're here because either:
2267 * total_errors == rm_first_datacol, or
2268 * vdev_raidz_combrec() failed
2270 * In either case, there is enough bad data to prevent
2273 * Start checksum ereports for all children which haven't
2274 * failed, and the IO wasn't speculative.
2276 zio
->io_error
= SET_ERROR(ECKSUM
);
2278 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
2279 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2281 rc
= &rm
->rm_col
[c
];
2282 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
2283 if (rc
->rc_error
!= 0)
2286 zio_bad_cksum_t zbc
;
2287 zbc
.zbc_has_cksum
= 0;
2288 zbc
.zbc_injected
= rm
->rm_ecksuminjected
;
2290 int ret
= zfs_ereport_start_checksum(
2291 zio
->io_spa
, cvd
, &zio
->io_bookmark
, zio
,
2292 rc
->rc_offset
, rc
->rc_size
,
2293 (void *)(uintptr_t)c
, &zbc
);
2294 if (ret
!= EALREADY
) {
2295 mutex_enter(&cvd
->vdev_stat_lock
);
2296 cvd
->vdev_stat
.vs_checksum_errors
++;
2297 mutex_exit(&cvd
->vdev_stat_lock
);
2304 zio_checksum_verified(zio
);
2306 if (zio
->io_error
== 0 && spa_writeable(zio
->io_spa
) &&
2307 (unexpected_errors
|| (zio
->io_flags
& ZIO_FLAG_RESILVER
))) {
2309 * Use the good data we have in hand to repair damaged children.
2311 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2312 rc
= &rm
->rm_col
[c
];
2313 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
2315 if (rc
->rc_error
== 0)
2318 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
2319 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2320 ZIO_TYPE_WRITE
, ZIO_PRIORITY_ASYNC_WRITE
,
2321 ZIO_FLAG_IO_REPAIR
| (unexpected_errors
?
2322 ZIO_FLAG_SELF_HEAL
: 0), NULL
, NULL
));
2328 vdev_raidz_state_change(vdev_t
*vd
, int faulted
, int degraded
)
2330 if (faulted
> vd
->vdev_nparity
)
2331 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_CANT_OPEN
,
2332 VDEV_AUX_NO_REPLICAS
);
2333 else if (degraded
+ faulted
!= 0)
2334 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_DEGRADED
, VDEV_AUX_NONE
);
2336 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_HEALTHY
, VDEV_AUX_NONE
);
2340 * Determine if any portion of the provided block resides on a child vdev
2341 * with a dirty DTL and therefore needs to be resilvered. The function
2342 * assumes that at least one DTL is dirty which implies that full stripe
2343 * width blocks must be resilvered.
2346 vdev_raidz_need_resilver(vdev_t
*vd
, uint64_t offset
, size_t psize
)
2348 uint64_t dcols
= vd
->vdev_children
;
2349 uint64_t nparity
= vd
->vdev_nparity
;
2350 uint64_t ashift
= vd
->vdev_top
->vdev_ashift
;
2351 /* The starting RAIDZ (parent) vdev sector of the block. */
2352 uint64_t b
= offset
>> ashift
;
2353 /* The zio's size in units of the vdev's minimum sector size. */
2354 uint64_t s
= ((psize
- 1) >> ashift
) + 1;
2355 /* The first column for this stripe. */
2356 uint64_t f
= b
% dcols
;
2358 if (s
+ nparity
>= dcols
)
2361 for (uint64_t c
= 0; c
< s
+ nparity
; c
++) {
2362 uint64_t devidx
= (f
+ c
) % dcols
;
2363 vdev_t
*cvd
= vd
->vdev_child
[devidx
];
2366 * dsl_scan_need_resilver() already checked vd with
2367 * vdev_dtl_contains(). So here just check cvd with
2368 * vdev_dtl_empty(), cheaper and a good approximation.
2370 if (!vdev_dtl_empty(cvd
, DTL_PARTIAL
))
2378 vdev_raidz_xlate(vdev_t
*cvd
, const range_seg64_t
*in
, range_seg64_t
*res
)
2380 vdev_t
*raidvd
= cvd
->vdev_parent
;
2381 ASSERT(raidvd
->vdev_ops
== &vdev_raidz_ops
);
2383 uint64_t width
= raidvd
->vdev_children
;
2384 uint64_t tgt_col
= cvd
->vdev_id
;
2385 uint64_t ashift
= raidvd
->vdev_top
->vdev_ashift
;
2387 /* make sure the offsets are block-aligned */
2388 ASSERT0(in
->rs_start
% (1 << ashift
));
2389 ASSERT0(in
->rs_end
% (1 << ashift
));
2390 uint64_t b_start
= in
->rs_start
>> ashift
;
2391 uint64_t b_end
= in
->rs_end
>> ashift
;
2393 uint64_t start_row
= 0;
2394 if (b_start
> tgt_col
) /* avoid underflow */
2395 start_row
= ((b_start
- tgt_col
- 1) / width
) + 1;
2397 uint64_t end_row
= 0;
2398 if (b_end
> tgt_col
)
2399 end_row
= ((b_end
- tgt_col
- 1) / width
) + 1;
2401 res
->rs_start
= start_row
<< ashift
;
2402 res
->rs_end
= end_row
<< ashift
;
2404 ASSERT3U(res
->rs_start
, <=, in
->rs_start
);
2405 ASSERT3U(res
->rs_end
- res
->rs_start
, <=, in
->rs_end
- in
->rs_start
);
2408 vdev_ops_t vdev_raidz_ops
= {
2409 .vdev_op_open
= vdev_raidz_open
,
2410 .vdev_op_close
= vdev_raidz_close
,
2411 .vdev_op_asize
= vdev_raidz_asize
,
2412 .vdev_op_io_start
= vdev_raidz_io_start
,
2413 .vdev_op_io_done
= vdev_raidz_io_done
,
2414 .vdev_op_state_change
= vdev_raidz_state_change
,
2415 .vdev_op_need_resilver
= vdev_raidz_need_resilver
,
2416 .vdev_op_hold
= NULL
,
2417 .vdev_op_rele
= NULL
,
2418 .vdev_op_remap
= NULL
,
2419 .vdev_op_xlate
= vdev_raidz_xlate
,
2420 .vdev_op_type
= VDEV_TYPE_RAIDZ
, /* name of this vdev type */
2421 .vdev_op_leaf
= B_FALSE
/* not a leaf vdev */