src/timer.c

   1 /*
   2  * (C) 2008,2009 by Holger Hans Peter Freyther <zecke@selfish.org>
   3  * (C) 2011 by Harald Welte <laforge@gnumonks.org>
   4  * All Rights Reserved
   5  *
   6  * Authors: Holger Hans Peter Freyther <zecke@selfish.org>
   7  *          Harald Welte <laforge@gnumonks.org>
   8  *          Pablo Neira Ayuso <pablo@gnumonks.org>
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License along
  21  * with this program; if not, write to the Free Software Foundation, Inc.,
  22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  23  *
  24  */
  25
  26 /* These store the amount of time that we wait until next timer expires. */
  27 static struct timeval nearest;
  28 static struct timeval *nearest_p;
  29
  30 /*! \addtogroup timer
  31  *  @{
  32  */
  33
  34 /*! \file timer.c
  35  */
  36
  37 #include <assert.h>
  38 #include <string.h>
  39 #include <limits.h>
  40 #include <osmocom/core/timer.h>
  41 #include <osmocom/core/timer_compat.h>
  42 #include <osmocom/core/linuxlist.h>
  43
  44 static struct rb_root timer_root = RB_ROOT;
  45
  46 static void __add_timer(struct osmo_timer_list *timer)
  47 {
  48         struct rb_node **new = &(timer_root.rb_node);
  49         struct rb_node *parent = NULL;
  50
  51         while (*new) {
  52                 struct osmo_timer_list *this;
  53
  54                 this = container_of(*new, struct osmo_timer_list, node);
  55
  56                 parent = *new;
  57                 if (timercmp(&timer->timeout, &this->timeout, <))
  58                         new = &((*new)->rb_left);
  59                 else
  60                         new = &((*new)->rb_right);
  61         }
  62
  63         rb_link_node(&timer->node, parent, new);
  64         rb_insert_color(&timer->node, &timer_root);
  65 }
  66
  67 /*! \brief add a new timer to the timer management
  68  *  \param[in] timer the timer that should be added
  69  */
  70 void osmo_timer_add(struct osmo_timer_list *timer)
  71 {
  72         osmo_timer_del(timer);
  73         timer->active = 1;
  74         INIT_LLIST_HEAD(&timer->list);
  75         __add_timer(timer);
  76 }
  77
  78 /*! \brief schedule a timer at a given future relative time
  79  *  \param[in] timer the to-be-added timer
  80  *  \param[in] seconds number of seconds from now
  81  *  \param[in] microseconds number of microseconds from now
  82  *
  83  * This function can be used to (re-)schedule a given timer at a
  84  * specified number of seconds+microseconds in the future.  It will
  85  * internally add it to the timer management data structures, thus
  86  * osmo_timer_add() is automatically called.
  87  */
  88 void
  89 osmo_timer_schedule(struct osmo_timer_list *timer, int seconds, int microseconds)
  90 {
  91         struct timeval current_time;
  92
  93         gettimeofday(&current_time, NULL);
  94         timer->timeout.tv_sec = seconds;
  95         timer->timeout.tv_usec = microseconds;
  96         timeradd(&timer->timeout, &current_time, &timer->timeout);
  97         osmo_timer_add(timer);
  98 }
  99
 100 /*! \brief delete a timer from timer management
 101  *  \param[in] timer the to-be-deleted timer
 102  *
 103  * This function can be used to delete a previously added/scheduled
 104  * timer from the timer management code.
 105  */
 106 void osmo_timer_del(struct osmo_timer_list *timer)
 107 {
 108         if (timer->active) {
 109                 timer->active = 0;
 110                 rb_erase(&timer->node, &timer_root);
 111                 /* make sure this is not already scheduled for removal. */
 112                 if (!llist_empty(&timer->list))
 113                         llist_del_init(&timer->list);
 114         }
 115 }
 116
 117 /*! \brief check if given timer is still pending
 118  *  \param[in] timer the to-be-checked timer
 119  *  \return 1 if pending, 0 otherwise
 120  *
 121  * This function can be used to determine whether a given timer
 122  * has alredy expired (returns 0) or is still pending (returns 1)
 123  */
 124 int osmo_timer_pending(struct osmo_timer_list *timer)
 125 {
 126         return timer->active;
 127 }
 128
 129 /*
 130  * if we have a nearest time return the delta between the current
 131  * time and the time of the nearest timer.
 132  * If the nearest timer timed out return NULL and then we will
 133  * dispatch everything after the select
 134  */
 135 struct timeval *osmo_timers_nearest(void)
 136 {
 137         /* nearest_p is exactly what we need already: NULL if nothing is
 138          * waiting, {0,0} if we must dispatch immediately, and the correct
 139          * delay if we need to wait */
 140         return nearest_p;
 141 }
 142
 143 static void update_nearest(struct timeval *cand, struct timeval *current)
 144 {
 145         if (cand->tv_sec != LONG_MAX) {
 146                 if (timercmp(cand, current, >))
 147                         timersub(cand, current, &nearest);
 148                 else {
 149                         /* loop again inmediately */
 150                         nearest.tv_sec = 0;
 151                         nearest.tv_usec = 0;
 152                 }
 153                 nearest_p = &nearest;
 154         } else {
 155                 nearest_p = NULL;
 156         }
 157 }
 158
 159 /*
 160  * Find the nearest time and update s_nearest_time
 161  */
 162 void osmo_timers_prepare(void)
 163 {
 164         struct rb_node *node;
 165         struct timeval current;
 166
 167         gettimeofday(&current, NULL);
 168
 169         node = rb_first(&timer_root);
 170         if (node) {
 171                 struct osmo_timer_list *this;
 172                 this = container_of(node, struct osmo_timer_list, node);
 173                 update_nearest(&this->timeout, &current);
 174         } else {
 175                 nearest_p = NULL;
 176         }
 177 }
 178
 179 /*
 180  * fire all timers... and remove them
 181  */
 182 int osmo_timers_update(void)
 183 {
 184         struct timeval current_time;
 185         struct rb_node *node;
 186         struct llist_head timer_eviction_list;
 187         struct osmo_timer_list *this;
 188         int work = 0;
 189
 190         gettimeofday(&current_time, NULL);
 191
 192         INIT_LLIST_HEAD(&timer_eviction_list);
 193         for (node = rb_first(&timer_root); node; node = rb_next(node)) {
 194                 this = container_of(node, struct osmo_timer_list, node);
 195
 196                 if (timercmp(&this->timeout, &current_time, >))
 197                         break;
 198
 199                 llist_add(&this->list, &timer_eviction_list);
 200         }
 201
 202         /*
 203          * The callbacks might mess with our list and in this case
 204          * even llist_for_each_entry_safe is not safe to use. To allow
 205          * osmo_timer_del to be called from within the callback we need
 206          * to restart the iteration for each element scheduled for removal.
 207          *
 208          * The problematic scenario is the following: Given two timers A
 209          * and B that have expired at the same time. Thus, they are both
 210          * in the eviction list in this order: A, then B. If we remove
 211          * timer B from the A's callback, we continue with B in the next
 212          * iteration step, leading to an access-after-release.
 213          */
 214 restart:
 215         llist_for_each_entry(this, &timer_eviction_list, list) {
 216                 osmo_timer_del(this);
 217                 this->cb(this->data);
 218                 work = 1;
 219                 goto restart;
 220         }
 221
 222         return work;
 223 }
 224
 225 int osmo_timers_check(void)
 226 {
 227         struct rb_node *node;
 228         int i = 0;
 229
 230         for (node = rb_first(&timer_root); node; node = rb_next(node)) {
 231                 i++;
 232         }
 233         return i;
 234 }
 235
 236 /*! }@ */