Fix v9/64-bit strcmp when string ends in multiple zero bytes.
diff mbox

Message ID 20140430.160000.1171411871854680001.davem@davemloft.net
State New
Headers show

Commit Message

David Miller April 30, 2014, 8 p.m. UTC
Can I get a quick ACK for the strcmp testcase change?  I also plan to
commit this also to the active release branches.

Thanks!

	[BZ #16885]
	* sysdeps/sparc/sparc64/strcmp.S: Fix end comparison handling when
	multiple zero bytes exist at the end of a string.
	Reported by Aurelien Jarno <aurelien@aurel32.net>

	* string/test-strcmp.c (check): Add explicit test for situations where
	there are multiple zero bytes after the first.
---
 ChangeLog                      |  8 ++++++++
 string/test-strcmp.c           | 29 +++++++++++++++++++++++++++++
 sysdeps/sparc/sparc64/strcmp.S | 31 +++++++++++++++++++++++++++++++
 3 files changed, 68 insertions(+)

Comments

Carlos O'Donell May 1, 2014, 5:34 a.m. UTC | #1
On 04/30/2014 04:00 PM, David Miller wrote:
> 
> Can I get a quick ACK for the strcmp testcase change?  I also plan to
> commit this also to the active release branches.

The test is a bit "narrow" in scope and I'd like to see you
expand it just a bit.

OK with changes.

> diff --git a/string/test-strcmp.c b/string/test-strcmp.c
> index b395dc7..d1c73a3 100644
> --- a/string/test-strcmp.c
> +++ b/string/test-strcmp.c
> @@ -329,6 +329,35 @@ check (void)
>  		FOR_EACH_IMPL (impl, 0)
>  		check_result (impl, s1 + i1, s2 + i2, exp_result);
>        }
> +
> +  /* Test cases where there are multiple zero bytes after the first.  */
> +
> +  for (size_t i = 0; i < 8; i++)

Cover the full length of the available strings e.g. MIN(l1, l2);

> +    {
> +      int exp_result;
> +
> +      for (CHAR val = 0x01; val < 0x10; val++)

Permute over all char values e.g. [0x1,0xff] or val < 0x100;

> +	{
> +	  for (size_t j = 0; j < i; j++)
> +	    {
> +	      s1[j] = val;
> +	      s2[j] = val;
> +	    }
> +
> +	  s1[i] = 0x00;
> +	  s2[i] = val;
> +
> +	  for (size_t j = i + 1; j < 16; j++)
> +	    {
> +	      s1[j] = 0x00;
> +	      s2[j] = 0x00;
> +	    }

As i only moves forward and j fills with val up to i,
this loop clears more than it should?

Hoist this out of the loop and just initialize both of
the strings to 0x00.

Given that s2 is larger than s1 you can show that s2
is always terminated even though you add an extra val
in there to make the strcmp fail.

> +
> +	  exp_result = SIMPLE_STRCMP (s1, s2);
> +	  FOR_EACH_IMPL (impl, 0)
> +	    check_result (impl, s1, s2, exp_result);
> +	}
> +    }
>  }

OK with those changes and verification that it still
catches the original failure case and hasn't exponentially
blown up the test time :}

Cheers,
Carlos.
David Miller May 1, 2014, 4:05 p.m. UTC | #2
From: "Carlos O'Donell" <carlos@redhat.com>
Date: Thu, 01 May 2014 01:34:01 -0400

> On 04/30/2014 04:00 PM, David Miller wrote:
>> +    {
>> +      int exp_result;
>> +
>> +      for (CHAR val = 0x01; val < 0x10; val++)
> 
> Permute over all char values e.g. [0x1,0xff] or val < 0x100;

I tried that already, just making this change alone causes the test to
take minutes rather then just a few seconds.

I'll see if I can mitigate the cost and still add the extra coverage.

Thanks.
Carlos O'Donell May 1, 2014, 4:27 p.m. UTC | #3
On 05/01/2014 12:05 PM, David Miller wrote:
> From: "Carlos O'Donell" <carlos@redhat.com>
> Date: Thu, 01 May 2014 01:34:01 -0400
> 
>> On 04/30/2014 04:00 PM, David Miller wrote:
>>> +    {
>>> +      int exp_result;
>>> +
>>> +      for (CHAR val = 0x01; val < 0x10; val++)
>>
>> Permute over all char values e.g. [0x1,0xff] or val < 0x100;
> 
> I tried that already, just making this change alone causes the test to
> take minutes rather then just a few seconds.
> 
> I'll see if I can mitigate the cost and still add the extra coverage.

Perhaps not all values, but just values with interesting patterns then?

for (CHAR val = 0x01; val < 0x100; val << 1) ?

Cheers,
Carlos.
Richard Earnshaw May 1, 2014, 4:54 p.m. UTC | #4
On 01/05/14 17:27, Carlos O'Donell wrote:
> On 05/01/2014 12:05 PM, David Miller wrote:
>> From: "Carlos O'Donell" <carlos@redhat.com>
>> Date: Thu, 01 May 2014 01:34:01 -0400
>>
>>> On 04/30/2014 04:00 PM, David Miller wrote:
>>>> +    {
>>>> +      int exp_result;
>>>> +
>>>> +      for (CHAR val = 0x01; val < 0x10; val++)
>>>
>>> Permute over all char values e.g. [0x1,0xff] or val < 0x100;
>>
>> I tried that already, just making this change alone causes the test to
>> take minutes rather then just a few seconds.
>>
>> I'll see if I can mitigate the cost and still add the extra coverage.
> 
> Perhaps not all values, but just values with interesting patterns then?
> 
> for (CHAR val = 0x01; val < 0x100; val << 1) ?
> 
> Cheers,
> Carlos.
> 
> 

I would expect the values that are likely to cause problems will lie
somewhere in the set {0x00, 0x01, 0x7e, 0x7f, 0x80, 0x81, 0xfe, 0xff},
given the way zero detection tends to work, plus the fact that standard
arithmetic is often done with potential for overflow from one byte to
another.

R.
Carlos O'Donell May 1, 2014, 7:42 p.m. UTC | #5
On 05/01/2014 12:54 PM, Richard Earnshaw wrote:
> On 01/05/14 17:27, Carlos O'Donell wrote:
>> On 05/01/2014 12:05 PM, David Miller wrote:
>>> From: "Carlos O'Donell" <carlos@redhat.com>
>>> Date: Thu, 01 May 2014 01:34:01 -0400
>>>
>>>> On 04/30/2014 04:00 PM, David Miller wrote:
>>>>> +    {
>>>>> +      int exp_result;
>>>>> +
>>>>> +      for (CHAR val = 0x01; val < 0x10; val++)
>>>>
>>>> Permute over all char values e.g. [0x1,0xff] or val < 0x100;
>>>
>>> I tried that already, just making this change alone causes the test to
>>> take minutes rather then just a few seconds.
>>>
>>> I'll see if I can mitigate the cost and still add the extra coverage.
>>
>> Perhaps not all values, but just values with interesting patterns then?
>>
>> for (CHAR val = 0x01; val < 0x100; val << 1) ?
>>
>> Cheers,
>> Carlos.
>>
>>
> 
> I would expect the values that are likely to cause problems will lie
> somewhere in the set {0x00, 0x01, 0x7e, 0x7f, 0x80, 0x81, 0xfe, 0xff},
> given the way zero detection tends to work, plus the fact that standard
> arithmetic is often done with potential for overflow from one byte to
> another.

David's final patch goes through all values from [0x01,0xff], so it
covers all of these cases. Thanks for the review!

Cheers,
Carlos.

Patch
diff mbox

diff --git a/ChangeLog b/ChangeLog
index a6ffe08..62f5fd1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,13 @@ 
 2014-04-30  David S. Miller  <davem@davemloft.net>
 
+	[BZ #16885]
+	* sysdeps/sparc/sparc64/strcmp.S: Fix end comparison handling when
+	multiple zero bytes exist at the end of a string.
+	Reported by Aurelien Jarno <aurelien@aurel32.net>
+
+	* string/test-strcmp.c (check): Add explicit test for situations where
+	there are multiple zero bytes after the first.
+
 	* sysdeps/sparc/bits/string.h (_STRING_ARCH_unaligned): Define to
 	0.
 
diff --git a/string/test-strcmp.c b/string/test-strcmp.c
index b395dc7..d1c73a3 100644
--- a/string/test-strcmp.c
+++ b/string/test-strcmp.c
@@ -329,6 +329,35 @@  check (void)
 		FOR_EACH_IMPL (impl, 0)
 		check_result (impl, s1 + i1, s2 + i2, exp_result);
       }
+
+  /* Test cases where there are multiple zero bytes after the first.  */
+
+  for (size_t i = 0; i < 8; i++)
+    {
+      int exp_result;
+
+      for (CHAR val = 0x01; val < 0x10; val++)
+	{
+	  for (size_t j = 0; j < i; j++)
+	    {
+	      s1[j] = val;
+	      s2[j] = val;
+	    }
+
+	  s1[i] = 0x00;
+	  s2[i] = val;
+
+	  for (size_t j = i + 1; j < 16; j++)
+	    {
+	      s1[j] = 0x00;
+	      s2[j] = 0x00;
+	    }
+
+	  exp_result = SIMPLE_STRCMP (s1, s2);
+	  FOR_EACH_IMPL (impl, 0)
+	    check_result (impl, s1, s2, exp_result);
+	}
+    }
 }
 
 
diff --git a/sysdeps/sparc/sparc64/strcmp.S b/sysdeps/sparc/sparc64/strcmp.S
index 8925396..312924a 100644
--- a/sysdeps/sparc/sparc64/strcmp.S
+++ b/sysdeps/sparc/sparc64/strcmp.S
@@ -121,6 +121,37 @@  ENTRY(strcmp)
 	movleu	%xcc, -1, %o0
 	srlx	rTMP1, 7, rTMP1
 
+	/* In order not to be influenced by bytes after the zero byte, we
+	 * have to retain only the highest bit in the mask for the comparison
+	 * with rSTRXOR to work properly.
+	 */
+	mov	0, rTMP2
+	andcc	rTMP1, 0x0100, %g0
+	
+	movne	%xcc, 8, rTMP2
+	sllx	rTMP1, 63 - 16, %o1
+
+	movrlz	%o1, 16, rTMP2
+	sllx	rTMP1, 63 - 24, %o1
+
+	movrlz	%o1, 24, rTMP2
+	sllx	rTMP1, 63 - 32, %o1
+
+	movrlz	%o1, 32, rTMP2
+	sllx	rTMP1, 63 - 40, %o1
+
+	movrlz	%o1, 40, rTMP2
+	sllx	rTMP1, 63 - 48, %o1
+
+	movrlz	%o1, 48, rTMP2
+	sllx	rTMP1, 63 - 56, %o1
+
+	movrlz	%o1, 56, rTMP2
+
+	srlx	rTMP1, rTMP2, rTMP1
+
+	sllx	rTMP1, rTMP2, rTMP1
+
 	cmp	rTMP1, rSTRXOR
 	retl
 	 movgu	%xcc, 0, %o0