1// SPDX-License-Identifier: GPL-2.0
2/*
3 * KUnit test for the Kernel Hashtable structures.
4 *
5 * Copyright (C) 2022, Google LLC.
6 * Author: Rae Moar <rmoar@google.com>
7 */
8#include <kunit/test.h>
9
10#include <linux/hashtable.h>
11
12struct hashtable_test_entry {
13	int key;
14	int data;
15	struct hlist_node node;
16	int visited;
17};
18
19static void hashtable_test_hash_init(struct kunit *test)
20{
21	/* Test the different ways of initialising a hashtable. */
22	DEFINE_HASHTABLE(hash1, 2);
23	DECLARE_HASHTABLE(hash2, 3);
24
25	/* When using DECLARE_HASHTABLE, must use hash_init to
26	 * initialize the hashtable.
27	 */
28	hash_init(hash2);
29
30	KUNIT_EXPECT_TRUE(test, hash_empty(hash1));
31	KUNIT_EXPECT_TRUE(test, hash_empty(hash2));
32}
33
34static void hashtable_test_hash_empty(struct kunit *test)
35{
36	struct hashtable_test_entry a;
37	DEFINE_HASHTABLE(hash, 1);
38
39	KUNIT_EXPECT_TRUE(test, hash_empty(hash));
40
41	a.key = 1;
42	a.data = 13;
43	hash_add(hash, &a.node, a.key);
44
45	/* Hashtable should no longer be empty. */
46	KUNIT_EXPECT_FALSE(test, hash_empty(hash));
47}
48
49static void hashtable_test_hash_hashed(struct kunit *test)
50{
51	struct hashtable_test_entry a, b;
52	DEFINE_HASHTABLE(hash, 4);
53
54	a.key = 1;
55	a.data = 13;
56	hash_add(hash, &a.node, a.key);
57	b.key = 1;
58	b.data = 2;
59	hash_add(hash, &b.node, b.key);
60
61	KUNIT_EXPECT_TRUE(test, hash_hashed(&a.node));
62	KUNIT_EXPECT_TRUE(test, hash_hashed(&b.node));
63}
64
65static void hashtable_test_hash_add(struct kunit *test)
66{
67	struct hashtable_test_entry a, b, *x;
68	int bkt;
69	DEFINE_HASHTABLE(hash, 3);
70
71	a.key = 1;
72	a.data = 13;
73	a.visited = 0;
74	hash_add(hash, &a.node, a.key);
75	b.key = 2;
76	b.data = 10;
77	b.visited = 0;
78	hash_add(hash, &b.node, b.key);
79
80	hash_for_each(hash, bkt, x, node) {
81		x->visited++;
82		if (x->key == a.key)
83			KUNIT_EXPECT_EQ(test, x->data, 13);
84		else if (x->key == b.key)
85			KUNIT_EXPECT_EQ(test, x->data, 10);
86		else
87			KUNIT_FAIL(test, "Unexpected key in hashtable.");
88	}
89
90	/* Both entries should have been visited exactly once. */
91	KUNIT_EXPECT_EQ(test, a.visited, 1);
92	KUNIT_EXPECT_EQ(test, b.visited, 1);
93}
94
95static void hashtable_test_hash_del(struct kunit *test)
96{
97	struct hashtable_test_entry a, b, *x;
98	DEFINE_HASHTABLE(hash, 6);
99
100	a.key = 1;
101	a.data = 13;
102	hash_add(hash, &a.node, a.key);
103	b.key = 2;
104	b.data = 10;
105	b.visited = 0;
106	hash_add(hash, &b.node, b.key);
107
108	hash_del(&b.node);
109	hash_for_each_possible(hash, x, node, b.key) {
110		x->visited++;
111		KUNIT_EXPECT_NE(test, x->key, b.key);
112	}
113
114	/* The deleted entry should not have been visited. */
115	KUNIT_EXPECT_EQ(test, b.visited, 0);
116
117	hash_del(&a.node);
118
119	/* The hashtable should be empty. */
120	KUNIT_EXPECT_TRUE(test, hash_empty(hash));
121}
122
123static void hashtable_test_hash_for_each(struct kunit *test)
124{
125	struct hashtable_test_entry entries[3];
126	struct hashtable_test_entry *x;
127	int bkt, i, j, count;
128	DEFINE_HASHTABLE(hash, 3);
129
130	/* Add three entries to the hashtable. */
131	for (i = 0; i < 3; i++) {
132		entries[i].key = i;
133		entries[i].data = i + 10;
134		entries[i].visited = 0;
135		hash_add(hash, &entries[i].node, entries[i].key);
136	}
137
138	count = 0;
139	hash_for_each(hash, bkt, x, node) {
140		x->visited += 1;
141		KUNIT_ASSERT_GE_MSG(test, x->key, 0, "Unexpected key in hashtable.");
142		KUNIT_ASSERT_LT_MSG(test, x->key, 3, "Unexpected key in hashtable.");
143		count++;
144	}
145
146	/* Should have visited each entry exactly once. */
147	KUNIT_EXPECT_EQ(test, count, 3);
148	for (j = 0; j < 3; j++)
149		KUNIT_EXPECT_EQ(test, entries[j].visited, 1);
150}
151
152static void hashtable_test_hash_for_each_safe(struct kunit *test)
153{
154	struct hashtable_test_entry entries[3];
155	struct hashtable_test_entry *x;
156	struct hlist_node *tmp;
157	int bkt, i, j, count;
158	DEFINE_HASHTABLE(hash, 3);
159
160	/* Add three entries to the hashtable. */
161	for (i = 0; i < 3; i++) {
162		entries[i].key = i;
163		entries[i].data = i + 10;
164		entries[i].visited = 0;
165		hash_add(hash, &entries[i].node, entries[i].key);
166	}
167
168	count = 0;
169	hash_for_each_safe(hash, bkt, tmp, x, node) {
170		x->visited += 1;
171		KUNIT_ASSERT_GE_MSG(test, x->key, 0, "Unexpected key in hashtable.");
172		KUNIT_ASSERT_LT_MSG(test, x->key, 3, "Unexpected key in hashtable.");
173		count++;
174
175		/* Delete entry during loop. */
176		hash_del(&x->node);
177	}
178
179	/* Should have visited each entry exactly once. */
180	KUNIT_EXPECT_EQ(test, count, 3);
181	for (j = 0; j < 3; j++)
182		KUNIT_EXPECT_EQ(test, entries[j].visited, 1);
183}
184
185static void hashtable_test_hash_for_each_possible(struct kunit *test)
186{
187	struct hashtable_test_entry entries[4];
188	struct hashtable_test_entry *x, *y;
189	int buckets[2];
190	int bkt, i, j, count;
191	DEFINE_HASHTABLE(hash, 5);
192
193	/* Add three entries with key = 0 to the hashtable. */
194	for (i = 0; i < 3; i++) {
195		entries[i].key = 0;
196		entries[i].data = i;
197		entries[i].visited = 0;
198		hash_add(hash, &entries[i].node, entries[i].key);
199	}
200
201	/* Add an entry with key = 1. */
202	entries[3].key = 1;
203	entries[3].data = 3;
204	entries[3].visited = 0;
205	hash_add(hash, &entries[3].node, entries[3].key);
206
207	count = 0;
208	hash_for_each_possible(hash, x, node, 0) {
209		x->visited += 1;
210		KUNIT_ASSERT_GE_MSG(test, x->data, 0, "Unexpected data in hashtable.");
211		KUNIT_ASSERT_LT_MSG(test, x->data, 4, "Unexpected data in hashtable.");
212		count++;
213	}
214
215	/* Should have visited each entry with key = 0 exactly once. */
216	for (j = 0; j < 3; j++)
217		KUNIT_EXPECT_EQ(test, entries[j].visited, 1);
218
219	/* Save the buckets for the different keys. */
220	hash_for_each(hash, bkt, y, node) {
221		KUNIT_ASSERT_GE_MSG(test, y->key, 0, "Unexpected key in hashtable.");
222		KUNIT_ASSERT_LE_MSG(test, y->key, 1, "Unexpected key in hashtable.");
223		buckets[y->key] = bkt;
224	}
225
226	/* If entry with key = 1 is in the same bucket as the entries with
227	 * key = 0, check it was visited. Otherwise ensure that only three
228	 * entries were visited.
229	 */
230	if (buckets[0] == buckets[1]) {
231		KUNIT_EXPECT_EQ(test, count, 4);
232		KUNIT_EXPECT_EQ(test, entries[3].visited, 1);
233	} else {
234		KUNIT_EXPECT_EQ(test, count, 3);
235		KUNIT_EXPECT_EQ(test, entries[3].visited, 0);
236	}
237}
238
239static void hashtable_test_hash_for_each_possible_safe(struct kunit *test)
240{
241	struct hashtable_test_entry entries[4];
242	struct hashtable_test_entry *x, *y;
243	struct hlist_node *tmp;
244	int buckets[2];
245	int bkt, i, j, count;
246	DEFINE_HASHTABLE(hash, 5);
247
248	/* Add three entries with key = 0 to the hashtable. */
249	for (i = 0; i < 3; i++) {
250		entries[i].key = 0;
251		entries[i].data = i;
252		entries[i].visited = 0;
253		hash_add(hash, &entries[i].node, entries[i].key);
254	}
255
256	/* Add an entry with key = 1. */
257	entries[3].key = 1;
258	entries[3].data = 3;
259	entries[3].visited = 0;
260	hash_add(hash, &entries[3].node, entries[3].key);
261
262	count = 0;
263	hash_for_each_possible_safe(hash, x, tmp, node, 0) {
264		x->visited += 1;
265		KUNIT_ASSERT_GE_MSG(test, x->data, 0, "Unexpected data in hashtable.");
266		KUNIT_ASSERT_LT_MSG(test, x->data, 4, "Unexpected data in hashtable.");
267		count++;
268
269		/* Delete entry during loop. */
270		hash_del(&x->node);
271	}
272
273	/* Should have visited each entry with key = 0 exactly once. */
274	for (j = 0; j < 3; j++)
275		KUNIT_EXPECT_EQ(test, entries[j].visited, 1);
276
277	/* Save the buckets for the different keys. */
278	hash_for_each(hash, bkt, y, node) {
279		KUNIT_ASSERT_GE_MSG(test, y->key, 0, "Unexpected key in hashtable.");
280		KUNIT_ASSERT_LE_MSG(test, y->key, 1, "Unexpected key in hashtable.");
281		buckets[y->key] = bkt;
282	}
283
284	/* If entry with key = 1 is in the same bucket as the entries with
285	 * key = 0, check it was visited. Otherwise ensure that only three
286	 * entries were visited.
287	 */
288	if (buckets[0] == buckets[1]) {
289		KUNIT_EXPECT_EQ(test, count, 4);
290		KUNIT_EXPECT_EQ(test, entries[3].visited, 1);
291	} else {
292		KUNIT_EXPECT_EQ(test, count, 3);
293		KUNIT_EXPECT_EQ(test, entries[3].visited, 0);
294	}
295}
296
297static struct kunit_case hashtable_test_cases[] = {
298	KUNIT_CASE(hashtable_test_hash_init),
299	KUNIT_CASE(hashtable_test_hash_empty),
300	KUNIT_CASE(hashtable_test_hash_hashed),
301	KUNIT_CASE(hashtable_test_hash_add),
302	KUNIT_CASE(hashtable_test_hash_del),
303	KUNIT_CASE(hashtable_test_hash_for_each),
304	KUNIT_CASE(hashtable_test_hash_for_each_safe),
305	KUNIT_CASE(hashtable_test_hash_for_each_possible),
306	KUNIT_CASE(hashtable_test_hash_for_each_possible_safe),
307	{},
308};
309
310static struct kunit_suite hashtable_test_module = {
311	.name = "hashtable",
312	.test_cases = hashtable_test_cases,
313};
314
315kunit_test_suites(&hashtable_test_module);
316
317MODULE_LICENSE("GPL");
318