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