Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932077AbZGNKQY (ORCPT ); Tue, 14 Jul 2009 06:16:24 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1754433AbZGNKQX (ORCPT ); Tue, 14 Jul 2009 06:16:23 -0400 Received: from hera.kernel.org ([140.211.167.34]:34818 "EHLO hera.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754247AbZGNKQX (ORCPT ); Tue, 14 Jul 2009 06:16:23 -0400 Subject: Re: [PATCH] dma-debug: Fix the overlap() function to be correct and readable From: Jaswinder Singh Rajput To: Ingo Molnar Cc: Linus Torvalds , Linux Kernel Mailing List , Thomas Gleixner , Peter Zijlstra , Joerg Roedel In-Reply-To: <20090710195157.GA31361@elte.hu> References: <20090710162848.GA26862@elte.hu> <20090710193110.GA28281@elte.hu> <20090710195157.GA31361@elte.hu> Content-Type: text/plain Date: Tue, 14 Jul 2009 15:45:42 +0530 Message-Id: <1247566542.2473.18.camel@ht.satnam> Mime-Version: 1.0 X-Mailer: Evolution 2.24.5 (2.24.5-2.fc10) Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 4259 Lines: 123 On Fri, 2009-07-10 at 21:51 +0200, Ingo Molnar wrote: > * Ingo Molnar 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 > 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 > Cc: Joerg Roedel > Signed-off-by: Ingo Molnar > --- > 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/