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