Messages in this thread | | | Date | Fri, 1 Sep 2023 14:27:28 +0700 | From | Ammar Faizi <> | Subject | Re: [RFC PATCH v1 3/5] tools/nolibc: x86-64: Use `rep cmpsb` for `memcmp()` |
| |
On Fri, Sep 01, 2023 at 05:35:08AM +0200, Willy Tarreau wrote: > On Fri, Sep 01, 2023 at 10:24:42AM +0700, Ammar Faizi wrote: > > After thinking about this more, I think I'll drop the memcmp() patch > > because it will prevent optimization when comparing a small value. > > > > For example, without __asm__: > > > > memcmp(var, "abcd", 4); > > > > may compile to: > > > > cmpl $0x64636261, %reg > > ...something... > > > > But with __asm__, the compiler can't do that. Thus, it's not worth > > optimizing the memcmp() in this case. > > Ah you're totally right!
So, it turns out that such assumption is wrong. The compiler cannot optimize the current memcmp() into that. I just posted a question on SO:
https://stackoverflow.com/questions/77020562/what-prevents-the-compiler-from-optimizing-a-hand-written-memcmp
Given: ``` bool test_data(void *data) { return memcmp(data, "abcd", 4) == 0; } ```
The result when using default the <string.h> memcmp (good): ``` test_data: cmpl $1684234849, (%rdi) sete %al ret ```
The result when using nolibc memcmp() (bad): ``` test_data: cmpb $97, (%rdi) jne .L5 cmpb $98, 1(%rdi) jne .L5 cmpb $99, 2(%rdi) jne .L5 cmpb $100, 3(%rdi) sete %al ret .L5: xorl %eax, %eax ret ```
Link: https://godbolt.org/z/TT94r3bvf
This is because apart from the input length, the current nolibc `memcmp()` must stop comparing the next byte if it finds a non-match byte. Imagine what happens if we call:
``` char xstr[] = {'a', 'b', 'x'}; test_data(x); ```
In that case, the compiler may read past xstr if it uses a dword cmp, it can also lead to segfault in particular circumstances using a dword cmp.
What the current nolibc memcmp() does from the C language view:
1) Compare one byte at a time. 2) Must stop comparing the next byte if it finds a non-match byte.
Because point (2) comes in, the compiler is not allowed to optimize nolibc memcmp() into a wider load; otherwise, it may hit a segfault. That also means it cannot vectorize the memcmp() loop.
On the other hand, memcpy() and memset() don't have such a restriction so they can vectorize.
The real memcmp() assumes that both sources are at least `n` length in size, allowing for a wider load. The current nolibc memcmp() implementation doesn't reflect that assumption in the C code.
IOW, the real built-in memcmp() is undefined behavior for this code: ``` char x = 'q'; return memcmp(&x, "abcd", 4); ``` but the current nolibc memcmp() is well-defined behavior (well, must be, as what the C code reflects).
We can improve nolibc memcmp() by casting the sources to a wider type like (ulong, uint, ushort). But that's another story for another RFC patchset.
-- Ammar Faizi
| |