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; }
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.
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
linux-stable-mirror@lists.linaro.org
-
Andrew Morton -
Kuan-Wei Chiu