hash.c revision 258945
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 18258945Sroberto/* $Id: hash.c,v 1.13.332.3 2009/05/07 23:47:12 tbox 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 197258945Sroberto if (entropy != NULL) 198258945Sroberto isc_entropy_attach(entropy, &hctx->entropy); 199258945Sroberto 200258945Sroberto *hctxp = hctx; 201258945Sroberto return (ISC_R_SUCCESS); 202258945Sroberto 203258945Sroberto cleanup_lock: 204258945Sroberto DESTROYLOCK(&hctx->lock); 205258945Sroberto errout: 206258945Sroberto isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 207258945Sroberto if (rv != NULL) 208258945Sroberto isc_mem_put(mctx, rv, vlen); 209258945Sroberto 210258945Sroberto return (result); 211258945Sroberto} 212258945Sroberto 213258945Srobertostatic void 214258945Srobertoinitialize_lock(void) { 215258945Sroberto RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS); 216258945Sroberto} 217258945Sroberto 218258945Srobertoisc_result_t 219258945Srobertoisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) { 220258945Sroberto isc_result_t result = ISC_R_SUCCESS; 221258945Sroberto 222258945Sroberto REQUIRE(mctx != NULL); 223258945Sroberto INSIST(hash == NULL); 224258945Sroberto 225258945Sroberto RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS); 226258945Sroberto 227258945Sroberto LOCK(&createlock); 228258945Sroberto 229258945Sroberto if (hash == NULL) 230258945Sroberto result = isc_hash_ctxcreate(mctx, entropy, limit, &hash); 231258945Sroberto 232258945Sroberto UNLOCK(&createlock); 233258945Sroberto 234258945Sroberto return (result); 235258945Sroberto} 236258945Sroberto 237258945Srobertovoid 238258945Srobertoisc_hash_ctxinit(isc_hash_t *hctx) { 239258945Sroberto isc_result_t result; 240258945Sroberto 241258945Sroberto LOCK(&hctx->lock); 242258945Sroberto 243258945Sroberto if (hctx->initialized == ISC_TRUE) 244258945Sroberto goto out; 245258945Sroberto 246258945Sroberto if (hctx->entropy) { 247258945Sroberto result = isc_entropy_getdata(hctx->entropy, 248258945Sroberto hctx->rndvector, hctx->vectorlen, 249258945Sroberto NULL, 0); 250258945Sroberto INSIST(result == ISC_R_SUCCESS); 251258945Sroberto } else { 252258945Sroberto isc_uint32_t pr; 253258945Sroberto unsigned int i, copylen; 254258945Sroberto unsigned char *p; 255258945Sroberto 256258945Sroberto p = (unsigned char *)hctx->rndvector; 257258945Sroberto for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) { 258258945Sroberto isc_random_get(&pr); 259258945Sroberto if (i + sizeof(pr) <= hctx->vectorlen) 260258945Sroberto copylen = sizeof(pr); 261258945Sroberto else 262258945Sroberto copylen = hctx->vectorlen - i; 263258945Sroberto 264258945Sroberto memcpy(p, &pr, copylen); 265258945Sroberto } 266258945Sroberto INSIST(p == (unsigned char *)hctx->rndvector + 267258945Sroberto hctx->vectorlen); 268258945Sroberto } 269258945Sroberto 270258945Sroberto hctx->initialized = ISC_TRUE; 271258945Sroberto 272258945Sroberto out: 273258945Sroberto UNLOCK(&hctx->lock); 274258945Sroberto} 275258945Sroberto 276258945Srobertovoid 277258945Srobertoisc_hash_init() { 278258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 279258945Sroberto 280258945Sroberto isc_hash_ctxinit(hash); 281258945Sroberto} 282258945Sroberto 283258945Srobertovoid 284258945Srobertoisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) { 285258945Sroberto REQUIRE(VALID_HASH(hctx)); 286258945Sroberto REQUIRE(hctxp != NULL && *hctxp == NULL); 287258945Sroberto 288258945Sroberto isc_refcount_increment(&hctx->refcnt, NULL); 289258945Sroberto *hctxp = hctx; 290258945Sroberto} 291258945Sroberto 292258945Srobertostatic void 293258945Srobertodestroy(isc_hash_t **hctxp) { 294258945Sroberto isc_hash_t *hctx; 295258945Sroberto isc_mem_t *mctx; 296258945Sroberto 297258945Sroberto REQUIRE(hctxp != NULL && *hctxp != NULL); 298258945Sroberto hctx = *hctxp; 299258945Sroberto *hctxp = NULL; 300258945Sroberto 301258945Sroberto LOCK(&hctx->lock); 302258945Sroberto 303258945Sroberto isc_refcount_destroy(&hctx->refcnt); 304258945Sroberto 305258945Sroberto mctx = hctx->mctx; 306258945Sroberto if (hctx->entropy != NULL) 307258945Sroberto isc_entropy_detach(&hctx->entropy); 308258945Sroberto if (hctx->rndvector != NULL) 309258945Sroberto isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen); 310258945Sroberto 311258945Sroberto UNLOCK(&hctx->lock); 312258945Sroberto 313258945Sroberto DESTROYLOCK(&hctx->lock); 314258945Sroberto 315258945Sroberto memset(hctx, 0, sizeof(isc_hash_t)); 316258945Sroberto isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 317258945Sroberto isc_mem_detach(&mctx); 318258945Sroberto} 319258945Sroberto 320258945Srobertovoid 321258945Srobertoisc_hash_ctxdetach(isc_hash_t **hctxp) { 322258945Sroberto isc_hash_t *hctx; 323258945Sroberto unsigned int refs; 324258945Sroberto 325258945Sroberto REQUIRE(hctxp != NULL && VALID_HASH(*hctxp)); 326258945Sroberto hctx = *hctxp; 327258945Sroberto 328258945Sroberto isc_refcount_decrement(&hctx->refcnt, &refs); 329258945Sroberto if (refs == 0) 330258945Sroberto destroy(&hctx); 331258945Sroberto 332258945Sroberto *hctxp = NULL; 333258945Sroberto} 334258945Sroberto 335258945Srobertovoid 336258945Srobertoisc_hash_destroy() { 337258945Sroberto unsigned int refs; 338258945Sroberto 339258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 340258945Sroberto 341258945Sroberto isc_refcount_decrement(&hash->refcnt, &refs); 342258945Sroberto INSIST(refs == 0); 343258945Sroberto 344258945Sroberto destroy(&hash); 345258945Sroberto} 346258945Sroberto 347258945Srobertostatic inline unsigned int 348258945Srobertohash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen, 349258945Sroberto isc_boolean_t case_sensitive) 350258945Sroberto{ 351258945Sroberto hash_accum_t partial_sum = 0; 352258945Sroberto hash_random_t *p = hctx->rndvector; 353258945Sroberto unsigned int i = 0; 354258945Sroberto 355258945Sroberto /* Make it sure that the hash context is initialized. */ 356258945Sroberto if (hctx->initialized == ISC_FALSE) 357258945Sroberto isc_hash_ctxinit(hctx); 358258945Sroberto 359258945Sroberto if (case_sensitive) { 360258945Sroberto for (i = 0; i < keylen; i++) 361258945Sroberto partial_sum += key[i] * (hash_accum_t)p[i]; 362258945Sroberto } else { 363258945Sroberto for (i = 0; i < keylen; i++) 364258945Sroberto partial_sum += maptolower[key[i]] * (hash_accum_t)p[i]; 365258945Sroberto } 366258945Sroberto 367258945Sroberto partial_sum += p[i]; 368258945Sroberto 369258945Sroberto return ((unsigned int)(partial_sum % PRIME32)); 370258945Sroberto} 371258945Sroberto 372258945Srobertounsigned int 373258945Srobertoisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key, 374258945Sroberto unsigned int keylen, isc_boolean_t case_sensitive) 375258945Sroberto{ 376258945Sroberto REQUIRE(hctx != NULL && VALID_HASH(hctx)); 377258945Sroberto REQUIRE(keylen <= hctx->limit); 378258945Sroberto 379258945Sroberto return (hash_calc(hctx, key, keylen, case_sensitive)); 380258945Sroberto} 381258945Sroberto 382258945Srobertounsigned int 383258945Srobertoisc_hash_calc(const unsigned char *key, unsigned int keylen, 384258945Sroberto isc_boolean_t case_sensitive) 385258945Sroberto{ 386258945Sroberto INSIST(hash != NULL && VALID_HASH(hash)); 387258945Sroberto REQUIRE(keylen <= hash->limit); 388258945Sroberto 389258945Sroberto return (hash_calc(hash, key, keylen, case_sensitive)); 390258945Sroberto} 391