random-test.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <signal.h>
   4 #include "kerncompat.h"
   5 #include "radix-tree.h"
   6 #include "ctree.h"
   7 #include "disk-io.h"
   8 #include "print-tree.h"
   9
  10 int keep_running = 1;
  11
  12 static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
  13 {
  14         int num = rand();
  15         unsigned long res[2];
  16         int ret;
  17
  18         key->flags = 0;
  19         key->offset = 0;
  20 again:
  21         ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
  22         if (exists) {
  23                 if (ret == 0)
  24                         return -1;
  25                 num = res[0];
  26         } else if (ret != 0 && num == res[0]) {
  27                 num++;
  28                 if (ret > 1 && num == res[1]) {
  29                         num++;
  30                         goto again;
  31                 }
  32         }
  33         key->objectid = num;
  34         return 0;
  35 }
  36
  37 static int ins_one(struct ctree_root *root, struct radix_tree_root *radix)
  38 {
  39         struct ctree_path path;
  40         struct key key;
  41         int ret;
  42         char buf[128];
  43         unsigned long oid;
  44         init_path(&path);
  45         ret = setup_key(radix, &key, 0);
  46         sprintf(buf, "str-%Lu\n", key.objectid);
  47         ret = insert_item(root, &key, buf, strlen(buf));
  48         if (ret)
  49                 goto error;
  50         oid = (unsigned long)key.objectid;
  51         radix_tree_preload(GFP_KERNEL);
  52         ret = radix_tree_insert(radix, oid, (void *)oid);
  53         radix_tree_preload_end();
  54         if (ret)
  55                 goto error;
  56         return ret;
  57 error:
  58         printf("failed to insert %Lu\n", key.objectid);
  59         return -1;
  60 }
  61
  62 static int run_commit(struct ctree_root *root, struct radix_tree_root *radix)
  63 {
  64         return commit_transaction(root);
  65 }
  66
  67 static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
  68 {
  69         struct ctree_path path;
  70         struct key key;
  71         int ret;
  72         char buf[128];
  73         init_path(&path);
  74         ret = setup_key(radix, &key, 1);
  75         if (ret < 0)
  76                 return 0;
  77         sprintf(buf, "str-%Lu\n", key.objectid);
  78         ret = insert_item(root, &key, buf, strlen(buf));
  79         if (ret != -EEXIST) {
  80                 printf("insert on %Lu gave us %d\n", key.objectid, ret);
  81                 return 1;
  82         }
  83         return 0;
  84 }
  85
  86 static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
  87 {
  88         struct ctree_path path;
  89         struct key key;
  90         int ret;
  91         unsigned long *ptr;
  92         init_path(&path);
  93         ret = setup_key(radix, &key, 1);
  94         if (ret < 0)
  95                 return 0;
  96         ret = search_slot(root, &key, &path, -1);
  97         if (ret)
  98                 goto error;
  99         ret = del_item(root, &path);
 100         release_path(root, &path);
 101         if (ret != 0)
 102                 goto error;
 103         ptr = radix_tree_delete(radix, key.objectid);
 104         if (!ptr)
 105                 goto error;
 106         return 0;
 107 error:
 108         printf("failed to delete %Lu\n", key.objectid);
 109         return -1;
 110 }
 111
 112 static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
 113 {
 114         struct ctree_path path;
 115         struct key key;
 116         int ret;
 117         init_path(&path);
 118         ret = setup_key(radix, &key, 1);
 119         if (ret < 0)
 120                 return 0;
 121         ret = search_slot(root, &key, &path, 0);
 122         release_path(root, &path);
 123         if (ret)
 124                 goto error;
 125         return 0;
 126 error:
 127         printf("unable to find key %Lu\n", key.objectid);
 128         return -1;
 129 }
 130
 131 static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
 132 {
 133         struct ctree_path path;
 134         struct key key;
 135         int ret;
 136         init_path(&path);
 137         ret = setup_key(radix, &key, 0);
 138         if (ret < 0)
 139                 return ret;
 140         ret = search_slot(root, &key, &path, 0);
 141         release_path(root, &path);
 142         if (ret <= 0)
 143                 goto error;
 144         return 0;
 145 error:
 146         printf("able to find key that should not exist %Lu\n", key.objectid);
 147         return -1;
 148 }
 149
 150 static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix,
 151                       int nr)
 152 {
 153         struct ctree_path path;
 154         struct key key;
 155         unsigned long found = 0;
 156         int ret;
 157         int slot;
 158         int *ptr;
 159         int count = 0;
 160
 161         key.offset = 0;
 162         key.flags = 0;
 163         key.objectid = (unsigned long)-1;
 164         while(nr-- >= 0) {
 165                 init_path(&path);
 166                 ret = search_slot(root, &key, &path, -1);
 167                 if (ret < 0) {
 168                         release_path(root, &path);
 169                         return ret;
 170                 }
 171                 if (ret != 0) {
 172                         if (path.slots[0] == 0) {
 173                                 release_path(root, &path);
 174                                 break;
 175                         }
 176                         path.slots[0] -= 1;
 177                 }
 178                 slot = path.slots[0];
 179                 found = path.nodes[0]->leaf.items[slot].key.objectid;
 180                 ret = del_item(root, &path);
 181                 count++;
 182                 if (ret) {
 183                         fprintf(stderr,
 184                                 "failed to remove %lu from tree\n",
 185                                 found);
 186                         return -1;
 187                 }
 188                 release_path(root, &path);
 189                 ptr = radix_tree_delete(radix, found);
 190                 if (!ptr)
 191                         goto error;
 192                 if (!keep_running)
 193                         break;
 194         }
 195         return 0;
 196 error:
 197         fprintf(stderr, "failed to delete from the radix %lu\n", found);
 198         return -1;
 199 }
 200
 201 static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
 202                      int count)
 203 {
 204         int i;
 205         int err;
 206         int ret = 0;
 207         for (i = 0; i < count; i++) {
 208                 ret = ins_one(root, radix);
 209                 if (ret) {
 210                         printf("fill failed\n");
 211                         err = ret;
 212                         goto out;
 213                 }
 214                 if (!keep_running)
 215                         break;
 216         }
 217 out:
 218         return ret;
 219 }
 220
 221 static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
 222 {
 223         int ret;
 224         int nr = rand() % 20000;
 225         static int run_nr = 0;
 226
 227         /* do the bulk op much less frequently */
 228         if (run_nr++ % 100)
 229                 return 0;
 230         ret = empty_tree(root, radix, nr);
 231         if (ret)
 232                 return ret;
 233         ret = fill_tree(root, radix, nr);
 234         if (ret)
 235                 return ret;
 236         return 0;
 237 }
 238
 239
 240 int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
 241         { ins_one, insert_dup, del_one, lookup_item,
 242           lookup_enoent, bulk_op, run_commit };
 243
 244 static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
 245 {
 246         struct ctree_path path;
 247         struct key key;
 248         unsigned long found;
 249         int ret;
 250         int slot;
 251         int i;
 252
 253         key.offset = 0;
 254         key.flags = 0;
 255         key.objectid = (unsigned long)-1;
 256         while(1) {
 257                 init_path(&path);
 258                 ret = search_slot(root, &key, &path, 0);
 259                 if (ret < 0) {
 260                         release_path(root, &path);
 261                         return ret;
 262                 }
 263                 slot = path.slots[0];
 264                 if (ret != 0) {
 265                         if (slot == 0) {
 266                                 release_path(root, &path);
 267                                 break;
 268                         }
 269                         slot -= 1;
 270                 }
 271                 for (i = slot; i >= 0; i--) {
 272                         found = path.nodes[0]->leaf.items[i].key.objectid;
 273                         radix_tree_preload(GFP_KERNEL);
 274                         ret = radix_tree_insert(radix, found, (void *)found);
 275                         if (ret) {
 276                                 fprintf(stderr,
 277                                         "failed to insert %lu into radix\n",
 278                                         found);
 279                                 exit(1);
 280                         }
 281
 282                         radix_tree_preload_end();
 283                 }
 284                 release_path(root, &path);
 285                 key.objectid = found - 1;
 286                 if (key.objectid > found)
 287                         break;
 288         }
 289         return 0;
 290 }
 291 void sigstopper(int ignored)
 292 {
 293         keep_running = 0;
 294         fprintf(stderr, "caught exit signal, stopping\n");
 295 }
 296
 297 int print_usage(void)
 298 {
 299         printf("usage: tester [-ih] [-c count] [-f count]\n");
 300         printf("\t -c count -- iteration count after filling\n");
 301         printf("\t -f count -- run this many random inserts before starting\n");
 302         printf("\t -i       -- only do initial fill\n");
 303         printf("\t -h       -- this help text\n");
 304         exit(1);
 305 }
 306 int main(int ac, char **av)
 307 {
 308         RADIX_TREE(radix, GFP_KERNEL);
 309         struct ctree_super_block super;
 310         struct ctree_root *root;
 311         int i;
 312         int ret;
 313         int count;
 314         int op;
 315         int iterations = 20000;
 316         int init_fill_count = 800000;
 317         int err = 0;
 318         int initial_only = 0;
 319         radix_tree_init();
 320         root = open_ctree("dbfile", &super);
 321         fill_radix(root, &radix);
 322
 323         signal(SIGTERM, sigstopper);
 324         signal(SIGINT, sigstopper);
 325
 326         for (i = 1 ; i < ac ; i++) {
 327                 if (strcmp(av[i], "-i") == 0) {
 328                         initial_only = 1;
 329                 } else if (strcmp(av[i], "-c") == 0) {
 330                         iterations = atoi(av[i+1]);
 331                         i++;
 332                 } else if (strcmp(av[i], "-f") == 0) {
 333                         init_fill_count = atoi(av[i+1]);
 334                         i++;
 335                 } else {
 336                         print_usage();
 337                 }
 338         }
 339         printf("initial fill\n");
 340         ret = fill_tree(root, &radix, init_fill_count);
 341         printf("starting run\n");
 342         if (ret) {
 343                 err = ret;
 344                 goto out;
 345         }
 346         if (initial_only == 1) {
 347                 goto out;
 348         }
 349         for (i = 0; i < iterations; i++) {
 350                 op = rand() % ARRAY_SIZE(ops);
 351                 count = rand() % 128;
 352                 if (i % 2000 == 0) {
 353                         printf("%d\n", i);
 354                         fflush(stdout);
 355                 }
 356                 if (i && i % 5000 == 0) {
 357                         printf("open & close, root level %d nritems %d\n",
 358                                 node_level(root->node->node.header.flags),
 359                                 root->node->node.header.nritems);
 360                         write_ctree_super(root, &super);
 361                         close_ctree(root);
 362                         root = open_ctree("dbfile", &super);
 363                 }
 364                 while(count--) {
 365                         ret = ops[op](root, &radix);
 366                         if (ret) {
 367                                 fprintf(stderr, "op %d failed %d:%d\n",
 368                                         op, i, iterations);
 369                                 print_tree(root, root->node);
 370                                 fprintf(stderr, "op %d failed %d:%d\n",
 371                                         op, i, iterations);
 372                                 err = ret;
 373                                 goto out;
 374                         }
 375                         if (ops[op] == bulk_op || ops[op] == run_commit)
 376                                 break;
 377                         if (keep_running == 0) {
 378                                 err = 0;
 379                                 goto out;
 380                         }
 381                 }
 382         }
 383 out:
 384         write_ctree_super(root, &super);
 385         close_ctree(root);
 386         return err;
 387 }
 388