Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-26 Thread Ruediger Pluem 


Bojan Smojver wrote:
 On Thu, 2012-01-26 at 09:05 +1100, Bojan Smojver wrote:
 Will fix.
 
 Better?
 

Yes. No more regression in httpd and APR tests pass as well.

Regards

Rüdiger

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-25 Thread Ruediger Pluem 


Bojan Smojver wrote:
 On Mon, 2012-01-16 at 14:11 +0100, Ruediger Pluem wrote:
 r1231605 and r1231858 cause massive regressions and test case failures
 in httpd. Not sure why right now.
 
 Could you please run your tests with this patch. Let me know how it
 goes. Thanks.
 


I think there is still a problem with your patch:

@@ -468,6 +484,12 @@

 for (k = 0; k = overlay-max; k++) {
 for (iter = overlay-array[k]; iter; iter = iter-next) {
+if (res-hash_func)
+iter-hash = res-hash_func(iter-key, iter-klen);
+else
+iter-hash = apr_hashfunc_default_internal(iter-key,
+   iter-klen,
+   res-seed);

Shouldn't you store the result of res-hash_func / 
apr_hashfunc_default_internal in a local temporary
variable and use it later on? Otherwise you change the overlay hash and may 
make it unusable by setting a new hash
value. IMHO all operations by this code are currently readonly on the base and 
overlay hash.

 i = iter-hash  res-max;
 for (ent = res-array[i]; ent; ent = ent-next) {
 if ((ent-klen == iter-klen) 

Regards

Rüdiger

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-25 Thread Bojan Smojver 

--- Original message ---

From: Ruediger Pluem


Shouldn't you store the result of res-hash_func / 
apr_hashfunc_default_internal in a local temporary
variable and use it later on? Otherwise you change the overlay hash and 
may make it unusable by setting a new hash
value. IMHO all operations by this code are currently readonly on the 
base and overlay hash.


Yeah, good point. I was working under the assumption that overlay gets 
thrown away, which may not be true. Will fix.


--
Bojan

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-25 Thread Bojan Smojver 
On Thu, 2012-01-26 at 09:05 +1100, Bojan Smojver wrote:
 Will fix.

Better?

-- 
Bojan
Index: tables/apr_hash.c
===
--- tables/apr_hash.c	(revision 1235978)
+++ 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
 
@@ -75,7 +76,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_hashfunc_t   hash_func;
 apr_hash_entry_t*free;  /* List of recycled entries */
 };
@@ -95,13 +96,18 @@
 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;
 }
 
@@ -201,10 +207,10 @@
 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 +252,7 @@
  *
  *  -- Ralf S. Engelschall r...@engelschall.com
  */
- 
+
 if (*klen == APR_HASH_KEY_STRING) {
 for (p = key; *p; p++) {
 hash = hash * 33 + *p;
@@ -262,6 +268,11 @@
 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 +291,10 @@
 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 +336,7 @@
 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));
 
@@ -419,7 +434,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;
 
 #if APR_POOL_DEBUG
 /* we don't copy keys and values, so it's necessary that
@@ -447,6 +462,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) *
@@ -468,7 +484,12 @@
 
 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 = apr_hashfunc_default_internal(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)) {
@@ -486,7 +507,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++;
Index: test/testhash.c
===
--- test/testhash.c	(revision 1235978)
+++ test/testhash.c	(working copy)
@@ -438,6 +438,79 @@
 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);
+

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-22 Thread Bojan Smojver 
On Mon, 2012-01-16 at 14:11 +0100, Ruediger Pluem wrote:
 r1231605 and r1231858 cause massive regressions and test case failures
 in httpd. Not sure why right now.

Could you please run your tests with this patch. Let me know how it
goes. Thanks.

-- 
Bojan
Index: tables/apr_hash.c
===
--- tables/apr_hash.c	(revision 1234679)
+++ 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
 
@@ -75,7 +76,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_hashfunc_t   hash_func;
 apr_hash_entry_t*free;  /* List of recycled entries */
 };
@@ -95,13 +96,18 @@
 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;
 }
 
@@ -201,10 +207,10 @@
 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 +252,7 @@
  *
  *  -- Ralf S. Engelschall r...@engelschall.com
  */
- 
+
 if (*klen == APR_HASH_KEY_STRING) {
 for (p = key; *p; p++) {
 hash = hash * 33 + *p;
@@ -262,6 +268,11 @@
 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 +291,10 @@
 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 +336,7 @@
 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));
 
@@ -447,6 +462,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) *
@@ -468,6 +484,12 @@
 
 for (k = 0; k = overlay-max; k++) {
 for (iter = overlay-array[k]; iter; iter = iter-next) {
+if (res-hash_func)
+iter-hash = res-hash_func(iter-key, iter-klen);
+else
+iter-hash = apr_hashfunc_default_internal(iter-key,
+   iter-klen,
+   res-seed);
 i = iter-hash  res-max;
 for (ent = res-array[i]; ent; ent = ent-next) {
 if ((ent-klen == iter-klen) 
Index: test/testhash.c
===
--- test/testhash.c	(revision 1234679)
+++ test/testhash.c	(working copy)
@@ -438,6 +438,57 @@
 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,

RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-16 Thread Bojan Smojver 
On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
 If the timer has enough detail we could just use the time, ptr
 combination as the seed here.

See whether you like r1231858.

-- 
Bojan

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-16 Thread Ruediger Pluem 


Bojan Smojver wrote:
 On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
 If the timer has enough detail we could just use the time, ptr
 combination as the seed here.
 
 See whether you like r1231858.
 

r1231605 and r1231858 cause massive regressions and test case failures in httpd.
Not sure why right now.

est Summary Report
---
t/apache/acceptpathinfo.t (Wstat: 0 Tests: 36 Failed: 10)
  Failed tests:  2, 6, 8, 12, 14, 18, 26, 30, 35-36
t/apache/cfg_getline.t(Wstat: 0 Tests: 116 Failed: 58)
  Failed tests:  2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22
24, 26, 28, 30, 32, 34, 36, 38, 40, 42
44, 46, 48, 50, 52, 54, 56, 58, 60, 62
64, 66, 68, 70, 72, 74, 76, 78, 80, 82
84, 86, 88, 90, 92, 94, 96, 98, 100, 102
104, 106, 108, 110, 112, 114, 116
t/apache/pr17629.t(Wstat: 0 Tests: 4 Failed: 2)
  Failed tests:  1, 3
t/apache/pr43939.t(Wstat: 0 Tests: 4 Failed: 2)
  Failed tests:  1, 3
t/apache/pr49328.t(Wstat: 0 Tests: 1 Failed: 1)
  Failed test:  1
t/modules/asis.t  (Wstat: 0 Tests: 3 Failed: 3)
  Failed tests:  1-3
t/modules/filter.t(Wstat: 0 Tests: 1 Failed: 1)
  Failed test:  1
t/modules/lua.t   (Wstat: 0 Tests: 36 Failed: 8)
  Failed tests:  7-8, 13-14, 16-17, 22-23
t/modules/negotiation.t   (Wstat: 0 Tests: 99 Failed: 1)
  Failed test:  99
t/modules/proxy.t (Wstat: 0 Tests: 15 Failed: 2)
  Failed tests:  9-10
Files=104, Tests=4551, 112 wallclock secs ( 1.37 usr  0.53 sys + 37.48 cusr 
14.01 csys = 53.39 CPU)


Regards

Rüdiger

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-16 Thread Bojan Smojver 

--- Original message ---

From: Ruediger Pluem


r1231605 and r1231858 cause massive regressions and test case failures in 
httpd.


I won't be able to commit for a while. Please feel free to revert both. 
Sorry about the breakage. :-(


--
Bojan

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-16 Thread Bojan Smojver 

--- Original message ---

From: Bojan Smojver
Sent: 17.1.'12,  5:18

--- Original message ---

From: Ruediger Pluem


r1231605 and r1231858 cause massive regressions and test case failures 
in  httpd.


I won't be able to commit for a while. Please feel free to revert both. 
Sorry about the breakage. :-(


I had a look at the apr_hash.c and I see that I completely missed patching 
the merge function. So, if the tests in question are using it, they will 
fail for sure.


--
Bojan

Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-16 Thread Bojan Smojver 

--- Original message ---

From: Bojan Smojver
Sent: 17.1.'12,  5:18

--- Original message ---

From: Ruediger Pluem


r1231605 and r1231858 cause massive regressions and test case failures 
in  httpd.


I won't be able to commit for a while. Please feel free to revert both. 
Sorry about the breakage. :-(


Just reverted both.

--
Bojan

RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-15 Thread Bert Huijben 

 -Original Message-
 From: bo...@apache.org [mailto:bo...@apache.org]
 Sent: zondag 15 januari 2012 1:37
 To: comm...@apr.apache.org
 Subject: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
 
 Author: bojan
 Date: Sun Jan 15 00:37:14 2012
 New Revision: 1231605
 
 URL: http://svn.apache.org/viewvc?rev=1231605view=rev
 Log:
 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.
 
 Modified:
 apr/apr/trunk/tables/apr_hash.c
 
 Modified: apr/apr/trunk/tables/apr_hash.c
 URL:
 http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?rev=123160
 5r1=1231604r2=1231605view=diff
 ==
 
 --- apr/apr/trunk/tables/apr_hash.c (original)
 +++ apr/apr/trunk/tables/apr_hash.c Sun Jan 15 00:37:14 2012
 @@ -18,6 +18,10 @@
 
  #include apr_general.h
  #include apr_pools.h
 +#include apr_time.h
 +#if APR_HAVE_STDLIB_H
 +#include stdlib.h /* 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(ap
  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());

If you call srand() before every call to rand() the result is no longer random.

And in this case we do this inside a shared library, so this might introduce 
other attack vectors in applications that use apr.

If we really want to call srand() from apr we should do that from a one-time 
initialization (apr_initialize? Or some initialize flag), to avoid breaking 
applications that assume rand() produces random values for them. Calling 
srand() from apr_hash_make might even break scientific applications that want 
the same set of random values multiple times (srand(CONSTANT)).

If the timer has enough detail we could just use the time, ptr combination as 
the seed here. This is essentially what the code does by calling srand() every 
time anyway.

Bert

RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-15 Thread Bojan Smojver 
On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:

 If you call srand() before every call to rand() the result is no longer 
 random.

Yes, I'm aware of that.

 And in this case we do this inside a shared library, so this might introduce 
 other attack vectors in applications that use apr.

Also aware of that.

 If we really want to call srand() from apr we should do that from a one-time 
 initialization (apr_initialize? Or some initialize flag), to avoid breaking 
 applications that assume rand() produces random values for them. Calling 
 srand() from apr_hash_make might even break scientific applications that want 
 the same set of random values multiple times (srand(CONSTANT)).

We can call srand() once as you suggest, but that doesn't mean something
else isn't going to call it from some other thread at any point. Relying
on rand() returning predictable values in a multi-threaded app would be
naive anyway.

 If the timer has enough detail we could just use the time, ptr combination as 
 the seed here. This is essentially what the code does by calling srand() 
 every time anyway.

That is true. In fact, my first code to the list just used ht. We could
use ht and time to get random values. Same attack vectors as noted by
you above apply, of course.

-- 
Bojan

RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c

2012-01-15 Thread Bojan Smojver 
On Mon, 2012-01-16 at 08:38 +1100, Bojan Smojver wrote:
 That is true. In fact, my first code to the list just used ht. We
 could use ht and time to get random values. Same attack vectors as
 noted by you above apply, of course. 

Maybe like this?

-- 
Bojan
Index: tables/apr_hash.c
===
--- tables/apr_hash.c	(revision 1231774)
+++ tables/apr_hash.c	(working copy)
@@ -19,9 +19,6 @@
 #include apr_general.h
 #include apr_pools.h
 #include apr_time.h
-#if APR_HAVE_STDLIB_H
-#include stdlib.h /* for rand, srand */
-#endif
 
 #include apr_hash.h
 
@@ -106,8 +103,8 @@
 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-seed = (unsigned int)(((now  32) ^ (apr_uintptr_t)ht) ^
+  (now ^ (apr_uintptr_t)now));
 ht-array = alloc_array(ht, ht-max);
 ht-hash_func = NULL;