[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

[PATCH v3] Fix O(n) runtime in cache lookup, part 2/2

From: Stefan Fuhrmann <stefanfuhrmann_at_alice-dsl.de>
Date: Sun, 25 Apr 2010 00:20:19 +0200

Hi there,

this is a revised version of the patch posted here:
http://svn.haxx.se/dev/archive-2010-04/0107.shtml

Changes:

* use the new svn_cache__set_pinned function
* remove other changes that accidentally got added
  to the patch

-- Stefan^2.

[[[
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 937673)
+++ 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, pool));
   *id_p = dirent ? svn_fs_fs__id_copy(dirent->id, pool) : NULL;
 
   svn_pool_destroy(subpool);
@@ -435,10 +429,56 @@
     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_pool_t *node_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, 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 +794,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 937673)
+++ subversion/libsvn_fs_fs/dag.h (working copy)
@@ -304,6 +304,17 @@
                                         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. NODE_POOL is used for
+ any allocation of memory that needs to live as long as NODE lives.
+ */
+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_pool_t *node_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 937673)
+++ subversion/libsvn_fs_fs/fs_fs.c (working copy)
@@ -3669,6 +3670,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;
@@ -3682,8 +3684,15 @@
       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;
     }
@@ -3694,8 +3703,20 @@
   SVN_ERR(parse_dir_entries(&parsed_entries, unparsed_entries, pool));
 
   /* If this is an immutable directory, let's cache the contents. */
- if (! svn_fs_fs__id_txn_id(noderev->id))
- SVN_ERR(svn_cache__set(ffd->dir_cache, unparsed_id, parsed_entries, pool));
+ if (svn_fs_fs__id_txn_id(noderev->id))
+ {
+ /* The result has not been pinned. */
+ if (pin)
+ *pin = FALSE;
+ }
+ else
+ {
+ if (pin && *pin)
+ return svn_cache__set_pinned(ffd->dir_cache, unparsed_id, parsed_entries,
+ entries_p, pool);
+ else
+ SVN_ERR(svn_cache__set(ffd->dir_cache, unparsed_id, parsed_entries, pool));
+ }
 
   *entries_p = parsed_entries;
   return SVN_NO_ERROR;
@@ -4872,7 +4893,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,
@@ -5523,7 +5544,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 937673)
+++ 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-25 00:20:46 CEST

This is an archived mail posted to the Subversion Dev mailing list.