lib/test_rhashtable.c

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
   5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License version 2 as
   9  * published by the Free Software Foundation.
  10  */
  11
  12 /**************************************************************************
  13  * Self Test
  14  **************************************************************************/
  15
  16 #include <linux/init.h>
  17 #include <linux/jhash.h>
  18 #include <linux/kernel.h>
  19 #include <linux/module.h>
  20 #include <linux/rcupdate.h>
  21 #include <linux/rhashtable.h>
  22 #include <linux/slab.h>
  23
  24
  25 #define MAX_ENTRIES     1000000
  26
  27 static int entries = 50000;
  28 module_param(entries, int, 0);
  29 MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)");
  30
  31 static int runs = 4;
  32 module_param(runs, int, 0);
  33 MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
  34
  35 static int max_size = 65536;
  36 module_param(max_size, int, 0);
  37 MODULE_PARM_DESC(runs, "Maximum table size (default: 65536)");
  38
  39 static bool shrinking = false;
  40 module_param(shrinking, bool, 0);
  41 MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
  42
  43 static int size = 8;
  44 module_param(size, int, 0);
  45 MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
  46
  47 struct test_obj {
  48         int                     value;
  49         struct rhash_head       node;
  50 };
  51
  52 static struct test_obj array[MAX_ENTRIES];
  53
  54 static struct rhashtable_params test_rht_params = {
  55         .head_offset = offsetof(struct test_obj, node),
  56         .key_offset = offsetof(struct test_obj, value),
  57         .key_len = sizeof(int),
  58         .hashfn = jhash,
  59         .nulls_base = (3U << RHT_BASE_SHIFT),
  60 };
  61
  62 static int __init test_rht_lookup(struct rhashtable *ht)
  63 {
  64         unsigned int i;
  65
  66         for (i = 0; i < entries * 2; i++) {
  67                 struct test_obj *obj;
  68                 bool expected = !(i % 2);
  69                 u32 key = i;
  70
  71                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
  72
  73                 if (expected && !obj) {
  74                         pr_warn("Test failed: Could not find key %u\n", key);
  75                         return -ENOENT;
  76                 } else if (!expected && obj) {
  77                         pr_warn("Test failed: Unexpected entry found for key %u\n",
  78                                 key);
  79                         return -EEXIST;
  80                 } else if (expected && obj) {
  81                         if (obj->value != i) {
  82                                 pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
  83                                         obj->value, i);
  84                                 return -EINVAL;
  85                         }
  86                 }
  87         }
  88
  89         return 0;
  90 }
  91
  92 static void test_bucket_stats(struct rhashtable *ht)
  93 {
  94         unsigned int err, total = 0, chain_len = 0;
  95         struct rhashtable_iter hti;
  96         struct rhash_head *pos;
  97
  98         err = rhashtable_walk_init(ht, &hti);
  99         if (err) {
 100                 pr_warn("Test failed: allocation error");
 101                 return;
 102         }
 103
 104         err = rhashtable_walk_start(&hti);
 105         if (err && err != -EAGAIN) {
 106                 pr_warn("Test failed: iterator failed: %d\n", err);
 107                 return;
 108         }
 109
 110         while ((pos = rhashtable_walk_next(&hti))) {
 111                 if (PTR_ERR(pos) == -EAGAIN) {
 112                         pr_info("Info: encountered resize\n");
 113                         chain_len++;
 114                         continue;
 115                 } else if (IS_ERR(pos)) {
 116                         pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
 117                                 PTR_ERR(pos));
 118                         break;
 119                 }
 120
 121                 total++;
 122         }
 123
 124         rhashtable_walk_stop(&hti);
 125         rhashtable_walk_exit(&hti);
 126
 127         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
 128                 total, atomic_read(&ht->nelems), entries, chain_len);
 129
 130         if (total != atomic_read(&ht->nelems) || total != entries)
 131                 pr_warn("Test failed: Total count mismatch ^^^");
 132 }
 133
 134 static s64 __init test_rhashtable(struct rhashtable *ht)
 135 {
 136         struct test_obj *obj;
 137         int err;
 138         unsigned int i;
 139         s64 start, end;
 140
 141         /*
 142          * Insertion Test:
 143          * Insert entries into table with all keys even numbers
 144          */
 145         pr_info("  Adding %d keys\n", entries);
 146         start = ktime_get_ns();
 147         for (i = 0; i < entries; i++) {
 148                 struct test_obj *obj = &array[i];
 149
 150                 obj->value = i * 2;
 151
 152                 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
 153                 if (err)
 154                         return err;
 155         }
 156
 157         test_bucket_stats(ht);
 158         rcu_read_lock();
 159         test_rht_lookup(ht);
 160         rcu_read_unlock();
 161
 162         test_bucket_stats(ht);
 163
 164         pr_info("  Deleting %d keys\n", entries);
 165         for (i = 0; i < entries; i++) {
 166                 u32 key = i * 2;
 167
 168                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 169                 BUG_ON(!obj);
 170
 171                 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
 172         }
 173
 174         end = ktime_get_ns();
 175         pr_info("  Duration of test: %lld ns\n", end - start);
 176
 177         return end - start;
 178 }
 179
 180 static struct rhashtable ht;
 181
 182 static int __init test_rht_init(void)
 183 {
 184         int i, err;
 185         u64 total_time = 0;
 186
 187         entries = min(entries, MAX_ENTRIES);
 188
 189         test_rht_params.automatic_shrinking = shrinking;
 190         test_rht_params.max_size = max_size;
 191         test_rht_params.nelem_hint = size;
 192
 193         pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
 194                 size, max_size, shrinking);
 195
 196         for (i = 0; i < runs; i++) {
 197                 s64 time;
 198
 199                 pr_info("Test %02d:\n", i);
 200                 memset(&array, 0, sizeof(array));
 201                 err = rhashtable_init(&ht, &test_rht_params);
 202                 if (err < 0) {
 203                         pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 204                                 err);
 205                         continue;
 206                 }
 207
 208                 time = test_rhashtable(&ht);
 209                 rhashtable_destroy(&ht);
 210                 if (time < 0) {
 211                         pr_warn("Test failed: return code %lld\n", time);
 212                         return -EINVAL;
 213                 }
 214
 215                 total_time += time;
 216         }
 217
 218         pr_info("Average test time: %llu\n", total_time / runs);
 219
 220         return 0;
 221 }
 222
 223 static void __exit test_rht_exit(void)
 224 {
 225 }
 226
 227 module_init(test_rht_init);
 228 module_exit(test_rht_exit);
 229
 230 MODULE_LICENSE("GPL v2");