1 /* vi:set ts=8 sw=8 expandtab: */
2 /* Unit test tool for interval tree.
3 * Written by jay <jxiong@clusterfs.com>
10 #include <libcfs/kp30.h>
11 #include <../ldlm/interval_tree.c>
13 #define dprintf(fmt, args...) //printf(fmt, ##args)
14 #define error(fmt, args...) do { \
15 fflush(stdout), fflush(stderr); \
16 fprintf(stderr, "\nError:" fmt, ##args); \
20 #define __F(ext) (ext)->start, (ext)->end
21 #define __S "["LPX64":"LPX64"]"
23 #define ALIGN_SIZE 4096
24 #define ALIGN_MASK (~(ALIGN_SIZE - 1))
26 static struct it_node {
27 struct interval_node node;
28 struct list_head list;
32 CFS_LIST_HEAD(header);
33 static unsigned long max_count = ULONG_MAX & ALIGN_MASK;
34 static int have_wide_lock = 0;
36 static void it_test_clear(void)
39 for (i = 0; i < it_count; i++)
43 static enum interval_iter cb(struct interval_node *n, void *args)
45 struct it_node *node = (struct it_node *)n;
49 dprintf("NODE "__S" has ever been accessed\n",
51 return INTERVAL_ITER_CONT;
52 error("duplicate node accessing found\n");
53 return INTERVAL_ITER_STOP;
56 if (node->valid == 0) {
57 error("A deleted node "__S" being accessed\n",
59 return INTERVAL_ITER_STOP;
66 dprintf(""__S" ", __F(&n->in_extent));
70 return INTERVAL_ITER_CONT;
73 static int it_test_search(struct interval_node *root)
76 struct interval_node_extent ext;
77 int times = 10, i, err = 0;
81 ext.start = (random() % max_count) & ALIGN_MASK;
82 ext.end = random() % (max_count - ext.start + 2) + ext.start;
83 ext.end &= ALIGN_MASK;
84 if (ext.end > max_count)
87 dprintf("\n\nSearching the node overlapped "__S" ..\n",
90 interval_search(root, &ext, cb, NULL);
92 dprintf("\nverifing ...");
95 for (i = 0; i < it_count; i++) {
100 if (extent_overlapped(&ext, &n->node.in_extent) &&
102 error("node "__S" overlaps" __S","
103 "but never to be hit.\n",
104 __F(&n->node.in_extent),
107 if (!extent_overlapped(&ext, &n->node.in_extent) &&
109 error("node "__S" overlaps" __S", but hit.\n",
110 __F(&n->node.in_extent),
113 if (err) error("search error\n");
120 static int it_test_iterate(struct interval_node *root)
124 dprintf("\n\nIterate testing start..\n");
127 interval_iterate(root, cb, NULL);
130 for (i = 0; i < it_count; i++) {
131 if (it_array[i].valid == 0)
133 if (it_array[i].hit == 0)
134 error("Node "__S" is not accessed\n",
135 __F(&it_array[i].node.in_extent));
141 static int it_test_iterate_reverse(struct interval_node *root)
145 dprintf("\n\niterate reverse testing start..\n");
147 interval_iterate_reverse(root, cb, NULL);
150 for (i = 0; i < it_count; i++) {
151 if (it_array[i].valid == 0)
153 if (it_array[i].hit == 0)
154 error("Not every extent is accessed\n");
160 static int it_test_find(struct interval_node *root)
163 struct interval_node_extent *ext;
165 dprintf("\ninterval_find testing start ..\n");
166 for (idx = 0; idx < it_count; idx++) {
167 if (it_array[idx].valid == 0)
170 ext = &it_array[idx].node.in_extent;
171 dprintf("Try to find "__S"\n", __F(ext));
172 if (!interval_find(root, ext))
173 error("interval_find, try to find "__S"\n", __F(ext));
178 /* sanity test is tightly coupled with implementation, so when you changed
179 * the interval tree implementation, change this code also. */
180 static enum interval_iter sanity_cb(struct interval_node *node, void *args)
182 __u64 max_high = node->in_max_high;
183 struct interval_node *tmp, *parent;
184 int left = 1, has = 0, nr = 0;
186 parent = node->in_parent;
187 node->in_parent = NULL;
188 interval_for_each(tmp, node) {
189 if ((left && node_compare(tmp, node) > 0) ||
190 (!left && node_compare(tmp, node) < 0))
191 error("interval tree sanity test\n");
193 if (tmp->in_max_high > max_high) {
194 dprintf("max high sanity check, max_high is %llu,"
195 "child max_high: %llu"__S"\n",
196 max_high, tmp->in_max_high,
197 __F(&tmp->in_extent));
199 } else if (tmp->in_max_high == max_high) {
212 dprintf("node"__S":%llu Child list:\n",
213 node->in_extent.start,
217 interval_for_each(tmp, node) {
218 dprintf(""__S":%llu ",
219 __F(&tmp->in_extent),
227 error("max high sanity check, has == %d\n", has);
229 node->in_parent = parent;
233 if (node_is_black(tmp))
235 else if ((tmp->in_left && node_is_red(tmp->in_left)) ||
236 (tmp->in_right && node_is_red(tmp->in_right)))
237 error("wrong tree, a red node has red child\n");
243 if (node_is_black(tmp))
248 error("wrong tree, unbalanced!\n");
253 static int it_test_sanity(struct interval_node *root)
256 interval_iterate(root, sanity_cb, NULL);
260 static int it_test_search_hole(struct interval_node *root)
263 struct interval_node_extent ext, ext2;
265 __u64 low = 0, high = ~0;
271 ext.start = random() % max_count;
273 } while (interval_is_overlapped(root, &ext));
276 interval_expand(root, &ext, NULL);
277 dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext));
278 for (i = 0; i < it_count; i++) {
283 if (extent_overlapped(&ext, &n->node.in_extent)) {
284 error("Extending "__S" to .."__S" overlaps node"__S"\n",
285 __F(&ext2), __F(&ext), __F(&n->node.in_extent));
288 if (n->node.in_extent.end < ext2.start)
289 low = max_u64(n->node.in_extent.end + 1, low);
291 if (n->node.in_extent.start > ext2.end)
292 high = min_u64(n->node.in_extent.start - 1, high);
295 /* only expanding high right now */
296 if (ext2.start != ext.start || high != ext.end) {
297 ext2.start = low, ext2.end = high;
298 error("Real extending result:"__S", expected:"__S"\n",
299 __F(&ext), __F(&ext2));
305 static int contended_count = 0;
306 #define LOOP_COUNT 1000
307 static enum interval_iter perf_cb(struct interval_node *n, void *args)
309 unsigned long count = LOOP_COUNT;
312 return INTERVAL_ITER_CONT;
315 static inline long tv_delta(struct timeval *s, struct timeval *e)
317 long c = e->tv_sec - s->tv_sec;
319 c += (long int)(e->tv_usec - s->tv_usec) / 1000;
320 dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n",
321 s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec);
325 static int it_test_performance(struct interval_node *root, unsigned long len)
327 int i = 0, interval_time, list_time;
328 struct interval_node_extent ext;
330 struct timeval start, end;
333 ext.start = (random() % (max_count - len)) & ALIGN_MASK;
334 ext.end = (ext.start + len) & ALIGN_MASK;
335 if (have_wide_lock) {
336 ext.start = (max_count - len) & ALIGN_MASK;
340 dprintf("Extent search"__S"\n", __F(&ext));
344 gettimeofday(&start, NULL);
345 list_for_each_entry(n, &header, list) {
346 if (extent_overlapped(&ext, &n->node.in_extent)) {
352 gettimeofday(&end, NULL);
353 list_time = tv_delta(&start, &end);
358 gettimeofday(&start, NULL);
359 interval_search(root, &ext, perf_cb, &contended_count);
360 gettimeofday(&end, NULL);
361 interval_time = tv_delta(&start, &end);
363 if (i != contended_count)
364 error("count of contended lock don't match(%d: %d)\n",
367 printf("\tList vs Int. search: \n\t\t"
368 "(%d vs %d)ms, %d contended lock.\n",
369 list_time, interval_time, contended_count);
374 static struct interval_node *it_test_helper(struct interval_node *root)
379 count = random() % it_count;
381 idx = random() % it_count;
384 if (!interval_find(root, &n->node.in_extent))
385 error("Cannot find an existent node\n");
386 dprintf("Erasing a node "__S"\n",
387 __F(&n->node.in_extent));
388 interval_erase(&n->node, &root);
390 list_del_init(&n->list);
393 low = (random() % max_count) & ALIGN_MASK;
394 high = ((random() % max_count + 1) & ALIGN_MASK) + low;
395 if (high > max_count)
397 interval_set(&n->node, low, high);
398 while (interval_insert(&n->node, &root))
399 interval_set(&n->node, low, ++high);
400 dprintf("Adding a node "__S"\n",
401 __F(&n->node.in_extent));
403 list_add(&n->list, &header);
410 static struct interval_node *it_test_init(int count)
413 uint64_t high, low, len;
415 struct interval_node *root = NULL;
418 it_array = (struct it_node *)malloc(sizeof(struct it_node) * count);
419 if (it_array == NULL)
420 error("it_array == NULL, no memory\n");
423 for (i = 0; i < count; i++) {
426 low = (random() % max_count + 1) & ALIGN_MASK;
427 len = (random() % 256 + 1) * ALIGN_SIZE;
428 if (!have_wide_lock && !(random() % count)) {
433 high = low + (len & ALIGN_MASK);
435 interval_set(&n->node, low, high);
436 } while (interval_insert(&n->node, &root));
440 list_add_tail(&n->list, &header);
442 list_add_tail(&n->list, &it_array[rand()%i].list);
448 static void it_test_fini(void)
456 int main(int argc, char *argv[])
458 int count = 5, perf = 0;
459 struct interval_node *root;
462 gettimeofday(&tv, NULL);
466 if (strcmp(argv[1], "-p"))
467 error("Unknow options, usage: %s [-p]\n", argv[0]);
474 root = it_test_init(1000000);
475 printf("1M locks with 4K request size\n");
476 it_test_performance(root, 4096);
477 printf("1M locks with 128K request size\n");
478 it_test_performance(root, 128 * 1024);
479 printf("1M locks with 256K request size\n");
480 it_test_performance(root, 256 * 1024);
481 printf("1M locks with 1M request size\n");
482 it_test_performance(root, 1 * M);
483 printf("1M locks with 16M request size\n");
484 it_test_performance(root, 16 * M);
485 printf("1M locks with 32M request size\n");
486 it_test_performance(root, 32 * M);
487 printf("1M locks with 64M request size\n");
488 it_test_performance(root, 64 * M);
489 printf("1M locks with 128M request size\n");
490 it_test_performance(root, 128 * M);
491 printf("1M locks with 256M request size\n");
492 it_test_performance(root, 256 * M);
493 printf("1M locks with 512M request size\n");
494 it_test_performance(root, 512 * M);
495 printf("1M locks with 1G request size\n");
496 it_test_performance(root, 1024 * M);
497 printf("1M locks with 2G request size\n");
498 it_test_performance(root, 2048 * M);
499 printf("1M locks with 3G request size\n");
500 it_test_performance(root, 3072 * M);
501 printf("1M locks with 4G request size\n");
502 it_test_performance(root, max_count - 1);
507 root = it_test_init(random() % 100000 + 1000);
509 it_test_sanity(root);
510 it_test_iterate(root);
511 it_test_iterate_reverse(root);
513 it_test_search_hole(root);
514 it_test_search(root);
515 root = it_test_helper(root);