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

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.

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.
>
>

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

[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

[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

[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 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

[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

[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 vs invalid results, memory models, and control/data dependencies.

[Carlos O'Donell]

On 12/13/22 14:25, Noah Goldstein via Libc-alpha wrote:
> 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.

The issue here is the ability to optimistically carry out an operation, and then
eventually determine if the result could have been consistent, particularly in
the case of a software transaction as implemented in OCC.

My opinion is that this breaks down to a discussion of valid memory models
that can be used by an application. Today the C memory models and the POSIX
Memory Synchronization language do not allow data races. However, looking at the
Linux kernel for reference we see idiomatic usage for control and data dependencies.
The Linux Kernel strategies for this do not easily apply to userspace.

In the case of bug 29863 the memcmp has a dependency on the data in the shared
memory segment, and the argument being made in the bug report is that, regardless
of the ordering, the dependencies in the code should not produce a segfault. The logic
of the assembly would have to assume any observable ordering of writes to the bytes
and take steps to ensure that the results are correct. This is pessimistic for the
performance of a program that avoids data races, but optimistic for a program that
wants to have low-overhead execution without atomics. It also begs the question:
Does this have to extend to *all* glibc routines? Clearly it can't, because once
the routine has a compiler involved we are enforcing the compiler's knowledge
of UB and memory models.

Compiler optimizations will make this more and more difficult to do correctly.
Consider the case where there is no library memcmp and the compiler inlines the
memcmp and assumes the memory model is not violated.

The most recent update of this discussion was at LPC 2022 for the kernel:
Status Report: Broken Dependency Orderings in the Linux Kernel - Marco Elver, Paul Heidekrüger
https://www.youtube.com/watch?v=ad-75tViBm4

A claim that "it's been working for 20 years" is true, but likewise "compilers
and libraries have gotten better in the last 20 years" is also true. 

Toolchain authors have begun to formalize memory models, and these models do
not support operations like OCC if they have data races.

In summary:

- We should pursue performance given a well formed understanding of the memory
  models glibc supports e.g. ISO C11, and POSIX Issue 7.

- Authors using OCC should explain their memory model in detail, and may need to
  raise the issue with the broader toolchain authors to gain consensus for the
  design constraints imposed by OCC on the implementation language being
  compiled e.g. compiler picks a special memcpy, or does other operations.

-- 
Cheers,
Carlos.

Notes:
15.3.2: Address- and Data-Dependency Difficulties
https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-e2.pdf

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

[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

[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 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 vs invalid results, memory models, and control/data dependencies.

[Florian Weimer]

* Carlos O'Donell via Libc-alpha:

> - We should pursue performance given a well formed understanding of the memory
>   models glibc supports e.g. ISO C11, and POSIX Issue 7.

But the C memory model is known to be broken.  For example, it does not
rule out the existence of out-of-thin-air values, which makes relaxed MO
pretty useless.  I don't think we can use it as an argument to reject
requests from application developers.

> - Authors using OCC should explain their memory model in detail, and
>   may need to raise the issue with the broader toolchain authors to gain
>   consensus for the design constraints imposed by OCC on the
>   implementation language being compiled e.g. compiler picks a special
>   memcpy, or does other operations.

I think their requirements for memcmp are pretty clear.  We don't need a
fullly fleshed out memory model for that.

Thanks,
Florian

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

[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

[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]

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

“Undefined behavior” considered harmful (was Re: Bug 29863 - Segmentation fault in memcmp-sse2.S…)

[Zack Weinberg]

The original issue with memcmp() seems to have been resolved, but I’d
like to start a broader discussion about the C library’s
responsibilities in the face of a program that’s, to some degree,
incorrect.

On Tue, 13 Dec 2022 23:16:19 -0500, Carlos O'Donell wrote:
> 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.

Everything I’m about to say stems from the following three premises:

1. The C standard uses “undefined behavior” far more liberally than it
   ought to.  In many cases of existing UB the committee could define
   the behavior (possibly as implementation-defined or unspecified)
   without any actual negative consequences.  It seems the committee
   *is* moving in this direction as of C2x, for instance by dropping
   the allowances for non-twos-complement signed arithmetic, but they
   could and should go a lot farther down that road.

2. The remaining cases of UB are those where we still want to say that
   the program is *incorrect* if it does these things, but we don’t
   want to require the compiler to diagnose the incorrectness (usually
   because detection would be intractable).  *Even in these cases*,
   the current concept of “undefined behavior,” licensing the
   implementation to do *anything*, is troublesome.  The standard
   should replace the concept entirely, with something analogous to,
   say, the ARM ARM’s concept of “constrained unpredictable” behavior:
   A program that does X is incorrect, and doing X will have
   unpredictable consequences, BUT there are concrete limits on what
   those consequences can be.

3. Implementations can and should work in advance of the C committee
   on restricting the consequences of UB as outlined in (1) and (2).
   That is, the present state of the C standard should not stop _us_
   from specifying the behavior of GNU libc in cases where clause 7
   leaves behavior “undefined”.

The earlier thread provides a concrete example of a type 2 change that
I think is desirable: instead of 5.1.2.4p25 simply saying that if a
data race occurs, the behavior is undefined, it should say that if a
data race occurs, all calculations data- or control-dependent on the
conflicting expressions produce unpredictable results, where
“unpredictable result” is approximately the same thing as the current
“unspecified value” but might wind up needing to have a slightly
different definition.  [Notice that this is already a significant
constraint on what actually happens, since unpredictability can no
longer propagate backwards in time.]

Then, also, 7.1.4 should say that if the set of memory locations that
are potentially accessed by a library function can be specified
without reference to the contents of any of those memory locations
(true for memXXX, not for strXXX) then, a data race on the contents of
any of those memory locations cannot expand the set.

> Could you expand on why you think this is a "natural" guarantee and
> from what that derives from?

I am envisioning (pointer, length) 2-tuples as object capabilities.
By calling memcmp(a, b, n), the caller grants memcmp access to the
address ranges [a, a+n) and [b, b+n), but not a single byte more.
Some concrete machines (e.g. the valgrind and ASAN VMs, and to a
lesser extent CHERI) can actually enforce the limits of that grant.
Even if the hardware cannot enforce the limits, the callee should
honor them.

The contents, and the stability of the contents, of those address
ranges *cannot* affect the limits of the grant, because they appear
nowhere in the expressions that define the limits.

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

As described above, arguments from what is or is not currently UB have
no weight from my perspective.

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

Because we believe that the language guarantees are too weak and need
to be strengthened, and the standard committees will want to see that
strengthening play out as “existing practice” before they make any
changes.

zw

Re: “Undefined behavior” considered harmful (was Re: Bug 29863 - Segmentation fault in memcmp-sse2.S…)

[Andreas Schwab]

On Dez 29 2022, Zack Weinberg via Libc-alpha wrote:

> 1. The C standard uses “undefined behavior” far more liberally than it
>    ought to.  In many cases of existing UB the committee could define
>    the behavior (possibly as implementation-defined or unspecified)
>    without any actual negative consequences.  It seems the committee
>    *is* moving in this direction as of C2x, for instance by dropping
>    the allowances for non-twos-complement signed arithmetic, but they
>    could and should go a lot farther down that road.

That's not removing an undefined behavior, it's removing an
implementation choice.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: “Undefined behavior” considered harmful (was Re: Bug 29863 - Segmentation fault in memcmp-sse2.S…)

[Florian Weimer]

* Andreas Schwab:

> On Dez 29 2022, Zack Weinberg via Libc-alpha wrote:
>
>> 1. The C standard uses “undefined behavior” far more liberally than it
>>    ought to.  In many cases of existing UB the committee could define
>>    the behavior (possibly as implementation-defined or unspecified)
>>    without any actual negative consequences.  It seems the committee
>>    *is* moving in this direction as of C2x, for instance by dropping
>>    the allowances for non-twos-complement signed arithmetic, but they
>>    could and should go a lot farther down that road.
>
> That's not removing an undefined behavior, it's removing an
> implementation choice.

Right, arithmetic is still not twos-complement, it's only about
representation.  Same with C++.

(I associate twos-complement signed *arithmetic* with the obvious
(unsigned) overflow behavior.)

Re: “Undefined behavior” considered harmful (was Re: Bug 29863 - Segmentation fault in memcmp-sse2.S…)

[Florian Weimer]

* Zack Weinberg via Libc-alpha:

> The original issue with memcmp() seems to have been resolved, but I’d
> like to start a broader discussion about the C library’s
> responsibilities in the face of a program that’s, to some degree,
> incorrect.
>
> On Tue, 13 Dec 2022 23:16:19 -0500, Carlos O'Donell wrote:
>> 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.
>
> Everything I’m about to say stems from the following three premises:
>
> 1. The C standard uses “undefined behavior” far more liberally than it
>    ought to.  In many cases of existing UB the committee could define
>    the behavior (possibly as implementation-defined or unspecified)
>    without any actual negative consequences.  It seems the committee
>    *is* moving in this direction as of C2x, for instance by dropping
>    the allowances for non-twos-complement signed arithmetic, but they
>    could and should go a lot farther down that road.

I'm not sure if this is a priority.  It's a lot of work, and most
aspects are probably not technical in the end.  For example, Peter
Sewell's group did a lot of work on the (non-concurrent) C memory
model, both investigative and descriptive, and it's been hard to
integrate this into the standard, as far as I know.

From a licensing perspective, I would very much prefer if anything
that approaches an executable specification were outside the ISO
framework.  It would also enable exploring different directions based
on interests (some might prefer semantics more along the lines of
-fwrapv -fno-strict-aliasing, for example).

> 2. The remaining cases of UB are those where we still want to say that
>    the program is *incorrect* if it does these things, but we don’t
>    want to require the compiler to diagnose the incorrectness (usually
>    because detection would be intractable).  *Even in these cases*,
>    the current concept of “undefined behavior,” licensing the
>    implementation to do *anything*, is troublesome.  The standard
>    should replace the concept entirely, with something analogous to,
>    say, the ARM ARM’s concept of “constrained unpredictable” behavior:

Hmm.  Ada RM? Bounded errors?  Maybe these concepts are quite common?

> 3. Implementations can and should work in advance of the C committee
>    on restricting the consequences of UB as outlined in (1) and (2).
>    That is, the present state of the C standard should not stop _us_
>    from specifying the behavior of GNU libc in cases where clause 7
>    leaves behavior “undefined”.

That seems reasonable.  Yet in many cases, we still struggle to find
consensus among our smaller group.

> The earlier thread provides a concrete example of a type 2 change that
> I think is desirable: instead of 5.1.2.4p25 simply saying that if a
> data race occurs, the behavior is undefined, it should say that if a
> data race occurs, all calculations data- or control-dependent on the
> conflicting expressions produce unpredictable results, where
> “unpredictable result” is approximately the same thing as the current
> “unspecified value” but might wind up needing to have a slightly
> different definition.  [Notice that this is already a significant
> constraint on what actually happens, since unpredictability can no
> longer propagate backwards in time.]

I think this would have serious implications for any optimizations
involving multiple memory accesses.  With undefined data races and no
relevant writes from the current thread, you can assume that the
memory is stable.

I doubt there's a good alternative right now to the present situation.

>> Could you expand on why you think this is a "natural" guarantee and
>> from what that derives from?
>
> I am envisioning (pointer, length) 2-tuples as object capabilities.
> By calling memcmp(a, b, n), the caller grants memcmp access to the
> address ranges [a, a+n) and [b, b+n), but not a single byte more.
> Some concrete machines (e.g. the valgrind and ASAN VMs, and to a
> lesser extent CHERI) can actually enforce the limits of that grant.
> Even if the hardware cannot enforce the limits, the callee should
> honor them.
>
> The contents, and the stability of the contents, of those address
> ranges *cannot* affect the limits of the grant, because they appear
> nowhere in the expressions that define the limits.

But that's not how memcmp is implemented in practice.  Our
implementation assumes that it can access memory outside these bounds,
but that is not observable because we only do so when we are sure it
does not cause a page fault.  But there are other ways memory accesses
can be observable.

It's also proven difficult to find consensus whether string functions
may continue reading beyond bytes that determine the function's
result.

> Because we believe that the language guarantees are too weak and need
> to be strengthened, and the standard committees will want to see that
> strengthening play out as “existing practice” before they make any
> changes.

Or maybe they standardize that's incompatible with what we do, and
they feel free to do so because it was previously undefined, so it's
technically not a language change.

If we go in that direction, we should accept future, persistent
incompatibilities, and get out of the business to present a
standards-compliant view to the programmer even when the underlying
infrastructure isn't.  See __ASSUME_SYSVIPC_BROKEN_MODE_T for an
example what we've been doing so far.

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

[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

[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

[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

[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