New timer interface:
authorAndrei Pelinescu-Onciul <andrei@iptel.org>
Mon, 5 Dec 2005 18:29:30 +0000 (18:29 +0000)
committerAndrei Pelinescu-Onciul <andrei@iptel.org>
Mon, 5 Dec 2005 18:29:30 +0000 (18:29 +0000)
  - allows adding timers dynamically
  - supports one shot and periodic timers
  - precise
  - allows timeouts < 0.5 s (depends on the config., by default min. timeout
    = 62.5 ms)
  - based on a 3 level hierarchical timing wheel
  - very fast
  - low overhead for timer functions (most of the time, the excetion is
    timer_del which  take can take quite a long time in special situations)
  - supports "slow" timers (compile option, by default on), "slow" timer = a
    timer handler which is declared as possible taking a long timer to execute.
  - backward compatible: old timer functions are preserverd => no changes
    needed for the existing code (although migration to the new interface is
    recommended)
For more information read doc/timers.txt.
tm timer update will follow shortly (this week).

14 files changed:
Makefile.defs
clist.h [new file with mode: 0644]
config.h
doc/timers.txt [new file with mode: 0644]
error.c
globals.h
main.c
pt.h
signals.c [new file with mode: 0644]
signals.h [new file with mode: 0644]
timer.c
timer.h
timer_funcs.h [new file with mode: 0644]
version.h

index cd50f1b..f37728f 100644 (file)
@@ -61,7 +61,7 @@ MAIN_NAME=ser
 VERSION = 0
 PATCHLEVEL = 10
 SUBLEVEL =   99
-EXTRAVERSION = -dev24
+EXTRAVERSION = -dev25-timers
 
 RELEASE=$(VERSION).$(PATCHLEVEL).$(SUBLEVEL)$(EXTRAVERSION)
 OS = $(shell uname -s | sed -e s/SunOS/solaris/ | tr "[A-Z]" "[a-z]")
diff --git a/clist.h b/clist.h
new file mode 100644 (file)
index 0000000..c1863cb
--- /dev/null
+++ b/clist.h
@@ -0,0 +1,111 @@
+/*
+ * $Id$
+ *
+ * circular list maintenance macros
+ *
+ * Copyright (C) 2005 iptelorg GmbH
+ *
+ * This file is part of ser, a free SIP server.
+ *
+ * ser is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version
+ *
+ * For a license to use the ser software under conditions
+ * other than those described here, or to purchase support for this
+ * software, please contact iptel.org by e-mail at the following addresses:
+ *    info@iptel.org
+ *
+ * ser is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License 
+ * along with this program; if not, write to the Free Software 
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+/* History:
+ * --------
+ *  2005-08-08  created by andrei
+ */
+
+#ifndef _clist_h
+#define _clist_h
+
+/* circular list */
+#define clist_init(c, next, prev) \
+       do{ \
+               (c)->next=(void*)(c); \
+               (c)->prev=(void*)(c); \
+       } while(0)
+
+
+
+/* adds an entire sublist { s,e } (including s & e )
+ * after head
+ */
+#define clist_insert_sublist(head, s, e, next, prev) \
+       do{ \
+               (s)->prev=(head); \
+               (e)->next=(head)->next; \
+               (e)->next->prev=(e); \
+               (head)->next=s;   \
+       }while(0)
+
+
+
+/* appends an entire sublist { s,e } (including s & e )
+ * at the end of the list
+ */
+#define clist_append_sublist(head, s, e, next, prev) \
+       do{ \
+               (s)->prev=(head)->prev; \
+               (e)->next=(void*)(head); \
+               (s)->prev->next=(s); \
+               (head)->prev=(e);   \
+       }while(0)
+
+
+
+/* remove sublist { s,e } (including s & e )
+ * always, if start is the beginning of the list use
+ * clist_rm_sublist(head->next, e, next, prev ) */
+#define clist_rm_sublist(s, e, next, prev) \
+       do{\
+               (s)->prev->next=(e)->next;  \
+               (e)->next->prev=(s)->prev ; \
+       }while(0)
+
+
+
+/* insert after (head) */
+#define clist_insert(head, c, next, prev) \
+       clist_insert_sublist(head, c, c, next, prev)
+
+
+
+/* append at the end of the list (head->prev) */
+#define clist_append(head, c, next, prev) \
+       clist_append_sublist(head, c, c, next, prev)
+
+
+
+/* remove and element */
+#define clist_rm(c, next, prev) \
+       clist_rm_sublist(c, c, next, prev)
+
+
+
+/* iterate on a clist */
+#define clist_foreach(head, v, dir) \
+       for((v)=(head)->dir; (v)!=(void*)(head); (v)=(v)->dir)
+
+/* iterate on a clist, safe version (requires an extra bak. var)
+ * (it allows removing of the current element) */
+#define clist_foreach_safe(head, v, bak,  dir) \
+       for((v)=(head)->dir, (bak)=(v)->dir; (v)!=(void*)(head); \
+                               (v)=(bak), (bak)=(v)->dir)
+#endif
index 7039e09..da5ee64 100644 (file)
--- a/config.h
+++ b/config.h
 /*used if SH_MEM is defined*/
 #define SHM_MEM_SIZE 32
 
-#define TIMER_TICK 1
 
 /* dimensioning buckets in q_malloc */
 /* size of the size2bucket table; everything beyond that asks for
diff --git a/doc/timers.txt b/doc/timers.txt
new file mode 100644 (file)
index 0000000..b522da6
--- /dev/null
@@ -0,0 +1,174 @@
+# $Id$
+#
+# History:
+# --------
+# 2005-11-30    created by andrei
+
+
+New timer interface
+
+
+1. Introduction
+---------------
+
+ ser's new timer interface is based on a 3 level hierarchical timing wheel
+(see [1]). Most timeouts will go in the first "wheel" (all timeouts < 1<<14 
+ ticks, which by default mean 1024 s). Each wheel acts as a circular buffer.
+ The big advantage of this scheme is that most of the time you just run all the timer handlers from the current entry in the first wheel (no comparisons necessary). Each 2^14 ticks, all the timers in the second wheel's current entry are redistributed and each 2^23 ticks all the timers in the third wheel's current entry are redistributed.
+
+ The new timer interfaces allows adding timers dynamically, supports one shot
+ and periodic timers, is precise and fast (very low overhead) and supports
+"fast" and "slow" timers. For now it uses setitimer to "generate" the ticks and form time to time it re-adjusts them based on the real system time.
+
+
+[1] - G. Varghese, T. Lauck,  Hashed and Hierarchical Timing Wheels: Efficient
+      Data Structures for Implementing a Timer Facility, 1996
+
+
+2. include files
+-----------------
+
+All the public functions are defined in timer.h. timer_ticks.h contains
+ ticks conversion related macros (ticks to seconds, ms or viceversa).
+
+
+3. Example usage
+----------------
+
+#include "../../timer.h"
+#include "../../timer_ticks.h"
+
+/* simple periodic timer handler */
+static ticks_t timer_h(ticks_t ticks, struct timer_ln* tl, void* data)
+{
+       DBG("timer habdler called at %d ticks, foo is %d \n", ticks, *(int*)data);
+       return (ticks_t)(-1); /* periodical */
+}
+
+struct timer_ln *t;
+int foo;
+
+t=timer_alloc();
+if (t==0)
+       goto error;
+timer_init(t, timer_handle, &foo, 0);
+foo=0;
+timer_add(t, MS_TO_TICKS(1500)); /* start it after 1500ms */
+/* ....  */
+/* remove it and change the period to 2 s */
+timer_del(t);
+timer_reinit(t); /* without init or reinit timer_add will refuse to re-add it*/
+timer_add(t, S_TO_TICKS(2));
+/* .... */
+/* remove it at the end (optional) */
+timer_del(t);
+timer_free(t);
+
+
+4. Notes
+---------
+
+4.1 alloc & init
+----------------
+
+To use a timer you need a timer_ln structure. This structure must be stored
+ in shared memory.
+You can either use timer_alloc() which will return a pointer to a shared memory allocated timer_ln structure or you can "attach" timer_ln as a member to one
+ of your structures which is already stored in the shared memory.
+
+The timer_ln structure must be always initialized. Use the timer_init(...) macro for this. To the timer_init macro takes as parameters a pointer to the timer_ln structure, a pointer to a timer_handler_f function, a void* parameter for this
+ function and some timer flags.
+Example:
+
+struct foo{
+       int bar;
+       struct timer_ln timer;
+};
+
+struct foo* f;
+f=shm_malloc(sizeof(struct foo));
+
+time_init(&f->timer, timer_handle, &f->bar, 0);
+
+
+The timer flags can be either 0 (if it's a "slow" timer) or F_TIMER_FAST if
+ this is a "fast" timer.
+A "fast" timer is a timer that does very little work in its timer handler (it always exits fast). You should use a "slow" timer if you don't care so much if your timer call is a little bit delayed or if you do  dns lookups, query databases, blocking sends/writes. If you don't know which one to choose, choose "slow".
+
+
+4.2 timer handlers
+------------------
+
+The timer handler can be periodic, one shot or it can change from call to call. It all depends on what value you return from it. If you always return (ticks_t)(-1) or timer_ln->initial_timeout you have a periodic timer. If you return 0 you have an one shot timer (the timer will be removed when your timer handler function exits). For any other value v, your timer will be automatically re-added with the next expire set to v (expressed in ticks).
+
+4.3 timer_add
+-------------
+
+The timer becomes active after you add it with timer_add. timer_add takes as parameters a pointer to the corresponding timer_ln structure and an expire interval (in ticks, use the macros from timer_ticks.h to convert from s/ms).
+The timer must be intialized (with timer_init()) before adding it the first time.
+If you want to re-add a deleted timer (timer_del was called on it) or an expired one shot timer (the timer handlers returned 0 on the last run), you have to re-init it first, either by calling timer_reinit(t) or by calling again timer_init(...). If you don't re-initialize the timer, timer_add will refuse to add it and it will return -1. So if timer_add returns error (-1) it means that either you're trying to re-add a running timer or a deleted/expired timer that was not re-initialized.
+WARNING: do not initialize/re-initialize a running timer!
+
+4.4 timer_del
+-------------
+
+To remove a timer from the active timer list call timer_del(struct timer_ln*).
+timer_del is the slowest of all the timer functions. If you are trying to delete a timer whose timer is executing. timer_del will wait until it finishes.
+WARNING: if you have an one shot timer that frees its memory before exiting, make sure you don't call timer_del afterwards (e.g. use some reference counters and free the memory only if the counter is 0).
+
+Race example (using the struct foo defined above):
+
+/* simple one shot timer handler */
+static ticks_t timer_h(ticks_t ticks, struct timer_ln* tl, void* data)
+{
+       
+       /* free the mem. */
+       shm_free(data);
+       return 0;
+}
+
+struct foo* f;
+f=shm_malloc(sizeof(struct foo));
+
+time_init(&f->timer, timer_handle, f, 0);
+timer_add(&f->timer, rand());
+/* ... */
+/* random amount of time spent doing other things */
+timer_del(&f->timer); /* if the timer is already expired => f is already
+                         deleted => problems */
+
+The above timer_del/free_in_one_shot_timer race example is very simple, but consider that you can have much more complex scenarios, when timer_del can be called from different processes on some asynchronous events. If this looks like you're intended usage, make sure you use some  reference counters or some other protection mechanism to avoid the above race.
+
+
+4.5 Getting the ticks value
+----------------------------
+
+If you need the current ticks value you can get with get_ticks_raw().
+WARNING: don't use get_ticks(). get_ticks() returns the number of ticks converted to seconds and it was kept only for compatibility reasons with the existing code.
+
+4.6 Conversion
+---------------
+
+To convert between ticks & time and viceversa, include timer_ticks.h and use
+one of the following macros:
+
+MS_TO_TICKS(ms) /* converts from milliseconds to ticks, rounds up */
+S_TO_TICKS(s)   /* convert from seconds to ticks */
+TICKS_TO_MS(t)  /* converts from ticks to milliseconds, can overflow for
+                   very large values (use long long and
+                   TICKS_TO_MS((long long)t) to try to avoid it if you know
+                   that you'll deal with such large values */
+TICKS_TO_S(t)  /* converts from ticks to s, rounded down */
+
+
+4.7 Backward compatibility
+--------------------------
+
+The old  register_timer and get_ticks() are still supported for backward compatibility. This means that you don't have to change your existing working code.
+
+
+
+[Todo]:
+- SLOW, DRIFT, RESYNC, FREQUENCY
+
+
diff --git a/error.c b/error.c
index 4cb9136..266d5a9 100644 (file)
--- a/error.c
+++ b/error.c
@@ -109,7 +109,7 @@ int err2reason_phrase(
 
                case E_OUT_OF_MEM:
                /* dont disclose lack of mem in release mode */
-#ifdef DEBUG
+#ifdef EXTRA_DEBUG
                        error_txt="Excuse me I ran out of memory";
                        *sip_error=500;
                        break;
index e494f05..57938a8 100644 (file)
--- a/globals.h
+++ b/globals.h
@@ -150,6 +150,9 @@ extern int is_main;
 /* debugging level for dumping memory status */
 extern int memlog;
 
+/* debugging level for timer debugging (see -DTIMER_DEBUG) */
+extern int timerlog;
+
 /* looking up outbound interface ? */
 extern int mhomed;
 
diff --git a/main.c b/main.c
index 21e9c0f..b85b73c 100644 (file)
--- a/main.c
+++ b/main.c
 #include "pt.h"
 #include "script_cb.h"
 #include "ut.h"
+#include "signals.h"
 #ifdef USE_TCP
 #include "poll_types.h"
 #include "tcp_init.h"
@@ -255,6 +256,8 @@ int check_via =  0;
 int syn_branch = 1;
 /* debugging level for memory stats */
 int memlog = L_DBG;
+/* debugging level for timer debugging */
+int timerlog = L_WARN;
 /* should replies include extensive warnings? by default yes,
    good for trouble-shooting
 */
@@ -424,28 +427,6 @@ static void kill_all_children(int signum)
 
 
 
-#ifdef USE_SIGACTION
-static void (*set_sig_h(int sig, void (*handler) (int) ))(int)
-{
-       struct sigaction act;
-       struct sigaction old;
-       
-       memset(&act, 0, sizeof(act));
-       act.sa_handler=handler;
-       /*
-       sigemptyset(&act.sa_mask);
-       act.sa_flags=0;
-       */
-       LOG(L_CRIT, "setting signal %d to %p\n", sig, handler);
-       /* sa_sigaction not set, we use sa_hanlder instead */ 
-       return (sigaction (sig, &act, &old)==-1)?SIG_ERR:old.sa_handler;
-}
-#else
-#define set_sig_h signal
-#endif
-
-
-
 /* if this handler is called, a critical timeout has occured while
  * waiting for the children to finish => we should kill everything and exit */
 static void sig_alarm_kill(int signo)
@@ -842,7 +823,7 @@ int main_loop()
 #ifdef USE_TCP
        int sockfd[2];
 #endif
-#ifdef DEBUG
+#ifdef EXTRA_DEBUG
        int r;
 #endif
 
@@ -884,23 +865,38 @@ int main_loop()
                   as new processes are forked (while skipping 0 reserved for main 
                */
 
-               /* we need another process to act as the timer*/
-#ifdef USE_TCP
-               /* if we are using tcp we always need a timer process,
-                * we cannot count on select timeout to measure time
-                * (it works only on linux)
-                */
-               if ((!tcp_disable)||(timer_list))
-#else
-               if (timer_list)
+#ifdef USE_SLOW_TIMER
+               /* we need another process to act as the "slow" timer*/
+                               process_no++;
+                               if ((pid=fork())<0){
+                                       LOG(L_CRIT,  "ERROR: main_loop: Cannot fork\n");
+                                       goto error;
+                               }
+                               if (pid==0){
+                                       /* child */
+                                       pt[process_no].pid=getpid();
+                                       /* timer!*/
+                                       /* process_bit = 0; */
+                                       if (init_child(PROC_TIMER) < 0) {
+                                               LOG(L_ERR, "slow timer: init_child failed\n");
+                                               goto error;
+                                       }
+                                       
+                                       if (arm_slow_timer()<0) goto error;
+                                       slow_timer_main();
+                               }else{
+                                       pt[process_no].pid=pid; /*should be shared mem anyway*/
+                                       strncpy(pt[process_no].desc, "slow timer", MAX_PT_DESC );
+                                       slow_timer_pid=pid;
+                                       
+                               }
 #endif
-               {
+                               /* we need another process to act as the "main" timer*/
                                process_no++;
                                if ((pid=fork())<0){
                                        LOG(L_CRIT,  "ERROR: main_loop: Cannot fork\n");
                                        goto error;
                                }
-                               
                                if (pid==0){
                                        /* child */
                                        /* record pid twice to avoid the child using it, before
@@ -912,15 +908,13 @@ int main_loop()
                                                LOG(L_ERR, "timer: init_child failed\n");
                                                goto error;
                                        }
-                                       for(;;){
-                                               sleep(TIMER_TICK);
-                                               timer_ticker();
-                                       }
+                                       
+                                       if (arm_timer()<0) goto error;
+                                       timer_main();
                                }else{
                                                pt[process_no].pid=pid; /*should be shared mem anyway*/
                                                strncpy(pt[process_no].desc, "timer", MAX_PT_DESC );
                                }
-               }
 
                /* if configured, start a server for accepting FIFO commands,
                 * we need to do it after all the sockets are initialized, to 
@@ -1101,13 +1095,55 @@ int main_loop()
        bind_address=0;                         /* main proc -> it shouldn't send anything, */
        
 
+       {
+#ifdef USE_SLOW_TIMER
 #ifdef USE_TCP
-       /* if we are using tcp we always need the timer */
-       if ((!tcp_disable)||(timer_list))
-#else
-       if (timer_list)
+               if (!tcp_disable){
+                       if (socketpair(AF_UNIX, SOCK_STREAM, 0, sockfd)<0){
+                               LOG(L_ERR, "ERROR: main_loop: socketpair failed: %s\n",
+                                       strerror(errno));
+                               goto error;
+                       }
+               }
 #endif
-       {
+               /* fork again for the "slow" timer process*/
+               process_no++;
+               if ((pid=fork())<0){
+                       LOG(L_CRIT, "main_loop: cannot fork \"slow\" timer process\n");
+                       goto error;
+               }else if (pid==0){
+                       /* child */
+                       /* is_main=0; */
+#ifdef USE_TCP
+                       if (!tcp_disable){
+                               close(sockfd[0]);
+                               unix_tcp_sock=sockfd[1];
+                       }
+#endif
+                       /* record pid twice to avoid the child using it, before
+                        * parent gets a chance to set it*/
+                       pt[process_no].pid=getpid();
+                       if (init_child(PROC_TIMER) < 0) {
+                               LOG(L_ERR, "slow timer: init_child failed\n");
+                               goto error;
+                       }
+                       if (arm_slow_timer()<0) goto error;
+                       slow_timer_main();
+               }else{
+                       pt[process_no].pid=pid;
+                       strncpy(pt[process_no].desc, "slow timer", MAX_PT_DESC );
+                       slow_timer_pid=pid;
+#ifdef USE_TCP
+                       if(!tcp_disable){
+                                               close(sockfd[1]);
+                                               pt[process_no].unix_sock=sockfd[0];
+                                               pt[process_no].idx=-1; /* this is not a "tcp" process*/
+                       }
+#endif
+               }
+#endif /* USE_SLOW_TIMER */
+       
+               /* fork again for the "main" timer process*/
 #ifdef USE_TCP
                if (!tcp_disable){
                        if (socketpair(AF_UNIX, SOCK_STREAM, 0, sockfd)<0){
@@ -1117,7 +1153,6 @@ int main_loop()
                        }
                }
 #endif
-               /* fork again for the attendant process*/
                process_no++;
                if ((pid=fork())<0){
                        LOG(L_CRIT, "main_loop: cannot fork timer process\n");
@@ -1138,14 +1173,8 @@ int main_loop()
                                LOG(L_ERR, "timer: init_child failed\n");
                                goto error;
                        }
-                       
-                       for(;;){
-                               /* debug:  instead of doing something useful */
-                               /* (placeholder for timers, etc.) */
-                               sleep(TIMER_TICK);
-                               /* if we received a signal => TIMER_TICK may have not elapsed*/
-                               timer_ticker();
-                       }
+                       if (arm_timer()<0) goto error;
+                       timer_main();
                }else{
                        pt[process_no].pid=pid;
                        strncpy(pt[process_no].desc, "timer", MAX_PT_DESC );
@@ -1198,11 +1227,14 @@ int main_loop()
        }
 #endif
        /*DEBUG- remove it*/
-#ifdef DEBUG
+#ifdef EXTRA_DEBUG
        fprintf(stderr, "\n% 3d processes (%3d), % 3d children * "
                        "listening addresses + tcp listeners + tls listeners"
-                       "+ main + fifo %s\n", process_no+1, process_count(), children_no,
-                       (timer_list)?"+ timer":"");
+                       "+ main + fifo + timer"
+# ifdef USE_SLOW_TIMER
+                       " + slow_timer"
+# endif
+                       "\n", process_no+1, process_count(), children_no);
        for (r=0; r<=process_no; r++){
                fprintf(stderr, "% 3d   % 5d - %s\n", r, pt[r].pid, pt[r].desc);
        }
diff --git a/pt.h b/pt.h
index 797021c..22f9e6e 100644 (file)
--- a/pt.h
+++ b/pt.h
@@ -74,6 +74,9 @@ inline static int process_count()
                /* timer process */
                + 1 /* always, we need it in most cases, and we can't tell here
                           & now if we don't need it */
+#ifdef USE_SLOW_TIMER
+               + 1 /* slow timer process */
+#endif
                /* fifo server */
                +((fifo==NULL || strlen(fifo)==0) ? 0 : 1 )
                /* unixsock server*/
diff --git a/signals.c b/signals.c
new file mode 100644 (file)
index 0000000..b4fc589
--- /dev/null
+++ b/signals.c
@@ -0,0 +1,54 @@
+/*
+ * $Id$
+ *
+ * Copyright (C) 2001-2003 FhG Fokus
+ *
+  * This file is part of ser, a free SIP server.
+ *
+ * ser is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version
+ *
+ * For a license to use the ser software under conditions
+ * other than those described here, or to purchase support for this
+ * software, please contact iptel.org by e-mail at the following addresses:
+ *    info@iptel.org
+ *
+ * ser is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License 
+ * along with this program; if not, write to the Free Software 
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/*
+ * Handle the signals
+ *
+ * History:
+ * --------
+ *  2005-10-05  split from main.c  (andrei)
+ */
+
+#include "signals.h"
+#include <signal.h>
+
+#ifdef USE_SIGACTION
+void (*set_sig_h(int sig, void (*handler) (int) ))(int)
+{
+       struct sigaction act;
+       struct sigaction old;
+       
+       memset(&act, 0, sizeof(act));
+       act.sa_handler=handler;
+       /*
+       sigemptyset(&act.sa_mask);
+       act.sa_flags=0;
+       */
+       LOG(L_CRIT, "setting signal %d to %p\n", sig, handler);
+       /* sa_sigaction not set, we use sa_hanlder instead */ 
+       return (sigaction (sig, &act, &old)==-1)?SIG_ERR:old.sa_handler;
+}
+#endif
diff --git a/signals.h b/signals.h
new file mode 100644 (file)
index 0000000..50af843
--- /dev/null
+++ b/signals.h
@@ -0,0 +1,46 @@
+/*
+ * $Id$
+ *
+ * Copyright (C) 2001-2003 FhG Fokus
+ *
+ * This file is part of ser, a free SIP server.
+ *
+ * ser is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version
+ *
+ * For a license to use the ser software under conditions
+ * other than those described here, or to purchase support for this
+ * software, please contact iptel.org by e-mail at the following addresses:
+ *    info@iptel.org
+ *
+ * ser is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License 
+ * along with this program; if not, write to the Free Software 
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/*
+ * Handle the signals
+ *
+ * History:
+ * --------
+ *  2005-10-05  split from main.c  (andrei)
+ */
+
+
+#ifndef _signals_h
+#define _signals_h
+
+#ifdef USE_SIGACTION
+void (*set_sig_h(int sig, void (*handler) (int) ))(int);
+#else
+#define set_sig_h signal
+#endif
+
+
+#endif
diff --git a/timer.c b/timer.c
index 8f7e3f3..711790c 100644 (file)
--- a/timer.c
+++ b/timer.c
  * --------
  *  2003-03-19  replaced all the mallocs/frees w/ pkg_malloc/pkg_free (andrei)
  *  2003-03-29  cleaning pkg_mallocs introduced (jiri)
+ *  2005-07-27  complete re-design/re-implementation (andrei)
  */
 
 
 #include "timer.h"
+#include "timer_funcs.h"
+#include "timer_ticks.h"
 #include "dprint.h"
+#include <time.h>     /* gettimeofday */
+#include <sys/time.h> /* setitimer, gettimeofday */
+#include <signal.h>   /* SIGALRM */
+#include <errno.h>
+#include <unistd.h> /* pause() */
+#include <stdlib.h> /* random, debugging only */
 #include "error.h"
+#include "signals.h"
+/*
 #include "config.h"
+*/
+#include "globals.h"
 #include "mem/mem.h"
 #ifdef SHM_MEM
 #include "mem/shm_mem.h"
 #endif
+#include "locking.h"
+
+
+
 
-#include <stdlib.h>
+/* how often will the timer handler be called (in ticks) */
+#define TIMER_HANDLER_INTERVAL 1U
+/* how often to try to re-adjust the ticks */
+#define TIMER_RESYNC_TICKS     (TIMER_TICKS_HZ*5U)  /* each 5 s */
+#define TIMER_MAX_DRIFT        (TIMER_TICKS_HZ/10U) /* if drift > 0.1s adjust */
 
 
-struct sr_timer* timer_list=0;
 
-static int* jiffies=0;
+static ticks_t* ticks=0;
+static ticks_t last_ticks; /* last time we adjusted the time */
+static ticks_t last_adj_check; /* last time we ran adjust_ticks */
+static ticks_t prev_ticks; /* last time we ran the timer, also used as
+                                                         "current" ticks when running the timer for
+                                                         "skipped" ticks */
+
+static struct timeval last_time;
+static struct timeval start_time; /* for debugging */
+
+static volatile int run_timer=0;
 static int timer_id=0;
 
+static gen_lock_t* timer_lock=0;
+static struct timer_ln* volatile* running_timer=0;/* running timer handler */
+
+#define LOCK_TIMER_LIST()              lock_get(timer_lock)
+#define UNLOCK_TIMER_LIST()            lock_release(timer_lock)
+
+/* we can get away without atomic_set/atomic_cmp and write barriers because we
+ * always call SET_RUNNING and IS_RUNNING while holding the timer lock
+ * => it's implicitly atomic and the lock acts as write barrier */
+#define SET_RUNNING(t)         (*running_timer=(t))
+#define IS_RUNNING(t)          (*running_timer==(t))
+#define UNSET_RUNNING()                (*running_timer=0)
+
+#ifdef USE_SLOW_TIMER
+
+#define SLOW_TIMER_SIG SIGUSR2
+/* timer flags checks */
+#define IS_FAST_TIMER(t)       (t->flags&F_TIMER_FAST)
+#define SET_SLOW_LIST(t)       (t->flags|=F_TIMER_ON_SLOW_LIST)
+#define RESET_SLOW_LIST(t)     (t->flags&=~F_TIMER_ON_SLOW_LIST)
+#define IS_ON_SLOW_LIST(t)     (t->flags&F_TIMER_ON_SLOW_LIST)
+
+#define SLOW_LISTS_NO  1024U  /* slow lists number, 2^k recommended */
+
+
+static gen_lock_t*  slow_timer_lock; /* slow timer lock */
+static struct timer_head* slow_timer_lists; 
+static volatile unsigned short* t_idx; /* "main" timer index in slow_lists[] */
+static volatile unsigned short* s_idx; /* "slow" timer index in slow_lists[] */
+static struct timer_ln* volatile* running_timer2=0; /* timer handler running
+                                                                                                            in the "slow" timer */
+static sigset_t slow_timer_sset;
+pid_t slow_timer_pid;
+#define SET_RUNNING_SLOW(t)            (*running_timer2=(t))
+#define IS_RUNNING_SLOW(t)             (*running_timer2==(t))
+#define UNSET_RUNNING_SLOW()   (*running_timer2=0)
+
+#define LOCK_SLOW_TIMER_LIST()         lock_get(slow_timer_lock)
+#define UNLOCK_SLOW_TIMER_LIST()       lock_release(slow_timer_lock)
+
+
+#endif
+
+
+struct timer_lists* timer_lst=0;
+
+void sig_timer(int signo)
+{
+       (*ticks)++;
+       if (( *ticks % TIMER_HANDLER_INTERVAL)==0){
+               /* set a flag to run the handler */
+               run_timer=1;
+       }
+}
+
+
+
+void destroy_timer()
+{
+       struct itimerval it;
+       
+       /* disable timer */
+       memset(&it, 0, sizeof(it));
+       setitimer(ITIMER_REAL, &it, 0); 
+       set_sig_h(SIGALRM, SIG_IGN);
+       if (timer_lock){
+               lock_destroy(timer_lock);
+               lock_dealloc(timer_lock);
+               timer_lock=0;
+       }
+       if (ticks){
+#ifdef SHM_MEM
+               shm_free(ticks);
+#else
+               pkg_free(ticks);
+#endif
+               ticks=0;
+       }
+       if (timer_lst){
+#ifdef SHM_MEM
+               shm_free(timer_lst);
+#else
+               pkg_free(timer_lst);
+#endif
+               timer_lst=0;
+       }
+       if (running_timer){
+               shm_free((void*)running_timer);
+               running_timer=0;
+       }
+#ifdef USE_SLOW_TIMER
+       if (slow_timer_lock){
+               lock_destroy(slow_timer_lock);
+               lock_dealloc(slow_timer_lock);
+               slow_timer_lock=0;
+       }
+       if (slow_timer_lists){
+               shm_free((void*)slow_timer_lists);
+               slow_timer_lists=0;
+       }
+       if (t_idx){
+               shm_free((void*)t_idx);
+               t_idx=0;
+       }
+       if (s_idx){
+               shm_free((void*)s_idx);
+               s_idx=0;
+       }
+       if(running_timer2){
+               shm_free((void*)running_timer2);
+               running_timer2=0;
+       }
+#endif
+}
+
 
 
 /* ret 0 on success, <0 on error*/
 int init_timer()
 {
+       int r;
+       int ret;
+       
+       ret=-1;
+       
+       /* init the locks */
+       timer_lock=lock_alloc();
+       if (timer_lock==0){
+               ret=E_OUT_OF_MEM;
+               goto error;
+       }
+       if (lock_init(timer_lock)==0){
+               lock_dealloc(timer_lock);
+               timer_lock=0;
+               ret=-1;
+               goto error;
+       }
+       /* init the shared structs */
 #ifdef SHM_MEM
-       jiffies=shm_malloc(sizeof(int));
+       ticks=shm_malloc(sizeof(ticks_t));
+       timer_lst=shm_malloc(sizeof(struct timer_lists));
 #else
        /* in this case get_ticks won't work! */
        LOG(L_INFO, "WARNING: no shared memory support compiled in"
                                " get_ticks won't work\n");
-       jiffies=pkg_malloc(sizeof(int));
+       ticks=pkg_malloc(sizeof(ticks_t));
+       timer_lst=pkg_malloc(sizeof(struct timer_lists));
 #endif
-       if (jiffies==0){
-               LOG(L_CRIT, "ERROR: init_timer: could not init jiffies\n");
-               return E_OUT_OF_MEM;
+       if (ticks==0){
+               LOG(L_CRIT, "ERROR: init_timer: out of shared memory (ticks)\n");
+               ret=E_OUT_OF_MEM;
+               goto error;
        }
-       *jiffies=0;
+       if (timer_lst==0){
+               LOG(L_CRIT, "ERROR: init_timer: out of shared memory (timer_lst)\n");
+               ret=E_OUT_OF_MEM;
+               goto error;
+       }
+       running_timer=shm_malloc(sizeof(struct timer_ln*));
+       if (running_timer==0){
+               LOG(L_CRIT, "ERROR: init_timer: out of memory (running_timer)\n");
+               ret=E_OUT_OF_MEM;
+               goto error;
+       }
+
+       /* initial values */
+       memset(timer_lst, 0, sizeof(struct timer_lists));
+       *ticks=random(); /* random value for start, for debugging */
+       prev_ticks=last_ticks=last_adj_check=*ticks;
+       *running_timer=0;
+       if (gettimeofday(&start_time, 0)<0){
+               LOG(L_ERR, "ERROR: init_timer: gettimeofday failed: %s [%d]\n",
+                               strerror(errno), errno);
+               ret=-1;
+               goto error;
+       }
+       last_time=start_time;
+       DBG("init_timer: starting with *ticks=%u\n", (unsigned) *ticks);
+       
+       /* init timer structures */
+       for (r=0; r<H0_ENTRIES; r++)
+               _timer_init_list(&timer_lst->h0[r]);
+       for (r=0; r<H1_ENTRIES; r++)
+               _timer_init_list(&timer_lst->h1[r]);
+       for (r=0; r<H2_ENTRIES; r++)
+               _timer_init_list(&timer_lst->h2[r]);
+       _timer_init_list(&timer_lst->expired);
+       
+#ifdef USE_SLOW_TIMER
+       
+       /* init the locks */
+       slow_timer_lock=lock_alloc();
+       if (slow_timer_lock==0){
+               ret=E_OUT_OF_MEM;
+               goto error;
+       }
+       if (lock_init(slow_timer_lock)==0){
+               lock_dealloc(slow_timer_lock);
+               slow_timer_lock=0;
+               ret=-1;
+               goto error;
+       }
+       t_idx=shm_malloc(sizeof(*t_idx));
+       s_idx=shm_malloc(sizeof(*s_idx));
+       slow_timer_lists=shm_malloc(sizeof(struct timer_head)*SLOW_LISTS_NO);
+       running_timer2=shm_malloc(sizeof(struct timer_ln*));
+       if ((t_idx==0)||(s_idx==0) || (slow_timer_lists==0) ||(running_timer2==0)){
+               LOG(L_ERR, "ERROR: init_timer: out of shared memory (slow)\n");
+               ret=E_OUT_OF_MEM;
+               goto error;
+       }
+       *t_idx=*s_idx=0;
+       *running_timer2=0;
+       for (r=0; r<SLOW_LISTS_NO; r++)
+               _timer_init_list(&slow_timer_lists[r]);
+       
+#endif
+       
+       DBG("init_timer: timer_list between %p and %p\n",
+                       &timer_lst->h0[0], &timer_lst->h2[H2_ENTRIES]);
        return 0;
+error:
+       destroy_timer();
+       return ret;
 }
 
 
 
-void destroy_timer()
+#ifdef USE_SLOW_TIMER
+/* arm the "slow" timer ( start it) 
+ * returns -1 on error
+ * WARNING: use it in the same process as the timer
+ *  (the one using pause(); timer_handler()) or
+ *  change run_timer to a pointer in shared mem */
+int arm_slow_timer()
 {
-       struct sr_timer* t, *foo;
+       sigemptyset(&slow_timer_sset);
+       sigaddset(&slow_timer_sset, SLOW_TIMER_SIG);
+again:
+       if (sigprocmask(SIG_BLOCK, &slow_timer_sset, 0)==-1){
+               if (errno==EINTR) goto again;
+               LOG(L_ERR, "ERROR: arm_slow_timer: sigprocmask failed: %s [%d]}n",
+                               strerror(errno), errno);
+               goto error;
+       }
+       return 0;
+error:
+       return -1;
+}
+#endif
 
-       if (jiffies){
-#ifdef SHM_MEM
-               shm_free(jiffies); jiffies=0;
+
+
+
+/* arm the timer ( start it) 
+ * returns -1 on error
+ * WARNING: use it in the same process as the timer
+ *  (the one using pause(); timer_handler()) or
+ *  change run_timer to a pointer in shared mem */
+int arm_timer()
+{
+       struct itimerval it;
+       /* init signal generation */
+       it.it_interval.tv_sec=0;
+       it.it_interval.tv_usec=1000000/TIMER_TICKS_HZ;
+       it.it_value=it.it_interval;
+       /* install the signal handler */
+       if (set_sig_h(SIGALRM, sig_timer) == SIG_ERR ){
+               LOG(L_CRIT, "ERROR: init_timer: the SIGALRM signal handler cannot"
+                                       " be installed: %s [%d]\n", strerror(errno), errno);
+               return -1;
+       }
+       if (setitimer(ITIMER_REAL, &it, 0) == -1){
+               LOG(L_CRIT, "ERROR: init_timer: setitimer failed: %s [%d]\n",
+                                       strerror(errno), errno);
+               return -1;
+       }
+       if (gettimeofday(&last_time, 0)<0){
+               LOG(L_ERR, "ERROR: arm_timer: gettimeofday failed: %s [%d]\n",
+                               strerror(errno), errno);
+               return -1;
+       }
+       return 0;
+}
+
+
+
+/* adjust the timer using the "real" time, each TIMER_RESYNC_TICKS, but only
+ * if timer drift > TIMER_MAX_DRIFT
+ * NOTES: - it will adjust time within  TIMER_MAX_DRIFT from the "real"
+ *          elapsed time
+ *        - it will never decrease the *ticks, only increase it (monotonic)
+ *        - it works ok as long as the adjustment interval < MAX_TICKS_T
+ * -- andrei
+ */
+inline static void adjust_ticks()
+{
+       struct timeval crt_time;
+       long long diff_time;
+       ticks_t diff_time_ticks;
+       ticks_t diff_ticks_raw;
+       s_ticks_t delta;
+       
+       /* fix ticks if necessary */
+       if ((*ticks-last_adj_check)>=(ticks_t)TIMER_RESYNC_TICKS){
+               last_adj_check=*ticks;
+               if (gettimeofday(&crt_time, 0)<0){
+                       LOG(L_ERR, "ERROR: adjust_ticks: gettimeofday failed: %s [%d]\n",
+                               strerror(errno), errno);
+                       return; /* ignore */
+               }
+               diff_time=(long long)crt_time.tv_sec*1000000+crt_time.tv_usec-
+                                       ((long long) last_time.tv_sec*1000000+last_time.tv_usec);
+               if (diff_time<0){
+                       LOG(L_WARN, "WARNING: time changed backwards %ld ms ignoring...\n",
+                                               (long)(diff_time/1000));
+                       last_time=crt_time;
+                       last_ticks=*ticks;
+               }else{
+                       diff_ticks_raw=*ticks-last_ticks;
+                       diff_time_ticks=(ticks_t)((diff_time*TIMER_TICKS_HZ)/1000000LL);
+                       delta=(s_ticks_t)(diff_time_ticks-diff_ticks_raw);
+                       if (delta<-1){
+                               LOG(L_WARN, "WARNING: our timer runs faster then real-time"
+                                               " (%u ms / %u ticks our time .->"
+                                                " %ld ms / %u ticks real time)\n", 
+                                               diff_ticks_raw*1000/TIMER_TICKS_HZ, diff_ticks_raw,
+                                               (long)(diff_time/1000), diff_time_ticks);
+                               last_time=crt_time;
+                               last_ticks=*ticks;
+                       }else{
+                               /* fix the ticks */
+                               if (delta>(s_ticks_t)TIMER_MAX_DRIFT){
+#ifndef TIMER_DEBUG
+                                       if (delta > 2*(s_ticks_t)TIMER_MAX_DRIFT)
+#endif
+                                               LOG(L_INFO, "adjusting timer ticks (%lu) with %ld ms"
+                                                               " (%ld ticks)\n",
+                                                               (unsigned long)*ticks,
+                                                       (long)(delta*1000)/TIMER_TICKS_HZ, (long)delta);
+                                       *ticks+=(ticks_t)delta;
+                               }else{
+                                       /*DBG("incredible, but our timer is in sync with"
+                                                       " real time (%lu)\n", (unsigned long)*ticks);
+                                       */
+                               }
+                       }
+               }
+       }
+}
+
+
+
+
+struct timer_ln* timer_alloc()
+{
+       return shm_malloc(sizeof(struct timer_ln));
+}
+
+void timer_free(struct timer_ln* t)
+{
+       shm_free(t);
+}
+
+
+/* unsafe (no lock ) timer add function
+ * t = current ticks
+ * tl must be filled (the intial_timeout and flags must be set)
+ * returns -1 on error, 0 on success */
+static inline int _timer_add(ticks_t t, struct timer_ln* tl)
+{
+       ticks_t delta;
+
+#ifdef USE_SLOW_TIMER
+       tl->flags&=~((unsigned short)F_TIMER_ON_SLOW_LIST);
+       tl->slow_idx=0;
+#endif
+       delta=tl->initial_timeout;
+       tl->expire=t+delta;
+       return _timer_dist_tl(tl, delta);
+}
+
+
+
+/* "public", safe timer add functions
+ * adds a timer at delta ticks from the current time
+ * returns -1 on error, 0 on success
+ * WARNING: to re-add a deleted or expired timer you must call
+ *          timer_reinit(tl) prior to timer_add
+ *          The default behaviour allows timer_add to add a timer only if it
+ *          has never been added before.*/
+#ifdef TIMER_DEBUG
+int timer_add_safe(struct timer_ln* tl, ticks_t delta,
+                                       const char* file, const char* func, unsigned line)
 #else
-               pkg_free(jiffies); jiffies=0;
+int timer_add_safe(struct timer_ln* tl, ticks_t delta)
 #endif
+{
+       int ret;
+       
+       LOCK_TIMER_LIST();
+       if (tl->flags & F_TIMER_ACTIVE){
+#ifdef TIMER_DEBUG
+               LOG(timerlog, "timer_add called on an active timer %p (%p, %p),"
+                                       " flags %x\n", tl, tl->next, tl->prev, tl->flags);
+               LOG(timerlog, "WARN: -timer_add-; called from %s(%s):%d\n",
+                                       func, file, line);
+               LOG(timerlog, "WARN: -timer_add-: added %d times"
+                                       ", last from: %s(%s):%d, deleted %d times"
+                                       ", last from: %s(%s):%d, init %d times, expired %d \n",
+                                       tl->add_calls, tl->add_func, tl->add_file, tl->add_line,
+                                       tl->del_calls, tl->del_func, tl->del_file, tl->del_line,
+                                       tl->init, tl->expires_no);
+#else
+               DBG("timer_add called on an active timer %p (%p, %p),"
+                                       " flags %x\n", tl, tl->next, tl->prev, tl->flags);
+#endif
+               ret=-1; /* refusing to add active or non-reinit. timer */
+               goto error;
        }
+       tl->initial_timeout=delta;
+       if ((tl->next!=0) || (tl->prev!=0)){
+               LOG(L_CRIT, "BUG: timer_add: called with linked timer: %p (%p, %p)\n",
+                               tl, tl->next, tl->prev);
+               ret=-1;
+               goto error;
+       }
+       tl->flags|=F_TIMER_ACTIVE;
+#ifdef TIMER_DEBUG
+       tl->add_file=file;
+       tl->add_func=func;
+       tl->add_line=line;
+       tl->add_calls++;
+#endif
+       ret=_timer_add(*ticks, tl);
+error:
+       UNLOCK_TIMER_LIST();
+       return ret;
+}
+
+
 
-       t=timer_list;
-       while(t) {
-               foo=t->next;
-               pkg_free(t);
-               t=foo;
+/* safe timer delete
+ * deletes tl and inits the list pointer to 0
+ * WARNING: to be able to reuse a deleted timer you must call
+ *          timer_reinit(tl) on it
+ * 
+ */
+#ifdef TIMER_DEBUG
+void timer_del_safe(struct timer_ln* tl,
+                                       const char* file, const char* func, unsigned line)
+#else
+void timer_del_safe(struct timer_ln* tl)
+#endif
+{
+       
+again:
+       /* quick exit if timer inactive */
+       if ( !(tl->flags & F_TIMER_ACTIVE)){
+#ifdef TIMER_DEBUG
+               LOG(timerlog, "timer_del called on an inactive timer %p (%p, %p),"
+                                       " flags %x\n", tl, tl->next, tl->prev, tl->flags);
+               LOG(timerlog, "WARN: -timer_del-; called from %s(%s):%d\n",
+                                       func, file, line);
+               LOG(timerlog, "WARN: -timer_del-: added %d times"
+                                       ", last from: %s(%s):%d, deleted %d times"
+                                       ", last from: %s(%s):%d, init %d times, expired %d \n",
+                                       tl->add_calls, tl->add_func, tl->add_file, tl->add_line,
+                                       tl->del_calls, tl->del_func, tl->del_file, tl->del_line,
+                                       tl->init, tl->expires_no);
+#else
+               DBG("timer_del called on an inactive timer %p (%p, %p),"
+                                       " flags %x\n", tl, tl->next, tl->prev, tl->flags);
+#endif
+               return;
+       }
+#ifdef USE_SLOW_TIMER
+               if (IS_ON_SLOW_LIST(tl) && (tl->slow_idx!=*t_idx)){
+                       LOCK_SLOW_TIMER_LIST();
+                       if (!IS_ON_SLOW_LIST(tl) || (tl->slow_idx==*t_idx)){
+                               UNLOCK_SLOW_TIMER_LIST();
+                               goto again;
+                       }
+                       if (IS_RUNNING_SLOW(tl)){
+                               UNLOCK_SLOW_TIMER_LIST();
+                               sched_yield(); /* wait for it to complete */
+                               goto again;
+                       }
+                       if (tl->next!=0){
+                               _timer_rm_list(tl); /* detach */
+                               tl->next=tl->prev=0;
+#ifdef TIMER_DEBUG
+                               tl->del_file=file;
+                               tl->del_func=func;
+                               tl->del_line=line;
+                               tl->flags|=F_TIMER_DELETED;
+#endif
+                       }else{
+#ifdef TIMER_DEBUG
+                               LOG(timerlog, "timer_del: (s) timer %p (%p, %p) flags %x "
+                                                       "already detached\n",
+                                                       tl, tl->next, tl->prev, tl->flags);
+                               LOG(timerlog, "WARN: -timer_del-: @%d tl=%p "
+                                       "{ %p, %p, %d, %d, %p, %p, %04x, -}\n", get_ticks_raw(), 
+                                       tl,  tl->next, tl->prev, tl->expire, tl->initial_timeout,
+                                       tl->data, tl->f, tl->flags);
+                               LOG(timerlog, "WARN: -timer_del-; called from %s(%s):%d\n",
+                                               func, file, line);
+                               LOG(timerlog, "WARN: -timer_del-: added %d times"
+                                               ", last from: %s(%s):%d, deleted %d times"
+                                               ", last from: %s(%s):%d, init %d times, expired %d \n",
+                                               tl->add_calls,
+                                               tl->add_func, tl->add_file, tl->add_line,
+                                               tl->del_calls,
+                                               tl->del_func, tl->del_file, tl->del_line,
+                                               tl->init, tl->expires_no);
+#else
+                               DBG("timer_del: (s) timer %p (%p, %p) flags %x "
+                                                       "already detached\n",
+                                                       tl, tl->next, tl->prev, tl->flags);
+#endif
+                       }
+                       UNLOCK_SLOW_TIMER_LIST();
+               }else{
+#endif
+                       LOCK_TIMER_LIST();
+#ifdef USE_SLOW_TIMER
+                       if (IS_ON_SLOW_LIST(tl) && (tl->slow_idx!=*t_idx)){
+                               UNLOCK_TIMER_LIST();
+                               goto again;
+                       }
+#endif
+                       if (IS_RUNNING(tl)){
+                               UNLOCK_TIMER_LIST();
+                               sched_yield(); /* wait for it to complete */
+                               goto again;
+                       }
+                       if ((tl->next!=0)&&(tl->prev!=0)){
+                               _timer_rm_list(tl); /* detach */
+                               tl->next=tl->prev=0;
+#ifdef TIMER_DEBUG
+                               tl->del_file=file;
+                               tl->del_func=func;
+                               tl->del_line=line;
+                               tl->flags|=F_TIMER_DELETED;
+#endif
+                       }else{
+#ifdef TIMER_DEBUG
+                               LOG(timerlog, "timer_del: (f) timer %p (%p, %p) flags %x "
+                                                       "already detached\n",
+                                                       tl, tl->next, tl->prev, tl->flags);
+                               LOG(timerlog, "WARN: -timer_del-: @%d tl=%p "
+                                       "{ %p, %p, %d, %d, %p, %p, %04x, -}\n", get_ticks_raw(), 
+                                       tl,  tl->next, tl->prev, tl->expire, tl->initial_timeout,
+                                       tl->data, tl->f, tl->flags);
+                               LOG(timerlog, "WANT: -timer_del-; called from %s(%s):%d\n",
+                                               func, file, line);
+                               LOG(timerlog, "WARN: -timer_del-: added %d times"
+                                               ", last from: %s(%s):%d, deleted %d times"
+                                               ", last from: %s(%s):%d, init %d times, expired %d \n",
+                                               tl->add_calls,
+                                               tl->add_func, tl->add_file, tl->add_line,
+                                               tl->del_calls,
+                                               tl->del_func, tl->del_file, tl->del_line,
+                                               tl->init, tl->expires_no);
+#else
+                               DBG("timer_del: (f) timer %p (%p, %p) flags %x "
+                                                       "already detached\n",
+                                                       tl, tl->next, tl->prev, tl->flags);
+#endif
+                       }
+                       UNLOCK_TIMER_LIST();
+#ifdef USE_SLOW_TIMER
+               }
+#endif
+}
+
+
+
+/* called from timer_handle, must be called with the timer lock held */
+inline static void timer_list_expire(ticks_t t, struct timer_head* h
+#ifdef USE_SLOW_TIMER
+                                                                               , struct timer_head* slow_l,
+                                                                               slow_idx_t slow_mark
+#endif
+                                                                                                                                       )
+{
+       struct timer_ln * tl;
+       ticks_t ret;
+#ifdef TIMER_DEBUG
+       struct timer_ln* first;
+       int i=0;
+       
+       first=h->next;
+#endif
+       
+       /*DBG("timer_list_expire @ ticks = %lu, list =%p\n",
+                       (unsigned long) *ticks, h);
+       */
+       while(h->next!=(struct timer_ln*)h){
+               tl=h->next;
+#ifdef TIMER_DEBUG /* FIXME: replace w/ EXTRA_DEBUG */
+               if (tl==0){
+                       LOG(L_CRIT, "BUG: timer_list_expire: tl=%p, h=%p {%p, %p}\n",
+                                       tl, h, h->next, h->prev);
+                       abort();
+               }else if((tl->next==0) || (tl->prev==0)){
+                       LOG(L_CRIT, "BUG: timer_list_expire: @%d tl=%p "
+                                       "{ %p, %p, %d, %d, %p, %p, %04x, -},"
+                                       " h=%p {%p, %p}\n", t, 
+                                       tl,  tl->next, tl->prev, tl->expire, tl->initial_timeout,
+                                       tl->data, tl->f, tl->flags, 
+                                       h, h->next, h->prev);
+                       LOG(L_CRIT, "BUG: -timer_list_expire-: cycle %d, first %p,"
+                                               "running %p\n", i, first, *running_timer);
+                       LOG(L_CRIT, "BUG: -timer_list_expire-: added %d times"
+                                               ", last from: %s(%s):%d, deleted %d times"
+                                               ", last from: %s(%s):%d, init %d times, expired %d \n",
+                                               tl->add_calls,
+                                               tl->add_func, tl->add_file, tl->add_line,
+                                               tl->del_calls,
+                                               tl->del_func, tl->del_file, tl->del_line,
+                                               tl->init, tl->expires_no);
+                       abort();
+               }
+               i++;
+#endif
+               _timer_rm_list(tl); /* detach */
+#ifdef USE_SLOW_TIMER
+               if (IS_FAST_TIMER(tl)){
+#endif
+               /* if fast timer */
+                       SET_RUNNING(tl);
+                       tl->next=tl->prev=0; /* debugging */
+#ifdef TIMER_DEBUG
+                       tl->expires_no++;
+#endif
+                       UNLOCK_TIMER_LIST(); /* acts also as write barrier */ 
+                               ret=tl->f(t, tl, tl->data);
+                               if (ret==0){
+                                       UNSET_RUNNING();
+                                       LOCK_TIMER_LIST();
+                               }else{
+                                       /* not one-shot, re-add it */
+                                       LOCK_TIMER_LIST();
+                                       if (ret!=(ticks_t)-1) /* ! periodic */
+                                               tl->initial_timeout=ret;
+                                       _timer_add(t, tl);
+                                       UNSET_RUNNING();
+                               }
+#ifdef USE_SLOW_TIMER
+               }else{
+                       /* slow timer */
+                       SET_SLOW_LIST(tl);
+                       tl->slow_idx=slow_mark; /* current index */
+                       /* overflow check in timer_handler*/
+                       _timer_add_list(slow_l, tl);
+                       
+               }
+#endif
        }
 }
 
 
 
-/*register a periodic timer;
+/* "main" timer routine
+ * WARNING: it should never be called twice for the same *ticks value
+ * (it could cause too fast expires for long timers), *ticks must be also
+ *  always increasing */
+static void timer_handler()
+{
+       ticks_t saved_ticks;
+#ifdef USE_SLOW_TIMER
+       int run_slow_timer;
+       int i;
+       
+       run_slow_timer=0;
+       i=(slow_idx_t)(*t_idx%SLOW_LISTS_NO);
+#endif
+       
+       /*DBG("timer_handler: called, ticks=%lu, prev_ticks=%lu\n",
+                       (unsigned long)*ticks, (unsigned long)prev_ticks);
+       */
+       run_timer=0; /* reset run_timer */
+       adjust_ticks();
+       LOCK_TIMER_LIST();
+       do{
+               saved_ticks=*ticks; /* protect against time running backwards */
+               if (prev_ticks>=saved_ticks){
+                       LOG(L_CRIT, "BUG: timer_handler: backwards or still time\n");
+                       /* try to continue */
+                       prev_ticks=saved_ticks-1;
+                       break;
+               }
+               /* go through all the "missed" ticks, taking a possible overflow
+                * into account */
+               for (prev_ticks=prev_ticks+1; prev_ticks!=saved_ticks; prev_ticks++) 
+                       timer_run(prev_ticks);
+               timer_run(prev_ticks); /* do it for saved_ticks too */
+       }while(saved_ticks!=*ticks); /* in case *ticks changed */
+#ifdef USE_SLOW_TIMER
+       timer_list_expire(*ticks, &timer_lst->expired, &slow_timer_lists[i],
+                                               *t_idx);
+#else
+       timer_list_expire(*ticks, &timer_lst->expired);
+#endif
+       /* WARNING: add_timer(...,0) must go directly to expired list, since
+        * otherwise there is a race between timer running and adding it
+        * (it could expire it H0_ENTRIES ticks later instead of 'now')*/
+#ifdef USE_SLOW_TIMER
+       if (slow_timer_lists[i].next!=(struct timer_ln*)&slow_timer_lists[i]){
+               run_slow_timer=1;
+               if ((slow_idx_t)(*t_idx-*s_idx) < (SLOW_LISTS_NO-1U))
+                       (*t_idx)++;
+               else{
+                       LOG(L_ERR, "ERROR: slow timer too slow: overflow (%d - %d = %d)\n",
+                                       *t_idx, *s_idx, *t_idx-*s_idx);
+                       /* trying to continue */
+               }
+       }
+#endif
+       UNLOCK_TIMER_LIST();
+#ifdef USE_SLOW_TIMER
+       /* wake up the "slow" timer */
+       if (run_slow_timer)
+               kill(slow_timer_pid, SLOW_TIMER_SIG);
+#endif
+}
+
+
+
+/* main timer function, never exists */
+void timer_main()
+{
+       while(1){
+               if (run_timer){
+                       timer_handler();
+               }
+               pause();
+       }
+}
+
+
+
+/* generic call back for the old style timer functions */
+static ticks_t compat_old_handler(ticks_t ti, struct timer_ln* tl,
+                                                                       void * data)
+{
+       struct sr_timer* t;
+       
+       DBG("timer: compat_old_handler: calling, ticks=%u/%u, tl=%p, t=%p\n",
+                       prev_ticks, (unsigned)*ticks, tl, data);
+       t=(struct sr_timer*)data;
+       t->timer_f(TICKS_TO_S(*ticks), t->t_param);
+       return (ticks_t)-1; /* periodic */
+}
+
+
+
+/* register a periodic timer;
+ * compatibility mode.w/ the old timer interface...
  * ret: <0 on error
  * Hint: if you need it in a module, register it from mod_init or it 
  * won't work otherwise*/
@@ -101,7 +846,7 @@ int register_timer(timer_function f, void* param, unsigned int interval)
 {
        struct sr_timer* t;
 
-       t=pkg_malloc(sizeof(struct sr_timer));
+       t=shm_malloc(sizeof(struct sr_timer));
        if (t==0){
                LOG(L_ERR, "ERROR: register_timer: out of memory\n");
                goto error;
@@ -109,11 +854,13 @@ int register_timer(timer_function f, void* param, unsigned int interval)
        t->id=timer_id++;
        t->timer_f=f;
        t->t_param=param;
-       t->interval=interval;
-       t->expires=*jiffies+interval;
-       /* insert it into the list*/
-       t->next=timer_list;
-       timer_list=t;
+       
+       timer_init(&t->tl, compat_old_handler, t, 0); /* is slow */
+       if (timer_add(&t->tl, S_TO_TICKS(interval))!=0){
+               LOG(L_ERR, "ERROR: register_timer: timer_add failed\n");
+               return -1;
+       }
+       
        return t->id;
 
 error:
@@ -122,44 +869,95 @@ error:
 
 
 
-void timer_ticker()
+ticks_t get_ticks_raw()
 {
-       struct sr_timer* t;
-       unsigned int prev_jiffies;
-       
-       prev_jiffies=*jiffies;
-       *jiffies+=TIMER_TICK;
-       /* test for overflow (if tick= 1s =>overflow in 136 years)*/
-       if (*jiffies<prev_jiffies){ 
-               /*force expire & update every timer, a little buggy but it 
-                * happens once in 136 years :) */
-               for(t=timer_list;t;t=t->next){
-                       t->expires=*jiffies+t->interval;
-                       t->timer_f(*jiffies, t->t_param);
-               }
-               return;
-       }
-       
-       for (t=timer_list;t; t=t->next){
-               if (*jiffies>=t->expires){
-                       t->expires=*jiffies+t->interval;
-                       t->timer_f(*jiffies, t->t_param);
-               }
-       }
+#ifndef SHM_MEM
+       LOG(L_CRIT, "WARNING: get_ticks: no shared memory support compiled in"
+                       ", returning 0 (probably wrong)");
+       return 0;
+#endif
+       return *ticks;
 }
 
 
 
-unsigned int get_ticks()
+/* returns tick in s (for compatibility with the old code) */
+ticks_t get_ticks()
 {
-       if (jiffies==0){
-               LOG(L_CRIT, "BUG: get_ticks: jiffies not initialized\n");
-               return 0;
-       }
 #ifndef SHM_MEM
        LOG(L_CRIT, "WARNING: get_ticks: no shared memory support compiled in"
                        ", returning 0 (probably wrong)");
        return 0;
 #endif
-       return *jiffies;
+       return TICKS_TO_S(*ticks);
+}
+
+
+#ifdef USE_SLOW_TIMER
+
+
+/* slow timer main function, never exists
+ * This function is intended to be executed in a special separated process
+ * (the "slow" timer) which will run the timer handlers of all the registered
+ * timers not marked as "fast". The ideea is to execute the fast timers in the
+ * "main" timer process, as accurate as possible and defer the execution of the  * timers marked as "slow" to the "slow" timer.
+ * Implementation details:
+ *  - it waits for a signal and then wakes up and processes
+ *    all the lists in slow_timer_lists from [s_idx, t_idx). It will
+ *   -it  increments *s_idx (at the end it will be == *t_idx)
+ *   -all list operations are protected by the "slow" timer lock
+ */
+void slow_timer_main()
+{
+       int n;
+       ticks_t ret;
+       struct timer_ln* tl;
+       unsigned short i;
+       
+       while(1){
+               n=sigwaitinfo(&slow_timer_sset, 0);
+               if (n==-1){
+                       if (errno==EINTR) continue; /* some other signal, ignore it */
+                       LOG(L_ERR, "ERROR: slow_timer_main: sigwaitinfo failed: %s [%d]\n",
+                                       strerror(errno), errno);
+                       sleep(1);
+                       /* try to continue */
+               }
+               LOCK_SLOW_TIMER_LIST();
+               while(*s_idx!=*t_idx){
+                       i= *s_idx%SLOW_LISTS_NO;
+                       while(slow_timer_lists[i].next!=
+                                       (struct timer_ln*)&slow_timer_lists[i]){
+                               tl=slow_timer_lists[i].next;
+                               _timer_rm_list(tl);
+                               tl->next=tl->prev=0;
+#ifdef TIMER_DEBUG
+                               tl->expires_no++;
+#endif
+                               SET_RUNNING_SLOW(tl);
+                               UNLOCK_SLOW_TIMER_LIST();
+                                       ret=tl->f(*ticks, tl, tl->data);
+                                       if (ret==0){
+                                               /* one shot */
+                                               UNSET_RUNNING_SLOW();
+                                               LOCK_SLOW_TIMER_LIST();
+                                       }else{
+                                               /* not one shot, re-add it */
+                                               LOCK_TIMER_LIST(); /* add it to the "main"  list */
+                                                       RESET_SLOW_LIST(tl);
+                                                       if (ret!=(ticks_t)-1) /* != periodic */
+                                                               tl->initial_timeout=ret;
+                                                       _timer_add(*ticks, tl);
+                                               UNLOCK_TIMER_LIST();
+                                               LOCK_SLOW_TIMER_LIST();
+                                               UNSET_RUNNING_SLOW();
+                                       }
+                       }
+                       (*s_idx)++;
+               }
+               UNLOCK_SLOW_TIMER_LIST();
+       }
+       
 }
+
+#endif
diff --git a/timer.h b/timer.h
index 0ebdcd0..5a7f761 100644 (file)
--- a/timer.h
+++ b/timer.h
@@ -2,7 +2,7 @@
  * $Id$
  *
  *
- * timer related functions
+ * timer related functions (public interface)
  *
  * Copyright (C) 2001-2003 FhG Fokus
  *
  * along with this program; if not, write to the Free Software 
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  */
+/* History:
+ * --------
+ *  2005-07-27  complete re-design/re-implemnetation (andrei)
+ */
 
 
 
 #ifndef timer_h
 #define timer_h
 
+#define USE_SLOW_TIMER /* use another process to run the timer handlers 
+                                                 marked "slow" */
+/*#define TIMER_DEBUG -- compile with -DTIMER_DEBUG*/
+
+#include "clist.h"
+#include "dprint.h"
+
+#ifdef USE_SLOW_TIMER
+#include <sys/types.h>
+
+typedef unsigned short slow_idx_t; /* type fot the slow index */
+extern pid_t slow_timer_pid;
+#endif
+
+typedef unsigned int ticks_t;/* type used to keep the ticks (must be 32 bits)*/
+typedef signed   int s_ticks_t; /* signed ticks type */
+
+
+
+
+/* deprecated, old, kept for compatibility */
 typedef void (timer_function)(unsigned int ticks, void* param);
+/* deprecated, old, kept for compatibility 
+       get_ticks()*TIMER_TICK used to be the time in s
+       for new code, use get_ticks_raw() and one of the macros defined in
+       time_ticks.h (.e.g TICKS_TO_S(tick) to convert to s or ms )*/
+#define TIMER_TICK 1 /* 1 s, kept for compatibility */
 
 
-struct sr_timer{
-       int id;
-       timer_function* timer_f;
-       void* t_param;
-       unsigned int interval;
-       
-       unsigned int expires;
-       
-       struct sr_timer* next;
-};
+struct timer_ln; /* forward decl */
+/* new 
+ * params:
+ *         - handle pointer to the corresponding struct timer_ln
+ * return: 0 if the timer is one shot, new expire interval if not, -1
+ *         if periodic
+ * e.g.:   - a periodic timer would return: (ticks_t)(-1) or
+ *            ((struct timer_ln*)handle)->initial_timeout
+ *         - a timer which wants to expire again in x ms would return:
+ *             (x * TICKS_HZ + 999)/1000
+ */
+typedef ticks_t (timer_handler_f)(ticks_t t, struct timer_ln* tl,
+                                                                       void* data);
+
 
+/* timer flags */
+#define F_TIMER_FAST   1
+#define F_TIMER_ON_SLOW_LIST   0x100
+#define F_TIMER_ACTIVE 0x200 /* timer is running or has run and expired
+                                                                (one shot) */
+#ifdef TIMER_DEBUG
+#define F_TIMER_DELETED        0x400 
+#endif
+
+struct timer_ln{ /* timer_link already used in tm */
+       struct timer_ln* next;
+       struct timer_ln* prev;
+       ticks_t expire; 
+       ticks_t initial_timeout;
+       void* data;
+       timer_handler_f* f; 
+       volatile unsigned short flags;
+#ifdef USE_SLOW_TIMER
+       volatile slow_idx_t slow_idx;
+#else
+       unsigned short reserved;
+#endif
+#ifdef TIMER_DEBUG
+       unsigned int expires_no; /* timer handler calls */
+       const char* add_file;
+       const char* add_func;
+       unsigned add_line;
+       unsigned add_calls;
+       const char* del_file;
+       const char* del_func;
+       unsigned del_line;
+       unsigned int del_calls;
+       unsigned int init; /* how many times was init/re-init */
+#endif
+};
 
 
-extern struct sr_timer* timer_list;
 
+void timer_main(); /* timer main loop, never exists */
 
 
 int init_timer();
+int arm_timer();
 void destroy_timer();
+
+#ifdef USE_SLOW_TIMER
+int arm_slow_timer();
+void slow_timer_main();
+#endif
+
+
+struct timer_ln* timer_alloc();
+void timer_free(struct timer_ln* t);
+
+#ifdef TIMER_DEBUG
+/* use for a deleted/expired timer that you want to add again */
+#define timer_reinit(tl) \
+       do{ \
+               (tl)->flags&=~((unsigned short)(F_TIMER_ON_SLOW_LIST | \
+                                                                                         F_TIMER_ACTIVE));\
+               (tl)->init++; \
+       }while(0)
+#else
+/* use for a deleted/expired timer that you want to add again */
+#define timer_reinit(tl) \
+       (tl)->flags&=~((unsigned short)(F_TIMER_ON_SLOW_LIST | \
+                                                                                 F_TIMER_ACTIVE))
+#endif
+
+#define timer_init(tl, fun, param, flgs) \
+       do{ \
+               memset((tl), 0, sizeof(struct timer_ln)); \
+               (tl)->f=(fun); \
+               (tl)->data=(param); \
+               (tl)->flags=(flgs); \
+               timer_reinit(tl); \
+       }while(0)
+
+#ifdef TIMER_DEBUG
+int timer_add_safe(struct timer_ln *tl, ticks_t delta, 
+                                       const char*, const char*, unsigned);
+void timer_del_safe(struct timer_ln *tl,
+                                       const char*, const char*, unsigned);
+#define timer_add(tl, d) \
+       timer_add_safe((tl), (d), __FILE__, __FUNCTION__, __LINE__)
+#define timer_del(tl) \
+       timer_del_safe((tl), __FILE__, __FUNCTION__, __LINE__)
+#else
+int timer_add_safe(struct timer_ln *tl, ticks_t delta);
+void timer_del_safe(struct timer_ln *tl);
+#define timer_add timer_add_safe
+#define timer_del timer_del_safe
+#endif
+
+/* old timer compatibility functions & structure */
+
+struct sr_timer{
+       struct timer_ln tl;
+       int id;
+       timer_function* timer_f;
+       void* t_param;
+};
+
+
 /*register a periodic timer;
  * ret: <0 on error*/
 int register_timer(timer_function f, void* param, unsigned int interval);
-unsigned int get_ticks();
-void timer_ticker();
+ticks_t get_ticks();
+ticks_t get_ticks_raw();
 
 #endif
diff --git a/timer_funcs.h b/timer_funcs.h
new file mode 100644 (file)
index 0000000..405f5c1
--- /dev/null
@@ -0,0 +1,229 @@
+/*
+ * $Id$
+ *
+ *
+ * timer related functions (internal)
+ *
+ * Copyright (C) 2005 iptelorg GmbH
+ *
+ * This file is part of ser, a free SIP server.
+ *
+ * ser is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version
+ *
+ * For a license to use the ser software under conditions
+ * other than those described here, or to purchase support for this
+ * software, please contact iptel.org by e-mail at the following addresses:
+ *    info@iptel.org
+ *
+ * ser is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License 
+ * along with this program; if not, write to the Free Software 
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* History:
+ * --------
+ *  2005-07-27  complete re-design/re-implemnetation (andrei)
+ */
+
+
+#ifndef timer_funcs_h
+#define timer_funcs_h
+
+#include "timer.h"
+
+
+struct timer_head{
+       struct timer_ln* volatile next;
+       struct timer_ln* volatile prev;
+};
+
+
+
+/* hierarchical timing wheel with 3 levels
+ * Most timeouts should go in the first "wheel" (h0)
+ * h0 will contain timers expiring from crt. time up to
+ * crt. time + (1<<H0_BITS)/TICKS_HZ s and will use
+ * (1<<H0_BITS)*sizeof(struct timer_head) bytes of memory, so arrange it
+ * accordingly
+ */
+
+#define H0_BITS 14
+#define H1_BITS  9 
+#define H2_BITS  (32-H1_BITS-H0_BITS)
+/* Uses ~280K on a 64 bits system and ~140K on a 32 bit system; for TICKS_HZ=10
+ * holds ~ 30 min in the first hash/wheel and ~233h in the first two.
+ * More perfomant arrangement: 16, 8, 8 (but eats 1 MB on a 64 bit system, and
+ *  512K on a 32 bit one). For TICKS_HZ=10 it holds almost 2h in the
+ *  first hash/wheel and ~460h in the first two.
+ */
+
+#define H0_ENTRIES (1<<H0_BITS)
+#define H1_ENTRIES (1<<H1_BITS)
+#define H2_ENTRIES (1<<H2_BITS)
+
+#define H0_MASK (H0_ENTRIES-1)
+#define H1_MASK (H1_ENTRIES-1)
+#define H1_H0_MASK ((1<<(H0_BITS+H1_BITS))-1)
+
+
+struct timer_lists{
+       struct timer_head  h0[H0_ENTRIES];
+       struct timer_head  h1[H1_ENTRIES];
+       struct timer_head  h2[H2_ENTRIES];
+       struct timer_head  expired; /* list of expired entries */
+};
+
+extern struct timer_lists* timer_lst;
+
+
+#define _timer_init_list(head) clist_init((head), next, prev)
+
+
+#define _timer_add_list(head, tl) \
+       clist_append((head), (tl), next, prev)
+
+#define _timer_rm_list(tl) \
+       clist_rm((tl), next, prev)
+
+#define timer_foreach(tl, head)        clist_foreach((head), (tl), next)
+#define timer_foreach_safe(tl, tmp, head)      \
+       clist_foreach_safe((head), (tl), (tmp), next)
+
+
+
+
+/* generic add timer entry to the timer lists function (see _timer_add)
+ * tl->expire must be set previously, delta is the difference in ticks
+ * from current time to the timer desired expire (should be tl->expire-*tick)
+ * If you don't know delta, you probably want to call _timer_add instead.
+ */
+static inline int _timer_dist_tl(struct timer_ln* tl, ticks_t delta)
+{
+       if (delta<H0_ENTRIES){
+               if (delta==0){
+                       LOG(L_WARN, "WARNING: timer: add_timeout: 0 expire timer added\n");
+                       _timer_add_list(&timer_lst->expired, tl);
+               }else{
+                       DBG("_timer_dist_tl: adding timer %p, delta %u,"
+                                       " expire %u @h0[%u]\n",
+                               tl, (unsigned) delta, (unsigned) tl->expire,
+                               (unsigned)(tl->expire & H0_MASK));
+                       _timer_add_list( &timer_lst->h0[tl->expire & H0_MASK], tl);
+               }
+       }else if (delta<(H0_ENTRIES*H1_ENTRIES)){
+               DBG("_timer_dist_tl: adding timer %p, delta %u, expire %u @h1[%u]\n",
+                               tl, (unsigned) delta, (unsigned) tl->expire,
+                               (unsigned)((tl->expire & H1_H0_MASK)>>H0_BITS));
+               _timer_add_list(&timer_lst->h1[(tl->expire & H1_H0_MASK)>>H0_BITS],tl);
+       }else{
+               DBG("_timer_dist_tl: adding timer %p, delta %u, expire %u @h2[%u]\n",
+                               tl, (unsigned) delta, (unsigned) tl->expire,
+                               (unsigned)(tl->expire>>(H1_BITS+H0_BITS)));
+               _timer_add_list(&timer_lst->h2[tl->expire>>(H1_BITS+H0_BITS)], tl);
+       }
+       return 0;
+}
+
+
+
+#define _timer_mv_expire(h) \
+       do{ \
+               if ((h)->next!=(struct timer_ln*)(h)){ \
+                       clist_append_sublist(&timer_lst->expired, (h)->next, \
+                                                                       (h)->prev, next, prev); \
+                       _timer_init_list(h); \
+               } \
+       }while(0)
+
+
+#if 1
+
+static inline void timer_redist(ticks_t t, struct timer_head *h)
+{
+       struct timer_ln* tl;
+       struct timer_ln* tmp;
+       
+       DBG("timer_redist: list %p, ticks %lu\n", h, (unsigned long) t);
+       
+       timer_foreach_safe(tl, tmp, h){
+               _timer_dist_tl(tl, tl->expire-t);
+       }
+       /* clear the current list */
+       _timer_init_list(h);
+}
+
+static inline void timer_run(ticks_t t)
+{
+       /* trust the compiler for optimizing */
+       if ((t & H0_MASK)==0){              /*r1*/
+               if ((t & H1_H0_MASK)==0){        /*r2*/
+                       DBG("timer_run: ticks %u, redist h2[%u]\n",
+                                                       (unsigned ) t, (unsigned)( t>>(H0_BITS+H1_BITS)));
+                       timer_redist(t, &timer_lst->h2[t>>(H0_BITS+H1_BITS)]);
+               }
+               DBG("timer_run: ticks %u, redist h1[%u]\n",
+                                               (unsigned ) t, (unsigned)((t & H1_H0_MASK)>>H0_BITS));
+               
+               timer_redist(t, &timer_lst->h1[(t & H1_H0_MASK)>>H0_BITS]);/*r2 >> H0*/
+       }
+       /*
+       DBG("timer_run: ticks %u, expire h0[%u]\n",
+                                               (unsigned ) t, (unsigned)(t & H0_MASK));*/
+       _timer_mv_expire(&timer_lst->h0[t & H0_MASK]);  /*r1*/
+}
+#else
+
+static inline void timer_lst_mv0(ticks_t t, struct timer_head* h)
+{
+       struct timer_ln* tl;
+       struct timer_ln* tmp;
+       
+       timer_foreach_safe(tl, tmp, h){
+                       _timer_dist_tl(tl, &timer_lst->h0[tl->expire & H0_MASK]);
+       }
+       /* clear the current list */
+       _timer_init_list(h);
+}
+
+static inline void timer_lst_mv1(ticks_t t, struct timer_head* h)
+{
+       struct timer_ln* tl;
+       struct timer_ln* tmp;
+       
+       timer_foreach_safe(tl, tmp, h){
+               if ((tl->expire & H0_MASK)==0) /* directly to h0 */
+                       _timer_add_list(tl, &timer_lst->h0[tl->expire & H0_MASK]);
+               else  /* to h1 */
+                       _timer_add_list(tl, 
+                                               &timer_lst->h1[(tl->expire & H1_H0_MASK)>>H0_BITS]);
+       }
+       /* clear the current list */
+       _timer_init_list(h);
+}
+
+
+/* possible faster version */
+static inline void timer_run(ticks_t t)
+{
+       /* trust the compiler for optimizing */
+       if ((t & H0_MASK)==0){              /*r1*/
+               if ((t & H1_H0_MASK)==0)        /*r2*/
+                       /* just move the list "down" to hash1 */
+                       timer_lst_mv1(&timer_lst->h2[t>>(H0_BITS+H1_BITS)]); 
+               /* move "down" to hash0 */
+               timer_lst_mv0(&timer_lst->h1[(t & H1_H0_MASK)>>H0_BITS]);
+       }
+       _timer_mv_expire(t, &timer_lst->h0[t & H0_MASK]);  /*r1*/
+}
+#endif
+
+
+
+#endif
index 68cb33a..c27fb7f 100644 (file)
--- a/version.h
+++ b/version.h
 #define DEBUG_DMALLOC_STR ""
 #endif
 
+#ifdef TIMER_DEBUG
+#define TIMER_DEBUG_STR ", TIMER_DEBUG"
+#else
+#define TIMER_DEBUG_STR ""
+#endif
+
 #ifdef FAST_LOCK
 #ifdef BUSY_WAIT
 #define FAST_LOCK_STR ", FAST_LOCK-BUSY_WAIT"
        DISABLE_NAGLE_STR USE_MCAST_STR NO_DEBUG_STR NO_LOG_STR DNS_IP_HACK_STR \
        SHM_MEM_STR SHM_MMAP_STR PKG_MALLOC_STR VQ_MALLOC_STR F_MALLOC_STR \
        USE_SHM_MEM_STR DBG_QM_MALLOC_STR DBG_F_MALLOC_STR DEBUG_DMALLOC_STR \
+       TIMER_DEBUG_STR \
        FAST_LOCK_STR NOSMP_STR USE_PTHREAD_MUTEX_STR USE_POSIX_SEM_STR \
        USE_SYSV_SEM_STR