5

I'm working on a coroutine multiple-producers, single-consumer Event (here it is, for context). Simplified:

class WaitList {
 public:
  void Append() { coro_.store(GetCurrentCoro()); }
  void Remove() { coro_.store({}); }

  void WakeUp() {
    auto p = coro_.exchange({});
    if (p) p->WakeUpIfSleeping();
  }

 private:
  std::atomic<Coro*> coro_{nullptr};
};

class Event {
 public:
  void Wait() {
    waiters_.Append();
    if (IsReady()) waiters_.WakeUp();
    // fall asleep
    // ...
    // woken up
    waiters_.Remove();
  }

  void Send() {
    SetReady();
    waiters_.WakeUp();
  }

 private:
  bool IsReady() { return signal_.load(); }
  void SetReady() { return signal_.store(true); }

  WaitList waiters_;
  std::atomic<bool> signal_{false};
};

Please help me set the minimum required std::memory_orders for:

  1. Append
  2. IsReady
  3. SetReady
  4. WakeUp (talking about the exchange)
  5. Remove

The primary platform is x86_64, but being optimal for other platforms is welcome. If there are multiple local minima, you can list them all (there is a finite number of theoretically possible combinations: sizeof(std::memory_order) ^ 5).

It seems to me that 1-4 require std::memory_order_seq_cst, because:

  1. If Append and IsReady are reordered from the POV of Send thread, then after the sequence IsReady-SetReady-WakeUp-Append the coroutine will fall asleep forever (right?)
  2. If SetReady and WakeUp are reordered from the POV of Wait thread, then after the sequence WakeUp-Append-IsReady-SetReady the coroutine will fall asleep forever (right?)

Given that we are dealing with two atomics (coro_ and signal_), I'd expect acquire-release not to be enough.

I know it is possible to squash coro_ and signal_ into a single std::uintptr_t or something, but let's leave them as they are for the purpose of this exercise. It's not as simple in reality: there are multiple synchronization primitives all based around the same ideas, and the current layout generalizes to them well.

Anton3
  • 577
  • 4
  • 14
  • 2
    Can you show the usage pattern per thread? And do you use reuse the Events? – Homer512 Aug 18 '22 at 10:53
  • One thread calls `Wait`, and other threads call `Send`, possibly multiple times, at unrelated moments of time. All threads are guaranteed to finish before `Event` is destroyed (this part is out of scope of the question). Events can be reused, but for the sake of simplicity, let's say they cannot be reset, so the 2nd+ `Wait` operation should always wake up immediately. – Anton3 Aug 18 '22 at 11:49
  • 1
    Can you be more precise about what semantics are desired? What are the conditions under which a wakeup is supposed to occur, or not occur? – Nate Eldredge Aug 20 '22 at 17:56
  • The coroutine calling `Event::Wait` expects to be woken up as soon as `signal_ == true` – Anton3 Aug 21 '22 at 14:28
  • When a coroutine is sleeping, it wakes up (gets scheduled) as soon as `WakeUp` is called. If `WakeUp` has already been called by the time it falls asleep, it wakes up immediately. The details of how coroutine scheduling works are not very important here, I think. The main problem is how not to allow the waiter coroutine to miss an incoming signal and fall asleep forever. – Anton3 Aug 21 '22 at 14:31
  • This question is being [discussed on meta](https://meta.stackoverflow.com/questions/420254). – cigien Sep 07 '22 at 15:00
  • If the coroutine is woken by `WakeUpIfSleeping`, why does it care about the value of `signal_`? It can't be planning to call `Wait` again immediately, because that will just call `WakeUp` exactly the same as `Send` did. I'm not sure you _need_ `signal_` and `coro_` to be as tightly coupled as they are – Useless Sep 07 '22 at 16:49

0 Answers0