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 */
_timer_dist_tl(struct timer_ln * tl,ticks_t delta)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
timer_redist(ticks_t t,struct timer_head * h)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
timer_run(ticks_t t)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
timer_lst_mv0(ticks_t t,struct timer_head * h)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
timer_lst_mv1(ticks_t t,struct timer_head * h)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 */
timer_run(ticks_t t)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
217