4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
34 * lustre/tests/it_test.c
36 * Unit test tool for interval tree.
38 * Author: jay <jxiong@clusterfs.com>
46 #include <libcfs/libcfs.h>
47 #include <../ldlm/interval_tree.c>
49 #define dprintf(fmt, args...) //printf(fmt, ##args)
50 #define error(fmt, args...) do { \
51 fflush(stdout), fflush(stderr); \
52 fprintf(stderr, "\nError:" fmt, ##args); \
56 #define __F(ext) (ext)->start, (ext)->end
57 #define __S "["LPX64":"LPX64"]"
59 #define ALIGN_SIZE 4096
60 #define ALIGN_MASK (~(ALIGN_SIZE - 1))
62 static struct it_node {
63 struct interval_node node;
64 struct list_head list;
68 static CFS_LIST_HEAD(header);
69 static unsigned long max_count = ULONG_MAX & ALIGN_MASK;
70 static int have_wide_lock = 0;
72 static void it_test_clear(void)
75 for (i = 0; i < it_count; i++)
79 static enum interval_iter cb(struct interval_node *n, void *args)
81 struct it_node *node = (struct it_node *)n;
85 error("A duplicate node "__S" access found\n",
87 return INTERVAL_ITER_CONT;
90 if (node->valid == 0) {
91 error("A deleted node "__S" being accessed\n",
93 return INTERVAL_ITER_STOP;
100 dprintf(""__S" ", __F(&n->in_extent));
104 return INTERVAL_ITER_CONT;
107 static int it_test_search(struct interval_node *root)
110 struct interval_node_extent ext;
111 int times = 10, i, err = 0;
115 ext.start = (random() % max_count) & ALIGN_MASK;
116 ext.end = random() % (max_count - ext.start + 2) + ext.start;
117 ext.end &= ALIGN_MASK;
118 if (ext.end > max_count)
121 dprintf("\n\nSearching the node overlapped "__S" ..\n",
124 interval_search(root, &ext, cb, NULL);
126 dprintf("\nverifing ...");
129 for (i = 0; i < it_count; i++) {
134 if (extent_overlapped(&ext, &n->node.in_extent) &&
136 error("node "__S" overlaps" __S","
137 "but never to be hit.\n",
138 __F(&n->node.in_extent),
141 if (!extent_overlapped(&ext, &n->node.in_extent) &&
143 error("node "__S" overlaps" __S", but hit.\n",
144 __F(&n->node.in_extent),
147 if (err) error("search error\n");
154 static int it_test_iterate(struct interval_node *root)
158 dprintf("\n\nIterate testing start..\n");
161 interval_iterate(root, cb, NULL);
164 for (i = 0; i < it_count; i++) {
165 if (it_array[i].valid == 0)
167 if (it_array[i].hit == 0)
168 error("Node "__S" is not accessed\n",
169 __F(&it_array[i].node.in_extent));
175 static int it_test_iterate_reverse(struct interval_node *root)
179 dprintf("\n\niterate reverse testing start..\n");
181 interval_iterate_reverse(root, cb, NULL);
184 for (i = 0; i < it_count; i++) {
185 if (it_array[i].valid == 0)
187 if (it_array[i].hit == 0)
188 error("Not every extent is accessed\n");
194 static int it_test_find(struct interval_node *root)
197 struct interval_node_extent *ext;
199 dprintf("\ninterval_find testing start ..\n");
200 for (idx = 0; idx < it_count; idx++) {
201 if (it_array[idx].valid == 0)
204 ext = &it_array[idx].node.in_extent;
205 dprintf("Try to find "__S"\n", __F(ext));
206 if (!interval_find(root, ext))
207 error("interval_find, try to find "__S"\n", __F(ext));
212 /* sanity test is tightly coupled with implementation, so when you changed
213 * the interval tree implementation, change this code also. */
214 static enum interval_iter sanity_cb(struct interval_node *node, void *args)
216 __u64 max_high = node->in_max_high;
217 struct interval_node *tmp, *parent;
218 int left = 1, has = 0, nr = 0;
220 parent = node->in_parent;
221 node->in_parent = NULL;
222 interval_for_each(tmp, node) {
223 if ((left && node_compare(tmp, node) > 0) ||
224 (!left && node_compare(tmp, node) < 0))
225 error("interval tree sanity test\n");
227 if (tmp->in_max_high > max_high) {
228 dprintf("max high sanity check, max_high is %llu,"
229 "child max_high: %llu"__S"\n",
230 max_high, tmp->in_max_high,
231 __F(&tmp->in_extent));
233 } else if (tmp->in_max_high == max_high) {
247 dprintf("node"__S":%llu Child list:\n",
248 node->in_extent.start,
252 interval_for_each(tmp, node) {
253 dprintf(""__S":%llu ",
254 __F(&tmp->in_extent),
262 error("max high sanity check, has == %d\n", has);
264 node->in_parent = parent;
268 if (node_is_black(tmp))
270 else if ((tmp->in_left && node_is_red(tmp->in_left)) ||
271 (tmp->in_right && node_is_red(tmp->in_right)))
272 error("wrong tree, a red node has red child\n");
278 if (node_is_black(tmp))
283 error("wrong tree, unbalanced!\n");
288 static int it_test_sanity(struct interval_node *root)
291 interval_iterate(root, sanity_cb, NULL);
295 static int it_test_search_hole(struct interval_node *root)
298 struct interval_node_extent ext, ext2;
300 __u64 low = 0, high = ~0;
306 ext.start = random() % max_count;
308 } while (interval_is_overlapped(root, &ext));
311 interval_expand(root, &ext, NULL);
312 dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext));
313 for (i = 0; i < it_count; i++) {
318 if (extent_overlapped(&ext, &n->node.in_extent)) {
319 error("Extending "__S" to .."__S" overlaps node"__S"\n",
320 __F(&ext2), __F(&ext), __F(&n->node.in_extent));
323 if (n->node.in_extent.end < ext2.start)
324 low = max_u64(n->node.in_extent.end + 1, low);
326 if (n->node.in_extent.start > ext2.end)
327 high = min_u64(n->node.in_extent.start - 1, high);
330 /* only expanding high right now */
331 if (ext2.start != ext.start || high != ext.end) {
332 ext2.start = low, ext2.end = high;
333 error("Real extending result:"__S", expected:"__S"\n",
334 __F(&ext), __F(&ext2));
340 static int contended_count = 0;
341 #define LOOP_COUNT 1000
342 static enum interval_iter perf_cb(struct interval_node *n, void *args)
344 unsigned long count = LOOP_COUNT;
347 return INTERVAL_ITER_CONT;
350 static inline long tv_delta(struct timeval *s, struct timeval *e)
352 long c = e->tv_sec - s->tv_sec;
354 c += (long int)(e->tv_usec - s->tv_usec) / 1000;
355 dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n",
356 s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec);
360 static int it_test_performance(struct interval_node *root, unsigned long len)
362 int i = 0, interval_time, list_time;
363 struct interval_node_extent ext;
365 struct timeval start, end;
368 ext.start = (random() % (max_count - len)) & ALIGN_MASK;
369 ext.end = (ext.start + len) & ALIGN_MASK;
370 if (have_wide_lock) {
371 ext.start = (max_count - len) & ALIGN_MASK;
375 dprintf("Extent search"__S"\n", __F(&ext));
379 gettimeofday(&start, NULL);
380 list_for_each_entry(n, &header, list) {
381 if (extent_overlapped(&ext, &n->node.in_extent)) {
387 gettimeofday(&end, NULL);
388 list_time = tv_delta(&start, &end);
393 gettimeofday(&start, NULL);
394 interval_search(root, &ext, perf_cb, &contended_count);
395 gettimeofday(&end, NULL);
396 interval_time = tv_delta(&start, &end);
398 if (i != contended_count)
399 error("count of contended lock don't match(%d: %d)\n",
402 printf("\tList vs Int. search: \n\t\t"
403 "(%d vs %d)ms, %d contended lock.\n",
404 list_time, interval_time, contended_count);
409 static struct interval_node *it_test_helper(struct interval_node *root)
414 count = random() % it_count;
416 idx = random() % it_count;
419 if (!interval_find(root, &n->node.in_extent))
420 error("Cannot find an existent node\n");
421 dprintf("Erasing a node "__S"\n",
422 __F(&n->node.in_extent));
423 interval_erase(&n->node, &root);
425 list_del_init(&n->list);
428 low = (random() % max_count) & ALIGN_MASK;
429 high = ((random() % max_count + 1) & ALIGN_MASK) + low;
430 if (high > max_count)
432 interval_set(&n->node, low, high);
433 while (interval_insert(&n->node, &root))
434 interval_set(&n->node, low, ++high);
435 dprintf("Adding a node "__S"\n",
436 __F(&n->node.in_extent));
438 list_add(&n->list, &header);
445 static struct interval_node *it_test_init(int count)
448 uint64_t high, low, len;
450 struct interval_node *root = NULL;
453 it_array = (struct it_node *)malloc(sizeof(struct it_node) * count);
454 if (it_array == NULL)
455 error("it_array == NULL, no memory\n");
458 for (i = 0; i < count; i++) {
461 low = (random() % max_count + 1) & ALIGN_MASK;
462 len = (random() % 256 + 1) * ALIGN_SIZE;
463 if (!have_wide_lock && !(random() % count)) {
468 high = low + (len & ALIGN_MASK);
470 interval_set(&n->node, low, high);
471 } while (interval_insert(&n->node, &root));
475 list_add_tail(&n->list, &header);
477 list_add_tail(&n->list, &it_array[rand()%i].list);
483 static void it_test_fini(void)
491 int main(int argc, char *argv[])
493 int count = 5, perf = 0;
494 struct interval_node *root;
497 gettimeofday(&tv, NULL);
501 if (strcmp(argv[1], "-p"))
502 error("Unknow options, usage: %s [-p]\n", argv[0]);
509 root = it_test_init(1000000);
510 printf("1M locks with 4K request size\n");
511 it_test_performance(root, 4096);
512 printf("1M locks with 128K request size\n");
513 it_test_performance(root, 128 * 1024);
514 printf("1M locks with 256K request size\n");
515 it_test_performance(root, 256 * 1024);
516 printf("1M locks with 1M request size\n");
517 it_test_performance(root, 1 * M);
518 printf("1M locks with 16M request size\n");
519 it_test_performance(root, 16 * M);
520 printf("1M locks with 32M request size\n");
521 it_test_performance(root, 32 * M);
522 printf("1M locks with 64M request size\n");
523 it_test_performance(root, 64 * M);
524 printf("1M locks with 128M request size\n");
525 it_test_performance(root, 128 * M);
526 printf("1M locks with 256M request size\n");
527 it_test_performance(root, 256 * M);
528 printf("1M locks with 512M request size\n");
529 it_test_performance(root, 512 * M);
530 printf("1M locks with 1G request size\n");
531 it_test_performance(root, 1024 * M);
532 printf("1M locks with 2G request size\n");
533 it_test_performance(root, 2048 * M);
534 printf("1M locks with 3G request size\n");
535 it_test_performance(root, 3072 * M);
536 printf("1M locks with 4G request size\n");
537 it_test_performance(root, max_count - 1);
542 root = it_test_init(random() % 100000 + 1000);
544 it_test_sanity(root);
545 it_test_iterate(root);
546 it_test_iterate_reverse(root);
548 it_test_search_hole(root);
549 it_test_search(root);
550 root = it_test_helper(root);