x86/mm: Simplify redundant overlap calculation
Dave Hansen
maintainerPATCH 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.
--- arch/x86/mm/pat/set_memory.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
arch/x86/mm/pat/set_memory.c +1 -2
@@ -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
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")Reported-by David Binderman <[email protected]>
Gah, that one escaped a moment too soon:
... obviously
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
---
arch/x86/mm/pat/set_memory.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
arch/x86/mm/pat/set_memory.c +0 -0
@@ -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
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 ifr1_startorr1_endare 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: 0000000000000011a0 <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: 00I 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.
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 ifr1_startorr1_endare 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 longr1_end,
unsigned longr2_start, unsigned longr2_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 longr1_end,
unsigned longr2_start, unsigned longr2_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
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")Reported-by David Binderman <[email protected]>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@@ -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