Mbed-os: core_util_atomic_cas_u32() - retry on failure?

[danny4478]

This issue refers to core_util_atomic_cas_u32() in mbed_critical.c file.

According to the pseudo code code in header file this function should save new value in case comparison fails.
But: The implementation returns failure in case __STREXW fails.

As we see it:
We should add a do-while loop here as we did in core_util_atomic_incr_u8().
__STREXW can fail in case there was a context switch and the exclusiveness is not guaranteed.
In this case the function should retry, rather than fail and offload retry logic to the caller code.

Reviewrs: @alzix

[0xc0170]

cc @pan- @scartmell-arm

[pan-]

@danny4478 Retry logic has to be offloaded to the caller, it works that way for C and C++ standard atomic for a good reaon: Often the caller needs to update the value it wants to set if the compare fail.

As an example consider the insertion of a new head pointer in an atomic linked list:

```C++
template
struct list {
void push_front(const T& data)
{
node* new_node = node(data);
new_node->next = head;

    // new_node->next is replaced by core_util_atomic_cas_ptr in case of
    // faillure
    while(!core_util_atomic_cas_ptr(
        /* to replace */reinterpret_cast<void**>(&head), 
        /* expected */ reinterpret_cast<void**>(&new_node->next), 
        /* desiredValue */ reinterpret_cast<void*>(new_node) 
    );
}

private:
template
struct node {
node* next;
T data;
node(const T& data) : next(NULL), data(data) { }
};

node<T>* head;

}
``````

It wouldn't be possible to write such code if the retry logic was in core_util_atomic_cas_ptr and the retry logic would destroy consistency of the data structure and orphan nodes or reference destroyed nodes.

[0xc0170]

@danny4478 please read https://blogs.oracle.com/dave/atomic-fetch-and-add-vs-compare-and-swap

[pan-]

@danny4478 Looking at the atomic API, there is no function for atomic exchange. That might be the one you're looking for:

uint32_t core_util_atomic_exchange_u32(volatile uint32_t* ptr, uint32_t desired);

[kjbracey-arm]

The CAS implementations do differ here - the LDREX/STREX one is weak, the enter/exit critical one is strong.

It would be perfectly possible to have a strong implementation that retries when the STREX fails. The C and C++ standard provides having both versions.

The documentation for the mbed one doesn't say whether it's strong or weak, but I would have assumed it to be strong.

As it stands the critical section version is strong, and only fails if the old value isn't the expected value. The LDREX/STREX one is weak, and can spuriously fail when the old value is the expected value.

[kjbracey-arm]

Actually, there's a clear discrepancy. The pseudocode says it's strong:

  if *p != *old {
      *old = *p
      return false
  }
  *p = new
  return true

LDREX/STREX version behaviour is actually:

  if *p != *old {
      *old = *p
      return false
  }
  if we're lucky {
      *p = new
      return true
  } else {
      return false;
  }

[kjbracey-arm]

@pan- Yes, many algorithms like your example that use CAS are looping anyway, so spurious failures don't hurt them, so they can happily use a weak function - their loop covers both multithreading issues and spurious failures.

But other algorithms may not need to loop - they want a strong CAS that always works if the value matches, and only returns false if another thread has messed with the data.

Hence having both in the C/C++ standards (atomic_compare_exchange_strong/atomic_compare_exchange_weak).

In this case, I think you either need to upgrade the LDREX/STREX CAS to be strong to match the pseudocode (retry the compare on STREX failure), or adjust the pseudocode and documentation to say that it's weak.

[pan-]

@kjbracey-arm Why not have both weak and strong CAS ? It would makes porting of code exploiting atomic operations easier.

[kjbracey-arm]

Indeed, under clear weak and strong names.

Still need to figure out what the intended behaviour of the current call is though - I guess it has to be strong, given that it's safer, matches what the documentation says, and the weak LDREX version isn't being invoked anyway, so everyone's currently getting strong behaviour.

[danny4478]

OK. It looks like I would have to use my own implementation if I want to use __LDREX() / __STREX() with a retry in a loop.
IMHO, the documentation needs to change anyway.

[alzix]

I see another problem here. core_util_atomic_cas_u32 has two implementations (guarded by #if __EXCLUSIVE_ACCESS ) within the very same file but with a different behaviors.
I believe this is not only a pseudocode documentation issue, as it can potentially lead to portability issues.

[0xc0170]

@alzix That is another issue with this: #5555 where we can resolve it

[alzix]

5555 deals with selecting the the implementation.

This issue deals with behavior differences between the two implementations.
IMHO this issue should be addressed by either proper documentation as suggested by @kjbracey-arm or by fixing the actual implementation

[0xc0170]

Is this possible to fix by editing only documentation?

@kjbracey-arm Can you send a fix to address this?

[pan-]

@0xc0170 Not sure how this can be fixed with the documentation; one implementation based on critical section is a strong CAS while the other that uses a monitor is a weak CAS.

[kjbracey-arm]

You _could_ just document the existing call as weak. A weak CAS isn't _required_ to ever spuriously fail, so both implementations are valid weak ones.

Perfectly possible, but feels a bit like a trap, as users didn't actually look at a pair labelled "strong" and "weak" and mindfully choose the weak one.

I'll start with a minimal change that makes it strong in both cases. No-one ever /needs/ a weak implementation - it's just a potential optimisation to avoid a loop within a loop.