linux-kernel - Re: [RFC PATCH v1 3/5] tools/nolibc: x86-64: Use `rep cmpsb` for `memcmp()`

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ZPGSYKJeSlk4y7tE@biznet-home.integral.gnuweeb.org>
Date:   Fri, 1 Sep 2023 14:27:28 +0700
From:   Ammar Faizi <ammarfaizi2@...weeb.org>
To:     Willy Tarreau <w@....eu>
Cc:     Thomas Weißschuh <linux@...ssschuh.net>,
        Nicholas Rosenberg <inori@...x.org>,
        Alviro Iskandar Setiawan <alviro.iskandar@...weeb.org>,
        Michael William Jonathan <moe@...weeb.org>,
        GNU/Weeb Mailing List <gwml@...r.gnuweeb.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
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