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