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