Loading...
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__ */
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__ */