2 * Asterisk -- An open source telephony toolkit.
4 * Copyright (C) 1999 - 2005, Digium, Inc.
6 * Mark Spencer <markster@digium.com>
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.
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.
21 * \brief Scheduler Routines (from cheops-NG)
23 * \author Mark Spencer <markster@digium.com>
28 ASTERISK_FILE_VERSION(__FILE__
, "$Revision$")
30 #ifdef DEBUG_SCHEDULER
31 #define DEBUG(a) do { \
41 #include "asterisk/sched.h"
42 #include "asterisk/channel.h"
43 #include "asterisk/lock.h"
44 #include "asterisk/utils.h"
45 #include "asterisk/linkedlists.h"
46 #include "asterisk/dlinkedlists.h"
47 #include "asterisk/hashtab.h"
50 AST_DLLIST_ENTRY(sched
) list
;
51 int id
; /*!< ID number of event */
52 struct timeval when
; /*!< Absolute time event should take place */
53 int resched
; /*!< When to reschedule */
54 int variable
; /*!< Use return value from callback to reschedule */
55 const void *data
; /*!< Data */
56 ast_sched_cb callback
; /*!< Callback */
59 struct sched_context
{
61 unsigned int eventcnt
; /*!< Number of events processed */
62 unsigned int schedcnt
; /*!< Number of outstanding schedule events */
63 unsigned int highwater
; /*!< highest count so far */
64 AST_DLLIST_HEAD_NOLOCK(, sched
) schedq
; /*!< Schedule entry and main queue */
65 struct ast_hashtab
*schedq_ht
; /*!< hash table for fast searching */
67 #ifdef SCHED_MAX_CACHE
68 AST_LIST_HEAD_NOLOCK(, sched
) schedc
; /*!< Cache of unused schedule structures and how many */
69 unsigned int schedccnt
;
74 /* hash routines for sched */
76 static int sched_cmp(const void *a
, const void *b
)
78 const struct sched
*as
= a
;
79 const struct sched
*bs
= b
;
80 return as
->id
!= bs
->id
; /* return 0 on a match like strcmp would */
83 static unsigned int sched_hash(const void *obj
)
85 const struct sched
*s
= obj
;
86 unsigned int h
= s
->id
;
90 struct sched_context
*sched_context_create(void)
92 struct sched_context
*tmp
;
94 if (!(tmp
= ast_calloc(1, sizeof(*tmp
))))
97 ast_mutex_init(&tmp
->lock
);
100 tmp
->schedq_ht
= ast_hashtab_create(23, sched_cmp
, ast_hashtab_resize_java
, ast_hashtab_newsize_java
, sched_hash
, 1);
105 void sched_context_destroy(struct sched_context
*con
)
109 ast_mutex_lock(&con
->lock
);
111 #ifdef SCHED_MAX_CACHE
112 /* Eliminate the cache */
113 while ((s
= AST_LIST_REMOVE_HEAD(&con
->schedc
, list
)))
118 while ((s
= AST_DLLIST_REMOVE_HEAD(&con
->schedq
, list
)))
121 ast_hashtab_destroy(con
->schedq_ht
, NULL
);
122 con
->schedq_ht
= NULL
;
124 /* And the context */
125 ast_mutex_unlock(&con
->lock
);
126 ast_mutex_destroy(&con
->lock
);
130 static struct sched
*sched_alloc(struct sched_context
*con
)
135 * We keep a small cache of schedule entries
136 * to minimize the number of necessary malloc()'s
138 #ifdef SCHED_MAX_CACHE
139 if ((tmp
= AST_LIST_REMOVE_HEAD(&con
->schedc
, list
)))
143 tmp
= ast_calloc(1, sizeof(*tmp
));
148 static void sched_release(struct sched_context
*con
, struct sched
*tmp
)
151 * Add to the cache, or just free() if we
152 * already have too many cache entries
155 #ifdef SCHED_MAX_CACHE
156 if (con
->schedccnt
< SCHED_MAX_CACHE
) {
157 AST_LIST_INSERT_HEAD(&con
->schedc
, tmp
, list
);
165 * Return the number of milliseconds
166 * until the next scheduled event
168 int ast_sched_wait(struct sched_context
*con
)
172 DEBUG(ast_debug(1, "ast_sched_wait()\n"));
174 ast_mutex_lock(&con
->lock
);
175 if (AST_DLLIST_EMPTY(&con
->schedq
)) {
178 ms
= ast_tvdiff_ms(AST_DLLIST_FIRST(&con
->schedq
)->when
, ast_tvnow());
182 ast_mutex_unlock(&con
->lock
);
189 * Take a sched structure and put it in the
190 * queue, such that the soonest event is
193 static void schedule(struct sched_context
*con
, struct sched
*s
)
195 struct sched
*cur
= NULL
;
199 struct sched
*first
= AST_DLLIST_FIRST(&con
->schedq
);
200 struct sched
*last
= AST_DLLIST_LAST(&con
->schedq
);
203 df
= ast_tvdiff_us(s
->when
, first
->when
);
205 de
= ast_tvdiff_us(s
->when
, last
->when
);
213 AST_DLLIST_TRAVERSE(&con
->schedq
, cur
, list
) {
214 if (ast_tvcmp(s
->when
, cur
->when
) == -1) {
215 AST_DLLIST_INSERT_BEFORE(&con
->schedq
, cur
, s
, list
);
220 AST_DLLIST_INSERT_TAIL(&con
->schedq
, s
, list
);
223 AST_DLLIST_TRAVERSE_BACKWARDS(&con
->schedq
, cur
, list
) {
224 if (ast_tvcmp(s
->when
, cur
->when
) == 1) {
225 AST_DLLIST_INSERT_AFTER(&con
->schedq
, cur
, s
, list
);
230 AST_DLLIST_INSERT_HEAD(&con
->schedq
, s
, list
);
234 ret
= ast_hashtab_insert_safe(con
->schedq_ht
, s
);
236 ast_log(LOG_WARNING
,"Schedule Queue entry %d is already in table!\n",s
->id
);
240 if (con
->schedcnt
> con
->highwater
)
241 con
->highwater
= con
->schedcnt
;
245 * given the last event *tv and the offset in milliseconds 'when',
246 * computes the next value,
248 static int sched_settime(struct timeval
*tv
, int when
)
250 struct timeval now
= ast_tvnow();
252 /*ast_debug(1, "TV -> %lu,%lu\n", tv->tv_sec, tv->tv_usec);*/
253 if (ast_tvzero(*tv
)) /* not supplied, default to now */
255 *tv
= ast_tvadd(*tv
, ast_samp2tv(when
, 1000));
256 if (ast_tvcmp(*tv
, now
) < 0) {
257 ast_debug(1, "Request to schedule in the past?!?!\n");
263 int ast_sched_replace_variable(int old_id
, struct sched_context
*con
, int when
, ast_sched_cb callback
, const void *data
, int variable
)
265 /* 0 means the schedule item is new; do not delete */
267 AST_SCHED_DEL(con
, old_id
);
269 return ast_sched_add_variable(con
, when
, callback
, data
, variable
);
273 * Schedule callback(data) to happen when ms into the future
275 int ast_sched_add_variable(struct sched_context
*con
, int when
, ast_sched_cb callback
, const void *data
, int variable
)
279 DEBUG(ast_debug(1, "ast_sched_add()\n"));
281 ast_log(LOG_NOTICE
, "Scheduled event in 0 ms?\n");
284 ast_mutex_lock(&con
->lock
);
285 if ((tmp
= sched_alloc(con
))) {
286 tmp
->id
= con
->eventcnt
++;
287 tmp
->callback
= callback
;
290 tmp
->variable
= variable
;
291 tmp
->when
= ast_tv(0, 0);
292 if (sched_settime(&tmp
->when
, when
)) {
293 sched_release(con
, tmp
);
299 #ifdef DUMP_SCHEDULER
300 /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
304 ast_mutex_unlock(&con
->lock
);
308 int ast_sched_replace(int old_id
, struct sched_context
*con
, int when
, ast_sched_cb callback
, const void *data
)
311 AST_SCHED_DEL(con
, old_id
);
313 return ast_sched_add(con
, when
, callback
, data
);
316 int ast_sched_add(struct sched_context
*con
, int when
, ast_sched_cb callback
, const void *data
)
318 return ast_sched_add_variable(con
, when
, callback
, data
, 0);
321 const void *ast_sched_find_data(struct sched_context
*con
, int id
)
323 struct sched tmp
,*res
;
325 res
= ast_hashtab_lookup(con
->schedq_ht
, &tmp
);
332 * Delete the schedule entry with number
333 * "id". It's nearly impossible that there
334 * would be two or more in the list with that
337 int ast_sched_del(struct sched_context
*con
, int id
)
339 struct sched
*s
, tmp
;
341 DEBUG(ast_debug(1, "ast_sched_del(%d)\n", id
));
343 ast_mutex_lock(&con
->lock
);
345 /* OK, this is the heart of the sched performance upgrade.
346 If we have 4700 peers, we can have 4700+ entries in the
347 schedq list. searching this would take time. So, I add a
348 hashtab to the context to keep track of each entry, by id.
349 I also leave the linked list alone, almost, -- I implement
350 a doubly-linked list instead, because it would do little good
351 to look up the id in a hashtab, and then have to run thru
352 a couple thousand entries to remove it from the schedq list! */
354 s
= ast_hashtab_lookup(con
->schedq_ht
, &tmp
);
356 struct sched
*x
= AST_DLLIST_REMOVE(&con
->schedq
, s
, list
);
359 ast_log(LOG_WARNING
,"sched entry %d not in the schedq list?\n", s
->id
);
361 if (!ast_hashtab_remove_this_object(con
->schedq_ht
, s
))
362 ast_log(LOG_WARNING
,"Found sched entry %d, then couldn't remove it?\n", s
->id
);
364 sched_release(con
, s
);
367 #ifdef DUMP_SCHEDULER
368 /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
372 ast_mutex_unlock(&con
->lock
);
375 ast_debug(1, "Attempted to delete nonexistent schedule entry %d!\n", id
);
384 char *ast_sched_report(struct sched_context
*con
, char *buf
, int bufsiz
, struct ast_cb_names
*cbnames
)
389 ast_sched_cb xxx
= NULL
;
392 sprintf(buf
, " Highwater = %d\n schedcnt = %d\n", con
->highwater
, con
->schedcnt
);
393 countlist
= ast_calloc(sizeof(int),cbnames
->numassocs
+1);
395 AST_DLLIST_TRAVERSE(&con
->schedq
, cur
, list
) {
396 /* match the callback to the cblist */
397 for (i
=0;i
<cbnames
->numassocs
;i
++) {
398 if (cur
->callback
== cbnames
->cblist
[i
])
401 if (i
< cbnames
->numassocs
)
405 countlist
[cbnames
->numassocs
]++;
408 for (i
=0;i
<cbnames
->numassocs
;i
++) {
409 sprintf(buf2
," %s : %d\n", cbnames
->list
[i
], countlist
[i
]);
412 sprintf(buf2
," <unknown:%p> : %d\n", xxx
, countlist
[cbnames
->numassocs
]);
419 /*! \brief Dump the contents of the scheduler to LOG_DEBUG */
420 void ast_sched_dump(const struct sched_context
*con
)
423 struct timeval tv
= ast_tvnow();
424 #ifdef SCHED_MAX_CACHE
425 ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d Cache, %d high-water)\n", con
->schedcnt
, con
->eventcnt
- 1, con
->schedccnt
, con
->highwater
);
427 ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d high-water)\n", con
->schedcnt
, con
->eventcnt
- 1, con
->highwater
);
430 ast_debug(1, "=============================================================\n");
431 ast_debug(1, "|ID Callback Data Time (sec:ms) |\n");
432 ast_debug(1, "+-----+-----------------+-----------------+-----------------+\n");
433 AST_DLLIST_TRAVERSE(&con
->schedq
, q
, list
) {
434 struct timeval delta
= ast_tvsub(q
->when
, tv
);
436 ast_debug(1, "|%.4d | %-15p | %-15p | %.6ld : %.6ld |\n",
441 (long int)delta
.tv_usec
);
443 ast_debug(1, "=============================================================\n");
448 * Launch all events which need to be run at this time.
450 int ast_sched_runq(struct sched_context
*con
)
452 struct sched
*current
;
457 DEBUG(ast_debug(1, "ast_sched_runq()\n"));
459 ast_mutex_lock(&con
->lock
);
461 for (numevents
= 0; !AST_DLLIST_EMPTY(&con
->schedq
); numevents
++) {
462 /* schedule all events which are going to expire within 1ms.
463 * We only care about millisecond accuracy anyway, so this will
464 * help us get more than one event at one time if they are very
467 tv
= ast_tvadd(ast_tvnow(), ast_tv(0, 1000));
468 if (ast_tvcmp(AST_DLLIST_FIRST(&con
->schedq
)->when
, tv
) != -1)
471 current
= AST_DLLIST_REMOVE_HEAD(&con
->schedq
, list
);
472 if (!ast_hashtab_remove_this_object(con
->schedq_ht
, current
))
473 ast_log(LOG_ERROR
,"Sched entry %d was in the schedq list but not in the hashtab???\n", current
->id
);
478 * At this point, the schedule queue is still intact. We
479 * have removed the first event and the rest is still there,
480 * so it's permissible for the callback to add new events, but
481 * trying to delete itself won't work because it isn't in
482 * the schedule queue. If that's what it wants to do, it
486 ast_mutex_unlock(&con
->lock
);
487 res
= current
->callback(current
->data
);
488 ast_mutex_lock(&con
->lock
);
492 * If they return non-zero, we should schedule them to be
495 if (sched_settime(¤t
->when
, current
->variable
? res
: current
->resched
)) {
496 sched_release(con
, current
);
498 schedule(con
, current
);
500 /* No longer needed, so release it */
501 sched_release(con
, current
);
505 ast_mutex_unlock(&con
->lock
);
510 long ast_sched_when(struct sched_context
*con
,int id
)
512 struct sched
*s
, tmp
;
514 DEBUG(ast_debug(1, "ast_sched_when()\n"));
516 ast_mutex_lock(&con
->lock
);
518 /* these next 2 lines replace a lookup loop */
520 s
= ast_hashtab_lookup(con
->schedq_ht
, &tmp
);
523 struct timeval now
= ast_tvnow();
524 secs
= s
->when
.tv_sec
- now
.tv_sec
;
526 ast_mutex_unlock(&con
->lock
);