V2 [PATCH 1/4] strncmp: Add a testcase for page boundary [BZ #25933]

[H.J. Lu]

On Tue, Jun 16, 2020 at 11:25 AM Paul A. Clarke <pc@us.ibm.com> wrote:
>
> On Mon, Jun 15, 2020 at 04:06:58PM -0700, H.J. Lu via Libc-alpha wrote:
> > On Mon, Jun 15, 2020 at 3:03 PM Paul A. Clarke <pc@us.ibm.com> wrote:
> > >
> > > On Mon, Jun 15, 2020 at 02:34:13PM -0700, H.J. Lu via Libc-alpha wrote:
> > > > On Mon, Jun 15, 2020 at 1:29 PM Paul A. Clarke <pc@us.ibm.com> wrote:
> > > > >
> > > > > On Fri, Jun 12, 2020 at 01:10:53PM -0700, H.J. Lu via Libc-alpha wrote:
> > > > > > Add a strncmp testcase to cover cases where one of strings ends on the
> > > > > > page boundary.
> > > > > > ---
> > > > > >  string/test-strncmp.c | 25 +++++++++++++++++++++++++
> > > > > >  1 file changed, 25 insertions(+)
> > > > > >
> > > > > > diff --git a/string/test-strncmp.c b/string/test-strncmp.c
> > > > > > index d961ac4493..d0928a2864 100644
> > > > > > --- a/string/test-strncmp.c
> > > > > > +++ b/string/test-strncmp.c
> > > > > > @@ -403,6 +403,30 @@ check2 (void)
> > > > > >    free (s2);
> > > > > >  }
> > > > > >
> > > > > > +static void
> > > > > > +check3 (void)
> > > > > > +{
> > > > > > +  size_t size = 32 * 4;
> > > > > > +  CHAR *s1 = (CHAR *) (buf1 + (BUF1PAGES - 1) * page_size);
> > > > > > +  CHAR *s2 = (CHAR *) (buf2 + (BUF1PAGES - 1) * page_size);
> > > > > > +  int exp_result;
> > > > > > +
> > > > > > +  memset (s1, 'a', page_size);
> > > > > > +  memset (s2, 'a', page_size);
> > > > > > +  s1[(page_size / CHARBYTES) - 1] = (CHAR) 0;
> > > > > > +
> > > > > > +  for (size_t s = 99; s <= size; s++)
> s 99..128
> > > > > > +    for (size_t s1a = 31; s1a < 32; s1a++)
> s1a = 31
> > > > > > +      for (size_t s2a = 30; s2a < 32; s2a++)
> s2a = 30,31
> > > > > > +     {
> > > > > > +       CHAR *s1p = s1 + (page_size / CHARBYTES - s) - s1a;
> > > > > > +       CHAR *s2p = s2 + (page_size / CHARBYTES - s) - s2a;
> > > > > > +       exp_result = SIMPLE_STRNCMP (s1p, s2p, s);
> > > > > > +       FOR_EACH_IMPL (impl, 0)
> > > > > > +         check_result (impl, s1p, s2p, s, exp_result);
> > > > > > +     }
> > > > > > +}
> > > > >
> > > > > There are lots of magic numbers here.
> > > > >
> > > > > Could you add some context around those number
> > > >
> > > > My commit log says
> > > >
> > > > ---
> > > > Add a strncmp testcase to cover cases where one of strings ends on the
> > > > page boundary.
> > > > ---
> > >
> > > Which says nothing about why you need to test over 90000 different
> >
> > Loops in check3 have about 60, not 90000, different cases
> > according to my calculation.
>
> OK. I saw the magic 99, 31, and 30, and didn't account for the magic 32s.
> The second "loop" doesn't even loop, as it's a single iteration at 31. (Why?)

I can remove the second loop.

> The third loop is just 30 and 31.
>
> It's all needlessly complex and confusing.

It is designed to trigger the bug.

> > > cases of a string ending on a page boundary, nor what any of the
> > > magic numbers represent.
> >
> > AVX vector size is 32 bytes.  Each AVX2 loop iteration processes
> > 4 * 32 bytes.   check3 covers cases where one of strings ends on
> > the page boundary with the maximum string length less than the
> > number bytes of each AVX2 loop iteration and different offsets from
> > page boundary.   Here is the updated patch with added comments.
>
> I suggest making the implementation more generic.  "32" isn't magic
> for every architecture.

But it is the key to trigger the bug.

> Your v2 suggests:
> > +  /* Check AVX2 loop unrolling with the maximum string length less
> > +     than 4 * 32 bytes and different offsets from page boundary.  */
>
> Is it common to include architecture-specific comments (above) and code
> (below) in common code?

I simply explain why the testcase is written this way.

> > +  for (size_t s = 99; s <= size; s++)
> > +    for (size_t s1a = 31; s1a < 32; s1a++)
> > +      for (size_t s2a = 30; s2a < 32; s2a++)
> > +       {
> > +         CHAR *s1p = s1 + (page_size / CHARBYTES - s) - s1a;
> > +         CHAR *s2p = s2 + (page_size / CHARBYTES - s) - s2a;
> > +         exp_result = SIMPLE_STRNCMP (s1p, s2p, s);
> > +         FOR_EACH_IMPL (impl, 0)
> > +           check_result (impl, s1p, s2p, s, exp_result);
> > +       }
>
> If you just want to approach the end of the page from different offsets,
> would something like the following suffice (not tested)?
>
> +  /* Pick a length which hopefully encompasses most cache line lengths
> +     and vector sizes including loop unrolling.  */
> +  for (size_t s = 256; s; s--)
> +    {
> +      CHAR *s1p = s1 + (page_size / CHARBYTES - s) + 1;

When s <= 1, s1p will point beyond the end of buf1.

> +      CHAR *s2p = s2 + (page_size / CHARBYTES - 256);
> +      exp_result = SIMPLE_STRNCMP (s1p, s2p, s);
> +      FOR_EACH_IMPL (impl, 0)
> +        check_result (impl, s1p, s2p, s, exp_result);
> +      exp_result = SIMPLE_STRNCMP (s2p, s1p, s);
> +      FOR_EACH_IMPL (impl, 0)
> +        check_result (impl, s2p, s1p, s, exp_result);
> +    }
>
> If 256 isn't enough in the general case, maybe just use something O(page_size).
>

This loop will trigger the bug.  The key is 31/30.

 /* Pick a length which hopefully encompasses most cache line lengths
     and vector sizes including loop unrolling.  */
  for (size_t s = 256; s; s--)
    {
      CHAR *s1p = s1 + (page_size / CHARBYTES - s) - 31;
      CHAR *s2p = s2 + (page_size / CHARBYTES - s) - 30;
      exp_result = SIMPLE_STRNCMP (s1p, s2p, s);
      {
        FOR_EACH_IMPL (impl, 0)
          check_result (impl, s1p, s2p, s, exp_result);
      }
      exp_result = SIMPLE_STRNCMP (s2p, s1p, s);
      {
        FOR_EACH_IMPL (impl, 0)
          check_result (impl, s2p, s1p, s, exp_result);
      }
    }


-- 
H.J.