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