Skip to contentSkip to conversation

x86/mm: Simplify redundant overlap calculation

PATCH In review Dave Hansen 4 participants 6 messages Jan 23, 2024

Subsystems (2)
lore
Share & tools
lore

Dave Hansen

author maintainer
#0 lore raw

PATCH 1/1 x86/mm: Simplify redundant overlap calculation

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")
Cc Andy Lutomirski <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
---
 arch/x86/mm/pat/set_memory.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
arch/x86/mm/pat/set_memory.c +1 -2
index e9b448d1b1b70..fdc00516c0b54 100644
@@ -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
Signature · 1 line
2.34.1
#1 lore raw
Quoted 10 lines · 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")

Gah, that one escaped a moment too soon:

... obviously

#2 lore raw
In reply to Dave Hansen

Hello there,

Quoted 1 line

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")
Cc Andy Lutomirski <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>

---
 arch/x86/mm/pat/set_memory.c | 3 +--

 1 file changed, 1 insertion(+), 2 deletions(-)
arch/x86/mm/pat/set_memory.c +0 -0
index e9b448d1b1b70..fdc00516c0b54 100644
@@ -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

#3 lore raw
Quoted 10 lines · David Binderman
Quoted 1 line

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.

#4 lore raw
Quoted 7 lines · Dave Hansen
Quoted 6 lines · David Binderman
Quoted 1 line

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.

Quoted 8 lines
Quoted 4 lines

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. :)

Quoted 8 lines

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 &&.

Quoted 7 lines

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

Reviewed-by on v1 1/1
#5 lore raw
In reply to Dave Hansen
Quoted 16 lines · 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")
Cc Andy Lutomirski <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Quoted 4 lines
---
 arch/x86/mm/pat/set_memory.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
Quoted 14 lines
arch/x86/mm/pat/set_memory.c +1 -2
index e9b448d1b1b70..fdc00516c0b54 100644
@@ -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