Skip to contentSkip to conversation

add strncmp to PowerPC

PATCH In review Steven Rostedt 6 participants 10 messages Feb 29, 2008 – Mar 5, 2008 PowerPC

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 add strncmp to PowerPC

strncmp is defined in assembly for bootup, but it is not defined in the normal running kernel. This patch takes the strncmp code from the bootup and copies it to the kernel proper.

---
 arch/powerpc/kernel/ppc_ksyms.c |    1 +
 arch/powerpc/lib/string.S       |   12 ++++++++++++
 include/asm-powerpc/string.h    |    2 ++
 3 files changed, 15 insertions(+)
arch/powerpc/kernel/ppc_ksyms.c +1 -0
Index: linux-sched-devel.git/arch/powerpc/kernel/ppc_ksyms.c
===================================================================
@@ -78,6 +78,7 @@ EXPORT_SYMBOL(strncpy);
 EXPORT_SYMBOL(strcat);
 EXPORT_SYMBOL(strlen);
 EXPORT_SYMBOL(strcmp);
+EXPORT_SYMBOL(strncmp);
 
 EXPORT_SYMBOL(csum_partial);
 EXPORT_SYMBOL(csum_partial_copy_generic);
arch/powerpc/lib/string.S +12 -0
Index: linux-sched-devel.git/arch/powerpc/lib/string.S
===================================================================
@@ -75,6 +75,18 @@ _GLOBAL(strcmp)
 	beq	1b
 	blr
 
+_GLOBAL(strncmp)
+	mtctr	r5
+	addi	r5,r3,-1
+	addi	r4,r4,-1
+1:	lbzu	r3,1(r5)
+	cmpwi	1,r3,0
+	lbzu	r0,1(r4)
+	subf.	r3,r0,r3
+	beqlr	1
+	bdnzt	eq,1b
+	blr
+
 _GLOBAL(strlen)
 	addi	r4,r3,-1
 1:	lbzu	r0,1(r4)
include/asm-powerpc/string.h +2 -0
Index: linux-sched-devel.git/include/asm-powerpc/string.h
===================================================================
@@ -7,6 +7,7 @@
 #define __HAVE_ARCH_STRNCPY
 #define __HAVE_ARCH_STRLEN
 #define __HAVE_ARCH_STRCMP
+#define __HAVE_ARCH_STRNCMP
 #define __HAVE_ARCH_STRCAT
 #define __HAVE_ARCH_MEMSET
 #define __HAVE_ARCH_MEMCPY
@@ -18,6 +19,7 @@ extern char * strcpy(char *,const char *
 extern char * strncpy(char *,const char *, __kernel_size_t);
 extern __kernel_size_t strlen(const char *);
 extern int strcmp(const char *,const char *);
+extern int strncmp(const char *,const char *,__kernel_size_t);
 extern char * strcat(char *, const char *);
 extern void * memset(void *,int,__kernel_size_t);
 extern void * memcpy(void *,const void *,__kernel_size_t);
#1 lore raw
Quoted 6 lines · Steven Rostedt

strncmp is defined in assembly for bootup, but it is not defined in the normal running kernel. This patch takes the strncmp code from the bootup and copies it to the kernel proper.

---

Do we have any indication that it performs better than the C one ?

Ben.

Quoted 66 lines
 arch/powerpc/kernel/ppc_ksyms.c |    1 +
 arch/powerpc/lib/string.S       |   12 ++++++++++++
 include/asm-powerpc/string.h    |    2 ++
 3 files changed, 15 insertions(+)

Index: linux-sched-devel.git/arch/powerpc/kernel/ppc_ksyms.c
===================================================================

arch/powerpc/kernel/ppc_ksyms.c +1 -0
@@ -78,6 +78,7 @@ EXPORT_SYMBOL(strncpy);
 EXPORT_SYMBOL(strcat);
 EXPORT_SYMBOL(strlen);
 EXPORT_SYMBOL(strcmp);
+EXPORT_SYMBOL(strncmp);
 
 EXPORT_SYMBOL(csum_partial);
 EXPORT_SYMBOL(csum_partial_copy_generic);

Index: linux-sched-devel.git/arch/powerpc/lib/string.S
===================================================================

arch/powerpc/lib/string.S +12 -0
@@ -75,6 +75,18 @@ _GLOBAL(strcmp)
 	beq	1b
 	blr
 
+_GLOBAL(strncmp)
+	mtctr	r5
+	addi	r5,r3,-1
+	addi	r4,r4,-1
+1:	lbzu	r3,1(r5)
+	cmpwi	1,r3,0
+	lbzu	r0,1(r4)
+	subf.	r3,r0,r3
+	beqlr	1
+	bdnzt	eq,1b
+	blr
+
 _GLOBAL(strlen)
 	addi	r4,r3,-1
 1:	lbzu	r0,1(r4)

Index: linux-sched-devel.git/include/asm-powerpc/string.h
===================================================================

include/asm-powerpc/string.h +2 -0
@@ -7,6 +7,7 @@
 #define __HAVE_ARCH_STRNCPY
 #define __HAVE_ARCH_STRLEN
 #define __HAVE_ARCH_STRCMP
+#define __HAVE_ARCH_STRNCMP
 #define __HAVE_ARCH_STRCAT
 #define __HAVE_ARCH_MEMSET
 #define __HAVE_ARCH_MEMCPY
@@ -18,6 +19,7 @@ extern char * strcpy(char *,const char *
 extern char * strncpy(char *,const char *, __kernel_size_t);
 extern __kernel_size_t strlen(const char *);
 extern int strcmp(const char *,const char *);
+extern int strncmp(const char *,const char *,__kernel_size_t);
 extern char * strcat(char *, const char *);
 extern void * memset(void *,int,__kernel_size_t);
 extern void * memcpy(void *,const void *,__kernel_size_t);

_______________________________________________
Linuxppc-dev mailing list
[email protected]
https://ozlabs.org/mailman/listinfo/linuxppc-dev

#2 lore raw
Quoted 2 lines · Benjamin Herrenschmidt

Do we have any indication that it performs better than the C one ?

See below.

Quoted 5 lines

Ben.

Quoted 1 line
Quoted 12 lines

arch/powerpc/lib/string.S _GLOBAL(strcmp) · line 89

Quoted 12 lines
arch/powerpc/lib/string.S +12 -0
+_GLOBAL(strncmp)
+	mtctr	r5
+	addi	r5,r3,-1
+	addi	r4,r4,-1
+1:	lbzu	r3,1(r5)
+	cmpwi	1,r3,0
+	lbzu	r0,1(r4)
+	subf.	r3,r0,r3
+	beqlr	1
+	bdnzt	eq,1b
+	blr
+

And here's the objdump of the C version:

0000000000000080 <.strncmp>:

  80:   fb e1 ff f0     std     r31,-16(r1)
  84:   f8 21 ff c1     stdu    r1,-64(r1)
  88:   7c 69 1b 78     mr      r9,r3
  8c:   7c a0 2b 79     mr.     r0,r5
  90:   38 60 00 00     li      r3,0
  94:   7c 09 03 a6     mtctr   r0
  98:   7c 3f 0b 78     mr      r31,r1
  9c:   41 82 00 68     beq-    104 <.strncmp+0x84>
  a0:   89 69 00 00     lbz     r11,0(r9)
  a4:   88 04 00 00     lbz     r0,0(r4)
  a8:   7c 00 58 50     subf    r0,r0,r11
  ac:   78 00 06 20     clrldi  r0,r0,56
  b0:   2f a0 00 00     cmpdi   cr7,r0,0
  b4:   7c 00 07 74     extsb   r0,r0
  b8:   7c 03 03 78     mr      r3,r0
  bc:   40 9e 00 48     bne-    cr7,104 <.strncmp+0x84>
  c0:   2f ab 00 00     cmpdi   cr7,r11,0
  c4:   41 9e 00 40     beq-    cr7,104 <.strncmp+0x84>
  c8:   38 84 00 01     addi    r4,r4,1
  cc:   38 69 00 01     addi    r3,r9,1
  d0:   42 40 00 30     bdz-    100 <.strncmp+0x80>
  d4:   88 03 00 00     lbz     r0,0(r3)
  d8:   89 24 00 00     lbz     r9,0(r4)
  dc:   38 63 00 01     addi    r3,r3,1
  e0:   38 84 00 01     addi    r4,r4,1
  e4:   2f 20 00 00     cmpdi   cr6,r0,0
  e8:   7c 09 00 50     subf    r0,r9,r0
  ec:   78 00 06 20     clrldi  r0,r0,56
  f0:   2f a0 00 00     cmpdi   cr7,r0,0
  f4:   7c 00 07 74     extsb   r0,r0
  f8:   40 9e 00 08     bne-    cr7,100 <.strncmp+0x80>
  fc:   40 9a ff d4     bne+    cr6,d0 <.strncmp+0x50>
 100:   7c 03 03 78     mr      r3,r0
 104:   e8 21 00 00     ld      r1,0(r1)
 108:   eb e1 ff f0     ld      r31,-16(r1)
 10c:   4e 80 00 20     blr

I'll let you decide ;-)

Even if it was logically faster (which I still doubt) it's a hell of a lot of cache lines to waste.

-- Steve

#3 lore raw
Quoted 67 lines · Steven Rostedt
Quoted 2 lines · Benjamin Herrenschmidt

Do we have any indication that it performs better than the C one ?

See below.

Quoted 5 lines

Ben.

Quoted 1 line
Quoted 12 lines

arch/powerpc/lib/string.S _GLOBAL(strcmp) · line 89

Quoted 12 lines
arch/powerpc/lib/string.S +12 -0
+_GLOBAL(strncmp)
+	mtctr	r5
+	addi	r5,r3,-1
+	addi	r4,r4,-1
+1:	lbzu	r3,1(r5)
+	cmpwi	1,r3,0
+	lbzu	r0,1(r4)
+	subf.	r3,r0,r3
+	beqlr	1
+	bdnzt	eq,1b
+	blr
+

And here's the objdump of the C version:

0000000000000080 <.strncmp>:

  80:   fb e1 ff f0     std     r31,-16(r1)
  84:   f8 21 ff c1     stdu    r1,-64(r1)
  88:   7c 69 1b 78     mr      r9,r3
  8c:   7c a0 2b 79     mr.     r0,r5
  90:   38 60 00 00     li      r3,0
  94:   7c 09 03 a6     mtctr   r0
  98:   7c 3f 0b 78     mr      r31,r1
  9c:   41 82 00 68     beq-    104 <.strncmp+0x84>
  a0:   89 69 00 00     lbz     r11,0(r9)
  a4:   88 04 00 00     lbz     r0,0(r4)
  a8:   7c 00 58 50     subf    r0,r0,r11
  ac:   78 00 06 20     clrldi  r0,r0,56
  b0:   2f a0 00 00     cmpdi   cr7,r0,0
  b4:   7c 00 07 74     extsb   r0,r0
  b8:   7c 03 03 78     mr      r3,r0
  bc:   40 9e 00 48     bne-    cr7,104 <.strncmp+0x84>
  c0:   2f ab 00 00     cmpdi   cr7,r11,0
  c4:   41 9e 00 40     beq-    cr7,104 <.strncmp+0x84>
  c8:   38 84 00 01     addi    r4,r4,1
  cc:   38 69 00 01     addi    r3,r9,1
  d0:   42 40 00 30     bdz-    100 <.strncmp+0x80>
  d4:   88 03 00 00     lbz     r0,0(r3)
  d8:   89 24 00 00     lbz     r9,0(r4)
  dc:   38 63 00 01     addi    r3,r3,1
  e0:   38 84 00 01     addi    r4,r4,1
  e4:   2f 20 00 00     cmpdi   cr6,r0,0
  e8:   7c 09 00 50     subf    r0,r9,r0
  ec:   78 00 06 20     clrldi  r0,r0,56
  f0:   2f a0 00 00     cmpdi   cr7,r0,0
  f4:   7c 00 07 74     extsb   r0,r0
  f8:   40 9e 00 08     bne-    cr7,100 <.strncmp+0x80>
  fc:   40 9a ff d4     bne+    cr6,d0 <.strncmp+0x50>
 100:   7c 03 03 78     mr      r3,r0
 104:   e8 21 00 00     ld      r1,0(r1)
 108:   eb e1 ff f0     ld      r31,-16(r1)
 10c:   4e 80 00 20     blr
Quoted 4 lines

I'll let you decide ;-)

Even if it was logically faster (which I still doubt) it's a hell of a lot of cache lines to waste.

Indeed, but there are some corner cases that the C code handles. Like a length of 0 which may lead to infinite loop in the asm code.

OTOH, I'm a bit surprised by the extsb instructions in the compiler generated code. We don't compile with -fsigned-char, do we? The clrldi instructions are also extremely stupid.

Now that I think a bit more about it, I believe that the C version is
incorrect: the clrldi/extsb dance takes a value between -255 and +255 and collapses it into the -128 to 127 range, meaning that the return value may be wrong if we rely on the sign of the result. So unless I miss something, the problem is much more serious than just stupid code (I had just a look at the libc version in C and characters are cast to unsigned char before the comparison).

Regards,
Gabriel

#4 lore raw
Quoted 7 lines · Gabriel Paubert

Now that I think a bit more about it, I believe that the C version is
incorrect: the clrldi/extsb dance takes a value between -255 and +255 and collapses it into the -128 to 127 range, meaning that the return value may be wrong if we rely on the sign of the result. So unless I miss something, the problem is much more serious than just stupid code (I had just a look at the libc version in C and characters are cast to unsigned char before the comparison).

The latter is explicitly required by the C standard. Ie. even if your characters are signed they are always compared as unsigned by strcmp/strncmp/memcmp.

Andreas.

Signature · 4 lines
Andreas Schwab, SuSE Labs, [email protected]
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."
#5 lore raw
In reply to Gabriel Paubert
Quoted 2 lines
Quoted 2 lines

Even if it was logically faster (which I still doubt) it's a hell of a lot of cache lines to waste.

Yeah, 1 on 64-bit and 3 on 32-bit, that's a terrible lot.</sarcasm>

Quoted 6 lines

Indeed, but there are some corner cases that the C code handles. Like a length of 0 which may lead to infinite loop in the asm code.

OTOH, I'm a bit surprised by the extsb instructions in the compiler generated code. We don't compile with -fsigned-char, do we? The clrldi instructions are also extremely stupid.

Those are both necessary to be equivalent to the C code, which uses signed char explicitly. It is generally considered a Good Thing(tm) for the compiler to generate assembler code equivalent to the C code, even if the C code is wrong.

Quoted 2 lines

Now that I think a bit more about it, I believe that the C version is incorrect

It is. It's a great entry for the IOCCC as well.

I just tested the following (can't guarantee it's correct, just a PoC):

int strncmp(const char *s1, const char *s2, unsigned long /*size_t*/ len)

{
        while (len--) {
                unsigned char c1, c2;
                c1 = *s1++;
                c2 = *s2++;
                int cmp = c1 - c2;
                if (cmp)
                        return cmp;
                if (c1 == 0 || c2 == 0)
                        break;
        }
        return 0;
}

which generates (with GCC-4.2.3)

strncmp:

        addi 5,5,1
        mtctr 5
.L2:
        bdz .L11
        lbz 0,0(3)
        addi 3,3,1
        lbz 9,0(4)
        addi 4,4,1
        cmpwi 7,0,0
        subf. 0,9,0
        cmpwi 6,9,0
        bne- 0,.L4
        beq- 7,.L4
        bne+ 6,.L2
.L4:
        mr 3,0
        blr
.L11:
        li 0,0
        mr 3,0
        blr

which isn't horrid, although it does some weirdish things obviously.

Current GCC-4.4.0 generates

strncmp:

        addi 5,5,1
        mr 10,3
        mtctr 5
        li 11,0
        bdz .L7
        .p2align 4,,15
.L4:
        lbzx 0,10,11
        lbzx 9,4,11
        addi 11,11,1
        subf. 3,9,0
        cmpwi 6,9,0
        cmpwi 7,0,0
        bnelr 0
        beqlr 7
        beqlr 6
        bdnz .L4
.L7:
        li 3,0
        blr

which is about as good as it can get (well, it didn't realise you only need to test one of c1, c2 for zero. Did I say this was just proof-of-concept code?)

Segher

#6 lore raw
In reply to Benjamin Herrenschmidt
Quoted 1 line · Benjamin Herrenschmidt

Do we have any indication that it performs better than the C one ?

I would expect it to, given that the assembler one has two branches in the per-byte loop compared to 3 in the C version.

Paul.

#7 lore raw
Quoted 4 lines
Quoted 1 line

Do we have any indication that it performs better than the C one ?

I would expect it to, given that the assembler one has two branches in the per-byte loop compared to 3 in the C version.

But really, does it matter for strncmp() in the kernel?

Anyway, this asm code has bugs, as do both the current C version in the kernel, and the code I posted. We need to do better :-)

Segher

#8 lore raw
Quoted 2 lines · Segher Boessenkool

Anyway, this asm code has bugs, as do both the current C version in the kernel, and the code I posted. We need to do better :-)

The only bug I know of in the asm code is the behaviour when the count is zero. Do you know of any other?

Paul.

#9 lore raw
Quoted 5 lines
Quoted 2 lines

Anyway, this asm code has bugs, as do both the current C version in the kernel, and the code I posted. We need to do better :-)

The only bug I know of in the asm code is the behaviour when the count is zero. Do you know of any other?

No, that's the bug I meant. Sorry for using such inexact language.

Segher