Re: [GIT PULL] selinux/selinux-pr-20260615

[Kuan-Wei Chiu <visitorckw@gmail.com>]

Hi Linus,

On Wed, Jun 17, 2026 at 12:54:44PM +0100, Linus Torvalds wrote:
> On Tue, 16 Jun 2026 at 03:55, Paul Moore <paul@paul-moore.com> wrote:
> >
> > - Avoid nontransitive comparisons comparisons in our sorting code
> >
> > Done to prevent unexpected sorting results due to overflow.  Qualys
> > documented a similar issue with glibc:
> > https://www.qualys.com/2024/01/30/qsort.txt
> 
> So this is clearly worth fixing in the selinux code regardless, but
> did anybody check whether our sorting routines in lib/sort.c actually
> have any overflow issues with non-transitive comparison functions?
> 
> Strange sort order may be confusing but tends to be largely harmless
> (the confusion might then obviously cause other issues)
> 
>  The whole "confuses the sort function enough to result in bad
> accesses" might be worth fixing in lib/sort.c if somebody looked into
> it...
> 
Since I made most of the recent changes to lib/sort.c, I can
hopefully shed some light on this.

With the current Linux lib/sort.c implementation, passing a compare
function that lacks transitivity will absolutely **not** lead to any
out-of-bounds memory accesses. Unlike glibc which defaults to merge
sort and falls back to heapsort if malloc fails, the kernel uses a
strict in-place heapsort. Because of this, the compare and swap
operations will always operate safely within the boundaries of the
provided array.

However, it still inevitably leads to unexpected sorting results. This
has caused actual user-visible issues in the past (the previous acpi
breakage being an example [1][2]). It turns out it is easy for people
to accidentally write comparators that violate transitivity, which is
why I submitted a patch previously to emphasize the properties a
comparator must satisfy. [3]

I have actually thought about whether we could detect transitivity
violations at runtime. But if we map this to graph theory: treating
each element as a node and the comparison results as directed edges,
detecting a violation is equivalent to finding a cycle in the graph.
Doing this would require an O(n^2) time complexity, which is obviously
unacceptable at runtime.

[1]: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
[2]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=233323f9b9f828cd7cd5145ad811c1990b692542
[3]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=4e0a15f8b4bd47548032acccdbeb5b9083b3675e

Regards,
Kuan-Wei