I am studying Google's filament job system. Currently, I am studying the WorkStealingDequeue they implemented. You can look at the full source code here . This data structure is based on this work. In their implementation of pop and steal, they use memory_order_seq_cst as a full memory barrier.
template <typename TYPE, size_t COUNT>
TYPE WorkStealingDequeue<TYPE, COUNT>::pop() noexcept {
// mBottom is only written in push(), which cannot be concurrent with pop(),
// however, it is read in steal(), so we need basic atomicity.
// i.e.: bottom = mBottom--;
int32_t bottom = mBottom.fetch_sub(1, std::memory_order_relaxed) - 1;
// we need a full memory barrier here; mBottom must be written and visible to
// other threads before we read mTop.
int32_t top = mTop.load(std::memory_order_seq_cst);
if (top < bottom) {
// Queue isn't empty and it's not the last item, just return it.
return getItemAt(bottom);
}
TYPE item{};
if (top == bottom) {
// We took the last item in the queue
item = getItemAt(bottom);
// Items can be added only in push() which isn't concurrent to us, however we could
// be racing with a steal() -- pretend to steal from ourselves to resolve this
// potential conflict.
if (mTop.compare_exchange_strong(top, top + 1,
std::memory_order_seq_cst,
std::memory_order_relaxed)) {
// success: mTop was equal to top, mTop now equals top+1
// We successfully poped an item, adjust top to make the queue canonically empty.
top++;
} else {
// failure: mTop was not equal to top, which means the item was stolen under our feet.
// top now equals to mTop. Simply discard the item we just poped.
// The queue is now empty.
item = TYPE();
}
}
// no concurrent writes to mBottom possible
mBottom.store(top, std::memory_order_relaxed);
return item;
}
template <typename TYPE, size_t COUNT>
TYPE WorkStealingDequeue<TYPE, COUNT>::steal() noexcept {
do {
// mTop must be read before mBottom
int32_t top = mTop.load(std::memory_order_seq_cst);
// mBottom is written concurrently to the read below in pop() or push(), so
// we need basic atomicity. Also makes sure that writes made in push()
// (prior to mBottom update) are visible.
int32_t bottom = mBottom.load(std::memory_order_acquire);
if (top >= bottom) {
// queue is empty
return TYPE();
}
// The queue isn't empty
TYPE item(getItemAt(top));
if (mTop.compare_exchange_strong(top, top + 1,
std::memory_order_seq_cst,
std::memory_order_relaxed)) {
// success: we stole a job, just return it.
return item;
}
// failure: the item we just tried to steal was pop()'ed under our feet,
// simply discard it; nothing to do.
} while (true);
}
For the implementation to be correct, It is required that mBottom to be fetched before mTop in pop() and mTop to be fetched before mBottom in steal(). If we think memory_order_seq_cst as a full memory barrier like most implementation do, then the above code is correct. But from what I understand, C++11 doesn't say anything about memory_order_seq_cst as full memory barrier. From what I understand to ensure the correct ordering then the mBottom fetch_sub operation must be at least std::memory_order_acq_rel. Is my analysis correct?
And then is memory_order_seq_cst on mTop necessary? memory_order_seq_cst force all operation on mTop to be on a single total order(STO). But in this case, the only one that participate in the STO is mTop. I believe we already have modification order guarantee which stated that every threads must agree on the modification order of every variable relative to itself. Is memory_order_acq_rel in the compare_exchange_strong operation enough?
getItemAt(top)
might speculatively read a torn value there, which is technically a "race" and therefore technically UB, but there's no way either compilers or hardware will mess up there. This standard proposal even tries to rectify this defect in the standard by explicitly allowing tearable reads: open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0690r1.html and it explicitly mentions this Lev-Chase algorithm as a possible application of such a feature.