1#include <stdlib.h>
  2#include <assert.h>
  3#include <stdio.h>
  4#include <linux/types.h>
  5#include <linux/kernel.h>
  6#include <linux/bitops.h>
  7
  8#include "test.h"
  9
 10struct item *
 11item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
 12{
 13	return radix_tree_tag_set(root, index, tag);
 14}
 15
 16struct item *
 17item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
 18{
 19	return radix_tree_tag_clear(root, index, tag);
 20}
 21
 22int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
 23{
 24	return radix_tree_tag_get(root, index, tag);
 25}
 26
 27int __item_insert(struct radix_tree_root *root, struct item *item)
 28{
 29	return radix_tree_insert(root, item->index, item);
 30}
 31
 32int item_insert(struct radix_tree_root *root, unsigned long index)
 33{
 34	return __item_insert(root, item_create(index));
 35}
 36
 37int item_delete(struct radix_tree_root *root, unsigned long index)
 38{
 39	struct item *item = radix_tree_delete(root, index);
 40
 41	if (item) {
 42		assert(item->index == index);
 43		free(item);
 44		return 1;
 45	}
 46	return 0;
 47}
 48
 49struct item *item_create(unsigned long index)
 50{
 51	struct item *ret = malloc(sizeof(*ret));
 52
 53	ret->index = index;
 54	return ret;
 55}
 56
 57void item_check_present(struct radix_tree_root *root, unsigned long index)
 58{
 59	struct item *item;
 60
 61	item = radix_tree_lookup(root, index);
 62	assert(item != 0);
 63	assert(item->index == index);
 64}
 65
 66struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
 67{
 68	return radix_tree_lookup(root, index);
 69}
 70
 71void item_check_absent(struct radix_tree_root *root, unsigned long index)
 72{
 73	struct item *item;
 74
 75	item = radix_tree_lookup(root, index);
 76	assert(item == 0);
 77}
 78
 79/*
 80 * Scan only the passed (start, start+nr] for present items
 81 */
 82void item_gang_check_present(struct radix_tree_root *root,
 83			unsigned long start, unsigned long nr,
 84			int chunk, int hop)
 85{
 86	struct item *items[chunk];
 87	unsigned long into;
 88
 89	for (into = 0; into < nr; ) {
 90		int nfound;
 91		int nr_to_find = chunk;
 92		int i;
 93
 94		if (nr_to_find > (nr - into))
 95			nr_to_find = nr - into;
 96
 97		nfound = radix_tree_gang_lookup(root, (void **)items,
 98						start + into, nr_to_find);
 99		assert(nfound == nr_to_find);
100		for (i = 0; i < nfound; i++)
101			assert(items[i]->index == start + into + i);
102		into += hop;
103	}
104}
105
106/*
107 * Scan the entire tree, only expecting present items (start, start+nr]
108 */
109void item_full_scan(struct radix_tree_root *root, unsigned long start,
110			unsigned long nr, int chunk)
111{
112	struct item *items[chunk];
113	unsigned long into = 0;
114	unsigned long this_index = start;
115	int nfound;
116	int i;
117
118//	printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
119
120	while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
121					chunk))) {
122//		printf("At 0x%08lx, nfound=%d\n", into, nfound);
123		for (i = 0; i < nfound; i++) {
124			assert(items[i]->index == this_index);
125			this_index++;
126		}
127//		printf("Found 0x%08lx->0x%08lx\n",
128//			items[0]->index, items[nfound-1]->index);
129		into = this_index;
130	}
131	if (chunk)
132		assert(this_index == start + nr);
133	nfound = radix_tree_gang_lookup(root, (void **)items,
134					this_index, chunk);
135	assert(nfound == 0);
136}
137
138static int verify_node(struct radix_tree_node *slot, unsigned int tag,
139			unsigned int height, int tagged)
140{
141	int anyset = 0;
142	int i;
143	int j;
144
145	slot = indirect_to_ptr(slot);
146
147	/* Verify consistency at this level */
148	for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
149		if (slot->tags[tag][i]) {
150			anyset = 1;
151			break;
152		}
153	}
154	if (tagged != anyset) {
155		printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset);
156		for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
157			printf("tag %d: ", j);
158			for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
159				printf("%016lx ", slot->tags[j][i]);
160			printf("\n");
161		}
162		return 1;
163	}
164	assert(tagged == anyset);
165
166	/* Go for next level */
167	if (height > 1) {
168		for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
169			if (slot->slots[i])
170				if (verify_node(slot->slots[i], tag, height - 1,
171					    !!test_bit(i, slot->tags[tag]))) {
172					printf("Failure at off %d\n", i);
173					for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
174						printf("tag %d: ", j);
175						for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
176							printf("%016lx ", slot->tags[j][i]);
177						printf("\n");
178					}
179					return 1;
180				}
181	}
182	return 0;
183}
184
185void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
186{
187	if (!root->height)
188		return;
189	verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag));
190}
191
192void item_kill_tree(struct radix_tree_root *root)
193{
194	struct item *items[32];
195	int nfound;
196
197	while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
198		int i;
199
200		for (i = 0; i < nfound; i++) {
201			void *ret;
202
203			ret = radix_tree_delete(root, items[i]->index);
204			assert(ret == items[i]);
205			free(items[i]);
206		}
207	}
208	assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
209	assert(root->rnode == NULL);
210}
211
212void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
213{
214	assert(radix_tree_maxindex(root->height) >= maxindex);
215	if (root->height > 1)
216		assert(radix_tree_maxindex(root->height-1) < maxindex);
217	else if (root->height == 1)
218		assert(radix_tree_maxindex(root->height-1) <= maxindex);
219}