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