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
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 #define CODE_P (0U)
38 #define CODE_Q (1U)
39 #define CODE_R (2U)
40
41 #define PARITY_P (1U)
42 #define PARITY_PQ (2U)
43 #define PARITY_PQR (3U)
44
45 #define TARGET_X (0U)
46 #define TARGET_Y (1U)
47 #define TARGET_Z (2U)
48
49 /*
50 * Parity generation methods indexes
51 */
52 enum raidz_math_gen_op {
53 RAIDZ_GEN_P = 0,
54 RAIDZ_GEN_PQ,
55 RAIDZ_GEN_PQR,
56 RAIDZ_GEN_NUM = 3
57 };
58 /*
59 * Data reconstruction methods indexes
60 */
61 enum raidz_rec_op {
62 RAIDZ_REC_P = 0,
63 RAIDZ_REC_Q,
64 RAIDZ_REC_R,
65 RAIDZ_REC_PQ,
66 RAIDZ_REC_PR,
67 RAIDZ_REC_QR,
68 RAIDZ_REC_PQR,
69 RAIDZ_REC_NUM = 7
70 };
71
72 extern const char *raidz_gen_name[RAIDZ_GEN_NUM];
73 extern const char *raidz_rec_name[RAIDZ_REC_NUM];
74
75 /*
76 * Methods used to define raidz implementation
77 *
78 * @raidz_gen_f Parity generation function
79 * @par1 pointer to raidz_map
80 * @raidz_rec_f Data reconstruction function
81 * @par1 pointer to raidz_map
82 * @par2 array of reconstruction targets
83 * @will_work_f Function returns TRUE if impl. is supported on the system
84 * @init_impl_f Function is called once on init
85 * @fini_impl_f Function is called once on fini
86 */
87 typedef void (*raidz_gen_f)(void *);
88 typedef int (*raidz_rec_f)(void *, const int *);
89 typedef boolean_t (*will_work_f)(void);
90 typedef void (*init_impl_f)(void);
91 typedef void (*fini_impl_f)(void);
92
93 #define RAIDZ_IMPL_NAME_MAX (20)
94
95 typedef struct raidz_impl_ops {
96 init_impl_f init;
97 fini_impl_f fini;
98 raidz_gen_f gen[RAIDZ_GEN_NUM]; /* Parity generate functions */
99 raidz_rec_f rec[RAIDZ_REC_NUM]; /* Data reconstruction functions */
100 will_work_f is_supported; /* Support check function */
101 char name[RAIDZ_IMPL_NAME_MAX]; /* Name of the implementation */
102 } raidz_impl_ops_t;
103
104 typedef struct raidz_col {
105 size_t rc_devidx; /* child device index for I/O */
106 size_t rc_offset; /* device offset */
107 size_t rc_size; /* I/O size */
108 abd_t *rc_abd; /* I/O data */
109 void *rc_gdata; /* used to store the "good" version */
110 int rc_error; /* I/O error for this device */
111 unsigned int rc_tried; /* Did we attempt this I/O column? */
112 unsigned int rc_skipped; /* Did we skip this I/O column? */
113 } raidz_col_t;
114
115 typedef struct raidz_map {
116 size_t rm_cols; /* Regular column count */
117 size_t rm_scols; /* Count including skipped columns */
118 size_t rm_bigcols; /* Number of oversized columns */
119 size_t rm_asize; /* Actual total I/O size */
120 size_t rm_missingdata; /* Count of missing data devices */
121 size_t rm_missingparity; /* Count of missing parity devices */
122 size_t rm_firstdatacol; /* First data column/parity count */
123 size_t rm_nskip; /* Skipped sectors for padding */
124 size_t rm_skipstart; /* Column index of padding start */
125 void *rm_abd_copy; /* rm_asize-buffer of copied data */
126 size_t rm_reports; /* # of referencing checksum reports */
127 unsigned int rm_freed; /* map no longer has referencing ZIO */
128 unsigned int rm_ecksuminjected; /* checksum error was injected */
129 const raidz_impl_ops_t *rm_ops; /* RAIDZ math operations */
130 raidz_col_t rm_col[1]; /* Flexible array of I/O columns */
131 } raidz_map_t;
132
133 #define RAIDZ_ORIGINAL_IMPL (INT_MAX)
134
135 extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
136 #if defined(__x86)
137 extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
138 #endif
139 #if defined(__x86)
140 extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
141 #endif
142 #if defined(__x86)
143 extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
144 #endif
145
146 /*
147 * Commonly used raidz_map helpers
148 *
149 * raidz_parity Returns parity of the RAIDZ block
150 * raidz_ncols Returns number of columns the block spans
151 * raidz_nbigcols Returns number of big columns
152 * raidz_col_p Returns pointer to a column
153 * raidz_col_size Returns size of a column
154 * raidz_big_size Returns size of big columns
155 * raidz_short_size Returns size of short columns
156 */
157 #define raidz_parity(rm) ((rm)->rm_firstdatacol)
158 #define raidz_ncols(rm) ((rm)->rm_cols)
159 #define raidz_nbigcols(rm) ((rm)->rm_bigcols)
160 #define raidz_col_p(rm, c) ((rm)->rm_col + (c))
161 #define raidz_col_size(rm, c) ((rm)->rm_col[c].rc_size)
162 #define raidz_big_size(rm) (raidz_col_size(rm, CODE_P))
163 #define raidz_short_size(rm) (raidz_col_size(rm, raidz_ncols(rm)-1))
164
165 /*
166 * Macro defines an RAIDZ parity generation method
167 *
168 * @code parity the function produce
169 * @impl name of the implementation
170 */
171 #define _RAIDZ_GEN_WRAP(code, impl) \
172 static void \
173 impl ## _gen_ ## code(void *rmp) \
174 { \
175 raidz_map_t *rm = (raidz_map_t *) rmp; \
176 raidz_generate_## code ## _impl(rm); \
177 }
178
179 /*
180 * Macro defines an RAIDZ data reconstruction method
181 *
182 * @code parity the function produce
183 * @impl name of the implementation
184 */
185 #define _RAIDZ_REC_WRAP(code, impl) \
186 static int \
187 impl ## _rec_ ## code(void *rmp, const int *tgtidx) \
188 { \
189 raidz_map_t *rm = (raidz_map_t *) rmp; \
190 return (raidz_reconstruct_## code ## _impl(rm, tgtidx)); \
191 }
192
193 /*
194 * Define all gen methods for an implementation
195 *
196 * @impl name of the implementation
197 */
198 #define DEFINE_GEN_METHODS(impl) \
199 _RAIDZ_GEN_WRAP(p, impl); \
200 _RAIDZ_GEN_WRAP(pq, impl); \
201 _RAIDZ_GEN_WRAP(pqr, impl)
202
203 /*
204 * Define all rec functions for an implementation
205 *
206 * @impl name of the implementation
207 */
208 #define DEFINE_REC_METHODS(impl) \
209 _RAIDZ_REC_WRAP(p, impl); \
210 _RAIDZ_REC_WRAP(q, impl); \
211 _RAIDZ_REC_WRAP(r, impl); \
212 _RAIDZ_REC_WRAP(pq, impl); \
213 _RAIDZ_REC_WRAP(pr, impl); \
214 _RAIDZ_REC_WRAP(qr, impl); \
215 _RAIDZ_REC_WRAP(pqr, impl)
216
217 #define RAIDZ_GEN_METHODS(impl) \
218 { \
219 [RAIDZ_GEN_P] = & impl ## _gen_p, \
220 [RAIDZ_GEN_PQ] = & impl ## _gen_pq, \
221 [RAIDZ_GEN_PQR] = & impl ## _gen_pqr \
222 }
223
224 #define RAIDZ_REC_METHODS(impl) \
225 { \
226 [RAIDZ_REC_P] = & impl ## _rec_p, \
227 [RAIDZ_REC_Q] = & impl ## _rec_q, \
228 [RAIDZ_REC_R] = & impl ## _rec_r, \
229 [RAIDZ_REC_PQ] = & impl ## _rec_pq, \
230 [RAIDZ_REC_PR] = & impl ## _rec_pr, \
231 [RAIDZ_REC_QR] = & impl ## _rec_qr, \
232 [RAIDZ_REC_PQR] = & impl ## _rec_pqr \
233 }
234
235
236 typedef struct raidz_impl_kstat {
237 uint64_t gen[RAIDZ_GEN_NUM]; /* gen method speed B/s */
238 uint64_t rec[RAIDZ_REC_NUM]; /* rec method speed B/s */
239 } raidz_impl_kstat_t;
240
241 /*
242 * Enumerate various multiplication constants
243 * used in reconstruction methods
244 */
245 typedef enum raidz_mul_info {
246 /* Reconstruct Q */
247 MUL_Q_X = 0,
248 /* Reconstruct R */
249 MUL_R_X = 0,
250 /* Reconstruct PQ */
251 MUL_PQ_X = 0,
252 MUL_PQ_Y = 1,
253 /* Reconstruct PR */
254 MUL_PR_X = 0,
255 MUL_PR_Y = 1,
256 /* Reconstruct QR */
257 MUL_QR_XQ = 0,
258 MUL_QR_X = 1,
259 MUL_QR_YQ = 2,
260 MUL_QR_Y = 3,
261 /* Reconstruct PQR */
262 MUL_PQR_XP = 0,
263 MUL_PQR_XQ = 1,
264 MUL_PQR_XR = 2,
265 MUL_PQR_YU = 3,
266 MUL_PQR_YP = 4,
267 MUL_PQR_YQ = 5,
268
269 MUL_CNT = 6
270 } raidz_mul_info_t;
271
272 /*
273 * Powers of 2 in the Galois field.
274 */
275 extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
276 /* Logs of 2 in the Galois field defined above. */
277 extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
278
279 /*
280 * Multiply a given number by 2 raised to the given power.
281 */
282 static inline uint8_t
vdev_raidz_exp2(const uint8_t a,const unsigned exp)283 vdev_raidz_exp2(const uint8_t a, const unsigned exp)
284 {
285 if (a == 0)
286 return (0);
287
288 return (vdev_raidz_pow2[(exp + (unsigned) vdev_raidz_log2[a]) % 255]);
289 }
290
291 /*
292 * Galois Field operations.
293 *
294 * gf_exp2 - computes 2 raised to the given power
295 * gf_exp2 - computes 4 raised to the given power
296 * gf_mul - multiplication
297 * gf_div - division
298 * gf_inv - multiplicative inverse
299 */
300 typedef unsigned gf_t;
301 typedef unsigned gf_log_t;
302
303 static inline gf_t
gf_mul(const gf_t a,const gf_t b)304 gf_mul(const gf_t a, const gf_t b)
305 {
306 gf_log_t logsum;
307
308 if (a == 0 || b == 0)
309 return (0);
310
311 logsum = (gf_log_t) vdev_raidz_log2[a] + (gf_log_t) vdev_raidz_log2[b];
312
313 return ((gf_t) vdev_raidz_pow2[logsum % 255]);
314 }
315
316 static inline gf_t
gf_div(const gf_t a,const gf_t b)317 gf_div(const gf_t a, const gf_t b)
318 {
319 gf_log_t logsum;
320
321 ASSERT3U(b, >, 0);
322 if (a == 0)
323 return (0);
324
325 logsum = (gf_log_t) 255 + (gf_log_t) vdev_raidz_log2[a] -
326 (gf_log_t) vdev_raidz_log2[b];
327
328 return ((gf_t) vdev_raidz_pow2[logsum % 255]);
329 }
330
331 static inline gf_t
gf_inv(const gf_t a)332 gf_inv(const gf_t a)
333 {
334 gf_log_t logsum;
335
336 ASSERT3U(a, >, 0);
337
338 logsum = (gf_log_t) 255 - (gf_log_t) vdev_raidz_log2[a];
339
340 return ((gf_t) vdev_raidz_pow2[logsum]);
341 }
342
343 static inline gf_t
gf_exp2(gf_log_t exp)344 gf_exp2(gf_log_t exp)
345 {
346 return (vdev_raidz_pow2[exp % 255]);
347 }
348
349 static inline gf_t
gf_exp4(gf_log_t exp)350 gf_exp4(gf_log_t exp)
351 {
352 ASSERT3U(exp, <=, 255);
353 return ((gf_t) vdev_raidz_pow2[(2 * exp) % 255]);
354 }
355
356 #ifdef __cplusplus
357 }
358 #endif
359
360 #endif /* _VDEV_RAIDZ_H */
361