Backporting gcc_qsort
gcc_qsort as introduced by Alexander Monakov [0] in trunk for 9.x is a great change that defines the order of otherwise-unbalanced internal sorts, some of which would otherwise cause bootstrapping failures. I would like to request that these it as well as subsequent fixups (all listed specifically below) be backported to the 8.x branch. They apply cleanly to 8.x, and I can confirm that they fix qsort-related bootstrap failures at least in my case of crossing x86_64-gnu to x86_64-musl. Would there be any downside to backporting? The changes that I locally backported and tested successfully were: r260216: Introduce gcc_qsort r260222: gcc_qsort: avoid oversized memcpy temporaries r262092: gcc_qsort: avoid overlapping memcpy (PR 86311) r264065: qsort_chk: call from gcc_qsort instead of wrapping it [0]: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00479.html Regards, Cory Fields
Re: Backporting gcc_qsort
Understood. Thank you for the explanations. I'll just plan to apply the patches locally as well. Regards, Cory On Mon, Oct 1, 2018 at 11:18 AM Alexander Monakov wrote: > > On Mon, 1 Oct 2018, Jeff Law wrote: > > To add a bit more context for Cory. > > > > Generally backports are limited to fixing regressions and serious code > > generation bugs. While we do make some exceptions, those are good > > general guidelines. > > > > I don't think the qsort changes warrant an exception. > > Personally I think in this case there isn't a strong reason to backport, the > patch is fairly isolated, so individuals or companies that need it should have > no problem backporting it on their own. Previously, Franz Sirl reported back > in June they've used the patch to achieve matching output on their > Linux-hosted > vs Cygwin-hosted cross-compilers based on GCC 8: > https://gcc.gnu.org/ml/gcc-patches/2018-06/msg00751.html > > Alexander
Unstable build/host qsorts causing differing generated target code
Quick disclaimer: I'm 100% new to GCC code and the dev process, so there are bound to be some faulty assumptions below. I recently worked on a build of gcc, x86_64-pc-linux-gnu -> x86_64-pc-linux-musl. In order to boost my confidence in musl, I decided that I'd like to ensure that 3 (and 4) stage bootstraps succeed and compare equal. I quickly ran into failed object comparisons at stage3. The issue, as it turned out, was that musl's qsort algorithm differs significantly from gcc's, though both (as far as I can tell) are perfectly legal. The c spec allows for different results in the cast of unstable arrays. So otherwise-identical gcc builds linked against differing libc's potentially produce different binaries for the target. And at least in the case of glibc/musl, I've verified that it's happening. Due to the qsorts used in the gen* build programs, I assume it's even possible for cross-compiled target code to vary based libc used by the native system compiler that builds the cross-compiler. After tracking down the issue, I set out to fix the unstable sorts. This turned out to be tricky, given the dozens or hundreds of uses of qsort in the code-base. As someone not familiar with the gcc code or typical debugging procedures, my big-hammer solution was to copy glibc's qsort implementation into musl, run both versions for every call to qsort, and assert that the resulting arrays are equal. This turned up dozens of failures, which I fixed case-by-case until a bootstrap succeeded. I then removed the patches one-by-one to narrow down exactly which ones were causing compilation differences. This ended up only being 2 small changes for trunk, 4 for 7.2.x. I will submit those to the -patches list as a follow-up. More generally, many of these unstable sorts remain, and fixing them up individually seems futile. Before working on this further, I'm wondering if it makes sense to pull a qsort into libiberty and poison the libc function. That way if unstable sorts do sneak in, at least they would be consistently unstable. Input would be much appreciated. Regards, Cory Fields
Re: Unstable build/host qsorts causing differing generated target code
On Fri, Jan 12, 2018 at 1:45 PM, Jeff Law wrote: > On 01/12/2018 11:26 AM, Cory Fields wrote: >> Quick disclaimer: I'm 100% new to GCC code and the dev process, so >> there are bound to be some faulty assumptions below. >> >> I recently worked on a build of gcc, x86_64-pc-linux-gnu -> >> x86_64-pc-linux-musl. In order to boost my confidence in musl, I >> decided that I'd like to ensure that 3 (and 4) stage bootstraps >> succeed and compare equal. >> >> I quickly ran into failed object comparisons at stage3. The issue, as >> it turned out, was that musl's qsort algorithm differs significantly >> from gcc's, though both (as far as I can tell) are perfectly legal. >> The c spec allows for different results in the cast of unstable >> arrays. > THe key here is the results can differ if the comparison function is not > stable. That's inherent in the qsort algorithms. > > But, if the comparison functions are fixed, then the implementation > differences between the qsorts won't matter. > > Alexander Monokov has led an effort to identify cases where the > comparison functions do not provide a stable ordering and to fix them. > Some remain, but the majority have been addressed over the last year. > His work also includes a qsort checking implementation to try and spot > these problems as part of GCC's internal consistency checking mechanisms. > > His work is on the development trunk and will show up in the upcoming > gcc-8 release. > > jeff Hi Jeff Thanks for letting me know about this effort. That's great news! Indeed, I ran into less of these issues on trunk. I'll go ahead and submit patches for the cases that turned up there. Regards, Cory
Re: Unstable build/host qsorts causing differing generated target code
Yes, this is the issue that I ran into.
I took the check further by asserting that if cmp(A, B) == 0,
memcmp(A, B) == 0 as well. But that''s tricky because the structure
may contain data that differs from A to B, but ultimately isn't used
after the sort. So it leads to a bunch of false-ish-positives. Though
arguably even those cases should be fixed as well.
Out of curiosity, other than bloat, what would be the downside of
using an internal sort? It would also have the benefit of allowing
more rigorous stability checks.
On Fri, Jan 12, 2018 at 2:37 PM, Alexander Monakov wrote:
> On Fri, 12 Jan 2018, Jakub Jelinek wrote:
>> The qsort checking failures are tracked in http://gcc.gnu.org/PR82407
>> meta bug, 8 bugs in there are fixed, 2 known ones remain.
>
> Note that qsort_chk only catches really bad issues where the compiler
> invokes undefined behavior by passing an invalid comparator to qsort;
> differences between Glibc and musl-hosted compilers may remain because
> qsort is not quaranteed to be a stable sort: when sorting an array {A, B}
> where
> A and B are not bitwise-identical but cmp(A, B) returns 0, the implementation
> of
> qsort may yield either {B, A} or {A, B}, and that may cause codegen
> differences.
>
> (in other words, bootstrapping on a libc with randomized qsort has
> a good chance to run into bootstrap miscompares even if qsort_chk-clean)
>
> Alexander
-static-pie and -static -pie
Hi list I'm playing with -static-pie and musl, which seems to be in good shape for 8.0.0. Nice work :) However, the fact that "gcc -static -pie" and "gcc -static-pie" produce different results is very unexpected. I understand the case for the new link-type, but merging the options when possible would be a huge benefit to existing buildsystems that already cope with both individually. My use-case: I'd like to build with --enable-default-pie, and by adding "-static" to my builds, produce static-pie binaries. But at the moment, that attempts to add an interp section. So my question is, if no conflicting options are found, why not hoist "-static -pie" to "-static-pie" ? Regards, Cory
Re: -static-pie and -static -pie
On Tue, Jan 30, 2018 at 1:35 PM, H.J. Lu wrote: > On Tue, Jan 30, 2018 at 10:26 AM, Cory Fields wrote: >> Hi list >> >> I'm playing with -static-pie and musl, which seems to be in good shape >> for 8.0.0. Nice work :) >> >> However, the fact that "gcc -static -pie" and "gcc -static-pie" >> produce different results is very unexpected. I understand the case >> for the new link-type, but merging the options when possible would be >> a huge benefit to existing buildsystems that already cope with both >> individually. >> >> My use-case: >> I'd like to build with --enable-default-pie, and by adding "-static" > > Why not adding "-static-pie" instead of "-static"? > >> to my builds, produce static-pie binaries. But at the moment, that >> attempts to add an interp section. >> >> So my question is, if no conflicting options are found, why not hoist >> "-static -pie" to "-static-pie" ? >> >> Regards, >> Cory > > > > -- > H.J. My build system, and plenty of others I'm sure, already handle -static and -pie. Having that understood to mean "static-pie" would mean that the combination would now just work. Asking a different way, if I request -static and -pie, without -nopie, quietly creating non-pie binary seems like a bug. Is there a reason _not_ to interpret it as -static-pie in that case?
Re: -static-pie and -static -pie
On Tue, Jan 30, 2018 at 2:14 PM, H.J. Lu wrote:
> On Tue, Jan 30, 2018 at 11:07 AM, Cory Fields wrote:
>> On Tue, Jan 30, 2018 at 1:35 PM, H.J. Lu wrote:
>>> On Tue, Jan 30, 2018 at 10:26 AM, Cory Fields wrote:
>>>> Hi list
>>>>
>>>> I'm playing with -static-pie and musl, which seems to be in good shape
>>>> for 8.0.0. Nice work :)
>>>>
>>>> However, the fact that "gcc -static -pie" and "gcc -static-pie"
>>>> produce different results is very unexpected. I understand the case
>>>> for the new link-type, but merging the options when possible would be
>>>> a huge benefit to existing buildsystems that already cope with both
>>>> individually.
>>>>
>>>> My use-case:
>>>> I'd like to build with --enable-default-pie, and by adding "-static"
>>>
>>> Why not adding "-static-pie" instead of "-static"?
>>>
>>>> to my builds, produce static-pie binaries. But at the moment, that
>>>> attempts to add an interp section.
>>>>
>>>> So my question is, if no conflicting options are found, why not hoist
>>>> "-static -pie" to "-static-pie" ?
>>>>
>>>> Regards,
>>>> Cory
>>>
>>>
>>>
>>> --
>>> H.J.
>>
>> My build system, and plenty of others I'm sure, already handle -static
>> and -pie. Having that understood to mean "static-pie" would mean that
>> the combination would now just work.
>>
>> Asking a different way, if I request -static and -pie, without -nopie,
>> quietly creating non-pie binary seems like a bug. Is there a reason
>> _not_ to interpret it as -static-pie in that case?
>
> GNU_USER_TARGET_STARTFILE_SPEC is defined as
>
> #define GNU_USER_TARGET_STARTFILE_SPEC \
> "%{shared:; \
> pg|p|profile:%{static-pie:grcrt1.o%s;:gcrt1.o%s}; \
> static:crt1.o%s; \
> static-pie:rcrt1.o%s; \
> " PIE_SPEC ":Scrt1.o%s; \
> :crt1.o%s} \
>crti.o%s \
>%{static:crtbeginT.o%s; \
> shared|static-pie|" PIE_SPEC ":crtbeginS.o%s; \
> :crtbegin.o%s} \
>%{fvtable-verify=none:%s; \
> fvtable-verify=preinit:vtv_start_preinit.o%s; \
> fvtable-verify=std:vtv_start.o%s} \
>" CRTOFFLOADBEGIN
>
> to pick a suitable crt1.o for static PIE when -static-pie is used.
>
> If gcc.c can convert ... -static ... -pie and ... -pie ... -static ... to
> -static-pic for GNU_USER_TARGET_STARTFILE_SPEC, it
> should work.
>
> --
> H.J.
Great, that's how I've fixed it locally. Would you consider accepting
a patch for this?
Re: -static-pie and -static -pie
After looking at this for quite a while, I'm afraid I'm unsure how to proceed.
As of now, static and static-pie are mutually exclusive. So given the
GNU_USER_TARGET_STARTFILE_SPEC you pasted
earlier, "static" matches before "static-pie", causing the wrong start files.
It seems to me that the static-pie target complicates things more than
matching against static+pie individually.
If I convert -static + -pie to -static-pie, then "static" won't be
matched in specs, where maybe it otherwise should. Same for -pie.
Would you prefer to swallow -static and -pie and pass along only
-static-pie? Or forward them all along, and fix the specs which look
for static before static-pie ?
Regards,
Cory
On Tue, Jan 30, 2018 at 2:36 PM, H.J. Lu wrote:
> On Tue, Jan 30, 2018 at 11:18 AM, Cory Fields wrote:
>> On Tue, Jan 30, 2018 at 2:14 PM, H.J. Lu wrote:
>>> On Tue, Jan 30, 2018 at 11:07 AM, Cory Fields wrote:
>>>> On Tue, Jan 30, 2018 at 1:35 PM, H.J. Lu wrote:
>>>>> On Tue, Jan 30, 2018 at 10:26 AM, Cory Fields
>>>>> wrote:
>>>>>> Hi list
>>>>>>
>>>>>> I'm playing with -static-pie and musl, which seems to be in good shape
>>>>>> for 8.0.0. Nice work :)
>>>>>>
>>>>>> However, the fact that "gcc -static -pie" and "gcc -static-pie"
>>>>>> produce different results is very unexpected. I understand the case
>>>>>> for the new link-type, but merging the options when possible would be
>>>>>> a huge benefit to existing buildsystems that already cope with both
>>>>>> individually.
>>>>>>
>>>>>> My use-case:
>>>>>> I'd like to build with --enable-default-pie, and by adding "-static"
>>>>>
>>>>> Why not adding "-static-pie" instead of "-static"?
>>>>>
>>>>>> to my builds, produce static-pie binaries. But at the moment, that
>>>>>> attempts to add an interp section.
>>>>>>
>>>>>> So my question is, if no conflicting options are found, why not hoist
>>>>>> "-static -pie" to "-static-pie" ?
>>>>>>
>>>>>> Regards,
>>>>>> Cory
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> H.J.
>>>>
>>>> My build system, and plenty of others I'm sure, already handle -static
>>>> and -pie. Having that understood to mean "static-pie" would mean that
>>>> the combination would now just work.
>>>>
>>>> Asking a different way, if I request -static and -pie, without -nopie,
>>>> quietly creating non-pie binary seems like a bug. Is there a reason
>>>> _not_ to interpret it as -static-pie in that case?
>>>
>>> GNU_USER_TARGET_STARTFILE_SPEC is defined as
>>>
>>> #define GNU_USER_TARGET_STARTFILE_SPEC \
>>> "%{shared:; \
>>> pg|p|profile:%{static-pie:grcrt1.o%s;:gcrt1.o%s}; \
>>> static:crt1.o%s; \
>>> static-pie:rcrt1.o%s; \
>>> " PIE_SPEC ":Scrt1.o%s; \
>>> :crt1.o%s} \
>>>crti.o%s \
>>>%{static:crtbeginT.o%s; \
>>> shared|static-pie|" PIE_SPEC ":crtbeginS.o%s; \
>>> :crtbegin.o%s} \
>>>%{fvtable-verify=none:%s; \
>>> fvtable-verify=preinit:vtv_start_preinit.o%s; \
>>> fvtable-verify=std:vtv_start.o%s} \
>>>" CRTOFFLOADBEGIN
>>>
>>> to pick a suitable crt1.o for static PIE when -static-pie is used.
>>>
>>> If gcc.c can convert ... -static ... -pie and ... -pie ... -static ... to
>>> -static-pic for GNU_USER_TARGET_STARTFILE_SPEC, it
>>> should work.
>>>
>>> --
>>> H.J.
>>
>> Great, that's how I've fixed it locally. Would you consider accepting
>> a patch for this?
>
> I'd like to see it in GCC 8. Please open a GCC bug and submit your
> patch against it.
>
> Thanks.
>
> --
> H.J.
