1 /* 2 * Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved. 4 * 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 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 static short int_not_found; 37 38 static unsigned long int int_hash(const int *p) 39 { 40 return 3 & *p; /* To force collisions */ 41 } 42 43 static int int_cmp(const int *p, const int *q) 44 { 45 return *p != *q; 46 } 47 48 static int int_find(int n) 49 { 50 unsigned int i; 51 52 for (i = 0; i < n_int_tests; i++) 53 if (int_tests[i] == n) 54 return i; 55 return -1; 56 } 57 58 static void int_doall(int *v) 59 { 60 const int n = int_find(*v); 61 62 if (n < 0) 63 int_not_found++; 64 else 65 int_found[n]++; 66 } 67 68 static void int_doall_arg(int *p, short *f) 69 { 70 const int n = int_find(*p); 71 72 if (n < 0) 73 int_not_found++; 74 else 75 f[n]++; 76 } 77 78 IMPLEMENT_LHASH_DOALL_ARG(int, short); 79 80 static int test_int_lhash(void) 81 { 82 static struct { 83 int data; 84 int null; 85 } dels[] = { 86 { 65537, 0 }, 87 { 173, 0 }, 88 { 999, 1 }, 89 { 37, 0 }, 90 { 1, 0 }, 91 { 34, 1 } 92 }; 93 const unsigned int n_dels = OSSL_NELEM(dels); 94 LHASH_OF(int) *h = lh_int_new(&int_hash, &int_cmp); 95 unsigned int i; 96 int testresult = 0, j, *p; 97 98 if (!TEST_ptr(h)) 99 goto end; 100 101 /* insert */ 102 for (i = 0; i < n_int_tests; i++) 103 if (!TEST_ptr_null(lh_int_insert(h, int_tests + i))) { 104 TEST_info("int insert %d", i); 105 goto end; 106 } 107 108 /* num_items */ 109 if (!TEST_int_eq(lh_int_num_items(h), n_int_tests)) 110 goto end; 111 112 /* retrieve */ 113 for (i = 0; i < n_int_tests; i++) 114 if (!TEST_int_eq(*lh_int_retrieve(h, int_tests + i), int_tests[i])) { 115 TEST_info("lhash int retrieve value %d", i); 116 goto end; 117 } 118 for (i = 0; i < n_int_tests; i++) 119 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + i), int_tests + i)) { 120 TEST_info("lhash int retrieve address %d", i); 121 goto end; 122 } 123 j = 1; 124 if (!TEST_ptr_eq(lh_int_retrieve(h, &j), int_tests + 2)) 125 goto end; 126 127 /* replace */ 128 j = 13; 129 if (!TEST_ptr(p = lh_int_insert(h, &j))) 130 goto end; 131 if (!TEST_ptr_eq(p, int_tests + 1)) 132 goto end; 133 if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + 1), &j)) 134 goto end; 135 136 /* do_all */ 137 memset(int_found, 0, sizeof(int_found)); 138 int_not_found = 0; 139 lh_int_doall(h, &int_doall); 140 if (!TEST_int_eq(int_not_found, 0)) { 141 TEST_info("lhash int doall encountered a not found condition"); 142 goto end; 143 } 144 for (i = 0; i < n_int_tests; i++) 145 if (!TEST_int_eq(int_found[i], 1)) { 146 TEST_info("lhash int doall %d", i); 147 goto end; 148 } 149 150 /* do_all_arg */ 151 memset(int_found, 0, sizeof(int_found)); 152 int_not_found = 0; 153 lh_int_doall_short(h, int_doall_arg, int_found); 154 if (!TEST_int_eq(int_not_found, 0)) { 155 TEST_info("lhash int doall arg encountered a not found condition"); 156 goto end; 157 } 158 for (i = 0; i < n_int_tests; i++) 159 if (!TEST_int_eq(int_found[i], 1)) { 160 TEST_info("lhash int doall arg %d", i); 161 goto end; 162 } 163 164 /* delete */ 165 for (i = 0; i < n_dels; i++) { 166 const int b = lh_int_delete(h, &dels[i].data) == NULL; 167 if (!TEST_int_eq(b ^ dels[i].null, 0)) { 168 TEST_info("lhash int delete %d", i); 169 goto end; 170 } 171 } 172 173 /* error */ 174 if (!TEST_int_eq(lh_int_error(h), 0)) 175 goto end; 176 177 testresult = 1; 178 end: 179 lh_int_free(h); 180 return testresult; 181 } 182 183 static unsigned long int stress_hash(const int *p) 184 { 185 return *p; 186 } 187 188 static int test_stress(void) 189 { 190 LHASH_OF(int) *h = lh_int_new(&stress_hash, &int_cmp); 191 const unsigned int n = 2500000; 192 unsigned int i; 193 int testresult = 0, *p; 194 195 if (!TEST_ptr(h)) 196 goto end; 197 198 /* insert */ 199 for (i = 0; i < n; i++) { 200 p = OPENSSL_malloc(sizeof(i)); 201 if (!TEST_ptr(p)) { 202 TEST_info("lhash stress out of memory %d", i); 203 goto end; 204 } 205 *p = 3 * i + 1; 206 lh_int_insert(h, p); 207 } 208 209 /* num_items */ 210 if (!TEST_int_eq(lh_int_num_items(h), n)) 211 goto end; 212 213 TEST_info("hash full statistics:"); 214 OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err); 215 TEST_note("hash full node usage:"); 216 OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err); 217 218 /* delete in a different order */ 219 for (i = 0; i < n; i++) { 220 const int j = (7 * i + 4) % n * 3 + 1; 221 222 if (!TEST_ptr(p = lh_int_delete(h, &j))) { 223 TEST_info("lhash stress delete %d\n", i); 224 goto end; 225 } 226 if (!TEST_int_eq(*p, j)) { 227 TEST_info("lhash stress bad value %d", i); 228 goto end; 229 } 230 OPENSSL_free(p); 231 } 232 233 TEST_info("hash empty statistics:"); 234 OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err); 235 TEST_note("hash empty node usage:"); 236 OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err); 237 238 testresult = 1; 239 end: 240 lh_int_free(h); 241 return testresult; 242 } 243 244 int setup_tests(void) 245 { 246 ADD_TEST(test_int_lhash); 247 ADD_TEST(test_stress); 248 return 1; 249 } 250