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/07/25 15:12:26 UTC
svn commit: r1506955 - in /subversion/branches/fsfs-improvements/subversion:
include/svn_fs.h libsvn_fs/fs-loader.c libsvn_fs/fs-loader.h
libsvn_fs_base/tree.c libsvn_fs_fs/pack.c libsvn_fs_fs/pack.h
libsvn_fs_fs/tree.c libsvn_repos/reporter.c
Author: stefan2
Date: Thu Jul 25 13:12:26 2013
New Revision: 1506955
URL: http://svn.apache.org/r1506955
Log:
On the fsfs-improvements branch: Introduce the concept of "optimal
tree traversal order". Add an FS vtable entry that allows an FS to
suggest an order in which entries of a given directory should be
visited to maximize FS-internal efficiency.
Implement that for FSFS as well as BDB backends and use in the
libsvn_repos reporter to determine the order in which directories
will be traversed.
* subversion/include/svn_fs.h
(svn_fs_dir_optimal_order): declare new public FS API function
* subversion/libsvn_fs/fs-loader.h
(root_vtable): add new entry
* subversion/libsvn_fs/fs-loader.c
(svn_fs_dir_optimal_order): implement new FS API function
* subversion/libsvn_fs_base/tree.c
(base_dir_optimal_order): trivial implementation
(root_vtable): add entry
* subversion/libsvn_fs_fs/pack.h
(svn_fs_fs__order_dir_entries): declare new private API
* subversion/libsvn_fs_fs/pack.c
(compare_dir_entries_format6,
svn_fs_fs__order_dir_entries): implement it aiming for disk locality
* subversion/libsvn_fs_fs/tree.c
(fs_dir_optimal_order): new, forward to internal API
(root_vtable): add new entry
* subversion/libsvn_repos/reporter.c
(delta_dirs): walk dirs in suggested order
Modified:
subversion/branches/fsfs-improvements/subversion/include/svn_fs.h
subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.c
subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.h
subversion/branches/fsfs-improvements/subversion/libsvn_fs_base/tree.c
subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.c
subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.h
subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/tree.c
subversion/branches/fsfs-improvements/subversion/libsvn_repos/reporter.c
Modified: subversion/branches/fsfs-improvements/subversion/include/svn_fs.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/include/svn_fs.h?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/include/svn_fs.h (original)
+++ subversion/branches/fsfs-improvements/subversion/include/svn_fs.h Thu Jul 25 13:12:26 2013
@@ -1823,6 +1823,19 @@ svn_fs_dir_entries(apr_hash_t **entries_
const char *path,
apr_pool_t *pool);
+/** Take the #svn_fs_dirent_t structures in @a entries as returned by
+ * #svn_fs_dir_entries for @a root and determine an optimized ordering
+ * in which data access would most likely be efficient. Set @a *ordered_p
+ * to a newly allocated APR array of pointers to these #svn_fs_dirent_t
+ * structures. Allocate the array (but not its contents) in @a pool.
+ *
+ * @since New in 1.9.
+ */
+svn_error_t *
+svn_fs_dir_optimal_order(apr_array_header_t **ordered_p,
+ svn_fs_root_t *root,
+ apr_hash_t *entries,
+ apr_pool_t *pool);
/** Create a new directory named @a path in @a root. The new directory has
* no entries, and no properties. @a root must be the root of a transaction,
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.c?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.c (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.c Thu Jul 25 13:12:26 2013
@@ -1173,6 +1173,16 @@ svn_fs_dir_entries(apr_hash_t **entries_
}
svn_error_t *
+svn_fs_dir_optimal_order(apr_array_header_t **ordered_p,
+ svn_fs_root_t *root,
+ apr_hash_t *entries,
+ apr_pool_t *pool)
+{
+ return svn_error_trace(root->vtable->dir_optimal_order(ordered_p, root,
+ entries, pool));
+}
+
+svn_error_t *
svn_fs_make_dir(svn_fs_root_t *root, const char *path, apr_pool_t *pool)
{
SVN_ERR(svn_fs__path_valid(path, pool));
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.h?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.h (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs/fs-loader.h Thu Jul 25 13:12:26 2013
@@ -322,6 +322,10 @@ typedef struct root_vtable_t
/* Directories */
svn_error_t *(*dir_entries)(apr_hash_t **entries_p, svn_fs_root_t *root,
const char *path, apr_pool_t *pool);
+ svn_error_t *(*dir_optimal_order)(apr_array_header_t **ordered_p,
+ svn_fs_root_t *root,
+ apr_hash_t *entries,
+ apr_pool_t *pool);
svn_error_t *(*make_dir)(svn_fs_root_t *root, const char *path,
apr_pool_t *pool);
svn_error_t *(*copy)(svn_fs_root_t *from_root, const char *from_path,
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs_base/tree.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs_base/tree.c?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs_base/tree.c (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs_base/tree.c Thu Jul 25 13:12:26 2013
@@ -1561,6 +1561,23 @@ base_dir_entries(apr_hash_t **table_p,
return SVN_NO_ERROR;
}
+static svn_error_t *
+base_dir_optimal_order(apr_array_header_t **ordered_p,
+ svn_fs_root_t *root,
+ apr_hash_t *entries,
+ apr_pool_t *pool)
+{
+ /* 1:1 copy of entries with no differnce in ordering */
+ apr_hash_index_t *hi;
+ apr_array_header_t *result = apr_array_make(pool, apr_hash_count(entries),
+ sizeof(svn_fs_dirent_t *));
+ for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi))
+ APR_ARRAY_PUSH(result, svn_fs_dirent_t *) = svn__apr_hash_index_val(hi);
+
+ *ordered_p = result;
+ return SVN_NO_ERROR;
+}
+
/* Merges and commits. */
@@ -5384,6 +5401,7 @@ static root_vtable_t root_vtable = {
base_change_node_prop,
base_props_changed,
base_dir_entries,
+ base_dir_optimal_order,
base_make_dir,
base_copy,
base_revision_link,
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.c?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.c (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.c Thu Jul 25 13:12:26 2013
@@ -41,6 +41,51 @@
#include "svn_private_config.h"
#include "temp_serializer.h"
+/* Directories entries sorted by revision (decreasing - to max cache hits)
+ * and offset (increasing - to max benefit from APR file buffering).
+ */
+static int
+compare_dir_entries_format6(const svn_sort__item_t *a,
+ const svn_sort__item_t *b)
+{
+ const svn_fs_dirent_t *lhs = (const svn_fs_dirent_t *) a->value;
+ const svn_fs_dirent_t *rhs = (const svn_fs_dirent_t *) b->value;
+
+ const svn_fs_fs__id_part_t *lhs_rev_item
+ = svn_fs_fs__id_rev_offset(lhs->id);
+ const svn_fs_fs__id_part_t *rhs_rev_item
+ = svn_fs_fs__id_rev_offset(rhs->id);
+
+ /* decreasing ("reverse") order on revs */
+ if (lhs_rev_item->revision != rhs_rev_item->revision)
+ return lhs_rev_item->revision > rhs_rev_item->revision ? -1 : 1;
+
+ /* increasing order on offsets */
+ if (lhs_rev_item->number != rhs_rev_item->number)
+ return lhs_rev_item->number > rhs_rev_item->number ? 1 : -1;
+
+ return 0;
+}
+
+apr_array_header_t *
+svn_fs_fs__order_dir_entries(svn_fs_t *fs,
+ apr_hash_t *directory,
+ apr_pool_t *pool)
+{
+ apr_array_header_t *ordered
+ = svn_sort__hash(directory, compare_dir_entries_format6, pool);
+
+ apr_array_header_t *result
+ = apr_array_make(pool, ordered->nelts, sizeof(svn_fs_dirent_t *));
+
+ int i;
+ for (i = 0; i < ordered->nelts; ++i)
+ APR_ARRAY_PUSH(result, svn_fs_dirent_t *)
+ = APR_ARRAY_IDX(ordered, i, svn_sort__item_t).value;
+
+ return result;
+}
+
/* Given REV in FS, set *REV_OFFSET to REV's offset in the packed file.
Use POOL for temporary allocations. */
svn_error_t *
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.h?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.h (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/pack.h Thu Jul 25 13:12:26 2013
@@ -50,4 +50,14 @@ svn_fs_fs__get_packed_offset(apr_off_t *
svn_revnum_t rev,
apr_pool_t *pool);
+/* Return the svn_dir_entry_t* objects of DIRECTORY in an APR array
+ * allocated in POOL with entries added in storage (on-disk) order.
+ * FS format will be used to pick the optimal ordering strategy.
+ */
+apr_array_header_t *
+svn_fs_fs__order_dir_entries(svn_fs_t *fs,
+ apr_hash_t *directory,
+ apr_pool_t *pool);
+
+
#endif
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/tree.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/tree.c?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_fs_fs/tree.c Thu Jul 25 13:12:26 2013
@@ -57,6 +57,7 @@
#include "tree.h"
#include "fs_fs.h"
#include "id.h"
+#include "pack.h"
#include "temp_serializer.h"
#include "transaction.h"
@@ -2235,6 +2236,17 @@ fs_dir_entries(apr_hash_t **table_p,
return svn_fs_fs__dag_dir_entries(table_p, node, pool);
}
+static svn_error_t *
+fs_dir_optimal_order(apr_array_header_t **ordered_p,
+ svn_fs_root_t *root,
+ apr_hash_t *entries,
+ apr_pool_t *pool)
+{
+ *ordered_p = svn_fs_fs__order_dir_entries(root->fs, entries, pool);
+
+ return SVN_NO_ERROR;
+}
+
/* Raise an error if PATH contains a newline because FSFS cannot handle
* such paths. See issue #4340. */
static svn_error_t *
@@ -4126,6 +4138,7 @@ static root_vtable_t root_vtable = {
fs_change_node_prop,
fs_props_changed,
fs_dir_entries,
+ fs_dir_optimal_order,
fs_make_dir,
fs_copy,
fs_revision_link,
Modified: subversion/branches/fsfs-improvements/subversion/libsvn_repos/reporter.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-improvements/subversion/libsvn_repos/reporter.c?rev=1506955&r1=1506954&r2=1506955&view=diff
==============================================================================
--- subversion/branches/fsfs-improvements/subversion/libsvn_repos/reporter.c (original)
+++ subversion/branches/fsfs-improvements/subversion/libsvn_repos/reporter.c Thu Jul 25 13:12:26 2013
@@ -1143,6 +1143,8 @@ delta_dirs(report_baton_t *b, svn_revnum
apr_hash_t *s_entries = NULL, *t_entries;
apr_hash_index_t *hi;
apr_pool_t *subpool;
+ apr_array_header_t *t_ordered_entries = NULL;
+ int i;
/* Compare the property lists. If we're starting empty, pass a NULL
source path so that we add all the properties.
@@ -1275,9 +1277,12 @@ delta_dirs(report_baton_t *b, svn_revnum
}
/* Loop over the dirents in the target. */
- for (hi = apr_hash_first(pool, t_entries); hi; hi = apr_hash_next(hi))
+ SVN_ERR(svn_fs_dir_optimal_order(&t_ordered_entries, b->t_root,
+ t_entries, pool));
+ for (i = 0; i < t_ordered_entries->nelts; ++i)
{
- const svn_fs_dirent_t *t_entry = svn__apr_hash_index_val(hi);
+ const svn_fs_dirent_t *t_entry
+ = APR_ARRAY_IDX(t_ordered_entries, i, svn_fs_dirent_t *);
const svn_fs_dirent_t *s_entry;
const char *s_fullpath, *t_fullpath, *e_fullpath;