* rustc SIGILL since qsort_r patches @ 2023-11-05 0:55 Cristian Rodríguez 2023-11-05 1:10 ` Andrew Pinski 2023-11-07 14:32 ` Florian Weimer 0 siblings, 2 replies; 25+ messages in thread From: Cristian Rodríguez @ 2023-11-05 0:55 UTC (permalink / raw) To: Adhemerval Zanella via Libc-alpha [-- Attachment #1: Type: text/plain, Size: 1052 bytes --] Hi: After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) happens compiling anything in release mode with any toolchain (stable, beta, nightly) #0 0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/ libLLVM-17-rust-1.75.0-nightly.so #1 0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335 #2 0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/ libLLVM-17-rust-1.75.0-nightly.so git head == bad 2.38 == good Main interest is to know if I am not alone and if anyone else has observed this problem so far. Thanks.. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-05 0:55 rustc SIGILL since qsort_r patches Cristian Rodríguez @ 2023-11-05 1:10 ` Andrew Pinski 2023-11-05 1:13 ` Andrew Pinski 2023-11-06 14:13 ` Adhemerval Zanella Netto 2023-11-07 14:32 ` Florian Weimer 1 sibling, 2 replies; 25+ messages in thread From: Andrew Pinski @ 2023-11-05 1:10 UTC (permalink / raw) To: Cristian Rodríguez; +Cc: Adhemerval Zanella via Libc-alpha On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote: > > Hi: > > After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) > > happens compiling anything in release mode with any toolchain (stable, beta, nightly) > > #0 0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so > > #1 0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335 > > #2 0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so > I think this is a bug in LLVM's BranchFolder::MergePotentialsElt::operator< code: See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html Specifically it has the following comment: // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing 489 // an object with itself. 490#ifndef _GLIBCXX_DEBUG 491 llvm_unreachable("Predecessor appears twice"); 492#else 493 return false; 494#endif Well glibc's qsort implementation will also now compare with itself. Thanks, Andrew > git head == bad > 2.38 == good > > Main interest is to know if I am not alone and if anyone else has observed this problem so far. > Thanks.. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-05 1:10 ` Andrew Pinski @ 2023-11-05 1:13 ` Andrew Pinski 2023-11-05 12:15 ` Cristian Rodríguez 2023-11-06 14:13 ` Adhemerval Zanella Netto 1 sibling, 1 reply; 25+ messages in thread From: Andrew Pinski @ 2023-11-05 1:13 UTC (permalink / raw) To: Cristian Rodríguez; +Cc: Adhemerval Zanella via Libc-alpha On Sat, Nov 4, 2023 at 6:10 PM Andrew Pinski <pinskia@gmail.com> wrote: > > On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote: > > > > Hi: > > > > After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) > > > > happens compiling anything in release mode with any toolchain (stable, beta, nightly) > > > > #0 0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so > > > > #1 0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335 > > > > #2 0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so > > > > I think this is a bug in LLVM's > BranchFolder::MergePotentialsElt::operator< code: > See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html > > Specifically it has the following comment: > // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing > 489 // an object with itself. > 490#ifndef _GLIBCXX_DEBUG > 491 llvm_unreachable("Predecessor appears twice"); > 492#else > 493 return false; > 494#endif > > Well glibc's qsort implementation will also now compare with itself. Also qsort comparison is not exactly < but rather <=> which array_pod_sort_comparator tries to emulate but BranchFolder::MergePotentialsElt::operator< specifically calls unreachable if 2 are things are equal. > > Thanks, > Andrew > > > git head == bad > > 2.38 == good > > > > Main interest is to know if I am not alone and if anyone else has observed this problem so far. > > Thanks.. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-05 1:13 ` Andrew Pinski @ 2023-11-05 12:15 ` Cristian Rodríguez 0 siblings, 0 replies; 25+ messages in thread From: Cristian Rodríguez @ 2023-11-05 12:15 UTC (permalink / raw) To: Andrew Pinski; +Cc: Adhemerval Zanella via Libc-alpha [-- Attachment #1: Type: text/plain, Size: 473 bytes --] On Sat, Nov 4, 2023 at 10:13 PM Andrew Pinski <pinskia@gmail.com> wrote: > > > Well glibc's qsort implementation will also now compare with itself. > > Also qsort comparison is not exactly < but rather <=> which > array_pod_sort_comparator tries to emulate but > BranchFolder::MergePotentialsElt::operator< specifically calls > unreachable if 2 are things are equal. > > > Thank you, filled a bug report. https://github.com/llvm/llvm-project/issues/71312 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-05 1:10 ` Andrew Pinski 2023-11-05 1:13 ` Andrew Pinski @ 2023-11-06 14:13 ` Adhemerval Zanella Netto 2023-11-07 11:09 ` Florian Weimer 1 sibling, 1 reply; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-06 14:13 UTC (permalink / raw) To: Andrew Pinski, Cristian Rodríguez; +Cc: Adhemerval Zanella via Libc-alpha On 04/11/23 22:10, Andrew Pinski wrote: > On Sat, Nov 4, 2023 at 5:55 PM Cristian Rodríguez <cristian@rodriguez.im> wrote: >> >> Hi: >> >> After quite some head scratching I found the recent qsort_r patches triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) >> >> happens compiling anything in release mode with any toolchain (stable, beta, nightly) >> >> #0 0x000015129e40516a in int llvm::array_pod_sort_comparator<llvm::BranchFolder::MergePotentialsElt>(void const*, void const*) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so >> >> #1 0x00001512a0043779 in __GI___qsort_r (pbase=0x15128c90bd80, total_elems=<optimized out>, size=0x10, cmp=<optimized out>, arg=<optimized out>) at qsort.c:335 >> >> #2 0x000015129e4df6e6 in llvm::BranchFolder::TryTailMergeBlocks(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, unsigned int) () from /home/crrodriguez/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/../lib/libLLVM-17-rust-1.75.0-nightly.so >> > > I think this is a bug in LLVM's > BranchFolder::MergePotentialsElt::operator< code: > See: https://llvm.org/doxygen/BranchFolding_8cpp_source.html > > Specifically it has the following comment: > // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing > 489 // an object with itself. > 490#ifndef _GLIBCXX_DEBUG > 491 llvm_unreachable("Predecessor appears twice"); > 492#else > 493 return false; > 494#endif > > Well glibc's qsort implementation will also now compare with itself. > > Thanks, > Andrew > >> git head == bad >> 2.38 == good >> >> Main interest is to know if I am not alone and if anyone else has observed this problem so far. >> Thanks.. Just a side note that the quicksort implementation was also used for size (number of elements times size per element) larger than the installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or whether malloc fails. So it is a latent issue, that did not trigger before by chance. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-06 14:13 ` Adhemerval Zanella Netto @ 2023-11-07 11:09 ` Florian Weimer 2023-11-07 12:48 ` Adhemerval Zanella Netto 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-07 11:09 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Adhemerval Zanella Netto: > Just a side note that the quicksort implementation was also used for > size (number of elements times size per element) larger than the > installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or > whether malloc fails. So it is a latent issue, that did not trigger > before by chance. Is it ever beneficial to call the comparison function with identical pointers, though? This change is going to have annoying consequences for backwards compatibility. Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 11:09 ` Florian Weimer @ 2023-11-07 12:48 ` Adhemerval Zanella Netto 2023-11-07 13:04 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-07 12:48 UTC (permalink / raw) To: Florian Weimer Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha On 07/11/23 08:09, Florian Weimer wrote: > * Adhemerval Zanella Netto: > >> Just a side note that the quicksort implementation was also used for >> size (number of elements times size per element) larger than the >> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >> whether malloc fails. So it is a latent issue, that did not trigger >> before by chance. > > Is it ever beneficial to call the comparison function with identical > pointers, though? Afaik this how introsort works, and I am not aware of any comparison sort with O(1) worst-case space complexity that does not require a comparison callback that work as <=>. > > This change is going to have annoying consequences for backwards > compatibility. > > Thanks, > Florian > ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 12:48 ` Adhemerval Zanella Netto @ 2023-11-07 13:04 ` Florian Weimer 2023-11-07 13:07 ` Adhemerval Zanella Netto ` (2 more replies) 0 siblings, 3 replies; 25+ messages in thread From: Florian Weimer @ 2023-11-07 13:04 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Adhemerval Zanella Netto: > On 07/11/23 08:09, Florian Weimer wrote: >> * Adhemerval Zanella Netto: >> >>> Just a side note that the quicksort implementation was also used for >>> size (number of elements times size per element) larger than the >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >>> whether malloc fails. So it is a latent issue, that did not trigger >>> before by chance. >> >> Is it ever beneficial to call the comparison function with identical >> pointers, though? > > Afaik this how introsort works, and I am not aware of any comparison > sort with O(1) worst-case space complexity that does not require > a comparison callback that work as <=>. I think the LLVM code will only assert if it is called with equal pointers, as the array elements are expected to be distinct (hence the assert). My question is more along these lines: If the pointers are equal, does it make sense to perform the indirection function call? I guess that depends on the nature of the comparison function. I'm not sure where equal-pointers call happens, but why wouldn't something like this be an overall win? while (k <= n / 2) { size_t j = 2 * k; if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) j++; + if (k ==j) + continue; if (cmp (base + (k * size), base + (j * size), arg) >= 0) break; do_swap (base + (size * j), base + (k * size), size, swap_type); k = j; } Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 13:04 ` Florian Weimer @ 2023-11-07 13:07 ` Adhemerval Zanella Netto 2023-11-07 13:13 ` Florian Weimer 2023-11-07 14:57 ` Stepan Golosunov 2 siblings, 0 replies; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-07 13:07 UTC (permalink / raw) To: Florian Weimer Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha On 07/11/23 10:04, Florian Weimer wrote: > * Adhemerval Zanella Netto: > >> On 07/11/23 08:09, Florian Weimer wrote: >>> * Adhemerval Zanella Netto: >>> >>>> Just a side note that the quicksort implementation was also used for >>>> size (number of elements times size per element) larger than the >>>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >>>> whether malloc fails. So it is a latent issue, that did not trigger >>>> before by chance. >>> >>> Is it ever beneficial to call the comparison function with identical >>> pointers, though? >> >> Afaik this how introsort works, and I am not aware of any comparison >> sort with O(1) worst-case space complexity that does not require >> a comparison callback that work as <=>. > > I think the LLVM code will only assert if it is called with equal > pointers, as the array elements are expected to be distinct (hence the > assert). > > My question is more along these lines: If the pointers are equal, does > it make sense to perform the indirection function call? I guess that > depends on the nature of the comparison function. > > I'm not sure where equal-pointers call happens, but why wouldn't > something like this be an overall win? Ah right, it looks reasonable to me yes. > > while (k <= n / 2) > { > size_t j = 2 * k; > if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) > j++; > > + if (k ==j) > + continue; > if (cmp (base + (k * size), base + (j * size), arg) >= 0) > break; > > do_swap (base + (size * j), base + (k * size), size, swap_type); > k = j; > } > > > Thanks, > Florian > ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 13:04 ` Florian Weimer 2023-11-07 13:07 ` Adhemerval Zanella Netto @ 2023-11-07 13:13 ` Florian Weimer 2023-11-07 13:26 ` Adhemerval Zanella Netto 2023-11-07 14:57 ` Stepan Golosunov 2 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-07 13:13 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Florian Weimer: > I'm not sure where equal-pointers call happens, but why wouldn't > something like this be an overall win? > > while (k <= n / 2) > { > size_t j = 2 * k; > if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) > j++; > > + if (k ==j) > + continue; That should be a break, not a continue. > if (cmp (base + (k * size), base + (j * size), arg) >= 0) > break; > > do_swap (base + (size * j), base + (k * size), size, swap_type); > k = j; > } And I think we need it because we entire undefined terrority: we end up calling __memswap with identical pointers. Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 13:13 ` Florian Weimer @ 2023-11-07 13:26 ` Adhemerval Zanella Netto 2023-11-07 14:02 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-07 13:26 UTC (permalink / raw) To: Florian Weimer Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha On 07/11/23 10:13, Florian Weimer wrote: > * Florian Weimer: > >> I'm not sure where equal-pointers call happens, but why wouldn't >> something like this be an overall win? >> >> while (k <= n / 2) >> { >> size_t j = 2 * k; >> if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) >> j++; >> >> + if (k ==j) >> + continue; > > That should be a break, not a continue. > >> if (cmp (base + (k * size), base + (j * size), arg) >= 0) >> break; >> >> do_swap (base + (size * j), base + (k * size), size, swap_type); >> k = j; >> } > > And I think we need it because we entire undefined terrority: we end up > calling __memswap with identical pointers. Fair enough, could you send a patch? ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 13:26 ` Adhemerval Zanella Netto @ 2023-11-07 14:02 ` Florian Weimer 0 siblings, 0 replies; 25+ messages in thread From: Florian Weimer @ 2023-11-07 14:02 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Adhemerval Zanella Netto: >> And I think we need it because we entire undefined terrority: we end up >> calling __memswap with identical pointers. > > Fair enough, could you send a patch? Sure, I'll send something later today. Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 13:04 ` Florian Weimer 2023-11-07 13:07 ` Adhemerval Zanella Netto 2023-11-07 13:13 ` Florian Weimer @ 2023-11-07 14:57 ` Stepan Golosunov 2023-11-07 16:05 ` Florian Weimer 2 siblings, 1 reply; 25+ messages in thread From: Stepan Golosunov @ 2023-11-07 14:57 UTC (permalink / raw) To: Florian Weimer Cc: Adhemerval Zanella Netto, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote: > * Adhemerval Zanella Netto: > > > On 07/11/23 08:09, Florian Weimer wrote: > >> * Adhemerval Zanella Netto: > >> > >>> Just a side note that the quicksort implementation was also used for > >>> size (number of elements times size per element) larger than the > >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or > >>> whether malloc fails. So it is a latent issue, that did not trigger > >>> before by chance. > >> > >> Is it ever beneficial to call the comparison function with identical > >> pointers, though? > > > > Afaik this how introsort works, and I am not aware of any comparison > > sort with O(1) worst-case space complexity that does not require > > a comparison callback that work as <=>. > > I think the LLVM code will only assert if it is called with equal > pointers, as the array elements are expected to be distinct (hence the > assert). > > My question is more along these lines: If the pointers are equal, does > it make sense to perform the indirection function call? I guess that > depends on the nature of the comparison function. > > I'm not sure where equal-pointers call happens, but why wouldn't > something like this be an overall win? > > while (k <= n / 2) > { > size_t j = 2 * k; Shouldn't this be size_t j = 2 * k + 1; instead? Looks like the existing formula is designed for base-1 arrays. > if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) > j++; > > + if (k ==j) > + continue; > if (cmp (base + (k * size), base + (j * size), arg) >= 0) > break; > > do_swap (base + (size * j), base + (k * size), size, swap_type); > k = j; > } > > > Thanks, > Florian > ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 14:57 ` Stepan Golosunov @ 2023-11-07 16:05 ` Florian Weimer 2023-11-17 10:35 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-07 16:05 UTC (permalink / raw) To: Stepan Golosunov Cc: Adhemerval Zanella Netto, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Stepan Golosunov: > On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote: >> * Adhemerval Zanella Netto: >> >> > On 07/11/23 08:09, Florian Weimer wrote: >> >> * Adhemerval Zanella Netto: >> >> >> >>> Just a side note that the quicksort implementation was also used for >> >>> size (number of elements times size per element) larger than the >> >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >> >>> whether malloc fails. So it is a latent issue, that did not trigger >> >>> before by chance. >> >> >> >> Is it ever beneficial to call the comparison function with identical >> >> pointers, though? >> > >> > Afaik this how introsort works, and I am not aware of any comparison >> > sort with O(1) worst-case space complexity that does not require >> > a comparison callback that work as <=>. >> >> I think the LLVM code will only assert if it is called with equal >> pointers, as the array elements are expected to be distinct (hence the >> assert). >> >> My question is more along these lines: If the pointers are equal, does >> it make sense to perform the indirection function call? I guess that >> depends on the nature of the comparison function. >> >> I'm not sure where equal-pointers call happens, but why wouldn't >> something like this be an overall win? >> >> while (k <= n / 2) >> { >> size_t j = 2 * k; > > Shouldn't this be > > size_t j = 2 * k + 1; > > instead? Looks like the existing formula is designed for base-1 > arrays. Not sure, Adhemerval? Obtaining the parent index would need adjusting then as well, right? Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 16:05 ` Florian Weimer @ 2023-11-17 10:35 ` Florian Weimer 2023-11-17 11:44 ` Adhemerval Zanella Netto 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-17 10:35 UTC (permalink / raw) To: Stepan Golosunov Cc: Adhemerval Zanella Netto, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Florian Weimer: > * Stepan Golosunov: > >> On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote: >>> * Adhemerval Zanella Netto: >>> >>> > On 07/11/23 08:09, Florian Weimer wrote: >>> >> * Adhemerval Zanella Netto: >>> >> >>> >>> Just a side note that the quicksort implementation was also used for >>> >>> size (number of elements times size per element) larger than the >>> >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >>> >>> whether malloc fails. So it is a latent issue, that did not trigger >>> >>> before by chance. >>> >> >>> >> Is it ever beneficial to call the comparison function with identical >>> >> pointers, though? >>> > >>> > Afaik this how introsort works, and I am not aware of any comparison >>> > sort with O(1) worst-case space complexity that does not require >>> > a comparison callback that work as <=>. >>> >>> I think the LLVM code will only assert if it is called with equal >>> pointers, as the array elements are expected to be distinct (hence the >>> assert). >>> >>> My question is more along these lines: If the pointers are equal, does >>> it make sense to perform the indirection function call? I guess that >>> depends on the nature of the comparison function. >>> >>> I'm not sure where equal-pointers call happens, but why wouldn't >>> something like this be an overall win? >>> >>> while (k <= n / 2) >>> { >>> size_t j = 2 * k; >> >> Shouldn't this be >> >> size_t j = 2 * k + 1; >> >> instead? Looks like the existing formula is designed for base-1 >> arrays. > > Not sure, Adhemerval? > > Obtaining the parent index would need adjusting then as well, right? I have isolated a test from stdlib/qsort.c and can confirm that heapsort_r does not actually reliably sort. Application-side, this does not sort in a mis-sort because of the insertion at the end, but the qsort is substantially slower against adversial inputs than the old implementation because it performs many more comparisons. It clearly shows quadratic behavior. I'm going to try to fix the heapsort implementation. Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-17 10:35 ` Florian Weimer @ 2023-11-17 11:44 ` Adhemerval Zanella Netto 2023-11-17 13:33 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-17 11:44 UTC (permalink / raw) To: Florian Weimer, Stepan Golosunov Cc: Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha On 17/11/23 07:35, Florian Weimer wrote: > * Florian Weimer: > >> * Stepan Golosunov: >> >>> On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote: >>>> * Adhemerval Zanella Netto: >>>> >>>>> On 07/11/23 08:09, Florian Weimer wrote: >>>>>> * Adhemerval Zanella Netto: >>>>>> >>>>>>> Just a side note that the quicksort implementation was also used for >>>>>>> size (number of elements times size per element) larger than the >>>>>>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >>>>>>> whether malloc fails. So it is a latent issue, that did not trigger >>>>>>> before by chance. >>>>>> >>>>>> Is it ever beneficial to call the comparison function with identical >>>>>> pointers, though? >>>>> >>>>> Afaik this how introsort works, and I am not aware of any comparison >>>>> sort with O(1) worst-case space complexity that does not require >>>>> a comparison callback that work as <=>. >>>> >>>> I think the LLVM code will only assert if it is called with equal >>>> pointers, as the array elements are expected to be distinct (hence the >>>> assert). >>>> >>>> My question is more along these lines: If the pointers are equal, does >>>> it make sense to perform the indirection function call? I guess that >>>> depends on the nature of the comparison function. >>>> >>>> I'm not sure where equal-pointers call happens, but why wouldn't >>>> something like this be an overall win? >>>> >>>> while (k <= n / 2) >>>> { >>>> size_t j = 2 * k; >>> >>> Shouldn't this be >>> >>> size_t j = 2 * k + 1; >>> >>> instead? Looks like the existing formula is designed for base-1 >>> arrays. >> >> Not sure, Adhemerval? >> >> Obtaining the parent index would need adjusting then as well, right? > > I have isolated a test from stdlib/qsort.c and can confirm that > heapsort_r does not actually reliably sort. Application-side, this does > not sort in a mis-sort because of the insertion at the end, but the > qsort is substantially slower against adversial inputs than the old > implementation because it performs many more comparisons. It clearly > shows quadratic behavior. > > I'm going to try to fix the heapsort implementation. Indeed introsort is slower than the previous mergesort, but are you sure is is quadratic? Could you share the input that is triggering wrong behavior, I will try to improve testing to catch it. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-17 11:44 ` Adhemerval Zanella Netto @ 2023-11-17 13:33 ` Florian Weimer 2023-11-17 13:57 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-17 13:33 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Stepan Golosunov, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Adhemerval Zanella Netto: > Indeed introsort is slower than the previous mergesort, but are you sure > is is quadratic? Could you share the input that is triggering wrong > behavior, I will try to improve testing to catch it. Try this input array: 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18, 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36, 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 98, 99 I count 2645 comparisons. This is unrelated to the heapsort bugs, for which I have a fix. The heapsort function isn't even called. The bulk of the comparisons happen before the insertion sort phase, which looks correct, so the handover to heapsort for adversarial input isn't happening. Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-17 13:33 ` Florian Weimer @ 2023-11-17 13:57 ` Florian Weimer 2023-11-17 16:17 ` Florian Weimer 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-17 13:57 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Stepan Golosunov, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Florian Weimer: > * Adhemerval Zanella Netto: > >> Indeed introsort is slower than the previous mergesort, but are you sure >> is is quadratic? Could you share the input that is triggering wrong >> behavior, I will try to improve testing to catch it. > > Try this input array: > > 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18, > 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36, > 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13, > 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, > 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, > 87, 89, 91, 93, 95, 97, 98, 99 > > I count 2645 comparisons. > > This is unrelated to the heapsort bugs, for which I have a fix. The > heapsort function isn't even called. > > The bulk of the comparisons happen before the insertion sort phase, > which looks correct, so the handover to heapsort for adversarial input > isn't happening. Depth decrement is missing when descending into the companion partition of a small partition. Fixing that exposes more heap sort problems unfortunately. Looking … Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-17 13:57 ` Florian Weimer @ 2023-11-17 16:17 ` Florian Weimer 2023-11-17 18:37 ` Adhemerval Zanella 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-17 16:17 UTC (permalink / raw) To: Adhemerval Zanella Netto Cc: Stepan Golosunov, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha * Florian Weimer: > * Florian Weimer: > >> * Adhemerval Zanella Netto: >> >>> Indeed introsort is slower than the previous mergesort, but are you sure >>> is is quadratic? Could you share the input that is triggering wrong >>> behavior, I will try to improve testing to catch it. >> >> Try this input array: >> >> 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18, >> 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36, >> 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13, >> 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, >> 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, >> 87, 89, 91, 93, 95, 97, 98, 99 >> >> I count 2645 comparisons. >> >> This is unrelated to the heapsort bugs, for which I have a fix. The >> heapsort function isn't even called. >> >> The bulk of the comparisons happen before the insertion sort phase, >> which looks correct, so the handover to heapsort for adversarial input >> isn't happening. > > Depth decrement is missing when descending into the companion partition > of a small partition. > > Fixing that exposes more heap sort problems unfortunately. Looking … I think I found all the issues. Need to write up the tests still. Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-17 16:17 ` Florian Weimer @ 2023-11-17 18:37 ` Adhemerval Zanella 0 siblings, 0 replies; 25+ messages in thread From: Adhemerval Zanella @ 2023-11-17 18:37 UTC (permalink / raw) To: Florian Weimer Cc: Stepan Golosunov, Andrew Pinski, Cristian Rodríguez, Adhemerval Zanella via Libc-alpha > On 17 Nov 2023, at 13:17, Florian Weimer <fweimer@redhat.com> wrote: > > * Florian Weimer: > >> * Florian Weimer: >> >>> * Adhemerval Zanella Netto: >>> >>>> Indeed introsort is slower than the previous mergesort, but are you sure >>>> is is quadratic? Could you share the input that is triggering wrong >>>> behavior, I will try to improve testing to catch it. >>> >>> Try this input array: >>> >>> 0, 94, 2, 50, 4, 74, 6, 52, 8, 86, 10, 54, 12, 76, 14, 56, 16, 92, 18, >>> 58, 20, 78, 22, 60, 24, 88, 26, 62, 28, 80, 30, 64, 32, 96, 34, 66, 36, >>> 82, 38, 68, 40, 90, 42, 70, 44, 84, 46, 72, 48, 1, 3, 5, 7, 9, 11, 13, >>> 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, >>> 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, >>> 87, 89, 91, 93, 95, 97, 98, 99 >>> >>> I count 2645 comparisons. >>> >>> This is unrelated to the heapsort bugs, for which I have a fix. The >>> heapsort function isn't even called. >>> >>> The bulk of the comparisons happen before the insertion sort phase, >>> which looks correct, so the handover to heapsort for adversarial input >>> isn't happening. >> >> Depth decrement is missing when descending into the companion partition >> of a small partition. >> >> Fixing that exposes more heap sort problems unfortunately. Looking … > > I think I found all the issues. Need to write up the tests still. > > Thanks, > Florian Thanks for working on this! ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-05 0:55 rustc SIGILL since qsort_r patches Cristian Rodríguez 2023-11-05 1:10 ` Andrew Pinski @ 2023-11-07 14:32 ` Florian Weimer 2023-11-08 14:19 ` Florian Weimer 1 sibling, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-07 14:32 UTC (permalink / raw) To: Cristian Rodríguez; +Cc: Adhemerval Zanella via Libc-alpha * Cristian Rodríguez: > After quite some head scratching I found the recent qsort_r patches > triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) > > happens compiling anything in release mode with any toolchain (stable, > beta, nightly) Could you share more details about your environment? I'm trying to reproduce it to see which code paths we need to fix. Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-07 14:32 ` Florian Weimer @ 2023-11-08 14:19 ` Florian Weimer 2023-11-08 19:56 ` Cristian Rodríguez 0 siblings, 1 reply; 25+ messages in thread From: Florian Weimer @ 2023-11-08 14:19 UTC (permalink / raw) To: Cristian Rodríguez; +Cc: Adhemerval Zanella via Libc-alpha * Florian Weimer: > * Cristian Rodríguez: > >> After quite some head scratching I found the recent qsort_r patches >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) >> >> happens compiling anything in release mode with any toolchain (stable, >> beta, nightly) > > Could you share more details about your environment? I'm trying to > reproduce it to see which code paths we need to fix. I have just pushed what I think is a workaround. Would you please check if it fixes your LLVM/rustc issue? Thanks, Florian ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-08 14:19 ` Florian Weimer @ 2023-11-08 19:56 ` Cristian Rodríguez 2023-11-09 11:49 ` Cristian Rodríguez 0 siblings, 1 reply; 25+ messages in thread From: Cristian Rodríguez @ 2023-11-08 19:56 UTC (permalink / raw) To: Florian Weimer; +Cc: Adhemerval Zanella via Libc-alpha [-- Attachment #1: Type: text/plain, Size: 763 bytes --] On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com> wrote: > * Florian Weimer: > > > * Cristian Rodríguez: > > > >> After quite some head scratching I found the recent qsort_r patches > >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) > >> > >> happens compiling anything in release mode with any toolchain (stable, > >> beta, nightly) > > > > Could you share more details about your environment? I'm trying to > > reproduce it to see which code paths we need to fix. > > I have just pushed what I think is a workaround. Would you please check > if it fixes your LLVM/rustc issue? > > Thanks, > Florian > > I will try it in the environment when it hits the build pipes and report back. Thanks. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-08 19:56 ` Cristian Rodríguez @ 2023-11-09 11:49 ` Cristian Rodríguez 2023-11-09 12:40 ` Adhemerval Zanella Netto 0 siblings, 1 reply; 25+ messages in thread From: Cristian Rodríguez @ 2023-11-09 11:49 UTC (permalink / raw) To: Florian Weimer; +Cc: Adhemerval Zanella via Libc-alpha [-- Attachment #1: Type: text/plain, Size: 988 bytes --] On Wed, Nov 8, 2023 at 4:56 PM Cristian Rodríguez <cristian@rodriguez.im> wrote: > > > On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com> wrote: > >> * Florian Weimer: >> >> > * Cristian Rodríguez: >> > >> >> After quite some head scratching I found the recent qsort_r patches >> >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) >> >> >> >> happens compiling anything in release mode with any toolchain (stable, >> >> beta, nightly) >> > >> > Could you share more details about your environment? I'm trying to >> > reproduce it to see which code paths we need to fix. >> >> I have just pushed what I think is a workaround. Would you please check >> if it fixes your LLVM/rustc issue? >> >> Thanks, >> Florian >> >> I will try it in the environment when it hits the build pipes and report > back. > Thanks. > It successfully papers over llvm's bug..which has since also been fixed. Thank you and keep up ! ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: rustc SIGILL since qsort_r patches 2023-11-09 11:49 ` Cristian Rodríguez @ 2023-11-09 12:40 ` Adhemerval Zanella Netto 0 siblings, 0 replies; 25+ messages in thread From: Adhemerval Zanella Netto @ 2023-11-09 12:40 UTC (permalink / raw) To: Cristian Rodríguez, Florian Weimer; +Cc: Adhemerval Zanella via Libc-alpha On 09/11/23 08:49, Cristian Rodríguez wrote: > > > On Wed, Nov 8, 2023 at 4:56 PM Cristian Rodríguez <cristian@rodriguez.im <mailto:cristian@rodriguez.im>> wrote: > > > > On Wed, Nov 8, 2023 at 11:19 AM Florian Weimer <fweimer@redhat.com <mailto:fweimer@redhat.com>> wrote: > > * Florian Weimer: > > > * Cristian Rodríguez: > > > >> After quite some head scratching I found the recent qsort_r patches > >> triggers a bug "somewhere" that makes rustc LTO end in sigkill (ud2) > >> > >> happens compiling anything in release mode with any toolchain (stable, > >> beta, nightly) > > > > Could you share more details about your environment? I'm trying to > > reproduce it to see which code paths we need to fix. > > I have just pushed what I think is a workaround. Would you please check > if it fixes your LLVM/rustc issue? > > Thanks, > Florian > > I will try it in the environment when it hits the build pipes and report back. > Thanks. > > > It successfully papers over llvm's bug..which has since also been fixed. > Thank you and keep up ! > > Thanks for brings this up as well. ^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2023-11-17 18:38 UTC | newest] Thread overview: 25+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-11-05 0:55 rustc SIGILL since qsort_r patches Cristian Rodríguez 2023-11-05 1:10 ` Andrew Pinski 2023-11-05 1:13 ` Andrew Pinski 2023-11-05 12:15 ` Cristian Rodríguez 2023-11-06 14:13 ` Adhemerval Zanella Netto 2023-11-07 11:09 ` Florian Weimer 2023-11-07 12:48 ` Adhemerval Zanella Netto 2023-11-07 13:04 ` Florian Weimer 2023-11-07 13:07 ` Adhemerval Zanella Netto 2023-11-07 13:13 ` Florian Weimer 2023-11-07 13:26 ` Adhemerval Zanella Netto 2023-11-07 14:02 ` Florian Weimer 2023-11-07 14:57 ` Stepan Golosunov 2023-11-07 16:05 ` Florian Weimer 2023-11-17 10:35 ` Florian Weimer 2023-11-17 11:44 ` Adhemerval Zanella Netto 2023-11-17 13:33 ` Florian Weimer 2023-11-17 13:57 ` Florian Weimer 2023-11-17 16:17 ` Florian Weimer 2023-11-17 18:37 ` Adhemerval Zanella 2023-11-07 14:32 ` Florian Weimer 2023-11-08 14:19 ` Florian Weimer 2023-11-08 19:56 ` Cristian Rodríguez 2023-11-09 11:49 ` Cristian Rodríguez 2023-11-09 12:40 ` Adhemerval Zanella Netto
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).