]>
git.proxmox.com Git - mirror_ubuntu-focal-kernel.git/blob - tools/testing/radix-tree/test.c
4 #include <linux/types.h>
5 #include <linux/kernel.h>
6 #include <linux/bitops.h>
11 item_tag_set(struct radix_tree_root
*root
, unsigned long index
, int tag
)
13 return radix_tree_tag_set(root
, index
, tag
);
17 item_tag_clear(struct radix_tree_root
*root
, unsigned long index
, int tag
)
19 return radix_tree_tag_clear(root
, index
, tag
);
22 int item_tag_get(struct radix_tree_root
*root
, unsigned long index
, int tag
)
24 return radix_tree_tag_get(root
, index
, tag
);
27 int __item_insert(struct radix_tree_root
*root
, struct item
*item
)
29 return __radix_tree_insert(root
, item
->index
, item
->order
, item
);
32 struct item
*item_create(unsigned long index
, unsigned int order
)
34 struct item
*ret
= malloc(sizeof(*ret
));
41 int item_insert_order(struct radix_tree_root
*root
, unsigned long index
,
44 struct item
*item
= item_create(index
, order
);
45 int err
= __item_insert(root
, item
);
51 int item_insert(struct radix_tree_root
*root
, unsigned long index
)
53 return item_insert_order(root
, index
, 0);
56 void item_sanity(struct item
*item
, unsigned long index
)
59 assert(!radix_tree_is_internal_node(item
));
60 assert(item
->order
< BITS_PER_LONG
);
61 mask
= (1UL << item
->order
) - 1;
62 assert((item
->index
| mask
) == (index
| mask
));
65 int item_delete(struct radix_tree_root
*root
, unsigned long index
)
67 struct item
*item
= radix_tree_delete(root
, index
);
70 item_sanity(item
, index
);
77 void item_check_present(struct radix_tree_root
*root
, unsigned long index
)
81 item
= radix_tree_lookup(root
, index
);
83 item_sanity(item
, index
);
86 struct item
*item_lookup(struct radix_tree_root
*root
, unsigned long index
)
88 return radix_tree_lookup(root
, index
);
91 void item_check_absent(struct radix_tree_root
*root
, unsigned long index
)
95 item
= radix_tree_lookup(root
, index
);
100 * Scan only the passed (start, start+nr] for present items
102 void item_gang_check_present(struct radix_tree_root
*root
,
103 unsigned long start
, unsigned long nr
,
106 struct item
*items
[chunk
];
109 for (into
= 0; into
< nr
; ) {
111 int nr_to_find
= chunk
;
114 if (nr_to_find
> (nr
- into
))
115 nr_to_find
= nr
- into
;
117 nfound
= radix_tree_gang_lookup(root
, (void **)items
,
118 start
+ into
, nr_to_find
);
119 assert(nfound
== nr_to_find
);
120 for (i
= 0; i
< nfound
; i
++)
121 assert(items
[i
]->index
== start
+ into
+ i
);
127 * Scan the entire tree, only expecting present items (start, start+nr]
129 void item_full_scan(struct radix_tree_root
*root
, unsigned long start
,
130 unsigned long nr
, int chunk
)
132 struct item
*items
[chunk
];
133 unsigned long into
= 0;
134 unsigned long this_index
= start
;
138 // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
140 while ((nfound
= radix_tree_gang_lookup(root
, (void **)items
, into
,
142 // printf("At 0x%08lx, nfound=%d\n", into, nfound);
143 for (i
= 0; i
< nfound
; i
++) {
144 assert(items
[i
]->index
== this_index
);
147 // printf("Found 0x%08lx->0x%08lx\n",
148 // items[0]->index, items[nfound-1]->index);
152 assert(this_index
== start
+ nr
);
153 nfound
= radix_tree_gang_lookup(root
, (void **)items
,
158 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
159 int tag_tagged_items(struct radix_tree_root
*root
, pthread_mutex_t
*lock
,
160 unsigned long start
, unsigned long end
, unsigned batch
,
161 unsigned iftag
, unsigned thentag
)
163 unsigned long tagged
= 0;
164 struct radix_tree_iter iter
;
171 pthread_mutex_lock(lock
);
172 radix_tree_for_each_tagged(slot
, root
, &iter
, start
, iftag
) {
173 if (iter
.index
> end
)
175 radix_tree_iter_tag_set(root
, &iter
, thentag
);
177 if ((tagged
% batch
) != 0)
179 slot
= radix_tree_iter_resume(slot
, &iter
);
181 pthread_mutex_unlock(lock
);
183 pthread_mutex_lock(lock
);
187 pthread_mutex_unlock(lock
);
192 /* Use the same pattern as find_swap_entry() in mm/shmem.c */
193 unsigned long find_item(struct radix_tree_root
*root
, void *item
)
195 struct radix_tree_iter iter
;
197 unsigned long found
= -1;
198 unsigned long checked
= 0;
200 radix_tree_for_each_slot(slot
, root
, &iter
, 0) {
206 if ((checked
% 4) != 0)
208 slot
= radix_tree_iter_resume(slot
, &iter
);
214 static int verify_node(struct radix_tree_node
*slot
, unsigned int tag
,
221 slot
= entry_to_node(slot
);
223 /* Verify consistency at this level */
224 for (i
= 0; i
< RADIX_TREE_TAG_LONGS
; i
++) {
225 if (slot
->tags
[tag
][i
]) {
230 if (tagged
!= anyset
) {
231 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
232 tag
, slot
->shift
, tagged
, anyset
);
233 for (j
= 0; j
< RADIX_TREE_MAX_TAGS
; j
++) {
234 printf("tag %d: ", j
);
235 for (i
= 0; i
< RADIX_TREE_TAG_LONGS
; i
++)
236 printf("%016lx ", slot
->tags
[j
][i
]);
241 assert(tagged
== anyset
);
243 /* Go for next level */
244 if (slot
->shift
> 0) {
245 for (i
= 0; i
< RADIX_TREE_MAP_SIZE
; i
++)
247 if (verify_node(slot
->slots
[i
], tag
,
248 !!test_bit(i
, slot
->tags
[tag
]))) {
249 printf("Failure at off %d\n", i
);
250 for (j
= 0; j
< RADIX_TREE_MAX_TAGS
; j
++) {
251 printf("tag %d: ", j
);
252 for (i
= 0; i
< RADIX_TREE_TAG_LONGS
; i
++)
253 printf("%016lx ", slot
->tags
[j
][i
]);
262 void verify_tag_consistency(struct radix_tree_root
*root
, unsigned int tag
)
264 struct radix_tree_node
*node
= root
->rnode
;
265 if (!radix_tree_is_internal_node(node
))
267 verify_node(node
, tag
, !!root_tag_get(root
, tag
));
270 void item_kill_tree(struct radix_tree_root
*root
)
272 struct radix_tree_iter iter
;
274 struct item
*items
[32];
277 radix_tree_for_each_slot(slot
, root
, &iter
, 0) {
278 if (radix_tree_exceptional_entry(*slot
))
279 radix_tree_delete(root
, iter
.index
);
282 while ((nfound
= radix_tree_gang_lookup(root
, (void **)items
, 0, 32))) {
285 for (i
= 0; i
< nfound
; i
++) {
288 ret
= radix_tree_delete(root
, items
[i
]->index
);
289 assert(ret
== items
[i
]);
293 assert(radix_tree_gang_lookup(root
, (void **)items
, 0, 32) == 0);
294 assert(root
->rnode
== NULL
);
297 void tree_verify_min_height(struct radix_tree_root
*root
, int maxindex
)
300 struct radix_tree_node
*node
= root
->rnode
;
301 if (!radix_tree_is_internal_node(node
)) {
302 assert(maxindex
== 0);
306 node
= entry_to_node(node
);
307 assert(maxindex
<= node_maxindex(node
));
311 assert(maxindex
> shift_maxindex(shift
- RADIX_TREE_MAP_SHIFT
));
313 assert(maxindex
> 0);