search

zlib-ng / zlib-ng

zlib replacement with optimizations for "next generation" systems.
zlib License
1.57k stars 256 forks source link

ppc64le: match[2] assertion error #361

Closed iii-i closed 5 years ago

iii-i commented 5 years ago

When running the following script on ppc64le:

while true; do
    for l in $(seq 1 9); do
        head -c10000000 /dev/urandom | hexdump -C | ./minigzip -$l | ./minigzip -d | pv >/dev/null
    done
done

after a few minutes I get a match[2]? assertion error.

I patched z_error in order to get a core dump, and here is the backtrace:

(gdb) bt
#0  0x00007fffa823faf0 in raise () from /lib64/libc.so.6
#1  0x00007fffa8241e6c in abort () from /lib64/libc.so.6
#2  0x00000000100184d8 in z_error (m=0x1001c6d0 "match[2]?") at zutil.c:109
#3  0x000000001000a674 in longest_match (s=0x3eb3c0b0, cur_match=24931) at match_p.h:123
#4  0x000000001000b948 in deflate_medium (s=0x3eb3c0b0, flush=0) at deflate_medium.c:287
#5  0x0000000010006098 in zng_deflate (strm=0x3eb30028, flush=0) at deflate.c:1026
#6  0x0000000010001738 in zng_gzwrite (gz=0x3eb30010, buf=0x7fffd3f2ab58, len=16384) at test/minigzip.c:186
#7  0x0000000010001ddc in gz_compress (in=0x7fffa83e16c0 <_IO_2_1_stdin_>, out=0x3eb30010) at test/minigzip.c:312
#8  0x00000000100027ec in main (argc=0, argv=0x7fffd3f2f068) at test/minigzip.c:516

Some values:

(gdb) frame 3
(gdb) x/4bx scan-2
0x3eb49b7f: 0x2e    0x2e    0x33    0x2e
(gdb) x/4bx match-2
0x3eb43963: 0x2e    0x2e    0x73    0x61
(gdb) p/x s->ins_h
0x3df3
mtl1979 commented 5 years ago

So essentially there is one bit difference but hash for both three byte sequences is same (bit 0x40)...

iii-i commented 5 years ago

I managed to reproduce this with a smaller file:

ppc64le$ ./minigzip -d <500K.gz >500K.tmp
ppc64le$ ./minigzip -4 500K.tmp
match[2]?
Aborted (core dumped)
mtl1979 commented 5 years ago

When I tried to calculate the hash on paper, I got same s->ins_h (0x3df3) when using byte sequence from scan-2, but different when using bytes from match-2, so insert_string_c() seems to work correctly assuming s->hash_shift is 5 and s->hash_mask is 01111111 11111111 in binary. or 32767 in decimal.

For match-2 I got hash of 0x‭3db3. I'm still not sure where it can get same hash for both sequences...

iii-i commented 5 years ago

Bisect (unhelpfully) points to:

commit 24772ef137a41fc2bd22e10c8e1bd1d58a92dd20
Author: Hans Kristian Rosbach
Date:   Wed Jan 16 12:35:34 2019 +0100

    Let deflate_medium be enabled by default.
iii-i commented 5 years ago

Even smaller file:

ppc64le$ ./minigzip -4 2K.txt
match[2]?
mtl1979 commented 5 years ago

@iii-i We have already found quite many bugs in deflate_medium and managed to fix some of them. Like I already said, finding the exact line where the bug is might be harder than just blatantly getting rid of the assert and simply comparing all three bytes.

iii-i commented 5 years ago

@mtl1979 I could give it a try - but wouldn't that degrade performance everywhere? Also, isn't there a possibility that, since we don't fully understand the bug, it would resurface elsewhere? Another thing that bugs me is that I see this on ppc64le, but not on x86_64.

In the meantime I tried to strip the problematic file byte-by-byte and got this:

ppc64le$ ./minigzip -4 274B.txt
match[2]?

The pattern is the same:

(gdb) x/3xb scan-2
0x1004db4b: 0x2e    0x2e    0x41
(gdb) p/x ((((0x2e << 5) ^ 0x2e) << 5) ^ 0x41) & 0x7fff
0x3d81
(gdb) x/3xb match-2
0x1004da52: 0x2e    0x2e    0x21
(gdb) p/x ((((0x2e << 5) ^ 0x2e) << 5) ^ 0x21) & 0x7fff
0x3de1
(gdb) p s->strstart
267
(gdb) p s->lookahead
7
(gdb) p/x s->ins_h
0x3d81
(gdb) p s->head[0x3d81]
267
(gdb) p s->prev[267]
21
(gdb) p s->prev[21]
18
(gdb) p s->prev[18]
0
(gdb) p cur_match
18
iii-i commented 5 years ago

I checked the sequence of insert_string_c calls, and it is indeed incorrect:

Breakpoint 1, insert_string_c (s=0x1004c2f0, str=0, count=0) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=0, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=1, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=2, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=3, count=2) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=5, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=6, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=7, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=8, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=9, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=10, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=11, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=12, count=2) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=14, count=1) at zlib-ng/deflate_p.h:31
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=18, count=1) at zlib-ng/deflate_p.h:31

18 is the corrupted cur_match in the problematic longest_match call.

iii-i commented 5 years ago

Unfortunately, this did not help at all. I have single-stepped through the code between insert_string_c(14) and insert_string_c(18) calls and I'm currently trying to wrap my head around the trace. But maybe you can already see something? One interesting thing is that the problem involves calling deflate_medium() twice.

(gdb) b insert_string_c if str==14
Breakpoint 1 at 0x1000c028: file /home/iii/zlib-ng/deflate_p.h, line 31.
(gdb) r
Breakpoint 1, insert_string_c (s=0x1004c2f0, str=14, count=1) at zlib-ng/deflate_p.h:31
31      Pos ret = 0;
(gdb) finish
Run till exit from #0  insert_string_c (s=0x1004c2f0, str=14, count=1) at zlib-ng/deflate_p.h:31
head[x31b5] = 5
head[x368e] = 6
head[x37f5] = 9
head[x3d8e] = 4
head[x3dbc] = 8
head[x3ded] = 14
head[x3dee] = 13
head[x51ee] = 11
head[x7e8e] = 10
0x000000001000aa08 in deflate_medium (s=0x1004c2f0, flush=0) at zlib-ng/deflate_medium.c:271
271             hash_head = functable.insert_string(s, s->strstart, 1);
Value returned is 3
274             next_match.match_start = 0;
275             next_match.match_length = 1;
276             next_match.strstart = s->strstart;
277             next_match.orgstart = next_match.strstart;
282             if (hash_head != 0 && s->strstart - hash_head <= MAX_DIST2) {
287                 next_match.match_length = longest_match(s, hash_head);
288                 next_match.match_start = s->match_start;
289                 if (next_match.match_start >= next_match.strstart) {
293                 if (next_match.match_length < MIN_MATCH)
296                     fizzle_matches(s, &current_match, &next_match);
300             if (next_match.match_length == 3 && (next_match.strstart - next_match.match_start) > 12000)
302             s->strstart = current_match.strstart;
309         bflush = emit_match(s, current_match);
312         s->strstart += current_match.match_length;
314         if (bflush)
316     }
206         IPos hash_head = 0;   /* head of the hash chain */
214         if (s->lookahead < MIN_LOOKAHEAD) {
223         s->prev_length = 2;
230         if (next_match.match_length > 0) {
231             current_match = next_match;
232             next_match.match_length = 0;
266         insert_match(s, current_match);
269         if (s->lookahead > MIN_LOOKAHEAD && (current_match.strstart + current_match.match_length) < (s->window_size - MIN_LOOKAHEAD)) {
305             next_match.match_length = 0;
309         bflush = emit_match(s, current_match);
312         s->strstart += current_match.match_length;
(gdb) p s->strstart
18
314         if (bflush)
316     }
206         IPos hash_head = 0;   /* head of the hash chain */
214         if (s->lookahead < MIN_LOOKAHEAD) {
215             functable.fill_window(s);
216             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
217                 return need_more;
(gdb) b deflate_medium
Breakpoint 2 at 0x1000a720: file zlib-ng/deflate_medium.c, line 202.
(gdb) c
Continuing.
Breakpoint 2, deflate_medium (s=0x1004c2f0, flush=4) at zlib-ng/deflate_medium.c:202
202     memset(&current_match, 0, sizeof(struct match));
203     memset(&next_match, 0, sizeof(struct match));
206         IPos hash_head = 0;   /* head of the hash chain */
214         if (s->lookahead < MIN_LOOKAHEAD) {
215             functable.fill_window(s);
216             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
219             if (s->lookahead == 0)
221             next_match.match_length = 0;
223         s->prev_length = 2;
230         if (next_match.match_length > 0) {
235             hash_head = 0;
236             if (s->lookahead >= MIN_MATCH) {
237                 hash_head = functable.insert_string(s, s->strstart, 1);
(gdb) p s->strstart
$4 = 18
mtl1979 commented 5 years ago

If deflate_medium is called twice in a row, it means it goes past the valid input buffer...

iii-i commented 5 years ago

It turns out that the presence of two deflate_medium() calls is irrelevant. If I append 1k \0s to the file, there will be only one call (because we won't hit s->lookahead < MIN_LOOKAHEAD just yet), but the current issue will still occur at the same spot.

iii-i commented 5 years ago

The following makes the problem go away:

--- a/deflate_medium.c
+++ b/deflate_medium.c
@@ -93,7 +93,7 @@ static void insert_match(deflate_state *s, struct match match) {
     if (match.match_length <= 16* s->max_insert_length && s->lookahead >= MIN_MATCH) {
         match.match_length--; /* string at strstart already in table */
         match.strstart++;
-#ifdef NOT_TWEAK_COMPILER
+#if 1
         do {
             if (likely(match.strstart >= match.orgstart)) {
                 functable.insert_string(s, match.strstart, 1);

The input on which the original and the tweaked code diverge appears to be: match_length == 6 && strstart == 12 && orgstart == 15. I think the tweaked code misses the case when strstart < orgstart < strstart + match_length - we still need to insert [orgstart:strstart + match_length] then.

mtl1979 commented 5 years ago

So it's an overlapping match?

iii-i commented 5 years ago

You mean, something non-trivial produced by fizzle_matches? Yes:

Breakpoint 1, fizzle_matches
(gdb) p *current
{match_start = 7, match_length = 3, strstart = 11, orgstart = 11}
(gdb) p *next
{match_start = 3, match_length = 4, strstart = 14, orgstart = 14}
(gdb) finish
(gdb) p current_match
{match_start = 7, match_length = 1, strstart = 11, orgstart = 11}
(gdb) p next_match
{match_start = 1, match_length = 6, strstart = 12, orgstart = 15}
(gdb) x/18c s->window
0x1004da40: 46 '.'  46 '.'  46 '.'  46 '.'  46 '.'  45 '-'  46 '.'  117 'u'
0x1004da48: 46 '.'  46 '.'  124 '|' 117 'u' 46 '.'  46 '.'  46 '.'  46 '.'
0x1004da50: 45 '-'  46 '.'
iii-i commented 5 years ago

I've updated the PR, could you have a look please? I used match.strstart + match.match_length - match.orgstart as a length - in this case it has the same value as match.orgstart - match.strstart, but if we take e.g. match_length == 4 && strstart == 12 && orgstart == 15, we would need to insert only 1 hash.