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;
 249 err:
 250                 count = 1;
 251                 dprintf("node"__S":%llu Child list:\n",
 252                         node->in_extent.start,
 253                         node->in_extent.end,
 254                         node->in_max_high);
 255
 256                 interval_for_each(tmp, node) {
 257                         dprintf(""__S":%llu ",
 258                                 __F(&tmp->in_extent),
 259                                 tmp->in_max_high);
 260                         if (count++ == 8) {
 261                                 dprintf("\n");
 262                                 count = 1;
 263                         }
 264                 }
 265
 266                 error("max high sanity check, has == %d\n", has);
 267         }
 268         node->in_parent = parent;
 269
 270         tmp = node;
 271         while (tmp) {
 272                 if (node_is_black(tmp))
 273                         nr++;
 274                 else if ((tmp->in_left && node_is_red(tmp->in_left)) ||
 275                          (tmp->in_right && node_is_red(tmp->in_right)))
 276                         error("wrong tree, a red node has red child\n");
 277                 tmp = tmp->in_left;
 278         }
 279
 280         tmp = node;
 281         while (tmp) {
 282                 if (node_is_black(tmp))
 283                         nr--;
 284                 tmp = tmp->in_right;
 285         }
 286         if (nr)
 287                 error("wrong tree, unbalanced!\n");
 288
 289         return 0;
 290 }
 291
 292 static int it_test_sanity(struct interval_node *root)
 293 {
 294         it_test_clear();
 295         interval_iterate(root, sanity_cb, NULL);
 296         return 0;
 297 }
 298
 299 static int it_test_search_hole(struct interval_node *root)
 300 {
 301         int i, count = 10;
 302         struct interval_node_extent ext, ext2;
 303         struct it_node *n;
 304         __u64 low = 0, high = ~0;
 305
 306         do {
 307                 if (--count == 0)
 308                         return 0;
 309
 310                 ext.start = random() % max_count;
 311                 ext.end = ext.start;
 312         } while (interval_is_overlapped(root, &ext));
 313         ext2 = ext;
 314
 315         interval_expand(root, &ext, NULL);
 316         dprintf("Extending "__S" to .."__S"\n", __F(&ext2), __F(&ext));
 317         for (i = 0; i < it_count; i++) {
 318                 n = &it_array[i];
 319                 if (n->valid == 0)
 320                         continue;
 321
 322                 if (extent_overlapped(&ext, &n->node.in_extent)) {
 323                         error("Extending "__S" to .."__S" overlaps node"__S"\n",
 324                                 __F(&ext2), __F(&ext), __F(&n->node.in_extent));
 325                 }
 326
 327                 if (n->node.in_extent.end < ext2.start)
 328                         low = max_u64(n->node.in_extent.end + 1, low);
 329
 330                 if (n->node.in_extent.start > ext2.end)
 331                         high = min_u64(n->node.in_extent.start - 1, high);
 332         }
 333
 334         /* only expanding high right now */
 335         if (ext2.start != ext.start || high != ext.end) {
 336                 ext2.start = low, ext2.end = high;
 337                 error("Real extending result:"__S", expected:"__S"\n",
 338                        __F(&ext), __F(&ext2));
 339         }
 340
 341         return 0;
 342 }
 343
 344 static int contended_count = 0;
 345 #define LOOP_COUNT 1000
 346 static enum interval_iter perf_cb(struct interval_node *n, void *args)
 347 {
 348         unsigned long count = LOOP_COUNT;
 349         while (count--);
 350         contended_count++;
 351         return INTERVAL_ITER_CONT;
 352 }
 353
 354 static inline long tv_delta(struct timeval *s, struct timeval *e)
 355 {
 356         long c = e->tv_sec - s->tv_sec;
 357         c *= 1000;
 358         c += (long int)(e->tv_usec - s->tv_usec) / 1000;
 359         dprintf("\tStart: %lu:%lu -> End: %lu:%lu\n",
 360                 s->tv_sec, s->tv_usec, e->tv_sec, e->tv_usec);
 361         return c;
 362 }
 363
 364 static int it_test_performance(struct interval_node *root, unsigned long len)
 365 {
 366         int i = 0, interval_time, list_time;
 367         struct interval_node_extent ext;
 368         struct it_node *n;
 369         struct timeval start, end;
 370         unsigned long count;
 371
 372         ext.start = (random() % (max_count - len)) & ALIGN_MASK;
 373         ext.end = (ext.start + len) & ALIGN_MASK;
 374         if (have_wide_lock) {
 375                 ext.start = (max_count - len) & ALIGN_MASK;
 376                 ext.end = max_count;
 377         }
 378
 379         dprintf("Extent search"__S"\n", __F(&ext));
 380
 381         /* list */
 382         contended_count = 0;
 383         gettimeofday(&start, NULL);
 384         list_for_each_entry(n, &header, list) {
 385                 if (extent_overlapped(&ext, &n->node.in_extent)) {
 386                         count = LOOP_COUNT;
 387                         while (count--);
 388                         contended_count++;
 389                 }
 390         }
 391         gettimeofday(&end, NULL);
 392         list_time = tv_delta(&start, &end);
 393         i = contended_count;
 394
 395         /* interval */
 396         contended_count = 0;
 397         gettimeofday(&start, NULL);
 398         interval_search(root, &ext, perf_cb, &contended_count);
 399         gettimeofday(&end, NULL);
 400         interval_time = tv_delta(&start, &end);
 401
 402         if (i != contended_count)
 403                 error("count of contended lock don't match(%d: %d)\n",
 404                       i, contended_count);
 405
 406         printf("\tList vs Int. search: \n\t\t"
 407                "(%d vs %d)ms, %d contended lock.\n",
 408                 list_time, interval_time, contended_count);
 409
 410         return 0;
 411 }
 412
 413 static struct interval_node *it_test_helper(struct interval_node *root)
 414 {
 415         int idx, count = 0;
 416         struct it_node *n;
 417
 418         count = random() % it_count;
 419         while (count--) {
 420                 idx = random() % it_count;
 421                 n = &it_array[idx];
 422                 if (n->valid) {
 423                         if (!interval_find(root, &n->node.in_extent))
 424                                 error("Cannot find an existent node\n");
 425                         dprintf("Erasing a node "__S"\n",
 426                                 __F(&n->node.in_extent));
 427                         interval_erase(&n->node, &root);
 428                         n->valid = 0;
 429                         list_del_init(&n->list);
 430                 } else {
 431                         __u64 low, high;
 432                         low = (random() % max_count) & ALIGN_MASK;
 433                         high = ((random() % max_count + 1) & ALIGN_MASK) + low;
 434                         if (high > max_count)
 435                                 high = max_count;
 436                         interval_set(&n->node, low, high);
 437                         while (interval_insert(&n->node, &root))
 438                                 interval_set(&n->node, low, ++high);
 439                         dprintf("Adding a node "__S"\n",
 440                                 __F(&n->node.in_extent));
 441                         n->valid = 1;
 442                         list_add(&n->list, &header);
 443                 }
 444         }
 445
 446         return root;
 447 }
 448
 449 static struct interval_node *it_test_init(int count)
 450 {
 451         int i;
 452         uint64_t high, low, len;
 453         struct it_node *n;
 454         struct interval_node *root = NULL;
 455
 456         it_count = count;
 457         it_array = (struct it_node *)malloc(sizeof(struct it_node) * count);
 458         if (it_array == NULL)
 459                 error("it_array == NULL, no memory\n");
 460
 461         have_wide_lock = 0;
 462         for (i = 0; i < count; i++) {
 463                 n = &it_array[i];
 464                 do {
 465                         low = (random() % max_count + 1) & ALIGN_MASK;
 466                         len = (random() % 256 + 1) * ALIGN_SIZE;
 467                         if (!have_wide_lock && !(random() % count)) {
 468                                 low = 0;
 469                                 len = max_count;
 470                                 have_wide_lock = 1;
 471                         }
 472                         high = low + (len & ALIGN_MASK);
 473
 474                         interval_set(&n->node, low, high);
 475                 } while (interval_insert(&n->node, &root));
 476                 n->hit = 0;
 477                 n->valid = 1;
 478                 if (i == 0)
 479                         list_add_tail(&n->list, &header);
 480                 else
 481                         list_add_tail(&n->list, &it_array[rand()%i].list);
 482         }
 483
 484         return root;
 485 }
 486
 487 static void it_test_fini(void)
 488 {
 489         free(it_array);
 490         it_array = NULL;
 491         it_count = 0;
 492         max_count = 0;
 493 }
 494
 495 int main(int argc, char *argv[])
 496 {
 497         int count = 5, perf = 0;
 498         struct interval_node *root;
 499         struct timeval tv;
 500
 501         gettimeofday(&tv, NULL);
 502         srandom(tv.tv_usec);
 503
 504         if (argc == 2) {
 505                 if (strcmp(argv[1], "-p"))
 506                         error("Unknow options, usage: %s [-p]\n", argv[0]);
 507                 perf = 1;
 508                 count = 1;
 509         }
 510
 511         if (perf) {
 512                 int M = 1024 * 1024;
 513                 root = it_test_init(1000000);
 514                 printf("1M locks with 4K request size\n");
 515                 it_test_performance(root, 4096);
 516                 printf("1M locks with 128K request size\n");
 517                 it_test_performance(root, 128 * 1024);
 518                 printf("1M locks with 256K request size\n");
 519                 it_test_performance(root, 256 * 1024);
 520                 printf("1M locks with 1M request size\n");
 521                 it_test_performance(root, 1 * M);
 522                 printf("1M locks with 16M request size\n");
 523                 it_test_performance(root, 16 * M);
 524                 printf("1M locks with 32M request size\n");
 525                 it_test_performance(root, 32 * M);
 526                 printf("1M locks with 64M request size\n");
 527                 it_test_performance(root, 64 * M);
 528                 printf("1M locks with 128M request size\n");
 529                 it_test_performance(root, 128 * M);
 530                 printf("1M locks with 256M request size\n");
 531                 it_test_performance(root, 256 * M);
 532                 printf("1M locks with 512M request size\n");
 533                 it_test_performance(root, 512 * M);
 534                 printf("1M locks with 1G request size\n");
 535                 it_test_performance(root, 1024 * M);
 536                 printf("1M locks with 2G request size\n");
 537                 it_test_performance(root, 2048 * M);
 538                 printf("1M locks with 3G request size\n");
 539                 it_test_performance(root, 3072 * M);
 540                 printf("1M locks with 4G request size\n");
 541                 it_test_performance(root, max_count - 1);
 542                 it_test_fini();
 543                 return 0;
 544         }
 545
 546         root = it_test_init(random() % 100000 + 1000);
 547         while (count--) {
 548                 it_test_sanity(root);
 549                 it_test_iterate(root);
 550                 it_test_iterate_reverse(root);
 551                 it_test_find(root);
 552                 it_test_search_hole(root);
 553                 it_test_search(root);
 554                 root = it_test_helper(root);
 555         }
 556         it_test_fini();
 557
 558         return 0;
 559 }