1b2441318SGreg Kroah-Hartman /* SPDX-License-Identifier: GPL-2.0 */ 21366c37eSMatthew Wilcox #include <linux/gfp.h> 31366c37eSMatthew Wilcox #include <linux/types.h> 41366c37eSMatthew Wilcox #include <linux/radix-tree.h> 51366c37eSMatthew Wilcox #include <linux/rcupdate.h> 61366c37eSMatthew Wilcox 71366c37eSMatthew Wilcox struct item { 83e252fa7SRoss Zwisler struct rcu_head rcu_head; 91366c37eSMatthew Wilcox unsigned long index; 10101d9607SMatthew Wilcox unsigned int order; 111366c37eSMatthew Wilcox }; 121366c37eSMatthew Wilcox 13101d9607SMatthew Wilcox struct item *item_create(unsigned long index, unsigned int order); 141366c37eSMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index); 15fd8f58c4SRoss Zwisler void item_sanity(struct item *item, unsigned long index); 1647e0fab2SMatthew Wilcox void item_free(struct item *item, unsigned long index); 171366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index); 18b66b5a48SMatthew Wilcox int item_delete_rcu(struct xarray *xa, unsigned long index); 191366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index); 201366c37eSMatthew Wilcox 211366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index); 221366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index); 231366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 241366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 251366c37eSMatthew Wilcox int chunk, int hop); 261366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 271366c37eSMatthew Wilcox unsigned long nr, int chunk); 281366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root); 291366c37eSMatthew Wilcox 30372266baSMatthew Wilcox int tag_tagged_items(struct xarray *, unsigned long start, unsigned long end, 31372266baSMatthew Wilcox unsigned batch, xa_mark_t iftag, xa_mark_t thentag); 32478922e2SMatthew Wilcox 33ad3d6c72SMatthew Wilcox void xarray_tests(void); 341366c37eSMatthew Wilcox void tag_check(void); 354f3755d1SMatthew Wilcox void multiorder_checks(void); 363e3cdc68SMatthew Wilcox void iteration_test(unsigned order, unsigned duration); 377e934cf5SMatthew Wilcox (Oracle) void iteration_test2(unsigned duration); 38cfa40bcfSKonstantin Khlebnikov void benchmark(void); 390a835c4fSMatthew Wilcox void idr_checks(void); 408ab8ba38SMatthew Wilcox void ida_tests(void); 411366c37eSMatthew Wilcox 421366c37eSMatthew Wilcox struct item * 431366c37eSMatthew Wilcox item_tag_set(struct radix_tree_root *root, unsigned long index, int tag); 441366c37eSMatthew Wilcox struct item * 451366c37eSMatthew Wilcox item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag); 461366c37eSMatthew Wilcox int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag); 471366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex); 481366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag); 491366c37eSMatthew Wilcox 501366c37eSMatthew Wilcox extern int nr_allocated; 511366c37eSMatthew Wilcox 521366c37eSMatthew Wilcox /* Normally private parts of lib/radix-tree.c */ 53148deab2SMatthew Wilcox struct radix_tree_node *entry_to_node(void *ptr); 540796c583SRoss Zwisler void radix_tree_dump(struct radix_tree_root *root); 551366c37eSMatthew Wilcox int root_tag_get(struct radix_tree_root *root, unsigned int tag); 560694f0c9SMatthew Wilcox unsigned long node_maxindex(struct radix_tree_node *); 570694f0c9SMatthew Wilcox unsigned long shift_maxindex(unsigned int shift); 586df5ee78SMatthew Wilcox int radix_tree_cpu_dead(unsigned int cpu); 592791653aSMatthew Wilcox extern struct radix_tree_preload radix_tree_preloads; 60