1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright 2008 Sun Microsystems, Inc. All rights reserved
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/tests/it_test.c
38 * Unit test tool for interval tree.
40 * Author: jay <jxiong@clusterfs.com>
48 #include <libcfs/libcfs.h>
49 #include <../ldlm/interval_tree.c>
51 #define dprintf(fmt, args...) //printf(fmt, ##args)
52 #define error(fmt, args...) do { \
53 fflush(stdout), fflush(stderr); \
54 fprintf(stderr, "\nError:" fmt, ##args); \
58 #define __F(ext) (ext)->start, (ext)->end
59 #define __S "["LPX64":"LPX64"]"
61 #define ALIGN_SIZE 4096
62 #define ALIGN_MASK (~(ALIGN_SIZE - 1))
64 static struct it_node {
65 struct interval_node node;
66 struct list_head list;
70 static CFS_LIST_HEAD(header);
71 static unsigned long max_count = ULONG_MAX & ALIGN_MASK;
72 static int have_wide_lock = 0;
74 static void it_test_clear(void)
77 for (i = 0; i < it_count; i++)
81 static enum interval_iter cb(struct interval_node *n, void *args)
83 struct it_node *node = (struct it_node *)n;
87 dprintf("NODE "__S" has ever been accessed\n",
89 return INTERVAL_ITER_CONT;
90 error("duplicate node accessing found\n");
91 return INTERVAL_ITER_STOP;
94 if (node->valid == 0) {
95 error("A deleted node "__S" being accessed\n",
97 return INTERVAL_ITER_STOP;
104 dprintf(""__S" ", __F(&n->in_extent));
108 return INTERVAL_ITER_CONT;
111 static int it_test_search(struct interval_node *root)
114 struct interval_node_extent ext;
115 int times = 10, i, err = 0;
119 ext.start = (random() % max_count) & ALIGN_MASK;
120 ext.end = random() % (max_count - ext.start + 2) + ext.start;
121 ext.end &= ALIGN_MASK;
122 if (ext.end > max_count)
125 dprintf("\n\nSearching the node overlapped "__S" ..\n",
128 interval_search(root, &ext, cb, NULL);
130 dprintf("\nverifing ...");
133 for (i = 0; i < it_count; i++) {
138 if (extent_overlapped(&ext, &n->node.in_extent) &&
140 error("node "__S" overlaps" __S","
141 "but never to be hit.\n",
142 __F(&n->node.in_extent),
145 if (!extent_overlapped(&ext, &n->node.in_extent) &&
147 error("node "__S" overlaps" __S", but hit.\n",
148 __F(&n->node.in_extent),
151 if (err) error("search error\n");
158 static int it_test_iterate(struct interval_node *root)
162 dprintf("\n\nIterate testing start..\n");
165 interval_iterate(root, cb, NULL);
168 for (i = 0; i < it_count; i++) {
169 if (it_array[i].valid == 0)
171 if (it_array[i].hit == 0)
172 error("Node "__S" is not accessed\n",
173 __F(&it_array[i].node.in_extent));
179 static int it_test_iterate_reverse(struct interval_node *root)
183 dprintf("\n\niterate reverse testing start..\n");
185 interval_iterate_reverse(root, cb, NULL);
188 for (i = 0; i < it_count; i++) {
189 if (it_array[i].valid == 0)
191 if (it_array[i].hit == 0)
192 error("Not every extent is accessed\n");
198 static int it_test_find(struct interval_node *root)
201 struct interval_node_extent *ext;
203 dprintf("\ninterval_find testing start ..\n");
204 for (idx = 0; idx < it_count; idx++) {
205 if (it_array[idx].valid == 0)
208 ext = &it_array[idx].node.in_extent;
209 dprintf("Try to find "__S"\n", __F(ext));
210 if (!interval_find(root, ext))
211 error("interval_find, try to find "__S"\n", __F(ext));
216 /* sanity test is tightly coupled with implementation, so when you changed
217 * the interval tree implementation, change this code also. */
218 static enum interval_iter sanity_cb(struct interval_node *node, void *args)
220 __u64 max_high = node->in_max_high;
221 struct interval_node *tmp, *parent;
222 int left = 1, has = 0, nr = 0;
224 parent = node->in_parent;
225 node->in_parent = NULL;
226 interval_for_each(tmp, node) {
227 if ((left && node_compare(tmp, node) > 0) ||
228 (!left && node_compare(tmp, node) < 0))
229 error("interval tree sanity test\n");
231 if (tmp->in_max_high > max_high) {
232 dprintf("max high sanity check, max_high is %llu,"
233 "child max_high: %llu"__S"\n",
234 max_high, tmp->in_max_high,
235 __F(&tmp->in_extent));
237 } else if (tmp->in_max_high == max_high) {
251 dprintf("node"__S":%llu Child list:\n",
252 node->in_extent.start,
256 interval_for_each(tmp, node) {
257 dprintf(""__S":%llu ",
258 __F(&tmp->in_extent),
266 error("max high sanity check, has == %d\n", has);
268 node->in_parent = parent;
272 if (node_is_black(tmp))
274 else if ((tmp->in_left && node_is_red(tmp->in_left)) ||
275 (tmp->in_right && node_is_red(tmp->in_right)))
276 error("wrong tree, a red node has red child\n");
282 if (node_is_black(tmp))
287 error("wrong tree, unbalanced!\n");
292 static int it_test_sanity(struct interval_node *root)
295 interval_iterate(root, sanity_cb, NULL);
299 static int it_test_search_hole(struct interval_node *root)
302 struct interval_node_extent ext, ext2;
304 __u64 low = 0, high = ~0;
310 ext.start = random() % max_count;
312 } while (interval_is_overlapped(root, &ext));
315 interval_expand(root, &ext, NULL);
316 dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext));
317 for (i = 0; i < it_count; i++) {
322 if (extent_overlapped(&ext, &n->node.in_extent)) {
323 error("Extending "__S" to .."__S" overlaps node"__S"\n",
324 __F(&ext2), __F(&ext), __F(&n->node.in_extent));
327 if (n->node.in_extent.end < ext2.start)
328 low = max_u64(n->node.in_extent.end + 1, low);
330 if (n->node.in_extent.start > ext2.end)
331 high = min_u64(n->node.in_extent.start - 1, high);
334 /* only expanding high right now */
335 if (ext2.start != ext.start || high != ext.end) {
336 ext2.start = low, ext2.end = high;
337 error("Real extending result:"__S", expected:"__S"\n",
338 __F(&ext), __F(&ext2));
344 static int contended_count = 0;
345 #define LOOP_COUNT 1000
346 static enum interval_iter perf_cb(struct interval_node *n, void *args)
348 unsigned long count = LOOP_COUNT;
351 return INTERVAL_ITER_CONT;
354 static inline long tv_delta(struct timeval *s, struct timeval *e)
356 long c = e->tv_sec - s->tv_sec;
358 c += (long int)(e->tv_usec - s->tv_usec) / 1000;
359 dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n",
360 s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec);
364 static int it_test_performance(struct interval_node *root, unsigned long len)
366 int i = 0, interval_time, list_time;
367 struct interval_node_extent ext;
369 struct timeval start, end;
372 ext.start = (random() % (max_count - len)) & ALIGN_MASK;
373 ext.end = (ext.start + len) & ALIGN_MASK;
374 if (have_wide_lock) {
375 ext.start = (max_count - len) & ALIGN_MASK;
379 dprintf("Extent search"__S"\n", __F(&ext));
383 gettimeofday(&start, NULL);
384 list_for_each_entry(n, &header, list) {
385 if (extent_overlapped(&ext, &n->node.in_extent)) {
391 gettimeofday(&end, NULL);
392 list_time = tv_delta(&start, &end);
397 gettimeofday(&start, NULL);
398 interval_search(root, &ext, perf_cb, &contended_count);
399 gettimeofday(&end, NULL);
400 interval_time = tv_delta(&start, &end);
402 if (i != contended_count)
403 error("count of contended lock don't match(%d: %d)\n",
406 printf("\tList vs Int. search: \n\t\t"
407 "(%d vs %d)ms, %d contended lock.\n",
408 list_time, interval_time, contended_count);
413 static struct interval_node *it_test_helper(struct interval_node *root)
418 count = random() % it_count;
420 idx = random() % it_count;
423 if (!interval_find(root, &n->node.in_extent))
424 error("Cannot find an existent node\n");
425 dprintf("Erasing a node "__S"\n",
426 __F(&n->node.in_extent));
427 interval_erase(&n->node, &root);
429 list_del_init(&n->list);
432 low = (random() % max_count) & ALIGN_MASK;
433 high = ((random() % max_count + 1) & ALIGN_MASK) + low;
434 if (high > max_count)
436 interval_set(&n->node, low, high);
437 while (interval_insert(&n->node, &root))
438 interval_set(&n->node, low, ++high);
439 dprintf("Adding a node "__S"\n",
440 __F(&n->node.in_extent));
442 list_add(&n->list, &header);
449 static struct interval_node *it_test_init(int count)
452 uint64_t high, low, len;
454 struct interval_node *root = NULL;
457 it_array = (struct it_node *)malloc(sizeof(struct it_node) * count);
458 if (it_array == NULL)
459 error("it_array == NULL, no memory\n");
462 for (i = 0; i < count; i++) {
465 low = (random() % max_count + 1) & ALIGN_MASK;
466 len = (random() % 256 + 1) * ALIGN_SIZE;
467 if (!have_wide_lock && !(random() % count)) {
472 high = low + (len & ALIGN_MASK);
474 interval_set(&n->node, low, high);
475 } while (interval_insert(&n->node, &root));
479 list_add_tail(&n->list, &header);
481 list_add_tail(&n->list, &it_array[rand()%i].list);
487 static void it_test_fini(void)
495 int main(int argc, char *argv[])
497 int count = 5, perf = 0;
498 struct interval_node *root;
501 gettimeofday(&tv, NULL);
505 if (strcmp(argv[1], "-p"))
506 error("Unknow options, usage: %s [-p]\n", argv[0]);
513 root = it_test_init(1000000);
514 printf("1M locks with 4K request size\n");
515 it_test_performance(root, 4096);
516 printf("1M locks with 128K request size\n");
517 it_test_performance(root, 128 * 1024);
518 printf("1M locks with 256K request size\n");
519 it_test_performance(root, 256 * 1024);
520 printf("1M locks with 1M request size\n");
521 it_test_performance(root, 1 * M);
522 printf("1M locks with 16M request size\n");
523 it_test_performance(root, 16 * M);
524 printf("1M locks with 32M request size\n");
525 it_test_performance(root, 32 * M);
526 printf("1M locks with 64M request size\n");
527 it_test_performance(root, 64 * M);
528 printf("1M locks with 128M request size\n");
529 it_test_performance(root, 128 * M);
530 printf("1M locks with 256M request size\n");
531 it_test_performance(root, 256 * M);
532 printf("1M locks with 512M request size\n");
533 it_test_performance(root, 512 * M);
534 printf("1M locks with 1G request size\n");
535 it_test_performance(root, 1024 * M);
536 printf("1M locks with 2G request size\n");
537 it_test_performance(root, 2048 * M);
538 printf("1M locks with 3G request size\n");
539 it_test_performance(root, 3072 * M);
540 printf("1M locks with 4G request size\n");
541 it_test_performance(root, max_count - 1);
546 root = it_test_init(random() % 100000 + 1000);
548 it_test_sanity(root);
549 it_test_iterate(root);
550 it_test_iterate_reverse(root);
552 it_test_search_hole(root);
553 it_test_search(root);
554 root = it_test_helper(root);