X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FBaton.h;h=833239153d8567fb356258c42f484db3ee8b0343;hp=e0f66951dfc185e25a4adefc1e155c0730d92e78;hb=f795d501ba155f3fac9ed8bec40cbbc8eb4045ad;hpb=05499631dc3e1160d673a7dd57e70fc797e532dc diff --git a/folly/Baton.h b/folly/Baton.h index e0f66951..83323915 100644 --- a/folly/Baton.h +++ b/folly/Baton.h @@ -16,10 +16,11 @@ #pragma once +#include +#include #include #include -#include -#include +#include #include #include @@ -27,22 +28,37 @@ namespace folly { -/// A Baton allows a thread to block once and be awoken: it captures -/// a single handoff. During its lifecycle (from construction/reset to -/// destruction/reset) a baton must either be post()ed and wait()ed exactly -/// once each, or not at all. +/// A Baton allows a thread to block once and be awoken. The single +/// poster version (with SinglePoster == true) captures a single +/// handoff, and during its lifecycle (from construction/reset to +/// destruction/reset) a baton must either be post()ed and wait()ed +/// exactly once each, or not at all. +/// +/// The multi-poster version (SinglePoster == false) allows multiple +/// concurrent handoff attempts, the first of which completes the +/// handoff and the rest if any are idempotent. /// /// Baton includes no internal padding, and is only 4 bytes in size. /// Any alignment or padding to avoid false sharing is up to the user. /// -/// This is basically a stripped-down semaphore that supports only a -/// single call to sem_post and a single call to sem_wait. The current -/// posix semaphore sem_t isn't too bad, but this provides more a bit more -/// speed, inlining, smaller size, a guarantee that the implementation -/// won't change, and compatibility with DeterministicSchedule. By having -/// a much more restrictive lifecycle we can also add a bunch of assertions -/// that can help to catch race conditions ahead of time. -template class Atom = std::atomic> +/// This is basically a stripped-down semaphore that supports (only a +/// single call to sem_post, when SinglePoster == true) and a single +/// call to sem_wait. +/// +/// The non-blocking version (Blocking == false) provides more speed +/// by using only load acquire and store release operations in the +/// critical path, at the cost of disallowing blocking and timing out. +/// +/// The current posix semaphore sem_t isn't too bad, but this provides +/// more a bit more speed, inlining, smaller size, a guarantee that +/// the implementation won't change, and compatibility with +/// DeterministicSchedule. By having a much more restrictive +/// lifecycle we can also add a bunch of assertions that can help to +/// catch race conditions ahead of time. +template < + template class Atom = std::atomic, + bool SinglePoster = true, // single vs multiple posters + bool Blocking = true> // blocking vs spinning struct Baton { constexpr Baton() : state_(INIT) {} @@ -96,32 +112,82 @@ struct Baton { } /// Causes wait() to wake up. For each lifetime of a Baton (where a - /// lifetime starts at construction or reset() and ends at destruction - /// or reset()) there can be at most one call to post(). Any thread - /// may call post(). - /// - /// Although we could implement a more generic semaphore semantics - /// without any extra size or CPU overhead, the single-call limitation - /// allows us to have better assert-ions during debug builds. + /// lifetime starts at construction or reset() and ends at + /// destruction or reset()) there can be at most one call to post(), + /// in the single poster version. Any thread may call post(). void post() { - uint32_t before = state_.load(std::memory_order_acquire); - - assert(before == INIT || before == WAITING || before == TIMED_OUT); - - if (before == INIT && - state_.compare_exchange_strong(before, EARLY_DELIVERY)) { + if (!Blocking) { + /// Non-blocking version + /// + assert([&] { + auto state = state_.load(std::memory_order_relaxed); + return (state == INIT || state == EARLY_DELIVERY); + }()); + state_.store(EARLY_DELIVERY, std::memory_order_release); return; } - assert(before == WAITING || before == TIMED_OUT); + /// Blocking versions + /// + if (SinglePoster) { + /// Single poster version + /// + uint32_t before = state_.load(std::memory_order_acquire); - if (before == TIMED_OUT) { - return; - } + assert(before == INIT || before == WAITING || before == TIMED_OUT); - assert(before == WAITING); - state_.store(LATE_DELIVERY, std::memory_order_release); - state_.futexWake(1); + if (before == INIT && + state_.compare_exchange_strong(before, EARLY_DELIVERY)) { + return; + } + + assert(before == WAITING || before == TIMED_OUT); + + if (before == TIMED_OUT) { + return; + } + + assert(before == WAITING); + state_.store(LATE_DELIVERY, std::memory_order_release); + state_.futexWake(1); + } else { + /// Multi-poster version + /// + while (true) { + uint32_t before = state_.load(std::memory_order_acquire); + + if (before == INIT && + state_.compare_exchange_strong(before, EARLY_DELIVERY)) { + return; + } + + if (before == TIMED_OUT) { + return; + } + + if (before == EARLY_DELIVERY || before == LATE_DELIVERY) { + // The reason for not simply returning (without the following + // atomic operation) is to avoid the following case: + // + // T1: T2: T3: + // local1.post(); local2.post(); global.wait(); + // global.post(); global.post(); local1.try_wait() == true; + // local2.try_wait() == false; + // + if (state_.fetch_add(0) != before) { + continue; + } + return; + } + + assert(before == WAITING); + if (!state_.compare_exchange_weak(before, LATE_DELIVERY)) { + continue; + } + state_.futexWake(1); + return; + } + } } /// Waits until post() has been called in the current Baton lifetime. @@ -139,6 +205,13 @@ struct Baton { return; } + if (!Blocking) { + while (!try_wait()) { + std::this_thread::yield(); + } + return; + } + // guess we have to block :( uint32_t expected = INIT; if (!state_.compare_exchange_strong(expected, WAITING)) { @@ -189,6 +262,8 @@ struct Baton { /// false otherwise template bool timed_wait(const std::chrono::time_point& deadline) { + static_assert(Blocking, "Non-blocking Baton does not support timed wait."); + if (spinWaitForEarlyDelivery()) { assert(state_.load(std::memory_order_acquire) == EARLY_DELIVERY); return true; @@ -235,7 +310,7 @@ struct Baton { /// call wait, try_wait or timed_wait on the same baton without resetting /// /// @return true if baton has been posted, false othewise - bool try_wait() { + bool try_wait() const { auto s = state_.load(std::memory_order_acquire); assert(s == INIT || s == EARLY_DELIVERY); return s == EARLY_DELIVERY;