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
  11 static int duration = 0;
  12
  13 static size_t hash_fn(const void *k, void *ctx)
  14 {
  15         return (long)k;
  16 }
  17
  18 static bool equal_fn(const void *a, const void *b, void *ctx)
  19 {
  20         return (long)a == (long)b;
  21 }
  22
  23 static inline size_t next_pow_2(size_t n)
  24 {
  25         size_t r = 1;
  26
  27         while (r < n)
  28                 r <<= 1;
  29         return r;
  30 }
  31
  32 static inline size_t exp_cap(size_t sz)
  33 {
  34         size_t r = next_pow_2(sz);
  35
  36         if (sz * 4 / 3 > r)
  37                 r <<= 1;
  38         return r;
  39 }
  40
  41 #define ELEM_CNT 62
  42
  43 static void test_hashmap_generic(void)
  44 {
  45         struct hashmap_entry *entry, *tmp;
  46         int err, bkt, found_cnt, i;
  47         long long found_msk;
  48         struct hashmap *map;
  49
  50         map = hashmap__new(hash_fn, equal_fn, NULL);
  51         if (CHECK(IS_ERR(map), "hashmap__new",
  52                   "failed to create map: %ld\n", PTR_ERR(map)))
  53                 return;
  54
  55         for (i = 0; i < ELEM_CNT; i++) {
  56                 const void *oldk, *k = (const void *)(long)i;
  57                 void *oldv, *v = (void *)(long)(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 != NULL || oldv != NULL, "check_kv",
  69                                   "unexpected k/v: %p=%p\n", oldk, oldv))
  70                                 goto cleanup;
  71                 }
  72
  73                 if (CHECK(err, "elem_add", "failed to add k/v %ld = %ld: %d\n",
  74                                (long)k, (long)v, err))
  75                         goto cleanup;
  76
  77                 if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
  78                           "failed to find key %ld\n", (long)k))
  79                         goto cleanup;
  80                 if (CHECK(oldv != v, "elem_val",
  81                           "found value is wrong: %ld\n", (long)oldv))
  82                         goto cleanup;
  83         }
  84
  85         if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
  86                   "invalid map size: %zu\n", hashmap__size(map)))
  87                 goto cleanup;
  88         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
  89                   "hashmap_cap",
  90                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
  91                 goto cleanup;
  92
  93         found_msk = 0;
  94         hashmap__for_each_entry(map, entry, bkt) {
  95                 long k = (long)entry->key;
  96                 long v = (long)entry->value;
  97
  98                 found_msk |= 1ULL << k;
  99                 if (CHECK(v - k != 1024, "check_kv",
 100                           "invalid k/v pair: %ld = %ld\n", k, v))
 101                         goto cleanup;
 102         }
 103         if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
 104                   "not all keys iterated: %llx\n", found_msk))
 105                 goto cleanup;
 106
 107         for (i = 0; i < ELEM_CNT; i++) {
 108                 const void *oldk, *k = (const void *)(long)i;
 109                 void *oldv, *v = (void *)(long)(256 + i);
 110
 111                 err = hashmap__add(map, k, v);
 112                 if (CHECK(err != -EEXIST, "hashmap__add",
 113                           "unexpected add result: %d\n", err))
 114                         goto cleanup;
 115
 116                 if (i % 2)
 117                         err = hashmap__update(map, k, v, &oldk, &oldv);
 118                 else
 119                         err = hashmap__set(map, k, v, &oldk, &oldv);
 120
 121                 if (CHECK(err, "elem_upd",
 122                           "failed to update k/v %ld = %ld: %d\n",
 123                           (long)k, (long)v, err))
 124                         goto cleanup;
 125                 if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
 126                           "failed to find key %ld\n", (long)k))
 127                         goto cleanup;
 128                 if (CHECK(oldv != v, "elem_val",
 129                           "found value is wrong: %ld\n", (long)oldv))
 130                         goto cleanup;
 131         }
 132
 133         if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
 134                   "invalid updated map size: %zu\n", hashmap__size(map)))
 135                 goto cleanup;
 136         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
 137                   "hashmap__capacity",
 138                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
 139                 goto cleanup;
 140
 141         found_msk = 0;
 142         hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
 143                 long k = (long)entry->key;
 144                 long v = (long)entry->value;
 145
 146                 found_msk |= 1ULL << k;
 147                 if (CHECK(v - k != 256, "elem_check",
 148                           "invalid updated k/v pair: %ld = %ld\n", k, v))
 149                         goto cleanup;
 150         }
 151         if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
 152                   "not all keys iterated after update: %llx\n", found_msk))
 153                 goto cleanup;
 154
 155         found_cnt = 0;
 156         hashmap__for_each_key_entry(map, entry, (void *)0) {
 157                 found_cnt++;
 158         }
 159         if (CHECK(!found_cnt, "found_cnt",
 160                   "didn't find any entries for key 0\n"))
 161                 goto cleanup;
 162
 163         found_msk = 0;
 164         found_cnt = 0;
 165         hashmap__for_each_key_entry_safe(map, entry, tmp, (void *)0) {
 166                 const void *oldk, *k;
 167                 void *oldv, *v;
 168
 169                 k = entry->key;
 170                 v = entry->value;
 171
 172                 found_cnt++;
 173                 found_msk |= 1ULL << (long)k;
 174
 175                 if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 176                           "failed to delete k/v %ld = %ld\n",
 177                           (long)k, (long)v))
 178                         goto cleanup;
 179                 if (CHECK(oldk != k || oldv != v, "check_old",
 180                           "invalid deleted k/v: expected %ld = %ld, got %ld = %ld\n",
 181                           (long)k, (long)v, (long)oldk, (long)oldv))
 182                         goto cleanup;
 183                 if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 184                           "unexpectedly deleted k/v %ld = %ld\n",
 185                           (long)oldk, (long)oldv))
 186                         goto cleanup;
 187         }
 188
 189         if (CHECK(!found_cnt || !found_msk, "found_entries",
 190                   "didn't delete any key entries\n"))
 191                 goto cleanup;
 192         if (CHECK(hashmap__size(map) != ELEM_CNT - found_cnt, "elem_cnt",
 193                   "invalid updated map size (already deleted: %d): %zu\n",
 194                   found_cnt, hashmap__size(map)))
 195                 goto cleanup;
 196         if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
 197                   "hashmap__capacity",
 198                   "unexpected map capacity: %zu\n", hashmap__capacity(map)))
 199                 goto cleanup;
 200
 201         hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
 202                 const void *oldk, *k;
 203                 void *oldv, *v;
 204
 205                 k = entry->key;
 206                 v = entry->value;
 207
 208                 found_cnt++;
 209                 found_msk |= 1ULL << (long)k;
 210
 211                 if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 212                           "failed to delete k/v %ld = %ld\n",
 213                           (long)k, (long)v))
 214                         goto cleanup;
 215                 if (CHECK(oldk != k || oldv != v, "elem_check",
 216                           "invalid old k/v: expect %ld = %ld, got %ld = %ld\n",
 217                           (long)k, (long)v, (long)oldk, (long)oldv))
 218                         goto cleanup;
 219                 if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
 220                           "unexpectedly deleted k/v %ld = %ld\n",
 221                           (long)k, (long)v))
 222                         goto cleanup;
 223         }
 224
 225         if (CHECK(found_cnt != ELEM_CNT || found_msk != (1ULL << ELEM_CNT) - 1,
 226                   "found_cnt",
 227                   "not all keys were deleted: found_cnt:%d, found_msk:%llx\n",
 228                   found_cnt, found_msk))
 229                 goto cleanup;
 230         if (CHECK(hashmap__size(map) != 0, "hashmap__size",
 231                   "invalid updated map size (already deleted: %d): %zu\n",
 232                   found_cnt, hashmap__size(map)))
 233                 goto cleanup;
 234
 235         found_cnt = 0;
 236         hashmap__for_each_entry(map, entry, bkt) {
 237                 CHECK(false, "elem_exists",
 238                       "unexpected map entries left: %ld = %ld\n",
 239                       (long)entry->key, (long)entry->value);
 240                 goto cleanup;
 241         }
 242
 243         hashmap__clear(map);
 244         hashmap__for_each_entry(map, entry, bkt) {
 245                 CHECK(false, "elem_exists",
 246                       "unexpected map entries left: %ld = %ld\n",
 247                       (long)entry->key, (long)entry->value);
 248                 goto cleanup;
 249         }
 250
 251 cleanup:
 252         hashmap__free(map);
 253 }
 254
 255 static size_t collision_hash_fn(const void *k, void *ctx)
 256 {
 257         return 0;
 258 }
 259
 260 static void test_hashmap_multimap(void)
 261 {
 262         void *k1 = (void *)0, *k2 = (void *)1;
 263         struct hashmap_entry *entry;
 264         struct hashmap *map;
 265         long found_msk;
 266         int err, bkt;
 267
 268         /* force collisions */
 269         map = hashmap__new(collision_hash_fn, equal_fn, NULL);
 270         if (CHECK(IS_ERR(map), "hashmap__new",
 271                   "failed to create map: %ld\n", PTR_ERR(map)))
 272                 return;
 273
 274         /* set up multimap:
 275          * [0] -> 1, 2, 4;
 276          * [1] -> 8, 16, 32;
 277          */
 278         err = hashmap__append(map, k1, (void *)1);
 279         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 280                 goto cleanup;
 281         err = hashmap__append(map, k1, (void *)2);
 282         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 283                 goto cleanup;
 284         err = hashmap__append(map, k1, (void *)4);
 285         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 286                 goto cleanup;
 287
 288         err = hashmap__append(map, k2, (void *)8);
 289         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 290                 goto cleanup;
 291         err = hashmap__append(map, k2, (void *)16);
 292         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 293                 goto cleanup;
 294         err = hashmap__append(map, k2, (void *)32);
 295         if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
 296                 goto cleanup;
 297
 298         if (CHECK(hashmap__size(map) != 6, "hashmap_size",
 299                   "invalid map size: %zu\n", hashmap__size(map)))
 300                 goto cleanup;
 301
 302         /* verify global iteration still works and sees all values */
 303         found_msk = 0;
 304         hashmap__for_each_entry(map, entry, bkt) {
 305                 found_msk |= (long)entry->value;
 306         }
 307         if (CHECK(found_msk != (1 << 6) - 1, "found_msk",
 308                   "not all keys iterated: %lx\n", found_msk))
 309                 goto cleanup;
 310
 311         /* iterate values for key 1 */
 312         found_msk = 0;
 313         hashmap__for_each_key_entry(map, entry, k1) {
 314                 found_msk |= (long)entry->value;
 315         }
 316         if (CHECK(found_msk != (1 | 2 | 4), "found_msk",
 317                   "invalid k1 values: %lx\n", found_msk))
 318                 goto cleanup;
 319
 320         /* iterate values for key 2 */
 321         found_msk = 0;
 322         hashmap__for_each_key_entry(map, entry, k2) {
 323                 found_msk |= (long)entry->value;
 324         }
 325         if (CHECK(found_msk != (8 | 16 | 32), "found_msk",
 326                   "invalid k2 values: %lx\n", found_msk))
 327                 goto cleanup;
 328
 329 cleanup:
 330         hashmap__free(map);
 331 }
 332
 333 static void test_hashmap_empty()
 334 {
 335         struct hashmap_entry *entry;
 336         int bkt;
 337         struct hashmap *map;
 338         void *k = (void *)0;
 339
 340         /* force collisions */
 341         map = hashmap__new(hash_fn, equal_fn, NULL);
 342         if (CHECK(IS_ERR(map), "hashmap__new",
 343                   "failed to create map: %ld\n", PTR_ERR(map)))
 344                 goto cleanup;
 345
 346         if (CHECK(hashmap__size(map) != 0, "hashmap__size",
 347                   "invalid map size: %zu\n", hashmap__size(map)))
 348                 goto cleanup;
 349         if (CHECK(hashmap__capacity(map) != 0, "hashmap__capacity",
 350                   "invalid map capacity: %zu\n", hashmap__capacity(map)))
 351                 goto cleanup;
 352         if (CHECK(hashmap__find(map, k, NULL), "elem_find",
 353                   "unexpected find\n"))
 354                 goto cleanup;
 355         if (CHECK(hashmap__delete(map, k, NULL, NULL), "elem_del",
 356                   "unexpected delete\n"))
 357                 goto cleanup;
 358
 359         hashmap__for_each_entry(map, entry, bkt) {
 360                 CHECK(false, "elem_found", "unexpected iterated entry\n");
 361                 goto cleanup;
 362         }
 363         hashmap__for_each_key_entry(map, entry, k) {
 364                 CHECK(false, "key_found", "unexpected key entry\n");
 365                 goto cleanup;
 366         }
 367
 368 cleanup:
 369         hashmap__free(map);
 370 }
 371
 372 void test_hashmap()
 373 {
 374         if (test__start_subtest("generic"))
 375                 test_hashmap_generic();
 376         if (test__start_subtest("multimap"))
 377                 test_hashmap_multimap();
 378         if (test__start_subtest("empty"))
 379                 test_hashmap_empty();
 380 }