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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <Z23nNV+zM101SltV@visitorckw-System-Product-Name>
Date: Fri, 27 Dec 2024 07:31:01 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: peterz@...radead.org, shile.zhang@...ux.alibaba.com, mingo@...nel.org,
	rostedt@...dmis.org, jpoimboe@...nel.org, jserv@...s.ncku.edu.tw,
	chuang@...nycu.edu.tw, linux-kernel@...r.kernel.org,
	stable@...r.kernel.org
Subject: Re: [PATCH] scripts/sorttable: Fix orc_sort_cmp() to maintain
 symmetry and transitivity

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@...il.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