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