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