Return-Path: X-Original-To: apmail-apr-dev-archive@www.apache.org Delivered-To: apmail-apr-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 73A819828 for ; Tue, 31 Jan 2012 01:24:17 +0000 (UTC) Received: (qmail 519 invoked by uid 500); 31 Jan 2012 01:24:17 -0000 Delivered-To: apmail-apr-dev-archive@apr.apache.org Received: (qmail 99977 invoked by uid 500); 31 Jan 2012 01:24:16 -0000 Mailing-List: contact dev-help@apr.apache.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Id: Delivered-To: mailing list dev@apr.apache.org Received: (qmail 99624 invoked by uid 99); 31 Jan 2012 01:24:15 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2012 01:24:15 +0000 X-ASF-Spam-Status: No, hits=-0.0 required=5.0 tests=SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of bojan@rexursive.com designates 150.101.121.179 as permitted sender) Received: from [150.101.121.179] (HELO beauty.rexursive.com) (150.101.121.179) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2012 01:24:09 +0000 Received: from [10.1.120.20] (shrek.rexursive.com [10.1.120.20]) by beauty.rexursive.com (Postfix) with ESMTPSA id 967341A9642 for ; Tue, 31 Jan 2012 12:23:46 +1100 (EST) Message-ID: <1327973026.16813.24.camel@shrek.rexursive.com> Subject: Hash collisions patch for 0.9.x From: Bojan Smojver To: APR Development List Date: Tue, 31 Jan 2012 12:23:46 +1100 Content-Type: multipart/mixed; boundary="=-9YcEmK2vOUXaxqsTZiP5" X-Mailer: Evolution 3.2.3 (3.2.3-1.fc16) Mime-Version: 1.0 X-Virus-Checked: Checked by ClamAV on apache.org --=-9YcEmK2vOUXaxqsTZiP5 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit 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 --=-9YcEmK2vOUXaxqsTZiP5 Content-Disposition: attachment; filename="apr_hash-random-0.9.x.patch" Content-Type: text/x-patch; name="apr_hash-random-0.9.x.patch"; charset="UTF-8" Content-Transfer-Encoding: 8bit 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 */ - 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 +#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; } - --=-9YcEmK2vOUXaxqsTZiP5--