You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2013/06/20 23:40:50 UTC

svn commit: r1495204 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

Author: stefan2
Date: Thu Jun 20 21:40:50 2013
New Revision: 1495204

URL: http://svn.apache.org/r1495204
Log:
Follow-up to r1495063: integer overflows result in an inefficient hash
function and reduce cache effectiveness.

* subversion/libsvn_fs_fs/tree.c
  (cache_lookup): prevent unnecessary integer overflows in hash function

Modified:
    subversion/trunk/subversion/libsvn_fs_fs/tree.c

Modified: subversion/trunk/subversion/libsvn_fs_fs/tree.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/tree.c?rev=1495204&r1=1495203&r2=1495204&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/tree.c Thu Jun 20 21:40:50 2013
@@ -362,14 +362,14 @@ cache_lookup( fs_fs_dag_cache_t *cache
       int j;
 
       for (j = 0; j < 4; j++)
-        val |= (path[i + j] << (j * 8));
+        val |= ((apr_uint32_t)(unsigned char)path[i + j] << (j * 8));
 
       hash_value = hash_value * 0xd1f3da69 + val;
     }
 #endif
 
   for (; i < path_len; ++i)
-    hash_value = hash_value * 33 + path[i];
+    hash_value = hash_value * 33 + (unsigned char)path[i];
 
   bucket_index = hash_value + (hash_value >> 16);
   bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;

Re: svn commit: r1495204 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Jun 20, 2013 at 11:43 PM, Blair Zajac <bl...@orcaware.com> wrote:

> On 06/20/2013 02:40 PM, stefan2@apache.org wrote:
>
>> Author: stefan2
>> Date: Thu Jun 20 21:40:50 2013
>> New Revision: 1495204
>>
>> URL: http://svn.apache.org/r1495204
>> Log:
>> Follow-up to r1495063: integer overflows result in an inefficient hash
>> function and reduce cache effectiveness.
>>
>> * subversion/libsvn_fs_fs/tree.c
>>    (cache_lookup): prevent unnecessary integer overflows in hash function
>>
>
> Hi Stefan,
>
> I've been reading up on hash functions and am curious about this how
> overflow can reduce cache effectiveness.  Do you have any links or can
> offer an explanation?
>
>
This illustrates what happened before the patch:

char c = 99;
unsigned hash = 0;
hash |= c << 8; /* c << 8 is often 0, actually it's undefined */

On a more general note, you don't want to make
it easy for parts of the input to cancel each other out.
So, adding (potentially) negative values is a bad thing
(strategically).

-- Stefan^2.

Re: svn commit: r1495204 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

Posted by Blair Zajac <bl...@orcaware.com>.
On 06/20/2013 02:40 PM, stefan2@apache.org wrote:
> Author: stefan2
> Date: Thu Jun 20 21:40:50 2013
> New Revision: 1495204
>
> URL: http://svn.apache.org/r1495204
> Log:
> Follow-up to r1495063: integer overflows result in an inefficient hash
> function and reduce cache effectiveness.
>
> * subversion/libsvn_fs_fs/tree.c
>    (cache_lookup): prevent unnecessary integer overflows in hash function

Hi Stefan,

I've been reading up on hash functions and am curious about this how 
overflow can reduce cache effectiveness.  Do you have any links or can 
offer an explanation?

Thanks,
Blair