319 lines · c
1// SPDX-License-Identifier: GPL-2.02/*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 12struct hashtable_test_entry {13 int key;14 int data;15 struct hlist_node node;16 int visited;17};18 19static 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 to26 * 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 34static 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 49static 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 65static 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 else87 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 95static 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 123static 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 152static 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 185static 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 with227 * key = 0, check it was visited. Otherwise ensure that only three228 * 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 239static 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 with285 * key = 0, check it was visited. Otherwise ensure that only three286 * 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 297static 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 310static struct kunit_suite hashtable_test_module = {311 .name = "hashtable",312 .test_cases = hashtable_test_cases,313};314 315kunit_test_suites(&hashtable_test_module);316 317MODULE_DESCRIPTION("KUnit test for the Kernel Hashtable structures");318MODULE_LICENSE("GPL");319