lib/test_rhashtable.c

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
   5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   6  *
   7  * Based on the following paper:
   8  * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
   9  *
  10  * Code partially derived from nft_hash
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License version 2 as
  14  * published by the Free Software Foundation.
  15  */
  16
  17 /**************************************************************************
  18  * Self Test
  19  **************************************************************************/
  20
  21 #include <linux/init.h>
  22 #include <linux/jhash.h>
  23 #include <linux/kernel.h>
  24 #include <linux/module.h>
  25 #include <linux/rcupdate.h>
  26 #include <linux/rhashtable.h>
  27 #include <linux/slab.h>
  28
  29
  30 #define TEST_HT_SIZE    8
  31 #define TEST_ENTRIES    2048
  32 #define TEST_PTR        ((void *) 0xdeadbeef)
  33 #define TEST_NEXPANDS   4
  34
  35 struct test_obj {
  36         void                    *ptr;
  37         int                     value;
  38         struct rhash_head       node;
  39 };
  40
  41 static int __init test_rht_lookup(struct rhashtable *ht)
  42 {
  43         unsigned int i;
  44
  45         for (i = 0; i < TEST_ENTRIES * 2; i++) {
  46                 struct test_obj *obj;
  47                 bool expected = !(i % 2);
  48                 u32 key = i;
  49
  50                 obj = rhashtable_lookup(ht, &key);
  51
  52                 if (expected && !obj) {
  53                         pr_warn("Test failed: Could not find key %u\n", key);
  54                         return -ENOENT;
  55                 } else if (!expected && obj) {
  56                         pr_warn("Test failed: Unexpected entry found for key %u\n",
  57                                 key);
  58                         return -EEXIST;
  59                 } else if (expected && obj) {
  60                         if (obj->ptr != TEST_PTR || obj->value != i) {
  61                                 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
  62                                         obj->ptr, TEST_PTR, obj->value, i);
  63                                 return -EINVAL;
  64                         }
  65                 }
  66         }
  67
  68         return 0;
  69 }
  70
  71 static void test_bucket_stats(struct rhashtable *ht, bool quiet)
  72 {
  73         unsigned int cnt, rcu_cnt, i, total = 0;
  74         struct rhash_head *pos;
  75         struct test_obj *obj;
  76         struct bucket_table *tbl;
  77
  78         tbl = rht_dereference_rcu(ht->tbl, ht);
  79         for (i = 0; i < tbl->size; i++) {
  80                 rcu_cnt = cnt = 0;
  81
  82                 if (!quiet)
  83                         pr_info(" [%#4x/%zu]", i, tbl->size);
  84
  85                 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
  86                         cnt++;
  87                         total++;
  88                         if (!quiet)
  89                                 pr_cont(" [%p],", obj);
  90                 }
  91
  92                 rht_for_each_entry_rcu(obj, pos, tbl, i, node)
  93                         rcu_cnt++;
  94
  95                 if (rcu_cnt != cnt)
  96                         pr_warn("Test failed: Chain count mismach %d != %d",
  97                                 cnt, rcu_cnt);
  98
  99                 if (!quiet)
 100                         pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
 101                                 i, tbl->buckets[i], cnt);
 102         }
 103
 104         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d\n",
 105                 total, atomic_read(&ht->nelems), TEST_ENTRIES);
 106
 107         if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES)
 108                 pr_warn("Test failed: Total count mismatch ^^^");
 109 }
 110
 111 static int __init test_rhashtable(struct rhashtable *ht)
 112 {
 113         struct bucket_table *tbl;
 114         struct test_obj *obj;
 115         struct rhash_head *pos, *next;
 116         int err;
 117         unsigned int i;
 118
 119         /*
 120          * Insertion Test:
 121          * Insert TEST_ENTRIES into table with all keys even numbers
 122          */
 123         pr_info("  Adding %d keys\n", TEST_ENTRIES);
 124         for (i = 0; i < TEST_ENTRIES; i++) {
 125                 struct test_obj *obj;
 126
 127                 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
 128                 if (!obj) {
 129                         err = -ENOMEM;
 130                         goto error;
 131                 }
 132
 133                 obj->ptr = TEST_PTR;
 134                 obj->value = i * 2;
 135
 136                 rhashtable_insert(ht, &obj->node);
 137         }
 138
 139         rcu_read_lock();
 140         test_bucket_stats(ht, true);
 141         test_rht_lookup(ht);
 142         rcu_read_unlock();
 143
 144         for (i = 0; i < TEST_NEXPANDS; i++) {
 145                 pr_info("  Table expansion iteration %u...\n", i);
 146                 mutex_lock(&ht->mutex);
 147                 rhashtable_expand(ht);
 148                 mutex_unlock(&ht->mutex);
 149
 150                 rcu_read_lock();
 151                 pr_info("  Verifying lookups...\n");
 152                 test_rht_lookup(ht);
 153                 rcu_read_unlock();
 154         }
 155
 156         for (i = 0; i < TEST_NEXPANDS; i++) {
 157                 pr_info("  Table shrinkage iteration %u...\n", i);
 158                 mutex_lock(&ht->mutex);
 159                 rhashtable_shrink(ht);
 160                 mutex_unlock(&ht->mutex);
 161
 162                 rcu_read_lock();
 163                 pr_info("  Verifying lookups...\n");
 164                 test_rht_lookup(ht);
 165                 rcu_read_unlock();
 166         }
 167
 168         rcu_read_lock();
 169         test_bucket_stats(ht, true);
 170         rcu_read_unlock();
 171
 172         pr_info("  Deleting %d keys\n", TEST_ENTRIES);
 173         for (i = 0; i < TEST_ENTRIES; i++) {
 174                 u32 key = i * 2;
 175
 176                 obj = rhashtable_lookup(ht, &key);
 177                 BUG_ON(!obj);
 178
 179                 rhashtable_remove(ht, &obj->node);
 180                 kfree(obj);
 181         }
 182
 183         return 0;
 184
 185 error:
 186         tbl = rht_dereference_rcu(ht->tbl, ht);
 187         for (i = 0; i < tbl->size; i++)
 188                 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
 189                         kfree(obj);
 190
 191         return err;
 192 }
 193
 194 static struct rhashtable ht;
 195
 196 static int __init test_rht_init(void)
 197 {
 198         struct rhashtable_params params = {
 199                 .nelem_hint = TEST_HT_SIZE,
 200                 .head_offset = offsetof(struct test_obj, node),
 201                 .key_offset = offsetof(struct test_obj, value),
 202                 .key_len = sizeof(int),
 203                 .hashfn = jhash,
 204                 .max_shift = 1, /* we expand/shrink manually here */
 205                 .nulls_base = (3U << RHT_BASE_SHIFT),
 206         };
 207         int err;
 208
 209         pr_info("Running resizable hashtable tests...\n");
 210
 211         err = rhashtable_init(&ht, &params);
 212         if (err < 0) {
 213                 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 214                         err);
 215                 return err;
 216         }
 217
 218         err = test_rhashtable(&ht);
 219
 220         rhashtable_destroy(&ht);
 221
 222         return err;
 223 }
 224
 225 static void __exit test_rht_exit(void)
 226 {
 227 }
 228
 229 module_init(test_rht_init);
 230 module_exit(test_rht_exit);
 231
 232 MODULE_LICENSE("GPL v2");