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 } 460