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