hash.c revision 7a272c6b0de3b8c0ad018b9896e287da19c43bef
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews/*
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater * Copyright (C) 2004-2007, 2009 Internet Systems Consortium, Inc. ("ISC")
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Copyright (C) 2003 Internet Software Consortium.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * Permission to use, copy, modify, and/or distribute this software for any
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * purpose with or without fee is hereby granted, provided that the above
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * copyright notice and this permission notice appear in all copies.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater/* $Id: hash.c,v 1.15 2009/05/06 23:47:50 tbox Exp $ */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*! \file
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Some portion of this code was derived from universal hash function
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater * libraries of Rice University.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein\section license UH Universal Hashing Library
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsCopyright ((c)) 2002, Rice University
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsAll rights reserved.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsRedistribution and use in source and binary forms, with or without
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsmodification, are permitted provided that the following conditions are
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsmet:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Redistributions of source code must retain the above copyright
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews notice, this list of conditions and the following disclaimer.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Redistributions in binary form must reproduce the above
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copyright notice, this list of conditions and the following
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews disclaimer in the documentation and/or other materials provided
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews with the distribution.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Neither the name of Rice University (RICE) nor the names of its
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews contributors may be used to endorse or promote products derived
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews from this software without specific prior written permission.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsThis software is provided by RICE and the contributors on an "as is"
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsbasis, without any representations or warranties of any kind, express
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsor implied including, but not limited to, representations or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewswarranties of non-infringement, merchantability or fitness for a
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsparticular purpose. In no event shall RICE or contributors be liable
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsfor any direct, indirect, incidental, special, exemplary, or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsconsequential damages (including, but not limited to, procurement of
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewssubstitute goods or services; loss of use, data, or profits; or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsbusiness interruption) however caused and on any theory of liability,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewswhether in contract, strict liability, or tort (including negligence
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsor otherwise) arising in any way out of the use of this software, even
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsif advised of the possibility of such damage.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews*/
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a8f061d5c61bbdbe922cbb0adb70ae81770b52cbMark Andrews#include <config.h>
a8f061d5c61bbdbe922cbb0adb70ae81770b52cbMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/entropy.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/hash.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/mem.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/magic.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/mutex.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/once.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/random.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/refcount.h>
d19fc9d988171a1a7ff87d200b86c9aa657aa3beMark Andrews#include <isc/string.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/util.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h')
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*%
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * A large 32-bit prime number that specifies the range of the hash output.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define PRIME32 0xFFFFFFFB /* 2^32 - 5 */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*@{*/
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*%
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Types of random seed and hash accumulator. Perhaps they can be system
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * dependent.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewstypedef isc_uint32_t hash_accum_t;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewstypedef isc_uint16_t hash_random_t;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*@}*/
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*% isc hash structure */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstruct isc_hash {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int magic;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_t *mctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mutex_t lock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t initialized;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_t refcnt;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein isc_entropy_t *entropy; /*%< entropy source */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein unsigned int limit; /*%< upper limit of key length */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein size_t vectorlen; /*%< size of the vector below */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein hash_random_t *rndvector; /*%< random vector for universal hashing */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews};
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrewsstatic isc_mutex_t createlock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic isc_once_t once = ISC_ONCE_INIT;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic isc_hash_t *hash = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic unsigned char maptolower[] = {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews};
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_result_t
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int limit, isc_hash_t **hctxp)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews isc_result_t result;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews size_t vlen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_random_t *rv;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_accum_t overflow_limit;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(mctx != NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Overflow check. Since our implementation only does a modulo
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * operation at the last stage of hash calculation, the accumulator
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * must not overflow.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews overflow_limit =
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (overflow_limit < (limit + 1) * 0xff)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_RANGE);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx == NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_NOMEMORY);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews vlen = sizeof(hash_random_t) * (limit + 1);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews rv = isc_mem_get(mctx, vlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (rv == NULL) {
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = ISC_R_NOMEMORY;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto errout;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * We need a lock.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = isc_mutex_init(&hctx->lock);
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews if (result != ISC_R_SUCCESS)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto errout;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * From here down, no failures will/can occur.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->magic = HASH_MAGIC;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->mctx = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_attach(mctx, &hctx->mctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->initialized = ISC_FALSE;
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = isc_refcount_init(&hctx->refcnt, 1);
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews if (result != ISC_R_SUCCESS)
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews goto cleanup_lock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->entropy = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->limit = limit;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->vectorlen = vlen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->rndvector = rv;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (entropy != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_entropy_attach(entropy, &hctx->entropy);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews cleanup_lock:
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews DESTROYLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews errout:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (rv != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, rv, vlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews return (result);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic void
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsinitialize_lock(void) {
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_result_t
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_result_t result = ISC_R_SUCCESS;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(mctx != NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(hash == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews LOCK(&createlock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hash == NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews UNLOCK(&createlock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (result);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxinit(isc_hash_t *hctx) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_result_t result;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews LOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->initialized == ISC_TRUE)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto out;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->entropy) {
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater result = isc_entropy_getdata(hctx->entropy,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->rndvector, hctx->vectorlen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews NULL, 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(result == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews } else {
3f40de5598aaf9fa1aa90d6eb82350152bc66ec8Mark Andrews isc_uint32_t pr;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int i, copylen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned char *p;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews p = (unsigned char *)hctx->rndvector;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_random_get(&pr);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (i + sizeof(pr) <= hctx->vectorlen)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copylen = sizeof(pr);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews else
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copylen = hctx->vectorlen - i;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews memcpy(p, &pr, copylen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(p == (unsigned char *)hctx->rndvector +
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->vectorlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->initialized = ISC_TRUE;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews out:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews UNLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_init() {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(hash != NULL && VALID_HASH(hash));
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_ctxinit(hash);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(VALID_HASH(hctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_increment(&hctx->refcnt, NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic void
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsdestroy(isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_t *mctx;
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 unsigned char canary0[4], canary1[4];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp != NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = *hctxp;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews LOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_destroy(&hctx->refcnt);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews mctx = hctx->mctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->entropy != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_entropy_detach(&hctx->entropy);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->rndvector != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews UNLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews DESTROYLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 memcpy(canary0, hctx + 1, sizeof(canary0));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews memset(hctx, 0, sizeof(isc_hash_t));
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 memcpy(canary1, hctx + 1, sizeof(canary1));
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_detach(&mctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxdetach(isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = *hctxp;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_decrement(&hctx->refcnt, &refs);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (refs == 0)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews destroy(&hctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_destroy() {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(hash != NULL && VALID_HASH(hash));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_decrement(&hash->refcnt, &refs);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(refs == 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews destroy(&hash);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic inline unsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewshash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_accum_t partial_sum = 0;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_random_t *p = hctx->rndvector;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int i = 0;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /* Make it sure that the hash context is initialized. */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->initialized == ISC_FALSE)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_ctxinit(hctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (case_sensitive) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += key[i] * (hash_accum_t)p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews } else {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return ((unsigned int)(partial_sum % PRIME32));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsunsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int keylen, isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctx != NULL && VALID_HASH(hctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(keylen <= hctx->limit);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (hash_calc(hctx, key, keylen, case_sensitive));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsunsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_calc(const unsigned char *key, unsigned int keylen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(hash != NULL && VALID_HASH(hash));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(keylen <= hash->limit);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (hash_calc(hash, key, keylen, case_sensitive));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}