diff mbox

[v3] Improve strtok(_r) performance

Message ID e4210655-f5d9-69ad-b1f7-248d87c48401@linaro.org
State New
Headers show

Commit Message

Adhemerval Zanella Netto Dec. 14, 2016, 7:43 p.m. UTC 
On 14/12/2016 17:26, Adhemerval Zanella wrote:
> 

> 

> On 14/12/2016 16:25, Wilco Dijkstra wrote:

>> Hi,

>>

>> In powerpc64/power7/memchr.S this bit looks suspicious:

>>

>> L(done):

>> #ifdef __LITTLE_ENDIAN__

>>         addi    r0,r3,-1

>>         andc    r0,r0,r3

>>         popcntd r0,r0         /* Count trailing zeros.  */

>> #else

>>         cntlzd  r0,r3         /* Count leading zeros before the match.  */

>> #endif

>>         cmpld   r8,r7         /* Are we on the last dword?  */

>>         srdi    r0,r0,3       /* Convert leading/trailing zeros to bytes.  */

>>         add     r3,r8,r0

>>         cmpld   cr7,r0,r5     /* If on the last dword, check byte offset.  */

>>         bnelr

>>         blelr   cr7

>>         li      r3,0

>>         blr

>>

>> When the size is the maximum and the input pointer is at offset 2 or larger within an 8-byte aligned address, r7 == r8, and it will return NULL if it matches in the first 8 bytes since the match appears to be after the end pointer. When it matches later, r7 != r8 and it works.

> 

> I think this snippet is ok, the problem is at r7 calculation where it should

> handle overflow.  This simple test triggers the issue:

> 

> #define _GNU_SOURCE 1

> #include <string.h>

> #include <stdio.h>

> 

> void *

> my_rawmemchr (const void *s, int c)

> { 

>   if (c != '\0')

>     return memchr (s, c, (size_t)-1);

>   return (char *)s + strlen (s);

> }

> 

> int main ()

> {

>   // p=0x3fffb057fe00 | aling=10

>   int seek_char = 0x41;

>   size_t align = 10;

>   unsigned char input [32];

>   input[10] = 0x34;

>   input[11] = 0x78;

>   input[12] = 0x3d;

>   input[13] = 0x7b;

>   input[14] = 0xa1;

>   input[15] = seek_char;

> 

>   printf ("%p\n", my_rawmemchr (input+align, seek_char));

>   printf ("%p\n", rawmemchr (input+align, seek_char));

>   return 0;

> }

> 

> On POWER7 memchr.S:

> 

>  24 ENTRY (__memchr)

>  25         CALL_MCOUNT 3

>  26         dcbt    0,r3

>  27         clrrdi  r8,r3,3

>  28         insrdi  r4,r4,8,48

>  29         add     r7,r3,r5      /* Calculate the last acceptable address.  */

> 

> And using the example above:

> 

> (gdb) i r r3 r5

> r3             0x3fffffffeab2   70368744172210

> r5             0xffffffffffffffff       18446744073709551615

> (gdb) ni

> 30      in ../sysdeps/powerpc/powerpc64/power7/memchr.S

> (gdb) i r r7

> r7             0x3fffffffeab1   70368744172209

> 

> If we set r7 to maximum pointer value (0xf...f) memchr returns the expected result.

> 


This patch should fix test-rawmemchr by adding a saturated addition when
calculating the last double address to check.  I will prepare a patch
when the make check finished on the powerpc64le machine I have access.
diff mbox

Patch

diff --git a/sysdeps/powerpc/powerpc64/power7/memchr.S b/sysdeps/powerpc/powerpc64/power7/memchr.S
index 03f0d7c..34605a7 100644
--- a/sysdeps/powerpc/powerpc64/power7/memchr.S
+++ b/sysdeps/powerpc/powerpc64/power7/memchr.S
@@ -26,7 +26,15 @@  ENTRY (__memchr)
        dcbt    0,r3
        clrrdi  r8,r3,3
        insrdi  r4,r4,8,48
-       add     r7,r3,r5      /* Calculate the last acceptable address.  */
+
+       /* Calculate the last acceptable address and also take care of possible
+          overflow by using a large size.  */
+       add     r7,r3,r5
+       subfc   r6,r3,r7
+       subfe   r9,r9,r9
+       extsw   r6,r9
+       or      r7,r7,r6
+
        insrdi  r4,r4,16,32
        cmpldi  r5,32
        li      r9, -1