Crash in `rs_search_for_block`

[librsync]

Crash in `rs_search_for_block`

[dbaarda]

The entire search implementation this bug is referencing has now been replaced with a completely new open-addressing hashtable that is significantly faster for large files.

So I think this bug can be closed, unless people want to use this bug to track adding a regression test?

[mertemba]

The bug is present on Linux as well. On an ARMv7 with GCC 5.2.0, I get the following error (when using librsync via Python/rdiff-backup):

Program received signal SIGSEGV, Segmentation fault.
rs_search_for_block (weak_sum=1858441517, inbuf=0x2 <error: Cannot access memory at address 0x2>, block_len=block_len@entry=3232, sig=0x54d1f220, stats=stats@entry=0x54d1f8f0, 
    match_where=0x7efee080, match_where@entry=0x7efee078) at /home/ladmin/librsync/src/librsync-2.0.0/src/search.c:224
224             if (weak_sum != b->weak_sum)
(gdb) bt
#0  rs_search_for_block (weak_sum=1858441517, inbuf=0x2 <error: Cannot access memory at address 0x2>, block_len=block_len@entry=3232, sig=0x54d1f220, stats=stats@entry=0x54d1f8f0, 
    match_where=0x7efee080, match_where@entry=0x7efee078) at /home/ladmin/librsync/src/librsync-2.0.0/src/search.c:224
#1  0x761c1bf4 in rs_findmatch (match_len=<synthetic pointer>, match_pos=0x7efee078, job=0x54d1f840) at /home/ladmin/librsync/src/librsync-2.0.0/src/delta.c:273
#2  rs_delta_s_scan (job=0x54d1f840) at /home/ladmin/librsync/src/librsync-2.0.0/src/delta.c:157
#3  0x761c2abc in rs_job_work (job=0x54d1f840, buffers=buffers@entry=0x7efee118) at /home/ladmin/librsync/src/librsync-2.0.0/src/job.c:187
#4  0x761c2b38 in rs_job_iter (job=<optimized out>, buffers=0x7efee118) at /home/ladmin/librsync/src/librsync-2.0.0/src/job.c:145
#5  0x761fe078 in ?? () from /usr/lib/python2.7/site-packages/rdiff_backup/_librsync.so

The crash is located here. Apparently it's the same error as described above, the value of i is too high.

If it matters to you, l is 3245, and sig->targets[l].i is accessible memory, but i is 27209 and sig->block_sigs has length 5726.

The crash didn't happen with librsync 1.0.0 (built in March 2015).

[mmasenlle]

I think this patch may be a fix

@@ -218,7 +218,7 @@ rs_search_for_block(rs_weak_sum_t weak_sum,
            r = m;
     }

-    if (l == r) {
+    if (l == r && l < sig->count) {
        int i = sig->targets[l].i;
        rs_block_sig_t *b = &(sig->block_sigs[i]);
        if (weak_sum != b->weak_sum)

[sourcefrog]

I can reproduce this too, on OS X.

I'm surprised this has started failing because the relevant code doesn't seem to have changed for years.

[sourcefrog]

I think #53 fixes this (certainly avoids the crash) and makes this code easier to understand.

If anyone wants to review it, please do, otherwise I'll merge in a couple of days.

[mertemba]

Hi, I compiled and tested current master with your patches on top.
The client of rdiff-backup (with v1.0.0 working fine) seems to lock up and hangs with 100% CPU usage, and can only be stopped with SIGKILL. (Note: The server uses the same patches as well.)
Should I provide an example file, where rdiff-backup fails? It is a 32KB binary SQLite database file in a bigger backup directory, maybe the issue persists if the file is isolated.

[sourcefrog]

Can you get a traceback from gdb?

On Sun, Jan 3, 2016 at 10:08 AM jellysheep [email protected] wrote:

Hi, I compiled and tested current master with your patches on top.
The client of rdiff-backup (with v1.0.0 working fine) seems to lock up and
hangs with 100% CPU usage, and can only be stopped with SIGKILL.
Should I provide an example file, where rdiff-backup fails? It is a 32KB
binary SQLite database file in a bigger backup directory, maybe the issue
persists if the file is isolated.

—
Reply to this email directly or view it on GitHub
#50 (comment).

[mertemba]

Sure, here it is, sorry for the delay:

0x00007ffff2b67bab in rs__search_for_block (weak_sum=1816519131, inbuf=0x555555dec6fc "", block_len=block_len@entry=3600, sig=0x5555559223b0, stats=stats@entry=0x5555559326c0, 
    match_where=match_where@entry=0x7ffffffeb508) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/search.c:195
195         v = (weak_sum > b->weak_sum) - (weak_sum < b->weak_sum);
(gdb) bt
#0  0x00007ffff2b67bab in rs__search_for_block (weak_sum=1816519131, inbuf=0x555555dec6fc "", block_len=block_len@entry=3600, sig=0x5555559223b0, stats=stats@entry=0x5555559326c0, 
    match_where=match_where@entry=0x7ffffffeb508) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/search.c:195
#1  0x00007ffff2b649e9 in rs_findmatch (match_len=<synthetic pointer>, match_pos=0x7ffffffeb508, job=0x5555559325f0) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/delta.c:273
#2  rs_delta_s_scan (job=0x5555559325f0) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/delta.c:157
#3  0x00007ffff2b65725 in rs_job_work (buffers=0x7ffffffeb5b0, job=0x5555559325f0) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/job.c:180
#4  rs_job_iter (job=0x5555559325f0, buffers=0x7ffffffeb5b0) at /home/ladmin/SafeBox/Software/librsync-git/src/librsync/src/job.c:138
#5  0x00007ffff2d725a2 in ?? () from /usr/lib/python2.7/site-packages/rdiff_backup/_librsync.so

As this is a traceback of rdiff-backup, the rest of the stack is full of Python methods.
The local variables are, if of any concern:

(gdb) info locals
m = 1103
i = 1375
b = 0x555555d564f8
strong_sum = "\004\000\000\000\000\000\000\000nf\266\362\377\177\000\000\016\020\b\260\000\000\000\000\000{\334\033\bA\211\260"
got_strong = 0
hash_tag = 20000
bucket = <optimized out>
l = 1104
r = 1102
v = <optimized out>

EDIT: This is on commit 9b9efb0, with your commits applied on top.

[klausenbusk]

I think I have this crash with duplicity. systemd-coredump give me this:

jan 08 22:33:42 arch systemd-coredump[12752]: Process 12731 (python2) of user 1005 dumped core.

                                              Stack trace of thread 12731:
                                              #0  0x00000000b6c003fd rs_search_for_block (librsync.so.2)
                                              #1  0x00000000b6bfccfc n/a (librsync.so.2)
                                              #2  0x00000000b6bfdbd4 rs_job_iter (librsync.so.2)
                                              #3  0x00000000b6c1ddfc n/a (_librsync.so)
                                              #4  0x00000000b767bb55 PyCFunction_Call (libpython2.7.so.1.0)
                                              #5  0x00000000b76de777 PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #6  0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #7  0x00000000b76e1625 PyEval_EvalCodeEx (libpython2.7.so.1.0)
                                              #8  0x00000000b76ddc31 PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #9  0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #10 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #11 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #12 0x00000000b76e1625 PyEval_EvalCodeEx (libpython2.7.so.1.0)
                                              #13 0x00000000b76ddc31 PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #14 0x00000000b76e1625 PyEval_EvalCodeEx (libpython2.7.so.1.0)
                                              #15 0x00000000b76ddc31 PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #16 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #17 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #18 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #19 0x00000000b76ddd1e PyEval_EvalFrameEx (libpython2.7.so.1.0)
                                              #20 0x00000000b76e1625 PyEval_EvalCodeEx (libpython2.7.so.1.0)
                                              #21 0x00000000b76e176b PyEval_EvalCode (libpython2.7.so.1.0)
                                              #22 0x00000000b76fbad6 run_mod (libpython2.7.so.1.0)
                                              #23 0x00000000b76fcf1b PyRun_FileExFlags (libpython2.7.so.1.0)
                                              #24 0x00000000b76fe3a0 PyRun_SimpleFileExFlags (libpython2.7.so.1.0)
                                              #25 0x00000000b76fe8e5 PyRun_AnyFileExFlags (libpython2.7.so.1.0)
                                              #26 0x00000000b7711d82 Py_Main (libpython2.7.so.1.0)
                                              #27 0x0000000008048594 main (python2.7)
                                              #28 0x00000000b744d497 __libc_start_main (libc.so.6)
                                              #29 0x00000000080485c2 _start (python2.7)

Edit: I use Arch Linux, relevant thread maybe: https://bbs.archlinux.org/viewtopic.php?pid=1593684

[sourcefrog]

Thanks, I'll look deeper and add a test

[sourcefrog]

Edit: I use Arch Linux, relevant thread maybe: https://bbs.archlinux.org/viewtopic.php?pid=1593684

Thanks - in particular that thread has at least two people saying this is a new regression between 1.0.0 and 2.0.0.

[sourcefrog]

There are a fair number of changes between 1.0.0 and 2.0.0, in v1.0.0...v2.0.0
(It's not quite as large as it looks in that page because there were some rearrangements in the introduction of CMake that are not perfectly matched by git or github.)

There were two major feature changes:

• Use of CMake, which might be changing detection of configuration parameters or compiler commands
• #14, a major rework of search.c by @VictorDenisov, which is probably what introduced the bug

This code needs unit tests and for the bug to just be fixed, of course, but it's good to know when it came in.

[VictorDenisov]

Looking into this.

[klausenbusk]

In Arch Linux at least, they have reverted to 1.0.0 https://bugs.archlinux.org/task/47645

[sourcefrog]

If someone can post a signature and new-file that reproduces this, and that doesn't contain overly sensitive private data, that would help me be sure it's fixed.

[VictorDenisov]

@mmasenlle Is correct. Although I would write it this way:

@@ -218,7 +218,7 @@ rs_search_for_block(rs_weak_sum_t weak_sum,
            r = m;
     }

-    if (l == r) {
+    if (l == r && l <= bucket->r) {
        int i = sig->targets[l].i;
        rs_block_sig_t *b = &(sig->block_sigs[i]);
        if (weak_sum != b->weak_sum)

[VictorDenisov]

Sorry, everyone. My bad. It's an embarrassing bug. I'm preparing a patch. Will post shortly.

[sourcefrog]

I know the current test coverage is not so great, but can you try to write
a unit test? I have the start of a search_test.c in my bisect branch.

On Mon, Jan 18, 2016 at 10:57 PM, Victor Denisov [email protected]
wrote:

Sorry, everyone. My bad. It's an embarrassing bug. I'm preparing a patch.
Will post shortly.

—
Reply to this email directly or view it on GitHub
#50 (comment).

[sourcefrog]

ps, thanks!

[VictorDenisov]

That would be a tough one. I'll try.

[timmattison]

@VictorDenisov How is this going? Still in testing? librsync issues on Mac OS with the homebrew package appear to be related to this. It'd be great to get this patched and start using rdiff-backup and duplicity again.

[sourcefrog]

Ball is with me to review and merge it.

[sourcefrog]

You can test from his #59

[sourcefrog]

Still needs a NEWS.md update, and a new release.

[VictorDenisov]

@timmattison if you can provide the file that fails that would be great. it's very difficult to come up with a file that exploits this issue and I didn't have time yet to write something to brute force it.

[klausenbusk]

@VictorDenisov maybe duplicity can reproduce it? Me and a another guy on ArchLinux forum both had the problem with duplicity, before the package maintainer decided to downgrade librsync.

[JElchison]

If it helps, I have a setup that can produce this segfault reliably within 20 minutes. Unfortunately, the setup is not portable (it's one of my monthly backups using Duplicity), but I'm willing to perform validation testing for the fix/release if that would help.

I, along with (at least) multiple other Duplicity users, are blocked from making backups until this issue is resolved. So, I'm motivated. :)

More info: https://answers.launchpad.net/duplicity/+question/284756

[sourcefrog]

Please test git head and let me know.

On Wed, Feb 10, 2016 at 7:12 PM, JElchison [email protected] wrote:

If it helps, I have a setup that can produce this segfault reliably within
20 minutes. Unfortunately, the setup is not portable (it's one of my
monthly backups using Duplicity), but I'm willing to perform validation
testing for the fix/release if that would help.

I, along with (at least) multiple other Duplicity users, are blocked from
making backups until this issue is resolved. So, I'm motivated. :)

More info: https://answers.launchpad.net/duplicity/+question/284756

—
Reply to this email directly or view it on GitHub
#50 (comment).

[mmasenlle]

file.txt
sig.txt

rdiff delta sig.txt file.txt

With sig.txt signature file and rdiff version Release 1.0.1 (commit a6a0c7c) I get the crash.

Current version (rdiff (librsync 2.0.1) - last commit 09c428e) works fine.

[VictorDenisov]

Thanks @mmasenlle . @sourcefrog These files are pretty small. I can put them in the repository and write a regression test for the bug. Are you ok with that?

[sourcefrog]

That'd be good

On Fri, Feb 12, 2016 at 6:28 AM, Victor Denisov [email protected]
wrote:

Thanks @mmasenlle https://github.com/mmasenlle . @sourcefrog
https://github.com/sourcefrog These files are pretty small. I can put
them in the repository and write a regression test for the bug. Are you ok
with that?

—
Reply to this email directly or view it on GitHub
#50 (comment).

[VictorDenisov]

I tried running this test in my environment before the fix was merged and after and didn't see any difference - it worked in both cases. I guess it means we can't use it as a good regression test for this bug.

[JElchison]

Confirmed fix using duplicity 0.7.06, python 2.7.11 on OS X El Capitan 10.11.3 (15D21)

$ uname -a
Darwin xxxxx 15.3.0 Darwin Kernel Version 15.3.0: Thu Dec 10 18:40:58 PST 2015; root:xnu-3248.30.4~1/RELEASE_X86_64 x86_64

Tested librsync v2.0.0 (26164ee)

• Result = segfault in 0x000000010b549208 rs_search_for_block + 648

Tested librsync current master (09c428e)

• Result = no segfault. First successful backup in ~20 attempts since upgrading librsync to 2.0.0.

[dbaarda]

Note that the new open-addressing hashtable includes more comprehensive unit tests so the test coverage has been significantly improved too. So I'm going to declare this fixed.