xfarray.h

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