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