Notes on Folly: Folly Fibers

2019-09-18
c++

The folly::fibers provides a set of constructs for cooperative context switch. In this post, we explains in detail how tasks are scheduled and executed in FiberManager.

As usual, let’s start with an example. In this example, we simply let FiberManager run two tasks consecutively: when one task finishes, another task starts. It doesn’t involve complex control transfers. Once we’ve understood how different components work together, we’ll get to the part where tasks yields to others in the middle of the control flow.

#include <folly/fibers/EventBaseLoopController.h>
#include <folly/fibers/FiberManager.h>
#include <folly/init/Init.h>
#include <glog/logging.h>

using folly::fibers::EventBaseLoopController;
using folly::fibers::FiberManager;

int main(int argc, char *argv[]) {
  folly::init(&argc, &argv);

  folly::EventBase evb;

  std::unique_ptr<EventBaseLoopController> loopController =
      std::make_unique<EventBaseLoopController>();
  loopController->attachEventBase(evb);

  FiberManager fiberManager(std::move(loopController), FiberManager::Options());
  folly::fibers::Baton baton;

  fiberManager.addTask([&] {
    LOG(INFO) << "task1: start\n";
    LOG(INFO) << "task1: finish()\n";
  });

  fiberManager.addTask([&] {
    LOG(INFO) << "task2: start\n";
    LOG(INFO) << "task2: finish\n";
  });

  LOG(INFO) << "Start looping";
  evb.loop();
}

compile using 

g++ -std=c++17 test.cc /usr/local/lib/libfolly.a /usr/lib/x86_64-linux-gnu/libiberty.a  -lgtest  -lglog  -lgflags -lpthread -ldl -ldouble-conversion -levent -lboost_context

The result is

$ ./a.out -alsologtostderr
I0921 16:28:43.240685   277 test.cc:31] Start looping
I0921 16:28:43.241350   277 test.cc:22] task1: start
I0921 16:28:43.241384   277 test.cc:23] task1: finish
I0921 16:28:43.241406   277 test.cc:27] task2: start
I0921 16:28:43.241430   277 test.cc:28] task2: finish
I0921 16:28:43.241499   277 test.cc:33] End looping

This number 277 is the thread number. We see all above code was running in only one thread.

FiberManager

How did FiberManager manages multiple tasks?

template <typename F>
void FiberManager::addTask(F&& func) {
  readyFibers_.push_back(*createTask(std::forward<F>(func)));
  ensureLoopScheduled();
}

addTask simply puts the task in readyFibers_, and ensureLoopScheduled calls schedule of loopController_:

inline void FiberManager::ensureLoopScheduled() {
  if (isLoopScheduled_) {
    return;
  }

  isLoopScheduled_ = true;
  loopController_->schedule();
}

We can guess schedule makes sure the task will run in the future. Because we’re using EventBaseLoopController, the controller simply calls EventBase‘s schedule:

inline void EventBaseLoopController::schedule() {
  if (eventBase_ == nullptr) {
    // In this case we need to postpone scheduling.
    awaitingScheduling_ = true;
  } else {
    // Schedule it to run in current iteration.

    if (!eventBaseKeepAlive_) {
      eventBaseKeepAlive_ = getKeepAliveToken(eventBase_);
    }
    eventBase_->getEventBase().runInLoop(&callback_, true);
    awaitingScheduling_ = false;
  }
}

So it calls into EventBase‘s runInLoop, which, if you take a look at EventBase code, simply adds the callback_ to its queue. Only when EventBase starts its loop, this callback_ will be pulled out to execute its runLoopCallback method.

So what’s the callback_ here?

inline EventBaseLoopController::EventBaseLoopController() : callback_(*this) {}

That’s our controller! Our controller is a subclass of folly::EventBase::LoopCallback that implements runLoopCallback, which is

void runLoopCallback() noexcept override {
  controller_.runLoop();
}

In sum, when EventBase executes its loop, it calls our EventBaseLoopController‘s runLoop method. How’s this method implemented in EventBaseLoopController?

fm_->loopUntilNoReadyImpl();

Oh yes, of course! EventBaseLoopController degelates the loop in FiberManager ! FiberManager has all information about all pending fibers, the current running fiber. It’s natural to let it drive the loop.

Note that because runInLoop should only be called from the EventBase’s thread, addTask is not thread-safe, and folly offers addTaskRemote for thread-safe access.

Now let’s pause a while on FiberManager and let’s take a look at the Task we’ve saved in readyFibers_ list.

Fiber

We see FiberManager::addTask calls

readyFibers_.push_back(*createTask(std::forward<F>(func)));

We can reduce createTask to the following code:

Fiber* FiberManager::createTask(F&& func) {
  typedef AddTaskHelper<F> Helper;

  auto fiber = getFiber();
  auto funcLoc = static_cast<typename Helper::Func*>(fiber->getUserBuffer());
  new (funcLoc) typename Helper::Func(std::forward<F>(func), *this);

  fiber->setFunction(std::ref(*funcLoc));
  return fiber;
}

Fiber* FiberManager::getFiber() {
  Fiber* fiber = new Fiber(this);
  ...
  fiber->init(recordStack);
  return fiber;
}

And Fiber::Fiber is

Fiber::Fiber(FiberManager& fiberManager)
    : fiberManager_(fiberManager),
      fiberStackSize_(fiberManager_.options_.stackSize),
      fiberStackLimit_(fiberManager_.stackAllocator_.allocate(fiberStackSize_)),
      fiberImpl_([this] { fiberFunc(); }, fiberStackLimit_, fiberStackSize_) {
  fiberManager_.allFibers_.push_back(*this);
}

template <typename F>
void Fiber::setFunction(F&& func) {
  assert(state_ == INVALID);
  func_ = std::forward<F>(func);
  state_ = NOT_STARTED;
}

where a FiberImpl_ is instantiated using buffer allocated at fiberStackLimit_. The task is saved into the fiber’s func_, and the fiber state is set to NOT_STARTED.

What is FiberImpl_? In BoostContextCompatibility.h, the essense is

Please refer to Notes on Folly: Cooperative Context Switch for how control is transferred using make_fcontext and jump_fcontext.
class FiberImpl {
  using FiberContext = boost::context::detail::fcontext_t;
  FiberImpl(
      folly::Function<void()> func,
      unsigned char* stackLimit,
      size_t stackSize)
      : func_(std::move(func)) {
    auto stackBase = stackLimit + stackSize;
    stackBase_ = stackBase;
    fiberContext_ =
        boost::context::detail::make_fcontext(stackBase, stackSize, &fiberFunc);
  }

  void activate() {
    auto transfer = boost::context::detail::jump_fcontext(fiberContext_, this);
    fiberContext_ = transfer.fctx;
  }

  void deactivate() {
    auto transfer =
        boost::context::detail::jump_fcontext(mainContext_, nullptr);
    mainContext_ = transfer.fctx;
    fixStackUnwinding();
  }

  static void fiberFunc(boost::context::detail::transfer_t transfer) {
    auto fiberImpl = reinterpret_cast<FiberImpl*>(transfer.data);
    fiberImpl->mainContext_ = transfer.fctx;
    fiberImpl->fixStackUnwinding();
    fiberImpl->func_();
  }
};
};

That is our old friend make_fcontext. So this fiberImpl_ prepares an environment to jump to Fiber::fiberFunc. fiberFunc has a few housekeeping code, but after removing those code, it’s pretty clear:

[[noreturn]] void Fiber::fiberFunc() {
  while (true) {
    state_ = RUNNING;
    if (resultFunc_) {
      resultFunc_();
    } else {
      func_();
    }
    fiberManager_.deactivateFiber(this);
  }
}

This fiberManager_.deactivateFiber(this); simply calls Fiber::deactivate, which calls jump_fcontext to transfer control to mainContext_.

The while loop and [[noreturn]] attribute look weird, right? Why do you need to put this in a loop, and if it does not return, how would it transfer the control back to FiberManager ?

The fixStackUnwinding plays an extremely important role here. We know that jump_fcontext does NOT push rbp register on the stack, so when it transfers the control to another function, and if the function simply exits, the whole program exits. This is not what we want. What we want is to jump back to somewhere to continue run other fibers. fixStackUnwinding fixed it! How does it manage to do it? I’ll leave it to you to figure out? Hint: look harder into memory layout in make_fcontext.

So far we have seen

  • FiberManager creates Fiber, saves Fiber in a list.
  • Fiber::Fiber prepares an environment to jump to Fiber::fiberFunc, which runs the fiber function, and yields to other fibers (we haven’t looked at how it does it but this is an educated guess so far).

What’s missing here is the start of a fiber. i.e. where is activate gets called? That will be the beginning of a series of control transfers.

Revisit FiberManager

Now, let’s get back to FiberManager, where the loopUntilNoReadyImpl runs fibers:

inline void FiberManager::loopUntilNoReadyImpl() {
  runFibersHelper([&] {
    ...
    while (!readyFibers_.empty()) {
      auto& fiber = readyFibers_.front();
      readyFibers_.pop_front();
      runReadyFiber(&fiber);
    }
    ...
  });
}

It pulls fibers out of readyFibers_ list, and runs each one. In runReadyFiber, we finally see fiber is activated (Uggh, guarded by a while loop again):

inline void FiberManager::runReadyFiber(Fiber* fiber) {
  currentFiber_ = fiber;
  while (fiber->state_ == Fiber::NOT_STARTED ||
         fiber->state_ == Fiber::READY_TO_RUN) {
    activateFiber(fiber);
    ...
  }
}

activateFiber calls fiber->fiberImpl_.activate, which calls jump_context to transfer control to FiberImpl::fiberFunc, which calls fiberImpl_->func_(). func_ is the first argument passed to initialize the fiberImpl_, the fiberFunc:

Fiber::Fiber(...)
    : fiberImpl_([this] { fiberFunc(); }, fiberStackLimit_, fiberStackSize_) {
  ...
}

Let’s list fiberFunc here again for reference:

[[noreturn]] void Fiber::fiberFunc() {
  while (true) {
    state_ = RUNNING;
    if (resultFunc_) {
      resultFunc_();
    } else {
      func_();
    }
    state_ = INVALID;
    fiberManager_.deactivateFiber(this);
  }
}

where the func_ is what we passed into addTask, i.e.

[&] {
    LOG(INFO) << "task1: start\n";
    LOG(INFO) << "task1: finish()\n";
}
We’ll get to the case where a task is yield in the middle of the control flow

After this task is finished, the state_ is set to INVALID, and the deactivate is called. Where does it transfer control? Thanks to FiberImpl_::fixStackUnwinding, the control can be correctly transferred back to activateFiber:

inline void FiberManager::runReadyFiber(Fiber* fiber) {
  currentFiber_ = fiber;
  while (fiber->state_ == Fiber::NOT_STARTED ||
         fiber->state_ == Fiber::READY_TO_RUN) {
    activateFiber(fiber);
    ...
  }
}

Because the fiber’s state is set to INVALID, so it breaks out the while loop, and goes back to loopUntilNoReadyImpl

while (!readyFibers_.empty()) {
  auto& fiber = readyFibers_.front();
  readyFibers_.pop_front();
  runReadyFiber(&fiber);
}

where each fiber gets a chance to run. That’s why we see both tasks run. When there are no more fibers to run, the loop ends, and the EventBase loop ends.

Summary

This post is not long, but it’s a long journal for me to figure this out. I’ve simplified quite a bit of the code to let us focus on the main logic of the control transfer.

  1. FiberManager instantiates a task (a Fiber), and puts the task on a queue waiting for processing.
  2. The main processing logic is still in FiberManager (because information about the queue, current activated fiber are still in FiberManager), but folly creates LoopController interfaces to delegate the processing loop. In our example, we use EventBase‘s loop to drive the execution of all tasks.
    3. I know the “activate” process is not intuitive at all. Make sure you really understand how make_fcontext and jump_fcontext work!
  3. The most important role here is the Fiber. When a FiberManager activates a fiber, it transfers the control to the function associated with the fiber. The Fiber has house keeping record on state—the fiber marks RUNNING before the run, and INVALID after the run. When a fiber finishes, it asks FiberManager to deactivate itself, which transfers the control back to FiberManager‘s loop

What if tasks use Baton to yield? Would the above analysis stay the same?