contrib/bind-9.2.4rc7/lib/isc/hash.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and 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.2.2.5 2004/03/09 06:11:46 marka Exp $ */
  19
  20 /*
  21  * Some portion of this code was derived from universal hash function
  22  * libraries of Rice University.
  23  */
  24
  25 /*  "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/rwlock.h>
  72 #include <isc/string.h>
  73 #include <isc/util.h>
  74
  75 #define HASH_MAGIC              ISC_MAGIC('H', 'a', 's', 'h')
  76 #define VALID_HASH(h)           ISC_MAGIC_VALID((h), HASH_MAGIC)
  77
  78 /*
  79  * A large 32-bit prime number that specifies the range of the hash output.
  80  */
  81 #define PRIME32 0xFFFFFFFB              /* 2^32 -  5 */
  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 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         unsigned int    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_rwlock_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                    unsigned int limit, isc_hash_t **hctxp)
 144 {
 145         isc_result_t ret;
 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                 ret = ISC_R_NOMEMORY;
 172                 goto errout;
 173         }
 174
 175         /*
 176          * We need a lock.
 177          */
 178         if (isc_mutex_init(&hctx->lock) != ISC_R_SUCCESS) {
 179                 ret = ISC_R_UNEXPECTED;
 180                 goto errout;
 181         }
 182
 183         /*
 184          * From here down, no failures will/can occur.
 185          */
 186         hctx->magic = HASH_MAGIC;
 187         hctx->mctx = NULL;
 188         isc_mem_attach(mctx, &hctx->mctx);
 189         hctx->initialized = ISC_FALSE;
 190         isc_refcount_init(&hctx->refcnt, 1);
 191         hctx->entropy = NULL;
 192         hctx->limit = limit;
 193         hctx->vectorlen = vlen;
 194         hctx->rndvector = rv;
 195
 196         if (entropy != NULL)
 197                 isc_entropy_attach(entropy, &hctx->entropy);
 198
 199         *hctxp = hctx;
 200         return (ISC_R_SUCCESS);
 201
 202  errout:
 203         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 204         if (rv != NULL)
 205                 isc_mem_put(mctx, rv, vlen);
 206
 207         return (ret);
 208 }
 209
 210 static void
 211 initialize_lock(void) {
 212         RUNTIME_CHECK(isc_rwlock_init(&createlock, 0, 0) == ISC_R_SUCCESS);
 213 }
 214
 215 isc_result_t
 216 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
 217         isc_result_t result = ISC_R_SUCCESS;
 218
 219         REQUIRE(mctx != NULL);
 220         INSIST(hash == NULL);
 221
 222         RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
 223
 224         RWLOCK(&createlock, isc_rwlocktype_write);
 225
 226         if (hash == NULL)
 227                 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
 228
 229         RWUNLOCK(&createlock, isc_rwlocktype_write);
 230
 231         return (result);
 232 }
 233
 234 void
 235 isc_hash_ctxinit(isc_hash_t *hctx) {
 236         isc_result_t result;
 237
 238         LOCK(&hctx->lock);
 239
 240         if (hctx->initialized == ISC_TRUE)
 241                 goto out;
 242
 243         if (hctx->entropy) {
 244                 result = isc_entropy_getdata(hctx->entropy,
 245                                              hctx->rndvector, hctx->vectorlen,
 246                                              NULL, 0);
 247                 INSIST(result == ISC_R_SUCCESS);
 248         } else {
 249                 isc_uint32_t pr;
 250                 unsigned int i, copylen;
 251                 unsigned char *p;
 252
 253                 p = (unsigned char *)hctx->rndvector;
 254                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 255                         isc_random_get(&pr);
 256                         if (i + sizeof(pr) <= hctx->vectorlen)
 257                                 copylen = sizeof(pr);
 258                         else
 259                                 copylen = hctx->vectorlen - i;
 260
 261                         memcpy(p, &pr, copylen);
 262                 }
 263                 INSIST(p == (unsigned char *)hctx->rndvector +
 264                        hctx->vectorlen);
 265         }
 266
 267         hctx->initialized = ISC_TRUE;
 268
 269  out:
 270         UNLOCK(&hctx->lock);
 271 }
 272
 273 void
 274 isc_hash_init() {
 275         INSIST(hash != NULL && VALID_HASH(hash));
 276
 277         isc_hash_ctxinit(hash);
 278 }
 279
 280 void
 281 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 282         REQUIRE(VALID_HASH(hctx));
 283         REQUIRE(hctxp != NULL && *hctxp == NULL);
 284
 285         isc_refcount_increment(&hctx->refcnt, NULL);
 286         *hctxp = hctx;
 287 }
 288
 289 static void
 290 destroy(isc_hash_t **hctxp) {
 291         isc_hash_t *hctx;
 292         isc_mem_t *mctx;
 293
 294         REQUIRE(hctxp != NULL && *hctxp != NULL);
 295         hctx = *hctxp;
 296         *hctxp = NULL;
 297
 298         LOCK(&hctx->lock);
 299
 300         isc_refcount_destroy(&hctx->refcnt);
 301
 302         mctx = hctx->mctx;
 303         if (hctx->entropy != NULL)
 304                 isc_entropy_detach(&hctx->entropy);
 305         if (hctx->rndvector != NULL)
 306                 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
 307
 308         UNLOCK(&hctx->lock);
 309
 310         DESTROYLOCK(&hctx->lock);
 311
 312         memset(hctx, 0, sizeof(isc_hash_t));
 313         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 314         isc_mem_detach(&mctx);
 315 }
 316
 317 void
 318 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 319         isc_hash_t *hctx;
 320         unsigned int refs;
 321
 322         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 323         hctx = *hctxp;
 324
 325         isc_refcount_decrement(&hctx->refcnt, &refs);
 326         if (refs == 0)
 327                 destroy(&hctx);
 328
 329         *hctxp = NULL;
 330 }
 331
 332 void
 333 isc_hash_destroy() {
 334         unsigned int refs;
 335
 336         INSIST(hash != NULL && VALID_HASH(hash));
 337
 338         isc_refcount_decrement(&hash->refcnt, &refs);
 339         INSIST(refs == 0);
 340
 341         destroy(&hash);
 342 }
 343
 344 static inline unsigned int
 345 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 346           isc_boolean_t case_sensitive)
 347 {
 348         hash_accum_t partial_sum = 0;
 349         hash_random_t *p = hctx->rndvector;
 350         unsigned int i = 0;
 351
 352         /* Make it sure that the hash context is initialized. */
 353         if (hctx->initialized == ISC_FALSE)
 354                 isc_hash_ctxinit(hctx);
 355
 356         if (case_sensitive) {
 357                 for (i = 0; i < keylen; i++)
 358                         partial_sum += key[i] * (hash_accum_t)p[i];
 359         } else {
 360                 for (i = 0; i < keylen; i++)
 361                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 362         }
 363
 364         partial_sum += p[i];
 365
 366         return ((unsigned int)(partial_sum % PRIME32));
 367 }
 368
 369 unsigned int
 370 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 371                  unsigned int keylen, isc_boolean_t case_sensitive)
 372 {
 373         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 374         REQUIRE(keylen <= hctx->limit);
 375
 376         return (hash_calc(hctx, key, keylen, case_sensitive));
 377 }
 378
 379 unsigned int
 380 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 381               isc_boolean_t case_sensitive)
 382 {
 383         INSIST(hash != NULL && VALID_HASH(hash));
 384         REQUIRE(keylen <= hash->limit);
 385
 386         return (hash_calc(hash, key, keylen, case_sensitive));
 387 }