Hi devs,
this is a follow-up to the previous patch.
It uses the extended cache interface to
bring directory traversal times down from
O(N^2) to amortized O(N).
dir_entry_id_from_node now calls the new
svn_fs_fs__dag_dir_entry function that
duplicates only one entry instead of all
under the given node.
[[[
Allow for cache entries to be access directly, i.e. without
prior copying. Use that to fix FSFS directory traversal
runtime from O(N^2) to O(n).
* subversion/libsvn_fs_fs/dag.c
(dir_entry_id_from_node): call the new, efficient
lookup function.
(svn_fs_fs__dag_dir_entry): implement the new
lookup function
(svn_fs_fs__dag_dir_entries, svn_fs_fs__dag_delete):
adapt to svn_fs_fs__rep_contents_dir signature change
* subversion/libsvn_fs_fs/dag.h
(svn_fs_fs__dag_dir_entry): declare new function
* subversion/libsvn_fs_fs/fs_fs.c
(svn_fs_fs__rep_contents_dir): add support for optionally
returning a pinned cache reference instead of a copy.
(svn_fs_fs__set_entry, write_final_rev): adapt to
svn_fs_fs__rep_contents_dir signature change
* subversion/libsvn_fs_fs/fs_fs.h
(svn_fs_fs__rep_contents_dir): add pin parameter
patch by stefanfuhrmann < at > alice-dsl.de
]]]
Index: subversion/libsvn_fs_fs/dag.c
===================================================================
--- subversion/libsvn_fs_fs/dag.c (revision 930220)
+++ subversion/libsvn_fs_fs/dag.c (working copy)
@@ -310,16 +310,10 @@
const char *name,
apr_pool_t *pool)
{
- apr_hash_t *entries;
svn_fs_dirent_t *dirent;
apr_pool_t *subpool = svn_pool_create(pool);
- SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, parent, subpool, pool));
- if (entries)
- dirent = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
- else
- dirent = NULL;
-
+ SVN_ERR(svn_fs_fs__dag_dir_entry(&dirent, parent, name, subpool));
*id_p = dirent ? svn_fs_fs__id_copy(dirent->id, pool) : NULL;
svn_pool_destroy(subpool);
@@ -435,10 +429,55 @@
return svn_error_create(SVN_ERR_FS_NOT_DIRECTORY, NULL,
_("Can't get entries of non-directory"));
- return svn_fs_fs__rep_contents_dir(entries, node->fs, noderev, pool);
+ return svn_fs_fs__rep_contents_dir(entries, node->fs, noderev, NULL, pool);
}
+svn_error_t *
+svn_fs_fs__dag_dir_entry(svn_fs_dirent_t **dirent,
+ dag_node_t *node,
+ const char* name,
+ apr_pool_t *pool)
+{
+ apr_hash_t *entries;
+ node_revision_t *noderev;
+ fs_fs_data_t *ffd;
+ svn_boolean_t pinned = TRUE;
+ svn_fs_dirent_t *entry;
+ SVN_ERR(get_node_revision(&noderev, node, pool));
+
+ if (noderev->kind != svn_node_dir)
+ return svn_error_create(SVN_ERR_FS_NOT_DIRECTORY, NULL,
+ _("Can't get entries of non-directory"));
+
+ /* Get a dirent hash for this directory. */
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, node->fs, noderev,
+ &pinned, pool));
+
+ /* Find name in the ENTRIES hash. */
+ entry = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
+
+ /* Duplicate the result. */
+ if (entry)
+ {
+ svn_fs_dirent_t *new_entry = apr_palloc(pool, sizeof(*entry));
+ new_entry->name = apr_pstrdup(pool, entry->name);
+ new_entry->kind = entry->kind;
+ new_entry->id = svn_fs_fs__id_copy(entry->id, pool);
+
+ *dirent = new_entry;
+ }
+ else
+ *dirent = NULL;
+
+ /* Cleanup, if necessary */
+ ffd = node->fs->fsap_data;
+ return pinned
+ ? svn_cache__unpin((void **) entries, ffd->dir_cache, pool)
+ : SVN_NO_ERROR;
+}
+
+
svn_error_t *
svn_fs_fs__dag_set_entry(dag_node_t *node,
const char *entry_name,
@@ -769,7 +808,7 @@
subpool = svn_pool_create(pool);
/* Get a dirent hash for this directory. */
- SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev, subpool));
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev, NULL, subpool));
/* Find name in the ENTRIES hash. */
dirent = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
Index: subversion/libsvn_fs_fs/dag.h
===================================================================
--- subversion/libsvn_fs_fs/dag.h (revision 930220)
+++ subversion/libsvn_fs_fs/dag.h (working copy)
@@ -304,6 +304,14 @@
apr_pool_t *pool,
apr_pool_t *node_pool);
+/* Fetches the NODE's entries and returns a copy of the entry selected
+ by the key value given in NAME and set *DIRENT to a copy of that
+ entry. If such entry was found, the copy will be allocated in POOL.
+ Otherwise, the *DIRENT will be set to NULL. */
+svn_error_t * svn_fs_fs__dag_dir_entry(svn_fs_dirent_t **dirent,
+ dag_node_t *node,
+ const char* name,
+ apr_pool_t *pool);
/* Set ENTRY_NAME in NODE to point to ID (with kind KIND), allocating
from POOL. NODE must be a mutable directory. ID can refer to a
Index: subversion/libsvn_fs_fs/fs_fs.c
===================================================================
--- subversion/libsvn_fs_fs/fs_fs.c (revision 930220)
+++ subversion/libsvn_fs_fs/fs_fs.c (working copy)
@@ -3664,6 +3664,7 @@
svn_fs_fs__rep_contents_dir(apr_hash_t **entries_p,
svn_fs_t *fs,
node_revision_t *noderev,
+ svn_boolean_t* pin,
apr_pool_t *pool)
{
fs_fs_data_t *ffd = fs->fsap_data;
@@ -3677,12 +3678,24 @@
svn_boolean_t found;
unparsed_id = svn_fs_fs__id_unparse(noderev->id, pool)->data;
- SVN_ERR(svn_cache__get((void **) entries_p, &found, ffd->dir_cache,
- unparsed_id, pool));
+
+ /* Cache lookup. Get a pinned reference if *pin has been set. */
+ if (pin && *pin)
+ SVN_ERR(svn_cache__get_pinned((void **) entries_p, &found, ffd->dir_cache,
+ unparsed_id, pool));
+ else
+ SVN_ERR(svn_cache__get((void **) entries_p, &found, ffd->dir_cache,
+ unparsed_id, pool));
+
if (found)
return SVN_NO_ERROR;
}
+ /* not in cache (yet)
+ -> nothing has been pinned and nothing will be pinned this time. */
+ if (pin)
+ *pin = FALSE;
+
/* Read in the directory hash. */
unparsed_entries = apr_hash_make(pool);
SVN_ERR(get_dir_contents(unparsed_entries, fs, noderev, pool));
@@ -4867,7 +4880,7 @@
/* Before we can modify the directory, we need to dump its old
contents into a mutable representation file. */
SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev,
- subpool));
+ NULL, subpool));
SVN_ERR(unparse_dir_entries(&entries, entries, subpool));
SVN_ERR(svn_io_file_open(&file, filename,
APR_WRITE | APR_CREATE | APR_BUFFERED,
@@ -5518,7 +5531,7 @@
/* This is a directory. Write out all the children first. */
subpool = svn_pool_create(pool);
- SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, noderev, pool));
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, noderev, NULL, pool));
for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi))
{
Index: subversion/libsvn_fs_fs/fs_fs.h
===================================================================
--- subversion/libsvn_fs_fs/fs_fs.h (revision 930220)
+++ subversion/libsvn_fs_fs/fs_fs.h (working copy)
@@ -115,10 +115,16 @@
/* Set *ENTRIES to an apr_hash_t of dirent structs that contain the
directory entries of node-revision NODEREV in filesystem FS. The
returned table (and its keys and values) is allocated in POOL,
- which is also used for temporary allocations. */
+ which is also used for temporary allocations.
+ If *pin is TRUE, directory entries that have already been cached
+ will be returned as pinned references instead of copies. Otherwise,
+ pin may be NULL. After the function returned, *pin will then indicate
+ whether the cache lookup was successful and the caller must unpin
+ the *entries explicitly, in that case. */
svn_error_t *svn_fs_fs__rep_contents_dir(apr_hash_t **entries,
svn_fs_t *fs,
node_revision_t *noderev,
+ svn_boolean_t* pin,
apr_pool_t *pool);
/* Set *CONTENTS to be a readable svn_stream_t that receives the text
Received on 2010-04-06 19:56:43 CEST