Kannel: Open Source WAP and SMS gateway  $Revision: 5037 $
timers.c
Go to the documentation of this file.
1 /* ====================================================================
2  * The Kannel Software License, Version 1.0
3  *
4  * Copyright (c) 2001-2016 Kannel Group
5  * Copyright (c) 1998-2001 WapIT Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Kannel Group (http://www.kannel.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Kannel" and "Kannel Group" must not be used to
28  * endorse or promote products derived from this software without
29  * prior written permission. For written permission, please
30  * contact org@kannel.org.
31  *
32  * 5. Products derived from this software may not be called "Kannel",
33  * nor may "Kannel" appear in their name, without prior written
34  * permission of the Kannel Group.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS
40  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
41  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
42  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
44  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
45  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
46  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This software consists of voluntary contributions made by many
50  * individuals on behalf of the Kannel Group. For more information on
51  * the Kannel Group, please see <http://www.kannel.org/>.
52  *
53  * Portions of this software are based upon software originally written at
54  * WapIT Ltd., Helsinki, Finland for the Kannel project.
55  */
56 
57 /*
58  * timers.c - timers and set of timers, mainly for WTP.
59  *
60  * See timers.h for a description of the interface.
61  */
62 
63 #include <signal.h>
64 
65 #include "gwlib/gwlib.h"
66 #include "wap_events.h"
67 #include "timers.h"
68 
69 /*
70  * Active timers are stored in a TimerHeap. It is a partially ordered
71  * array. Each element i is the child of element i/2 (rounded down),
72  * and a child never elapses before its parent. The result is that
73  * element 0, the top of the heap, is always the first timer to
74  * elapse. The heap is kept in this partial order by all operations on
75  * it. Maintaining a partial order is much cheaper than maintaining
76  * a sorted list.
77  * The array will be resized as needed. The size field is the number
78  * of elements for which space is reserved, and the len field is the
79  * number of elements actually used. The elements used will always be
80  * at tab[0] through tab[len-1].
81  */
82 struct TimerHeap
83 {
84  Timer **tab;
85  long len;
86  long size;
87 };
88 typedef struct TimerHeap TimerHeap;
89 
90 struct Timerset
91 {
92  /*
93  * This field is set to true when the timer thread should shut down.
94  */
95  volatile sig_atomic_t stopping;
96  /*
97  * The entire set is locked for any operation on it. This is
98  * not as expensive as it sounds because usually each set is
99  * used by one caller thread and one (internal) timer thread,
100  * and the timer thread does not wake up very often.
101  */
102  Mutex *mutex;
103  /*
104  * Active timers are stored here in a partially ordered structure.
105  * See the definition of TimerHeap, above, for an explanation.
106  */
107  TimerHeap *heap;
108  /*
109  * The thread that watches the top of the heap, and processes
110  * timers that have elapsed.
111  */
112  long thread;
113 };
114 typedef struct Timerset Timerset;
115 
116 struct Timer
117 {
118  /*
119  * An event is produced on the output list when the
120  * timer elapses. The timer is not considered to have
121  * elapsed completely until that pointer has also been
122  * consumed from this list (by the caller, presumably).
123  * That is why the timer code sometimes goes back and
124  * removes a pointer from the output list.
125  */
126  List *output;
127  /*
128  * The timer is set to elapse at this time, expressed in
129  * Unix time format. This field is set to -1 if the timer
130  * is not active (i.e. in the timer set's heap).
131  */
132  long elapses;
133  /*
134  * A duplicate of this event will be put on the output list
135  * when the timer elapses. It can be NULL if the timer has
136  * not been started yet.
137  */
139  /*
140  * This field is normally NULL, but after the timer elapses
141  * it points to the event that was put on the output list.
142  * It is set back to NULL if the event was taken back from
143  * the list, or if it's confirmed that the event was consumed.
144  */
146  /*
147  * Index in the timer set's heap. This field is managed by
148  * the heap operations, and is used to make them faster.
149  * If this timer is not in the heap, this field is -1.
150  */
151  long index;
152 };
153 
154 /*
155  * Currently we have one timerset (and thus one heap and one thread)
156  * for all timers. This might change in the future in order to tune
157  * performance. In that case, it will be necessary to add a "set"
158  * field to the Timer structure.
159  */
160 static Timerset *timers;
161 
162 /*
163  * Used by timer functions to assert that the timer module has been
164  * intialized.
165  */
166 static int initialized = 0;
167 
168 /*
169  * Internal functions
170  */
171 static void abort_elapsed(Timer *timer);
172 static TimerHeap *heap_create(void);
173 static void heap_destroy(TimerHeap *heap);
174 static void heap_delete(TimerHeap *heap, long index);
175 static int heap_adjust(TimerHeap *heap, long index);
176 static void heap_insert(TimerHeap *heap, Timer *timer);
177 static void heap_swap(TimerHeap *heap, long index1, long index2);
178 static void lock(Timerset *set);
179 static void unlock(Timerset *set);
180 static void watch_timers(void *arg); /* The timer thread */
181 static void elapse_timer(Timer *timer);
182 
183 
184 void timers_init(void)
185 {
186  if (initialized == 0) {
187  timers = gw_malloc(sizeof(*timers));
188  timers->mutex = mutex_create();
189  timers->heap = heap_create();
190  timers->stopping = 0;
191  timers->thread = gwthread_create(watch_timers, timers);
192  }
193  initialized++;
194 }
195 
196 void timers_shutdown(void)
197 {
198  if (initialized > 1) {
199  initialized--;
200  return;
201  }
202 
203  /* Stop all timers. */
204  if (timers->heap->len > 0)
205  warning(0, "Timers shutting down with %ld active timers.",
206  timers->heap->len);
207  while (timers->heap->len > 0)
208  gwtimer_stop(timers->heap->tab[0]);
209 
210  /* Kill timer thread */
211  timers->stopping = 1;
212  gwthread_wakeup(timers->thread);
213  gwthread_join(timers->thread);
214 
215  initialized = 0;
216 
217  /* Free resources */
218  heap_destroy(timers->heap);
219  mutex_destroy(timers->mutex);
220  gw_free(timers);
221 }
222 
223 
224 Timer *gwtimer_create(List *outputlist)
225 {
226  Timer *t;
227 
229 
230  t = gw_malloc(sizeof(*t));
231  t->elapses = -1;
232  t->event = NULL;
233  t->elapsed_event = NULL;
234  t->index = -1;
235  t->output = outputlist;
236  gwlist_add_producer(outputlist);
237 
238  return t;
239 }
240 
241 void gwtimer_destroy(Timer *timer)
242 {
244 
245  if (timer == NULL)
246  return;
247 
248  gwtimer_stop(timer);
250  wap_event_destroy(timer->event);
251  gw_free(timer);
252 }
253 
254 void gwtimer_start(Timer *timer, int interval, WAPEvent *event)
255 {
256  int wakeup = 0;
257 
259  gw_assert(timer != NULL);
260  gw_assert(event != NULL || timer->event != NULL);
261 
262  lock(timers);
263 
264  /* Convert to absolute time */
265  interval += time(NULL);
266 
267  if (timer->elapses > 0) {
268  /* Resetting an existing timer. Move it to its new
269  * position in the heap. */
270  if (interval < timer->elapses && timer->index == 0)
271  wakeup = 1;
272  timer->elapses = interval;
273  gw_assert(timers->heap->tab[timer->index] == timer);
274  wakeup |= heap_adjust(timers->heap, timer->index);
275  } else {
276  /* Setting a new timer, or resetting an elapsed one.
277  * First deal with a possible elapse event that may
278  * still be on the output list. */
279  abort_elapsed(timer);
280 
281  /* Then activate the timer. */
282  timer->elapses = interval;
283  gw_assert(timer->index < 0);
284  heap_insert(timers->heap, timer);
285  wakeup = timer->index == 0; /* Do we have a new top? */
286  }
287 
288  if (event != NULL) {
289  wap_event_destroy(timer->event);
290  timer->event = event;
291  }
292 
293  unlock(timers);
294 
295  if (wakeup)
296  gwthread_wakeup(timers->thread);
297 }
298 
299 void gwtimer_stop(Timer *timer)
300 {
302  gw_assert(timer != NULL);
303  lock(timers);
304 
305  /*
306  * If the timer is active, make it inactive and remove it from
307  * the heap.
308  */
309  if (timer->elapses > 0) {
310  timer->elapses = -1;
311  gw_assert(timers->heap->tab[timer->index] == timer);
312  heap_delete(timers->heap, timer->index);
313  }
314 
315  abort_elapsed(timer);
316 
317  unlock(timers);
318 }
319 
320 static void lock(Timerset *set)
321 {
322  gw_assert(set != NULL);
323  mutex_lock(set->mutex);
324 }
325 
326 static void unlock(Timerset *set)
327 {
328  gw_assert(set != NULL);
329  mutex_unlock(set->mutex);
330 }
331 
332 /*
333  * Go back and remove this timer's elapse event from the output list,
334  * to pretend that it didn't elapse after all. This is necessary
335  * to deal with some races between the timer thread and the caller's
336  * start/stop actions.
337  */
338 static void abort_elapsed(Timer *timer)
339 {
340  long count;
341 
342  if (timer->elapsed_event == NULL)
343  return;
344 
345  count = gwlist_delete_equal(timer->output, timer->elapsed_event);
346  if (count > 0) {
347  debug("timers", 0, "Aborting %s timer.",
350  }
351  timer->elapsed_event = NULL;
352 }
353 
354 /*
355  * Create a new timer heap.
356  */
357 static TimerHeap *heap_create(void)
358 {
359  TimerHeap *heap;
360 
361  heap = gw_malloc(sizeof(*heap));
362  heap->tab = gw_malloc(sizeof(heap->tab[0]));
363  heap->size = 1;
364  heap->len = 0;
365 
366  return heap;
367 }
368 
369 static void heap_destroy(TimerHeap *heap)
370 {
371  if (heap == NULL)
372  return;
373 
374  gw_free(heap->tab);
375  gw_free(heap);
376 }
377 
378 /*
379  * Remove a timer from the heap. Do this by swapping it with the element
380  * in the last position, then shortening the heap, then moving the
381  * swapped element up or down to maintain the partial ordering.
382  */
383 static void heap_delete(TimerHeap *heap, long index)
384 {
385  long last;
386 
387  gw_assert(index >= 0);
388  gw_assert(index < heap->len);
389  gw_assert(heap->tab[index]->index == index);
390 
391  last = heap->len - 1;
392  heap_swap(heap, index, last);
393  heap->tab[last]->index = -1;
394  heap->len--;
395  if (index != last)
396  heap_adjust(heap, index);
397 }
398 
399 /*
400  * Add a timer to the heap. Do this by adding it at the end, then
401  * moving it up or down as necessary to achieve partial ordering.
402  */
403 static void heap_insert(TimerHeap *heap, Timer *timer)
404 {
405  heap->len++;
406  if (heap->len > heap->size) {
407  heap->tab = gw_realloc(heap->tab,
408  heap->len * sizeof(heap->tab[0]));
409  heap->size = heap->len;
410  }
411  heap->tab[heap->len - 1] = timer;
412  timer->index = heap->len - 1;
413  heap_adjust(heap, timer->index);
414 }
415 
416 /*
417  * Swap two elements of the heap, and update their index fields.
418  * This is the basic heap operation.
419  */
420 static void heap_swap(TimerHeap *heap, long index1, long index2)
421 {
422  Timer *t;
423 
424  gw_assert(index1 >= 0);
425  gw_assert(index1 < heap->len);
426  gw_assert(index2 >= 0);
427  gw_assert(index2 < heap->len);
428 
429  if (index1 == index2)
430  return;
431 
432  t = heap->tab[index1];
433  heap->tab[index1] = heap->tab[index2];
434  heap->tab[index2] = t;
435  heap->tab[index1]->index = index1;
436  heap->tab[index2]->index = index2;
437 }
438 
439 /*
440  * The current element has broken the partial ordering of the
441  * heap (see explanation in the definition of Timerset), and
442  * it has to be moved up or down until the ordering is restored.
443  * Return 1 if the timer at the heap's top is now earlier than
444  * before this operation, otherwise 0.
445  */
446 static int heap_adjust(TimerHeap *heap, long index)
447 {
448  Timer *t;
449  Timer *parent;
450  long child_index;
451 
452  /*
453  * We can assume that the heap was fine before this element's
454  * elapse time was changed. There are three cases to deal
455  * with:
456  * - Element's new elapse time is too small; it should be
457  * moved toward the top.
458  * - Element's new elapse time is too large; it should be
459  * moved toward the bottom.
460  * - Element's new elapse time still fits here, we don't
461  * have to do anything.
462  */
463 
464  gw_assert(index >= 0);
465  gw_assert(index < heap->len);
466 
467  /* Move to top? */
468  t = heap->tab[index];
469  parent = heap->tab[index / 2];
470  if (t->elapses < parent->elapses) {
471  /* This will automatically terminate when it reaches
472  * the top, because in that t == parent. */
473  do {
474  heap_swap(heap, index, index / 2);
475  index = index / 2;
476  parent = heap->tab[index / 2];
477  } while (t->elapses < parent->elapses);
478  /* We're done. Return 1 if we changed the top. */
479  return index == 0;
480  }
481 
482  /* Move to bottom? */
483  for (; ; ) {
484  child_index = index * 2;
485  if (child_index >= heap->len)
486  return 0; /* Already at bottom */
487  if (child_index == heap->len - 1) {
488  /* Only one child */
489  if (heap->tab[child_index]->elapses < t->elapses)
490  heap_swap(heap, index, child_index);
491  break;
492  }
493 
494  /* Find out which child elapses first */
495  if (heap->tab[child_index + 1]->elapses <
496  heap->tab[child_index]->elapses) {
497  child_index++;
498  }
499 
500  if (heap->tab[child_index]->elapses < t->elapses) {
501  heap_swap(heap, index, child_index);
502  index = child_index;
503  } else {
504  break;
505  }
506  }
507 
508  return 0;
509 }
510 
511 /*
512  * This timer has elapsed. Do the housekeeping. We have its set locked.
513  */
514 static void elapse_timer(Timer *timer)
515 {
516  gw_assert(timer != NULL);
517  gw_assert(timers != NULL);
518  /* This must be true because abort_elapsed is always called
519  * before a timer is activated. */
520  gw_assert(timer->elapsed_event == NULL);
521 
522  debug("timers", 0, "%s elapsed.", wap_event_name(timer->event->type));
523 
524  timer->elapsed_event = wap_event_duplicate(timer->event);
525  gwlist_produce(timer->output, timer->elapsed_event);
526  timer->elapses = -1;
527 }
528 
529 /*
530  * Main function for timer thread.
531  */
532 static void watch_timers(void *arg)
533 {
534  Timerset *set;
535  long top_time;
536  long now;
537 
538  set = arg;
539 
540  while (!set->stopping) {
541  lock(set);
542 
543  now = time(NULL);
544 
545  while (set->heap->len > 0 && set->heap->tab[0]->elapses <= now) {
546  elapse_timer(set->heap->tab[0]);
547  heap_delete(set->heap, 0);
548  }
549 
550  /*
551  * Now sleep until the next timer elapses. If there isn't one,
552  * then just sleep very long. We will get woken up if the
553  * top of the heap changes before we wake.
554  */
555 
556  if (set->heap->len == 0) {
557  unlock(set);
558  gwthread_sleep(1000000.0);
559  } else {
560  top_time = set->heap->tab[0]->elapses;
561  unlock(set);
562  gwthread_sleep(top_time - now);
563  }
564  }
565 }
static void heap_insert(TimerHeap *heap, Timer *timer)
Definition: timers.c:403
WAPEvent * elapsed_event
Definition: timers.c:145
static int initialized
Definition: timers.c:166
#define mutex_unlock(m)
Definition: thread.h:136
long size
Definition: gw-timer.c:85
void gwlist_produce(List *list, void *item)
Definition: list.c:411
static TimerHeap * heap_create(void)
Definition: timers.c:357
volatile sig_atomic_t stopping
Definition: gw-timer.c:94
static void heap_delete(TimerHeap *heap, long index)
Definition: timers.c:383
void gwthread_join(long thread)
#define mutex_create()
Definition: thread.h:96
List * output
Definition: gw-timer.c:128
static void lock(Timerset *set)
Definition: timers.c:320
Timer ** tab
Definition: gw-timer.c:83
void gwtimer_stop(Timer *timer)
Definition: timers.c:299
static void heap_destroy(TimerHeap *heap)
Definition: timers.c:369
TimerHeap * heap
Definition: gw-timer.c:106
void gwtimer_start(Timer *timer, int interval, WAPEvent *event)
Definition: timers.c:254
void gwlist_remove_producer(List *list)
Definition: list.c:401
void gwtimer_destroy(Timer *timer)
Definition: timers.c:241
static void elapse_timer(Timer *timer)
Definition: timers.c:514
const char * wap_event_name(WAPEventName type)
Definition: wap_events.c:169
long gwlist_delete_equal(List *list, void *item)
Definition: list.c:266
void warning(int err, const char *fmt,...)
Definition: log.c:624
void timers_shutdown(void)
Definition: timers.c:196
static Timerset * timers
Definition: timers.c:160
#define gwthread_create(func, arg)
Definition: gwthread.h:90
gw_assert(wtls_machine->packet_to_send!=NULL)
void gwthread_sleep(double seconds)
void mutex_destroy(Mutex *mutex)
Definition: thread.c:97
void timers_init(void)
Definition: timers.c:184
double interval
Definition: fakewap.c:234
long thread
Definition: gw-timer.c:111
WAPEvent * event
Definition: timers.c:138
WAPEvent * wap_event_duplicate(WAPEvent *event)
Definition: wap_events.c:135
static void unlock(Timerset *set)
Definition: timers.c:326
long elapses
Definition: gw-timer.c:138
void debug(const char *place, int err, const char *fmt,...)
Definition: log.c:690
static int heap_adjust(TimerHeap *heap, long index)
Definition: timers.c:446
static void heap_swap(TimerHeap *heap, long index1, long index2)
Definition: timers.c:420
void gwthread_wakeup(long thread)
WAPEventName type
Definition: wap_events.h:88
static void watch_timers(void *arg)
Definition: timers.c:532
long index
Definition: gw-timer.c:157
Definition: thread.h:76
long len
Definition: gw-timer.c:84
Timer * gwtimer_create(List *outputlist)
Definition: timers.c:224
Mutex * mutex
Definition: gw-timer.c:101
void gwlist_add_producer(List *list)
Definition: list.c:383
#define mutex_lock(m)
Definition: thread.h:130
Definition: list.c:102
void wap_event_destroy(WAPEvent *event)
Definition: wap_events.c:102
static void abort_elapsed(Timer *timer)
Definition: timers.c:338
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.