gcc_qsort: avoid overlapping memcpy (PR 86311)

Message ID alpine.LNX.2.20.13.1806251724040.2272@monopod.intra.ispras.ru
State New
Headers show
Series
  • gcc_qsort: avoid overlapping memcpy (PR 86311)
Related show

Commit Message

Alexander Monakov June 25, 2018, 2:44 p.m.
Hi,

In PR 86311 Valgrind flags a call to memcpy with overlapping buffers. This can
happen in reorder{23,45} helpers when we're reordering in-place, and the 3rd/5th
element doesn't need to be moved: in that case the middle memcpy is called
with source == destination.

The fix is simple: just use a temporary, just like for other elements.

I'm a bit surprised at this though: when I looked, gcc turned those fixed-size
memcpy calls to MEMs even at -O0, so Valgrind wouldn't see them.

Bootstrapped on x86_64, OK to apply?

Thanks.
Alexander

	PR middle-end/86311
	* sort.cc (REORDER_23): Avoid memcpy with same destination and source.
	(REORDER_45): Likewise.

Comments

Alexander Monakov June 25, 2018, 2:52 p.m. | #1
On Mon, 25 Jun 2018, Alexander Monakov wrote:
> 

> In PR 86311 Valgrind flags a call to memcpy with overlapping buffers. This can

> happen in reorder{23,45} helpers when we're reordering in-place, and the 3rd/5th

> element doesn't need to be moved: in that case the middle memcpy is called

> with source == destination.

> 

> The fix is simple: just use a temporary, just like for other elements.


Sigh - I see GCC optimizes memmove as well as memcpy in this case, so changing
the offending memcpy calls to memmoves would be a bit cleaner. OK to go with
this instead?

Alexander
Richard Biener June 25, 2018, 4:31 p.m. | #2
On June 25, 2018 4:52:43 PM GMT+02:00, Alexander Monakov <amonakov@ispras.ru> wrote:
>On Mon, 25 Jun 2018, Alexander Monakov wrote:

>> 

>> In PR 86311 Valgrind flags a call to memcpy with overlapping buffers.

>This can

>> happen in reorder{23,45} helpers when we're reordering in-place, and

>the 3rd/5th

>> element doesn't need to be moved: in that case the middle memcpy is

>called

>> with source == destination.

>> 

>> The fix is simple: just use a temporary, just like for other

>elements.

>

>Sigh - I see GCC optimizes memmove as well as memcpy in this case, so

>changing

>the offending memcpy calls to memmoves would be a bit cleaner. OK to go

>with

>this instead?


I think that's better. Or conditionalizing the offending ones on dest! = src? 

Richard. 

>Alexander
Alexander Monakov June 25, 2018, 4:59 p.m. | #3
On Mon, 25 Jun 2018, Richard Biener wrote:
>> Sigh - I see GCC optimizes memmove as well as memcpy in this case, so

>> changing the offending memcpy calls to memmoves would be a bit cleaner. OK to

>> go with this instead?

> 

> I think that's better. Or conditionalizing the offending ones on dest! = src? 


That would work, but would require an extra comparison ('c->n == 3' test would
need to be kept) and also would introduce a poorly-predictable branch depending
on comparator outcomes - something the design of gcc_qsort strives to avoid in
the first place.

This is the patch I'm going to apply.

	PR middle-end/86311
	* sort.cc (REORDER_23): Avoid memcpy with same destination and source.
	(REORDER_45): Likewise.

diff --git a/gcc/sort.cc b/gcc/sort.cc
index a48a477d4e8..293e2058f89 100644
--- a/gcc/sort.cc
+++ b/gcc/sort.cc
@@ -69,7 +69,7 @@ do {                                                     \
   memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
   char *out = c->out + OFFSET;                           \
   if (likely (c->n == 3))                                \
-    memcpy (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE)); \
+    memmove (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE));\
   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t1, sizeof (TYPE));                      \
 } while (0)
@@ -101,7 +101,7 @@ do {                                                     \
   memcpy (&t3, e3 + OFFSET, sizeof (TYPE));              \
   char *out = c->out + OFFSET;                           \
   if (likely (c->n == 5))                                \
-    memcpy (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE)); \
+    memmove (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE));\
   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t1, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t2, sizeof (TYPE)); out += STRIDE;       \

Patch

diff --git a/gcc/sort.cc b/gcc/sort.cc
index a48a477d4e8..baabc39044f 100644
--- a/gcc/sort.cc
+++ b/gcc/sort.cc
@@ -64,12 +64,15 @@  reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
 {
 #define REORDER_23(TYPE, STRIDE, OFFSET)                 \
 do {                                                     \
-  TYPE t0, t1;                                           \
+  TYPE t0, t1, t2;                                       \
   memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
   memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
   char *out = c->out + OFFSET;                           \
   if (likely (c->n == 3))                                \
-    memcpy (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE)); \
+    {                                                    \
+      memcpy (&t2, e2 + OFFSET, sizeof (TYPE));          \
+      memcpy (out + 2*STRIDE, &t2, sizeof (TYPE));       \
+    }                                                    \
   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t1, sizeof (TYPE));                      \
 } while (0)
@@ -94,14 +97,17 @@  reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
 {
 #define REORDER_45(TYPE, STRIDE, OFFSET)                 \
 do {                                                     \
-  TYPE t0, t1, t2, t3;                                   \
+  TYPE t0, t1, t2, t3, t4;                               \
   memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
   memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
   memcpy (&t2, e2 + OFFSET, sizeof (TYPE));              \
   memcpy (&t3, e3 + OFFSET, sizeof (TYPE));              \
   char *out = c->out + OFFSET;                           \
   if (likely (c->n == 5))                                \
-    memcpy (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE)); \
+    {                                                    \
+      memcpy (&t4, e4 + OFFSET, sizeof (TYPE));          \
+      memcpy (out + 4*STRIDE, &t4, sizeof (TYPE));       \
+    }                                                    \
   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t1, sizeof (TYPE)); out += STRIDE;       \
   memcpy (out, &t2, sizeof (TYPE)); out += STRIDE;       \