Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Wilco Dijkstra]

Hi,

>On Tue, Dec 13, 2022, at 11:16 PM, Carlos O'Donell wrote:
>> The standards are in no way prescriptive in saying that memcmp shall not read or
>> write to memory outside of the input domain.
>
> ... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library function shall not directly or
> indirectly access objects accessible by threads other than the current thread unless the
> objects are accessed directly or indirectly via the function's arguments."  There is more
> wiggle room in this wording than I'd ideally like, but since memcmp has no way of knowing
> whether any particular piece of data outside the ranges supplied as arguments is "accessible
> by threads other than the current thread", it needs to be conservative and not touch any of it.

I'd expect that mem* functions will never read outside their bounds since the bounds are
explicitly defined by the arguments, not by the data. So that should be easy to guarantee.

For the str* functions it may be harder since the data itself defines when to stop reading.
So if an implementation uses multiple accesses to the same address, you could potentially
mistake the end of a string (eg. first one detects a special case, while the 2nd then verifies it).

Still, I wouldn't expect totally random memory accesses even in this case - you would read
beyond the end of a string if the string end is changed concurrently.

Note there is also a security risk here - an attacker could cause an out of bounds access
to extract secret data that otherwise wouldn't be accessible. Eg. functions in the Linux
kernel accessing user data should be resilient to concurrent modifications of the data.

Finally it's worth mentioning that nscd does the exact same thing: it uses memcmp and
non-atomic accesses on shared data that is being modified by other threads. It looks
totally broken, especially with weaker memory ordering, however this kind of insanity
may actually be a common design pattern...

Cheers,
Wilco

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

On Wed, 14 Dec 2022 16:56:28 -0500, Wilco Dijkstra wrote:
> I'd expect that mem* functions will never read outside their bounds
> since the bounds are explicitly defined by the arguments, not by the
> data. So that should be easy to guarantee.

I concur.

> For the str* functions it may be harder since the data itself
> defines when to stop reading.  So if an implementation uses multiple
> accesses to the same address, you could potentially mistake the end
> of a string (eg. first one detects a special case, while the 2nd
> then verifies it).

I also concur here.
 
> Still, I wouldn't expect totally random memory accesses even in this
> case - you would read beyond the end of a string if the string end
> is changed concurrently.

We may run into a problem where it’s difficult to _state_ the limits
of the misbehavior, just because the C standard doesn’t itself try to
put limits on misbehavior in the face of an incorrect program, so we
don’t have any language for it (which I would argue is a bug in the
standard, see the detailed reply to Carlos that I’ll be writing, er,
tomorrow).

Still, taking strcmp(a, b) for example, and assuming WLOG a flat
address space in which a < b, it should be possible to guarantee

 - no accesses to any byte in the range [0, a) ever
 - if an oracle for strlen(), capable of executing in zero cycles,
   would return the same value for strlen(a) throughout the execution
   of strcmp(), then no accesses to any byte in the range
   [a+strlen(a), b)
 - if an oracle for strlen(), capable of executing in zero cycles,
   would return the same value for strlen(b) throughout the execution
   of strcmp(), then no accesses to any byte in the range
   [b+strlen(b), ADDR_MAX)
 - however, if the oracle strlen() values _do_ change during the
   execution of strcmp(), then accesses to bytes in the latter two
   ranges are possible
 - a SIGSEGV is permissible if and only if there was at least one
   point during execution at which a call to the oracle strlen() would
   have triggered a SIGSEGV

Ne?

> Finally it's worth mentioning that nscd does the exact same thing:
> it uses memcmp and non-atomic accesses on shared data that is being
> modified by other threads. It looks totally broken, especially with
> weaker memory ordering, however this kind of insanity may actually
> be a common design pattern...

I don’t want to hold up nscd as an example of quality design or
implementation, but yeah, I share your concern re “may actually be a
common design pattern”…

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Alejandro Colomar]

Hi Zack,

On 12/29/22 08:21, Zack Weinberg via Libc-alpha wrote:
> On Wed, 14 Dec 2022 16:56:28 -0500, Wilco Dijkstra wrote:
>> I'd expect that mem* functions will never read outside their bounds
>> since the bounds are explicitly defined by the arguments, not by the
>> data. So that should be easy to guarantee.
> 
> I concur.
> 
>> For the str* functions it may be harder since the data itself
>> defines when to stop reading.  So if an implementation uses multiple
>> accesses to the same address, you could potentially mistake the end
>> of a string (eg. first one detects a special case, while the 2nd
>> then verifies it).
> 
> I also concur here.
>   
>> Still, I wouldn't expect totally random memory accesses even in this
>> case - you would read beyond the end of a string if the string end
>> is changed concurrently.
> 
> We may run into a problem where it’s difficult to _state_ the limits
> of the misbehavior, just because the C standard doesn’t itself try to
> put limits on misbehavior in the face of an incorrect program, so we
> don’t have any language for it (which I would argue is a bug in the
> standard, see the detailed reply to Carlos that I’ll be writing, er,
> tomorrow).

The standard already makes some kind of guarantee, when it differences between 
bound UB and critical UB.  The problem is that once you've met bound UB, it's 
hard not to convert it to critical UB in the following lines of code.  Even a 
compiler assumption that would otherwise be fine might result in critical UB.

> 
> Still, taking strcmp(a, b) for example, and assuming WLOG a flat
> address space in which a < b, it should be possible to guarantee
> 
>   - no accesses to any byte in the range [0, a) ever
>   - if an oracle for strlen(), capable of executing in zero cycles,
>     would return the same value for strlen(a) throughout the execution
>     of strcmp(), then no accesses to any byte in the range
>     [a+strlen(a), b)
>   - if an oracle for strlen(), capable of executing in zero cycles,
>     would return the same value for strlen(b) throughout the execution
>     of strcmp(), then no accesses to any byte in the range
>     [b+strlen(b), ADDR_MAX)
>   - however, if the oracle strlen() values _do_ change during the
>     execution of strcmp(), then accesses to bytes in the latter two
>     ranges are possible
>   - a SIGSEGV is permissible if and only if there was at least one
>     point during execution at which a call to the oracle strlen() would
>     have triggered a SIGSEGV

Are you meaning this would be an invalid implementation of strcmp(3)?:

int
strcmp(const char *s1, const char *s2)
{
	for (; *s1 != '\0' || *s1 != '\0'; s1++, s2++) {
		if (*s1 < *s2)
			return -1;
		if (*s1 > *s2)
			return 1;
	}
}

Okay, probably it's not the fastest one, but it's simple.  This one would 
SIGSEGV in the following case:

Another thread might insert a NUL at the beginning of each string (after the 
loop has passed over it), and in the next cycle remove the 
previously-terminating NUL from the strings.  The loop would then run forever, 
until a crash.

Cheers,

Alex

> 
> Ne?
> 
>> Finally it's worth mentioning that nscd does the exact same thing:
>> it uses memcmp and non-atomic accesses on shared data that is being
>> modified by other threads. It looks totally broken, especially with
>> weaker memory ordering, however this kind of insanity may actually
>> be a common design pattern...
> 
> I don’t want to hold up nscd as an example of quality design or
> implementation, but yeah, I share your concern re “may actually be a
> common design pattern”…
> 
> zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Joseph Myers]

On Thu, 29 Dec 2022, Alejandro Colomar via Libc-alpha wrote:

> Okay, probably it's not the fastest one, but it's simple.  This one would
> SIGSEGV in the following case:
> 
> Another thread might insert a NUL at the beginning of each string (after the
> loop has passed over it), and in the next cycle remove the
> previously-terminating NUL from the strings.  The loop would then run forever,
> until a crash.

I also think it should be OK for strcmp to SEGV if a NUL terminator byte 
in either string at the time strlen is called, or at any time during its 
execution, ceases at any point during the execution of strlen to be a NUL 
byte (even if there is an earlier or later NUL already present at the time 
the terminator byte is changed).  (There is a reasonable case for avoiding 
a SEGV when the contents of the strings change during execution, as long 
as any byte that is the NUL terminator byte at any point during execution 
of the call never ceases to be a NUL byte during execution of that call - 
an earlier NUL might be added, however.)

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

On Fri, Dec 30, 2022, at 1:02 PM, Joseph Myers wrote:
> I also think it should be OK for strcmp to SEGV if a NUL terminator
> byte in either string at the time strlen is called, or at any time
> during its execution, ceases at any point during the execution of
> strlen to be a NUL byte (even if there is an earlier or later NUL
> already present at the time the terminator byte is changed).  (There
> is a reasonable case for avoiding a SEGV when the contents of the
> strings change during execution, as long as any byte that is the NUL
> terminator byte at any point during execution of the call never ceases
> to be a NUL byte during execution of that call - an earlier NUL might
> be added, however.)

Coming back to this ages later, I'm not sure how this differs from what
I said about the oracle for strlen... Imagine we have a hardware
debugger that can freeze execution of the entire computer at the moment
the call instruction for strcmp is invoked, perform strlen() on both
strings passed to strcmp, and then resume execution.  Call the string
lengths measured by this hypothetical debugger the "original" string
lengths.  What I was trying to communicate is that any concurrent
modification to the strings that *changes either string's length from
its original* should still permit constrained-unpredictable behavior by
the implementation of strcmp. It seems to me that this is the same as
talking about insertion or deletion of NULs within the bounds of the
original string lengths.

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

On Wed, 14 Dec 2022 12:36:44 -0500, Paolo Bonzini wrote: 
> On 12/14/22 15:16, Zack Weinberg via Libc-alpha wrote:
> > 7.1.4p5 (N1570) "A library
> > function shall not directly or indirectly access objects accessible
> > by threads other than the current thread unless the objects are
> > accessed directly or indirectly via the function's arguments."
>
> I don't think this applies here for two reasons though:
> 
> 1) a SIGSEGV would always be acceptable (that's not a valid object),
> and so would an infinite loop

An infinite loop would indeed be acceptable, but I don’t see any
justification for a SIGSEGV as long as the _page tables_ are not being
changed concurrently from another thread.  To put it another way,
given a call `memcmp(a, b, n)`, as long as the address ranges
`[a, a+n)` and `[b, b+n)` remain _readable_ for the duration of the
call, no, SIGSEGV is not an acceptable outcome in my book, no matter
how unstable the contents of those address ranges are.

 > 2) I think that the as-if rule would even allow reads to objects
> accessible by other threads, if they don't affect the result (so they
> are not observable by the calling thread) *and* are not observable by
> those other threads either.  The classic case here is strlen() doing
> aligned word (or larger) reads, even though those reads might trespass
> the NUL terminator.

I’m not entirely comfortable with that logic, because those reads are
forbidden by the _abstract_ machine’s memory model, in which reading
even a single byte beyond the bounds of an explicitly declared array
or malloc() block is UB.  Very few concrete machines can enforce that
rule precisely; the only ones I can think of are the valgrind VM and
_maybe_ CHERI.  But that hasn’t so far stopped the compiler people
from implementing optimizations that assume the concrete machine
_does_ enforce that rule precisely.

> The following code is admittedly a bit contrived but shows the
> pitfalls of reading more than once from the same location:
> 
>   while (*(u32*)s == *(u32*)d) {
>     n-=4, s+=4, d+=4;
>     if (n < 4) goto short;
>   }
> 
>   // we know the loop will stop don't we?
>   while (*s==*d) s++, d++;
>   return *s < *d ? -1 : 1;
> 
> short:
>   while (n && *s == *d) s++, d++, n--;
>   return n ? (*s < *d ? -1 : 1) : 0;

In my book, this falls clearly into “don’t do that then” territory.
It is our responsibility as library implementors to code memcmp so
that it _does not_ access beyond the [a,a+n) [b,b+n) range, _even if_
there is a concurrent mutator.

> There are also compiler issues: it's also hard to ensure that the
> compiler won't decide to read twice for very down-to-Earth instruction
> selection reasons, for example by using a register-and-memory ALU
> operation.  Many mem*/str* routines do not have a single memory write,
> so the compiler has a *lot* of leeway to reorder and rematerialize
> memory accesses.

Again, “don’t do that then”―not “don’t read twice,” but “don’t elide
bounds checks, specifically, based on the assumption that two reads
from the same location will return the same value.”

> For example you could have something like this in a
> memmem():
> 
>   c = *p;
>   ...
>   p += table[c];
> 
> If the compiler changes the second statement to "p += table1[*p]", for
> example to avoid a spill,

that should be _perfectly fine_, because the next line of code is
something like

  if (p > limit) break;

and not

  c = *p;

If the compiler deletes the bounds check, I’m prepared to argue both
that that’s an incorrect optimization, and that if the standard says
it’s fine then the _standard_ is wrong.

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Paolo Bonzini]

On 12/14/22 15:16, Zack Weinberg via Libc-alpha wrote:
>> The standards are in no way prescriptive in saying that memcmp
>> shall not read or write to memory outside of the input domain.
>
> ... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library
> function shall not directly or indirectly access objects accessible
> by threads other than the current thread unless the objects are
> accessed directly or indirectly via the function's arguments."  There
> is more wiggle room in this wording than I'd ideally like, but since
> memcmp has no way of knowing whether any particular piece of data
> outside the ranges supplied as arguments is "accessible by threads
> other than the current thread", it needs to be conservative and not
> touch any of it.

I don't think this applies here for two reasons though:

1) a SIGSEGV would always be acceptable (that's not a valid object), and 
so would an infinite loop

2) I think that the as-if rule would even allow reads to objects 
accessible by other threads, if they don't affect the result (so they 
are not observable by the calling thread) *and* are not observable by 
those other threads either.  The classic case here is strlen() doing 
aligned word (or larger) reads, even though those reads might trespass 
the NUL terminator.


Promising any kind of behavior when a data race happens involving the 
str*/mem* functions is harder than it seems.  As soon as the functions 
read a byte more than once, the view of memory that they operate on does 
not even obey causality.

The following code is admittedly a bit contrived but shows the pitfalls 
of reading more than once from the same location:

   while (*(u32*)s == *(u32*)d) {
     n-=4, s+=4, d+=4;
     if (n < 4) goto short;
   }

   // we know the loop will stop don't we?
   while (*s==*d) s++, d++;
   return *s < *d ? -1 : 1;

short:
   while (n && *s == *d) s++, d++, n--;
   return n ? (*s < *d ? -1 : 1) : 0;

... and you could access beyond the [a,a+n) [b,b+n) range if a 
concurrent mutator causes the second while loop to go off the cliff.

There are also compiler issues: it's also hard to ensure that the 
compiler won't decide to read twice for very down-to-Earth instruction 
selection reasons, for example by using a register-and-memory ALU 
operation.  Many mem*/str* routines do not have a single memory write, 
so the compiler has a *lot* of leeway to reorder and rematerialize 
memory accesses.  For example you could have something like this in a 
memmem():

   c = *p;
   ...
   p += table[c];

If the compiler changes the second statement to "p += table1[*p]", for 
example to avoid a spill, concurrent mutation can result in 
out-of-bounds accesses or other kinds of UB.  The standard certainly 
didn't require that str*/mem* be written in assembly, or that it does 
all of it's accesses as atomic loads or perhaps (argh!) volatile.

Paolo

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

I'll respond to this at more length later, but I want to point out that this statement ...

On Tue, Dec 13, 2022, at 11:16 PM, Carlos O'Donell wrote:
> The standards are in no way prescriptive in saying that memcmp shall not read or
> write to memory outside of the input domain.

... is (as I read it) contradicted by 7.1.4p5 (N1570) "A library function shall not directly or indirectly access objects accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function's arguments."  There is more wiggle room in this wording than I'd ideally like, but since memcmp has no way of knowing whether any particular piece of data outside the ranges supplied as arguments is "accessible by threads other than the current thread", it needs to be conservative and not touch any of it.

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Florian Weimer]

* Noah Goldstein:

> On Tue, Dec 13, 2022 at 1:20 PM Florian Weimer <fweimer@redhat.com> wrote:
>>
>> * Noah Goldstein via Libc-alpha:
>>
>> > Is this something we have to support? I believe other functions /
>> > implementations of memcmp will suffer from a similar bug.
>>
>> Of course the crash is by no means deterministic, so I'm not sure how
>> useful it is to detect application bugs.  Maybe papering over the
>> application bug is the right approach here.
>>
>> On the other hand, I really don't see how such a racing memcmp call
>> could deliver any useful information whatsoever.  The result will always
>> be arbitrary in practice.  So I hope such application bugs are really
>> rare.
>
> The usecase in the bugzilla is optimistic reads in concurrent
> databases.

So what happens is that whatever the result is, it is still validated
with some separate mechanism (e.g., a seqlock or some other form of TM)?
That does not seem unreasonable at all, so I'd be in favor of supporting
this, given that the cost is so low.

Thanks,
Florian

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Carlos O'Donell]

On 12/13/22 21:28, Zack Weinberg wrote:
> Carlos O'Donell <carlos@redhat.com> writes:
> 
>> On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote:
>>> I think it would be reasonable for glibc to make the following weaker guarantee:
>>> for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being
>>> concurrently modified, the return value is unspecified but *not* indeterminate.
>>> Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n),
>>> no matter what.
>>
>> I disagree strongly.
> 
> I’m really surprised to hear you say that.  To me this is a natural
> guarantee for memcmp — in fact, for *all* of the mem* functions — to
> make, to the point where my reaction was *of course* this is our bug!

Please let me expand on my answer.

We are talking about the C language, and when you write "unspecified" in that context
it means the language *does* have something to say about the behaviour but does not pick
one or other of the available behaviours. This is not the case, the language very clearly
says this is undefined behaviour, so it says nothing about what should happen.

My understanding was that you were trying to ascribe more determinism to the operation
of memcpy under the presence of data races than could be granted by UB.

I strongly disagree to ascribing more determinism than UB.

Could you expand on why you think this is a "natural" guarantee and from what that
derives from? Is it that you view the input domain to the function as the "natural"
bytes upon which the function is allowed to operate?

>> These are advanced lockless techniques.
>> They should be hidden behind new APIs that provide the required guarantees.
> 
> That the application was doing “advanced lockless techniques” is, to me,

If the application does not follow the language requirements then it is UB.

There are some advanced lockless techniques that do not follow the C memory model.

My point is that such techniques and the requirements should be well understood
and implemented by APIs that provide the required guarantees, not by existing C
string and memory APIs.

> not relevant in the slightest.  The important thing to me is that the
> memory regions `memcmp` is allowed to access are wholly specified by the
> mathematical values of its three arguments, and *not* by the data
> pointed to by the first two arguments.  Nothing any other thread does
> can change the fact that memcmp has no business touching bytes at
> addresses outside [a, a+n) and [b, b+n).

I strongly disagree (though the quiet theoretician in me agrees with you).

The standards are in no way prescriptive in saying that memcmp shall not read or
write to memory outside of the input domain.

> Why do you think it is important for the C library to have latitude to
> break that aspect of the mem* functions’ API contract?  Even if only
> under exotic circumstances?

Why do you think an application programmer has the right to ignore the requirements
of the language and expect the runtime to operate as intended?

Why would we as library authors enter into an API contract that is *stronger* than
the language guarantees?

I am empathetic to the yottadb developers, but we need new APIs for these requirements.

I will still review Noah's patch here:
https://sourceware.org/pipermail/libc-alpha/2022-December/144058.html

I do not have a sustained objection to modifying things to "just work" (tm) because
with UB you could do anything, and it doesn't impact the normal use cases.

That is to say for a specific patch, and a specific change, I can agree, but not
to the larger generalizations about memcmp.

-- 
Cheers,
Carlos.

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

Carlos O'Donell <carlos@redhat.com> writes:

> On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote:
>> I think it would be reasonable for glibc to make the following weaker guarantee:
>> for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being
>> concurrently modified, the return value is unspecified but *not* indeterminate.
>> Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n),
>> no matter what.
>
> I disagree strongly.

I’m really surprised to hear you say that.  To me this is a natural
guarantee for memcmp — in fact, for *all* of the mem* functions — to
make, to the point where my reaction was *of course* this is our bug!

> These are advanced lockless techniques.
> They should be hidden behind new APIs that provide the required guarantees.

That the application was doing “advanced lockless techniques” is, to me,
not relevant in the slightest.  The important thing to me is that the
memory regions `memcmp` is allowed to access are wholly specified by the
mathematical values of its three arguments, and *not* by the data
pointed to by the first two arguments.  Nothing any other thread does
can change the fact that memcmp has no business touching bytes at
addresses outside [a, a+n) and [b, b+n).

Why do you think it is important for the C library to have latitude to
break that aspect of the mem* functions’ API contract?  Even if only
under exotic circumstances?

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Carlos O'Donell]

On 12/13/22 15:56, Zack Weinberg via Libc-alpha wrote:
> On Tue, Dec 13, 2022, at 2:25 PM, Noah Goldstein via Libc-alpha wrote:
>> On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote:
>>> Thank you for acknowledging that it is a bug.
>> I'm not sure this is a bug, I'm just saying to avoid this behavior you can
>> make that change.
>>
>> I think we all agree supporting a correct non-atomic memcmp when the values
>> in memory can change during execution is not reasonable.
>> I think SIG11 is not a great outcome (of the many possible behaviors when its
>> incorrect), but am not sure it's worth fixing.
> 
> I think it would be reasonable for glibc to make the following weaker guarantee:
> for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being
> concurrently modified, the return value is unspecified but *not* indeterminate.
> Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n),
> no matter what.

I disagree strongly.

These are advanced lockless techniques.

They should be hidden behind new APIs that provide the required guarantees.
 
> This would, I believe, be sufficient to prevent a crash under the conditions
> described by Narayanan Iyer.

I would want to see compiler and langauge authors agree to such changes.

-- 
Cheers,
Carlos.

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Noah Goldstein]

On Tue, Dec 13, 2022 at 1:20 PM Florian Weimer <fweimer@redhat.com> wrote:
>
> * Noah Goldstein via Libc-alpha:
>
> > Is this something we have to support? I believe other functions /
> > implementations of memcmp will suffer from a similar bug.
>
> Of course the crash is by no means deterministic, so I'm not sure how
> useful it is to detect application bugs.  Maybe papering over the
> application bug is the right approach here.
>
> On the other hand, I really don't see how such a racing memcmp call
> could deliver any useful information whatsoever.  The result will always
> be arbitrary in practice.  So I hope such application bugs are really
> rare.

The usecase in the bugzilla is optimistic reads in concurrent databases.

>
> > The fix:
> > https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46
> > ```
> > -#   define SIZE_OFFSET (CHAR_PER_VEC * 2)
> > +#   define SIZE_OFFSET 0
> > ```
>
> How costly is this change?  I would have thought about ANDing the offset
> so that it is always in range (but maybe it will stil result in a page
> crossing, I don't really know how this works).

Its a bit expensive b.c it misaligned a lot of hot paths.

A better fix (untested) is probably:
```
@@ -308,7 +308,7 @@ L(ret_nonzero_vec_end_0):
  setg %dl
  leal -1(%rdx, %rdx), %eax
 #  else
- addl %edx, %eax
+ addq %rdx, %rax
  movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rsi, %rax), %ecx
  movzbl (VEC_SIZE * -1 + SIZE_OFFSET)(%rdi, %rax), %eax
  subl %ecx, %eax

```
The issue is the 32-bit negative number becomes a very large
unsigned 64-bit number. If we just use 64-bit addition the
issue goes away (I think at least).

I'm okay with this change going in (assuming it works).

This fix can be a "happy accident" that this unsupported
usage no longer causes a sig-11, but I think it's a mistake to
explicitly support this use case as anything other than UB.

>
> Thanks,
> Florian
>

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Florian Weimer]

* Noah Goldstein via Libc-alpha:

> Is this something we have to support? I believe other functions /
> implementations of memcmp will suffer from a similar bug.

Of course the crash is by no means deterministic, so I'm not sure how
useful it is to detect application bugs.  Maybe papering over the
application bug is the right approach here.

On the other hand, I really don't see how such a racing memcmp call
could deliver any useful information whatsoever.  The result will always
be arbitrary in practice.  So I hope such application bugs are really
rare.

> The fix:
> https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46
> ```
> -#   define SIZE_OFFSET (CHAR_PER_VEC * 2)
> +#   define SIZE_OFFSET 0
> ```

How costly is this change?  I would have thought about ANDing the offset
so that it is always in range (but maybe it will stil result in a page
crossing, I don't really know how this works).

Thanks,
Florian

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Zack Weinberg]

On Tue, Dec 13, 2022, at 2:25 PM, Noah Goldstein via Libc-alpha wrote:
> On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote:
>> Thank you for acknowledging that it is a bug.
> I'm not sure this is a bug, I'm just saying to avoid this behavior you can
> make that change.
>
> I think we all agree supporting a correct non-atomic memcmp when the values
> in memory can change during execution is not reasonable.
> I think SIG11 is not a great outcome (of the many possible behaviors when its
> incorrect), but am not sure it's worth fixing.

I think it would be reasonable for glibc to make the following weaker guarantee:
for any call `memcmp(a, b, n)`, if the data pointed to by `a` and/or `b` is being
concurrently modified, the return value is unspecified but *not* indeterminate.
Also, memcmp will never access memory outside the bounds [a, a+n) and [b, b+n),
no matter what.

This would, I believe, be sufficient to prevent a crash under the conditions
described by Narayanan Iyer.

zw

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Noah Goldstein]

On Tue, Dec 13, 2022 at 11:13 AM Narayanan Iyer <nars@yottadb.com> wrote:
>
> Noah,
>
> Thank you for acknowledging that it is a bug.
I'm not sure this is a bug, I'm just saying to avoid this behavior you can
make that change.

I think we all agree supporting a correct non-atomic memcmp when the values
in memory can change during execution is not reasonable.
I think SIG11 is not a great outcome (of the many possible behaviors when its
incorrect), but am not sure it's worth fixing.

>
> In case it helps, I found in our testing cluster, that a system which uses sysdeps/x86_64/multiarch/memcmp-sse2.S has the bug whereas a system that uses sysdeps/x86_64/multiarch/memcmp-avx2-movbe.S does not have the bug.
I wouldn't count on any of the other implementations being hardened to this.


>
> So it is possible, the issue is only in the sse2 version.

I did a quick check of avx2/evex and don't see the same pattern but I think
it might be present in the tail of the loops (end of much larger copies so
probably comes up less).

>
> Thanks,
> Narayanan.
>
> -----Original Message-----
> From: Noah Goldstein [mailto:goldstein.w.n@gmail.com]
> Sent: Tuesday, December 13, 2022 2:08 PM
> To: Narayanan Iyer <nars@yottadb.com>
> Cc: libc-alpha@sourceware.org
> Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change
>
> On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
> >
> > Hi,
> >
> > I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
> >
> > And have included the title of that report in the email subject as well.
> >
> > It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).
> >
> > Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.
> >
> > I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.
> >
> > Thanks,
> > Narayanan.
> >
> >
>
> The fix:
> https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46
> ```
> -#   define SIZE_OFFSET (CHAR_PER_VEC * 2)
> +#   define SIZE_OFFSET 0
> ```
>
> Is this something we have to support? I believe other functions /
> implementations
> of memcmp will suffer from a similar bug.
>

RE: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Narayanan Iyer]

Noah,

Thank you for acknowledging that it is a bug.

In case it helps, I found in our testing cluster, that a system which uses sysdeps/x86_64/multiarch/memcmp-sse2.S has the bug whereas a system that uses sysdeps/x86_64/multiarch/memcmp-avx2-movbe.S does not have the bug.

So it is possible, the issue is only in the sse2 version.

Thanks,
Narayanan.

-----Original Message-----
From: Noah Goldstein [mailto:goldstein.w.n@gmail.com] 
Sent: Tuesday, December 13, 2022 2:08 PM
To: Narayanan Iyer <nars@yottadb.com>
Cc: libc-alpha@sourceware.org
Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> Hi,
>
> I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
>
> And have included the title of that report in the email subject as well.
>
> It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).
>
> Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.
>
> I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.
>
> Thanks,
> Narayanan.
>
>

The fix:
https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46
```
-#   define SIZE_OFFSET (CHAR_PER_VEC * 2)
+#   define SIZE_OFFSET 0
```

Is this something we have to support? I believe other functions /
implementations
of memcmp will suffer from a similar bug.

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Noah Goldstein]

On Tue, Dec 13, 2022 at 10:20 AM Narayanan Iyer via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> Hi,
>
> I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
>
> And have included the title of that report in the email subject as well.
>
> It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).
>
> Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.
>
> I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.
>
> Thanks,
> Narayanan.
>
>

The fix:
https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse2.S;h=afd450d0206d6633da9fbc4607a7fa6aeb4e137c;hb=HEAD#l46
```
-#   define SIZE_OFFSET (CHAR_PER_VEC * 2)
+#   define SIZE_OFFSET 0
```

Is this something we have to support? I believe other functions /
implementations
of memcmp will suffer from a similar bug.

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Cristian Rodríguez]

On Tue, Dec 13, 2022 at 3:20 PM Narayanan Iyer via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> Hi,
>
> I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
>

It might as well make  a shelter.. from pigs on the wing... That's UB
all the way.

RE: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Narayanan Iyer]

As I also mentioned at https://sourceware.org/bugzilla/show_bug.cgi?id=29863#c3, it might not be a well defined test case. But memcmp() is never expected to SIG-11 in any circumstance as long as the buffers it is passed in are accessible from start to finish.

In the same bug report, I had also provided a timeline of the instructions that I believe got executed in the crash case and pointed to the failing assembly instruction. The test case was just a easy way for you to see the problem yourself. Even if you don't accept the test case, can you take a look at the rest of my bug report to see if you agree with the finding.

Thanks,
Narayanan.

-----Original Message-----
From: Andrew Pinski [mailto:pinskia@gmail.com] 
Sent: Tuesday, December 13, 2022 1:32 PM
To: Narayanan Iyer <nars@yottadb.com>
Cc: libc-alpha@sourceware.org
Subject: Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

On Tue, Dec 13, 2022 at 10:21 AM Narayanan Iyer via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> Hi,
>
> I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
>
> And have included the title of that report in the email subject as well.
>
> It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).

I don't see how this is a valid well defined testcase. Changing memory
without barriers in both threads is not well defined. memcmp is not
guaranteed to be atomic or have any atomicity either.
So you just happen to work before and now your undefined code does not work.

Thanks,
Andrew Pinski

>
> Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.
>
> I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.
>
> Thanks,
> Narayanan.
>
>

Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Andrew Pinski]

On Tue, Dec 13, 2022 at 10:21 AM Narayanan Iyer via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> Hi,
>
> I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863
>
> And have included the title of that report in the email subject as well.
>
> It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).

I don't see how this is a valid well defined testcase. Changing memory
without barriers in both threads is not well defined. memcmp is not
guaranteed to be atomic or have any atomicity either.
So you just happen to work before and now your undefined code does not work.

Thanks,
Andrew Pinski

>
> Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.
>
> I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.
>
> Thanks,
> Narayanan.
>
>

Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Narayanan Iyer]

Hi,

I had created a glibc bug report at https://sourceware.org/bugzilla/show_bug.cgi?id=29863

And have included the title of that report in the email subject as well.

It has been a week since I created the issue and I did not hear anything back. I believe this is a regression in glibc 2.36 and have provided enough information in the bug report (along with the commit that caused the regression).

Given the upcoming glibc 2.37 release, I was asked (by Carlos O'Donell <carlos@redhat.com>) to raise it on this mailing list to get the attention of the glibc developers.

I am hoping one of you could take a quick look at the bug report and see if it is worth fixing it in time for glibc 2.37.

Thanks,
Narayanan.