“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