pkg: fix wrong package name, closes FS#148, reported from Andrew Pogrebennyk
[sip-router] / timer_funcs.h
1 /*
2  * $Id$
3  *
4  *
5  * timer related functions (internal)
6  *
7  * Copyright (C) 2005 iptelorg GmbH
8  *
9  * This file is part of SIP-router, a free SIP server.
10  *
11  * SIP-router is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version
15  *
16  * SIP-router is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License 
22  * along with this program; if not, write to the Free Software 
23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
24  */
25
26 /* History:
27  * --------
28  *  2005-07-27  complete re-design/re-implemnetation (andrei)
29  */
30
31 /**
32  * @file
33  * @brief SIP-router core :: Timer related functions (internal)
34  * @ingroup core
35  * Module: @ref core
36  */
37
38
39 #ifndef timer_funcs_h
40 #define timer_funcs_h
41
42 #include "timer.h"
43
44
45 struct timer_head{
46         struct timer_ln* volatile next;
47         struct timer_ln* volatile prev;
48 };
49
50
51
52 /** @name hierarchical timing wheel with 3 levels
53  *
54  * Most timeouts should go in the first "wheel" (h0)
55  * h0 will contain timers expiring from crt. time up to
56  * crt. time + (1<<H0_BITS)/TICKS_HZ s and will use
57  * (1<<H0_BITS)*sizeof(struct timer_head) bytes of memory, so arrange it
58  * accordingly
59  *
60  * Uses ~280K on a 64 bits system and ~140K on a 32 bit system; for TICKS_HZ=10
61  * holds ~ 30 min in the first hash/wheel and ~233h in the first two.
62  * More perfomant arrangement: 16, 8, 8 (but eats 1 MB on a 64 bit system, and
63  *  512K on a 32 bit one). For TICKS_HZ=10 it holds almost 2h in the
64  *  first hash/wheel and ~460h in the first two.
65  */
66 /*@{ */
67
68 #define H0_BITS 14
69 #define H1_BITS  9 
70 #define H2_BITS  (32-H1_BITS-H0_BITS)
71
72
73 #define H0_ENTRIES (1<<H0_BITS)
74 #define H1_ENTRIES (1<<H1_BITS)
75 #define H2_ENTRIES (1<<H2_BITS)
76
77 #define H0_MASK (H0_ENTRIES-1)
78 #define H1_MASK (H1_ENTRIES-1)
79 #define H1_H0_MASK ((1<<(H0_BITS+H1_BITS))-1)
80
81 /*@} */
82
83 struct timer_lists{
84         struct timer_head  h0[H0_ENTRIES];
85         struct timer_head  h1[H1_ENTRIES];
86         struct timer_head  h2[H2_ENTRIES];
87         struct timer_head  expired; /* list of expired entries */
88 };
89
90 extern struct timer_lists* timer_lst;
91
92
93 #define _timer_init_list(head)  clist_init((head), next, prev)
94
95
96 #define _timer_add_list(head, tl) \
97         clist_append((head), (tl), next, prev)
98
99 #define _timer_rm_list(tl) \
100         clist_rm((tl), next, prev)
101
102 #define timer_foreach(tl, head) clist_foreach((head), (tl), next)
103 #define timer_foreach_safe(tl, tmp, head)       \
104         clist_foreach_safe((head), (tl), (tmp), next)
105
106
107
108
109 /** @brief generic add timer entry to the timer lists function (see _timer_add)
110  *
111  * tl->expire must be set previously, delta is the difference in ticks
112  * from current time to the timer desired expire (should be tl->expire-*tick)
113  * If you don't know delta, you probably want to call _timer_add instead.
114  */
115 static inline int _timer_dist_tl(struct timer_ln* tl, ticks_t delta)
116 {
117         if (delta<H0_ENTRIES){
118                 if (delta==0){
119                         LOG(L_WARN, "WARNING: timer: add_timeout: 0 expire timer added\n");
120                         _timer_add_list(&timer_lst->expired, tl);
121                 }else{
122                         _timer_add_list( &timer_lst->h0[tl->expire & H0_MASK], tl);
123                 }
124         }else if (delta<(H0_ENTRIES*H1_ENTRIES)){
125                 _timer_add_list(&timer_lst->h1[(tl->expire & H1_H0_MASK)>>H0_BITS],tl);
126         }else{
127                 _timer_add_list(&timer_lst->h2[tl->expire>>(H1_BITS+H0_BITS)], tl);
128         }
129         return 0;
130 }
131
132
133
134 #define _timer_mv_expire(h) \
135         do{ \
136                 if ((h)->next!=(struct timer_ln*)(h)){ \
137                         clist_append_sublist(&timer_lst->expired, (h)->next, \
138                                                                         (h)->prev, next, prev); \
139                         _timer_init_list(h); \
140                 } \
141         }while(0)
142
143
144 #if 1
145
146 static inline void timer_redist(ticks_t t, struct timer_head *h)
147 {
148         struct timer_ln* tl;
149         struct timer_ln* tmp;
150         
151         timer_foreach_safe(tl, tmp, h){
152                 _timer_dist_tl(tl, tl->expire-t);
153         }
154         /* clear the current list */
155         _timer_init_list(h);
156 }
157
158 static inline void timer_run(ticks_t t)
159 {
160         /* trust the compiler for optimizing */
161         if ((t & H0_MASK)==0){              /*r1*/
162                 if ((t & H1_H0_MASK)==0){        /*r2*/
163                         timer_redist(t, &timer_lst->h2[t>>(H0_BITS+H1_BITS)]);
164                 }
165                 
166                 timer_redist(t, &timer_lst->h1[(t & H1_H0_MASK)>>H0_BITS]);/*r2 >> H0*/
167         }
168         /*
169         DBG("timer_run: ticks %u, expire h0[%u]\n",
170                                                 (unsigned ) t, (unsigned)(t & H0_MASK));*/
171         _timer_mv_expire(&timer_lst->h0[t & H0_MASK]);  /*r1*/
172 }
173 #else
174
175 static inline void timer_lst_mv0(ticks_t t, struct timer_head* h)
176 {
177         struct timer_ln* tl;
178         struct timer_ln* tmp;
179         
180         timer_foreach_safe(tl, tmp, h){
181                         _timer_dist_tl(tl, &timer_lst->h0[tl->expire & H0_MASK]);
182         }
183         /* clear the current list */
184         _timer_init_list(h);
185 }
186
187 static inline void timer_lst_mv1(ticks_t t, struct timer_head* h)
188 {
189         struct timer_ln* tl;
190         struct timer_ln* tmp;
191         
192         timer_foreach_safe(tl, tmp, h){
193                 if ((tl->expire & H0_MASK)==0) /* directly to h0 */
194                         _timer_add_list(tl, &timer_lst->h0[tl->expire & H0_MASK]);
195                 else  /* to h1 */
196                         _timer_add_list(tl, 
197                                                 &timer_lst->h1[(tl->expire & H1_H0_MASK)>>H0_BITS]);
198         }
199         /* clear the current list */
200         _timer_init_list(h);
201 }
202
203
204 /** @brief possible faster version */
205 static inline void timer_run(ticks_t t)
206 {
207         /* trust the compiler for optimizing */
208         if ((t & H0_MASK)==0){              /*r1*/
209                 if ((t & H1_H0_MASK)==0)        /*r2*/
210                         /* just move the list "down" to hash1 */
211                         timer_lst_mv1(&timer_lst->h2[t>>(H0_BITS+H1_BITS)]); 
212                 /* move "down" to hash0 */
213                 timer_lst_mv0(&timer_lst->h1[(t & H1_H0_MASK)>>H0_BITS]);
214         }
215         _timer_mv_expire(t, &timer_lst->h0[t & H0_MASK]);  /*r1*/
216 }
217 #endif
218
219
220
221 #endif