lustre/tests/it_test.c

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