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, ¶ms); 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"); 233