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"); 213