From 50544f1d1370bf5624f87436d98d853d54693fd4 Mon Sep 17 00:00:00 2001 From: Bojan Smojver Date: Sun, 15 Jan 2012 00:37:14 +0000 Subject: Randomise hashes by providing a seed. This is supposed to be a "good enough" approach. Using a crypto quality function like apr_generate_random_bytes() may be stronger, but this function may block, so it will be avoided for now. git-svn-id: https://svn.apache.org/repos/asf/apr/apr/trunk@1231605 13f79535-47bb-0310-9956-ffa450edef68 --- tables/apr_hash.c | 32 +++++++++++++++++++++++++------- 1 file changed, 25 insertions(+), 7 deletions(-) (limited to 'tables') diff --git a/tables/apr_hash.c b/tables/apr_hash.c index d64e77941..f899d5156 100644 --- a/tables/apr_hash.c +++ b/tables/apr_hash.c @@ -18,6 +18,10 @@ #include "apr_general.h" #include "apr_pools.h" +#include "apr_time.h" +#if APR_HAVE_STDLIB_H +#include /* for rand, srand */ +#endif #include "apr_hash.h" @@ -75,7 +79,7 @@ struct apr_hash_t { apr_pool_t *pool; apr_hash_entry_t **array; apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */ - unsigned int count, max; + unsigned int count, max, seed; apr_hashfunc_t hash_func; apr_hash_entry_t *free; /* List of recycled entries */ }; @@ -95,13 +99,18 @@ static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max) APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) { apr_hash_t *ht; + apr_time_t now = apr_time_now(); + ht = apr_palloc(pool, sizeof(apr_hash_t)); ht->pool = pool; ht->free = NULL; ht->count = 0; ht->max = INITIAL_MAX; + srand((unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)ht)); + ht->seed = (unsigned int)(rand()); ht->array = alloc_array(ht, ht->max); - ht->hash_func = apr_hashfunc_default; + ht->hash_func = NULL; + return ht; } @@ -201,10 +210,10 @@ static void expand_array(apr_hash_t *ht) ht->max = new_max; } -APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, - apr_ssize_t *klen) +static unsigned int apr_hashfunc_default_internal(const char *char_key, + apr_ssize_t *klen, + unsigned int hash) { - unsigned int hash = 0; const unsigned char *key = (const unsigned char *)char_key; const unsigned char *p; apr_ssize_t i; @@ -246,7 +255,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, * * -- Ralf S. Engelschall */ - + if (*klen == APR_HASH_KEY_STRING) { for (p = key; *p; p++) { hash = hash * 33 + *p; @@ -262,6 +271,11 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, return hash; } +APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, + apr_ssize_t *klen) +{ + return apr_hashfunc_default_internal(char_key, klen, 0); +} /* * This is where we keep the details of the hash function and control @@ -280,7 +294,10 @@ static apr_hash_entry_t **find_entry(apr_hash_t *ht, apr_hash_entry_t **hep, *he; unsigned int hash; - hash = ht->hash_func(key, &klen); + if (ht->hash_func) + hash = ht->hash_func(key, &klen); + else + hash = apr_hashfunc_default_internal(key, &klen, ht->seed); /* scan linked list */ for (hep = &ht->array[hash & ht->max], he = *hep; @@ -322,6 +339,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool, ht->free = NULL; ht->count = orig->count; ht->max = orig->max; + ht->seed = orig->seed; ht->hash_func = orig->hash_func; ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t)); -- cgit v1.2.1