1 /* 2 * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved. 4 * 5 * Licensed under the OpenSSL license (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 9 */ 10 11 #include <stdio.h> 12 #include <string.h> 13 14 #include <openssl/opensslconf.h> 15 #include <openssl/lhash.h> 16 #include <openssl/err.h> 17 #include <openssl/crypto.h> 18 19 #include "internal/nelem.h" 20 #include "testutil.h" 21 22 /* 23 * The macros below generate unused functions which error out one of the clang 24 * builds. We disable this check here. 25 */ 26 #ifdef __clang__ 27 #pragma clang diagnostic ignored "-Wunused-function" 28 #endif 29 30 DEFINE_LHASH_OF(int); 31 32 static int int_tests[] = { 65537, 13, 1, 3, -5, 6, 7, 4, -10, -12, -14, 22, 9, 33 -17, 16, 17, -23, 35, 37, 173, 11 }; 34 static const unsigned int n_int_tests = OSSL_NELEM(int_tests); 35 static short int_found[OSSL_NELEM(int_tests)]; 36 37 static unsigned long int int_hash(const int *p) 38 { 39 return 3 & *p; /* To force collisions */ 40 } 41 42 static int int_cmp(const int *p, const int *q) 43 { 44 return *p != *q; 45 } 46 47 static int int_find(int n) 48 { 49 unsigned int i; 50 51 for (i = 0; i < n_int_tests; i++) 52 if (int_tests[i] == n) 53 return i; 54 return -1; 55 } 56 57 static void int_doall(int *v) 58 { 59 int_found[int_find(*v)]++; 60 } 61 62 static void int_doall_arg(int *p, short *f) 63 { 64 f[int_find(*p)]++; 65 } 66 67 IMPLEMENT_LHASH_DOALL_ARG(int, short); 68 69 static int test_int_lhash(void) 70 { 71 static struct { 72 int data; 73 int null; 74 } dels[] = { 75 { 65537, 0 }, 76 { 173, 0 }, 77 { 999, 1 }, 78 { 37, 0 }, 79 { 1, 0 }, 80 { 34, 1 } 81 }; 82 const unsigned int n_dels = OSSL_NELEM(dels); 83 LHASH_OF(int) *h = lh_int_new(&int_hash, &int_cmp); 84 unsigned int i; 85 int testresult = 0, j, *p; 86 87 if (!TEST_ptr(h)) 88 goto end; 89 90 /* insert */ 91 for (i = 0; i < n_int_tests; i++) 92 if (!TEST_ptr_null(lh_int_insert(h, int_tests + i))) { 93 TEST_info("int insert %d", i); 94 goto end; 95 } 96 97 /* num_items */ 98 if (!TEST_int_eq(lh_int_num_items(h), n_int_tests)) 99 goto end; 100 101 /* retrieve */ 102 for (i = 0; i < n_int_tests; i++) 103 if (!TEST_int_eq(*lh_int_retrieve(h, int_tests + i), int_tests[i])) { 104 TEST_info("lhash int retrieve value %d", i); 105 goto end; 106 } 107 for (i = 0; i < n_int_tests; i++) 108 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + i), int_tests + i)) { 109 TEST_info("lhash int retrieve address %d", i); 110 goto end; 111 } 112 j = 1; 113 if (!TEST_ptr_eq(lh_int_retrieve(h, &j), int_tests + 2)) 114 goto end; 115 116 /* replace */ 117 j = 13; 118 if (!TEST_ptr(p = lh_int_insert(h, &j))) 119 goto end; 120 if (!TEST_ptr_eq(p, int_tests + 1)) 121 goto end; 122 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + 1), &j)) 123 goto end; 124 125 /* do_all */ 126 memset(int_found, 0, sizeof(int_found)); 127 lh_int_doall(h, &int_doall); 128 for (i = 0; i < n_int_tests; i++) 129 if (!TEST_int_eq(int_found[i], 1)) { 130 TEST_info("lhash int doall %d", i); 131 goto end; 132 } 133 134 /* do_all_arg */ 135 memset(int_found, 0, sizeof(int_found)); 136 lh_int_doall_short(h, int_doall_arg, int_found); 137 for (i = 0; i < n_int_tests; i++) 138 if (!TEST_int_eq(int_found[i], 1)) { 139 TEST_info("lhash int doall arg %d", i); 140 goto end; 141 } 142 143 /* delete */ 144 for (i = 0; i < n_dels; i++) { 145 const int b = lh_int_delete(h, &dels[i].data) == NULL; 146 if (!TEST_int_eq(b ^ dels[i].null, 0)) { 147 TEST_info("lhash int delete %d", i); 148 goto end; 149 } 150 } 151 152 /* error */ 153 if (!TEST_int_eq(lh_int_error(h), 0)) 154 goto end; 155 156 testresult = 1; 157 end: 158 lh_int_free(h); 159 return testresult; 160 } 161 162 static unsigned long int stress_hash(const int *p) 163 { 164 return *p; 165 } 166 167 static int test_stress(void) 168 { 169 LHASH_OF(int) *h = lh_int_new(&stress_hash, &int_cmp); 170 const unsigned int n = 2500000; 171 unsigned int i; 172 int testresult = 0, *p; 173 174 if (!TEST_ptr(h)) 175 goto end; 176 177 /* insert */ 178 for (i = 0; i < n; i++) { 179 p = OPENSSL_malloc(sizeof(i)); 180 if (!TEST_ptr(p)) { 181 TEST_info("lhash stress out of memory %d", i); 182 goto end; 183 } 184 *p = 3 * i + 1; 185 lh_int_insert(h, p); 186 } 187 188 /* num_items */ 189 if (!TEST_int_eq(lh_int_num_items(h), n)) 190 goto end; 191 192 TEST_info("hash full statistics:"); 193 OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err); 194 TEST_note("hash full node usage:"); 195 OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err); 196 197 /* delete in a different order */ 198 for (i = 0; i < n; i++) { 199 const int j = (7 * i + 4) % n * 3 + 1; 200 201 if (!TEST_ptr(p = lh_int_delete(h, &j))) { 202 TEST_info("lhash stress delete %d\n", i); 203 goto end; 204 } 205 if (!TEST_int_eq(*p, j)) { 206 TEST_info("lhash stress bad value %d", i); 207 goto end; 208 } 209 OPENSSL_free(p); 210 } 211 212 TEST_info("hash empty statistics:"); 213 OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err); 214 TEST_note("hash empty node usage:"); 215 OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err); 216 217 testresult = 1; 218 end: 219 lh_int_free(h); 220 return testresult; 221 } 222 223 int setup_tests(void) 224 { 225 ADD_TEST(test_int_lhash); 226 ADD_TEST(test_stress); 227 return 1; 228 } 229