[ARM] 2947/1: copy template with new memcpy/memmove

Patch from Nicolas Pitre

This patch provides a new implementation for optimized memory copy
functions on ARM.  It is made of two levels: a template that consists of
the core copy code and separate files that define macros to be used with
the core code depending on the type of copy needed. This allows for best
performances while sharing the same core for implementing memcpy(),
copy_from_user() and copy_to_user() for instance.

Two reasons for this work:

1) the current copy_to_user/copy_from_user implementation assumes no
   task switch will ever occur in the middle of each copied page making
   it completely unsafe with CONFIG_PREEMPT=y.

2) current copy implementations are measurably suboptimal and optimizing
   different implementations separately is a pain and more opportunities
   for bugs.

The reason for (1) is the fact that copy inside user pages are performed
with the ldm instruction which has no mean for testing user protections
and could possibly race with process preemption bypassing the COW mechanism
for example.  This is a longstanding issue that we said ought to be fixed
for about two years now.  The solution is to substitute those ldm insns
with a series of ldrt or strt insns to enforce user memory protection.
At least on StrongARM and XScale cores the ldm is not faster than the
equivalent ldr/str insns with a warm i-cache so there is no measurable
performance degradation with that change. The fact that the copy code is
a template makes it pretty easy to reuse the same core code as for memcpy
and benefit from the same performance optimizations.

Now (2) is best demonstrated with actual throughput measurements.
First, here is a summary of memcopy tests performed on a StrongARM core:

	PTR alignment	buffer size	kernel version	this version
	------------------------------------------------------------
	  aligned	     32		 59.73		107.43
	unaligned	     32		 61.31		 74.72
	  aligned	    100		132.47		136.15
	unaligned	    100	    	103.84		123.76
	  aligned	   4096		130.67		130.80
	unaligned	   4096	    	130.68		130.64
	  aligned	1048576		 68.03		68.18
	unaligned	1048576		 68.03		68.18

The buffer size is in bytes and the measured speed in MB/s.  The copy
was performed repeatedly with given buffer and throughput averaged over
3 seconds.

Here we can see that the current kernel version has a higher entry cost
that shows up with small buffers.  As buffer size grows both implementation
converge to the same throughput.

Now here's the exact same test performed on an XScale core (PXA255):

	PTR alignment	buffer size	kernel version	this version
	------------------------------------------------------------
	  aligned	     32		 46.99		 77.58
	unaligned	     32		 53.61		 59.59
	  aligned	    100		107.19		136.59
	unaligned	    100		 83.61		 97.58
	  aligned	   4096		129.13		129.98
	unaligned	   4096		128.36		128.53
	  aligned	1048576		 53.76		 59.41
	unaligned	1048576		 33.67		 56.96

Again we can see the entry setup cost being higher for the current kernel
before getting to the main copy loop.  Then throughput results converge
as long as the buffer remains in the cache. Then the 1MB case shows more
differences probably due to better pld placement and/or less instruction
interlocks in this proposed implementation.

Disclaimer: The PXA system was running with slower clocks than the
StrongARM system so trying to infer any conclusion by comparing those
separate sets of results side by side would be completely inappropriate.

So...  What this patch does is to replace both memcpy and memmove with
an implementation based on the provided copy code template.  The memmove
code is kept separate since it is used only if the memory areas involved
do overlap in which case the code is a transposition of the template but
with the copy occurring in the opposite direction (trying to fit that
mode into the template turned it into a mess not worth it for memmove
alone).  And obviously both memcpy and memmove were tested with all kinds
of pointer alignments and buffer sizes to exercise all code paths for
correctness.

The next patch will provide the now trivial replacement implementation
copy_to_user and copy_from_user.

Signed-off-by: Nicolas Pitre <nico@cam.org>
Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>

1 files changed, 38 insertions, 372 deletions

diff --git a/arch/arm/lib/memcpy.S b/arch/arm/lib/memcpy.S
index f5a593c..7e71d67 100644
--- a/arch/arm/lib/memcpy.S
+++ b/arch/arm/lib/memcpy.S
@@ -1,393 +1,59 @@
 /*
  *  linux/arch/arm/lib/memcpy.S
  *
- *  Copyright (C) 1995-1999 Russell King
+ *  Author:	Nicolas Pitre
+ *  Created:	Sep 28, 2005
+ *  Copyright:	MontaVista Software, Inc.
  *
- * 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.
- *
- *  ASM optimised string functions
+ *  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>
 
-		.text
-
-#define ENTER	\
-		mov	ip,sp	;\
-		stmfd	sp!,{r0,r4-r9,fp,ip,lr,pc}	;\
-		sub	fp,ip,#4
-
-#define EXIT	\
-		LOADREGS(ea, fp, {r0, r4 - r9, fp, sp, pc})
-
-#define EXITEQ	\
-		LOADREGS(eqea, fp, {r0, r4 - r9, fp, sp, pc})
-
-/*
- * Prototype: void memcpy(void *to,const void *from,unsigned long n);
- */
-ENTRY(memcpy)
-ENTRY(memmove)
-		ENTER
-		cmp	r1, r0
-		bcc	23f
-		subs	r2, r2, #4
-		blt	6f
-	PLD(	pld	[r1, #0]		)
-		ands	ip, r0, #3
-		bne	7f
-		ands	ip, r1, #3
-		bne	8f
+	.macro ldr1w ptr reg abort
+	ldr \reg, [\ptr], #4
+	.endm
 
-1:		subs	r2, r2, #8
-		blt	5f
-		subs	r2, r2, #20
-		blt	4f
-	PLD(	pld	[r1, #28]		)
-	PLD(	subs	r2, r2, #64		)
-	PLD(	blt	3f			)
-2:	PLD(	pld	[r1, #60]		)
-	PLD(	pld	[r1, #92]		)
-		ldmia	r1!, {r3 - r9, ip}
-		subs	r2, r2, #32
-		stmgeia	r0!, {r3 - r9, ip}
-		ldmgeia	r1!, {r3 - r9, ip}
-		subges	r2, r2, #32
-		stmia	r0!, {r3 - r9, ip}
-		bge	2b
-3:	PLD(	ldmia	r1!, {r3 - r9, ip}	)
-	PLD(	adds	r2, r2, #32		)
-	PLD(	stmgeia	r0!, {r3 - r9, ip}	)
-	PLD(	ldmgeia	r1!, {r3 - r9, ip}	)
-	PLD(	subges	r2, r2, #32		)
-	PLD(	stmia	r0!, {r3 - r9, ip}	)
-4:		cmn	r2, #16
-		ldmgeia	r1!, {r3 - r6}
-		subge	r2, r2, #16
-		stmgeia	r0!, {r3 - r6}
-		adds	r2, r2, #20
-		ldmgeia	r1!, {r3 - r5}
-		subge	r2, r2, #12
-		stmgeia	r0!, {r3 - r5}
-5:		adds	r2, r2, #8
-		blt	6f
-		subs	r2, r2, #4
-		ldrlt	r3, [r1], #4
-		ldmgeia	r1!, {r4, r5}
-		subge	r2, r2, #4
-		strlt	r3, [r0], #4
-		stmgeia	r0!, {r4, r5}
+	.macro ldr4w ptr reg1 reg2 reg3 reg4 abort
+	ldmia \ptr!, {\reg1, \reg2, \reg3, \reg4}
+	.endm
 
-6:		adds	r2, r2, #4
-		EXITEQ
-		cmp	r2, #2
-		ldrb	r3, [r1], #1
-		ldrgeb	r4, [r1], #1
-		ldrgtb	r5, [r1], #1
-		strb	r3, [r0], #1
-		strgeb	r4, [r0], #1
-		strgtb	r5, [r0], #1
-		EXIT
+	.macro ldr8w ptr reg1 reg2 reg3 reg4 reg5 reg6 reg7 reg8 abort
+	ldmia \ptr!, {\reg1, \reg2, \reg3, \reg4, \reg5, \reg6, \reg7, \reg8}
+	.endm
 
-7:		rsb	ip, ip, #4
-		cmp	ip, #2
-		ldrb	r3, [r1], #1
-		ldrgeb	r4, [r1], #1
-		ldrgtb	r5, [r1], #1
-		strb	r3, [r0], #1
-		strgeb	r4, [r0], #1
-		strgtb	r5, [r0], #1
-		subs	r2, r2, ip
-		blt	6b
-		ands	ip, r1, #3
-		beq	1b
+	.macro ldr1b ptr reg cond=al abort
+	ldr\cond\()b \reg, [\ptr], #1
+	.endm
 
-8:		bic	r1, r1, #3
-		ldr	r7, [r1], #4
-		cmp	ip, #2
-		bgt	18f
-		beq	13f
-		cmp	r2, #12
-		blt	11f
-	PLD(	pld	[r1, #12]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	10f			)
-	PLD(	pld	[r1, #28]		)
-9:	PLD(	pld	[r1, #44]		)
-10:		mov	r3, r7, pull #8
-		ldmia	r1!, {r4 - r7}
-		subs	r2, r2, #16
-		orr	r3, r3, r4, push #24
-		mov	r4, r4, pull #8
-		orr	r4, r4, r5, push #24
-		mov	r5, r5, pull #8
-		orr	r5, r5, r6, push #24
-		mov	r6, r6, pull #8
-		orr	r6, r6, r7, push #24
-		stmia	r0!, {r3 - r6}
-		bge	9b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	10b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	12f
-11:		mov	r3, r7, pull #8
-		ldr	r7, [r1], #4
-		subs	r2, r2, #4
-		orr	r3, r3, r7, push #24
-		str	r3, [r0], #4
-		bge	11b
-12:		sub	r1, r1, #3
-		b	6b
+	.macro str1w ptr reg abort
+	str \reg, [\ptr], #4
+	.endm
 
-13:		cmp	r2, #12
-		blt	16f
-	PLD(	pld	[r1, #12]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	15f			)
-	PLD(	pld	[r1, #28]		)
-14:	PLD(	pld	[r1, #44]		)
-15:		mov	r3, r7, pull #16
-		ldmia	r1!, {r4 - r7}
-		subs	r2, r2, #16
-		orr	r3, r3, r4, push #16
-		mov	r4, r4, pull #16
-		orr	r4, r4, r5, push #16
-		mov	r5, r5, pull #16
-		orr	r5, r5, r6, push #16
-		mov	r6, r6, pull #16
-		orr	r6, r6, r7, push #16
-		stmia	r0!, {r3 - r6}
-		bge	14b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	15b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	17f
-16:		mov	r3, r7, pull #16
-		ldr	r7, [r1], #4
-		subs	r2, r2, #4
-		orr	r3, r3, r7, push #16
-		str	r3, [r0], #4
-		bge	16b
-17:		sub	r1, r1, #2
-		b	6b
+	.macro str8w ptr reg1 reg2 reg3 reg4 reg5 reg6 reg7 reg8 abort
+	stmia \ptr!, {\reg1, \reg2, \reg3, \reg4, \reg5, \reg6, \reg7, \reg8}
+	.endm
 
-18:		cmp	r2, #12
-		blt	21f
-	PLD(	pld	[r1, #12]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	20f			)
-	PLD(	pld	[r1, #28]		)
-19:	PLD(	pld	[r1, #44]		)
-20:		mov	r3, r7, pull #24
-		ldmia	r1!, {r4 - r7}
-		subs	r2, r2, #16
-		orr	r3, r3, r4, push #8
-		mov	r4, r4, pull #24
-		orr	r4, r4, r5, push #8
-		mov	r5, r5, pull #24
-		orr	r5, r5, r6, push #8
-		mov	r6, r6, pull #24
-		orr	r6, r6, r7, push #8
-		stmia	r0!, {r3 - r6}
-		bge	19b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	20b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	22f
-21:		mov	r3, r7, pull #24
-		ldr	r7, [r1], #4
-		subs	r2, r2, #4
-		orr	r3, r3, r7, push #8
-		str	r3, [r0], #4
-		bge	21b
-22:		sub	r1, r1, #1
-		b	6b
+	.macro str1b ptr reg cond=al abort
+	str\cond\()b \reg, [\ptr], #1
+	.endm
 
+	.macro enter reg1 reg2
+	stmdb sp!, {r0, \reg1, \reg2}
+	.endm
 
-23:		add	r1, r1, r2
-		add	r0, r0, r2
-		subs	r2, r2, #4
-		blt	29f
-	PLD(	pld	[r1, #-4]		)
-		ands	ip, r0, #3
-		bne	30f
-		ands	ip, r1, #3
-		bne	31f
+	.macro exit reg1 reg2
+	ldmfd sp!, {r0, \reg1, \reg2}
+	.endm
 
-24:		subs	r2, r2, #8
-		blt	28f
-		subs	r2, r2, #20
-		blt	27f
-	PLD(	pld	[r1, #-32]		)
-	PLD(	subs	r2, r2, #64		)
-	PLD(	blt	26f			)
-25:	PLD(	pld	[r1, #-64]		)
-	PLD(	pld	[r1, #-96]		)
-		ldmdb	r1!, {r3 - r9, ip}
-		subs	r2, r2, #32
-		stmgedb	r0!, {r3 - r9, ip}
-		ldmgedb	r1!, {r3 - r9, ip}
-		subges	r2, r2, #32
-		stmdb	r0!, {r3 - r9, ip}
-		bge	25b
-26:	PLD(	ldmdb	r1!, {r3 - r9, ip}	)
-	PLD(	adds	r2, r2, #32		)
-	PLD(	stmgedb	r0!, {r3 - r9, ip}	)
-	PLD(	ldmgedb	r1!, {r3 - r9, ip}	)
-	PLD(	subges	r2, r2, #32		)
-	PLD(	stmdb	r0!, {r3 - r9, ip}	)
-27:		cmn	r2, #16
-		ldmgedb	r1!, {r3 - r6}
-		subge	r2, r2, #16
-		stmgedb	r0!, {r3 - r6}
-		adds	r2, r2, #20
-		ldmgedb	r1!, {r3 - r5}
-		subge	r2, r2, #12
-		stmgedb	r0!, {r3 - r5}
-28:		adds	r2, r2, #8
-		blt	29f
-		subs	r2, r2, #4
-		ldrlt	r3, [r1, #-4]!
-		ldmgedb	r1!, {r4, r5}
-		subge	r2, r2, #4
-		strlt	r3, [r0, #-4]!
-		stmgedb	r0!, {r4, r5}
+	.text
 
-29:		adds	r2, r2, #4
-		EXITEQ
-		cmp	r2, #2
-		ldrb	r3, [r1, #-1]!
-		ldrgeb	r4, [r1, #-1]!
-		ldrgtb	r5, [r1, #-1]!
-		strb	r3, [r0, #-1]!
-		strgeb	r4, [r0, #-1]!
-		strgtb	r5, [r0, #-1]!
-		EXIT
+/* Prototype: void *memcpy(void *dest, const void *src, size_t n); */
 
-30:		cmp	ip, #2
-		ldrb	r3, [r1, #-1]!
-		ldrgeb	r4, [r1, #-1]!
-		ldrgtb	r5, [r1, #-1]!
-		strb	r3, [r0, #-1]!
-		strgeb	r4, [r0, #-1]!
-		strgtb	r5, [r0, #-1]!
-		subs	r2, r2, ip
-		blt	29b
-		ands	ip, r1, #3
-		beq	24b
-
-31:		bic	r1, r1, #3
-		ldr	r3, [r1], #0
-		cmp	ip, #2
-		blt	41f
-		beq	36f
-		cmp	r2, #12
-		blt	34f
-	PLD(	pld	[r1, #-16]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	33f			)
-	PLD(	pld	[r1, #-32]		)
-32:	PLD(	pld	[r1, #-48]		)
-33:		mov	r7, r3, push #8
-		ldmdb	r1!, {r3, r4, r5, r6}
-		subs	r2, r2, #16
-		orr	r7, r7, r6, pull #24
-		mov	r6, r6, push #8
-		orr	r6, r6, r5, pull #24
-		mov	r5, r5, push #8
-		orr	r5, r5, r4, pull #24
-		mov	r4, r4, push #8
-		orr	r4, r4, r3, pull #24
-		stmdb	r0!, {r4, r5, r6, r7}
-		bge	32b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	33b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	35f
-34:		mov	ip, r3, push #8
-		ldr	r3, [r1, #-4]!
-		subs	r2, r2, #4
-		orr	ip, ip, r3, pull #24
-		str	ip, [r0, #-4]!
-		bge	34b
-35:		add	r1, r1, #3
-		b	29b
-
-36:		cmp	r2, #12
-		blt	39f
-	PLD(	pld	[r1, #-16]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	38f			)
-	PLD(	pld	[r1, #-32]		)
-37:	PLD(	pld	[r1, #-48]		)
-38:		mov	r7, r3, push #16
-		ldmdb	r1!, {r3, r4, r5, r6}
-		subs	r2, r2, #16
-		orr	r7, r7, r6, pull #16
-		mov	r6, r6, push #16
-		orr	r6, r6, r5, pull #16
-		mov	r5, r5, push #16
-		orr	r5, r5, r4, pull #16
-		mov	r4, r4, push #16
-		orr	r4, r4, r3, pull #16
-		stmdb	r0!, {r4, r5, r6, r7}
-		bge	37b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	38b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	40f
-39:		mov	ip, r3, push #16
-		ldr	r3, [r1, #-4]!
-		subs	r2, r2, #4
-		orr	ip, ip, r3, pull #16
-		str	ip, [r0, #-4]!
-		bge	39b
-40:		add	r1, r1, #2
-		b	29b
+ENTRY(memcpy)
 
-41:		cmp	r2, #12
-		blt	44f
-	PLD(	pld	[r1, #-16]		)
-		sub	r2, r2, #12
-	PLD(	subs	r2, r2, #32		)
-	PLD(	blt	43f			)
-	PLD(	pld	[r1, #-32]		)
-42:	PLD(	pld	[r1, #-48]		)
-43:		mov	r7, r3, push #24
-		ldmdb	r1!, {r3, r4, r5, r6}
-		subs	r2, r2, #16
-		orr	r7, r7, r6, pull #8
-		mov	r6, r6, push #24
-		orr	r6, r6, r5, pull #8
-		mov	r5, r5, push #24
-		orr	r5, r5, r4, pull #8
-		mov	r4, r4, push #24
-		orr	r4, r4, r3, pull #8
-		stmdb	r0!, {r4, r5, r6, r7}
-		bge	42b
-	PLD(	cmn	r2, #32			)
-	PLD(	bge	43b			)
-	PLD(	add	r2, r2, #32		)
-		adds	r2, r2, #12
-		blt	45f
-44:		mov	ip, r3, push #24
-		ldr	r3, [r1, #-4]!
-		subs	r2, r2, #4
-		orr	ip, ip, r3, pull #8
-		str	ip, [r0, #-4]!
-		bge	44b
-45:		add	r1, r1, #1
-		b	29b
+#include "copy_template.S"