This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [reviewed] qsort comparator consistency checking
- From: Christophe Lyon <christophe dot lyon at linaro dot org>
- To: Alexander Monakov <amonakov at ispras dot ru>
- Cc: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 29 Sep 2017 19:46:13 +0200
- Subject: Re: [reviewed] qsort comparator consistency checking
- Authentication-results: sourceware.org; auth=none
- References: <alpine.LNX.2.20.13.1709291604420.18755@monopod.intra.ispras.ru>
Hi,
On 29 September 2017 at 15:29, Alexander Monakov <amonakov@ispras.ru> wrote:
> Hello,
>
> I'm going to install the following patch on trunk in the next few hours.
> This revision doesn't offer per-callsite opt-out anymore as suggested by
> Richi on the Cauldron (made possible by fixing all known issues on trunk).
> Thus this patch has a few minor differences compared to the previous
> revision that was ack'ed by Jeff.
>
> Tested on x86_64-linux, i686-linux and ppc64le-linux.
>
> Alexander
>
> * genmodes.c (calc_wider_mode): Suppress qsort macro.
> * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
> (qsort_chk): Declare.
> * vec.c [CHECKING_P] (qsort_chk_error): New static function.
> (qsort_chk): New function.
>
This patch (r253295) breaks the gcc build for aarch64-linux-gnu:
libtool: compile:
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc/xgcc
-shared-libgcc -B/tmp/3041688_6.t
mpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc
-nostdinc++ -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj
-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src
-L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-g
nu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src/.libs
-L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64
-none-linux-gnu/libstdc++-v3/libsupc++/.libs
-B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/bin/
-B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/lib/
-isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/include
-isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/sys-include
-I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/../libgcc
-I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/aarch64-none-linux-gnu
-I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include
-I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/libsupc++
-D_GLIBCXX_SHARED -std=gnu++14 -Wall -Wextra -Wwrite-strings
-Wcast-qual -Wabi -fdiagnostics-show-location=once -ffunction-sections
-fdata-sections -frandom-seed=ops.lo -g -O2 -D_GNU_SOURCE -c
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc
-fPIC -DPIC -D_GLIBCXX_SHARED -o ops.o
In file included from
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/deque:66:0,
from
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/stack:60,
from
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc:32:
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:
In member function 'void std::deque<_Tp,
_Alloc>::_M_range_insert_aux(std::deque<_Tp, _Alloc>::iterator,
_ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with
_ForwardIterator =
std::experimental::filesystem::v1::__cxx11::path::iterator; _Tp =
std::experimental::filesystem::v1::__cxx11::path; _Alloc =
std::allocator<std::experimental::filesystem::v1::__cxx11::path>]':
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7:
error: qsort comparator non-negative on sorted output: 8
}
^
during RTL pass: sched2
/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7:
internal compiler error: qsort checking failed
0x55f7a1 qsort_chk_error
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:222
0x15337d8 qsort_chk(void*, unsigned long, unsigned long, int (*)(void
const*, void const*))
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:274
0x14360e0 ready_sort_real
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:3087
0x143de85 schedule_block(basic_block_def**, void*)
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:6749
0xd42132 schedule_region
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3174
0xd42132 schedule_insns()
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3513
0xd424ee rest_of_handle_sched2
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3737
0xd424ee execute
/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3873
Christophe
> diff --git a/gcc/genmodes.c b/gcc/genmodes.c
> index 97ed949c255..4eb8ee56d88 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 59449f1942b..f0664e93fc8 100644
> --- a/gcc/system.h
> +++ b/gcc/system.h
> @@ -1181,4 +1181,14 @@ helper_const_non_const_cast (const char *p)
> /* Get definitions of HOST_WIDE_INT. */
> #include "hwint.h"
>
> +/* qsort comparator consistency checking: except in release-checking compilers,
> + redirect 4-argument qsort calls to qsort_chk; keep 1-argument invocations
> + corresponding to vec::qsort (cmp): they use C qsort internally anyway. */
> +#if CHECKING_P
> +#define PP_5th(a1, a2, a3, a4, a5, ...) a5
> +#undef qsort
> +#define qsort(...) PP_5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__)
> +void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *));
> +#endif
> +
> #endif /* ! GCC_SYSTEM_H */
> diff --git a/gcc/vec.c b/gcc/vec.c
> index d612703184b..9a80f3421db 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
> @@ -190,6 +196,93 @@ dump_vec_loc_statistics (void)
> vec_mem_desc.dump (VEC_ORIGIN);
> }
>
> +#if CHECKING_P
> +/* 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");
> +}
> +
> +/* 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 *))
> +{
> + (qsort) (base, n, size, cmp);
> +#if 0
> +#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
> +}
> +#endif /* #if CHECKING_P */
> +
> #ifndef GENERATOR_FILE
> #if CHECKING_P
>