X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FBaton.h;h=833239153d8567fb356258c42f484db3ee8b0343;hb=16a97089051c76dd187a4a25018965cc44e330e0;hp=c87a086e8a3c47b5ca1080cf771e1c46be8e686f;hpb=a3b85e00633ea9f955abaa4114e92023ee94494b;p=folly.git diff --git a/folly/Baton.h b/folly/Baton.h index c87a086e..83323915 100644 --- a/folly/Baton.h +++ b/folly/Baton.h @@ -1,5 +1,5 @@ /* - * Copyright 2014 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,44 +14,62 @@ * limitations under the License. */ -#ifndef FOLLY_BATON_H -#define FOLLY_BATON_H +#pragma once +#include +#include #include #include -#include -#include -#include +#include #include #include +#include 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> -struct Baton : boost::noncopyable { - Baton() : state_(INIT) {} +/// 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) {} + + Baton(Baton const&) = delete; + Baton& operator=(Baton const&) = delete; /// It is an error to destroy a Baton on which a thread is currently /// wait()ing. In practice this means that the waiter usually takes /// responsibility for destroying the Baton. ~Baton() { - // The docblock for this function says that is can't be called when + // The docblock for this function says that it can't be called when // there is a concurrent waiter. We assume a strong version of this // requirement in which the caller must _know_ that this is true, they // are not allowed to be merely lucky. If two threads are involved, @@ -94,32 +112,82 @@ struct Baton : boost::noncopyable { } /// 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); + + if (before == INIT && + state_.compare_exchange_strong(before, EARLY_DELIVERY)) { + return; + } - assert(before == WAITING); - state_.store(LATE_DELIVERY, std::memory_order_release); - state_.futexWake(1); + 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. @@ -137,6 +205,13 @@ struct Baton : boost::noncopyable { 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)) { @@ -187,6 +262,8 @@ struct Baton : boost::noncopyable { /// 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; @@ -215,6 +292,13 @@ struct Baton : boost::noncopyable { } } + /// Similar to timed_wait, but with a duration. + template + bool timed_wait(const Duration& duration) { + auto deadline = Clock::now() + duration; + return timed_wait(deadline); + } + /// Similar to wait, but doesn't block the thread if it hasn't been posted. /// /// try_wait has the following semantics: @@ -226,7 +310,7 @@ struct Baton : boost::noncopyable { /// 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; @@ -273,13 +357,11 @@ struct Baton : boost::noncopyable { // hooray! return true; } -#if FOLLY_X64 // The pause instruction is the polite way to spin, but it doesn't // actually affect correctness to omit it if we don't have it. // Pausing donates the full capabilities of the current core to // its other hyperthreads for a dozen cycles or so - asm volatile ("pause"); -#endif + asm_volatile_pause(); } return false; @@ -289,5 +371,3 @@ struct Baton : boost::noncopyable { }; } // namespace folly - -#endif