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 2015/10/24 20:07:22 UTC
svn commit: r1710368 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c
Author: stefan2
Date: Sat Oct 24 18:07:22 2015
New Revision: 1710368
URL: http://svn.apache.org/viewvc?rev=1710368&view=rev
Log:
Minor refactoring of FSFS' L1 dag node cache access.
Split lookup and insertion into two separate functions. That comes at
the cost of calculating the hash twice but allows us to delay the cache
auto-clear call until we actually have an L2 item that we can promote
to L1. The redcution in cache misses will often compensate for the hash
calculation overhead.
* subversion/libsvn_fs_fs/tree.c
(hash_func): Move out of cache_lookup.
(cache_lookup): Don't clear the entry when we found a mismatch and
return the node - if found - instead of the whole bucket.
(cache_insert): New function.
(dag_node_cache_get): Update and slightly simplify the caller.
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=1710368&r1=1710367&r2=1710368&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/tree.c Sat Oct 24 18:07:22 2015
@@ -209,17 +209,15 @@ auto_clear_dag_cache(fs_fs_dag_cache_t*
}
}
-/* For the given REVISION and PATH, return the respective entry in CACHE.
- If the entry is empty, its NODE member will be NULL and the caller
- may then set it to the corresponding DAG node allocated in CACHE->POOL.
+/* Returns a 32 bit hash value for the given REVISION and PATH of exactly
+ * PATH_LEN chars.
*/
-static cache_entry_t *
-cache_lookup( fs_fs_dag_cache_t *cache
- , svn_revnum_t revision
- , const char *path)
+static apr_uint32_t
+hash_func(svn_revnum_t revision,
+ const char *path,
+ apr_size_t path_len)
{
- apr_size_t i, bucket_index;
- apr_size_t path_len = strlen(path);
+ apr_size_t i;
apr_uint32_t hash_value = (apr_uint32_t)revision;
#if SVN_UNALIGNED_ACCESS_IS_OK
@@ -227,20 +225,7 @@ cache_lookup( fs_fs_dag_cache_t *cache
const apr_uint32_t factor = 0xd1f3da69;
#endif
- /* optimistic lookup: hit the same bucket again? */
- cache_entry_t *result = &cache->buckets[cache->last_hit];
- if ( (result->revision == revision)
- && (result->path_len == path_len)
- && !memcmp(result->path, path, path_len))
- {
- /* Remember the position of the last node we found in this cache. */
- if (result->node)
- cache->last_non_empty = cache->last_hit;
-
- return result;
- }
-
- /* need to do a full lookup. Calculate the hash value
+ /* Calculate the hash value
(HASH_VALUE has been initialized to REVISION).
Note that the actual hash function is arbitrary as long as its result
@@ -283,6 +268,37 @@ cache_lookup( fs_fs_dag_cache_t *cache
*/
hash_value = hash_value * 32 + (hash_value + (unsigned char)path[i]);
+ return hash_value;
+}
+
+/* For the given REVISION and PATH, return the respective node found in
+ * CACHE. If there is none, return NULL.
+ */
+static dag_node_t *
+cache_lookup( fs_fs_dag_cache_t *cache
+ , svn_revnum_t revision
+ , const char *path)
+{
+ apr_size_t bucket_index;
+ apr_size_t path_len = strlen(path);
+ apr_uint32_t hash_value;
+
+ /* optimistic lookup: hit the same bucket again? */
+ cache_entry_t *result = &cache->buckets[cache->last_hit];
+ if ( (result->revision == revision)
+ && (result->path_len == path_len)
+ && !memcmp(result->path, path, path_len))
+ {
+ /* Remember the position of the last node we found in this cache. */
+ if (result->node)
+ cache->last_non_empty = cache->last_hit;
+
+ return result->node;
+ }
+
+ /* need to do a full lookup. */
+ hash_value = hash_func(revision, path, path_len);
+
bucket_index = hash_value + (hash_value >> 16);
bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
@@ -297,16 +313,7 @@ cache_lookup( fs_fs_dag_cache_t *cache
|| (result->path_len != path_len)
|| memcmp(result->path, path, path_len))
{
- result->hash_value = hash_value;
- result->revision = revision;
- if (result->path_len < path_len)
- result->path = apr_palloc(cache->pool, path_len + 1);
- result->path_len = path_len;
- memcpy(result->path, path, path_len + 1);
-
- result->node = NULL;
-
- cache->insertions++;
+ return NULL;
}
else if (result->node)
{
@@ -315,7 +322,46 @@ cache_lookup( fs_fs_dag_cache_t *cache
cache->last_non_empty = bucket_index;
}
- return result;
+ return result->node;
+}
+
+/* Store a copy of NODE in CACHE, taking REVISION and PATH as key.
+ * This function will clean the cache at regular intervals.
+ */
+static void
+cache_insert(fs_fs_dag_cache_t *cache,
+ svn_revnum_t revision,
+ const char *path,
+ dag_node_t *node)
+{
+ apr_size_t bucket_index;
+ apr_size_t path_len = strlen(path);
+ apr_uint32_t hash_value;
+ cache_entry_t *entry;
+
+ auto_clear_dag_cache(cache);
+
+ /* calculate the bucket index to use */
+ hash_value = hash_func(revision, path, path_len);
+
+ bucket_index = hash_value + (hash_value >> 16);
+ bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
+
+ /* access the corresponding bucket and remember its location */
+ entry = &cache->buckets[bucket_index];
+ cache->last_hit = bucket_index;
+
+ /* if it is *NOT* a match, clear the bucket, expect the caller to fill
+ in the node and count it as an insertion */
+ entry->hash_value = hash_value;
+ entry->revision = revision;
+ if (entry->path_len < path_len)
+ entry->path = apr_palloc(cache->pool, path_len + 1);
+ entry->path_len = path_len;
+ memcpy(entry->path, path, path_len + 1);
+
+ entry->node = svn_fs_fs__dag_dup(node, cache->pool);
+ cache->insertions++;
}
/* Optimistic lookup using the last seen non-empty location in CACHE.
@@ -393,11 +439,9 @@ dag_node_cache_get(dag_node_t **node_p,
/* immutable DAG node. use the global caches for it */
fs_fs_data_t *ffd = root->fs->fsap_data;
- cache_entry_t *bucket;
- auto_clear_dag_cache(ffd->dag_node_cache);
- bucket = cache_lookup(ffd->dag_node_cache, root->rev, path);
- if (bucket->node == NULL)
+ node = cache_lookup(ffd->dag_node_cache, root->rev, path);
+ if (node == NULL)
{
locate_cache(&cache, &key, root, path, pool);
SVN_ERR(svn_cache__get((void **)&node, &found, cache, key, pool));
@@ -408,14 +452,13 @@ dag_node_cache_get(dag_node_t **node_p,
svn_fs_fs__dag_set_fs(node, root->fs);
/* Retain the DAG node in L1 cache. */
- bucket->node = svn_fs_fs__dag_dup(node,
- ffd->dag_node_cache->pool);
+ cache_insert(ffd->dag_node_cache, root->rev, path, node);
}
}
else
{
/* Copy the node from L1 cache into the passed-in POOL. */
- node = svn_fs_fs__dag_dup(bucket->node, pool);
+ node = svn_fs_fs__dag_dup(node, pool);
}
}
else