main/sched.c

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