1 /* ====================================================================
2 * The Kannel Software License, Version 1.0
3 *
4 * Copyright (c) 2001-2014 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 */
138 WAPEvent *event;
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 */
145 WAPEvent *elapsed_event;
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
timers_init(void)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
timers_shutdown(void)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
gwtimer_create(List * outputlist)224 Timer *gwtimer_create(List *outputlist)
225 {
226 Timer *t;
227
228 gw_assert(initialized);
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
gwtimer_destroy(Timer * timer)241 void gwtimer_destroy(Timer *timer)
242 {
243 gw_assert(initialized);
244
245 if (timer == NULL)
246 return;
247
248 gwtimer_stop(timer);
249 gwlist_remove_producer(timer->output);
250 wap_event_destroy(timer->event);
251 gw_free(timer);
252 }
253
gwtimer_start(Timer * timer,int interval,WAPEvent * event)254 void gwtimer_start(Timer *timer, int interval, WAPEvent *event)
255 {
256 int wakeup = 0;
257
258 gw_assert(initialized);
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
gwtimer_stop(Timer * timer)299 void gwtimer_stop(Timer *timer)
300 {
301 gw_assert(initialized);
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
lock(Timerset * set)320 static void lock(Timerset *set)
321 {
322 gw_assert(set != NULL);
323 mutex_lock(set->mutex);
324 }
325
unlock(Timerset * set)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 */
abort_elapsed(Timer * timer)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.",
348 wap_event_name(timer->elapsed_event->type));
349 wap_event_destroy(timer->elapsed_event);
350 }
351 timer->elapsed_event = NULL;
352 }
353
354 /*
355 * Create a new timer heap.
356 */
heap_create(void)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
heap_destroy(TimerHeap * heap)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 */
heap_delete(TimerHeap * heap,long index)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 */
heap_insert(TimerHeap * heap,Timer * timer)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 */
heap_swap(TimerHeap * heap,long index1,long index2)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 */
heap_adjust(TimerHeap * heap,long index)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 */
elapse_timer(Timer * timer)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 */
watch_timers(void * arg)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 }
566