aboutsummaryrefslogtreecommitdiffstats
path: root/utils/signals/timer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'utils/signals/timer.cpp')
-rw-r--r--utils/signals/timer.cpp547
1 files changed, 547 insertions, 0 deletions
diff --git a/utils/signals/timer.cpp b/utils/signals/timer.cpp
new file mode 100644
index 000000000000..698b9835dc10
--- /dev/null
+++ b/utils/signals/timer.cpp
@@ -0,0 +1,547 @@
+// Copyright 2010 The Kyua Authors.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright
+// notice, this list of conditions and the following disclaimer in the
+// documentation and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors
+// may be used to endorse or promote products derived from this software
+// without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "utils/signals/timer.hpp"
+
+extern "C" {
+#include <sys/time.h>
+
+#include <signal.h>
+}
+
+#include <cerrno>
+#include <map>
+#include <set>
+#include <vector>
+
+#include "utils/datetime.hpp"
+#include "utils/format/macros.hpp"
+#include "utils/logging/macros.hpp"
+#include "utils/noncopyable.hpp"
+#include "utils/optional.ipp"
+#include "utils/sanity.hpp"
+#include "utils/signals/exceptions.hpp"
+#include "utils/signals/interrupts.hpp"
+#include "utils/signals/programmer.hpp"
+
+namespace datetime = utils::datetime;
+namespace signals = utils::signals;
+
+using utils::none;
+using utils::optional;
+
+namespace {
+
+
+static void sigalrm_handler(const int);
+
+
+/// Calls setitimer(2) with exception-based error reporting.
+///
+/// This does not currently support intervals.
+///
+/// \param delta The time to the first activation of the programmed timer.
+/// \param old_timeval If not NULL, pointer to a timeval into which to store the
+/// existing system timer.
+///
+/// \throw system_error If the call to setitimer(2) fails.
+static void
+safe_setitimer(const datetime::delta& delta, itimerval* old_timeval)
+{
+ ::itimerval timeval;
+ timerclear(&timeval.it_interval);
+ timeval.it_value.tv_sec = delta.seconds;
+ timeval.it_value.tv_usec = delta.useconds;
+
+ if (::setitimer(ITIMER_REAL, &timeval, old_timeval) == -1) {
+ const int original_errno = errno;
+ throw signals::system_error("Failed to program system's interval timer",
+ original_errno);
+ }
+}
+
+
+/// Deadline scheduler for all user timers on top of the unique system timer.
+class global_state : utils::noncopyable {
+ /// Collection of active timers.
+ ///
+ /// Because this is a collection of pointers, all timers are guaranteed to
+ /// be unique, and we want all of these pointers to be valid.
+ typedef std::set< signals::timer* > timers_set;
+
+ /// Sequence of ordered timers.
+ typedef std::vector< signals::timer* > timers_vector;
+
+ /// Collection of active timestamps by their activation timestamp.
+ ///
+ /// This collection is ordered intentionally so that it can be scanned
+ /// sequentially to find either expired or expiring-now timers.
+ typedef std::map< datetime::timestamp, timers_set > timers_by_timestamp_map;
+
+ /// The original timer before any timer was programmed.
+ ::itimerval _old_timeval;
+
+ /// Programmer for the SIGALRM handler.
+ std::auto_ptr< signals::programmer > _sigalrm_programmer;
+
+ /// Time of the current activation of the timer.
+ datetime::timestamp _timer_activation;
+
+ /// Mapping of all active timers using their timestamp as the key.
+ timers_by_timestamp_map _all_timers;
+
+ /// Adds a timer to the _all_timers map.
+ ///
+ /// \param timer The timer to add.
+ void
+ add_to_all_timers(signals::timer* timer)
+ {
+ timers_set& timers = _all_timers[timer->when()];
+ INV(timers.find(timer) == timers.end());
+ timers.insert(timer);
+ }
+
+ /// Removes a timer from the _all_timers map.
+ ///
+ /// This ensures that empty vectors are removed from _all_timers if the
+ /// removal of the timer causes its bucket to be emptied.
+ ///
+ /// \param timer The timer to remove.
+ void
+ remove_from_all_timers(signals::timer* timer)
+ {
+ // We may not find the timer in _all_timers if the timer has fired,
+ // because fire() took it out from the map.
+ timers_by_timestamp_map::iterator iter = _all_timers.find(
+ timer->when());
+ if (iter != _all_timers.end()) {
+ timers_set& timers = (*iter).second;
+ INV(timers.find(timer) != timers.end());
+ timers.erase(timer);
+ if (timers.empty()) {
+ _all_timers.erase(iter);
+ }
+ }
+ }
+
+ /// Calculates all timers to execute at this timestamp.
+ ///
+ /// \param now The current timestamp.
+ ///
+ /// \post _all_timers is updated to contain only the timers that are
+ /// strictly in the future.
+ ///
+ /// \return A sequence of valid timers that need to be invoked in the order
+ /// of activation. These are all previously registered timers with
+ /// activations in the past.
+ timers_vector
+ compute_timers_to_run_and_prune_old(
+ const datetime::timestamp& now,
+ const signals::interrupts_inhibiter& /* inhibiter */)
+ {
+ timers_vector to_run;
+
+ timers_by_timestamp_map::iterator iter = _all_timers.begin();
+ while (iter != _all_timers.end() && (*iter).first <= now) {
+ const timers_set& timers = (*iter).second;
+ to_run.insert(to_run.end(), timers.begin(), timers.end());
+
+ // Remove expired entries here so that we can always assume that
+ // the first entry in all_timers corresponds to the next
+ // activation.
+ const timers_by_timestamp_map::iterator previous_iter = iter;
+ ++iter;
+ _all_timers.erase(previous_iter);
+ }
+
+ return to_run;
+ }
+
+ /// Adjusts the global system timer to point to the next activation.
+ ///
+ /// \param now The current timestamp.
+ ///
+ /// \throw system_error If the programming fails.
+ void
+ reprogram_system_timer(
+ const datetime::timestamp& now,
+ const signals::interrupts_inhibiter& /* inhibiter */)
+ {
+ if (_all_timers.empty()) {
+ // Nothing to do. We can reach this case if all the existing timers
+ // are in the past and they all fired. Just ignore the request and
+ // leave the global timer as is.
+ return;
+ }
+
+ // While fire() prunes old entries from the list of timers, it is
+ // possible for this routine to run with "expired" timers (i.e. timers
+ // whose deadline lies in the past but that have not yet fired for
+ // whatever reason that is out of our control) in the list. We have to
+ // iterate until we find the next activation instead of assuming that
+ // the first entry represents the desired value.
+ timers_by_timestamp_map::const_iterator iter = _all_timers.begin();
+ PRE(!(*iter).second.empty());
+ datetime::timestamp next = (*iter).first;
+ while (next < now) {
+ ++iter;
+ if (iter == _all_timers.end()) {
+ // Nothing to do. We can reach this case if all the existing
+ // timers are in the past but they have not yet fired.
+ return;
+ }
+ PRE(!(*iter).second.empty());
+ next = (*iter).first;
+ }
+
+ if (next < _timer_activation || now > _timer_activation) {
+ INV(next >= now);
+ const datetime::delta delta = next - now;
+ LD(F("Reprogramming timer; firing on %s; now is %s") % next % now);
+ safe_setitimer(delta, NULL);
+ _timer_activation = next;
+ }
+ }
+
+public:
+ /// Programs the first timer.
+ ///
+ /// The programming of the first timer involves setting up the SIGALRM
+ /// handler and installing a timer handler for the first time, which in turn
+ /// involves keeping track of the old handlers so that we can restore them.
+ ///
+ /// \param timer The timer being programmed.
+ /// \param now The current timestamp.
+ ///
+ /// \throw system_error If the programming fails.
+ global_state(signals::timer* timer, const datetime::timestamp& now) :
+ _timer_activation(timer->when())
+ {
+ PRE(now < timer->when());
+
+ signals::interrupts_inhibiter inhibiter;
+
+ const datetime::delta delta = timer->when() - now;
+ LD(F("Installing first timer; firing on %s; now is %s") %
+ timer->when() % now);
+
+ _sigalrm_programmer.reset(
+ new signals::programmer(SIGALRM, sigalrm_handler));
+ try {
+ safe_setitimer(delta, &_old_timeval);
+ _timer_activation = timer->when();
+ add_to_all_timers(timer);
+ } catch (...) {
+ _sigalrm_programmer.reset(NULL);
+ throw;
+ }
+ }
+
+ /// Unprograms all timers.
+ ///
+ /// This clears the global system timer and unsets the SIGALRM handler.
+ ~global_state(void)
+ {
+ signals::interrupts_inhibiter inhibiter;
+
+ LD("Unprogramming all timers");
+
+ if (::setitimer(ITIMER_REAL, &_old_timeval, NULL) == -1) {
+ UNREACHABLE_MSG("Failed to restore original timer");
+ }
+
+ _sigalrm_programmer->unprogram();
+ _sigalrm_programmer.reset(NULL);
+ }
+
+ /// Programs a new timer, possibly adjusting the global system timer.
+ ///
+ /// Programming any timer other than the first one only involves reloading
+ /// the existing timer, not backing up the previous handler nor installing a
+ /// handler for SIGALRM.
+ ///
+ /// \param timer The timer being programmed.
+ /// \param now The current timestamp.
+ ///
+ /// \throw system_error If the programming fails.
+ void
+ program_new(signals::timer* timer, const datetime::timestamp& now)
+ {
+ signals::interrupts_inhibiter inhibiter;
+
+ add_to_all_timers(timer);
+ reprogram_system_timer(now, inhibiter);
+ }
+
+ /// Unprograms a timer.
+ ///
+ /// This removes the timer from the global state and reprograms the global
+ /// system timer if necessary.
+ ///
+ /// \param timer The timer to unprogram.
+ ///
+ /// \return True if the system interval timer has been reprogrammed to
+ /// another future timer; false if there are no more active timers.
+ bool
+ unprogram(signals::timer* timer)
+ {
+ signals::interrupts_inhibiter inhibiter;
+
+ LD(F("Unprogramming timer; previously firing on %s") % timer->when());
+
+ remove_from_all_timers(timer);
+ if (_all_timers.empty()) {
+ return false;
+ } else {
+ reprogram_system_timer(datetime::timestamp::now(), inhibiter);
+ return true;
+ }
+ }
+
+ /// Executes active timers.
+ ///
+ /// Active timers are all those that fire on or before 'now'.
+ ///
+ /// \param now The current time.
+ void
+ fire(const datetime::timestamp& now)
+ {
+ timers_vector to_run;
+ {
+ signals::interrupts_inhibiter inhibiter;
+ to_run = compute_timers_to_run_and_prune_old(now, inhibiter);
+ reprogram_system_timer(now, inhibiter);
+ }
+
+ for (timers_vector::iterator iter = to_run.begin();
+ iter != to_run.end(); ++iter) {
+ signals::detail::invoke_do_fired(*iter);
+ }
+ }
+};
+
+
+/// Unique instance of the global state.
+static std::auto_ptr< global_state > globals;
+
+
+/// SIGALRM handler for the timer implementation.
+///
+/// \param signo The signal received; must be SIGALRM.
+static void
+sigalrm_handler(const int signo)
+{
+ PRE(signo == SIGALRM);
+ globals->fire(datetime::timestamp::now());
+}
+
+
+} // anonymous namespace
+
+
+/// Indirection to invoke the private do_fired() method of a timer.
+///
+/// \param timer The timer on which to run do_fired().
+void
+utils::signals::detail::invoke_do_fired(timer* timer)
+{
+ timer->do_fired();
+}
+
+
+/// Internal implementation for the timer.
+///
+/// We assume that there is a 1-1 mapping between timer objects and impl
+/// objects. If this assumption breaks, then the rest of the code in this
+/// module breaks as well because we use pointers to the parent timer as the
+/// identifier of the timer.
+struct utils::signals::timer::impl : utils::noncopyable {
+ /// Timestamp when this timer is expected to fire.
+ ///
+ /// Note that the timer might be processed after this timestamp, so users of
+ /// this field need to check for timers that fire on or before the
+ /// activation time.
+ datetime::timestamp when;
+
+ /// True until unprogram() is called.
+ bool programmed;
+
+ /// Whether this timer has fired already or not.
+ ///
+ /// This is updated from an interrupt context, hence why it is marked
+ /// volatile.
+ volatile bool fired;
+
+ /// Constructor.
+ ///
+ /// \param when_ Timestamp when this timer is expected to fire.
+ impl(const datetime::timestamp& when_) :
+ when(when_), programmed(true), fired(false)
+ {
+ }
+
+ /// Destructor.
+ ~impl(void) {
+ }
+};
+
+
+/// Constructor; programs a run-once timer.
+///
+/// This programs the global timer and signal handler if this is the first timer
+/// being installed. Otherwise, reprograms the global timer if this timer
+/// expires earlier than all other active timers.
+///
+/// \param delta The time until the timer fires.
+signals::timer::timer(const datetime::delta& delta)
+{
+ signals::interrupts_inhibiter inhibiter;
+
+ const datetime::timestamp now = datetime::timestamp::now();
+ _pimpl.reset(new impl(now + delta));
+ if (globals.get() == NULL) {
+ globals.reset(new global_state(this, now));
+ } else {
+ globals->program_new(this, now);
+ }
+}
+
+
+/// Destructor; unprograms the timer if still programmed.
+///
+/// Given that this is a destructor and it can't report errors back to the
+/// caller, the caller must attempt to call unprogram() on its own. This is
+/// extremely important because, otherwise, expired timers will never run!
+signals::timer::~timer(void)
+{
+ signals::interrupts_inhibiter inhibiter;
+
+ if (_pimpl->programmed) {
+ LW("Auto-destroying still-programmed signals::timer object");
+ try {
+ unprogram();
+ } catch (const system_error& e) {
+ UNREACHABLE;
+ }
+ }
+
+ if (!_pimpl->fired) {
+ const datetime::timestamp now = datetime::timestamp::now();
+ if (now > _pimpl->when) {
+ LW("Expired timer never fired; the code never called unprogram()!");
+ }
+ }
+}
+
+
+/// Returns the time of the timer activation.
+///
+/// \return A timestamp that has no relation to the current time (i.e. can be in
+/// the future or in the past) nor the timer's activation status.
+const datetime::timestamp&
+signals::timer::when(void) const
+{
+ return _pimpl->when;
+}
+
+
+/// Callback for the SIGALRM handler when this timer expires.
+///
+/// \warning This is executed from a signal handler context without signals
+/// inhibited. See signal(7) for acceptable system calls.
+void
+signals::timer::do_fired(void)
+{
+ PRE(!_pimpl->fired);
+ _pimpl->fired = true;
+ callback();
+}
+
+
+/// User-provided callback to run when the timer expires.
+///
+/// The default callback does nothing. We record the activation of the timer
+/// separately, which may be appropriate in the majority of the cases.
+///
+/// \warning This is executed from a signal handler context without signals
+/// inhibited. See signal(7) for acceptable system calls.
+void
+signals::timer::callback(void)
+{
+ // Intentionally left blank.
+}
+
+
+/// Checks whether the timer has fired already or not.
+///
+/// \return Returns true if the timer has fired.
+bool
+signals::timer::fired(void) const
+{
+ return _pimpl->fired;
+}
+
+
+/// Unprograms the timer.
+///
+/// \pre The timer is programmed (i.e. this can only be called once).
+///
+/// \post If the timer never fired asynchronously because the signal delivery
+/// did not arrive on time, make sure we invoke the timer's callback here.
+///
+/// \throw system_error If unprogramming the timer failed.
+void
+signals::timer::unprogram(void)
+{
+ signals::interrupts_inhibiter inhibiter;
+
+ if (!_pimpl->programmed) {
+ // We cannot assert that the timer is not programmed because it might
+ // have been unprogrammed asynchronously between the time we called
+ // unprogram() and the time we reach this. Simply return in this case.
+ LD("Called unprogram on already-unprogrammed timer; possibly just "
+ "a race");
+ return;
+ }
+
+ if (!globals->unprogram(this)) {
+ globals.reset(NULL);
+ }
+ _pimpl->programmed = false;
+
+ // Handle the case where the timer has expired before we ever got its
+ // corresponding signal. Do so by invoking its callback now.
+ if (!_pimpl->fired) {
+ const datetime::timestamp now = datetime::timestamp::now();
+ if (now > _pimpl->when) {
+ LW(F("Firing expired timer on destruction (was to fire on %s)") %
+ _pimpl->when);
+ do_fired();
+ }
+ }
+}