Message ID | 20221214185210.2930992-1-goldstein.w.n@gmail.com |
---|---|
State | New |
Headers | show |
Series | [v4] x86: Prevent SIGSEGV in memcmp-sse2 when data is concurrently modified [BZ #29863] | expand |
On Wed, Dec 14, 2022 at 10:52 AM Noah Goldstein <goldstein.w.n@gmail.com> 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 SIGSEGV > in `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 change does not mean the usage of `memcmp` is > supported. The program behaviour is undefined (UB) in the > presence of data races, and `memcmp` is incorrect when the values > of `a` and/or `b` are modified concurrently (data race). This UB > may manifest itself as a SIGSEGV. That being said, if we can > allow the idiomatic use cases, like those in yottadb with > opportunistic concurrency control (OCC), to execute without a > SIGSEGV, at no cost to regular use cases, then we can aim to > minimize harm to those existing users. > > 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. > > The relevant sequential logic can be seen in the following > pseudo-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 assumed to cover a[0:(31 - len)] > 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 > > /* The sequential version is able to assume this value is a > positive 32-bit value because the first check included bytes in > range a[0:(31 - len)] and b[0:(31 - len)] so `eax` must be > 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 is `(16 - > len)`. This can result in a negative 32-bit signed integer, which > when zero extended to 64-bits is a random large value this out > out of bounds. */ > addl %edx, %eax > > /* Crash here because 32-bit negative number in `eax` zero > 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 prevents the 32-bit zero extension > and since `eax` is still a low bound of `16 - len` the `rdx + rax` > is bound by `(len - 32) - (16 - len) >= -16`. Since we have a > fixed offset of `16` in the memory access this must be in bounds. > --- > sysdeps/x86_64/multiarch/memcmp-sse2.S | 12 +++++++++++- > 1 file changed, 11 insertions(+), 1 deletion(-) > > diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S > index afd450d020..51bc9344f0 100644 > --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S > +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S > @@ -308,7 +308,17 @@ L(ret_nonzero_vec_end_0): > setg %dl > leal -1(%rdx, %rdx), %eax > # else > - addl %edx, %eax > + /* Use `addq` instead of `addl` here so that even if `rax` + `rdx` > + is negative value of the sum will be usable as a 64-bit offset > + (negative 32-bit numbers zero-extend to a large and often > + out-of-bounds 64-bit offsets). Note that `rax` + `rdx` >= 0 is > + an invariant when `memcmp` is used correctly, but if the input > + strings `rsi`/`rdi` are concurrently modified as the function > + runs (there is a Data-Race) it is possible for `rax` + `rdx` to > + be negative. Given that there is virtually no extra to cost > + using `addq` instead of `addl` we may as well protect the > + data-race case. */ > + addq %rdx, %rax > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > subl %ecx, %eax > -- > 2.34.1 > LGTM. Thanks.
On Wed, Dec 14, 2022 at 1:36 PM H.J. Lu via Libc-alpha <libc-alpha@sourceware.org> wrote: > > On Wed, Dec 14, 2022 at 10:52 AM Noah Goldstein <goldstein.w.n@gmail.com> 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 SIGSEGV > > in `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 change does not mean the usage of `memcmp` is > > supported. The program behaviour is undefined (UB) in the > > presence of data races, and `memcmp` is incorrect when the values > > of `a` and/or `b` are modified concurrently (data race). This UB > > may manifest itself as a SIGSEGV. That being said, if we can > > allow the idiomatic use cases, like those in yottadb with > > opportunistic concurrency control (OCC), to execute without a > > SIGSEGV, at no cost to regular use cases, then we can aim to > > minimize harm to those existing users. > > > > 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. > > > > The relevant sequential logic can be seen in the following > > pseudo-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 assumed to cover a[0:(31 - len)] > > 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 > > > > /* The sequential version is able to assume this value is a > > positive 32-bit value because the first check included bytes in > > range a[0:(31 - len)] and b[0:(31 - len)] so `eax` must be > > 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 is `(16 - > > len)`. This can result in a negative 32-bit signed integer, which > > when zero extended to 64-bits is a random large value this out > > out of bounds. */ > > addl %edx, %eax > > > > /* Crash here because 32-bit negative number in `eax` zero > > 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 prevents the 32-bit zero extension > > and since `eax` is still a low bound of `16 - len` the `rdx + rax` > > is bound by `(len - 32) - (16 - len) >= -16`. Since we have a > > fixed offset of `16` in the memory access this must be in bounds. > > --- > > sysdeps/x86_64/multiarch/memcmp-sse2.S | 12 +++++++++++- > > 1 file changed, 11 insertions(+), 1 deletion(-) > > > > diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > index afd450d020..51bc9344f0 100644 > > --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S > > +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > @@ -308,7 +308,17 @@ L(ret_nonzero_vec_end_0): > > setg %dl > > leal -1(%rdx, %rdx), %eax > > # else > > - addl %edx, %eax > > + /* Use `addq` instead of `addl` here so that even if `rax` + `rdx` > > + is negative value of the sum will be usable as a 64-bit offset > > + (negative 32-bit numbers zero-extend to a large and often > > + out-of-bounds 64-bit offsets). Note that `rax` + `rdx` >= 0 is > > + an invariant when `memcmp` is used correctly, but if the input > > + strings `rsi`/`rdi` are concurrently modified as the function > > + runs (there is a Data-Race) it is possible for `rax` + `rdx` to > > + be negative. Given that there is virtually no extra to cost > > + using `addq` instead of `addl` we may as well protect the > > + data-race case. */ > > + addq %rdx, %rax > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > > subl %ecx, %eax > > -- > > 2.34.1 > > > > LGTM. > > Thanks. > > -- > H.J. I would like to backport this patch to release branches. Any comments or objections? --Sunil
On Tue, Jan 10, 2023 at 2:03 PM Sunil Pandey <skpgkp2@gmail.com> wrote: > > On Wed, Dec 14, 2022 at 1:36 PM H.J. Lu via Libc-alpha > <libc-alpha@sourceware.org> wrote: > > > > On Wed, Dec 14, 2022 at 10:52 AM Noah Goldstein <goldstein.w.n@gmail.com> 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 SIGSEGV > > > in `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 change does not mean the usage of `memcmp` is > > > supported. The program behaviour is undefined (UB) in the > > > presence of data races, and `memcmp` is incorrect when the values > > > of `a` and/or `b` are modified concurrently (data race). This UB > > > may manifest itself as a SIGSEGV. That being said, if we can > > > allow the idiomatic use cases, like those in yottadb with > > > opportunistic concurrency control (OCC), to execute without a > > > SIGSEGV, at no cost to regular use cases, then we can aim to > > > minimize harm to those existing users. > > > > > > 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. > > > > > > The relevant sequential logic can be seen in the following > > > pseudo-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 assumed to cover a[0:(31 - len)] > > > 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 > > > > > > /* The sequential version is able to assume this value is a > > > positive 32-bit value because the first check included bytes in > > > range a[0:(31 - len)] and b[0:(31 - len)] so `eax` must be > > > 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 is `(16 - > > > len)`. This can result in a negative 32-bit signed integer, which > > > when zero extended to 64-bits is a random large value this out > > > out of bounds. */ > > > addl %edx, %eax > > > > > > /* Crash here because 32-bit negative number in `eax` zero > > > 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 prevents the 32-bit zero extension > > > and since `eax` is still a low bound of `16 - len` the `rdx + rax` > > > is bound by `(len - 32) - (16 - len) >= -16`. Since we have a > > > fixed offset of `16` in the memory access this must be in bounds. > > > --- > > > sysdeps/x86_64/multiarch/memcmp-sse2.S | 12 +++++++++++- > > > 1 file changed, 11 insertions(+), 1 deletion(-) > > > > > > diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > > index afd450d020..51bc9344f0 100644 > > > --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S > > > +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S > > > @@ -308,7 +308,17 @@ L(ret_nonzero_vec_end_0): > > > setg %dl > > > leal -1(%rdx, %rdx), %eax > > > # else > > > - addl %edx, %eax > > > + /* Use `addq` instead of `addl` here so that even if `rax` + `rdx` > > > + is negative value of the sum will be usable as a 64-bit offset > > > + (negative 32-bit numbers zero-extend to a large and often > > > + out-of-bounds 64-bit offsets). Note that `rax` + `rdx` >= 0 is > > > + an invariant when `memcmp` is used correctly, but if the input > > > + strings `rsi`/`rdi` are concurrently modified as the function > > > + runs (there is a Data-Race) it is possible for `rax` + `rdx` to > > > + be negative. Given that there is virtually no extra to cost > > > + using `addq` instead of `addl` we may as well protect the > > > + data-race case. */ > > > + addq %rdx, %rax > > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx > > > movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax > > > subl %ecx, %eax > > > -- > > > 2.34.1 > > > > > > > LGTM. > > > > Thanks. > > > > -- > > H.J. > > I would like to backport this patch to release branches. > Any comments or objections? Fine by me. > > --Sunil
diff --git a/sysdeps/x86_64/multiarch/memcmp-sse2.S b/sysdeps/x86_64/multiarch/memcmp-sse2.S index afd450d020..51bc9344f0 100644 --- a/sysdeps/x86_64/multiarch/memcmp-sse2.S +++ b/sysdeps/x86_64/multiarch/memcmp-sse2.S @@ -308,7 +308,17 @@ L(ret_nonzero_vec_end_0): setg %dl leal -1(%rdx, %rdx), %eax # else - addl %edx, %eax + /* Use `addq` instead of `addl` here so that even if `rax` + `rdx` + is negative value of the sum will be usable as a 64-bit offset + (negative 32-bit numbers zero-extend to a large and often + out-of-bounds 64-bit offsets). Note that `rax` + `rdx` >= 0 is + an invariant when `memcmp` is used correctly, but if the input + strings `rsi`/`rdi` are concurrently modified as the function + runs (there is a Data-Race) it is possible for `rax` + `rdx` to + be negative. Given that there is virtually no extra to cost + using `addq` instead of `addl` we may as well protect the + data-race case. */ + addq %rdx, %rax movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax subl %ecx, %eax