1258945Sroberto/* 2258945Sroberto * Copyright (C) 2004-2007, 2009 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * Copyright (C) 2003 Internet Software Consortium. 4258945Sroberto * 5258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 6258945Sroberto * purpose with or without fee is hereby granted, provided that the above 7258945Sroberto * copyright notice and this permission notice appear in all copies. 8258945Sroberto * 9258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 16258945Sroberto */ 17258945Sroberto 18280849Scy/* $Id: hash.c,v 1.16 2009/09/01 00:22:28 jinmei Exp $ */ 19258945Sroberto 20258945Sroberto/*! \file 21258945Sroberto * Some portion of this code was derived from universal hash function 22258945Sroberto * libraries of Rice University. 23258945Sroberto\section license UH Universal Hashing Library 24258945Sroberto 25258945SrobertoCopyright ((c)) 2002, Rice University 26258945SrobertoAll rights reserved. 27258945Sroberto 28258945SrobertoRedistribution and use in source and binary forms, with or without 29258945Srobertomodification, are permitted provided that the following conditions are 30258945Srobertomet: 31258945Sroberto 32258945Sroberto * Redistributions of source code must retain the above copyright 33258945Sroberto notice, this list of conditions and the following disclaimer. 34258945Sroberto 35258945Sroberto * Redistributions in binary form must reproduce the above 36258945Sroberto copyright notice, this list of conditions and the following 37258945Sroberto disclaimer in the documentation and/or other materials provided 38258945Sroberto with the distribution. 39258945Sroberto 40258945Sroberto * Neither the name of Rice University (RICE) nor the names of its 41258945Sroberto contributors may be used to endorse or promote products derived 42258945Sroberto from this software without specific prior written permission. 43258945Sroberto 44258945Sroberto 45258945SrobertoThis software is provided by RICE and the contributors on an "as is" 46258945Srobertobasis, without any representations or warranties of any kind, express 47258945Srobertoor implied including, but not limited to, representations or 48258945Srobertowarranties of non-infringement, merchantability or fitness for a 49258945Srobertoparticular purpose. In no event shall RICE or contributors be liable 50258945Srobertofor any direct, indirect, incidental, special, exemplary, or 51258945Srobertoconsequential damages (including, but not limited to, procurement of 52258945Srobertosubstitute goods or services; loss of use, data, or profits; or 53258945Srobertobusiness interruption) however caused and on any theory of liability, 54258945Srobertowhether in contract, strict liability, or tort (including negligence 55258945Srobertoor otherwise) arising in any way out of the use of this software, even 56258945Srobertoif advised of the possibility of such damage. 57258945Sroberto*/ 58258945Sroberto 59258945Sroberto#include <config.h> 60258945Sroberto 61258945Sroberto#include <isc/entropy.h> 62258945Sroberto#include <isc/hash.h> 63258945Sroberto#include <isc/mem.h> 64258945Sroberto#include <isc/magic.h> 65258945Sroberto#include <isc/mutex.h> 66258945Sroberto#include <isc/once.h> 67258945Sroberto#include <isc/random.h> 68258945Sroberto#include <isc/refcount.h> 69258945Sroberto#include <isc/string.h> 70258945Sroberto#include <isc/util.h> 71258945Sroberto 72258945Sroberto#define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h') 73258945Sroberto#define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC) 74258945Sroberto 75258945Sroberto/*% 76258945Sroberto * A large 32-bit prime number that specifies the range of the hash output. 77258945Sroberto */ 78258945Sroberto#define PRIME32 0xFFFFFFFB /* 2^32 - 5 */ 79258945Sroberto 80258945Sroberto/*@{*/ 81258945Sroberto/*% 82258945Sroberto * Types of random seed and hash accumulator. Perhaps they can be system 83258945Sroberto * dependent. 84258945Sroberto */ 85258945Srobertotypedef isc_uint32_t hash_accum_t; 86258945Srobertotypedef isc_uint16_t hash_random_t; 87258945Sroberto/*@}*/ 88258945Sroberto 89258945Sroberto/*% isc hash structure */ 90258945Srobertostruct isc_hash { 91258945Sroberto unsigned int magic; 92258945Sroberto isc_mem_t *mctx; 93258945Sroberto isc_mutex_t lock; 94258945Sroberto isc_boolean_t initialized; 95258945Sroberto isc_refcount_t refcnt; 96258945Sroberto isc_entropy_t *entropy; /*%< entropy source */ 97258945Sroberto unsigned int limit; /*%< upper limit of key length */ 98258945Sroberto size_t vectorlen; /*%< size of the vector below */ 99258945Sroberto hash_random_t *rndvector; /*%< random vector for universal hashing */ 100258945Sroberto}; 101258945Sroberto 102258945Srobertostatic isc_mutex_t createlock; 103258945Srobertostatic isc_once_t once = ISC_ONCE_INIT; 104258945Srobertostatic isc_hash_t *hash = NULL; 105258945Sroberto 106258945Srobertostatic unsigned char maptolower[] = { 107258945Sroberto 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 108258945Sroberto 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 109258945Sroberto 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 110258945Sroberto 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 111258945Sroberto 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 112258945Sroberto 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 113258945Sroberto 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 114258945Sroberto 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 115258945Sroberto 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 116258945Sroberto 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 117258945Sroberto 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 118258945Sroberto 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 119258945Sroberto 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 120258945Sroberto 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 121258945Sroberto 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 122258945Sroberto 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 123258945Sroberto 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 124258945Sroberto 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 125258945Sroberto 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 126258945Sroberto 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 127258945Sroberto 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 128258945Sroberto 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 129258945Sroberto 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 130258945Sroberto 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 131258945Sroberto 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 132258945Sroberto 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 133258945Sroberto 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 134258945Sroberto 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 135258945Sroberto 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 136258945Sroberto 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 137258945Sroberto 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 138258945Sroberto 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff 139258945Sroberto}; 140258945Sroberto 141258945Srobertoisc_result_t 142258945Srobertoisc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy, 143258945Sroberto unsigned int limit, isc_hash_t **hctxp) 144258945Sroberto{ 145258945Sroberto isc_result_t result; 146258945Sroberto isc_hash_t *hctx; 147258945Sroberto size_t vlen; 148258945Sroberto hash_random_t *rv; 149258945Sroberto hash_accum_t overflow_limit; 150258945Sroberto 151258945Sroberto REQUIRE(mctx != NULL); 152258945Sroberto REQUIRE(hctxp != NULL && *hctxp == NULL); 153258945Sroberto 154258945Sroberto /* 155258945Sroberto * Overflow check. Since our implementation only does a modulo 156258945Sroberto * operation at the last stage of hash calculation, the accumulator 157258945Sroberto * must not overflow. 158258945Sroberto */ 159258945Sroberto overflow_limit = 160258945Sroberto 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8); 161258945Sroberto if (overflow_limit < (limit + 1) * 0xff) 162258945Sroberto return (ISC_R_RANGE); 163258945Sroberto 164258945Sroberto hctx = isc_mem_get(mctx, sizeof(isc_hash_t)); 165258945Sroberto if (hctx == NULL) 166258945Sroberto return (ISC_R_NOMEMORY); 167258945Sroberto 168258945Sroberto vlen = sizeof(hash_random_t) * (limit + 1); 169258945Sroberto rv = isc_mem_get(mctx, vlen); 170258945Sroberto if (rv == NULL) { 171258945Sroberto result = ISC_R_NOMEMORY; 172258945Sroberto goto errout; 173258945Sroberto } 174258945Sroberto 175258945Sroberto /* 176258945Sroberto * We need a lock. 177258945Sroberto */ 178258945Sroberto result = isc_mutex_init(&hctx->lock); 179258945Sroberto if (result != ISC_R_SUCCESS) 180258945Sroberto goto errout; 181258945Sroberto 182258945Sroberto /* 183258945Sroberto * From here down, no failures will/can occur. 184258945Sroberto */ 185258945Sroberto hctx->magic = HASH_MAGIC; 186258945Sroberto hctx->mctx = NULL; 187258945Sroberto isc_mem_attach(mctx, &hctx->mctx); 188258945Sroberto hctx->initialized = ISC_FALSE; 189258945Sroberto result = isc_refcount_init(&hctx->refcnt, 1); 190258945Sroberto if (result != ISC_R_SUCCESS) 191258945Sroberto goto cleanup_lock; 192258945Sroberto hctx->entropy = NULL; 193258945Sroberto hctx->limit = limit; 194258945Sroberto hctx->vectorlen = vlen; 195258945Sroberto hctx->rndvector = rv; 196258945Sroberto 197280849Scy#ifdef BIND9 198258945Sroberto if (entropy != NULL) 199258945Sroberto isc_entropy_attach(entropy, &hctx->entropy); 200280849Scy#else 201280849Scy UNUSED(entropy); 202280849Scy#endif 203258945Sroberto 204258945Sroberto *hctxp = hctx; 205258945Sroberto return (ISC_R_SUCCESS); 206258945Sroberto 207258945Sroberto cleanup_lock: 208258945Sroberto DESTROYLOCK(&hctx->lock); 209258945Sroberto errout: 210258945Sroberto isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 211258945Sroberto if (rv != NULL) 212258945Sroberto isc_mem_put(mctx, rv, vlen); 213258945Sroberto 214258945Sroberto return (result); 215258945Sroberto} 216258945Sroberto 217258945Srobertostatic void 218258945Srobertoinitialize_lock(void) { 219258945Sroberto RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS); 220258945Sroberto} 221258945Sroberto 222258945Srobertoisc_result_t 223258945Srobertoisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) { 224258945Sroberto isc_result_t result = ISC_R_SUCCESS; 225258945Sroberto 226258945Sroberto REQUIRE(mctx != NULL); 227258945Sroberto INSIST(hash == NULL); 228258945Sroberto 229258945Sroberto RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS); 230258945Sroberto 231258945Sroberto LOCK(&createlock); 232258945Sroberto 233258945Sroberto if (hash == NULL) 234258945Sroberto result = isc_hash_ctxcreate(mctx, entropy, limit, &hash); 235258945Sroberto 236258945Sroberto UNLOCK(&createlock); 237258945Sroberto 238258945Sroberto return (result); 239258945Sroberto} 240258945Sroberto 241258945Srobertovoid 242258945Srobertoisc_hash_ctxinit(isc_hash_t *hctx) { 243258945Sroberto LOCK(&hctx->lock); 244258945Sroberto 245258945Sroberto if (hctx->initialized == ISC_TRUE) 246258945Sroberto goto out; 247258945Sroberto 248258945Sroberto if (hctx->entropy) { 249280849Scy#ifdef BIND9 250280849Scy isc_result_t result; 251280849Scy 252258945Sroberto result = isc_entropy_getdata(hctx->entropy, 253258945Sroberto hctx->rndvector, hctx->vectorlen, 254258945Sroberto NULL, 0); 255258945Sroberto INSIST(result == ISC_R_SUCCESS); 256280849Scy#else 257280849Scy INSIST(0); 258280849Scy#endif 259258945Sroberto } else { 260258945Sroberto isc_uint32_t pr; 261258945Sroberto unsigned int i, copylen; 262258945Sroberto unsigned char *p; 263258945Sroberto 264258945Sroberto p = (unsigned char *)hctx->rndvector; 265258945Sroberto for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) { 266258945Sroberto isc_random_get(&pr); 267258945Sroberto if (i + sizeof(pr) <= hctx->vectorlen) 268258945Sroberto copylen = sizeof(pr); 269258945Sroberto else 270258945Sroberto copylen = hctx->vectorlen - i; 271258945Sroberto 272258945Sroberto memcpy(p, &pr, copylen); 273258945Sroberto } 274258945Sroberto INSIST(p == (unsigned char *)hctx->rndvector + 275258945Sroberto hctx->vectorlen); 276258945Sroberto } 277258945Sroberto 278258945Sroberto hctx->initialized = ISC_TRUE; 279258945Sroberto 280258945Sroberto out: 281258945Sroberto UNLOCK(&hctx->lock); 282258945Sroberto} 283258945Sroberto 284258945Srobertovoid 285258945Srobertoisc_hash_init() { 286258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 287258945Sroberto 288258945Sroberto isc_hash_ctxinit(hash); 289258945Sroberto} 290258945Sroberto 291258945Srobertovoid 292258945Srobertoisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) { 293258945Sroberto REQUIRE(VALID_HASH(hctx)); 294258945Sroberto REQUIRE(hctxp != NULL && *hctxp == NULL); 295258945Sroberto 296258945Sroberto isc_refcount_increment(&hctx->refcnt, NULL); 297258945Sroberto *hctxp = hctx; 298258945Sroberto} 299258945Sroberto 300258945Srobertostatic void 301258945Srobertodestroy(isc_hash_t **hctxp) { 302258945Sroberto isc_hash_t *hctx; 303258945Sroberto isc_mem_t *mctx; 304280849Scy unsigned char canary0[4], canary1[4]; 305258945Sroberto 306258945Sroberto REQUIRE(hctxp != NULL && *hctxp != NULL); 307258945Sroberto hctx = *hctxp; 308258945Sroberto *hctxp = NULL; 309258945Sroberto 310258945Sroberto LOCK(&hctx->lock); 311258945Sroberto 312258945Sroberto isc_refcount_destroy(&hctx->refcnt); 313258945Sroberto 314258945Sroberto mctx = hctx->mctx; 315280849Scy#ifdef BIND9 316258945Sroberto if (hctx->entropy != NULL) 317258945Sroberto isc_entropy_detach(&hctx->entropy); 318280849Scy#endif 319258945Sroberto if (hctx->rndvector != NULL) 320258945Sroberto isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen); 321258945Sroberto 322258945Sroberto UNLOCK(&hctx->lock); 323258945Sroberto 324258945Sroberto DESTROYLOCK(&hctx->lock); 325258945Sroberto 326280849Scy memcpy(canary0, hctx + 1, sizeof(canary0)); 327258945Sroberto memset(hctx, 0, sizeof(isc_hash_t)); 328280849Scy memcpy(canary1, hctx + 1, sizeof(canary1)); 329280849Scy INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0); 330258945Sroberto isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 331258945Sroberto isc_mem_detach(&mctx); 332258945Sroberto} 333258945Sroberto 334258945Srobertovoid 335258945Srobertoisc_hash_ctxdetach(isc_hash_t **hctxp) { 336258945Sroberto isc_hash_t *hctx; 337258945Sroberto unsigned int refs; 338258945Sroberto 339258945Sroberto REQUIRE(hctxp != NULL && VALID_HASH(*hctxp)); 340258945Sroberto hctx = *hctxp; 341258945Sroberto 342258945Sroberto isc_refcount_decrement(&hctx->refcnt, &refs); 343258945Sroberto if (refs == 0) 344258945Sroberto destroy(&hctx); 345258945Sroberto 346258945Sroberto *hctxp = NULL; 347258945Sroberto} 348258945Sroberto 349258945Srobertovoid 350258945Srobertoisc_hash_destroy() { 351258945Sroberto unsigned int refs; 352258945Sroberto 353258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 354258945Sroberto 355258945Sroberto isc_refcount_decrement(&hash->refcnt, &refs); 356258945Sroberto INSIST(refs == 0); 357258945Sroberto 358258945Sroberto destroy(&hash); 359258945Sroberto} 360258945Sroberto 361258945Srobertostatic inline unsigned int 362258945Srobertohash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen, 363258945Sroberto isc_boolean_t case_sensitive) 364258945Sroberto{ 365258945Sroberto hash_accum_t partial_sum = 0; 366258945Sroberto hash_random_t *p = hctx->rndvector; 367258945Sroberto unsigned int i = 0; 368258945Sroberto 369258945Sroberto /* Make it sure that the hash context is initialized. */ 370258945Sroberto if (hctx->initialized == ISC_FALSE) 371258945Sroberto isc_hash_ctxinit(hctx); 372258945Sroberto 373258945Sroberto if (case_sensitive) { 374258945Sroberto for (i = 0; i < keylen; i++) 375258945Sroberto partial_sum += key[i] * (hash_accum_t)p[i]; 376258945Sroberto } else { 377258945Sroberto for (i = 0; i < keylen; i++) 378258945Sroberto partial_sum += maptolower[key[i]] * (hash_accum_t)p[i]; 379258945Sroberto } 380258945Sroberto 381258945Sroberto partial_sum += p[i]; 382258945Sroberto 383258945Sroberto return ((unsigned int)(partial_sum % PRIME32)); 384258945Sroberto} 385258945Sroberto 386258945Srobertounsigned int 387258945Srobertoisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key, 388258945Sroberto unsigned int keylen, isc_boolean_t case_sensitive) 389258945Sroberto{ 390258945Sroberto REQUIRE(hctx != NULL && VALID_HASH(hctx)); 391258945Sroberto REQUIRE(keylen <= hctx->limit); 392258945Sroberto 393258945Sroberto return (hash_calc(hctx, key, keylen, case_sensitive)); 394258945Sroberto} 395258945Sroberto 396258945Srobertounsigned int 397258945Srobertoisc_hash_calc(const unsigned char *key, unsigned int keylen, 398258945Sroberto isc_boolean_t case_sensitive) 399258945Sroberto{ 400258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 401258945Sroberto REQUIRE(keylen <= hash->limit); 402258945Sroberto 403258945Sroberto return (hash_calc(hash, key, keylen, case_sensitive)); 404258945Sroberto} 405