1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * This file and its contents are supplied under the terms of the
4 * Common Development and Distribution License ("CDDL"), version 1.0.
5 * You may only use this file in accordance with the terms of version
6 * 1.0 of the CDDL.
7 *
8 * A full copy of the text of the CDDL should have accompanied this
9 * source. A copy of the CDDL is also available via the Internet at
10 * https://opensource.org/license/CDDL-1.0.
11 */
12 /*
13 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
14 */
15
16 #ifndef _VDEV_RAIDZ_H
17 #define _VDEV_RAIDZ_H
18
19 #include <sys/types.h>
20 #include <sys/debug.h>
21 #include <sys/kstat.h>
22 #include <sys/abd.h>
23 #include <sys/vdev_impl.h>
24 #include <sys/abd_impl.h>
25 #include <sys/zfs_rlock.h>
26
27 #ifdef __cplusplus
28 extern "C" {
29 #endif
30
31 #define CODE_P (0U)
32 #define CODE_Q (1U)
33 #define CODE_R (2U)
34
35 #define PARITY_P (1U)
36 #define PARITY_PQ (2U)
37 #define PARITY_PQR (3U)
38
39 #define TARGET_X (0U)
40 #define TARGET_Y (1U)
41 #define TARGET_Z (2U)
42
43 /*
44 * Parity generation methods indexes
45 */
46 enum raidz_math_gen_op {
47 RAIDZ_GEN_P = 0,
48 RAIDZ_GEN_PQ,
49 RAIDZ_GEN_PQR,
50 RAIDZ_GEN_NUM = 3
51 };
52 /*
53 * Data reconstruction methods indexes
54 */
55 enum raidz_rec_op {
56 RAIDZ_REC_P = 0,
57 RAIDZ_REC_Q,
58 RAIDZ_REC_R,
59 RAIDZ_REC_PQ,
60 RAIDZ_REC_PR,
61 RAIDZ_REC_QR,
62 RAIDZ_REC_PQR,
63 RAIDZ_REC_NUM = 7
64 };
65
66 extern const char *const raidz_gen_name[RAIDZ_GEN_NUM];
67 extern const char *const raidz_rec_name[RAIDZ_REC_NUM];
68
69 /*
70 * Methods used to define raidz implementation
71 *
72 * @raidz_gen_f Parity generation function
73 * @par1 pointer to raidz_map
74 * @raidz_rec_f Data reconstruction function
75 * @par1 pointer to raidz_map
76 * @par2 array of reconstruction targets
77 * @will_work_f Function returns TRUE if impl. is supported on the system
78 * @init_impl_f Function is called once on init
79 * @fini_impl_f Function is called once on fini
80 */
81 typedef void (*raidz_gen_f)(void *);
82 typedef int (*raidz_rec_f)(void *, const int *);
83 typedef boolean_t (*will_work_f)(void);
84 typedef void (*init_impl_f)(void);
85 typedef void (*fini_impl_f)(void);
86
87 #define RAIDZ_IMPL_NAME_MAX (20)
88
89 typedef struct raidz_impl_ops {
90 init_impl_f init;
91 fini_impl_f fini;
92 raidz_gen_f gen[RAIDZ_GEN_NUM]; /* Parity generate functions */
93 raidz_rec_f rec[RAIDZ_REC_NUM]; /* Data reconstruction functions */
94 will_work_f is_supported; /* Support check function */
95 char name[RAIDZ_IMPL_NAME_MAX]; /* Name of the implementation */
96 } raidz_impl_ops_t;
97
98
99 typedef struct raidz_col {
100 int rc_devidx; /* child device index for I/O */
101 uint32_t rc_size; /* I/O size */
102 uint64_t rc_offset; /* device offset */
103 abd_t rc_abdstruct; /* rc_abd probably points here */
104 abd_t *rc_abd; /* I/O data */
105 abd_t *rc_orig_data; /* pre-reconstruction */
106 int rc_error; /* I/O error for this device */
107 uint8_t rc_tried:1; /* Did we attempt this I/O column? */
108 uint8_t rc_skipped:1; /* Did we skip this I/O column? */
109 uint8_t rc_need_orig_restore:1; /* need to restore from orig_data? */
110 uint8_t rc_force_repair:1; /* Write good data to this column */
111 uint8_t rc_allow_repair:1; /* Allow repair I/O to this column */
112 uint8_t rc_tgt_is_dspare:1; /* The target is draid spare vdev */
113 uint8_t rc_latency_outlier:1; /* Latency outlier for this device */
114 int rc_shadow_devidx; /* for double write during expansion */
115 int rc_shadow_error; /* for double write during expansion */
116 uint64_t rc_shadow_offset; /* for double write during expansion */
117 } raidz_col_t;
118
119 typedef struct raidz_row {
120 int rr_cols; /* Regular column count */
121 int rr_scols; /* Count including skipped columns */
122 int rr_bigcols; /* Remainder data column count */
123 int rr_missingdata; /* Count of missing data devices */
124 int rr_missingparity; /* Count of missing parity devices */
125 int rr_firstdatacol; /* First data column/parity count */
126 abd_t *rr_abd_empty; /* dRAID empty sector buffer */
127 int rr_nempty; /* empty sectors included in parity */
128 int rr_outlier_cnt; /* Count of latency outlier devices */
129 #ifdef ZFS_DEBUG
130 uint64_t rr_offset; /* Logical offset for *_io_verify() */
131 uint64_t rr_size; /* Physical size for *_io_verify() */
132 #endif
133 raidz_col_t rr_col[]; /* Flexible array of I/O columns */
134 } raidz_row_t;
135
136 typedef struct raidz_map {
137 boolean_t rm_ecksuminjected; /* checksum error was injected */
138 int rm_nrows; /* Regular row count */
139 int rm_nskip; /* RAIDZ sectors skipped for padding */
140 int rm_skipstart; /* Column index of padding start */
141 int rm_original_width; /* pre-expansion width of raidz vdev */
142 int rm_nphys_cols; /* num entries in rm_phys_col[] */
143 zfs_locked_range_t *rm_lr;
144 const raidz_impl_ops_t *rm_ops; /* RAIDZ math operations */
145 raidz_col_t *rm_phys_col; /* if non-NULL, read i/o aggregation */
146 raidz_row_t *rm_row[]; /* flexible array of rows */
147 } raidz_map_t;
148
149 /*
150 * Nodes in vdev_raidz_t:vd_expand_txgs.
151 * Blocks with physical birth time of re_txg or later have the specified
152 * logical width (until the next node).
153 */
154 typedef struct reflow_node {
155 uint64_t re_txg;
156 uint64_t re_logical_width;
157 avl_node_t re_link;
158 } reflow_node_t;
159
160
161 #define RAIDZ_ORIGINAL_IMPL (INT_MAX)
162
163 extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
164 extern boolean_t raidz_will_scalar_work(void);
165
166 #if defined(__x86_64) && HAVE_SIMD(SSE2) /* only x86_64 for now */
167 extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
168 #endif
169 #if defined(__x86_64) && HAVE_SIMD(SSSE3) /* only x86_64 for now */
170 extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
171 #endif
172 #if defined(__x86_64) && HAVE_SIMD(AVX2) /* only x86_64 for now */
173 extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
174 #endif
175 #if defined(__x86_64) && HAVE_SIMD(AVX512F) /* only x86_64 for now */
176 extern const raidz_impl_ops_t vdev_raidz_avx512f_impl;
177 #endif
178 #if defined(__x86_64) && HAVE_SIMD(AVX512BW) /* only x86_64 for now */
179 extern const raidz_impl_ops_t vdev_raidz_avx512bw_impl;
180 #endif
181 #if defined(__aarch64__)
182 extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
183 extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
184 #endif
185 #if defined(__powerpc__)
186 extern const raidz_impl_ops_t vdev_raidz_powerpc_altivec_impl;
187 #endif
188
189 /*
190 * Commonly used raidz_map helpers
191 *
192 * raidz_parity Returns parity of the RAIDZ block
193 * raidz_ncols Returns number of columns the block spans
194 * Note, all rows have the same number of columns.
195 * raidz_nbigcols Returns number of big columns
196 * raidz_col_p Returns pointer to a column
197 * raidz_col_size Returns size of a column
198 * raidz_big_size Returns size of big columns
199 * raidz_short_size Returns size of short columns
200 */
201 #define raidz_parity(rm) ((rm)->rm_row[0]->rr_firstdatacol)
202 #define raidz_ncols(rm) ((rm)->rm_row[0]->rr_cols)
203 #define raidz_nbigcols(rm) ((rm)->rm_bigcols)
204 #define raidz_col_p(rm, c) ((rm)->rm_col + (c))
205 #define raidz_col_size(rm, c) ((rm)->rm_col[c].rc_size)
206 #define raidz_big_size(rm) (raidz_col_size(rm, CODE_P))
207 #define raidz_short_size(rm) (raidz_col_size(rm, raidz_ncols(rm)-1))
208
209 /*
210 * Macro defines an RAIDZ parity generation method
211 *
212 * @code parity the function produce
213 * @impl name of the implementation
214 */
215 #define _RAIDZ_GEN_WRAP(code, impl) \
216 static void \
217 impl ## _gen_ ## code(void *rrp) \
218 { \
219 raidz_row_t *rr = (raidz_row_t *)rrp; \
220 raidz_generate_## code ## _impl(rr); \
221 }
222
223 /*
224 * Macro defines an RAIDZ data reconstruction method
225 *
226 * @code parity the function produce
227 * @impl name of the implementation
228 */
229 #define _RAIDZ_REC_WRAP(code, impl) \
230 static int \
231 impl ## _rec_ ## code(void *rrp, const int *tgtidx) \
232 { \
233 raidz_row_t *rr = (raidz_row_t *)rrp; \
234 return (raidz_reconstruct_## code ## _impl(rr, tgtidx)); \
235 }
236
237 /*
238 * Define all gen methods for an implementation
239 *
240 * @impl name of the implementation
241 */
242 #define DEFINE_GEN_METHODS(impl) \
243 _RAIDZ_GEN_WRAP(p, impl); \
244 _RAIDZ_GEN_WRAP(pq, impl); \
245 _RAIDZ_GEN_WRAP(pqr, impl)
246
247 /*
248 * Define all rec functions for an implementation
249 *
250 * @impl name of the implementation
251 */
252 #define DEFINE_REC_METHODS(impl) \
253 _RAIDZ_REC_WRAP(p, impl); \
254 _RAIDZ_REC_WRAP(q, impl); \
255 _RAIDZ_REC_WRAP(r, impl); \
256 _RAIDZ_REC_WRAP(pq, impl); \
257 _RAIDZ_REC_WRAP(pr, impl); \
258 _RAIDZ_REC_WRAP(qr, impl); \
259 _RAIDZ_REC_WRAP(pqr, impl)
260
261 #define RAIDZ_GEN_METHODS(impl) \
262 { \
263 [RAIDZ_GEN_P] = & impl ## _gen_p, \
264 [RAIDZ_GEN_PQ] = & impl ## _gen_pq, \
265 [RAIDZ_GEN_PQR] = & impl ## _gen_pqr \
266 }
267
268 #define RAIDZ_REC_METHODS(impl) \
269 { \
270 [RAIDZ_REC_P] = & impl ## _rec_p, \
271 [RAIDZ_REC_Q] = & impl ## _rec_q, \
272 [RAIDZ_REC_R] = & impl ## _rec_r, \
273 [RAIDZ_REC_PQ] = & impl ## _rec_pq, \
274 [RAIDZ_REC_PR] = & impl ## _rec_pr, \
275 [RAIDZ_REC_QR] = & impl ## _rec_qr, \
276 [RAIDZ_REC_PQR] = & impl ## _rec_pqr \
277 }
278
279
280 typedef struct raidz_impl_kstat {
281 uint64_t gen[RAIDZ_GEN_NUM]; /* gen method speed B/s */
282 uint64_t rec[RAIDZ_REC_NUM]; /* rec method speed B/s */
283 } raidz_impl_kstat_t;
284
285 /*
286 * Enumerate various multiplication constants
287 * used in reconstruction methods
288 */
289 typedef enum raidz_mul_info {
290 /* Reconstruct Q */
291 MUL_Q_X = 0,
292 /* Reconstruct R */
293 MUL_R_X = 0,
294 /* Reconstruct PQ */
295 MUL_PQ_X = 0,
296 MUL_PQ_Y = 1,
297 /* Reconstruct PR */
298 MUL_PR_X = 0,
299 MUL_PR_Y = 1,
300 /* Reconstruct QR */
301 MUL_QR_XQ = 0,
302 MUL_QR_X = 1,
303 MUL_QR_YQ = 2,
304 MUL_QR_Y = 3,
305 /* Reconstruct PQR */
306 MUL_PQR_XP = 0,
307 MUL_PQR_XQ = 1,
308 MUL_PQR_XR = 2,
309 MUL_PQR_YU = 3,
310 MUL_PQR_YP = 4,
311 MUL_PQR_YQ = 5,
312
313 MUL_CNT = 6
314 } raidz_mul_info_t;
315
316 /*
317 * Powers of 2 in the Galois field.
318 */
319 extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
320 /* Logs of 2 in the Galois field defined above. */
321 extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
322
323 /*
324 * Multiply a given number by 2 raised to the given power.
325 */
326 static inline uint8_t
vdev_raidz_exp2(const uint8_t a,const unsigned exp)327 vdev_raidz_exp2(const uint8_t a, const unsigned exp)
328 {
329 if (a == 0)
330 return (0);
331
332 return (vdev_raidz_pow2[(exp + (unsigned)vdev_raidz_log2[a]) % 255]);
333 }
334
335 /*
336 * Galois Field operations.
337 *
338 * gf_exp2 - computes 2 raised to the given power
339 * gf_exp4 - computes 4 raised to the given power
340 * gf_mul - multiplication
341 * gf_div - division
342 * gf_inv - multiplicative inverse
343 */
344 typedef unsigned gf_t;
345 typedef unsigned gf_log_t;
346
347 static inline gf_t
gf_mul(const gf_t a,const gf_t b)348 gf_mul(const gf_t a, const gf_t b)
349 {
350 gf_log_t logsum;
351
352 if (a == 0 || b == 0)
353 return (0);
354
355 logsum = (gf_log_t)vdev_raidz_log2[a] + (gf_log_t)vdev_raidz_log2[b];
356
357 return ((gf_t)vdev_raidz_pow2[logsum % 255]);
358 }
359
360 static inline gf_t
gf_div(const gf_t a,const gf_t b)361 gf_div(const gf_t a, const gf_t b)
362 {
363 gf_log_t logsum;
364
365 ASSERT3U(b, >, 0);
366 if (a == 0)
367 return (0);
368
369 logsum = (gf_log_t)255 + (gf_log_t)vdev_raidz_log2[a] -
370 (gf_log_t)vdev_raidz_log2[b];
371
372 return ((gf_t)vdev_raidz_pow2[logsum % 255]);
373 }
374
375 static inline gf_t
gf_inv(const gf_t a)376 gf_inv(const gf_t a)
377 {
378 gf_log_t logsum;
379
380 ASSERT3U(a, >, 0);
381
382 logsum = (gf_log_t)255 - (gf_log_t)vdev_raidz_log2[a];
383
384 return ((gf_t)vdev_raidz_pow2[logsum]);
385 }
386
387 static inline gf_t
gf_exp2(gf_log_t exp)388 gf_exp2(gf_log_t exp)
389 {
390 return (vdev_raidz_pow2[exp % 255]);
391 }
392
393 static inline gf_t
gf_exp4(gf_log_t exp)394 gf_exp4(gf_log_t exp)
395 {
396 ASSERT3U(exp, <=, 255);
397 return ((gf_t)vdev_raidz_pow2[(2 * exp) % 255]);
398 }
399
400 #ifdef __cplusplus
401 }
402 #endif
403
404 #endif /* _VDEV_RAIDZ_H */
405