diff options
author | bojan <bojan@13f79535-47bb-0310-9956-ffa450edef68> | 2012-01-30 07:07:02 +0000 |
---|---|---|
committer | bojan <bojan@13f79535-47bb-0310-9956-ffa450edef68> | 2012-01-30 07:07:02 +0000 |
commit | b5454a07475c6d16ec3d0230291b341ffd0e5410 (patch) | |
tree | c4a5168c0133e5e0364742b401b8296c8a722b96 | |
parent | 93207e5814de79069865def5e5701b40281dcd9a (diff) | |
download | libapr-b5454a07475c6d16ec3d0230291b341ffd0e5410.tar.gz |
Backport r1236970, r1237078 and r1237507 from trunk.
Randomise hashes by providing a seed (initial hash value).
git-svn-id: http://svn.apache.org/repos/asf/apr/apr/branches/1.4.x@1237547 13f79535-47bb-0310-9956-ffa450edef68
-rw-r--r-- | CHANGES | 4 | ||||
-rw-r--r-- | tables/apr_hash.c | 39 | ||||
-rw-r--r-- | test/testhash.c | 74 |
3 files changed, 107 insertions, 10 deletions
@@ -1,6 +1,10 @@ -*- coding: utf-8 -*- Changes for APR 1.4.6 + *) Security: oCERT-2011-003 + Randomise hashes by providing a seed. + [Bojan Smojver, Branko Čibej, Ruediger Pluem et al.] + *) apr_random: Prevent segfault if pool used to initialize apr_random is destroyed before forking. [Stefan Fritsch] diff --git a/tables/apr_hash.c b/tables/apr_hash.c index 05ee42f46..a6e8a6497 100644 --- a/tables/apr_hash.c +++ b/tables/apr_hash.c @@ -18,6 +18,7 @@ #include "apr_general.h" #include "apr_pools.h" +#include "apr_time.h" #include "apr_hash.h" @@ -75,7 +76,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 +96,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; + ht->seed = (unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)pool ^ + (apr_uintptr_t)ht ^ (apr_uintptr_t)&now) - 1; ht->array = alloc_array(ht, ht->max); - ht->hash_func = apr_hashfunc_default; + ht->hash_func = NULL; + return ht; } @@ -178,10 +184,9 @@ 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 hashfunc_default(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; @@ -223,7 +228,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, * * -- Ralf S. Engelschall <rse@engelschall.com> */ - + if (*klen == APR_HASH_KEY_STRING) { for (p = key; *p; p++) { hash = hash * 33 + *p; @@ -239,6 +244,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 hashfunc_default(char_key, klen, 0); +} /* * This is where we keep the details of the hash function and control @@ -257,7 +267,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 = hashfunc_default(key, &klen, ht->seed); /* scan linked list */ for (hep = &ht->array[hash & ht->max], he = *hep; @@ -299,6 +312,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)); @@ -396,7 +410,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, apr_hash_entry_t *new_vals = NULL; apr_hash_entry_t *iter; apr_hash_entry_t *ent; - unsigned int i,j,k; + unsigned int i, j, k, hash; #if APR_POOL_DEBUG /* we don't copy keys and values, so it's necessary that @@ -424,6 +438,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, if (base->count + overlay->count > res->max) { res->max = res->max * 2 + 1; } + res->seed = base->seed; res->array = alloc_array(res, res->max); if (base->count + overlay->count) { new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * @@ -445,7 +460,11 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, for (k = 0; k <= overlay->max; k++) { for (iter = overlay->array[k]; iter; iter = iter->next) { - i = iter->hash & res->max; + if (res->hash_func) + hash = res->hash_func(iter->key, &iter->klen); + else + hash = hashfunc_default(iter->key, &iter->klen, res->seed); + i = hash & res->max; for (ent = res->array[i]; ent; ent = ent->next) { if ((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0)) { @@ -463,7 +482,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, new_vals[j].klen = iter->klen; new_vals[j].key = iter->key; new_vals[j].val = iter->val; - new_vals[j].hash = iter->hash; + new_vals[j].hash = hash; new_vals[j].next = res->array[i]; res->array[i] = &new_vals[j]; res->count++; diff --git a/test/testhash.c b/test/testhash.c index 6e7e518d5..62b5be5ca 100644 --- a/test/testhash.c +++ b/test/testhash.c @@ -437,6 +437,79 @@ static void overlay_same(abts_case *tc, void *data) ABTS_STR_EQUAL(tc, "#entries 5\n", StrArray[5]); } +static void overlay_fetch(abts_case *tc, void *data) +{ + apr_hash_t *base = NULL; + apr_hash_t *overlay = NULL; + apr_hash_t *result = NULL; + int count; + + base = apr_hash_make(p); + overlay = apr_hash_make(p); + ABTS_PTR_NOTNULL(tc, base); + ABTS_PTR_NOTNULL(tc, overlay); + + apr_hash_set(base, "base1", APR_HASH_KEY_STRING, "value1"); + apr_hash_set(base, "base2", APR_HASH_KEY_STRING, "value2"); + apr_hash_set(base, "base3", APR_HASH_KEY_STRING, "value3"); + apr_hash_set(base, "base4", APR_HASH_KEY_STRING, "value4"); + apr_hash_set(base, "base5", APR_HASH_KEY_STRING, "value5"); + + apr_hash_set(overlay, "overlay1", APR_HASH_KEY_STRING, "value1"); + apr_hash_set(overlay, "overlay2", APR_HASH_KEY_STRING, "value2"); + apr_hash_set(overlay, "overlay3", APR_HASH_KEY_STRING, "value3"); + apr_hash_set(overlay, "overlay4", APR_HASH_KEY_STRING, "value4"); + apr_hash_set(overlay, "overlay5", APR_HASH_KEY_STRING, "value5"); + + result = apr_hash_overlay(p, overlay, base); + + count = apr_hash_count(result); + ABTS_INT_EQUAL(tc, 10, count); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(result, "base1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(result, "base2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(result, "base3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(result, "base4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(result, "base5", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(result, "overlay1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(result, "overlay2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(result, "overlay3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(result, "overlay4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(result, "overlay5", APR_HASH_KEY_STRING)); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(base, "base1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(base, "base2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(base, "base3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(base, "base4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(base, "base5", APR_HASH_KEY_STRING)); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(overlay, "overlay1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(overlay, "overlay2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(overlay, "overlay3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(overlay, "overlay4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(overlay, "overlay5", APR_HASH_KEY_STRING)); +} + abts_suite *testhash(abts_suite *suite) { suite = ADD_SUITE(suite) @@ -460,6 +533,7 @@ abts_suite *testhash(abts_suite *suite) abts_run_test(suite, overlay_empty, NULL); abts_run_test(suite, overlay_2unique, NULL); abts_run_test(suite, overlay_same, NULL); + abts_run_test(suite, overlay_fetch, NULL); return suite; } |