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