xref: /openbmc/linux/lib/hashtable_test.c (revision 789538c6)
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 
12 struct hashtable_test_entry {
13 	int key;
14 	int data;
15 	struct hlist_node node;
16 	int visited;
17 };
18 
hashtable_test_hash_init(struct kunit * test)19 static 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 
hashtable_test_hash_empty(struct kunit * test)34 static 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 
hashtable_test_hash_hashed(struct kunit * test)49 static 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 
hashtable_test_hash_add(struct kunit * test)65 static 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 
hashtable_test_hash_del(struct kunit * test)95 static 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 
hashtable_test_hash_for_each(struct kunit * test)123 static 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 
hashtable_test_hash_for_each_safe(struct kunit * test)152 static 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 
hashtable_test_hash_for_each_possible(struct kunit * test)185 static 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 
hashtable_test_hash_for_each_possible_safe(struct kunit * test)239 static 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 
297 static 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 
310 static struct kunit_suite hashtable_test_module = {
311 	.name = "hashtable",
312 	.test_cases = hashtable_test_cases,
313 };
314 
315 kunit_test_suites(&hashtable_test_module);
316 
317 MODULE_LICENSE("GPL");
318