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"); 318