summaryrefslogtreecommitdiffstats
path: root/fs/xfs/scrub/xfarray.h
blob: acb2f94c56c13da8ea3775f28c6b36fd32690ccf (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
/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
 * Copyright (C) 2021-2023 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <djwong@kernel.org>
 */
#ifndef __XFS_SCRUB_XFARRAY_H__
#define __XFS_SCRUB_XFARRAY_H__

/* xfile array index type, along with cursor initialization */
typedef uint64_t		xfarray_idx_t;
#define XFARRAY_CURSOR_INIT	((__force xfarray_idx_t)0)

/* Iterate each index of an xfile array. */
#define foreach_xfarray_idx(array, idx) \
	for ((idx) = XFARRAY_CURSOR_INIT; \
	     (idx) < xfarray_length(array); \
	     (idx)++)

struct xfarray {
	/* Underlying file that backs the array. */
	struct xfile	*xfile;

	/* Number of array elements. */
	xfarray_idx_t	nr;

	/* Maximum possible array size. */
	xfarray_idx_t	max_nr;

	/* Number of unset slots in the array below @nr. */
	uint64_t	unset_slots;

	/* Size of an array element. */
	size_t		obj_size;

	/* log2 of array element size, if possible. */
	int		obj_size_log;
};

int xfarray_create(const char *descr, unsigned long long required_capacity,
		size_t obj_size, struct xfarray **arrayp);
void xfarray_destroy(struct xfarray *array);
int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
bool xfarray_element_is_null(struct xfarray *array, const void *ptr);

/*
 * Load an array element, but zero the buffer if there's no data because we
 * haven't stored to that array element yet.
 */
static inline int
xfarray_load_sparse(
	struct xfarray	*array,
	uint64_t	idx,
	void		*rec)
{
	int		error = xfarray_load(array, idx, rec);

	if (error == -ENODATA) {
		memset(rec, 0, array->obj_size);
		return 0;
	}
	return error;
}

/* Append an element to the array. */
static inline int xfarray_append(struct xfarray *array, const void *ptr)
{
	return xfarray_store(array, array->nr, ptr);
}

uint64_t xfarray_length(struct xfarray *array);
int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);

/*
 * Iterate the non-null elements in a sparse xfarray.  Callers should
 * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it
 * will be set to one more than the index of the record that was retrieved.
 * Returns 1 if a record was retrieved, 0 if there weren't any more records, or
 * a negative errno.
 */
static inline int
xfarray_iter(
	struct xfarray	*array,
	xfarray_idx_t	*idx,
	void		*rec)
{
	int ret = xfarray_load_next(array, idx, rec);

	if (ret == -ENODATA)
		return 0;
	if (ret == 0)
		return 1;
	return ret;
}

/* Declarations for xfile array sort functionality. */

typedef cmp_func_t xfarray_cmp_fn;

/* Perform an in-memory heapsort for small subsets. */
#define XFARRAY_ISORT_SHIFT		(4)
#define XFARRAY_ISORT_NR		(1U << XFARRAY_ISORT_SHIFT)

/* Evalulate this many points to find the qsort pivot. */
#define XFARRAY_QSORT_PIVOT_NR		(9)

struct xfarray_sortinfo {
	struct xfarray		*array;

	/* Comparison function for the sort. */
	xfarray_cmp_fn		cmp_fn;

	/* Maximum height of the partition stack. */
	uint8_t			max_stack_depth;

	/* Current height of the partition stack. */
	int8_t			stack_depth;

	/* Maximum stack depth ever used. */
	uint8_t			max_stack_used;

	/* XFARRAY_SORT_* flags; see below. */
	unsigned int		flags;

	/* Cache a folio here for faster scanning for pivots */
	struct folio		*folio;

	/* First array index in folio that is completely readable */
	xfarray_idx_t		first_folio_idx;

	/* Last array index in folio that is completely readable */
	xfarray_idx_t		last_folio_idx;

#ifdef DEBUG
	/* Performance statistics. */
	uint64_t		loads;
	uint64_t		stores;
	uint64_t		compares;
	uint64_t		heapsorts;
#endif
	/*
	 * Extra bytes are allocated beyond the end of the structure to store
	 * quicksort information.  C does not permit multiple VLAs per struct,
	 * so we document all of this in a comment.
	 *
	 * Pretend that we have a typedef for array records:
	 *
	 * typedef char[array->obj_size]	xfarray_rec_t;
	 *
	 * First comes the quicksort partition stack:
	 *
	 * xfarray_idx_t	lo[max_stack_depth];
	 * xfarray_idx_t	hi[max_stack_depth];
	 *
	 * union {
	 *
	 * If for a given subset we decide to use an in-memory sort, we use a
	 * block of scratchpad records here to compare items:
	 *
	 * 	xfarray_rec_t	scratch[ISORT_NR];
	 *
	 * Otherwise, we want to partition the records to partition the array.
	 * We store the chosen pivot record at the start of the scratchpad area
	 * and use the rest to sample some records to estimate the median.
	 * The format of the qsort_pivot array enables us to use the kernel
	 * heapsort function to place the median value in the middle.
	 *
	 * 	struct {
	 * 		xfarray_rec_t	pivot;
	 * 		struct {
	 *			xfarray_rec_t	rec;  (rounded up to 8 bytes)
	 * 			xfarray_idx_t	idx;
	 *		} qsort_pivot[QSORT_PIVOT_NR];
	 * 	};
	 * }
	 */
};

/* Sort can be interrupted by a fatal signal. */
#define XFARRAY_SORT_KILLABLE	(1U << 0)

int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
		unsigned int flags);

#endif /* __XFS_SCRUB_XFARRAY_H__ */