Re: [PATCH] dma-debug: Fix the overlap() function to be correct and readable

[Jaswinder Singh Rajput <jaswinder@kernel.org>]

On Fri, 2009-07-10 at 21:51 +0200, Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> > > IOW, I think this whole function is just total crap, apparently 
> > > put together by randomly assembling characters until it 
> > > compiles. Somebody should put more effort into looking at it, 
> > > but I think it should be something like
> > > 
> > > 	static inline int overlap(void *addr, unsigned long len, void *start, void *end)
> > > 	{
> > > 		unsigned long a1 = (unsigned long) addr;
> > > 		unsigned long b1 = a1 + len;
> > > 		unsigned long a2 = (unsigned long) start;
> > > 		unsigned long b2 = (unsigned long) end;
> > 
> > At least some arguments have unsigned long natural types (they come 
> > out of page_address() for example) so the function parameters could 
> > perhaps be changed to unsigned long too as well.
> > 
> > > 	#ifdef WE_CARE_DEEPLY
> > > 		/* Overflow? */
> > > 		if (b1 < a1)
> > > 			return 1;
> > > 	#ifdef AND_ARE_ANAL
> > > 		if (b2 < a2)
> > > 			return 1;
> > > 	#endif
> > > 	#endif
> > > 		return !(b1 <= a2 || a1 >= b2);
> > > 	}
> > > 
> > > but I really migth have done soemthing wrong there. It's a 
> > > simple function, but somebody needs to double-check that I 
> > > haven't made it worse.
> > 
> > Looks correct to me.
> 
> How about the patch below? Lightly tested.
> 
> 	Ingo
> 
> ------------>
> >From 35c89da82e969a2fd157478940e7ecde1e19ccc4 Mon Sep 17 00:00:00 2001
> From: Ingo Molnar <mingo@elte.hu>
> Date: Fri, 10 Jul 2009 21:38:02 +0200
> Subject: [PATCH] dma-debug: Fix the overlap() function to be correct and readable
> 
> Linus noticed how unclean and buggy the overlap() function is:
> 
>  - It uses convoluted (and bug-causing) positive checks for
>    range overlap - instead of using a more natural negative
>    check.
> 
>  - Even the positive checks are buggy: a positive intersection
>    check has four natural cases while we checked only for three,
>    missing the (addr < start && addr2 == end) case for example.
> 
>  - The variables are mis-named, making it non-obvious how the
>    check was done.
> 
>  - It needlessly uses u64 instead of unsigned long. Since these
>    are kernel memory pointers and we explicitly exclude highmem
>    ranges anyway we cannot ever overflow 32 bits, even if we
>    could. (and on 64-bit it doesnt matter anyway)
> 
> All in one, this function needs a total revamp. I used Linus's
> suggestions minus the paranoid checks (we cannot overflow really
> because if we get totally bad DMA ranges passed far more things
> break in the systems than just DMA debugging). I also fixed a
> few other small details i noticed.
> 
> Reported-by: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: Joerg Roedel <joerg.roedel@amd.com>
> Signed-off-by: Ingo Molnar <mingo@elte.hu>
> ---
>  lib/dma-debug.c |   24 ++++++++++++------------
>  1 files changed, 12 insertions(+), 12 deletions(-)
> 
> diff --git a/lib/dma-debug.c b/lib/dma-debug.c
> index c9187fe..02fed52 100644
> --- a/lib/dma-debug.c
> +++ b/lib/dma-debug.c
> @@ -856,22 +856,21 @@ static void check_for_stack(struct device *dev, void *addr)
>  				"stack [addr=%p]\n", addr);
>  }
>  
> -static inline bool overlap(void *addr, u64 size, void *start, void *end)
> +static inline bool overlap(void *addr, unsigned long len, void *start, void *end)
>  {
> -	void *addr2 = (char *)addr + size;
> +	unsigned long a1 = (unsigned long)addr;
> +	unsigned long b1 = a1 + len;
> +	unsigned long a2 = (unsigned long)start;
> +	unsigned long b2 = (unsigned long)end;
>  
> -	return ((addr >= start && addr < end) ||
> -		(addr2 >= start && addr2 < end) ||
> -		((addr < start) && (addr2 > end)));
> +	return !(b1 <= a2 || a1 >= b2);
>  }
>  

If b1 = a2 (overlap) then this function will say 0
If a1 = b2 (overlap) then this function will say 0

if b1 > (a2 + infinite) which is not overlap this function will say 1

I think we need to test both edges.

So it should be :

	return ((a2 <= b1 && b2 >= a1) || (a1 <= b2 && a2 <= b1));

Thanks,
--
JSR