lustre/tests/it_test.c

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