Mailing-List: contact commits-help@subversion.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@subversion.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1501075 - in /subversion/branches/1.8.x: ./ STATUS
 subversion/libsvn_fs_fs/tree.c
Date: Tue, 09 Jul 2013 04:00:45 -0000
To: commits@subversion.apache.org
From: svn-role@apache.org
Message-Id: <20130709040045.3DFE22388C3D@eris.apache.org>

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;