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

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

Commit Message

David Miller May 1, 2014, 7:06 p.m. UTC
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:
>> +  /* 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);

That evaluates to "3", which would test less. :-)

The important bit is to make sure we cover placing the initial
terminating zero byte at every byte offset within a word, therefore
testing up to 16 characters more than covers all of the possible
cases.

>> +    {
>> +      int exp_result;
>> +
>> +      for (CHAR val = 0x01; val < 0x10; val++)
> 
> Permute over all char values e.g. [0x1,0xff] or val < 0x100;

Ok, and we have to use 'int' for this otherwise we loop forever.

>> +	{
>> +	  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.

Agreed, this was excessive.

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

Thanks for your feedback Carlos, here is what I will commit.

Comments

Carlos O'Donell May 1, 2014, 7:42 p.m. UTC | #1
On 05/01/2014 03:06 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:
>>> +  /* 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);
> 
> That evaluates to "3", which would test less. :-)

Wait what? The l1 and l2 are the lengths of the strings in the
function `check' ... oh wait I see it zeroes out s1[3] before
computing the length. Lame.

> The important bit is to make sure we cover placing the initial
> terminating zero byte at every byte offset within a word, therefore
> testing up to 16 characters more than covers all of the possible
> cases.

That's right. Thanks. I just wanted a cogent argument for the
longer length that gives better coverage.

>>> +    {
>>> +      int exp_result;
>>> +
>>> +      for (CHAR val = 0x01; val < 0x10; val++)
>>
>> Permute over all char values e.g. [0x1,0xff] or val < 0x100;
> 
> Ok, and we have to use 'int' for this otherwise we loop forever.
> 
>>> +	{
>>> +	  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.
> 
> Agreed, this was excessive.
> 
>> OK with those changes and verification that it still
>> catches the original failure case and hasn't exponentially
>> blown up the test time :}
> 
> Thanks for your feedback Carlos, here is what I will commit.

Looks good now.

> ====================
> Fix v9/64-bit strcmp when string ends in multiple zero bytes.
> 
> 	[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                      | 10 ++++++++++
>  string/test-strcmp.c           | 28 ++++++++++++++++++++++++++++
>  sysdeps/sparc/sparc64/strcmp.S | 31 +++++++++++++++++++++++++++++++
>  3 files changed, 69 insertions(+)
> 
> diff --git a/ChangeLog b/ChangeLog
> index 55724f6..581d243 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,13 @@
> +2014-05-01  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.
> +
>  2014-05-01  Andreas Schwab  <schwab@linux-m68k.org>
>  
>  	[BZ #16890]
> diff --git a/string/test-strcmp.c b/string/test-strcmp.c
> index b395dc7..fcd059f 100644
> --- a/string/test-strcmp.c
> +++ b/string/test-strcmp.c
> @@ -329,6 +329,34 @@ 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 < 16 + 1; i++)
> +    {
> +      s1[i] = 0x00;
> +      s2[i] = 0x00;
> +    }
> +
> +  for (size_t i = 0; i < 16; i++)
> +    {
> +      int exp_result;
> +
> +      for (int val = 0x01; val < 0x100; val++)
> +	{
> +	  for (size_t j = 0; j < i; j++)
> +	    {
> +	      s1[j] = val;
> +	      s2[j] = val;
> +	    }
> +
> +	  s2[i] = val;

Perfect. I see you zeroed out 16 bytes above so you still have
a useful terminator here (not that it would impact the test, but
it makes logical sense for what you're testing).

> +
> +	  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
> 

Cheers,
Carlos.
Joseph Myers May 1, 2014, 8:18 p.m. UTC | #2
Remember the NEWS update and closing the bug in Bugzilla....
David Miller May 1, 2014, 8:27 p.m. UTC | #3
From: "Joseph S. Myers" <joseph@codesourcery.com>
Date: Thu, 1 May 2014 20:18:30 +0000

> Remember the NEWS update and closing the bug in Bugzilla....

Thanks for the reminder, will do.

Patch
diff mbox

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

	[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                      | 10 ++++++++++
 string/test-strcmp.c           | 28 ++++++++++++++++++++++++++++
 sysdeps/sparc/sparc64/strcmp.S | 31 +++++++++++++++++++++++++++++++
 3 files changed, 69 insertions(+)

diff --git a/ChangeLog b/ChangeLog
index 55724f6..581d243 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@ 
+2014-05-01  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.
+
 2014-05-01  Andreas Schwab  <schwab@linux-m68k.org>
 
 	[BZ #16890]
diff --git a/string/test-strcmp.c b/string/test-strcmp.c
index b395dc7..fcd059f 100644
--- a/string/test-strcmp.c
+++ b/string/test-strcmp.c
@@ -329,6 +329,34 @@  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 < 16 + 1; i++)
+    {
+      s1[i] = 0x00;
+      s2[i] = 0x00;
+    }
+
+  for (size_t i = 0; i < 16; i++)
+    {
+      int exp_result;
+
+      for (int val = 0x01; val < 0x100; val++)
+	{
+	  for (size_t j = 0; j < i; j++)
+	    {
+	      s1[j] = val;
+	      s2[j] = val;
+	    }
+
+	  s2[i] = val;
+
+	  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