bpf/prog_tests/hashmap.c

0001 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
0002
0003 /*
0004  * Tests for libbpf's hashmap.
0005  *
0006  * Copyright (c) 2019 Facebook
0007  */
0008 #include "test_progs.h"
0009 #include "bpf/hashmap.h"
0010
0011 static int duration = 0;
0012
0013 static size_t hash_fn(const void *k, void *ctx)
0014 {
0015     return (long)k;
0016 }
0017
0018 static bool equal_fn(const void *a, const void *b, void *ctx)
0019 {
0020     return (long)a == (long)b;
0021 }
0022
0023 static inline size_t next_pow_2(size_t n)
0024 {
0025     size_t r = 1;
0026
0027     while (r < n)
0028         r <<= 1;
0029     return r;
0030 }
0031
0032 static inline size_t exp_cap(size_t sz)
0033 {
0034     size_t r = next_pow_2(sz);
0035
0036     if (sz * 4 / 3 > r)
0037         r <<= 1;
0038     return r;
0039 }
0040
0041 #define ELEM_CNT 62
0042
0043 static void test_hashmap_generic(void)
0044 {
0045     struct hashmap_entry *entry, *tmp;
0046     int err, bkt, found_cnt, i;
0047     long long found_msk;
0048     struct hashmap *map;
0049
0050     map = hashmap__new(hash_fn, equal_fn, NULL);
0051     if (!ASSERT_OK_PTR(map, "hashmap__new"))
0052         return;
0053
0054     for (i = 0; i < ELEM_CNT; i++) {
0055         const void *oldk, *k = (const void *)(long)i;
0056         void *oldv, *v = (void *)(long)(1024 + i);
0057
0058         err = hashmap__update(map, k, v, &oldk, &oldv);
0059         if (CHECK(err != -ENOENT, "hashmap__update",
0060               "unexpected result: %d\n", err))
0061             goto cleanup;
0062
0063         if (i % 2) {
0064             err = hashmap__add(map, k, v);
0065         } else {
0066             err = hashmap__set(map, k, v, &oldk, &oldv);
0067             if (CHECK(oldk != NULL || oldv != NULL, "check_kv",
0068                   "unexpected k/v: %p=%p\n", oldk, oldv))
0069                 goto cleanup;
0070         }
0071
0072         if (CHECK(err, "elem_add", "failed to add k/v %ld = %ld: %d\n",
0073                    (long)k, (long)v, err))
0074             goto cleanup;
0075
0076         if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
0077               "failed to find key %ld\n", (long)k))
0078             goto cleanup;
0079         if (CHECK(oldv != v, "elem_val",
0080               "found value is wrong: %ld\n", (long)oldv))
0081             goto cleanup;
0082     }
0083
0084     if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
0085           "invalid map size: %zu\n", hashmap__size(map)))
0086         goto cleanup;
0087     if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
0088           "hashmap_cap",
0089           "unexpected map capacity: %zu\n", hashmap__capacity(map)))
0090         goto cleanup;
0091
0092     found_msk = 0;
0093     hashmap__for_each_entry(map, entry, bkt) {
0094         long k = (long)entry->key;
0095         long v = (long)entry->value;
0096
0097         found_msk |= 1ULL << k;
0098         if (CHECK(v - k != 1024, "check_kv",
0099               "invalid k/v pair: %ld = %ld\n", k, v))
0100             goto cleanup;
0101     }
0102     if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
0103           "not all keys iterated: %llx\n", found_msk))
0104         goto cleanup;
0105
0106     for (i = 0; i < ELEM_CNT; i++) {
0107         const void *oldk, *k = (const void *)(long)i;
0108         void *oldv, *v = (void *)(long)(256 + i);
0109
0110         err = hashmap__add(map, k, v);
0111         if (CHECK(err != -EEXIST, "hashmap__add",
0112               "unexpected add result: %d\n", err))
0113             goto cleanup;
0114
0115         if (i % 2)
0116             err = hashmap__update(map, k, v, &oldk, &oldv);
0117         else
0118             err = hashmap__set(map, k, v, &oldk, &oldv);
0119
0120         if (CHECK(err, "elem_upd",
0121               "failed to update k/v %ld = %ld: %d\n",
0122               (long)k, (long)v, err))
0123             goto cleanup;
0124         if (CHECK(!hashmap__find(map, k, &oldv), "elem_find",
0125               "failed to find key %ld\n", (long)k))
0126             goto cleanup;
0127         if (CHECK(oldv != v, "elem_val",
0128               "found value is wrong: %ld\n", (long)oldv))
0129             goto cleanup;
0130     }
0131
0132     if (CHECK(hashmap__size(map) != ELEM_CNT, "hashmap__size",
0133           "invalid updated map size: %zu\n", hashmap__size(map)))
0134         goto cleanup;
0135     if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
0136           "hashmap__capacity",
0137           "unexpected map capacity: %zu\n", hashmap__capacity(map)))
0138         goto cleanup;
0139
0140     found_msk = 0;
0141     hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
0142         long k = (long)entry->key;
0143         long v = (long)entry->value;
0144
0145         found_msk |= 1ULL << k;
0146         if (CHECK(v - k != 256, "elem_check",
0147               "invalid updated k/v pair: %ld = %ld\n", k, v))
0148             goto cleanup;
0149     }
0150     if (CHECK(found_msk != (1ULL << ELEM_CNT) - 1, "elem_cnt",
0151           "not all keys iterated after update: %llx\n", found_msk))
0152         goto cleanup;
0153
0154     found_cnt = 0;
0155     hashmap__for_each_key_entry(map, entry, (void *)0) {
0156         found_cnt++;
0157     }
0158     if (CHECK(!found_cnt, "found_cnt",
0159           "didn't find any entries for key 0\n"))
0160         goto cleanup;
0161
0162     found_msk = 0;
0163     found_cnt = 0;
0164     hashmap__for_each_key_entry_safe(map, entry, tmp, (void *)0) {
0165         const void *oldk, *k;
0166         void *oldv, *v;
0167
0168         k = entry->key;
0169         v = entry->value;
0170
0171         found_cnt++;
0172         found_msk |= 1ULL << (long)k;
0173
0174         if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
0175               "failed to delete k/v %ld = %ld\n",
0176               (long)k, (long)v))
0177             goto cleanup;
0178         if (CHECK(oldk != k || oldv != v, "check_old",
0179               "invalid deleted k/v: expected %ld = %ld, got %ld = %ld\n",
0180               (long)k, (long)v, (long)oldk, (long)oldv))
0181             goto cleanup;
0182         if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
0183               "unexpectedly deleted k/v %ld = %ld\n",
0184               (long)oldk, (long)oldv))
0185             goto cleanup;
0186     }
0187
0188     if (CHECK(!found_cnt || !found_msk, "found_entries",
0189           "didn't delete any key entries\n"))
0190         goto cleanup;
0191     if (CHECK(hashmap__size(map) != ELEM_CNT - found_cnt, "elem_cnt",
0192           "invalid updated map size (already deleted: %d): %zu\n",
0193           found_cnt, hashmap__size(map)))
0194         goto cleanup;
0195     if (CHECK(hashmap__capacity(map) != exp_cap(hashmap__size(map)),
0196           "hashmap__capacity",
0197           "unexpected map capacity: %zu\n", hashmap__capacity(map)))
0198         goto cleanup;
0199
0200     hashmap__for_each_entry_safe(map, entry, tmp, bkt) {
0201         const void *oldk, *k;
0202         void *oldv, *v;
0203
0204         k = entry->key;
0205         v = entry->value;
0206
0207         found_cnt++;
0208         found_msk |= 1ULL << (long)k;
0209
0210         if (CHECK(!hashmap__delete(map, k, &oldk, &oldv), "elem_del",
0211               "failed to delete k/v %ld = %ld\n",
0212               (long)k, (long)v))
0213             goto cleanup;
0214         if (CHECK(oldk != k || oldv != v, "elem_check",
0215               "invalid old k/v: expect %ld = %ld, got %ld = %ld\n",
0216               (long)k, (long)v, (long)oldk, (long)oldv))
0217             goto cleanup;
0218         if (CHECK(hashmap__delete(map, k, &oldk, &oldv), "elem_del",
0219               "unexpectedly deleted k/v %ld = %ld\n",
0220               (long)k, (long)v))
0221             goto cleanup;
0222     }
0223
0224     if (CHECK(found_cnt != ELEM_CNT || found_msk != (1ULL << ELEM_CNT) - 1,
0225           "found_cnt",
0226           "not all keys were deleted: found_cnt:%d, found_msk:%llx\n",
0227           found_cnt, found_msk))
0228         goto cleanup;
0229     if (CHECK(hashmap__size(map) != 0, "hashmap__size",
0230           "invalid updated map size (already deleted: %d): %zu\n",
0231           found_cnt, hashmap__size(map)))
0232         goto cleanup;
0233
0234     found_cnt = 0;
0235     hashmap__for_each_entry(map, entry, bkt) {
0236         CHECK(false, "elem_exists",
0237               "unexpected map entries left: %ld = %ld\n",
0238               (long)entry->key, (long)entry->value);
0239         goto cleanup;
0240     }
0241
0242     hashmap__clear(map);
0243     hashmap__for_each_entry(map, entry, bkt) {
0244         CHECK(false, "elem_exists",
0245               "unexpected map entries left: %ld = %ld\n",
0246               (long)entry->key, (long)entry->value);
0247         goto cleanup;
0248     }
0249
0250 cleanup:
0251     hashmap__free(map);
0252 }
0253
0254 static size_t collision_hash_fn(const void *k, void *ctx)
0255 {
0256     return 0;
0257 }
0258
0259 static void test_hashmap_multimap(void)
0260 {
0261     void *k1 = (void *)0, *k2 = (void *)1;
0262     struct hashmap_entry *entry;
0263     struct hashmap *map;
0264     long found_msk;
0265     int err, bkt;
0266
0267     /* force collisions */
0268     map = hashmap__new(collision_hash_fn, equal_fn, NULL);
0269     if (!ASSERT_OK_PTR(map, "hashmap__new"))
0270         return;
0271
0272     /* set up multimap:
0273      * [0] -> 1, 2, 4;
0274      * [1] -> 8, 16, 32;
0275      */
0276     err = hashmap__append(map, k1, (void *)1);
0277     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0278         goto cleanup;
0279     err = hashmap__append(map, k1, (void *)2);
0280     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0281         goto cleanup;
0282     err = hashmap__append(map, k1, (void *)4);
0283     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0284         goto cleanup;
0285
0286     err = hashmap__append(map, k2, (void *)8);
0287     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0288         goto cleanup;
0289     err = hashmap__append(map, k2, (void *)16);
0290     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0291         goto cleanup;
0292     err = hashmap__append(map, k2, (void *)32);
0293     if (CHECK(err, "elem_add", "failed to add k/v: %d\n", err))
0294         goto cleanup;
0295
0296     if (CHECK(hashmap__size(map) != 6, "hashmap_size",
0297           "invalid map size: %zu\n", hashmap__size(map)))
0298         goto cleanup;
0299
0300     /* verify global iteration still works and sees all values */
0301     found_msk = 0;
0302     hashmap__for_each_entry(map, entry, bkt) {
0303         found_msk |= (long)entry->value;
0304     }
0305     if (CHECK(found_msk != (1 << 6) - 1, "found_msk",
0306           "not all keys iterated: %lx\n", found_msk))
0307         goto cleanup;
0308
0309     /* iterate values for key 1 */
0310     found_msk = 0;
0311     hashmap__for_each_key_entry(map, entry, k1) {
0312         found_msk |= (long)entry->value;
0313     }
0314     if (CHECK(found_msk != (1 | 2 | 4), "found_msk",
0315           "invalid k1 values: %lx\n", found_msk))
0316         goto cleanup;
0317
0318     /* iterate values for key 2 */
0319     found_msk = 0;
0320     hashmap__for_each_key_entry(map, entry, k2) {
0321         found_msk |= (long)entry->value;
0322     }
0323     if (CHECK(found_msk != (8 | 16 | 32), "found_msk",
0324           "invalid k2 values: %lx\n", found_msk))
0325         goto cleanup;
0326
0327 cleanup:
0328     hashmap__free(map);
0329 }
0330
0331 static void test_hashmap_empty()
0332 {
0333     struct hashmap_entry *entry;
0334     int bkt;
0335     struct hashmap *map;
0336     void *k = (void *)0;
0337
0338     /* force collisions */
0339     map = hashmap__new(hash_fn, equal_fn, NULL);
0340     if (!ASSERT_OK_PTR(map, "hashmap__new"))
0341         goto cleanup;
0342
0343     if (CHECK(hashmap__size(map) != 0, "hashmap__size",
0344           "invalid map size: %zu\n", hashmap__size(map)))
0345         goto cleanup;
0346     if (CHECK(hashmap__capacity(map) != 0, "hashmap__capacity",
0347           "invalid map capacity: %zu\n", hashmap__capacity(map)))
0348         goto cleanup;
0349     if (CHECK(hashmap__find(map, k, NULL), "elem_find",
0350           "unexpected find\n"))
0351         goto cleanup;
0352     if (CHECK(hashmap__delete(map, k, NULL, NULL), "elem_del",
0353           "unexpected delete\n"))
0354         goto cleanup;
0355
0356     hashmap__for_each_entry(map, entry, bkt) {
0357         CHECK(false, "elem_found", "unexpected iterated entry\n");
0358         goto cleanup;
0359     }
0360     hashmap__for_each_key_entry(map, entry, k) {
0361         CHECK(false, "key_found", "unexpected key entry\n");
0362         goto cleanup;
0363     }
0364
0365 cleanup:
0366     hashmap__free(map);
0367 }
0368
0369 void test_hashmap()
0370 {
0371     if (test__start_subtest("generic"))
0372         test_hashmap_generic();
0373     if (test__start_subtest("multimap"))
0374         test_hashmap_multimap();
0375     if (test__start_subtest("empty"))
0376         test_hashmap_empty();
0377 }