Loading...
Note: File does not exist in v3.1.
1#include <stdio.h>
2#include <stdlib.h>
3#include <unistd.h>
4#include <time.h>
5#include <assert.h>
6
7#include <linux/slab.h>
8#include <linux/radix-tree.h>
9
10#include "test.h"
11#include "regression.h"
12
13void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
14{
15 long idx;
16 RADIX_TREE(tree, GFP_KERNEL);
17
18 middle = 1 << 30;
19
20 for (idx = -down; idx < up; idx++)
21 item_insert(&tree, middle + idx);
22
23 item_check_absent(&tree, middle - down - 1);
24 for (idx = -down; idx < up; idx++)
25 item_check_present(&tree, middle + idx);
26 item_check_absent(&tree, middle + up);
27
28 item_gang_check_present(&tree, middle - down,
29 up + down, chunk, hop);
30 item_full_scan(&tree, middle - down, down + up, chunk);
31 item_kill_tree(&tree);
32}
33
34void gang_check(void)
35{
36 __gang_check(1 << 30, 128, 128, 35, 2);
37 __gang_check(1 << 31, 128, 128, 32, 32);
38 __gang_check(1 << 31, 128, 128, 32, 100);
39 __gang_check(1 << 31, 128, 128, 17, 7);
40 __gang_check(0xffff0000, 0, 65536, 17, 7);
41 __gang_check(0xfffffffe, 1, 1, 17, 7);
42}
43
44void __big_gang_check(void)
45{
46 unsigned long start;
47 int wrapped = 0;
48
49 start = 0;
50 do {
51 unsigned long old_start;
52
53// printf("0x%08lx\n", start);
54 __gang_check(start, rand() % 113 + 1, rand() % 71,
55 rand() % 157, rand() % 91 + 1);
56 old_start = start;
57 start += rand() % 1000000;
58 start %= 1ULL << 33;
59 if (start < old_start)
60 wrapped = 1;
61 } while (!wrapped);
62}
63
64void big_gang_check(void)
65{
66 int i;
67
68 for (i = 0; i < 1000; i++) {
69 __big_gang_check();
70 srand(time(0));
71 printf("%d ", i);
72 fflush(stdout);
73 }
74}
75
76void add_and_check(void)
77{
78 RADIX_TREE(tree, GFP_KERNEL);
79
80 item_insert(&tree, 44);
81 item_check_present(&tree, 44);
82 item_check_absent(&tree, 43);
83 item_kill_tree(&tree);
84}
85
86void dynamic_height_check(void)
87{
88 int i;
89 RADIX_TREE(tree, GFP_KERNEL);
90 tree_verify_min_height(&tree, 0);
91
92 item_insert(&tree, 42);
93 tree_verify_min_height(&tree, 42);
94
95 item_insert(&tree, 1000000);
96 tree_verify_min_height(&tree, 1000000);
97
98 assert(item_delete(&tree, 1000000));
99 tree_verify_min_height(&tree, 42);
100
101 assert(item_delete(&tree, 42));
102 tree_verify_min_height(&tree, 0);
103
104 for (i = 0; i < 1000; i++) {
105 item_insert(&tree, i);
106 tree_verify_min_height(&tree, i);
107 }
108
109 i--;
110 for (;;) {
111 assert(item_delete(&tree, i));
112 if (i == 0) {
113 tree_verify_min_height(&tree, 0);
114 break;
115 }
116 i--;
117 tree_verify_min_height(&tree, i);
118 }
119
120 item_kill_tree(&tree);
121}
122
123void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
124{
125 int i;
126
127 for (i = 0; i < count; i++) {
128/* if (i % 1000 == 0)
129 putchar('.'); */
130 if (idx[i] < start || idx[i] > end) {
131 if (item_tag_get(tree, idx[i], totag)) {
132 printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag));
133 }
134 assert(!item_tag_get(tree, idx[i], totag));
135 continue;
136 }
137 if (item_tag_get(tree, idx[i], fromtag) ^
138 item_tag_get(tree, idx[i], totag)) {
139 printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag));
140 }
141 assert(!(item_tag_get(tree, idx[i], fromtag) ^
142 item_tag_get(tree, idx[i], totag)));
143 }
144}
145
146#define ITEMS 50000
147
148void copy_tag_check(void)
149{
150 RADIX_TREE(tree, GFP_KERNEL);
151 unsigned long idx[ITEMS];
152 unsigned long start, end, count = 0, tagged, cur, tmp;
153 int i;
154
155// printf("generating radix tree indices...\n");
156 start = rand();
157 end = rand();
158 if (start > end && (rand() % 10)) {
159 cur = start;
160 start = end;
161 end = cur;
162 }
163 /* Specifically create items around the start and the end of the range
164 * with high probability to check for off by one errors */
165 cur = rand();
166 if (cur & 1) {
167 item_insert(&tree, start);
168 if (cur & 2) {
169 if (start <= end)
170 count++;
171 item_tag_set(&tree, start, 0);
172 }
173 }
174 if (cur & 4) {
175 item_insert(&tree, start-1);
176 if (cur & 8)
177 item_tag_set(&tree, start-1, 0);
178 }
179 if (cur & 16) {
180 item_insert(&tree, end);
181 if (cur & 32) {
182 if (start <= end)
183 count++;
184 item_tag_set(&tree, end, 0);
185 }
186 }
187 if (cur & 64) {
188 item_insert(&tree, end+1);
189 if (cur & 128)
190 item_tag_set(&tree, end+1, 0);
191 }
192
193 for (i = 0; i < ITEMS; i++) {
194 do {
195 idx[i] = rand();
196 } while (item_lookup(&tree, idx[i]));
197
198 item_insert(&tree, idx[i]);
199 if (rand() & 1) {
200 item_tag_set(&tree, idx[i], 0);
201 if (idx[i] >= start && idx[i] <= end)
202 count++;
203 }
204/* if (i % 1000 == 0)
205 putchar('.'); */
206 }
207
208// printf("\ncopying tags...\n");
209 cur = start;
210 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);
211
212// printf("checking copied tags\n");
213 assert(tagged == count);
214 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
215
216 /* Copy tags in several rounds */
217// printf("\ncopying tags...\n");
218 cur = start;
219 do {
220 tmp = rand() % (count/10+2);
221 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
222 } while (tmp == tagged);
223
224// printf("%lu %lu %lu\n", tagged, tmp, count);
225// printf("checking copied tags\n");
226 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
227 assert(tagged < tmp);
228 verify_tag_consistency(&tree, 0);
229 verify_tag_consistency(&tree, 1);
230 verify_tag_consistency(&tree, 2);
231// printf("\n");
232 item_kill_tree(&tree);
233}
234
235static void single_thread_tests(void)
236{
237 int i;
238
239 tag_check();
240 printf("after tag_check: %d allocated\n", nr_allocated);
241 gang_check();
242 printf("after gang_check: %d allocated\n", nr_allocated);
243 add_and_check();
244 printf("after add_and_check: %d allocated\n", nr_allocated);
245 dynamic_height_check();
246 printf("after dynamic_height_check: %d allocated\n", nr_allocated);
247 big_gang_check();
248 printf("after big_gang_check: %d allocated\n", nr_allocated);
249 for (i = 0; i < 2000; i++) {
250 copy_tag_check();
251 printf("%d ", i);
252 fflush(stdout);
253 }
254 printf("after copy_tag_check: %d allocated\n", nr_allocated);
255}
256
257int main(void)
258{
259 rcu_register_thread();
260 radix_tree_init();
261
262 regression1_test();
263 regression2_test();
264 regression3_test();
265 single_thread_tests();
266
267 sleep(1);
268 printf("after sleep(1): %d allocated\n", nr_allocated);
269 rcu_unregister_thread();
270
271 exit(0);
272}