tools/testing/selftests/bpf/prog_tests/hashmap.c

   1 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
   2
   3 /*
   4  * Tests for libbpf's hashmap.
   5  *
   6  * Copyright (c) 2019 Facebook
   7  */
   8 #include "test_progs.h"
   9 #include "bpf/hashmap.h"
  10 #include <stddef.h>
  11
  12 static int duration = 0;
  13
  14 static size_t hash_fn(long k, void *ctx)
  15 {
  16         return k;
  17 }
  18
  19 static bool equal_fn(long a, long b, void *ctx)
  20 {
  21         return a == b;
  22 }
  23
  24 static inline size_t next_pow_2(size_t n)
  25 {
  26         size_t r = 1;
  27
  28         while (r < n)
  29                 r <<= 1;
  30         return r;
  31 }
  32
  33 static inline size_t exp_cap(size_t sz)
  34 {
  35         size_t r = next_pow_2(sz);
  36
  37         if (sz * 4 / 3 > r)
  38                 r <<= 1;
  39         return r;
  40 }
  41
  42 #define ELEM_CNT 62
  43
  44 static void test_hashmap_generic(void)
  45 {
  46         struct hashmap_entry *entry, *tmp;
  47         int err, bkt, found_cnt, i;
  48         long long found_msk;
  49         struct hashmap *map;
  50
  51         map = hashmap__new(hash_fn, equal_fn, NULL);
  52         if (!ASSERT_OK_PTR(map, "hashmap__new"))
  53                 return;
  54
  55         for (i = 0; i < ELEM_CNT; i++) {
  56                 long oldk, k = i;
  57                 long oldv, v = 1024 + i;
  58
  59                 err = hashmap__update(map, k, v, &oldk, &oldv);
  60                 if (CHECK(err != -ENOENT, "hashmap__update",
  61                           "unexpected result: %d\n", err))
  62                         goto cleanup;
  63
  64                 if (i % 2) {
  65                         err = hashmap__add(map, k, v);
  66                 } else {
  67                         err = hashmap__set(map, k, v, &oldk, &oldv);
  68                         if (CHECK(oldk != 0 || oldv != 0, "check_kv",
  69                                   "unexpected k/v: %ld=%ld\n", oldk, oldv))
  70                                 goto cleanup;
  71                 }
  72
  73                 if (CHECK(err, "elem_add", "failed to add k/v %ld = %ld: %d\n", k, v, err))
  74                         goto cleanup;
  75
  76                 if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
  77                           "failed to find key %ld\n", k))
  78                         goto cleanup;
  79                 if (CHECK(oldv != v, "elem_val", "found value is wrong: %ld\n", oldv))
  80                         goto cleanup;
  81         }
  82
  83         if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
  84                   "invalid map size: %zu\n", hashmap__size(map)))
  85                 goto cleanup;
  86         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
  87                   "hashmap_cap",
  88                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
  89                 goto cleanup;
  90
  91         found_msk = 0;
  92         hashmap__for_each_entry(map, entry, bkt) {
  93                 long k = entry->key;
  94                 long v = entry->value;
  95
  96                 found_msk |= 1ULL << k;
  97                 if (CHECK(v - k != 1024, "check_kv",
  98                           "invalid k/v pair: %ld = %ld\n", k, v))
  99                         goto cleanup;
 100         }
 101         if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
 102                   "not all keys iterated: %llx\n", found_msk))
 103                 goto cleanup;
 104
 105         for (i = 0; i < ELEM_CNT; i++) {
 106                 long oldk, k = i;
 107                 long oldv, v = 256 + i;
 108
 109                 err = hashmap__add(map, k, v);
 110                 if (CHECK(err != -EEXIST, "hashmap__add",
 111                           "unexpected add result: %d\n", err))
 112                         goto cleanup;
 113
 114                 if (i % 2)
 115                         err = hashmap__update(map, k, v, &oldk, &oldv);
 116                 else
 117                         err = hashmap__set(map, k, v, &oldk, &oldv);
 118
 119                 if (CHECK(err, "elem_upd",
 120                           "failed to update k/v %ld = %ld: %d\n",
 121                           k, v, err))
 122                         goto cleanup;
 123                 if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
 124                           "failed to find key %ld\n", k))
 125                         goto cleanup;
 126                 if (CHECK(oldv != v, "elem_val",
 127                           "found value is wrong: %ld\n", oldv))
 128                         goto cleanup;
 129         }
 130
 131         if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
 132                   "invalid updated map size: %zu\n", hashmap__size(map)))
 133                 goto cleanup;
 134         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
 135                   "hashmap__capacity",
 136                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
 137                 goto cleanup;
 138
 139         found_msk = 0;
 140         hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
 141                 long k = entry->key;
 142                 long v = entry->value;
 143
 144                 found_msk |= 1ULL << k;
 145                 if (CHECK(v - k != 256, "elem_check",
 146                           "invalid updated k/v pair: %ld = %ld\n", k, v))
 147                         goto cleanup;
 148         }
 149         if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
 150                   "not all keys iterated after update: %llx\n", found_msk))
 151                 goto cleanup;
 152
 153         found_cnt = 0;
 154         hashmap__for_each_key_entry(map, entry, 0) {
 155                 found_cnt++;
 156         }
 157         if (CHECK(!found_cnt, "found_cnt",
 158                   "didn't find any entries for key 0\n"))
 159                 goto cleanup;
 160
 161         found_msk = 0;
 162         found_cnt = 0;
 163         hashmap__for_each_key_entry_safe(map, entry, tmp, 0) {
 164                 long oldk, k;
 165                 long oldv, v;
 166
 167                 k = entry->key;
 168                 v = entry->value;
 169
 170                 found_cnt++;
 171                 found_msk |= 1ULL << k;
 172
 173                 if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 174                           "failed to delete k/v %ld = %ld\n", k, v))
 175                         goto cleanup;
 176                 if (CHECK(oldk != k || oldv != v, "check_old",
 177                           "invalid deleted k/v: expected %ld = %ld, got %ld = %ld\n",
 178                           k, v, oldk, oldv))
 179                         goto cleanup;
 180                 if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 181                           "unexpectedly deleted k/v %ld = %ld\n", oldk, oldv))
 182                         goto cleanup;
 183         }
 184
 185         if (CHECK(!found_cnt || !found_msk, "found_entries",
 186                   "didn't delete any key entries\n"))
 187                 goto cleanup;
 188         if (CHECK(hashmap__size(map) != ELEM_CNT - found_cnt, "elem_cnt",
 189                   "invalid updated map size (already deleted: %d): %zu\n",
 190                   found_cnt, hashmap__size(map)))
 191                 goto cleanup;
 192         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
 193                   "hashmap__capacity",
 194                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
 195                 goto cleanup;
 196
 197         hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
 198                 long oldk, k;
 199                 long oldv, v;
 200
 201                 k = entry->key;
 202                 v = entry->value;
 203
 204                 found_cnt++;
 205                 found_msk |= 1ULL << k;
 206
 207                 if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 208                           "failed to delete k/v %ld = %ld\n", k, v))
 209                         goto cleanup;
 210                 if (CHECK(oldk != k || oldv != v, "elem_check",
 211                           "invalid old k/v: expect %ld = %ld, got %ld = %ld\n",
 212                           k, v, oldk, oldv))
 213                         goto cleanup;
 214                 if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 215                           "unexpectedly deleted k/v %ld = %ld\n", k, v))
 216                         goto cleanup;
 217         }
 218
 219         if (CHECK(found_cnt != ELEM_CNT || found_msk != (1ULL << ELEM_CNT) - 1,
 220                   "found_cnt",
 221                   "not all keys were deleted: found_cnt:%d, found_msk:%llx\n",
 222                   found_cnt, found_msk))
 223                 goto cleanup;
 224         if (CHECK(hashmap__size(map) != 0, "hashmap__size",
 225                   "invalid updated map size (already deleted: %d): %zu\n",
 226                   found_cnt, hashmap__size(map)))
 227                 goto cleanup;
 228
 229         found_cnt = 0;
 230         hashmap__for_each_entry(map, entry, bkt) {
 231                 CHECK(false, "elem_exists",
 232                       "unexpected map entries left: %ld = %ld\n",
 233                       entry->key, entry->value);
 234                 goto cleanup;
 235         }
 236
 237         hashmap__clear(map);
 238         hashmap__for_each_entry(map, entry, bkt) {
 239                 CHECK(false, "elem_exists",
 240                       "unexpected map entries left: %ld = %ld\n",
 241                       entry->key, entry->value);
 242                 goto cleanup;
 243         }
 244
 245 cleanup:
 246         hashmap__free(map);
 247 }
 248
 249 static size_t str_hash_fn(long a, void *ctx)
 250 {
 251         return str_hash((char *)a);
 252 }
 253
 254 static bool str_equal_fn(long a, long b, void *ctx)
 255 {
 256         return strcmp((char *)a, (char *)b) == 0;
 257 }
 258
 259 /* Verify that hashmap interface works with pointer keys and values */
 260 static void test_hashmap_ptr_iface(void)
 261 {
 262         const char *key, *value, *old_key, *old_value;
 263         struct hashmap_entry *cur;
 264         struct hashmap *map;
 265         int err, i, bkt;
 266
 267         map = hashmap__new(str_hash_fn, str_equal_fn, NULL);
 268         if (CHECK(!map, "hashmap__new", "can't allocate hashmap\n"))
 269                 goto cleanup;
 270
 271 #define CHECK_STR(fn, var, expected)                                    \
 272         CHECK(strcmp(var, (expected)), (fn),                            \
 273               "wrong value of " #var ": '%s' instead of '%s'\n", var, (expected))
 274
 275         err = hashmap__insert(map, "a", "apricot", HASHMAP_ADD, NULL, NULL);
 276         if (CHECK(err, "hashmap__insert", "unexpected error: %d\n", err))
 277                 goto cleanup;
 278
 279         err = hashmap__insert(map, "a", "apple", HASHMAP_SET, &old_key, &old_value);
 280         if (CHECK(err, "hashmap__insert", "unexpected error: %d\n", err))
 281                 goto cleanup;
 282         CHECK_STR("hashmap__update", old_key, "a");
 283         CHECK_STR("hashmap__update", old_value, "apricot");
 284
 285         err = hashmap__add(map, "b", "banana");
 286         if (CHECK(err, "hashmap__add", "unexpected error: %d\n", err))
 287                 goto cleanup;
 288
 289         err = hashmap__set(map, "b", "breadfruit", &old_key, &old_value);
 290         if (CHECK(err, "hashmap__set", "unexpected error: %d\n", err))
 291                 goto cleanup;
 292         CHECK_STR("hashmap__set", old_key, "b");
 293         CHECK_STR("hashmap__set", old_value, "banana");
 294
 295         err = hashmap__update(map, "b", "blueberry", &old_key, &old_value);
 296         if (CHECK(err, "hashmap__update", "unexpected error: %d\n", err))
 297                 goto cleanup;
 298         CHECK_STR("hashmap__update", old_key, "b");
 299         CHECK_STR("hashmap__update", old_value, "breadfruit");
 300
 301         err = hashmap__append(map, "c", "cherry");
 302         if (CHECK(err, "hashmap__append", "unexpected error: %d\n", err))
 303                 goto cleanup;
 304
 305         if (CHECK(!hashmap__delete(map, "c", &old_key, &old_value),
 306                   "hashmap__delete", "expected to have entry for 'c'\n"))
 307                 goto cleanup;
 308         CHECK_STR("hashmap__delete", old_key, "c");
 309         CHECK_STR("hashmap__delete", old_value, "cherry");
 310
 311         CHECK(!hashmap__find(map, "b", &value), "hashmap__find", "can't find value for 'b'\n");
 312         CHECK_STR("hashmap__find", value, "blueberry");
 313
 314         if (CHECK(!hashmap__delete(map, "b", NULL, NULL),
 315                   "hashmap__delete", "expected to have entry for 'b'\n"))
 316                 goto cleanup;
 317
 318         i = 0;
 319         hashmap__for_each_entry(map, cur, bkt) {
 320                 if (CHECK(i != 0, "hashmap__for_each_entry", "too many entries"))
 321                         goto cleanup;
 322                 key = cur->pkey;
 323                 value = cur->pvalue;
 324                 CHECK_STR("entry", key, "a");
 325                 CHECK_STR("entry", value, "apple");
 326                 i++;
 327         }
 328 #undef CHECK_STR
 329
 330 cleanup:
 331         hashmap__free(map);
 332 }
 333
 334 static size_t collision_hash_fn(long k, void *ctx)
 335 {
 336         return 0;
 337 }
 338
 339 static void test_hashmap_multimap(void)
 340 {
 341         long k1 = 0, k2 = 1;
 342         struct hashmap_entry *entry;
 343         struct hashmap *map;
 344         long found_msk;
 345         int err, bkt;
 346
 347         /* force collisions */
 348         map = hashmap__new(collision_hash_fn, equal_fn, NULL);
 349         if (!ASSERT_OK_PTR(map, "hashmap__new"))
 350                 return;
 351
 352         /* set up multimap:
 353          * [0] -> 1, 2, 4;
 354          * [1] -> 8, 16, 32;
 355          */
 356         err = hashmap__append(map, k1, 1);
 357         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 358                 goto cleanup;
 359         err = hashmap__append(map, k1, 2);
 360         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 361                 goto cleanup;
 362         err = hashmap__append(map, k1, 4);
 363         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 364                 goto cleanup;
 365
 366         err = hashmap__append(map, k2, 8);
 367         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 368                 goto cleanup;
 369         err = hashmap__append(map, k2, 16);
 370         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 371                 goto cleanup;
 372         err = hashmap__append(map, k2, 32);
 373         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 374                 goto cleanup;
 375
 376         if (CHECK(hashmap__size(map) != 6, "hashmap_size",
 377                   "invalid map size: %zu\n", hashmap__size(map)))
 378                 goto cleanup;
 379
 380         /* verify global iteration still works and sees all values */
 381         found_msk = 0;
 382         hashmap__for_each_entry(map, entry, bkt) {
 383                 found_msk |= entry->value;
 384         }
 385         if (CHECK(found_msk != (1 << 6) - 1, "found_msk",
 386                   "not all keys iterated: %lx\n", found_msk))
 387                 goto cleanup;
 388
 389         /* iterate values for key 1 */
 390         found_msk = 0;
 391         hashmap__for_each_key_entry(map, entry, k1) {
 392                 found_msk |= entry->value;
 393         }
 394         if (CHECK(found_msk != (1 | 2 | 4), "found_msk",
 395                   "invalid k1 values: %lx\n", found_msk))
 396                 goto cleanup;
 397
 398         /* iterate values for key 2 */
 399         found_msk = 0;
 400         hashmap__for_each_key_entry(map, entry, k2) {
 401                 found_msk |= entry->value;
 402         }
 403         if (CHECK(found_msk != (8 | 16 | 32), "found_msk",
 404                   "invalid k2 values: %lx\n", found_msk))
 405                 goto cleanup;
 406
 407 cleanup:
 408         hashmap__free(map);
 409 }
 410
 411 static void test_hashmap_empty()
 412 {
 413         struct hashmap_entry *entry;
 414         int bkt;
 415         struct hashmap *map;
 416         long k = 0;
 417
 418         /* force collisions */
 419         map = hashmap__new(hash_fn, equal_fn, NULL);
 420         if (!ASSERT_OK_PTR(map, "hashmap__new"))
 421                 goto cleanup;
 422
 423         if (CHECK(hashmap__size(map) != 0, "hashmap__size",
 424                   "invalid map size: %zu\n", hashmap__size(map)))
 425                 goto cleanup;
 426         if (CHECK(hashmap__capacity(map) != 0, "hashmap__capacity",
 427                   "invalid map capacity: %zu\n", hashmap__capacity(map)))
 428                 goto cleanup;
 429         if (CHECK(hashmap__find(map, k, NULL), "elem_find",
 430                   "unexpected find\n"))
 431                 goto cleanup;
 432         if (CHECK(hashmap__delete(map, k, NULL, NULL), "elem_del",
 433                   "unexpected delete\n"))
 434                 goto cleanup;
 435
 436         hashmap__for_each_entry(map, entry, bkt) {
 437                 CHECK(false, "elem_found", "unexpected iterated entry\n");
 438                 goto cleanup;
 439         }
 440         hashmap__for_each_key_entry(map, entry, k) {
 441                 CHECK(false, "key_found", "unexpected key entry\n");
 442                 goto cleanup;
 443         }
 444
 445 cleanup:
 446         hashmap__free(map);
 447 }
 448
 449 void test_hashmap()
 450 {
 451         if (test__start_subtest("generic"))
 452                 test_hashmap_generic();
 453         if (test__start_subtest("multimap"))
 454                 test_hashmap_multimap();
 455         if (test__start_subtest("empty"))
 456                 test_hashmap_empty();
 457         if (test__start_subtest("ptr_iface"))
 458                 test_hashmap_ptr_iface();
 459 }