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