incompatibility between libtheora/mmx and musl ?

incompatibility between libtheora/mmx and musl ?

[u-uy74]

Hello,

Libtheora contains an assembler part for ia32 and x86_64 which has been
in use for many years, with at least both glibc and uclibc.

Now, musl-based builds of libtheora for ia32 with this code enabled
lead to the encoder segfaulting. No problem when using the C version.

This is seen when building at Aetey. Ffmpeg in Alpine exhibits the same
problem, too (strictly speaking, possibly another problem but ffmpeg
crashes there with the same pattern, when encoding to theora).

People at Xiph do not have any musl-based system and want really detailed
debugging info which implies tracing through musl and following malloc's
internal data (which is what seems to become corrupted).

In other words, the detailed knowledge (xiph and musl) is located
separately from each other and also from the motivation (aetey, alpine
and possibly others).

I would appreciate some help and suggestions. The alternative is diving
into mmx-assembler and musl code or resorting to C-only routines which
give roughly half of the performance of the assembler ones.

More details are there at

 https://trac.xiph.org/ticket/2287

There is also a corresponding

 https://bugs.alpinelinux.org/issues/6132

Regards,
Rune

Re: incompatibility between libtheora/mmx and musl ?

[Markus Wichmann]

On Tue, Sep 13, 2016 at 08:06:49PM +0200, u-uy74@aetey.se wrote:
>  https://trac.xiph.org/ticket/2287

Alright, I had a look at it.

1. The free() in the loader: That would be reclaim_gaps(). valgrind
really doesn't like it.

2. Uninitialized values in calloc: There is only one conditional in
calloc(), and it depends on the two parameters. Is it possible that
those are uninitialized?

Ciao,
Markus

Re: incompatibility between libtheora/mmx and musl ?

[Rich Felker]

On Tue, Sep 13, 2016 at 09:20:06PM +0200, Markus Wichmann wrote:
> On Tue, Sep 13, 2016 at 08:06:49PM +0200, u-uy74@aetey.se wrote:
> >  https://trac.xiph.org/ticket/2287
> 
> Alright, I had a look at it.
> 
> 1. The free() in the loader: That would be reclaim_gaps(). valgrind
> really doesn't like it.
> 
> 2. Uninitialized values in calloc: There is only one conditional in
> calloc(), and it depends on the two parameters. Is it possible that
> those are uninitialized?

I think this is also a false positive -- valgrind treats calloc as a
normal consumer of malloc rather than part of the malloc
implementation and thus does not like the conditional zeroing:

	for (z=p; n; n--, z++) if (*z) *z=0;

Rich

Re: incompatibility between libtheora/mmx and musl ?

[Rich Felker]

On Tue, Sep 13, 2016 at 08:06:49PM +0200, u-uy74@aetey.se wrote:
> Hello,
> 
> Libtheora contains an assembler part for ia32 and x86_64 which has been
> in use for many years, with at least both glibc and uclibc.
> 
> Now, musl-based builds of libtheora for ia32 with this code enabled
> lead to the encoder segfaulting. No problem when using the C version.
> 
> This is seen when building at Aetey. Ffmpeg in Alpine exhibits the same
> problem, too (strictly speaking, possibly another problem but ffmpeg
> crashes there with the same pattern, when encoding to theora).
> 
> People at Xiph do not have any musl-based system and want really detailed
> debugging info which implies tracing through musl and following malloc's
> internal data (which is what seems to become corrupted).
> 
> In other words, the detailed knowledge (xiph and musl) is located
> separately from each other and also from the motivation (aetey, alpine
> and possibly others).
> 
> I would appreciate some help and suggestions. The alternative is diving
> into mmx-assembler and musl code or resorting to C-only routines which
> give roughly half of the performance of the assembler ones.
> 
> More details are there at
> 
>  https://trac.xiph.org/ticket/2287
> 
> There is also a corresponding
> 
>  https://bugs.alpinelinux.org/issues/6132

The most likely explanation is that they're overflowing a heap buffer.
Perhaps it would be possible to pad all their malloc/realloc calls
with +64 or so to see if that makes the problem go away. If so that
gives a good starting point for tracking down the bug.

Rich

Re: incompatibility between libtheora/mmx and musl ?

[u-uy74]

On Tue, Sep 13, 2016 at 04:43:04PM -0400, Rich Felker wrote:
> > Libtheora contains an assembler part for ia32 and x86_64 which has been
> > in use for many years, with at least both glibc and uclibc.
> > 
> > Now, musl-based builds of libtheora for ia32 with this code enabled
> > lead to the encoder segfaulting. No problem when using the C version.

> >  https://trac.xiph.org/ticket/2287
> > 
> > There is also a corresponding
> > 
> >  https://bugs.alpinelinux.org/issues/6132
> 
> The most likely explanation is that they're overflowing a heap buffer.
> Perhaps it would be possible to pad all their malloc/realloc calls
> with +64 or so to see if that makes the problem go away. If so that
> gives a good starting point for tracking down the bug.

Thanks for the suggestion, indeed libtheora seems to consistently use
ogg_malloc() which is redefinable.

Building with

 #define _ogg_malloc(x)  malloc((x)+256)
 #define _ogg_calloc(x,y)  calloc((x)+256,(y))
 #define _ogg_realloc(y,x) realloc((y),(x)+256)
 #define _ogg_free    free

instead of the default

 #define _ogg_malloc  malloc
 #define _ogg_calloc  calloc
 #define _ogg_realloc realloc
 #define _ogg_free    free

did not make any difference. The crash on a test file occurs in the same
way and the resulting partial output file is as long as otherwise.

This may mean that this is not a simple overflowing but rather
overwriting or reading distant "random" places (?) (register corruption?)

Rune

Re: incompatibility between libtheora/mmx and musl ?

[Szabolcs Nagy]

* u-uy74@aetey.se <u-uy74@aetey.se> [2016-09-14 12:32:53 +0200]:
> On Tue, Sep 13, 2016 at 04:43:04PM -0400, Rich Felker wrote:
> > > Libtheora contains an assembler part for ia32 and x86_64 which has been
> > > in use for many years, with at least both glibc and uclibc.
> > > 
> > > Now, musl-based builds of libtheora for ia32 with this code enabled
> > > lead to the encoder segfaulting. No problem when using the C version.
> 
> > >  https://trac.xiph.org/ticket/2287
> > > 
> > > There is also a corresponding
> > > 
> > >  https://bugs.alpinelinux.org/issues/6132
> > 
> > The most likely explanation is that they're overflowing a heap buffer.
> > Perhaps it would be possible to pad all their malloc/realloc calls
> > with +64 or so to see if that makes the problem go away. If so that
> > gives a good starting point for tracking down the bug.
> 
> Thanks for the suggestion, indeed libtheora seems to consistently use
> ogg_malloc() which is redefinable.
> 
> Building with
> 
>  #define _ogg_malloc(x)  malloc((x)+256)
>  #define _ogg_calloc(x,y)  calloc((x)+256,(y))
>  #define _ogg_realloc(y,x) realloc((y),(x)+256)
>  #define _ogg_free    free
> 
> instead of the default
> 
>  #define _ogg_malloc  malloc
>  #define _ogg_calloc  calloc
>  #define _ogg_realloc realloc
>  #define _ogg_free    free
> 
> did not make any difference. The crash on a test file occurs in the same
> way and the resulting partial output file is as long as otherwise.
> 
> This may mean that this is not a simple overflowing but rather
> overwriting or reading distant "random" places (?) (register corruption?)
> 

can be underflow (or the way they align the pointer returned by malloc)

you can increase/decrease alignment of musl's alloc by
changing SIZE_ALIGN in src/malloc/malloc.c
(or you can try some hack in _ogg_malloc/free if you are
sure that's what they are using)

there can be some call abi issue (register clobbering,
stack alignment,..) because of the asm, but that's hard
to check.

you may try tracing malloc calls (i don't know an easy
way other than instrumenting musl, you can try python
scripting gdb, the default gdb command language is not
enough for reporting malloc args and return values).

Re: incompatibility between libtheora/mmx and musl ?

[u-uy74]

On Wed, Sep 14, 2016 at 01:24:00PM +0200, Szabolcs Nagy wrote:
> >  #define _ogg_malloc(x)  malloc((x)+256)
> >  #define _ogg_calloc(x,y)  calloc((x)+256,(y))
> >  #define _ogg_realloc(y,x) realloc((y),(x)+256)
> >  #define _ogg_free    free
> > 
> > instead of the default
> > 
> >  #define _ogg_malloc  malloc
> >  #define _ogg_calloc  calloc
> >  #define _ogg_realloc realloc
> >  #define _ogg_free    free
> > 
> > did not make any difference. The crash on a test file occurs in the same
> > way and the resulting partial output file is as long as otherwise.
> > 
> > This may mean that this is not a simple overflowing but rather
> > overwriting or reading distant "random" places (?) (register corruption?)

> can be underflow (or the way they align the pointer returned by malloc)

Pointer alignment yes they do in some cases but in a different layer,
inside the malloc()-ed buffers, it is plain C and looks harmless to me.

> you can increase/decrease alignment of musl's alloc by
> changing SIZE_ALIGN in src/malloc/malloc.c

Doubling the alignment did not apparently change the crashing.

Reducing the alignment in half did not apparently change the crashing.

(A single test file with a single quality setting tested
crashed the same way, at the same place in the output stream)

> (or you can try some hack in _ogg_malloc/free if you are
> sure that's what they are using)

Yes it is present/used for this very purpose, to enable easy "hijacking".

OTOH when I checked the arguments in gdb they looked always sane, up to
the last and crashing realloc() call. That's why I do not expect seeing
anything unusual there.

Valgrind did not see any bad free()s either.

> there can be some call abi issue (register clobbering,
> stack alignment,..) because of the asm, but that's hard
> to check.

Is musl in any way special compared to glibc/uclibc in its register usage?

> you may try tracing malloc calls (i don't know an easy
> way other than instrumenting musl, you can try python
> scripting gdb, the default gdb command language is not
> enough for reporting malloc args and return values).

This is something I wished to avoid. It does not promise much either,
but I may possibly try this if nothing else helps.

Thanks everyone for the help!

Rune

Re: incompatibility between libtheora/mmx and musl ?

[Rich Felker]

On Wed, Sep 14, 2016 at 04:04:50PM +0200, u-uy74@aetey.se wrote:
> On Wed, Sep 14, 2016 at 01:24:00PM +0200, Szabolcs Nagy wrote:
> > >  #define _ogg_malloc(x)  malloc((x)+256)
> > >  #define _ogg_calloc(x,y)  calloc((x)+256,(y))
> > >  #define _ogg_realloc(y,x) realloc((y),(x)+256)
> > >  #define _ogg_free    free
> > > 
> > > instead of the default
> > > 
> > >  #define _ogg_malloc  malloc
> > >  #define _ogg_calloc  calloc
> > >  #define _ogg_realloc realloc
> > >  #define _ogg_free    free
> > > 
> > > did not make any difference. The crash on a test file occurs in the same
> > > way and the resulting partial output file is as long as otherwise.
> > > 
> > > This may mean that this is not a simple overflowing but rather
> > > overwriting or reading distant "random" places (?) (register corruption?)
> 
> > can be underflow (or the way they align the pointer returned by malloc)
> 
> Pointer alignment yes they do in some cases but in a different layer,
> inside the malloc()-ed buffers, it is plain C and looks harmless to me.
> 
> > you can increase/decrease alignment of musl's alloc by
> > changing SIZE_ALIGN in src/malloc/malloc.c
> 
> Doubling the alignment did not apparently change the crashing.
> 
> Reducing the alignment in half did not apparently change the crashing.
> 
> (A single test file with a single quality setting tested
> crashed the same way, at the same place in the output stream)

I think this was a bad recommendation to test. musl's SIZE_ALIGN is a
macro to avoid magic numbers and make the code (very minimally)
self-documenting, but that doesn't mean it's a parameter. It's tied
into assumptions about the actual metadata structure and changing it
is almost surely going to introduce internal inconsistency/corruption
in the malloc implementation.

> > (or you can try some hack in _ogg_malloc/free if you are
> > sure that's what they are using)
> 
> Yes it is present/used for this very purpose, to enable easy "hijacking".
> 
> OTOH when I checked the arguments in gdb they looked always sane, up to
> the last and crashing realloc() call. That's why I do not expect seeing
> anything unusual there.
> 
> Valgrind did not see any bad free()s either.
> 
> > there can be some call abi issue (register clobbering,
> > stack alignment,..) because of the asm, but that's hard
> > to check.
> 
> Is musl in any way special compared to glibc/uclibc in its register usage?

Not in principle; this is mandated by the ABI. But it's possible that
their violation of ABI contracts is visible with some implementations
but not others. For example if they're calling malloc from code that's
using asm it's possible that they assume the floating point registers
(or mmx state) are call-saved rather than call-clobbered. This is an
invalid assumption that might happen to actively break on musl but not
glibc. IIRC you need some special instructions to switch between x87
and (original) mmx usage; perhaps they're missing this somewhere.

Rich

Re: incompatibility between libtheora/mmx and musl ?

[Timo Teras]

On Wed, 14 Sep 2016 10:28:42 -0400
Rich Felker <dalias@libc.org> wrote:

> > > there can be some call abi issue (register clobbering,
> > > stack alignment,..) because of the asm, but that's hard
> > > to check.  
> > 
> > Is musl in any way special compared to glibc/uclibc in its register
> > usage?  
> 
> Not in principle; this is mandated by the ABI. But it's possible that
> their violation of ABI contracts is visible with some implementations
> but not others. For example if they're calling malloc from code that's
> using asm it's possible that they assume the floating point registers
> (or mmx state) are call-saved rather than call-clobbered. This is an
> invalid assumption that might happen to actively break on musl but not
> glibc. IIRC you need some special instructions to switch between x87
> and (original) mmx usage; perhaps they're missing this somewhere.

Also, since it's Alpine (mentioned in first there with the bug report),
we compile everything PIE. So on x86 ebx is reserved and should not be
clobbered.

Re: incompatibility between libtheora/mmx and musl ?

[Rich Felker]

On Wed, Sep 14, 2016 at 05:31:37PM +0300, Timo Teras wrote:
> On Wed, 14 Sep 2016 10:28:42 -0400
> Rich Felker <dalias@libc.org> wrote:
> 
> > > > there can be some call abi issue (register clobbering,
> > > > stack alignment,..) because of the asm, but that's hard
> > > > to check.  
> > > 
> > > Is musl in any way special compared to glibc/uclibc in its register
> > > usage?  
> > 
> > Not in principle; this is mandated by the ABI. But it's possible that
> > their violation of ABI contracts is visible with some implementations
> > but not others. For example if they're calling malloc from code that's
> > using asm it's possible that they assume the floating point registers
> > (or mmx state) are call-saved rather than call-clobbered. This is an
> > invalid assumption that might happen to actively break on musl but not
> > glibc. IIRC you need some special instructions to switch between x87
> > and (original) mmx usage; perhaps they're missing this somewhere.
> 
> Also, since it's Alpine (mentioned in first there with the bug report),
> we compile everything PIE. So on x86 ebx is reserved and should not be
> clobbered.

ebx is always a call-saved register in the x86 ABI, though. The
difference is that, if they make any cross-library calls that may go
through the PLT, ebx must point to the caller's GOT at the time of the
call. But this difference only applies in the main-program (for
static-linked libtheora, for instance); with dynamic linking the code
is already required to be PIC and thus already has to be taking this
into account.

Rich

Re: incompatibility between libtheora/mmx and musl ?

[Rich Felker]

On Wed, Sep 14, 2016 at 10:28:42AM -0400, Rich Felker wrote:
> > > (or you can try some hack in _ogg_malloc/free if you are
> > > sure that's what they are using)
> > 
> > Yes it is present/used for this very purpose, to enable easy "hijacking".
> > 
> > OTOH when I checked the arguments in gdb they looked always sane, up to
> > the last and crashing realloc() call. That's why I do not expect seeing
> > anything unusual there.
> > 
> > Valgrind did not see any bad free()s either.
> > 
> > > there can be some call abi issue (register clobbering,
> > > stack alignment,..) because of the asm, but that's hard
> > > to check.
> > 
> > Is musl in any way special compared to glibc/uclibc in its register usage?
> 
> Not in principle; this is mandated by the ABI. But it's possible that
> their violation of ABI contracts is visible with some implementations
> but not others. For example if they're calling malloc from code that's
> using asm it's possible that they assume the floating point registers
> (or mmx state) are call-saved rather than call-clobbered. This is an
> invalid assumption that might happen to actively break on musl but not
> glibc. IIRC you need some special instructions to switch between x87
> and (original) mmx usage; perhaps they're missing this somewhere.

Another possibility: they may be changing the x87 control word to
something that yields non-conforming behavior. musl does not support
this (unless of course you change it back before any musl code could
get invoked).

Rich

Re: incompatibility between libtheora/mmx and musl ?

[Szabolcs Nagy]

* Rich Felker <dalias@libc.org> [2016-09-14 10:28:42 -0400]:
> On Wed, Sep 14, 2016 at 04:04:50PM +0200, u-uy74@aetey.se wrote:
> > On Wed, Sep 14, 2016 at 01:24:00PM +0200, Szabolcs Nagy wrote:
> > > there can be some call abi issue (register clobbering,
> > > stack alignment,..) because of the asm, but that's hard
> > > to check.
> > 
> > Is musl in any way special compared to glibc/uclibc in its register usage?
> 
> Not in principle; this is mandated by the ABI. But it's possible that
> their violation of ABI contracts is visible with some implementations
> but not others. For example if they're calling malloc from code that's
> using asm it's possible that they assume the floating point registers
> (or mmx state) are call-saved rather than call-clobbered. This is an
> invalid assumption that might happen to actively break on musl but not
> glibc. IIRC you need some special instructions to switch between x87
> and (original) mmx usage; perhaps they're missing this somewhere.
> 

this might be an issue:
musl uses float instructions in malloc,
if mmx needs different fpu state and
they don't change it back for a malloc
call that can corrupt the heap.

to test this, try to use the 'non-float bin index'
code in musl from here:
http://port70.net/~nsz/musl/malloc.c

Re: incompatibility between libtheora/mmx and musl ?

[u-uy74]

On Wed, Sep 14, 2016 at 04:41:45PM +0200, Szabolcs Nagy wrote:
> this might be an issue:
> musl uses float instructions in malloc,
> if mmx needs different fpu state and
> they don't change it back for a malloc
> call that can corrupt the heap.
> 
> to test this, try to use the 'non-float bin index'
> code in musl from here:
> http://port70.net/~nsz/musl/malloc.c

Bingo!

The resulting encoder works like a charm.

I forward this info to Xiph and expect the fix will be on the way.

Thanks a lot Szabolcs (and everyone)!

Rune

"non-float" malloc (was: incompatibility between libtheora/mmx and musl)

[u-uy74]

Hello Szabolcs,

On Wed, Sep 14, 2016 at 04:41:45PM +0200, Szabolcs Nagy wrote:
> this might be an issue:
> musl uses float instructions in malloc,
> if mmx needs different fpu state and
> they don't change it back for a malloc
> call that can corrupt the heap.
> 
> to test this, try to use the 'non-float bin index'
> code in musl from here:
> http://port70.net/~nsz/musl/malloc.c

Thanks again for the solution to the libtheora mystery.

Now I have reported the same issue affecting ffmpeg, it contains quite
a bit of simd assembler code and assumed until now among others that
malloc() never uses floating point.

Hopefully a fix is on the way there.

For the time being, to have a working ffmpeg build,
I tried to use your "non-float" malloc.

Unfortunately this leads to a segfault when used with the explicit runtime
loader, because brk() happily grows over the dynamic loader's data.
The modified variant of the malloc code seems to not apply
the traverses_stack_p() check.

I guess as long as you want to keep the special malloc.c
you would like it to be robust.

Would you mind adding the brk()/stack overlap checking to this variant
of the code?

Regards,
Rune

Re: "non-float" malloc (was: incompatibility between libtheora/mmx and musl)

[u-uy74]

On Sun, Oct 02, 2016 at 12:59:50PM +0200, u-uy74@aetey.se wrote:
> Would you mind adding the brk()/stack overlap checking to this variant
> of the code?

Something like (shamelessly cut-n-pasted from expand_heap.c)

--- malloc.c.ori        2016-10-02 13:06:34.407671803 +0200
+++ malloc.c    2016-10-02 13:13:06.787149613 +0200
@@ -60,6 +60,27 @@
 
 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
 
+/* This function returns true if the interval [old,new]
+ * intersects the 'len'-sized interval below &libc.auxv
+ * (interpreted as the main-thread stack) or below &b
+ * (the current stack). It is used to defend against
+ * buggy brk implementations that can cross the stack. */
+
+static int traverses_stack_p(uintptr_t old, uintptr_t new)
+{
+        const uintptr_t len = 8<<20;
+        uintptr_t a, b;
+
+        b = (uintptr_t)libc.auxv;
+        a = b > len ? b-len : 0;
+        if (new>a && old<b) return 1;
+
+        b = (uintptr_t)&b;
+        a = b > len ? b-len : 0;
+        if (new>a && old<b) return 1;
+
+        return 0;
+}
 
 /* Synchronization tools */
 
@@ -204,7 +225,8 @@
        new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
        n = new - mal.brk;
 
-       if (__brk(new) != new) {
+       if (traverses_stack_p(mal.brk, new) ||
+           __brk(new) != new) {
                size_t min = (size_t)PAGE_SIZE << mal.mmap_step/2;
                n += -n & PAGE_SIZE-1;
                if (n < min) n = min;

Does it look correct?

Regards,
Rune

Re: "non-float" malloc (was: incompatibility between libtheora/mmx and musl)

[Szabolcs Nagy]

* u-uy74@aetey.se <u-uy74@aetey.se> [2016-10-02 12:59:50 +0200]:
> On Wed, Sep 14, 2016 at 04:41:45PM +0200, Szabolcs Nagy wrote:
> > to test this, try to use the 'non-float bin index'
> > code in musl from here:
> > http://port70.net/~nsz/musl/malloc.c
> 
> Unfortunately this leads to a segfault when used with the explicit runtime
> loader, because brk() happily grows over the dynamic loader's data.
> The modified variant of the malloc code seems to not apply
> the traverses_stack_p() check.
> 

i meant that you should only use the bin index calculation from that file,
not as a malloc replacement.

other parts of musl malloc has been changed since i wrote that..

Re: "non-float" malloc (was: incompatibility between libtheora/mmx and musl)

[u-uy74]

On Sun, Oct 02, 2016 at 02:08:32PM +0200, Szabolcs Nagy wrote:
> i meant that you should only use the bin index calculation from that file,
> not as a malloc replacement.

Ah I see.

> other parts of musl malloc has been changed since i wrote that..

This means I tried to synchronize the versions in a wrong direction.
Thanks for the clarification!

Rune

Re: "non-float" malloc (was: incompatibility between libtheora/mmx and musl)

[u-uy74]

On Sun, Oct 02, 2016 at 02:24:08PM +0200, u-uy74@aetey.se wrote:
> This means I tried to synchronize the versions in a wrong direction.
> Thanks for the clarification!

FWIIW with the appropriate tweak (bin indexing) applied to the appropriate
version, ffmpeg can be run without noticeable issues.

Nevertheless, hope ffmpeg fixes the UB-dependent code soon,
there are probably more potential problems there than just malloc() vs fpu.

Regards,
Rune