* [PATCH 0/2] mm/slub: Fix debugfs stack trace sorting and simplify sort call @ 2025-08-25 1:34 Kuan-Wei Chiu 2025-08-25 1:34 ` [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal Kuan-Wei Chiu 2025-08-25 1:34 ` [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting Kuan-Wei Chiu 0 siblings, 2 replies; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-25 1:34 UTC (permalink / raw) To: vbabka, akpm Cc: cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, Kuan-Wei Chiu Fix the comparison function used for sorting stack trace locations in the slub debugfs interface. The original implementation violated the antisymmetry property required by sort(), which could lead to unreliable ordering of the output. The patches correct the comparison function to return 0 when counts are equal and replace the unnecessary use of sort_r() with the simpler sort(). Kuan-Wei Chiu (2): mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting mm/slub.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) -- 2.34.1 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 1:34 [PATCH 0/2] mm/slub: Fix debugfs stack trace sorting and simplify sort call Kuan-Wei Chiu @ 2025-08-25 1:34 ` Kuan-Wei Chiu 2025-08-25 14:48 ` Joshua Hahn 2025-08-25 17:28 ` Vlastimil Babka 2025-08-25 1:34 ` [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting Kuan-Wei Chiu 1 sibling, 2 replies; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-25 1:34 UTC (permalink / raw) To: vbabka, akpm Cc: cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, Kuan-Wei Chiu, stable 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. This can lead to undefined or incorrect ordering results. Fix it by explicitly returning 0 when the counts are equal, ensuring that the comparison function follows the expected mathematical properties. Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") Cc: stable@vger.kernel.org Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- mm/slub.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/mm/slub.c b/mm/slub.c index 30003763d224..c91b3744adbc 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) if (loc1->count > loc2->count) return -1; - else + if (loc1->count < loc2->count) return 1; + return 0; } static void *slab_debugfs_start(struct seq_file *seq, loff_t *ppos) -- 2.34.1 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 1:34 ` [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal Kuan-Wei Chiu @ 2025-08-25 14:48 ` Joshua Hahn 2025-08-25 16:18 ` Kuan-Wei Chiu 2025-08-25 17:28 ` Vlastimil Babka 1 sibling, 1 reply; 12+ messages in thread From: Joshua Hahn @ 2025-08-25 14:48 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: vbabka, akpm, cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, stable On Mon, 25 Aug 2025 09:34:18 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> 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. > > This can lead to undefined or incorrect ordering results. Fix it by > explicitly returning 0 when the counts are equal, ensuring that the > comparison function follows the expected mathematical properties. > > Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") > Cc: stable@vger.kernel.org > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > --- > mm/slub.c | 3 ++- > 1 file changed, 2 insertions(+), 1 deletion(-) > > diff --git a/mm/slub.c b/mm/slub.c > index 30003763d224..c91b3744adbc 100644 > --- a/mm/slub.c > +++ b/mm/slub.c > @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) > > if (loc1->count > loc2->count) > return -1; > - else > + if (loc1->count < loc2->count) > return 1; > + return 0; > } Hello Kuan-Wei, This is a great catch! I was thinking that in addition to separating out the == case, we can also simplify the behavior by just opting to use the cmp_int macro, which is defined in the <linux/sort.h> header, which is already included in mm/slub.c. For the description, we have: * Return: 1 if the left argument is greater than the right one; 0 if the * arguments are equal; -1 if the left argument is less than the right one. So in this case, we can replace the entire code block above with: return cmp_int(loc2->count, loc1->count); or return -1 * cmp_int(loc1->count, loc2->count); if you prefer to keep the position of loc1 and loc2. I guess we do lose some interpretability of what -1 and 1 would refer to here, but I think a comment should be able to take care of that. Please let me know what you think. I hope you have a great day! Joshua ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 14:48 ` Joshua Hahn @ 2025-08-25 16:18 ` Kuan-Wei Chiu 2025-08-25 17:12 ` Joshua Hahn 0 siblings, 1 reply; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-25 16:18 UTC (permalink / raw) To: Joshua Hahn Cc: vbabka, akpm, cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, stable Hi Joshua, On Mon, Aug 25, 2025 at 07:48:36AM -0700, Joshua Hahn wrote: > On Mon, 25 Aug 2025 09:34:18 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> 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. > > > > This can lead to undefined or incorrect ordering results. Fix it by > > explicitly returning 0 when the counts are equal, ensuring that the > > comparison function follows the expected mathematical properties. > > > > Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") > > Cc: stable@vger.kernel.org > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > > --- > > mm/slub.c | 3 ++- > > 1 file changed, 2 insertions(+), 1 deletion(-) > > > > diff --git a/mm/slub.c b/mm/slub.c > > index 30003763d224..c91b3744adbc 100644 > > --- a/mm/slub.c > > +++ b/mm/slub.c > > @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) > > > > if (loc1->count > loc2->count) > > return -1; > > - else > > + if (loc1->count < loc2->count) > > return 1; > > + return 0; > > } > > Hello Kuan-Wei, > > This is a great catch! I was thinking that in addition to separating out the > == case, we can also simplify the behavior by just opting to use the > cmp_int macro, which is defined in the <linux/sort.h> header, which is > already included in mm/slub.c. For the description, we have: > > * Return: 1 if the left argument is greater than the right one; 0 if the > * arguments are equal; -1 if the left argument is less than the right one. > > So in this case, we can replace the entire code block above with: > > return cmp_int(loc2->count, loc1->count); > > or > > return -1 * cmp_int(loc1->count, loc2->count); > > if you prefer to keep the position of loc1 and loc2. I guess we do lose > some interpretability of what -1 and 1 would refer to here, but I think > a comment should be able to take care of that. > > Please let me know what you think. I hope you have a great day! > Joshua Thanks for the suggestion! If we're going with the cmp_int() macro, I personally prefer return cmp_int(loc2->count, loc1->count); this avoids the need to explain the extra * (-1), and I think cmp_int() is simple enough to be easily understood by readers. That said, both options work fine for me. Regards, Kuan-Wei ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 16:18 ` Kuan-Wei Chiu @ 2025-08-25 17:12 ` Joshua Hahn 0 siblings, 0 replies; 12+ messages in thread From: Joshua Hahn @ 2025-08-25 17:12 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: vbabka, akpm, cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, stable On Tue, 26 Aug 2025 00:18:42 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> wrote: > Hi Joshua, > > On Mon, Aug 25, 2025 at 07:48:36AM -0700, Joshua Hahn wrote: > > On Mon, 25 Aug 2025 09:34:18 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> 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. > > > > > > This can lead to undefined or incorrect ordering results. Fix it by > > > explicitly returning 0 when the counts are equal, ensuring that the > > > comparison function follows the expected mathematical properties. > > > > > > Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") > > > Cc: stable@vger.kernel.org > > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > > > --- > > > mm/slub.c | 3 ++- > > > 1 file changed, 2 insertions(+), 1 deletion(-) > > > > > > diff --git a/mm/slub.c b/mm/slub.c > > > index 30003763d224..c91b3744adbc 100644 > > > --- a/mm/slub.c > > > +++ b/mm/slub.c > > > @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) > > > > > > if (loc1->count > loc2->count) > > > return -1; > > > - else > > > + if (loc1->count < loc2->count) > > > return 1; > > > + return 0; > > > } > > > > Hello Kuan-Wei, > > > > This is a great catch! I was thinking that in addition to separating out the > > == case, we can also simplify the behavior by just opting to use the > > cmp_int macro, which is defined in the <linux/sort.h> header, which is > > already included in mm/slub.c. For the description, we have: > > > > * Return: 1 if the left argument is greater than the right one; 0 if the > > * arguments are equal; -1 if the left argument is less than the right one. > > > > So in this case, we can replace the entire code block above with: > > > > return cmp_int(loc2->count, loc1->count); > > > > or > > > > return -1 * cmp_int(loc1->count, loc2->count); > > > > if you prefer to keep the position of loc1 and loc2. I guess we do lose > > some interpretability of what -1 and 1 would refer to here, but I think > > a comment should be able to take care of that. > > > > Please let me know what you think. I hope you have a great day! > > Joshua > > Thanks for the suggestion! > If we're going with the cmp_int() macro, I personally prefer > return cmp_int(loc2->count, loc1->count); Makes sense with me, please feel free to add my reviewed-by tag as well! Have a great day! Joshua Reviewed-by: Joshua Hahn <joshua.hahnjy@gmail.com> ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 1:34 ` [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal Kuan-Wei Chiu 2025-08-25 14:48 ` Joshua Hahn @ 2025-08-25 17:28 ` Vlastimil Babka 2025-08-25 17:54 ` Kuan-Wei Chiu 1 sibling, 1 reply; 12+ messages in thread From: Vlastimil Babka @ 2025-08-25 17:28 UTC (permalink / raw) To: Kuan-Wei Chiu, akpm Cc: cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, stable, Joshua Hahn 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? > 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. > Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") > Cc: stable@vger.kernel.org I don't think it can cause any serious bugs so Cc: stable is unnecessary. > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> Thanks! > --- > mm/slub.c | 3 ++- > 1 file changed, 2 insertions(+), 1 deletion(-) > > diff --git a/mm/slub.c b/mm/slub.c > index 30003763d224..c91b3744adbc 100644 > --- a/mm/slub.c > +++ b/mm/slub.c > @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) > > if (loc1->count > loc2->count) > return -1; > - else > + if (loc1->count < loc2->count) > return 1; > + return 0; > } > > static void *slab_debugfs_start(struct seq_file *seq, loff_t *ppos) ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 17:28 ` Vlastimil Babka @ 2025-08-25 17:54 ` Kuan-Wei Chiu 2025-08-26 7:53 ` Harry Yoo 0 siblings, 1 reply; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-25 17:54 UTC (permalink / raw) To: Vlastimil Babka Cc: akpm, cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, stable, Joshua Hahn 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. [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. > > Fixes: 553c0369b3e1 ("mm/slub: sort debugfs output by frequency of stack traces") > > Cc: stable@vger.kernel.org > > I don't think it can cause any serious bugs so Cc: stable is unnecessary. > I'll drop it in v2. Regards, Kuan-Wei > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > > Thanks! > > > --- > > mm/slub.c | 3 ++- > > 1 file changed, 2 insertions(+), 1 deletion(-) > > > > diff --git a/mm/slub.c b/mm/slub.c > > index 30003763d224..c91b3744adbc 100644 > > --- a/mm/slub.c > > +++ b/mm/slub.c > > @@ -7718,8 +7718,9 @@ static int cmp_loc_by_count(const void *a, const void *b, const void *data) > > > > if (loc1->count > loc2->count) > > return -1; > > - else > > + if (loc1->count < loc2->count) > > return 1; > > + return 0; > > } > > > > static void *slab_debugfs_start(struct seq_file *seq, loff_t *ppos) > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-25 17:54 ` Kuan-Wei Chiu @ 2025-08-26 7:53 ` Harry Yoo 2025-08-28 17:13 ` Kuan-Wei Chiu 0 siblings, 1 reply; 12+ messages in thread From: Harry Yoo @ 2025-08-26 7:53 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: Vlastimil Babka, akpm, cl, rientjes, roman.gushchin, glittao, jserv, linux-mm, linux-kernel, stable, Joshua Hahn 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? > [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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-26 7:53 ` Harry Yoo @ 2025-08-28 17:13 ` Kuan-Wei Chiu 2025-08-29 2:06 ` Harry Yoo 0 siblings, 1 reply; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-28 17:13 UTC (permalink / raw) To: Harry Yoo Cc: Vlastimil Babka, akpm, cl, rientjes, roman.gushchin, glittao, jserv, linux-mm, linux-kernel, stable, Joshua Hahn, chuang, cfmc.cs13, jhcheng.cs13, c.yuanhaur 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal 2025-08-28 17:13 ` Kuan-Wei Chiu @ 2025-08-29 2:06 ` Harry Yoo 0 siblings, 0 replies; 12+ messages in thread From: Harry Yoo @ 2025-08-29 2:06 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: Vlastimil Babka, akpm, cl, rientjes, roman.gushchin, glittao, jserv, linux-mm, linux-kernel, stable, Joshua Hahn, chuang, cfmc.cs13, jhcheng.cs13, c.yuanhaur On Fri, Aug 29, 2025 at 01:13:58AM +0800, Kuan-Wei Chiu wrote: > 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. No problem ;) > 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. Yeah I couldn't either. Maybe mathematical proof would work, but I didn't try. > 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. Agreed. No doubt the series is worth merging, just wanted to clarify that bit. Thanks! -- Cheers, Harry / Hyeonggon > 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting 2025-08-25 1:34 [PATCH 0/2] mm/slub: Fix debugfs stack trace sorting and simplify sort call Kuan-Wei Chiu 2025-08-25 1:34 ` [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal Kuan-Wei Chiu @ 2025-08-25 1:34 ` Kuan-Wei Chiu 2025-08-25 17:31 ` Vlastimil Babka 1 sibling, 1 reply; 12+ messages in thread From: Kuan-Wei Chiu @ 2025-08-25 1:34 UTC (permalink / raw) To: vbabka, akpm Cc: cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel, Kuan-Wei Chiu The comparison function used to sort stack trace locations in debugfs never relied on the third argument. Therefore, sort_r() is unnecessary. Switch to sort() with a two-argument comparison function to keep the code simple and aligned with the intended usage. Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- mm/slub.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/mm/slub.c b/mm/slub.c index c91b3744adbc..67b68f132f84 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -7711,7 +7711,7 @@ static void *slab_debugfs_next(struct seq_file *seq, void *v, loff_t *ppos) return NULL; } -static int cmp_loc_by_count(const void *a, const void *b, const void *data) +static int cmp_loc_by_count(const void *a, const void *b) { struct location *loc1 = (struct location *)a; struct location *loc2 = (struct location *)b; @@ -7782,8 +7782,8 @@ static int slab_debug_trace_open(struct inode *inode, struct file *filep) } /* Sort locations by count */ - sort_r(t->loc, t->count, sizeof(struct location), - cmp_loc_by_count, NULL, NULL); + sort(t->loc, t->count, sizeof(struct location), + cmp_loc_by_count, NULL); bitmap_free(obj_map); return 0; -- 2.34.1 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting 2025-08-25 1:34 ` [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting Kuan-Wei Chiu @ 2025-08-25 17:31 ` Vlastimil Babka 0 siblings, 0 replies; 12+ messages in thread From: Vlastimil Babka @ 2025-08-25 17:31 UTC (permalink / raw) To: Kuan-Wei Chiu, akpm Cc: cl, rientjes, roman.gushchin, harry.yoo, glittao, jserv, linux-mm, linux-kernel On 8/25/25 03:34, Kuan-Wei Chiu wrote: > The comparison function used to sort stack trace locations in debugfs > never relied on the third argument. Therefore, sort_r() is unnecessary. > Switch to sort() with a two-argument comparison function to keep the > code simple and aligned with the intended usage. > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> LGTM. > --- > mm/slub.c | 6 +++--- > 1 file changed, 3 insertions(+), 3 deletions(-) > > diff --git a/mm/slub.c b/mm/slub.c > index c91b3744adbc..67b68f132f84 100644 > --- a/mm/slub.c > +++ b/mm/slub.c > @@ -7711,7 +7711,7 @@ static void *slab_debugfs_next(struct seq_file *seq, void *v, loff_t *ppos) > return NULL; > } > > -static int cmp_loc_by_count(const void *a, const void *b, const void *data) > +static int cmp_loc_by_count(const void *a, const void *b) > { > struct location *loc1 = (struct location *)a; > struct location *loc2 = (struct location *)b; > @@ -7782,8 +7782,8 @@ static int slab_debug_trace_open(struct inode *inode, struct file *filep) > } > > /* Sort locations by count */ > - sort_r(t->loc, t->count, sizeof(struct location), > - cmp_loc_by_count, NULL, NULL); > + sort(t->loc, t->count, sizeof(struct location), > + cmp_loc_by_count, NULL); > > bitmap_free(obj_map); > return 0; ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2025-08-29 2:06 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2025-08-25 1:34 [PATCH 0/2] mm/slub: Fix debugfs stack trace sorting and simplify sort call Kuan-Wei Chiu 2025-08-25 1:34 ` [PATCH 1/2] mm/slub: Fix cmp_loc_by_count() to return 0 when counts are equal Kuan-Wei Chiu 2025-08-25 14:48 ` Joshua Hahn 2025-08-25 16:18 ` Kuan-Wei Chiu 2025-08-25 17:12 ` Joshua Hahn 2025-08-25 17:28 ` Vlastimil Babka 2025-08-25 17:54 ` Kuan-Wei Chiu 2025-08-26 7:53 ` Harry Yoo 2025-08-28 17:13 ` Kuan-Wei Chiu 2025-08-29 2:06 ` Harry Yoo 2025-08-25 1:34 ` [PATCH 2/2] mm/slub: Replace sort_r() with sort() for debugfs stack trace sorting Kuan-Wei Chiu 2025-08-25 17:31 ` Vlastimil Babka
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox