Bug 19387

On x86_64 (and other archs?), memchr in the following program fails to find the searched character. The program prints "(nil)".

----------------------------------------------------------------------

#include <stdalign.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

int main()
{
  alignas(64) char w[65] = {0}; /* all the array is filled with 0s */
  /* we will search for a 1 */
  w[64] = 1; /* placing a 1 right after the end of 64-byte block */

  printf("%p\n", memchr(&w[63], 1, SIZE_MAX));
}

----------------------------------------------------------------------

The failing conditions:
- the address of the string (s) modulo 64 is in the range 49 .. 63;
- there is no searched char in the rest of the 64-byte block;
- the number (n) of bytes to search is in the range (size_t)-15 .. (size_t)-1;
- n + (uintptr_t)s % 16 overflows.

The implementation of memchr used on my machine is in sysdeps/x86_64/memchr.S:

----------------------------------------------------------------------

    21  /* fast SSE2 version with using pmaxub and 64 byte loop */
    22  
    23          .text
    24  ENTRY(memchr)
    25          movd    %rsi, %xmm1
    26          mov     %rdi, %rcx

Move (uintptr_t)s into %rcx.

    27  
    28          punpcklbw %xmm1, %xmm1
    29          test    %rdx, %rdx
    30          jz      L(return_null)
    31          punpcklbw %xmm1, %xmm1
    32  
    33          and     $63, %rcx

Compute (uintptr_t)s % 64 in %rcx.

    34          pshufd  $0, %xmm1, %xmm1
    35  
    36          cmp     $48, %rcx
    37          ja      L(crosscache)

If (uintptr_t)s % 64 > 48 go to L(crosscache).

[skip]

    55          .p2align 4
    56  L(crosscache):
    57          and     $15, %rcx

Compute (uintptr_t)s % 16 in %rcx.

    58          and     $-16, %rdi
    59          movdqa  (%rdi), %xmm0
    60  
    61          pcmpeqb %xmm1, %xmm0
    62  /* Check if there is a match.  */
    63          pmovmskb %xmm0, %eax
    64  /* Remove the leading bytes.  */
    65          sar     %cl, %eax
    66          test    %eax, %eax
    67          je      L(unaligned_no_match)

No match in the unaligned part of the string, so go to L(unaligned_no_match).

[skip]

    77          .p2align 4
    78  L(unaligned_no_match):
    79          add     %rcx, %rdx

Add (uintptr_t)s % 16 to n in %rdx.

    80          sub     $16, %rdx
    81          jbe     L(return_null)

If n + (uintptr_t)s % 16 <= 16 return NULL.

----------------------------------------------------------------------

Checked on x86_64:
- git master (glibc-2.22-616-g5537f46) -- failed;
- Debian jessie (glibc 2.19-18+deb8u1) -- failed;
- Debian wheezy (eglibc 2.13-38+deb7u8) -- failed.

Checked on x86_64 with gcc -m32:
- Debian jessie (glibc 2.19-18+deb8u1) -- failed;
- Debian wheezy (eglibc 2.13-38+deb7u8) -- ok.

I didn't look into the details of 32-bit version.

Not finding a char can have evident security implications but using it with n=SIZE_MAX seems rare hence filing it publicly.