1 /* $NetBSD: hashmap_test.c,v 1.2 2025/01/26 16:25:49 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 #include <inttypes.h> 17 #include <sched.h> /* IWYU pragma: keep */ 18 #include <setjmp.h> 19 #include <stdarg.h> 20 #include <stddef.h> 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 25 #define UNIT_TESTING 26 #include <cmocka.h> 27 28 #include <isc/hash.h> 29 #include <isc/hashmap.h> 30 #include <isc/mem.h> 31 #include <isc/string.h> 32 #include <isc/util.h> 33 34 #include <tests/isc.h> 35 36 /* INCLUDE LAST */ 37 38 #define mctx __mctx 39 #include "hashmap.c" 40 #undef mctx 41 42 typedef struct test_node { 43 uint32_t hashval; 44 char key[64]; 45 } test_node_t; 46 47 static bool 48 nodes_match(void *node0, const void *key) { 49 struct test_node *node = node0; 50 51 return memcmp(node->key, key, 16) == 0; 52 } 53 54 static bool 55 long_nodes_match(void *node0, const void *key) { 56 struct test_node *node = node0; 57 size_t len = strlen(key); 58 59 return memcmp(node->key, key, len) == 0; 60 } 61 62 static bool 63 upper_nodes_match(void *node0, const void *key) { 64 struct test_node *node = node0; 65 66 return isc_ascii_lowerequal((uint8_t *)node->key, key, 16); 67 } 68 69 static void 70 test_hashmap_full(uint8_t init_bits, uintptr_t count) { 71 isc_hashmap_t *hashmap = NULL; 72 isc_result_t result; 73 test_node_t *nodes, *long_nodes, *upper_nodes; 74 75 nodes = isc_mem_cget(mctx, count, sizeof(nodes[0])); 76 long_nodes = isc_mem_cget(mctx, count, sizeof(nodes[0])); 77 upper_nodes = isc_mem_cget(mctx, count, sizeof(nodes[0])); 78 79 isc_hashmap_create(mctx, init_bits, &hashmap); 80 assert_non_null(hashmap); 81 82 /* 83 * Note: snprintf() is followed with strlcat() 84 * to ensure we are always filling the 16 byte key. 85 */ 86 for (size_t i = 0; i < count; i++) { 87 /* short keys */ 88 snprintf((char *)nodes[i].key, 16, "%u", (unsigned int)i); 89 strlcat((char *)nodes[i].key, " key of a raw hashmap!!", 16); 90 nodes[i].hashval = isc_hash32(nodes[i].key, 16, true); 91 92 /* long keys */ 93 snprintf((char *)long_nodes[i].key, sizeof(long_nodes[i].key), 94 "%u", (unsigned int)i); 95 strlcat((char *)long_nodes[i].key, " key of a raw hashmap!!", 96 sizeof(long_nodes[i].key)); 97 long_nodes[i].hashval = isc_hash32( 98 long_nodes[i].key, 99 strlen((const char *)long_nodes[i].key), true); 100 101 /* (some) uppercase keys */ 102 snprintf((char *)upper_nodes[i].key, 16, "%u", (unsigned int)i); 103 strlcat((char *)upper_nodes[i].key, " KEY of a raw hashmap!!", 104 16); 105 upper_nodes[i].hashval = isc_hash32(upper_nodes[i].key, 16, 106 false); 107 } 108 109 /* insert short nodes */ 110 for (size_t i = 0; i < count; i++) { 111 void *f = NULL; 112 result = isc_hashmap_add(hashmap, nodes[i].hashval, nodes_match, 113 nodes[i].key, &nodes[i], &f); 114 assert_int_equal(result, ISC_R_SUCCESS); 115 assert_ptr_equal(f, NULL); 116 } 117 118 /* check if the short nodes were insert */ 119 for (size_t i = 0; i < count; i++) { 120 void *f = NULL; 121 result = isc_hashmap_find(hashmap, nodes[i].hashval, 122 nodes_match, nodes[i].key, &f); 123 assert_int_equal(result, ISC_R_SUCCESS); 124 assert_ptr_equal(&nodes[i], f); 125 } 126 127 /* check for double inserts */ 128 for (size_t i = 0; i < count; i++) { 129 void *f = NULL; 130 result = isc_hashmap_add(hashmap, nodes[i].hashval, nodes_match, 131 nodes[i].key, &nodes[i], &f); 132 assert_int_equal(result, ISC_R_EXISTS); 133 assert_ptr_equal(f, &nodes[i]); 134 } 135 136 for (size_t i = 0; i < count; i++) { 137 void *f = NULL; 138 result = isc_hashmap_add(hashmap, long_nodes[i].hashval, 139 long_nodes_match, long_nodes[i].key, 140 &long_nodes[i], &f); 141 assert_int_equal(result, ISC_R_SUCCESS); 142 assert_ptr_equal(f, NULL); 143 } 144 145 for (size_t i = 0; i < count; i++) { 146 void *f = NULL; 147 result = isc_hashmap_find(hashmap, upper_nodes[i].hashval, 148 long_nodes_match, upper_nodes[i].key, 149 &f); 150 assert_int_equal(result, ISC_R_NOTFOUND); 151 assert_null(f); 152 } 153 154 for (size_t i = 0; i < count; i++) { 155 void *f = NULL; 156 result = isc_hashmap_find(hashmap, long_nodes[i].hashval, 157 long_nodes_match, long_nodes[i].key, 158 &f); 159 assert_int_equal(result, ISC_R_SUCCESS); 160 assert_ptr_equal(f, &long_nodes[i]); 161 } 162 163 for (size_t i = 0; i < count; i++) { 164 void *f = NULL; 165 result = isc_hashmap_delete(hashmap, nodes[i].hashval, 166 nodes_match, nodes[i].key); 167 assert_int_equal(result, ISC_R_SUCCESS); 168 result = isc_hashmap_find(hashmap, nodes[i].hashval, 169 nodes_match, nodes[i].key, &f); 170 assert_int_equal(result, ISC_R_NOTFOUND); 171 assert_null(f); 172 } 173 174 for (size_t i = 0; i < count; i++) { 175 void *f = NULL; 176 result = isc_hashmap_add(hashmap, upper_nodes[i].hashval, 177 upper_nodes_match, upper_nodes[i].key, 178 &upper_nodes[i], &f); 179 assert_int_equal(result, ISC_R_SUCCESS); 180 assert_ptr_equal(f, NULL); 181 } 182 183 for (size_t i = 0; i < count; i++) { 184 void *f = NULL; 185 result = isc_hashmap_delete(hashmap, long_nodes[i].hashval, 186 long_nodes_match, 187 long_nodes[i].key); 188 assert_int_equal(result, ISC_R_SUCCESS); 189 result = isc_hashmap_find(hashmap, long_nodes[i].hashval, 190 long_nodes_match, long_nodes[i].key, 191 &f); 192 assert_int_equal(result, ISC_R_NOTFOUND); 193 assert_null(f); 194 } 195 196 for (size_t i = 0; i < count; i++) { 197 void *f = NULL; 198 result = isc_hashmap_find(hashmap, upper_nodes[i].hashval, 199 upper_nodes_match, upper_nodes[i].key, 200 &f); 201 assert_int_equal(result, ISC_R_SUCCESS); 202 assert_ptr_equal(f, &upper_nodes[i]); 203 } 204 205 for (size_t i = 0; i < count; i++) { 206 void *f = NULL; 207 result = isc_hashmap_find(hashmap, nodes[i].hashval, 208 nodes_match, nodes[i].key, &f); 209 assert_int_equal(result, ISC_R_NOTFOUND); 210 assert_null(f); 211 } 212 213 isc_hashmap_destroy(&hashmap); 214 assert_null(hashmap); 215 216 isc_mem_cput(mctx, nodes, count, sizeof(nodes[0])); 217 isc_mem_cput(mctx, long_nodes, count, sizeof(nodes[0])); 218 isc_mem_cput(mctx, upper_nodes, count, sizeof(nodes[0])); 219 } 220 221 #include "hashmap_nodes.h" 222 223 static void 224 test_hashmap_iterator(bool random_data) { 225 isc_hashmap_t *hashmap = NULL; 226 isc_result_t result; 227 isc_hashmap_iter_t *iter = NULL; 228 size_t count = 7600; 229 test_node_t *nodes; 230 bool *seen; 231 232 nodes = isc_mem_cget(mctx, count, sizeof(nodes[0])); 233 seen = isc_mem_cget(mctx, count, sizeof(seen[0])); 234 235 isc_hashmap_create(mctx, HASHMAP_MIN_BITS, &hashmap); 236 assert_non_null(hashmap); 237 238 for (size_t i = 0; i < count; i++) { 239 /* short keys */ 240 snprintf((char *)nodes[i].key, 16, "%u", (unsigned int)i); 241 strlcat((char *)nodes[i].key, " key of a raw hashmap!!", 16); 242 if (random_data) { 243 nodes[i].hashval = isc_hash32(nodes[i].key, 16, true); 244 } else { 245 nodes[i].hashval = test_hashvals[i]; 246 } 247 } 248 249 for (size_t i = 0; i < count; i++) { 250 void *f = NULL; 251 result = isc_hashmap_add(hashmap, nodes[i].hashval, nodes_match, 252 nodes[i].key, &nodes[i], &f); 253 assert_int_equal(result, ISC_R_SUCCESS); 254 assert_ptr_equal(f, NULL); 255 } 256 257 /* We want to iterate while rehashing is in progress */ 258 assert_true(rehashing_in_progress(hashmap)); 259 260 memset(seen, 0, count * sizeof(seen[0])); 261 isc_hashmap_iter_create(hashmap, &iter); 262 263 for (result = isc_hashmap_iter_first(iter); result == ISC_R_SUCCESS; 264 result = isc_hashmap_iter_next(iter)) 265 { 266 char key[16] = { 0 }; 267 ptrdiff_t i; 268 const uint8_t *tkey = NULL; 269 test_node_t *v = NULL; 270 271 isc_hashmap_iter_current(iter, (void *)&v); 272 isc_hashmap_iter_currentkey(iter, &tkey); 273 274 i = v - &nodes[0]; 275 276 snprintf(key, 16, "%u", (unsigned int)i); 277 strlcat(key, " key of a raw hashmap!!", 16); 278 279 assert_memory_equal(key, tkey, 16); 280 281 assert_false(seen[i]); 282 seen[i] = true; 283 } 284 assert_int_equal(result, ISC_R_NOMORE); 285 for (size_t i = 0; i < count; i++) { 286 assert_true(seen[i]); 287 } 288 289 /* erase odd */ 290 memset(seen, 0, count * sizeof(seen[0])); 291 result = isc_hashmap_iter_first(iter); 292 while (result == ISC_R_SUCCESS) { 293 char key[16] = { 0 }; 294 ptrdiff_t i; 295 const uint8_t *tkey = NULL; 296 test_node_t *v = NULL; 297 298 isc_hashmap_iter_current(iter, (void *)&v); 299 isc_hashmap_iter_currentkey(iter, &tkey); 300 301 i = v - nodes; 302 snprintf(key, 16, "%u", (unsigned int)i); 303 strlcat(key, " key of a raw hashmap!!", 16); 304 assert_memory_equal(key, tkey, 16); 305 306 if (i % 2 == 0) { 307 result = isc_hashmap_iter_delcurrent_next(iter); 308 } else { 309 result = isc_hashmap_iter_next(iter); 310 } 311 312 assert_false(seen[i]); 313 seen[i] = true; 314 } 315 assert_int_equal(result, ISC_R_NOMORE); 316 for (size_t i = 0; i < count; i++) { 317 assert_true(seen[i]); 318 } 319 320 /* erase even */ 321 memset(seen, 0, count * sizeof(seen[0])); 322 result = isc_hashmap_iter_first(iter); 323 while (result == ISC_R_SUCCESS) { 324 char key[16] = { 0 }; 325 ptrdiff_t i; 326 const uint8_t *tkey = NULL; 327 test_node_t *v = NULL; 328 329 isc_hashmap_iter_current(iter, (void *)&v); 330 isc_hashmap_iter_currentkey(iter, &tkey); 331 332 i = v - nodes; 333 snprintf(key, 16, "%u", (unsigned int)i); 334 strlcat(key, " key of a raw hashmap!!", 16); 335 assert_memory_equal(key, tkey, 16); 336 337 if (i % 2 == 1) { 338 result = isc_hashmap_iter_delcurrent_next(iter); 339 } else { 340 result = isc_hashmap_iter_next(iter); 341 } 342 } 343 assert_int_equal(result, ISC_R_NOMORE); 344 345 for (result = isc_hashmap_iter_first(iter); result == ISC_R_SUCCESS; 346 result = isc_hashmap_iter_next(iter)) 347 { 348 assert_true(false); 349 } 350 assert_int_equal(result, ISC_R_NOMORE); 351 352 /* Iterator doesn't progress rehashing */ 353 assert_true(rehashing_in_progress(hashmap)); 354 355 isc_hashmap_iter_destroy(&iter); 356 assert_null(iter); 357 358 isc_hashmap_destroy(&hashmap); 359 assert_null(hashmap); 360 361 isc_mem_cput(mctx, seen, count, sizeof(seen[0])); 362 isc_mem_cput(mctx, nodes, count, sizeof(nodes[0])); 363 } 364 365 /* 1 bit, 120 elements test, full rehashing */ 366 ISC_RUN_TEST_IMPL(isc_hashmap_1_120) { 367 test_hashmap_full(1, 120); 368 return; 369 } 370 371 /* 6 bit, 1000 elements test, full rehashing */ 372 ISC_RUN_TEST_IMPL(isc_hashmap_6_1000) { 373 test_hashmap_full(6, 1000); 374 return; 375 } 376 377 /* 24 bit, 200K elements test, no rehashing */ 378 ISC_RUN_TEST_IMPL(isc_hashmap_24_200000) { 379 test_hashmap_full(24, 200000); 380 return; 381 } 382 383 /* 15 bit, 45K elements test, full rehashing */ 384 ISC_RUN_TEST_IMPL(isc_hashmap_1_48000) { 385 test_hashmap_full(1, 48000); 386 return; 387 } 388 389 /* 8 bit, 20k elements test, partial rehashing */ 390 ISC_RUN_TEST_IMPL(isc_hashmap_8_20000) { 391 test_hashmap_full(8, 20000); 392 return; 393 } 394 395 /* test hashmap iterator */ 396 397 ISC_RUN_TEST_IMPL(isc_hashmap_iterator) { 398 test_hashmap_iterator(true); 399 return; 400 } 401 402 ISC_RUN_TEST_IMPL(isc_hashmap_iterator_static) { 403 test_hashmap_iterator(false); 404 return; 405 } 406 407 ISC_RUN_TEST_IMPL(isc_hashmap_hash_zero_length) { 408 isc_hashmap_t *hashmap = NULL; 409 uint32_t hashval; 410 bool again = false; 411 412 again: 413 isc_hashmap_create(mctx, 1, &hashmap); 414 415 hashval = isc_hash32("", 0, true); 416 417 isc_hashmap_destroy(&hashmap); 418 419 if (hashval == 0 && !again) { 420 /* 421 * We could be extremely unlucky and the siphash could hash the 422 * zero length string to 0, so try one more time. 423 */ 424 again = true; 425 goto again; 426 } 427 428 assert_int_not_equal(hashval, 0); 429 } 430 431 static bool 432 case_match(void *node0, const void *key) { 433 struct test_node *node = node0; 434 size_t len = strlen(key); 435 436 return memcmp(node->key, key, len) == 0; 437 } 438 439 static bool 440 nocase_match(void *node0, const void *key) { 441 struct test_node *node = node0; 442 size_t len = strlen(key); 443 444 return isc_ascii_lowerequal((uint8_t *)node->key, key, len); 445 } 446 447 ISC_RUN_TEST_IMPL(isc_hashmap_case) { 448 isc_result_t result; 449 isc_hashmap_t *hashmap = NULL; 450 test_node_t lower = { .key = "isc_hashmap_case" }; 451 test_node_t same = { .key = "isc_hashmap_case" }; 452 test_node_t upper = { .key = "ISC_HASHMAP_CASE" }; 453 test_node_t mixed = { .key = "IsC_hAsHmAp_CaSe" }; 454 void *f = NULL; 455 456 isc_hashmap_create(mctx, 1, &hashmap); 457 458 result = isc_hashmap_add(hashmap, 459 isc_hash32(lower.key, strlen(lower.key), true), 460 case_match, lower.key, &lower, NULL); 461 assert_int_equal(result, ISC_R_SUCCESS); 462 463 result = isc_hashmap_add(hashmap, 464 isc_hash32(same.key, strlen(same.key), true), 465 case_match, same.key, &same, NULL); 466 assert_int_equal(result, ISC_R_EXISTS); 467 468 result = isc_hashmap_add(hashmap, 469 isc_hash32(upper.key, strlen(upper.key), true), 470 case_match, upper.key, &upper, NULL); 471 assert_int_equal(result, ISC_R_SUCCESS); 472 473 result = isc_hashmap_find( 474 hashmap, isc_hash32(mixed.key, strlen(mixed.key), true), 475 case_match, mixed.key, &f); 476 assert_int_equal(result, ISC_R_NOTFOUND); 477 assert_ptr_equal(f, NULL); 478 479 isc_hashmap_destroy(&hashmap); 480 481 isc_hashmap_create(mctx, 1, &hashmap); 482 483 result = isc_hashmap_add( 484 hashmap, isc_hash32(lower.key, strlen(lower.key), false), 485 nocase_match, lower.key, &lower, NULL); 486 assert_int_equal(result, ISC_R_SUCCESS); 487 488 result = isc_hashmap_add(hashmap, 489 isc_hash32(same.key, strlen(same.key), false), 490 nocase_match, same.key, &same, NULL); 491 assert_int_equal(result, ISC_R_EXISTS); 492 493 result = isc_hashmap_add( 494 hashmap, isc_hash32(upper.key, strlen(upper.key), false), 495 nocase_match, upper.key, &upper, NULL); 496 assert_int_equal(result, ISC_R_EXISTS); 497 498 result = isc_hashmap_find( 499 hashmap, isc_hash32(mixed.key, strlen(mixed.key), false), 500 nocase_match, mixed.key, &f); 501 assert_int_equal(result, ISC_R_SUCCESS); 502 assert_ptr_equal(f, &lower); 503 504 isc_hashmap_destroy(&hashmap); 505 } 506 507 ISC_TEST_LIST_START 508 ISC_TEST_ENTRY(isc_hashmap_hash_zero_length) 509 ISC_TEST_ENTRY(isc_hashmap_case) 510 ISC_TEST_ENTRY(isc_hashmap_1_120) 511 ISC_TEST_ENTRY(isc_hashmap_6_1000) 512 ISC_TEST_ENTRY(isc_hashmap_24_200000) 513 ISC_TEST_ENTRY(isc_hashmap_1_48000) 514 ISC_TEST_ENTRY(isc_hashmap_8_20000) 515 ISC_TEST_ENTRY(isc_hashmap_iterator) 516 ISC_TEST_ENTRY(isc_hashmap_iterator_static) 517 ISC_TEST_LIST_END 518 519 ISC_TEST_MAIN 520