Add qsort comparator consistency checking (PR71702)

Hi,

this patch adds internal checking for comparator functions that GCC passes to
qsort.  PR71702 describes an ICE that happens because comparator
'dr_group_sort_cmp' used to be non-transitive in some cases until GCC 6.  This
patch would uncover that issue on a number of small testcases in GCC's
testsuite, so it should be useful to catch similar issues in the future as well.

Although the meat of the implementation is not tied to vec<>, this patch adds
verification only to vec::qsort.  I see there's a number of other ::qsort uses
in GCC; it should be useful to have such checking there as well.  I'd appreciate
input on that (I'd go with '#define qsort(b, n, s, c) qsort_chk (b, n, s, c)'
in system.h and implement qsort_chk as a checking wrapper around libc qsort).

Bootstrapped and regtested on x86_64, OK to apply?

Alexander

	* vec.c (vec_check_sort_cmp): New.  Use it...
	* vec.h (vec<T, A, vl_embed>::qsort): ...here to verify comparator
	consistency when checking is enabled.

On Fri, Jul 15, 2016 at 6:00 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> Hi,
>
> this patch adds internal checking for comparator functions that GCC passes to
> qsort.  PR71702 describes an ICE that happens because comparator
> 'dr_group_sort_cmp' used to be non-transitive in some cases until GCC 6.  This
> patch would uncover that issue on a number of small testcases in GCC's
> testsuite, so it should be useful to catch similar issues in the future as well.
>
> Although the meat of the implementation is not tied to vec<>, this patch adds
> verification only to vec::qsort.  I see there's a number of other ::qsort uses
> in GCC; it should be useful to have such checking there as well.  I'd appreciate
> input on that (I'd go with '#define qsort(b, n, s, c) qsort_chk (b, n, s, c)'
> in system.h and implement qsort_chk as a checking wrapper around libc qsort).
>
> Bootstrapped and regtested on x86_64, OK to apply?

Ugh.  What impact does this have on stage2 compile-time?

Richard.

> Alexander
>
>         * vec.c (vec_check_sort_cmp): New.  Use it...
>         * vec.h (vec<T, A, vl_embed>::qsort): ...here to verify comparator
>         consistency when checking is enabled.
>
> diff --git a/gcc/vec.c b/gcc/vec.c
> index fd200ea..b4ac0b4 100644
> --- a/gcc/vec.c
> +++ b/gcc/vec.c
> @@ -190,6 +190,44 @@ dump_vec_loc_statistics (void)
>    vec_mem_desc.dump (VEC_ORIGIN);
>  }
>
> +/* Verify consistency of comparator CMP on array BASE of N SIZE-sized elements.
> +   Assuming the array should be sorted according to CMP, any assertion failure
> +   here implies that CMP is not transitive, or is not anti-commutative.  */
> +
> +void
> +vec_check_sort_cmp (const void *base, size_t n, size_t size,
> +                   int (*cmp) (const void *, const void *))
> +{
> +  const char *cbase = (const char *) base;
> +  size_t i1, i2, i, j;
> +  /* The following loop nest has O(n^2) time complexity.  Limit n to avoid
> +     slowness on artificial testcases.  */
> +  if (n > 100)
> +    n = 100;
> +#define CMP(i, j) cmp (cbase + (i) * size, cbase + (j) * size)
> +  /* The outer loop iterates over maximum spans [i1, i2) such that elements
> +     within each span compare equal.  */
> +  for (i1 = 0; i1 < n; i1 = i2)
> +    {
> +      /* Position i2 past the last element that compares equal to i1'th.  */
> +      for (i2 = i1 + 1; i2 < n; i2++)
> +       if (CMP (i1, i2))
> +         break;
> +       else
> +         gcc_assert (!CMP (i2, i1));
> +      /* Verify that all remaining pairs within current span compare equal.  */
> +      for (i = i1 + 1; i + 1 < i2; i++)
> +       for (j = i + 1; j < i2; j++)
> +         gcc_assert (!CMP (i, j) && !CMP (j, i));
> +      /* Verify that all elements within current span compare less than any
> +         element beyond the span.  */
> +      for (i = i1; i < i2; i++)
> +       for (j = i2; j < n; j++)
> +         gcc_assert (CMP (i, j) < 0 && CMP (j, i) > 0);
> +    }
> +#undef CMP
> +}
> +
>  #ifndef GENERATOR_FILE
>  #if CHECKING_P
>
> diff --git a/gcc/vec.h b/gcc/vec.h
> index eb8c270..ff1e37e 100644
> --- a/gcc/vec.h
> +++ b/gcc/vec.h
> @@ -182,6 +182,9 @@ extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
>  /* Support function for statistics.  */
>  extern void dump_vec_loc_statistics (void);
>
> +extern void vec_check_sort_cmp (const void *, size_t, size_t,
> +                               int (*) (const void *, const void *));
> +
>  /* Hashtable mapping vec addresses to descriptors.  */
>  extern htab_t vec_mem_usage_hash;
>
> @@ -947,8 +950,11 @@ template<typename T, typename A>
>  inline void
>  vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
>  {
> -  if (length () > 1)
> -    ::qsort (address (), length (), sizeof (T), cmp);
> +  if (length () <= 1)
> +    return;
> +  ::qsort (address (), length (), sizeof (T), cmp);
> +  if (CHECKING_P)
> +    vec_check_sort_cmp (address (), length (), sizeof (T), cmp);
>  }
>
>

On Mon, 18 Jul 2016, Richard Biener wrote:
> Ugh.  What impact does this have on stage2 compile-time?

It doesn't seem to be high enough to be measured reliably.  I've made a trial
run with -time=time.log in BOOT_CFLAGS, but there's a lot of variability in
timings and the sum total of times ended up 1% lower on the patched compiler.

However, this patch only runs checking for vec::qsort, while I'd like to have
such checking on all qsort calls.  That would make it a bit more concerning.

It is possible to consider other schemes of limiting the impact of this checking
by restricting the subset of pairs being tested. For instance, it's possible to
run all-pairs check on a really small prefix of the sorted array (e.g. 10,
instead of 100 in the proposed patch), and for the rest of the elements, check
only a logarithmic number of pairs. This would make this checking have time
complexity O(n log n), matching qsort (but likely with a lower constant factor).
Would this scheme be appropriate?

Thanks.
Alexander

On Mon, Jul 18, 2016 at 7:36 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> On Mon, 18 Jul 2016, Richard Biener wrote:
>> Ugh.  What impact does this have on stage2 compile-time?
>
> It doesn't seem to be high enough to be measured reliably.  I've made a trial
> run with -time=time.log in BOOT_CFLAGS, but there's a lot of variability in
> timings and the sum total of times ended up 1% lower on the patched compiler.
>
> However, this patch only runs checking for vec::qsort, while I'd like to have
> such checking on all qsort calls.  That would make it a bit more concerning.
>
> It is possible to consider other schemes of limiting the impact of this checking
> by restricting the subset of pairs being tested. For instance, it's possible to
> run all-pairs check on a really small prefix of the sorted array (e.g. 10,
> instead of 100 in the proposed patch), and for the rest of the elements, check
> only a logarithmic number of pairs. This would make this checking have time
> complexity O(n log n), matching qsort (but likely with a lower constant factor).
> Would this scheme be appropriate?

Yes.  The other option is to enable this checking not with ENABLE_CHECKING
but some new checking option, say ENABLE_CHECKING_ALGORITHMS, and
do full checking in that case.

[The -fchecking option was supposed to be eventually extended to cover more
checking subsets, thus allow -fchecking=yes,algorithms for example]

Richard.

> Thanks.
> Alexander

On Tue, 19 Jul 2016, Richard Biener wrote:
> Yes.  The other option is to enable this checking not with ENABLE_CHECKING
> but some new checking option, say ENABLE_CHECKING_ALGORITHMS, and
> do full checking in that case.

Thanks - I'm going to fold in this idea when redoing the patch (i.e. check a
subset of pairs under normal checking, all pairs under this option macro).

While the topic is fresh, I'd like to mention a small complication with
extending this checking to cover all qsort calls.  I mentioned in the opening
mail that I was going to do that with a '#define qsort(..) qsort_chk (..)' in
gcc/system.h, but I missed that vec::qsort would be subject to this macro
expansion as well.

I see two possible solutions.  The first is to use the argument counting trick
to disambiguate between libc qsort(base, n, sz, cmp) and vec::qsort(cmp) on the
preprocessor level.  I don't see a reason it wouldn't work, but in this context
I'd consider that a last-resort measure rather than an appropriate solution.

The second is to rename vec::qsort to vec::sort. While mass renaming is not very
nice, I hope it is acceptable in this case (I think formally vec::qsort
declaration in GCC is not portable, because it implicitly expects that stdlib.h
wouldn't shadow qsort with a function-like macro).


Actually, thinking about it more, instead of redirecting qsort in system.h, it
may be more appropriate to introduce gcc_qsort that wraps qsort and does
checking, add gcc_qsort_nochk as an escape hatch for cases where checking
shouldn't be done, and poison qsort in system.h (this again depends on doing the
vec::sort mass-rename).

Alexander

On Tue, Jul 19, 2016 at 3:27 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> On Tue, 19 Jul 2016, Richard Biener wrote:
>> Yes.  The other option is to enable this checking not with ENABLE_CHECKING
>> but some new checking option, say ENABLE_CHECKING_ALGORITHMS, and
>> do full checking in that case.
>
> Thanks - I'm going to fold in this idea when redoing the patch (i.e. check a
> subset of pairs under normal checking, all pairs under this option macro).
>
> While the topic is fresh, I'd like to mention a small complication with
> extending this checking to cover all qsort calls.  I mentioned in the opening
> mail that I was going to do that with a '#define qsort(..) qsort_chk (..)' in
> gcc/system.h, but I missed that vec::qsort would be subject to this macro
> expansion as well.
>
> I see two possible solutions.  The first is to use the argument counting trick
> to disambiguate between libc qsort(base, n, sz, cmp) and vec::qsort(cmp) on the
> preprocessor level.  I don't see a reason it wouldn't work, but in this context
> I'd consider that a last-resort measure rather than an appropriate solution.
>
> The second is to rename vec::qsort to vec::sort. While mass renaming is not very
> nice, I hope it is acceptable in this case (I think formally vec::qsort
> declaration in GCC is not portable, because it implicitly expects that stdlib.h
> wouldn't shadow qsort with a function-like macro).
>
>
> Actually, thinking about it more, instead of redirecting qsort in system.h, it
> may be more appropriate to introduce gcc_qsort that wraps qsort and does
> checking, add gcc_qsort_nochk as an escape hatch for cases where checking
> shouldn't be done, and poison qsort in system.h (this again depends on doing the
> vec::sort mass-rename).

I don't think macro expansion applies to vec.qsort or vec::qsort and if it did
such macro would be bogus and we'd simply undefine it.

To capture non-vec qsorts simply wrap qsort everywhere like you suggested.

Richard.

>
> Alexander