external/bsd/bind/dist/lib/isc/hash.c

   1 /*      $NetBSD: hash.c,v 1.9 2015/07/08 17:28:59 christos Exp $        */
   2
   3 /*
   4  * Copyright (C) 2004-2007, 2009, 2013-2015  Internet Systems Consortium, Inc. ("ISC")
   5  * Copyright (C) 2003  Internet Software Consortium.
   6  *
   7  * Permission to use, copy, modify, and/or distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  12  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  13  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  14  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  15  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  16  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  17  * PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 /* Id: hash.c,v 1.16 2009/09/01 00:22:28 jinmei Exp  */
  21
  22 /*! \file
  23  * Some portion of this code was derived from universal hash function
  24  * libraries of Rice University.
  25 \section license UH Universal Hashing Library
  26
  27 Copyright ((c)) 2002, Rice University
  28 All rights reserved.
  29
  30 Redistribution and use in source and binary forms, with or without
  31 modification, are permitted provided that the following conditions are
  32 met:
  33
  34     * Redistributions of source code must retain the above copyright
  35     notice, this list of conditions and the following disclaimer.
  36
  37     * Redistributions in binary form must reproduce the above
  38     copyright notice, this list of conditions and the following
  39     disclaimer in the documentation and/or other materials provided
  40     with the distribution.
  41
  42     * Neither the name of Rice University (RICE) nor the names of its
  43     contributors may be used to endorse or promote products derived
  44     from this software without specific prior written permission.
  45
  46
  47 This software is provided by RICE and the contributors on an "as is"
  48 basis, without any representations or warranties of any kind, express
  49 or implied including, but not limited to, representations or
  50 warranties of non-infringement, merchantability or fitness for a
  51 particular purpose. In no event shall RICE or contributors be liable
  52 for any direct, indirect, incidental, special, exemplary, or
  53 consequential damages (including, but not limited to, procurement of
  54 substitute goods or services; loss of use, data, or profits; or
  55 business interruption) however caused and on any theory of liability,
  56 whether in contract, strict liability, or tort (including negligence
  57 or otherwise) arising in any way out of the use of this software, even
  58 if advised of the possibility of such damage.
  59 */
  60
  61 #include <config.h>
  62
  63 #include <isc/entropy.h>
  64 #include <isc/hash.h>
  65 #include <isc/mem.h>
  66 #include <isc/magic.h>
  67 #include <isc/mutex.h>
  68 #include <isc/once.h>
  69 #include <isc/random.h>
  70 #include <isc/refcount.h>
  71 #include <isc/string.h>
  72 #include <isc/util.h>
  73
  74 #define HASH_MAGIC              ISC_MAGIC('H', 'a', 's', 'h')
  75 #define VALID_HASH(h)           ISC_MAGIC_VALID((h), HASH_MAGIC)
  76
  77 /*%
  78  * A large 32-bit prime number that specifies the range of the hash output.
  79  */
  80 #define PRIME32 0xFFFFFFFB              /* 2^32 -  5 */
  81
  82 /*@{*/
  83 /*%
  84  * Types of random seed and hash accumulator.  Perhaps they can be system
  85  * dependent.
  86  */
  87 typedef isc_uint32_t hash_accum_t;
  88 typedef isc_uint16_t hash_random_t;
  89 /*@}*/
  90
  91 /*% isc hash structure */
  92 struct isc_hash {
  93         unsigned int    magic;
  94         isc_mem_t       *mctx;
  95         isc_mutex_t     lock;
  96         isc_boolean_t   initialized;
  97         isc_refcount_t  refcnt;
  98         isc_entropy_t   *entropy; /*%< entropy source */
  99         size_t          limit;  /*%< upper limit of key length */
 100         size_t          vectorlen; /*%< size of the vector below */
 101         hash_random_t   *rndvector; /*%< random vector for universal hashing */
 102 };
 103
 104 static isc_mutex_t createlock;
 105 static isc_once_t once = ISC_ONCE_INIT;
 106 static isc_hash_t *hash = NULL;
 107
 108 static unsigned char maptolower[] = {
 109         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 110         0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 111         0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 112         0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 113         0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
 114         0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
 115         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
 116         0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
 117         0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 118         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 119         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 120         0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
 121         0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 122         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 123         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 124         0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
 125         0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 126         0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 127         0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 128         0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 129         0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 130         0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 131         0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 132         0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 133         0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 134         0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 135         0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 136         0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 137         0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 138         0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 139         0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 140         0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
 141 };
 142
 143 isc_result_t
 144 isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
 145                    size_t limit, isc_hash_t **hctxp)
 146 {
 147         isc_result_t result;
 148         isc_hash_t *hctx;
 149         size_t vlen;
 150         hash_random_t *rv;
 151         hash_accum_t overflow_limit;
 152
 153         REQUIRE(mctx != NULL);
 154         REQUIRE(hctxp != NULL && *hctxp == NULL);
 155
 156         /*
 157          * Overflow check.  Since our implementation only does a modulo
 158          * operation at the last stage of hash calculation, the accumulator
 159          * must not overflow.
 160          */
 161         overflow_limit =
 162                 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
 163         if (overflow_limit < (limit + 1) * 0xff)
 164                 return (ISC_R_RANGE);
 165
 166         hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
 167         if (hctx == NULL)
 168                 return (ISC_R_NOMEMORY);
 169
 170         vlen = sizeof(hash_random_t) * (limit + 1);
 171         rv = isc_mem_get(mctx, vlen);
 172         if (rv == NULL) {
 173                 result = ISC_R_NOMEMORY;
 174                 goto errout;
 175         }
 176
 177         /*
 178          * We need a lock.
 179          */
 180         result = isc_mutex_init(&hctx->lock);
 181         if (result != ISC_R_SUCCESS)
 182                 goto errout;
 183
 184         /*
 185          * From here down, no failures will/can occur.
 186          */
 187         hctx->magic = HASH_MAGIC;
 188         hctx->mctx = NULL;
 189         isc_mem_attach(mctx, &hctx->mctx);
 190         hctx->initialized = ISC_FALSE;
 191         result = isc_refcount_init(&hctx->refcnt, 1);
 192         if (result != ISC_R_SUCCESS)
 193                 goto cleanup_lock;
 194         hctx->entropy = NULL;
 195         hctx->limit = limit;
 196         hctx->vectorlen = vlen;
 197         hctx->rndvector = rv;
 198
 199         if (entropy != NULL)
 200                 isc_entropy_attach(entropy, &hctx->entropy);
 201
 202         *hctxp = hctx;
 203         return (ISC_R_SUCCESS);
 204
 205  cleanup_lock:
 206         DESTROYLOCK(&hctx->lock);
 207  errout:
 208         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 209         if (rv != NULL)
 210                 isc_mem_put(mctx, rv, vlen);
 211
 212         return (result);
 213 }
 214
 215 static void
 216 initialize_lock(void) {
 217         RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
 218 }
 219
 220 isc_result_t
 221 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
 222         isc_result_t result = ISC_R_SUCCESS;
 223
 224         REQUIRE(mctx != NULL);
 225         INSIST(hash == NULL);
 226
 227         RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
 228
 229         LOCK(&createlock);
 230
 231         if (hash == NULL)
 232                 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
 233
 234         UNLOCK(&createlock);
 235
 236         return (result);
 237 }
 238
 239 void
 240 isc_hash_ctxinit(isc_hash_t *hctx) {
 241         LOCK(&hctx->lock);
 242
 243         if (hctx->initialized == ISC_TRUE)
 244                 goto out;
 245
 246         if (hctx->entropy != NULL) {
 247                 isc_result_t result;
 248
 249                 result = isc_entropy_getdata(hctx->entropy,
 250                                              hctx->rndvector,
 251                                              (unsigned int)hctx->vectorlen,
 252                                              NULL, 0);
 253                 INSIST(result == ISC_R_SUCCESS);
 254         } else {
 255                 isc_uint32_t pr;
 256                 size_t i, copylen;
 257                 unsigned char *p;
 258
 259                 p = (unsigned char *)hctx->rndvector;
 260                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 261                         isc_random_get(&pr);
 262                         if (i + sizeof(pr) <= hctx->vectorlen)
 263                                 copylen = sizeof(pr);
 264                         else
 265                                 copylen = hctx->vectorlen - i;
 266
 267                         memmove(p, &pr, copylen);
 268                 }
 269                 INSIST(p == (unsigned char *)hctx->rndvector +
 270                        hctx->vectorlen);
 271         }
 272
 273         hctx->initialized = ISC_TRUE;
 274
 275  out:
 276         UNLOCK(&hctx->lock);
 277 }
 278
 279 void
 280 isc_hash_init(void) {
 281         INSIST(hash != NULL && VALID_HASH(hash));
 282
 283         isc_hash_ctxinit(hash);
 284 }
 285
 286 void
 287 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 288         REQUIRE(VALID_HASH(hctx));
 289         REQUIRE(hctxp != NULL && *hctxp == NULL);
 290
 291         isc_refcount_increment(&hctx->refcnt, NULL);
 292         *hctxp = hctx;
 293 }
 294
 295 static void
 296 destroy(isc_hash_t **hctxp) {
 297         isc_hash_t *hctx;
 298         isc_mem_t *mctx;
 299
 300         REQUIRE(hctxp != NULL && *hctxp != NULL);
 301         hctx = *hctxp;
 302         *hctxp = NULL;
 303
 304         LOCK(&hctx->lock);
 305
 306         isc_refcount_destroy(&hctx->refcnt);
 307
 308         mctx = hctx->mctx;
 309         if (hctx->entropy != NULL)
 310                 isc_entropy_detach(&hctx->entropy);
 311         if (hctx->rndvector != NULL)
 312                 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
 313
 314         UNLOCK(&hctx->lock);
 315
 316         DESTROYLOCK(&hctx->lock);
 317
 318         memset(hctx, 0, sizeof(isc_hash_t));
 319         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 320         isc_mem_detach(&mctx);
 321 }
 322
 323 void
 324 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 325         isc_hash_t *hctx;
 326         unsigned int refs;
 327
 328         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 329         hctx = *hctxp;
 330
 331         isc_refcount_decrement(&hctx->refcnt, &refs);
 332         if (refs == 0)
 333                 destroy(&hctx);
 334
 335         *hctxp = NULL;
 336 }
 337
 338 void
 339 isc_hash_destroy(void) {
 340         unsigned int refs;
 341
 342         INSIST(hash != NULL && VALID_HASH(hash));
 343
 344         isc_refcount_decrement(&hash->refcnt, &refs);
 345         INSIST(refs == 0);
 346
 347         destroy(&hash);
 348 }
 349
 350 static inline unsigned int
 351 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 352           isc_boolean_t case_sensitive)
 353 {
 354         hash_accum_t partial_sum = 0;
 355         hash_random_t *p = hctx->rndvector;
 356         unsigned int i = 0;
 357
 358         /* Make it sure that the hash context is initialized. */
 359         if (hctx->initialized == ISC_FALSE)
 360                 isc_hash_ctxinit(hctx);
 361
 362         if (case_sensitive) {
 363                 for (i = 0; i < keylen; i++)
 364                         partial_sum += key[i] * (hash_accum_t)p[i];
 365         } else {
 366                 for (i = 0; i < keylen; i++)
 367                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 368         }
 369
 370         partial_sum += p[i];
 371
 372         return ((unsigned int)(partial_sum % PRIME32));
 373 }
 374
 375 unsigned int
 376 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 377                  unsigned int keylen, isc_boolean_t case_sensitive)
 378 {
 379         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 380         REQUIRE(keylen <= hctx->limit);
 381
 382         return (hash_calc(hctx, key, keylen, case_sensitive));
 383 }
 384
 385 unsigned int
 386 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 387               isc_boolean_t case_sensitive)
 388 {
 389         INSIST(hash != NULL && VALID_HASH(hash));
 390         REQUIRE(keylen <= hash->limit);
 391
 392         return (hash_calc(hash, key, keylen, case_sensitive));
 393 }
 394
 395 void
 396 isc__hash_setvec(const isc_uint16_t *vec) {
 397         int i;
 398         hash_random_t *p;
 399
 400         if (hash == NULL)
 401                 return;
 402
 403         p = hash->rndvector;
 404         for (i = 0; i < 256; i++) {
 405                 p[i] = vec[i];
 406         }
 407 }