src/libstrongswan/processing/scheduler.c

   1 /*
   2  * Copyright (C) 2008 Tobias Brunner
   3  * Copyright (C) 2005-2006 Martin Willi
   4  * Copyright (C) 2005 Jan Hutter
   5  * Hochschule fuer Technik Rapperswil
   6  *
   7  * This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License as published by the
   9  * Free Software Foundation; either version 2 of the License, or (at your
  10  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  11  *
  12  * This program is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15  * for more details.
  16  */
  17
  18 #include <stdlib.h>
  19
  20 #include "scheduler.h"
  21
  22 #include <debug.h>
  23 #include <processing/processor.h>
  24 #include <processing/jobs/callback_job.h>
  25 #include <threading/thread.h>
  26 #include <threading/condvar.h>
  27 #include <threading/mutex.h>
  28
  29 /* the initial size of the heap */
  30 #define HEAP_SIZE_DEFAULT 64
  31
  32 typedef struct event_t event_t;
  33
  34 /**
  35  * Event containing a job and a schedule time
  36  */
  37 struct event_t {
  38         /**
  39          * Time to fire the event.
  40          */
  41         timeval_t time;
  42
  43         /**
  44          * Every event has its assigned job.
  45          */
  46         job_t *job;
  47 };
  48
  49 /**
  50  * destroy an event and its job
  51  */
  52 static void event_destroy(event_t *event)
  53 {
  54         event->job->destroy(event->job);
  55         free(event);
  56 }
  57
  58 typedef struct private_scheduler_t private_scheduler_t;
  59
  60 /**
  61  * Private data of a scheduler_t object.
  62  */
  63 struct private_scheduler_t {
  64
  65         /**
  66          * Public part of a scheduler_t object.
  67          */
  68          scheduler_t public;
  69
  70         /**
  71          * Job which queues scheduled jobs to the processor.
  72          */
  73         callback_job_t *job;
  74
  75         /**
  76          * The heap in which the events are stored.
  77          */
  78         event_t **heap;
  79
  80         /**
  81          * The size of the heap.
  82          */
  83         u_int heap_size;
  84
  85         /**
  86          * The number of scheduled events.
  87          */
  88         u_int event_count;
  89
  90         /**
  91          * Exclusive access to list
  92          */
  93         mutex_t *mutex;
  94
  95         /**
  96          * Condvar to wait for next job.
  97          */
  98         condvar_t *condvar;
  99 };
 100
 101 /**
 102  * Comparse two timevals, return >0 if a > b, <0 if a < b and =0 if equal
 103  */
 104 static int timeval_cmp(timeval_t *a, timeval_t *b)
 105 {
 106         if (a->tv_sec > b->tv_sec)
 107         {
 108                 return 1;
 109         }
 110         if (a->tv_sec < b->tv_sec)
 111         {
 112                 return -1;
 113         }
 114         if (a->tv_usec > b->tv_usec)
 115         {
 116                 return 1;
 117         }
 118         if (a->tv_usec < b->tv_usec)
 119         {
 120                 return -1;
 121         }
 122         return 0;
 123 }
 124
 125 /**
 126  * Returns the top event without removing it. Returns NULL if the heap is empty.
 127  */
 128 static event_t *peek_event(private_scheduler_t *this)
 129 {
 130         return this->event_count > 0 ? this->heap[1] : NULL;
 131 }
 132
 133 /**
 134  * Removes the top event from the heap and returns it. Returns NULL if the heap
 135  * is empty.
 136  */
 137 static event_t *remove_event(private_scheduler_t *this)
 138 {
 139         event_t *event, *top;
 140         if (!this->event_count)
 141         {
 142                 return NULL;
 143         }
 144
 145         /* store the value to return */
 146         event = this->heap[1];
 147         /* move the bottom event to the top */
 148         top = this->heap[1] = this->heap[this->event_count];
 149
 150         if (--this->event_count > 1)
 151         {
 152                 /* seep down the top event */
 153                 u_int position = 1;
 154                 while ((position << 1) <= this->event_count)
 155                 {
 156                         u_int child = position << 1;
 157
 158                         if ((child + 1) <= this->event_count &&
 159                                 timeval_cmp(&this->heap[child + 1]->time,
 160                                                         &this->heap[child]->time) < 0)
 161                         {
 162                                 /* the "right" child is smaller */
 163                                 child++;
 164                         }
 165
 166                         if (timeval_cmp(&top->time, &this->heap[child]->time) <= 0)
 167                         {
 168                                 /* the top event fires before the smaller of the two children,
 169                                  * stop */
 170                                 break;
 171                         }
 172
 173                         /* swap with the smaller child */
 174                         this->heap[position] = this->heap[child];
 175                         position = child;
 176                 }
 177                 this->heap[position] = top;
 178         }
 179         return event;
 180 }
 181
 182 /**
 183  * Get events from the queue and pass it to the processor
 184  */
 185 static job_requeue_t schedule(private_scheduler_t * this)
 186 {
 187         timeval_t now;
 188         event_t *event;
 189         bool timed = FALSE, oldstate;
 190
 191         this->mutex->lock(this->mutex);
 192
 193         time_monotonic(&now);
 194
 195         if ((event = peek_event(this)) != NULL)
 196         {
 197                 if (timeval_cmp(&now, &event->time) >= 0)
 198                 {
 199                         remove_event(this);
 200                         this->mutex->unlock(this->mutex);
 201                         DBG2(DBG_JOB, "got event, queuing job for execution");
 202                         lib->processor->queue_job(lib->processor, event->job);
 203                         free(event);
 204                         return JOB_REQUEUE_DIRECT;
 205                 }
 206                 timersub(&event->time, &now, &now);
 207                 if (now.tv_sec)
 208                 {
 209                         DBG2(DBG_JOB, "next event in %ds %dms, waiting",
 210                                  now.tv_sec, now.tv_usec/1000);
 211                 }
 212                 else
 213                 {
 214                         DBG2(DBG_JOB, "next event in %dms, waiting", now.tv_usec/1000);
 215                 }
 216                 timed = TRUE;
 217         }
 218         thread_cleanup_push((thread_cleanup_t)this->mutex->unlock, this->mutex);
 219         oldstate = thread_cancelability(TRUE);
 220
 221         if (timed)
 222         {
 223                 this->condvar->timed_wait_abs(this->condvar, this->mutex, event->time);
 224         }
 225         else
 226         {
 227                 DBG2(DBG_JOB, "no events, waiting");
 228                 this->condvar->wait(this->condvar, this->mutex);
 229         }
 230         thread_cancelability(oldstate);
 231         thread_cleanup_pop(TRUE);
 232         return JOB_REQUEUE_DIRECT;
 233 }
 234
 235 METHOD(scheduler_t, get_job_load, u_int,
 236         private_scheduler_t *this)
 237 {
 238         int count;
 239         this->mutex->lock(this->mutex);
 240         count = this->event_count;
 241         this->mutex->unlock(this->mutex);
 242         return count;
 243 }
 244
 245 METHOD(scheduler_t, schedule_job_tv, void,
 246         private_scheduler_t *this, job_t *job, timeval_t tv)
 247 {
 248         event_t *event;
 249         u_int position;
 250
 251         event = malloc_thing(event_t);
 252         event->job = job;
 253         event->time = tv;
 254
 255         this->mutex->lock(this->mutex);
 256
 257         this->event_count++;
 258         if (this->event_count > this->heap_size)
 259         {
 260                 /* double the size of the heap */
 261                 this->heap_size <<= 1;
 262                 this->heap = (event_t**)realloc(this->heap,
 263                                                                         (this->heap_size + 1) * sizeof(event_t*));
 264         }
 265         /* "put" the event to the bottom */
 266         position = this->event_count;
 267
 268         /* then bubble it up */
 269         while (position > 1 && timeval_cmp(&this->heap[position >> 1]->time,
 270                                                                            &event->time) > 0)
 271         {
 272                 /* parent has to be fired after the new event, move up */
 273                 this->heap[position] = this->heap[position >> 1];
 274                 position >>= 1;
 275         }
 276         this->heap[position] = event;
 277
 278         this->condvar->signal(this->condvar);
 279         this->mutex->unlock(this->mutex);
 280 }
 281
 282 METHOD(scheduler_t, schedule_job, void,
 283         private_scheduler_t *this, job_t *job, u_int32_t s)
 284 {
 285         timeval_t tv;
 286
 287         time_monotonic(&tv);
 288         tv.tv_sec += s;
 289
 290         schedule_job_tv(this, job, tv);
 291 }
 292
 293 METHOD(scheduler_t, schedule_job_ms, void,
 294         private_scheduler_t *this, job_t *job, u_int32_t ms)
 295 {
 296         timeval_t tv, add;
 297
 298         time_monotonic(&tv);
 299         add.tv_sec = ms / 1000;
 300         add.tv_usec = (ms % 1000) * 1000;
 301
 302         timeradd(&tv, &add, &tv);
 303
 304         schedule_job_tv(this, job, tv);
 305 }
 306
 307 METHOD(scheduler_t, destroy, void,
 308         private_scheduler_t *this)
 309 {
 310         event_t *event;
 311         this->job->cancel(this->job);
 312         this->condvar->destroy(this->condvar);
 313         this->mutex->destroy(this->mutex);
 314         while ((event = remove_event(this)) != NULL)
 315         {
 316                 event_destroy(event);
 317         }
 318         free(this->heap);
 319         free(this);
 320 }
 321
 322 /*
 323  * Described in header.
 324  */
 325 scheduler_t * scheduler_create()
 326 {
 327         private_scheduler_t *this;
 328
 329         INIT(this,
 330                 .public = {
 331                         .get_job_load = _get_job_load,
 332                         .schedule_job = _schedule_job,
 333                         .schedule_job_ms = _schedule_job_ms,
 334                         .schedule_job_tv = _schedule_job_tv,
 335                         .destroy = _destroy,
 336                 },
 337                 .heap_size = HEAP_SIZE_DEFAULT,
 338                 .mutex = mutex_create(MUTEX_TYPE_DEFAULT),
 339                 .condvar = condvar_create(CONDVAR_TYPE_DEFAULT),
 340         );
 341
 342         this->heap = (event_t**)calloc(this->heap_size + 1, sizeof(event_t*));
 343
 344         this->job = callback_job_create_with_prio((callback_job_cb_t)schedule,
 345                                                                                 this, NULL, NULL, JOB_PRIO_CRITICAL);
 346         lib->processor->queue_job(lib->processor, (job_t*)this->job);
 347
 348         return &this->public;
 349 }
 350