1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #include <stdlib.h> |
3 | #include <assert.h> |
4 | #include <stdio.h> |
5 | #include <linux/types.h> |
6 | #include <linux/kernel.h> |
7 | #include <linux/bitops.h> |
8 | |
9 | #include "test.h" |
10 | |
11 | struct item * |
12 | item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) |
13 | { |
14 | return radix_tree_tag_set(root, index, tag); |
15 | } |
16 | |
17 | struct item * |
18 | item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) |
19 | { |
20 | return radix_tree_tag_clear(root, index, tag); |
21 | } |
22 | |
23 | int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag) |
24 | { |
25 | return radix_tree_tag_get(root, index, tag); |
26 | } |
27 | |
28 | struct item *item_create(unsigned long index, unsigned int order) |
29 | { |
30 | struct item *ret = malloc(sizeof(*ret)); |
31 | |
32 | ret->index = index; |
33 | ret->order = order; |
34 | return ret; |
35 | } |
36 | |
37 | int item_insert(struct radix_tree_root *root, unsigned long index) |
38 | { |
39 | struct item *item = item_create(index, order: 0); |
40 | int err = radix_tree_insert(root, index: item->index, item); |
41 | if (err) |
42 | free(item); |
43 | return err; |
44 | } |
45 | |
46 | void item_sanity(struct item *item, unsigned long index) |
47 | { |
48 | unsigned long mask; |
49 | assert(!radix_tree_is_internal_node(ptr: item)); |
50 | assert(item->order < BITS_PER_LONG); |
51 | mask = (1UL << item->order) - 1; |
52 | assert((item->index | mask) == (index | mask)); |
53 | } |
54 | |
55 | void item_free(struct item *item, unsigned long index) |
56 | { |
57 | item_sanity(item, index); |
58 | free(item); |
59 | } |
60 | |
61 | int item_delete(struct radix_tree_root *root, unsigned long index) |
62 | { |
63 | struct item *item = radix_tree_delete(root, index); |
64 | |
65 | if (!item) |
66 | return 0; |
67 | |
68 | item_free(item, index); |
69 | return 1; |
70 | } |
71 | |
72 | static void item_free_rcu(struct rcu_head *head) |
73 | { |
74 | struct item *item = container_of(head, struct item, rcu_head); |
75 | |
76 | free(item); |
77 | } |
78 | |
79 | int item_delete_rcu(struct xarray *xa, unsigned long index) |
80 | { |
81 | struct item *item = xa_erase(xa, index); |
82 | |
83 | if (item) { |
84 | item_sanity(item, index); |
85 | call_rcu(head: &item->rcu_head, func: item_free_rcu); |
86 | return 1; |
87 | } |
88 | return 0; |
89 | } |
90 | |
91 | void item_check_present(struct radix_tree_root *root, unsigned long index) |
92 | { |
93 | struct item *item; |
94 | |
95 | item = radix_tree_lookup(root, index); |
96 | assert(item != NULL); |
97 | item_sanity(item, index); |
98 | } |
99 | |
100 | struct item *item_lookup(struct radix_tree_root *root, unsigned long index) |
101 | { |
102 | return radix_tree_lookup(root, index); |
103 | } |
104 | |
105 | void item_check_absent(struct radix_tree_root *root, unsigned long index) |
106 | { |
107 | struct item *item; |
108 | |
109 | item = radix_tree_lookup(root, index); |
110 | assert(item == NULL); |
111 | } |
112 | |
113 | /* |
114 | * Scan only the passed (start, start+nr] for present items |
115 | */ |
116 | void item_gang_check_present(struct radix_tree_root *root, |
117 | unsigned long start, unsigned long nr, |
118 | int chunk, int hop) |
119 | { |
120 | struct item *items[chunk]; |
121 | unsigned long into; |
122 | |
123 | for (into = 0; into < nr; ) { |
124 | int nfound; |
125 | int nr_to_find = chunk; |
126 | int i; |
127 | |
128 | if (nr_to_find > (nr - into)) |
129 | nr_to_find = nr - into; |
130 | |
131 | nfound = radix_tree_gang_lookup(root, results: (void **)items, |
132 | first_index: start + into, max_items: nr_to_find); |
133 | assert(nfound == nr_to_find); |
134 | for (i = 0; i < nfound; i++) |
135 | assert(items[i]->index == start + into + i); |
136 | into += hop; |
137 | } |
138 | } |
139 | |
140 | /* |
141 | * Scan the entire tree, only expecting present items (start, start+nr] |
142 | */ |
143 | void item_full_scan(struct radix_tree_root *root, unsigned long start, |
144 | unsigned long nr, int chunk) |
145 | { |
146 | struct item *items[chunk]; |
147 | unsigned long into = 0; |
148 | unsigned long this_index = start; |
149 | int nfound; |
150 | int i; |
151 | |
152 | // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); |
153 | |
154 | while ((nfound = radix_tree_gang_lookup(root, results: (void **)items, first_index: into, |
155 | max_items: chunk))) { |
156 | // printf("At 0x%08lx, nfound=%d\n", into, nfound); |
157 | for (i = 0; i < nfound; i++) { |
158 | assert(items[i]->index == this_index); |
159 | this_index++; |
160 | } |
161 | // printf("Found 0x%08lx->0x%08lx\n", |
162 | // items[0]->index, items[nfound-1]->index); |
163 | into = this_index; |
164 | } |
165 | if (chunk) |
166 | assert(this_index == start + nr); |
167 | nfound = radix_tree_gang_lookup(root, results: (void **)items, |
168 | first_index: this_index, max_items: chunk); |
169 | assert(nfound == 0); |
170 | } |
171 | |
172 | /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */ |
173 | int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end, |
174 | unsigned batch, xa_mark_t iftag, xa_mark_t thentag) |
175 | { |
176 | XA_STATE(xas, xa, start); |
177 | unsigned int tagged = 0; |
178 | struct item *item; |
179 | |
180 | if (batch == 0) |
181 | batch = 1; |
182 | |
183 | xas_lock_irq(&xas); |
184 | xas_for_each_marked(&xas, item, end, iftag) { |
185 | xas_set_mark(&xas, thentag); |
186 | if (++tagged % batch) |
187 | continue; |
188 | |
189 | xas_pause(&xas); |
190 | xas_unlock_irq(&xas); |
191 | rcu_barrier(); |
192 | xas_lock_irq(&xas); |
193 | } |
194 | xas_unlock_irq(&xas); |
195 | |
196 | return tagged; |
197 | } |
198 | |
199 | static int verify_node(struct radix_tree_node *slot, unsigned int tag, |
200 | int tagged) |
201 | { |
202 | int anyset = 0; |
203 | int i; |
204 | int j; |
205 | |
206 | slot = entry_to_node(ptr: slot); |
207 | |
208 | /* Verify consistency at this level */ |
209 | for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { |
210 | if (slot->tags[tag][i]) { |
211 | anyset = 1; |
212 | break; |
213 | } |
214 | } |
215 | if (tagged != anyset) { |
216 | printf("tag: %u, shift %u, tagged: %d, anyset: %d\n" , |
217 | tag, slot->shift, tagged, anyset); |
218 | for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { |
219 | printf("tag %d: " , j); |
220 | for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) |
221 | printf("%016lx " , slot->tags[j][i]); |
222 | printf("\n" ); |
223 | } |
224 | return 1; |
225 | } |
226 | assert(tagged == anyset); |
227 | |
228 | /* Go for next level */ |
229 | if (slot->shift > 0) { |
230 | for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) |
231 | if (slot->slots[i]) |
232 | if (verify_node(slot: slot->slots[i], tag, |
233 | tagged: !!test_bit(i, slot->tags[tag]))) { |
234 | printf("Failure at off %d\n" , i); |
235 | for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { |
236 | printf("tag %d: " , j); |
237 | for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) |
238 | printf("%016lx " , slot->tags[j][i]); |
239 | printf("\n" ); |
240 | } |
241 | return 1; |
242 | } |
243 | } |
244 | return 0; |
245 | } |
246 | |
247 | void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) |
248 | { |
249 | struct radix_tree_node *node = root->xa_head; |
250 | if (!radix_tree_is_internal_node(ptr: node)) |
251 | return; |
252 | verify_node(slot: node, tag, tagged: !!root_tag_get(root, tag)); |
253 | } |
254 | |
255 | void item_kill_tree(struct xarray *xa) |
256 | { |
257 | XA_STATE(xas, xa, 0); |
258 | void *entry; |
259 | |
260 | xas_for_each(&xas, entry, ULONG_MAX) { |
261 | if (!xa_is_value(entry)) { |
262 | item_free(item: entry, index: xas.xa_index); |
263 | } |
264 | xas_store(&xas, NULL); |
265 | } |
266 | |
267 | assert(xa_empty(xa)); |
268 | } |
269 | |
270 | void tree_verify_min_height(struct radix_tree_root *root, int maxindex) |
271 | { |
272 | unsigned shift; |
273 | struct radix_tree_node *node = root->xa_head; |
274 | if (!radix_tree_is_internal_node(ptr: node)) { |
275 | assert(maxindex == 0); |
276 | return; |
277 | } |
278 | |
279 | node = entry_to_node(ptr: node); |
280 | assert(maxindex <= node_maxindex(node)); |
281 | |
282 | shift = node->shift; |
283 | if (shift > 0) |
284 | assert(maxindex > shift_maxindex(shift: shift - RADIX_TREE_MAP_SHIFT)); |
285 | else |
286 | assert(maxindex > 0); |
287 | } |
288 | |