Commit | Line | Data |
---|---|---|
789538c6 RM |
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(&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 | ||
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(&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(&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"); |