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 rhashtable_params test_rht_params = {
  53         .head_offset = offsetof(struct test_obj, node),
  54         .key_offset = offsetof(struct test_obj, value),
  55         .key_len = sizeof(int),
  56         .hashfn = jhash,
  57         .nulls_base = (3U << RHT_BASE_SHIFT),
  58 };
  59
  60 static int __init test_rht_lookup(struct rhashtable *ht)
  61 {
  62         unsigned int i;
  63
  64         for (i = 0; i < entries * 2; i++) {
  65                 struct test_obj *obj;
  66                 bool expected = !(i % 2);
  67                 u32 key = i;
  68
  69                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
  70
  71                 if (expected && !obj) {
  72                         pr_warn("Test failed: Could not find key %u\n", key);
  73                         return -ENOENT;
  74                 } else if (!expected && obj) {
  75                         pr_warn("Test failed: Unexpected entry found for key %u\n",
  76                                 key);
  77                         return -EEXIST;
  78                 } else if (expected && obj) {
  79                         if (obj->value != i) {
  80                                 pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
  81                                         obj->value, i);
  82                                 return -EINVAL;
  83                         }
  84                 }
  85         }
  86
  87         return 0;
  88 }
  89
  90 static void test_bucket_stats(struct rhashtable *ht, bool quiet)
  91 {
  92         unsigned int cnt, rcu_cnt, i, total = 0;
  93         struct rhash_head *pos;
  94         struct test_obj *obj;
  95         struct bucket_table *tbl;
  96
  97         tbl = rht_dereference_rcu(ht->tbl, ht);
  98         for (i = 0; i < tbl->size; i++) {
  99                 rcu_cnt = cnt = 0;
 100
 101                 if (!quiet)
 102                         pr_info(" [%#4x/%u]", i, tbl->size);
 103
 104                 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
 105                         cnt++;
 106                         total++;
 107                         if (!quiet)
 108                                 pr_cont(" [%p],", obj);
 109                 }
 110
 111                 rht_for_each_entry_rcu(obj, pos, tbl, i, node)
 112                         rcu_cnt++;
 113
 114                 if (rcu_cnt != cnt)
 115                         pr_warn("Test failed: Chain count mismach %d != %d",
 116                                 cnt, rcu_cnt);
 117
 118                 if (!quiet)
 119                         pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
 120                                 i, tbl->buckets[i], cnt);
 121         }
 122
 123         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d\n",
 124                 total, atomic_read(&ht->nelems), entries);
 125
 126         if (total != atomic_read(&ht->nelems) || total != entries)
 127                 pr_warn("Test failed: Total count mismatch ^^^");
 128 }
 129
 130 static s64 __init test_rhashtable(struct rhashtable *ht)
 131 {
 132         struct bucket_table *tbl;
 133         struct test_obj *obj;
 134         struct rhash_head *pos, *next;
 135         int err;
 136         unsigned int i;
 137         s64 start, end;
 138
 139         /*
 140          * Insertion Test:
 141          * Insert entries into table with all keys even numbers
 142          */
 143         pr_info("  Adding %d keys\n", entries);
 144         start = ktime_get_ns();
 145         for (i = 0; i < entries; i++) {
 146                 struct test_obj *obj;
 147
 148                 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
 149                 if (!obj) {
 150                         err = -ENOMEM;
 151                         goto error;
 152                 }
 153
 154                 obj->value = i * 2;
 155
 156                 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
 157                 if (err) {
 158                         kfree(obj);
 159                         goto error;
 160                 }
 161         }
 162
 163         rcu_read_lock();
 164         test_bucket_stats(ht, true);
 165         test_rht_lookup(ht);
 166         rcu_read_unlock();
 167
 168         rcu_read_lock();
 169         test_bucket_stats(ht, true);
 170         rcu_read_unlock();
 171
 172         pr_info("  Deleting %d keys\n", entries);
 173         for (i = 0; i < entries; i++) {
 174                 u32 key = i * 2;
 175
 176                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 177                 BUG_ON(!obj);
 178
 179                 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
 180                 kfree(obj);
 181         }
 182
 183         end = ktime_get_ns();
 184         pr_info("  Duration of test: %lld ns\n", end - start);
 185
 186         return end - start;
 187
 188 error:
 189         tbl = rht_dereference_rcu(ht->tbl, ht);
 190         for (i = 0; i < tbl->size; i++)
 191                 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
 192                         kfree(obj);
 193
 194         return err;
 195 }
 196
 197 static struct rhashtable ht;
 198
 199 static int __init test_rht_init(void)
 200 {
 201         int i, err;
 202         u64 total_time = 0;
 203
 204         entries = min(entries, MAX_ENTRIES);
 205
 206         test_rht_params.automatic_shrinking = shrinking;
 207         test_rht_params.max_size = max_size;
 208         test_rht_params.nelem_hint = size;
 209
 210         pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
 211                 size, max_size, shrinking);
 212
 213         for (i = 0; i < runs; i++) {
 214                 s64 time;
 215
 216                 pr_info("Test %02d:\n", i);
 217                 err = rhashtable_init(&ht, &test_rht_params);
 218                 if (err < 0) {
 219                         pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 220                                 err);
 221                         continue;
 222                 }
 223
 224                 time = test_rhashtable(&ht);
 225                 rhashtable_destroy(&ht);
 226                 if (time < 0) {
 227                         pr_warn("Test failed: return code %lld\n", time);
 228                         return -EINVAL;
 229                 }
 230
 231                 total_time += time;
 232         }
 233
 234         pr_info("Average test time: %llu\n", total_time / runs);
 235
 236         return 0;
 237 }
 238
 239 static void __exit test_rht_exit(void)
 240 {
 241 }
 242
 243 module_init(test_rht_init);
 244 module_exit(test_rht_exit);
 245
 246 MODULE_LICENSE("GPL v2");