[PATCH] x86/mm: Simplify redundant overlap calculation

[PATCH] x86/mm: Simplify redundant overlap calculation

[Dave Hansen]

There have been a couple of reports that the two sides of the
overlaps() calculation are redundant.  I spent way too much time
looking at this, but I became convinced that they are redundant
when a little test program of mine produced identical disassembly
for both versions of the check.

Remove the second condition.  It is exactly the same as the first.

Fixes: 91ee8f5c1f50 ("x86/mm/cpa: Allow range check for static protections")
Reported-by: David Binderman <dcb314@hotmail.com>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: x86@kernel.org
---
 arch/x86/mm/pat/set_memory.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/x86/mm/pat/set_memory.c b/arch/x86/mm/pat/set_memory.c
index e9b448d1b1b70..fdc00516c0b54 100644
--- a/arch/x86/mm/pat/set_memory.c
+++ b/arch/x86/mm/pat/set_memory.c
@@ -435,8 +435,7 @@ static void cpa_flush(struct cpa_data *data, int cache)
 static bool overlaps(unsigned long r1_start, unsigned long r1_end,
 		     unsigned long r2_start, unsigned long r2_end)
 {
-	return (r1_start <= r2_end && r1_end >= r2_start) ||
-		(r2_start <= r1_end && r2_end >= r1_start);
+	return (r1_start <= r2_end && r1_end >= r2_start);
 }
 
 #ifdef CONFIG_PCI_BIOS
-- 
2.34.1

Re: [PATCH] x86/mm: Simplify redundant overlap calculation

[Dave Hansen]

On 1/23/24 08:36, Dave Hansen wrote:
> There have been a couple of reports that the two sides of the
> overlaps() calculation are redundant.  I spent way too much time
> looking at this, but I became convinced that they are redundant
> when a little test program of mine produced identical disassembly
> for both versions of the check.
> 
> Remove the second condition.  It is exactly the same as the first.
> 
> Fixes: 91ee8f5c1f50 ("x86/mm/cpa: Allow range check for static protections")
> Reported-by: David Binderman <dcb314@hotmail.com>

Gah, that one escaped a moment too soon:

Signed-off-by: Dave Hansen <dave.hansen@linux.intel.com>

... obviously

Re: [PATCH] x86/mm: Simplify redundant overlap calculation

[David Binderman]

Hello there,

>Remove the second condition.  It is exactly the same as the first.

I don't think the first condition is sufficient. I suspect something like

       return (r2_start <= r1_start && r1_start <= r2_end) ||
               (r2_start <= r1_end && r1_end <= r2_end);

Given the range [r2_start .. r2_end], then if r1_start or r1_end
are in that range, you have overlap.

Unless you know different.

Regards

David Binderman



Fixes: 91ee8f5c1f50 ("x86/mm/cpa: Allow range check for static protections")
Reported-by: David Binderman <dcb314@hotmail.com>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: x86@kernel.org
---
 arch/x86/mm/pat/set_memory.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/x86/mm/pat/set_memory.c b/arch/x86/mm/pat/set_memory.c
index e9b448d1b1b70..fdc00516c0b54 100644
--- a/arch/x86/mm/pat/set_memory.c
+++ b/arch/x86/mm/pat/set_memory.c
@@ -435,8 +435,7 @@ static void cpa_flush(struct cpa_data *data, int cache)
 static bool overlaps(unsigned long r1_start, unsigned long r1_end,
                      unsigned long r2_start, unsigned long r2_end)
 {
-       return (r1_start <= r2_end && r1_end >= r2_start) ||
-               (r2_start <= r1_end && r2_end >= r1_start);
+       return (r1_start <= r2_end && r1_end >= r2_start);
 }
 
 #ifdef CONFIG_PCI_BIOS
--
2.34.1

Re: [PATCH] x86/mm: Simplify redundant overlap calculation

[Dave Hansen]

On 1/23/24 08:54, David Binderman wrote:
>> Remove the second condition.  It is exactly the same as the first.
> I don't think the first condition is sufficient. I suspect something like
> 
>        return (r2_start <= r1_start && r1_start <= r2_end) ||
>                (r2_start <= r1_end && r1_end <= r2_end);
> 
> Given the range [r2_start .. r2_end], then if r1_start or r1_end
> are in that range, you have overlap.
> 
> Unless you know different.

First of all, I've gotten these bounds checks wrong in code more times
than I can count.  I have zero trust that I'll get them right. :)

But the compiler seems to know different at least:

int  overlaps1(unsigned long r1_start, unsigned long r1_end,
	      unsigned long r2_start, unsigned long r2_end)
{
	return  (r1_start <= r2_end && r1_end >= r2_start) ||
		(r2_start <= r1_end && r2_end >= r1_start);
}

int  overlaps2(unsigned long r1_start, unsigned long r1_end,
	      unsigned long r2_start, unsigned long r2_end)
{
	return (r1_start <= r2_end && r1_end >= r2_start);
}

Results in:

0000000000001180 <overlaps1>:
    1180:	f3 0f 1e fa          	endbr64
    1184:	48 39 cf             	cmp    %rcx,%rdi
    1187:	49 89 d0             	mov    %rdx,%r8
    118a:	0f 96 c2             	setbe  %dl
    118d:	31 c0                	xor    %eax,%eax
    118f:	4c 39 c6             	cmp    %r8,%rsi
    1192:	0f 93 c0             	setae  %al
    1195:	21 d0                	and    %edx,%eax
    1197:	c3                   	ret
    1198:	0f 1f 84 00 00 00 00 	nopl   0x0(%rax,%rax,1)
    119f:	00

00000000000011a0 <overlaps2>:
    11a0:	f3 0f 1e fa          	endbr64
    11a4:	48 39 cf             	cmp    %rcx,%rdi
    11a7:	49 89 d0             	mov    %rdx,%r8
    11aa:	0f 96 c2             	setbe  %dl
    11ad:	31 c0                	xor    %eax,%eax
    11af:	4c 39 c6             	cmp    %r8,%rsi
    11b2:	0f 93 c0             	setae  %al
    11b5:	21 d0                	and    %edx,%eax
    11b7:	c3                   	ret
    11b8:	0f 1f 84 00 00 00 00 	nopl   0x0(%rax,%rax,1)
    11bf:	00

I also wrote a quick program to throw random numbers into both versions
and see if they differ.  They never did, which they obviously can't if
they're the exact same instructions.

Re: [PATCH] x86/mm: Simplify redundant overlap calculation

[Sohil Mehta]

On 1/23/2024 9:00 AM, Dave Hansen wrote:
> On 1/23/24 08:54, David Binderman wrote:
>>> Remove the second condition.  It is exactly the same as the first.
>> I don't think the first condition is sufficient. I suspect something like
>>
>>        return (r2_start <= r1_start && r1_start <= r2_end) ||
>>                (r2_start <= r1_end && r1_end <= r2_end);
>>

This check seems accurate however Dave's single line check below also
looks accurate to me. See the analysis below.

>> Given the range [r2_start .. r2_end], then if r1_start or r1_end
>> are in that range, you have overlap.
>>
>> Unless you know different.
> 
> First of all, I've gotten these bounds checks wrong in code more times
> than I can count.  I have zero trust that I'll get them right. :)
> 
> But the compiler seems to know different at least:
> 
> int  overlaps1(unsigned long r1_start, unsigned long r1_end,
> 	      unsigned long r2_start, unsigned long r2_end)
> {
> 	return  (r1_start <= r2_end && r1_end >= r2_start) ||
> 		(r2_start <= r1_end && r2_end >= r1_start);
> }

Dave, I think if you change the order of the && in the 2nd check it
makes it easier to visually realize that both of these checks are indeed
the same:

(r1_start <= r2_end  )	&& (r1_end   >= r2_start)
			||
(r2_end   >= r1_start)	&& (r2_start <= r1_end  )

The first operation in () on both lines is exactly the same. Same is
true for the second operation after the &&.

> 
> int  overlaps2(unsigned long r1_start, unsigned long r1_end,
> 	      unsigned long r2_start, unsigned long r2_end)
> {
> 	return (r1_start <= r2_end && r1_end >= r2_start);
> }
> 

I completely agree that overlap1() and overlap2() are expected to
generate the same output for any input.

However, the next question is whether overlap2() is enough to detect
there is indeed an overlap between the ranges. I find that would be true
based on the assumption that the end is always greater than or equal to
the start in both ranges.

I have now spent way too much time on this. But if you rearrange the
check in overlaps2() as below then I find it easier to put it in words:

(r1_start <= r2_end && r2_start <= r1_end)

"Both of the ranges have to start before either of ranges end for there
to be an overlap".

Sohil

Re: [PATCH] x86/mm: Simplify redundant overlap calculation

[Sohil Mehta]

On 1/23/2024 8:36 AM, Dave Hansen wrote:
> There have been a couple of reports that the two sides of the
> overlaps() calculation are redundant.  I spent way too much time
> looking at this, but I became convinced that they are redundant
> when a little test program of mine produced identical disassembly
> for both versions of the check.
> 
> Remove the second condition.  It is exactly the same as the first.
> 
> Fixes: 91ee8f5c1f50 ("x86/mm/cpa: Allow range check for static protections")
> Reported-by: David Binderman <dcb314@hotmail.com>
> Cc: Andy Lutomirski <luto@kernel.org>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Borislav Petkov <bp@alien8.de>
> Cc: x86@kernel.org
> ---
>  arch/x86/mm/pat/set_memory.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 

Reviewed-by: Sohil Mehta <sohil.mehta@intel.com>

> diff --git a/arch/x86/mm/pat/set_memory.c b/arch/x86/mm/pat/set_memory.c
> index e9b448d1b1b70..fdc00516c0b54 100644
> --- a/arch/x86/mm/pat/set_memory.c
> +++ b/arch/x86/mm/pat/set_memory.c
> @@ -435,8 +435,7 @@ static void cpa_flush(struct cpa_data *data, int cache)
>  static bool overlaps(unsigned long r1_start, unsigned long r1_end,
>  		     unsigned long r2_start, unsigned long r2_end)
>  {
> -	return (r1_start <= r2_end && r1_end >= r2_start) ||
> -		(r2_start <= r1_end && r2_end >= r1_start);
> +	return (r1_start <= r2_end && r1_end >= r2_start);
>  }
>  
>  #ifdef CONFIG_PCI_BIOS