contrib/bind9/lib/isc/hash.c

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