egcs 1.0.1 miscompiles Linux 2.0.33

egcs 1.0.1 miscompiles Linux 2.0.33

[Thomas Koenig]

[x-posted to linux-kernel and egcs mailing lists]

Compiling the Linux kernel 2.0.33 with haifa-enabled egcs 1.0.1 causes a
repeatable kernel oops for me in vortex_open() during ifconfig.
I had used "-O3 -fomit-frame-pointer -mcpu=pentium" as the
architecture-specific settings for a 586.  This does not happen with
gcc 2.7.2.1.

Unable to handle kernel paging request at virtual address f6003b0d
current->tss.cr3 = 01d36000, 
*pde = 00000000
Oops: 0000
CPU:    0
EIP:    0010:[<001a7cf6>]
EFLAGS: 00010246
eax: 360036c0   ebx: 01020010   ecx: 00000000   edx: 00006000
esi: 001da00b   edi: 01f36f49   ebp: 00001002   esp: 01f36ed4
ds: 0018   es: 0018   fs: 002b   gs: 002b   ss: 0018
Process ifconfig (pid: 42, process nr: 9, stackpage=01f36000)
Stack: 001f68d0 001da00b 01f36f49 00001002 01fa43d8 01d672e8 00000001 01f36f00 
       40008000 00000000 bffffd48 01d47414 08003e6a 00008914 00124a05 0010a010 
       00000000 360036c0 00006000 0013cdc6 001f68d0 bffffd48 01d47414 08003e6a 
Call Trace: [<00124a05>] [<0010a010>] [<0013cdc6>] [<0013d687>] [<001544d6>] [<0013a7c1>] [<0012d0f9>] 
       [<0010a8d5>] 
Code: 8a 88 4d 04 00 00 83 e1 07 83 f9 07 74 6c 83 3d 90 6c 1f 00 

Using `../System.map' to map addresses to symbols.

>>EIP: 1a7cf6 <vortex_open+3a/768>
Trace: 124a05 <getblk+29/470>
Trace: 10a010 <dump_thread+c8/d0>
Trace: 13cdc6 <dev_ifsioc+2aa/664>
Trace: 13d687 <dev_ioctl+1b7/1f8>
Trace: 1544d6 <inet_ioctl+326/354>
Trace: 13a7c1 <sock_ioctl+1d/24>
Trace: 12d0f9 <sys_ioctl+105/114>
Trace: 10a8d5 <system_call+55/80>

Code: 1a7cf6 <vortex_open+3a/768> 
Code: 1a7cf6 <vortex_open+3a/768>  8a 88 4d 04 00 	movb   0x44d(%eax),%cl
Code: 1a7cfb <vortex_open+3f/768>  00 
Code: 1a7cfc <vortex_open+40/768>  83 e1 07       	andl   $0x7,%ecx
Code: 1a7cff <vortex_open+43/768>  83 f9 07       	cmpl   $0x7,%ecx
Code: 1a7d08 <vortex_open+4c/768>  74 6c          	je     1a7d70 <vortex_open+b4/768>
Code: 1a7d0a <vortex_open+4e/768>  83 3d 90 6c 1f 	cmpl   $0x0,0x1f6c90
Code: 1a7d0f <vortex_open+53/768>  00 00 
Code: 1a7d17 <vortex_open+5b/768>  90             	nop    
Code: 1a7d18 <vortex_open+5c/768>  90             	nop    
Code: 1a7d19 <vortex_open+5d/768>  90             	nop    

$ gcc -v
Reading specs from /usr/local/lib/gcc-lib/i586-pc-linux-gnulibc1/egcs-2.90.23/specs
gcc version egcs-2.90.23 980102 (egcs-1.0.1 release)

Here's a disassembly of the 3c59x.o file, up to the relevant place.

00000bc8 <vortex_open>:
     bc8:	83 ec 3c       	subl   $0x3c,%esp
     bcb:	55             	pushl  %ebp
     bcc:	57             	pushl  %edi
     bcd:	56             	pushl  %esi
     bce:	53             	pushl  %ebx
     bcf:	8b 44 24 50    	movl   0x50(%esp,1),%eax
     bd3:	8b 54 24 50    	movl   0x50(%esp,1),%edx
     bd7:	8b 40 14       	movl   0x14(%eax),%eax
     bda:	89 44 24 48    	movl   %eax,0x48(%esp,1)
     bde:	8b 52 44       	movl   0x44(%edx),%edx
     be1:	8b 4c 24 48    	movl   0x48(%esp,1),%ecx
     be5:	89 54 24 44    	movl   %edx,0x44(%esp,1)
     be9:	83 c1 0e       	addl   $0xe,%ecx
     bec:	b8 03 08 00 00 	movl   $0x803,%eax
     bf1:	89 ca          	movl   %ecx,%edx
     bf3:	66 ef          	outw   %ax,(%dx)
     bf5:	8b 54 24 48    	movl   0x48(%esp,1),%edx
     bf9:	ed             	inl    (%dx),%eax
     bfa:	89 c3          	movl   %eax,%ebx
     bfc:	8b 44 24 44    	movl   0x44(%esp,1),%eax
     c00:	31 c9          	xorl   %ecx,%ecx
     c02:	8a 88 4d 04 00 	movb   0x44d(%eax),%cl
     c07:	00 
     c08:	83 e1 07       	andl   $0x7,%ecx
     c0b:	83 f9 07       	cmpl   $0x7,%ecx
     c0e:	74 6c          	je     c7c <vortex_open+b4>
     c10:	83 3d 14 00 00 	cmpl   $0x1,0x14
[...]

-- 
Thomas Koenig, Thomas.Koenig@ciw.uni-karlsruhe.de, ig25@dkauni2.bitnet.
The joy of engineering is to find a straight line on a double
logarithmic diagram.

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Manfred Hollstein]

On Sat, 10 January 1998, 23:45:46, ig25@mvmap66.ciw.uni-karlsruhe.de wrote:

 > [x-posted to linux-kernel and egcs mailing lists]
 > 
 > Compiling the Linux kernel 2.0.33 with haifa-enabled egcs 1.0.1 causes a
 > repeatable kernel oops for me in vortex_open() during ifconfig.
 > I had used "-O3 -fomit-frame-pointer -mcpu=pentium" as the
 > architecture-specific settings for a 586.  This does not happen with
 > gcc 2.7.2.1.
 > 
 > Unable to handle kernel paging request at virtual address f6003b0d
 > current->tss.cr3 = 01d36000, 
 > *pde = 00000000
 > Oops: 0000

I saw similar behaviour with egcs and (even worse) with the latest gcc-2.8.0
snapshot. Interestingly, kernels >= 2.1.77 do not have such problems, so my
guess is, it's not only the compiler.

Manfred

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Jeffrey A Law]

  In message <199801102245.XAA00404@mvmap66.ciw.uni-karlsruhe.de>you write:
  > [x-posted to linux-kernel and egcs mailing lists]
  > 
  > Compiling the Linux kernel 2.0.33 with haifa-enabled egcs 1.0.1 causes a
  > repeatable kernel oops for me in vortex_open() during ifconfig.
  > I had used "-O3 -fomit-frame-pointer -mcpu=pentium" as the
  > architecture-specific settings for a 586.  This does not happen with
  > gcc 2.7.2.1.
Hmm, I've got a stock 2.0.33 working with the current 1.0.2 prerelease
sources with the following options for my two x86 boxes:
"-O2 -fomit-frame-pointer -mcpu=pentium -march=pentium" 
"-O2 -fomit-frame-pointer -mcpu=pentiumpro -march=pentiumpro" 

I didn't configure for haifa, and I also don't have 3c59x configured
into my kernel (cuz I don't have a vortex :-)

We're closing in on an egcs-1.0.2 release, and I'd like to nail down
any problems of this nature asap.   What can I do to help y'all
nail this problem down?

jeff

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Andi Kleen]

Jeffrey A Law <law@hurl.cygnus.com> writes:

>   In message <199801102245.XAA00404@mvmap66.ciw.uni-karlsruhe.de>you write:
>   > [x-posted to linux-kernel and egcs mailing lists]
>   > 
>   > Compiling the Linux kernel 2.0.33 with haifa-enabled egcs 1.0.1 causes a
>   > repeatable kernel oops for me in vortex_open() during ifconfig.
>   > I had used "-O3 -fomit-frame-pointer -mcpu=pentium" as the
>   > architecture-specific settings for a 586.  This does not happen with
>   > gcc 2.7.2.1.
> Hmm, I've got a stock 2.0.33 working with the current 1.0.2 prerelease
> sources with the following options for my two x86 boxes:
> "-O2 -fomit-frame-pointer -mcpu=pentium -march=pentium" 
> "-O2 -fomit-frame-pointer -mcpu=pentiumpro -march=pentiumpro" 
> 
> I didn't configure for haifa, and I also don't have 3c59x configured
> into my kernel (cuz I don't have a vortex :-)
> 
> We're closing in on an egcs-1.0.2 release, and I'd like to nail down
> any problems of this nature asap.   What can I do to help y'all
> nail this problem down?

Last time a similar problem came up (with pgcc) it was attributed to
some bad contraints in asm-i386/string.h. When I remember it right Linus
argued at this time that gcc wasn't following its own documented
behaviour so that he didn't intent to fix it in the kernel.

Maybe Linus can comment himself on the issue?

Afaik the ioport.c problem (which doesn't occur on egcs 1.0.x because
it doesn't do the ADDRESSOF optimization yet) and this string.h problem
that bites with some drivers are the only known problems that cause the
Linux kernel to be miscompiled by egcs/gcc 2.8.0

Here is a message from Gabriel Paubert with an analysis:

------------- please bite here ------------- bitte hier abbeissen ---------


Sorry if this message is long, but I think it is _very_ important. And
although it is probably more kernel related than gcc related, it is 
also interesting to all linux-gcc readers IMHO.

All started with the following exception report:

On Wed, 1 Oct 1997, Oliver Teuber wrote:

> hello
> 
> today i bought a new dec network adapter DE500-AA ... 
[snipped]
> Sep 30 23:57:02 olibox kernel: loading device 'eth0'...
> Sep 30 23:57:02 olibox kernel: Unable to handle kernel paging request at virtual address f3344544
> Sep 30 23:57:02 olibox kernel: current->tss.cr3 = 07466000, hr3 = 07466000
> Sep 30 23:57:02 olibox kernel: *pde = 00000000
> Sep 30 23:57:02 olibox kernel: Oops: 0000
> Sep 30 23:57:02 olibox kernel: CPU:    0
> Sep 30 23:57:02 olibox kernel: EIP:    0010:[<0884df3b>]
> Sep 30 23:57:02 olibox kernel: EFLAGS: 00010206
> Sep 30 23:57:02 olibox kernel: eax: 07470ea4   ebx: 00000000   ecx: 00000005   edx: 00000005
> Sep 30 23:57:02 olibox kernel: esi: 07470ea4   edi: 33344544   ebp: 07470ea4   esp: 07470e7c
> Sep 30 23:57:02 olibox kernel: ds: 0018   es: 0018   fs: 002b   gs: 002b   ss: 0018
> Sep 30 23:57:02 olibox kernel: Process insmod (pid: 96, process nr: 13, stackpage=07470000)
> Sep 30 23:57:02 olibox kernel: Stack: 07ce7408 00001000 00000001 07ce7408 ffffffff 00000000 0000ffff 001f81d8 
> Sep 30 23:57:02 olibox kernel:        07470eac 00000000 3f3f5f5f 0000003f 08851274 0885127a 08851280 08851286 
> Sep 30 23:57:02 olibox kernel:        0885128c 0884abb1 07470ee8 00001c80 07ce7408 00000000 ffffffed 07ce7408 
> Sep 30 23:57:02 olibox kernel: Call Trace: [<08851274>] [<0885127a>] [<08851280>] [<08851286>] [<0885128c>] [<0884abb1>] [<0884901a>] 
> Sep 30 23:57:02 olibox kernel:        [register_netdev+93/228] [<08849000>] [<08850afc>] [<08850b36>] [sys_init_module+963/1028] [<08849000>] [do_no_page+0/852] [<08850afc>] 
> Sep 30 23:57:02 olibox kernel:        [<08850b50>] [do_page_fault+0/816] [system_call+258/320] 
> Sep 30 23:57:02 olibox kernel: Code: f3 a6 74 0a 96 46 80 78 ff 00 75 ed 31 c0 85 c0 74 17 89 ee 
> 

After analysing I came to the conclusion that it occured in a strstr inlined
function. Oliver used pgcc to compile 2.0.30 and I could not reproduce the
problem with standard gcc. However the strange thing was the content
of %edi: "DE43" in ASCII. The pointed to value instead of the pointer !

Then after rambling through GCC doc (I've learnt a lot today :-)), I came 
to the conclusion that this is either a bug in pgcc or, more likely
bad constraints in asm-i386/string.h. Let us have a look at the strstr
asm statement:

__asm__ __volatile__(
	"cld\n\t" \
	"movl %4,%%edi\n\t"
	"repne\n\t"
	"scasb\n\t"
	"notl %%ecx\n\t"
	"decl %%ecx\n\t"	/* NOTE! This also sets Z if searchstring='' */
	"movl %%ecx,%%edx\n"
	"1:\tmovl %4,%%edi\n\t"
	"movl %%esi,%%eax\n\t"
	"movl %%edx,%%ecx\n\t"
	"repe\n\t"
	"cmpsb\n\t"
	"je 2f\n\t"		/* also works for empty string, see above */
	"xchgl %%eax,%%esi\n\t"
	"incl %%esi\n\t"
	"cmpb $0,-1(%%eax)\n\t"
	"jne 1b\n\t"
	"xorl %%eax,%%eax\n\t"
	"2:"
	:"=a" (__res):"0" (0),"c" (0xffffffff),"S" (cs),"g" (ct)
	:"cx","dx","di","si");
return __res;
}

If I correctly understand GCC doc, nothing prevents gcc from using %edi 
and %edx to compute argument %4. So I sent the following patch appended 
at the end which tried to prevent this by allocating %edi as an input 
parameter and used two additional scratch variables allocated by the
compiler as modified and used ("=&" constraints) parameters.

I think this is The Right Way (TM acknowledged) to declare scratch 
variables for inline assembly. gcc correctly recognizes that the variable is 
dead after the asm statement and does not generate any superfluous code. 

The de4x5 driver now works when compiled with pgcc (and quite well
according to Oliver's report). Later I got object files he compiled
without and without my patch and they confirmed my earlier hypothesis, the
second movl %4,%%edi used %edi in its addressing mode, hence the fault. 

Is it possible that many of the pgcc problems reported until now were due
to this ? (Again I think that it is not a pgcc problem, correct me if I am
wrong. I sometimes have problem understanding gcc doc [1]). 

According to my findings, the following functions in asm-i386/string.h are
potential victims of this problem (should I call it a bug ?), there
might be similar problems in other files (unlikely IMHO): 

   strspn, strcspn, strpbrk, strstr, and strtok. 

the cure is probably similar. But before starting to send a larger patch,
I would like to hear the opinion of experts on the subject :-)

   Gabriel.

[1] Could a native english speaker explain me the semantic subtleties of the
first of the following sentences :-); Intel took the pain to rewrite it 
between Pentium and PPro documentation, so it must be important ;):

"The C1 flag is set to 0; otherwise, cleared to 0. The C0, C2, and C3 
flags are undefined." (Intel Architecture Software Developer's Reference,
Volume 2 [24319101.pdf]. On fdecstp and fincstp instructions.)

Here is the patch, I've been trying to allow the compiler to use memory
instead of registers if it is too short on registers (eternal Intel problem),
but it has not been very successful. And BTW if I try to compile the
driver with -fpic, it apparently triggers a compiler bug :(. 

==============================================================================
--- linux-2.0.30/include/asm-i386/string.h.virgin	Wed Oct  1 10:55:48 1997
+++ linux-2.0.30/include/asm-i386/string.h	Wed Oct  1 14:18:21 1997
@@ -261,29 +261,32 @@
 #define __HAVE_ARCH_STRSTR
 extern inline char * strstr(const char * cs,const char * ct)
 {
-register char * __res;
+char * __res;
+const char *_ct;
+int len;
 __asm__ __volatile__(
 	"cld\n\t" \
-	"movl %4,%%edi\n\t"
+	"movl %%edi,%2\n\t"
 	"repne\n\t"
 	"scasb\n\t"
 	"notl %%ecx\n\t"
 	"decl %%ecx\n\t"	/* NOTE! This also sets Z if searchstring='' */
-	"movl %%ecx,%%edx\n"
-	"1:\tmovl %4,%%edi\n\t"
+	"movl %%ecx,%1\n"
+	"1:\tmovl %2,%%edi\n\t"
 	"movl %%esi,%%eax\n\t"
-	"movl %%edx,%%ecx\n\t"
 	"repe\n\t"
 	"cmpsb\n\t"
 	"je 2f\n\t"		/* also works for empty string, see above */
 	"xchgl %%eax,%%esi\n\t"
+	"movl %1,%%ecx\n\t"
 	"incl %%esi\n\t"
 	"cmpb $0,-1(%%eax)\n\t"
 	"jne 1b\n\t"
 	"xorl %%eax,%%eax\n\t"
 	"2:"
-	:"=a" (__res):"0" (0),"c" (0xffffffff),"S" (cs),"g" (ct)
-	:"cx","dx","di","si");
+	:"=a,a,a,a" (__res),  "=&r,?m,&r,?m" (len), "=&r,&r,?m,?m" (_ct)
+	:"0,0,0,0" (0),"c,c,c,c" (0xffffffff),"S,S,S,S" (cs),"D,D,D,D" (ct)
+	:"cx","di","si");
 return __res;
 }


-Andi

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Linus Torvalds]

On 25 Feb 1998, Andi Kleen wrote:
> 
> Last time a similar problem came up (with pgcc) it was attributed to
> some bad contraints in asm-i386/string.h. When I remember it right Linus
> argued at this time that gcc wasn't following its own documented
> behaviour so that he didn't intent to fix it in the kernel.

Right. As far as I can tell, Linux does completely legal asm statements. 
And here "legal" isn't some arbitrary decision by me, but according to all
the documentation and the obvious meaning of things. 

> Maybe Linus can comment himself on the issue?

I will.

> Afaik the ioport.c problem (which doesn't occur on egcs 1.0.x because
> it doesn't do the ADDRESSOF optimization yet)

Note that the ADDRESSOF optimization is a completely valid one, and when I
heard that gcc was breaking that particular thing I was very happy - it
meant only that gcc was getting more clever. I knew that code was fragile
when I wrote it, but it happened to work.

2.1.x already has another way of handling iopl() which is actually much
better than the broken one anyway. And if gcc optimizes that away I'll
consider it a bug. Back-porting that one to 2.0.x is very straightforward.

So I'd like to state again that I've never considered the ADDRESSOF
optimization a gcc bug, and that once I heard gcc was clever enough to
optimize the thing away I immediately patched the current 2.1.x kernel.

>					 and this string.h problem
> that bites with some drivers are the only known problems that cause the
> Linux kernel to be miscompiled by egcs/gcc 2.8.0

But the string.h one is definitely a gcc bug, and nobody has convinced me
otherwise. 

> Here is a message from Gabriel Paubert with an analysis:
> 
> ------------- please bite here ------------- bitte hier abbeissen ---------
> 
> 
> Sorry if this message is long, but I think it is _very_ important. And
> although it is probably more kernel related than gcc related, it is 
> also interesting to all linux-gcc readers IMHO.
> 
> All started with the following exception report:

[ removed for brevity ]

> After analysing I came to the conclusion that it occured in a strstr inlined
> function. Oliver used pgcc to compile 2.0.30 and I could not reproduce the
> problem with standard gcc. However the strange thing was the content
> of %edi: "DE43" in ASCII. The pointed to value instead of the pointer !
> 
> Then after rambling through GCC doc (I've learnt a lot today :-)), I came 
> to the conclusion that this is either a bug in pgcc or, more likely
> bad constraints in asm-i386/string.h. Let us have a look at the strstr
> asm statement:
> 
> __asm__ __volatile__(
> 	"cld\n\t" \
> 	"movl %4,%%edi\n\t"
> 	"repne\n\t"
> 	"scasb\n\t"
> 	"notl %%ecx\n\t"
> 	"decl %%ecx\n\t"	/* NOTE! This also sets Z if searchstring='' */
> 	"movl %%ecx,%%edx\n"
> 	"1:\tmovl %4,%%edi\n\t"
> 	"movl %%esi,%%eax\n\t"
> 	"movl %%edx,%%ecx\n\t"
> 	"repe\n\t"
> 	"cmpsb\n\t"
> 	"je 2f\n\t"		/* also works for empty string, see above */
> 	"xchgl %%eax,%%esi\n\t"
> 	"incl %%esi\n\t"
> 	"cmpb $0,-1(%%eax)\n\t"
> 	"jne 1b\n\t"
> 	"xorl %%eax,%%eax\n\t"
> 	"2:"
> 	:"=a" (__res):"0" (0),"c" (0xffffffff),"S" (cs),"g" (ct)
> 	:"cx","dx","di","si");
> return __res;
> }
> 
> If I correctly understand GCC doc, nothing prevents gcc from using %edi 
> and %edx to compute argument %4. So I sent the following patch appended 
> at the end which tried to prevent this by allocating %edi as an input 
> parameter and used two additional scratch variables allocated by the
> compiler as modified and used ("=&" constraints) parameters.

Incorrect. Gcc documentation _explicitly_ states that when you mark a
register clobbered ("cx","dx","di","si" in this case: %edi is definitely
on the list), then that register will NOT be used either for inputs of for
outputs, and that the inline assembly can read and write it multiple
times.

The fact that gcc uses the register for address computations is in clear
violation of the documentation that states that you can read and write the
register many times. QED. 

This is not to say that we can't work around problems like this, but I get
_very_ irritated when people claim that they are kernel bugs when the gcc
documentation is clearly of a different opinion (and the _only_ sane
reason for having a clobber-list in the first place is to mark registers
that are used as temporaries in the asm statement, so _obviously_ using
them for address arguments inside the asm is broken - I can't believe that
anybody can try to explain that away). 

The other known gcc-2.8.0 bug was that gcc-2.8.0 will move asm statements
that have no outputs around, even though (again) the gcc documentation
clearly states that an asm statement with no outputs is considered to be
"volatile". Again, this wasn't a question of interpretation or anything
like that - the documentation very clearly and explicitly states that.

In short, I think gcc should be fixed, or at the very least it should be a
_documented_ bug at which point I have no gripe with fixing it in the
kernel. But I refuse to work around undocumented bugs - that starts to
smell too much like microsoft, and then I might as well start using
Windows myself. 

		Linus

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Jeffrey A Law]

  In message < Pine.LNX.3.95.980225210447.14073B-100000@penguin.transmeta.com >yoite:
  > On 25 Feb 1998, Andi Kleen wrote:
  > > 
  > > Last time a similar problem came up (with pgcc) it was attributed to
  > > some bad contraints in asm-i386/string.h. When I remember it right Linus
  > > argued at this time that gcc wasn't following its own documented
  > > behaviour so that he didn't intent to fix it in the kernel.
  > 
  > Right. As far as I can tell, Linux does completely legal asm statements. 
  > And here "legal" isn't some arbitrary decision by me, but according to all
  > the documentation and the obvious meaning of things. 
Agreed.  The documentation is a little ambigious, but the natural
meaning of a clobber would be that it can't be used for an input
operand *or* in the address of an input operand.

  > > Afaik the ioport.c problem (which doesn't occur on egcs 1.0.x because
  > > it doesn't do the ADDRESSOF optimization yet)
  > 
  > Note that the ADDRESSOF optimization is a completely valid one, and when I
  > heard that gcc was breaking that particular thing I was very happy - it
  > meant only that gcc was getting more clever. I knew that code was fragile
  > when I wrote it, but it happened to work.
Ah.  Good.  I was under the impression it was producing incorrect
code, but apparently the asm was slightly bogus.

  > >					 and this string.h problem
  > > that bites with some drivers are the only known problems that cause the
  > > Linux kernel to be miscompiled by egcs/gcc 2.8.0
  > 
  > But the string.h one is definitely a gcc bug, and nobody has convinced me
  > otherwise. 
Agreed.  And I've got that message from Gabriel.  But what I do
not have is something I can compile which will show the bug.  Can
someone please send me an actual use of the asm which generates
incorrect code?  ie, something I can feed directly into the compiler
so that I can analyze why the compiler is generating the wrong code.

The asm itself isn't enough, these kinds of bugs usually depend on
the use and code surrounding the use.

Thanks,

jeff

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Gabriel Paubert]

On Fri, 27 Feb 1998, Jeffrey A Law wrote:

> Agreed.  And I've got that message from Gabriel.  But what I do
> not have is something I can compile which will show the bug.  Can
> someone please send me an actual use of the asm which generates
> incorrect code?  ie, something I can feed directly into the compiler
> so that I can analyze why the compiler is generating the wrong code.

I did send an example of bad code generation yesterday. I have appended it
again in case it got lost. But perhaps it's sitting idle somewhere in
between, I've already seen E-mail messages taking 2 months to reach me,
and 3 weeks is not uncommon here :-(

> The asm itself isn't enough, these kinds of bugs usually depend on
> the use and code surrounding the use.

True, and it also strongly depends on compiler options in this case. But
this code (I unfortunately deleted the example that generated bad code
when I had 2.7.2.1 but it was _very_ similar to this one). 

It seems that the clobbered registers are not considered as early-clobbers
for address generation. When using explicit earlyclobbers, I've never been
able to generate similar code even when increasing register pressure,
instead the compiler exits claiming that a forbidden register was spilled,
for example %esp ! 

  Regards,
  Gabriel.

== Excerpt from yesterday's message ==

On Wed, 25 Feb 1998, Jeffrey A Law wrote:

> I think the best way to proceed is for someone to give me a hunk of
> code that I can feed the compiler that will show a case where a
> clobber is being used for input addressing.  That way I can debug
> the compiler and see what's really happening.

I can't keep up with the weekly updates, so my GCC currently is:
 gcc version egcs-2.91.06 980122 (gcc-2.8.0 release)

The following code breaks when compiled with -fno-strength-reduce, but
independantly of -O2/-O3, -fomit-frame-pointer, and -m[345]86:

===============================================================================
#include <linux/string.h>

int count_substring_matches(char **haystacks, char **needles)
{
	int hits=0, i, j;
	for(i=0; haystacks[i]; i++) {
		for(j=0; needles[j]; j++) {
		  	if (strstr(haystacks[i], needles[j])) hits++;
		}
	}
	return hits;
}
===============================================================================

generates for the strstr function:

===============================================================================
#APP
	cld
	movl (%ebx,%edx,4),%edi
	repne
	scasb
	notl %ecx
	decl %ecx
	movl %ecx,%edx
1:	movl (%ebx,%edx,4),%edi
	movl %esi,%eax
	movl %edx,%ecx
	repe
	cmpsb
	je 2f
	xchgl %eax,%esi
	incl %esi
	cmpb $0,-1(%eax)
	jne 1b
	xorl %eax,%eax
	2:
#NO_APP
===============================================================================

in this precise case the problem is with %edx. Other compilers/versions
used %edi in the address computation. Note that it generates correct code
when I exchange the order of the nested loops !

If I add -fpic the addressing mode is even able to use two
clobbered registers and becomes (%edx,%edi,4), and only -fstrength-reduce
-fomit-frame-pointer generates correct pic code. Otherwise the compiler
sometimes reloads %edi with movl (%edx),%edi. 

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Jeffrey A Law]

  In message < Pine.HPP.3.96.980227155318.28492P-100000@gra-ux1.iram.es >you writ > 
  > I did send an example of bad code generation yesterday. I have appended it
  > again in case it got lost. But perhaps it's sitting idle somewhere in
  > between, I've already seen E-mail messages taking 2 months to reach me,
  > and 3 weeks is not uncommon here :-(
You did.  My over aggressive morning filing of messages put it into
the low priority bug queue...  I found it when I went back and looked
harder for it.  I'll spend some time in the debugger this weekend
to see what's happening.

jeff

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Jeffrey A Law]

  In message <Pine.HPP.3.96.980227155318.28492P-100000@gra-ux1.iram.es>you write:
  > #include <linux/string.h>
  > 
  > int count_substring_matches(char **haystacks, char **needles)
  > {
  > 	int hits=0, i, j;
  > 	for(i=0; haystacks[i]; i++) {
  > 		for(j=0; needles[j]; j++) {
  > 		  	if (strstr(haystacks[i], needles[j])) hits++;
  > 		}
  > 	}
  > 	return hits;
  > }
Thanks.  In general, you're better off running testcases like this though
the compiler with "-save-temps" and sending the .i file.  That way it
doesn't depend on whatever include files happen to be on my system.
Doing so also allows me to test it with a cross compiler from my
normal work machines instead of having to go to one of my linux
machines to create the .i file, then move it back to one of my normal
work machines.

extern inline char * strstr(const char * cs,const char * ct)
{
register char * __res;
__asm__ __volatile__(
        "cld\n\t"       "movl %4,%%edi\n\t"
        "repne\n\t"
        "scasb\n\t"
        "notl %%ecx\n\t"
        "decl %%ecx\n\t"
        "movl %%ecx,%%edx\n"
        "1:\tmovl %4,%%edi\n\t"
        "movl %%esi,%%eax\n\t"
        "movl %%edx,%%ecx\n\t"
        "repe\n\t"
        "cmpsb\n\t"
        "je 2f\n\t"
        "xchgl %%eax,%%esi\n\t"
        "incl %%esi\n\t"
        "cmpb $0,-1(%%eax)\n\t"
        "jne 1b\n\t"
        "xorl %%eax,%%eax\n\t"
        "2:"
        :"=a" (__res):"0" (0),"c" (0xffffffff),"S" (cs),"g" (ct)
        :"cx","dx","di","si");
return __res;
}

This asm has some serious problems.  Any attempt to fix the compiler
to be more strict with how it uses registers which are clobbered by
the asm is going to lead to problems.

Note that cx and si are mentioned in both the input and clobber
list.   This is wrong.   You've set up a case where the inputs
and clobbers must be in the same register.  This can't work and
is just going to cause problems.

I'm not an x86 hacker, so it's not really clear to me how you
would rewrite that asm.  But it's clearly going to need to be
rewritten.  And until it is, I can't do much on the compiler
side as I don't have a valid testcase.

jeff

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[John Carr]

I think this is beyond the limits of what can or should be done with gcc's
inline assembly.  strstr is a volatile asm which needs 18 instructions, 5
registers, and takes a long time to run.  I've seen cases like this where
the separate function is faster than the inlined version because of reduced
register pressure in the caller.

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Linus Torvalds]

On Sun, 1 Mar 1998, Jeffrey A Law wrote:
> 
> I'm not an x86 hacker, so it's not really clear to me how you
> would rewrite that asm.  But it's clearly going to need to be
> rewritten.  And until it is, I can't do much on the compiler
> side as I don't have a valid testcase.

Ok, so here's a hypothetical example that is not x86-specific. In fact it
is not specific to any CPU at all, as I made it up (and as such it is a
bad example, but it does show the basic problem..) 

Let's say that this particular made up CPU has a strange way of disabling
interrupts, where it has to load the value through a special register that
gcc doesn't even know about and the instruction saves the old value in the
same register. The chip designers decided that you can only use one
specific GP register to read and write this exception register (let's call
this register "ecx" for no other reason than the fact that only intel is
so silly). So we have a instruction like this:

	rdwrexception %ecx

that writes the exception register with the value in %ecx, and puts the
old exception value into %ecx. 

Now, the exception register actually contains more than just the interrupt
bits, so when you want to restore the interrupt bits into the exception
register you have to do something like this:

	#
	# write safe value to exception register (disable everything)
	# in order to get the current value
	#
	movl $0xffffffff,%ecx
	rdwrexception %ecx

	#
	# mask off the interrupt bit and set it to the saved value
	#
	andl $0xfffffffe,%ecx
	orl restore_value,%ecx
	rdwrexception %ecx

And the inline assembly would look a bit like this:

	#define restore_flags(restore_value) \
		asm("rdwrexception %0\n\t" \
		    "andl $0xfffffffe,%0\n\t" \
		    "orl %1,%0\n\t" \
		    "rdwrexception %0" \
		    : /* no outputs */ \
		    :"c" (0xffffffff), \
		     "g" (restore_value) \
		    :"cx")

Now, how should I re-write this to avoid the clobber?

I could use "=c" and "0" to tell gcc that %ecx is a read-write thing and
will change. But that doesn't tell gcc that it mustn't use %ecx for the
value in "restore_value": what if somebody were to say

	restore_flags(0xffffffff);

then gcc would decide that as it already has the constant 0xffffffff in
%ecx, then it should use %ecx for "restore_value" too. But that would be
wrong, because then you'd get

	orl %ecx,%ecx

which wouldn't do what you wanted..

See the problem? I think that clobbers are the perfect answer, and as they
have worked for previous gcc versions for this same problem, I think it is
the _correct_ answer. I'm willing to be convinced otherwise, but I'd
really like to know how to do something like the above without using a
clobber (and without making the asm code worse: I can easily think of many
ways to "fix" the problem if I was willing to make worse assembly code).

		Linus

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Linus Torvalds]

On Sun, 1 Mar 1998, John Carr wrote:
> 
> I think this is beyond the limits of what can or should be done with gcc's
> inline assembly.  strstr is a volatile asm which needs 18 instructions, 5
> registers, and takes a long time to run.  I've seen cases like this where
> the separate function is faster than the inlined version because of reduced
> register pressure in the caller.

Oh, agreed. The main reason for having the string functions as inline
assembly is that I used them to teach myself inline asm back in 1991 when
there was almost no documentation on them and certainly no good examples.
They are certainly not inline assembly for any good speed reasons (at
least most of them).

I suspect that if you checked out Linux-0.01 you'd find most of the string
stuff there, and in a form that resembles the current stuff ;)

But the problem they bring up (exactly _because_ they are complex) are
generic problems. So as far as I'm concerned this really isn't an issue
about "how to get strstr() to do the right thing" but a more generic issue
of "how can I trust gcc to do inline asm correctly if it can't handle the
complex cases"..

		Linus

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Jeffrey A Law]

  In message < 199803012155.QAA12210@jfc. >you write:
  > 
  > I think this is beyond the limits of what can or should be done with gcc's
  > inline assembly.  strstr is a volatile asm which needs 18 instructions, 5
  > registers, and takes a long time to run.  I've seen cases like this where
  > the separate function is faster than the inlined version because of reduced
  > register pressure in the caller.
Regardless of the size, the strchr asm is exposing some problems in
the generic asm mechanisms.  Like Linus, my main concern is with
fixing those generic problems, not strstr specifically.



jeff

Re: egcs 1.0.1 miscompiles Linux 2.0.33

[Richard Henderson]

On Sun, Mar 01, 1998 at 01:59:56PM -0800, Linus Torvalds wrote:
> 	#define restore_flags(restore_value) \
> 		asm("rdwrexception %0\n\t" \
> 		    "andl $0xfffffffe,%0\n\t" \
> 		    "orl %1,%0\n\t" \
> 		    "rdwrexception %0" \
> 		    : /* no outputs */ \
> 		    :"c" (0xffffffff), \
> 		     "g" (restore_value) \
> 		    :"cx")
> 
> Now, how should I re-write this to avoid the clobber?
> 
> I could use "=c" and "0" to tell gcc that %ecx is a read-write thing and
> will change. But that doesn't tell gcc that it mustn't use %ecx for the
> value in "restore_value"

You should use "=&c" to say that the output should use a new register.
That output will be shared with no other input except an explicit "0".


r~

asm operands (Was: Re: egcs 1.0.1 miscompiles Linux 2.0.33)

[Kamil Iskra]

On Sun, 1 Mar 1998, Jeffrey A Law wrote:

> You've set up a case where the inputs
> and clobbers must be in the same register.  This can't work and
> is just going to cause problems.

Is this only true for x86 and other SMALL_REGISTER_CLASSES targets, or is
it a general rule that the same registers cannot be specified in input and
clobber parts of asm statements?

Say, on m68k, if I do an asm like this:

whatever=({
  register int ret __asm__("d0");
  register int arg1 __asm__("d0")=whatever;
  register int arg2 __asm__("d1")=whatever;

  __asm__ __volatile__ ("/* some os-specific hackery */"
  : "=r" (ret)
  : "r" (arg1), "r" (arg2)
  : "d0", "d1", "a0", "a1", "fp0", "fp1", "cc", "memory");

  ret;
});

Is this correct or not? I'm asking, for we've been using this construction
extensively for years under the AmigaOS target to access the system
libraries, and it worked fine (unless we passed too many arguments, but
that's a different story, I think).

/ Kamil Iskra    AmigaOS  Linux/i386  Linux/m68k               \
| GeekGadgets GCC maintainer   UNIX system administrator       |
| iskra@student.uci.agh.edu.pl  kiskra@ernie.icslab.agh.edu.pl |
\ kamil@dwd.interkom.pl   http://student.uci.agh.edu.pl/~iskra /

Re: asm operands (Was: Re: egcs 1.0.1 miscompiles Linux 2.0.33)

[Jeffrey A Law]

  In message < Pine.GSO.3.95.980302123005.21281B-100000@ernie >you write:
  > On Sun, 1 Mar 1998, Jeffrey A Law wrote:
  > 
  > > You've set up a case where the inputs
  > > and clobbers must be in the same register.  This can't work and
  > > is just going to cause problems.
  > 
  > Is this only true for x86 and other SMALL_REGISTER_CLASSES targets, or is
  > it a general rule that the same registers cannot be specified in input and
  > clobber parts of asm statements?
It's a general rule.


  > Say, on m68k, if I do an asm like this:
  > 
  > whatever=({
  >   register int ret __asm__("d0");
  >   register int arg1 __asm__("d0")=whatever;
  >   register int arg2 __asm__("d1")=whatever;
  > 
  >   __asm__ __volatile__ ("/* some os-specific hackery */"
  >   : "=r" (ret)
  >   : "r" (arg1), "r" (arg2)
  >   : "d0", "d1", "a0", "a1", "fp0", "fp1", "cc", "memory");
  > 
  >   ret;
  > });
I think you get away with this because you've assigned those variables
to registers.  If you hadn't bound arg1 and arg2 to registers, then
I would have expected the compiler to eventually crash on this kind
of asm statement if it ever needed to use d0/d1 as spill regs.

Obviously since you have more regs than the x86, the compiler is
less likely to need to spill in general and is even less likely to
need to use d0/d1 as spill regs.

jeff