This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Add qsort comparator consistency checking (PR71702)


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);
>  }
>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]