I discussed this with some experts; OOTA does not apply here. The decrement in drop(weak) is ordered after the cmpxchg in weak.upgrade(), but that's different from depending on it. So it cannot be used in an OOTA dependency cycle.
That said, the bad execution will never happen in practice. But it's allowed by the standard.
OOTA is impossible in real implementations but the standard technically permits it. Could you give more details about why the experts say OOTA does not apply here? As I given in my above comment, the equivalent code does form the circular computation.
That said, the bad execution will never happen in practice. But it's allowed by the standard.
This just sounds like OOTA(i.e. OOTA can theoretically happen but never happen in practice).
The decrement inside drop(weak) is always performed in the same way, no matter what happens inside weak.upgrade(). Just because one happens before the other does not imply an actual dependency.
If the thread 2 is logically equivalent to the following:
// thread 2:
if weak.inner()?.strong_count.fetch_add(1,2, Acquire, Relaxed).is_ok(){ // #3
// obtain arc
drop(weak);
}else{
// None
drop(weak);
}
it obvious that the evaluation of drop(weak) depends on the result of strong_count, which forms the circular dependency computation.
The unclear part is the original code is:
// thread 1:
if weak_count.load(Relaxed) == 1{ // #1
strong_count.store(1, Relaxed); // #2
}
// thread 2
let maybe_arc = weak.upgrade();
/*
let mut pre = strong_count.load(relaxed);
while(pre !=0){
if Err(e) = strong_count.compare_exchange(pre,pre+1,Acquire, Relaxed){
pre = e;
continue;
}
break;
}
*/
drop(weak);
The evaluation of weak.upgrade() invokes the code like something in the comment. The execution of drop(weak) depends on pre. For example, pre==1 and the CAS failed such that the loop is not exited, the drop(weak) won't be executed.
If you change the code you also change which dependencies exist. It's not equivalent from a dependency perspective.
Well, from the original code:
// thread 1:
if weak_count.load(Relaxed) == 1{ // #1
strong_count.store(1, Relaxed); // #2
}
// thread 2
let maybe_arc = weak.upgrade();
/*
let mut pre = strong_count.load(relaxed);
while(pre !=0){
if Err(e) = strong_count.compare_exchange(pre,pre+1,Acquire, Relaxed){
pre = e;
continue;
}
break;
}
*/
drop(weak);
The codes within weak.upgrade() are those in the comment. The evaluation of the loop depends on the value of pre, the drop(weak) won't be executed when the loop does not exit. The exit of the loop depends on the value of pre. Doesn't this form a circular dependency?
In this case, the loop is always going to exit after at most two iterations, so drop(weak) is always executed.
Ok, you meant the loop can eventually exit such that drop(weak) is executed, the evaluation of drop(weak) does not depend on pre, so the code has no circular dependency computation, right?
If the loop were something like
// thread 1:
if weak_count.load(Relaxed) == 1{ // #1
strong_count.store(1, Relaxed); // #2
}
// thread 2:
while strong_count.load(relaxed) !=1{}
drop(weak);
This would be OOTA?
For the original code, if there are magnitude other threads where the code is like thread 2, the CAS in the loop can fail such that the loop can run for a long time, and the drop(weak) won't be executed before the loop exits, is this a kind of circular dependency computation?
The key is that there is a loop within the upgrade. It is just like a spin lock with a failed cmpxchg(i.e., a while loop with the condition of a pure load with Relaxed memory order). The code sequenced after the loop cannot be executed until the while exits. It is the same that the spin-lock might exit after at most two iterations or be a long-time run loop. The compiler shouldn't assume the loop can exit quickly, so the subsequent codes are always executed.