Bug in atomic_sub_if_positive

Bug in atomic_sub_if_positive

[Morten Larsen]

As far as I can tell the branch optimization fixes in 2.6.21 introduced
a bug in atomic_sub_if_positive that causes it to return even when the
sc instruction fails. The result is that e.g. down_trylock becomes
unreliable as the semaphore counter is not always decremented.

Below is a patch that fixed the problem on my system.

Morten S. Larsen


--- a/include/asm-mips/atomic.h 2008-06-25 22:38:43.159739000 -0700
+++ b/include/asm-mips/atomic.h 2008-06-25 22:39:07.552065000 -0700
@@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
                "       beqz    %0, 2f
\n"
                "        subu   %0, %1, %3
\n"
                "       .set    reorder
\n"
-               "1:
\n"
                "       .subsection 2
\n"
                "2:     b       1b
\n"
                "       .previous
\n"
+               "1:
\n"
                "       .set    mips0
\n"
                : "=&r" (result), "=&r" (temp), "=m" (v->counter)
                : "Ir" (i), "m" (v->counter)
@@ -682,10 +682,10 @@ static __inline__ long atomic64_sub_if_p
                "       beqz    %0, 2f
\n"
                "        dsubu  %0, %1, %3
\n"
                "       .set    reorder
\n"
-               "1:
\n"
                "       .subsection 2
\n"
                "2:     b       1b
\n"
                "       .previous
\n"
+               "1:
\n"
                "       .set    mips0
\n"
                : "=&r" (result), "=&r" (temp), "=m" (v->counter)
                : "Ir" (i), "m" (v->counter)

Re: Bug in atomic_sub_if_positive

[Ralf Baechle]

On Wed, Jun 25, 2008 at 11:07:24PM -0700, Morten Larsen wrote:

> As far as I can tell the branch optimization fixes in 2.6.21 introduced
> a bug in atomic_sub_if_positive that causes it to return even when the
> sc instruction fails. The result is that e.g. down_trylock becomes
> unreliable as the semaphore counter is not always decremented.

I did play with a test program and can't reproduce the effect with my
assembler.  I have darm memories of gas immitating some obscure behaviour
of the IRIX assembler and I think it doesn't do so for all MIPS targets.

So I'm wandering what toolchain have you been using?

  Ralf

RE: Bug in atomic_sub_if_positive

[Morten Larsen]

 
> I did play with a test program and can't reproduce the effect with my
> assembler.  I have darm memories of gas immitating some 
> obscure behaviour
> of the IRIX assembler and I think it doesn't do so for all 
> MIPS targets.
> 
> So I'm wandering what toolchain have you been using?
> 
>   Ralf
> 
The toolchain is from Wind River Systems 2.0 Linux Edition.
The kernel (based on 2.6.21.7) is also supplied by Wind River, and it
has preemption turned on.
The CPU is a Broadcom/SiByte BCM1125H (single core version of BCM1250
Swarm.)

Morten

RE: Bug in atomic_sub_if_positive

[Morten Larsen]

> As far as I can tell the branch optimization fixes in 2.6.21 introduced
> a bug in atomic_sub_if_positive that causes it to return even when the
> sc instruction fails. The result is that e.g. down_trylock becomes
> unreliable as the semaphore counter is not always decremented.

Previous patch was garbled by Outlook - this one should be clean:

--- a/include/asm-mips/atomic.h	2008-06-25 22:38:43.159739000 -0700
+++ b/include/asm-mips/atomic.h	2008-06-25 22:39:07.552065000 -0700
@@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
 		"	beqz	%0, 2f					\n"
 		"	 subu	%0, %1, %3				\n"
 		"	.set	reorder					\n"
-		"1:							\n"
 		"	.subsection 2					\n"
 		"2:	b	1b					\n"
 		"	.previous					\n"
+		"1:							\n"
 		"	.set	mips0					\n"
 		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
 		: "Ir" (i), "m" (v->counter)
@@ -682,10 +682,10 @@ static __inline__ long atomic64_sub_if_p
 		"	beqz	%0, 2f					\n"
 		"	 dsubu	%0, %1, %3				\n"
 		"	.set	reorder					\n"
-		"1:							\n"
 		"	.subsection 2					\n"
 		"2:	b	1b					\n"
 		"	.previous					\n"
+		"1:							\n"
 		"	.set	mips0					\n"
 		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
 		: "Ir" (i), "m" (v->counter)

Re: [SPAM] RE: Bug in atomic_sub_if_positive

[Markus Gothe]

[-- Attachment #1.1: Type: text/plain, Size: 1761 bytes --]

NACK.

You must realize that 1b stands for 'label 1, backwards', so correctly  
it would be '2: b 1f'... Which is a kind off inconsequent numbering in  
this case.

//Markus

On 2 Jul 2008, at 02:12, Morten Larsen wrote:

>
>> As far as I can tell the branch optimization fixes in 2.6.21  
>> introduced
>> a bug in atomic_sub_if_positive that causes it to return even when  
>> the
>> sc instruction fails. The result is that e.g. down_trylock becomes
>> unreliable as the semaphore counter is not always decremented.
>
> Previous patch was garbled by Outlook - this one should be clean:
>
> --- a/include/asm-mips/atomic.h	2008-06-25 22:38:43.159739000 -0700
> +++ b/include/asm-mips/atomic.h	2008-06-25 22:39:07.552065000 -0700
> @@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
> 		"	beqz	%0, 2f					\n"
> 		"	 subu	%0, %1, %3				\n"
> 		"	.set	reorder					\n"
> -		"1:							\n"
> 		"	.subsection 2					\n"
> 		"2:	b	1b					\n"
> 		"	.previous					\n"
> +		"1:							\n"
> 		"	.set	mips0					\n"
> 		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
> 		: "Ir" (i), "m" (v->counter)
> @@ -682,10 +682,10 @@ static __inline__ long atomic64_sub_if_p
> 		"	beqz	%0, 2f					\n"
> 		"	 dsubu	%0, %1, %3				\n"
> 		"	.set	reorder					\n"
> -		"1:							\n"
> 		"	.subsection 2					\n"
> 		"2:	b	1b					\n"
> 		"	.previous					\n"
> +		"1:							\n"
> 		"	.set	mips0					\n"
> 		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
> 		: "Ir" (i), "m" (v->counter)

_______________________________________

Mr Markus Gothe
Software Engineer

Phone: +46 (0)13 21 81 20 (ext. 1046)
Fax: +46 (0)13 21 21 15
Mobile: +46 (0)70 348 44 35
Diskettgatan 11, SE-583 35 Linköping, Sweden
www.27m.com




[-- Attachment #1.2: Type: text/html, Size: 14542 bytes --]

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 194 bytes --]

RE: [SPAM] RE: Bug in atomic_sub_if_positive

[Morten Larsen]

Thanks for the reply. My main point is that if the sc instruction fails (returns zero) then we need to start over (with another ll instruction.) It appears that the current code does not do this correctly. If you have a better suggestion for a patch, that's fine with me. Below is the code from the 2.6.20.21 kernel, which is (also) working for me.

=:-) Morten


                 __asm__ __volatile__(
                 "       .set    mips3                                   \n"
                 "1:     ll      %1, %2          # atomic_sub_if_positive\n"
                 "       subu    %0, %1, %3                              \n"
                 "       bltz    %0, 1f                                  \n"
                 "       sc      %0, %2                                  \n"
                 "       .set    noreorder                               \n"
                 "       beqz    %0, 1b                                  \n"
                 "        subu   %0, %1, %3                              \n"
                 "       .set    reorder                                 \n"
                 "1:                                                     \n"
                 "       .set    mips0                                   \n"
                 : "=&r" (result), "=&r" (temp), "=m" (v->counter)
                 : "Ir" (i), "m" (v->counter)
                 : "memory");



________________________________

	From: Markus Gothe [mailto:markus.gothe@27m.se] 
	Sent: Tuesday, July 01, 2008 5:29 PM
	To: Morten Larsen
	Cc: linux-mips@linux-mips.org
	Subject: Re: [SPAM] RE: Bug in atomic_sub_if_positive
	
	
	NACK. 

	You must realize that 1b stands for 'label 1, backwards', so correctly it would be '2: b 1f'... Which is a kind off inconsequent numbering in this case.

	//Markus

	On 2 Jul 2008, at 02:12, Morten Larsen wrote:



			As far as I can tell the branch optimization fixes in 2.6.21 introduced
			

			a bug in atomic_sub_if_positive that causes it to return even when the
			

			sc instruction fails. The result is that e.g. down_trylock becomes
			

			unreliable as the semaphore counter is not always decremented.
			


		Previous patch was garbled by Outlook - this one should be clean:
		
		--- a/include/asm-mips/atomic.h 2008-06-25 22:38:43.159739000 -0700
		+++ b/include/asm-mips/atomic.h 2008-06-25 22:39:07.552065000 -0700
		@@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
		" beqz %0, 2f \n"
		" subu %0, %1, %3 \n"
		" .set reorder \n"
		- "1: \n"
		" .subsection 2 \n"
		"2: b 1b \n"
		" .previous \n"
		+ "1: \n"
		" .set mips0 \n"
		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
		: "Ir" (i), "m" (v->counter)
		@@ -682,10 +682,10 @@ static __inline__ long atomic64_sub_if_p
		" beqz %0, 2f \n"
		" dsubu %0, %1, %3 \n"
		" .set reorder \n"
		- "1: \n"
		" .subsection 2 \n"
		"2: b 1b \n"
		" .previous \n"
		+ "1: \n"
		" .set mips0 \n"
		: "=&r" (result), "=&r" (temp), "=m" (v->counter)
		: "Ir" (i), "m" (v->counter)
		


			_______________________________________

	Mr Markus Gothe
	Software Engineer

	Phone: +46 (0)13 21 81 20 (ext. 1046)
	Fax: +46 (0)13 21 21 15
	Mobile: +46 (0)70 348 44 35
	Diskettgatan 11, SE-583 35 Linköping, Sweden
	www.27m.com

		
	

Re: Bug in atomic_sub_if_positive

[Thiemo Seufer]

Morten Larsen wrote:
> 
> > As far as I can tell the branch optimization fixes in 2.6.21 introduced
> > a bug in atomic_sub_if_positive that causes it to return even when the
> > sc instruction fails. The result is that e.g. down_trylock becomes
> > unreliable as the semaphore counter is not always decremented.
> 
> Previous patch was garbled by Outlook - this one should be clean:
> 
> --- a/include/asm-mips/atomic.h	2008-06-25 22:38:43.159739000 -0700
> +++ b/include/asm-mips/atomic.h	2008-06-25 22:39:07.552065000 -0700
> @@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
>  		"	beqz	%0, 2f					\n"
>  		"	 subu	%0, %1, %3				\n"
>  		"	.set	reorder					\n"
> -		"1:							\n"
>  		"	.subsection 2					\n"
>  		"2:	b	1b					\n"
>  		"	.previous					\n"
> +		"1:							\n"

AFAICS this change should make no difference to the generated code. I
suspect you assembler handles .subsection incorrectly. Can you provide
a disassembled exapmle which gets altered by this patch? Also, please
tell us the exact version of the assembler you use.


Thiemo

Re: Bug in atomic_sub_if_positive

[Atsushi Nemoto]

On Wed, 2 Jul 2008 10:59:56 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> > --- a/include/asm-mips/atomic.h	2008-06-25 22:38:43.159739000 -0700
> > +++ b/include/asm-mips/atomic.h	2008-06-25 22:39:07.552065000 -0700
> > @@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
> >  		"	beqz	%0, 2f					\n"
> >  		"	 subu	%0, %1, %3				\n"
> >  		"	.set	reorder					\n"
> > -		"1:							\n"
> >  		"	.subsection 2					\n"
> >  		"2:	b	1b					\n"
> >  		"	.previous					\n"
> > +		"1:							\n"
> 
> AFAICS this change should make no difference to the generated code. I
> suspect you assembler handles .subsection incorrectly. Can you provide
> a disassembled exapmle which gets altered by this patch? Also, please
> tell us the exact version of the assembler you use.

Why no defference?  The '1b' in subsection refer backword '1' label on
the source code (which is a label for LL insn in this case with the
patch) ?

Anyway I can provide them.  I'm using vanilla 2.17 and 2.18.

Without the patch:
801233bc <try_acquire_console_sem>:
801233bc:	lui	v0,0x8038
801233c0:	ll	a0,31976(v0)
801233c4:	addiu	v1,a0,-1
801233c8:	bltz	v1,801233dc <try_acquire_console_sem+0x20>
801233cc: 	nop
801233d0: 	sc	v1,31976(v0)
801233d4: 	beqz	v1,80124dac <sys_syslog+0x8>
801233d8: 	addiu	v1,a0,-1
801233dc: 	bltz	v1,801233fc <try_acquire_console_sem+0x40>
801233e0: 	li	v0,-1
...
80124dac:	b	801233dc <try_acquire_console_sem+0x20>
80124db0:	nop

With the patch:
801233bc <try_acquire_console_sem>:
801233bc:	lui	v0,0x8038
801233c0:	ll	a0,31976(v0)
801233c4:	addiu	v1,a0,-1
801233c8:	bltz	v1,801233dc <try_acquire_console_sem+0x20>
801233cc:	nop
801233d0:	sc	v1,31976(v0)
801233d4:	beqz	v1,80124dac <sys_syslog+0x8>
801233d8:	addiu	v1,a0,-1
801233dc:	bltz	v1,801233fc <try_acquire_console_sem+0x40>
801233e0:	li	v0,-1
...
80124dac:	b	801233c0 <try_acquire_console_sem+0x4>
80124db0:	nop


The patch looks correct.

---
Atsushi Nemoto

Re: Bug in atomic_sub_if_positive

[Thiemo Seufer]

Atsushi Nemoto wrote:
> On Wed, 2 Jul 2008 10:59:56 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> > > --- a/include/asm-mips/atomic.h	2008-06-25 22:38:43.159739000 -0700
> > > +++ b/include/asm-mips/atomic.h	2008-06-25 22:39:07.552065000 -0700
> > > @@ -292,10 +292,10 @@ static __inline__ int atomic_sub_if_posi
> > >  		"	beqz	%0, 2f					\n"
> > >  		"	 subu	%0, %1, %3				\n"
> > >  		"	.set	reorder					\n"
> > > -		"1:							\n"
> > >  		"	.subsection 2					\n"
> > >  		"2:	b	1b					\n"
> > >  		"	.previous					\n"
> > > +		"1:							\n"
> > 
> > AFAICS this change should make no difference to the generated code. I
> > suspect you assembler handles .subsection incorrectly. Can you provide
> > a disassembled exapmle which gets altered by this patch? Also, please
> > tell us the exact version of the assembler you use.
> 
> Why no defference?  The '1b' in subsection refer backword '1' label on
> the source code (which is a label for LL insn in this case with the
> patch) ?

Oh. Now that you spelled it out I see it, too. :-)

> Anyway I can provide them.  I'm using vanilla 2.17 and 2.18.
> 
> Without the patch:
> 801233bc <try_acquire_console_sem>:
> 801233bc:	lui	v0,0x8038
> 801233c0:	ll	a0,31976(v0)
> 801233c4:	addiu	v1,a0,-1
> 801233c8:	bltz	v1,801233dc <try_acquire_console_sem+0x20>
> 801233cc: 	nop
> 801233d0: 	sc	v1,31976(v0)
> 801233d4: 	beqz	v1,80124dac <sys_syslog+0x8>
> 801233d8: 	addiu	v1,a0,-1
> 801233dc: 	bltz	v1,801233fc <try_acquire_console_sem+0x40>
> 801233e0: 	li	v0,-1
> ...
> 80124dac:	b	801233dc <try_acquire_console_sem+0x20>
> 80124db0:	nop
> 
> With the patch:
> 801233bc <try_acquire_console_sem>:
> 801233bc:	lui	v0,0x8038
> 801233c0:	ll	a0,31976(v0)
> 801233c4:	addiu	v1,a0,-1
> 801233c8:	bltz	v1,801233dc <try_acquire_console_sem+0x20>
> 801233cc:	nop
> 801233d0:	sc	v1,31976(v0)
> 801233d4:	beqz	v1,80124dac <sys_syslog+0x8>
> 801233d8:	addiu	v1,a0,-1
> 801233dc:	bltz	v1,801233fc <try_acquire_console_sem+0x40>
> 801233e0:	li	v0,-1
> ...
> 80124dac:	b	801233c0 <try_acquire_console_sem+0x4>
> 80124db0:	nop
> 
> 
> The patch looks correct.

Agreed.


Thiemo

Re: Bug in atomic_sub_if_positive

[Atsushi Nemoto]

On Wed, 2 Jul 2008 11:51:55 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> > The patch looks correct.
> 
> Agreed.

Ralf, too late for 2.6.26?
Anyway I think it should go into -stable tree too.

---
Atsushi Nemoto

Re: Bug in atomic_sub_if_positive

[Ralf Baechle]

On Fri, Jul 04, 2008 at 12:04:26AM +0900, Atsushi Nemoto wrote:

> On Wed, 2 Jul 2008 11:51:55 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> > > The patch looks correct.
> > 
> > Agreed.
> 
> Ralf, too late for 2.6.26?

Pull request to Linus is out.

> Anyway I think it should go into -stable tree too.

It is.  This one is important.  Heck, I don't get how a kernel can be as
reliable as it was with an elefant like this :-)

  Ralf