summaryrefslogtreecommitdiffstats
path: root/include/sys/vdev_raidz_impl.h
blob: ca902f15d8e55e2f84a5a9b29d69675e0ded8064 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
 */

#ifndef _VDEV_RAIDZ_H
#define	_VDEV_RAIDZ_H

#include <sys/types.h>
#include <sys/debug.h>
#include <sys/kstat.h>

#ifdef  __cplusplus
extern "C" {
#endif

#define	CODE_P		(0U)
#define	CODE_Q		(1U)
#define	CODE_R		(2U)

#define	PARITY_P	(1U)
#define	PARITY_PQ	(2U)
#define	PARITY_PQR	(3U)

#define	TARGET_X	(0U)
#define	TARGET_Y	(1U)
#define	TARGET_Z	(2U)

/*
 * Parity generation methods indexes
 */
enum raidz_math_gen_op {
	RAIDZ_GEN_P = 0,
	RAIDZ_GEN_PQ,
	RAIDZ_GEN_PQR,
	RAIDZ_GEN_NUM = 3
};
/*
 * Data reconstruction methods indexes
 */
enum raidz_rec_op {
	RAIDZ_REC_P = 0,
	RAIDZ_REC_Q,
	RAIDZ_REC_R,
	RAIDZ_REC_PQ,
	RAIDZ_REC_PR,
	RAIDZ_REC_QR,
	RAIDZ_REC_PQR,
	RAIDZ_REC_NUM = 7
};

extern const char *raidz_gen_name[RAIDZ_GEN_NUM];
extern const char *raidz_rec_name[RAIDZ_REC_NUM];

/*
 * Methods used to define raidz implementation
 *
 * @raidz_gen_f	Parity generation function
 *     @par1	pointer to raidz_map
 * @raidz_rec_f	Data reconstruction function
 *     @par1	pointer to raidz_map
 *     @par2	array of reconstruction targets
 * @will_work_f Function returns TRUE if impl. is supported on the system
 * @init_impl_f Function is called once on init
 * @fini_impl_f Function is called once on fini
 */
typedef void		(*raidz_gen_f)(void *);
typedef int		(*raidz_rec_f)(void *, const int *);
typedef boolean_t	(*will_work_f)(void);
typedef void		(*init_impl_f)(void);
typedef void		(*fini_impl_f)(void);

#define	RAIDZ_IMPL_NAME_MAX	(16)

typedef struct raidz_impl_ops {
	init_impl_f init;
	fini_impl_f fini;
	raidz_gen_f gen[RAIDZ_GEN_NUM];	/* Parity generate functions */
	raidz_rec_f rec[RAIDZ_REC_NUM];	/* Data reconstruction functions */
	will_work_f is_supported;	/* Support check function */
	char name[RAIDZ_IMPL_NAME_MAX];	/* Name of the implementation */
} raidz_impl_ops_t;

typedef struct raidz_col {
	size_t rc_devidx;		/* child device index for I/O */
	size_t rc_offset;		/* device offset */
	size_t rc_size;			/* I/O size */
	void *rc_data;			/* I/O data */
	void *rc_gdata;			/* used to store the "good" version */
	int rc_error;			/* I/O error for this device */
	unsigned int rc_tried;		/* Did we attempt this I/O column? */
	unsigned int rc_skipped;	/* Did we skip this I/O column? */
} raidz_col_t;

typedef struct raidz_map {
	size_t rm_cols;			/* Regular column count */
	size_t rm_scols;		/* Count including skipped columns */
	size_t rm_bigcols;		/* Number of oversized columns */
	size_t rm_asize;		/* Actual total I/O size */
	size_t rm_missingdata;		/* Count of missing data devices */
	size_t rm_missingparity;	/* Count of missing parity devices */
	size_t rm_firstdatacol;		/* First data column/parity count */
	size_t rm_nskip;		/* Skipped sectors for padding */
	size_t rm_skipstart;		/* Column index of padding start */
	void *rm_datacopy;		/* rm_asize-buffer of copied data */
	size_t rm_reports;		/* # of referencing checksum reports */
	unsigned int rm_freed;		/* map no longer has referencing ZIO */
	unsigned int rm_ecksuminjected;	/* checksum error was injected */
	raidz_impl_ops_t *rm_ops;	/* RAIDZ math operations */
	raidz_col_t rm_col[1];		/* Flexible array of I/O columns */
} raidz_map_t;

#define	RAIDZ_ORIGINAL_IMPL	(INT_MAX)

extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
#if defined(__x86_64) && defined(HAVE_SSE2)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
#endif
#if defined(__x86_64) && defined(HAVE_SSSE3)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
#endif
#if defined(__x86_64) && defined(HAVE_AVX2)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
#endif
#if defined(__aarch64__)
extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
#endif

/*
 * Commonly used raidz_map helpers
 *
 * raidz_parity		Returns parity of the RAIDZ block
 * raidz_ncols		Returns number of columns the block spans
 * raidz_nbigcols	Returns number of big columns columns
 * raidz_col_p		Returns pointer to a column
 * raidz_col_size	Returns size of a column
 * raidz_big_size	Returns size of big columns
 * raidz_short_size	Returns size of short columns
 */
#define	raidz_parity(rm)	((rm)->rm_firstdatacol)
#define	raidz_ncols(rm)		((rm)->rm_cols)
#define	raidz_nbigcols(rm)	((rm)->rm_bigcols)
#define	raidz_col_p(rm, c)	((rm)->rm_col + (c))
#define	raidz_col_size(rm, c)	((rm)->rm_col[c].rc_size)
#define	raidz_big_size(rm)	(raidz_col_size(rm, CODE_P))
#define	raidz_short_size(rm)	(raidz_col_size(rm, raidz_ncols(rm)-1))

/*
 * Macro defines an RAIDZ parity generation method
 *
 * @code	parity the function produce
 * @impl	name of the implementation
 */
#define	_RAIDZ_GEN_WRAP(code, impl) 					\
static void								\
impl ## _gen_ ## code(void *rmp)					\
{									\
	raidz_map_t *rm = (raidz_map_t *) rmp;				\
	raidz_generate_## code ## _impl(rm); 				\
}

/*
 * Macro defines an RAIDZ data reconstruction method
 *
 * @code	parity the function produce
 * @impl	name of the implementation
 */
#define	_RAIDZ_REC_WRAP(code, impl) 					\
static int 								\
impl ## _rec_ ## code(void *rmp, const int *tgtidx)			\
{									\
	raidz_map_t *rm = (raidz_map_t *) rmp;				\
	return (raidz_reconstruct_## code ## _impl(rm, tgtidx));	\
}

/*
 * Define all gen methods for an implementation
 *
 * @impl	name of the implementation
 */
#define	DEFINE_GEN_METHODS(impl)					\
	_RAIDZ_GEN_WRAP(p, impl);					\
	_RAIDZ_GEN_WRAP(pq, impl);					\
	_RAIDZ_GEN_WRAP(pqr, impl)

/*
 * Define all rec functions for an implementation
 *
 * @impl	name of the implementation
 */
#define	DEFINE_REC_METHODS(impl)					\
	_RAIDZ_REC_WRAP(p, impl);					\
	_RAIDZ_REC_WRAP(q, impl);					\
	_RAIDZ_REC_WRAP(r, impl);					\
	_RAIDZ_REC_WRAP(pq, impl);					\
	_RAIDZ_REC_WRAP(pr, impl);					\
	_RAIDZ_REC_WRAP(qr, impl);					\
	_RAIDZ_REC_WRAP(pqr, impl)

#define	RAIDZ_GEN_METHODS(impl)						\
{									\
	[RAIDZ_GEN_P] = & impl ## _gen_p,				\
	[RAIDZ_GEN_PQ] = & impl ## _gen_pq,				\
	[RAIDZ_GEN_PQR] = & impl ## _gen_pqr				\
}

#define	RAIDZ_REC_METHODS(impl)						\
{									\
	[RAIDZ_REC_P] = & impl ## _rec_p,				\
	[RAIDZ_REC_Q] = & impl ## _rec_q,				\
	[RAIDZ_REC_R] = & impl ## _rec_r,				\
	[RAIDZ_REC_PQ] = & impl ## _rec_pq,				\
	[RAIDZ_REC_PR] = & impl ## _rec_pr,				\
	[RAIDZ_REC_QR] = & impl ## _rec_qr,				\
	[RAIDZ_REC_PQR] = & impl ## _rec_pqr				\
}


typedef struct raidz_impl_kstat {
	uint64_t gen[RAIDZ_GEN_NUM];	/* gen method speed B/s */
	uint64_t rec[RAIDZ_REC_NUM];	/* rec method speed B/s */
} raidz_impl_kstat_t;

/*
 * Enumerate various multiplication constants
 * used in reconstruction methods
 */
typedef enum raidz_mul_info {
	/* Reconstruct Q */
	MUL_Q_X		= 0,
	/* Reconstruct R */
	MUL_R_X		= 0,
	/* Reconstruct PQ */
	MUL_PQ_X	= 0,
	MUL_PQ_Y	= 1,
	/* Reconstruct PR */
	MUL_PR_X	= 0,
	MUL_PR_Y	= 1,
	/* Reconstruct QR */
	MUL_QR_XQ	= 0,
	MUL_QR_X	= 1,
	MUL_QR_YQ	= 2,
	MUL_QR_Y	= 3,
	/* Reconstruct PQR */
	MUL_PQR_XP	= 0,
	MUL_PQR_XQ	= 1,
	MUL_PQR_XR	= 2,
	MUL_PQR_YU	= 3,
	MUL_PQR_YP	= 4,
	MUL_PQR_YQ	= 5,

	MUL_CNT		= 6
} raidz_mul_info_t;

/*
 * Powers of 2 in the Galois field.
 */
extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
/* Logs of 2 in the Galois field defined above. */
extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));

/*
 * Multiply a given number by 2 raised to the given power.
 */
static inline uint8_t
vdev_raidz_exp2(const uint8_t a, const unsigned exp)
{
	if (a == 0)
		return (0);

	return (vdev_raidz_pow2[(exp + (unsigned) vdev_raidz_log2[a]) % 255]);
}

/*
 * Galois Field operations.
 *
 * gf_exp2	- computes 2 raised to the given power
 * gf_exp2	- computes 4 raised to the given power
 * gf_mul	- multiplication
 * gf_div	- division
 * gf_inv	- multiplicative inverse
 */
typedef unsigned gf_t;
typedef unsigned gf_log_t;

static inline gf_t
gf_mul(const gf_t a, const gf_t b)
{
	gf_log_t logsum;

	if (a == 0 || b == 0)
		return (0);

	logsum = (gf_log_t) vdev_raidz_log2[a] + (gf_log_t) vdev_raidz_log2[b];

	return ((gf_t) vdev_raidz_pow2[logsum % 255]);
}

static inline gf_t
gf_div(const gf_t  a, const gf_t b)
{
	gf_log_t logsum;

	ASSERT3U(b, >, 0);
	if (a == 0)
		return (0);

	logsum = (gf_log_t) 255 + (gf_log_t) vdev_raidz_log2[a] -
	    (gf_log_t) vdev_raidz_log2[b];

	return ((gf_t) vdev_raidz_pow2[logsum % 255]);
}

static inline gf_t
gf_inv(const gf_t a)
{
	gf_log_t logsum;

	ASSERT3U(a, >, 0);

	logsum = (gf_log_t) 255 - (gf_log_t) vdev_raidz_log2[a];

	return ((gf_t) vdev_raidz_pow2[logsum]);
}

static inline gf_t
gf_exp2(gf_log_t exp)
{
	return (vdev_raidz_pow2[exp % 255]);
}

static inline gf_t
gf_exp4(gf_log_t exp)
{
	ASSERT3U(exp, <=, 255);
	return ((gf_t) vdev_raidz_pow2[(2 * exp) % 255]);
}

#ifdef  __cplusplus
}
#endif

#endif /* _VDEV_RAIDZ_H */