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 * 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 {
83 Timer **tab;
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 */
101 Mutex *mutex;
102 /*
103 * Active timers are stored here in a partially ordered structure.
104 * See the definition of TimerHeap, above, for an explanation.
105 */
106 TimerHeap *heap;
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 */
119 Timerset *timerset;
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 */
128 List *output;
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 */
151 void *elapsed_data;
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
gw_timerset_create(void)177 Timerset *gw_timerset_create(void)
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
gw_timerset_destroy(Timerset * set)190 void gw_timerset_destroy(Timerset *set)
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
gw_timer_create(Timerset * set,List * outputlist,void (* callback)(void *))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
gw_timer_destroy(Timer * timer)229 void gw_timer_destroy(Timer *timer)
230 {
231 if (timer == NULL)
232 return;
233
234 gw_timer_stop(timer);
235 if (timer->output != NULL)
236 gwlist_remove_producer(timer->output);
237 gw_free(timer);
238 }
239
gw_timer_elapsed_destroy(Timer * timer)240 void gw_timer_elapsed_destroy(Timer *timer)
241 {
242 if (timer == NULL)
243 return;
244
245 gw_timer_elapsed_stop(timer);
246 if (timer->output != NULL)
247 gwlist_remove_producer(timer->output);
248 gw_free(timer);
249 }
250
gw_timer_start(Timer * timer,int interval,void * data)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)
294 gwthread_wakeup(timer->timerset->thread);
295 }
296
gw_timer_elapsed_start(Timer * timer,int interval,void * data)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)
341 gwthread_wakeup(timer->timerset->thread);
342 }
343
gw_timer_stop(Timer * timer)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
gw_timer_elapsed_stop(Timer * timer)364 void gw_timer_elapsed_stop(Timer *timer)
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
gw_timer_break(Timerset * set)385 List *gw_timer_break(Timerset *set)
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
gw_timer_data(Timer * timer)422 void *gw_timer_data(Timer *timer)
423 {
424 gw_assert(timer != NULL);
425
426 return timer->data;
427 }
428
lock(Timerset * set)429 static void lock(Timerset *set)
430 {
431 gw_assert(set != NULL);
432 mutex_lock(set->mutex);
433 }
434
unlock(Timerset * set)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 */
abort_elapsed(Timer * timer)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 */
heap_create(void)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
heap_destroy(TimerHeap * heap)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 */
heap_delete(TimerHeap * heap,long index)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 */
heap_insert(TimerHeap * heap,Timer * timer)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 */
heap_swap(TimerHeap * heap,long index1,long index2)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 */
heap_adjust(TimerHeap * heap,long index)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 */
elapse_timer(Timer * timer)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 */
watch_timers(void * arg)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 }
671