diff options
Diffstat (limited to 'usr.sbin/bind')
| -rw-r--r-- | usr.sbin/bind/lib/isc/hash.c | 387 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/include/isc/hash.h | 175 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/unix/include/isc/stat.h | 53 |
3 files changed, 615 insertions, 0 deletions
diff --git a/usr.sbin/bind/lib/isc/hash.c b/usr.sbin/bind/lib/isc/hash.c new file mode 100644 index 00000000000..897af1d3c4a --- /dev/null +++ b/usr.sbin/bind/lib/isc/hash.c @@ -0,0 +1,387 @@ +/* + * Copyright (C) 2003 Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM + * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL + * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING + * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* $ISC: hash.c,v 1.2.2.4 2003/07/30 01:15:18 marka Exp $ */ + +/* + * Some portion of this code was derived from universal hash function + * libraries of Rice University. + */ + +/* "UH Universal Hashing Library" + +Copyright ((c)) 2002, Rice University +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + + * Neither the name of Rice University (RICE) nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + +This software is provided by RICE and the contributors on an "as is" +basis, without any representations or warranties of any kind, express +or implied including, but not limited to, representations or +warranties of non-infringement, merchantability or fitness for a +particular purpose. In no event shall RICE or contributors be liable +for any direct, indirect, incidental, special, exemplary, or +consequential damages (including, but not limited to, procurement of +substitute goods or services; loss of use, data, or profits; or +business interruption) however caused and on any theory of liability, +whether in contract, strict liability, or tort (including negligence +or otherwise) arising in any way out of the use of this software, even +if advised of the possibility of such damage. +*/ + +#include <config.h> + +#include <isc/entropy.h> +#include <isc/hash.h> +#include <isc/mem.h> +#include <isc/magic.h> +#include <isc/mutex.h> +#include <isc/once.h> +#include <isc/random.h> +#include <isc/refcount.h> +#include <isc/rwlock.h> +#include <isc/string.h> +#include <isc/util.h> + +#define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h') +#define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC) + +/* + * A large 32-bit prime number that specifies the range of the hash output. + */ +#define PRIME32 0xFFFFFFFB /* 2^32 - 5 */ + +/* + * Types of random seed and hash accumulator. Perhaps they can be system + * dependent. + */ +typedef isc_uint32_t hash_accum_t; +typedef isc_uint16_t hash_random_t; + +struct isc_hash { + unsigned int magic; + isc_mem_t *mctx; + isc_mutex_t lock; + isc_boolean_t initialized; + isc_refcount_t refcnt; + isc_entropy_t *entropy; /* entropy source */ + unsigned int limit; /* upper limit of key length */ + size_t vectorlen; /* size of the vector below */ + hash_random_t *rndvector; /* random vector for universal hashing */ +}; + +static isc_rwlock_t createlock; +static isc_once_t once = ISC_ONCE_INIT; +static isc_hash_t *hash = NULL; + +static unsigned char maptolower[] = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, + 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, + 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, + 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, + 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, + 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, + 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, + 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, + 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, + 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, + 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, + 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, + 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, + 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, + 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, + 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, + 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, + 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, + 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, + 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, + 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, + 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, + 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, + 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, + 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, + 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, + 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, + 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, + 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, + 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, + 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff +}; + +isc_result_t +isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy, + unsigned int limit, isc_hash_t **hctxp) +{ + isc_result_t ret; + isc_hash_t *hctx; + size_t vlen; + hash_random_t *rv; + hash_accum_t overflow_limit; + + REQUIRE(mctx != NULL); + REQUIRE(hctxp != NULL && *hctxp == NULL); + + /* + * Overflow check. Since our implementation only does a modulo + * operation at the last stage of hash calculation, the accumulator + * must not overflow. + */ + overflow_limit = + 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8); + if (overflow_limit < (limit + 1) * 0xff) + return (ISC_R_RANGE); + + hctx = isc_mem_get(mctx, sizeof(isc_hash_t)); + if (hctx == NULL) + return (ISC_R_NOMEMORY); + + vlen = sizeof(hash_random_t) * (limit + 1); + rv = isc_mem_get(mctx, vlen); + if (rv == NULL) { + ret = ISC_R_NOMEMORY; + goto errout; + } + + /* + * We need a lock. + */ + if (isc_mutex_init(&hctx->lock) != ISC_R_SUCCESS) { + ret = ISC_R_UNEXPECTED; + goto errout; + } + + /* + * From here down, no failures will/can occur. + */ + hctx->magic = HASH_MAGIC; + hctx->mctx = NULL; + isc_mem_attach(mctx, &hctx->mctx); + hctx->initialized = ISC_FALSE; + isc_refcount_init(&hctx->refcnt, 1); + hctx->entropy = NULL; + hctx->limit = limit; + hctx->vectorlen = vlen; + hctx->rndvector = rv; + + if (entropy != NULL) + isc_entropy_attach(entropy, &hctx->entropy); + + *hctxp = hctx; + return (ISC_R_SUCCESS); + + errout: + isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); + if (rv != NULL) + isc_mem_put(mctx, rv, vlen); + + return (ret); +} + +static void +initialize_lock(void) { + RUNTIME_CHECK(isc_rwlock_init(&createlock, 0, 0) == ISC_R_SUCCESS); +} + +isc_result_t +isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) { + isc_result_t result = ISC_R_SUCCESS; + + REQUIRE(mctx != NULL); + INSIST(hash == NULL); + + RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS); + + RWLOCK(&createlock, isc_rwlocktype_write); + + if (hash == NULL) + result = isc_hash_ctxcreate(mctx, entropy, limit, &hash); + + RWUNLOCK(&createlock, isc_rwlocktype_write); + + return (result); +} + +void +isc_hash_ctxinit(isc_hash_t *hctx) { + isc_result_t result; + + LOCK(&hctx->lock); + + if (hctx->initialized == ISC_TRUE) + goto out; + + if (hctx->entropy) { + result = isc_entropy_getdata(hctx->entropy, + hctx->rndvector, hctx->vectorlen, + NULL, 0); + INSIST(result == ISC_R_SUCCESS); + } else { + isc_uint32_t pr; + unsigned int i, copylen; + unsigned char *p; + + p = (unsigned char *)hctx->rndvector; + for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) { + isc_random_get(&pr); + if (i + sizeof(pr) <= hctx->vectorlen) + copylen = sizeof(pr); + else + copylen = hctx->vectorlen - i; + + memcpy(p, &pr, copylen); + } + INSIST(p == (unsigned char *)hctx->rndvector + + hctx->vectorlen); + } + + hctx->initialized = ISC_TRUE; + + out: + UNLOCK(&hctx->lock); +} + +void +isc_hash_init() { + INSIST(hash != NULL && VALID_HASH(hash)); + + isc_hash_ctxinit(hash); +} + +void +isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) { + REQUIRE(VALID_HASH(hctx)); + REQUIRE(hctxp != NULL && *hctxp == NULL); + + isc_refcount_increment(&hctx->refcnt, NULL); + *hctxp = hctx; +} + +static void +destroy(isc_hash_t **hctxp) { + isc_hash_t *hctx; + isc_mem_t *mctx; + + REQUIRE(hctxp != NULL && *hctxp != NULL); + hctx = *hctxp; + *hctxp = NULL; + + LOCK(&hctx->lock); + + isc_refcount_destroy(&hctx->refcnt); + + mctx = hctx->mctx; + if (hctx->entropy != NULL) + isc_entropy_detach(&hctx->entropy); + if (hctx->rndvector != NULL) + isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen); + + UNLOCK(&hctx->lock); + + DESTROYLOCK(&hctx->lock); + + memset(hctx, 0, sizeof(isc_hash_t)); + isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); + isc_mem_detach(&mctx); +} + +void +isc_hash_ctxdetach(isc_hash_t **hctxp) { + isc_hash_t *hctx; + unsigned int refs; + + REQUIRE(hctxp != NULL && VALID_HASH(*hctxp)); + hctx = *hctxp; + + isc_refcount_decrement(&hctx->refcnt, &refs); + if (refs == 0) + destroy(&hctx); + + *hctxp = NULL; +} + +void +isc_hash_destroy() { + unsigned int refs; + + INSIST(hash != NULL && VALID_HASH(hash)); + + isc_refcount_decrement(&hash->refcnt, &refs); + INSIST(refs == 0); + + destroy(&hash); +} + +static inline unsigned int +hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen, + isc_boolean_t case_sensitive) +{ + hash_accum_t partial_sum = 0; + hash_random_t *p = hctx->rndvector; + unsigned int i = 0; + + /* Make it sure that the hash context is initialized. */ + if (hctx->initialized == ISC_FALSE) + isc_hash_ctxinit(hctx); + + if (case_sensitive) { + for (i = 0; i < keylen; i++) + partial_sum += key[i] * (hash_accum_t)p[i]; + } else { + for (i = 0; i < keylen; i++) + partial_sum += maptolower[key[i]] * (hash_accum_t)p[i]; + } + + partial_sum += p[i]; + + return ((unsigned int)(partial_sum % PRIME32)); +} + +unsigned int +isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key, + unsigned int keylen, isc_boolean_t case_sensitive) +{ + REQUIRE(hctx != NULL && VALID_HASH(hctx)); + REQUIRE(keylen <= hctx->limit); + + return (hash_calc(hctx, key, keylen, case_sensitive)); +} + +unsigned int +isc_hash_calc(const unsigned char *key, unsigned int keylen, + isc_boolean_t case_sensitive) +{ + INSIST(hash != NULL && VALID_HASH(hash)); + REQUIRE(keylen <= hash->limit); + + return (hash_calc(hash, key, keylen, case_sensitive)); +} diff --git a/usr.sbin/bind/lib/isc/include/isc/hash.h b/usr.sbin/bind/lib/isc/include/isc/hash.h new file mode 100644 index 00000000000..adb914e931c --- /dev/null +++ b/usr.sbin/bind/lib/isc/include/isc/hash.h @@ -0,0 +1,175 @@ +/* + * Copyright (C) 2003 Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM + * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL + * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING + * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* $ISC: hash.h,v 1.2.2.1 2003/07/25 07:30:43 marka Exp $ */ + +#ifndef ISC_HASH_H +#define ISC_HASH_H 1 + +/***** + ***** Module Info + *****/ + +/* + * Hash + * + * The hash API + * + * Provides an unpredictable hash value for variable length data. + * A hash object contains a random vector (which is hidden from clients + * of this API) to make the actual hash value unpredictable. + * + * The algorithm used in the API guarantees the probability of hash + * collision; in the current implementation, as long as the values stored + * in the random vector are unpredictable, the probability of hash + * collision between arbitrary two different values is at most 1/2^16. + * + * Altough the API is generic about the hash keys, it mainly expects + * DNS names (and sometimes IPv4/v6 addresses) as inputs. It has an + * upper limit of the input length, and may run slow to calculaate the + * has values for large inputs. + * + * This API is designed to be general so that it can provide multiple + * different hash contexts that have different random vectors. However, + * it should be typical to have a single context for an entire system. + * To support such cases, the API also provides a single-context mode. + * + * MP: + * The hash object is almost read-only. Once the internal random vector + * is initialized, no write operation will occur, and there will be no + * need to lock the object to calculate actual hash values. + * + * Reliability: + * In some cases this module uses low-level data copy to initialize the + * random vector. Errors in this part are likely to crash the server or + * corrupt memory. + * + * Resources: + * A buffer, used as a random vector for calculating hash values. + * + * Security: + * This module intends to provide unpredictable hash values in + * adversarial environments in order to avoid denial of service attacks + * to hash buckets. + * Its unpredictability relies on the quality of entropy to build the + * random vector. + * + * Standards: + * None. + */ + +/*** + *** Imports + ***/ + +#include <isc/types.h> + +/*** + *** Functions + ***/ +ISC_LANG_BEGINDECLS + +isc_result_t +isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy, unsigned int limit, + isc_hash_t **hctx); +isc_result_t +isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit); +/* + * Create a new hash object. + * + * isc_hash_ctxcreate() creates a different object. + * isc_hash_create() creates a module-internal object to support the + * single-context mode. It should be called only once. + * + * 'entropy' must be NULL or a valid entropy object. If 'entropy' is NULL, + * pseudo random values will be used to build the random vector, which may + * weaken security. + * + * 'limit' specifies the maximum number of hash keys. If it is too large, + * these functions may fail. + */ + +void +isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp); +/* + * Attach to a hash object. + * This function is only necessary for the multiple-context mode. + */ + +void +isc_hash_ctxdetach(isc_hash_t **hctxp); +/* + * Detach from a hash object. + * + * This function is for the multiple-context mode, and takes a valid + * hash object as an argument. + */ + +void +isc_hash_destroy(void); +/* + * This function is for the single-context mode, and is expected to be used + * as a counterpart of isc_hash_create(). + * A valid module-internal hash object must have been created, and this + * function should be called only once. + */ + +void +isc_hash_ctxinit(isc_hash_t *hctx); +void +isc_hash_init(void); +/* + * Initialize a hash object. It fills in the random vector with a proper + * source of entropy, which is typically from the entropy object specified + * at the creation. Thus, it is desirable to call these functions after + * initializing the entropy object with some good entropy sources. + * + * These functions should be called before the first hash calculation. + * + * isc_hash_ctxinit() is for the multiple-context mode, and takes a valid hash + * object as an argument. + * isc_hash_init() is for the single-context mode. A valid module-internal + * hash object must have been created, and this function should be called only + * once. + */ + +unsigned int +isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key, + unsigned int keylen, isc_boolean_t case_sensitive); +unsigned int +isc_hash_calc(const unsigned char *key, unsigned int keylen, + isc_boolean_t case_sensitive); +/* + * Calculate a hash value. + * + * isc_hash_ctxinit() is for the multiple-context mode, and takes a valid hash + * object as an argument. + * isc_hash_init() is for the single-context mode. A valid module-internal + * hash object must have been created. + * + * 'key' is the hash key, which is a variable length buffer. + * 'keylen' specifies the key length, which must not be larger than the limit + * specified for the corresponding hash object. + * + * 'case_sensitive' specifies whether the hash key should be treated as + * case_sensitive values. It should typically be ISC_FALSE if the hash key + * is a DNS name. + */ + +ISC_LANG_ENDDECLS + +#endif /* ISC_HASH_H */ diff --git a/usr.sbin/bind/lib/isc/unix/include/isc/stat.h b/usr.sbin/bind/lib/isc/unix/include/isc/stat.h new file mode 100644 index 00000000000..a7943bf37fa --- /dev/null +++ b/usr.sbin/bind/lib/isc/unix/include/isc/stat.h @@ -0,0 +1,53 @@ +/* + * Copyright (C) 2003 Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM + * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL + * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING + * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* $ISC: stat.h,v 1.1.2.1 2003/05/20 00:06:56 marka Exp $ */ + +#ifndef ISC_STAT_H +#define ISC_STAT_H 1 + +/***** + ***** Module Info + *****/ + +/* + * Portable netdb.h support. + * + * This module is responsible for defining S_IS??? macros. + * + * MP: + * No impact. + * + * Reliability: + * No anticipated impact. + * + * Resources: + * N/A. + * + * Security: + * No anticipated impact. + * + */ + +/*** + *** Imports. + ***/ + +#include <sys/types.h> +#include <sys/stat.h> + +#endif /* ISC_STAT_H */ |