| Message ID | 20170715204749.24398-7-amonakov@ispras.ru |
|---|---|
| State | New |
| Headers | show |
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
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
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
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
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
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
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
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
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
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<T>::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
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<T>::sort) No it doesn't? One uses std::sort from <algorithm> on a pair of random access iterators to sort a std::vector. Cheers, Oleg
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<T>::sort), the argument counting vec::qsort -> vec::sort renaming is fine with me. Jakub
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<T>::sort) > > No it doesn't? One uses std::sort from <algorithm> 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
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
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<T>::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
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
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
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
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
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<T, A, L> 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, cmp) +#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) + size_t i1, i2, i, j; + /* This outer loop iterates over maximum spans [i1, i2) such that + elements within each span compare equal to each other. */ + for (i1 = 0; i1 < n; i1 = i2) + { + /* Position i2 one past last element that compares equal to i1'th. */ + for (i2 = i1 + 1; i2 < n; i2++) + if (CMP (i1, i2)) + break; + else if (CMP (i2, i1)) + return ERR2 (i1, i2); + size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); + /* Verify that other pairs within current span compare equal. */ + for (i = i1 + 1; i + 1 < i2; i++) + for (j = i + 1; j < i1 + lim1; j++) + if (CMP (i, j)) + return ERR3 (i, i1, j); + else if (CMP (j, i)) + return ERR2 (i, j); + /* Verify that elements within this span compare less than + elements beyond the span. */ + for (i = i1; i < i2; i++) + for (j = i2; j < i2 + lim2; j++) + if (CMP (i, j) >= 0) + return ERR3 (i, i1, j); + else if (CMP (j, i) <= 0) + return ERR2 (i, j); + } +#undef ERR3 +#undef ERR2 +#undef CMP +#undef ELT +#undef LIM +} + /* Vector memory usage. */ struct vec_usage: public mem_usage {
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(-)