You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Philip Martin <ph...@wandisco.com> on 2014/02/18 16:38:22 UTC
Re: svn commit: r1559767 - /subversion/trunk/subversion/libsvn_delta/xdelta.c
stefan2@apache.org writes:
> Author: stefan2
> Date: Mon Jan 20 16:23:15 2014
> New Revision: 1559767
>
> URL: http://svn.apache.org/r1559767
> Log:
> Speed up txdelta for non-deltifyable sections. This alone speeds up
> the commit of a 1GB random data file form 28s to 14s.
>
> The idea is to use a fixed-length bit array that tell us whether we
> _might_ have a match for a given checksum. In contrast to the iterative,
> multi-level check in find_match, this pre-check is very fast and highly
> predictable.
>
> * subversion/libsvn_delta/xdelta.c
> (FLAGS_COUNT): Define a new array size constant.
> (blocks): Add the FLAGS array.
> (hash_flags): New, separate hash function for FLAGS.
> (add_block): Populate / update FLAGS as well.
> (init_blocks_table): Initialize FLAGS.
> (compute_delta): Add a tight loop skipping non-matching sections;
> continue with normal lookup when there might be match.
This is triggering valgrind warnings in random-test:
$ valgrind -q .libs/lt-random-test 2
==19698== Conditional jump or move depends on uninitialised value(s)
==19698== at 0x402EAA3: bcmp (mc_replace_strmem.c:935)
==19698== by 0x4052114: find_block (xdelta.c:201)
==19698== by 0x4052314: find_match (xdelta.c:284)
==19698== by 0x40527A3: compute_delta (xdelta.c:428)
==19698== by 0x4052A4D: svn_txdelta__xdelta (xdelta.c:494)
==19698== by 0x404FF49: compute_window (text_delta.c:160)
==19698== by 0x4050718: txdelta_next_window (text_delta.c:392)
==19698== by 0x40504D7: svn_txdelta_next_window (text_delta.c:346)
==19698== by 0x402794: do_random_combine_test (random-test.c:446)
==19698== by 0x402A4B: random_combine_test (random-test.c:499)
==19698== by 0x403BDBB: do_test_num (svn_test_main.c:396)
==19698== by 0x403CECD: main (svn_test_main.c:866)
==19698==
==19698== Conditional jump or move depends on uninitialised value(s)
==19698== at 0x4052117: find_block (xdelta.c:201)
==19698== by 0x4052314: find_match (xdelta.c:284)
==19698== by 0x40527A3: compute_delta (xdelta.c:428)
==19698== by 0x4052A4D: svn_txdelta__xdelta (xdelta.c:494)
==19698== by 0x404FF49: compute_window (text_delta.c:160)
==19698== by 0x4050718: txdelta_next_window (text_delta.c:392)
==19698== by 0x40504D7: svn_txdelta_next_window (text_delta.c:346)
==19698== by 0x402794: do_random_combine_test (random-test.c:446)
==19698== by 0x402A4B: random_combine_test (random-test.c:499)
==19698== by 0x403BDBB: do_test_num (svn_test_main.c:396)
==19698== by 0x403CECD: main (svn_test_main.c:866)
==19698==
PASS: lt-random-test 2: random combine delta test
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: svn commit: r1559767 - /subversion/trunk/subversion/libsvn_delta/xdelta.c
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Wed, Feb 19, 2014 at 2:34 AM, Philip Martin
<ph...@wandisco.com>wrote:
> Philip Martin <ph...@wandisco.com> writes:
>
> > $ valgrind -q .libs/lt-random-test 2
> > ==19698== Conditional jump or move depends on uninitialised value(s)
> > ==19698== at 0x402EAA3: bcmp (mc_replace_strmem.c:935)
> > ==19698== by 0x4052114: find_block (xdelta.c:201)
> > ==19698== by 0x4052314: find_match (xdelta.c:284)
> > ==19698== by 0x40527A3: compute_delta (xdelta.c:428)
> > ==19698== by 0x4052A4D: svn_txdelta__xdelta (xdelta.c:494)
> > ==19698== by 0x404FF49: compute_window (text_delta.c:160)
> > ==19698== by 0x4050718: txdelta_next_window (text_delta.c:392)
> > ==19698== by 0x40504D7: svn_txdelta_next_window (text_delta.c:346)
> > ==19698== by 0x402794: do_random_combine_test (random-test.c:446)
> > ==19698== by 0x402A4B: random_combine_test (random-test.c:499)
> > ==19698== by 0x403BDBB: do_test_num (svn_test_main.c:396)
> > ==19698== by 0x403CECD: main (svn_test_main.c:866)
>
> The following patch causes the test to abort showing that the
> pre-condition mentioned in the comment is not met:
>
> Index: sw/subversion/src2/subversion/libsvn_delta/xdelta.c
> ===================================================================
> --- sw/subversion/src2/subversion/libsvn_delta/xdelta.c (revision 1569558)
> +++ sw/subversion/src2/subversion/libsvn_delta/xdelta.c (working copy)
> @@ -412,6 +412,8 @@ compute_delta(svn_txdelta__ops_baton_t *build_bato
> {
> apr_size_t matchlen;
> apr_size_t apos;
> + apr_size_t lo_orig = lo;
> + apr_uint32_t rolling_orig = rolling;
>
> /* Quickly skip positions whose respective ROLLING checksums
> definitely do not match any SLOT in BLOCKS. */
> @@ -425,6 +427,7 @@ compute_delta(svn_txdelta__ops_baton_t *build_bato
> /* LO is still <= UPPER, i.e. the following lookup is legal:
> Closely check whether we've got a match for the current location.
> Due to the above pre-filter, chances are that we find one. */
> + SVN_ERR_ASSERT_NO_RETURN(lo <= upper);
> matchlen = find_match(&blocks, rolling, a, asize, b, bsize,
> &lo, &apos, pending_insert_start);
>
> With seed=4237012947 and catching the abort in gdb I see
>
> (gdb) p lo
> $1 = 7666
> (gdb) p upper
> $2 = 7610
> (gdb) p lo_orig
> $3 = 7666
>
> The previous iteration, when lo_orig=7591, calls find_match with lo=7592
> and that sets lo=7587 and matchlen=79. Then lo+=matchlen causes lo>upper.
>
Thanks to your analysis, Philip, this has been easy
to fix: r1570141.
-- Stefan^2.
Re: svn commit: r1559767 - /subversion/trunk/subversion/libsvn_delta/xdelta.c
Posted by Philip Martin <ph...@wandisco.com>.
Philip Martin <ph...@wandisco.com> writes:
> $ valgrind -q .libs/lt-random-test 2
> ==19698== Conditional jump or move depends on uninitialised value(s)
> ==19698== at 0x402EAA3: bcmp (mc_replace_strmem.c:935)
> ==19698== by 0x4052114: find_block (xdelta.c:201)
> ==19698== by 0x4052314: find_match (xdelta.c:284)
> ==19698== by 0x40527A3: compute_delta (xdelta.c:428)
> ==19698== by 0x4052A4D: svn_txdelta__xdelta (xdelta.c:494)
> ==19698== by 0x404FF49: compute_window (text_delta.c:160)
> ==19698== by 0x4050718: txdelta_next_window (text_delta.c:392)
> ==19698== by 0x40504D7: svn_txdelta_next_window (text_delta.c:346)
> ==19698== by 0x402794: do_random_combine_test (random-test.c:446)
> ==19698== by 0x402A4B: random_combine_test (random-test.c:499)
> ==19698== by 0x403BDBB: do_test_num (svn_test_main.c:396)
> ==19698== by 0x403CECD: main (svn_test_main.c:866)
The following patch causes the test to abort showing that the
pre-condition mentioned in the comment is not met:
Index: sw/subversion/src2/subversion/libsvn_delta/xdelta.c
===================================================================
--- sw/subversion/src2/subversion/libsvn_delta/xdelta.c (revision 1569558)
+++ sw/subversion/src2/subversion/libsvn_delta/xdelta.c (working copy)
@@ -412,6 +412,8 @@ compute_delta(svn_txdelta__ops_baton_t *build_bato
{
apr_size_t matchlen;
apr_size_t apos;
+ apr_size_t lo_orig = lo;
+ apr_uint32_t rolling_orig = rolling;
/* Quickly skip positions whose respective ROLLING checksums
definitely do not match any SLOT in BLOCKS. */
@@ -425,6 +427,7 @@ compute_delta(svn_txdelta__ops_baton_t *build_bato
/* LO is still <= UPPER, i.e. the following lookup is legal:
Closely check whether we've got a match for the current location.
Due to the above pre-filter, chances are that we find one. */
+ SVN_ERR_ASSERT_NO_RETURN(lo <= upper);
matchlen = find_match(&blocks, rolling, a, asize, b, bsize,
&lo, &apos, pending_insert_start);
With seed=4237012947 and catching the abort in gdb I see
(gdb) p lo
$1 = 7666
(gdb) p upper
$2 = 7610
(gdb) p lo_orig
$3 = 7666
The previous iteration, when lo_orig=7591, calls find_match with lo=7592
and that sets lo=7587 and matchlen=79. Then lo+=matchlen causes lo>upper.
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*