contrib/bind9/lib/isc/hash.c

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