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