Audience: EWG, SG22
S. Davis Herring <herring@lanl.gov>
May 21, 2024

History

Since r0:

• Rebased onto N4981
• Clarified discussion of P2318R1’s analysis and proposal
• Discussed implications for pointer zap

Introduction

P2318R1 describes a variety of plausible models of pointer provenance that differ principally in how they handle conversions between pointers and integers (including the integer values of the storage bytes for a pointer). (See its §A.4 for discussion of the variants in terms of examples.) It proposes the variant called PNVI-ae-udi, which does seem to provide a good combination of optimization possibilities and support for existing code. However, in several cases it is overly charitable to the programmer: for example, using an explicit copy loop rather than calling std::memcpy “exposes” storage, which can interfere with optimization, even if the byte values obviously do not escape. (The paper proposes to eventually add annotations to avoid such unwanted side effects.) It also sometimes depends in an apparently arbitrary fashion on the order of operations with no data dependencies (as in the pointer_from_integer_1ig.c example with an exposure of j added).

The main alternative that was considered and rejected is the PVI model, which avoids the notion of storage exposure but imposes further restrictions on integer conversions. These restrictions provide further opportunities for optimization but also complicate the execution model in subtle ways that make it difficult for the programmer to determine whether a manipulation preserves the validity of a pointer (yet to be reconstructed). They also interact badly with serialization of pointers where operations on the converted pointer value are entirely invisible; additional annotations might be required to support this use case.

This paper compares the existing rules for pointers to these provenance models and proposes minor changes to better align them. These changes have the additional benefit of addressing some of the concerns surrounding “pointer zap”. In particular, the use cases for the “provenance fence” operation proposed in P2414R3 become implementable with only mild assumptions about implementation-defined behavior for invalid pointer values.

Analysis

Pointer values are described in abstract terms ([basic.compound]/3); while they “represent the address” of an object, that address may be given a numerical interpretation only via copying the bits into an integer or via the implementation-defined mapping to integers ([expr.reinterpret.cast]/4), and there is no specification of how any address is chosen. As such, integers obtained by memcpying or casting pointers may be taken to be completely unspecified aside from the (separate) round-trip requirements. ([basic.align]/1 talks about addresses as ordinal or cardinal numbers of bytes, but nothing else depends on that interpretation.)

This nondeterminism already implies undefined behavior in many of the circumstances that the provenance models are meant to reject. Consider the simple example

int main() {
  int jenny=0;
  // std::cout << &jenny;
  *(int*)8675309=1;
  return jenny;
}

(Assume that the implementation does not specially define a pointer value corresponding to this particular integer.) Even if the address of jenny is the suspicious value given, this has undefined behavior under PNVI-ae-udi (because the address of jenny is never exposed) and PVI (because the integer literal is not derived from the address of jenny). However, it is equally undefined in N4981 because there are possible executions of the program ([intro.abstract]/5) where the address is some other value and the cast produces an invalid pointer value. Printing the address is no help: even if the program displays “0x845fed”, that itself can be a manifestation of the undefined behavior. P2318R1 considers this interpretation but does not deem it conclusive, explaining that the same analysis of many tests can be obtained from address nondeterminism instead of the explicit provenance semantics but lamenting that that approach “requir[es] examination of multiple executions”.

On the other hand, consider

int main() {
  int x,y=0;
  uintptr_t p=(uintptr_t)&x,q=(uintptr_t)&y;
  p^=q;
  q^=p;
  p^=q;
  *(int*)q=*(int*)p;
  return x;
}

PVI disallows this manipulation, saying that the values resulting from operations on p and q do not inherit their provenances; PNVI-ae-udi allows it because it simply observes that both addresses have escaped from the abstract world of pointer values. In the latter case, the compiler would have to support “guessing” addresses even if it could prove that the value of such a pointer doesn’t actually depend on the original pointer. N4981 already handles this case more elegantly: the program has well defined behavior because for any choice of addresses for x and y, q (p) ends up being the address of x (y), so the casts back to pointers produce the swapped pointer values. This interpretation extends to arbitrary integer manipulations and I/O: the operations allowed are precisely those that reliably reproduce some address initially obtained, whether via arithmetic, control flow, or data dependencies. In practice it is impossible to detect every pointer value construction that fails to be reliable (that “guesses”), but there is no obligation to do so since the behavior is undefined in such cases.

The pointer zap rule ([basic.compound]/4) has two purposes: its footnote explains that even examining a pointer into deallocated storage might trap (in the course of loading something like a segment register), but it also serves as a sort of notional “generation counter” for reused parts of the free store. Consider

int main() {
  int *p=new int;
  uintptr_t i=(uintptr_t)p;
  delete p;
  p=new int(1);
  if((uintptr_t)p==i) *(int*)i=0;
  return *p;
}

PVI rejects this LBYL approach: i cannot acquire the provenance of the new p merely because it has been compared to another integer with that provenance. (Consider that the comparison might occur in an opaque function.) PNVI-ae-udi allows it because the address of that new object is exposed in the course of making the check; N4981 allows it simply because i is cast back to a pointer precisely when it has the same value as the cast of the new p. It is only natural that two integers with the same value should have the same behavior.

N4981 does not, however, implement the user-disambiguation (udi) provision: in saying that a pointer subjected to a round-trip conversion “will have its original value”, [expr.reinterpret.cast]/5 erroneously forbids real implementations that produce the same integer value for pointers to an object and one past the object that immediately precedes it in memory. Similarly, [basic.types.general]/2–3 refer to a singular value for what might be a pointer reconstructed from bytes (and /4 claims that the bits are sufficient to determine the value). [bit.cast]/2 acknowledges the possibility of more than one value with the same value representation, but leaves it unspecified which is produced.

The case of concern for lock-free algorithms is analogous to the one-past pointer situation in that multiple abstract pointer values exist whose memory representations (as must be the currency of atomic operations) are identical. Of course, at most one such value (of a given type) is valid at any moment during execution, so there is no ambiguity as to which value the program would prefer to result from a conversion. In its place is the complication that the normal phrasings of these algorithms cannot use any such result because it might be invalidated by unsequenced deallocations. In this case a temporal version of user-disambiguation may be applied: any correct algorithm discovers that the address in question is that of some live object before it uses any associated pointer value, thereby nominating that object’s identity as the value of the pointer.

Proposal

To implement udi, apply the same angelic nondeterminism by which implicit object creation selects the objects to create: if any pointer value exists that corresponds to the integer and gives the program defined behavior, one such value is the result. (As is necessary for any implementation to exist, no program can observe the acausal information about which pointer value is selected.) This change affects [basic.types.general]/2–4, [expr.reinterpret.cast]/5, and [bit.cast]/2 (which currently instead plays into the general demonic nondeterminism of [intro.abstract]/5). This paper does not attempt to address the situation of modifying a pointer by storing to part of its object representation, but it changes the simple memcpy case to avoid eventually giving different behavior to direct and circuitous means of accomplishing a bit-wise copy.

To avoid confusing inconsistencies with comparing their integer representations (on implementations where each address has just one such), restrict [expr.eq] to provide consistent results for any pair of pointer values. This change cannot be detected during constant evaluation ([expr.const]/5.24); following P2318R1, we could consider actually comparing the addresses other than during constant evaluation (because programs cannot benefit from the inherently unreliable != result for distinct pointer values that share an address).

Consequences for pointer zap

Note that the pointer value that gives the program defined behavior might be to an object whose lifetime has not started or even whose region of storage has not yet been created. Clearly such a “prospective” pointer value cannot immediately be used: any attempt to do so necessitates that the result of the integer conversion instead be a pointer to some object in existing storage which cannot then be used after a delete and new. Of course, the reuse of the address might never take place; a correct algorithm will never use the pointer in that circumstance, so it is harmless for it to refer to the previous object. Otherwise, there is no inconsistency in allowing it to be stored until such time as its object comes into existence. (Note that references cannot be used in place of pointers here because a pointer value must be valid in the context of applying * to it ([basic.compound]/4).)

We can then implement LIFO Push with a trivial modification of the initial implementation from P2414R3:

template <typename Node> class LIFOList { // Node must support set_next()
  std::atomic<Node*> top_{nullptr};
public:
  void push(Node* newnode) {
    while (true) {
      Node* oldtop = reinterpret_cast<Node*>(
        reinterpret_cast<std::uintptr_t>(top_.load())); // step 1
      newnode->set_next(oldtop); // step 2
      if (top_.compare_exchange_weak(oldtop, newnode)) return; // step 3
    }
  }

  Node* pop_all() { return top_.exchange(nullptr); }
};

The only change here is the round-trip cast in step 1. If top_ is deallocated and replaced (at the same address) after the load(), oldtop is a pointer to the new object, so newnode contains a pointer valid when it is installed by the compare-exchange. No “provenance fence” is then needed in pop_all because the pointers it reads are all valid at the time. Note that the algorithm still relies on the implementation-defined behavior of applying various operations (other than indirection or deallocation) to the pointer value top_.load() that might not be valid in the context of such operations ([basic.compound]/4), since the reallocation might not yet have happened (if it happens at all).

This paper does not propose requiring that all implementations support these operations (integer conversion, initialization/assignment, and compare-exchange) on non-valid pointer values: it is already optional for the implementation to provide std::uintptr_t, so it is not fundamentally more restrictive to implement LIFO Push only on implementations that support such operations. Nonetheless, EWG might choose to strengthen these requirements while considering these applications to improve their portability.

Nor does this paper propose special behavior for std::atomic<T*> (as has been considered as another partial solution for such algorithms): the mismatched value obtained by the compare-exchange must itself be subjected to a round-trip in order to potentially refer to a future object. It would however be reasonable to specify that such a round trip is implicit in the operation since std::atomic already traffics in value representations and suppresses certain kinds of undefined behavior.

Consequences for implementations

These changes are intended more to formalize than to change existing implementations, in that there does not seem to be any other consistent model that can be used in the presence of multiple pointer values with the same address. However, implementations do not always use a consistent model, as illustrated by the following program:

#include<cstdint>
int y,x; // use x,y at -O0
int main() {
  y=1;
  int *const p=&x+1,*const q=&y;
  const std::uintptr_t u=(std::uintptr_t)p,v=(std::uintptr_t)q;
  if(u==v) {
    const auto w=u+v-u/2-u/2-(u&1);
    if(w==u) { // redundant check
      *(int*)w=2;
      return y;
    }
  }
  return -1;
}

Here GCC and Clang each forward the store of 1 to the return y when optimizing, despite the fact that w is actually equal to v regardless of u’s value (rather than, say, equal to u regardless of v) and despite the two surrounding equality checks. Apparently the “original value” for w is deduced from the “redundant check” comparison, since changing that to w==v causes both implementations to return 2 instead. (Indeed, the generated assembly describes the store through w as being to $x+4 as given and to $y with the comparison to v substituted.)

Wording

Relative to N4981.

#[basic.types]

#[basic.types.general]

Move paragraphs 2 and 3 to [basic.types.trivial] (q.v.).

Change paragraph 4:

The object representation of a complete object type T is the sequence of N unsigned char objects taken up by a non-bit-field complete object of type T, where N equals sizeof(T). The value representation of a type T is the set of bits in the object representation of T that participate in representing a value of type T. The object and value representation of a non-bit-field complete object of type T are the bytes and bits, respectively, of the object corresponding to the object and value representation of its type. The object representation of a bit-field object is the sequence of N bits taken up by the object, where N is the width of the bit-field ([class.bit]). The value representation of a bit-field object is the set of bits in the object representation that participate in representing its value. Bits in the object representation of a type or object that are not part of the value representation are padding bits. For trivially copyable types, the value representation is a set of bits in the object representation that determines a value, which is one discrete element of an implementation-defined set of values.[Footnote: […] — end footnote]

#[basic.types.trivial]

Add this subclause before [basic.fundamental]:

Move paragraphs 2 and 3 here from [basic.types.general] and change them:

For anyIf an object (other thanof type T is not a potentially-overlapping subobject) of trivially copyable type T, whether or not the object holds a valid value of type T, the underlying bytes ([intro.memory]) making up the object can be copied into an array of char, unsigned char, or std::byte ([cstddef.syn]).[Footnote: […] — end footnote] If the content of that array is copied back into the object, the object shall subsequently holdacquires its original bit value.

[Example:

[…]

— end example]

For two distinct such objects obj1 and obj2 of trivially copyable type T, where neither obj1 nor obj2 is a potentially-overlapping subobject, if the underlying bytes ([intro.memory]) making up obj1 are copied into obj2,[Footnote: […] — end footnote] obj2 shall subsequently holdacquires the samebit value asof obj1.

[Example:

[…]

— end example]

#[basic.compound]

Change paragraph 4:

A pointer value P is valid in the context of an evaluation E if P is a null pointer value, or if it is a pointer to or past the end of an object O and E happens after the beginning and happens before the end of the duration of the region of storage for O. […]

#[expr]

#[expr.reinterpret.cast]

Change paragraphs 4 and 5:

A pointer can be explicitly converted to any integral type large enough to holddistinguish all bit values of its type. The mapping function is implementation-defined.

[Note: It is intended to be unsurprising to those who know the addressing structure of the underlying machine. — end note]

[…]

A value of integral type or enumeration type can be explicitly converted to a pointer. A pointer converted to an integer of sufficient size (if any such exists on the implementation) and back to the same pointer type will have its original valueIf the value is equal to that produced by converting one or more pointer values ([basic.compound]); mappings between pointers and integers are to an integral type, the result is an unspecified choice among those values that would result in the program having defined behavior. If no such value exists, the behavior is undefined.

[Note: It is possible for the result to not be valid in the context of the conversion ([basic.compound]) because it points to an object in a region of storage whose duration has ended or has not yet begun. — end note]

oOtherwise, the result is implementation-defined.

[Note: It can be an invalid pointer value. — end note]

#[expr.eq]

Insert before paragraph 3:

Change paragraph 6:

If two operands compare equal, the result is true for the == operator and false for the != operator. If two operands compare unequal, the result is false for the == operator and true for the != operator. Otherwise, the result of each of the operators is unspecified.

#[bit.cast]

Change paragraph 2:

Returns: An object of type To. Implicitly creates objects nested within the result ([intro.object]). Each bit of the value representation of the result is equal to the corresponding bit in the object representation of from. Padding bits of the result are unspecified. For tThe result and each object created within it, if there is no value of the object’s type acquire the bit values corresponding to the value representation produced; if any such bit value is empty, the behavior is undefined. If there are multiple such values, which value is produced is unspecified. A bit in the value representation of the result is indeterminate if it does not correspond to a bit in the value representation of from or corresponds to a bit for which the smallest enclosing object is not within its lifetime or has an indeterminate value ([basic.indet]). […]

Acknowledgments

Thanks to Richard Smith and Peter Sewell for reviewing an early, overcomplicated draft of this paper. Thanks to Hans Boehm and Paul McKenney for an enlightening discussion of P2414R3.