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