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