[RFC PATCH 0/2] Implement word-at-a-time string functions

[RFC PATCH 0/2] Implement word-at-a-time string functions

[Will Deacon]

Hello,

This patch series does two things:

1. Implements the word-at-a-time API for ARM and replaces our user
   string operations with the generic optimised variants.

2. On CPUs with efficient hardware support for unaligned accesses (v6+),
   select DCACHE_WORD_ACCESS for little-endian configurations.

In standalone tests on a Cortex-A9, this results in a 55% performance
improvement for name hashing and some simple find operations over a
tmpfs filesystem show that the relative improvement for per-word hashing
increases with the length of the pathname (assumedly up to the 55%
ceiling, although with 1k pathnames the improvement is 10% so I doubt
we'd be able to hit the maximum speedup in this simple test).

If anybody has some better pathname-lookup-intensive benchmarks, I'd be
happy to try them out.

All comments welcome,

Will


Will Deacon (2):
  ARM: use generic strnlen_user and strncpy_from_user functions
  ARM: dcache: select DCACHE_WORD_ACCESS for little-endian ARMv6+ CPUs

 arch/arm/Kconfig                      |    3 +
 arch/arm/include/asm/uaccess.h        |   27 ++-------
 arch/arm/include/asm/word-at-a-time.h |   96 +++++++++++++++++++++++++++++++++
 arch/arm/kernel/armksyms.c            |    4 --
 arch/arm/lib/Makefile                 |    1 -
 arch/arm/lib/strncpy_from_user.S      |   43 ---------------
 arch/arm/lib/strnlen_user.S           |   40 --------------
 7 files changed, 105 insertions(+), 109 deletions(-)
 create mode 100644 arch/arm/include/asm/word-at-a-time.h
 delete mode 100644 arch/arm/lib/strncpy_from_user.S
 delete mode 100644 arch/arm/lib/strnlen_user.S

-- 
1.7.4.1

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Will Deacon]

This patch implements the word-at-a-time interface for ARM using the
same algorithm as x86. Although we have a clz instruction from ARMv5,
this only saves us one mov instruction when building with Thumb-2 and
makes no difference when targetting ARM, so we use the magic 0x0ff0001
constant for all CPUs. For big-endian configurations, we use the
implementation from asm-generic.

With this implemented, we can replace our byte-at-a-time strnlen_user
and strncpy_from_user functions with the optimised generic versions.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 arch/arm/Kconfig                      |    2 +
 arch/arm/include/asm/uaccess.h        |   27 +++------------
 arch/arm/include/asm/word-at-a-time.h |   55 +++++++++++++++++++++++++++++++++
 arch/arm/kernel/armksyms.c            |    4 --
 arch/arm/lib/Makefile                 |    1 -
 arch/arm/lib/strncpy_from_user.S      |   43 -------------------------
 arch/arm/lib/strnlen_user.S           |   40 ------------------------
 7 files changed, 63 insertions(+), 109 deletions(-)
 create mode 100644 arch/arm/include/asm/word-at-a-time.h
 delete mode 100644 arch/arm/lib/strncpy_from_user.S
 delete mode 100644 arch/arm/lib/strnlen_user.S

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index b649c59..b236fd9 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -46,6 +46,8 @@ config ARM
 	select GENERIC_SMP_IDLE_THREAD
 	select KTIME_SCALAR
 	select GENERIC_CLOCKEVENTS_BROADCAST if SMP
+	select GENERIC_STRNCPY_FROM_USER
+	select GENERIC_STRNLEN_USER
 	help
 	  The ARM series is a line of low-power-consumption RISC chip designs
 	  licensed by ARM Ltd and targeted at embedded applications and
diff --git a/arch/arm/include/asm/uaccess.h b/arch/arm/include/asm/uaccess.h
index 71f6536..479a635 100644
--- a/arch/arm/include/asm/uaccess.h
+++ b/arch/arm/include/asm/uaccess.h
@@ -189,6 +189,9 @@ static inline void set_fs(mm_segment_t fs)
 
 #define access_ok(type,addr,size)	(__range_ok(addr,size) == 0)
 
+#define user_addr_max() \
+	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
+
 /*
  * The "__xxx" versions of the user access functions do not verify the
  * address space - it must have been done previously with a separate
@@ -398,9 +401,6 @@ extern unsigned long __must_check __clear_user_std(void __user *addr, unsigned l
 #define __clear_user(addr,n)		(memset((void __force *)addr, 0, n), 0)
 #endif
 
-extern unsigned long __must_check __strncpy_from_user(char *to, const char __user *from, unsigned long count);
-extern unsigned long __must_check __strnlen_user(const char __user *s, long n);
-
 static inline unsigned long __must_check copy_from_user(void *to, const void __user *from, unsigned long n)
 {
 	if (access_ok(VERIFY_READ, from, n))
@@ -427,24 +427,9 @@ static inline unsigned long __must_check clear_user(void __user *to, unsigned lo
 	return n;
 }
 
-static inline long __must_check strncpy_from_user(char *dst, const char __user *src, long count)
-{
-	long res = -EFAULT;
-	if (access_ok(VERIFY_READ, src, 1))
-		res = __strncpy_from_user(dst, src, count);
-	return res;
-}
-
-#define strlen_user(s)	strnlen_user(s, ~0UL >> 1)
+extern long strncpy_from_user(char *dest, const char __user *src, long count);
 
-static inline long __must_check strnlen_user(const char __user *s, long n)
-{
-	unsigned long res = 0;
-
-	if (__addr_ok(s))
-		res = __strnlen_user(s, n);
-
-	return res;
-}
+extern __must_check long strlen_user(const char __user *str);
+extern __must_check long strnlen_user(const char __user *str, long n);
 
 #endif /* _ASMARM_UACCESS_H */
diff --git a/arch/arm/include/asm/word-at-a-time.h b/arch/arm/include/asm/word-at-a-time.h
new file mode 100644
index 0000000..74b2d45
--- /dev/null
+++ b/arch/arm/include/asm/word-at-a-time.h
@@ -0,0 +1,55 @@
+#ifndef __ASM_ARM_WORD_AT_A_TIME_H
+#define __ASM_ARM_WORD_AT_A_TIME_H
+
+#ifndef __ARMEB__
+
+/*
+ * Little-endian word-at-a-time zero byte handling.
+ * Heavily based on the x86 algorithm.
+ */
+#include <linux/kernel.h>
+
+struct word_at_a_time {
+	const unsigned long one_bits, high_bits;
+};
+
+#define WORD_AT_A_TIME_CONSTANTS { REPEAT_BYTE(0x01), REPEAT_BYTE(0x80) }
+
+static inline unsigned long has_zero(unsigned long a, unsigned long *bits,
+				     const struct word_at_a_time *c)
+{
+	unsigned long mask = ((a - c->one_bits) & ~a) & c->high_bits;
+	*bits = mask;
+	return mask;
+}
+
+#define prep_zero_mask(a, bits, c) (bits)
+
+static inline unsigned long create_zero_mask(unsigned long bits)
+{
+	bits = (bits - 1) & ~bits;
+	return bits >> 7;
+}
+
+static inline unsigned long find_zero(unsigned long mask)
+{
+	unsigned long ret;
+
+#if __LINUX_ARM_ARCH__ >= 5
+	/* We have clz available. */
+	ret = fls(mask) >> 3;
+#else
+	/* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */
+	ret = (0x0ff0001 + mask) >> 23;
+	/* Fix the 1 for 00 case */
+	ret &= mask;
+#endif
+
+	return ret;
+}
+
+#else	/* __ARMEB__ */
+#include <asm-generic/word-at-a-time.h>
+#endif
+
+#endif /* __ASM_ARM_WORD_AT_A_TIME_H */
diff --git a/arch/arm/kernel/armksyms.c b/arch/arm/kernel/armksyms.c
index b57c75e..c3dff6a 100644
--- a/arch/arm/kernel/armksyms.c
+++ b/arch/arm/kernel/armksyms.c
@@ -87,10 +87,6 @@ EXPORT_SYMBOL(memmove);
 EXPORT_SYMBOL(memchr);
 EXPORT_SYMBOL(__memzero);
 
-	/* user mem (segment) */
-EXPORT_SYMBOL(__strnlen_user);
-EXPORT_SYMBOL(__strncpy_from_user);
-
 #ifdef CONFIG_MMU
 EXPORT_SYMBOL(copy_page);
 
diff --git a/arch/arm/lib/Makefile b/arch/arm/lib/Makefile
index 992769a..d5060da 100644
--- a/arch/arm/lib/Makefile
+++ b/arch/arm/lib/Makefile
@@ -8,7 +8,6 @@ lib-y		:= backtrace.o changebit.o csumipv6.o csumpartial.o   \
 		   csumpartialcopy.o csumpartialcopyuser.o clearbit.o \
 		   delay.o findbit.o memchr.o memcpy.o		      \
 		   memmove.o memset.o memzero.o setbit.o              \
-		   strncpy_from_user.o strnlen_user.o                 \
 		   strchr.o strrchr.o                                 \
 		   testchangebit.o testclearbit.o testsetbit.o        \
 		   ashldi3.o ashrdi3.o lshrdi3.o muldi3.o             \
diff --git a/arch/arm/lib/strncpy_from_user.S b/arch/arm/lib/strncpy_from_user.S
deleted file mode 100644
index f202d7b..0000000
--- a/arch/arm/lib/strncpy_from_user.S
+++ /dev/null
@@ -1,43 +0,0 @@
-/*
- *  linux/arch/arm/lib/strncpy_from_user.S
- *
- *  Copyright (C) 1995-2000 Russell King
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- */
-#include <linux/linkage.h>
-#include <asm/assembler.h>
-#include <asm/errno.h>
-
-	.text
-	.align	5
-
-/*
- * Copy a string from user space to kernel space.
- *  r0 = dst, r1 = src, r2 = byte length
- * returns the number of characters copied (strlen of copied string),
- *  -EFAULT on exception, or "len" if we fill the whole buffer
- */
-ENTRY(__strncpy_from_user)
-	mov	ip, r1
-1:	subs	r2, r2, #1
-	ldrusr	r3, r1, 1, pl
-	bmi	2f
-	strb	r3, [r0], #1
-	teq	r3, #0
-	bne	1b
-	sub	r1, r1, #1	@ take NUL character out of count
-2:	sub	r0, r1, ip
-	mov	pc, lr
-ENDPROC(__strncpy_from_user)
-
-	.pushsection .fixup,"ax"
-	.align	0
-9001:	mov	r3, #0
-	strb	r3, [r0, #0]	@ null terminate
-	mov	r0, #-EFAULT
-	mov	pc, lr
-	.popsection
-
diff --git a/arch/arm/lib/strnlen_user.S b/arch/arm/lib/strnlen_user.S
deleted file mode 100644
index 0ecbb45..0000000
--- a/arch/arm/lib/strnlen_user.S
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- *  linux/arch/arm/lib/strnlen_user.S
- *
- *  Copyright (C) 1995-2000 Russell King
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- */
-#include <linux/linkage.h>
-#include <asm/assembler.h>
-#include <asm/errno.h>
-
-	.text
-	.align	5
-
-/* Prototype: unsigned long __strnlen_user(const char *str, long n)
- * Purpose  : get length of a string in user memory
- * Params   : str - address of string in user memory
- * Returns  : length of string *including terminator*
- *	      or zero on exception, or n + 1 if too long
- */
-ENTRY(__strnlen_user)
-	mov	r2, r0
-1:
-	ldrusr	r3, r0, 1
-	teq	r3, #0
-	beq	2f
-	subs	r1, r1, #1
-	bne	1b
-	add	r0, r0, #1
-2:	sub	r0, r0, r2
-	mov	pc, lr
-ENDPROC(__strnlen_user)
-
-	.pushsection .fixup,"ax"
-	.align	0
-9001:	mov	r0, #0
-	mov	pc, lr
-	.popsection
-- 
1.7.4.1

[RFC PATCH 2/2] ARM: dcache: select DCACHE_WORD_ACCESS for little-endian ARMv6+ CPUs

[Will Deacon]

DCACHE_WORD_ACCESS uses the word-at-a-time API for optimised string
comparisons in the vfs layer.

This patch implements support for load_unaligned_zeropad for ARM CPUs
with native support for unaligned memory accesses (v6+) when running
little-endian.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 arch/arm/Kconfig                      |    1 +
 arch/arm/include/asm/word-at-a-time.h |   41 +++++++++++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 0 deletions(-)

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index b236fd9..9e7b51f 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -48,6 +48,7 @@ config ARM
 	select GENERIC_CLOCKEVENTS_BROADCAST if SMP
 	select GENERIC_STRNCPY_FROM_USER
 	select GENERIC_STRNLEN_USER
+	select DCACHE_WORD_ACCESS if (CPU_V6 || CPU_V6K || CPU_V7) && !CPU_BIG_ENDIAN
 	help
 	  The ARM series is a line of low-power-consumption RISC chip designs
 	  licensed by ARM Ltd and targeted at embedded applications and
diff --git a/arch/arm/include/asm/word-at-a-time.h b/arch/arm/include/asm/word-at-a-time.h
index 74b2d45..4d52f92 100644
--- a/arch/arm/include/asm/word-at-a-time.h
+++ b/arch/arm/include/asm/word-at-a-time.h
@@ -48,6 +48,47 @@ static inline unsigned long find_zero(unsigned long mask)
 	return ret;
 }
 
+#ifdef CONFIG_DCACHE_WORD_ACCESS
+
+#define zero_bytemask(mask) (mask)
+
+/*
+ * Load an unaligned word from kernel space.
+ *
+ * In the (very unlikely) case of the word being a page-crosser
+ * and the next page not being mapped, take the exception and
+ * return zeroes in the non-existing part.
+ */
+static inline unsigned long load_unaligned_zeropad(const void *addr)
+{
+	unsigned long ret, offset;
+
+	/* Load word from unaligned pointer addr */
+	asm(
+	"1:	ldr	%0, [%2]\n"
+	"2:\n"
+	"	.pushsection .fixup,\"ax\"\n"
+	"	.align 2\n"
+	"3:	and	%1, %2, #0x3\n"
+	"	bic	%2, %2, #0x3\n"
+	"	ldr	%0, [%2]\n"
+	"	lsl	%1, %1, #0x3\n"
+	"	lsr	%0, %0, %1\n"
+	"	b	2b\n"
+	"	.popsection\n"
+	"	.pushsection __ex_table,\"a\"\n"
+	"	.align	3\n"
+	"	.long	1b, 3b\n"
+	"	.popsection"
+	: "=&r" (ret), "=&r" (offset)
+	: "r" (addr), "Qo" (*(unsigned long *)addr));
+
+	return ret;
+}
+
+
+#endif	/* DCACHE_WORD_ACCESS */
+
 #else	/* __ARMEB__ */
 #include <asm-generic/word-at-a-time.h>
 #endif
-- 
1.7.4.1

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Will Deacon]

On Fri, Jun 08, 2012 at 04:38:54PM +0100, Will Deacon wrote:
> This patch implements the word-at-a-time interface for ARM using the
> same algorithm as x86. Although we have a clz instruction from ARMv5,
> this only saves us one mov instruction when building with Thumb-2 and
> makes no difference when targetting ARM, so we use the magic 0x0ff0001
> constant for all CPUs. For big-endian configurations, we use the
> implementation from asm-generic.

Damn, I forgot to update this comment. I decided that it was worth getting
rid of the mov since it's fairly clean using the fls macro, so we do emit
a clz instruction on ARMv5 and later.

Will

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Nicolas Pitre]

On Fri, 8 Jun 2012, Will Deacon wrote:

> This patch implements the word-at-a-time interface for ARM using the
> same algorithm as x86. Although we have a clz instruction from ARMv5,
> this only saves us one mov instruction when building with Thumb-2 and
> makes no difference when targetting ARM, so we use the magic 0x0ff0001
> constant for all CPUs. For big-endian configurations, we use the
> implementation from asm-generic.
> 
> With this implemented, we can replace our byte-at-a-time strnlen_user
> and strncpy_from_user functions with the optimised generic versions.
> 
> Signed-off-by: Will Deacon <will.deacon@arm.com>

With the updated patch comment...

Reviewed-by: Nicolas Pitre <nico@linaro.org>


> ---
>  arch/arm/Kconfig                      |    2 +
>  arch/arm/include/asm/uaccess.h        |   27 +++------------
>  arch/arm/include/asm/word-at-a-time.h |   55 +++++++++++++++++++++++++++++++++
>  arch/arm/kernel/armksyms.c            |    4 --
>  arch/arm/lib/Makefile                 |    1 -
>  arch/arm/lib/strncpy_from_user.S      |   43 -------------------------
>  arch/arm/lib/strnlen_user.S           |   40 ------------------------
>  7 files changed, 63 insertions(+), 109 deletions(-)
>  create mode 100644 arch/arm/include/asm/word-at-a-time.h
>  delete mode 100644 arch/arm/lib/strncpy_from_user.S
>  delete mode 100644 arch/arm/lib/strnlen_user.S
> 
> diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
> index b649c59..b236fd9 100644
> --- a/arch/arm/Kconfig
> +++ b/arch/arm/Kconfig
> @@ -46,6 +46,8 @@ config ARM
>  	select GENERIC_SMP_IDLE_THREAD
>  	select KTIME_SCALAR
>  	select GENERIC_CLOCKEVENTS_BROADCAST if SMP
> +	select GENERIC_STRNCPY_FROM_USER
> +	select GENERIC_STRNLEN_USER
>  	help
>  	  The ARM series is a line of low-power-consumption RISC chip designs
>  	  licensed by ARM Ltd and targeted at embedded applications and
> diff --git a/arch/arm/include/asm/uaccess.h b/arch/arm/include/asm/uaccess.h
> index 71f6536..479a635 100644
> --- a/arch/arm/include/asm/uaccess.h
> +++ b/arch/arm/include/asm/uaccess.h
> @@ -189,6 +189,9 @@ static inline void set_fs(mm_segment_t fs)
>  
>  #define access_ok(type,addr,size)	(__range_ok(addr,size) == 0)
>  
> +#define user_addr_max() \
> +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> +
>  /*
>   * The "__xxx" versions of the user access functions do not verify the
>   * address space - it must have been done previously with a separate
> @@ -398,9 +401,6 @@ extern unsigned long __must_check __clear_user_std(void __user *addr, unsigned l
>  #define __clear_user(addr,n)		(memset((void __force *)addr, 0, n), 0)
>  #endif
>  
> -extern unsigned long __must_check __strncpy_from_user(char *to, const char __user *from, unsigned long count);
> -extern unsigned long __must_check __strnlen_user(const char __user *s, long n);
> -
>  static inline unsigned long __must_check copy_from_user(void *to, const void __user *from, unsigned long n)
>  {
>  	if (access_ok(VERIFY_READ, from, n))
> @@ -427,24 +427,9 @@ static inline unsigned long __must_check clear_user(void __user *to, unsigned lo
>  	return n;
>  }
>  
> -static inline long __must_check strncpy_from_user(char *dst, const char __user *src, long count)
> -{
> -	long res = -EFAULT;
> -	if (access_ok(VERIFY_READ, src, 1))
> -		res = __strncpy_from_user(dst, src, count);
> -	return res;
> -}
> -
> -#define strlen_user(s)	strnlen_user(s, ~0UL >> 1)
> +extern long strncpy_from_user(char *dest, const char __user *src, long count);
>  
> -static inline long __must_check strnlen_user(const char __user *s, long n)
> -{
> -	unsigned long res = 0;
> -
> -	if (__addr_ok(s))
> -		res = __strnlen_user(s, n);
> -
> -	return res;
> -}
> +extern __must_check long strlen_user(const char __user *str);
> +extern __must_check long strnlen_user(const char __user *str, long n);
>  
>  #endif /* _ASMARM_UACCESS_H */
> diff --git a/arch/arm/include/asm/word-at-a-time.h b/arch/arm/include/asm/word-at-a-time.h
> new file mode 100644
> index 0000000..74b2d45
> --- /dev/null
> +++ b/arch/arm/include/asm/word-at-a-time.h
> @@ -0,0 +1,55 @@
> +#ifndef __ASM_ARM_WORD_AT_A_TIME_H
> +#define __ASM_ARM_WORD_AT_A_TIME_H
> +
> +#ifndef __ARMEB__
> +
> +/*
> + * Little-endian word-at-a-time zero byte handling.
> + * Heavily based on the x86 algorithm.
> + */
> +#include <linux/kernel.h>
> +
> +struct word_at_a_time {
> +	const unsigned long one_bits, high_bits;
> +};
> +
> +#define WORD_AT_A_TIME_CONSTANTS { REPEAT_BYTE(0x01), REPEAT_BYTE(0x80) }
> +
> +static inline unsigned long has_zero(unsigned long a, unsigned long *bits,
> +				     const struct word_at_a_time *c)
> +{
> +	unsigned long mask = ((a - c->one_bits) & ~a) & c->high_bits;
> +	*bits = mask;
> +	return mask;
> +}
> +
> +#define prep_zero_mask(a, bits, c) (bits)
> +
> +static inline unsigned long create_zero_mask(unsigned long bits)
> +{
> +	bits = (bits - 1) & ~bits;
> +	return bits >> 7;
> +}
> +
> +static inline unsigned long find_zero(unsigned long mask)
> +{
> +	unsigned long ret;
> +
> +#if __LINUX_ARM_ARCH__ >= 5
> +	/* We have clz available. */
> +	ret = fls(mask) >> 3;
> +#else
> +	/* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */
> +	ret = (0x0ff0001 + mask) >> 23;
> +	/* Fix the 1 for 00 case */
> +	ret &= mask;
> +#endif
> +
> +	return ret;
> +}
> +
> +#else	/* __ARMEB__ */
> +#include <asm-generic/word-at-a-time.h>
> +#endif
> +
> +#endif /* __ASM_ARM_WORD_AT_A_TIME_H */
> diff --git a/arch/arm/kernel/armksyms.c b/arch/arm/kernel/armksyms.c
> index b57c75e..c3dff6a 100644
> --- a/arch/arm/kernel/armksyms.c
> +++ b/arch/arm/kernel/armksyms.c
> @@ -87,10 +87,6 @@ EXPORT_SYMBOL(memmove);
>  EXPORT_SYMBOL(memchr);
>  EXPORT_SYMBOL(__memzero);
>  
> -	/* user mem (segment) */
> -EXPORT_SYMBOL(__strnlen_user);
> -EXPORT_SYMBOL(__strncpy_from_user);
> -
>  #ifdef CONFIG_MMU
>  EXPORT_SYMBOL(copy_page);
>  
> diff --git a/arch/arm/lib/Makefile b/arch/arm/lib/Makefile
> index 992769a..d5060da 100644
> --- a/arch/arm/lib/Makefile
> +++ b/arch/arm/lib/Makefile
> @@ -8,7 +8,6 @@ lib-y		:= backtrace.o changebit.o csumipv6.o csumpartial.o   \
>  		   csumpartialcopy.o csumpartialcopyuser.o clearbit.o \
>  		   delay.o findbit.o memchr.o memcpy.o		      \
>  		   memmove.o memset.o memzero.o setbit.o              \
> -		   strncpy_from_user.o strnlen_user.o                 \
>  		   strchr.o strrchr.o                                 \
>  		   testchangebit.o testclearbit.o testsetbit.o        \
>  		   ashldi3.o ashrdi3.o lshrdi3.o muldi3.o             \
> diff --git a/arch/arm/lib/strncpy_from_user.S b/arch/arm/lib/strncpy_from_user.S
> deleted file mode 100644
> index f202d7b..0000000
> --- a/arch/arm/lib/strncpy_from_user.S
> +++ /dev/null
> @@ -1,43 +0,0 @@
> -/*
> - *  linux/arch/arm/lib/strncpy_from_user.S
> - *
> - *  Copyright (C) 1995-2000 Russell King
> - *
> - * This program is free software; you can redistribute it and/or modify
> - * it under the terms of the GNU General Public License version 2 as
> - * published by the Free Software Foundation.
> - */
> -#include <linux/linkage.h>
> -#include <asm/assembler.h>
> -#include <asm/errno.h>
> -
> -	.text
> -	.align	5
> -
> -/*
> - * Copy a string from user space to kernel space.
> - *  r0 = dst, r1 = src, r2 = byte length
> - * returns the number of characters copied (strlen of copied string),
> - *  -EFAULT on exception, or "len" if we fill the whole buffer
> - */
> -ENTRY(__strncpy_from_user)
> -	mov	ip, r1
> -1:	subs	r2, r2, #1
> -	ldrusr	r3, r1, 1, pl
> -	bmi	2f
> -	strb	r3, [r0], #1
> -	teq	r3, #0
> -	bne	1b
> -	sub	r1, r1, #1	@ take NUL character out of count
> -2:	sub	r0, r1, ip
> -	mov	pc, lr
> -ENDPROC(__strncpy_from_user)
> -
> -	.pushsection .fixup,"ax"
> -	.align	0
> -9001:	mov	r3, #0
> -	strb	r3, [r0, #0]	@ null terminate
> -	mov	r0, #-EFAULT
> -	mov	pc, lr
> -	.popsection
> -
> diff --git a/arch/arm/lib/strnlen_user.S b/arch/arm/lib/strnlen_user.S
> deleted file mode 100644
> index 0ecbb45..0000000
> --- a/arch/arm/lib/strnlen_user.S
> +++ /dev/null
> @@ -1,40 +0,0 @@
> -/*
> - *  linux/arch/arm/lib/strnlen_user.S
> - *
> - *  Copyright (C) 1995-2000 Russell King
> - *
> - * This program is free software; you can redistribute it and/or modify
> - * it under the terms of the GNU General Public License version 2 as
> - * published by the Free Software Foundation.
> - */
> -#include <linux/linkage.h>
> -#include <asm/assembler.h>
> -#include <asm/errno.h>
> -
> -	.text
> -	.align	5
> -
> -/* Prototype: unsigned long __strnlen_user(const char *str, long n)
> - * Purpose  : get length of a string in user memory
> - * Params   : str - address of string in user memory
> - * Returns  : length of string *including terminator*
> - *	      or zero on exception, or n + 1 if too long
> - */
> -ENTRY(__strnlen_user)
> -	mov	r2, r0
> -1:
> -	ldrusr	r3, r0, 1
> -	teq	r3, #0
> -	beq	2f
> -	subs	r1, r1, #1
> -	bne	1b
> -	add	r0, r0, #1
> -2:	sub	r0, r0, r2
> -	mov	pc, lr
> -ENDPROC(__strnlen_user)
> -
> -	.pushsection .fixup,"ax"
> -	.align	0
> -9001:	mov	r0, #0
> -	mov	pc, lr
> -	.popsection
> -- 
> 1.7.4.1
> 
> 
> _______________________________________________
> linux-arm-kernel mailing list
> linux-arm-kernel at lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
> 

[RFC PATCH 2/2] ARM: dcache: select DCACHE_WORD_ACCESS for little-endian ARMv6+ CPUs

[Nicolas Pitre]

On Fri, 8 Jun 2012, Will Deacon wrote:

> DCACHE_WORD_ACCESS uses the word-at-a-time API for optimised string
> comparisons in the vfs layer.
> 
> This patch implements support for load_unaligned_zeropad for ARM CPUs
> with native support for unaligned memory accesses (v6+) when running
> little-endian.
> 
> Signed-off-by: Will Deacon <will.deacon@arm.com>

Reviewed-by: Nicolas Pitre <nico@linaro.org>

> ---
>  arch/arm/Kconfig                      |    1 +
>  arch/arm/include/asm/word-at-a-time.h |   41 +++++++++++++++++++++++++++++++++
>  2 files changed, 42 insertions(+), 0 deletions(-)
> 
> diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
> index b236fd9..9e7b51f 100644
> --- a/arch/arm/Kconfig
> +++ b/arch/arm/Kconfig
> @@ -48,6 +48,7 @@ config ARM
>  	select GENERIC_CLOCKEVENTS_BROADCAST if SMP
>  	select GENERIC_STRNCPY_FROM_USER
>  	select GENERIC_STRNLEN_USER
> +	select DCACHE_WORD_ACCESS if (CPU_V6 || CPU_V6K || CPU_V7) && !CPU_BIG_ENDIAN
>  	help
>  	  The ARM series is a line of low-power-consumption RISC chip designs
>  	  licensed by ARM Ltd and targeted at embedded applications and
> diff --git a/arch/arm/include/asm/word-at-a-time.h b/arch/arm/include/asm/word-at-a-time.h
> index 74b2d45..4d52f92 100644
> --- a/arch/arm/include/asm/word-at-a-time.h
> +++ b/arch/arm/include/asm/word-at-a-time.h
> @@ -48,6 +48,47 @@ static inline unsigned long find_zero(unsigned long mask)
>  	return ret;
>  }
>  
> +#ifdef CONFIG_DCACHE_WORD_ACCESS
> +
> +#define zero_bytemask(mask) (mask)
> +
> +/*
> + * Load an unaligned word from kernel space.
> + *
> + * In the (very unlikely) case of the word being a page-crosser
> + * and the next page not being mapped, take the exception and
> + * return zeroes in the non-existing part.
> + */
> +static inline unsigned long load_unaligned_zeropad(const void *addr)
> +{
> +	unsigned long ret, offset;
> +
> +	/* Load word from unaligned pointer addr */
> +	asm(
> +	"1:	ldr	%0, [%2]\n"
> +	"2:\n"
> +	"	.pushsection .fixup,\"ax\"\n"
> +	"	.align 2\n"
> +	"3:	and	%1, %2, #0x3\n"
> +	"	bic	%2, %2, #0x3\n"
> +	"	ldr	%0, [%2]\n"
> +	"	lsl	%1, %1, #0x3\n"
> +	"	lsr	%0, %0, %1\n"
> +	"	b	2b\n"
> +	"	.popsection\n"
> +	"	.pushsection __ex_table,\"a\"\n"
> +	"	.align	3\n"
> +	"	.long	1b, 3b\n"
> +	"	.popsection"
> +	: "=&r" (ret), "=&r" (offset)
> +	: "r" (addr), "Qo" (*(unsigned long *)addr));
> +
> +	return ret;
> +}
> +
> +
> +#endif	/* DCACHE_WORD_ACCESS */
> +
>  #else	/* __ARMEB__ */
>  #include <asm-generic/word-at-a-time.h>
>  #endif
> -- 
> 1.7.4.1
> 
> 
> _______________________________________________
> linux-arm-kernel mailing list
> linux-arm-kernel at lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
> 

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Will Deacon]

On Tue, Jun 12, 2012 at 03:53:56AM +0100, Nicolas Pitre wrote:
> On Fri, 8 Jun 2012, Will Deacon wrote:
> 
> > This patch implements the word-at-a-time interface for ARM using the
> > same algorithm as x86. Although we have a clz instruction from ARMv5,
> > this only saves us one mov instruction when building with Thumb-2 and
> > makes no difference when targetting ARM, so we use the magic 0x0ff0001
> > constant for all CPUs. For big-endian configurations, we use the
> > implementation from asm-generic.
> > 
> > With this implemented, we can replace our byte-at-a-time strnlen_user
> > and strncpy_from_user functions with the optimised generic versions.
> > 
> > Signed-off-by: Will Deacon <will.deacon@arm.com>
> 
> With the updated patch comment...
> 
> Reviewed-by: Nicolas Pitre <nico@linaro.org>

Thanks Nicolas. I'll post a v2 with the updated change log and your
reviewed-bys. I may also CC lkml in case somebody over there has some
better benchmarks for this stuff.

Cheers,

Will

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Uwe Kleine-König]

Hello,

On Fri, Jun 08, 2012 at 04:38:54PM +0100, Will Deacon wrote:
> This patch implements the word-at-a-time interface for ARM using the
> same algorithm as x86. Although we have a clz instruction from ARMv5,
> this only saves us one mov instruction when building with Thumb-2 and
> makes no difference when targetting ARM, so we use the magic 0x0ff0001
> constant for all CPUs. For big-endian configurations, we use the
> implementation from asm-generic.
> 
> With this implemented, we can replace our byte-at-a-time strnlen_user
> and strncpy_from_user functions with the optimised generic versions.
This patch is in Linus tree as 8c56cc8be5b38e3684eba96dc9b3f7ca7e495755
now and it broke my booting my Cortex-M3 machine. I didn't debug that
yet, but wanted to let you know already now before I call it a day.

> +#define user_addr_max() \
> +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> +
I think this is the problem as for no-mmu USER_DS == KERNEL_DS. I will
take a look tomorrow.

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Will Deacon]

On Tue, Oct 02, 2012 at 06:53:16PM +0100, Uwe Kleine-K?nig wrote:
> Hello,

Hi Uwe,

> On Fri, Jun 08, 2012 at 04:38:54PM +0100, Will Deacon wrote:
> > This patch implements the word-at-a-time interface for ARM using the
> > same algorithm as x86. Although we have a clz instruction from ARMv5,
> > this only saves us one mov instruction when building with Thumb-2 and
> > makes no difference when targetting ARM, so we use the magic 0x0ff0001
> > constant for all CPUs. For big-endian configurations, we use the
> > implementation from asm-generic.
> > 
> > With this implemented, we can replace our byte-at-a-time strnlen_user
> > and strncpy_from_user functions with the optimised generic versions.
> This patch is in Linus tree as 8c56cc8be5b38e3684eba96dc9b3f7ca7e495755
> now and it broke my booting my Cortex-M3 machine. I didn't debug that
> yet, but wanted to let you know already now before I call it a day.

Ok, thanks for the heads-up. I didn't test it with an M-class CPU, but
hopefully that's understandable :)

> > +#define user_addr_max() \
> > +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> > +
> I think this is the problem as for no-mmu USER_DS == KERNEL_DS. I will
> take a look tomorrow.

I can't immediately see why that would cause a problem, so please let me
know if you get more information.

Will

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Uwe Kleine-König]

Hi Will,

On Tue, Oct 02, 2012 at 08:18:51PM +0100, Will Deacon wrote:
> On Tue, Oct 02, 2012 at 06:53:16PM +0100, Uwe Kleine-K?nig wrote:
> > On Fri, Jun 08, 2012 at 04:38:54PM +0100, Will Deacon wrote:
> > > This patch implements the word-at-a-time interface for ARM using the
> > > same algorithm as x86. Although we have a clz instruction from ARMv5,
> > > this only saves us one mov instruction when building with Thumb-2 and
> > > makes no difference when targetting ARM, so we use the magic 0x0ff0001
> > > constant for all CPUs. For big-endian configurations, we use the
> > > implementation from asm-generic.
> > > 
> > > With this implemented, we can replace our byte-at-a-time strnlen_user
> > > and strncpy_from_user functions with the optimised generic versions.
> > This patch is in Linus tree as 8c56cc8be5b38e3684eba96dc9b3f7ca7e495755
> > now and it broke my booting my Cortex-M3 machine. I didn't debug that
> > yet, but wanted to let you know already now before I call it a day.
> 
> Ok, thanks for the heads-up. I didn't test it with an M-class CPU, but
> hopefully that's understandable :)
I think so, yes. But I intend to change that, and I heard your coworker
gets an efm32 :-)

> > > +#define user_addr_max() \
> > > +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> > > +
> > I think this is the problem as for no-mmu USER_DS == KERNEL_DS. I will
> > take a look tomorrow.
> 
> I can't immediately see why that would cause a problem, so please let me
> know if you get more information.
BTW, I once saw the call to sys_mount fail:

	sys_mount ->
	copy_mount_string ->
	strndup_user ->
	strnlen_user returns 0 which makes sys_mount fail with -EFAULT.

but that was not the problem I hit when I bisected (using merges instead
of rebasing).

We have a bank holiday today in Germany, so it's still tomorrow when I
will look into the problem. So I hope to be able to give more details
soon.

Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Will Deacon]

On Wed, Oct 03, 2012 at 07:00:42AM +0100, Uwe Kleine-K?nig wrote:
> On Tue, Oct 02, 2012 at 08:18:51PM +0100, Will Deacon wrote:
> > Ok, thanks for the heads-up. I didn't test it with an M-class CPU, but
> > hopefully that's understandable :)
>
> I think so, yes. But I intend to change that, and I heard your coworker
> gets an efm32 :-)

Yep, he'll be in charge of testing for us (!)

> > > > +#define user_addr_max() \
> > > > +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> > > > +
> > > I think this is the problem as for no-mmu USER_DS == KERNEL_DS. I will
> > > take a look tomorrow.
> > 
> > I can't immediately see why that would cause a problem, so please let me
> > know if you get more information.
> BTW, I once saw the call to sys_mount fail:
> 
> 	sys_mount ->
> 	copy_mount_string ->
> 	strndup_user ->
> 	strnlen_user returns 0 which makes sys_mount fail with -EFAULT.
> 
> but that was not the problem I hit when I bisected (using merges instead
> of rebasing).

Was this also on your M3?

> We have a bank holiday today in Germany, so it's still tomorrow when I
> will look into the problem. So I hope to be able to give more details
> soon.

Ok, have a good day off.

Will

[RFC PATCH 1/2] ARM: use generic strnlen_user and strncpy_from_user functions

[Uwe Kleine-König]

On Wed, Oct 03, 2012 at 10:16:36AM +0100, Will Deacon wrote:
> On Wed, Oct 03, 2012 at 07:00:42AM +0100, Uwe Kleine-K?nig wrote:
> > On Tue, Oct 02, 2012 at 08:18:51PM +0100, Will Deacon wrote:
> > > Ok, thanks for the heads-up. I didn't test it with an M-class CPU, but
> > > hopefully that's understandable :)
> >
> > I think so, yes. But I intend to change that, and I heard your coworker
> > gets an efm32 :-)
> 
> Yep, he'll be in charge of testing for us (!)
:-)

> > > > > +#define user_addr_max() \
> > > > > +	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
> > > > > +
> > > > I think this is the problem as for no-mmu USER_DS == KERNEL_DS. I will
> > > > take a look tomorrow.
> > > 
> > > I can't immediately see why that would cause a problem, so please let me
> > > know if you get more information.
> > BTW, I once saw the call to sys_mount fail:
> > 
> > 	sys_mount ->
> > 	copy_mount_string ->
> > 	strndup_user ->
> > 	strnlen_user returns 0 which makes sys_mount fail with -EFAULT.
> > 
> > but that was not the problem I hit when I bisected (using merges instead
> > of rebasing).
> 
> Was this also on your M3?
Yeah. I found a change that fixes it for me:

diff --git a/arch/arm/include/asm/uaccess.h b/arch/arm/include/asm/uaccess.h
index 77bd79f..7775e03 100644
--- a/arch/arm/include/asm/uaccess.h
+++ b/arch/arm/include/asm/uaccess.h
@@ -216,7 +216,7 @@ static inline void set_fs(mm_segment_t fs)
 #define access_ok(type,addr,size)	(__range_ok(addr,size) == 0)
 
 #define user_addr_max() \
-	(segment_eq(get_fs(), USER_DS) ? TASK_SIZE : ~0UL)
+	(segment_eq(get_fs(), KERNEL_DL) ? ~0UL : TASK_SIZE)
 
 /*
  * The "__xxx" versions of the user access functions do not verify the

I'm not sure if this has some security implications for the !MMU case!?
(But if so according to my understanding (which might well be wrong)
using TASK_SIZE isn't correct also. So this only widens the window, but
doesn't create it.)

On !MMU TASK_SIZE is CONFIG_DRAM_SIZE, but I'm using XIP and the flash
is at an higher address than RAM. So maybe XIP is broken on MMU
machines, too?

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |