linux-kernel - Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <aLCOVoshch9phL5M@visitorckw-System-Product-Name>
Date: Fri, 29 Aug 2025 01:13:58 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Harry Yoo <harry.yoo@...cle.com>
Cc: Vlastimil Babka <vbabka@...e.cz>, akpm@...ux-foundation.org,
	cl@...two.org, rientjes@...gle.com, roman.gushchin@...ux.dev,
	glittao@...il.com, jserv@...s.ncku.edu.tw, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org, stable@...r.kernel.org,
	Joshua Hahn <joshua.hahnjy@...il.com>, chuang@...nycu.edu.tw,
	cfmc.cs13@...u.edu.tw, jhcheng.cs13@...u.edu.tw,
	c.yuanhaur@...tl.edu
Subject: Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when
 counts are equal

On Tue, Aug 26, 2025 at 04:53:34PM +0900, Harry Yoo wrote:
> On Tue, Aug 26, 2025 at 01:54:49AM +0800, Kuan-Wei Chiu wrote:
> > Hi Vlastimil,
> > 
> > On Mon, Aug 25, 2025 at 07:28:17PM +0200, Vlastimil Babka wrote:
> > > On 8/25/25 03:34, Kuan-Wei Chiu wrote:
> > > > The comparison function cmp_loc_by_count() used for sorting stack trace
> > > > locations in debugfs currently returns -1 if a->count > b->count and 1
> > > > otherwise. This breaks the antisymmetry property required by sort(),
> > > > because when two counts are equal, both cmp(a, b) and cmp(b, a) return
> > > > 1.
> > > 
> > > Good catch.
> > > 
> > > > This can lead to undefined or incorrect ordering results. Fix it by
> > > 
> > > Wonder if it can really affect anything in practice other than swapping
> > > needlessly some records with an equal count?
> > > 
> > It could result in some elements being incorrectly ordered, similar to
> > what happened before in ACPI causing issues with s2idle [1][2]. But in
> > this case, the worst impact is just the display order not matching the
> > count, so it's not too critical.
> 
> Could you give an example where the previous cmp_loc_by_count() code
> produces an incorrectly sorted array?
> 
Sorry for the late reply.

I tried generating random arrays to find a concrete example where the
old cmp_loc_by_count() causes a wrong ordering, but I couldn't
reproduce one. So I would like to withdraw my earlier claim that it
definitely leads to incorrect results, since I cannot demonstrate a
failing case.

The complexity of the sort() implementation also makes it hard to
reason precisely whether such inputs exist.

That said, I still believe the patch should be merged, because sort()
only guarantees correct behavior if the comparison function satisfies
antisymmetry and transitivity. When those are violated, correctness
depends on implementation details, and future changes (e.g., switching
to a different sorting algorithm) could potentially break the ordering.

Regards,
Kuan-Wei

> > [1]: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com
> > [2]: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail.com
> > 
> > > > explicitly returning 0 when the counts are equal, ensuring that the
> > > > comparison function follows the expected mathematical properties.
> > > 
> > > Agreed with the cmp_int() suggestion for a v2.
> > > 
> > I'll make that change in v2.
> 
> -- 
> Cheers,
> Harry / Hyeonggon