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