A bit more code change required, so I'll send the patch first, for folks
that still use this branch. Let me know what you find.
On my x86_64 F-16 machine, all tests pass.
--
Bojan
Property changes on: .
___________________________________________________________________
Added: svn:mergeinfo
Merged /apr/apr/trunk:r1236970,1237078,1237507
Index: CHANGES
===================================================================
--- CHANGES (revision 1237537)
+++ CHANGES (working copy)
@@ -1,6 +1,9 @@
-*- coding: utf-8 -*-
Changes with APR 0.9.21
+ *) Security: oCERT-2011-003
+ Randomise hashes by providing a seed.
+ [Bojan Smojver, Branko Čibej, Ruediger Pluem et al.]
Changes with APR 0.9.20
Index: tables/apr_hash.c
===================================================================
--- tables/apr_hash.c (revision 1237537)
+++ tables/apr_hash.c (working copy)
@@ -18,6 +18,7 @@
#include "apr_general.h"
#include "apr_pools.h"
+#include "apr_time.h"
#include "apr_hash.h"
@@ -72,7 +73,7 @@
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_hash_entry_t *free; /* List of recycled entries */
};
@@ -88,15 +89,26 @@
return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1));
}
+#if APR_SIZEOF_VOIDP == 8
+typedef apr_uint64_t apr_uintptr_t;
+#else
+typedef apr_uint32_t apr_uintptr_t;
+#endif
+
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);
+
return ht;
}
@@ -165,23 +177,11 @@
ht->max = new_max;
}
-/*
- * This is where we keep the details of the hash function and control
- * the maximum collision rate.
- *
- * If val is non-NULL it creates and initializes a new hash entry if
- * there isn't already one there; it returns an updatable pointer so
- * that hash entries can be removed.
- */
-
-static apr_hash_entry_t **find_entry(apr_hash_t *ht,
- const void *key,
- apr_ssize_t klen,
- const void *val)
+static unsigned int hashfunc_default(const char *char_key, apr_ssize_t *klen,
+ unsigned int hash)
{
- apr_hash_entry_t **hep, *he;
+ const unsigned char *key = (const unsigned char *)char_key;
const unsigned char *p;
- unsigned int hash;
apr_ssize_t i;
/*
@@ -221,19 +221,41 @@
*
* -- Ralf S. Engelschall <[email protected]>
*/
- hash = 0;
- if (klen == APR_HASH_KEY_STRING) {
+
+ if (*klen == APR_HASH_KEY_STRING) {
for (p = key; *p; p++) {
hash = hash * 33 + *p;
}
- klen = p - (const unsigned char *)key;
+ *klen = p - key;
}
else {
- for (p = key, i = klen; i; i--, p++) {
+ for (p = key, i = *klen; i; i--, p++) {
hash = hash * 33 + *p;
}
}
+ return hash;
+}
+
+/*
+ * This is where we keep the details of the hash function and control
+ * the maximum collision rate.
+ *
+ * If val is non-NULL it creates and initializes a new hash entry if
+ * there isn't already one there; it returns an updatable pointer so
+ * that hash entries can be removed.
+ */
+
+static apr_hash_entry_t **find_entry(apr_hash_t *ht,
+ const void *key,
+ apr_ssize_t klen,
+ const void *val)
+{
+ apr_hash_entry_t **hep, *he;
+ unsigned int hash;
+
+ hash = hashfunc_default(key, &klen, ht->seed);
+
/* scan linked list */
for (hep = &ht->array[hash & ht->max], he = *hep;
he; hep = &he->next, he = *hep) {
@@ -274,6 +296,7 @@
ht->free = NULL;
ht->count = orig->count;
ht->max = orig->max;
+ ht->seed = orig->seed;
ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
@@ -363,7 +386,7 @@
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;
#ifdef POOL_DEBUG
/* we don't copy keys and values, so it's necessary that
@@ -390,6 +413,7 @@
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) *
@@ -411,7 +435,8 @@
for (k = 0; k <= overlay->max; k++) {
for (iter = overlay->array[k]; iter; iter = iter->next) {
- i = iter->hash & res->max;
+ 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)) {
@@ -429,7 +454,7 @@
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++;
Property changes on: test/NWGNUproc_child
___________________________________________________________________
Deleted: svn:mergeinfo
Property changes on: test/NWGNUaprtest
___________________________________________________________________
Deleted: svn:mergeinfo
Property changes on: test/NWGNUtestatmc
___________________________________________________________________
Deleted: svn:mergeinfo
Property changes on: test/NWGNUmod_test
___________________________________________________________________
Deleted: svn:mergeinfo
Index: test/testhash.c
===================================================================
--- test/testhash.c (revision 1237537)
+++ test/testhash.c (working copy)
@@ -21,22 +21,44 @@
#include "apr_pools.h"
#include "apr_hash.h"
-static void dump_hash(apr_pool_t *p, apr_hash_t *h, char *str)
+#if APR_HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+
+#define MAX_LTH 256
+#define MAX_DEPTH 11
+
+static int comp_string(const void *str1, const void *str2)
{
+ return strcmp(str1,str2);
+}
+
+static void dump_hash(apr_pool_t *p, apr_hash_t *h, char str[][MAX_LTH])
+{
apr_hash_index_t *hi;
char *val, *key;
apr_ssize_t len;
int i = 0;
- str[0] = '\0';
-
for (hi = apr_hash_first(p, h); hi; hi = apr_hash_next(hi)) {
apr_hash_this(hi,(void*) &key, &len, (void*) &val);
- apr_snprintf(str, 8196, "%sKey %s (%" APR_SSIZE_T_FMT ") Value %s\n",
- str, key, len, val);
+ str[i][0]='\0';
+ apr_snprintf(str[i], MAX_LTH, "%sKey %s (%" APR_SSIZE_T_FMT ") Value %s\n",
+ str[i], key, len, val);
i++;
}
- apr_snprintf(str, 8196, "%s#entries %d\n", str, i);
+ str[i][0]='\0';
+ apr_snprintf(str[i], MAX_LTH, "%s#entries %d\n", str[i], i);
+
+ /* Sort the result strings so that they can be checked for expected results easily,
+ * without having to worry about platform quirks
+ */
+ qsort(
+ str, /* Pointer to elements */
+ i, /* number of elements */
+ MAX_LTH, /* size of one element */
+ comp_string /* Pointer to comparison routine */
+ );
}
static void sum_hash(apr_pool_t *p, apr_hash_t *h, int *pcount, int *keySum, int *valSum)
@@ -132,7 +154,7 @@
static void hash_traverse(CuTest *tc)
{
apr_hash_t *h;
- char str[8196];
+ char StrArray[MAX_DEPTH][MAX_LTH];
h = apr_hash_make(p);
CuAssertPtrNotNull(tc, h);
@@ -147,15 +169,17 @@
apr_hash_set(h, "SAME2", APR_HASH_KEY_STRING, "same");
apr_hash_set(h, "OVERWRITE", APR_HASH_KEY_STRING, "Overwrite key");
- dump_hash(p, h, str);
- CuAssertStrEquals(tc, "Key FOO1 (4) Value bar1\n"
- "Key FOO2 (4) Value bar2\n"
- "Key OVERWRITE (9) Value Overwrite key\n"
- "Key FOO3 (4) Value bar3\n"
- "Key SAME1 (5) Value same\n"
- "Key FOO4 (4) Value bar4\n"
- "Key SAME2 (5) Value same\n"
- "#entries 7\n", str);
+ dump_hash(p, h, StrArray);
+
+ CuAssertStrEquals(tc, "Key FOO1 (4) Value bar1\n", StrArray[0]);
+ CuAssertStrEquals(tc, "Key FOO2 (4) Value bar2\n", StrArray[1]);
+ CuAssertStrEquals(tc, "Key FOO3 (4) Value bar3\n", StrArray[2]);
+ CuAssertStrEquals(tc, "Key FOO4 (4) Value bar4\n", StrArray[3]);
+ CuAssertStrEquals(tc, "Key OVERWRITE (9) Value Overwrite key\n",
+ StrArray[4]);
+ CuAssertStrEquals(tc, "Key SAME1 (5) Value same\n", StrArray[5]);
+ CuAssertStrEquals(tc, "Key SAME2 (5) Value same\n", StrArray[6]);
+ CuAssertStrEquals(tc, "#entries 7\n", StrArray[7]);
}
/* This is kind of a hack, but I am just keeping an existing test. This is
@@ -269,7 +293,7 @@
apr_hash_t *overlay = NULL;
apr_hash_t *result = NULL;
int count;
- char str[8196];
+ char StrArray[MAX_DEPTH][MAX_LTH];
base = apr_hash_make(p);
overlay = apr_hash_make(p);
@@ -287,13 +311,14 @@
count = apr_hash_count(result);
CuAssertIntEquals(tc, 5, count);
- dump_hash(p, result, str);
- CuAssertStrEquals(tc, "Key key1 (4) Value value1\n"
- "Key key2 (4) Value value2\n"
- "Key key3 (4) Value value3\n"
- "Key key4 (4) Value value4\n"
- "Key key5 (4) Value value5\n"
- "#entries 5\n", str);
+ dump_hash(p, result, StrArray);
+
+ CuAssertStrEquals(tc, "Key key1 (4) Value value1\n", StrArray[0]);
+ CuAssertStrEquals(tc, "Key key2 (4) Value value2\n", StrArray[1]);
+ CuAssertStrEquals(tc, "Key key3 (4) Value value3\n", StrArray[2]);
+ CuAssertStrEquals(tc, "Key key4 (4) Value value4\n", StrArray[3]);
+ CuAssertStrEquals(tc, "Key key5 (4) Value value5\n", StrArray[4]);
+ CuAssertStrEquals(tc, "#entries 5\n", StrArray[5]);
}
static void overlay_2unique(CuTest *tc)
@@ -302,7 +327,7 @@
apr_hash_t *overlay = NULL;
apr_hash_t *result = NULL;
int count;
- char str[8196];
+ char StrArray[MAX_DEPTH][MAX_LTH];
base = apr_hash_make(p);
overlay = apr_hash_make(p);
@@ -326,21 +351,19 @@
count = apr_hash_count(result);
CuAssertIntEquals(tc, 10, count);
- dump_hash(p, result, str);
- /* I don't know why these are out of order, but they are. I would probably
- * consider this a bug, but others should comment.
- */
- CuAssertStrEquals(tc, "Key base5 (5) Value value5\n"
- "Key overlay1 (8) Value value1\n"
- "Key overlay2 (8) Value value2\n"
- "Key overlay3 (8) Value value3\n"
- "Key overlay4 (8) Value value4\n"
- "Key overlay5 (8) Value value5\n"
- "Key base1 (5) Value value1\n"
- "Key base2 (5) Value value2\n"
- "Key base3 (5) Value value3\n"
- "Key base4 (5) Value value4\n"
- "#entries 10\n", str);
+ dump_hash(p, result, StrArray);
+
+ CuAssertStrEquals(tc, "Key base1 (5) Value value1\n", StrArray[0]);
+ CuAssertStrEquals(tc, "Key base2 (5) Value value2\n", StrArray[1]);
+ CuAssertStrEquals(tc, "Key base3 (5) Value value3\n", StrArray[2]);
+ CuAssertStrEquals(tc, "Key base4 (5) Value value4\n", StrArray[3]);
+ CuAssertStrEquals(tc, "Key base5 (5) Value value5\n", StrArray[4]);
+ CuAssertStrEquals(tc, "Key overlay1 (8) Value value1\n", StrArray[5]);
+ CuAssertStrEquals(tc, "Key overlay2 (8) Value value2\n", StrArray[6]);
+ CuAssertStrEquals(tc, "Key overlay3 (8) Value value3\n", StrArray[7]);
+ CuAssertStrEquals(tc, "Key overlay4 (8) Value value4\n", StrArray[8]);
+ CuAssertStrEquals(tc, "Key overlay5 (8) Value value5\n", StrArray[9]);
+ CuAssertStrEquals(tc, "#entries 10\n", StrArray[10]);
}
static void overlay_same(CuTest *tc)
@@ -348,7 +371,7 @@
apr_hash_t *base = NULL;
apr_hash_t *result = NULL;
int count;
- char str[8196];
+ char StrArray[MAX_DEPTH][MAX_LTH];
base = apr_hash_make(p);
CuAssertPtrNotNull(tc, base);
@@ -364,18 +387,89 @@
count = apr_hash_count(result);
CuAssertIntEquals(tc, 5, count);
- dump_hash(p, result, str);
- /* I don't know why these are out of order, but they are. I would probably
- * consider this a bug, but others should comment.
- */
- CuAssertStrEquals(tc, "Key base5 (5) Value value5\n"
- "Key base1 (5) Value value1\n"
- "Key base2 (5) Value value2\n"
- "Key base3 (5) Value value3\n"
- "Key base4 (5) Value value4\n"
- "#entries 5\n", str);
+ dump_hash(p, result, StrArray);
+
+ CuAssertStrEquals(tc, "Key base1 (5) Value value1\n", StrArray[0]);
+ CuAssertStrEquals(tc, "Key base2 (5) Value value2\n", StrArray[1]);
+ CuAssertStrEquals(tc, "Key base3 (5) Value value3\n", StrArray[2]);
+ CuAssertStrEquals(tc, "Key base4 (5) Value value4\n", StrArray[3]);
+ CuAssertStrEquals(tc, "Key base5 (5) Value value5\n", StrArray[4]);
+ CuAssertStrEquals(tc, "#entries 5\n", StrArray[5]);
}
-
+
+static void overlay_fetch(CuTest *tc)
+{
+ 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);
+ CuAssertPtrNotNull(tc, base);
+ CuAssertPtrNotNull(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);
+ CuAssertIntEquals(tc, 10, count);
+
+ CuAssertStrEquals(tc, "value1",
+ apr_hash_get(result, "base1", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value2",
+ apr_hash_get(result, "base2", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value3",
+ apr_hash_get(result, "base3", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value4",
+ apr_hash_get(result, "base4", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value5",
+ apr_hash_get(result, "base5", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value1",
+ apr_hash_get(result, "overlay1", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value2",
+ apr_hash_get(result, "overlay2", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value3",
+ apr_hash_get(result, "overlay3", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value4",
+ apr_hash_get(result, "overlay4", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value5",
+ apr_hash_get(result, "overlay5", APR_HASH_KEY_STRING));
+
+ CuAssertStrEquals(tc, "value1",
+ apr_hash_get(base, "base1", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value2",
+ apr_hash_get(base, "base2", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value3",
+ apr_hash_get(base, "base3", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value4",
+ apr_hash_get(base, "base4", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value5",
+ apr_hash_get(base, "base5", APR_HASH_KEY_STRING));
+
+ CuAssertStrEquals(tc, "value1",
+ apr_hash_get(overlay, "overlay1", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value2",
+ apr_hash_get(overlay, "overlay2", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value3",
+ apr_hash_get(overlay, "overlay3", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value4",
+ apr_hash_get(overlay, "overlay4", APR_HASH_KEY_STRING));
+ CuAssertStrEquals(tc, "value5",
+ apr_hash_get(overlay, "overlay5", APR_HASH_KEY_STRING));
+}
+
CuSuite *testhash(void)
{
CuSuite *suite = CuSuiteNew("Hash");
@@ -397,7 +491,7 @@
SUITE_ADD_TEST(suite, overlay_empty);
SUITE_ADD_TEST(suite, overlay_2unique);
SUITE_ADD_TEST(suite, overlay_same);
+ SUITE_ADD_TEST(suite, overlay_fetch);
return suite;
}
-
