[PATCH v2] perf bench: Fix undefined behavior in cmpworker()

[PATCH v2] perf bench: Fix undefined behavior in cmpworker()

[Kuan-Wei Chiu]

The comparison function cmpworker() violates the C standard's
requirements for qsort() comparison functions, which mandate symmetry
and transitivity:

Symmetry: If x < y, then y > x.
Transitivity: If x < y and y < z, then x < z.

In its current implementation, cmpworker() incorrectly returns 0 when
w1->tid < w2->tid, which breaks both symmetry and transitivity. This
violation causes undefined behavior, potentially leading to issues such
as memory corruption in glibc [1].

Fix the issue by returning -1 when w1->tid < w2->tid, ensuring
compliance with the C standard and preventing undefined behavior.

Link: https://www.qualys.com/2024/01/30/qsort.txt [1]
Fixes: 121dd9ea0116 ("perf bench: Add epoll parallel epoll_wait benchmark")
Cc: stable@vger.kernel.org
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Changes in v2:
- Rewrite commit message

 tools/perf/bench/epoll-wait.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/perf/bench/epoll-wait.c b/tools/perf/bench/epoll-wait.c
index ef5c4257844d..4868d610e9bf 100644
--- a/tools/perf/bench/epoll-wait.c
+++ b/tools/perf/bench/epoll-wait.c
@@ -420,7 +420,7 @@ static int cmpworker(const void *p1, const void *p2)
 
 	struct worker *w1 = (struct worker *) p1;
 	struct worker *w2 = (struct worker *) p2;
-	return w1->tid > w2->tid;
+	return w1->tid > w2->tid ? 1 : -1;
 }
 
 int bench_epoll_wait(int argc, const char **argv)
-- 
2.34.1

Re: [PATCH v2] perf bench: Fix undefined behavior in cmpworker()

[James Clark]

On 07/01/2025 7:39 am, Kuan-Wei Chiu wrote:
> The comparison function cmpworker() violates the C standard's
> requirements for qsort() comparison functions, which mandate symmetry
> and transitivity:
> 
> Symmetry: If x < y, then y > x.
> Transitivity: If x < y and y < z, then x < z.
> 
> In its current implementation, cmpworker() incorrectly returns 0 when
> w1->tid < w2->tid, which breaks both symmetry and transitivity. This
> violation causes undefined behavior, potentially leading to issues such
> as memory corruption in glibc [1].
> 
> Fix the issue by returning -1 when w1->tid < w2->tid, ensuring
> compliance with the C standard and preventing undefined behavior.
> 
> Link: https://www.qualys.com/2024/01/30/qsort.txt [1]
> Fixes: 121dd9ea0116 ("perf bench: Add epoll parallel epoll_wait benchmark")
> Cc: stable@vger.kernel.org
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> Changes in v2:
> - Rewrite commit message
> 
>   tools/perf/bench/epoll-wait.c | 2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/tools/perf/bench/epoll-wait.c b/tools/perf/bench/epoll-wait.c
> index ef5c4257844d..4868d610e9bf 100644
> --- a/tools/perf/bench/epoll-wait.c
> +++ b/tools/perf/bench/epoll-wait.c
> @@ -420,7 +420,7 @@ static int cmpworker(const void *p1, const void *p2)
>   
>   	struct worker *w1 = (struct worker *) p1;
>   	struct worker *w2 = (struct worker *) p2;
> -	return w1->tid > w2->tid;
> +	return w1->tid > w2->tid ? 1 : -1;

I suppose you can skip the 0 for equality because you know that no two 
tids are the same?

Anyone looking at this in the future might still think it's still wrong 
unless it does the full comparison. Even if it's not technically 
required I would write it like a "normal" one now that we're here:

   if (w1->tid > w2->tid) return 1;
   if (w1->tid < w2->tid) return -1;
   return 0;

Re: [PATCH v2] perf bench: Fix undefined behavior in cmpworker()

[Kuan-Wei Chiu]

On Thu, Jan 16, 2025 at 10:40:45AM +0000, James Clark wrote:
> 
> 
> On 07/01/2025 7:39 am, Kuan-Wei Chiu wrote:
> > The comparison function cmpworker() violates the C standard's
> > requirements for qsort() comparison functions, which mandate symmetry
> > and transitivity:
> > 
> > Symmetry: If x < y, then y > x.
> > Transitivity: If x < y and y < z, then x < z.
> > 
> > In its current implementation, cmpworker() incorrectly returns 0 when
> > w1->tid < w2->tid, which breaks both symmetry and transitivity. This
> > violation causes undefined behavior, potentially leading to issues such
> > as memory corruption in glibc [1].
> > 
> > Fix the issue by returning -1 when w1->tid < w2->tid, ensuring
> > compliance with the C standard and preventing undefined behavior.
> > 
> > Link: https://www.qualys.com/2024/01/30/qsort.txt [1]
> > Fixes: 121dd9ea0116 ("perf bench: Add epoll parallel epoll_wait benchmark")
> > Cc: stable@vger.kernel.org
> > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> > ---
> > Changes in v2:
> > - Rewrite commit message
> > 
> >   tools/perf/bench/epoll-wait.c | 2 +-
> >   1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/tools/perf/bench/epoll-wait.c b/tools/perf/bench/epoll-wait.c
> > index ef5c4257844d..4868d610e9bf 100644
> > --- a/tools/perf/bench/epoll-wait.c
> > +++ b/tools/perf/bench/epoll-wait.c
> > @@ -420,7 +420,7 @@ static int cmpworker(const void *p1, const void *p2)
> >   	struct worker *w1 = (struct worker *) p1;
> >   	struct worker *w2 = (struct worker *) p2;
> > -	return w1->tid > w2->tid;
> > +	return w1->tid > w2->tid ? 1 : -1;
> 
> I suppose you can skip the 0 for equality because you know that no two tids
> are the same?
>
Yes, exactly.

> Anyone looking at this in the future might still think it's still wrong
> unless it does the full comparison. Even if it's not technically required I
> would write it like a "normal" one now that we're here:
> 
>   if (w1->tid > w2->tid) return 1;
>   if (w1->tid < w2->tid) return -1;
>   return 0;
> 
Sure. I'll make that change in v3.

Regards,
Kuan-Wei