[basic.stc.dynamic.allocation] p2 "was subsequently passed to a replaceable deallocation function" is vague in a multithread context

[xmh0511]

Full name of submitter (unless configured in github; will be published with the issue): Jim X

Consider this example:

#include <thread>
#include <atomic>

int main(){
   std::atomic<bool> flag = false;
   std::jthread t1([&](){
      auto p = operator new(sizeof(int));  // #1
      while(!flag.load(std::memory_order::acquire));
      operator delete(p); // #2
   });

  std::jthread t2([&](){
    auto p2 = operator new(sizeof(int));  // #3
    flag.store(true,std::memory_order::release);
  });
}

In this example, both #1 and #3 happen-before #2. Can both #1 and #3 return the same address? The relevant rule is [basic.stc.dynamic.allocation] p2

If the request succeeds, the value returned by a replaceable allocation function is a non-null pointer value ([basic.compound]) p0 different from any previously returned value p1, unless that value p1 was subsequently passed to a replaceable deallocation function.

In a multithread context, it's hard to say what "previously returned" and "was subsequently passed to a replaceable deallocation function" mean. There is no global timeline across different threads.

Suggested Resolution:

We may need to define what "previously returned" and "was subsequently passed to a replaceable deallocation function" in terms of happens-before.

[safocl]

In a multithread context, it's hard to say what "previously returned" and "was subsequently passed to a replaceable deallocation function" mean. There is no global timeline across different threads.

In my opinion, the wording is quite clear and straightforward. It explicitly states that the allocation function must always (in the context of the discussion) return a pointer to an address that has not previously been allocated. At the same time, in my opinion, it's also explicitly stated that the only time such a pointer can be returned for the same address is when that pointer to that address has already been passed to the deallocation function. There's no dependency on multithreading here—only the criterion for currently passing a pointer to the deallocation function. In other words, this simply doesn't limit the pool of addresses in the returned pointers to a pool of exclusively unique, new memory addresses.

[safocl]

Can both #1 and #2 return the same address?

If we are talking about #1 and #3, then it clearly and unambiguously cannot, since both of these lines will be made before line #2 (passed to a replaceable deallocation function).

[xmh0511]

only time such a pointer can be returned for the same address is when that pointer to that address has already been passed to the deallocation function.

This completely is your intuition, not what the standard defines order. Anyway, as I said in the issue, there is no global timeline across multiple threads. You cannot say what "has already been" means in multiple threads.

[safocl]

This completely is your intuition, not what the standard defines order.

No, I'm sure that's exactly what the standard is about -- it stipulates that until pointer p1 is passed to the deallocation function, pointer p0 returned from the allocation function cannot contain the same address as p1.

Anyway, as I said in the issue, there is no global timeline across multiple threads. You cannot say what "has already been" means in multiple threads.

The allocation and deallocation functions aren't thread-specific. According to the rule presented in the discussion, they're required to track all calls, regardless of the thread in which they were made. Therefore, I don't really see any confusion in the standard on this matter. The allocation and deallocation functions manage the program's dynamic memory — it's shared across all program code.

[jensmaurer]

I'm sure there is a reformulation that uses "happens-before" instead of "previously" and "subsequently". Specific suggestions welcome.

[xmh0511]

The possible suggestion might be:

If the request succeeds, the value returned by a replaceable allocation function is a non-null pointer value ([basic.compound]) p0. p0 that is successfully returned by a replaceable allocation function calling A and p1 that is successfully returned by a replaceable allocation function calling B may be the same value if:

• B happens before A and
• There is a replaceable deallocation function C to which p1 is passed, such that B happens before C and C happens before A, and there is no other replaceable allocation function calling X such that C happens before X and X happens before A.

This may be too verbose. A brief way is to associate the definition with a total order; the above suggestion does the same thing indirectly.

[new.delete.dataraces]

Calls to these functions that allocate or deallocate a particular unit of storage shall occur in a single total order, and each such deallocation call shall happen before the next allocation (if any) in this order.

We just hand-wave to say they occur in a single total order; however, we never associated the single total order with coherence rules defined in [intro.races]

For example, according to the write-write coherence rule:

If an operation A that modifies an atomic object M happens before an operation B that modifies M, then A is earlier than B in the modification order of M.

The proposed wording might be:

If the request succeeds, the value returned by a replaceable allocation function is a non-null pointer value ([basic.compound]) p0. p0 that is successfully returned by a replaceable allocation function calling A and p1 that is successfully returned by a replaceable allocation function calling B may be the same value if there exists a replaceable deallocation function calling C to which p1 is passed such that B immedidately precedes C and C immediately precedes A in the single total order.

Under these changes, then according to the write-write coherence rule, #1 < #2 in the single total order. Then we can use proof by contradiction here. Assuming #3 returns the same value, then according to the above change, the single total order must be #1 < #2 < #3, then [new.delete.dataraces] says #2 happens before #3. This would make the loop never exit. So the assumption is false.

[xmh0511]

Reference to the similar consensus here, see cplusplus/papers#2665 (comment)

We may apply the same approach here too

Clarify the single total order is consistent with HB