8
\$\begingroup\$

This is a much improved version (I hope) of code in this previous code review of mine.

I have:

  • renamed several things. Are the names good?
  • made it lazily start the worker thread only after the first timer is added. Is it clear that the implementation uses one worker thread to handle an unlimited number of timer callbacks?
  • added the ability to bind additional arguments to the timer callback.
  • added helper functions that match the API of setTimeout and setInterval from JavaScript. I expect many developers to immediately recognize it and know how to use it right away. Do you agree or are they completely redundant with addTimer?
  • made it completely thread safe (as far as I can tell), and added guarantees that make it easy to use reliably. Can you see any concurrency problems?
  • tried to make the class much more self-documenting. Does the header file provide sufficient information at the right level of detail? I tried to document the thread-safety guarantees I provide in the code. Are they sufficiently specified?

Questions:

  1. Do you think it is a good idea to add an RAII class that automatically calls clearTimeout for a timer when it goes out of scope? Should every resource acquisition have a scope guard?
  2. Have I used const and noexcept appropriately?

timerthread.h

#ifndef TIMERTHREAD_H
#define TIMERTHREAD_H

#include <algorithm>
#include <functional>
#include <chrono>
#include <unordered_map>
#include <set>
#include <cstdint>

#ifdef HAVE_PLATFORMTHREAD_H
#include "platformthread.h"
#else
#include <thread>
#include <mutex>
#include <condition_variable>
#endif

class TimerThread
{
public:
    // Each Timer is assigned a unique ID of type timer_id
    using timer_id = std::uint64_t;

    // Valid IDs are guaranteed not to be this value
    static timer_id constexpr no_timer = timer_id(0);

    //
    // Callback storage

    // Function object we actually use
    using handler_type = std::function<void()>;

    // Function object that we boil down to handler_type with std::bind
    template<typename... Args>
    using bound_handler_type = std::function<void(Args...)>;

    // Values that are a large-range millisecond count
    using millisec = std::int64_t;

    // Constructor does not start worker until there is a Timer
    explicit TimerThread();

    // Destructor is thread safe, even if a timer
    // callback is running. All callbacks are guaranteed
    // to have returned before this destructor returns
    ~TimerThread();

    // Create timer using milliseconds
    // The delay will be called msDelay milliseconds from now
    // If msPeriod is nonzero, call the callback again every
    // msPeriod milliseconds
    // All timer creation functions eventually call this one
    timer_id addTimer(millisec msDelay,
                      millisec msPeriod,
                      handler_type handler);

    // Create timer using std::chrono delay and period
    // Optionally binds additional arguments to the callback
    template<typename SRep, typename SPer,
             typename PRep, typename PPer,
             typename... Args>
    timer_id addTimer(
            typename std::chrono::duration<SRep, SPer> const& delay,
            typename std::chrono::duration<PRep, PPer> const& period,
            bound_handler_type<Args...> handler,
            Args&& ...args);

    // Create timer using millisecond units delay and period
    // Optionally binds additional arguments to the callback
    template<typename... Args>
    timer_id addTimer(millisec msDelay,
                      millisec msPeriod,
                      bound_handler_type<Args...> handler,
                      Args&& ...args);

    // setInterval API like browser javascript
    // Call handler every `period` milliseconds,
    // starting `period` milliseconds from now
    // Optionally binds additional arguments to the callback
    timer_id setInterval(handler_type handler,
                         millisec period);

    // setTimeout API like browser javascript
    // Call handler once `timeout` ms from now
    timer_id setTimeout(handler_type handler,
                        millisec timeout);

    // setInterval API like browser javascript
    // Call handler every `period` milliseconds,
    // starting `period` milliseconds from now
    template<typename... Args>
    timer_id setInterval(bound_handler_type<Args...> handler,
                         millisec period,
                         Args&& ...args);

    // setTimeout API like browser javascript
    // Call handler once `timeout` ms from now
    // binds extra arguments and passes them to the
    // timer callback
    template<typename... Args>
    timer_id setTimeout(bound_handler_type<Args...> handler,
                        millisec timeout,
                        Args&& ...args);

    // Destroy the specified timer
    //
    // Synchronizes with the worker thread if the
    // callback for this timer is running, which
    // guarantees that the handler for that callback
    // is not running before clearTimer returns
    //
    // You are not required to clear any timers. You can
    // forget their timer_id if you do not need to cancel
    // them.
    //
    // The only time you need this is when you want to
    // stop a timer that has a repetition period, or
    // you want to cancel a timeout that has not fired
    // yet
    //
    // See clear() to wipe out all timers in one go
    //
    bool clearTimer(timer_id id);

    // Destroy all timers, but preserve id uniqueness
    // This carefully makes sure every timer is not
    // executing its callback before destructing it
    void clear();

    // Peek at current state
    std::size_t size() const noexcept;
    bool empty() const noexcept;

    // Returns lazily initialized singleton
    static TimerThread& global();

private:
    using Lock = std::mutex;
    using ScopedLock = std::unique_lock<Lock>;
    using ConditionVar = std::condition_variable;

    using Clock = std::chrono::steady_clock;
    using Timestamp = std::chrono::time_point<Clock>;
    using Duration = std::chrono::milliseconds;

    struct Timer
    {
        explicit Timer(timer_id id = 0);
        Timer(Timer&& r) noexcept;
        Timer& operator=(Timer&& r) noexcept;

        Timer(timer_id id,
                Timestamp next,
                Duration period,
                handler_type handler) noexcept;

        // Never called
        Timer(Timer const& r) = delete;
        Timer& operator=(Timer const& r) = delete;

        timer_id id;
        Timestamp next;
        Duration period;
        handler_type handler;

        // You must be holding the 'sync' lock to assign waitCond
        std::unique_ptr<ConditionVar> waitCond;

        bool running;
    };

    // Comparison functor to sort the timer "queue" by Timer::next
    struct NextActiveComparator
    {
        bool operator()(Timer const& a, Timer const& b) const noexcept
        {
            return a.next < b.next;
        }
    };

    // Queue is a set of references to Timer objects, sorted by next
    using QueueValue = std::reference_wrapper<Timer>;
    using Queue = std::multiset<QueueValue, NextActiveComparator>;
    using TimerMap = std::unordered_map<timer_id, Timer>;

    void timerThreadWorker();
    bool destroy_impl(ScopedLock& lock,
                      TimerMap::iterator i,
                      bool notify);

    // Inexhaustible source of unique IDs
    timer_id nextId;

    // The Timer objects are physically stored in this map
    TimerMap active;

    // The ordering queue holds references to items in `active`
    Queue queue;

    // One worker thread for an unlimited number of timers is acceptable
    // Lazily started when first timer is started
    // TODO: Implement auto-stopping the timer thread when it is idle for
    // a configurable period.
    mutable Lock sync;
    ConditionVar wakeUp;
    std::thread worker;
    bool done;
};

template<typename SRep, typename SPer,
         typename PRep, typename PPer,
         typename... Args>
TimerThread::timer_id TimerThread::addTimer(
        typename std::chrono::duration<SRep, SPer> const& delay,
        typename std::chrono::duration<PRep, PPer> const& period,
        bound_handler_type<Args...> handler,
        Args&& ...args)
{
    millisec msDelay =
            std::chrono::duration_cast<
            std::chrono::milliseconds>(delay).count();

    millisec msPeriod =
            std::chrono::duration_cast<
            std::chrono::milliseconds>(period).count();

    return addTimer(msDelay, msPeriod,
                    std::move(handler),
                    std::forward<Args>(args)...);
}

template<typename... Args>
TimerThread::timer_id TimerThread::addTimer(
        millisec msDelay,
        millisec msPeriod,
        bound_handler_type<Args...> handler,
        Args&& ...args)
{
    return addTimer(msDelay, msPeriod,
                    std::bind(std::move(handler),
                              std::forward<Args>(args)...));
}

// Javascript-like setInterval
template<typename... Args>
TimerThread::timer_id TimerThread::setInterval(
        bound_handler_type<Args...> handler,
        millisec period,
        Args&& ...args)
{
    return setInterval(std::bind(std::move(handler),
                                 std::forward<Args>(args)...),
                       period);
}

// Javascript-like setTimeout
template<typename... Args>
TimerThread::timer_id TimerThread::setTimeout(
        bound_handler_type<Args...> handler,
        millisec timeout,
        Args&& ...args)
{
    return setTimeout(std::bind(std::move(handler),
                                std::forward<Args>(args)...),
                      timeout);
}

#endif // TIMERTHREAD_H

timerthread.cpp

#include "timerthread.h"

#include <cassert>

void TimerThread::timerThreadWorker()
{
    ScopedLock lock(sync);

    while (!done)
    {
        if (queue.empty())
        {
            // Wait for done or work
            wakeUp.wait(lock, [this] {
                return done || !queue.empty();
            });
            continue;
        }

        auto queueHead = queue.begin();
        Timer& timer = *queueHead;
        auto now = Clock::now();
        if (now >= timer.next)
        {
            queue.erase(queueHead);

            // Mark it as running to handle racing destroy
            timer.running = true;

            // Call the handler outside the lock
            lock.unlock();
            timer.handler();
            lock.lock();

            if (timer.running)
            {
                timer.running = false;

                // If it is periodic, schedule a new one
                if (timer.period.count() > 0)
                {
                    timer.next = timer.next + timer.period;
                    queue.emplace(timer);
                } else {
                    // Not rescheduling, destruct it
                    active.erase(timer.id);
                }
            }
            else
            {
                // timer.running changed!
                //
                // Running was set to false, destroy was called
                // for this Timer while the callback was in progress
                // (this thread was not holding the lock during the callback)
                // The thread trying to destroy this timer is waiting on
                // a condition variable, so notify it
                timer.waitCond->notify_all();

                // The clearTimer call expects us to remove the instance
                // when it detects that it is racing with its callback
                active.erase(timer.id);
            }
        } else {
            // Wait until the timer is ready or a timer creation notifies
            wakeUp.wait_until(lock, timer.next);
        }
    }
}

TimerThread::TimerThread()
    : nextId(no_timer + 1)
    , queue()
    , done(false)
{
}

TimerThread::~TimerThread()
{
    ScopedLock lock(sync);

    // The worker might not be running
    if (worker.joinable())
    {
        done = true;
        lock.unlock();
        wakeUp.notify_all();

        // If a timer handler is running, this
        // will make sure it has returned before
        // allowing any deallocations to happen
        worker.join();

        // Note that any timers still in the queue
        // will be destructed properly but they
        // will not be invoked
    }
}

TimerThread::timer_id TimerThread::setInterval(
        handler_type handler, millisec period)
{
    return addTimer(period, period, std::move(handler));
}

TimerThread::timer_id TimerThread::setTimeout(
        handler_type handler, millisec timeout)
{
    return addTimer(timeout, 0, std::move(handler));
}

TimerThread::timer_id TimerThread::addTimer(
        millisec msDelay,
        millisec msPeriod,
        handler_type handler)
{
    ScopedLock lock(sync);

    // Lazily start thread when first timer is requested
    if (!worker.joinable())
        worker = std::thread(&TimerThread::timerThreadWorker, this);

    // Assign an ID and insert it into function storage
    auto id = nextId++;
    auto iter = active.emplace(id, Timer(id,
            Clock::now() + Duration(msDelay),
            Duration(msPeriod),
            std::move(handler)));

    // Insert a reference to the Timer into ordering queue
    Queue::iterator place = queue.emplace(iter.first->second);

    // We need to notify the timer thread only if we inserted
    // this timer into the front of the timer queue
    bool needNotify = (place == queue.begin());

    lock.unlock();

    if (needNotify)
        wakeUp.notify_all();

    return id;
}

bool TimerThread::clearTimer(timer_id id)
{
    ScopedLock lock(sync);
    auto i = active.find(id);
    return destroy_impl(lock, i, true);
}

void TimerThread::clear()
{
    ScopedLock lock(sync);
    while (!active.empty())
    {
        destroy_impl(lock, active.begin(),
                     queue.size() == 1);
    }
}

std::size_t TimerThread::size() const noexcept
{
    ScopedLock lock(sync);
    return active.size();
}

bool TimerThread::empty() const noexcept
{
    ScopedLock lock(sync);
    return active.empty();
}

// NOTE: if notify is true, returns with lock unlocked
bool TimerThread::destroy_impl(ScopedLock& lock,
                               TimerMap::iterator i,
                               bool notify)
{
    assert(lock.owns_lock());

    if (i == active.end())
        return false;

    Timer& timer = i->second;

    if (timer.running)
    {
        // A callback is in progress for this Timer,
        // so flag it for deletion in the worker
        timer.running = false;

        // Assign a condition variable to this timer
        timer.waitCond.reset(new ConditionVar);

        // Block until the callback is finished
        timer.waitCond->wait(lock);
    }
    else
    {
        queue.erase(timer);
        active.erase(i);

        if (notify)
        {
            lock.unlock();
            wakeUp.notify_all();
        }
    }

    return true;
}

TimerThread& TimerThread::global()
{
    static TimerThread singleton;
    return singleton;
}

// TimerThread::Timer implementation

TimerThread::Timer::Timer(timer_id id)
    : id(id)
    , running(false)
{
}

TimerThread::Timer::Timer(Timer&& r) noexcept
    : id(std::move(r.id))
    , next(std::move(r.next))
    , period(std::move(r.period))
    , handler(std::move(r.handler))
    , running(std::move(r.running))
{
}

TimerThread::Timer::Timer(timer_id id,
                          Timestamp next,
                          Duration period,
                          handler_type handler) noexcept
    : id(id)
    , next(next)
    , period(period)
    , handler(std::move(handler))
    , running(false)
{
}
\$\endgroup\$
  • \$\begingroup\$ would you be able to provide example code for how to use your updated code? \$\endgroup\$ – dereknash Apr 14 '17 at 18:46
  • \$\begingroup\$ @dereknash The link to the previous code review has some examples. The class name in this version is changed from Timer to TimerThread and create was changed to addTimer. This version eliminates the exists issue mentioned there, and clearTimer ensures that the timer callback is safely not running before it returns. \$\endgroup\$ – doug65536 Apr 15 '17 at 8:37
  • \$\begingroup\$ The implementation looks pretty good as far as I can tell. On your previous code review you added usage examples, could you add an updated version of this here too? \$\endgroup\$ – p0fi Jun 14 '17 at 8:38
  • \$\begingroup\$ @doug65536 Small Question: What's the license of your code? Can I use it for my bachelor thesis? Its fast and reliably fires in the intervals I need. \$\endgroup\$ – Ruhrpottpatriot Jun 18 '19 at 17:10
  • \$\begingroup\$ @Ruhrpottpatriot Definitely! Consider it MIT license with completely unrestricted permission for academic use. \$\endgroup\$ – doug65536 Jun 19 '19 at 7:06
6
\$\begingroup\$

I think I spotted a possible deadlock. It will occur in case clearTimer or clear are called from within a timer handler (i.e. from the worker thread).

The statement timer.waitCond->wait(lock); in destroy_impl() will block forever since the corresponding notify_all is done from timerThreadWorker() after the handler callback has returned.

To fix this, I propose changing it to:

if (std::this_thread::get_id() != worker.get_id()) {
    timer.waitCond->wait(lock);
}
\$\endgroup\$
2
\$\begingroup\$

One possible use of deallocated memory is on the line

wakeUp.wait_until(lock, timer.next);

Since the timer can be deleted before wakeUp is called (see destroy_impl), wait_until might use deallocated memory. Simply copying the value of next because using it in wait_util should fix it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.