folly/futures/detail/Core.h

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <atomic>
  20 #include <mutex>
  21 #include <stdexcept>
  22 #include <vector>
  23
  24 #include <folly/Optional.h>
  25 #include <folly/MicroSpinLock.h>
  26
  27 #include <folly/futures/Try.h>
  28 #include <folly/futures/Promise.h>
  29 #include <folly/futures/Future.h>
  30 #include <folly/Executor.h>
  31 #include <folly/futures/detail/FSM.h>
  32
  33 #include <folly/io/async/Request.h>
  34
  35 namespace folly { namespace detail {
  36
  37 /*
  38         OnlyCallback
  39        /            \
  40   Start              Armed - Done
  41        \            /
  42          OnlyResult
  43
  44 This state machine is fairly self-explanatory. The most important bit is
  45 that the callback is only executed on the transition from Armed to Done,
  46 and that transition can happen immediately after transitioning from Only*
  47 to Armed, if it is active (the usual case).
  48 */
  49 enum class State : uint8_t {
  50   Start,
  51   OnlyResult,
  52   OnlyCallback,
  53   Armed,
  54   Done,
  55 };
  56
  57 /// The shared state object for Future and Promise.
  58 /// Some methods must only be called by either the Future thread or the
  59 /// Promise thread. The Future thread is the thread that currently "owns" the
  60 /// Future and its callback-related operations, and the Promise thread is
  61 /// likewise the thread that currently "owns" the Promise and its
  62 /// result-related operations. Also, Futures own interruption, Promises own
  63 /// interrupt handlers. Unfortunately, there are things that users can do to
  64 /// break this, and we can't detect that. However if they follow move
  65 /// semantics religiously wrt threading, they should be ok.
  66 ///
  67 /// It's worth pointing out that Futures and/or Promises can and usually will
  68 /// migrate between threads, though this usually happens within the API code.
  69 /// For example, an async operation will probably make a Promise, grab its
  70 /// Future, then move the Promise into another thread that will eventually
  71 /// fulfill it. With executors and via, this gets slightly more complicated at
  72 /// first blush, but it's the same principle. In general, as long as the user
  73 /// doesn't access a Future or Promise object from more than one thread at a
  74 /// time there won't be any problems.
  75 template<typename T>
  76 class Core {
  77   static_assert(!std::is_void<T>::value,
  78                 "void futures are not supported. Use Unit instead.");
  79  public:
  80   /// This must be heap-constructed. There's probably a way to enforce that in
  81   /// code but since this is just internal detail code and I don't know how
  82   /// off-hand, I'm punting.
  83   Core() : result_(), fsm_(State::Start), attached_(2) {}
  84
  85   explicit Core(Try<T>&& t)
  86     : result_(std::move(t)),
  87       fsm_(State::OnlyResult),
  88       attached_(1) {}
  89
  90   ~Core() {
  91     DCHECK(attached_ == 0);
  92   }
  93
  94   // not copyable
  95   Core(Core const&) = delete;
  96   Core& operator=(Core const&) = delete;
  97
  98   // not movable (see comment in the implementation of Future::then)
  99   Core(Core&&) noexcept = delete;
 100   Core& operator=(Core&&) = delete;
 101
 102   // Core is assumed to be convertible only if the type is convertible
 103   // and the size is the same. This is a compromise for the complexity
 104   // of having to make Core truly have a conversion constructor which
 105   // would cause various other problems.
 106   // If we made Core move constructible then we would need to update the
 107   // Promise and Future with the location of the new Core. This is complex
 108   // and may be inefficient.
 109   // Core should only be modified so that for size(T) == size(U),
 110   // sizeof(Core<T>) == size(Core<U>).
 111   // This assumption is used as a proxy to make sure that
 112   // the members of Core<T> and Core<U> line up so that we can use a
 113   // reinterpret cast.
 114   template <
 115       class U,
 116       typename = typename std::enable_if<std::is_convertible<U, T>::value &&
 117                                          sizeof(U) == sizeof(T)>::type>
 118   static Core<T>* convert(Core<U>* from) {
 119     return reinterpret_cast<Core<T>*>(from);
 120   }
 121
 122   /// May call from any thread
 123   bool hasResult() const {
 124     switch (fsm_.getState()) {
 125       case State::OnlyResult:
 126       case State::Armed:
 127       case State::Done:
 128         assert(!!result_);
 129         return true;
 130
 131       default:
 132         return false;
 133     }
 134   }
 135
 136   /// May call from any thread
 137   bool ready() const {
 138     return hasResult();
 139   }
 140
 141   /// May call from any thread
 142   Try<T>& getTry() {
 143     if (ready()) {
 144       return *result_;
 145     } else {
 146       throw FutureNotReady();
 147     }
 148   }
 149
 150   template <typename F>
 151   class LambdaBufHelper {
 152    public:
 153     template <typename FF>
 154     explicit LambdaBufHelper(FF&& func) : func_(std::forward<FF>(func)) {}
 155     void operator()(Try<T>&& t) {
 156       SCOPE_EXIT { this->~LambdaBufHelper(); };
 157       func_(std::move(t));
 158     }
 159    private:
 160     F func_;
 161   };
 162
 163   /// Call only from Future thread.
 164   template <typename F>
 165   void setCallback(F func) {
 166     bool transitionToArmed = false;
 167     auto setCallback_ = [&]{
 168       context_ = RequestContext::saveContext();
 169
 170       // Move the lambda into the Core if it fits
 171       if (sizeof(LambdaBufHelper<F>) <= lambdaBufSize) {
 172         auto funcLoc = reinterpret_cast<LambdaBufHelper<F>*>(&lambdaBuf_);
 173         new (funcLoc) LambdaBufHelper<F>(std::forward<F>(func));
 174         callback_ = std::ref(*funcLoc);
 175       } else {
 176         callback_ = std::move(func);
 177       }
 178     };
 179
 180     FSM_START(fsm_)
 181       case State::Start:
 182         FSM_UPDATE(fsm_, State::OnlyCallback, setCallback_);
 183         break;
 184
 185       case State::OnlyResult:
 186         FSM_UPDATE(fsm_, State::Armed, setCallback_);
 187         transitionToArmed = true;
 188         break;
 189
 190       case State::OnlyCallback:
 191       case State::Armed:
 192       case State::Done:
 193         throw std::logic_error("setCallback called twice");
 194     FSM_END
 195
 196     // we could always call this, it is an optimization to only call it when
 197     // it might be needed.
 198     if (transitionToArmed) {
 199       maybeCallback();
 200     }
 201   }
 202
 203   /// Call only from Promise thread
 204   void setResult(Try<T>&& t) {
 205     bool transitionToArmed = false;
 206     auto setResult_ = [&]{ result_ = std::move(t); };
 207     FSM_START(fsm_)
 208       case State::Start:
 209         FSM_UPDATE(fsm_, State::OnlyResult, setResult_);
 210         break;
 211
 212       case State::OnlyCallback:
 213         FSM_UPDATE(fsm_, State::Armed, setResult_);
 214         transitionToArmed = true;
 215         break;
 216
 217       case State::OnlyResult:
 218       case State::Armed:
 219       case State::Done:
 220         throw std::logic_error("setResult called twice");
 221     FSM_END
 222
 223     if (transitionToArmed) {
 224       maybeCallback();
 225     }
 226   }
 227
 228   /// Called by a destructing Future (in the Future thread, by definition)
 229   void detachFuture() {
 230     activate();
 231     detachOne();
 232   }
 233
 234   /// Called by a destructing Promise (in the Promise thread, by definition)
 235   void detachPromise() {
 236     // detachPromise() and setResult() should never be called in parallel
 237     // so we don't need to protect this.
 238     if (UNLIKELY(!result_)) {
 239       setResult(Try<T>(exception_wrapper(BrokenPromise(typeid(T).name()))));
 240     }
 241     detachOne();
 242   }
 243
 244   /// May call from any thread
 245   void deactivate() {
 246     active_.store(false, std::memory_order_release);
 247   }
 248
 249   /// May call from any thread
 250   void activate() {
 251     active_.store(true, std::memory_order_release);
 252     maybeCallback();
 253   }
 254
 255   /// May call from any thread
 256   bool isActive() { return active_.load(std::memory_order_acquire); }
 257
 258   /// Call only from Future thread
 259   void setExecutor(Executor* x, int8_t priority = Executor::MID_PRI) {
 260     if (!executorLock_.try_lock()) {
 261       executorLock_.lock();
 262     }
 263     executor_ = x;
 264     priority_ = priority;
 265     executorLock_.unlock();
 266   }
 267
 268   void setExecutorNoLock(Executor* x, int8_t priority = Executor::MID_PRI) {
 269     executor_ = x;
 270     priority_ = priority;
 271   }
 272
 273   Executor* getExecutor() {
 274     return executor_;
 275   }
 276
 277   /// Call only from Future thread
 278   void raise(exception_wrapper e) {
 279     if (!interruptLock_.try_lock()) {
 280       interruptLock_.lock();
 281     }
 282     if (!interrupt_ && !hasResult()) {
 283       interrupt_ = folly::make_unique<exception_wrapper>(std::move(e));
 284       if (interruptHandler_) {
 285         interruptHandler_(*interrupt_);
 286       }
 287     }
 288     interruptLock_.unlock();
 289   }
 290
 291   std::function<void(exception_wrapper const&)> getInterruptHandler() {
 292     if (!interruptHandlerSet_.load(std::memory_order_acquire)) {
 293       return nullptr;
 294     }
 295     if (!interruptLock_.try_lock()) {
 296       interruptLock_.lock();
 297     }
 298     auto handler = interruptHandler_;
 299     interruptLock_.unlock();
 300     return handler;
 301   }
 302
 303   /// Call only from Promise thread
 304   void setInterruptHandler(std::function<void(exception_wrapper const&)> fn) {
 305     if (!interruptLock_.try_lock()) {
 306       interruptLock_.lock();
 307     }
 308     if (!hasResult()) {
 309       if (interrupt_) {
 310         fn(*interrupt_);
 311       } else {
 312         setInterruptHandlerNoLock(std::move(fn));
 313       }
 314     }
 315     interruptLock_.unlock();
 316   }
 317
 318   void setInterruptHandlerNoLock(
 319       std::function<void(exception_wrapper const&)> fn) {
 320     interruptHandlerSet_.store(true, std::memory_order_relaxed);
 321     interruptHandler_ = std::move(fn);
 322   }
 323
 324  protected:
 325   void maybeCallback() {
 326     FSM_START(fsm_)
 327       case State::Armed:
 328         if (active_.load(std::memory_order_acquire)) {
 329           FSM_UPDATE2(fsm_, State::Done, []{}, [this]{ this->doCallback(); });
 330         }
 331         FSM_BREAK
 332
 333       default:
 334         FSM_BREAK
 335     FSM_END
 336   }
 337
 338   void doCallback() {
 339     Executor* x = executor_;
 340     int8_t priority;
 341     if (x) {
 342       if (!executorLock_.try_lock()) {
 343         executorLock_.lock();
 344       }
 345       x = executor_;
 346       priority = priority_;
 347       executorLock_.unlock();
 348     }
 349
 350     // keep Core alive until callback did its thing
 351     ++attached_;
 352
 353     if (x) {
 354       try {
 355         if (LIKELY(x->getNumPriorities() == 1)) {
 356           x->add([this]() mutable {
 357             SCOPE_EXIT { detachOne(); };
 358             RequestContext::setContext(context_);
 359             SCOPE_EXIT { callback_ = {}; };
 360             callback_(std::move(*result_));
 361           });
 362         } else {
 363           x->addWithPriority([this]() mutable {
 364             SCOPE_EXIT { detachOne(); };
 365             RequestContext::setContext(context_);
 366             SCOPE_EXIT { callback_ = {}; };
 367             callback_(std::move(*result_));
 368           }, priority);
 369         }
 370       } catch (...) {
 371         --attached_; // Account for extra ++attached_ before try
 372         RequestContext::setContext(context_);
 373         result_ = Try<T>(exception_wrapper(std::current_exception()));
 374         SCOPE_EXIT { callback_ = {}; };
 375         callback_(std::move(*result_));
 376       }
 377     } else {
 378       SCOPE_EXIT { detachOne(); };
 379       RequestContext::setContext(context_);
 380       SCOPE_EXIT { callback_ = {}; };
 381       callback_(std::move(*result_));
 382     }
 383   }
 384
 385   void detachOne() {
 386     auto a = --attached_;
 387     assert(a >= 0);
 388     assert(a <= 2);
 389     if (a == 0) {
 390       delete this;
 391     }
 392   }
 393
 394   // Core should only be modified so that for size(T) == size(U),
 395   // sizeof(Core<T>) == size(Core<U>).
 396   // See Core::convert for details.
 397
 398   // lambdaBuf occupies exactly one cache line
 399   static constexpr size_t lambdaBufSize = 8 * sizeof(void*);
 400   typename std::aligned_storage<lambdaBufSize>::type lambdaBuf_;
 401   // place result_ next to increase the likelihood that the value will be
 402   // contained entirely in one cache line
 403   folly::Optional<Try<T>> result_;
 404   std::function<void(Try<T>&&)> callback_ {nullptr};
 405   FSM<State> fsm_;
 406   std::atomic<unsigned char> attached_;
 407   std::atomic<bool> active_ {true};
 408   std::atomic<bool> interruptHandlerSet_ {false};
 409   folly::MicroSpinLock interruptLock_ {0};
 410   folly::MicroSpinLock executorLock_ {0};
 411   int8_t priority_ {-1};
 412   Executor* executor_ {nullptr};
 413   std::shared_ptr<RequestContext> context_ {nullptr};
 414   std::unique_ptr<exception_wrapper> interrupt_ {};
 415   std::function<void(exception_wrapper const&)> interruptHandler_ {nullptr};
 416 };
 417
 418 template <typename... Ts>
 419 struct CollectAllVariadicContext {
 420   CollectAllVariadicContext() {}
 421   template <typename T, size_t I>
 422   inline void setPartialResult(Try<T>& t) {
 423     std::get<I>(results) = std::move(t);
 424   }
 425   ~CollectAllVariadicContext() {
 426     p.setValue(std::move(results));
 427   }
 428   Promise<std::tuple<Try<Ts>...>> p;
 429   std::tuple<Try<Ts>...> results;
 430   typedef Future<std::tuple<Try<Ts>...>> type;
 431 };
 432
 433 template <typename... Ts>
 434 struct CollectVariadicContext {
 435   CollectVariadicContext() {}
 436   template <typename T, size_t I>
 437   inline void setPartialResult(Try<T>& t) {
 438     if (t.hasException()) {
 439        if (!threw.exchange(true)) {
 440          p.setException(std::move(t.exception()));
 441        }
 442      } else if (!threw) {
 443        std::get<I>(results) = std::move(t);
 444      }
 445   }
 446   ~CollectVariadicContext() {
 447     if (!threw.exchange(true)) {
 448       p.setValue(unwrap(std::move(results)));
 449     }
 450   }
 451   Promise<std::tuple<Ts...>> p;
 452   std::tuple<folly::Try<Ts>...> results;
 453   std::atomic<bool> threw {false};
 454   typedef Future<std::tuple<Ts...>> type;
 455
 456  private:
 457   template <typename... Ts2>
 458   static std::tuple<Ts...> unwrap(std::tuple<folly::Try<Ts>...>&& o,
 459                                   Ts2&&... ts2) {
 460     static_assert(sizeof...(ts2) <
 461                   std::tuple_size<std::tuple<folly::Try<Ts>...>>::value,
 462                   "Non-templated unwrap should be used instead");
 463     assert(std::get<sizeof...(ts2)>(o).hasValue());
 464
 465     return unwrap(std::move(o),
 466                   std::forward<Ts2>(ts2)...,
 467                   std::move(*std::get<sizeof...(ts2)>(o)));
 468   }
 469
 470   static std::tuple<Ts...> unwrap(std::tuple<folly::Try<Ts>...>&& /* o */,
 471                                   Ts&&... ts) {
 472     return std::tuple<Ts...>(std::forward<Ts>(ts)...);
 473   }
 474 };
 475
 476 template <template <typename...> class T, typename... Ts>
 477 void collectVariadicHelper(const std::shared_ptr<T<Ts...>>& /* ctx */) {
 478   // base case
 479 }
 480
 481 template <template <typename ...> class T, typename... Ts,
 482           typename THead, typename... TTail>
 483 void collectVariadicHelper(const std::shared_ptr<T<Ts...>>& ctx,
 484                            THead&& head, TTail&&... tail) {
 485   head.setCallback_([ctx](Try<typename THead::value_type>&& t) {
 486     ctx->template setPartialResult<typename THead::value_type,
 487                                    sizeof...(Ts) - sizeof...(TTail) - 1>(t);
 488   });
 489   // template tail-recursion
 490   collectVariadicHelper(ctx, std::forward<TTail>(tail)...);
 491 }
 492
 493 }} // folly::detail