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