diff options
Diffstat (limited to 'utils/signals/timer.cpp')
| -rw-r--r-- | utils/signals/timer.cpp | 547 |
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(); + } + } +} |