Author: svn-role
Date: Tue Jul 9 04:00:44 2013
New Revision: 1501075
URL: http://svn.apache.org/r1501075
Log:
Merge the 1.8.x-r1495063 branch:
* ^/subversion/branches/1.8.x-r1495063
r1495806, r1495985
Fix crash in FSFS DAG caching code on strict-alignment architectures.
Also, improve hash hash effectiveness and efficiency.
Justification:
FSFS shouldn't crash.
See http://svn.haxx.se/dev/archive-2013-06/0432.shtml
Branch: 1.8.x-r1495063
Notes:
It took a while to figure out the "right way" to fix the hash function.
The branch takes all the individual back-and-forth changes and combines
them into one small patch.
Votes:
+1: stefan2, stsp, breser
Modified:
subversion/branches/1.8.x/ (props changed)
subversion/branches/1.8.x/STATUS
subversion/branches/1.8.x/subversion/libsvn_fs_fs/tree.c
Propchange: subversion/branches/1.8.x/
------------------------------------------------------------------------------
Merged
/subversion/trunk:r1495063,1495204,1495209,1495214,1495256,1495805,1495978
Merged /subversion/branches/1.8.x-r1495063:r1495804-1501074
Modified: subversion/branches/1.8.x/STATUS
URL:
http://svn.apache.org/viewvc/subversion/branches/1.8.x/STATUS?rev=1501075&r1=1501074&r2=1501075&view=diff
==============================================================================
--- subversion/branches/1.8.x/STATUS (original)
+++ subversion/branches/1.8.x/STATUS Tue Jul 9 04:00:44 2013
@@ -120,21 +120,6 @@ Veto-blocked changes:
Approved changes:
=================
- * ^/subversion/branches/1.8.x-r1495063
- r1495806, r1495985
- Fix crash in FSFS DAG caching code on strict-alignment architectures.
- Also, improve hash hash effectiveness and efficiency.
- Justification:
- FSFS shouldn't crash.
- See http://svn.haxx.se/dev/archive-2013-06/0432.shtml
- Branch: 1.8.x-r1495063
- Notes:
- It took a while to figure out the "right way" to fix the hash function.
- The branch takes all the individual back-and-forth changes and combines
- them into one small patch.
- Votes:
- +1: stefan2, stsp, breser
-
* r1499438, r1499447, r1499460, r1500695, r1500928
Make building with BDB 6 an opt-in feature.
In configure, do not warn if BDB was not found.
Modified: subversion/branches/1.8.x/subversion/libsvn_fs_fs/tree.c
URL:
http://svn.apache.org/viewvc/subversion/branches/1.8.x/subversion/libsvn_fs_fs/tree.c?rev=1501075&r1=1501074&r2=1501075&view=diff
==============================================================================
--- subversion/branches/1.8.x/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/branches/1.8.x/subversion/libsvn_fs_fs/tree.c Tue Jul 9
04:00:44 2013
@@ -151,7 +151,7 @@ typedef struct cache_entry_t
{
/* hash value derived from PATH, REVISION.
Used to short-circuit failed lookups. */
- long int hash_value;
+ apr_uint32_t hash_value;
/* revision to which the NODE belongs */
svn_revnum_t revision;
@@ -340,7 +340,12 @@ cache_lookup( fs_fs_dag_cache_t *cache
{
apr_size_t i, bucket_index;
apr_size_t path_len = strlen(path);
- long int hash_value = revision;
+ apr_uint32_t hash_value = (apr_uint32_t)revision;
+
+#if SVN_UNALIGNED_ACCESS_IS_OK
+ /* "randomizing" / distributing factor used in our hash function */
+ const apr_uint32_t factor = 0xd1f3da69;
+#endif
/* optimistic lookup: hit the same bucket again? */
cache_entry_t *result = &cache->buckets[cache->last_hit];
@@ -353,11 +358,25 @@ cache_lookup( fs_fs_dag_cache_t *cache
/* need to do a full lookup. Calculate the hash value
(HASH_VALUE has been initialized to REVISION). */
- for (i = 0; i + 4 <= path_len; i += 4)
- hash_value = hash_value * 0xd1f3da69 + *(const apr_uint32_t*)(path + i);
+ i = 0;
+#if SVN_UNALIGNED_ACCESS_IS_OK
+ /* We relax the dependency chain between iterations by processing
+ two chunks from the input per hash_value self-multiplication.
+ The HASH_VALUE update latency is now 1 MUL latency + 1 ADD latency
+ per 2 chunks instead of 1 chunk.
+ */
+ for (; i + 8 <= path_len; i += 8)
+ hash_value = hash_value * factor * factor
+ + ( *(const apr_uint32_t*)(path + i) * factor
+ + *(const apr_uint32_t*)(path + i + 4));
+#endif
for (; i < path_len; ++i)
- hash_value = hash_value * 33 + path[i];
+ /* Help GCC to minimize the HASH_VALUE update latency by splitting the
+ MUL 33 of the naive implementation: h = h * 33 + path[i]. This
+ shortens the dependency chain from 1 shift + 2 ADDs to 1 shift + 1 ADD.
+ */
+ hash_value = hash_value * 32 + (hash_value + (unsigned char)path[i]);
bucket_index = hash_value + (hash_value >> 16);
bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
