1 /* 2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include <stdio.h> 11 #include <string.h> 12 #include <stdlib.h> 13 #include <openssl/crypto.h> 14 #include <openssl/lhash.h> 15 #include <openssl/err.h> 16 #include "internal/ctype.h" 17 #include "internal/lhash.h" 18 #include "lhash_lcl.h" 19 20 /* 21 * A hashing implementation that appears to be based on the linear hashing 22 * alogrithm: 23 * https://en.wikipedia.org/wiki/Linear_hashing 24 * 25 * Litwin, Witold (1980), "Linear hashing: A new tool for file and table 26 * addressing", Proc. 6th Conference on Very Large Databases: 212-223 27 * http://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf 28 * 29 * From the wikipedia article "Linear hashing is used in the BDB Berkeley 30 * database system, which in turn is used by many software systems such as 31 * OpenLDAP, using a C implementation derived from the CACM article and first 32 * published on the Usenet in 1988 by Esmond Pitt." 33 * 34 * The CACM paper is available here: 35 * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf 36 */ 37 38 #undef MIN_NODES 39 #define MIN_NODES 16 40 #define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */ 41 #define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */ 42 43 static int expand(OPENSSL_LHASH *lh); 44 static void contract(OPENSSL_LHASH *lh); 45 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash); 46 47 OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c) 48 { 49 OPENSSL_LHASH *ret; 50 51 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 52 /* 53 * Do not set the error code, because the ERR code uses LHASH 54 * and we want to avoid possible endless error loop. 55 * CRYPTOerr(CRYPTO_F_OPENSSL_LH_NEW, ERR_R_MALLOC_FAILURE); 56 */ 57 return NULL; 58 } 59 if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL) 60 goto err; 61 ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c); 62 ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h); 63 ret->num_nodes = MIN_NODES / 2; 64 ret->num_alloc_nodes = MIN_NODES; 65 ret->pmax = MIN_NODES / 2; 66 ret->up_load = UP_LOAD; 67 ret->down_load = DOWN_LOAD; 68 return ret; 69 70 err: 71 OPENSSL_free(ret->b); 72 OPENSSL_free(ret); 73 return NULL; 74 } 75 76 void OPENSSL_LH_free(OPENSSL_LHASH *lh) 77 { 78 unsigned int i; 79 OPENSSL_LH_NODE *n, *nn; 80 81 if (lh == NULL) 82 return; 83 84 for (i = 0; i < lh->num_nodes; i++) { 85 n = lh->b[i]; 86 while (n != NULL) { 87 nn = n->next; 88 OPENSSL_free(n); 89 n = nn; 90 } 91 } 92 OPENSSL_free(lh->b); 93 OPENSSL_free(lh); 94 } 95 96 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data) 97 { 98 unsigned long hash; 99 OPENSSL_LH_NODE *nn, **rn; 100 void *ret; 101 102 lh->error = 0; 103 if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh)) 104 return NULL; /* 'lh->error++' already done in 'expand' */ 105 106 rn = getrn(lh, data, &hash); 107 108 if (*rn == NULL) { 109 if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) { 110 lh->error++; 111 return NULL; 112 } 113 nn->data = data; 114 nn->next = NULL; 115 nn->hash = hash; 116 *rn = nn; 117 ret = NULL; 118 lh->num_insert++; 119 lh->num_items++; 120 } else { /* replace same key */ 121 ret = (*rn)->data; 122 (*rn)->data = data; 123 lh->num_replace++; 124 } 125 return ret; 126 } 127 128 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data) 129 { 130 unsigned long hash; 131 OPENSSL_LH_NODE *nn, **rn; 132 void *ret; 133 134 lh->error = 0; 135 rn = getrn(lh, data, &hash); 136 137 if (*rn == NULL) { 138 lh->num_no_delete++; 139 return NULL; 140 } else { 141 nn = *rn; 142 *rn = nn->next; 143 ret = nn->data; 144 OPENSSL_free(nn); 145 lh->num_delete++; 146 } 147 148 lh->num_items--; 149 if ((lh->num_nodes > MIN_NODES) && 150 (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))) 151 contract(lh); 152 153 return ret; 154 } 155 156 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data) 157 { 158 unsigned long hash; 159 OPENSSL_LH_NODE **rn; 160 void *ret; 161 162 tsan_store((TSAN_QUALIFIER int *)&lh->error, 0); 163 164 rn = getrn(lh, data, &hash); 165 166 if (*rn == NULL) { 167 tsan_counter(&lh->num_retrieve_miss); 168 return NULL; 169 } else { 170 ret = (*rn)->data; 171 tsan_counter(&lh->num_retrieve); 172 } 173 174 return ret; 175 } 176 177 static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg, 178 OPENSSL_LH_DOALL_FUNC func, 179 OPENSSL_LH_DOALL_FUNCARG func_arg, void *arg) 180 { 181 int i; 182 OPENSSL_LH_NODE *a, *n; 183 184 if (lh == NULL) 185 return; 186 187 /* 188 * reverse the order so we search from 'top to bottom' We were having 189 * memory leaks otherwise 190 */ 191 for (i = lh->num_nodes - 1; i >= 0; i--) { 192 a = lh->b[i]; 193 while (a != NULL) { 194 n = a->next; 195 if (use_arg) 196 func_arg(a->data, arg); 197 else 198 func(a->data); 199 a = n; 200 } 201 } 202 } 203 204 void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func) 205 { 206 doall_util_fn(lh, 0, func, (OPENSSL_LH_DOALL_FUNCARG)0, NULL); 207 } 208 209 void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg) 210 { 211 doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC)0, func, arg); 212 } 213 214 static int expand(OPENSSL_LHASH *lh) 215 { 216 OPENSSL_LH_NODE **n, **n1, **n2, *np; 217 unsigned int p, pmax, nni, j; 218 unsigned long hash; 219 220 nni = lh->num_alloc_nodes; 221 p = lh->p; 222 pmax = lh->pmax; 223 if (p + 1 >= pmax) { 224 j = nni * 2; 225 n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j); 226 if (n == NULL) { 227 lh->error++; 228 return 0; 229 } 230 lh->b = n; 231 memset(n + nni, 0, sizeof(*n) * (j - nni)); 232 lh->pmax = nni; 233 lh->num_alloc_nodes = j; 234 lh->num_expand_reallocs++; 235 lh->p = 0; 236 } else { 237 lh->p++; 238 } 239 240 lh->num_nodes++; 241 lh->num_expands++; 242 n1 = &(lh->b[p]); 243 n2 = &(lh->b[p + pmax]); 244 *n2 = NULL; 245 246 for (np = *n1; np != NULL;) { 247 hash = np->hash; 248 if ((hash % nni) != p) { /* move it */ 249 *n1 = (*n1)->next; 250 np->next = *n2; 251 *n2 = np; 252 } else 253 n1 = &((*n1)->next); 254 np = *n1; 255 } 256 257 return 1; 258 } 259 260 static void contract(OPENSSL_LHASH *lh) 261 { 262 OPENSSL_LH_NODE **n, *n1, *np; 263 264 np = lh->b[lh->p + lh->pmax - 1]; 265 lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */ 266 if (lh->p == 0) { 267 n = OPENSSL_realloc(lh->b, 268 (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax)); 269 if (n == NULL) { 270 /* fputs("realloc error in lhash",stderr); */ 271 lh->error++; 272 return; 273 } 274 lh->num_contract_reallocs++; 275 lh->num_alloc_nodes /= 2; 276 lh->pmax /= 2; 277 lh->p = lh->pmax - 1; 278 lh->b = n; 279 } else 280 lh->p--; 281 282 lh->num_nodes--; 283 lh->num_contracts++; 284 285 n1 = lh->b[(int)lh->p]; 286 if (n1 == NULL) 287 lh->b[(int)lh->p] = np; 288 else { 289 while (n1->next != NULL) 290 n1 = n1->next; 291 n1->next = np; 292 } 293 } 294 295 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, 296 const void *data, unsigned long *rhash) 297 { 298 OPENSSL_LH_NODE **ret, *n1; 299 unsigned long hash, nn; 300 OPENSSL_LH_COMPFUNC cf; 301 302 hash = (*(lh->hash)) (data); 303 tsan_counter(&lh->num_hash_calls); 304 *rhash = hash; 305 306 nn = hash % lh->pmax; 307 if (nn < lh->p) 308 nn = hash % lh->num_alloc_nodes; 309 310 cf = lh->comp; 311 ret = &(lh->b[(int)nn]); 312 for (n1 = *ret; n1 != NULL; n1 = n1->next) { 313 tsan_counter(&lh->num_hash_comps); 314 if (n1->hash != hash) { 315 ret = &(n1->next); 316 continue; 317 } 318 tsan_counter(&lh->num_comp_calls); 319 if (cf(n1->data, data) == 0) 320 break; 321 ret = &(n1->next); 322 } 323 return ret; 324 } 325 326 /* 327 * The following hash seems to work very well on normal text strings no 328 * collisions on /usr/dict/words and it distributes on %2^n quite well, not 329 * as good as MD5, but still good. 330 */ 331 unsigned long OPENSSL_LH_strhash(const char *c) 332 { 333 unsigned long ret = 0; 334 long n; 335 unsigned long v; 336 int r; 337 338 if ((c == NULL) || (*c == '\0')) 339 return ret; 340 341 n = 0x100; 342 while (*c) { 343 v = n | (*c); 344 n += 0x100; 345 r = (int)((v >> 2) ^ v) & 0x0f; 346 ret = (ret << r) | (ret >> (32 - r)); 347 ret &= 0xFFFFFFFFL; 348 ret ^= v * v; 349 c++; 350 } 351 return (ret >> 16) ^ ret; 352 } 353 354 unsigned long openssl_lh_strcasehash(const char *c) 355 { 356 unsigned long ret = 0; 357 long n; 358 unsigned long v; 359 int r; 360 361 if (c == NULL || *c == '\0') 362 return ret; 363 364 for (n = 0x100; *c != '\0'; n += 0x100) { 365 v = n | ossl_tolower(*c); 366 r = (int)((v >> 2) ^ v) & 0x0f; 367 ret = (ret << r) | (ret >> (32 - r)); 368 ret &= 0xFFFFFFFFL; 369 ret ^= v * v; 370 c++; 371 } 372 return (ret >> 16) ^ ret; 373 } 374 375 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh) 376 { 377 return lh ? lh->num_items : 0; 378 } 379 380 unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh) 381 { 382 return lh->down_load; 383 } 384 385 void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load) 386 { 387 lh->down_load = down_load; 388 } 389 390 int OPENSSL_LH_error(OPENSSL_LHASH *lh) 391 { 392 return lh->error; 393 } 394