blob: 1dfeba73fc743718d94551e9356ec8c6580a1fac [file] [log] [blame]
Geert Uytterhoeven9d6dbe12015-01-29 15:40:25 +01001/*
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
35struct test_obj {
36 void *ptr;
37 int value;
38 struct rhash_head node;
39};
40
41static 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
71static 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
111static 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
185error:
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
194static int __init test_rht_init(void)
195{
196 struct rhashtable ht;
197 struct rhashtable_params params = {
198 .nelem_hint = TEST_HT_SIZE,
199 .head_offset = offsetof(struct test_obj, node),
200 .key_offset = offsetof(struct test_obj, value),
201 .key_len = sizeof(int),
202 .hashfn = jhash,
203 .nulls_base = (3U << RHT_BASE_SHIFT),
204 .grow_decision = rht_grow_above_75,
205 .shrink_decision = rht_shrink_below_30,
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
225module_init(test_rht_init);
226
227MODULE_LICENSE("GPL v2");