Whamcloud - gitweb
b=16098
[fs/lustre-release.git] / lustre / tests / it_test.c
1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=8:tabstop=8:
3  *
4  * GPL HEADER START
5  *
6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7  *
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.
11  *
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).
17  *
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
21  *
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
24  * have any questions.
25  *
26  * GPL HEADER END
27  */
28 /*
29  * Copyright  2008 Sun Microsystems, Inc. All rights reserved
30  * Use is subject to license terms.
31  */
32 /*
33  * This file is part of Lustre, http://www.lustre.org/
34  * Lustre is a trademark of Sun Microsystems, Inc.
35  *
36  * lustre/tests/it_test.c
37  *
38  * Unit test tool for interval tree.
39  *
40  * Author: jay <jxiong@clusterfs.com>
41  */
42
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <time.h>
46 #include <sys/time.h>
47
48 #include <libcfs/libcfs.h>
49 #include <../ldlm/interval_tree.c>
50
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);        \
55         abort();                                        \
56 } while(0)
57
58 #define __F(ext)         (ext)->start, (ext)->end
59 #define __S              "["LPX64":"LPX64"]"
60
61 #define ALIGN_SIZE       4096
62 #define ALIGN_MASK       (~(ALIGN_SIZE - 1))
63
64 static struct it_node {
65         struct interval_node node;
66         struct list_head list;
67         int hit, valid;
68 } *it_array;
69 static int it_count;
70 static CFS_LIST_HEAD(header);
71 static unsigned long max_count = ULONG_MAX & ALIGN_MASK;
72 static int have_wide_lock = 0;
73
74 static void it_test_clear(void)
75 {
76         int i = 0;
77         for (i = 0; i < it_count; i++)
78                 it_array[i].hit = 0;
79 }
80
81 static enum interval_iter cb(struct interval_node *n, void *args)
82 {
83         struct it_node *node = (struct it_node *)n;
84         static int count = 1;
85
86         if (node->hit == 1) {
87                 dprintf("NODE "__S" has ever been accessed\n",
88                         __F(&n->in_extent));
89                 return INTERVAL_ITER_CONT;
90                 error("duplicate node accessing found\n");
91                 return INTERVAL_ITER_STOP;
92         }
93         
94         if (node->valid == 0) {
95                 error("A deleted node "__S" being accessed\n",
96                        __F(&n->in_extent));
97                 return INTERVAL_ITER_STOP;
98         }
99
100         if (count++ == 8) {
101                 dprintf("\n");
102                 count = 1;
103         }
104         dprintf(""__S" ", __F(&n->in_extent));
105         fflush(stdout);
106
107         node->hit = 1;
108         return INTERVAL_ITER_CONT;
109 }
110
111 static int it_test_search(struct interval_node *root)
112 {
113         struct it_node *n;
114         struct interval_node_extent ext;
115         int times = 10, i, err = 0;
116
117         while (times--) {
118                 it_test_clear();
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)
123                         ext.end = max_count;
124
125                 dprintf("\n\nSearching the node overlapped "__S" ..\n",
126                         __F(&ext));
127
128                 interval_search(root, &ext, cb, NULL);
129
130                 dprintf("\nverifing ...");
131         
132                 /* verify */
133                 for (i = 0; i < it_count; i++) {
134                         n = &it_array[i];
135                         if (n->valid == 0)
136                                 continue;
137
138                         if (extent_overlapped(&ext, &n->node.in_extent) && 
139                             n->hit == 0)
140                                 error("node "__S" overlaps" __S","
141                                       "but never to be hit.\n", 
142                                       __F(&n->node.in_extent),
143                                       __F(&ext));
144
145                         if (!extent_overlapped(&ext, &n->node.in_extent) && 
146                             n->hit)
147                                 error("node "__S" overlaps" __S", but hit.\n", 
148                                       __F(&n->node.in_extent),
149                                       __F(&ext));
150                 }
151                 if (err) error("search error\n");
152                 dprintf("ok.\n");
153         }
154
155         return 0;
156 }
157
158 static int it_test_iterate(struct interval_node *root)
159 {
160         int i;
161
162         dprintf("\n\nIterate testing start..\n");
163
164         it_test_clear();
165         interval_iterate(root, cb, NULL);
166
167         /* verify */
168         for (i = 0; i < it_count; i++) {
169                 if (it_array[i].valid == 0)
170                         continue;
171                 if (it_array[i].hit == 0)
172                         error("Node "__S" is not accessed\n",
173                               __F(&it_array[i].node.in_extent));
174         }
175
176         return 0;
177 }
178
179 static int it_test_iterate_reverse(struct interval_node *root)
180 {
181         int i;
182
183         dprintf("\n\niterate reverse testing start..\n");
184         it_test_clear();
185         interval_iterate_reverse(root, cb, NULL);
186
187         /* verify */
188         for (i = 0; i < it_count; i++) {
189                 if (it_array[i].valid == 0)
190                         continue;
191                 if (it_array[i].hit == 0)
192                         error("Not every extent is accessed\n");
193         }
194
195         return 0;
196 }
197
198 static int it_test_find(struct interval_node *root)
199 {
200         int idx;
201         struct interval_node_extent *ext;
202
203         dprintf("\ninterval_find testing start ..\n");
204         for (idx = 0; idx < it_count; idx++) {
205                 if (it_array[idx].valid == 0)
206                         continue;
207
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));
212         }
213         return 0;
214 }
215
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)
219 {
220         __u64 max_high = node->in_max_high;
221         struct interval_node *tmp, *parent;
222         int left = 1, has = 0, nr = 0;
223
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");
230
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));
236                         goto err;
237                 } else if (tmp->in_max_high == max_high) {
238                         has = 1;
239                 }
240
241                 if (tmp == node) {
242                         left = 0;
243                         continue;
244                 }
245         }
246
247         if (!has) {
248                 int count = 1;
249 err:
250                 dprintf("node"__S":%llu Child list:\n",
251                         node->in_extent.start,
252                         node->in_extent.end,
253                         node->in_max_high);
254
255                 interval_for_each(tmp, node) {
256                         dprintf(""__S":%llu ",
257                                 __F(&tmp->in_extent),
258                                 tmp->in_max_high);
259                         if (count++ == 8) {
260                                 dprintf("\n");
261                                 count = 1;
262                         }
263                 }
264
265                 error("max high sanity check, has == %d\n", has);
266         }
267         node->in_parent = parent;
268
269         tmp = node;
270         while (tmp) {
271                 if (node_is_black(tmp))
272                         nr++;
273                 else if ((tmp->in_left && node_is_red(tmp->in_left)) ||
274                          (tmp->in_right && node_is_red(tmp->in_right)))
275                         error("wrong tree, a red node has red child\n");
276                 tmp = tmp->in_left;
277         }
278
279         tmp = node;
280         while (tmp) {
281                 if (node_is_black(tmp))
282                         nr--;
283                 tmp = tmp->in_right;
284         }
285         if (nr)
286                 error("wrong tree, unbalanced!\n");
287         
288         return 0;
289 }
290
291 static int it_test_sanity(struct interval_node *root)
292 {
293         it_test_clear();
294         interval_iterate(root, sanity_cb, NULL);
295         return 0;
296 }
297
298 static int it_test_search_hole(struct interval_node *root)
299 {
300         int i, count = 10;
301         struct interval_node_extent ext, ext2;
302         struct it_node *n;
303         __u64 low = 0, high = ~0;
304
305         do {
306                 if (--count == 0)
307                         return 0;
308
309                 ext.start = random() % max_count;
310                 ext.end = ext.start;
311         } while (interval_is_overlapped(root, &ext));
312         ext2 = ext;
313
314         interval_expand(root, &ext, NULL);
315         dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext));
316         for (i = 0; i < it_count; i++) {
317                 n = &it_array[i];
318                 if (n->valid == 0)
319                         continue;
320
321                 if (extent_overlapped(&ext, &n->node.in_extent)) {
322                         error("Extending "__S" to .."__S" overlaps node"__S"\n",
323                                 __F(&ext2), __F(&ext), __F(&n->node.in_extent));
324                 }
325
326                 if (n->node.in_extent.end < ext2.start)
327                         low = max_u64(n->node.in_extent.end + 1, low);
328
329                 if (n->node.in_extent.start > ext2.end)
330                         high = min_u64(n->node.in_extent.start - 1, high);
331         }
332
333         /* only expanding high right now */
334         if (ext2.start != ext.start || high != ext.end) {
335                 ext2.start = low, ext2.end = high;
336                 error("Real extending result:"__S", expected:"__S"\n",
337                        __F(&ext), __F(&ext2));
338         }
339
340         return 0;
341 }
342
343 static int contended_count = 0; 
344 #define LOOP_COUNT 1000
345 static enum interval_iter perf_cb(struct interval_node *n, void *args)
346 {
347         unsigned long count = LOOP_COUNT;
348         while (count--);
349         contended_count++;
350         return INTERVAL_ITER_CONT;
351 }
352
353 static inline long tv_delta(struct timeval *s, struct timeval *e)
354 {
355         long c = e->tv_sec - s->tv_sec;
356         c *= 1000;
357         c += (long int)(e->tv_usec - s->tv_usec) / 1000;
358         dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n", 
359                 s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec);
360         return c;
361 }
362
363 static int it_test_performance(struct interval_node *root, unsigned long len)
364 {
365         int i = 0, interval_time, list_time;
366         struct interval_node_extent ext;
367         struct it_node *n;
368         struct timeval start, end;
369         unsigned long count;
370         
371         ext.start = (random() % (max_count - len)) & ALIGN_MASK;
372         ext.end = (ext.start + len) & ALIGN_MASK;
373         if (have_wide_lock) {
374                 ext.start = (max_count - len) & ALIGN_MASK;
375                 ext.end = max_count;
376         }
377
378         dprintf("Extent search"__S"\n", __F(&ext));
379
380         /* list */
381         contended_count = 0;
382         gettimeofday(&start, NULL);
383         list_for_each_entry(n, &header, list) {
384                 if (extent_overlapped(&ext, &n->node.in_extent)) {
385                         count = LOOP_COUNT;
386                         while (count--);
387                         contended_count++;
388                 }
389         }
390         gettimeofday(&end, NULL);
391         list_time = tv_delta(&start, &end);
392         i = contended_count;
393
394         /* interval */
395         contended_count = 0;
396         gettimeofday(&start, NULL);
397         interval_search(root, &ext, perf_cb, &contended_count);
398         gettimeofday(&end, NULL);
399         interval_time = tv_delta(&start, &end);
400
401         if (i != contended_count)
402                 error("count of contended lock don't match(%d: %d)\n",
403                       i, contended_count);
404
405         printf("\tList vs Int. search: \n\t\t"
406                "(%d vs %d)ms, %d contended lock.\n",
407                 list_time, interval_time, contended_count);
408
409         return 0;
410 }
411
412 static struct interval_node *it_test_helper(struct interval_node *root)
413 {
414         int idx, count = 0;
415         struct it_node *n;
416
417         count = random() % it_count;
418         while (count--) {
419                 idx = random() % it_count;
420                 n = &it_array[idx];
421                 if (n->valid) {
422                         if (!interval_find(root, &n->node.in_extent))
423                                 error("Cannot find an existent node\n");
424                         dprintf("Erasing a node "__S"\n", 
425                                 __F(&n->node.in_extent));
426                         interval_erase(&n->node, &root);
427                         n->valid = 0;
428                         list_del_init(&n->list);
429                 } else {
430                         __u64 low, high;
431                         low = (random() % max_count) & ALIGN_MASK;
432                         high = ((random() % max_count + 1) & ALIGN_MASK) + low;
433                         if (high > max_count)
434                                 high = max_count;
435                         interval_set(&n->node, low, high);
436                         while (interval_insert(&n->node, &root))
437                                 interval_set(&n->node, low, ++high);
438                         dprintf("Adding a node "__S"\n", 
439                                 __F(&n->node.in_extent));
440                         n->valid = 1;
441                         list_add(&n->list, &header);
442                 }
443         }
444
445         return root;
446 }
447
448 static struct interval_node *it_test_init(int count)
449 {
450         int i;
451         uint64_t high, low, len;
452         struct it_node *n;
453         struct interval_node *root = NULL;
454
455         it_count = count;
456         it_array = (struct it_node *)malloc(sizeof(struct it_node) * count);
457         if (it_array == NULL)
458                 error("it_array == NULL, no memory\n");
459
460         have_wide_lock = 0;
461         for (i = 0; i < count; i++) {
462                 n = &it_array[i];
463                 do {
464                         low = (random() % max_count + 1) & ALIGN_MASK;
465                         len = (random() % 256 + 1) * ALIGN_SIZE;
466                         if (!have_wide_lock && !(random() % count)) {
467                                 low = 0;
468                                 len = max_count;
469                                 have_wide_lock = 1;
470                         }
471                         high = low + (len & ALIGN_MASK);
472
473                         interval_set(&n->node, low, high);
474                 } while (interval_insert(&n->node, &root));
475                 n->hit = 0;
476                 n->valid = 1;
477                 if (i == 0)
478                         list_add_tail(&n->list, &header);
479                 else
480                         list_add_tail(&n->list, &it_array[rand()%i].list);
481         }
482
483         return root;
484 }
485
486 static void it_test_fini(void)
487 {
488         free(it_array);
489         it_array = NULL;
490         it_count = 0;
491         max_count = 0;
492 }
493
494 int main(int argc, char *argv[])
495 {
496         int count = 5, perf = 0;
497         struct interval_node *root;
498         struct timeval tv;
499
500         gettimeofday(&tv, NULL);
501         srandom(tv.tv_usec);
502
503         if (argc == 2) {
504                 if (strcmp(argv[1], "-p"))
505                         error("Unknow options, usage: %s [-p]\n", argv[0]);
506                 perf = 1;
507                 count = 1;
508         }
509
510         if (perf) {
511                 int M = 1024 * 1024;
512                 root = it_test_init(1000000);
513                 printf("1M locks with 4K request size\n");
514                 it_test_performance(root, 4096);
515                 printf("1M locks with 128K request size\n");
516                 it_test_performance(root, 128 * 1024);
517                 printf("1M locks with 256K request size\n");
518                 it_test_performance(root, 256 * 1024);
519                 printf("1M locks with 1M request size\n");
520                 it_test_performance(root, 1 * M);
521                 printf("1M locks with 16M request size\n");
522                 it_test_performance(root, 16 * M);
523                 printf("1M locks with 32M request size\n");
524                 it_test_performance(root, 32 * M);
525                 printf("1M locks with 64M request size\n");
526                 it_test_performance(root, 64 * M);
527                 printf("1M locks with 128M request size\n");
528                 it_test_performance(root, 128 * M);
529                 printf("1M locks with 256M request size\n");
530                 it_test_performance(root, 256 * M);
531                 printf("1M locks with 512M request size\n");
532                 it_test_performance(root, 512 * M);
533                 printf("1M locks with 1G request size\n");
534                 it_test_performance(root, 1024 * M);
535                 printf("1M locks with 2G request size\n");
536                 it_test_performance(root, 2048 * M);
537                 printf("1M locks with 3G request size\n");
538                 it_test_performance(root, 3072 * M);
539                 printf("1M locks with 4G request size\n");
540                 it_test_performance(root, max_count - 1);
541                 it_test_fini();
542                 return 0;
543         }
544
545         root = it_test_init(random() % 100000 + 1000);
546         while (count--) {
547                 it_test_sanity(root);
548                 it_test_iterate(root);
549                 it_test_iterate_reverse(root);
550                 it_test_find(root);
551                 it_test_search_hole(root);
552                 it_test_search(root);
553                 root = it_test_helper(root);
554         }
555         it_test_fini();
556
557         return 0;
558 }