X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=crypto%2Flhash%2Flhash.c;h=f7ac9d02f58b1017e4e1c3d7ef2f7368fdd6de08;hb=cab76c0f6482df5140efa2ca93c9e2d972fcd9b0;hp=19c6d2c31d5e0734063efaa619d3ec0ca2b4f284;hpb=152d26461609ae36f329d6f48b2d0749e43834f3;p=oweals%2Fopenssl.git diff --git a/crypto/lhash/lhash.c b/crypto/lhash/lhash.c index 19c6d2c31d..f7ac9d02f5 100644 --- a/crypto/lhash/lhash.c +++ b/crypto/lhash/lhash.c @@ -1,5 +1,5 @@ /* - * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -12,8 +12,26 @@ #include #include #include +#include #include "lhash_lcl.h" +/* + * A hashing implementation that appears to be based on the linear hashing + * alogrithm: + * https://en.wikipedia.org/wiki/Linear_hashing + * + * Litwin, Witold (1980), "Linear hashing: A new tool for file and table + * addressing", Proc. 6th Conference on Very Large Databases: 212-223 + * http://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf + * + * From the wikipedia article "Linear hashing is used in the BDB Berkeley + * database system, which in turn is used by many software systems such as + * OpenLDAP, using a C implementation derived from the CACM article and first + * published on the Usenet in 1988 by Esmond Pitt." + * + * The CACM paper is available here: + * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf + */ #undef MIN_NODES #define MIN_NODES 16 @@ -28,10 +46,16 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c) { OPENSSL_LHASH *ret; - if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) - goto err0; + if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { + /* + * Do not set the error code, because the ERR code uses LHASH + * and we want to avoid possible endless error loop. + * CRYPTOerr(CRYPTO_F_OPENSSL_LH_NEW, ERR_R_MALLOC_FAILURE); + */ + return NULL; + } if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL) - goto err1; + goto err; ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c); ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h); ret->num_nodes = MIN_NODES / 2; @@ -39,12 +63,12 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c) ret->pmax = MIN_NODES / 2; ret->up_load = UP_LOAD; ret->down_load = DOWN_LOAD; - return (ret); + return ret; - err1: +err: + OPENSSL_free(ret->b); OPENSSL_free(ret); - err0: - return (NULL); + return NULL; } void OPENSSL_LH_free(OPENSSL_LHASH *lh) @@ -82,7 +106,7 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data) if (*rn == NULL) { if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) { lh->error++; - return (NULL); + return NULL; } nn->data = data; nn->next = NULL; @@ -92,12 +116,11 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data) lh->num_insert++; lh->num_items++; } else { /* replace same key */ - ret = (*rn)->data; (*rn)->data = data; lh->num_replace++; } - return (ret); + return ret; } void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data) @@ -111,7 +134,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data) if (*rn == NULL) { lh->num_no_delete++; - return (NULL); + return NULL; } else { nn = *rn; *rn = nn->next; @@ -125,7 +148,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data) (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))) contract(lh); - return (ret); + return ret; } void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data) @@ -134,17 +157,19 @@ void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data) OPENSSL_LH_NODE **rn; void *ret; - lh->error = 0; + tsan_store((TSAN_QUALIFIER int *)&lh->error, 0); + rn = getrn(lh, data, &hash); if (*rn == NULL) { - lh->num_retrieve_miss++; - return (NULL); + tsan_counter(&lh->num_retrieve_miss); + return NULL; } else { ret = (*rn)->data; - lh->num_retrieve++; + tsan_counter(&lh->num_retrieve); } - return (ret); + + return ret; } static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg, @@ -187,16 +212,34 @@ void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void static int expand(OPENSSL_LHASH *lh) { OPENSSL_LH_NODE **n, **n1, **n2, *np; - unsigned int p, i, j; - unsigned long hash, nni; + unsigned int p, pmax, nni, j; + unsigned long hash; + + nni = lh->num_alloc_nodes; + p = lh->p; + pmax = lh->pmax; + if (p + 1 >= pmax) { + j = nni * 2; + n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j); + if (n == NULL) { + lh->error++; + return 0; + } + lh->b = n; + memset(n + nni, 0, sizeof(*n) * (j - nni)); + lh->pmax = nni; + lh->num_alloc_nodes = j; + lh->num_expand_reallocs++; + lh->p = 0; + } else { + lh->p++; + } lh->num_nodes++; lh->num_expands++; - p = (int)lh->p++; n1 = &(lh->b[p]); - n2 = &(lh->b[p + (int)lh->pmax]); + n2 = &(lh->b[p + pmax]); *n2 = NULL; - nni = lh->num_alloc_nodes; for (np = *n1; np != NULL;) { hash = np->hash; @@ -209,23 +252,6 @@ static int expand(OPENSSL_LHASH *lh) np = *n1; } - if ((lh->p) >= lh->pmax) { - j = (int)lh->num_alloc_nodes * 2; - n = OPENSSL_realloc(lh->b, (int)(sizeof(OPENSSL_LH_NODE *) * j)); - if (n == NULL) { - /* fputs("realloc error in lhash",stderr); */ - lh->error++; - lh->p = 0; - return 0; - } - for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */ - n[i] = NULL; /* 02/03/92 eay */ - lh->pmax = lh->num_alloc_nodes; - lh->num_alloc_nodes = j; - lh->num_expand_reallocs++; - lh->p = 0; - lh->b = n; - } return 1; } @@ -272,7 +298,7 @@ static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, OPENSSL_LH_COMPFUNC cf; hash = (*(lh->hash)) (data); - lh->num_hash_calls++; + tsan_counter(&lh->num_hash_calls); *rhash = hash; nn = hash % lh->pmax; @@ -282,17 +308,17 @@ static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, cf = lh->comp; ret = &(lh->b[(int)nn]); for (n1 = *ret; n1 != NULL; n1 = n1->next) { - lh->num_hash_comps++; + tsan_counter(&lh->num_hash_comps); if (n1->hash != hash) { ret = &(n1->next); continue; } - lh->num_comp_calls++; + tsan_counter(&lh->num_comp_calls); if (cf(n1->data, data) == 0) break; ret = &(n1->next); } - return (ret); + return ret; } /* @@ -308,12 +334,7 @@ unsigned long OPENSSL_LH_strhash(const char *c) int r; if ((c == NULL) || (*c == '\0')) - return (ret); -/*- - unsigned char b[16]; - MD5(c,strlen(c),b); - return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); -*/ + return ret; n = 0x100; while (*c) { @@ -325,7 +346,7 @@ unsigned long OPENSSL_LH_strhash(const char *c) ret ^= v * v; c++; } - return ((ret >> 16) ^ ret); + return (ret >> 16) ^ ret; } unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)