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