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