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