external/bsd/bind/dist/lib/isc/hash.c

   1 /*      $NetBSD$        */
   2
   3 /*
   4  * Copyright (C) 2004-2007, 2009  Internet Systems Consortium, Inc. ("ISC")
   5  * Copyright (C) 2003  Internet Software Consortium.
   6  *
   7  * Permission to use, copy, modify, and/or distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  12  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  13  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  14  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  15  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  16  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  17  * PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 /* Id: hash.c,v 1.16 2009/09/01 00:22:28 jinmei Exp */
  21
  22 /*! \file
  23  * Some portion of this code was derived from universal hash function
  24  * libraries of Rice University.
  25 \section license 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 /*%
  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
  91 /*% isc hash structure */
  92 struct isc_hash {
  93         unsigned int    magic;
  94         isc_mem_t       *mctx;
  95         isc_mutex_t     lock;
  96         isc_boolean_t   initialized;
  97         isc_refcount_t  refcnt;
  98         isc_entropy_t   *entropy; /*%< entropy source */
  99         unsigned int    limit;  /*%< upper limit of key length */
 100         size_t          vectorlen; /*%< size of the vector below */
 101         hash_random_t   *rndvector; /*%< random vector for universal hashing */
 102 };
 103
 104 static isc_mutex_t createlock;
 105 static isc_once_t once = ISC_ONCE_INIT;
 106 static isc_hash_t *hash = NULL;
 107
 108 static unsigned char maptolower[] = {
 109         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 110         0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 111         0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 112         0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 113         0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
 114         0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
 115         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
 116         0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
 117         0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 118         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 119         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 120         0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
 121         0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 122         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 123         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 124         0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
 125         0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 126         0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 127         0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 128         0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 129         0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 130         0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 131         0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 132         0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 133         0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 134         0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 135         0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 136         0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 137         0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 138         0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 139         0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 140         0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
 141 };
 142
 143 isc_result_t
 144 isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
 145                    unsigned int limit, isc_hash_t **hctxp)
 146 {
 147         isc_result_t result;
 148         isc_hash_t *hctx;
 149         size_t vlen;
 150         hash_random_t *rv;
 151         hash_accum_t overflow_limit;
 152
 153         REQUIRE(mctx != NULL);
 154         REQUIRE(hctxp != NULL && *hctxp == NULL);
 155
 156         /*
 157          * Overflow check.  Since our implementation only does a modulo
 158          * operation at the last stage of hash calculation, the accumulator
 159          * must not overflow.
 160          */
 161         overflow_limit =
 162                 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
 163         if (overflow_limit < (limit + 1) * 0xff)
 164                 return (ISC_R_RANGE);
 165
 166         hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
 167         if (hctx == NULL)
 168                 return (ISC_R_NOMEMORY);
 169
 170         vlen = sizeof(hash_random_t) * (limit + 1);
 171         rv = isc_mem_get(mctx, vlen);
 172         if (rv == NULL) {
 173                 result = ISC_R_NOMEMORY;
 174                 goto errout;
 175         }
 176
 177         /*
 178          * We need a lock.
 179          */
 180         result = isc_mutex_init(&hctx->lock);
 181         if (result != ISC_R_SUCCESS)
 182                 goto errout;
 183
 184         /*
 185          * From here down, no failures will/can occur.
 186          */
 187         hctx->magic = HASH_MAGIC;
 188         hctx->mctx = NULL;
 189         isc_mem_attach(mctx, &hctx->mctx);
 190         hctx->initialized = ISC_FALSE;
 191         result = isc_refcount_init(&hctx->refcnt, 1);
 192         if (result != ISC_R_SUCCESS)
 193                 goto cleanup_lock;
 194         hctx->entropy = NULL;
 195         hctx->limit = limit;
 196         hctx->vectorlen = vlen;
 197         hctx->rndvector = rv;
 198
 199 #ifdef BIND9
 200         if (entropy != NULL)
 201                 isc_entropy_attach(entropy, &hctx->entropy);
 202 #else
 203         UNUSED(entropy);
 204 #endif
 205
 206         *hctxp = hctx;
 207         return (ISC_R_SUCCESS);
 208
 209  cleanup_lock:
 210         DESTROYLOCK(&hctx->lock);
 211  errout:
 212         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 213         if (rv != NULL)
 214                 isc_mem_put(mctx, rv, vlen);
 215
 216         return (result);
 217 }
 218
 219 static void
 220 initialize_lock(void) {
 221         RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
 222 }
 223
 224 isc_result_t
 225 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
 226         isc_result_t result = ISC_R_SUCCESS;
 227
 228         REQUIRE(mctx != NULL);
 229         INSIST(hash == NULL);
 230
 231         RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
 232
 233         LOCK(&createlock);
 234
 235         if (hash == NULL)
 236                 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
 237
 238         UNLOCK(&createlock);
 239
 240         return (result);
 241 }
 242
 243 void
 244 isc_hash_ctxinit(isc_hash_t *hctx) {
 245         LOCK(&hctx->lock);
 246
 247         if (hctx->initialized == ISC_TRUE)
 248                 goto out;
 249
 250         if (hctx->entropy) {
 251 #ifdef BIND9
 252                 isc_result_t result;
 253
 254                 result = isc_entropy_getdata(hctx->entropy,
 255                                              hctx->rndvector, hctx->vectorlen,
 256                                              NULL, 0);
 257                 INSIST(result == ISC_R_SUCCESS);
 258 #else
 259                 INSIST(0);
 260 #endif
 261         } else {
 262                 isc_uint32_t pr;
 263                 unsigned int i, copylen;
 264                 unsigned char *p;
 265
 266                 p = (unsigned char *)hctx->rndvector;
 267                 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
 268                         isc_random_get(&pr);
 269                         if (i + sizeof(pr) <= hctx->vectorlen)
 270                                 copylen = sizeof(pr);
 271                         else
 272                                 copylen = hctx->vectorlen - i;
 273
 274                         memcpy(p, &pr, copylen);
 275                 }
 276                 INSIST(p == (unsigned char *)hctx->rndvector +
 277                        hctx->vectorlen);
 278         }
 279
 280         hctx->initialized = ISC_TRUE;
 281
 282  out:
 283         UNLOCK(&hctx->lock);
 284 }
 285
 286 void
 287 isc_hash_init() {
 288         INSIST(hash != NULL && VALID_HASH(hash));
 289
 290         isc_hash_ctxinit(hash);
 291 }
 292
 293 void
 294 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
 295         REQUIRE(VALID_HASH(hctx));
 296         REQUIRE(hctxp != NULL && *hctxp == NULL);
 297
 298         isc_refcount_increment(&hctx->refcnt, NULL);
 299         *hctxp = hctx;
 300 }
 301
 302 static void
 303 destroy(isc_hash_t **hctxp) {
 304         isc_hash_t *hctx;
 305         isc_mem_t *mctx;
 306         unsigned char canary0[4], canary1[4];
 307
 308         REQUIRE(hctxp != NULL && *hctxp != NULL);
 309         hctx = *hctxp;
 310         *hctxp = NULL;
 311
 312         LOCK(&hctx->lock);
 313
 314         isc_refcount_destroy(&hctx->refcnt);
 315
 316         mctx = hctx->mctx;
 317 #ifdef BIND9
 318         if (hctx->entropy != NULL)
 319                 isc_entropy_detach(&hctx->entropy);
 320 #endif
 321         if (hctx->rndvector != NULL)
 322                 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
 323
 324         UNLOCK(&hctx->lock);
 325
 326         DESTROYLOCK(&hctx->lock);
 327
 328         memcpy(canary0, hctx + 1, sizeof(canary0));
 329         memset(hctx, 0, sizeof(isc_hash_t));
 330         memcpy(canary1, hctx + 1, sizeof(canary1));
 331         INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0);
 332         isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
 333         isc_mem_detach(&mctx);
 334 }
 335
 336 void
 337 isc_hash_ctxdetach(isc_hash_t **hctxp) {
 338         isc_hash_t *hctx;
 339         unsigned int refs;
 340
 341         REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
 342         hctx = *hctxp;
 343
 344         isc_refcount_decrement(&hctx->refcnt, &refs);
 345         if (refs == 0)
 346                 destroy(&hctx);
 347
 348         *hctxp = NULL;
 349 }
 350
 351 void
 352 isc_hash_destroy() {
 353         unsigned int refs;
 354
 355         INSIST(hash != NULL && VALID_HASH(hash));
 356
 357         isc_refcount_decrement(&hash->refcnt, &refs);
 358         INSIST(refs == 0);
 359
 360         destroy(&hash);
 361 }
 362
 363 static inline unsigned int
 364 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
 365           isc_boolean_t case_sensitive)
 366 {
 367         hash_accum_t partial_sum = 0;
 368         hash_random_t *p = hctx->rndvector;
 369         unsigned int i = 0;
 370
 371         /* Make it sure that the hash context is initialized. */
 372         if (hctx->initialized == ISC_FALSE)
 373                 isc_hash_ctxinit(hctx);
 374
 375         if (case_sensitive) {
 376                 for (i = 0; i < keylen; i++)
 377                         partial_sum += key[i] * (hash_accum_t)p[i];
 378         } else {
 379                 for (i = 0; i < keylen; i++)
 380                         partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
 381         }
 382
 383         partial_sum += p[i];
 384
 385         return ((unsigned int)(partial_sum % PRIME32));
 386 }
 387
 388 unsigned int
 389 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
 390                  unsigned int keylen, isc_boolean_t case_sensitive)
 391 {
 392         REQUIRE(hctx != NULL && VALID_HASH(hctx));
 393         REQUIRE(keylen <= hctx->limit);
 394
 395         return (hash_calc(hctx, key, keylen, case_sensitive));
 396 }
 397
 398 unsigned int
 399 isc_hash_calc(const unsigned char *key, unsigned int keylen,
 400               isc_boolean_t case_sensitive)
 401 {
 402         INSIST(hash != NULL && VALID_HASH(hash));
 403         REQUIRE(keylen <= hash->limit);
 404
 405         return (hash_calc(hash, key, keylen, case_sensitive));
 406 }