Skip to content

Instantly share code, notes, and snippets.

@yohhoy
Created Apr 6, 2012
Embed
What would you like to do?
fiber library(prototype)
/*
* libfiber.hpp
*
* (C) Copyright yohhoy 2012.
* Distributed under the Boost Software License, Version 1.0.
* (See copy at http://www.boost.org/LICENSE_1_0.txt)
*/
#ifndef LIBFIBER_HPP_INCLUDED_
#define LIBFIBER_HPP_INCLUDED_
#include <vector>
#include <functional>
#include <algorithm>
#include <boost/context/all.hpp>
/*
* fiber namespace
*/
namespace fiber {
// forward decl.
class fiber;
/*
* scheduling policy enum
*/
enum class policy {
lazy = 0,
eager = 1
};
namespace detail {
// fiber base class
struct fiber_base {
fiber_base() {}
template <class F, class... Args>
explicit fiber_base(F f, Args&&... args)
: fn_(std::bind(f, std::forward<Args>(args)...))
, ctx_(&fiber_base::thunk, this,
boost::contexts::default_stacksize(),
boost::contexts::stack_unwind,
boost::contexts::return_to_caller)
{}
static void thunk(fiber_base* self)
{
assert(self->fn_ != nullptr);
(self->fn_)();
}
std::function<void()> fn_;
boost::contexts::context ctx_;
};
// fiber scheduler class
class scheduler {
private:
scheduler()
: sched_policy_(policy::lazy)
{
queue_.push_back(mainfiber());
}
scheduler(const scheduler&) = delete;
scheduler& operator=(const scheduler&) = delete;
public:
void append(fiber_base* f)
{
assert(std::find(queue_.begin(), queue_.end(), f) == queue_.end());
queue_.push_back(f);
}
void remove(fiber_base* f)
{
auto i = std::find(queue_.begin(), queue_.end(), f);
assert(i != queue_.end());
queue_.erase(i);
}
void rotate()
{
std::rotate(queue_.begin(), std::next(queue_.begin()), queue_.end());
}
fiber_base* curr_fiber()
{
return queue_.front();
}
fiber_base* next_fiber(fiber_base* hint)
{
if (!hint) {
rotate();
} else {
assert(std::find(queue_.begin(), queue_.end(), hint) != queue_.end());
while (curr_fiber() != hint)
rotate();
}
while (curr_fiber() != mainfiber() && curr_fiber()->ctx_.is_complete())
rotate();
return curr_fiber();
}
void yield(fiber_base* hint)
{
if (curr_fiber() == mainfiber()) {
fiber_base* next = next_fiber(hint);
while (next != mainfiber()) {
if (next->ctx_.is_started())
hint = reinterpret_cast<fiber_base*>(next->ctx_.resume());
else
hint = reinterpret_cast<fiber_base*>(next->ctx_.start());
next = next_fiber(hint);
}
} else {
curr_fiber()->ctx_.suspend(reinterpret_cast<intptr_t>(hint));
}
}
void yield_eager(fiber_base* hint)
{
if (sched_policy_ == policy::eager)
yield(hint);
}
policy& scheduling_policy() { return sched_policy_; }
static fiber_base* mainfiber()
{
static fiber_base main_fiber;
return &main_fiber;
}
static scheduler& instance()
{
static scheduler sched;
return sched;
}
private:
std::vector<fiber_base*> queue_;
policy sched_policy_;
};
} // namespace detail
/*
* scheduling policy functions
*/
policy get_scheduling_policy()
{
return detail::scheduler::instance().scheduling_policy();
}
policy set_scheduling_policy(policy new_policy)
{
policy old_policy = detail::scheduler::instance().scheduling_policy();
detail::scheduler::instance().scheduling_policy() = new_policy;
return old_policy;
}
/*
* fiber class
*/
class fiber {
public:
// fiber::id
typedef uintptr_t id;
fiber() BOOST_NOEXCEPT {}
template <class F, class... Args>
explicit fiber(F f, Args&&... args)
: impl_(new detail::fiber_base(f, std::forward<Args>(args)...))
{
detail::scheduler::instance().append(impl_.get());
detail::scheduler::instance().yield_eager(impl_.get());
}
~fiber()
{
if (joinable())
std::terminate();
}
fiber(const fiber&) = delete;
fiber& operator=(const fiber&) = delete;
fiber(fiber&& rhs) BOOST_NOEXCEPT
{
swap(rhs);
}
fiber& operator=(fiber&& rhs) BOOST_NOEXCEPT
{
if (joinable())
std::terminate();
fiber(std::move(rhs)).swap(*this);
return *this;
}
void swap(fiber& other) BOOST_NOEXCEPT
{
impl_.swap(other.impl_);
}
bool joinable() const BOOST_NOEXCEPT
{
return static_cast<bool>(impl_);
}
void join()
{
assert(joinable());
while (!impl_->ctx_.is_complete())
detail::scheduler::instance().yield(nullptr);
detail::scheduler::instance().remove(impl_.get());
impl_ = nullptr;
}
id get_id() const BOOST_NOEXCEPT
{
return impl_ ? reinterpret_cast<id>(impl_.get()) : id();
}
private:
std::unique_ptr<detail::fiber_base> impl_;
};
/*
* this_fiber namespace
*/
namespace this_fiber {
inline fiber::id get_id() BOOST_NOEXCEPT
{
return reinterpret_cast<fiber::id>(detail::scheduler::instance().curr_fiber());
}
inline void yield() BOOST_NOEXCEPT
{
detail::scheduler::instance().yield(nullptr);
}
} // namespace this_fiber
/*
* mutex class
*/
class mutex {
friend class condition_variable;
public:
mutex()
: locked_(false), owner_() {}
~mutex()
{
assert(!locked_ && owner_ == fiber::id());
}
mutex(const mutex&) = delete;
mutex& operator=(const mutex&) = delete;
void lock()
{
assert(owner_ != this_fiber::get_id());
while (locked_)
detail::scheduler::instance().yield(nullptr);
locked_ = true;
owner_ = this_fiber::get_id();
}
bool try_lock()
{
if (locked_)
return false;
lock();
return true;
}
void unlock()
{
assert(owner_ == this_fiber::get_id() && locked_);
locked_ = false;
owner_ = fiber::id();
detail::scheduler::instance().yield_eager(nullptr);
}
private:
bool locked_;
fiber::id owner_;
};
/*
* recursive_mutex class
*/
class recursive_mutex {
public:
recursive_mutex()
: nlock_(0), owner_() {}
~recursive_mutex()
{
assert(!nlock_ && owner_ == fiber::id());
}
recursive_mutex(const recursive_mutex&) = delete;
recursive_mutex& operator=(const recursive_mutex&) = delete;
void lock()
{
while (owner_ != this_fiber::get_id() && 0 < nlock_)
detail::scheduler::instance().yield(nullptr);
++nlock_;
owner_ = this_fiber::get_id();
}
bool try_lock()
{
if (owner_ != this_fiber::get_id() && 0 < nlock_)
return false;
lock();
return true;
}
void unlock()
{
assert(owner_ == this_fiber::get_id() && 0 < nlock_);
if (--nlock_ == 0) {
owner_ = fiber::id();
detail::scheduler::instance().yield_eager(nullptr);
}
}
private:
unsigned nlock_;
fiber::id owner_;
};
/*
* lock_guard template class
*/
template <class Mutex>
class lock_guard {
public:
typedef Mutex mutex_type;
explicit lock_guard(mutex_type& m)
: m_(m)
{
m_.lock();
}
~lock_guard()
{
m_.unlock();
}
lock_guard(const lock_guard&) = delete;
lock_guard& operator=(const lock_guard&) = delete;
private:
mutex_type& m_;
};
// tags for unique_lock
struct defer_lock_t {};
struct try_to_lock_t {};
struct adopt_lock_t {};
constexpr defer_lock_t defer_lock{};
constexpr try_to_lock_t try_to_lock{};
constexpr adopt_lock_t adopt_lock{};
/*
* unique_lock template class
*/
template <class Mutex>
class unique_lock {
public:
typedef Mutex mutex_type;
unique_lock() BOOST_NOEXCEPT
: pm_(nullptr), owns_(false) {}
explicit unique_lock(mutex_type& m) BOOST_NOEXCEPT
: pm_(&m), owns_(false)
{
pm_->lock();
owns_ = true;
}
unique_lock(mutex_type& m, defer_lock_t)
: pm_(&m), owns_(false) {}
unique_lock(mutex_type& m, try_to_lock_t)
: pm_(&m), owns_(m.try_lock()) {}
unique_lock(mutex_type& m, adopt_lock_t)
: pm_(&m), owns_(true) {}
~unique_lock()
{
if (owns_)
pm_->unlock();
}
unique_lock(const unique_lock&) = delete;
unique_lock& operator=(const unique_lock&) = delete;
unique_lock(unique_lock&& rhs) BOOST_NOEXCEPT
: pm_(rhs.pm_), owns_(rhs.owns_)
{
rhs.pm_ = nullptr;
rhs.owns_ = false;
}
unique_lock& operator=(unique_lock&& rhs) BOOST_NOEXCEPT
{
if (owns_)
pm_->unlock();
unique_lock(std::move(rhs)).swap(*this);
return *this;
}
void lock()
{
assert(pm_ && !owns_);
pm_->lock();
owns_ = true;
}
bool try_lock()
{
assert(pm_ && !owns_);
owns_ = pm_->try_lock();
return owns_;
}
void unlock()
{
assert(pm_ && owns_);
pm_->unlock();
owns_ = false;
}
void swap(unique_lock& other) BOOST_NOEXCEPT
{
std::swap(pm_, other.pm_);
std::swap(owns_, other.owns_);
}
mutex_type* release() BOOST_NOEXCEPT
{
mutex_type* ret = pm_;
pm_ = nullptr;
owns_ = false;
return ret;
}
bool owns_lock() const BOOST_NOEXCEPT { return owns_; }
explicit operator bool() BOOST_NOEXCEPT { return owns_; }
mutex_type* mutex() const BOOST_NOEXCEPT { return pm_; }
private:
mutex_type* pm_;
bool owns_;
};
/*
* condition_variable class
*/
class condition_variable {
struct unlock_guard {
unlock_guard(mutex& m) : m_(m) { m_.unlock(); }
~unlock_guard() { m_.lock(); }
mutex& m_;
};
public:
condition_variable()
: nwaiter_(0), nsignal_(0) {}
~condition_variable() {}
condition_variable(const condition_variable&) = delete;
condition_variable& operator=(const condition_variable&) = delete;
void notify_one() BOOST_NOEXCEPT
{
if (0 < nwaiter_) {
++nsignal_;
detail::scheduler::instance().yield_eager(nullptr);
}
}
void notify_all() BOOST_NOEXCEPT
{
if (0 < nwaiter_) {
nsignal_ += nwaiter_;
detail::scheduler::instance().yield_eager(nullptr);
}
}
void wait(unique_lock<mutex>& lock)
{
assert(lock.owns_lock() && lock.mutex()->owner_ == this_fiber::get_id());
++nwaiter_;
unlock_guard ulk(*lock.mutex());
do {
detail::scheduler::instance().yield(nullptr);
} while (nsignal_ == 0);
--nsignal_;
--nwaiter_;
}
template <class Pred>
void wait(unique_lock<mutex>& lock, Pred pred)
{
while (!pred())
wait(lock);
}
private:
unsigned nwaiter_;
unsigned nsignal_;
};
} // namespace fiber
#endif // LIBFIBER_HPP_INCLUDED_
@yohhoy
Copy link
Author

yohhoy commented Apr 8, 2012

GCC 4.6.3 + Boost 1.50.0 (svn-trunk r77773)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment