Fixing where test-strncmp could read beyond page boundary

  In do_random_tests(), 2 "page" size buffers are used with various
offsets and lengths where the operations are fairly close to the end
of a page boundary.  Most of the computations are done carefully to
avoid crossing the page boundary, except the actual "size" which is
eventually passed to strncmp() (via CALL_IMPL()) is not.  "size" is
computed once and not adjusted to accommodate for the random offsets
into the buffers at which the strings to be compared start.

This change ensures that the "size" passed to strncmp() contains the
strings within the page.

I also added a number of comments within do_random_tests() in the
hope that someone new to the code will find it much more
comprehensible than I did.

2016-12-16  Paul A. Clarke  <pc@us.ibm.com>

     * string/test-strncmp.c (do_random_tests): Ensure "size" defines
     strings within a single page.
---
  string/test-strncmp.c | 40 +++++++++++++++++++++++++++++++++++++---
  1 file changed, 37 insertions(+), 3 deletions(-)
  

On 12/20/2016 09:19 AM, Paul Clarke wrote:
> This change ensures that the "size" passed to strncmp() contains the
> strings within the page.

If there is a known difference or a known EOS before the end of the page, then
SIZE can legitimately be beyond the end of the page and the routine should not
SEGV.

Are you certain you're not removing valid testing for this function?


r~
  

On 12/20/2016 11:29 AM, Richard Henderson wrote:
> On 12/20/2016 09:19 AM, Paul Clarke wrote:
>> This change ensures that the "size" passed to strncmp() contains the
>> strings within the page.
>
> If there is a known difference or a known EOS before the end of the page, then
> SIZE can legitimately be beyond the end of the page and the routine should not
> SEGV.
>
> Are you certain you're not removing valid testing for this function?

That's a fair question.

do_random_tests() checks if strncmp() gives correct results for different alignment and length combinations. It checks if strncmp() is not issuing unaligned loads beyond a native alignment: by placing the strings near the end of a page, such loads will provoke a seg fault. This test already takes pains to ensure the string proper does not cross a page boundary by doing various checks, but one check missing is for variable 'size'. The 'size' parameter can be used in the implementation of strncmp() to decide the loop value for the number of loads. So these checks help to make the testcase valid thereby any failure would be in the implementation of strncmp().

Regards,
PC
  

On 12/20/2016 10:46 AM, Paul Clarke wrote:
> The 'size' parameter can be used in the implementation of strncmp() to decide
> the loop value for the number of loads.

No, it can't.  I know because I've made that mistake before.


r~
  

On 12/20/2016 08:15 PM, Richard Henderson wrote:
> On 12/20/2016 10:46 AM, Paul Clarke wrote:
>> The 'size' parameter can be used in the implementation of strncmp() to decide
>> the loop value for the number of loads.
>
> No, it can't.  I know because I've made that mistake before.

Richard is right.  Even C11 is pretty clear that this optimization is 
not permitted because it says that “characters that follow a
null character are not compared”.

It's unspecified whether reading stops at the first difference.  But 
considering that you need to check for NUL bytes anyway, I don't think 
this matters in practice because any size-based optimization would be 
invalid anyway.

This is also relevant to real-world code, which may use

   strncmp (s, "expected-prefix", strlen ("expected-prefix")) == 0

to determine whether s begins with "expected-prefix".  s could point 
close to the end of the heap.

Thanks,
Florian
  

On 12/21/2016 03:44 AM, Florian Weimer wrote:
> On 12/20/2016 08:15 PM, Richard Henderson wrote:
>> On 12/20/2016 10:46 AM, Paul Clarke wrote:
>>> The 'size' parameter can be used in the implementation of strncmp() to decide
>>> the loop value for the number of loads.
>>
>> No, it can't.  I know because I've made that mistake before.
>
> Richard is right.  Even C11 is pretty clear that this optimization is
> not permitted because it says that “characters that follow a
> null character are not compared”.
>
> It's unspecified whether reading stops at the first difference.  But
> considering that you need to check for NUL bytes anyway, I don't think
> this matters in practice because any size-based optimization would be
> invalid anyway.
>
> This is also relevant to real-world code, which may use
>
>    strncmp (s, "expected-prefix", strlen ("expected-prefix")) == 0
>
> to determine whether s begins with "expected-prefix".  s could point
> close to the end of the heap.

Thanks for the thorough reviews. Looking more carefully this time, I agree.

Since I sifted through the fairly complex code and found it challenging, let me try to preserve some value from the effort and submit a patch with just the explanatory comments, in case someone else needs to understand the code in the future.

PC