Integer overflows in memchr

[Po Lu]

It has been brought to my attention that a defective memchr is
distributed with certain Android E-book readers with Android 2.3.5 that
is liable to integer overflows with large values of N:

  memchr ("", 0, SIZE_MAX);

returns NULL, since:

Dump of assembler code for function memchr:
   0xafd20644 <+0>:     adds    r2, r0, r2              @ <- overflow
   0xafd20646 <+2>:     adds    r3, r0, #3
   0xafd20648 <+4>:     push    {r4, r5, lr}
   0xafd2064a <+6>:     cmp     r0, r2                  @ <- r0 is consequently 
smaller than r2
   0xafd2064c <+8>:     bcs.n   0xafd20686 <memchr+66>
   0xafd2064e <+10>:    ldrb.w  r4, [r3, #-3]
   0xafd20652 <+14>:    cmp     r4, r1
   0xafd20654 <+16>:    beq.n   0xafd20688 <memchr+68>
   0xafd20656 <+18>:    adds    r4, r0, #1
   0xafd20658 <+20>:    cmp     r2, r4
   0xafd2065a <+22>:    bls.n   0xafd20686 <memchr+66>
   0xafd2065c <+24>:    ldrb    r5, [r0, #1]
   0xafd2065e <+26>:    cmp     r5, r1
   0xafd20660 <+28>:    beq.n   0xafd2066e <memchr+42>
   0xafd20662 <+30>:    adds    r4, r0, #2
   0xafd20664 <+32>:    cmp     r2, r4
   0xafd20666 <+34>:    bls.n   0xafd20686 <memchr+66>
   0xafd20668 <+36>:    ldrb    r5, [r0, #2]
   0xafd2066a <+38>:    cmp     r5, r1
   0xafd2066c <+40>:    bne.n   0xafd20672 <memchr+46>
   0xafd2066e <+42>:    mov     r0, r4
   0xafd20670 <+44>:    b.n     0xafd20688 <memchr+68>
   0xafd20672 <+46>:    cmp     r2, r3
   0xafd20674 <+48>:    bls.n   0xafd20686 <memchr+66>
   0xafd20676 <+50>:    ldrb    r4, [r0, #3]
   0xafd20678 <+52>:    adds    r3, #4
   0xafd2067a <+54>:    cmp     r4, r1
   0xafd2067c <+56>:    bne.n   0xafd20682 <memchr+62>
   0xafd2067e <+58>:    subs    r0, r3, #4
   0xafd20680 <+60>:    b.n     0xafd20688 <memchr+68>
   0xafd20682 <+62>:    adds    r0, #4
   0xafd20684 <+64>:    b.n     0xafd2064a <memchr+6>
   0xafd20686 <+66>:    movs    r0, #0                  @ <- NULL is returned
   0xafd20688 <+68>:    pop     {r4, r5, pc}

disassembly of libc.so samples extracted from real Android devices
reveals that defective versions of memchr are present until Android 4.3,
API level 18.

As it appears, this is a misbegotten (and poorly) "optimized" version of
memchr that derives a destination pointer from the source, and deduces
whether the limit has been encountered by a simple integer magnitude
comparison between the two pointers, which prompts an immediate return
when the offset is such that the first sum overflows.  This extends to
affect strnlen, which is implemented around memchr, and assumes that a
NULL value indicates that the NULL byte is beyond the provided limit:

Dump of assembler code for function strnlen:
   0xafd20ab4 <+0>:     push    {r4, r5, r6, lr}
   0xafd20ab6 <+2>:     mov     r4, r1                  @ <- MAXLEN
   0xafd20ab8 <+4>:     mov     r2, r4
   0xafd20aba <+6>:     movs    r1, #0
   0xafd20abc <+8>:     mov     r5, r0
   0xafd20abe <+10>:    bl      0xafd20644 <memchr>
   0xafd20ac2 <+14>:    cbz     r0, 0xafd20ac6 <strnlen+18>
   0xafd20ac4 <+16>:    subs    r4, r0, r5
   0xafd20ac6 <+18>:    mov     r0, r4                  @ <- MAXLEN returned
   0xafd20ac8 <+20>:    pop     {r4, r5, r6, pc}

producing crashes in this function in Emacs:

static int
store_mode_line_string (const char *string, Lisp_Object lisp_string,
                        bool copy_string,
                        int field_width, int precision, Lisp_Object props)
{
  ptrdiff_t len;
  int n = 0;

  if (string != NULL)
    {
      len = strnlen (string, precision <= 0 ? SIZE_MAX : precision);
      lisp_string = make_string (string, len);

when PRECISION is 0, and SIZE_MAX is returned, causing `make_string' to
be called to allocate a string of negative length.  Perhaps Gnulib
should provide a module with replacements for memchr and affected string
functions, viz., strnlen, memmem, wmemchr, mbstowcs, mbsrtowcs,
wcsrtombs, and wcstombs.