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