6744a7f99faf18f734237f84cde8a1be2e135999
[asterisk/asterisk.git] / sched.c
1 /*
2  * Asterisk
3  * 
4  * Mark Spencer <markster@marko.net>
5  *
6  * Copyright(C) Mark Spencer
7  * 
8  * Distributed under the terms of the GNU General Public License (GPL) Version 2
9  *
10  * Scheduler Routines (form cheops-NG)
11  *
12  */
13
14 #ifdef DEBUG_SCHEDULER
15 #define DEBUG(a) DEBUG_M(a)
16 #else
17 #define DEBUG(a) 
18 #endif
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <sys/time.h>
23 #include <unistd.h>
24 #include <asterisk/sched.h>
25 #include <asterisk/logger.h>
26 #include <asterisk/channel.h>
27
28 /* Determine if a is sooner than b */
29 #define SOONER(a,b) (((b).tv_sec > (a).tv_sec) || \
30                                          (((b).tv_sec == (a).tv_sec) && ((b).tv_usec > (a).tv_usec)))
31
32 struct sched {
33         struct sched *next;                             /* Next event in the list */
34         int id;                                                 /* ID number of event */
35         struct timeval when;                    /* Absolute time event should take place */
36         int resched;                                    /* When to reschedule */
37         void *data;                                     /* Data */
38         ast_sched_cb callback;          /* Callback */
39 };
40
41 struct sched_context {
42         /* Number of events processed */
43         int eventcnt;
44
45         /* Number of outstanding schedule events */
46         int schedcnt;
47
48         /* Schedule entry and main queue */
49         struct sched *schedq;
50
51 #ifdef SCHED_MAX_CACHE
52         /* Cache of unused schedule structures and how many */
53         struct sched *schedc;
54         int schedccnt;
55 #endif
56 };
57
58 struct sched_context *sched_context_create(void)
59 {
60         struct sched_context *tmp;
61         tmp = malloc(sizeof(struct sched_context));
62         if (tmp) {
63                 tmp->eventcnt = 1;
64                 tmp->schedcnt = 0;
65                 tmp->schedq = NULL;
66 #ifdef SCHED_MAX_CACHE
67                 tmp->schedc = NULL;
68                 tmp->schedccnt = 0;
69 #endif
70         }
71         return tmp;
72 }
73
74 void sched_context_destroy(struct sched_context *con)
75 {
76         struct sched *s, *sl;
77 #ifdef SCHED_MAX_CACHE
78         /* Eliminate the cache */
79         s = con->schedc;
80         while(s) {
81                 sl = s;
82                 s = s->next;
83                 free(sl);
84         }
85 #endif
86         /* And the queue */
87         s = con->schedq;
88         while(s) {
89                 sl = s;
90                 s = s->next;
91                 free(sl);
92         }
93         /* And the context */
94         free(con);
95 }
96
97 static struct sched *sched_alloc(struct sched_context *con)
98 {
99         /*
100          * We keep a small cache of schedule entries
101          * to minimize the number of necessary malloc()'s
102          */
103         struct sched *tmp;
104 #ifdef SCHED_MAX_CACHE
105         if (con->schedc) {
106                 tmp = con->schedc;
107                 con->schedc = con->schedc->next;
108                 con->schedccnt--;
109         } else
110 #endif
111                 tmp = malloc(sizeof(struct sched));
112         return tmp;
113 }
114
115 static void sched_release(struct sched_context *con, struct sched *tmp)
116 {
117         /*
118          * Add to the cache, or just free() if we
119          * already have too many cache entries
120          */
121
122 #ifdef SCHED_MAX_CACHE   
123         if (con->schedccnt < SCHED_MAX_CACHE) {
124                 tmp->next = con->schedc;
125                 con->schedc = tmp;
126                 con->schedccnt++;
127         } else
128 #endif
129                 free(tmp);
130 }
131
132 int ast_sched_wait(struct sched_context *con)
133 {
134         /*
135          * Return the number of milliseconds 
136          * until the next scheduled event
137          */
138         struct timeval tv;
139         int ms;
140         DEBUG(ast_log(LOG_DEBUG, "ast_sched_wait()\n"));
141         if (!con->schedq)
142                 return -1;
143         if (gettimeofday(&tv, NULL) < 0) {
144                 /* This should never happen */
145                 return 0;
146         };
147         ms = (con->schedq->when.tv_sec - tv.tv_sec) * 1000;
148         ms += (con->schedq->when.tv_usec - tv.tv_usec) / 1000;
149         if (ms < 0)
150                 ms = 0;
151         return ms;
152         
153 }
154
155
156 static void schedule(struct sched_context *con, struct sched *s)
157 {
158         /*
159          * Take a sched structure and put it in the
160          * queue, such that the soonest event is
161          * first in the list. 
162          */
163          
164         struct sched *last=NULL;
165         struct sched *current=con->schedq;
166         while(current) {
167                 if (SOONER(s->when, current->when))
168                         break;
169                 last = current;
170                 current = current->next;
171         }
172         /* Insert this event into the schedule */
173         s->next = current;
174         if (last) 
175                 last->next = s;
176         else
177                 con->schedq = s;
178         con->schedcnt++;
179 }
180
181 static inline int sched_settime(struct timeval *tv, int when)
182 {
183         struct timeval tv_tmp;
184         long error_sec, error_usec;
185
186         if (gettimeofday(&tv_tmp, NULL) < 0) {
187                 /* This shouldn't ever happen, but let's be sure */
188                 ast_log(LOG_NOTICE, "gettimeofday() failed!\n");
189                 return -1;
190         }
191         /*ast_log(LOG_DEBUG, "TV -> %lu,%lu\n", tv->tv_sec, tv->tv_usec);*/
192         if (((unsigned long)(tv->tv_sec) > 0)&&((unsigned long)(tv->tv_usec) > 0)) {
193                 if ((unsigned long)(tv_tmp.tv_usec) < (unsigned long)(tv->tv_usec)) {
194                         tv_tmp.tv_usec += 1000000;
195                         tv_tmp.tv_sec -= 1;
196                 }
197                 error_sec = (unsigned long)(tv_tmp.tv_sec) - (unsigned long)(tv->tv_sec);
198                 error_usec = (unsigned long)(tv_tmp.tv_usec) - (unsigned long)(tv->tv_usec);
199         } else {
200                 /*ast_log(LOG_DEBUG, "Initializing error\n");*/
201                 error_sec = 0;
202                 error_usec = 0;
203         }
204         /*ast_log(LOG_DEBUG, "ERROR -> %lu,%lu\n", error_sec, error_usec);*/
205         if (error_sec * 1000 + error_usec / 1000 < when) {
206                 tv->tv_sec = tv_tmp.tv_sec + (when/1000 - error_sec);
207                 tv->tv_usec = tv_tmp.tv_usec + ((when % 1000) * 1000 - error_usec);
208         } else {
209                 ast_log(LOG_NOTICE, "Request to schedule in the past?!?!\n");
210                 tv->tv_sec = tv_tmp.tv_sec;
211                 tv->tv_usec = tv_tmp.tv_usec;
212         }
213         if (tv->tv_usec > 1000000) {
214                 tv->tv_sec++;
215                 tv->tv_usec-= 1000000;
216         }
217         return 0;
218 }
219
220 int ast_sched_add(struct sched_context *con, int when, ast_sched_cb callback, void *data)
221 {
222         /*
223          * Schedule callback(data) to happen when ms into the future
224          */
225         struct sched *tmp;
226         DEBUG(ast_log(LOG_DEBUG, "ast_sched_add()\n"));
227         if (!when) {
228                 ast_log(LOG_NOTICE, "Scheduled event in 0 ms?");
229                 return -1;
230         }
231         if ((tmp = sched_alloc(con))) {
232                 tmp->id = con->eventcnt++;
233                 tmp->callback = callback;
234                 tmp->data = data;
235                 tmp->resched = when;
236                 tmp->when.tv_sec = 0;
237                 tmp->when.tv_usec = 0;
238                 if (sched_settime(&tmp->when, when)) {
239                         sched_release(con, tmp);
240                         return -1;
241                 } else
242                         schedule(con, tmp);
243         } else 
244                 return -1;
245         return tmp->id;
246 }
247
248 int ast_sched_del(struct sched_context *con, int id)
249 {
250         /*
251          * Delete the schedule entry with number
252          * "id".  It's nearly impossible that there
253          * would be two or more in the list with that
254          * id.
255          */
256         struct sched *last=NULL, *s;
257         DEBUG(ast_log(LOG_DEBUG, "ast_sched_del()\n"));
258         s = con->schedq;
259         while(s) {
260                 if (s->id == id) {
261                         if (last)
262                                 last->next = s->next;
263                         else
264                                 con->schedq = s->next;
265                         con->schedcnt--;
266                         sched_release(con, s);
267                         return 0;
268                 }
269                 last = s;
270                 s = s->next;
271         }
272         ast_log(LOG_NOTICE, "Attempted to delete non-existant schedule entry %d!\n", id);
273 #ifdef DO_CRASH
274         CRASH;
275 #endif
276         return -1;
277 }
278
279 void ast_sched_dump(struct sched_context *con)
280 {
281         /*
282          * Dump the contents of the scheduler to
283          * stderr
284          */
285         struct sched *q;
286         struct timeval tv;
287         time_t s, ms;
288         gettimeofday(&tv, NULL);
289 #ifdef SCHED_MAX_CACHE
290         ast_log(LOG_DEBUG, "Asterisk Schedule Dump (%d in Q, %d Total, %d Cache)\n", 
291                                                         con-> schedcnt, con->eventcnt - 1, con->schedccnt);
292 #else
293         ast_log(LOG_DEBUG, "Asterisk Schedule Dump (%d in Q, %d Total)\n",
294                                                         con-> schedcnt, con->eventcnt - 1);
295 #endif
296
297         ast_log(LOG_DEBUG, "=================================================\n");
298         ast_log(LOG_DEBUG, "|ID    Callback    Data        Time  (sec:ms)   |\n");
299         ast_log(LOG_DEBUG, "+-----+-----------+-----------+-----------------+\n");
300         q = con->schedq;
301         while(q) {
302                 s =  q->when.tv_sec - tv.tv_sec;
303                 ms = q->when.tv_usec - tv.tv_usec;
304                 if (ms < 0) {
305                         ms += 1000000;
306                         s--;
307                 }
308                 ast_log(LOG_DEBUG, "|%.4d | %p | %p | %.6ld : %.6ld |\n", 
309                                 q->id,
310                                 q->callback,
311                                 q->data,
312                                 s,
313                                 ms);
314                 q=q->next;
315         }
316         ast_log(LOG_DEBUG, "=================================================\n");
317         
318 }
319
320 int ast_sched_runq(struct sched_context *con)
321 {
322         /*
323          * Launch all events which need to be run at this time.
324          */
325         struct sched *current;
326         struct timeval tv;
327         int x=0;
328         DEBUG(ast_log(LOG_DEBUG, "ast_sched_runq()\n"));
329                 
330         for(;;) {
331                 if (!con->schedq)
332                         break;
333                 if (gettimeofday(&tv, NULL)) {
334                         /* This should never happen */
335                         ast_log(LOG_NOTICE, "gettimeofday() failed!\n");
336                         return 0;
337                 }
338                 /* We only care about millisecond accuracy anyway, so this will
339                    help us get more than one event at one time if they are very
340                    close together. */
341                 tv.tv_usec += 1000;
342                 if (SOONER(con->schedq->when, tv)) {
343                         current = con->schedq;
344                         con->schedq = con->schedq->next;
345                         con->schedcnt--;
346
347                         /*
348                          * At this point, the schedule queue is still intact.  We
349                          * have removed the first event and the rest is still there,
350                          * so it's permissible for the callback to add new events, but
351                          * trying to delete itself won't work because it isn't in
352                          * the schedule queue.  If that's what it wants to do, it 
353                          * should return 0.
354                          */
355                         if (current->callback(current->data)) {
356                                 /*
357                                  * If they return non-zero, we should schedule them to be
358                                  * run again.
359                                  */
360                                 if (sched_settime(&current->when, current->resched)) {
361                                         sched_release(con, current);
362                                 } else
363                                         schedule(con, current);
364                         } else {
365                                 /* No longer needed, so release it */
366                                 sched_release(con, current);
367                         }
368                         x++;
369                 } else
370                         break;
371         }
372         return x;
373 }