Subject: Re: memcpy and prefetch

From: Ralf Baechle <[email-masked]>
Date: Wed, 4 Feb 2009 21:27:46 +0000

On Thu, Jan 29, 2009 at 10:39:37PM -0500, David VomLehn (dvomlehn) wrote:

> > The idea here is that we have two issues with prefetching:
> > 
> >  o Prefetching beyond the end of the source or destination range on a
> >    in-coherent range might bring back stale values from a DMA I/O
> >    buffer resulting in data corruption.  Hardware DMA coherency will
> >    avoid this issue.
> > 
> >  o IP27 has full blown hardware coherency.  Historically 
> > CONFIG_DMA_COHERENT
> >    was not able to cope with something of the complexity of IP27, so
> >    there was a separate CONFIG_DMA_IP27 and the broken logic 
> > expression
> >    was meant to treat CONFIG_DMA_COHERENT and CONFIG_DMA_IP27 the same
> >    as for prefetching.
> > 
> >  o Prefetching beyond the end of physical memory can cause 
> > exceptions on
> >    some systems.  The Malta has this problem.
> > 
> > Thus no prefetching on Malta or non-coherent systems.

> It seems to me as though we could avoid the first and third problems
> with a memcpy that doesn't prefetch past the end of the buffer, the
> thought being that if we are reading or writing a memory region, we
> really shouldn't be doing DMA to or from that location. This would
> probably be slightly suboptimal, performance-wise, for those systems
> that do have DMA coherence. It seems as though we could have two
> mutually exclusive versions, selectable via the CONFIG_DMA_COHERENT
> flag. For those of us without DMA coherence, it would probably give our
> memcpy performance a bit of a kick in the pants over using no prefetch
> at all.

Unnecessary prefetching can come at a high cost due to memory latencies
and cache pollution.  So you want to avoid unnecessary prefetches rather
than hoping for hardware cache coherency to sorts out the mess software
left behind.

The general expectation is that prefetching will help - but depending on
the pipeline structure prefetching can be hard to exploit optimally.  For
example there are MIPS cores were the optimal sequence is something like

  load store load store load store load store

But on others it's

  load load load load store store store store

Placing prefetching instructions into loops built from such blocks can
result in very surprising result.

> If this makes sense, we might be able to sign up to do the work. Anyone
> have a good, caching-aware memcpy test?

Testing memcpy is an interesting little project.  Correctness is one
thing but a good implementation needs to do a few performance tradeoffs
which are best meassure with real world, not synthetic workloads.

  Ralf

---

From: Atsushi Nemoto <[email-masked]>
Date: Fri, 06 Feb 2009 00:31:13 +0900 (JST)

> which are best meassure with real world, not synthetic workloads.

For correctness test, drivers/dma/dmatest.c might be a good template.

For speed test, test_cipher_speed in crypt/tcrypt.c can be used as a
template.  Attached is a test module I wrote based on it, when I
implemented an asm version of csum_partial_copy_nocheck, etc.  It will
show something like this:

# insmod /tmp/testspeed.ko mode=1

testing speed of csum_partial_copy_nocheck
test 0 (32 byte): 2051560 operations in 1 seconds (65649920 bytes)
test 1 (96 byte): 823512 operations in 1 seconds (79057152 bytes)
test 2 (256 byte): 329124 operations in 1 seconds (84255744 bytes)
test 3 (512 byte): 167739 operations in 1 seconds (85882368 bytes)
...
testing speed of gen_csum_partial_copy_nocheck
test 0 (32 byte): 1555953 operations in 1 seconds (49790496 bytes)
test 1 (96 byte): 700025 operations in 1 seconds (67202400 bytes)
test 2 (256 byte): 293716 operations in 1 seconds (75191296 bytes)
test 3 (512 byte): 151770 operations in 1 seconds (77706240 bytes)
...
insmod: error inserting '/tmp/testspeed.ko': -1 Resource temporarily unavailable

Feel free to hack it ;)

/*
 * Quick & dirty speed testing module.  (Based on tcrypt).
 *
 * This file is subject to the terms and conditions of the GNU General Public
 * License.  See the file "COPYING" in the main directory of this archive
 * for more details.
 */

#include <linux/init.h>
#include <linux/module.h>
#include <linux/mm.h>
#include <linux/slab.h>
#include <linux/moduleparam.h>
#include <linux/jiffies.h>
#include <net/checksum.h>

static unsigned int sec = 1;
static int mode;

/* non-optimized version of csum_partial_copy_nocheck */
static unsigned int gen_csum_partial_copy_nocheck(const void *src,
	void *dst, int len, unsigned int sum)
{
	sum = csum_partial(src, len, sum);
	memcpy(dst, src, len);
	return sum;
}

/* non-optimized version of csum_partial_copy_from_user */
static unsigned int gen_csum_partial_copy_from_user(const void __user *src,
	void *dst, int len, unsigned int sum, int *err_ptr)
{
	might_sleep();
	if (__copy_from_user(dst, src, len))
		*err_ptr = -EFAULT;
	return csum_partial(dst, len, sum);
}

#define loop_while_sec(start, end, sec, count) \
	for (start = jiffies, end = start + sec * HZ, count = 0; \
	     time_before(jiffies, end); count++)

static int test_csum_partial_copy_speed(int cachemiss)
{
	unsigned long start, end;
	unsigned int i;
	void *src, *dst;
	size_t sizes[] = {
		0x20, 0x60, 0x100, 0x200, 0x400,
		1460, /* ETH_DATA_LEN - 20(ip header) - 20(tcp header) */
		0x800, 0x1000,
	};
	size_t maxsize = sizes[ARRAY_SIZE(sizes) - 1];
	int ofs;
	int count;
	int err;
	int bufsize = 0x10000;

	src = kmalloc(bufsize, GFP_KERNEL);
	if (!src)
		return -ENOMEM;
	dst = kmalloc(bufsize, GFP_KERNEL);
	if (!dst) {
		kfree(src);
		return -ENOMEM;
	}
	memset(src, 0xff, maxsize);

	printk("\ntesting speed of csum_partial_copy_nocheck\n");

	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
		printk("test %u (%d byte): ", i, sizes[i]);

		ofs = 0;
		loop_while_sec(start, end, sec, count) {
			csum_partial_copy_nocheck(src + ofs, dst + ofs,
						  sizes[i], 0);
			if (cachemiss) {
				ofs += sizes[i];
				if (ofs + sizes[i] > bufsize)
					ofs = 0;
			}
		}

		printk("%d operations in %d seconds (%d bytes)\n",
		       count, sec, count * sizes[i]);
	}

	printk("\ntesting speed of csum_partial_copy_from_user\n");

	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
		printk("test %u (%d byte): ", i, sizes[i]);

		ofs = 0;
		loop_while_sec(start, end, sec, count) {
			csum_partial_copy_from_user((const void __force __user *)src + ofs,
						    dst + ofs,
						    sizes[i], 0, &err);
			if (cachemiss) {
				ofs += sizes[i];
				if (ofs + sizes[i] > bufsize)
					ofs = 0;
			}
		}

		printk("%d operations in %d seconds (%d bytes)\n",
		       count, sec, count * sizes[i]);
	}

	printk("\ntesting speed of gen_csum_partial_copy_nocheck\n");

	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
		printk("test %u (%d byte): ", i, sizes[i]);

		ofs = 0;
		loop_while_sec(start, end, sec, count) {
			gen_csum_partial_copy_nocheck(src + ofs, dst + ofs,
						      sizes[i], 0);
			if (cachemiss) {
				ofs += sizes[i];
				if (ofs + sizes[i] > bufsize)
					ofs = 0;
			}
		}

		printk("%d operations in %d seconds (%d bytes)\n",
		       count, sec, count * sizes[i]);
	}

	printk("\ntesting speed of gen_csum_partial_copy_from_user\n");

	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
		printk("test %u (%d byte): ", i, sizes[i]);

		ofs = 0;
		loop_while_sec(start, end, sec, count) {
			gen_csum_partial_copy_from_user((const void __force __user *)src + ofs,
							dst + ofs,
							sizes[i], 0, &err);
			if (cachemiss) {
				ofs += sizes[i];
				if (ofs + sizes[i] > bufsize)
					ofs = 0;
			}
		}

		printk("%d operations in %d seconds (%d bytes)\n",
		       count, sec, count * sizes[i]);
	}

	kfree(src);
	kfree(dst);
	return 0;
}

static int __init init(void)
{
	int ret = 0;
	switch (mode) {
	case 0:
		ret = test_csum_partial_copy_speed(0);
		break;
	case 1:
		ret = test_csum_partial_copy_speed(1);
		break;
	}
	if (ret)
		return ret;

	/* We intentionaly return -EAGAIN to prevent keeping the module. */
	return -EAGAIN;
}

static void __exit fini(void) {}

module_init(init);
module_exit(fini);

module_param(mode, int, 0);
module_param(sec, uint, 0);
MODULE_PARM_DESC(sec, "Length in seconds of speed tests (default 1)");

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Quick & dirty speed testing module");