An optimization bug in egcs 1.0.2?

An optimization bug in egcs 1.0.2?

[H.J. Lu]

Hi,

While compiling glibc 2.0.7 with egcs 1.0.2, I noticed that egcs 1.0.2
turns

if (imap->l_global)
  {
   /* This object is in the global scope list.  Remove it.  */
   struct link_map **tail = _dl_global_scope_end;
   do
     --tail;
    while (*tail != imap);
    --_dl_global_scope_end;
    memcpy (tail, tail + 1,
      (void *) _dl_global_scope_end -  (void *) tail);
    _dl_global_scope_end[0] = NULL;
    _dl_global_scope_end[1] = NULL;
  }

into

if (imap->l_global)
  {
   /* This object is in the global scope list.  Remove it.  */
   struct link_map **tail = _dl_global_scope_end;
   do
     --tail;
    while (*tail != imap);
    --_dl_global_scope_end;
    _dl_global_scope_end[0] = NULL;
    _dl_global_scope_end[1] = NULL;
    memcpy (tail, tail + 1,
      (void *) _dl_global_scope_end -  (void *) tail);
    _dl_global_scope_end[1] = NULL;
  }

when I use -O2 -fPIC. As the result, the resuling binary doesn't work
since _dl_global_scope_end[0] is within (void *) tail + 1 and 
(void *) tail + 1 + (void *) _dl_global_scope_end -  (void *) tail.
Is that normal for a C compiler to do it?

BTW, I changed it to

if (imap->l_global)
  {
   /* This object is in the global scope list.  Remove it.  */
   struct link_map **tail = _dl_global_scope_end;
   do
     --tail;
    while (*tail != imap);
    memcpy (tail, tail + 1,
      (void *) _dl_global_scope_end -  (void *) tail);
    --_dl_global_scope_end;
  }

since _dl_global_scope_end [0] and _dl_global_scope_end [1] are
always NULL to begin with. It works fine for me.

Thanks.


-- 
H.J. Lu (hjl@gnu.org)

Re: An optimization bug in egcs 1.0.2?

[John Carr]

The code calls memcpy with overlapping objects.  That is undefined in
ANSI C; use memmove instead.  (It also subtracts pointers to void so
the authors presumably didn't care about ANSI C, but the misuse of
memcpy is a real problem.)

There may also be a bug in egcs in addition to the bug in the code.
Can you generate a standalone test case with annotated assembly code?


> if (imap->l_global)
>   {
>    /* This object is in the global scope list.  Remove it.  */
>    struct link_map **tail = _dl_global_scope_end;
>    do
>      --tail;
>     while (*tail != imap);
>     --_dl_global_scope_end;
>     memcpy (tail, tail + 1,
>       (void *) _dl_global_scope_end -  (void *) tail);
>     _dl_global_scope_end[0] = NULL;
>     _dl_global_scope_end[1] = NULL;
>   }

Re: An optimization bug in egcs 1.0.2?

[H.J. Lu]

> 
> 
> The code calls memcpy with overlapping objects.  That is undefined in
> ANSI C; use memmove instead.  (It also subtracts pointers to void so
> the authors presumably didn't care about ANSI C, but the misuse of
> memcpy is a real problem.)

It is from the dynamic linker in glibc 2. memcpy is safe there.
memcpy is used for optimization.

> 
> There may also be a bug in egcs in addition to the bug in the code.
> Can you generate a standalone test case with annotated assembly code?

I don't think there is a question on egcs. I don't want to spend
any more time on it since it has been fixed in glibc 2. If you really
want to look into it, I can do it when I find time.

> 
> 
> > if (imap->l_global)
> >   {
> >    /* This object is in the global scope list.  Remove it.  */
> >    struct link_map **tail = _dl_global_scope_end;
> >    do
> >      --tail;
> >     while (*tail != imap);
> >     --_dl_global_scope_end;
> >     memcpy (tail, tail + 1,
> >       (void *) _dl_global_scope_end -  (void *) tail);
> >     _dl_global_scope_end[0] = NULL;
> >     _dl_global_scope_end[1] = NULL;
> >   }
> 


-- 
H.J. Lu (hjl@gnu.org)

Re: An optimization bug in egcs 1.0.2?

[Jeffrey A Law]

  In message < m0yHHxm-00058JC@ocean.lucon.org >you write:
  > > 
  > > 
  > > The code calls memcpy with overlapping objects.  That is undefined in
  > > ANSI C; use memmove instead.  (It also subtracts pointers to void so
  > > the authors presumably didn't care about ANSI C, but the misuse of
  > > memcpy is a real problem.)
  > 
  > It is from the dynamic linker in glibc 2. memcpy is safe there.
  > memcpy is used for optimization.
Is the compiler producing an inline expansion of memcpy?  If so
you'll need to compile with -fno-builtin.


jeff

Re: An optimization bug in egcs 1.0.2?

[H.J. Lu]

> 
> On Mon, Mar 23, 1998 at 04:53:09PM -0800, H.J. Lu wrote:
> > It is from the dynamic linker in glibc 2. memcpy is safe there.
> > memcpy is used for optimization.
> 
> No, memcpy on overlapping objects is wrong.  
> 
>     memcpy (tail, tail + 1,                                                  
>       (void *) _dl_global_scope_end -  (void *) tail);                       
> 
> This may happen to work on the particular implementation
> of memcpy used on i386, but will fail for others.
> 

I was wrong. The bug was in glibc 2.0.7. Here is the code in question.
As you can see, _dl_global_scope_end is adjusted before calling
memmove, which, BTW, is not inlined by egcs 1.0.2. The dynamic linker
will then call fixup () where there is

	*_dl_global_scope_end = NULL;

As the result, when memmove is entered, memory pointed to by tail + 1
has been already changed.

Ulrich, we should go over every place in dl where _dl_global_scope_end
is used to double check if there is a similar bug.

Thanks.

-- 
H.J. Lu (hjl@gnu.org)
----
#include <string.h>
#include <link.h>

void
_dl_remove (struct link_map *map)
{
  struct link_map **tail = _dl_global_scope_end;
  do
    --tail;
  while (*tail != map);
  --_dl_global_scope_end;
  memmove (tail, tail + 1,
  	(char *) _dl_global_scope_end - (char *) tail);
  _dl_global_scope_end [0] = NULL;
  _dl_global_scope_end [1] = NULL;
}

Re: An optimization bug in egcs 1.0.2?

[H.J. Lu]

> 
> On Mon, Mar 23, 1998 at 04:53:09PM -0800, H.J. Lu wrote:
> > It is from the dynamic linker in glibc 2. memcpy is safe there.
> > memcpy is used for optimization.
> 
> No, memcpy on overlapping objects is wrong.  
> 
>     memcpy (tail, tail + 1,                                                  
>       (void *) _dl_global_scope_end -  (void *) tail);                       
> 
> This may happen to work on the particular implementation
> of memcpy used on i386, but will fail for others.
> 

That has nothing to do with memcpy. I extracted the miscompiled
portion from glibc 2.0.7 into a separate file. I am enclosing
the source code and the asm output. I believe something is wrong.


-- 
H.J. Lu (hjl@gnu.org)
----dl-remove.c---
#include <string.h>
#include <link.h>

void
_dl_remove (struct link_map *map)
{
  struct link_map **tail = _dl_global_scope_end;
  do
    --tail;
  while (*tail != map);
  --_dl_global_scope_end;
  memmove (tail, tail + 1,
  	(char *) _dl_global_scope_end - (char *) tail);
  _dl_global_scope_end [0] = NULL;
  _dl_global_scope_end [1] = NULL;
}
----
	.file	"dl-remove.c"
	.version	"01.01"
/ GNU C version egcs-2.90.27 980315 (egcs-1.0.2 release) (i586-unknown-linux-gnulibc1) compiled by GNU C version egcs-2.90.26 980308 (egcs-1.0.2 prerelease).
/ options passed:  -g -g0 -O2 -Wall -Winline -Wno-parentheses
/ -Wstrict-prototypes -Wwrite-strings -fno-exceptions -fPIC -fno-common
/ options enabled:  -fdefer-pop -fcse-follow-jumps -fcse-skip-blocks
/ -fexpensive-optimizations -fthread-jumps -fstrength-reduce -fpeephole
/ -fforce-mem -ffunction-cse -finline -fkeep-static-consts -fcaller-saves
/ -fpcc-struct-return -frerun-cse-after-loop -frerun-loop-opt
/ -fschedule-insns2 -fPIC -fverbose-asm -fgnu-linker -fregmove
/ -falias-check -fargument-alias -m80387 -mhard-float -mno-soft-float
/ -mieee-fp -mfp-ret-in-387 -mcpu=pentium -march=pentium

gcc2_compiled.:
.text
	.align 4
.globl _dl_remove
	.type	 _dl_remove,@function
_dl_remove:
	pushl %ebp
	movl %esp,%ebp
	pushl %ebx
	call .L9
.L9:
	popl %ebx
	addl $_GLOBAL_OFFSET_TABLE_+[.-.L9],%ebx
	movl _dl_global_scope_end@GOT(%ebx),%eax
	movl 8(%ebp),%ecx
	movl (%eax),%edx
	.align 4
.L5:
	addl $-4,%edx
	cmpl %ecx,(%edx)
	jne .L5
	movl _dl_global_scope_end@GOT(%ebx),%eax
	addl $-4,(%eax)
	movl _dl_global_scope_end@GOT(%ebx),%eax
	movl (%eax),%eax
	subl %edx,%eax
	pushl %eax
	leal 4(%edx),%eax
	pushl %eax
	pushl %edx
	call memmove@PLT
	movl _dl_global_scope_end@GOT(%ebx),%eax
	movl (%eax),%eax
	movl $0,(%eax)
	movl _dl_global_scope_end@GOT(%ebx),%eax
	movl (%eax),%eax
	movl $0,4(%eax)
	movl -4(%ebp),%ebx
	movl %ebp,%esp
	popl %ebp
	ret
.Lfe1:
	.size	 _dl_remove,.Lfe1-_dl_remove
	.ident	"GCC: (GNU) egcs-2.90.27 980315 (egcs-1.0.2 release)"

Re: An optimization bug in egcs 1.0.2?

[Richard Henderson]

On Mon, Mar 23, 1998 at 04:53:09PM -0800, H.J. Lu wrote:
> It is from the dynamic linker in glibc 2. memcpy is safe there.
> memcpy is used for optimization.

No, memcpy on overlapping objects is wrong.  

    memcpy (tail, tail + 1,                                                  
      (void *) _dl_global_scope_end -  (void *) tail);                       

This may happen to work on the particular implementation
of memcpy used on i386, but will fail for others.


r~