Subject: Bug in memmove

From: "Gleb O. Raiko" <[email-masked]>
Date: Wed, 06 Jun 2001 17:11:19 +0400

Hello,

It seems there is a bug in our memmove routine. The condition is rare
though, for example, memmove copies incorrectly, if src=5, dst=4, len=9.
I guess, exact condition is:

len > 8, 0 < src - dst < 8, src isn't aligned on qw (8 bytes), src - dst
!= 4

I may be wrong on exact condition, but at least the example works.

Briefly, memmove calls memcpy if src > dst. Then, when memcpy aligns src
on qw, it copies qw to dst. So, after src is aligned, it is overwritten
as well. In the example, memcpy copies qw at 4 (so, new data ends on
4+8=12), but aligned src is at address 8, so a word at address 8 is
overwritten.

Two questions here. First, do we have a pattern that satisfies the
condition, i.e. is the bug showstopper? My guess, it's not. Second, does
somebody have ideas how to fix the bug? Well, I have, but want to hear
somebody else.

Regards,
Gleb.

---

From: "Maciej W. Rozycki" <[email-masked]>
Date: Fri, 22 Jun 2001 20:21:30 +0200 (MET DST)

> though, for example, memmove copies incorrectly, if src=5, dst=4, len=9.
[...]
> somebody have ideas how to fix the bug? Well, I have, but want to hear

 Here is a quick fix I developed after reading your report.  It fixes the
case you described.  Now memcpy() is invoked only if there is no overlap
at all -- the approach is taken from the Alpha port. 

 The copy loop begs for optimization (the original memmove() bits do as
well), but at least it works correctly.  The patch applies cleanly to
2.4.5 as of today. 

 Ralf, I think it should get applied unless someone cooks up a better
solution, i.e. optimizes it.  I'll optimize it myself, eventually, if no
one else does, but don't hold your breath.

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: [email-masked], PGP key available        +

patch-mips-2.4.0-test12-20010110-memmove-1
diff -up --recursive --new-file linux-mips-2.4.0-test12-20010110.macro/arch/mips/lib/memcpy.S linux-mips-2.4.0-test12-20010110/arch/mips/lib/memcpy.S
--- linux-mips-2.4.0-test12-20010110.macro/arch/mips/lib/memcpy.S	Wed Dec  6 05:27:02 2000
+++ linux-mips-2.4.0-test12-20010110/arch/mips/lib/memcpy.S	Sun Jun 10 17:50:55 2001
@@ -402,16 +402,20 @@ u_end_bytes:
 
 	.align	5
 LEAF(memmove)
-	sltu	t0, a0, a1			# dst < src -> memcpy
-	bnez	t0, memcpy
-	 addu	v0, a0, a2
-	sltu	t0, v0, a1			# dst + len < src -> non-
-	bnez	t0, __memcpy			# overlapping, can use memcpy
+	addu	t0, a0, a2
+	sltu	t0, a1, t0			# dst + len <= src -> memcpy
+	addu	t1, a1, a2
+	sltu	t1, a0, t1			# dst >= src + len -> memcpy
+	and	t0, t1
+	beqz	t0, __memcpy
 	 move	v0, a0				/* return value */
 	beqz	a2, r_out
 	END(memmove)
 
 LEAF(__rmemcpy)					/* a0=dst a1=src a2=len */
+	sltu	t0, a1, a0
+	beqz	t0, r_end_bytes_up		# src >= dst
+	 nop
 	addu	a0, a2				# dst = dst + len
 	addu	a1, a2				# src = src + len
 
@@ -563,6 +567,17 @@ r_end_bytes:
 	 subu	a0, a0, 0x1
 
 r_out:
+	jr	ra
+	 move	a2, zero
+
+r_end_bytes_up:
+	lb	t0, (a1)
+	subu	a2, a2, 0x1
+	sb	t0, (a0)
+	addu	a1, a1, 0x1
+	bnez	a2, r_end_bytes_up
+	 addu	a0, a0, 0x1
+
 	jr	ra
 	 move	a2, zero

---

From: Ralf Baechle <[email-masked]>
Date: Sat, 23 Jun 2001 16:22:21 +0200

> one else does, but don't hold your breath.

Applied to my working tree.  I'll commit it in a few hours once I found
time to implement the same fix for 2.2 and mips64.

  Ralf

---

From: "Gleb O. Raiko" <[email-masked]>
Date: Mon, 25 Jun 2001 16:03:31 +0400

Maciej,

> one else does, but don't hold your breath.
Great! Optimized memmove is in todos of several MIPS developers.
Considering your patch and my investigation though, it's not
showstopper. In fact, there are a few places that call memmove, all of
them aren't on "common path". However, I would consider that common path
certainly depends on the way Linux is used. I may imagine the
configuration where the bug may trigger.

Perhaps, eliminating that known "horror fix" (you know) is more
important.

Regards,
Gleb.

---

From: "Maciej W. Rozycki" <[email-masked]>
Date: Mon, 25 Jun 2001 14:13:31 +0200 (MET DST)

> configuration where the bug may trigger.

 Note that the non-optimal code gets only invoked if the areas do really
overlap.

> Perhaps, eliminating that known "horror fix" (you know) is more

 Let's just let it remain in place until working optimization is done.