| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <1456957112-2702469-1-git-send-email-tom@herbertland.com>
Date: Wed, 2 Mar 2016 14:18:32 -0800
From: Tom Herbert <tom@...bertland.com>
To: <davem@...emloft.net>, <netdev@...r.kernel.org>
CC: <torvalds@...ux-foundation.org>, <tglx@...utronix.de>,
<mingo@...hat.com>, <hpa@...or.com>, <x86@...nel.org>,
<kernel-team@...com>
Subject: [PATCH v5 net-next] net: Implement fast csum_partial for x86_64
This patch implements performant csum_partial for x86_64. The intent is
to speed up checksum calculation, particularly for smaller lengths such
as those that are present when doing skb_postpull_rcsum when getting
CHECKSUM_COMPLETE from device or after CHECKSUM_UNNECESSARY conversion.
- v4
- went back to C code with inline assembly for critical routines
- implemented suggestion from Linus to deal with lengths < 8
- v5
- fixed register attribute add32_with_carry3
- do_csum returns unsigned long
- don't consider alignment at all. Rationalization is that x86
handles unaligned accesses very well except in the case that
the access crosses a page boundary which has a performance
penalty (I see about 10nsecs on my system). Drivers and the
stack go to considerable lengths to not have packets cross page
boundaries, so the case that csum_partial is called with
buffer that crosses a page boundary should be a very rare
occurrence. Not dealing with alignment is a significant
simplification.
Testing:
Correctness:
Verified correctness by testing arbitrary length buffer filled with
random data. For each buffer I compared the computed checksum
using the original algorithm for each possible alignment (0-7 bytes).
Performance:
Isolating old and new implementation for some common cases:
Old New %
Len/Aln nsecs nsecs Improv
--------+-------+--------+-------
1400/0 195.6 181.7 3% (Big packet)
40/0 11.8 6.5 45% (Ipv6 hdr cmn case)
8/4 8.1 3.2 60% (UDP, VXLAN in IPv4)
14/0 8.9 6.3 29% (Eth hdr)
14/4 9.5 6.3 33% (Eth hdr in IPv4)
14/3 9.6 6.3 34% (Eth with odd align)
20/0 9.1 6.8 25% (IP hdr without options)
7/1 9.1 3.9 57% (buffer in one quad)
100/0 17.4 13.6 21% (medium-sized pkt)
100/2 17.7 13.5 24% (medium-sized pkt w/ alignment)
Results from: Intel(R) Xeon(R) CPU X5650 @ 2.67GHz
Also tested on these with similar results:
Intel(R) Xeon(R) CPU E5-2660 v2 @ 2.20GHz
Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
Intel(R) Atom(TM) CPU N450 @ 1.66GHz
Branch prediction:
To test the effects of poor branch prediction in the jump tables I
tested checksum performance with runs for two combinations of length
and alignment. As the baseline I performed the test by doing half of
calls with the first combination, followed by using the second
combination for the second half. In the test case, I interleave the
two combinations so that in every call the length and alignment are
different to defeat the effects of branch prediction. Running several
cases, I did not see any material performance difference between the
two scenarios (perf stat output is below), neither does either case
show a significant number of branch misses.
Interleave lengths case:
perf stat --repeat 10 -e '{instructions, branches, branch-misses}' \
./csum -M new-thrash -I -l 100 -S 24 -a 1 -c 100000000
Performance counter stats for './csum -M new-thrash -I -l 100 -S 24 -a 1 -c 100000000' (10 runs):
9,556,693,202 instructions ( +- 0.00% )
1,176,208,640 branches ( +- 0.00% )
19,487 branch-misses # 0.00% of all branches ( +- 6.07% )
2.049732539 seconds time elapsed
Non-interleave case:
perf stat --repeat 10 -e '{instructions, branches, branch-misses}' \
./csum -M new-thrash -l 100 -S 24 -a 1 -c 100000000
Performance counter stats for './csum -M new-thrash -l 100 -S 24 -a 1 -c 100000000' (10 runs):
9,782,188,310 instructions ( +- 0.00% )
1,251,286,958 branches ( +- 0.01% )
18,950 branch-misses # 0.00% of all branches ( +- 12.74% )
2.271789046 seconds time elapsed
Signed-off-by: Tom Herbert <tom@...bertland.com>
---
arch/x86/include/asm/checksum_64.h | 21 +++++
arch/x86/lib/csum-partial_64.c | 171 ++++++++++++++++++-------------------
2 files changed, 102 insertions(+), 90 deletions(-)
diff --git a/arch/x86/include/asm/checksum_64.h b/arch/x86/include/asm/checksum_64.h
index cd00e17..1224f7d 100644
--- a/arch/x86/include/asm/checksum_64.h
+++ b/arch/x86/include/asm/checksum_64.h
@@ -188,6 +188,27 @@ static inline unsigned add32_with_carry(unsigned a, unsigned b)
return a;
}
+static inline unsigned long add64_with_carry(unsigned long a, unsigned long b)
+{
+ asm("addq %2,%0\n\t"
+ "adcq $0,%0"
+ : "=r" (a)
+ : "0" (a), "rm" (b));
+ return a;
+}
+
+static inline unsigned int add32_with_carry3(unsigned int a, unsigned int b,
+ unsigned int c)
+{
+ asm("addl %1,%0\n\t"
+ "adcl %2,%0\n\t"
+ "adcl $0,%0"
+ : "+r" (a)
+ : "rm" (b), "rm" (c));
+
+ return a;
+}
+
#define HAVE_ARCH_CSUM_ADD
static inline __wsum csum_add(__wsum csum, __wsum addend)
{
diff --git a/arch/x86/lib/csum-partial_64.c b/arch/x86/lib/csum-partial_64.c
index 9845371..7f1f60f 100644
--- a/arch/x86/lib/csum-partial_64.c
+++ b/arch/x86/lib/csum-partial_64.c
@@ -8,6 +8,7 @@
#include <linux/compiler.h>
#include <linux/module.h>
#include <asm/checksum.h>
+#include <asm/word-at-a-time.h>
static inline unsigned short from32to16(unsigned a)
{
@@ -21,99 +22,78 @@ static inline unsigned short from32to16(unsigned a)
/*
* Do a 64-bit checksum on an arbitrary memory area.
- * Returns a 32bit checksum.
+ * Returns a 64bit checksum.
*
- * This isn't as time critical as it used to be because many NICs
- * do hardware checksumming these days.
- *
- * Things tried and found to not make it faster:
- * Manual Prefetching
- * Unrolling to an 128 bytes inner loop.
- * Using interleaving with more registers to break the carry chains.
+ * This is optimized for small lengths such as might be common when pulling
+ * up checksums over protocol headers to handle CHECKSUM_COMPLETE (e.g.
+ * checksum over 40 bytes will be quite common for pulling up checksum over
+ * IPv6 headers).
*/
-static unsigned do_csum(const unsigned char *buff, unsigned len)
+static unsigned long do_csum(const void *buff, int len)
{
- unsigned odd, count;
unsigned long result = 0;
- if (unlikely(len == 0))
- return result;
- odd = 1 & (unsigned long) buff;
- if (unlikely(odd)) {
- result = *buff << 8;
- len--;
- buff++;
+ /* Check for less than a quad to sum */
+ if (len < 8) {
+ unsigned long val = load_unaligned_zeropad(buff);
+
+ return (val & ((1ul << len * 8) - 1));
+ }
+
+ /* Main loop using 64byte blocks */
+ for (; len > 64; len -= 64, buff += 64) {
+ asm("addq 0*8(%[src]),%[res]\n\t"
+ "adcq 1*8(%[src]),%[res]\n\t"
+ "adcq 2*8(%[src]),%[res]\n\t"
+ "adcq 3*8(%[src]),%[res]\n\t"
+ "adcq 4*8(%[src]),%[res]\n\t"
+ "adcq 5*8(%[src]),%[res]\n\t"
+ "adcq 6*8(%[src]),%[res]\n\t"
+ "adcq 7*8(%[src]),%[res]\n\t"
+ "adcq $0,%[res]"
+ : [res] "=r" (result)
+ : [src] "r" (buff),
+ "[res]" (result));
}
- count = len >> 1; /* nr of 16-bit words.. */
- if (count) {
- if (2 & (unsigned long) buff) {
- result += *(unsigned short *)buff;
- count--;
- len -= 2;
- buff += 2;
- }
- count >>= 1; /* nr of 32-bit words.. */
- if (count) {
- unsigned long zero;
- unsigned count64;
- if (4 & (unsigned long) buff) {
- result += *(unsigned int *) buff;
- count--;
- len -= 4;
- buff += 4;
- }
- count >>= 1; /* nr of 64-bit words.. */
- /* main loop using 64byte blocks */
- zero = 0;
- count64 = count >> 3;
- while (count64) {
- asm("addq 0*8(%[src]),%[res]\n\t"
- "adcq 1*8(%[src]),%[res]\n\t"
- "adcq 2*8(%[src]),%[res]\n\t"
- "adcq 3*8(%[src]),%[res]\n\t"
- "adcq 4*8(%[src]),%[res]\n\t"
- "adcq 5*8(%[src]),%[res]\n\t"
- "adcq 6*8(%[src]),%[res]\n\t"
- "adcq 7*8(%[src]),%[res]\n\t"
- "adcq %[zero],%[res]"
- : [res] "=r" (result)
- : [src] "r" (buff), [zero] "r" (zero),
- "[res]" (result));
- buff += 64;
- count64--;
- }
+ /*
+ * Sum over remaining quads (<= 8 of them). This uses a jump table
+ * based on number of quads to sum. The jump assumes that each case
+ * is 4 bytes. Each adcq instruction is 4 bytes except for adcq 0()
+ * which is 3 bytes, so a nop instruction is inserted to make that case
+ * 4 bytes.
+ */
+ asm("lea 0f(, %[slen], 4), %%r11\n\t"
+ "clc\n\t"
+ "jmpq *%%r11\n\t"
+ "adcq 7*8(%[src]),%[res]\n\t"
+ "adcq 6*8(%[src]),%[res]\n\t"
+ "adcq 5*8(%[src]),%[res]\n\t"
+ "adcq 4*8(%[src]),%[res]\n\t"
+ "adcq 3*8(%[src]),%[res]\n\t"
+ "adcq 2*8(%[src]),%[res]\n\t"
+ "adcq 1*8(%[src]),%[res]\n\t"
+ "adcq 0*8(%[src]),%[res]\n\t"
+ "nop\n\t"
+ "0: adcq $0,%[res]"
+ : [res] "=r" (result)
+ : [src] "r" (buff),
+ [slen] "r" (-(unsigned long)(len >> 3)), "[res]" (result)
+ : "r11");
- /* last up to 7 8byte blocks */
- count %= 8;
- while (count) {
- asm("addq %1,%0\n\t"
- "adcq %2,%0\n"
- : "=r" (result)
- : "m" (*(unsigned long *)buff),
- "r" (zero), "0" (result));
- --count;
- buff += 8;
- }
- result = add32_with_carry(result>>32,
- result&0xffffffff);
+ /* Sum over any remaining bytes (< 8 of them) */
+ if (len & 0x7) {
+ unsigned long val;
+ /*
+ * Since "len" is > 8 here we backtrack in the buffer to load
+ * the outstanding bytes into the low order bytes of a quad and
+ * then shift to extract the relevant bytes. By doing this we
+ * avoid additional calls to load_unaligned_zeropad.
+ */
- if (len & 4) {
- result += *(unsigned int *) buff;
- buff += 4;
- }
- }
- if (len & 2) {
- result += *(unsigned short *) buff;
- buff += 2;
- }
- }
- if (len & 1)
- result += *buff;
- result = add32_with_carry(result>>32, result & 0xffffffff);
- if (unlikely(odd)) {
- result = from32to16(result);
- result = ((result >> 8) & 0xff) | ((result & 0xff) << 8);
+ val = *(unsigned long *)(buff + len - 8);
+ val >>= 8 * (-len & 0x7);
+ result = add64_with_carry(val, result);
}
return result;
}
@@ -125,15 +105,26 @@ static unsigned do_csum(const unsigned char *buff, unsigned len)
* returns a 32-bit number suitable for feeding into itself
* or csum_tcpudp_magic
*
- * this function must be called with even lengths, except
- * for the last fragment, which may be odd
- *
- * it's best to have buff aligned on a 64-bit boundary
+ * Note that this implementation makes no attempt to avoid unaligned accesses
+ * (e.g. load a quad word with non 8-byte alignment). On x86 unaligned accesses
+ * only seem to be a performance penalty when the access crosses a page
+ * boundary-- such a scenario should be an extremely rare occurrence for use
+ * cases of csum_partial.
*/
__wsum csum_partial(const void *buff, int len, __wsum sum)
{
- return (__force __wsum)add32_with_carry(do_csum(buff, len),
- (__force u32)sum);
+ if (len == 8) {
+ /* Optimize trivial case */
+ return (__force __wsum)add32_with_carry3((__force u32)sum,
+ *(unsigned int *)buff,
+ *(unsigned int *)(buff + 4));
+ } else {
+ unsigned long result = do_csum(buff, len);
+
+ return (__force __wsum)add32_with_carry3((__force u32)sum,
+ result >> 32,
+ result & 0xffffffff);
+ }
}
/*
--
2.6.5
Powered by blists - more mailing lists