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 unsigned order)
29{
30 return __radix_tree_insert(root, item->index, order, item);
31}
32
33int item_insert(struct radix_tree_root *root, unsigned long index)
34{
35 return __item_insert(root, item_create(index), 0);
36}
37
38int item_insert_order(struct radix_tree_root *root, unsigned long index,
39 unsigned order)
40{
41 return __item_insert(root, item_create(index), order);
42}
43
44int item_delete(struct radix_tree_root *root, unsigned long index)
45{
46 struct item *item = radix_tree_delete(root, index);
47
48 if (item) {
49 assert(item->index == index);
50 free(item);
51 return 1;
52 }
53 return 0;
54}
55
56struct item *item_create(unsigned long index)
57{
58 struct item *ret = malloc(sizeof(*ret));
59
60 ret->index = index;
61 return ret;
62}
63
64void item_check_present(struct radix_tree_root *root, unsigned long index)
65{
66 struct item *item;
67
68 item = radix_tree_lookup(root, index);
69 assert(item != 0);
70 assert(item->index == index);
71}
72
73struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
74{
75 return radix_tree_lookup(root, index);
76}
77
78void item_check_absent(struct radix_tree_root *root, unsigned long index)
79{
80 struct item *item;
81
82 item = radix_tree_lookup(root, index);
83 assert(item == 0);
84}
85
86
87
88
89void item_gang_check_present(struct radix_tree_root *root,
90 unsigned long start, unsigned long nr,
91 int chunk, int hop)
92{
93 struct item *items[chunk];
94 unsigned long into;
95
96 for (into = 0; into < nr; ) {
97 int nfound;
98 int nr_to_find = chunk;
99 int i;
100
101 if (nr_to_find > (nr - into))
102 nr_to_find = nr - into;
103
104 nfound = radix_tree_gang_lookup(root, (void **)items,
105 start + into, nr_to_find);
106 assert(nfound == nr_to_find);
107 for (i = 0; i < nfound; i++)
108 assert(items[i]->index == start + into + i);
109 into += hop;
110 }
111}
112
113
114
115
116void item_full_scan(struct radix_tree_root *root, unsigned long start,
117 unsigned long nr, int chunk)
118{
119 struct item *items[chunk];
120 unsigned long into = 0;
121 unsigned long this_index = start;
122 int nfound;
123 int i;
124
125
126
127 while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
128 chunk))) {
129
130 for (i = 0; i < nfound; i++) {
131 assert(items[i]->index == this_index);
132 this_index++;
133 }
134
135
136 into = this_index;
137 }
138 if (chunk)
139 assert(this_index == start + nr);
140 nfound = radix_tree_gang_lookup(root, (void **)items,
141 this_index, chunk);
142 assert(nfound == 0);
143}
144
145static int verify_node(struct radix_tree_node *slot, unsigned int tag,
146 int tagged)
147{
148 int anyset = 0;
149 int i;
150 int j;
151
152 slot = entry_to_node(slot);
153
154
155 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
156 if (slot->tags[tag][i]) {
157 anyset = 1;
158 break;
159 }
160 }
161 if (tagged != anyset) {
162 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
163 tag, slot->shift, tagged, anyset);
164 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
165 printf("tag %d: ", j);
166 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
167 printf("%016lx ", slot->tags[j][i]);
168 printf("\n");
169 }
170 return 1;
171 }
172 assert(tagged == anyset);
173
174
175 if (slot->shift > 0) {
176 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
177 if (slot->slots[i])
178 if (verify_node(slot->slots[i], tag,
179 !!test_bit(i, slot->tags[tag]))) {
180 printf("Failure at off %d\n", i);
181 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
182 printf("tag %d: ", j);
183 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
184 printf("%016lx ", slot->tags[j][i]);
185 printf("\n");
186 }
187 return 1;
188 }
189 }
190 return 0;
191}
192
193void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
194{
195 struct radix_tree_node *node = root->rnode;
196 if (!radix_tree_is_internal_node(node))
197 return;
198 verify_node(node, tag, !!root_tag_get(root, tag));
199}
200
201void item_kill_tree(struct radix_tree_root *root)
202{
203 struct item *items[32];
204 int nfound;
205
206 while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
207 int i;
208
209 for (i = 0; i < nfound; i++) {
210 void *ret;
211
212 ret = radix_tree_delete(root, items[i]->index);
213 assert(ret == items[i]);
214 free(items[i]);
215 }
216 }
217 assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
218 assert(root->rnode == NULL);
219}
220
221void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
222{
223 unsigned shift;
224 struct radix_tree_node *node = root->rnode;
225 if (!radix_tree_is_internal_node(node)) {
226 assert(maxindex == 0);
227 return;
228 }
229
230 node = entry_to_node(node);
231 assert(maxindex <= node_maxindex(node));
232
233 shift = node->shift;
234 if (shift > 0)
235 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
236 else
237 assert(maxindex > 0);
238}
239
