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

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

[Kuan-Wei Chiu]

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")
Cc: stable@vger.kernel.org
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 scripts/sorttable.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/scripts/sorttable.h b/scripts/sorttable.h
index 7bd0184380d3..a7c5445baf00 100644
--- a/scripts/sorttable.h
+++ b/scripts/sorttable.h
@@ -110,7 +110,7 @@ static inline unsigned long orc_ip(const int *ip)
 
 static int orc_sort_cmp(const void *_a, const void *_b)
 {
-	struct orc_entry *orc_a;
+	struct orc_entry *orc_a, *orc_b;
 	const int *a = g_orc_ip_table + *(int *)_a;
 	const int *b = g_orc_ip_table + *(int *)_b;
 	unsigned long a_val = orc_ip(a);
@@ -128,6 +128,9 @@ static int orc_sort_cmp(const void *_a, const void *_b)
 	 * whitelisted .o files which didn't get objtool generation.
 	 */
 	orc_a = g_orc_table + (a - g_orc_ip_table);
+	orc_b = g_orc_table + (b - g_orc_ip_table);
+	if (orc_a->type == ORC_TYPE_UNDEFINED && orc_b->type == ORC_TYPE_UNDEFINED)
+		return 0;
 	return orc_a->type == ORC_TYPE_UNDEFINED ? -1 : 1;
 }
 
-- 
2.34.1

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

[Andrew Morton]

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?

Can we please clarify this?  Which kernel version(s) need the fix?

Or perhaps this should have been presented as two separate patches.

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

[Kuan-Wei Chiu]

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