Wed Aug 18 22:33:56 2010

Asterisk developer's documentation


sched.c

Go to the documentation of this file.
00001 /*
00002  * Asterisk -- An open source telephony toolkit.
00003  *
00004  * Copyright (C) 1999 - 2005, Digium, Inc.
00005  *
00006  * Mark Spencer <markster@digium.com>
00007  *
00008  * See http://www.asterisk.org for more information about
00009  * the Asterisk project. Please do not directly contact
00010  * any of the maintainers of this project for assistance;
00011  * the project provides a web site, mailing lists and IRC
00012  * channels for your use.
00013  *
00014  * This program is free software, distributed under the terms of
00015  * the GNU General Public License Version 2. See the LICENSE file
00016  * at the top of the source tree.
00017  */
00018 
00019 /*! \file
00020  *
00021  * \brief Scheduler Routines (from cheops-NG)
00022  *
00023  * \author Mark Spencer <markster@digium.com>
00024  */
00025 
00026 #include "asterisk.h"
00027 
00028 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 244553 $")
00029 
00030 #ifdef DEBUG_SCHEDULER
00031 #define DEBUG(a) do { \
00032    if (option_debug) \
00033       DEBUG_M(a) \
00034    } while (0)
00035 #else
00036 #define DEBUG(a) 
00037 #endif
00038 
00039 #include <sys/time.h>
00040 
00041 #include "asterisk/sched.h"
00042 #include "asterisk/channel.h"
00043 #include "asterisk/lock.h"
00044 #include "asterisk/utils.h"
00045 #include "asterisk/linkedlists.h"
00046 #include "asterisk/dlinkedlists.h"
00047 #include "asterisk/hashtab.h"
00048 
00049 struct sched {
00050    AST_DLLIST_ENTRY(sched) list;
00051    int id;                       /*!< ID number of event */
00052    struct timeval when;          /*!< Absolute time event should take place */
00053    int resched;                  /*!< When to reschedule */
00054    int variable;                 /*!< Use return value from callback to reschedule */
00055    const void *data;             /*!< Data */
00056    ast_sched_cb callback;        /*!< Callback */
00057 };
00058 
00059 struct sched_context {
00060    ast_mutex_t lock;
00061    unsigned int eventcnt;                  /*!< Number of events processed */
00062    unsigned int schedcnt;                  /*!< Number of outstanding schedule events */
00063    unsigned int highwater;             /*!< highest count so far */
00064    AST_DLLIST_HEAD_NOLOCK(, sched) schedq;   /*!< Schedule entry and main queue */
00065    struct ast_hashtab *schedq_ht;             /*!< hash table for fast searching */
00066 
00067 #ifdef SCHED_MAX_CACHE
00068    AST_LIST_HEAD_NOLOCK(, sched) schedc;   /*!< Cache of unused schedule structures and how many */
00069    unsigned int schedccnt;
00070 #endif
00071 };
00072 
00073 
00074 /* hash routines for sched */
00075 
00076 static int sched_cmp(const void *a, const void *b)
00077 {
00078    const struct sched *as = a;
00079    const struct sched *bs = b;
00080    return as->id != bs->id; /* return 0 on a match like strcmp would */
00081 }
00082 
00083 static unsigned int sched_hash(const void *obj)
00084 {
00085    const struct sched *s = obj;
00086    unsigned int h = s->id;
00087    return h;
00088 }
00089 
00090 struct sched_context *sched_context_create(void)
00091 {
00092    struct sched_context *tmp;
00093 
00094    if (!(tmp = ast_calloc(1, sizeof(*tmp))))
00095       return NULL;
00096 
00097    ast_mutex_init(&tmp->lock);
00098    tmp->eventcnt = 1;
00099    
00100    tmp->schedq_ht = ast_hashtab_create(23, sched_cmp, ast_hashtab_resize_java, ast_hashtab_newsize_java, sched_hash, 1);
00101    
00102    return tmp;
00103 }
00104 
00105 void sched_context_destroy(struct sched_context *con)
00106 {
00107    struct sched *s;
00108 
00109    ast_mutex_lock(&con->lock);
00110 
00111 #ifdef SCHED_MAX_CACHE
00112    /* Eliminate the cache */
00113    while ((s = AST_LIST_REMOVE_HEAD(&con->schedc, list)))
00114       ast_free(s);
00115 #endif
00116 
00117    /* And the queue */
00118    while ((s = AST_DLLIST_REMOVE_HEAD(&con->schedq, list)))
00119       ast_free(s);
00120 
00121    ast_hashtab_destroy(con->schedq_ht, NULL);
00122    con->schedq_ht = NULL;
00123    
00124    /* And the context */
00125    ast_mutex_unlock(&con->lock);
00126    ast_mutex_destroy(&con->lock);
00127    ast_free(con);
00128 }
00129 
00130 static struct sched *sched_alloc(struct sched_context *con)
00131 {
00132    struct sched *tmp;
00133 
00134    /*
00135     * We keep a small cache of schedule entries
00136     * to minimize the number of necessary malloc()'s
00137     */
00138 #ifdef SCHED_MAX_CACHE
00139    if ((tmp = AST_LIST_REMOVE_HEAD(&con->schedc, list)))
00140       con->schedccnt--;
00141    else
00142 #endif
00143       tmp = ast_calloc(1, sizeof(*tmp));
00144 
00145    return tmp;
00146 }
00147 
00148 static void sched_release(struct sched_context *con, struct sched *tmp)
00149 {
00150    /*
00151     * Add to the cache, or just free() if we
00152     * already have too many cache entries
00153     */
00154 
00155 #ifdef SCHED_MAX_CACHE   
00156    if (con->schedccnt < SCHED_MAX_CACHE) {
00157       AST_LIST_INSERT_HEAD(&con->schedc, tmp, list);
00158       con->schedccnt++;
00159    } else
00160 #endif
00161       ast_free(tmp);
00162 }
00163 
00164 /*! \brief
00165  * Return the number of milliseconds 
00166  * until the next scheduled event
00167  */
00168 int ast_sched_wait(struct sched_context *con)
00169 {
00170    int ms;
00171 
00172    DEBUG(ast_debug(1, "ast_sched_wait()\n"));
00173 
00174    ast_mutex_lock(&con->lock);
00175    if (AST_DLLIST_EMPTY(&con->schedq)) {
00176       ms = -1;
00177    } else {
00178       ms = ast_tvdiff_ms(AST_DLLIST_FIRST(&con->schedq)->when, ast_tvnow());
00179       if (ms < 0)
00180          ms = 0;
00181    }
00182    ast_mutex_unlock(&con->lock);
00183 
00184    return ms;
00185 }
00186 
00187 
00188 /*! \brief
00189  * Take a sched structure and put it in the
00190  * queue, such that the soonest event is
00191  * first in the list. 
00192  */
00193 static void schedule(struct sched_context *con, struct sched *s)
00194 {
00195    struct sched *cur = NULL;
00196    int ret;
00197    int df = 0;
00198    int de = 0;
00199    struct sched *first = AST_DLLIST_FIRST(&con->schedq);
00200    struct sched *last = AST_DLLIST_LAST(&con->schedq);
00201 
00202    if (first)
00203       df = ast_tvdiff_us(s->when, first->when);
00204    if (last)
00205       de = ast_tvdiff_us(s->when, last->when);
00206 
00207    if (df < 0)
00208       df = -df;
00209    if (de < 0)
00210       de = -de;
00211 
00212    if (df < de) {
00213       AST_DLLIST_TRAVERSE(&con->schedq, cur, list) {
00214          if (ast_tvcmp(s->when, cur->when) == -1) {
00215             AST_DLLIST_INSERT_BEFORE(&con->schedq, cur, s, list);
00216             break;
00217          }
00218       }
00219       if (!cur) {
00220          AST_DLLIST_INSERT_TAIL(&con->schedq, s, list);
00221       }
00222    } else {
00223       AST_DLLIST_TRAVERSE_BACKWARDS(&con->schedq, cur, list) {
00224          if (ast_tvcmp(s->when, cur->when) == 1) {
00225             AST_DLLIST_INSERT_AFTER(&con->schedq, cur, s, list);
00226             break;
00227          }
00228       }
00229       if (!cur) {
00230          AST_DLLIST_INSERT_HEAD(&con->schedq, s, list);
00231       }
00232    }
00233 
00234    ret = ast_hashtab_insert_safe(con->schedq_ht, s);
00235    if (!ret)
00236       ast_log(LOG_WARNING,"Schedule Queue entry %d is already in table!\n",s->id);
00237 
00238    con->schedcnt++;
00239 
00240    if (con->schedcnt > con->highwater)
00241       con->highwater = con->schedcnt;
00242 }
00243 
00244 /*! \brief
00245  * given the last event *tv and the offset in milliseconds 'when',
00246  * computes the next value,
00247  */
00248 static int sched_settime(struct timeval *t, int when)
00249 {
00250    struct timeval now = ast_tvnow();
00251 
00252    /*ast_debug(1, "TV -> %lu,%lu\n", tv->tv_sec, tv->tv_usec);*/
00253    if (ast_tvzero(*t))  /* not supplied, default to now */
00254       *t = now;
00255    *t = ast_tvadd(*t, ast_samp2tv(when, 1000));
00256    if (ast_tvcmp(*t, now) < 0) {
00257       *t = now;
00258    }
00259    return 0;
00260 }
00261 
00262 int ast_sched_replace_variable(int old_id, struct sched_context *con, int when, ast_sched_cb callback, const void *data, int variable)
00263 {
00264    /* 0 means the schedule item is new; do not delete */
00265    if (old_id > 0) {
00266       AST_SCHED_DEL(con, old_id);
00267    }
00268    return ast_sched_add_variable(con, when, callback, data, variable);
00269 }
00270 
00271 /*! \brief
00272  * Schedule callback(data) to happen when ms into the future
00273  */
00274 int ast_sched_add_variable(struct sched_context *con, int when, ast_sched_cb callback, const void *data, int variable)
00275 {
00276    struct sched *tmp;
00277    int res = -1;
00278 
00279    DEBUG(ast_debug(1, "ast_sched_add()\n"));
00280 
00281    ast_mutex_lock(&con->lock);
00282    if ((tmp = sched_alloc(con))) {
00283       tmp->id = con->eventcnt++;
00284       tmp->callback = callback;
00285       tmp->data = data;
00286       tmp->resched = when;
00287       tmp->variable = variable;
00288       tmp->when = ast_tv(0, 0);
00289       if (sched_settime(&tmp->when, when)) {
00290          sched_release(con, tmp);
00291       } else {
00292          schedule(con, tmp);
00293          res = tmp->id;
00294       }
00295    }
00296 #ifdef DUMP_SCHEDULER
00297    /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
00298    if (option_debug)
00299       ast_sched_dump(con);
00300 #endif
00301    ast_mutex_unlock(&con->lock);
00302 
00303    return res;
00304 }
00305 
00306 int ast_sched_replace(int old_id, struct sched_context *con, int when, ast_sched_cb callback, const void *data)
00307 {
00308    if (old_id > -1) {
00309       AST_SCHED_DEL(con, old_id);
00310    }
00311    return ast_sched_add(con, when, callback, data);
00312 }
00313 
00314 int ast_sched_add(struct sched_context *con, int when, ast_sched_cb callback, const void *data)
00315 {
00316    return ast_sched_add_variable(con, when, callback, data, 0);
00317 }
00318 
00319 const void *ast_sched_find_data(struct sched_context *con, int id)
00320 {
00321    struct sched tmp,*res;
00322    tmp.id = id;
00323    res = ast_hashtab_lookup(con->schedq_ht, &tmp);
00324    if (res)
00325       return res->data;
00326    return NULL;
00327 }
00328    
00329 /*! \brief
00330  * Delete the schedule entry with number
00331  * "id".  It's nearly impossible that there
00332  * would be two or more in the list with that
00333  * id.
00334  */
00335 #ifndef AST_DEVMODE
00336 int ast_sched_del(struct sched_context *con, int id)
00337 #else
00338 int _ast_sched_del(struct sched_context *con, int id, const char *file, int line, const char *function)
00339 #endif
00340 {
00341    struct sched *s, tmp;
00342 
00343    DEBUG(ast_debug(1, "ast_sched_del(%d)\n", id));
00344    
00345    ast_mutex_lock(&con->lock);
00346 
00347    /* OK, this is the heart of the sched performance upgrade.
00348       If we have 4700 peers, we can have 4700+ entries in the
00349       schedq list. searching this would take time. So, I add a 
00350       hashtab to the context to keep track of each entry, by id.
00351       I also leave the linked list alone, almost, --  I implement
00352        a doubly-linked list instead, because it would do little good
00353       to look up the id in a hashtab, and then have to run thru 
00354       a couple thousand entries to remove it from the schedq list! */
00355    tmp.id = id;
00356    s = ast_hashtab_lookup(con->schedq_ht, &tmp);
00357    if (s) {
00358       struct sched *x = AST_DLLIST_REMOVE(&con->schedq, s, list);
00359       
00360       if (!x)
00361          ast_log(LOG_WARNING,"sched entry %d not in the schedq list?\n", s->id);
00362 
00363       if (!ast_hashtab_remove_this_object(con->schedq_ht, s))
00364          ast_log(LOG_WARNING,"Found sched entry %d, then couldn't remove it?\n", s->id);
00365       con->schedcnt--;
00366       sched_release(con, s);
00367    }
00368    
00369 #ifdef DUMP_SCHEDULER
00370    /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
00371    if (option_debug)
00372       ast_sched_dump(con);
00373 #endif
00374    ast_mutex_unlock(&con->lock);
00375 
00376    if (!s) {
00377       ast_debug(1, "Attempted to delete nonexistent schedule entry %d!\n", id);
00378 #ifndef AST_DEVMODE
00379       ast_assert(s != NULL);
00380 #else
00381       _ast_assert(0, "s != NULL", file, line, function);
00382 #endif
00383       return -1;
00384    }
00385    
00386    return 0;
00387 }
00388 
00389 void ast_sched_report(struct sched_context *con, struct ast_str **buf, struct ast_cb_names *cbnames)
00390 {
00391    int i;
00392    struct sched *cur;
00393    int countlist[cbnames->numassocs + 1];
00394    
00395    memset(countlist, 0, sizeof(countlist));
00396    ast_str_set(buf, 0, " Highwater = %d\n schedcnt = %d\n", con->highwater, con->schedcnt);
00397 
00398    ast_mutex_lock(&con->lock);
00399    AST_DLLIST_TRAVERSE(&con->schedq, cur, list) {
00400       /* match the callback to the cblist */
00401       for (i = 0; i < cbnames->numassocs; i++) {
00402          if (cur->callback == cbnames->cblist[i]) {
00403             break;
00404          }
00405       }
00406       if (i < cbnames->numassocs) {
00407          countlist[i]++;
00408       } else {
00409          countlist[cbnames->numassocs]++;
00410       }
00411    }
00412    ast_mutex_unlock(&con->lock);
00413 
00414    for (i = 0; i < cbnames->numassocs; i++) {
00415       ast_str_append(buf, 0, "    %s : %d\n", cbnames->list[i], countlist[i]);
00416    }
00417 
00418    ast_str_append(buf, 0, "   <unknown> : %d\n", countlist[cbnames->numassocs]);
00419 }
00420    
00421 /*! \brief Dump the contents of the scheduler to LOG_DEBUG */
00422 void ast_sched_dump(struct sched_context *con)
00423 {
00424    struct sched *q;
00425    struct timeval when = ast_tvnow();
00426 #ifdef SCHED_MAX_CACHE
00427    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);
00428 #else
00429    ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d high-water)\n", con->schedcnt, con->eventcnt - 1, con->highwater);
00430 #endif
00431 
00432    ast_debug(1, "=============================================================\n");
00433    ast_debug(1, "|ID    Callback          Data              Time  (sec:ms)   |\n");
00434    ast_debug(1, "+-----+-----------------+-----------------+-----------------+\n");
00435    ast_mutex_lock(&con->lock);
00436    AST_DLLIST_TRAVERSE(&con->schedq, q, list) {
00437       struct timeval delta = ast_tvsub(q->when, when);
00438 
00439       ast_debug(1, "|%.4d | %-15p | %-15p | %.6ld : %.6ld |\n", 
00440          q->id,
00441          q->callback,
00442          q->data,
00443          (long)delta.tv_sec,
00444          (long int)delta.tv_usec);
00445    }
00446    ast_mutex_unlock(&con->lock);
00447    ast_debug(1, "=============================================================\n");
00448 }
00449 
00450 /*! \brief
00451  * Launch all events which need to be run at this time.
00452  */
00453 int ast_sched_runq(struct sched_context *con)
00454 {
00455    struct sched *current;
00456    struct timeval when;
00457    int numevents;
00458    int res;
00459 
00460    DEBUG(ast_debug(1, "ast_sched_runq()\n"));
00461       
00462    ast_mutex_lock(&con->lock);
00463 
00464    for (numevents = 0; !AST_DLLIST_EMPTY(&con->schedq); numevents++) {
00465       /* schedule all events which are going to expire within 1ms.
00466        * We only care about millisecond accuracy anyway, so this will
00467        * help us get more than one event at one time if they are very
00468        * close together.
00469        */
00470       when = ast_tvadd(ast_tvnow(), ast_tv(0, 1000));
00471       if (ast_tvcmp(AST_DLLIST_FIRST(&con->schedq)->when, when) != -1)
00472          break;
00473       
00474       current = AST_DLLIST_REMOVE_HEAD(&con->schedq, list);
00475       if (!ast_hashtab_remove_this_object(con->schedq_ht, current))
00476          ast_log(LOG_ERROR,"Sched entry %d was in the schedq list but not in the hashtab???\n", current->id);
00477 
00478       con->schedcnt--;
00479 
00480       /*
00481        * At this point, the schedule queue is still intact.  We
00482        * have removed the first event and the rest is still there,
00483        * so it's permissible for the callback to add new events, but
00484        * trying to delete itself won't work because it isn't in
00485        * the schedule queue.  If that's what it wants to do, it 
00486        * should return 0.
00487        */
00488          
00489       ast_mutex_unlock(&con->lock);
00490       res = current->callback(current->data);
00491       ast_mutex_lock(&con->lock);
00492          
00493       if (res) {
00494          /*
00495           * If they return non-zero, we should schedule them to be
00496           * run again.
00497           */
00498          if (sched_settime(&current->when, current->variable? res : current->resched)) {
00499             sched_release(con, current);
00500          } else
00501             schedule(con, current);
00502       } else {
00503          /* No longer needed, so release it */
00504          sched_release(con, current);
00505       }
00506    }
00507 
00508    ast_mutex_unlock(&con->lock);
00509    
00510    return numevents;
00511 }
00512 
00513 long ast_sched_when(struct sched_context *con,int id)
00514 {
00515    struct sched *s, tmp;
00516    long secs = -1;
00517    DEBUG(ast_debug(1, "ast_sched_when()\n"));
00518 
00519    ast_mutex_lock(&con->lock);
00520    
00521    /* these next 2 lines replace a lookup loop */
00522    tmp.id = id;
00523    s = ast_hashtab_lookup(con->schedq_ht, &tmp);
00524    
00525    if (s) {
00526       struct timeval now = ast_tvnow();
00527       secs = s->when.tv_sec - now.tv_sec;
00528    }
00529    ast_mutex_unlock(&con->lock);
00530    
00531    return secs;
00532 }

Generated on Wed Aug 18 22:33:56 2010 for Asterisk - the Open Source PBX by  doxygen 1.4.7