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 /*
58 * Iterate the non-null elements in a sparse xfarray. Callers should
59 * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it
60 * will be set to one more than the index of the record that was retrieved.
61 * Returns 1 if a record was retrieved, 0 if there weren't any more records, or
62 * a negative errno.
63 */
64 static inline int
xfarray_iter(struct xfarray * array,xfarray_idx_t * idx,void * rec)65 xfarray_iter(
66 struct xfarray *array,
67 xfarray_idx_t *idx,
68 void *rec)
69 {
70 int ret = xfarray_load_next(array, idx, rec);
71
72 if (ret == -ENODATA)
73 return 0;
74 if (ret == 0)
75 return 1;
76 return ret;
77 }
78
79 /* Declarations for xfile array sort functionality. */
80
81 typedef cmp_func_t xfarray_cmp_fn;
82
83 /* Perform an in-memory heapsort for small subsets. */
84 #define XFARRAY_ISORT_SHIFT (4)
85 #define XFARRAY_ISORT_NR (1U << XFARRAY_ISORT_SHIFT)
86
87 /* Evalulate this many points to find the qsort pivot. */
88 #define XFARRAY_QSORT_PIVOT_NR (9)
89
90 struct xfarray_sortinfo {
91 struct xfarray *array;
92
93 /* Comparison function for the sort. */
94 xfarray_cmp_fn cmp_fn;
95
96 /* Maximum height of the partition stack. */
97 uint8_t max_stack_depth;
98
99 /* Current height of the partition stack. */
100 int8_t stack_depth;
101
102 /* Maximum stack depth ever used. */
103 uint8_t max_stack_used;
104
105 /* XFARRAY_SORT_* flags; see below. */
106 unsigned int flags;
107
108 /* Cache a page here for faster access. */
109 struct xfile_page xfpage;
110 void *page_kaddr;
111
112 #ifdef DEBUG
113 /* Performance statistics. */
114 uint64_t loads;
115 uint64_t stores;
116 uint64_t compares;
117 uint64_t heapsorts;
118 #endif
119 /*
120 * Extra bytes are allocated beyond the end of the structure to store
121 * quicksort information. C does not permit multiple VLAs per struct,
122 * so we document all of this in a comment.
123 *
124 * Pretend that we have a typedef for array records:
125 *
126 * typedef char[array->obj_size] xfarray_rec_t;
127 *
128 * First comes the quicksort partition stack:
129 *
130 * xfarray_idx_t lo[max_stack_depth];
131 * xfarray_idx_t hi[max_stack_depth];
132 *
133 * union {
134 *
135 * If for a given subset we decide to use an in-memory sort, we use a
136 * block of scratchpad records here to compare items:
137 *
138 * xfarray_rec_t scratch[ISORT_NR];
139 *
140 * Otherwise, we want to partition the records to partition the array.
141 * We store the chosen pivot record at the start of the scratchpad area
142 * and use the rest to sample some records to estimate the median.
143 * The format of the qsort_pivot array enables us to use the kernel
144 * heapsort function to place the median value in the middle.
145 *
146 * struct {
147 * xfarray_rec_t pivot;
148 * struct {
149 * xfarray_rec_t rec; (rounded up to 8 bytes)
150 * xfarray_idx_t idx;
151 * } qsort_pivot[QSORT_PIVOT_NR];
152 * };
153 * }
154 */
155 };
156
157 /* Sort can be interrupted by a fatal signal. */
158 #define XFARRAY_SORT_KILLABLE (1U << 0)
159
160 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
161 unsigned int flags);
162
163 #endif /* __XFS_SCRUB_XFARRAY_H__ */
164