contrib/bind/lib/isc/hash.c

   1 /*
   2  * Copyright (C) 2004-2007, 2009  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.13.128.3 2009/05/07 23:46:32 tbox 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         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_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                    unsigned int 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         if (entropy != NULL)
 198                 isc_entropy_attach(entropy, &hctx->entropy);
 199
 200         *hctxp = hctx;
 201         return (ISC_R_SUCCESS);
 202
 203  cleanup_lock:
 204         DESTROYLOCK(&hctx->lock);
 205  errout:
 206         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 207         if (rv != NULL)
 208                 isc_mem_put(mctx, rv, vlen);
 209
 210         return (result);
 211 }
 212
 213 static void
 214 initialize_lock(void) {
 215         RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
 216 }
 217
 218 isc_result_t
 219 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
 220         isc_result_t result = ISC_R_SUCCESS;
 221
 222         REQUIRE(mctx != NULL);
 223         INSIST(hash == NULL);
 224
 225         RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
 226
 227         LOCK(&createlock);
 228
 229         if (hash == NULL)
 230                 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
 231
 232         UNLOCK(&createlock);
 233
 234         return (result);
 235 }
 236
 237 void
 238 isc_hash_ctxinit(isc_hash_t *hctx) {
 239         isc_result_t result;
 240
 241         LOCK(&hctx->lock);
 242
 243         if (hctx->initialized == ISC_TRUE)
 244                 goto out;
 245
 246         if (hctx->entropy) {
 247                 result = isc_entropy_getdata(hctx->entropy,
 248                                              hctx->rndvector, hctx->vectorlen,
 249                                              NULL, 0);
 250                 INSIST(result == ISC_R_SUCCESS);
 251         } else {
 252                 isc_uint32_t pr;
 253                 unsigned int i, copylen;
 254                 unsigned char *p;
 255
 256                 p = (unsigned char *)hctx->rndvector;
 257                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 258                         isc_random_get(&pr);
 259                         if (i + sizeof(pr) <= hctx->vectorlen)
 260                                 copylen = sizeof(pr);
 261                         else
 262                                 copylen = hctx->vectorlen - i;
 263
 264                         memcpy(p, &pr, copylen);
 265                 }
 266                 INSIST(p == (unsigned char *)hctx->rndvector +
 267                        hctx->vectorlen);
 268         }
 269
 270         hctx->initialized = ISC_TRUE;
 271
 272  out:
 273         UNLOCK(&hctx->lock);
 274 }
 275
 276 void
 277 isc_hash_init() {
 278         INSIST(hash != NULL && VALID_HASH(hash));
 279
 280         isc_hash_ctxinit(hash);
 281 }
 282
 283 void
 284 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 285         REQUIRE(VALID_HASH(hctx));
 286         REQUIRE(hctxp != NULL && *hctxp == NULL);
 287
 288         isc_refcount_increment(&hctx->refcnt, NULL);
 289         *hctxp = hctx;
 290 }
 291
 292 static void
 293 destroy(isc_hash_t **hctxp) {
 294         isc_hash_t *hctx;
 295         isc_mem_t *mctx;
 296
 297         REQUIRE(hctxp != NULL && *hctxp != NULL);
 298         hctx = *hctxp;
 299         *hctxp = NULL;
 300
 301         LOCK(&hctx->lock);
 302
 303         isc_refcount_destroy(&hctx->refcnt);
 304
 305         mctx = hctx->mctx;
 306         if (hctx->entropy != NULL)
 307                 isc_entropy_detach(&hctx->entropy);
 308         if (hctx->rndvector != NULL)
 309                 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
 310
 311         UNLOCK(&hctx->lock);
 312
 313         DESTROYLOCK(&hctx->lock);
 314
 315         memset(hctx, 0, sizeof(isc_hash_t));
 316         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 317         isc_mem_detach(&mctx);
 318 }
 319
 320 void
 321 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 322         isc_hash_t *hctx;
 323         unsigned int refs;
 324
 325         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 326         hctx = *hctxp;
 327
 328         isc_refcount_decrement(&hctx->refcnt, &refs);
 329         if (refs == 0)
 330                 destroy(&hctx);
 331
 332         *hctxp = NULL;
 333 }
 334
 335 void
 336 isc_hash_destroy() {
 337         unsigned int refs;
 338
 339         INSIST(hash != NULL && VALID_HASH(hash));
 340
 341         isc_refcount_decrement(&hash->refcnt, &refs);
 342         INSIST(refs == 0);
 343
 344         destroy(&hash);
 345 }
 346
 347 static inline unsigned int
 348 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 349           isc_boolean_t case_sensitive)
 350 {
 351         hash_accum_t partial_sum = 0;
 352         hash_random_t *p = hctx->rndvector;
 353         unsigned int i = 0;
 354
 355         /* Make it sure that the hash context is initialized. */
 356         if (hctx->initialized == ISC_FALSE)
 357                 isc_hash_ctxinit(hctx);
 358
 359         if (case_sensitive) {
 360                 for (i = 0; i < keylen; i++)
 361                         partial_sum += key[i] * (hash_accum_t)p[i];
 362         } else {
 363                 for (i = 0; i < keylen; i++)
 364                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 365         }
 366
 367         partial_sum += p[i];
 368
 369         return ((unsigned int)(partial_sum % PRIME32));
 370 }
 371
 372 unsigned int
 373 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 374                  unsigned int keylen, isc_boolean_t case_sensitive)
 375 {
 376         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 377         REQUIRE(keylen <= hctx->limit);
 378
 379         return (hash_calc(hctx, key, keylen, case_sensitive));
 380 }
 381
 382 unsigned int
 383 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 384               isc_boolean_t case_sensitive)
 385 {
 386         INSIST(hash != NULL && VALID_HASH(hash));
 387         REQUIRE(keylen <= hash->limit);
 388
 389         return (hash_calc(hash, key, keylen, case_sensitive));
 390 }