mardi 28 avril 2020

When can memory_order_acquire or memory_order_release be safely removed from compare_exchange?

I refer to the code in Lewiss Baker's coroutine tutorial.

https://lewissbaker.github.io/2017/11/17/understanding-operator-co-await

bool async_manual_reset_event::awaiter::await_suspend(
  std::experimental::coroutine_handle<> awaitingCoroutine) noexcept
{
  // Special m_state value that indicates the event is in the 'set' state.
  const void* const setState = &m_event;

  // Remember the handle of the awaiting coroutine.
  m_awaitingCoroutine = awaitingCoroutine;

  // Try to atomically push this awaiter onto the front of the list.
  void* oldValue = m_event.m_state.load(std::memory_order_acquire);
  do
  {
    // Resume immediately if already in 'set' state.
    if (oldValue == setState) return false; 

    // Update linked list to point at current head.
    m_next = static_cast<awaiter*>(oldValue);

    // Finally, try to swap the old list head, inserting this awaiter
    // as the new list head.
  } while (!m_event.m_state.compare_exchange_weak(
             oldValue,
             this,
             std::memory_order_release,
             std::memory_order_acquire));

  // Successfully enqueued. Remain suspended.
  return true;
}

where m_state is just a std::atomic<void *>.

bool async_manual_reset_event::is_set() const noexcept
{
  return m_state.load(std::memory_order_acquire) == this;
}
void async_manual_reset_event::reset() noexcept
{
  void* oldValue = this;
  m_state.compare_exchange_strong(oldValue, nullptr, std::memory_order_acquire);
}
void async_manual_reset_event::set() noexcept
{
  // Needs to be 'release' so that subsequent 'co_await' has
  // visibility of our prior writes.
  // Needs to be 'acquire' so that we have visibility of prior
  // writes by awaiting coroutines.
  void* oldValue = m_state.exchange(this, std::memory_order_acq_rel);
  if (oldValue != this)
  {
    // Wasn't already in 'set' state.
    // Treat old value as head of a linked-list of waiters
    // which we have now acquired and need to resume.
    auto* waiters = static_cast<awaiter*>(oldValue);
    while (waiters != nullptr)
    {
      // Read m_next before resuming the coroutine as resuming
      // the coroutine will likely destroy the awaiter object.
      auto* next = waiters->m_next;
      waiters->m_awaitingCoroutine.resume();
      waiters = next;
    }
  }
}

Note in m_state.exchange of the set() method, the comment above shows clearly why the call to exchange requires both acquire and release.

I wonder why in the m_state.compare_exchange_weak of the await_suspend() method, the third parameter is a std::memory_order_release but not a memory_order_acq_rel (the acquire is removed).

The author (Lewis) did explain that we need release in the compare_exchange_weak because we need to let later set() see the writes in compare_exchange_weak. But why don't we require other compare_exchange_weak in other threads to see the writes in the current compare_exchange_weak?

Is it because of release sequence? I.e., in a release chain (write release at first, and all the middle operations are "read acquire then write release" operations, and the final operation is read acquire), then you don't need to tell them to acquire in the middle?

In the following code, I tried to implement a shared lock,

    struct lock {
        uint64_t exclusive : 1;
        uint64_t id : 48;
        uint64_t shared_count : 15;
    };
    std::atomic<lock> lock_ { {0, 0, 0} };
    bool try_lock_shared() noexcept {
        lock currentlock = lock_.load(std::memory_order_acquire);
        if (currentlock.exclusive == 1) {
            return false;
        }
        lock newlock;
        do {
            newlock = currentlock;
            newlock.shared_count++;
        }
        while(!lock_.compare_exchange_weak(currentlock, newlock, std::memory_order_acq_rel) && currentlock.exclusive == 0);

        return currentlock.exclusive == 0;
    }
    bool try_lock() noexcept {
        uint64_t id = utils::get_thread_id();
        lock currentlock = lock_.load(std::memory_order_acquire);
        if (currentlock.exclusive == 1) {
            assert(currentlock.id != id);
            return false;
        }

        bool result = false;
        lock newlock { 1, id, 0 };
        do {
            newlock.shared_count = currentlock.shared_count;
        }
        while(!(result = lock_.compare_exchange_weak(currentlock, newlock, std::memory_order_acq_rel)) && currentlock.exclusive == 0);

        return result;
    }

I used lock_.compare_exchange_weak(currentlock, newlock, std::memory_order_acq_rel) everywhere, can I safely replace them to compare_exchange_weak(currentlock, newlock, std::memory_order_release, std::memory_order_acquire) ?

I could also see examples that memory_order_release is removed from compare_exchange_strong (see the compare_exchange_strong in reset() function of Lewis code), where you only need std::memory_order_acquire for compare_exchange_strong (but not release). I didn't really see memory_order_release is removed from weak nor memory_order_acquire is removed from strong.

This made me wonder whether there's deeper rule that I didn't understand or not.

Thanks.

Aucun commentaire:

Enregistrer un commentaire