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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Tue, 23 Jan 2024 11:19:44 -0800
From: Sohil Mehta <sohil.mehta@...el.com>
To: Dave Hansen <dave.hansen@...el.com>, David Binderman <dcb314@...mail.com>,
	Dave Hansen <dave.hansen@...ux.intel.com>, "linux-kernel@...r.kernel.org"
	<linux-kernel@...r.kernel.org>
CC: Andy Lutomirski <luto@...nel.org>, Peter Zijlstra <peterz@...radead.org>,
	Thomas Gleixner <tglx@...utronix.de>, Ingo Molnar <mingo@...hat.com>,
	Borislav Petkov <bp@...en8.de>, "x86@...nel.org" <x86@...nel.org>
Subject: Re: [PATCH] x86/mm: Simplify redundant overlap calculation

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