From: Carlos O'Donell <carlos@redhat.com>
To: Noah Goldstein <goldstein.w.n@gmail.com>, libc-alpha@sourceware.org
Cc: hjl.tools@gmail.com, carlos@systemhalted.org
Subject: Re: [PATCH v1] x86: Prevent SIG11 in memcmp-sse2 when data is concurrently modified [BZ #29863]
Date: Tue, 13 Dec 2022 21:41:36 -0500 [thread overview]
Message-ID: <8dc9f68a-c736-0996-76f8-ab7aeb4ccc00@redhat.com> (raw)
In-Reply-To: <20221214001147.2814047-1-goldstein.w.n@gmail.com>
Please post a v2. Thanks!
Subject: x86: Prevent SIGSEGV in memcmp-sse2 when data is concurrently modified [BZ #29863]
Replaces SIG11 with SIGSEGV (the documented name of the signal).
On 12/13/22 19:11, Noah Goldstein via Libc-alpha wrote:
> In the case of INCORRECT usage of `memcmp(a, b, N)` where `a` and `b`
> are concurrently modified as `memcmp` runs, there can be a SIG11 in
s/SIG11/SIGSEGV/g
> `L(ret_nonzero_vec_end_0)` because the sequential logic assumes
> that `(rdx - 32 + rax)` is a positive 32-bit integer.
>
> To be clear, this "fix" does not mean this usage of `memcmp` is
> supported. `memcmp` is incorrect when the values of `a` and/or `b`
> are modified while its running, and that incorrectness may manifest
> itself as a SIG-11. That being said, if we can make the results
s/SIG-11/SIGSEGV/g
> less dramatic with no cost to regular uses cases, there is no harm
> in doing so.
I agree that a user focused change like this is going to be a balance between
keeping it working for an unsupported use case versus the cost to the library.
Given that you've found a low-cost way to support the incorrect but idiomatic
use case then I have no sustained objections to this patch. However, this won't
be the last we hear of this as we continue down the path of optimizing against
a well defined memory model.
> The fix replaces a 32-bit `addl %edx, %eax` with the 64-bit variant
> `addq %rdx, %rax`. The 1-extra byte of code size from using the
> 64-bit instruction doesn't contribute to overall code size as the
> next target is aligned and has multiple bytes of `nop` padding
> before it. As well all the logic between the add and `ret` still
> fits in the same fetch block, so the cost of this change is
> basically zero.
OK.
> The sequential logic makes the assume behind the following code:
Suggest:
The relevant sequential logic can be seen in the following code:
> ```
> /*
> * rsi = a
> * rdi = b
> * rdx = len - 32
> */
> /* cmp a[0:15] and b[0:15]. Since length is known to be [17, 32]
> in this case, this check is also assume to cover a[0:(31 - len)]
s/assume/assumed/g
> and b[0:(31 - len)]. */
> movups (%rsi), %xmm0
> movups (%rdi), %xmm1
> PCMPEQ %xmm0, %xmm1
> pmovmskb %xmm1, %eax
> subl %ecx, %eax
> jnz L(END_NEQ)
>
> /* cmp a[len-16:len-1] and b[len-16:len-1]. */
> movups 16(%rsi, %rdx), %xmm0
> movups 16(%rdi, %rdx), %xmm1
> PCMPEQ %xmm0, %xmm1
> pmovmskb %xmm1, %eax
> subl %ecx, %eax
> jnz L(END_NEQ2)
> ret
>
> L(END2):
> /* Position first mismatch. */
> bsfl %eax, %eax
>
> /* BUG IS FROM THIS. The sequential version is able to assume this
s/BUG IS FROM THIS. //g
> value is a positive 32-bit value because first check included
s/because first/because the first/g
> bytes in range a[0:(31 - len)], b[0:(31 - len)] so `eax` must be
s/,/ and/g
> greater than `31 - len` so the minimum value of `edx` + `eax` is
> `(len - 32) + (32 - len) >= 0`. In the concurrent case, however,
> `a` or `b` could have been changed so a mismatch in `eax` less or
> equal than `(31 - len)` is possible (the new low bound in `(16 -
s/in/is/g
> len)`. This can result in a negative 32-bit signed integer, which
> when non-sign extended to 64-bits is a random large value out of
s/out of/that is out of/g
> bounds. */
> addl %edx, %eax
>
> /* Crash here because 32-bit negative number in `eax` non-sign
> extends to out of bounds 64-bit offset. */
> movzbl 16(%rdi, %rax), %ecx
> movzbl 16(%rsi, %rax), %eax
> ```
>
> This fix is quite simple, just make the `addl %edx, %eax` 64 bit (i.e
> `addq %rdx, %rax`). This prevent the 32-bit non-sign extension
s/prevent/prevents/g
> and since `eax` still a low bound of `16 - len` the `rdx + rax`
s/still/is still/g
> is bound by `(len - 32) - (16 - len) >= -16`. Since we have a
> fixed offset of `16` in the memory access this must be inbounds.
s/inbounds/in bounds/g
> ---
> sysdeps/x86_64/multiarch/memcmp-sse2.S | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S
> index afd450d020..34e60e567d 100644
> --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S
> +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S
> @@ -308,7 +308,7 @@ L(ret_nonzero_vec_end_0):
> setg %dl
> leal -1(%rdx, %rdx), %eax
> # else
> - addl %edx, %eax
> + addq %rdx, %rax
OK. 64-bit addq.
> movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx
> movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax
> subl %ecx, %eax
--
Cheers,
Carlos.
next prev parent reply other threads:[~2022-12-14 2:42 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-12-14 0:11 Noah Goldstein
2022-12-14 2:41 ` Carlos O'Donell [this message]
2022-12-14 9:04 ` Andreas Schwab
2022-12-14 3:25 ` [PATCH v2] x86: Prevent SIGSEGV " Noah Goldstein
2022-12-14 4:42 ` Carlos O'Donell
2022-12-14 7:36 ` [PATCH v3] " Noah Goldstein
2022-12-14 16:09 ` H.J. Lu
2022-12-14 16:57 ` Carlos O'Donell
2022-12-14 17:18 ` Noah Goldstein
2022-12-14 18:52 ` Noah Goldstein
2022-12-14 16:57 ` Carlos O'Donell
2022-12-14 16:07 ` [PATCH v1] x86: Prevent SIG11 " H.J. Lu
2022-12-14 18:52 ` [PATCH v4] x86: Prevent SIGSEGV " Noah Goldstein
2022-12-14 21:35 ` H.J. Lu
2023-01-10 22:02 ` Sunil Pandey
2023-01-10 23:02 ` Noah Goldstein
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=8dc9f68a-c736-0996-76f8-ab7aeb4ccc00@redhat.com \
--to=carlos@redhat.com \
--cc=carlos@systemhalted.org \
--cc=goldstein.w.n@gmail.com \
--cc=hjl.tools@gmail.com \
--cc=libc-alpha@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).