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 2014/12/15 08:28:27 UTC
svn commit: r1645586 - in /subversion/trunk/subversion/libsvn_fs_x: ./ tree.c
Author: stefan2
Date: Mon Dec 15 07:28:27 2014
New Revision: 1645586
URL: http://svn.apache.org/r1645586
Log:
Sync FSX with FSFS. Cleanly merge r1645567 from FSFS.
This ports the DAG walk speedups for ra_serf to FSX.
Modified:
subversion/trunk/subversion/libsvn_fs_x/ (props changed)
subversion/trunk/subversion/libsvn_fs_x/tree.c
Propchange: subversion/trunk/subversion/libsvn_fs_x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Mon Dec 15 07:28:27 2014
@@ -85,5 +85,5 @@
/subversion/branches/verify-at-commit/subversion/libsvn_fs_x:1462039-1462408
/subversion/branches/verify-keep-going/subversion/libsvn_fs_x:1439280-1492639,1546002-1546110
/subversion/branches/wc-collate-path/subversion/libsvn_fs_x:1402685-1480384
-/subversion/trunk/subversion/libsvn_fs_fs:1415133-1596500,1596567,1597414,1597989,1598273,1599140,1600872,1601633,1603485-1603487,1603499,1603605,1604128,1604188,1604413-1604414,1604416-1604417,1604421,1604442,1604700,1604717,1604720,1604726,1604755,1604794,1604802,1604824,1604836,1604844,1604902-1604903,1604911,1604925,1604933,1604947,1605059-1605060,1605064-1605065,1605068,1605071-1605073,1605075,1605123,1605188-1605189,1605191,1605197,1605444,1605633,1606132,1606142,1606144,1606514,1606526,1606528,1606551,1606554,1606564,1606598-1606599,1606656,1606658,1606662,1606744,1606840,1607085,1607572,1612407,1612810,1613339,1613872,1614611,1615348,1615351-1615352,1615356,1616338-1616339,1616613,1617586,1617688,1618138,1618151,1618153,1618226,1618641,1618653,1618662,1619068,1619358,1619413,1619769,1619774,1620602,1620909,1620912,1620928,1620930,1621275,1621635,1622931,1622937,1622942,1622946,1622959-1622960,1622963,1622987,1623007,1623368,1623373,1623377,1623379,1623381,1623398,1623402,162
4011,1624265,1624512,1626246,1626871,1626873,1626886,1627497-1627498,1627502,1627947-1627949,1627966,1628083,1628093,1628158-1628159,1628161,1628392-1628393,1628415,1628427,1628676,1628738,1628762,1628764,1629854-1629855,1629857,1629865,1629873,1629875,1629879,1630067,1630070,1631049-1631051,1631075,1631115,1631171,1631180,1631185-1631186,1631196-1631197,1631239-1631240,1631548,1631550,1631563,1631567,1631588,1631598,1632646,1632776,1632849,1632851-1632853,1632856-1632857,1632868,1632908,1632926,1633232,1633617-1633618,1634872,1634875,1634879-1634880,1634920,1636478,1636483,1636629,1637184,1637186,1637330,1637358,1637393,1639319,1639322,1639335,1639348,1639352,1639355,1639358,1639419,1639426,1639430,1639436,1639440,1639549,1640061,1640197,1640915,1641013,1643139,1643233
+/subversion/trunk/subversion/libsvn_fs_fs:1415133-1596500,1596567,1597414,1597989,1598273,1599140,1600872,1601633,1603485-1603487,1603499,1603605,1604128,1604188,1604413-1604414,1604416-1604417,1604421,1604442,1604700,1604717,1604720,1604726,1604755,1604794,1604802,1604824,1604836,1604844,1604902-1604903,1604911,1604925,1604933,1604947,1605059-1605060,1605064-1605065,1605068,1605071-1605073,1605075,1605123,1605188-1605189,1605191,1605197,1605444,1605633,1606132,1606142,1606144,1606514,1606526,1606528,1606551,1606554,1606564,1606598-1606599,1606656,1606658,1606662,1606744,1606840,1607085,1607572,1612407,1612810,1613339,1613872,1614611,1615348,1615351-1615352,1615356,1616338-1616339,1616613,1617586,1617688,1618138,1618151,1618153,1618226,1618641,1618653,1618662,1619068,1619358,1619413,1619769,1619774,1620602,1620909,1620912,1620928,1620930,1621275,1621635,1622931,1622937,1622942,1622946,1622959-1622960,1622963,1622987,1623007,1623368,1623373,1623377,1623379,1623381,1623398,1623402,162
4011,1624265,1624512,1626246,1626871,1626873,1626886,1627497-1627498,1627502,1627947-1627949,1627966,1628083,1628093,1628158-1628159,1628161,1628392-1628393,1628415,1628427,1628676,1628738,1628762,1628764,1629854-1629855,1629857,1629865,1629873,1629875,1629879,1630067,1630070,1631049-1631051,1631075,1631115,1631171,1631180,1631185-1631186,1631196-1631197,1631239-1631240,1631548,1631550,1631563,1631567,1631588,1631598,1632646,1632776,1632849,1632851-1632853,1632856-1632857,1632868,1632908,1632926,1633232,1633617-1633618,1634872,1634875,1634879-1634880,1634920,1636478,1636483,1636629,1637184,1637186,1637330,1637358,1637393,1639319,1639322,1639335,1639348,1639352,1639355,1639358,1639419,1639426,1639430,1639436,1639440,1639549,1640061,1640197,1640915,1641013,1643139,1643233,1645567
/subversion/trunk/subversion/libsvn_fs_x:1414756-1509914
Modified: subversion/trunk/subversion/libsvn_fs_x/tree.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_x/tree.c?rev=1645586&r1=1645585&r2=1645586&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_x/tree.c (original)
+++ subversion/trunk/subversion/libsvn_fs_x/tree.c Mon Dec 15 07:28:27 2014
@@ -203,6 +203,13 @@ struct fs_x_dag_cache_t
Thus, remember the last hit location for optimistic lookup. */
apr_size_t last_hit;
+ /* Position of the last bucket hit that actually had a DAG node in it.
+ LAST_HIT may refer to a bucket that matches path@rev but has not
+ its NODE element set, yet.
+ This value is a mere hint for optimistic lookup and any value is
+ valid (as long as it is < BUCKET_COUNT). */
+ apr_size_t last_non_empty;
+
/* List of receiving pools that are still alive. */
cache_lock_t *first_lock;
};
@@ -338,6 +345,10 @@ cache_lookup( fs_x_dag_cache_t *cache
&& (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;
}
@@ -388,10 +399,38 @@ cache_lookup( fs_x_dag_cache_t *cache
cache->insertions++;
}
+ else if (result->node)
+ {
+ /* This bucket is valid & has a suitable DAG node in it.
+ Remember its location. */
+ cache->last_non_empty = bucket_index;
+ }
return result;
}
+/* Optimistic lookup using the last seen non-empty location in CACHE.
+ Return the node of that entry, if it is still in use and matches PATH.
+ Return NULL otherwise. Since the caller usually already knows the path
+ length, provide it in PATH_LEN. */
+static dag_node_t *
+cache_lookup_last_path(fs_fs_dag_cache_t *cache,
+ const char *path,
+ apr_size_t path_len)
+{
+ cache_entry_t *result = &cache->buckets[cache->last_non_empty];
+ assert(strlen(path) == path_len);
+
+ if ( result->node
+ && (result->path_len == path_len)
+ && !memcmp(result->path, path, path_len))
+ {
+ return result->node;
+ }
+
+ return NULL;
+}
+
/* 2nd level cache */
/* Find and return the DAG node cache for ROOT and the key that
@@ -891,6 +930,56 @@ typedef enum open_path_flags_t {
open_path_allow_null = 8
} open_path_flags_t;
+/* Try a short-cut for the open_path() function using the last node accessed.
+ * If that ROOT is that nodes's "created rev" and PATH of PATH_LEN chars is
+ * its "created path", return the node in *NODE_P. Set it to NULL otherwise.
+ *
+ * This function is used to support ra_serf-style access patterns where we
+ * are first asked for path@rev and then for path@c_rev of the same node.
+ * The shortcut works by ignoring the "rev" part of the cache key and then
+ * checking whether we got lucky. Lookup and verification are both quick
+ * plus there are many early outs for common types of mismatch.
+ */
+static svn_error_t *
+try_match_last_node(dag_node_t **node_p,
+ svn_fs_root_t *root,
+ const char *path,
+ apr_size_t path_len,
+ apr_pool_t *scratch_pool)
+{
+ fs_fs_data_t *ffd = root->fs->fsap_data;
+
+ /* Optimistic lookup: if the last node returned from the cache applied to
+ the same PATH, return it in NODE. */
+ dag_node_t *node
+ = cache_lookup_last_path(ffd->dag_node_cache, path, path_len);
+
+ /* Did we get a bucket with a committed node? */
+ if (node && !svn_fs_fs__dag_check_mutable(node))
+ {
+ /* Get the path&rev pair at which this node was created.
+ This is repository location for which this node is _known_ to be
+ the right lookup result irrespective of how we found it. */
+ const char *created_path
+ = svn_fs_fs__dag_get_created_path(node);
+ svn_revnum_t revision;
+ SVN_ERR(svn_fs_fs__dag_get_revision(&revision, node, scratch_pool));
+
+ /* Is it an exact match? */
+ if (revision == root->rev && strcmp(created_path, path) == 0)
+ {
+ /* Cache it under its full path@rev access path. */
+ SVN_ERR(dag_node_cache_set(root, path, node, scratch_pool));
+
+ *node_p = node;
+ return SVN_NO_ERROR;
+ }
+ }
+
+ *node_p = NULL;
+ return SVN_NO_ERROR;
+}
+
/* Open the node identified by PATH in ROOT, allocating in POOL. Set
*PARENT_PATH_P to a path from the node up to ROOT. The resulting
@@ -938,20 +1027,55 @@ open_path(parent_path_t **parent_path_p,
at the respective position and replacing that with a '/' in the next
iteration. This is correct as we assert() PATH to be canonical. */
svn_stringbuf_t *path_so_far = svn_stringbuf_create(path, pool);
+ apr_size_t path_len = path_so_far->len;
- /* callers often traverse the tree in some path-based order. That means
- a sibling of PATH has been presently accessed. Try to start the lookup
- directly at the parent node, if the caller did not requested the full
- parent chain. */
+ /* Callers often traverse the DAG in some path-based order or along the
+ history segments. That allows us to try a few guesses about where to
+ find the next item. This is only useful if the caller didn't request
+ the full parent chain. */
assert(svn_fs__is_canonical_abspath(path));
path_so_far->len = 0; /* "" */
if (flags & open_path_node_only)
{
- const char *directory = svn_dirent_dirname(path, pool);
+ const char *directory;
+
+ /* First attempt: Assume that we access the DAG for the same path as
+ in the last lookup but for a different revision that happens to be
+ the last revision that touched the respective node. This is a
+ common pattern when e.g. checking out over ra_serf. Note that this
+ will only work for committed data as the revision info for nodes in
+ txns is bogus.
+
+ This shortcut is quick and will exit this function upon success.
+ So, try it first. */
+ if (!root->is_txn_root)
+ {
+ dag_node_t *node;
+ SVN_ERR(try_match_last_node(&node, root, path, path_len, iterpool));
+
+ /* Did the shortcut work? */
+ if (node)
+ {
+ /* Construct and return the result. */
+ svn_pool_destroy(iterpool);
+
+ parent_path = make_parent_path(node, 0, 0, pool);
+ parent_path->copy_inherit = copy_id_inherit_self;
+ *parent_path_p = parent_path;
+
+ return SVN_NO_ERROR;
+ }
+ }
+
+ /* Second attempt: Try starting the lookup immediately at the parent
+ node. We will often have recently accessed either a sibling or
+ said parent DIRECTORY itself for the same revision. */
+ directory = svn_dirent_dirname(path, pool);
if (directory[1] != 0) /* root nodes are covered anyway */
{
SVN_ERR(dag_node_cache_get(&here, root, directory, TRUE, pool));
- /* did the shortcut work? */
+
+ /* Did the shortcut work? */
if (here)
{
apr_size_t dirname_len = strlen(directory);