crypto/lhash/lhash.c

   1 /*
   2  * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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     if (lh == NULL)
  79         return;
  80
  81     OPENSSL_LH_flush(lh);
  82     OPENSSL_free(lh->b);
  83     OPENSSL_free(lh);
  84 }
  85
  86 void OPENSSL_LH_flush(OPENSSL_LHASH *lh)
  87 {
  88     unsigned int i;
  89     OPENSSL_LH_NODE *n, *nn;
  90
  91     if (lh == NULL)
  92         return;
  93
  94     for (i = 0; i < lh->num_nodes; i++) {
  95         n = lh->b[i];
  96         while (n != NULL) {
  97             nn = n->next;
  98             OPENSSL_free(n);
  99             n = nn;
 100         }
 101     }
 102 }
 103
 104 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
 105 {
 106     unsigned long hash;
 107     OPENSSL_LH_NODE *nn, **rn;
 108     void *ret;
 109
 110     lh->error = 0;
 111     if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
 112         return NULL;        /* 'lh->error++' already done in 'expand' */
 113
 114     rn = getrn(lh, data, &hash);
 115
 116     if (*rn == NULL) {
 117         if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
 118             lh->error++;
 119             return NULL;
 120         }
 121         nn->data = data;
 122         nn->next = NULL;
 123         nn->hash = hash;
 124         *rn = nn;
 125         ret = NULL;
 126         lh->num_insert++;
 127         lh->num_items++;
 128     } else {                    /* replace same key */
 129         ret = (*rn)->data;
 130         (*rn)->data = data;
 131         lh->num_replace++;
 132     }
 133     return ret;
 134 }
 135
 136 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
 137 {
 138     unsigned long hash;
 139     OPENSSL_LH_NODE *nn, **rn;
 140     void *ret;
 141
 142     lh->error = 0;
 143     rn = getrn(lh, data, &hash);
 144
 145     if (*rn == NULL) {
 146         lh->num_no_delete++;
 147         return NULL;
 148     } else {
 149         nn = *rn;
 150         *rn = nn->next;
 151         ret = nn->data;
 152         OPENSSL_free(nn);
 153         lh->num_delete++;
 154     }
 155
 156     lh->num_items--;
 157     if ((lh->num_nodes > MIN_NODES) &&
 158         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
 159         contract(lh);
 160
 161     return ret;
 162 }
 163
 164 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
 165 {
 166     unsigned long hash;
 167     OPENSSL_LH_NODE **rn;
 168     void *ret;
 169
 170     tsan_store((TSAN_QUALIFIER int *)&lh->error, 0);
 171
 172     rn = getrn(lh, data, &hash);
 173
 174     if (*rn == NULL) {
 175         tsan_counter(&lh->num_retrieve_miss);
 176         return NULL;
 177     } else {
 178         ret = (*rn)->data;
 179         tsan_counter(&lh->num_retrieve);
 180     }
 181
 182     return ret;
 183 }
 184
 185 static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
 186                           OPENSSL_LH_DOALL_FUNC func,
 187                           OPENSSL_LH_DOALL_FUNCARG func_arg, void *arg)
 188 {
 189     int i;
 190     OPENSSL_LH_NODE *a, *n;
 191
 192     if (lh == NULL)
 193         return;
 194
 195     /*
 196      * reverse the order so we search from 'top to bottom' We were having
 197      * memory leaks otherwise
 198      */
 199     for (i = lh->num_nodes - 1; i >= 0; i--) {
 200         a = lh->b[i];
 201         while (a != NULL) {
 202             n = a->next;
 203             if (use_arg)
 204                 func_arg(a->data, arg);
 205             else
 206                 func(a->data);
 207             a = n;
 208         }
 209     }
 210 }
 211
 212 void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
 213 {
 214     doall_util_fn(lh, 0, func, (OPENSSL_LH_DOALL_FUNCARG)0, NULL);
 215 }
 216
 217 void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg)
 218 {
 219     doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC)0, func, arg);
 220 }
 221
 222 static int expand(OPENSSL_LHASH *lh)
 223 {
 224     OPENSSL_LH_NODE **n, **n1, **n2, *np;
 225     unsigned int p, pmax, nni, j;
 226     unsigned long hash;
 227
 228     nni = lh->num_alloc_nodes;
 229     p = lh->p;
 230     pmax = lh->pmax;
 231     if (p + 1 >= pmax) {
 232         j = nni * 2;
 233         n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j);
 234         if (n == NULL) {
 235             lh->error++;
 236             return 0;
 237         }
 238         lh->b = n;
 239         memset(n + nni, 0, sizeof(*n) * (j - nni));
 240         lh->pmax = nni;
 241         lh->num_alloc_nodes = j;
 242         lh->num_expand_reallocs++;
 243         lh->p = 0;
 244     } else {
 245         lh->p++;
 246     }
 247
 248     lh->num_nodes++;
 249     lh->num_expands++;
 250     n1 = &(lh->b[p]);
 251     n2 = &(lh->b[p + pmax]);
 252     *n2 = NULL;
 253
 254     for (np = *n1; np != NULL;) {
 255         hash = np->hash;
 256         if ((hash % nni) != p) { /* move it */
 257             *n1 = (*n1)->next;
 258             np->next = *n2;
 259             *n2 = np;
 260         } else
 261             n1 = &((*n1)->next);
 262         np = *n1;
 263     }
 264
 265     return 1;
 266 }
 267
 268 static void contract(OPENSSL_LHASH *lh)
 269 {
 270     OPENSSL_LH_NODE **n, *n1, *np;
 271
 272     np = lh->b[lh->p + lh->pmax - 1];
 273     lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
 274     if (lh->p == 0) {
 275         n = OPENSSL_realloc(lh->b,
 276                             (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax));
 277         if (n == NULL) {
 278             /* fputs("realloc error in lhash",stderr); */
 279             lh->error++;
 280             return;
 281         }
 282         lh->num_contract_reallocs++;
 283         lh->num_alloc_nodes /= 2;
 284         lh->pmax /= 2;
 285         lh->p = lh->pmax - 1;
 286         lh->b = n;
 287     } else
 288         lh->p--;
 289
 290     lh->num_nodes--;
 291     lh->num_contracts++;
 292
 293     n1 = lh->b[(int)lh->p];
 294     if (n1 == NULL)
 295         lh->b[(int)lh->p] = np;
 296     else {
 297         while (n1->next != NULL)
 298             n1 = n1->next;
 299         n1->next = np;
 300     }
 301 }
 302
 303 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
 304                                const void *data, unsigned long *rhash)
 305 {
 306     OPENSSL_LH_NODE **ret, *n1;
 307     unsigned long hash, nn;
 308     OPENSSL_LH_COMPFUNC cf;
 309
 310     hash = (*(lh->hash)) (data);
 311     tsan_counter(&lh->num_hash_calls);
 312     *rhash = hash;
 313
 314     nn = hash % lh->pmax;
 315     if (nn < lh->p)
 316         nn = hash % lh->num_alloc_nodes;
 317
 318     cf = lh->comp;
 319     ret = &(lh->b[(int)nn]);
 320     for (n1 = *ret; n1 != NULL; n1 = n1->next) {
 321         tsan_counter(&lh->num_hash_comps);
 322         if (n1->hash != hash) {
 323             ret = &(n1->next);
 324             continue;
 325         }
 326         tsan_counter(&lh->num_comp_calls);
 327         if (cf(n1->data, data) == 0)
 328             break;
 329         ret = &(n1->next);
 330     }
 331     return ret;
 332 }
 333
 334 /*
 335  * The following hash seems to work very well on normal text strings no
 336  * collisions on /usr/dict/words and it distributes on %2^n quite well, not
 337  * as good as MD5, but still good.
 338  */
 339 unsigned long OPENSSL_LH_strhash(const char *c)
 340 {
 341     unsigned long ret = 0;
 342     long n;
 343     unsigned long v;
 344     int r;
 345
 346     if ((c == NULL) || (*c == '\0'))
 347         return ret;
 348
 349     n = 0x100;
 350     while (*c) {
 351         v = n | (*c);
 352         n += 0x100;
 353         r = (int)((v >> 2) ^ v) & 0x0f;
 354         ret = (ret << r) | (ret >> (32 - r));
 355         ret &= 0xFFFFFFFFL;
 356         ret ^= v * v;
 357         c++;
 358     }
 359     return (ret >> 16) ^ ret;
 360 }
 361
 362 unsigned long openssl_lh_strcasehash(const char *c)
 363 {
 364     unsigned long ret = 0;
 365     long n;
 366     unsigned long v;
 367     int r;
 368
 369     if (c == NULL || *c == '\0')
 370         return ret;
 371
 372     for (n = 0x100; *c != '\0'; n += 0x100) {
 373         v = n | ossl_tolower(*c);
 374         r = (int)((v >> 2) ^ v) & 0x0f;
 375         ret = (ret << r) | (ret >> (32 - r));
 376         ret &= 0xFFFFFFFFL;
 377         ret ^= v * v;
 378         c++;
 379     }
 380     return (ret >> 16) ^ ret;
 381 }
 382
 383 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
 384 {
 385     return lh ? lh->num_items : 0;
 386 }
 387
 388 unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
 389 {
 390     return lh->down_load;
 391 }
 392
 393 void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
 394 {
 395     lh->down_load = down_load;
 396 }
 397
 398 int OPENSSL_LH_error(OPENSSL_LHASH *lh)
 399 {
 400     return lh->error;
 401 }