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