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