Re: [PATCH] scripts/sorttable: Fix orc_sort_cmp() to maintain symmetry and transitivity

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

Hi Andrew,

On Thu, Dec 26, 2024 at 01:37:38PM -0800, Andrew Morton wrote:
> On Thu, 26 Dec 2024 22:03:32 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> 
> > The orc_sort_cmp() function, used with qsort(), previously violated the
> > symmetry and transitivity rules required by the C standard.
> > Specifically, when both entries are ORC_TYPE_UNDEFINED, it could result
> > in both a < b and b < a, which breaks the required symmetry and
> > transitivity. This can lead to undefined behavior and incorrect sorting
> > results, potentially causing memory corruption in glibc
> > implementations [1].
> > 
> > Symmetry: If x < y, then y > x.
> > Transitivity: If x < y and y < z, then x < z.
> > 
> > Fix the comparison logic to return 0 when both entries are
> > ORC_TYPE_UNDEFINED, ensuring compliance with qsort() requirements.
> > 
> > Link: https://www.qualys.com/2024/01/30/qsort.txt [1]
> > Fixes: 57fa18994285 ("scripts/sorttable: Implement build-time ORC unwind table sorting")
> > Fixes: fb799447ae29 ("x86,objtool: Split UNWIND_HINT_EMPTY in two")
> 
> Two Fixes:, years apart.  This is problematic for stable tree
> maintainers - what do they do if their kernel has one of the above
> commits but not the other?
>
TL;DR:
Any kernel containing either of the two commits requires a fix.

> Can we please clarify this?  Which kernel version(s) need the fix?
> 
The issue originally appeared in commit 57fa18994285
("scripts/sorttable: Implement build-time ORC unwind table sorting"),
where the comparison function was:

    return orc_a->sp_reg == ORC_REG_UNDEFINED && !orc_a->end ? -1 : 1;

It was later updated in commit fb799447ae29 ("x86,objtool: Split
UNWIND_HINT_EMPTY in two") to:

    return orc_a->type == ORC_TYPE_UNDEFINED ? -1 : 1;

Both commits introduce the need for a fix, as the comparison logic in
both cases violates symmetry and transitivity.

> Or perhaps this should have been presented as two separate patches.
> 
For 6.1.y and earlier kernels, applying this patch directly is likely
to cause conflicts. A separate patch tailored to those versions will be
required. Please correct me if I'm mistaken, but my understanding is
that after this patch lands in Linus' tree, I should submit additional
patches for 6.1 and earlier versions to the stable mailing list with
the appropriate subject prefix.

Regards,
Kuan-Wei