[Bug libc/12019] memchr overshoots on Alpha

[Bug libc/12019] memchr overshoots on Alpha

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=12019

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/12019] memchr overshoots on Alpha

[gabravier at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=12019

Gabriel Ravier <gabravier at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gabravier at gmail dot com

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/12019] memchr overshoots on Alpha

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2010-09-26 18:14 -------
Pushed.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[mcree at orcon dot net dot nz]

------- Additional Comments From mcree at orcon dot net dot nz  2010-09-26 08:32 -------
Created an attachment (id=5004)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=5004&action=view)
Fix compile errors in the new memchr

When testing memchr I originally compiled it separately from the glibc source. 
Now that I have compiled it from git master I see that there is a necessary
header file that is not included.  Also the compiler doesn't like a bitwise and
applied to a pointer so I added some explicit casts.


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2010-09-23 15:09 -------
I've merged the branch to master.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |FIXED


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[mcree at orcon dot net dot nz]

------- Additional Comments From mcree at orcon dot net dot nz  2010-09-23 10:48 -------
RTH's patch certainly fixes the segfault that was in the test case reported by
Debian.  Speed tests also show it runs faster when searching large memory
buffers.  I allocated 100Mbytes memory, filled it with 0xff except for a 0x00
half way in, then timed the memchr() search for the 0x00.  With current memchr()
(alphaev6 optimised version from Debian's libc6.1-alphaev67 package) get (after
averaging over 10 memchr() searches):
 
              cycles:  129525563 (scaled from 50.0%)
        instructions:   50746044 (scaled from 50.0%)
        cache-misses:     837238 (scaled from 50.0%)
        mbox-replays:    4416463 (scaled from 25.0%)

With RTH's new version get (compiled with -O2 -mcpu=ev67):

              cycles:   52405038 (scaled from 50.0%)
        instructions:   62017822 (scaled from 50.0%)
        cache-misses:    1034687 (scaled from 50.0%)
        mbox-replays:       6866 (scaled from 25.0%)

so while it executes more CPU instructions it does it much faster!  It's over
twice as fast as the old version.  Nice.  The almost complete removal of Mbox
replay traps is presumably a significant part of the speedup.


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-22 22:47 -------
Lib-ification on your git branch looked okay to me.
http://sourceware.org/git/?p=glibc-ports.git;a=commitdiff;h=10ae74bdc
Are you planning on merging this to mainline?

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2010-09-15 17:47 -------
Thanks.  I've edited the file into form for libc and have pushed the
patch into glibc-ports rth/testing branch.  Please sanity-check the
transformation into library form.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |WAITING


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #4985 is|1                           |0
              patch|                            |


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-15 16:43 -------
Created an attachment (id=4985)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4985&action=view)
third attempt

An added if handles the case when the cache line loop rejected all n bytes;
this attempt passes on my gnulib test on Alpha.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #4984 is|0                           |1
           obsolete|                            |


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-15 16:28 -------
Still fails, but this time at a different place:

Program received signal SIGSEGV, Segmentation fault.
0x0000000120000c84 in memchr1 (xs=0x20000027eff, xc=85, n=0)
    at ../axp-memchr.c:164
164	  current = *s_align;
(gdb) bt
#0  0x0000000120000c84 in memchr1 (xs=0x20000027eff, xc=85, n=0)
    at ../axp-memchr.c:164
#1  0x0000000120001850 in main () at ../../gltests/test-memchr.c:277
(gdb) up
#1  0x0000000120001850 in main () at ../../gltests/test-memchr.c:277
277	            ASSERT (MEMCHR (mem, 'U', n) == NULL);
(gdb) p n
$1 = 257


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2010-09-15 16:04 -------
Created an attachment (id=4984)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4984&action=view)
Second attempt.

This version should have the N <= 8 case fixed.  Please re-try.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #4980 is|0                           |1
           obsolete|                            |


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-15 13:41 -------
Andreas: this is NOT an invalid use of memchr.  Reread the Austin Group ruling
on memchr, http://www.opengroup.org/austin/docs/austin_454.txt, which I linked
to in the original post:

"A number of changes were agreed as follows

Change p1284 lines 42163-42164
In the DESCRIPTION remove "of the object" from

The memchr( ) function shall locate the first occurrence of c (converted
to an unsigned char) in the initial n bytes (each interpreted as unsigned
char) of the object pointed to by s.

In the RETURN VALUE section

The memchr( ) function shall return a pointer to the located byte,
or a null pointer if the byte does not occur in the object.

to
The memchr( ) function shall return a pointer to the located byte,
or a null pointer if the byte is not found.

Add to DESCRIPTION
Implementations shall behave as if they read the memory byte by byte
from the beginning of the bytes pointed to by s and stop at the first
occurrence of c."

Also, see http://sourceware.org/bugzilla/show_bug.cgi?id=11230, where the same
bug was fixed for IA64 for the same reason.



-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[schwab at linux-m68k dot org]

------- Additional Comments From schwab at linux-m68k dot org  2010-09-15 08:27 -------
For string function the standard already says that the access never goes beyond
the first nul character.  This is quite different to the memory function.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[schwab at linux-m68k dot org]

------- Additional Comments From schwab at linux-m68k dot org  2010-09-15 08:23 -------
It's even stronger: the initial n characters of the *object* pointed to by s.  So
there is supposed to be an object at s that is at least n bytes in size.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2010-09-15 08:06 -------
Andreas,

7.22.5 of ISO/IEC 9899:201x (the description of memchr) never refers to S as
being an array.

Compare:

7.20.6.5. The snprintf function [...] The snprintf function is equivalent to
fprintf, except that the output is written into an array (specified by argument
s) rather than to a stream.

7.22.5. The memchr function locates the first occurrence of c (converted to an
unsigned char) in the initial n characters (each interpreted as unsigned char)
of the object pointed to by s.


Besides, even if your interpretation was correct, going beyond what the standard
promises would have other advantages.  For example: 1) consistency, as the
manual specifies that "rawmemchr (str, '\0') will never go beyond the end of the
string; 2) ease of implementing rawmemchr specially for the Alpha, based on the
Alpha memchr.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[schwab at linux-m68k dot org]

------- Additional Comments From schwab at linux-m68k dot org  2010-09-15 07:42 -------
(In reply to comment #1)
> Stepping through the assembly reveals that the segfault is happening on:
> 
> memchr(page-1,0,3)
> 
> where page[-1] is '\0' and page is the start of an inaccessible page; when it
> should be successfully returning page-1.

This is an invalid use of memchr, see 7.1.4:

If a function argument is described as being an array, the pointer actually
passed to the function shall have a value such that all address computations
and accesses to objects (that would be valid if the pointer did point to the
first element of such an array) are in fact valid. 

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-14 21:31 -------
Richard, I compiled patch 4980 on Alpha, and ran it through gnulib's testsuite;
it still fails for the same reason:

0x000000012000095c in ldq_u (s=2199023419392) at ../../gltests/test-memchr.c:28
28	  return *(const word *)(s & -8);
(gdb) bt
#0  0x000000012000095c in ldq_u (s=2199023419392)
    at ../../gltests/test-memchr.c:28
#1  0x0000000120000a38 in memchr1 (xs=0x20000027fff, xc=85, n=2)
    at ../../gltests/test-memchr.c:62
#2  0x0000000120001948 in main () at ../../gltests/test-memchr.c:298

57	  if (unlikely (n <= 8))
58	    {
59	      /* Tweak the standard unaligned quadword load sequence by issuing
60	       the second ldq_u at (s + n - 1) instead of (s + 8 - 1).  This
61	        avoids crossing a page boundary when S+N doesn't.  */
62	      word last = extqh (ldq_u (s + n - 1), s);
63	      word first = extql (current, s);

In other words, s+n-1 might STILL validly cross a page boundary, in the case
where n is an over-estimate.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2010-09-14 18:36 -------
Created an attachment (id=4980)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4980&action=view)
Proposed alpha re-implementation

I came up with this re-write last year when the Debian people
pinged me about this problem.  But I never heard back from the
guy that was supposed to test it on real hardware.

>From the ifdef alpha bit at the top you can see that I could
validate the algorithm from an x64 native host, but that isn't
really good enough.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[mattst88 at gmail dot com]

------- Additional Comments From mattst88 at gmail dot com  2010-09-14 18:35 -------
Does reverting
http://sourceware.org/git/?p=glibc-ports.git;a=commit;h=200b5faee1cfac10d831e9b278ef294ca3119f53
fix it?

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[vapier at gentoo dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |toolchain at gentoo dot org


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[vapier at gentoo dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mattst88 at gmail dot com


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

------- Additional Comments From eblake at redhat dot com  2010-09-14 18:30 -------
Stepping through the assembly reveals that the segfault is happening on:

memchr(page-1,0,3)

where page[-1] is '\0' and page is the start of an inaccessible page; when it
should be successfully returning page-1.


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[drepper at gmail dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|drepper at gmail dot com    |rth at gcc dot gnu dot org
             Status|NEW                         |ASSIGNED


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/12019] memchr overshoots on Alpha

[eblake at redhat dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   GCC host triplet|                            |alphaev56-unknown-linux-gnu


http://sourceware.org/bugzilla/show_bug.cgi?id=12019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.