xref: /openbmc/linux/fs/xfs/scrub/xfarray.h (revision 764018ca)
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 */
10 typedef 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 
19 struct 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 
39 int xfarray_create(const char *descr, unsigned long long required_capacity,
40 		size_t obj_size, struct xfarray **arrayp);
41 void xfarray_destroy(struct xfarray *array);
42 int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
43 int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
44 int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
45 int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
46 bool xfarray_element_is_null(struct xfarray *array, const void *ptr);
47 
48 /* Append an element to the array. */
xfarray_append(struct xfarray * array,const void * ptr)49 static inline int xfarray_append(struct xfarray *array, const void *ptr)
50 {
51 	return xfarray_store(array, array->nr, ptr);
52 }
53 
54 uint64_t xfarray_length(struct xfarray *array);
55 int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);
56 
57 /* Declarations for xfile array sort functionality. */
58 
59 typedef cmp_func_t xfarray_cmp_fn;
60 
61 /* Perform an in-memory heapsort for small subsets. */
62 #define XFARRAY_ISORT_SHIFT		(4)
63 #define XFARRAY_ISORT_NR		(1U << XFARRAY_ISORT_SHIFT)
64 
65 /* Evalulate this many points to find the qsort pivot. */
66 #define XFARRAY_QSORT_PIVOT_NR		(9)
67 
68 struct xfarray_sortinfo {
69 	struct xfarray		*array;
70 
71 	/* Comparison function for the sort. */
72 	xfarray_cmp_fn		cmp_fn;
73 
74 	/* Maximum height of the partition stack. */
75 	uint8_t			max_stack_depth;
76 
77 	/* Current height of the partition stack. */
78 	int8_t			stack_depth;
79 
80 	/* Maximum stack depth ever used. */
81 	uint8_t			max_stack_used;
82 
83 	/* XFARRAY_SORT_* flags; see below. */
84 	unsigned int		flags;
85 
86 	/* Cache a page here for faster access. */
87 	struct xfile_page	xfpage;
88 	void			*page_kaddr;
89 
90 #ifdef DEBUG
91 	/* Performance statistics. */
92 	uint64_t		loads;
93 	uint64_t		stores;
94 	uint64_t		compares;
95 	uint64_t		heapsorts;
96 #endif
97 	/*
98 	 * Extra bytes are allocated beyond the end of the structure to store
99 	 * quicksort information.  C does not permit multiple VLAs per struct,
100 	 * so we document all of this in a comment.
101 	 *
102 	 * Pretend that we have a typedef for array records:
103 	 *
104 	 * typedef char[array->obj_size]	xfarray_rec_t;
105 	 *
106 	 * First comes the quicksort partition stack:
107 	 *
108 	 * xfarray_idx_t	lo[max_stack_depth];
109 	 * xfarray_idx_t	hi[max_stack_depth];
110 	 *
111 	 * union {
112 	 *
113 	 * If for a given subset we decide to use an in-memory sort, we use a
114 	 * block of scratchpad records here to compare items:
115 	 *
116 	 * 	xfarray_rec_t	scratch[ISORT_NR];
117 	 *
118 	 * Otherwise, we want to partition the records to partition the array.
119 	 * We store the chosen pivot record at the start of the scratchpad area
120 	 * and use the rest to sample some records to estimate the median.
121 	 * The format of the qsort_pivot array enables us to use the kernel
122 	 * heapsort function to place the median value in the middle.
123 	 *
124 	 * 	struct {
125 	 * 		xfarray_rec_t	pivot;
126 	 * 		struct {
127 	 *			xfarray_rec_t	rec;  (rounded up to 8 bytes)
128 	 * 			xfarray_idx_t	idx;
129 	 *		} qsort_pivot[QSORT_PIVOT_NR];
130 	 * 	};
131 	 * }
132 	 */
133 };
134 
135 /* Sort can be interrupted by a fatal signal. */
136 #define XFARRAY_SORT_KILLABLE	(1U << 0)
137 
138 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
139 		unsigned int flags);
140 
141 #endif /* __XFS_SCRUB_XFARRAY_H__ */
142