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