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

[PATCH][libsvn_wc] Issue 2607: Post-commit working copy processing exhibits O(n^2) behaviour

From: Erik Huelsmann <ehuels_at_gmail.com>
Date: 2006-09-19 00:38:02 CEST

Well, the patch below addresses the problem in issue 2607.

I've whipped this patch together this evening, so, I could use some
review (and comments about the idea), but, even at this
proof-of-concept level, the run-time of the test script seems to have
halved on my machine.

Here's the log and patch:
[[[
Resolve issue 2607: post-commit processing exhibits O(n^2) behavior.

* subversion/include/svn_wc.h
* subversion/libsvn_wc/adm_ops.c
  (svn_wc_committed_queue_t): New type for commit item queues.
  (svn_wc_queue_committed): New. Adds a new item to the committed items
   queue. Optionally does required initialization.
  (svn_wc_process_committed_queue): New. Processes (with O(n) behavior)
   the queue of committed items, running all log files (which causes
   the entry file to be rewritten) as a last step.

* subversion/libsvn_wc/adm_ops.c
  (process_committed_internal): New. Abstracted out of
   svn_wc_process_committed4 to serve as a base for
   svn_wc_process_committed_queue too. Changed to account for the fact
   that the base log number may not start at 0 anymore.
  (commit_queue_item_t): New. Structure to store parameters for each
   committed item.

* subversion/libsvn_client/commit.c
  (svn_client_commit4): Adapted to use the new queued post-commit
   processing functions.
]]]

Index: subversion/include/svn_wc.h
===================================================================
--- subversion/include/svn_wc.h (revision 21524)
+++ subversion/include/svn_wc.h (working copy)
@@ -2308,7 +2308,53 @@

 /* Commits. */

+
 /**
+ * Storage type for queued post-commit data.
+ *
+ * @since New in 1.5.
+ */
+typedef void svn_wc_committed_queue_t;
+
+
+/**
+ * Queue committed items to be processed later by
+ * svn_wc_process_committed_queue().
+ *
+ * The first time this function is called, @a *queue should
+ * be @c NULL to signal that initialization is required.
+ *
+ * All pointer data passed to this function (@a path, @a wcprop_changes
+ * and @a digest) should remain valid until the queue has been
+ * processed by svn_wc_process_committed_queue().
+ *
+ * @since New in 1.5.
+ */
+svn_error_t *
+svn_wc_queue_committed(svn_wc_committed_queue_t **queue,
+ const char *path,
+ svn_boolean_t recurse,
+ svn_boolean_t remove_lock,
+ apr_array_header_t *wcprop_changes,
+ const unsigned char *digest,
+ apr_pool_t *pool);
+
+
+/**
+ * Like svn_wc_process_committed4(), but batch processes
+ * items queued with svn_wc_queue_committed().
+ */
+svn_error_t *
+svn_wc_process_committed_queue(svn_wc_committed_queue_t *queue,
+ svn_wc_adm_access_t *adm_access,
+ svn_revnum_t new_revnum,
+ const char *rev_date,
+ const char *rev_author,
+ svn_boolean_t remove_changelist,
+ apr_pool_t *pool);
+
+
+/**
  * Bump a successfully committed absolute @a path to @a new_revnum after a
  * commit succeeds. @a rev_date and @a rev_author are the (server-side)
  * date and author of the new revision; one or both may be @c NULL.
Index: subversion/libsvn_wc/adm_ops.c
===================================================================
--- subversion/libsvn_wc/adm_ops.c (revision 21524)
+++ subversion/libsvn_wc/adm_ops.c (working copy)
@@ -26,6 +26,7 @@
 #include <string.h>

 #include <apr_pools.h>
+#include <apr_tables.h>
 #include <apr_hash.h>
 #include <apr_md5.h>
 #include <apr_file_io.h>
@@ -468,22 +469,21 @@
 }

-svn_error_t *
-svn_wc_process_committed4(const char *path,
- svn_wc_adm_access_t *adm_access,
- svn_boolean_t recurse,
- svn_revnum_t new_revnum,
- const char *rev_date,
- const char *rev_author,
- apr_array_header_t *wcprop_changes,
- svn_boolean_t remove_lock,
- svn_boolean_t remove_changelist,
- const unsigned char *digest,
- apr_pool_t *pool)
+static svn_error_t *
+process_committed_internal(int *log_number,
+ const char *path,
+ svn_wc_adm_access_t *adm_access,
+ svn_boolean_t recurse,
+ svn_revnum_t new_revnum,
+ const char *rev_date,
+ const char *rev_author,
+ apr_array_header_t *wcprop_changes,
+ svn_boolean_t remove_lock,
+ svn_boolean_t remove_changelist,
+ const unsigned char *digest,
+ apr_pool_t *pool)
 {
- int log_number = 1;
-
- SVN_ERR(process_committed_leaf(0, path, adm_access, &recurse,
+ SVN_ERR(process_committed_leaf((*log_number)++, path, adm_access, &recurse,
                                  new_revnum, rev_date, rev_author,
                                  wcprop_changes,
                                  remove_lock, remove_changelist,
@@ -513,11 +513,11 @@
           apr_hash_this(hi, &key, NULL, &val);
           name = key;
           current_entry = val;
-
+
           /* Ignore the "this dir" entry. */
           if (! strcmp(name, SVN_WC_ENTRY_THIS_DIR))
             continue;
-
+
           /* Create child path by telescoping the main path. */
           this_path = svn_path_join(path, name, subpool);

@@ -526,7 +526,7 @@
                                         subpool));
           else
              child_access = adm_access;
-
+
           /* Recurse, but only allow further recursion if the child is
              a directory. Pass null for wcprop_changes, because the
              ones present in the current call are only applicable to
@@ -539,7 +539,7 @@
                      remove_changelist, NULL, subpool));
           else
             SVN_ERR(process_committed_leaf
- (log_number++, this_path, adm_access, NULL,
+ ((*log_number)++, this_path, adm_access, NULL,
                      new_revnum, rev_date, rev_author, NULL, FALSE,
                      remove_changelist, NULL, subpool));
         }
@@ -547,6 +547,134 @@
       svn_pool_destroy(subpool);
    }

+ return SVN_NO_ERROR;
+}
+
+typedef struct commit_queue_item_t
+{
+ const char *path;
+ svn_boolean_t recurse;
+ svn_boolean_t remove_lock;
+ apr_array_header_t *wcprop_changes;
+ const char *digest;
+} commit_queue_item_t;
+
+
+svn_error_t *
+svn_wc_queue_committed(svn_wc_committed_queue_t **queue,
+ const char *path,
+ svn_boolean_t recurse,
+ svn_boolean_t remove_lock,
+ apr_array_header_t *wcprop_changes,
+ const unsigned char *digest,
+ apr_pool_t *pool)
+{
+ commit_queue_item_t *cqi;
+ /*
+ Build an array with records with paths and options, in order to
+ */
+ if (! *queue)
+ /*###FIXME: I'd *love* a better estimate than 40, but...
+ how?! */
+ *queue = apr_array_make(pool, 40, sizeof(cqi));
+
+ cqi = apr_palloc(pool, sizeof(*cqi));
+ cqi->path = path;
+ cqi->recurse = recurse;
+ cqi->remove_lock = remove_lock;
+ cqi->wcprop_changes = wcprop_changes;
+ cqi->digest = digest;
+
+ APR_ARRAY_PUSH((apr_array_header_t *)*queue,commit_queue_item_t *) = cqi;
+
+ return SVN_NO_ERROR;
+}
+
+
+svn_error_t *
+svn_wc_process_committed_queue(svn_wc_committed_queue_t *queue,
+ svn_wc_adm_access_t *adm_access,
+ svn_revnum_t new_revnum,
+ const char *rev_date,
+ const char *rev_author,
+ svn_boolean_t remove_changelist,
+ apr_pool_t *pool)
+{
+ int i;
+ apr_hash_t *updated_dirs = apr_hash_make(pool);
+ apr_pool_t *iterpool = svn_pool_create(pool);
+ apr_hash_index_t *hi;
+
+ /* Now, we write all log files ... */
+ for (i = 0; i < ((apr_array_header_t *)queue)->nelts; i++)
+ {
+ int next_lognum;
+ const char *this_path;
+ svn_wc_adm_access_t *this_access;
+ commit_queue_item_t *cqi
+ = APR_ARRAY_IDX((apr_array_header_t *)queue, i,
commit_queue_item_t *);+
+ apr_pool_clear(iterpool);
+
+ SVN_ERR(svn_wc_adm_probe_retrieve(&this_access,
+ adm_access,
+ cqi->path, iterpool));
+ this_path = svn_wc_adm_access_path(this_access);
+ next_lognum = (int)apr_hash_get(updated_dirs,
+ this_path, APR_HASH_KEY_STRING);
+ SVN_ERR(process_committed_internal(&next_lognum, cqi->path,
+ this_access, cqi->recurse,
+ new_revnum, rev_date, rev_author,
+ cqi->wcprop_changes,
+ cqi->remove_lock, remove_changelist,
+ cqi->digest, iterpool));
+ apr_hash_set(updated_dirs, this_path, APR_HASH_KEY_STRING,
+ (const void *)next_lognum);
+ }
+
+ /* ... and then we run them ... */
+ for (hi = apr_hash_first(pool, updated_dirs); hi; hi = apr_hash_next(hi))
+ {
+ const void *key;
+ void *val;
+ const char *adm_path;
+ svn_wc_adm_access_t *this_access;
+
+ apr_pool_clear(iterpool);
+
+ apr_hash_this(hi, &key, NULL, &val);
+ adm_path = key;
+ SVN_ERR(svn_wc_adm_retrieve(&this_access,
+ adm_access, adm_path, iterpool));
+ SVN_ERR(svn_wc__run_log(this_access, NULL, iterpool));
+ }
+
+ ((apr_array_header_t *)queue)->nelts = 0;
+
+ return SVN_NO_ERROR;
+}
+
+svn_error_t *
+svn_wc_process_committed4(const char *path,
+ svn_wc_adm_access_t *adm_access,
+ svn_boolean_t recurse,
+ svn_revnum_t new_revnum,
+ const char *rev_date,
+ const char *rev_author,
+ apr_array_header_t *wcprop_changes,
+ svn_boolean_t remove_lock,
+ svn_boolean_t remove_changelist,
+ const unsigned char *digest,
+ apr_pool_t *pool)
+{
+ int log_number = 0;
+
+ SVN_ERR(process_committed_internal(&log_number,
+ path, adm_access, recurse,
+ new_revnum, rev_date, rev_author,
+ wcprop_changes, remove_lock,
+ remove_changelist, digest, pool));
+
   /* Run the log file(s) we just created. */
   SVN_ERR(svn_wc__run_log(adm_access, NULL, pool));

Index: subversion/libsvn_client/commit.c
===================================================================
--- subversion/libsvn_client/commit.c (revision 21524)
+++ subversion/libsvn_client/commit.c (working copy)
@@ -1523,6 +1523,7 @@
       || (cmt_err->apr_err == SVN_ERR_REPOS_POST_COMMIT_HOOK_FAILED))
     {
       apr_pool_t *subpool = svn_pool_create(pool);
+ svn_wc_committed_queue_t *queue = NULL;

       /* Make a note that our commit is finished. */
       commit_in_progress = FALSE;
@@ -1599,23 +1600,24 @@
           remove_lock = (! keep_locks && (item->state_flags
                                           &
SVN_CLIENT_COMMIT_ITEM_LOCK_TOKEN));
           assert(*commit_info_p);
- if ((bump_err = svn_wc_process_committed4
- (item->path, adm_access,
- loop_recurse,
- (*commit_info_p)->revision,
- (*commit_info_p)->date,
- (*commit_info_p)->author,
+ if ((bump_err = svn_wc_queue_committed
+ (&queue, item->path, loop_recurse, remove_lock,
                 item->wcprop_changes,
- remove_lock,
- (! keep_changelist),
- apr_hash_get(digests, item->path, APR_HASH_KEY_STRING),
- subpool)))
+ apr_hash_get(digests, item->path,
APR_HASH_KEY_STRING), pool))) break;

         }

       /* Destroy the subpool. */
       svn_pool_destroy(subpool);
+
+ bump_err =
+ svn_wc_process_committed_queue (queue, base_dir_access,
+ (*commit_info_p)->revision,
+ (*commit_info_p)->date,
+ (*commit_info_p)->author,
+ (! keep_changelist),
+ pool);
     }

   /* Sleep to ensure timestamp integrity. */

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Sep 19 00:38:20 2006

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

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.