Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/10/2017 05:24 AM, Alexander Monakov wrote:
> On Wed, 9 Aug 2017, Jeff Law wrote:
 The _5th macro isn't that bad either, appart from using reserved namespace
 identifiers (it really should be something like qsort_5th and the arguments
 shouldn't start with underscores).
>>>
>>> I didn't understand what Jeff found "ugly" about it; I wonder what epithets
>>> would be applied then to more, ahem, unusual parts of GCC.
>> I doubt anyone would want to hear what I might say about other code.
>> I'm sure I wouldn't want my kids reading how I might refer to certain
>> parts of GCC.
> 
> Imho it's no good to just say "ugly" in patch review without any further
> elaboration, it only serves to provide a minor chilling effect, telling
> the contributor they haven't done good enough (for your personal taste)
> without informing them where/how they could have improved.
> 
> More importantly, am I correct in understanding that at this point all
> remaining changes are reviewed and approved, and I can go ahead with
> preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the
> others on top of it?  Or is the original approach with argument-counting
> trick still under consideration?
I still don't like the argument-counting trick.  But avoiding it seems
even more painful.  So let's go with your original approach with the
argument-counting trick.  At least it's buried and folks likely won't
have to look at it with any regularity.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 9 Aug 2017, Jeff Law wrote:
> >> The _5th macro isn't that bad either, appart from using reserved namespace
> >> identifiers (it really should be something like qsort_5th and the arguments
> >> shouldn't start with underscores).
> > 
> > I didn't understand what Jeff found "ugly" about it; I wonder what epithets
> > would be applied then to more, ahem, unusual parts of GCC.
> I doubt anyone would want to hear what I might say about other code.
> I'm sure I wouldn't want my kids reading how I might refer to certain
> parts of GCC.

Imho it's no good to just say "ugly" in patch review without any further
elaboration, it only serves to provide a minor chilling effect, telling
the contributor they haven't done good enough (for your personal taste)
without informing them where/how they could have improved.

More importantly, am I correct in understanding that at this point all
remaining changes are reviewed and approved, and I can go ahead with
preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the
others on top of it?  Or is the original approach with argument-counting
trick still under consideration?

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 10:23 AM, Alexander Monakov wrote:
> On Thu, 3 Aug 2017, Jakub Jelinek wrote:
>> Do we really need to rename and poison anything?  qsort () in the source is
>> something that is most obvious to developers, so trying to force them to use
>> something different will just mean extra thing to learn.
> 
> Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.
Revisiting, I'm in agreement with you.

> 
>> The _5th macro isn't that bad either, appart from using reserved namespace
>> identifiers (it really should be something like qsort_5th and the arguments
>> shouldn't start with underscores).
> 
> I didn't understand what Jeff found "ugly" about it; I wonder what epithets
> would be applied then to more, ahem, unusual parts of GCC.
I doubt anyone would want to hear what I might say about other code.
I'm sure I wouldn't want my kids reading how I might refer to certain
parts of GCC.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 09:52 AM, Jakub Jelinek wrote:
> On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote:
>> On 08/03/2017 08:24 AM, Alexander Monakov wrote:
>>> On Wed, 2 Aug 2017, Jeff Law wrote:
>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>> its a very mechanical change.  Then a poison in system.h to ensure raw
>> calls to qsort don't return.
>>>
>>> Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
>>> renamed as well (to vec::sort, presumably).  It seems there are 83 or more
>>> calls to vec::qsort.
>> Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
>> patch to rename those too pre-approved.
> 
> Do we really need to rename and poison anything?  qsort () in the source is
> something that is most obvious to developers, so trying to force them to use
> something different will just mean extra thing to learn.
Thinking about this again, you're probably right.   I failed to
distinguish between this case and something like malloc.  For qsort, if
we're using the numbering hack, introduction of a new qsort call will
result in a qsort call that is properly checked.  In contrast we simply
don't want folks calling malloc & friends directly under any circumstances.

Sorry for taking everyone down a bogus path here.

Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Pedro Alves]

On 08/03/2017 05:23 PM, Alexander Monakov wrote:
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector::sort), the argument counting
> trick won't be needed, the redirection will simply be:

OTOH, std::sort's comparison function callback has a different
interface from qsort's.  std::sort wants less-than true/false,
while qsort wants -1/0/1.  Might be less confusing to
leave "sort" for a method that follows std::sort's interface.

You could also consider using std::sort, btw.  I don't think
there's a reason it can't work with vec.  Since std::sort is
a template, the inlining + indirection avoidance often results
in faster sorts (potentially at the expense of compile time).
Consistency checking could be implemented by adding a a gcc::sort
wrapper around std::sort (and calling the former throughout).

Thanks,
Pedro Alves

Re: [PATCH 6/6] qsort comparator consistency checking

[Oleg Endo]

On Thu, 2017-08-03 at 19:31 +0300, Alexander Monakov wrote:
> 
> My mistake, but the main point remains: STL uses 'sort' without the
> 'q'.

I think it'd be better if GCC's custom containers somewhat tried to
follow C++ standard container idioms.  Chopping off the 'q' is one step
towards it.

Cheers,
Oleg

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Fri, 4 Aug 2017, Oleg Endo wrote:
> > Note that with vec::qsort -> vec::sort renaming (which should be less
> > controversial, STL also has std::vector::sort)
> 
> No it doesn't?  One uses std::sort from  on a pair of random
> access iterators to sort a std::vector.

My mistake, but the main point remains: STL uses 'sort' without the 'q'.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jakub Jelinek]

On Thu, Aug 03, 2017 at 07:23:31PM +0300, Alexander Monakov wrote:
> On Thu, 3 Aug 2017, Jakub Jelinek wrote:
> > Do we really need to rename and poison anything?  qsort () in the source is
> > something that is most obvious to developers, so trying to force them to use
> > something different will just mean extra thing to learn.
> 
> Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.
> 
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector::sort), the argument counting

vec::qsort -> vec::sort renaming is fine with me.

Jakub

Re: [PATCH 6/6] qsort comparator consistency checking

[Oleg Endo]

On Thu, 2017-08-03 at 19:23 +0300, Alexander Monakov wrote:
> 
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector::sort)

No it doesn't?  One uses std::sort from  on a pair of random
access iterators to sort a std::vector.

Cheers,
Oleg

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Thu, 3 Aug 2017, Jakub Jelinek wrote:
> Do we really need to rename and poison anything?  qsort () in the source is
> something that is most obvious to developers, so trying to force them to use
> something different will just mean extra thing to learn.

Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.

Note that with vec::qsort -> vec::sort renaming (which should be less
controversial, STL also has std::vector::sort), the argument counting
trick won't be needed, the redirection will simply be:

  #undef qsort
  #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)

> I mean, isn't it better to just add a static inline qsort that in the
> checking case calls qsort_chk,

(redefining qsort like that is formally UB, I'd like to avoid it)

> or do the redirection using GNU asm redirection:
> typeof (qsort) __asm ("qsort_chk");
> and define extern "C" qsort_chk somewhere?
> configure could test whether it works on the target (it wouldn't perhaps
> on targets which already use some inline for qsort in their headers or use
> qsort as a macro (but the latter wouldn't work anyway with GCC already)).

I'd rather not go this way.

> The _5th macro isn't that bad either, appart from using reserved namespace
> identifiers (it really should be something like qsort_5th and the arguments
> shouldn't start with underscores).

I didn't understand what Jeff found "ugly" about it; I wonder what epithets
would be applied then to more, ahem, unusual parts of GCC.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jakub Jelinek]

On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote:
> On 08/03/2017 08:24 AM, Alexander Monakov wrote:
> > On Wed, 2 Aug 2017, Jeff Law wrote:
>  Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>  its a very mechanical change.  Then a poison in system.h to ensure raw
>  calls to qsort don't return.
> > 
> > Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
> > renamed as well (to vec::sort, presumably).  It seems there are 83 or more
> > calls to vec::qsort.
> Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
> patch to rename those too pre-approved.

Do we really need to rename and poison anything?  qsort () in the source is
something that is most obvious to developers, so trying to force them to use
something different will just mean extra thing to learn.

I mean, isn't it better to just add a static inline qsort that in the
checking case calls qsort_chk, or do the redirection using GNU asm
redirection:
typeof (qsort) __asm ("qsort_chk");
and define extern "C" qsort_chk somewhere?
configure could test whether it works on the target (it wouldn't perhaps
on targets which already use some inline for qsort in their headers or use
qsort as a macro (but the latter wouldn't work anyway with GCC already)).
The _5th macro isn't that bad either, appart from using reserved namespace
identifiers (it really should be something like qsort_5th and the arguments
shouldn't start with underscores).

Jakub

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 08:24 AM, Alexander Monakov wrote:
> On Wed, 2 Aug 2017, Jeff Law wrote:
 Well, there's not *that* many qsort calls.  My quick grep shows 94 and
 its a very mechanical change.  Then a poison in system.h to ensure raw
 calls to qsort don't return.
> 
> Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
> renamed as well (to vec::sort, presumably).  It seems there are 83 or more
> calls to vec::qsort.
Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
patch to rename those too pre-approved.


> 
>>> Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
>> qsort_chk/qsort_nochk for checked and non-checked?
> 
> I believe qsort_chk isn't appropriate, checking is not explicitly a part
> of interface, and we never use _chk in potentially-checking tree and RTL
> accessors either.
How about just "sort"?
Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 2 Aug 2017, Jeff Law wrote:
> >> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
> >> its a very mechanical change.  Then a poison in system.h to ensure raw
> >> calls to qsort don't return.

Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
renamed as well (to vec::sort, presumably).  It seems there are 83 or more
calls to vec::qsort.

> > Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
> qsort_chk/qsort_nochk for checked and non-checked?

I believe qsort_chk isn't appropriate, checking is not explicitly a part
of interface, and we never use _chk in potentially-checking tree and RTL
accessors either.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/02/2017 12:00 PM, Alexander Monakov wrote:
> On Wed, 2 Aug 2017, Jeff Law wrote:
>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>> its a very mechanical change.  Then a poison in system.h to ensure raw
>> calls to qsort don't return.
> 
> Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
qsort_chk/qsort_nochk for checked and non-checked?

> 
> Can you review the rest (the substantial functionality) of the patch
> without waiting for the mass-renaming change?
I think the rest is good as-is.  If we find a need to adjust the
checking intervals, then we can do that as a follow-up.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 2 Aug 2017, Jeff Law wrote:
> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
> its a very mechanical change.  Then a poison in system.h to ensure raw
> calls to qsort don't return.

Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?

Can you review the rest (the substantial functionality) of the patch
without waiting for the mass-renaming change?

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> This is the updated qsort comparator verifier.
> 
> Since we have vec::qsort(cmp), the patch uses the macro argument counting
> trick to redirect only the four-argument invocations of qsort to qsort_chk.
> I realize that won't win much sympathies, but a patch doing mass-renaming
> of qsort in the whole GCC codebase would win even fewer, I suspect.
> 
> The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
> checking, but there's no accompanying configure.ac change.  I'm not sure
> that would be useful in practice, so I'd rather turn it into #if 0.
> 
> The suppression in genmodes was needed because it's not linked with vec.o.
> 
>   * genmodes.c (calc_wider_mode): Suppress qsort macro.
> * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
> (qsort_nochk): New macro.
> (qsort_chk): Declare.
> (qsort_disable_checking): Declare.
> * vec.c (qsort_chk_error): New static function.
> (qsort_disable_checking): Define.
> (qsort_chk): New function.
Well, there's not *that* many qsort calls.  My quick grep shows 94 and
its a very mechanical change.  Then a poison in system.h to ensure raw
calls to qsort don't return.

The counting trick is, well, ugly.  There's also issues in that some
compilers don't properly implement the C99 pre-processor standard
properly (MSVC) and what happens when there's no arguments?  While not
likely an issue here, I think it highlights that this kind of
preprocessor hackery is just a bad idea.

I'd prefer to just bite the bullet and do the mechanical qsort change.

Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/31/2017 12:27 PM, Alexander Monakov wrote:
> On Mon, 31 Jul 2017, Jeff Law wrote:
>> I  must have missed something.  Can't you just define
>>
>> qsort (BASE, NMEMB, SIZE, COMPARE) into
>>
>> qsort_chk (BASE, NMEMB, SIZE, COMPARE)
>>
>> That shouldn't affect the qsort from vec?  Right?  Or am I missing something
> 
> If you do
> 
>   #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)
> 
> then all invocations of vec::qsort, i.e.
> 
>   myvec.qsort (mycmp);
> 
> will yield a preprocessing error due to wrong number of arguments supplied
> to the qsort macro (one instead of four).
Duh.  Hit me with a clue stick. I guess I have to get familiar with the
macro argument counting trick :-)

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Mon, 31 Jul 2017, Jeff Law wrote:
> I  must have missed something.  Can't you just define
> 
> qsort (BASE, NMEMB, SIZE, COMPARE) into
> 
> qsort_chk (BASE, NMEMB, SIZE, COMPARE)
> 
> That shouldn't affect the qsort from vec?  Right?  Or am I missing something

If you do

  #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)

then all invocations of vec::qsort, i.e.

  myvec.qsort (mycmp);

will yield a preprocessing error due to wrong number of arguments supplied
to the qsort macro (one instead of four).

Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> This is the updated qsort comparator verifier.
> 
> Since we have vec::qsort(cmp), the patch uses the macro argument counting
> trick to redirect only the four-argument invocations of qsort to qsort_chk.
> I realize that won't win much sympathies, but a patch doing mass-renaming
> of qsort in the whole GCC codebase would win even fewer, I suspect.
> 
> The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
> checking, but there's no accompanying configure.ac change.  I'm not sure
> that would be useful in practice, so I'd rather turn it into #if 0.
> 
> The suppression in genmodes was needed because it's not linked with vec.o.
> 
>   * genmodes.c (calc_wider_mode): Suppress qsort macro.
> * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
> (qsort_nochk): New macro.
> (qsort_chk): Declare.
> (qsort_disable_checking): Declare.
> * vec.c (qsort_chk_error): New static function.
> (qsort_disable_checking): Define.
> (qsort_chk): New function.
I  must have missed something.  Can't you just define

qsort (BASE, NMEMB, SIZE, COMPARE) into

qsort_chk (BASE, NMEMB, SIZE, COMPARE)

That shouldn't affect the qsort from vec?  Right?  Or am I missing something

Jeff

[PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

This is the updated qsort comparator verifier.

Since we have vec::qsort(cmp), the patch uses the macro argument counting
trick to redirect only the four-argument invocations of qsort to qsort_chk.
I realize that won't win much sympathies, but a patch doing mass-renaming
of qsort in the whole GCC codebase would win even fewer, I suspect.

The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
checking, but there's no accompanying configure.ac change.  I'm not sure
that would be useful in practice, so I'd rather turn it into #if 0.

The suppression in genmodes was needed because it's not linked with vec.o.

* genmodes.c (calc_wider_mode): Suppress qsort macro.
* system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
(qsort_nochk): New macro.
(qsort_chk): Declare.
(qsort_disable_checking): Declare.
* vec.c (qsort_chk_error): New static function.
(qsort_disable_checking): Define.
(qsort_chk): New function.
---
 gcc/genmodes.c |  2 +-
 gcc/system.h   | 11 +++
 gcc/vec.c  | 95 ++
 3 files changed, 107 insertions(+), 1 deletion(-)

diff --git a/gcc/genmodes.c b/gcc/genmodes.c
index f7eaeef..01a0e65 100644
--- a/gcc/genmodes.c
+++ b/gcc/genmodes.c
@@ -880,7 +880,7 @@ calc_wider_mode (void)
  for (i = 0, m = modes[c]; m; i++, m = m->next)
sortbuf[i] = m;
 
- qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
+ (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
 
  sortbuf[i] = 0;
  for (j = 0; j < i; j++)
diff --git a/gcc/system.h b/gcc/system.h
index b091794..0f44942 100644
--- a/gcc/system.h
+++ b/gcc/system.h
@@ -1170,4 +1170,15 @@ helper_const_non_const_cast (const char *p)
 /* Get definitions of HOST_WIDE_INT.  */
 #include "hwint.h"
 
+/* qsort comparator consistency checking machinery.  */
+#if CHECKING_P
+/* Except in release-checking compilers, redirect 4-argument qsort calls.  */
+#undef qsort
+#define _5th(_1, _2, _3, _4, _5, ...) _5
+#define qsort(...) _5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__)
+#endif
+#define qsort_nochk (qsort)
+void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *));
+extern unsigned qsort_disable_checking;
+
 #endif /* ! GCC_SYSTEM_H */
diff --git a/gcc/vec.c b/gcc/vec.c
index d612703..5d9f1e9 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -31,6 +31,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "hash-table.h"
 #include "selftest.h"
+#ifdef GENERATOR_FILE
+#include "errors.h"
+#else
+#include "input.h"
+#include "diagnostic-core.h"
+#endif
 
 /* vNULL is an empty type with a template cast operation that returns
a zero-initialized vec instance.  Use this when you want
@@ -42,6 +48,95 @@ along with GCC; see the file COPYING3.  If not see
they cannot have ctors/dtors.  */
 vnull vNULL;
 
+/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
+   witness elements.  */
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+static void
+qsort_chk_error (const void *p1, const void *p2, const void *p3,
+int (*cmp) (const void *, const void *))
+{
+  if (!p3)
+{
+  int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
+  error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
+}
+  else if (p1 == p2)
+{
+  int r = cmp (p1, p3);
+  error ("qsort comparator non-negative on sorted output: %d", r);
+}
+  else
+{
+  int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
+  error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
+}
+  internal_error ("qsort checking failed");
+}
+
+unsigned qsort_disable_checking;
+
+/* Wrapper around qsort with checking that CMP is consistent on given input.
+
+   Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
+   comparators to libc qsort can result in undefined behavior.  Therefore we
+   should ideally perform consistency checks prior to invoking qsort, but in
+   order to do that optimally we'd need to sort the array ourselves beforehand
+   with a sorting routine known to be "safe".  Instead, we expect that most
+   implementations in practice will still produce some permutation of input
+   array even for invalid comparators, which enables us to perform checks on
+   the output array.  */
+void
+qsort_chk (void *base, size_t n, size_t size,
+  int (*cmp)(const void *, const void *))
+{
+  if (!CHECKING_P || qsort_disable_checking)
+return (qsort) (base, n, size, cmp);
+  (qsort) (base, n, size, cmp);
+#ifdef ENABLE_FULL_QSORT_CHECKING
+#define LIM(n) (n)
+#else
+  /* Limit overall time complexity to O(n log n).  */
+#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
+#endif
+#define ELT(i) ((const char *) base + (i) * size)
+#define CMP(i, j) cmp (ELT (i), ELT (j))
+#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL,