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