remove a bunch of useless #include "options.h"
[asterisk/asterisk.git] / main / sched.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2005, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Scheduler Routines (from cheops-NG)
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 #include "asterisk.h"
27
28 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29
30 #ifdef DEBUG_SCHEDULER
31 #define DEBUG(a) do { \
32         if (option_debug) \
33                 DEBUG_M(a) \
34         } while (0)
35 #else
36 #define DEBUG(a) 
37 #endif
38
39 #include <sys/time.h>
40
41 #include "asterisk/sched.h"
42 #include "asterisk/channel.h"
43 #include "asterisk/lock.h"
44 #include "asterisk/utils.h"
45 #include "asterisk/linkedlists.h"
46
47 struct sched {
48         AST_LIST_ENTRY(sched) list;
49         int id;                       /*!< ID number of event */
50         struct timeval when;          /*!< Absolute time event should take place */
51         int resched;                  /*!< When to reschedule */
52         int variable;                 /*!< Use return value from callback to reschedule */
53         const void *data;             /*!< Data */
54         ast_sched_cb callback;        /*!< Callback */
55 };
56
57 struct sched_context {
58         ast_mutex_t lock;
59         unsigned int eventcnt;                  /*!< Number of events processed */
60         unsigned int schedcnt;                  /*!< Number of outstanding schedule events */
61         AST_LIST_HEAD_NOLOCK(, sched) schedq;   /*!< Schedule entry and main queue */
62
63 #ifdef SCHED_MAX_CACHE
64         AST_LIST_HEAD_NOLOCK(, sched) schedc;   /*!< Cache of unused schedule structures and how many */
65         unsigned int schedccnt;
66 #endif
67 };
68
69 struct sched_context *sched_context_create(void)
70 {
71         struct sched_context *tmp;
72
73         if (!(tmp = ast_calloc(1, sizeof(*tmp))))
74                 return NULL;
75
76         ast_mutex_init(&tmp->lock);
77         tmp->eventcnt = 1;
78         
79         return tmp;
80 }
81
82 void sched_context_destroy(struct sched_context *con)
83 {
84         struct sched *s;
85
86         ast_mutex_lock(&con->lock);
87
88 #ifdef SCHED_MAX_CACHE
89         /* Eliminate the cache */
90         while ((s = AST_LIST_REMOVE_HEAD(&con->schedc, list)))
91                 ast_free(s);
92 #endif
93
94         /* And the queue */
95         while ((s = AST_LIST_REMOVE_HEAD(&con->schedq, list)))
96                 ast_free(s);
97         
98         /* And the context */
99         ast_mutex_unlock(&con->lock);
100         ast_mutex_destroy(&con->lock);
101         ast_free(con);
102 }
103
104 static struct sched *sched_alloc(struct sched_context *con)
105 {
106         struct sched *tmp;
107
108         /*
109          * We keep a small cache of schedule entries
110          * to minimize the number of necessary malloc()'s
111          */
112 #ifdef SCHED_MAX_CACHE
113         if ((tmp = AST_LIST_REMOVE_HEAD(&con->schedc, list)))
114                 con->schedccnt--;
115         else
116 #endif
117                 tmp = ast_calloc(1, sizeof(*tmp));
118
119         return tmp;
120 }
121
122 static void sched_release(struct sched_context *con, struct sched *tmp)
123 {
124         /*
125          * Add to the cache, or just free() if we
126          * already have too many cache entries
127          */
128
129 #ifdef SCHED_MAX_CACHE   
130         if (con->schedccnt < SCHED_MAX_CACHE) {
131                 AST_LIST_INSERT_HEAD(&con->schedc, tmp, list);
132                 con->schedccnt++;
133         } else
134 #endif
135                 ast_free(tmp);
136 }
137
138 /*! \brief
139  * Return the number of milliseconds 
140  * until the next scheduled event
141  */
142 int ast_sched_wait(struct sched_context *con)
143 {
144         int ms;
145
146         DEBUG(ast_debug(1, "ast_sched_wait()\n"));
147
148         ast_mutex_lock(&con->lock);
149         if (AST_LIST_EMPTY(&con->schedq)) {
150                 ms = -1;
151         } else {
152                 ms = ast_tvdiff_ms(AST_LIST_FIRST(&con->schedq)->when, ast_tvnow());
153                 if (ms < 0)
154                         ms = 0;
155         }
156         ast_mutex_unlock(&con->lock);
157
158         return ms;
159 }
160
161
162 /*! \brief
163  * Take a sched structure and put it in the
164  * queue, such that the soonest event is
165  * first in the list. 
166  */
167 static void schedule(struct sched_context *con, struct sched *s)
168 {
169          
170         struct sched *cur = NULL;
171         
172         AST_LIST_TRAVERSE_SAFE_BEGIN(&con->schedq, cur, list) {
173                 if (ast_tvcmp(s->when, cur->when) == -1) {
174                         AST_LIST_INSERT_BEFORE_CURRENT(s, list);
175                         break;
176                 }
177         }
178         AST_LIST_TRAVERSE_SAFE_END;
179         if (!cur)
180                 AST_LIST_INSERT_TAIL(&con->schedq, s, list);
181         
182         con->schedcnt++;
183 }
184
185 /*! \brief
186  * given the last event *tv and the offset in milliseconds 'when',
187  * computes the next value,
188  */
189 static int sched_settime(struct timeval *tv, int when)
190 {
191         struct timeval now = ast_tvnow();
192
193         /*ast_debug(1, "TV -> %lu,%lu\n", tv->tv_sec, tv->tv_usec);*/
194         if (ast_tvzero(*tv))    /* not supplied, default to now */
195                 *tv = now;
196         *tv = ast_tvadd(*tv, ast_samp2tv(when, 1000));
197         if (ast_tvcmp(*tv, now) < 0) {
198                 ast_debug(1, "Request to schedule in the past?!?!\n");
199                 *tv = now;
200         }
201         return 0;
202 }
203
204 int ast_sched_replace_variable(int old_id, struct sched_context *con, int when, ast_sched_cb callback, const void *data, int variable)
205 {
206         /* 0 means the schedule item is new; do not delete */
207         if (old_id > 0)
208                 ast_sched_del(con, old_id);
209         return ast_sched_add_variable(con, when, callback, data, variable);
210 }
211
212 /*! \brief
213  * Schedule callback(data) to happen when ms into the future
214  */
215 int ast_sched_add_variable(struct sched_context *con, int when, ast_sched_cb callback, const void *data, int variable)
216 {
217         struct sched *tmp;
218         int res = -1;
219         DEBUG(ast_debug(1, "ast_sched_add()\n"));
220         if (!when) {
221                 ast_log(LOG_NOTICE, "Scheduled event in 0 ms?\n");
222                 return -1;
223         }
224         ast_mutex_lock(&con->lock);
225         if ((tmp = sched_alloc(con))) {
226                 tmp->id = con->eventcnt++;
227                 tmp->callback = callback;
228                 tmp->data = data;
229                 tmp->resched = when;
230                 tmp->variable = variable;
231                 tmp->when = ast_tv(0, 0);
232                 if (sched_settime(&tmp->when, when)) {
233                         sched_release(con, tmp);
234                 } else {
235                         schedule(con, tmp);
236                         res = tmp->id;
237                 }
238         }
239 #ifdef DUMP_SCHEDULER
240         /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
241         if (option_debug)
242                 ast_sched_dump(con);
243 #endif
244         ast_mutex_unlock(&con->lock);
245         return res;
246 }
247
248 int ast_sched_replace(int old_id, struct sched_context *con, int when, ast_sched_cb callback, const void *data)
249 {
250         if (old_id > -1)
251                 ast_sched_del(con, old_id);
252         return ast_sched_add(con, when, callback, data);
253 }
254
255 int ast_sched_add(struct sched_context *con, int when, ast_sched_cb callback, const void *data)
256 {
257         return ast_sched_add_variable(con, when, callback, data, 0);
258 }
259
260 /*! \brief
261  * Delete the schedule entry with number
262  * "id".  It's nearly impossible that there
263  * would be two or more in the list with that
264  * id.
265  */
266 int ast_sched_del(struct sched_context *con, int id)
267 {
268         struct sched *s;
269
270         DEBUG(ast_debug(1, "ast_sched_del()\n"));
271         
272         ast_mutex_lock(&con->lock);
273         AST_LIST_TRAVERSE_SAFE_BEGIN(&con->schedq, s, list) {
274                 if (s->id == id) {
275                         AST_LIST_REMOVE_CURRENT(list);
276                         con->schedcnt--;
277                         sched_release(con, s);
278                         break;
279                 }
280         }
281         AST_LIST_TRAVERSE_SAFE_END;
282
283 #ifdef DUMP_SCHEDULER
284         /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
285         if (option_debug)
286                 ast_sched_dump(con);
287 #endif
288         ast_mutex_unlock(&con->lock);
289
290         if (!s) {
291                 ast_debug(1, "Attempted to delete nonexistent schedule entry %d!\n", id);
292 #ifdef DO_CRASH
293                 CRASH;
294 #endif
295                 return -1;
296         }
297         
298         return 0;
299 }
300
301 /*! \brief Dump the contents of the scheduler to LOG_DEBUG */
302 void ast_sched_dump(const struct sched_context *con)
303 {
304         struct sched *q;
305         struct timeval tv = ast_tvnow();
306 #ifdef SCHED_MAX_CACHE
307         ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d Cache)\n", con->schedcnt, con->eventcnt - 1, con->schedccnt);
308 #else
309         ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total)\n", con->schedcnt, con->eventcnt - 1);
310 #endif
311
312         ast_debug(1, "=============================================================\n");
313         ast_debug(1, "|ID    Callback          Data              Time  (sec:ms)   |\n");
314         ast_debug(1, "+-----+-----------------+-----------------+-----------------+\n");
315         AST_LIST_TRAVERSE(&con->schedq, q, list) {
316                 struct timeval delta = ast_tvsub(q->when, tv);
317
318                 ast_debug(1, "|%.4d | %-15p | %-15p | %.6ld : %.6ld |\n", 
319                         q->id,
320                         q->callback,
321                         q->data,
322                         delta.tv_sec,
323                         (long int)delta.tv_usec);
324         }
325         ast_debug(1, "=============================================================\n");
326 }
327
328 /*! \brief
329  * Launch all events which need to be run at this time.
330  */
331 int ast_sched_runq(struct sched_context *con)
332 {
333         struct sched *current;
334         struct timeval tv;
335         int numevents;
336         int res;
337
338         DEBUG(ast_debug(1, "ast_sched_runq()\n"));
339                 
340         ast_mutex_lock(&con->lock);
341
342         for (numevents = 0; !AST_LIST_EMPTY(&con->schedq); numevents++) {
343                 /* schedule all events which are going to expire within 1ms.
344                  * We only care about millisecond accuracy anyway, so this will
345                  * help us get more than one event at one time if they are very
346                  * close together.
347                  */
348                 tv = ast_tvadd(ast_tvnow(), ast_tv(0, 1000));
349                 if (ast_tvcmp(AST_LIST_FIRST(&con->schedq)->when, tv) != -1)
350                         break;
351                 
352                 current = AST_LIST_REMOVE_HEAD(&con->schedq, list);
353                 con->schedcnt--;
354
355                 /*
356                  * At this point, the schedule queue is still intact.  We
357                  * have removed the first event and the rest is still there,
358                  * so it's permissible for the callback to add new events, but
359                  * trying to delete itself won't work because it isn't in
360                  * the schedule queue.  If that's what it wants to do, it 
361                  * should return 0.
362                  */
363                         
364                 ast_mutex_unlock(&con->lock);
365                 res = current->callback(current->data);
366                 ast_mutex_lock(&con->lock);
367                         
368                 if (res) {
369                         /*
370                          * If they return non-zero, we should schedule them to be
371                          * run again.
372                          */
373                         if (sched_settime(&current->when, current->variable? res : current->resched)) {
374                                 sched_release(con, current);
375                         } else
376                                 schedule(con, current);
377                 } else {
378                         /* No longer needed, so release it */
379                         sched_release(con, current);
380                 }
381         }
382
383         ast_mutex_unlock(&con->lock);
384         
385         return numevents;
386 }
387
388 long ast_sched_when(struct sched_context *con,int id)
389 {
390         struct sched *s;
391         long secs = -1;
392         DEBUG(ast_debug(1, "ast_sched_when()\n"));
393
394         ast_mutex_lock(&con->lock);
395         AST_LIST_TRAVERSE(&con->schedq, s, list) {
396                 if (s->id == id)
397                         break;
398         }
399         if (s) {
400                 struct timeval now = ast_tvnow();
401                 secs = s->when.tv_sec - now.tv_sec;
402         }
403         ast_mutex_unlock(&con->lock);
404         
405         return secs;
406 }