Orange Pi5 kernel

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