lib/hashtable_test.c

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