contrib/bind9/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.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         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 #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, hctx->vectorlen,
 254                                              NULL, 0);
 255                 INSIST(result == ISC_R_SUCCESS);
 256 #else
 257                 INSIST(0);
 258 #endif
 259         } else {
 260                 isc_uint32_t pr;
 261                 unsigned int i, copylen;
 262                 unsigned char *p;
 263
 264                 p = (unsigned char *)hctx->rndvector;
 265                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 266                         isc_random_get(&pr);
 267                         if (i + sizeof(pr) <= hctx->vectorlen)
 268                                 copylen = sizeof(pr);
 269                         else
 270                                 copylen = hctx->vectorlen - i;
 271
 272                         memcpy(p, &pr, copylen);
 273                 }
 274                 INSIST(p == (unsigned char *)hctx->rndvector +
 275                        hctx->vectorlen);
 276         }
 277
 278         hctx->initialized = ISC_TRUE;
 279
 280  out:
 281         UNLOCK(&hctx->lock);
 282 }
 283
 284 void
 285 isc_hash_init() {
 286         INSIST(hash != NULL && VALID_HASH(hash));
 287
 288         isc_hash_ctxinit(hash);
 289 }
 290
 291 void
 292 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 293         REQUIRE(VALID_HASH(hctx));
 294         REQUIRE(hctxp != NULL && *hctxp == NULL);
 295
 296         isc_refcount_increment(&hctx->refcnt, NULL);
 297         *hctxp = hctx;
 298 }
 299
 300 static void
 301 destroy(isc_hash_t **hctxp) {
 302         isc_hash_t *hctx;
 303         isc_mem_t *mctx;
 304         unsigned char canary0[4], canary1[4];
 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         memcpy(canary0, hctx + 1, sizeof(canary0));
 327         memset(hctx, 0, sizeof(isc_hash_t));
 328         memcpy(canary1, hctx + 1, sizeof(canary1));
 329         INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0);
 330         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 331         isc_mem_detach(&mctx);
 332 }
 333
 334 void
 335 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 336         isc_hash_t *hctx;
 337         unsigned int refs;
 338
 339         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 340         hctx = *hctxp;
 341
 342         isc_refcount_decrement(&hctx->refcnt, &refs);
 343         if (refs == 0)
 344                 destroy(&hctx);
 345
 346         *hctxp = NULL;
 347 }
 348
 349 void
 350 isc_hash_destroy() {
 351         unsigned int refs;
 352
 353         INSIST(hash != NULL && VALID_HASH(hash));
 354
 355         isc_refcount_decrement(&hash->refcnt, &refs);
 356         INSIST(refs == 0);
 357
 358         destroy(&hash);
 359 }
 360
 361 static inline unsigned int
 362 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 363           isc_boolean_t case_sensitive)
 364 {
 365         hash_accum_t partial_sum = 0;
 366         hash_random_t *p = hctx->rndvector;
 367         unsigned int i = 0;
 368
 369         /* Make it sure that the hash context is initialized. */
 370         if (hctx->initialized == ISC_FALSE)
 371                 isc_hash_ctxinit(hctx);
 372
 373         if (case_sensitive) {
 374                 for (i = 0; i < keylen; i++)
 375                         partial_sum += key[i] * (hash_accum_t)p[i];
 376         } else {
 377                 for (i = 0; i < keylen; i++)
 378                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 379         }
 380
 381         partial_sum += p[i];
 382
 383         return ((unsigned int)(partial_sum % PRIME32));
 384 }
 385
 386 unsigned int
 387 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 388                  unsigned int keylen, isc_boolean_t case_sensitive)
 389 {
 390         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 391         REQUIRE(keylen <= hctx->limit);
 392
 393         return (hash_calc(hctx, key, keylen, case_sensitive));
 394 }
 395
 396 unsigned int
 397 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 398               isc_boolean_t case_sensitive)
 399 {
 400         INSIST(hash != NULL && VALID_HASH(hash));
 401         REQUIRE(keylen <= hash->limit);
 402
 403         return (hash_calc(hash, key, keylen, case_sensitive));
 404 }