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 TEST_PTR        ((void *) 0xdeadbeef)
  26 #define MAX_ENTRIES     1000000
  27
  28 static int entries = 50000;
  29 module_param(entries, int, 0);
  30 MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)");
  31
  32 static int runs = 4;
  33 module_param(runs, int, 0);
  34 MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
  35
  36 static int max_size = 65536;
  37 module_param(max_size, int, 0);
  38 MODULE_PARM_DESC(runs, "Maximum table size (default: 65536)");
  39
  40 static bool shrinking = false;
  41 module_param(shrinking, bool, 0);
  42 MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
  43
  44 static int size = 8;
  45 module_param(size, int, 0);
  46 MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
  47
  48 struct test_obj {
  49         void                    *ptr;
  50         int                     value;
  51         struct rhash_head       node;
  52 };
  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->ptr != TEST_PTR || obj->value != i) {
  82                                 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
  83                                         obj->ptr, TEST_PTR, obj->value, i);
  84                                 return -EINVAL;
  85                         }
  86                 }
  87         }
  88
  89         return 0;
  90 }
  91
  92 static void test_bucket_stats(struct rhashtable *ht, bool quiet)
  93 {
  94         unsigned int cnt, rcu_cnt, i, total = 0;
  95         struct rhash_head *pos;
  96         struct test_obj *obj;
  97         struct bucket_table *tbl;
  98
  99         tbl = rht_dereference_rcu(ht->tbl, ht);
 100         for (i = 0; i < tbl->size; i++) {
 101                 rcu_cnt = cnt = 0;
 102
 103                 if (!quiet)
 104                         pr_info(" [%#4x/%u]", i, tbl->size);
 105
 106                 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
 107                         cnt++;
 108                         total++;
 109                         if (!quiet)
 110                                 pr_cont(" [%p],", obj);
 111                 }
 112
 113                 rht_for_each_entry_rcu(obj, pos, tbl, i, node)
 114                         rcu_cnt++;
 115
 116                 if (rcu_cnt != cnt)
 117                         pr_warn("Test failed: Chain count mismach %d != %d",
 118                                 cnt, rcu_cnt);
 119
 120                 if (!quiet)
 121                         pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
 122                                 i, tbl->buckets[i], cnt);
 123         }
 124
 125         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d\n",
 126                 total, atomic_read(&ht->nelems), entries);
 127
 128         if (total != atomic_read(&ht->nelems) || total != entries)
 129                 pr_warn("Test failed: Total count mismatch ^^^");
 130 }
 131
 132 static s64 __init test_rhashtable(struct rhashtable *ht)
 133 {
 134         struct bucket_table *tbl;
 135         struct test_obj *obj;
 136         struct rhash_head *pos, *next;
 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;
 149
 150                 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
 151                 if (!obj) {
 152                         err = -ENOMEM;
 153                         goto error;
 154                 }
 155
 156                 obj->ptr = TEST_PTR;
 157                 obj->value = i * 2;
 158
 159                 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params);
 160                 if (err) {
 161                         kfree(obj);
 162                         goto error;
 163                 }
 164         }
 165
 166         rcu_read_lock();
 167         test_bucket_stats(ht, true);
 168         test_rht_lookup(ht);
 169         rcu_read_unlock();
 170
 171         rcu_read_lock();
 172         test_bucket_stats(ht, true);
 173         rcu_read_unlock();
 174
 175         pr_info("  Deleting %d keys\n", entries);
 176         for (i = 0; i < entries; i++) {
 177                 u32 key = i * 2;
 178
 179                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 180                 BUG_ON(!obj);
 181
 182                 rhashtable_remove_fast(ht, &obj->node, test_rht_params);
 183                 kfree(obj);
 184         }
 185
 186         end = ktime_get_ns();
 187         pr_info("  Duration of test: %lld ns\n", end - start);
 188
 189         return end - start;
 190
 191 error:
 192         tbl = rht_dereference_rcu(ht->tbl, ht);
 193         for (i = 0; i < tbl->size; i++)
 194                 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
 195                         kfree(obj);
 196
 197         return err;
 198 }
 199
 200 static struct rhashtable ht;
 201
 202 static int __init test_rht_init(void)
 203 {
 204         int i, err;
 205         u64 total_time = 0;
 206
 207         entries = min(entries, MAX_ENTRIES);
 208
 209         test_rht_params.automatic_shrinking = shrinking;
 210         test_rht_params.max_size = max_size;
 211         test_rht_params.nelem_hint = size;
 212
 213         pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
 214                 size, max_size, shrinking);
 215
 216         for (i = 0; i < runs; i++) {
 217                 s64 time;
 218
 219                 pr_info("Test %02d:\n", i);
 220                 err = rhashtable_init(&ht, &test_rht_params);
 221                 if (err < 0) {
 222                         pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 223                                 err);
 224                         continue;
 225                 }
 226
 227                 time = test_rhashtable(&ht);
 228                 rhashtable_destroy(&ht);
 229                 if (time < 0) {
 230                         pr_warn("Test failed: return code %lld\n", time);
 231                         return -EINVAL;
 232                 }
 233
 234                 total_time += time;
 235         }
 236
 237         pr_info("Average test time: %llu\n", total_time / runs);
 238
 239         return 0;
 240 }
 241
 242 static void __exit test_rht_exit(void)
 243 {
 244 }
 245
 246 module_init(test_rht_init);
 247 module_exit(test_rht_exit);
 248
 249 MODULE_LICENSE("GPL v2");