PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[katsuki.uwatoko at toshiba.co.jp]

On Sat, 13 Jun 2015 08:52:09 +1000, Dave Chinner wrote:

> Yup, that's looking like a toolchain bug. Thread about arm directory
> read corruption:

I think that this is not a toolchain bug, this is related to 
Subject: [PATCH v2 1/1] ARM : missing corrupted reg in __do_div_asm
http://www.spinics.net/lists/arm-kernel/msg426684.html

--

The problematic line in xfs is: 
irecs->br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno)
in xfs_dabuf_map()/fs/xfs/xfs_da_btree.c.

The expansion of it is: 

  ld = mappedbno >> mp->m_blkbb_log;
  do_div(ld, mp->m_sb.sb_agblocks);
  startblock = ld << mp->m_sb.sb_agblklog;
  ld = mappedbno >> mp->m_blkbb_log;
  startblock |= do_div(ld, mp->m_sb.sb_agblocks);
  irecs->br_startblock = startblock;

The assembler of these are:

:
	bl	__do_div64
	ldr	r1, [sp, #44]
	subs	r3, r7, #32
	orr	r1, r1, r2, lsr r5
	add	r5, sp, #80
	str	r5, [sp, #64]
	ldr	r5, [sp, #60]
	movpl	r1, r2, asl r3
	mov	r2, r2, asl r7
	str	r2, [sp, #40]
	str	r1, [sp, #44]
	mov	r1, r9
	str	r5, [sp, #96]
	mov	r7, #0
	ldr	r2, [sp, #96]
	mov	r5, #1
	ldr	fp, [sp, #64]
	str	r7, [sp, #84]
	mov	r9, r2, asr #31
	str	r7, [sp, #104]
	bl	__do_div64
:

by GCC 4.7.2 with -O2 option.

Because a result of do_div is stored in the 1st arg (r0),
r0, which is "ld" in the C,  must be reloaded after the 1st call of do_div, before the 2nd call of do_div.
But it is not reloaded in the above assembler.
The problem is macro __do_div_asm, as the patch describes.

I confirmed that the patch fixed this problem.

	mov	r1, sl
	str	r2, [sp, #56]
	mov	r0, fp
	bl	__do_div64
	ldr	ip, [sp, #36]
	rsb	r6, r5, #32
	subs	r3, r5, #32
	ldr	r1, [sp, #56]
	orr	ip, ip, r2, lsr r6
	str	r7, [sp, #96]
	mov	r6, #1
	str	r8, [sp, #80]
	mov	r0, ip
	str	r1, [sp, #52]
	movpl	r0, r2, asl r3
	mov	r2, r2, asl r5
	str	r0, [sp, #36]
	mov	r1, sl
	str	r2, [sp, #32]
	mov	r0, fp
	bl	__do_div64

by GCC 4.7.2 with -O2 option and the patch.

Thank you,
-- 
UWATOKO

PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Dave Chinner]

On Wed, Aug 12, 2015 at 12:56:25AM +0000, katsuki.uwatoko at toshiba.co.jp wrote:
> On Sat, 13 Jun 2015 08:52:09 +1000, Dave Chinner wrote:
> 
> > Yup, that's looking like a toolchain bug. Thread about arm directory
> > read corruption:
> 
> I think that this is not a toolchain bug, this is related to 
> Subject: [PATCH v2 1/1] ARM : missing corrupted reg in __do_div_asm
> http://www.spinics.net/lists/arm-kernel/msg426684.html

Interesting! Very good work finding that bug, Katsuki-san. 

FWIW, I suspect this fix will need to go back into stable kernels,
too.

> --
> 
> The problematic line in xfs is: 
> irecs->br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno)
> in xfs_dabuf_map()/fs/xfs/xfs_da_btree.c.
> 
> The expansion of it is: 
> 
>   ld = mappedbno >> mp->m_blkbb_log;
>   do_div(ld, mp->m_sb.sb_agblocks);
>   startblock = ld << mp->m_sb.sb_agblklog;
>   ld = mappedbno >> mp->m_blkbb_log;
>   startblock |= do_div(ld, mp->m_sb.sb_agblocks);
>   irecs->br_startblock = startblock;
> 
> The assembler of these are:
> 
> :
> 	bl	__do_div64
> 	ldr	r1, [sp, #44]
> 	subs	r3, r7, #32
> 	orr	r1, r1, r2, lsr r5
> 	add	r5, sp, #80
> 	str	r5, [sp, #64]
> 	ldr	r5, [sp, #60]
> 	movpl	r1, r2, asl r3
> 	mov	r2, r2, asl r7
> 	str	r2, [sp, #40]
> 	str	r1, [sp, #44]
> 	mov	r1, r9
> 	str	r5, [sp, #96]
> 	mov	r7, #0
> 	ldr	r2, [sp, #96]
> 	mov	r5, #1
> 	ldr	fp, [sp, #64]
> 	str	r7, [sp, #84]
> 	mov	r9, r2, asr #31
> 	str	r7, [sp, #104]
> 	bl	__do_div64
> :
> 
> by GCC 4.7.2 with -O2 option.

To close the loop, what code do the other versions GCC produce for
this macro?  Evidence so far says that the result depends on the
compiler version, so I would like to have confirmation that other
versions of the compiler generate working code.  There are other
XFS_DADDR_TO_FSB() calls in the XFS code, too - do they demonstrate
the same problem, maybe with different compiler versions?

Basically I'm asking what is the scope of the problem you've found?
i.e. when was the bug introduced, what compilers expose it, etc
so that when ARM users report XFS corruptions we have some idea of
whether their kernel/compiler combination might have caused the
issue they are seeing...

Cheers,

Dave.
-- 
Dave Chinner
david at fromorbit.com

PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[katsuki.uwatoko at toshiba.co.jp]

On Wed, 12 Aug 2015 13:14:07 +1000, Dave Chinner wrote:

> To close the loop, what code do the other versions GCC produce for
> this macro?  Evidence so far says that the result depends on the
> compiler version, so I would like to have confirmation that other
> versions of the compiler generate working code.  There are other
> XFS_DADDR_TO_FSB() calls in the XFS code, too - do they demonstrate
> the same problem, maybe with different compiler versions?
> 
> Basically I'm asking what is the scope of the problem you've found?
> i.e. when was the bug introduced, what compilers expose it, etc
> so that when ARM users report XFS corruptions we have some idea of
> whether their kernel/compiler combination might have caused the
> issue they are seeing...

I have the following versions of GCC now.
	4.5.1
	4.6.4
	4.7.2
# Sorry I don't have the recent versions of GCC.

And the results are:
	4.5.1 (-O2)	OK.
	4.6.4 (-O2)	BAD.
	4.7.2 (-O2)	BAD.

But even using gcc 4.7, this bug does not happen with -Os instead of -O2.
It means that when CONFIG_CC_OPTIMIZE_FOR_SIZE Kernel option is used, it does not happen.

As for the version of kernel, I am using 3.10 now. At least. it is the same as 2.6.32.

--
The following are codes generated by GCCs.

GCC 4.5.1 with -O2 (OK)
     178:       41a00003        movmi   r0, r3
     17c:       51a00057        asrpl   r0, r7, r0
     180:       e58da02c        str     sl, [sp, #44]   ; 0x2c
     184:       ebfffffe        bl      0 <__do_div64>
     188:       e1cd26f8        strd    r2, [sp, #104]  ; 0x68
     18c:       e3a08000        mov     r8, #0
     190:       e5d51175        ldrb    r1, [r5, #373]  ; 0x175
     194:       e59d2068        ldr     r2, [sp, #104]  ; 0x68
     198:       e251e020        subs    lr, r1, #32
     19c:       e5d5308c        ldrb    r3, [r5, #140]  ; 0x8c
     1a0:       e261c020        rsb     ip, r1, #32
     1a4:       e1a00136        lsr     r0, r6, r1
     1a8:       e1800c17        orr     r0, r0, r7, lsl ip
     1ac:       e2634020        rsb     r4, r3, #32
     1b0:       51a00e57        asrpl   r0, r7, lr
     1b4:       e253c020        subs    ip, r3, #32
     1b8:       e1a0b432        lsr     fp, r2, r4
     1bc:       e1a0a312        lsl     sl, r2, r3
     1c0:       51a0bc12        lslpl   fp, r2, ip
     1c4:       e59dc024        ldr     ip, [sp, #36]   ; 0x24
     1c8:       e5954064        ldr     r4, [r5, #100]  ; 0x64
     1cc:       e1a01157        asr     r1, r7, r1
     1d0:       e58d804c        str     r8, [sp, #76]   ; 0x4c
     1d4:       e58dc048        str     ip, [sp, #72]   ; 0x48
     1d8:       ebfffffe        bl      0 <__do_div64>

GCC 4.6.4 with -O2 (BAD)
     19c:       51a0025e        asrpl   r0, lr, r2
     1a0:       e3a0a001        mov     sl, #1
     1a4:       ebfffffe        bl      0 <__do_div64>
     1a8:       e1a0bb32        lsr     fp, r2, fp
     1ac:       e2553020        subs    r3, r5, #32
     1b0:       e1a01008        mov     r1, r8
     1b4:       e58d704c        str     r7, [sp, #76]   ; 0x4c
     1b8:       e1a0800b        mov     r8, fp
     1bc:       e58d7060        str     r7, [sp, #96]   ; 0x60
     1c0:       51a08312        lslpl   r8, r2, r3
     1c4:       e1a02512        lsl     r2, r2, r5
     1c8:       e58d8034        str     r8, [sp, #52]   ; 0x34
     1cc:       e1a0500a        mov     r5, sl
     1d0:       e58d2030        str     r2, [sp, #48]   ; 0x30
     1d4:       e28d8048        add     r8, sp, #72     ; 0x48
     1d8:       ebfffffe        bl      0 <__do_div64>

GCC 4.7.2 with -Os (OK)
     1a0:       e1cd02d8        ldrd    r0, [sp, #40]   ; 0x28
     1a4:       e1a0200b        mov     r2, fp
     1a8:       ebfffffe        bl      0 <__aeabi_lasr>
     1ac:       e5954064        ldr     r4, [r5, #100]  ; 0x64
     1b0:       ebfffffe        bl      0 <__do_div64>
     1b4:       e3a01000        mov     r1, #0
     1b8:       e1a00002        mov     r0, r2
     1bc:       e5d5208c        ldrb    r2, [r5, #140]  ; 0x8c
     1c0:       ebfffffe        bl      0 <__aeabi_llsl>
     1c4:       e1a0200b        mov     r2, fp
     1c8:       e1a06000        mov     r6, r0
     1cc:       e1a07001        mov     r7, r1
     1d0:       e1cd02d8        ldrd    r0, [sp, #40]   ; 0x28
     1d4:       ebfffffe        bl      0 <__aeabi_lasr>
     1d8:       e58da040        str     sl, [sp, #64]   ; 0x40
     1dc:       ebfffffe        bl      0 <__do_div64>

Thank you,
-- 
UWATOKO

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Christoph Hellwig]

On Wed, Aug 12, 2015 at 12:56:25AM +0000, katsuki.uwatoko at toshiba.co.jp wrote:
> On Sat, 13 Jun 2015 08:52:09 +1000, Dave Chinner wrote:
> 
> > Yup, that's looking like a toolchain bug. Thread about arm directory
> > read corruption:
> 
> I think that this is not a toolchain bug, this is related to 
> Subject: [PATCH v2 1/1] ARM : missing corrupted reg in __do_div_asm
> http://www.spinics.net/lists/arm-kernel/msg426684.html

Maybe it's time to rely on gcc to handle 64 bit divisions now?

I've been pretty annoyed at the amount of 32-bit architecture build
failures due to the lack of support for native 64-bit divisions, and
the ugly do_div hackery to work around it.

We're living in a world where we are using a lot of 64-bit CPUs and
people optimize for them, so it might be a good time to start relying
on the compiler to get these right on older CPUs.

How bad is gcc's code for 64-bit divisions on arm and x86 these days?
Is there still a good case for offloading work the compiler should be
doing on the programmer?

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Linus Torvalds]

On Tue, Aug 11, 2015 at 11:24 PM, Christoph Hellwig <hch@infradead.org> wrote:
>
> Maybe it's time to rely on gcc to handle 64 bit divisions now?

Ugh. gcc still does a pretty horrible job at it. While gcc knows that
a widening 32x32->64 multiplication can be simplified, it doesn't do
the same thing for a 64/32->64 division, and always calls __udivdi3
for it.

Now, __udivdi3 does avoid the general nasty case by then testing the
upper 32 bits of the divisor against zero, so it's not entirely
disastrous. It's just ugly.

But perhaps more importantly, I'm not at all sure libgcc is
kernel-safe. In particular, I'm not at all sure it *remains*
kernel-safe. Just as an example: can you guarantee that libgcc doesn't
implement integer division on some architecture by using the FP
hardware?

There's been a few cases where not having libgcc saved us headaches. I
forget the exact details, but it was something like several years ago
that we had gcc start to generate some insane crap exception handling
for C code generation, and the fact that we didn't include libgcc was
what made us catch it because of the resulting link error.

libgcc just isn't reliable in kernel space. I'm not opposed to some
random architecture using it (arch/tile does include "-lgcc" for
example), but I _do_ object to the notion that we say "let's use
libgcc in general".

So no. I do not believe that the occasional pain of a few people who
do 64-bit divides incorrectly is a good enough argument to start using
libgcc.

                 Linus

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Andy Lutomirski]

On 08/12/2015 08:49 AM, Linus Torvalds wrote:
> On Tue, Aug 11, 2015 at 11:24 PM, Christoph Hellwig <hch@infradead.org> wrote:
>>
>> Maybe it's time to rely on gcc to handle 64 bit divisions now?
>
> Ugh. gcc still does a pretty horrible job at it. While gcc knows that
> a widening 32x32->64 multiplication can be simplified, it doesn't do
> the same thing for a 64/32->64 division, and always calls __udivdi3
> for it.
>
> Now, __udivdi3 does avoid the general nasty case by then testing the
> upper 32 bits of the divisor against zero, so it's not entirely
> disastrous. It's just ugly.
>
> But perhaps more importantly, I'm not at all sure libgcc is
> kernel-safe. In particular, I'm not at all sure it *remains*
> kernel-safe. Just as an example: can you guarantee that libgcc doesn't
> implement integer division on some architecture by using the FP
> hardware?
>
> There's been a few cases where not having libgcc saved us headaches. I
> forget the exact details, but it was something like several years ago
> that we had gcc start to generate some insane crap exception handling
> for C code generation, and the fact that we didn't include libgcc was
> what made us catch it because of the resulting link error.
>
> libgcc just isn't reliable in kernel space. I'm not opposed to some
> random architecture using it (arch/tile does include "-lgcc" for
> example), but I _do_ object to the notion that we say "let's use
> libgcc in general".
>
> So no. I do not believe that the occasional pain of a few people who
> do 64-bit divides incorrectly is a good enough argument to start using
> libgcc.
>

Does your objection still apply if we supplied our own implementations 
of a handful of libgcc helpers?

--Andy

>                   Linus
>

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Linus Torvalds]

On Wed, Aug 12, 2015 at 3:20 PM, Andy Lutomirski <luto@kernel.org> wrote:
>
> Does your objection still apply if we supplied our own implementations of a
> handful of libgcc helpers?

We already do that.

Several architectures actually implement _udivdi3.

However, do_div() is actually the much simpler/better interface.

I don't think we have a single case in the kernel where we really want
the full 64/64 division, and the 64/32->64 case really is
fundamentally simpler.

This whole "do_div is so complicated" thing is just BS.

The thing that triggered Christoph to ask was a bug in the
implementation of that *simpler*  interface. What makes you think that
making people implement _udivdi3 would magically avoid all such bugs?

                Linus

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Andy Lutomirski]

On Wed, Aug 12, 2015 at 3:36 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Wed, Aug 12, 2015 at 3:20 PM, Andy Lutomirski <luto@kernel.org> wrote:
>>
>> Does your objection still apply if we supplied our own implementations of a
>> handful of libgcc helpers?
>
> We already do that.
>
> Several architectures actually implement _udivdi3.
>
> However, do_div() is actually the much simpler/better interface.
>
> I don't think we have a single case in the kernel where we really want
> the full 64/64 division, and the 64/32->64 case really is
> fundamentally simpler.
>
> This whole "do_div is so complicated" thing is just BS.
>
> The thing that triggered Christoph to ask was a bug in the
> implementation of that *simpler*  interface. What makes you think that
> making people implement _udivdi3 would magically avoid all such bugs?
>

Nothing.

We could ask gcc to fix this, I suppose (add __udiv_64_over_32 or whatever).

--Andy

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Andrew Morton]

On Wed, 12 Aug 2015 15:20:54 -0700 Andy Lutomirski <luto@kernel.org> wrote:

> On 08/12/2015 08:49 AM, Linus Torvalds wrote:
> > On Tue, Aug 11, 2015 at 11:24 PM, Christoph Hellwig <hch@infradead.org> wrote:
> >>
> >> Maybe it's time to rely on gcc to handle 64 bit divisions now?
> >
> > Ugh. gcc still does a pretty horrible job at it. While gcc knows that
> > a widening 32x32->64 multiplication can be simplified, it doesn't do
> > the same thing for a 64/32->64 division, and always calls __udivdi3
> > for it.
> >
> > Now, __udivdi3 does avoid the general nasty case by then testing the
> > upper 32 bits of the divisor against zero, so it's not entirely
> > disastrous. It's just ugly.
> >
> > But perhaps more importantly, I'm not at all sure libgcc is
> > kernel-safe. In particular, I'm not at all sure it *remains*
> > kernel-safe. Just as an example: can you guarantee that libgcc doesn't
> > implement integer division on some architecture by using the FP
> > hardware?
> >
> > There's been a few cases where not having libgcc saved us headaches. I
> > forget the exact details, but it was something like several years ago
> > that we had gcc start to generate some insane crap exception handling
> > for C code generation, and the fact that we didn't include libgcc was
> > what made us catch it because of the resulting link error.
> >
> > libgcc just isn't reliable in kernel space. I'm not opposed to some
> > random architecture using it (arch/tile does include "-lgcc" for
> > example), but I _do_ object to the notion that we say "let's use
> > libgcc in general".
> >
> > So no. I do not believe that the occasional pain of a few people who
> > do 64-bit divides incorrectly is a good enough argument to start using
> > libgcc.
> >
> 
> Does your objection still apply if we supplied our own implementations 
> of a handful of libgcc helpers?

It's not just a matter of "how fast is the divide".  The 32-bit build
error is supposed to prompt people to ask "did I really need to use 64
bits".

That *used* to work.  A bit.  But nowadays the errors are detected so
late that the fix (often by someone other than the original developer)
is to just slap a do_div() in there.

And as the build error no longer appears to be having the desired
effect, I too have been wondering if it's time to just give up and
implement __udivdi and friends.

Or maybe there's a way of breaking 64-bit builds instead ;)

enabling libgcc for 64-bit divisions, was Re: PROBLEM: XFS on ARM corruption 'Structure needs cleaning'

[Pavel Machek]

Hi!

On Wed 2015-08-12 08:49:45, Linus Torvalds wrote:
> On Tue, Aug 11, 2015 at 11:24 PM, Christoph Hellwig <hch@infradead.org> wrote:
> >
> > Maybe it's time to rely on gcc to handle 64 bit divisions now?
> 
> Ugh. gcc still does a pretty horrible job at it. While gcc knows that
> a widening 32x32->64 multiplication can be simplified, it doesn't do
> the same thing for a 64/32->64 division, and always calls __udivdi3
> for it.
> 
> Now, __udivdi3 does avoid the general nasty case by then testing the
> upper 32 bits of the divisor against zero, so it's not entirely
> disastrous. It's just ugly.
> 
> But perhaps more importantly, I'm not at all sure libgcc is
> kernel-safe. In particular, I'm not at all sure it *remains*
> kernel-safe. Just as an example: can you guarantee that libgcc doesn't

U-Boot relies on toolchain-provided libgcc by default, and one of reasons
we do that is so that libgcc stays sane. Yes, there's occasionally some fun
with that.

But if kernel did that, at least U-Boot would not be alone with the fun.

									Pavel