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