You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Dustin Lang <ds...@astro.princeton.edu> on 2012/05/29 21:09:08 UTC
[PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Hi,
This is my first time working on the subversion code, so be gentle :)
I believe the attached patch solves one component of #4134 ("svnadmin dump files
are not reproducible, due to APR 1.4.6 hash order changes"), namely that deleted
nodes are stored in a hash and dumped out in (now-arbitrary) hash iteration
order. This patch simply uses "svn_sort_hash" to get a sorted view of the keys
before dumping them.
I have verified that it runs valgrind-clean when "svnadmin dump"ing >700 revs of
the astrometry.net repo (and now my repo and its svnsync'd mirror produce
exactly equal dumps, hoorah), but I don't really know if I've used the apr
infrastructure appropriately.
I don't know whether this completely solves #4134; it works for me, but my repo
is simple.
cheers,
dustin
http://subversion.tigris.org/issues/show_bug.cgi?id=4134
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Stefan Sperling <st...@elego.de>.
On Thu, May 31, 2012 at 07:12:08PM +0100, Julian Foad wrote:
> Stefan Sperling wrote:
>
> > On Wed, May 30, 2012 at 07:55:34AM +0100, Julian Foad wrote:
> >> If you're using _lexically on these paths, please explain this in a
> >> comment, otherwise this will be confusing to readers.
> >
> > Bert expanded the docstring of svn_sort_compare_items_lexically
> > in r1344158.
>
> No, he expanded docs of svn_path_compare_paths() and svn_sort_compare_items_as_paths().
>
> > I guess that addresses your concern?
>
> Not really; there's no direct links from this usage of _lexically() to
> Bert's comment, and I'm taking the fact that a to-and-fro email
> discussion occurred as evidence that it's not totally obvious.
>
Ah. Right, you're correct.
> > If so, I'll apply Dustin's patch unmodified.
>
> I'm only offering my opinion; I won't be offended if you think it's clear enough and go ahead without adding a comment.
I'll commit the patch and add the comment in a follow-up commit.
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Dustin Lang <ds...@astro.princeton.edu>.
> I think we'd also like to get output that is similar to what happened
> with ARP-1.4.5 (i.e. before the hash table randomness change in APR-1.4.6).
> I believe that was equivalent to lexical sort. The entries are hash keys,
> and the hash function in APR didn't result in the kind of ordering that
> svn_sort_compare_paths would choose.
Interesting, I hadn't thought of backward-compatibility as a real option; I
assumed that the hash table iterator would emit the entries sorted by their hash
values.
For what it's worth, here's what the old version of svnadmin I have kicking
around does:
> /usr/bin/svnadmin --version
svnadmin, version 1.6.6 (r40053)
...
> ls -l /usr/lib/libapr-1.so.0
lrwxrwxrwx 1 root root 17 May 25 2011 /usr/lib/libapr-1.so.0 -> libapr-1.so.0.3.8
dstn@apps3:~/svn-backup-astrometry
> ls -l /usr/lib/libaprutil-1.so.0
lrwxrwxrwx 1 root root 21 Nov 26 2010 /usr/lib/libaprutil-1.so.0 -> libaprutil-1.so.0.3.9
Node-path: trunk/documents/papers/archetypes/paper_plots/1qq.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/2qq.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/3qq.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/4qq.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/36gg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/12ggg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/66gg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/18lg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/55lg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/1gg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/2gg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/3gg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/103lg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/59lgg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/68lgg.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/36ggSLACS.ps
Node-path: trunk/documents/papers/archetypes/paper_plots/66ggSLACS.ps
Which sure isn't lexical :)
--dstn
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Stefan Sperling <st...@elego.de>.
On Thu, May 31, 2012 at 03:09:01PM -0400, Greg Stein wrote:
> Why ever would we want to rely in any way on a hash table iterator's order?
> What!?
You misunderstood what I wrote. I'm not suggesting we do so.
I was just assuming that the APR-1.4.5 resulted in lexically sorted
output (and apparently I was wrong about this, see Dustin's reply).
> We want a stable ordering. That generally means "sort" rather "hash table
> implementation details".
Yes, we agreed on that weeks ago.
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping them
Posted by Greg Stein <gs...@gmail.com>.
On May 31, 2012 2:52 PM, "Stefan Sperling" <st...@elego.de> wrote:
>
> On Thu, May 31, 2012 at 02:31:01PM -0400, Dustin Lang wrote:
> >
> > The point of this diff is to ensure that "svnadmin dump" lists the
> > deleted nodes in a consistent order between runs. At this point in
> > the code, we're just dealing with a list of strings, so it really
> > doesn't matter, we just need them in a consistent ordering.
> > lexically looks simpler and faster (not that this is
> > performance-critical).
>
> I think we'd also like to get output that is similar to what happened
> with ARP-1.4.5 (i.e. before the hash table randomness change in
APR-1.4.6).
> I believe that was equivalent to lexical sort. The entries are hash keys,
> and the hash function in APR didn't result in the kind of ordering that
> svn_sort_compare_paths would choose.
Why ever would we want to rely in any way on a hash table iterator's order?
What!?
We want a stable ordering. That generally means "sort" rather "hash table
implementation details".
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Stefan Sperling <st...@elego.de>.
On Thu, May 31, 2012 at 02:31:01PM -0400, Dustin Lang wrote:
>
> The point of this diff is to ensure that "svnadmin dump" lists the
> deleted nodes in a consistent order between runs. At this point in
> the code, we're just dealing with a list of strings, so it really
> doesn't matter, we just need them in a consistent ordering.
> lexically looks simpler and faster (not that this is
> performance-critical).
I think we'd also like to get output that is similar to what happened
with ARP-1.4.5 (i.e. before the hash table randomness change in APR-1.4.6).
I believe that was equivalent to lexical sort. The entries are hash keys,
and the hash function in APR didn't result in the kind of ordering that
svn_sort_compare_paths would choose.
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Dustin Lang <ds...@astro.princeton.edu>.
The point of this diff is to ensure that "svnadmin dump" lists the deleted nodes
in a consistent order between runs. At this point in the code, we're just
dealing with a list of strings, so it really doesn't matter, we just need them
in a consistent ordering. lexically looks simpler and faster (not that this is
performance-critical).
How about this comment:
// We just need the paths to be emitted in a consistent order, so lexical sort
// is fine (ie, we don't need svn_sort_compare_paths, but it work work too).
cheers,
--dstn
On Thu, 31 May 2012, Julian Foad wrote:
> Stefan Sperling wrote:
>
>> On Wed, May 30, 2012 at 07:55:34AM +0100, Julian Foad wrote:
>>> If you're using _lexically on these paths, please explain this in a
>>> comment, otherwise this will be confusing to readers.
>>
>> Bert expanded the docstring of svn_sort_compare_items_lexically
>> in r1344158.
>
> No, he expanded docs of svn_path_compare_paths() and svn_sort_compare_items_as_paths().
>
>> I guess that addresses your concern?
>
> Not really; there's no direct links from this usage of _lexically() to Bert's comment, and I'm taking the fact that a to-and-fro email discussion occurred as evidence that it's not totally obvious.
>
>> If so, I'll apply Dustin's patch unmodified.
>
> I'm only offering my opinion; I won't be offended if you think it's clear enough and go ahead without adding a comment.
>
> - Julian
>
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping them
Posted by Julian Foad <ju...@btopenworld.com>.
Stefan Sperling wrote:
> On Wed, May 30, 2012 at 07:55:34AM +0100, Julian Foad wrote:
>> If you're using _lexically on these paths, please explain this in a
>> comment, otherwise this will be confusing to readers.
>
> Bert expanded the docstring of svn_sort_compare_items_lexically
> in r1344158.
No, he expanded docs of svn_path_compare_paths() and svn_sort_compare_items_as_paths().
> I guess that addresses your concern?
Not really; there's no direct links from this usage of _lexically() to Bert's comment, and I'm taking the fact that a to-and-fro email discussion occurred as evidence that it's not totally obvious.
> If so, I'll apply Dustin's patch unmodified.
I'm only offering my opinion; I won't be offended if you think it's clear enough and go ahead without adding a comment.
- Julian
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Stefan Sperling <st...@elego.de>.
On Wed, May 30, 2012 at 07:55:34AM +0100, Julian Foad wrote:
> If you're using _lexically on these paths, please explain this in a comment, otherwise this will be confusing to readers.
Bert expanded the docstring of svn_sort_compare_items_lexically
in r1344158. I guess that addresses your concern? If so, I'll apply
Dustin's patch unmodified.
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping them
Posted by Julian Foad <ju...@btopenworld.com>.
Greg Stein wrote:
> On Tue, May 29, 2012 at 5:01 PM, Dustin Lang <ds...@astro.princeton.edu>
> wrote:
>> ...
>>> You can use svn_sort_compare_items_lexically because entries are single
>>> path components that do not contain slashes. In which case
>>> svn_sort_compare_items_as_paths produces the same result but is less
>>> efficient.
>>
>> The paths are like:
>>
>> trunk/documents/papers/archetypes/paper_plots/103lg.ps
>>
>> But I still believe you are right that lexical sort will work fine and is
>> simpler than svn_sort_compare_items_as_paths.
>
> Right. Everything up to the final '/' will match precisely, so only
> the children are being compared.
>
> More specifically, you are NOT sorting paths like:
>
> some/path
> some/path/more
> some/pathmore
>
> The sorting there is quite a bit different.
If you're using _lexically on these paths, please explain this in a comment, otherwise this will be confusing to readers.
- Julian
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping them
Posted by Greg Stein <gs...@gmail.com>.
On Tue, May 29, 2012 at 5:01 PM, Dustin Lang <ds...@astro.princeton.edu> wrote:
>...
>> You can use svn_sort_compare_items_lexically because entries are single
>> path components that do not contain slashes. In which case
>> svn_sort_compare_items_as_paths produces the same result but is less
>> efficient.
>
> The paths are like:
>
> trunk/documents/papers/archetypes/paper_plots/103lg.ps
>
> But I still believe you are right that lexical sort will work fine and is
> simpler than svn_sort_compare_items_as_paths.
Right. Everything up to the final '/' will match precisely, so only
the children are being compared.
More specifically, you are NOT sorting paths like:
some/path
some/path/more
some/pathmore
The sorting there is quite a bit different.
>...
Thanks for the patch! Stefan or I will get it applied. Any further
tweaks can be applied in a later revision.
Cheers,
-g
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Dustin Lang <ds...@astro.princeton.edu>.
Hi Stefan,
Thanks for the constructive review! I accept your nits, but have one comment:
> You can use svn_sort_compare_items_lexically because entries are single path
> components that do not contain slashes. In which case
> svn_sort_compare_items_as_paths produces the same result but is less
> efficient.
The paths are like:
trunk/documents/papers/archetypes/paper_plots/103lg.ps
But I still believe you are right that lexical sort will work fine and is
simpler than svn_sort_compare_items_as_paths.
The revised patch is attached. Here's a proposed commit message:
[[[
Issue #4134: svnadmin dump files are not reproducible, due to APR 1.4.6 hash order changes
This patch sorts deleted path names before dumping them.
* subversion/libsvn_repos/dump.c
(close_directory): sort hash deleted_entries before dumping.
Patch by: Dustin Lang <ds...@gmail.com>
Review by: stsp
(Stefan suggested several stylistic changes and using
svn_sort_compare_items_lexically.)
]]]
cheers,
dstn
On Tue, 29 May 2012, Stefan Sperling wrote:
> On Tue, May 29, 2012 at 03:09:08PM -0400, Dustin Lang wrote:
>>
>> Hi,
>>
>> This is my first time working on the subversion code, so be gentle :)
>>
>> I believe the attached patch solves one component of #4134
>> ("svnadmin dump files are not reproducible, due to APR 1.4.6 hash
>> order changes"), namely that deleted nodes are stored in a hash and
>> dumped out in (now-arbitrary) hash iteration order. This patch
>> simply uses "svn_sort_hash" to get a sorted view of the keys before
>> dumping them.
>>
>> I have verified that it runs valgrind-clean when "svnadmin dump"ing
>>> 700 revs of the astrometry.net repo (and now my repo and its
>> svnsync'd mirror produce exactly equal dumps, hoorah), but I don't
>> really know if I've used the apr infrastructure appropriately.
>>
>> I don't know whether this completely solves #4134; it works for me,
>> but my repo is simple.
>>
>> cheers,
>> dustin
>>
>
> This patch looks correct to me overall but I have some nits.
>
>> http://subversion.tigris.org/issues/show_bug.cgi?id=4134
>
>> Index: subversion/libsvn_repos/dump.c
>> ===================================================================
>> --- subversion/libsvn_repos/dump.c (revision 1343881)
>> +++ subversion/libsvn_repos/dump.c (working copy)
>> @@ -34,6 +34,7 @@
>> #include "svn_time.h"
>> #include "svn_checksum.h"
>> #include "svn_props.h"
>> +#include "svn_sorts.h"
>>
>> #include "private/svn_mergeinfo_private.h"
>> #include "private/svn_fs_private.h"
>> @@ -736,12 +737,14 @@
>> struct edit_baton *eb = db->edit_baton;
>> apr_hash_index_t *hi;
>> apr_pool_t *subpool = svn_pool_create(pool);
>> + unsigned int Npaths = apr_hash_count(db->deleted_entries);
>
> No CamelCase please. You don't need this variable at all (see below).
>
>> + unsigned int i;
>> + apr_array_header_t* sorted;
>
> Maybe call the array 'sorted_deleted_entries', or 'sorted_entries', instead?
>
>>
>> - for (hi = apr_hash_first(pool, db->deleted_entries);
>> - hi;
>> - hi = apr_hash_next(hi))
>> + sorted = svn_sort__hash(db->deleted_entries, svn_sort_compare_items_as_paths, pool);
>
> Please try to wrap lines at 78 columns.
>
> You can use svn_sort_compare_items_lexically because entries are single
> path components that do not contain slashes. In which case
> svn_sort_compare_items_as_paths produces the same result but is less efficient.
>
>> + for (i = 0; i < Npaths; i++)
>
> Here, you can use the idiom:
>
> for (i = 0; i < sorted->nelts; i++)
>
> which means you don't need 'Npaths'.
>
>> {
>> - const char *path = svn__apr_hash_index_key(hi);
>> + const char* path = APR_ARRAY_IDX(sorted, i, svn_sort__item_t).key;
>
> Please put the asterisk next to the variable name for consistency with code
> formatting elsewhere. Same applies to the declaration of 'sorted' above.
>
>>
>> svn_pool_clear(subpool);
>>
>> @@ -753,6 +756,8 @@
>> FALSE, NULL, SVN_INVALID_REVNUM, subpool));
>> }
>>
>> + apr_array_clear(sorted);
>
> No need to do this. This doesn't actually free any memory, it just marks
> array slots for reuse. Array memory will be freed when the caller clears
> or destroys 'pool'. It's up to the caller to do this, so just delete that line.
>
>> +
>> svn_pool_destroy(subpool);
>> return SVN_NO_ERROR;
>> }
>
>
Re: [PATCH] issue #4134 (partial): sort deleted nodes before dumping
them
Posted by Stefan Sperling <st...@elego.de>.
On Tue, May 29, 2012 at 03:09:08PM -0400, Dustin Lang wrote:
>
> Hi,
>
> This is my first time working on the subversion code, so be gentle :)
>
> I believe the attached patch solves one component of #4134
> ("svnadmin dump files are not reproducible, due to APR 1.4.6 hash
> order changes"), namely that deleted nodes are stored in a hash and
> dumped out in (now-arbitrary) hash iteration order. This patch
> simply uses "svn_sort_hash" to get a sorted view of the keys before
> dumping them.
>
> I have verified that it runs valgrind-clean when "svnadmin dump"ing
> >700 revs of the astrometry.net repo (and now my repo and its
> svnsync'd mirror produce exactly equal dumps, hoorah), but I don't
> really know if I've used the apr infrastructure appropriately.
>
> I don't know whether this completely solves #4134; it works for me,
> but my repo is simple.
>
> cheers,
> dustin
>
This patch looks correct to me overall but I have some nits.
> http://subversion.tigris.org/issues/show_bug.cgi?id=4134
> Index: subversion/libsvn_repos/dump.c
> ===================================================================
> --- subversion/libsvn_repos/dump.c (revision 1343881)
> +++ subversion/libsvn_repos/dump.c (working copy)
> @@ -34,6 +34,7 @@
> #include "svn_time.h"
> #include "svn_checksum.h"
> #include "svn_props.h"
> +#include "svn_sorts.h"
>
> #include "private/svn_mergeinfo_private.h"
> #include "private/svn_fs_private.h"
> @@ -736,12 +737,14 @@
> struct edit_baton *eb = db->edit_baton;
> apr_hash_index_t *hi;
> apr_pool_t *subpool = svn_pool_create(pool);
> + unsigned int Npaths = apr_hash_count(db->deleted_entries);
No CamelCase please. You don't need this variable at all (see below).
> + unsigned int i;
> + apr_array_header_t* sorted;
Maybe call the array 'sorted_deleted_entries', or 'sorted_entries', instead?
>
> - for (hi = apr_hash_first(pool, db->deleted_entries);
> - hi;
> - hi = apr_hash_next(hi))
> + sorted = svn_sort__hash(db->deleted_entries, svn_sort_compare_items_as_paths, pool);
Please try to wrap lines at 78 columns.
You can use svn_sort_compare_items_lexically because entries are single
path components that do not contain slashes. In which case
svn_sort_compare_items_as_paths produces the same result but is less efficient.
> + for (i = 0; i < Npaths; i++)
Here, you can use the idiom:
for (i = 0; i < sorted->nelts; i++)
which means you don't need 'Npaths'.
> {
> - const char *path = svn__apr_hash_index_key(hi);
> + const char* path = APR_ARRAY_IDX(sorted, i, svn_sort__item_t).key;
Please put the asterisk next to the variable name for consistency with code
formatting elsewhere. Same applies to the declaration of 'sorted' above.
>
> svn_pool_clear(subpool);
>
> @@ -753,6 +756,8 @@
> FALSE, NULL, SVN_INVALID_REVNUM, subpool));
> }
>
> + apr_array_clear(sorted);
No need to do this. This doesn't actually free any memory, it just marks
array slots for reuse. Array memory will be freed when the caller clears
or destroys 'pool'. It's up to the caller to do this, so just delete that line.
> +
> svn_pool_destroy(subpool);
> return SVN_NO_ERROR;
> }