1/* SPDX-License-Identifier: GPL-2.0-or-later */
2/*
3 * Copyright (C) 2021-2023 Oracle.  All Rights Reserved.
4 * Author: Darrick J. Wong <djwong@kernel.org>
5 */
6#ifndef __XFS_SCRUB_XFARRAY_H__
7#define __XFS_SCRUB_XFARRAY_H__
8
9/* xfile array index type, along with cursor initialization */
10typedef uint64_t		xfarray_idx_t;
11#define XFARRAY_CURSOR_INIT	((__force xfarray_idx_t)0)
12
13/* Iterate each index of an xfile array. */
14#define foreach_xfarray_idx(array, idx) \
15	for ((idx) = XFARRAY_CURSOR_INIT; \
16	     (idx) < xfarray_length(array); \
17	     (idx)++)
18
19struct xfarray {
20	/* Underlying file that backs the array. */
21	struct xfile	*xfile;
22
23	/* Number of array elements. */
24	xfarray_idx_t	nr;
25
26	/* Maximum possible array size. */
27	xfarray_idx_t	max_nr;
28
29	/* Number of unset slots in the array below @nr. */
30	uint64_t	unset_slots;
31
32	/* Size of an array element. */
33	size_t		obj_size;
34
35	/* log2 of array element size, if possible. */
36	int		obj_size_log;
37};
38
39int xfarray_create(const char *descr, unsigned long long required_capacity,
40		size_t obj_size, struct xfarray **arrayp);
41void xfarray_destroy(struct xfarray *array);
42int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
43int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
44int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
45int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
46bool xfarray_element_is_null(struct xfarray *array, const void *ptr);
47
48/*
49 * Load an array element, but zero the buffer if there's no data because we
50 * haven't stored to that array element yet.
51 */
52static inline int
53xfarray_load_sparse(
54	struct xfarray	*array,
55	uint64_t	idx,
56	void		*rec)
57{
58	int		error = xfarray_load(array, idx, rec);
59
60	if (error == -ENODATA) {
61		memset(rec, 0, array->obj_size);
62		return 0;
63	}
64	return error;
65}
66
67/* Append an element to the array. */
68static inline int xfarray_append(struct xfarray *array, const void *ptr)
69{
70	return xfarray_store(array, array->nr, ptr);
71}
72
73uint64_t xfarray_length(struct xfarray *array);
74int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);
75
76/*
77 * Iterate the non-null elements in a sparse xfarray.  Callers should
78 * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it
79 * will be set to one more than the index of the record that was retrieved.
80 * Returns 1 if a record was retrieved, 0 if there weren't any more records, or
81 * a negative errno.
82 */
83static inline int
84xfarray_iter(
85	struct xfarray	*array,
86	xfarray_idx_t	*idx,
87	void		*rec)
88{
89	int ret = xfarray_load_next(array, idx, rec);
90
91	if (ret == -ENODATA)
92		return 0;
93	if (ret == 0)
94		return 1;
95	return ret;
96}
97
98/* Declarations for xfile array sort functionality. */
99
100typedef cmp_func_t xfarray_cmp_fn;
101
102/* Perform an in-memory heapsort for small subsets. */
103#define XFARRAY_ISORT_SHIFT		(4)
104#define XFARRAY_ISORT_NR		(1U << XFARRAY_ISORT_SHIFT)
105
106/* Evalulate this many points to find the qsort pivot. */
107#define XFARRAY_QSORT_PIVOT_NR		(9)
108
109struct xfarray_sortinfo {
110	struct xfarray		*array;
111
112	/* Comparison function for the sort. */
113	xfarray_cmp_fn		cmp_fn;
114
115	/* Maximum height of the partition stack. */
116	uint8_t			max_stack_depth;
117
118	/* Current height of the partition stack. */
119	int8_t			stack_depth;
120
121	/* Maximum stack depth ever used. */
122	uint8_t			max_stack_used;
123
124	/* XFARRAY_SORT_* flags; see below. */
125	unsigned int		flags;
126
127	/* Cache a folio here for faster scanning for pivots */
128	struct folio		*folio;
129
130	/* First array index in folio that is completely readable */
131	xfarray_idx_t		first_folio_idx;
132
133	/* Last array index in folio that is completely readable */
134	xfarray_idx_t		last_folio_idx;
135
136#ifdef DEBUG
137	/* Performance statistics. */
138	uint64_t		loads;
139	uint64_t		stores;
140	uint64_t		compares;
141	uint64_t		heapsorts;
142#endif
143	/*
144	 * Extra bytes are allocated beyond the end of the structure to store
145	 * quicksort information.  C does not permit multiple VLAs per struct,
146	 * so we document all of this in a comment.
147	 *
148	 * Pretend that we have a typedef for array records:
149	 *
150	 * typedef char[array->obj_size]	xfarray_rec_t;
151	 *
152	 * First comes the quicksort partition stack:
153	 *
154	 * xfarray_idx_t	lo[max_stack_depth];
155	 * xfarray_idx_t	hi[max_stack_depth];
156	 *
157	 * union {
158	 *
159	 * If for a given subset we decide to use an in-memory sort, we use a
160	 * block of scratchpad records here to compare items:
161	 *
162	 * 	xfarray_rec_t	scratch[ISORT_NR];
163	 *
164	 * Otherwise, we want to partition the records to partition the array.
165	 * We store the chosen pivot record at the start of the scratchpad area
166	 * and use the rest to sample some records to estimate the median.
167	 * The format of the qsort_pivot array enables us to use the kernel
168	 * heapsort function to place the median value in the middle.
169	 *
170	 * 	struct {
171	 * 		xfarray_rec_t	pivot;
172	 * 		struct {
173	 *			xfarray_rec_t	rec;  (rounded up to 8 bytes)
174	 * 			xfarray_idx_t	idx;
175	 *		} qsort_pivot[QSORT_PIVOT_NR];
176	 * 	};
177	 * }
178	 */
179};
180
181/* Sort can be interrupted by a fatal signal. */
182#define XFARRAY_SORT_KILLABLE	(1U << 0)
183
184int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
185		unsigned int flags);
186
187#endif /* __XFS_SCRUB_XFARRAY_H__ */
188