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