contrib/bind-9.3/lib/isc/hash.c

   1 /*
   2  * Copyright (C) 2004, 2006  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.4.2.3 2006/01/04 00:37:22 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/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  * Types of random seed and hash accumulator.  Perhaps they can be system
  84  * dependent.
  85  */
  86 typedef isc_uint32_t hash_accum_t;
  87 typedef isc_uint16_t hash_random_t;
  88
  89 struct isc_hash {
  90         unsigned int    magic;
  91         isc_mem_t       *mctx;
  92         isc_mutex_t     lock;
  93         isc_boolean_t   initialized;
  94         isc_refcount_t  refcnt;
  95         isc_entropy_t   *entropy; /* entropy source */
  96         unsigned int    limit;  /* upper limit of key length */
  97         size_t          vectorlen; /* size of the vector below */
  98         hash_random_t   *rndvector; /* random vector for universal hashing */
  99 };
 100
 101 static isc_mutex_t createlock;
 102 static isc_once_t once = ISC_ONCE_INIT;
 103 static isc_hash_t *hash = NULL;
 104
 105 static unsigned char maptolower[] = {
 106         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 107         0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 108         0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 109         0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 110         0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
 111         0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
 112         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
 113         0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
 114         0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 115         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 116         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 117         0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
 118         0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 119         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 120         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 121         0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
 122         0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 123         0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 124         0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 125         0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 126         0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 127         0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 128         0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 129         0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 130         0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 131         0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 132         0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 133         0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 134         0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 135         0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 136         0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 137         0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
 138 };
 139
 140 isc_result_t
 141 isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
 142                    unsigned int limit, isc_hash_t **hctxp)
 143 {
 144         isc_result_t ret;
 145         isc_hash_t *hctx;
 146         size_t vlen;
 147         hash_random_t *rv;
 148         hash_accum_t overflow_limit;
 149
 150         REQUIRE(mctx != NULL);
 151         REQUIRE(hctxp != NULL && *hctxp == NULL);
 152
 153         /*
 154          * Overflow check.  Since our implementation only does a modulo
 155          * operation at the last stage of hash calculation, the accumulator
 156          * must not overflow.
 157          */
 158         overflow_limit =
 159                 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
 160         if (overflow_limit < (limit + 1) * 0xff)
 161                 return (ISC_R_RANGE);
 162
 163         hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
 164         if (hctx == NULL)
 165                 return (ISC_R_NOMEMORY);
 166
 167         vlen = sizeof(hash_random_t) * (limit + 1);
 168         rv = isc_mem_get(mctx, vlen);
 169         if (rv == NULL) {
 170                 ret = ISC_R_NOMEMORY;
 171                 goto errout;
 172         }
 173
 174         /*
 175          * We need a lock.
 176          */
 177         if (isc_mutex_init(&hctx->lock) != ISC_R_SUCCESS) {
 178                 ret = ISC_R_UNEXPECTED;
 179                 goto errout;
 180         }
 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         isc_refcount_init(&hctx->refcnt, 1);
 190         hctx->entropy = NULL;
 191         hctx->limit = limit;
 192         hctx->vectorlen = vlen;
 193         hctx->rndvector = rv;
 194
 195         if (entropy != NULL)
 196                 isc_entropy_attach(entropy, &hctx->entropy);
 197
 198         *hctxp = hctx;
 199         return (ISC_R_SUCCESS);
 200
 201  errout:
 202         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 203         if (rv != NULL)
 204                 isc_mem_put(mctx, rv, vlen);
 205
 206         return (ret);
 207 }
 208
 209 static void
 210 initialize_lock(void) {
 211         RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
 212 }
 213
 214 isc_result_t
 215 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
 216         isc_result_t result = ISC_R_SUCCESS;
 217
 218         REQUIRE(mctx != NULL);
 219         INSIST(hash == NULL);
 220
 221         RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
 222
 223         LOCK(&createlock);
 224
 225         if (hash == NULL)
 226                 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
 227
 228         UNLOCK(&createlock);
 229
 230         return (result);
 231 }
 232
 233 void
 234 isc_hash_ctxinit(isc_hash_t *hctx) {
 235         isc_result_t result;
 236
 237         LOCK(&hctx->lock);
 238
 239         if (hctx->initialized == ISC_TRUE)
 240                 goto out;
 241
 242         if (hctx->entropy) {
 243                 result = isc_entropy_getdata(hctx->entropy,
 244                                              hctx->rndvector, hctx->vectorlen,
 245                                              NULL, 0);
 246                 INSIST(result == ISC_R_SUCCESS);
 247         } else {
 248                 isc_uint32_t pr;
 249                 unsigned int i, copylen;
 250                 unsigned char *p;
 251
 252                 p = (unsigned char *)hctx->rndvector;
 253                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 254                         isc_random_get(&pr);
 255                         if (i + sizeof(pr) <= hctx->vectorlen)
 256                                 copylen = sizeof(pr);
 257                         else
 258                                 copylen = hctx->vectorlen - i;
 259
 260                         memcpy(p, &pr, copylen);
 261                 }
 262                 INSIST(p == (unsigned char *)hctx->rndvector +
 263                        hctx->vectorlen);
 264         }
 265
 266         hctx->initialized = ISC_TRUE;
 267
 268  out:
 269         UNLOCK(&hctx->lock);
 270 }
 271
 272 void
 273 isc_hash_init() {
 274         INSIST(hash != NULL && VALID_HASH(hash));
 275
 276         isc_hash_ctxinit(hash);
 277 }
 278
 279 void
 280 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 281         REQUIRE(VALID_HASH(hctx));
 282         REQUIRE(hctxp != NULL && *hctxp == NULL);
 283
 284         isc_refcount_increment(&hctx->refcnt, NULL);
 285         *hctxp = hctx;
 286 }
 287
 288 static void
 289 destroy(isc_hash_t **hctxp) {
 290         isc_hash_t *hctx;
 291         isc_mem_t *mctx;
 292
 293         REQUIRE(hctxp != NULL && *hctxp != NULL);
 294         hctx = *hctxp;
 295         *hctxp = NULL;
 296
 297         LOCK(&hctx->lock);
 298
 299         isc_refcount_destroy(&hctx->refcnt);
 300
 301         mctx = hctx->mctx;
 302         if (hctx->entropy != NULL)
 303                 isc_entropy_detach(&hctx->entropy);
 304         if (hctx->rndvector != NULL)
 305                 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
 306
 307         UNLOCK(&hctx->lock);
 308
 309         DESTROYLOCK(&hctx->lock);
 310
 311         memset(hctx, 0, sizeof(isc_hash_t));
 312         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 313         isc_mem_detach(&mctx);
 314 }
 315
 316 void
 317 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 318         isc_hash_t *hctx;
 319         unsigned int refs;
 320
 321         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 322         hctx = *hctxp;
 323
 324         isc_refcount_decrement(&hctx->refcnt, &refs);
 325         if (refs == 0)
 326                 destroy(&hctx);
 327
 328         *hctxp = NULL;
 329 }
 330
 331 void
 332 isc_hash_destroy() {
 333         unsigned int refs;
 334
 335         INSIST(hash != NULL && VALID_HASH(hash));
 336
 337         isc_refcount_decrement(&hash->refcnt, &refs);
 338         INSIST(refs == 0);
 339
 340         destroy(&hash);
 341 }
 342
 343 static inline unsigned int
 344 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 345           isc_boolean_t case_sensitive)
 346 {
 347         hash_accum_t partial_sum = 0;
 348         hash_random_t *p = hctx->rndvector;
 349         unsigned int i = 0;
 350
 351         /* Make it sure that the hash context is initialized. */
 352         if (hctx->initialized == ISC_FALSE)
 353                 isc_hash_ctxinit(hctx);
 354
 355         if (case_sensitive) {
 356                 for (i = 0; i < keylen; i++)
 357                         partial_sum += key[i] * (hash_accum_t)p[i];
 358         } else {
 359                 for (i = 0; i < keylen; i++)
 360                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 361         }
 362
 363         partial_sum += p[i];
 364
 365         return ((unsigned int)(partial_sum % PRIME32));
 366 }
 367
 368 unsigned int
 369 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 370                  unsigned int keylen, isc_boolean_t case_sensitive)
 371 {
 372         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 373         REQUIRE(keylen <= hctx->limit);
 374
 375         return (hash_calc(hctx, key, keylen, case_sensitive));
 376 }
 377
 378 unsigned int
 379 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 380               isc_boolean_t case_sensitive)
 381 {
 382         INSIST(hash != NULL && VALID_HASH(hash));
 383         REQUIRE(keylen <= hash->limit);
 384
 385         return (hash_calc(hash, key, keylen, case_sensitive));
 386 }