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 11static int duration = 0; 12 13static size_t hash_fn(const void *k, void *ctx) 14{ 15 return (long)k; 16} 17 18static bool equal_fn(const void *a, const void *b, void *ctx) 19{ 20 return (long)a == (long)b; 21} 22 23static 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 32static 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 43static 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 251cleanup: 252 hashmap__free(map); 253} 254 255static size_t collision_hash_fn(const void *k, void *ctx) 256{ 257 return 0; 258} 259 260static 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 329cleanup: 330 hashmap__free(map); 331} 332 333static 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 368cleanup: 369 hashmap__free(map); 370} 371 372void 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} 381