Kannel: Open Source WAP and SMS gateway  $Revision: 5037 $
gw-timer.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  * gw-timer.c - timers and set of timers.
59  *
60  * See gw-timer.h for a description of the interface.
61  */
62 
63 #include <signal.h>
64 
65 #include "gwlib/gwlib.h"
66 #include "gw-timer.h"
67 
68 /*
69  * Active timers are stored in a TimerHeap. It is a partially ordered
70  * array. Each element i is the child of element i/2 (rounded down),
71  * and a child never elapses before its parent. The result is that
72  * element 0, the top of the heap, is always the first timer to
73  * elapse. The heap is kept in this partial order by all operations on
74  * it. Maintaining a partial order is much cheaper than maintaining
75  * a sorted list.
76  * The array will be resized as needed. The size field is the number
77  * of elements for which space is reserved, and the len field is the
78  * number of elements actually used. The elements used will always be
79  * at tab[0] through tab[len-1].
80  */
81 struct TimerHeap
82 {
84  long len;
85  long size;
86 };
87 typedef struct TimerHeap TimerHeap;
88 
89 struct Timerset
90 {
91  /*
92  * This field is set to true when the timer thread should shut down.
93  */
94  volatile sig_atomic_t stopping;
95  /*
96  * The entire set is locked for any operation on it. This is
97  * not as expensive as it sounds because usually each set is
98  * used by one caller thread and one (internal) timer thread,
99  * and the timer thread does not wake up very often.
100  */
102  /*
103  * Active timers are stored here in a partially ordered structure.
104  * See the definition of TimerHeap, above, for an explanation.
105  */
107  /*
108  * The thread that watches the top of the heap, and processes
109  * timers that have elapsed.
110  */
111  long thread;
112 };
113 
114 struct Timer
115 {
116  /*
117  * The timer set this timer belongs to.
118  */
120  /*
121  * An event is produced on the output list when the
122  * timer elapses. The timer is not considered to have
123  * elapsed completely until that pointer has also been
124  * consumed from this list (by the caller, presumably).
125  * That is why the timer code sometimes goes back and
126  * removes a pointer from the output list.
127  */
129  /*
130  * A call back function is called when the timer elapses.
131  */
132  void (*callback) (void* data);
133  /*
134  * The timer is set to elapse at this time, expressed in
135  * Unix time format. This field is set to -1 if the timer
136  * is not active (i.e. in the timer set's heap).
137  */
138  long elapses;
139  /*
140  * A duplicate of this event will be put on the output list
141  * when the timer elapses. It can be NULL if the timer has
142  * not been started yet.
143  */
144  void *data;
145  /*
146  * This field is normally NULL, but after the timer elapses
147  * it points to the event that was put on the output list.
148  * It is set back to NULL if the event was taken back from
149  * the list, or if it's confirmed that the event was consumed.
150  */
152  /*
153  * The index in the timer set's heap. This field is managed by
154  * the heap operations, and is used to make them faster.
155  * If this timer is not in the heap, this field is -1.
156  */
157  long index;
158 };
159 
160 
161 /*
162  * Internal functions
163  */
164 static void abort_elapsed(Timer *timer);
165 static TimerHeap *heap_create(void);
166 static void heap_destroy(TimerHeap *heap);
167 static void heap_delete(TimerHeap *heap, long index);
168 static int heap_adjust(TimerHeap *heap, long index);
169 static void heap_insert(TimerHeap *heap, Timer *timer);
170 static void heap_swap(TimerHeap *heap, long index1, long index2);
171 static void lock(Timerset *set);
172 static void unlock(Timerset *set);
173 static void watch_timers(void *arg); /* The timer thread */
174 static void elapse_timer(Timer *timer);
175 
176 
178 {
179  Timerset *set;
180 
181  set = gw_malloc(sizeof(Timerset));
182  set->mutex = mutex_create();
183  set->heap = heap_create();
184  set->stopping = 0;
185  set->thread = gwthread_create(watch_timers, set);
186 
187  return set;
188 }
189 
191 {
192  if (set == NULL)
193  return;
194 
195  /* Stop all timers. */
196  while (set->heap->len > 0)
197  gw_timer_stop(set->heap->tab[0]);
198 
199  /* Kill timer thread */
200  set->stopping = 1;
201  gwthread_wakeup(set->thread);
202  gwthread_join(set->thread);
203 
204  /* Free resources */
205  heap_destroy(set->heap);
206  mutex_destroy(set->mutex);
207  gw_free(set);
208 }
209 
210 
211 Timer *gw_timer_create(Timerset *set, List *outputlist, void (*callback) (void*))
212 {
213  Timer *t;
214 
215  t = gw_malloc(sizeof(*t));
216  t->timerset = set;
217  t->elapses = -1;
218  t->data = NULL;
219  t->elapsed_data = NULL;
220  t->index = -1;
221  t->output = outputlist;
222  if (t->output != NULL)
223  gwlist_add_producer(outputlist);
224  t->callback = callback;
225 
226  return t;
227 }
228 
230 {
231  if (timer == NULL)
232  return;
233 
234  gw_timer_stop(timer);
235  if (timer->output != NULL)
237  gw_free(timer);
238 }
239 
241 {
242  if (timer == NULL)
243  return;
244 
245  gw_timer_elapsed_stop(timer);
246  if (timer->output != NULL)
248  gw_free(timer);
249 }
250 
251 void gw_timer_start(Timer *timer, int interval, void *data)
252 {
253  int wakeup = 0;
254 
255  gw_assert(timer != NULL);
256 
257  if (timer == NULL)
258  return;
259 
260  lock(timer->timerset);
261 
262  /* Convert to absolute time */
263  interval += time(NULL);
264 
265  if (timer->elapses > 0) {
266  /* Resetting an existing timer. Move it to its new
267  * position in the heap. */
268  if (interval < timer->elapses && timer->index == 0)
269  wakeup = 1;
270  timer->elapses = interval;
271  gw_assert(timer->index >= 0);
272  gw_assert(timer->timerset->heap->tab[timer->index] == timer);
273  wakeup |= heap_adjust(timer->timerset->heap, timer->index);
274  } else {
275  /* Setting a new timer, or resetting an elapsed one.
276  * First deal with a possible elapse event that may
277  * still be on the output list. */
278  abort_elapsed(timer);
279 
280  /* Then activate the timer. */
281  timer->elapses = interval;
282  gw_assert(timer->index < 0);
283  heap_insert(timer->timerset->heap, timer);
284  wakeup = timer->index == 0; /* Do we have a new top? */
285  }
286 
287  if (data != NULL) {
288  timer->data = data;
289  }
290 
291  unlock(timer->timerset);
292 
293  if (wakeup)
295 }
296 
297 void gw_timer_elapsed_start(Timer *timer, int interval, void *data)
298 {
299  int wakeup = 0;
300 
301  gw_assert(timer != NULL);
302 
303  if (timer == NULL)
304  return;
305 
306  lock(timer->timerset);
307 
308  /* Convert to absolute time */
309  interval += time(NULL);
310 
311  if (timer->elapses > 0) {
312  /* Resetting an existing timer. Move it to its new
313  * position in the heap. */
314  if (interval < timer->elapses && timer->index == 0)
315  wakeup = 1;
316  timer->elapses = interval;
317  gw_assert(timer->index >= 0);
318  gw_assert(timer->timerset->heap->tab[timer->index] == timer);
319  wakeup |= heap_adjust(timer->timerset->heap, timer->index);
320  } else {
321  /* Setting a new timer, or resetting an elapsed one.
322  * There should be no further elapse event on the
323  * output list here. */
324  /* abort_elapsed(timer); */
325  timer->elapsed_data = NULL;
326 
327  /* Then activate the timer. */
328  timer->elapses = interval;
329  gw_assert(timer->index < 0);
330  heap_insert(timer->timerset->heap, timer);
331  wakeup = timer->index == 0; /* Do we have a new top? */
332  }
333 
334  if (data != NULL) {
335  timer->data = data;
336  }
337 
338  unlock(timer->timerset);
339 
340  if (wakeup)
342 }
343 
344 void gw_timer_stop(Timer *timer)
345 {
346  gw_assert(timer != NULL);
347  lock(timer->timerset);
348 
349  /*
350  * If the timer is active, make it inactive and remove it from
351  * the heap.
352  */
353  if (timer->elapses > 0) {
354  timer->elapses = -1;
355  gw_assert(timer->timerset->heap->tab[timer->index] == timer);
356  heap_delete(timer->timerset->heap, timer->index);
357  }
358 
359  abort_elapsed(timer);
360 
361  unlock(timer->timerset);
362 }
363 
365 {
366  gw_assert(timer != NULL);
367  lock(timer->timerset);
368 
369  /*
370  * If the timer is active, make it inactive and remove it from
371  * the heap.
372  */
373  if (timer->elapses > 0) {
374  timer->elapses = -1;
375  gw_assert(timer->timerset->heap->tab[timer->index] == timer);
376  heap_delete(timer->timerset->heap, timer->index);
377  }
378 
379  /* abort_elapsed(timer); */
380  timer->elapsed_data = NULL;
381 
382  unlock(timer->timerset);
383 }
384 
386 {
387  List *ret = NULL;
388 
389  lock(set);
390 
391  if (set->heap->len == 0) {
392  unlock(set);
393  return NULL;
394  }
395 
396  ret = gwlist_create();
397 
398  /* Stop all timers. */
399  while (set->heap->len > 0) {
400  Timer *timer = set->heap->tab[0];
401 
402  gwlist_append(ret, timer);
403 
404  /*
405  * If the timer is active, make it inactive and remove it from
406  * the heap.
407  */
408  if (timer->elapses > 0) {
409  timer->elapses = -1;
410  gw_assert(set->heap->tab[timer->index] == timer);
411  heap_delete(set->heap, timer->index);
412  }
413 
414  abort_elapsed(timer);
415  }
416 
417  unlock(set);
418 
419  return ret;
420 }
421 
422 void *gw_timer_data(Timer *timer)
423 {
424  gw_assert(timer != NULL);
425 
426  return timer->data;
427 }
428 
429 static void lock(Timerset *set)
430 {
431  gw_assert(set != NULL);
432  mutex_lock(set->mutex);
433 }
434 
435 static void unlock(Timerset *set)
436 {
437  gw_assert(set != NULL);
438  mutex_unlock(set->mutex);
439 }
440 
441 /*
442  * Go back and remove this timer's elapse event from the output list,
443  * to pretend that it didn't elapse after all. This is necessary
444  * to deal with some races between the timer thread and the caller's
445  * start/stop actions.
446  */
447 static void abort_elapsed(Timer *timer)
448 {
449  if (timer->elapsed_data == NULL)
450  return;
451 
452  if (timer->output != NULL)
453  gwlist_delete_equal(timer->output, timer->elapsed_data);
454  timer->elapsed_data = NULL;
455 }
456 
457 /*
458  * Create a new timer heap.
459  */
460 static TimerHeap *heap_create(void)
461 {
462  TimerHeap *heap;
463 
464  heap = gw_malloc(sizeof(*heap));
465  heap->tab = gw_malloc(sizeof(heap->tab[0]));
466  heap->size = 1;
467  heap->len = 0;
468 
469  return heap;
470 }
471 
472 static void heap_destroy(TimerHeap *heap)
473 {
474  if (heap == NULL)
475  return;
476 
477  gw_free(heap->tab);
478  gw_free(heap);
479 }
480 
481 /*
482  * Remove a timer from the heap. Do this by swapping it with the element
483  * in the last position, then shortening the heap, then moving the
484  * swapped element up or down to maintain the partial ordering.
485  */
486 static void heap_delete(TimerHeap *heap, long index)
487 {
488  long last;
489 
490  gw_assert(index >= 0);
491  gw_assert(index < heap->len);
492  gw_assert(heap->tab[index]->index == index);
493 
494  last = heap->len - 1;
495  heap_swap(heap, index, last);
496  heap->tab[last]->index = -1;
497  heap->len--;
498  if (index != last)
499  heap_adjust(heap, index);
500 }
501 
502 /*
503  * Add a timer to the heap. Do this by adding it at the end, then
504  * moving it up or down as necessary to achieve partial ordering.
505  */
506 static void heap_insert(TimerHeap *heap, Timer *timer)
507 {
508  heap->len++;
509  if (heap->len > heap->size) {
510  heap->tab = gw_realloc(heap->tab,
511  heap->len * sizeof(heap->tab[0]));
512  heap->size = heap->len;
513  }
514  heap->tab[heap->len - 1] = timer;
515  timer->index = heap->len - 1;
516  heap_adjust(heap, timer->index);
517 }
518 
519 /*
520  * Swap two elements of the heap, and update their index fields.
521  * This is the basic heap operation.
522  */
523 static void heap_swap(TimerHeap *heap, long index1, long index2)
524 {
525  Timer *t;
526 
527  gw_assert(index1 >= 0);
528  gw_assert(index1 < heap->len);
529  gw_assert(index2 >= 0);
530  gw_assert(index2 < heap->len);
531 
532  if (index1 == index2)
533  return;
534 
535  t = heap->tab[index1];
536  heap->tab[index1] = heap->tab[index2];
537  heap->tab[index2] = t;
538  heap->tab[index1]->index = index1;
539  heap->tab[index2]->index = index2;
540 }
541 
542 /*
543  * The current element has broken the partial ordering of the
544  * heap (see explanation in the definition of Timerset), and
545  * it has to be moved up or down until the ordering is restored.
546  * Return 1 if the timer at the heap's top is now earlier than
547  * before this operation, otherwise 0.
548  */
549 static int heap_adjust(TimerHeap *heap, long index)
550 {
551  Timer *t;
552  Timer *parent;
553  long child_index;
554 
555  /*
556  * We can assume that the heap was fine before this element's
557  * elapse time was changed. There are three cases to deal
558  * with:
559  * - Element's new elapse time is too small; it should be
560  * moved toward the top.
561  * - Element's new elapse time is too large; it should be
562  * moved toward the bottom.
563  * - Element's new elapse time still fits here, we don't
564  * have to do anything.
565  */
566 
567  gw_assert(index >= 0);
568  gw_assert(index < heap->len);
569 
570  /* Move to top? */
571  t = heap->tab[index];
572  parent = heap->tab[index / 2];
573  if (t->elapses < parent->elapses) {
574  /* This will automatically terminate when it reaches
575  * the top, because in that t == parent. */
576  do {
577  heap_swap(heap, index, index / 2);
578  index = index / 2;
579  parent = heap->tab[index / 2];
580  } while (t->elapses < parent->elapses);
581  /* We're done. Return 1 if we changed the top. */
582  return index == 0;
583  }
584 
585  /* Move to bottom? */
586  for (; ; ) {
587  child_index = index * 2;
588  if (child_index >= heap->len)
589  return 0; /* Already at bottom */
590  if (child_index == heap->len - 1) {
591  /* Only one child */
592  if (heap->tab[child_index]->elapses < t->elapses)
593  heap_swap(heap, index, child_index);
594  break;
595  }
596 
597  /* Find out which child elapses first */
598  if (heap->tab[child_index + 1]->elapses <
599  heap->tab[child_index]->elapses) {
600  child_index++;
601  }
602 
603  if (heap->tab[child_index]->elapses < t->elapses) {
604  heap_swap(heap, index, child_index);
605  index = child_index;
606  } else {
607  break;
608  }
609  }
610 
611  return 0;
612 }
613 
614 /*
615  * This timer has elapsed. Do the housekeeping. We have its set locked.
616  */
617 static void elapse_timer(Timer *timer)
618 {
619  gw_assert(timer != NULL);
620  gw_assert(timer->timerset != NULL);
621  /* This must be true because abort_elapsed is always called
622  * before a timer is activated. */
623  gw_assert(timer->elapsed_data == NULL);
624 
625  timer->elapsed_data = timer->data;
626  timer->elapses = -1;
627  if (timer->output != NULL)
628  gwlist_produce(timer->output, timer->elapsed_data);
629  if (timer->callback != NULL)
630  timer->callback(timer->elapsed_data);
631 }
632 
633 /*
634  * Main function for timer thread.
635  */
636 static void watch_timers(void *arg)
637 {
638  Timerset *set;
639  long top_time;
640  long now;
641 
642  set = arg;
643 
644  while (!set->stopping) {
645  lock(set);
646 
647  now = time(NULL);
648 
649  while (set->heap->len > 0 && set->heap->tab[0]->elapses <= now) {
650  Timer *timer = set->heap->tab[0];
651  heap_delete(set->heap, 0);
652  elapse_timer(timer);
653  }
654 
655  /*
656  * Now sleep until the next timer elapses. If there isn't one,
657  * then just sleep very long. We will get woken up if the
658  * top of the heap changes before we wake.
659  */
660 
661  if (set->heap->len == 0) {
662  unlock(set);
663  gwthread_sleep(1000000.0);
664  } else {
665  top_time = set->heap->tab[0]->elapses;
666  unlock(set);
667  gwthread_sleep(top_time - now);
668  }
669  }
670 }
void gw_timerset_destroy(Timerset *set)
Definition: gw-timer.c:190
#define mutex_unlock(m)
Definition: thread.h:136
void gwlist_append(List *list, void *item)
Definition: list.c:179
long size
Definition: gw-timer.c:85
void gwlist_produce(List *list, void *item)
Definition: list.c:411
volatile sig_atomic_t stopping
Definition: gw-timer.c:94
void gwthread_join(long thread)
#define mutex_create()
Definition: thread.h:96
static void abort_elapsed(Timer *timer)
Definition: gw-timer.c:447
List * output
Definition: gw-timer.c:128
Timer * gw_timer_create(Timerset *set, List *outputlist, void(*callback)(void *))
Definition: gw-timer.c:211
static void heap_destroy(TimerHeap *heap)
Definition: gw-timer.c:472
Timer ** tab
Definition: gw-timer.c:83
void * data
Definition: gw-timer.c:144
TimerHeap * heap
Definition: gw-timer.c:106
static void heap_insert(TimerHeap *heap, Timer *timer)
Definition: gw-timer.c:506
void gw_timer_elapsed_stop(Timer *timer)
Definition: gw-timer.c:364
static void lock(Timerset *set)
Definition: gw-timer.c:429
Timerset * gw_timerset_create(void)
Definition: gw-timer.c:177
void(* callback)(void *data)
Definition: gw-timer.c:132
static void elapse_timer(Timer *timer)
Definition: gw-timer.c:617
void * elapsed_data
Definition: gw-timer.c:151
void gw_timer_stop(Timer *timer)
Definition: gw-timer.c:344
void gwlist_remove_producer(List *list)
Definition: list.c:401
long gwlist_delete_equal(List *list, void *item)
Definition: list.c:266
void gw_timer_destroy(Timer *timer)
Definition: gw-timer.c:229
static void watch_timers(void *arg)
Definition: gw-timer.c:636
#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
Timerset * timerset
Definition: gw-timer.c:119
static void heap_swap(TimerHeap *heap, long index1, long index2)
Definition: gw-timer.c:523
double interval
Definition: fakewap.c:234
long thread
Definition: gw-timer.c:111
static TimerHeap * heap_create(void)
Definition: gw-timer.c:460
void gw_timer_elapsed_destroy(Timer *timer)
Definition: gw-timer.c:240
long elapses
Definition: gw-timer.c:138
void gw_timer_start(Timer *timer, int interval, void *data)
Definition: gw-timer.c:251
void gw_timer_elapsed_start(Timer *timer, int interval, void *data)
Definition: gw-timer.c:297
void gwthread_wakeup(long thread)
List * gw_timer_break(Timerset *set)
Definition: gw-timer.c:385
#define gwlist_create()
Definition: list.h:136
long index
Definition: gw-timer.c:157
Definition: thread.h:76
long len
Definition: gw-timer.c:84
static void unlock(Timerset *set)
Definition: gw-timer.c:435
Mutex * mutex
Definition: gw-timer.c:101
static void heap_delete(TimerHeap *heap, long index)
Definition: gw-timer.c:486
void gwlist_add_producer(List *list)
Definition: list.c:383
#define mutex_lock(m)
Definition: thread.h:130
Definition: list.c:102
static int heap_adjust(TimerHeap *heap, long index)
Definition: gw-timer.c:549
void * gw_timer_data(Timer *timer)
Definition: gw-timer.c:422
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.