1/*
2 * Copyright (C) 2004-2007, 2009  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.13.332.3 2009/05/07 23:47:12 tbox 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
25Copyright ((c)) 2002, Rice University
26All rights reserved.
27
28Redistribution and use in source and binary forms, with or without
29modification, are permitted provided that the following conditions are
30met:
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
45This software is provided by RICE and the contributors on an "as is"
46basis, without any representations or warranties of any kind, express
47or implied including, but not limited to, representations or
48warranties of non-infringement, merchantability or fitness for a
49particular purpose. In no event shall RICE or contributors be liable
50for any direct, indirect, incidental, special, exemplary, or
51consequential damages (including, but not limited to, procurement of
52substitute goods or services; loss of use, data, or profits; or
53business interruption) however caused and on any theory of liability,
54whether in contract, strict liability, or tort (including negligence
55or otherwise) arising in any way out of the use of this software, even
56if 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 */
85typedef isc_uint32_t hash_accum_t;
86typedef isc_uint16_t hash_random_t;
87/*@}*/
88
89/*% isc hash structure */
90struct 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	unsigned int	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
102static isc_mutex_t createlock;
103static isc_once_t once = ISC_ONCE_INIT;
104static isc_hash_t *hash = NULL;
105
106static 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
141isc_result_t
142isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
143		   unsigned int 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	if (entropy != NULL)
198		isc_entropy_attach(entropy, &hctx->entropy);
199
200	*hctxp = hctx;
201	return (ISC_R_SUCCESS);
202
203 cleanup_lock:
204	DESTROYLOCK(&hctx->lock);
205 errout:
206	isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
207	if (rv != NULL)
208		isc_mem_put(mctx, rv, vlen);
209
210	return (result);
211}
212
213static void
214initialize_lock(void) {
215	RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
216}
217
218isc_result_t
219isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
220	isc_result_t result = ISC_R_SUCCESS;
221
222	REQUIRE(mctx != NULL);
223	INSIST(hash == NULL);
224
225	RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
226
227	LOCK(&createlock);
228
229	if (hash == NULL)
230		result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
231
232	UNLOCK(&createlock);
233
234	return (result);
235}
236
237void
238isc_hash_ctxinit(isc_hash_t *hctx) {
239	isc_result_t result;
240
241	LOCK(&hctx->lock);
242
243	if (hctx->initialized == ISC_TRUE)
244		goto out;
245
246	if (hctx->entropy) {
247		result = isc_entropy_getdata(hctx->entropy,
248					     hctx->rndvector, hctx->vectorlen,
249					     NULL, 0);
250		INSIST(result == ISC_R_SUCCESS);
251	} else {
252		isc_uint32_t pr;
253		unsigned int i, copylen;
254		unsigned char *p;
255
256		p = (unsigned char *)hctx->rndvector;
257		for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
258			isc_random_get(&pr);
259			if (i + sizeof(pr) <= hctx->vectorlen)
260				copylen = sizeof(pr);
261			else
262				copylen = hctx->vectorlen - i;
263
264			memcpy(p, &pr, copylen);
265		}
266		INSIST(p == (unsigned char *)hctx->rndvector +
267		       hctx->vectorlen);
268	}
269
270	hctx->initialized = ISC_TRUE;
271
272 out:
273	UNLOCK(&hctx->lock);
274}
275
276void
277isc_hash_init() {
278	INSIST(hash != NULL && VALID_HASH(hash));
279
280	isc_hash_ctxinit(hash);
281}
282
283void
284isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
285	REQUIRE(VALID_HASH(hctx));
286	REQUIRE(hctxp != NULL && *hctxp == NULL);
287
288	isc_refcount_increment(&hctx->refcnt, NULL);
289	*hctxp = hctx;
290}
291
292static void
293destroy(isc_hash_t **hctxp) {
294	isc_hash_t *hctx;
295	isc_mem_t *mctx;
296
297	REQUIRE(hctxp != NULL && *hctxp != NULL);
298	hctx = *hctxp;
299	*hctxp = NULL;
300
301	LOCK(&hctx->lock);
302
303	isc_refcount_destroy(&hctx->refcnt);
304
305	mctx = hctx->mctx;
306	if (hctx->entropy != NULL)
307		isc_entropy_detach(&hctx->entropy);
308	if (hctx->rndvector != NULL)
309		isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
310
311	UNLOCK(&hctx->lock);
312
313	DESTROYLOCK(&hctx->lock);
314
315	memset(hctx, 0, sizeof(isc_hash_t));
316	isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
317	isc_mem_detach(&mctx);
318}
319
320void
321isc_hash_ctxdetach(isc_hash_t **hctxp) {
322	isc_hash_t *hctx;
323	unsigned int refs;
324
325	REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
326	hctx = *hctxp;
327
328	isc_refcount_decrement(&hctx->refcnt, &refs);
329	if (refs == 0)
330		destroy(&hctx);
331
332	*hctxp = NULL;
333}
334
335void
336isc_hash_destroy() {
337	unsigned int refs;
338
339	INSIST(hash != NULL && VALID_HASH(hash));
340
341	isc_refcount_decrement(&hash->refcnt, &refs);
342	INSIST(refs == 0);
343
344	destroy(&hash);
345}
346
347static inline unsigned int
348hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
349	  isc_boolean_t case_sensitive)
350{
351	hash_accum_t partial_sum = 0;
352	hash_random_t *p = hctx->rndvector;
353	unsigned int i = 0;
354
355	/* Make it sure that the hash context is initialized. */
356	if (hctx->initialized == ISC_FALSE)
357		isc_hash_ctxinit(hctx);
358
359	if (case_sensitive) {
360		for (i = 0; i < keylen; i++)
361			partial_sum += key[i] * (hash_accum_t)p[i];
362	} else {
363		for (i = 0; i < keylen; i++)
364			partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
365	}
366
367	partial_sum += p[i];
368
369	return ((unsigned int)(partial_sum % PRIME32));
370}
371
372unsigned int
373isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
374		 unsigned int keylen, isc_boolean_t case_sensitive)
375{
376	REQUIRE(hctx != NULL && VALID_HASH(hctx));
377	REQUIRE(keylen <= hctx->limit);
378
379	return (hash_calc(hctx, key, keylen, case_sensitive));
380}
381
382unsigned int
383isc_hash_calc(const unsigned char *key, unsigned int keylen,
384	      isc_boolean_t case_sensitive)
385{
386	INSIST(hash != NULL && VALID_HASH(hash));
387	REQUIRE(keylen <= hash->limit);
388
389	return (hash_calc(hash, key, keylen, case_sensitive));
390}
391