Segmentation fault during compression inside FSE_normalizeCount about zstd

[sergey-dryabzhinsky]

It is clearly some border case: https://gist.github.com/sergey-dryabzhinsky/0e5c2e6cbf05f303137b

Saved value can always be less than testing one.

Ugly and fast solution on line 19: https://gist.github.com/sergey-dryabzhinsky/7f09a390c546288bf75b

And it's working:

$ cat ../../fse_crash.bin | ./zstd -c > /dev/null
$ cat ../../fse_crash.bin | ./zstd -c > ../../fse_crash.bin.zstd
$ cat ../../fse_crash.bin.zstd | ./zstd -dc > ../../fse_crash.bin.dezstd
$ cd ../../
$ md5sum fse_crash.bin
20abb5f7bbc890a21a67969b83c94434 fse_crash.bin
$ md5sum fse_crash.bin.dezstd
20abb5f7bbc890a21a67969b83c94434 fse_crash.bin.dezstd

[Cyan4973]

Yes, thanks,
having a reproducible test case will definitely help a lot to catch up this problem.

Regards

[insonator]

bcronje - Does it crash systematically with the 32K buffer in this gist ? (content is a zip - use base64 --ignore-garbage to un-base64 it)

https://gist.github.com/insonator/4efb72572a11345c143a

[bcronje]

@Cyan4973 @insonator

I have made some progress on this issue. The problem (in my case at least) is related to my build setup. When I include zstd source as part of my program build then I get the crash. If I do not include the zstd source as part of my program build, but instead link to libzstd, then I do not get the crash and everything works.

We have a fairly complicated build setup, but the relevant bits are:

CC compression/zstd.c && gcc  -g -W -Wall -fPIC  -I/usr/local/include -MD -MP -c compression/zstd.c -o zstd.u.o

g++ -g -W -Wall -fPIC -shared -o myapp.uo zstd.u.o

If I use the above compilation flags then I get the crash on a specific data buffer (other buffers compress fine).

However if I just link to libzstd as below then everything works fine without any problems or crashes:

g++ -g -W -Wall -fPIC -shared -o myapp.uo -L/usr/lib -lzstd

So obviously there is some compiler flag that we use that does not play nicely with zstd. My gcc compiler knowledge is limited, so I'm not sure how to take this further. Any ideas?

[Cyan4973]

Wow, it seems we are getting into a very difficult to debug issue.

A change I can see in the compilation line is the use of g++ instead of gcc for the linking process. It shouldn't be a problem, it's just a combination I'm not testing much.

Another question : what is the version of gcc ?
gcc 4.9 tends to be aggressive, if not just plain wrong, at some optimization level. I had to specifically disable some of them for LZ4.
That being said, I'm not seeing -O3 or equivalent in the compilation lines.

Last, a potentially interesting test case could be to use clang instead of gcc. The command line is remarkably similar, but of course the generated binary is different. It would help to direct the suspicion onto the source code or the compiler.

[bcronje]

Yes very strange indeed. The version of gcc is:

gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

I'm not using any optimization flags during these tests. We're using g++ as it's a C++ application. When I get some free time I'll see if I can test with clang.

[Cyan4973]

Mmmh, gcc 4.8.2 is supposed to be stable...
Anyway, a test with clang would probably help to target the right issue.

[insonator]

in the new version of FSE_adjustNormSlow --

    while (rank[newRank].count > savedR.count)
    {
        rank[newRank-1] = rank[newRank];
        newRank++;
    }
    rank[newRank-1] = savedR;

if you change this to something like

    while (rank[newRank].count > savedR.count)
    {
        assert(newRank <= FSE_MAX_SYMBOL_VALUE);
        rank[newRank-1] = rank[newRank];
        newRank++;
    }
    assert((newRank - 1) <= FSE_MAX_SYMBOL_VALUE);
    rank[newRank-1] = savedR;

do you catch the asserts with my 32K buffer ?

[sergey-dryabzhinsky]

zstd: ../lib/fse.c:630: FSE_adjustNormSlow: Assertion `newRank <= 255' failed.
It's in first assert line.

Build with CFLAGS="-O0 -g -std=c99 -W -Wall -fPIC"
Tested with:

• gcc-4.8: gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)
• gcc-4.7: gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-12ubuntu1)

But if zstd compiled with gcc 4.6 - no assertion.
And if it compiled with -O2 optimization flag with gcc 4.6, 4.7, 4.8 - no assertion at all.

[sergey-dryabzhinsky]

Compiled with clang-3.6:

-O0:
zstd: ../lib/fse.c:630: size_t FSE_adjustNormSlow(short *, int, const unsigned int *, U32): Assertion `newRank <= 255' failed.

-O2: no assertion.

[insonator]

I wonder if the qsort() algorithm act differently between each compiler ? Different strategies ? qsort() being a call non-optimized but a compiler-generated one when optimized ?

[bcronje]

I can confirm, first assertion line.

And can also confirm, turning gcc optimization off (i.e. -O0) then assertion is thrown. Using any optimization from -O1 and above does not assert. Confirmed this with your programs/zstd app.

@Cyan4973 To reproduce on your side, compile with -O0 and use this buffer: https://gist.github.com/bcronje/9ac4ac6904736851f0bb

[insonator]

Incorporating the fix on line 19 made it that around 45GB of data was compressed successfully.

Thanks !

[Cyan4973]

Great work !
You found the right reason and solution.
I'll integrate the fix in a later revision of zstd.
Best Regards

[bcronje]

Thank you all.

[Cyan4973]

Latest update within "dev" branch seems to fix this issue