460 lines · 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 Facebook7 */8#include "test_progs.h"9#include "bpf/hashmap.h"10#include <stddef.h>11 12static int duration = 0;13 14static size_t hash_fn(long k, void *ctx)15{16 return k;17}18 19static bool equal_fn(long a, long b, void *ctx)20{21 return a == b;22}23 24static 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 33static 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 6243 44static 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 else117 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 245cleanup:246 hashmap__free(map);247}248 249static size_t str_hash_fn(long a, void *ctx)250{251 return str_hash((char *)a);252}253 254static 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 */260static 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_STR329 330cleanup:331 hashmap__free(map);332}333 334static size_t collision_hash_fn(long k, void *ctx)335{336 return 0;337}338 339static 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 407cleanup:408 hashmap__free(map);409}410 411static 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 445cleanup:446 hashmap__free(map);447}448 449void 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}460