Prefetches in memcpy

Prefetches in memcpy

[Carsten Langgaard]

I have reported this before and it also gave a lot of responses, but
nothing has been done about, unfortunately :-(

The problem is the prefetches in the memcpy function in the kernel.
There is spread a number of PREF instructions in the memcpy function,
but there is no check if we are prefetching out-side the areas we are
copying to/from. This is extremely dangerous because we might prefetch
out-side the physical memory area, causing e.g. a bus error or something
even more nasty.

I recently found something even nastier, it could also hit a DMA buffer
region, and thereby break the PCI DMA flushing scheme.
For example if the kernel is doing a memcpy from an area that's next to
a DMA buffer area, we could end up in a situation where, we are
prefetching
data into the cache from a memory location that is used for DMA transfer
and owned by the device, but the DMA transfer has not yet completed.
We then end up in a situation, where the memory and cache is out of sync
and the cache is containing some old data.

So we definitely need to do something about the prefetches in the memcpy
function.
We can either get rid of all the prefetches or make sure we don't
prefetch out side the "memcpy" area.

/Carsten



--
_    _ ____  ___   Carsten Langgaard   Mailto:carstenl@mips.com
|\  /|||___)(___   MIPS Denmark        Direct: +45 4486 5527
| \/ |||    ____)  Lautrupvang 4B      Switch: +45 4486 5555
  TECHNOLOGIES     2750 Ballerup       Fax...: +45 4486 5556
                   Denmark             http://www.mips.com

Re: Prefetches in memcpy

[Ralf Baechle]

On Tue, Nov 05, 2002 at 02:45:47PM +0100, Carsten Langgaard wrote:

> The problem is the prefetches in the memcpy function in the kernel.
> There is spread a number of PREF instructions in the memcpy function,
> but there is no check if we are prefetching out-side the areas we are
> copying to/from. This is extremely dangerous because we might prefetch
> out-side the physical memory area, causing e.g. a bus error or something
> even more nasty.
> 
> I recently found something even nastier, it could also hit a DMA buffer
> region, and thereby break the PCI DMA flushing scheme.
> For example if the kernel is doing a memcpy from an area that's next to
> a DMA buffer area, we could end up in a situation where, we are
> prefetching
> data into the cache from a memory location that is used for DMA transfer
> and owned by the device, but the DMA transfer has not yet completed.
> We then end up in a situation, where the memory and cache is out of sync
> and the cache is containing some old data.
> 
> So we definitely need to do something about the prefetches in the memcpy
> function.  We can either get rid of all the prefetches or make sure we
> don't prefetch out side the "memcpy" area.

We could fix the prefetch into DMA buffer problem with an extra flush but
that's going to be expensive, I rather think we should avoid prefetches.
As Kevin explained KSEG1 is a loophole in the spec so we can't really say
what the behaviour of memcpy will be in KSEG1.

So I think the fix will have to be:

 - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
 - Introduce a second variant of memcpy that never does prefetching.  This
   one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
   for memcpy_fromio, memcpy_toio and friends.

  Ralf

Re: Prefetches in memcpy

[Kevin D. Kissell]

From: "Ralf Baechle" <ralf@uni-koblenz.de>
> So I think the fix will have to be:
> 
>  - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
>  - Introduce a second variant of memcpy that never does prefetching.  This
>    one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
>    for memcpy_fromio, memcpy_toio and friends.

Assuming we had a version that prefetched exactly to the end
of the source memory block and no further, why would we need
the second variant?

            Kevin K.

Re: Prefetches in memcpy

[Kevin D. Kissell]

From: "Ralf Baechle" <ralf@uni-koblenz.de>
> So I think the fix will have to be:
> 
>  - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
>  - Introduce a second variant of memcpy that never does prefetching.  This
>    one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
>    for memcpy_fromio, memcpy_toio and friends.

Assuming we had a version that prefetched exactly to the end
of the source memory block and no further, why would we need
the second variant?

            Kevin K.

Re: Prefetches in memcpy

[Ralf Baechle]

On Tue, Nov 05, 2002 at 05:13:48PM +0100, Kevin D. Kissell wrote:

> >  - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
> >  - Introduce a second variant of memcpy that never does prefetching.  This
> >    one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
> >    for memcpy_fromio, memcpy_toio and friends.
> 
> Assuming we had a version that prefetched exactly to the end
> of the source memory block and no further, why would we need
> the second variant?

Because the source of memcpy_fromio and the destination of memcpy_toio are
some I/O address, typically something like a shared memory region on a
network card, which is accessed uncached.  The uncached address region
might be mapped in KSEG2/KSEG3 or accessed through an uncached region of
XKPHYS or KSEG1 where as I recall your statment the effect of prefetch
instructions is undefined.

  Ralf

Re: Prefetches in memcpy

[Ralf Baechle]

On Tue, Nov 05, 2002 at 05:13:48PM +0100, Kevin D. Kissell wrote:

> >  - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
> >  - Introduce a second variant of memcpy that never does prefetching.  This
> >    one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
> >    for memcpy_fromio, memcpy_toio and friends.
> 
> Assuming we had a version that prefetched exactly to the end
> of the source memory block and no further, why would we need
> the second variant?

Uh...  Maybe missread your mail the first time.  We're also prefechting
the destination area, of course with a different hint.  The question is
what the hints for destination are actually doing, the specs are fairly
vague on that and seem to leave the decission to the implementor.  Do
we really want to try ...

  Ralf

Re: Prefetches in memcpy

[Alan Cox]

On Tue, 2002-11-05 at 16:13, Kevin D. Kissell wrote:
> Assuming we had a version that prefetched exactly to the end
> of the source memory block and no further, why would we need
> the second variant?

memcpy_to/from_io needs to do strictly ordered fetches on some devices
which fake a memory range with a fifo for performance (pci bursting
dirty tricks)

Re: Prefetches in memcpy

[Carsten Langgaard]

I would like to open this thread again, since nothing has been done about it.
I think we should get rid of the prefetches until someone comes up with a
version that doesn't prefetch beyond the copy destination/source area.

/Carsten


Ralf Baechle wrote:

> On Tue, Nov 05, 2002 at 02:45:47PM +0100, Carsten Langgaard wrote:
>
> > The problem is the prefetches in the memcpy function in the kernel.
> > There is spread a number of PREF instructions in the memcpy function,
> > but there is no check if we are prefetching out-side the areas we are
> > copying to/from. This is extremely dangerous because we might prefetch
> > out-side the physical memory area, causing e.g. a bus error or something
> > even more nasty.
> >
> > I recently found something even nastier, it could also hit a DMA buffer
> > region, and thereby break the PCI DMA flushing scheme.
> > For example if the kernel is doing a memcpy from an area that's next to
> > a DMA buffer area, we could end up in a situation where, we are
> > prefetching
> > data into the cache from a memory location that is used for DMA transfer
> > and owned by the device, but the DMA transfer has not yet completed.
> > We then end up in a situation, where the memory and cache is out of sync
> > and the cache is containing some old data.
> >
> > So we definitely need to do something about the prefetches in the memcpy
> > function.  We can either get rid of all the prefetches or make sure we
> > don't prefetch out side the "memcpy" area.
>
> We could fix the prefetch into DMA buffer problem with an extra flush but
> that's going to be expensive, I rather think we should avoid prefetches.
> As Kevin explained KSEG1 is a loophole in the spec so we can't really say
> what the behaviour of memcpy will be in KSEG1.
>
> So I think the fix will have to be:
>
>  - Avoid prefetching beyond the end of the copy area in memcpy and memmove.
>  - Introduce a second variant of memcpy that never does prefetching.  This
>    one will be safe to use in KSEG1 / uncached XKPHYS also and will be used
>    for memcpy_fromio, memcpy_toio and friends.
>
>   Ralf

--
_    _ ____  ___   Carsten Langgaard   Mailto:carstenl@mips.com
|\  /|||___)(___   MIPS Denmark        Direct: +45 4486 5527
| \/ |||    ____)  Lautrupvang 4B      Switch: +45 4486 5555
  TECHNOLOGIES     2750 Ballerup       Fax...: +45 4486 5556
                   Denmark             http://www.mips.com

Re: Prefetches in memcpy

[Dominic Sweetman]

Carsten,

> I think we should get rid of the prefetches until someone comes up with a
> version that doesn't prefetch beyond the copy destination/source area.

I agree.

--
Dominic

Re: Prefetches in memcpy

[Carsten Langgaard]

[-- Attachment #1: Type: text/plain, Size: 604 bytes --]

Here's what I think we should do for now (attached patch).

/Carsten


Dominic Sweetman wrote:

> Carsten,
>
> > I think we should get rid of the prefetches until someone comes up with a
> > version that doesn't prefetch beyond the copy destination/source area.
>
> I agree.
>
> --
> Dominic

--
_    _ ____  ___   Carsten Langgaard   Mailto:carstenl@mips.com
|\  /|||___)(___   MIPS Denmark        Direct: +45 4486 5527
| \/ |||    ____)  Lautrupvang 4B      Switch: +45 4486 5555
  TECHNOLOGIES     2750 Ballerup       Fax...: +45 4486 5556
                   Denmark             http://www.mips.com



[-- Attachment #2: memcpy.patch --]
[-- Type: text/plain, Size: 1770 bytes --]

Index: arch/mips/lib/memcpy.S
===================================================================
RCS file: /home/cvs/linux/arch/mips/lib/memcpy.S,v
retrieving revision 1.6.2.4
diff -u -r1.6.2.4 memcpy.S
--- arch/mips/lib/memcpy.S	19 Sep 2002 14:01:24 -0000	1.6.2.4
+++ arch/mips/lib/memcpy.S	5 Dec 2002 15:06:58 -0000
@@ -21,6 +21,17 @@
 #define src a1
 #define len a2
 
+/* 
+ * There is spread a number of PREF instructions in the memcpy function, but 
+ * there is no check if we are prefetching out-side the "memcpy" areas. 
+ * This is extremely dangerous because we might prefetch out-side the physical
+ * memory area causing e.g. a bus error or something even more nasty. 
+ * It could also hit a DMA buffer region, and there by break the PCI DMA 
+ * flushing scheme.
+ * So for now, we simply get rid of the PREFs here.
+ */
+#define PREF(hint,addr)
+	
 /*
  * Spec
  *
Index: arch/mips64/lib/memcpy.S
===================================================================
RCS file: /home/cvs/linux/arch/mips64/lib/memcpy.S,v
retrieving revision 1.9.2.3
diff -u -r1.9.2.3 memcpy.S
--- arch/mips64/lib/memcpy.S	19 Sep 2002 14:01:24 -0000	1.9.2.3
+++ arch/mips64/lib/memcpy.S	5 Dec 2002 15:06:59 -0000
@@ -21,6 +21,17 @@
 #define src a1
 #define len a2
 
+/* 
+ * There is spread a number of PREF instructions in the memcpy function, but 
+ * there is no check if we are prefetching out-side the "memcpy" areas. 
+ * This is extremely dangerous because we might prefetch out-side the physical
+ * memory area causing e.g. a bus error or something even more nasty. 
+ * It could also hit a DMA buffer region, and there by break the PCI DMA 
+ * flushing scheme.
+ * So for now, we simply get rid of the PREFs here.
+ */
+#define PREF(hint,addr)
+	
 /*
  * Spec
  *

Re: Prefetches in memcpy

[Maciej W. Rozycki]

On Thu, 5 Dec 2002, Carsten Langgaard wrote:

> Here's what I think we should do for now (attached patch).

 Obviously you want to #undef them first...

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: macro@ds2.pg.gda.pl, PGP key available        +

RE: Prefetches in memcpy

[Gilad]

As someone rather new to this list, and to mips-linux in general,
can someone explain the problem, as well as how one can avoid 
it or limit it's effects to a minimum ?

TIA

Re: Prefetches in memcpy

[Kevin D. Kissell]

> As someone rather new to this list, and to mips-linux in general,
> can someone explain the problem, as well as how one can avoid 
> it or limit it's effects to a minimum ?

The problem is that memcpy() uses prefetch to pre-load the
cache from the copy source, but does so very naively, such
that it continues prefetching beyond the end of the block to
be copied.  This is a Bad Idea for a couple of reasons.
The first to be commented upon was the fact that it can
result in bus hangs/bus errors if the kernel is trying to copy
from the last few hundred bytes of physical memory, but 
the really nasty one is that it screws up cache coherence
for DMA I/O.

The no-brainer solution which has been proposed as a
stopgap is simply to stop doing prefetch in memcpy()
altogether.  The "correct" solution would be to have a
slightly more complex memcpy() loop which only does
prefetch up to the end of the source block, which is
what is now done in the x86 port.

Re: Prefetches in memcpy

[Kevin D. Kissell]

> As someone rather new to this list, and to mips-linux in general,
> can someone explain the problem, as well as how one can avoid 
> it or limit it's effects to a minimum ?

The problem is that memcpy() uses prefetch to pre-load the
cache from the copy source, but does so very naively, such
that it continues prefetching beyond the end of the block to
be copied.  This is a Bad Idea for a couple of reasons.
The first to be commented upon was the fact that it can
result in bus hangs/bus errors if the kernel is trying to copy
from the last few hundred bytes of physical memory, but 
the really nasty one is that it screws up cache coherence
for DMA I/O.

The no-brainer solution which has been proposed as a
stopgap is simply to stop doing prefetch in memcpy()
altogether.  The "correct" solution would be to have a
slightly more complex memcpy() loop which only does
prefetch up to the end of the source block, which is
what is now done in the x86 port.