From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: [GIT PULL] core kernel fixes
Date: Fri, 10 Jul 2009 19:07:40 UTC
Message-ID: <fa.HQEgqQeVsknk2nf4x6nyPj9mkxQ@ifi.uio.no>

On Fri, 10 Jul 2009, Ingo Molnar wrote:
>
> Joerg Roedel (1):
>       dma-debug: fix off-by-one error in overlap function
>
> diff --git a/lib/dma-debug.c b/lib/dma-debug.c
> index 3b93129..c9187fe 100644
> --- a/lib/dma-debug.c
> +++ b/lib/dma-debug.c
> @@ -862,7 +862,7 @@ static inline bool overlap(void *addr, u64 size, void *start, void *end)
>
>  	return ((addr >= start && addr < end) ||
>  		(addr2 >= start && addr2 < end) ||
> -		((addr < start) && (addr2 >= end)));
> +		((addr < start) && (addr2 > end)));
>  }
>
>  static void check_for_illegal_area(struct device *dev, void *addr, u64 size)

The above seems like total shit.

If (addr < start && addr2 == end) then the two areas very much overlap.

What am I missing (apart from the fact that all those variables are
horribly badly named)?

Also, the tests make no sense. That's not how you are supposed to check
for overlap to begin with.

Isn't it easier to test for _not_ overlapping?

	/* range1 is fully before range2 */
	(end1 <= start2 ||
	/* range1 is fully after range2 */
	start1 >= end2)

possibly together with checking for overflow in the size addition? But I
didn't think that through, so maybe I'm doing something stupid.

Finally, why is 'size' a u64? It will overflow anyway if it's bigger than
a pointer, so it should be just 'unsigned long'. Or it should all be done
in u64 if people care. Or we should care about overflow (which cannot be
done with pointers).

Also, comparing pointers is unsafe to begin with. It's not clear if they
are signed or unsigned comparisons, and gcc has historically had bugs here
(only unsigned comparisons make sense for pointers, but _technically_ a
crazy compiler person could argue that at least in some environments any
valid pointers to the same object - which is the only thing C defines -
must not cross the sign barrier, so they use a buggy signed compare).

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;

	#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 might have done something wrong there. It's a simple
function, but somebody needs to double-check that I haven't made it worse.

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: [GIT PULL] core kernel fixes
Date: Fri, 10 Jul 2009 19:52:58 UTC
Message-ID: <fa.P+LoYeESMDpfqdFhM8aoO+gzRVw@ifi.uio.no>

On Fri, 10 Jul 2009, Ingo Molnar wrote:
> >
> > but I really might have done something wrong there. It's a simple
> > function, but somebody needs to double-check that I haven't made
> > it worse.
>
> Looks correct to me.

Note, I didn't look at how 'end' works, and it really does matter if 'end'
is an "inclusive" or "exclusive" end pointer address. So my replacement
overlap() function was written more as a conceptual patch - I did not
check the exact semantics of the arguments passed in.

If 'end' is exclusive, then 'b1' should be calculated as 'a1+size-1',
because the ranges must have the same rules. And then you should use the
'strict inequality' operators for testing the ranges.

		Linus