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 | |
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 | |
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 | |
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 | |
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 | |
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(node: &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(node: &a.node); |
118 | |
119 | /* The hashtable should be empty. */ |
120 | KUNIT_EXPECT_TRUE(test, hash_empty(hash)); |
121 | } |
122 | |
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 | |
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(node: &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 | |
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 | |
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(node: &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 | |