2 * Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
14 #include <openssl/opensslconf.h>
15 #include <openssl/lhash.h>
16 #include <openssl/err.h>
17 #include <openssl/rand.h>
18 #include <openssl/crypto.h>
19 #include <internal/hashtable.h>
21 #include "internal/nelem.h"
22 #include "threadstest.h"
26 * The macros below generate unused functions which error out one of the clang
27 * builds. We disable this check here.
30 #pragma clang diagnostic ignored "-Wunused-function"
33 DEFINE_LHASH_OF_EX(int);
35 static int int_tests[] = { 65537, 13, 1, 3, -5, 6, 7, 4, -10, -12, -14, 22, 9,
36 -17, 16, 17, -23, 35, 37, 173, 11 };
37 static const size_t n_int_tests = OSSL_NELEM(int_tests);
38 static short int_found[OSSL_NELEM(int_tests)];
39 static short int_not_found;
41 static unsigned long int int_hash(const int *p)
43 return 3 & *p; /* To force collisions */
46 static int int_cmp(const int *p, const int *q)
51 static int int_find(int n)
55 for (i = 0; i < n_int_tests; i++)
56 if (int_tests[i] == n)
61 static void int_doall(int *v)
63 const int n = int_find(*v);
71 static void int_doall_arg(int *p, short *f)
73 const int n = int_find(*p);
81 IMPLEMENT_LHASH_DOALL_ARG(int, short);
83 static int test_int_lhash(void)
96 const unsigned int n_dels = OSSL_NELEM(dels);
97 LHASH_OF(int) *h = lh_int_new(&int_hash, &int_cmp);
99 int testresult = 0, j, *p;
105 for (i = 0; i < n_int_tests; i++)
106 if (!TEST_ptr_null(lh_int_insert(h, int_tests + i))) {
107 TEST_info("int insert %d", i);
112 if (!TEST_int_eq((size_t)lh_int_num_items(h), n_int_tests))
116 for (i = 0; i < n_int_tests; i++)
117 if (!TEST_int_eq(*lh_int_retrieve(h, int_tests + i), int_tests[i])) {
118 TEST_info("lhash int retrieve value %d", i);
121 for (i = 0; i < n_int_tests; i++)
122 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + i), int_tests + i)) {
123 TEST_info("lhash int retrieve address %d", i);
127 if (!TEST_ptr_eq(lh_int_retrieve(h, &j), int_tests + 2))
132 if (!TEST_ptr(p = lh_int_insert(h, &j)))
134 if (!TEST_ptr_eq(p, int_tests + 1))
136 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + 1), &j))
140 memset(int_found, 0, sizeof(int_found));
142 lh_int_doall(h, &int_doall);
143 if (!TEST_int_eq(int_not_found, 0)) {
144 TEST_info("lhash int doall encountered a not found condition");
147 for (i = 0; i < n_int_tests; i++)
148 if (!TEST_int_eq(int_found[i], 1)) {
149 TEST_info("lhash int doall %d", i);
154 memset(int_found, 0, sizeof(int_found));
156 lh_int_doall_short(h, int_doall_arg, int_found);
157 if (!TEST_int_eq(int_not_found, 0)) {
158 TEST_info("lhash int doall arg encountered a not found condition");
161 for (i = 0; i < n_int_tests; i++)
162 if (!TEST_int_eq(int_found[i], 1)) {
163 TEST_info("lhash int doall arg %d", i);
168 for (i = 0; i < n_dels; i++) {
169 const int b = lh_int_delete(h, &dels[i].data) == NULL;
170 if (!TEST_int_eq(b ^ dels[i].null, 0)) {
171 TEST_info("lhash int delete %d", i);
177 if (!TEST_int_eq(lh_int_error(h), 0))
187 static int int_filter_all(HT_VALUE *v, void *arg)
192 HT_START_KEY_DEFN(intkey)
193 HT_DEF_KEY_FIELD(mykey, int)
194 HT_END_KEY_DEFN(INTKEY)
196 IMPLEMENT_HT_VALUE_TYPE_FNS(int, test, static)
198 static int int_foreach(HT_VALUE *v, void *arg)
200 int *vd = ossl_ht_test_int_from_value(v);
201 const int n = int_find(*vd);
210 static uint64_t hashtable_hash(uint8_t *key, size_t keylen)
212 return (uint64_t)(*(uint32_t *)key);
215 static int test_int_hashtable(void)
228 const size_t n_dels = OSSL_NELEM(dels);
229 HT_CONFIG hash_conf = {
240 HT_VALUE_LIST *list = NULL;
242 ht = ossl_ht_new(&hash_conf);
249 for (i = 0; i < n_int_tests; i++) {
250 HT_SET_KEY_FIELD(&key, mykey, int_tests[i]);
251 if (!TEST_int_eq(ossl_ht_test_int_insert(ht, TO_HT_KEY(&key),
252 &int_tests[i], NULL), 1)) {
253 TEST_info("int insert %zu", i);
259 if (!TEST_int_eq((size_t)ossl_ht_count(ht), n_int_tests))
262 /* foreach, no arg */
263 memset(int_found, 0, sizeof(int_found));
265 ossl_ht_foreach_until(ht, int_foreach, NULL);
266 if (!TEST_int_eq(int_not_found, 0)) {
267 TEST_info("hashtable int foreach encountered a not found condition");
271 for (i = 0; i < n_int_tests; i++)
272 if (!TEST_int_eq(int_found[i], 1)) {
273 TEST_info("hashtable int foreach %zu", i);
278 list = ossl_ht_filter(ht, 64, int_filter_all, NULL);
279 if (!TEST_int_eq((size_t)list->list_len, n_int_tests))
281 ossl_ht_value_list_free(list);
284 for (i = 0; i < n_dels; i++) {
285 HT_SET_KEY_FIELD(&key, mykey, dels[i].data);
286 todel = ossl_ht_delete(ht, TO_HT_KEY(&key));
287 if (dels[i].should_del) {
288 if (!TEST_int_eq(todel, 1)) {
289 TEST_info("hashtable couldn't find entry %d to delete\n",
294 if (!TEST_int_eq(todel, 0)) {
295 TEST_info("%d found an entry that shouldn't be there\n", dels[i].data);
307 static unsigned long int stress_hash(const int *p)
312 #ifdef MEASURE_HASH_PERFORMANCE
314 timeval_subtract (struct timeval *result, struct timeval *x, struct timeval *y)
316 /* Perform the carry for the later subtraction by updating y. */
317 if (x->tv_usec < y->tv_usec) {
318 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
319 y->tv_usec -= 1000000 * nsec;
322 if (x->tv_usec - y->tv_usec > 1000000) {
323 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
324 y->tv_usec += 1000000 * nsec;
329 * Compute the time remaining to wait.
330 * tv_usec is certainly positive.
332 result->tv_sec = x->tv_sec - y->tv_sec;
333 result->tv_usec = x->tv_usec - y->tv_usec;
335 /* Return 1 if result is negative. */
336 return x->tv_sec < y->tv_sec;
340 static int test_stress(void)
342 LHASH_OF(int) *h = lh_int_new(&stress_hash, &int_cmp);
343 const unsigned int n = 2500000;
345 int testresult = 0, *p;
346 #ifdef MEASURE_HASH_PERFORMANCE
347 struct timeval start, end, delta;
352 #ifdef MEASURE_HASH_PERFORMANCE
353 gettimeofday(&start, NULL);
356 for (i = 0; i < n; i++) {
357 p = OPENSSL_malloc(sizeof(i));
359 TEST_info("lhash stress out of memory %d", i);
367 if (!TEST_int_eq(lh_int_num_items(h), n))
370 /* delete in a different order */
371 for (i = 0; i < n; i++) {
372 const int j = (7 * i + 4) % n * 3 + 1;
374 if (!TEST_ptr(p = lh_int_delete(h, &j))) {
375 TEST_info("lhash stress delete %d\n", i);
378 if (!TEST_int_eq(*p, j)) {
379 TEST_info("lhash stress bad value %d", i);
387 #ifdef MEASURE_HASH_PERFORMANCE
388 gettimeofday(&end, NULL);
389 timeval_subtract(&delta, &end, &start);
390 TEST_info("lhash stress runs in %ld.%ld seconds", delta.tv_sec, delta.tv_usec);
396 static void hashtable_intfree(HT_VALUE *v)
398 OPENSSL_free(v->value);
401 static int test_hashtable_stress(void)
403 const unsigned int n = 2500000;
405 int testresult = 0, *p;
406 HT_CONFIG hash_conf = {
407 NULL, /* use default context */
408 hashtable_intfree, /* our free function */
409 hashtable_hash, /* our hash function */
410 625000, /* preset hash size */
414 #ifdef MEASURE_HASH_PERFORMANCE
415 struct timeval start, end, delta;
418 h = ossl_ht_new(&hash_conf);
423 #ifdef MEASURE_HASH_PERFORMANCE
424 gettimeofday(&start, NULL);
430 for (i = 0; i < n; i++) {
431 p = OPENSSL_malloc(sizeof(i));
433 TEST_info("hashtable stress out of memory %d", i);
437 HT_SET_KEY_FIELD(&key, mykey, *p);
438 if (!TEST_int_eq(ossl_ht_test_int_insert(h, TO_HT_KEY(&key),
440 TEST_info("hashtable unable to insert element %d\n", *p);
445 /* make sure we stored everything */
446 if (!TEST_int_eq((size_t)ossl_ht_count(h), n))
449 /* delete in a different order */
450 for (i = 0; i < n; i++) {
451 const int j = (7 * i + 4) % n * 3 + 1;
452 HT_SET_KEY_FIELD(&key, mykey, j);
453 if (!TEST_int_eq((ossl_ht_delete(h, TO_HT_KEY(&key))), 1)) {
454 TEST_info("hashtable didn't delete key %d\n", j);
461 #ifdef MEASURE_HASH_PERFORMANCE
462 gettimeofday(&end, NULL);
463 timeval_subtract(&delta, &end, &start);
464 TEST_info("hashtable stress runs in %ld.%ld seconds", delta.tv_sec, delta.tv_usec);
470 typedef struct test_mt_entry {
475 static HT *m_ht = NULL;
476 #define TEST_MT_POOL_SZ 256
477 #define TEST_THREAD_ITERATIONS 10000
479 static struct test_mt_entry test_mt_entries[TEST_MT_POOL_SZ];
480 static char *worker_exits[4];
482 HT_START_KEY_DEFN(mtkey)
483 HT_DEF_KEY_FIELD(index, unsigned int)
484 HT_END_KEY_DEFN(MTKEY)
486 IMPLEMENT_HT_VALUE_TYPE_FNS(TEST_MT_ENTRY, mt, static)
488 static int worker_num = 0;
489 static CRYPTO_RWLOCK *worker_lock;
490 static int free_failure = 0;
491 static int shutting_down = 0;
492 static int global_iteration = 0;
494 static void hashtable_mt_free(HT_VALUE *v)
496 TEST_MT_ENTRY *m = ossl_ht_mt_TEST_MT_ENTRY_from_value(v);
500 CRYPTO_atomic_load_int(&m->pending_delete, &pending_delete, worker_lock);
502 if (shutting_down == 1)
505 if (pending_delete == 0) {
506 TEST_info("Freeing element which was not scheduled for free");
509 CRYPTO_atomic_add(&m->pending_delete, -1,
514 #define BEHAVIOR_MASK 0x3
520 static void do_mt_hash_work(void)
526 TEST_MT_ENTRY *expected_m = NULL;
528 TEST_MT_ENTRY **r = NULL;
535 CRYPTO_atomic_add(&worker_num, 1, &num, worker_lock);
536 num--; /* atomic_add is an add/fetch operation */
540 for (iter = 0; iter < TEST_THREAD_ITERATIONS; iter++) {
541 if (!RAND_bytes((unsigned char *)&index, sizeof(unsigned int))) {
542 worker_exits[num] = "Failed to get random index";
545 index %= TEST_MT_POOL_SZ;
546 if (!RAND_bytes((unsigned char *)&behavior, sizeof(char))) {
547 worker_exits[num] = "Failed to get random behavior";
550 behavior &= BEHAVIOR_MASK;
552 expected_m = &test_mt_entries[index];
554 HT_SET_KEY_FIELD(&key, index, index);
556 if (!CRYPTO_atomic_add(&global_iteration, 1, &giter, worker_lock)) {
557 worker_exits[num] = "Unable to increment global iterator";
562 ossl_ht_read_lock(m_ht);
563 m = ossl_ht_mt_TEST_MT_ENTRY_get(m_ht, TO_HT_KEY(&key), &v);
564 if (m != NULL && m != expected_m) {
565 worker_exits[num] = "Read unexpected value from hashtable";
566 TEST_info("Iteration %d Read unexpected value %p when %p expected",
567 giter, (void *)m, (void *)expected_m);
569 ossl_ht_read_unlock(m_ht);
570 if (worker_exits[num] != NULL)
575 ossl_ht_write_lock(m_ht);
576 if (behavior == DO_REPLACE) {
580 expected_rc = !expected_m->in_table;
584 if (expected_rc != ossl_ht_mt_TEST_MT_ENTRY_insert(m_ht,
587 TEST_info("Iteration %d Expected rc %d on %s of element %d which is %s\n",
588 giter, expected_rc, behavior == DO_REPLACE ? "replace" : "insert",
589 index, expected_m->in_table ? "in table" : "not in table");
590 worker_exits[num] = "Failure on insert";
592 if (expected_rc == 1)
593 expected_m->in_table = 1;
594 ossl_ht_write_unlock(m_ht);
595 if (worker_exits[num] != NULL)
599 ossl_ht_write_lock(m_ht);
600 expected_rc = expected_m->in_table;
601 if (expected_rc != ossl_ht_delete(m_ht, TO_HT_KEY(&key))) {
602 TEST_info("Iteration %d Expected rc %d on delete of element %d which is %s\n",
603 giter, expected_rc, index,
604 expected_m->in_table ? "in table" : "not in table");
605 worker_exits[num] = "Failure on delete";
607 if (expected_rc == 1) {
608 expected_m->in_table = 0;
609 CRYPTO_atomic_add(&expected_m->pending_delete, 1, &ret, worker_lock);
611 ossl_ht_write_unlock(m_ht);
612 if (worker_exits[num] != NULL)
616 worker_exits[num] = "Undefined behavior specified";
622 static int test_hashtable_multithread(void)
624 HT_CONFIG hash_conf = {
625 NULL, /* use default context */
626 hashtable_mt_free, /* our free function */
627 NULL, /* default hash function */
628 0, /* default hash size */
633 #ifdef MEASURE_HASH_PERFORMANCE
634 struct timeval start, end, delta;
637 memset(worker_exits, 0, sizeof(char *) * 4);
638 memset(test_mt_entries, 0, sizeof(TEST_MT_ENTRY) * TEST_MT_POOL_SZ);
639 memset(workers, 0, sizeof(thread_t) * 4);
641 m_ht = ossl_ht_new(&hash_conf);
646 worker_lock = CRYPTO_THREAD_lock_new();
647 if (worker_lock == NULL)
649 #ifdef MEASURE_HASH_PERFORMANCE
650 gettimeofday(&start, NULL);
653 for (i = 0; i < 4; i++) {
654 if (!run_thread(&workers[i], do_mt_hash_work))
659 for (--i; i >= 0; i--) {
660 wait_for_thread(workers[i]);
665 * Now that the workers are done, check for any error
669 for (i = 0; i < 4; i++) {
670 if (worker_exits[i] != NULL) {
671 TEST_info("Worker %d failed: %s\n", i, worker_exits[i]);
675 if (free_failure == 1) {
676 TEST_info("Encountered a free failure");
680 #ifdef MEASURE_HASH_PERFORMANCE
681 gettimeofday(&end, NULL);
682 timeval_subtract(&delta, &end, &start);
683 TEST_info("multithread stress runs 40000 ops in %ld.%ld seconds", delta.tv_sec, delta.tv_usec);
693 int setup_tests(void)
695 ADD_TEST(test_int_lhash);
696 ADD_TEST(test_stress);
697 ADD_TEST(test_int_hashtable);
698 ADD_TEST(test_hashtable_stress);
699 ADD_TEST(test_hashtable_multithread);