| 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: <YpJQoxUt9RhKb0Pr@geo.homenetwork>
Date: Sun, 29 May 2022 00:41:07 +0800
From: Tao Zhou <tao.zhou@...ux.dev>
To: Yu-Jen Chang <arthurchang09@...il.com>, tao.zhou@...ux.dev
Cc: ak@...ux.intel.com, jdike@...ux.intel.com, tglx@...utronix.de,
mingo@...hat.com, bp@...en8.de, dave.hansen@...ux.intel.com,
x86@...nel.org, hpa@...or.com, keescook@...omium.org,
linux-kernel@...r.kernel.org, linux-hardening@...r.kernel.org,
richard@....at, anton.ivanov@...bridgegreys.com,
johannes@...solutions.net, linux-um@...ts.infradead.org,
jserv@...s.ncku.edu.tw
Subject: Re: [PATCH 1/2] x86/lib: Optimize memchr()
On Sat, May 28, 2022 at 04:12:35PM +0800, Yu-Jen Chang wrote:
> The original assembly version of memchr() is implemented with
> the byte-wise comparing technique, which does not fully
> use 64-bits registers in x86_64 CPU. We use word-wide
> comparing so that 8 characters can be compared at the same time
> on x86_64 CPU. First we align the input and then use word-wise
> comparing to find the first 64-bit word that contain the target.
> Secondly, we compare every byte in the word and get the output.
>
> We create two files to measure the performance. The first file
> contains on average 10 characters ahead the target character.
> The second file contains at least 1000 characters ahead the
> target character. Our implementation of “memchr()” is slightly
> better in the first test and nearly 4x faster than the orginal
> implementation in the second test.
>
> Signed-off-by: Yu-Jen Chang <arthurchang09@...il.com>
> Signed-off-by: Ching-Chun (Jim) Huang <jserv@...s.ncku.edu.tw>
> ---
> arch/x86/include/asm/string_64.h | 3 ++
> arch/x86/lib/Makefile | 1 +
> arch/x86/lib/string_64.c | 78 ++++++++++++++++++++++++++++++++
> 3 files changed, 82 insertions(+)
> create mode 100644 arch/x86/lib/string_64.c
>
> diff --git a/arch/x86/include/asm/string_64.h b/arch/x86/include/asm/string_64.h
> index 6e450827f..edce657e0 100644
> --- a/arch/x86/include/asm/string_64.h
> +++ b/arch/x86/include/asm/string_64.h
> @@ -14,6 +14,9 @@
> extern void *memcpy(void *to, const void *from, size_t len);
> extern void *__memcpy(void *to, const void *from, size_t len);
>
> +#define __HAVE_ARCH_MEMCHR
> +extern void *memchr(const void *cs, int c, size_t length);
> +
> #define __HAVE_ARCH_MEMSET
> void *memset(void *s, int c, size_t n);
> void *__memset(void *s, int c, size_t n);
> diff --git a/arch/x86/lib/Makefile b/arch/x86/lib/Makefile
> index f76747862..4d530e559 100644
> --- a/arch/x86/lib/Makefile
> +++ b/arch/x86/lib/Makefile
> @@ -69,5 +69,6 @@ else
> lib-y += clear_page_64.o copy_page_64.o
> lib-y += memmove_64.o memset_64.o
> lib-y += copy_user_64.o
> + lib-y += string_64.o
> lib-y += cmpxchg16b_emu.o
> endif
> diff --git a/arch/x86/lib/string_64.c b/arch/x86/lib/string_64.c
> new file mode 100644
> index 000000000..4e067d5be
> --- /dev/null
> +++ b/arch/x86/lib/string_64.c
> @@ -0,0 +1,78 @@
> +// SPDX-License-Identifier: GPL-2.0
> +#include <linux/string.h>
> +#include <linux/export.h>
> +#include <linux/align.h>
> +
> +/* How many bytes are loaded each iteration of the word copy loop */
> +#define LBLOCKSIZE (sizeof(long))
> +
> +#ifdef __HAVE_ARCH_MEMCHR
> +
> +void *memchr(const void *cs, int c, size_t length)
> +{
> + const unsigned char *src = (const unsigned char *)cs, d = c;
I don't know why this 'd = c' is not error.
d is a char pointer and c is int. At least this is not safe me do not know.
> + while (!IS_ALIGNED((long)src, sizeof(long))) {
> + if (!length--)
> + return NULL;
> + if (*src == d)
Compare a character value to a pointer value and this value is c.
May be right do not know.
Or:
char d = c;
...
> + return (void *)src;
> + src++;
> + }
> + if (length >= LBLOCKSIZE) {
> + unsigned long mask = d << 8 | d;
> + unsigned int i = 32;
> + long xor, data;
> + const long consta = 0xFEFEFEFEFEFEFEFF,
> + constb = 0x8080808080808080;
Two magic number..
> + /*
> + * Create a 8-bytes mask for word-wise comparing.
> + * For example, a mask for 'a' is 0x6161616161616161.
> + */
> +
> + mask |= mask << 16;
> + for (i = 32; i < LBLOCKSIZE * 8; i <<= 1)
> + mask |= mask << i;
> + /*
> + * We perform word-wise comparing with following operation:
> + * 1. Perform xor on the long word @src and @mask
> + * and put into @xor.
> + * 2. Add @xor with @consta.
> + * 3. ~@xor & @constb.
> + * 4. Perform & with the result of step 2 and 3.
> + *
> + * Step 1 creates a byte which is 0 in the long word if
> + * there is at least one target byte in it.
> + *
> + * Step 2 to Step 4 find if there is a byte with 0 in
> + * the long word.
> + */
> + asm volatile("1:\n\t"
> + "movq (%0),%1\n\t"
> + "xorq %6,%1\n\t"
> + "lea (%1,%4), %2\n\t"
> + "notq %1\n\t"
> + "andq %5,%1\n\t"
> + "testq %1,%2\n\t"
> + "jne 2f\n\t"
s/jne/jnz/
Lack much here from me. But I give example that should check the
CF flag is zero.
1) contain matching byte.
1111111011111111(consta)
+add
0000000001101100(xor)
------------------------
1111111101101011 (%1)
1111111110010100(~xor)
&and
1000000010000000(constb)
------------------------
1000000010000000 (%2)
the logical and of %1 and %2 is
1000000000000000 that is not zero.
2) not contain matching byte
1111111011111111
+
0110111011011100
----------------
0110110111011011(%1)
1001000100100011
&
1000000010000000
----------------
1000000000000000(%2)
%1 and %2 is
0000000000000000 that is zero.
I guess that here should use jump instruction jnz instead.
Even though, I do not know why that two magic number is so magical..
Thanks,
Tao
> + "add $8,%0\n\t"
> + "sub $8,%3\n\t"
> + "cmp $7,%3\n\t"
> + "ja 1b\n\t"
> + "2:\n\t"
> + : "=D"(src), "=r"(xor), "=r"(data), "=r"(length)
> + : "r"(consta), "r"(constb), "r"(mask), "0"(src),
> + "1"(xor), "2"(data), "3"(length)
> + : "memory", "cc");
> + }
> +
> + while (length--) {
> + if (*src == d)
> + return (void *)src;
> + src++;
> + }
> + return NULL;
> +}
> +EXPORT_SYMBOL(memchr);
> +#endif
> --
> 2.25.1
>
Powered by blists - more mailing lists