+ expose-range-checking-functions-from-arch-specific.patch added to -mm tree

+ expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[akpm]

The patch titled
     Expose range-checking functions from arch-specific uaccess.h
has been added to the -mm tree.  Its filename is
     expose-range-checking-functions-from-arch-specific.patch

*** Remember to use Documentation/SubmitChecklist when testing your code ***

See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find
out what to do about this

------------------------------------------------------
Subject: Expose range-checking functions from arch-specific uaccess.h
From: Rusty Russell <rusty@rustcorp.com.au>

There are some places where we want to check if a value + length is within
a range.  This can be tricky, so it's nice to have a single routine.

Also, this can be done more efficiently (with arch-dependent) carry bits,
as shown by the __range_ok() implementation on several archs.

This patch exposes arch-specific "val_outside(val, len, limit)" and a
generic "range_within(start, len, base, limit)" function.  As a
side-effect, it fixes the comment in i386/uaccess.h: __range_ok doesn't
test "(u33)addr + (u33)size >= (u33)current->addr_limit.seg", it tests
"(u33)addr + (u33)size > (u33)current->addr_limit.seg".

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Cc: <linux-arch@vger.kernel.org>
Cc: Randy Dunlap <randy.dunlap@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/asm-alpha/range.h     |    6 ++++++
 include/asm-arm/range.h       |    6 ++++++
 include/asm-arm26/range.h     |    6 ++++++
 include/asm-avr32/range.h     |    6 ++++++
 include/asm-blackfin/range.h  |    6 ++++++
 include/asm-cris/range.h      |    6 ++++++
 include/asm-frv/range.h       |    6 ++++++
 include/asm-generic/range.h   |   20 ++++++++++++++++++++
 include/asm-h8300/range.h     |    6 ++++++
 include/asm-i386/range.h      |   14 ++++++++++++++
 include/asm-i386/uaccess.h    |   16 ++++++----------
 include/asm-ia64/range.h      |    6 ++++++
 include/asm-m32r/range.h      |    6 ++++++
 include/asm-m68k/range.h      |    6 ++++++
 include/asm-m68knommu/range.h |    6 ++++++
 include/asm-mips/range.h      |    6 ++++++
 include/asm-parisc/range.h    |    6 ++++++
 include/asm-powerpc/range.h   |    6 ++++++
 include/asm-ppc/range.h       |    6 ++++++
 include/asm-s390/range.h      |    6 ++++++
 include/asm-sh/range.h        |    6 ++++++
 include/asm-sh64/range.h      |    6 ++++++
 include/asm-sparc/range.h     |    6 ++++++
 include/asm-sparc64/range.h   |    6 ++++++
 include/asm-um/range.h        |    6 ++++++
 include/asm-v850/range.h      |    6 ++++++
 include/asm-x86_64/range.h    |    6 ++++++
 include/asm-xtensa/range.h    |    6 ++++++
 include/linux/kernel.h        |   21 +++++++++++++++++++++
 29 files changed, 211 insertions(+), 10 deletions(-)

diff -puN /dev/null include/asm-alpha/range.h
--- /dev/null
+++ a/include/asm-alpha/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-arm/range.h
--- /dev/null
+++ a/include/asm-arm/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-arm26/range.h
--- /dev/null
+++ a/include/asm-arm26/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-avr32/range.h
--- /dev/null
+++ a/include/asm-avr32/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-blackfin/range.h
--- /dev/null
+++ a/include/asm-blackfin/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-cris/range.h
--- /dev/null
+++ a/include/asm-cris/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-frv/range.h
--- /dev/null
+++ a/include/asm-frv/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-generic/range.h
--- /dev/null
+++ a/include/asm-generic/range.h
@@ -0,0 +1,20 @@
+#ifndef _ASM_GENERIC_RANGE_H
+#define _ASM_GENERIC_RANGE_H
+
+/**
+ * val_outside - is a value and length past a limit?
+ * @val: the start value
+ * @len: the length from the start
+ * @limit: the first invalid value
+ *
+ * Like val + len > limit, except with overflow checking.
+ */
+static inline bool val_outside(unsigned long val, unsigned long len,
+			       unsigned long limit)
+
+{
+	return val + len > limit || val + len < val;
+}
+
+#endif	/* _ASM_GENERIC_RANGE_H */
+
diff -puN /dev/null include/asm-h8300/range.h
--- /dev/null
+++ a/include/asm-h8300/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-i386/range.h
--- /dev/null
+++ a/include/asm-i386/range.h
@@ -0,0 +1,14 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+/* Is val + size > limit? This needs 33-bit arithmetic. We have a carry... */
+static inline bool val_outside(unsigned long val, unsigned long len,
+			       unsigned long limit)
+{
+	unsigned long flag, roksum;
+	asm("addl %3,%1 ; sbbl %0,%0; cmpl %1,%4; sbbl $0,%0"
+		:"=&r" (flag), "=r" (roksum)
+		:"1" (val), "g" (len), "rm" (limit));
+	return flag;
+}
+#endif	/* __ASM_RANGE_H */
diff -puN include/asm-i386/uaccess.h~expose-range-checking-functions-from-arch-specific include/asm-i386/uaccess.h
--- a/include/asm-i386/uaccess.h~expose-range-checking-functions-from-arch-specific
+++ a/include/asm-i386/uaccess.h
@@ -49,17 +49,13 @@ extern struct movsl_mask {
  * Returns 0 if the range is valid, nonzero otherwise.
  *
  * This is equivalent to the following test:
- * (u33)addr + (u33)size >= (u33)current->addr_limit.seg
- *
- * This needs 33-bit arithmetic. We have a carry...
+ * (u33)addr + (u33)size > (u33)current->addr_limit.seg
  */
-#define __range_ok(addr,size) ({ \
-	unsigned long flag,roksum; \
-	__chk_user_ptr(addr); \
-	asm("addl %3,%1 ; sbbl %0,%0; cmpl %1,%4; sbbl $0,%0" \
-		:"=&r" (flag), "=r" (roksum) \
-		:"1" (addr),"g" ((int)(size)),"rm" (current_thread_info()->addr_limit.seg)); \
-	flag; })
+#define __range_ok(addr, size) ({				\
+	__chk_user_ptr(addr);					\
+	val_outside((int)(addr), (size),			\
+		    current_thread_info()->addr_limit.seg);	\
+})
 
 /**
  * access_ok: - Checks if a user space pointer is valid
diff -puN /dev/null include/asm-ia64/range.h
--- /dev/null
+++ a/include/asm-ia64/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-m32r/range.h
--- /dev/null
+++ a/include/asm-m32r/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-m68k/range.h
--- /dev/null
+++ a/include/asm-m68k/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-m68knommu/range.h
--- /dev/null
+++ a/include/asm-m68knommu/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-mips/range.h
--- /dev/null
+++ a/include/asm-mips/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-parisc/range.h
--- /dev/null
+++ a/include/asm-parisc/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-powerpc/range.h
--- /dev/null
+++ a/include/asm-powerpc/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-ppc/range.h
--- /dev/null
+++ a/include/asm-ppc/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-s390/range.h
--- /dev/null
+++ a/include/asm-s390/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-sh/range.h
--- /dev/null
+++ a/include/asm-sh/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-sh64/range.h
--- /dev/null
+++ a/include/asm-sh64/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-sparc/range.h
--- /dev/null
+++ a/include/asm-sparc/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-sparc64/range.h
--- /dev/null
+++ a/include/asm-sparc64/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-um/range.h
--- /dev/null
+++ a/include/asm-um/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-v850/range.h
--- /dev/null
+++ a/include/asm-v850/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-x86_64/range.h
--- /dev/null
+++ a/include/asm-x86_64/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN /dev/null include/asm-xtensa/range.h
--- /dev/null
+++ a/include/asm-xtensa/range.h
@@ -0,0 +1,6 @@
+#ifndef __ASM_RANGE_H
+#define __ASM_RANGE_H
+
+#include <asm-generic/range.h>
+
+#endif /* __ASM_RANGE_H */
diff -puN include/linux/kernel.h~expose-range-checking-functions-from-arch-specific include/linux/kernel.h
--- a/include/linux/kernel.h~expose-range-checking-functions-from-arch-specific
+++ a/include/linux/kernel.h
@@ -16,6 +16,7 @@
 #include <linux/log2.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
+#include <asm/range.h>
 
 extern const char linux_banner[];
 extern const char linux_proc_banner[];
@@ -311,6 +312,26 @@ static inline int __attribute__ ((format
 	(void)__tmp; \
 })
 
+/**
+ * range_within - is one range within another?
+ * @start: the start value
+ * @len: the length from the start
+ * @base: the first valid value
+ * @limit: the first invalid value
+ *
+ * This is usually used for memory range testing.  The common cases of
+ * constant 0 start and constant 0 len cases are optimized out.
+ */
+static inline bool range_within(unsigned long start, unsigned long len,
+				unsigned long base, unsigned long limit)
+{
+	if (start < base)
+		return false;
+	if (__builtin_constant_p(len) && len == 0)
+		return start - base <= limit - base;
+	return !val_outside(limit, start, len);
+}
+
 struct sysinfo;
 extern int do_sysinfo(struct sysinfo *info);
 
_

Patches currently in -mm which might be from rusty@rustcorp.com.au are

vmi-paravirt-ops-bugfix-for-2621.patch
git-kbuild.patch
git-net.patch
rename-the-parainstructions-symbols-to-be-consistent-with-the-others.patch
allow-boot-time-disable-of-paravirt_ops-patching.patch
allow-per-cpu-variables-to-be-page-aligned.patch
xfs-clean-up-shrinker-games.patch
mm-clean-up-and-kernelify-shrinker-registration.patch
array_size-check-for-type.patch
array_size-check-for-type-uml-fix.patch
module-use-krealloc.patch
extend-print_symbol-capability.patch
extend-print_symbol-capability-fix.patch
futex-restartable-futex_wait.patch
futex-restartable-futex_wait-fix.patch
add-ability-to-keep-track-of-callers-of-symbol_getput.patch
add-ability-to-keep-track-of-callers-of-symbol_getput-update.patch
update-mtd-use-of-symbol_getput.patch
update-dvb-use-of-symbol_getput.patch
simplify-module_get_kallsym-by-dropping-length-arg.patch
fix-race-between-rmmod-and-cat-proc-kallsyms.patch
simplify-kallsyms_lookup.patch
fix-race-between-cat-proc-wchan-and-rmmod-et-al.patch
fix-race-between-cat-proc-slab_allocators-and-rmmod.patch
expose-range-checking-functions-from-arch-specific.patch
____call_usermodehelper-dont-flush_signals.patch
mm-clean-up-and-kernelify-shrinker-registration-reiser4.patch

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

akpm@linux-foundation.org wrote:

> + * @limit: the first invalid value

If this is the case, ...

> + *
> + * Like val + len > limit, except with overflow checking.
> + */
> +static inline bool val_outside(unsigned long val, unsigned long len,
> +			       unsigned long limit)
> +
> +{
> +	return val + len > limit || val + len < val;

... then shouldn't that be "val + len >= limit"?

David

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Rusty Russell]

On Tue, 2007-04-10 at 11:17 +0100, David Howells wrote:
> akpm@linux-foundation.org wrote:
> 
> > + * @limit: the first invalid value
> 
> If this is the case, ...
> 
> > + *
> > + * Like val + len > limit, except with overflow checking.
> > + */
> > +static inline bool val_outside(unsigned long val, unsigned long len,
> > +			       unsigned long limit)
> > +
> > +{
> > +	return val + len > limit || val + len < val;
> 
> ... then shouldn't that be "val + len >= limit"?

You're the second one to ask this.  I'm pretty sure it's still right
(and it's what the old code used to do).

Consider the case where limit is 0xC0000000, val is 0xBFFFFFFF and len
is 1.

Hope that helps,
Rusty.

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Andrew Morton]

On Wed, 11 Apr 2007 12:19:10 +1000 Rusty Russell <rusty@rustcorp.com.au> wrote:

> On Tue, 2007-04-10 at 11:17 +0100, David Howells wrote:
> > akpm@linux-foundation.org wrote:
> > 
> > > + * @limit: the first invalid value
> > 
> > If this is the case, ...
> > 
> > > + *
> > > + * Like val + len > limit, except with overflow checking.
> > > + */
> > > +static inline bool val_outside(unsigned long val, unsigned long len,
> > > +			       unsigned long limit)
> > > +
> > > +{
> > > +	return val + len > limit || val + len < val;
> > 
> > ... then shouldn't that be "val + len >= limit"?
> 
> You're the second one to ask this.  I'm pretty sure it's still right
> (and it's what the old code used to do).
> 
> Consider the case where limit is 0xC0000000, val is 0xBFFFFFFF and len
> is 1.
> 

I probably shouldn't look at this after a glass of red, but otoh, perhaps
that's a good way of ensuring that we have a built-in margin.


I find this function incomprehensible.  I'd just avoid using the sorry
thing, personally.


To me, "val_outside" means "true if the value is outside":

bool val_outside(val, start, len)
{
	return val < start || val > (start+len-1);
}

that's what my function does.  I don't have a clue what yours does.

For starters, wtf is a "limit"?  A length?  Or an offset relative to "len"?
And wtf is "len" anyway?  Absolute?  Relative?

<reworks it>

	return val > (limit - len) || val < (val - len);

nope, that didn't help.



The consequences of people getting this wrong are oopses, memory
corruption, root holes and other such pleasantry, in rare (or deliberately
invoked) circumstances.  Can we try to make it easier for them?

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Rusty Russell <rusty@rustcorp.com.au> wrote:

> You're the second one to ask this.  I'm pretty sure it's still right
> (and it's what the old code used to do).

On reconsideration, I'll withdraw my objection.  I think you're right.

> Consider the case where limit is 0xC0000000, val is 0xBFFFFFFF and len
> is 1.

Better still, consider val=0, len=1 and limit=1 as it's much easier to do in
one's head.  I was thinking about the limit case only (I could see wrap-around
is taken care of).


It might be better to call your function something like limit_check().  You
don't really mean val_outside() you mean range_outside() or something.


Also, I agree that having a standard function to detect it is a good thing to
do.  We have to make this check so often, and occasionally it's got wrong.

A further thought for you... might it be worth having a wrapper macro that
casts the val argument (and possibly the limit) to unsigned long?  Quite often
what you want to check are pointers.


Anyway:

Acked-By: David Howells <dhowells@redhat.com>

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Andrew Morton <akpm@linux-foundation.org> wrote:

> To me, "val_outside" means "true if the value is outside":
> 
> bool val_outside(val, start, len)
> {
> 	return val < start || val > (start+len-1);
> }
> 
> that's what my function does.

Seconded.  Again, I would suggest calling it something like limit_check() or
range_check().

David

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Rusty Russell]

On Tue, 2007-04-10 at 19:48 -0700, Andrew Morton wrote:
> On Wed, 11 Apr 2007 12:19:10 +1000 Rusty Russell <rusty@rustcorp.com.au> wrote:
> > > > + * Like val + len > limit, except with overflow checking.
> > > > + */
> > > > +static inline bool val_outside(unsigned long val, unsigned long len,
> > > > +			       unsigned long limit)
> > > > +
> > > > +{
> > > > +	return val + len > limit || val + len < val;

> I probably shouldn't look at this after a glass of red, but otoh, perhaps
> that's a good way of ensuring that we have a built-in margin.

> I find this function incomprehensible.  I'd just avoid using the sorry
> thing, personally.

No, you're absolutely right.  Naming is vital, and something I criticise
others for regularly.  We don't say "that is incomprehensible" anywhere
near often enough 8(

Is this clearer?

static inline bool range_over_limit(unsigned long start,
				    unsigned long len,
				    unsigned long limit)
{
	return start + len > limit || start + len < start;
}

Cheers,
Rusty.
PS.  Previously this identical function was called __range_ok() (and
returned 0 if it was not ok...)

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Rusty Russell <rusty@rustcorp.com.au> wrote:

> static inline bool range_over_limit(unsigned long start,
> 				    unsigned long len,
> 				    unsigned long limit)

I'm still not sure the name is entirely clear, but it's better.  I'd still
stick the word "check" in there personally, perhaps check_range_limit(), but
that's just my preference.

> PS.  Previously this identical function was called __range_ok() (and
> returned 0 if it was not ok...)

Ummm...  Didn't __range_ok() implicitly involve get_addr_limit() rather than
taking an explicit range?  Certainly i386 thinks so:

#define __range_ok(addr,size) ({ \
	unsigned long flag,roksum; \
	__chk_user_ptr(addr); \
	asm("addl %3,%1 ; sbbl %0,%0; cmpl %1,%4; sbbl $0,%0" \
		:"=&r" (flag), "=r" (roksum) \
		:"1" (addr),"g" ((int)(size)),"rm" (current_thread_info()->addr_limit.seg)); \
	flag; })

David

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Andrew Morton]

On Wed, 11 Apr 2007 11:49:19 +0100
David Howells <dhowells@redhat.com> wrote:

> Andrew Morton <akpm@linux-foundation.org> wrote:
> 
> > To me, "val_outside" means "true if the value is outside":
> > 
> > bool val_outside(val, start, len)
> > {
> > 	return val < start || val > (start+len-1);
> > }
> > 
> > that's what my function does.
> 
> Seconded.  Again, I would suggest calling it something like limit_check() or
> range_check().
> 

I suspect we would benefit from a proper suite of tools for comparing a
single number against a range, and for comparing ranges.  As you say, it's
something which we do an awful lot of, and we regularly get it wrong <looks
at a great pile of coverity-derived bugfixes.  It's like using time_after()
instead of open-coding it and then screwing it up.

But considerable thought, review and documentation would need to go into
that.  I'd then spend the next two years buried in cleanup patches <looks
at a great pile of ARRAY_SIZE and ROUND_UP patches>.

However Rusty's patch is merely a modest code consolidation.  And it's a
per-arch thing, which I suspect is inappropriate for a general
compare-a-number-with-a-range toolkit.  So I guess the above is out of
scope.

But I do thing we should continue to pile on about the val_outside() naming
and documentation ;)

Also, as a start on the generic range-checking toolkit I'd suggest that
range_within() should be implemented in linux/range.h, not in
linux/kernel.h.

range_within() isn't terribly well documented.  Does it return true only if
range1 is wholly within range2?  What if the two overlap?  What are the
boundary cases?

And the naming start, len, base, limit is hard to follow.  Wouldn't it be
better to have

bool range_within(unsigned long outer_range_start,
		unsigned long outer_range_len,
		unsigned long inner_range_start,
		unsigned long inner_range_len)

or similar?

then we go on to 

bool range_overlaps(range1_start, range1_len, range2_start, range2_len)
bool range_wholly_less_than(lesser_range_start, lesser_range_len,
			greater_range_start, greater_range_len)

and on and on...

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Andrew Morton]

On Wed, 11 Apr 2007 18:03:06 +0100
David Howells <dhowells@redhat.com> wrote:

> > static inline bool range_over_limit(unsigned long start,
> > 				    unsigned long len,
> > 				    unsigned long limit)
> 
> I'm still not sure the name is entirely clear, but it's better.  I'd still
> stick the word "check" in there personally, perhaps check_range_limit(), but
> that's just my preference.

If we (crazily) agree that we should/coould/might grow a suite of range-handling
functions then we should stick to the range_foo() namespace for that.

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Andrew Morton <akpm@linux-foundation.org> wrote:

> If we (crazily) agree that we should/coould/might grow a suite of
> range-handling functions then we should stick to the range_foo() namespace
> for that.

range_check_limit() then.

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Rusty Russell]

On Wed, 2007-04-11 at 18:03 +0100, David Howells wrote:
> Rusty Russell <rusty@rustcorp.com.au> wrote:
> 
> > static inline bool range_over_limit(unsigned long start,
> > 				    unsigned long len,
> > 				    unsigned long limit)
> 
> I'm still not sure the name is entirely clear, but it's better.  I'd still
> stick the word "check" in there personally, perhaps check_range_limit(), but
> that's just my preference.

"if (check_range_limit())" seems like the reverse of "if
(range_over_limit())" tho.

> > PS.  Previously this identical function was called __range_ok() (and
> > returned 0 if it was not ok...)
> 
> Ummm...  Didn't __range_ok() implicitly involve get_addr_limit() rather than
> taking an explicit range?  Certainly i386 thinks so:

Yep, my bad.  I was thinking of the sense of the return value.

Thanks,
Rusty.

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Rusty Russell]

On Wed, 2007-04-11 at 11:24 -0700, Andrew Morton wrote:
> Also, as a start on the generic range-checking toolkit I'd suggest that
> range_within() should be implemented in linux/range.h, not in
> linux/kernel.h.
> 
> range_within() isn't terribly well documented.  Does it return true only if
> range1 is wholly within range2?  What if the two overlap?  What are the
> boundary cases?

Actually, I think it's brilliantly documented.  Defining base as the
first valid value and limit as the first invalid value makes it pretty
clear, IMHO.

Anyway, I just want range_under_limit(start, len, limit).  Beyond that
gets confusing.  See below.

> bool range_within(unsigned long outer_range_start,
> 		unsigned long outer_range_len,
> 		unsigned long inner_range_start,
> 		unsigned long inner_range_len)

This *is* nicer, because noone will get confused about whether limit is
inclusive or exclusive.  I think the outer and inner arg order should be
swapped.

> bool range_overlaps(range1_start, range1_len, range2_start, range2_len)

I assume this means "range1 intersects range2"?

> bool range_wholly_less_than(lesser_range_start, lesser_range_len,
> 			greater_range_start, greater_range_len)

This means "lesser range does not intersect greater range, and is closer
to 0"?

In which case, the greater_range_len seems redundant, but isn't (because
greater_range_len could make the range wrap)?

Erk,
Rusty.

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Rusty Russell]

On Wed, 2007-04-11 at 11:24 -0700, Andrew Morton wrote:
> I suspect we would benefit from a proper suite of tools for comparing a
> single number against a range, and for comparing ranges.

How about this ambition-reduction patch, instead?

===
range_within() was too ambitious: it started inspiring people.  Remove it.

val_outside() was a terrible name, too.  Try range_over_limit().

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff -r 2f617843ce25 include/asm-generic/range.h
--- a/include/asm-generic/range.h	Thu Apr 12 09:32:53 2007 +1000
+++ b/include/asm-generic/range.h	Thu Apr 12 09:36:20 2007 +1000
@@ -2,18 +2,18 @@
 #define _ASM_GENERIC_RANGE_H
 
 /**
- * val_outside - is a value and length past a limit?
- * @val: the start value
+ * range_over_limit() - is a start and length past a limit?
+ * @start: the start value
  * @len: the length from the start
  * @limit: the first invalid value
  *
- * Like val + len > limit, except with overflow checking.
+ * Like start + len > limit, except with overflow checking.
  */
-static inline bool val_outside(unsigned long val, unsigned long len,
-			       unsigned long limit)
+static inline bool range_over_limit(unsigned long start, unsigned long len,
+				    unsigned long limit)
 
 {
-	return val + len > limit || val + len < val;
+	return start + len > limit || start + len < start;
 }
 
 #endif	/* _ASM_GENERIC_RANGE_H */
diff -r 2f617843ce25 include/asm-i386/range.h
--- a/include/asm-i386/range.h	Thu Apr 12 09:32:53 2007 +1000
+++ b/include/asm-i386/range.h	Thu Apr 12 09:36:37 2007 +1000
@@ -1,14 +1,14 @@
 #ifndef __ASM_RANGE_H
 #define __ASM_RANGE_H
 
-/* Is val + size > limit? This needs 33-bit arithmetic. We have a carry... */
-static inline bool val_outside(unsigned long val, unsigned long len,
-			       unsigned long limit)
+/* Is start + size > limit? This needs 33-bit arithmetic. We have a carry... */
+static inline bool range_over_limit(unsigned long start, unsigned long len,
+				    unsigned long limit)
 {
 	unsigned long flag, roksum;
 	asm("addl %3,%1 ; sbbl %0,%0; cmpl %1,%4; sbbl $0,%0"
 		:"=&r" (flag), "=r" (roksum)
-		:"1" (val), "g" (len), "rm" (limit));
+		:"1" (start), "g" (len), "rm" (limit));
 	return flag;
 }
 #endif	/* __ASM_RANGE_H */
diff -r 2f617843ce25 include/asm-i386/uaccess.h
--- a/include/asm-i386/uaccess.h	Thu Apr 12 09:32:53 2007 +1000
+++ b/include/asm-i386/uaccess.h	Thu Apr 12 09:37:07 2007 +1000
@@ -51,10 +51,10 @@ extern struct movsl_mask {
  * This is equivalent to the following test:
  * (u33)addr + (u33)size > (u33)current->addr_limit.seg
  */
-#define __range_ok(addr, size) ({				\
-	__chk_user_ptr(addr);					\
-	val_outside((int)(addr), (size),			\
-		    current_thread_info()->addr_limit.seg);	\
+#define __range_ok(addr, size) ({					\
+	__chk_user_ptr(addr);						\
+	range_over_limit((int)(addr), (size),				\
+			 current_thread_info()->addr_limit.seg);	\
 })
 
 /**
diff -r 2f617843ce25 include/linux/kernel.h
--- a/include/linux/kernel.h	Thu Apr 12 09:32:53 2007 +1000
+++ b/include/linux/kernel.h	Thu Apr 12 09:35:13 2007 +1000
@@ -16,7 +16,6 @@
 #include <linux/log2.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
-#include <asm/range.h>
 
 extern const char linux_banner[];
 extern const char linux_proc_banner[];
@@ -312,26 +311,6 @@ static inline int __attribute__ ((format
 	(void)__tmp; \
 })
 
-/**
- * range_within - is one range within another?
- * @start: the start value
- * @len: the length from the start
- * @base: the first valid value
- * @limit: the first invalid value
- *
- * This is usually used for memory range testing.  The common cases of
- * constant 0 start and constant 0 len cases are optimized out.
- */
-static inline bool range_within(unsigned long start, unsigned long len,
-				unsigned long base, unsigned long limit)
-{
-	if (start < base)
-		return false;
-	if (__builtin_constant_p(len) && len == 0)
-		return start - base <= limit - base;
-	return !val_outside(limit, start, len);
-}
-
 struct sysinfo;
 extern int do_sysinfo(struct sysinfo *info);
 

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Geert Uytterhoeven]

On Wed, 11 Apr 2007, Andrew Morton wrote:
> On Wed, 11 Apr 2007 11:49:19 +0100
> David Howells <dhowells@redhat.com> wrote:
> > Andrew Morton <akpm@linux-foundation.org> wrote:
> > > To me, "val_outside" means "true if the value is outside":
> > > 
> > > bool val_outside(val, start, len)
> > > {
> > > 	return val < start || val > (start+len-1);
> > > }
> > > 
> > > that's what my function does.
> > 
> > Seconded.  Again, I would suggest calling it something like limit_check() or
> > range_check().
> 
> I suspect we would benefit from a proper suite of tools for comparing a
> single number against a range, and for comparing ranges.  As you say, it's

And probably we want a generic routine to do intersections of ranges,
too?

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Rusty Russell <rusty@rustcorp.com.au> wrote:

> +static inline bool range_over_limit(unsigned long start, unsigned long len,
> +				    unsigned long limit)

I like it.

> + * range_over_limit() - is a start and length past a limit?

As I understand it you wouldn't normally put "()" there for kdoc comments.

David

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[David Howells]

Rusty Russell <rusty@rustcorp.com.au> wrote:

> 
> "if (check_range_limit())" seems like the reverse of "if
> (range_over_limit())" tho.

True.  However, I like your range_over_limit() name better as it means you
don't need a "!" operator or a comparator when using it.

David

Re: + expose-range-checking-functions-from-arch-specific.patch added to -mm tree

[Randy Dunlap]

David Howells wrote:
> Rusty Russell <rusty@rustcorp.com.au> wrote:
> 
>> +static inline bool range_over_limit(unsigned long start, unsigned long len,
>> +				    unsigned long limit)
> 
> I like it.
> 
>> + * range_over_limit() - is a start and length past a limit?
> 
> As I understand it you wouldn't normally put "()" there for kdoc comments.

Correct, but scripts/kernel-doc filters out the "()" for its output.

-- 
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

RE: + expose-range-checking-functions-from-arch-specific.patchadded to -mm tree

[Luck, Tony]

> Actually, I think it's brilliantly documented.  Defining base as the
> first valid value and limit as the first invalid value makes it pretty
> clear, IMHO.

"first invalid value" is hard to express if the range you
want to check includes the largest value for the type
you are using.  Either "limit" needs to be the largest
allowable value, or you should stick to "base,len".

-Tony

RE: + expose-range-checking-functions-from-arch-specific.patchadded to -mm tree

[Rusty Russell]

On Thu, 2007-04-12 at 09:05 -0700, Luck, Tony wrote:
> > Actually, I think it's brilliantly documented.  Defining base as the
> > first valid value and limit as the first invalid value makes it pretty
> > clear, IMHO.
> 
> "first invalid value" is hard to express if the range you
> want to check includes the largest value for the type
> you are using.  Either "limit" needs to be the largest
> allowable value, or you should stick to "base,len".

Hi Tony!

	Sure.  But to be pedantic, that's not a question of documentation: the
documentation made it pretty clear that this expression was not
possible.

Nonetheless, I agree that base+len has merit over start & end.

Cheers,
Rusty.