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
35struct test_obj {
36	void			*ptr;
37	int			value;
38	struct rhash_head	node;
39};
40
41static 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
50static 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
80static 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
120static 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
174error:
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
183static struct rhashtable ht;
184
185static 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
205static void __exit test_rht_exit(void)
206{
207}
208
209module_init(test_rht_init);
210module_exit(test_rht_exit);
211
212MODULE_LICENSE("GPL v2");
213