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         init_path(&path);
  44         ret = setup_key(radix, &key, 0);
  45         sprintf(buf, "str-%Lu\n", key.objectid);
  46         ret = insert_item(root, &key, buf, strlen(buf));
  47         if (ret)
  48                 goto error;
  49         radix_tree_preload(GFP_KERNEL);
  50         ret = radix_tree_insert(radix, key.objectid,
  51                                         (void *)key.objectid);
  52         radix_tree_preload_end();
  53         if (ret)
  54                 goto error;
  55         return ret;
  56 error:
  57         printf("failed to insert %Lu\n", key.objectid);
  58         return -1;
  59 }
  60
  61 static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
  62 {
  63         struct ctree_path path;
  64         struct key key;
  65         int ret;
  66         char buf[128];
  67         init_path(&path);
  68         ret = setup_key(radix, &key, 1);
  69         if (ret < 0)
  70                 return 0;
  71         sprintf(buf, "str-%Lu\n", key.objectid);
  72         ret = insert_item(root, &key, buf, strlen(buf));
  73         if (ret != -EEXIST) {
  74                 printf("insert on %Lu gave us %d\n", key.objectid, ret);
  75                 return 1;
  76         }
  77         return 0;
  78 }
  79
  80 static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
  81 {
  82         struct ctree_path path;
  83         struct key key;
  84         int ret;
  85         unsigned long *ptr;
  86         init_path(&path);
  87         ret = setup_key(radix, &key, 1);
  88         if (ret < 0)
  89                 return 0;
  90         ret = search_slot(root, &key, &path, -1);
  91         if (ret)
  92                 goto error;
  93         ret = del_item(root, &path);
  94         release_path(root, &path);
  95         if (ret != 0)
  96                 goto error;
  97         ptr = radix_tree_delete(radix, key.objectid);
  98         if (!ptr)
  99                 goto error;
 100         return 0;
 101 error:
 102         printf("failed to delete %Lu\n", key.objectid);
 103         return -1;
 104 }
 105
 106 static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
 107 {
 108         struct ctree_path path;
 109         struct key key;
 110         int ret;
 111         init_path(&path);
 112         ret = setup_key(radix, &key, 1);
 113         if (ret < 0)
 114                 return 0;
 115         ret = search_slot(root, &key, &path, 0);
 116         release_path(root, &path);
 117         if (ret)
 118                 goto error;
 119         return 0;
 120 error:
 121         printf("unable to find key %Lu\n", key.objectid);
 122         return -1;
 123 }
 124
 125 static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
 126 {
 127         struct ctree_path path;
 128         struct key key;
 129         int ret;
 130         init_path(&path);
 131         ret = setup_key(radix, &key, 0);
 132         if (ret < 0)
 133                 return ret;
 134         ret = search_slot(root, &key, &path, 0);
 135         release_path(root, &path);
 136         if (ret == 0)
 137                 goto error;
 138         return 0;
 139 error:
 140         printf("able to find key that should not exist %Lu\n", key.objectid);
 141         return -1;
 142 }
 143
 144 int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
 145 { ins_one, insert_dup, del_one, lookup_item, lookup_enoent };
 146
 147 static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
 148 {
 149         struct ctree_path path;
 150         struct key key;
 151         unsigned long found;
 152         int ret;
 153         int slot;
 154         int i;
 155         key.offset = 0;
 156         key.flags = 0;
 157         key.objectid = (unsigned long)-1;
 158         while(1) {
 159                 init_path(&path);
 160                 ret = search_slot(root, &key, &path, 0);
 161                 slot = path.slots[0];
 162                 if (ret != 0) {
 163                         if (slot == 0) {
 164                                 release_path(root, &path);
 165                                 break;
 166                         }
 167                         slot -= 1;
 168                 }
 169                 for (i = slot; i >= 0; i--) {
 170                         found = path.nodes[0]->leaf.items[i].key.objectid;
 171                         radix_tree_preload(GFP_KERNEL);
 172                         ret = radix_tree_insert(radix, found, (void *)found);
 173                         if (ret) {
 174                                 fprintf(stderr,
 175                                         "failed to insert %lu into radix\n",
 176                                         found);
 177                                 exit(1);
 178                         }
 179
 180                         radix_tree_preload_end();
 181                 }
 182                 release_path(root, &path);
 183                 key.objectid = found - 1;
 184                 if (key.objectid > found)
 185                         break;
 186         }
 187         return 0;
 188 }
 189
 190 void sigstopper(int ignored)
 191 {
 192         keep_running = 0;
 193         fprintf(stderr, "caught exit signal, stopping\n");
 194 }
 195
 196 int print_usage(void)
 197 {
 198         printf("usage: tester [-ih] [-c count] [-f count]\n");
 199         printf("\t -c count -- iteration count after filling\n");
 200         printf("\t -f count -- run this many random inserts before starting\n");
 201         printf("\t -i       -- only do initial fill\n");
 202         printf("\t -h       -- this help text\n");
 203         exit(1);
 204 }
 205 int main(int ac, char **av)
 206 {
 207         RADIX_TREE(radix, GFP_KERNEL);
 208         struct ctree_super_block super;
 209         struct ctree_root *root;
 210         int i;
 211         int ret;
 212         int count;
 213         int op;
 214         int iterations = 20000;
 215         int init_fill_count = 800000;
 216         int err = 0;
 217         int initial_only = 0;
 218         radix_tree_init();
 219         root = open_ctree("dbfile", &super);
 220         fill_radix(root, &radix);
 221
 222         signal(SIGTERM, sigstopper);
 223         signal(SIGINT, sigstopper);
 224
 225         for (i = 1 ; i < ac ; i++) {
 226                 if (strcmp(av[i], "-i") == 0) {
 227                         initial_only = 1;
 228                 } else if (strcmp(av[i], "-c") == 0) {
 229                         iterations = atoi(av[i+1]);
 230                         i++;
 231                 } else if (strcmp(av[i], "-f") == 0) {
 232                         init_fill_count = atoi(av[i+1]);
 233                         i++;
 234                 } else {
 235                         print_usage();
 236                 }
 237         }
 238         for (i = 0; i < init_fill_count; i++) {
 239                 ret = ins_one(root, &radix);
 240                 if (ret) {
 241                         printf("initial fill failed\n");
 242                         err = ret;
 243                         goto out;
 244                 }
 245                 if (i % 10000 == 0) {
 246                         printf("initial fill %d level %d count %d\n", i,
 247                                 node_level(root->node->node.header.flags),
 248                                 root->node->node.header.nritems);
 249                 }
 250                 if (keep_running == 0) {
 251                         err = 0;
 252                         goto out;
 253                 }
 254         }
 255         if (initial_only == 1) {
 256                 goto out;
 257         }
 258         for (i = 0; i < iterations; i++) {
 259                 op = rand() % ARRAY_SIZE(ops);
 260                 count = rand() % 128;
 261                 if (i % 2000 == 0) {
 262                         printf("%d\n", i);
 263                         fflush(stdout);
 264                 }
 265                 if (i && i % 5000 == 0) {
 266                         printf("open & close, root level %d nritems %d\n",
 267                                 node_level(root->node->node.header.flags),
 268                                 root->node->node.header.nritems);
 269                         write_ctree_super(root, &super);
 270                         close_ctree(root);
 271                         root = open_ctree("dbfile", &super);
 272                 }
 273                 while(count--) {
 274                         ret = ops[op](root, &radix);
 275                         if (ret) {
 276                                 fprintf(stderr, "op %d failed %d:%d\n",
 277                                         op, i, iterations);
 278                                 print_tree(root, root->node);
 279                                 fprintf(stderr, "op %d failed %d:%d\n",
 280                                         op, i, iterations);
 281                                 err = ret;
 282                                 goto out;
 283                         }
 284                         if (keep_running == 0) {
 285                                 err = 0;
 286                                 goto out;
 287                         }
 288                 }
 289         }
 290 out:
 291         write_ctree_super(root, &super);
 292         close_ctree(root);
 293         return err;
 294 }
 295