1 // Copyright 2010 The Kyua Authors.
2 // All rights reserved.
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #include "utils/signals/timer.hpp"
42 #include "utils/datetime.hpp"
43 #include "utils/format/macros.hpp"
44 #include "utils/logging/macros.hpp"
45 #include "utils/noncopyable.hpp"
46 #include "utils/optional.ipp"
47 #include "utils/sanity.hpp"
48 #include "utils/signals/exceptions.hpp"
49 #include "utils/signals/interrupts.hpp"
50 #include "utils/signals/programmer.hpp"
52 namespace datetime = utils::datetime;
53 namespace signals = utils::signals;
56 using utils::optional;
61 static void sigalrm_handler(const int);
64 /// Calls setitimer(2) with exception-based error reporting.
66 /// This does not currently support intervals.
68 /// \param delta The time to the first activation of the programmed timer.
69 /// \param old_timeval If not NULL, pointer to a timeval into which to store the
70 /// existing system timer.
72 /// \throw system_error If the call to setitimer(2) fails.
74 safe_setitimer(const datetime::delta& delta, itimerval* old_timeval)
77 timerclear(&timeval.it_interval);
78 timeval.it_value.tv_sec = delta.seconds;
79 timeval.it_value.tv_usec = delta.useconds;
81 if (::setitimer(ITIMER_REAL, &timeval, old_timeval) == -1) {
82 const int original_errno = errno;
83 throw signals::system_error("Failed to program system's interval timer",
89 /// Deadline scheduler for all user timers on top of the unique system timer.
90 class global_state : utils::noncopyable {
91 /// Collection of active timers.
93 /// Because this is a collection of pointers, all timers are guaranteed to
94 /// be unique, and we want all of these pointers to be valid.
95 typedef std::set< signals::timer* > timers_set;
97 /// Sequence of ordered timers.
98 typedef std::vector< signals::timer* > timers_vector;
100 /// Collection of active timestamps by their activation timestamp.
102 /// This collection is ordered intentionally so that it can be scanned
103 /// sequentially to find either expired or expiring-now timers.
104 typedef std::map< datetime::timestamp, timers_set > timers_by_timestamp_map;
106 /// The original timer before any timer was programmed.
107 ::itimerval _old_timeval;
109 /// Programmer for the SIGALRM handler.
110 std::auto_ptr< signals::programmer > _sigalrm_programmer;
112 /// Time of the current activation of the timer.
113 datetime::timestamp _timer_activation;
115 /// Mapping of all active timers using their timestamp as the key.
116 timers_by_timestamp_map _all_timers;
118 /// Adds a timer to the _all_timers map.
120 /// \param timer The timer to add.
122 add_to_all_timers(signals::timer* timer)
124 timers_set& timers = _all_timers[timer->when()];
125 INV(timers.find(timer) == timers.end());
126 timers.insert(timer);
129 /// Removes a timer from the _all_timers map.
131 /// This ensures that empty vectors are removed from _all_timers if the
132 /// removal of the timer causes its bucket to be emptied.
134 /// \param timer The timer to remove.
136 remove_from_all_timers(signals::timer* timer)
138 // We may not find the timer in _all_timers if the timer has fired,
139 // because fire() took it out from the map.
140 timers_by_timestamp_map::iterator iter = _all_timers.find(
142 if (iter != _all_timers.end()) {
143 timers_set& timers = (*iter).second;
144 INV(timers.find(timer) != timers.end());
146 if (timers.empty()) {
147 _all_timers.erase(iter);
152 /// Calculates all timers to execute at this timestamp.
154 /// \param now The current timestamp.
156 /// \post _all_timers is updated to contain only the timers that are
157 /// strictly in the future.
159 /// \return A sequence of valid timers that need to be invoked in the order
160 /// of activation. These are all previously registered timers with
161 /// activations in the past.
163 compute_timers_to_run_and_prune_old(
164 const datetime::timestamp& now,
165 const signals::interrupts_inhibiter& /* inhibiter */)
167 timers_vector to_run;
169 timers_by_timestamp_map::iterator iter = _all_timers.begin();
170 while (iter != _all_timers.end() && (*iter).first <= now) {
171 const timers_set& timers = (*iter).second;
172 to_run.insert(to_run.end(), timers.begin(), timers.end());
174 // Remove expired entries here so that we can always assume that
175 // the first entry in all_timers corresponds to the next
177 const timers_by_timestamp_map::iterator previous_iter = iter;
179 _all_timers.erase(previous_iter);
185 /// Adjusts the global system timer to point to the next activation.
187 /// \param now The current timestamp.
189 /// \throw system_error If the programming fails.
191 reprogram_system_timer(
192 const datetime::timestamp& now,
193 const signals::interrupts_inhibiter& /* inhibiter */)
195 if (_all_timers.empty()) {
196 // Nothing to do. We can reach this case if all the existing timers
197 // are in the past and they all fired. Just ignore the request and
198 // leave the global timer as is.
202 // While fire() prunes old entries from the list of timers, it is
203 // possible for this routine to run with "expired" timers (i.e. timers
204 // whose deadline lies in the past but that have not yet fired for
205 // whatever reason that is out of our control) in the list. We have to
206 // iterate until we find the next activation instead of assuming that
207 // the first entry represents the desired value.
208 timers_by_timestamp_map::const_iterator iter = _all_timers.begin();
209 PRE(!(*iter).second.empty());
210 datetime::timestamp next = (*iter).first;
213 if (iter == _all_timers.end()) {
214 // Nothing to do. We can reach this case if all the existing
215 // timers are in the past but they have not yet fired.
218 PRE(!(*iter).second.empty());
219 next = (*iter).first;
222 if (next < _timer_activation || now > _timer_activation) {
224 const datetime::delta delta = next - now;
225 LD(F("Reprogramming timer; firing on %s; now is %s") % next % now);
226 safe_setitimer(delta, NULL);
227 _timer_activation = next;
232 /// Programs the first timer.
234 /// The programming of the first timer involves setting up the SIGALRM
235 /// handler and installing a timer handler for the first time, which in turn
236 /// involves keeping track of the old handlers so that we can restore them.
238 /// \param timer The timer being programmed.
239 /// \param now The current timestamp.
241 /// \throw system_error If the programming fails.
242 global_state(signals::timer* timer, const datetime::timestamp& now) :
243 _timer_activation(timer->when())
245 PRE(now < timer->when());
247 signals::interrupts_inhibiter inhibiter;
249 const datetime::delta delta = timer->when() - now;
250 LD(F("Installing first timer; firing on %s; now is %s") %
251 timer->when() % now);
253 _sigalrm_programmer.reset(
254 new signals::programmer(SIGALRM, sigalrm_handler));
256 safe_setitimer(delta, &_old_timeval);
257 _timer_activation = timer->when();
258 add_to_all_timers(timer);
260 _sigalrm_programmer.reset(NULL);
265 /// Unprograms all timers.
267 /// This clears the global system timer and unsets the SIGALRM handler.
270 signals::interrupts_inhibiter inhibiter;
272 LD("Unprogramming all timers");
274 if (::setitimer(ITIMER_REAL, &_old_timeval, NULL) == -1) {
275 UNREACHABLE_MSG("Failed to restore original timer");
278 _sigalrm_programmer->unprogram();
279 _sigalrm_programmer.reset(NULL);
282 /// Programs a new timer, possibly adjusting the global system timer.
284 /// Programming any timer other than the first one only involves reloading
285 /// the existing timer, not backing up the previous handler nor installing a
286 /// handler for SIGALRM.
288 /// \param timer The timer being programmed.
289 /// \param now The current timestamp.
291 /// \throw system_error If the programming fails.
293 program_new(signals::timer* timer, const datetime::timestamp& now)
295 signals::interrupts_inhibiter inhibiter;
297 add_to_all_timers(timer);
298 reprogram_system_timer(now, inhibiter);
301 /// Unprograms a timer.
303 /// This removes the timer from the global state and reprograms the global
304 /// system timer if necessary.
306 /// \param timer The timer to unprogram.
308 /// \return True if the system interval timer has been reprogrammed to
309 /// another future timer; false if there are no more active timers.
311 unprogram(signals::timer* timer)
313 signals::interrupts_inhibiter inhibiter;
315 LD(F("Unprogramming timer; previously firing on %s") % timer->when());
317 remove_from_all_timers(timer);
318 if (_all_timers.empty()) {
321 reprogram_system_timer(datetime::timestamp::now(), inhibiter);
326 /// Executes active timers.
328 /// Active timers are all those that fire on or before 'now'.
330 /// \param now The current time.
332 fire(const datetime::timestamp& now)
334 timers_vector to_run;
336 signals::interrupts_inhibiter inhibiter;
337 to_run = compute_timers_to_run_and_prune_old(now, inhibiter);
338 reprogram_system_timer(now, inhibiter);
341 for (timers_vector::iterator iter = to_run.begin();
342 iter != to_run.end(); ++iter) {
343 signals::detail::invoke_do_fired(*iter);
349 /// Unique instance of the global state.
350 static std::auto_ptr< global_state > globals;
353 /// SIGALRM handler for the timer implementation.
355 /// \param signo The signal received; must be SIGALRM.
357 sigalrm_handler(const int signo)
359 PRE(signo == SIGALRM);
360 globals->fire(datetime::timestamp::now());
364 } // anonymous namespace
367 /// Indirection to invoke the private do_fired() method of a timer.
369 /// \param timer The timer on which to run do_fired().
371 utils::signals::detail::invoke_do_fired(timer* timer)
377 /// Internal implementation for the timer.
379 /// We assume that there is a 1-1 mapping between timer objects and impl
380 /// objects. If this assumption breaks, then the rest of the code in this
381 /// module breaks as well because we use pointers to the parent timer as the
382 /// identifier of the timer.
383 struct utils::signals::timer::impl : utils::noncopyable {
384 /// Timestamp when this timer is expected to fire.
386 /// Note that the timer might be processed after this timestamp, so users of
387 /// this field need to check for timers that fire on or before the
389 datetime::timestamp when;
391 /// True until unprogram() is called.
394 /// Whether this timer has fired already or not.
396 /// This is updated from an interrupt context, hence why it is marked
402 /// \param when_ Timestamp when this timer is expected to fire.
403 impl(const datetime::timestamp& when_) :
404 when(when_), programmed(true), fired(false)
414 /// Constructor; programs a run-once timer.
416 /// This programs the global timer and signal handler if this is the first timer
417 /// being installed. Otherwise, reprograms the global timer if this timer
418 /// expires earlier than all other active timers.
420 /// \param delta The time until the timer fires.
421 signals::timer::timer(const datetime::delta& delta)
423 signals::interrupts_inhibiter inhibiter;
425 const datetime::timestamp now = datetime::timestamp::now();
426 _pimpl.reset(new impl(now + delta));
427 if (globals.get() == NULL) {
428 globals.reset(new global_state(this, now));
430 globals->program_new(this, now);
435 /// Destructor; unprograms the timer if still programmed.
437 /// Given that this is a destructor and it can't report errors back to the
438 /// caller, the caller must attempt to call unprogram() on its own. This is
439 /// extremely important because, otherwise, expired timers will never run!
440 signals::timer::~timer(void)
442 signals::interrupts_inhibiter inhibiter;
444 if (_pimpl->programmed) {
445 LW("Auto-destroying still-programmed signals::timer object");
448 } catch (const system_error& e) {
453 if (!_pimpl->fired) {
454 const datetime::timestamp now = datetime::timestamp::now();
455 if (now > _pimpl->when) {
456 LW("Expired timer never fired; the code never called unprogram()!");
462 /// Returns the time of the timer activation.
464 /// \return A timestamp that has no relation to the current time (i.e. can be in
465 /// the future or in the past) nor the timer's activation status.
466 const datetime::timestamp&
467 signals::timer::when(void) const
473 /// Callback for the SIGALRM handler when this timer expires.
475 /// \warning This is executed from a signal handler context without signals
476 /// inhibited. See signal(7) for acceptable system calls.
478 signals::timer::do_fired(void)
481 _pimpl->fired = true;
486 /// User-provided callback to run when the timer expires.
488 /// The default callback does nothing. We record the activation of the timer
489 /// separately, which may be appropriate in the majority of the cases.
491 /// \warning This is executed from a signal handler context without signals
492 /// inhibited. See signal(7) for acceptable system calls.
494 signals::timer::callback(void)
496 // Intentionally left blank.
500 /// Checks whether the timer has fired already or not.
502 /// \return Returns true if the timer has fired.
504 signals::timer::fired(void) const
506 return _pimpl->fired;
510 /// Unprograms the timer.
512 /// \pre The timer is programmed (i.e. this can only be called once).
514 /// \post If the timer never fired asynchronously because the signal delivery
515 /// did not arrive on time, make sure we invoke the timer's callback here.
517 /// \throw system_error If unprogramming the timer failed.
519 signals::timer::unprogram(void)
521 signals::interrupts_inhibiter inhibiter;
523 if (!_pimpl->programmed) {
524 // We cannot assert that the timer is not programmed because it might
525 // have been unprogrammed asynchronously between the time we called
526 // unprogram() and the time we reach this. Simply return in this case.
527 LD("Called unprogram on already-unprogrammed timer; possibly just "
532 if (!globals->unprogram(this)) {
535 _pimpl->programmed = false;
537 // Handle the case where the timer has expired before we ever got its
538 // corresponding signal. Do so by invoking its callback now.
539 if (!_pimpl->fired) {
540 const datetime::timestamp now = datetime::timestamp::now();
541 if (now > _pimpl->when) {
542 LW(F("Firing expired timer on destruction (was to fire on %s)") %