Re: [PATCH v12 08/31] string: Improve generic strncmp

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 21/02/23 06:28, Szabolcs Nagy wrote:
> The 02/02/2023 15:11, Adhemerval Zanella via Libc-alpha wrote:
>> It follows the strategy:
>>
>>    - Align the first input to word boundary using byte operations.
>>
>>    - If second input is also word aligned, read a word per time, check
>>      for  null (using has_zero), and check final words using byte
>>      operation.
>>
>>    - If second input is not word aligned, loop by aligning the source,
>>      and merge the result of two reads.  Similar to aligned case, check
>>      for null with has_zero, and check final words using byte operation.
>>
>> Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu,
>> and powerpc-linux-gnu by removing the arch-specific assembly
>> implementation and disabling multi-arch (it covers both LE and BE
>> for 64 and 32 bits).
> 
> on arm i see
> 
> FAIL: crypt/badsalttest
> 
> Program received signal SIGSEGV, Segmentation fault.
> strncmp_unaligned_loop (n=3, ofs=<optimized out>, w1=2371876, x2=0xf7feb000, x1=0xf7f6563c) at strncmp.c:85
> 85                w2b = *x2++;
> 
> this strncmp does out of bounds read:
> 
> Breakpoint 2, __GI_strncmp (p1=0xf7f65638 <md5_salt_prefix> "$1$", p2=p2@entry=0xf7feafff "*", n=n@entry=3) at strncmp.c:115
> 
> 0xf7feb000 is mapped PROT_NONE.
> 
>> +strncmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs,
>> +			size_t n)
>> +{
>> +  op_t w2a = *x2++;
>> +  uintptr_t sh_1 = ofs * CHAR_BIT;
>> +  uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1;
>> +
>> +  op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2);
>> +  if (!has_zero (w2) && n > (sizeof (op_t) - ofs))
>>      {
>> -      c1 = (unsigned char) *s1++;
>> -      c2 = (unsigned char) *s2++;
>> -      if (c1 == '\0' || c1 != c2)
>> -	return c1 - c2;
>> -      n--;
>> +      op_t w2b;
>> +
>> +      /* Unaligned loop.  The invariant is that W2B, which is "ahead" of W1,
>> +	 does not contain end-of-string.  Therefore it is safe (and necessary)
>> +	 to read another word from each while we do not have a difference.  */
>> +      while (1)
>> +	{
>> +	  w2b = *x2++;
> ^^^^^^^^^^^^^^^^^^^^^^
> 
> reading ahead is wrong if w1 and w2 already mismatches.

Right, I will take a look.

> 
>> +	  w2 = MERGE (w2a, sh_1, w2b, sh_2);
>> +	  if (n <= sizeof (op_t) || w1 != w2)
>> +	    return final_cmp (w1, w2, n);
>> +	  n -= sizeof(op_t);
>> +	  if (has_zero (w2b) || n <= (sizeof (op_t) - ofs))
>> +	    break;
>> +	  w1 = *x1++;
>> +	  w2a = w2b;
>> +	}
>> +
>> +      /* Zero found in the second partial of P2.  If we had EOS in the aligned
>> +	 word, we have equality.  */
>> +      if (has_zero (w1))
>> +	return 0;
>> +
>> +      /* Load the final word of P1 and align the final partial of P2.  */
>> +      w1 = *x1++;
>> +      w2 = MERGE (w2b, sh_1, 0, sh_2);
>>      }
>>  
>> -  return c1 - c2;
>> +  return final_cmp (w1, w2, n);