lib/silcutil/silcschedule.c

   1 /*
   2
   3   silcschedule.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 1998 - 2001 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; either version 2 of the License, or
  12   (at your option) any later version.
  13
  14   This program is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19 */
  20 /* $Id$ */
  21
  22 #include "silcincludes.h"
  23 #include "silcschedule_i.h"
  24
  25 /* Forward declarations */
  26 typedef struct SilcTaskQueueStruct *SilcTaskQueue;
  27
  28 /* System specific routines. Implemented under unix/ and win32/. */
  29
  30 /* System specific select(). Returns same values as normal select(). */
  31 int silc_select(SilcScheduleFd fds, uint32 fds_count, struct timeval *timeout);
  32
  33 /* Initializes the wakeup of the scheduler. In multi-threaded environment
  34    the scheduler needs to be wakenup when tasks are added or removed from
  35    the task queues. This will initialize the wakeup for the scheduler.
  36    Any tasks that needs to be registered must be registered to the `queue'.
  37    It is guaranteed that the scheduler will automatically free any
  38    registered tasks in this queue. This is system specific routine. */
  39 void *silc_schedule_wakeup_init(SilcSchedule schedule);
  40
  41 /* Uninitializes the system specific wakeup. */
  42 void silc_schedule_wakeup_uninit(void *context);
  43
  44 /* Wakes up the scheduler. This is platform specific routine */
  45 void silc_schedule_wakeup_internal(void *context);
  46
  47
  48 /* Internal task management routines. */
  49
  50 static void silc_task_queue_alloc(SilcTaskQueue *queue);
  51 static void silc_task_queue_free(SilcTaskQueue queue);
  52 static SilcTask silc_task_find(SilcTaskQueue queue, uint32 fd);
  53 static SilcTask silc_task_add(SilcTaskQueue queue, SilcTask newtask,
  54                               SilcTaskPriority priority);
  55 static SilcTask silc_task_get_first(SilcTaskQueue queue, SilcTask first);
  56 static SilcTask silc_task_add_timeout(SilcTaskQueue queue, SilcTask newtask,
  57                                       SilcTaskPriority priority);
  58 static int silc_schedule_task_remove(SilcTaskQueue queue, SilcTask task);
  59 static int silc_schedule_task_timeout_compare(struct timeval *smaller,
  60                                               struct timeval *bigger);
  61 static void silc_task_del_by_context(SilcTaskQueue queue, void *context);
  62 static void silc_task_del_by_callback(SilcTaskQueue queue,
  63                                       SilcTaskCallback callback);
  64 static void silc_task_del_by_fd(SilcTaskQueue queue, uint32 fd);
  65
  66 /* Returns the task queue by task type */
  67 #define SILC_SCHEDULE_GET_QUEUE(type)                                   \
  68   (type == SILC_TASK_FD ? schedule->fd_queue :                          \
  69    type == SILC_TASK_TIMEOUT ? schedule->timeout_queue :                \
  70    schedule->generic_queue)
  71
  72 /* SILC Task object. Represents one task in the scheduler. */
  73 struct SilcTaskStruct {
  74   uint32 fd;
  75   struct timeval timeout;
  76   SilcTaskCallback callback;
  77   void *context;
  78   bool valid;
  79   SilcTaskPriority priority;
  80   SilcTaskType type;
  81
  82   /* Pointers forming doubly linked circular list */
  83   struct SilcTaskStruct *next;
  84   struct SilcTaskStruct *prev;
  85 };
  86
  87 /* SILC Task Queue object. The queue holds all the tasks in the scheduler.
  88    There are always three task queues in the scheduler. One for non-timeout
  89    tasks (fd tasks performing tasks over specified file descriptor),
  90    one for timeout tasks and one for generic tasks. */
  91 struct SilcTaskQueueStruct {
  92   SilcTask task;                /* Pointer to all tasks */
  93   struct timeval timeout;       /* Current timeout */
  94   SILC_MUTEX_DEFINE(lock);      /* Queue's lock */
  95 };
  96
  97 /*
  98    SILC Scheduler structure.
  99
 100    This is the actual schedule object in SILC. Both SILC client and server
 101    uses this same scheduler. Actually, this scheduler could be used by any
 102    program needing scheduling.
 103
 104    Following short description of the fields:
 105
 106    SilcTaskQueue fd_queue
 107
 108        Task queue hook for non-timeout tasks. Usually this means that these
 109        tasks perform different kind of I/O on file descriptors. File
 110        descriptors are usually network sockets but they actually can be
 111        any file descriptors. This hook is initialized in silc_schedule_init
 112        function. Timeout tasks should not be added to this queue because
 113        they will never expire.
 114
 115    SilcTaskQueue timeout_queue
 116
 117        Task queue hook for timeout tasks. This hook is reserved specificly
 118        for tasks with timeout. Non-timeout tasks should not be added to this
 119        queue because they will never get scheduled. This hook is also
 120        initialized in silc_schedule_init function.
 121
 122    SilcTaskQueue generic_queue
 123
 124        Task queue hook for generic tasks. This hook is reserved specificly
 125        for generic tasks, tasks that apply to all file descriptors, except
 126        to those that have specificly registered a non-timeout task. This hook
 127        is also initialized in silc_schedule_init function.
 128
 129    SilcScheduleFd fd_list
 130
 131        List of file descriptors the scheduler is supposed to be listenning.
 132        This is updated internally.
 133
 134    uint32 max_fd
 135    uint32 last_fd
 136
 137        Size of the fd_list list. There can be `max_fd' many tasks in
 138        the scheduler at once. The `last_fd' is the last valid entry
 139        in the fd_list.
 140
 141    struct timeval *timeout;
 142
 143        Pointer to the schedules next timeout. Value of this timeout is
 144        automatically updated in the silc_schedule function.
 145
 146    bool valid
 147
 148        Marks validity of the scheduler. This is a boolean value. When this
 149        is false the scheduler is terminated and the program will end. This
 150        set to true when the scheduler is initialized with silc_schedule_init
 151        function.
 152
 153    fd_set in
 154    fd_set out
 155
 156        File descriptor sets for select(). These are automatically managed
 157        by the scheduler and should not be touched otherwise.
 158
 159    void *wakeup
 160
 161        System specific wakeup context. On multi-threaded environments the
 162        scheduler needs to be wakenup (in the thread) when tasks are added
 163        or removed. This is initialized by silc_schedule_wakeup_init.
 164
 165    SILC_MUTEX_DEFINE(lock)
 166
 167        Scheduler lock.
 168
 169 */
 170 struct SilcScheduleStruct {
 171   SilcTaskQueue fd_queue;
 172   SilcTaskQueue timeout_queue;
 173   SilcTaskQueue generic_queue;
 174   SilcScheduleFd fd_list;
 175   uint32 max_fd;
 176   uint32 last_fd;
 177   struct timeval *timeout;
 178   bool valid;
 179   void *wakeup;
 180   SILC_MUTEX_DEFINE(lock);
 181   bool is_locked;
 182 };
 183
 184 /* Initializes the scheduler. This returns the scheduler context that
 185    is given as arugment usually to all silc_schedule_* functions.
 186    The `max_tasks' indicates the number of maximum tasks that the
 187    scheduler can handle. */
 188
 189 SilcSchedule silc_schedule_init(int max_tasks)
 190 {
 191   SilcSchedule schedule;
 192
 193   SILC_LOG_DEBUG(("Initializing scheduler"));
 194
 195   schedule = silc_calloc(1, sizeof(*schedule));
 196
 197   /* Allocate three task queues, one for file descriptor based tasks,
 198      one for timeout tasks and one for generic tasks. */
 199   silc_task_queue_alloc(&schedule->fd_queue);
 200   silc_task_queue_alloc(&schedule->timeout_queue);
 201   silc_task_queue_alloc(&schedule->generic_queue);
 202
 203   /* Initialize the scheduler */
 204   schedule->fd_list = silc_calloc(max_tasks, sizeof(*schedule->fd_list));
 205   schedule->max_fd = max_tasks;
 206   schedule->timeout = NULL;
 207   schedule->valid = TRUE;
 208
 209   /* Allocate scheduler lock */
 210   silc_mutex_alloc(&schedule->lock);
 211
 212   /* Initialize the wakeup, for multi-threads support */
 213   schedule->wakeup = silc_schedule_wakeup_init(schedule);
 214
 215   return schedule;
 216 }
 217
 218 /* Uninitializes the schedule. This is called when the program is ready
 219    to end. This removes all tasks and task queues. Returns FALSE if the
 220    scheduler could not be uninitialized. This happens when the scheduler
 221    is still valid and silc_schedule_stop has not been called. */
 222
 223 bool silc_schedule_uninit(SilcSchedule schedule)
 224 {
 225   SILC_LOG_DEBUG(("Uninitializing scheduler"));
 226
 227   if (schedule->valid == TRUE)
 228     return FALSE;
 229
 230   /* Unregister all tasks */
 231   silc_schedule_task_remove(schedule->fd_queue, SILC_ALL_TASKS);
 232   silc_schedule_task_remove(schedule->timeout_queue, SILC_ALL_TASKS);
 233   silc_schedule_task_remove(schedule->generic_queue, SILC_ALL_TASKS);
 234
 235   /* Unregister all task queues */
 236   silc_task_queue_free(schedule->fd_queue);
 237   silc_task_queue_free(schedule->timeout_queue);
 238   silc_task_queue_free(schedule->generic_queue);
 239
 240   silc_free(schedule->fd_list);
 241
 242   /* Uninit the wakeup */
 243   silc_schedule_wakeup_uninit(schedule->wakeup);
 244
 245   silc_mutex_free(schedule->lock);
 246
 247   return TRUE;
 248 }
 249
 250 /* Stops the schedule even if it is not supposed to be stopped yet.
 251    After calling this, one should call silc_schedule_uninit (after the
 252    silc_schedule has returned). */
 253
 254 void silc_schedule_stop(SilcSchedule schedule)
 255 {
 256   SILC_LOG_DEBUG(("Stopping scheduler"));
 257   silc_mutex_lock(schedule->lock);
 258   schedule->valid = FALSE;
 259   silc_mutex_unlock(schedule->lock);
 260 }
 261
 262 /* Executes nontimeout tasks. It then checks whether any of ther fd tasks
 263    was signaled by the silc_select. If some task was not signaled then
 264    all generic tasks are executed for that task. The generic tasks are
 265    never executed for task that has explicit fd task set. */
 266 /* This holds the schedule->lock and the queue locks. */
 267
 268 static void silc_schedule_dispatch_nontimeout(SilcSchedule schedule)
 269 {
 270   SilcTask task;
 271   int i, last_fd = schedule->last_fd;
 272   uint32 fd;
 273
 274   for (i = 0; i <= last_fd; i++) {
 275     if (schedule->fd_list[i].events == 0)
 276       continue;
 277
 278     fd = schedule->fd_list[i].fd;
 279
 280     /* First check whether this fd has task in the fd queue */
 281     silc_mutex_lock(schedule->fd_queue->lock);
 282     task = silc_task_find(schedule->fd_queue, fd);
 283
 284     /* If the task was found then execute its callbacks. If not then
 285        execute all generic tasks for that fd. */
 286     if (task) {
 287       /* Validity of the task is checked always before and after
 288          execution beacuse the task might have been unregistered
 289          in the callback function, ie. it is not valid anymore. */
 290
 291       /* Is the task ready for reading */
 292       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 293         silc_mutex_unlock(schedule->fd_queue->lock);
 294         silc_mutex_unlock(schedule->lock);
 295         task->callback(schedule, SILC_TASK_READ, task->fd, task->context);
 296         silc_mutex_lock(schedule->lock);
 297         silc_mutex_lock(schedule->fd_queue->lock);
 298       }
 299
 300       /* Is the task ready for writing */
 301       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 302         silc_mutex_unlock(schedule->fd_queue->lock);
 303         silc_mutex_unlock(schedule->lock);
 304         task->callback(schedule, SILC_TASK_WRITE, task->fd, task->context);
 305         silc_mutex_lock(schedule->lock);
 306         silc_mutex_lock(schedule->fd_queue->lock);
 307       }
 308
 309       if (!task->valid)
 310         silc_schedule_task_remove(schedule->fd_queue, task);
 311
 312       silc_mutex_unlock(schedule->fd_queue->lock);
 313     } else {
 314       /* Run generic tasks for this fd. */
 315
 316       silc_mutex_unlock(schedule->fd_queue->lock);
 317
 318       silc_mutex_lock(schedule->generic_queue->lock);
 319       if (!schedule->generic_queue->task) {
 320         silc_mutex_unlock(schedule->generic_queue->lock);
 321         continue;
 322       }
 323
 324       task = schedule->generic_queue->task;
 325       while(1) {
 326         /* Validity of the task is checked always before and after
 327            execution beacuse the task might have been unregistered
 328            in the callback function, ie. it is not valid anymore. */
 329
 330         /* Is the task ready for reading */
 331         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 332           silc_mutex_unlock(schedule->generic_queue->lock);
 333           silc_mutex_unlock(schedule->lock);
 334           task->callback(schedule, SILC_TASK_READ, fd, task->context);
 335           silc_mutex_lock(schedule->lock);
 336           silc_mutex_lock(schedule->generic_queue->lock);
 337         }
 338
 339         /* Is the task ready for writing */
 340         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 341           silc_mutex_unlock(schedule->generic_queue->lock);
 342           silc_mutex_unlock(schedule->lock);
 343           task->callback(schedule, SILC_TASK_WRITE, fd, task->context);
 344           silc_mutex_lock(schedule->lock);
 345           silc_mutex_lock(schedule->generic_queue->lock);
 346         }
 347
 348         if (!task->valid) {
 349           /* Invalid (unregistered) tasks are removed from the
 350              task queue. */
 351           if (schedule->generic_queue->task == task->next) {
 352             silc_schedule_task_remove(schedule->generic_queue, task);
 353             silc_mutex_unlock(schedule->generic_queue->lock);
 354             break;
 355           }
 356
 357           task = task->next;
 358           silc_schedule_task_remove(schedule->generic_queue, task);
 359           continue;
 360         }
 361
 362         /* Break if there isn't more tasks in the queue */
 363         if (schedule->generic_queue->task == task->next)
 364           break;
 365
 366         task = task->next;
 367       }
 368
 369       silc_mutex_unlock(schedule->generic_queue->lock);
 370     }
 371   }
 372 }
 373
 374 /* Executes all tasks whose timeout has expired. The task is removed from
 375    the task queue after the callback function has returned. Also, invalid
 376    tasks are removed here. We don't have to care about priorities because
 377    tasks are already sorted in their priority order at the registration
 378    phase. */
 379 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 380
 381 static void silc_schedule_dispatch_timeout(SilcSchedule schedule)
 382 {
 383   SilcTaskQueue queue = schedule->timeout_queue;
 384   SilcTask task;
 385   struct timeval curtime;
 386
 387   SILC_LOG_DEBUG(("Running timeout tasks"));
 388
 389   silc_gettimeofday(&curtime);
 390
 391   queue = schedule->timeout_queue;
 392   if (queue && queue->task) {
 393     task = queue->task;
 394
 395     /* Walk thorugh all tasks in the particular task queue and run all
 396        the expired tasks. */
 397     while(1) {
 398       /* Execute the task if the timeout has expired */
 399       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 400         if (task->valid) {
 401           silc_mutex_unlock(queue->lock);
 402           silc_mutex_unlock(schedule->lock);
 403           task->callback(schedule, SILC_TASK_EXPIRE, task->fd, task->context);
 404           silc_mutex_lock(schedule->lock);
 405           silc_mutex_lock(queue->lock);
 406         }
 407
 408         /* Break if there isn't more tasks in the queue */
 409         if (queue->task == task->next) {
 410           silc_schedule_task_remove(queue, task);
 411           break;
 412         }
 413
 414         task = task->next;
 415
 416         /* Remove the task from queue */
 417         silc_schedule_task_remove(queue, task->prev);
 418       } else {
 419         /* The timeout hasn't expired, check for next one */
 420
 421         /* Break if there isn't more tasks in the queue */
 422         if (queue->task == task->next)
 423           break;
 424
 425         task = task->next;
 426       }
 427     }
 428   }
 429 }
 430
 431 /* Calculates next timeout for select(). This is the timeout value
 432    when at earliest some of the timeout tasks expire. If this is in the
 433    past, they will be run now. */
 434 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 435
 436 static void silc_schedule_select_timeout(SilcSchedule schedule)
 437 {
 438   SilcTaskQueue queue = schedule->timeout_queue;
 439   SilcTask task;
 440   struct timeval curtime;
 441
 442   /* Get the current time */
 443   silc_gettimeofday(&curtime);
 444   schedule->timeout = NULL;
 445
 446   /* First task in the task queue has always the smallest timeout. */
 447   task = queue->task;
 448   while(1) {
 449     if (task && task->valid == TRUE) {
 450       /* If the timeout is in past, we will run the task and all other
 451          timeout tasks from the past. */
 452       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 453         silc_schedule_dispatch_timeout(schedule);
 454
 455         /* The task(s) has expired and doesn't exist on the task queue
 456            anymore. We continue with new timeout. */
 457         queue = schedule->timeout_queue;
 458         task = queue->task;
 459         if (task == NULL || task->valid == FALSE)
 460           break;
 461       }
 462
 463       /* Calculate the next timeout for select() */
 464       queue->timeout.tv_sec = task->timeout.tv_sec - curtime.tv_sec;
 465       queue->timeout.tv_usec = task->timeout.tv_usec - curtime.tv_usec;
 466       if (queue->timeout.tv_sec < 0)
 467         queue->timeout.tv_sec = 0;
 468
 469       /* We wouldn't want to go under zero, check for it. */
 470       if (queue->timeout.tv_usec < 0) {
 471         queue->timeout.tv_sec -= 1;
 472         if (queue->timeout.tv_sec < 0)
 473           queue->timeout.tv_sec = 0;
 474         queue->timeout.tv_usec += 1000000L;
 475       }
 476
 477       /* We've got the timeout value */
 478       break;
 479     } else {
 480       /* Task is not valid, remove it and try next one. */
 481       silc_schedule_task_remove(queue, task);
 482       task = queue->task;
 483       if (queue->task == NULL)
 484         break;
 485     }
 486   }
 487
 488   /* Save the timeout */
 489   if (task) {
 490     schedule->timeout = &queue->timeout;
 491     SILC_LOG_DEBUG(("timeout: sec=%d, usec=%d", schedule->timeout->tv_sec,
 492                     schedule->timeout->tv_usec));
 493   }
 494 }
 495
 496 /* Runs the scheduler once and then returns. */
 497
 498 bool silc_schedule_one(SilcSchedule schedule, int timeout_usecs)
 499 {
 500   struct timeval timeout;
 501   int ret;
 502
 503   SILC_LOG_DEBUG(("In scheduler loop"));
 504
 505   if (!schedule->is_locked)
 506     silc_mutex_lock(schedule->lock);
 507
 508   /* If the task queues aren't initialized or we aren't valid anymore
 509      we will return */
 510   if ((!schedule->fd_queue && !schedule->timeout_queue
 511        && !schedule->generic_queue) || schedule->valid == FALSE) {
 512     SILC_LOG_DEBUG(("Scheduler not valid anymore, exiting"));
 513     if (!schedule->is_locked)
 514       silc_mutex_unlock(schedule->lock);
 515     return FALSE;
 516   }
 517
 518   /* Calculate next timeout for silc_select(). This is the timeout value
 519      when at earliest some of the timeout tasks expire. */
 520   silc_mutex_lock(schedule->timeout_queue->lock);
 521   silc_schedule_select_timeout(schedule);
 522   silc_mutex_unlock(schedule->timeout_queue->lock);
 523
 524   if (timeout_usecs >= 0) {
 525     timeout.tv_sec = 0;
 526     timeout.tv_usec = timeout_usecs;
 527     schedule->timeout = &timeout;
 528   }
 529
 530   silc_mutex_unlock(schedule->lock);
 531
 532   /* This is the main select(). The program blocks here until some
 533      of the selected file descriptors change status or the selected
 534      timeout expires. */
 535   SILC_LOG_DEBUG(("Select"));
 536   ret = silc_select(schedule->fd_list, schedule->last_fd + 1,
 537                     schedule->timeout);
 538
 539   silc_mutex_lock(schedule->lock);
 540
 541   switch (ret) {
 542   case -1:
 543     /* Error */
 544     if (errno == EINTR)
 545       break;
 546     SILC_LOG_ERROR(("Error in select(): %s", strerror(errno)));
 547     break;
 548   case 0:
 549     /* Timeout */
 550     silc_mutex_lock(schedule->timeout_queue->lock);
 551     silc_schedule_dispatch_timeout(schedule);
 552     silc_mutex_unlock(schedule->timeout_queue->lock);
 553     break;
 554   default:
 555     /* There is some data available now */
 556     SILC_LOG_DEBUG(("Running non-timeout tasks"));
 557     silc_schedule_dispatch_nontimeout(schedule);
 558     break;
 559   }
 560
 561   if (!schedule->is_locked)
 562     silc_mutex_unlock(schedule->lock);
 563
 564   return TRUE;
 565 }
 566
 567 /* The SILC scheduler. This is actually the main routine in SILC programs.
 568    When this returns the program is to be ended. Before this function can
 569    be called, one must call silc_schedule_init function. */
 570
 571 void silc_schedule(SilcSchedule schedule)
 572 {
 573   SILC_LOG_DEBUG(("Running scheduler"));
 574
 575   if (schedule->valid == FALSE) {
 576     SILC_LOG_ERROR(("Scheduler is not valid, stopping"));
 577     return;
 578   }
 579
 580   silc_mutex_lock(schedule->lock);
 581   schedule->is_locked = TRUE;
 582
 583   /* Start the scheduler loop */
 584   while (silc_schedule_one(schedule, -1))
 585     ;
 586
 587   silc_mutex_unlock(schedule->lock);
 588 }
 589
 590 /* Wakes up the scheduler. This is used only in multi-threaded
 591    environments where threads may add new tasks or remove old tasks
 592    from task queues. This is called to wake up the scheduler in the
 593    main thread so that it detects the changes in the task queues.
 594    If threads support is not compiled in this function has no effect.
 595    Implementation of this function is platform specific. */
 596
 597 void silc_schedule_wakeup(SilcSchedule schedule)
 598 {
 599 #ifdef SILC_THREADS
 600   SILC_LOG_DEBUG(("Wakeup scheduler"));
 601   silc_mutex_lock(schedule->lock);
 602   silc_schedule_wakeup_internal(schedule->wakeup);
 603   silc_mutex_unlock(schedule->lock);
 604 #endif
 605 }
 606
 607 /* Add new task to the scheduler */
 608
 609 SilcTask silc_schedule_task_add(SilcSchedule schedule, uint32 fd,
 610                                 SilcTaskCallback callback, void *context,
 611                                 long seconds, long useconds,
 612                                 SilcTaskType type,
 613                                 SilcTaskPriority priority)
 614 {
 615   SilcTask newtask;
 616   SilcTaskQueue queue;
 617   int timeout = FALSE;
 618
 619   SILC_LOG_DEBUG(("Registering new task, fd=%d type=%d priority=%d", fd,
 620                   type, priority));
 621
 622   queue = SILC_SCHEDULE_GET_QUEUE(type);
 623
 624   /* If the task is generic task, we check whether this task has already
 625      been registered. Generic tasks are registered only once and after that
 626      the same task applies to all file descriptors to be registered. */
 627   if (type == SILC_TASK_GENERIC) {
 628     silc_mutex_lock(queue->lock);
 629
 630     if (queue->task) {
 631       SilcTask task = queue->task;
 632       while(1) {
 633         if ((task->callback == callback) && (task->context == context)) {
 634           SILC_LOG_DEBUG(("Found matching generic task, using the match"));
 635
 636           silc_mutex_unlock(queue->lock);
 637
 638           /* Add the fd to be listened, the task found now applies to this
 639              fd as well. */
 640           silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 641           return task;
 642         }
 643
 644         if (queue->task == task->next)
 645           break;
 646
 647         task = task->next;
 648       }
 649     }
 650
 651     silc_mutex_unlock(queue->lock);
 652   }
 653
 654   newtask = silc_calloc(1, sizeof(*newtask));
 655   newtask->fd = fd;
 656   newtask->context = context;
 657   newtask->callback = callback;
 658   newtask->valid = TRUE;
 659   newtask->priority = priority;
 660   newtask->type = type;
 661   newtask->next = newtask;
 662   newtask->prev = newtask;
 663
 664   /* Create timeout if marked to be timeout task */
 665   if (((seconds + useconds) > 0) && (type == SILC_TASK_TIMEOUT)) {
 666     silc_gettimeofday(&newtask->timeout);
 667     newtask->timeout.tv_sec += seconds + (useconds / 1000000L);
 668     newtask->timeout.tv_usec += (useconds % 1000000L);
 669     if (newtask->timeout.tv_usec > 999999L) {
 670       newtask->timeout.tv_sec += 1;
 671       newtask->timeout.tv_usec -= 1000000L;
 672     }
 673     timeout = TRUE;
 674   }
 675
 676   /* If the task is non-timeout task we have to tell the scheduler that we
 677      would like to have these tasks scheduled at some odd distant future. */
 678   if (type != SILC_TASK_TIMEOUT)
 679     silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 680
 681   silc_mutex_lock(queue->lock);
 682
 683   /* Is this first task of the queue? */
 684   if (queue->task == NULL) {
 685     queue->task = newtask;
 686     silc_mutex_unlock(queue->lock);
 687     return newtask;
 688   }
 689
 690   if (timeout)
 691     newtask = silc_task_add_timeout(queue, newtask, priority);
 692   else
 693     newtask = silc_task_add(queue, newtask, priority);
 694
 695   silc_mutex_unlock(queue->lock);
 696
 697   return newtask;
 698 }
 699
 700 /* Removes a task from the scheduler */
 701
 702 void silc_schedule_task_del(SilcSchedule schedule, SilcTask task)
 703 {
 704   SilcTaskQueue queue = SILC_SCHEDULE_GET_QUEUE(task->type);
 705
 706   /* Unregister all tasks */
 707   if (task == SILC_ALL_TASKS) {
 708     SilcTask next;
 709     SILC_LOG_DEBUG(("Unregistering all tasks at once"));
 710
 711     silc_mutex_lock(queue->lock);
 712
 713     if (!queue->task) {
 714       silc_mutex_unlock(queue->lock);
 715       return;
 716     }
 717
 718     next = queue->task;
 719
 720     while(1) {
 721       if (next->valid)
 722         next->valid = FALSE;
 723       if (queue->task == next->next)
 724         break;
 725       next = next->next;
 726     }
 727
 728     silc_mutex_unlock(queue->lock);
 729     return;
 730   }
 731
 732   SILC_LOG_DEBUG(("Unregistering task"));
 733
 734   silc_mutex_lock(queue->lock);
 735
 736   /* Unregister the specific task */
 737   if (task->valid)
 738     task->valid = FALSE;
 739
 740   silc_mutex_unlock(queue->lock);
 741 }
 742
 743 /* Remove task by fd */
 744
 745 void silc_schedule_task_del_by_fd(SilcSchedule schedule, uint32 fd)
 746 {
 747   SILC_LOG_DEBUG(("Unregister task by fd"));
 748
 749   silc_task_del_by_fd(schedule->timeout_queue, fd);
 750   silc_task_del_by_fd(schedule->fd_queue, fd);
 751 }
 752
 753 /* Remove task by task callback. */
 754
 755 void silc_schedule_task_del_by_callback(SilcSchedule schedule,
 756                                         SilcTaskCallback callback)
 757 {
 758   SILC_LOG_DEBUG(("Unregister task by callback"));
 759
 760   silc_task_del_by_callback(schedule->timeout_queue, callback);
 761   silc_task_del_by_callback(schedule->fd_queue, callback);
 762   silc_task_del_by_callback(schedule->generic_queue, callback);
 763 }
 764
 765 /* Remove task by context. */
 766
 767 void silc_schedule_task_del_by_context(SilcSchedule schedule, void *context)
 768 {
 769   SILC_LOG_DEBUG(("Unregister task by context"));
 770
 771   silc_task_del_by_context(schedule->timeout_queue, context);
 772   silc_task_del_by_context(schedule->fd_queue, context);
 773   silc_task_del_by_context(schedule->generic_queue, context);
 774 }
 775
 776 /* Sets a file descriptor to be listened by select() in scheduler. One can
 777    call this directly if wanted. This can be called multiple times for
 778    one file descriptor to set different iomasks. */
 779
 780 void silc_schedule_set_listen_fd(SilcSchedule schedule,
 781                                  uint32 fd, SilcTaskEvent iomask)
 782 {
 783   int i;
 784   bool found = FALSE;
 785
 786   silc_mutex_lock(schedule->lock);
 787
 788   for (i = 0; i < schedule->max_fd; i++)
 789     if (schedule->fd_list[i].fd == fd) {
 790       schedule->fd_list[i].fd = fd;
 791       schedule->fd_list[i].events = iomask;
 792       if (i > schedule->last_fd)
 793         schedule->last_fd = i;
 794       found = TRUE;
 795       break;
 796     }
 797
 798   if (!found)
 799     for (i = 0; i < schedule->max_fd; i++)
 800       if (schedule->fd_list[i].events == 0) {
 801         schedule->fd_list[i].fd = fd;
 802         schedule->fd_list[i].events = iomask;
 803         if (i > schedule->last_fd)
 804           schedule->last_fd = i;
 805         break;
 806       }
 807
 808   silc_mutex_unlock(schedule->lock);
 809 }
 810
 811 /* Removes a file descriptor from listen list. */
 812
 813 void silc_schedule_unset_listen_fd(SilcSchedule schedule, uint32 fd)
 814 {
 815   int i;
 816
 817   silc_mutex_lock(schedule->lock);
 818
 819   for (i = 0; i < schedule->max_fd; i++)
 820     if (schedule->fd_list[i].fd == fd) {
 821       schedule->fd_list[i].fd = 0;
 822       schedule->fd_list[i].events = 0;
 823       if (schedule->last_fd == i)
 824         schedule->last_fd = schedule->max_fd - 1;
 825       break;
 826     }
 827
 828   silc_mutex_unlock(schedule->lock);
 829 }
 830
 831 /* Allocates a newtask task queue into the scheduler */
 832
 833 static void silc_task_queue_alloc(SilcTaskQueue *queue)
 834 {
 835   *queue = silc_calloc(1, sizeof(**queue));
 836   silc_mutex_alloc(&(*queue)->lock);
 837 }
 838
 839 /* Free's a task queue. */
 840
 841 static void silc_task_queue_free(SilcTaskQueue queue)
 842 {
 843   silc_mutex_free(queue->lock);
 844   silc_free(queue);
 845 }
 846
 847 /* Return task by its fd. */
 848
 849 static SilcTask silc_task_find(SilcTaskQueue queue, uint32 fd)
 850 {
 851   SilcTask next;
 852
 853   if (!queue->task)
 854     return NULL;
 855
 856   next = queue->task;
 857
 858   while (1) {
 859     if (next->fd == fd)
 860       return next;
 861     if (queue->task == next->next)
 862       return NULL;
 863     next = next->next;
 864   }
 865
 866   return NULL;
 867 }
 868
 869 /* Adds a non-timeout task into the task queue. This function is used
 870    by silc_task_register function. Returns a pointer to the registered
 871    task. */
 872
 873 static SilcTask silc_task_add(SilcTaskQueue queue, SilcTask newtask,
 874                               SilcTaskPriority priority)
 875 {
 876   SilcTask task, next, prev;
 877
 878   /* Take the first task in the queue */
 879   task = queue->task;
 880
 881   switch(priority) {
 882   case SILC_TASK_PRI_LOW:
 883     /* Lowest priority. The task is added at the end of the list. */
 884     prev = task->prev;
 885     newtask->prev = prev;
 886     newtask->next = task;
 887     prev->next = newtask;
 888     task->prev = newtask;
 889     break;
 890   case SILC_TASK_PRI_NORMAL:
 891     /* Normal priority. The task is added before lower priority tasks
 892        but after tasks with higher priority. */
 893     prev = task->prev;
 894     while(prev != task) {
 895       if (prev->priority > SILC_TASK_PRI_LOW)
 896         break;
 897       prev = prev->prev;
 898     }
 899     if (prev == task) {
 900       /* There are only lower priorities in the list, we will
 901          sit before them and become the first task in the queue. */
 902       prev = task->prev;
 903       newtask->prev = prev;
 904       newtask->next = task;
 905       task->prev = newtask;
 906       prev->next = newtask;
 907
 908       /* We are now the first task in queue */
 909       queue->task = newtask;
 910     } else {
 911       /* Found a spot from the list, add the task to the list. */
 912       next = prev->next;
 913       newtask->prev = prev;
 914       newtask->next = next;
 915       prev->next = newtask;
 916       next->prev = newtask;
 917     }
 918     break;
 919   default:
 920     silc_free(newtask);
 921     return NULL;
 922   }
 923
 924   return newtask;
 925 }
 926
 927 /* Return the timeout task with smallest timeout. */
 928
 929 static SilcTask silc_task_get_first(SilcTaskQueue queue, SilcTask first)
 930 {
 931   SilcTask prev, task;
 932
 933   prev = first->prev;
 934
 935   if (first == prev)
 936     return first;
 937
 938   task = first;
 939   while (1) {
 940     if (first == prev)
 941       break;
 942
 943     if (silc_schedule_task_timeout_compare(&prev->timeout, &task->timeout))
 944       task = prev;
 945
 946     prev = prev->prev;
 947   }
 948
 949   return task;
 950 }
 951
 952 /* Adds a timeout task into the task queue. This function is used by
 953    silc_task_register function. Returns a pointer to the registered
 954    task. Timeout tasks are sorted by their timeout value in ascending
 955    order. The priority matters if there are more than one task with
 956    same timeout. */
 957
 958 static SilcTask silc_task_add_timeout(SilcTaskQueue queue, SilcTask newtask,
 959                                       SilcTaskPriority priority)
 960 {
 961   SilcTask task, prev, next;
 962
 963   /* Take the first task in the queue */
 964   task = queue->task;
 965
 966   /* Take last task from the list */
 967   prev = task->prev;
 968
 969   switch(priority) {
 970   case SILC_TASK_PRI_LOW:
 971     /* Lowest priority. The task is added at the end of the list. */
 972     while(prev != task) {
 973
 974       /* If we have longer timeout than with the task head of us
 975          we have found our spot. */
 976       if (silc_schedule_task_timeout_compare(&prev->timeout,
 977                                              &newtask->timeout))
 978         break;
 979
 980       /* If we are equal size of timeout we will be after it. */
 981       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
 982                                               &prev->timeout))
 983         break;
 984
 985       /* We have shorter timeout, compare to next one. */
 986       prev = prev->prev;
 987     }
 988     /* Found a spot from the list, add the task to the list. */
 989     next = prev->next;
 990     newtask->prev = prev;
 991     newtask->next = next;
 992     prev->next = newtask;
 993     next->prev = newtask;
 994
 995     if (prev == task) {
 996       /* Check if we are going to be the first task in the queue */
 997       if (silc_schedule_task_timeout_compare(&prev->timeout,
 998                                              &newtask->timeout))
 999         break;
1000       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1001                                               &prev->timeout))
1002         break;
1003
1004       /* We are now the first task in queue */
1005       queue->task = newtask;
1006     }
1007     break;
1008   case SILC_TASK_PRI_NORMAL:
1009     /* Normal priority. The task is added before lower priority tasks
1010        but after tasks with higher priority. */
1011     while(prev != task) {
1012
1013       /* If we have longer timeout than with the task head of us
1014          we have found our spot. */
1015       if (silc_schedule_task_timeout_compare(&prev->timeout,
1016                                              &newtask->timeout))
1017         break;
1018
1019       /* If we are equal size of timeout, priority kicks in place. */
1020       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1021                                               &prev->timeout))
1022         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1023           break;
1024
1025       /* We have shorter timeout or higher priority, compare to next one. */
1026       prev = prev->prev;
1027     }
1028     /* Found a spot from the list, add the task to the list. */
1029     next = prev->next;
1030     newtask->prev = prev;
1031     newtask->next = next;
1032     prev->next = newtask;
1033     next->prev = newtask;
1034
1035     if (prev == task) {
1036       /* Check if we are going to be the first task in the queue */
1037       if (silc_schedule_task_timeout_compare(&prev->timeout,
1038                                              &newtask->timeout))
1039         break;
1040       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1041                                               &prev->timeout))
1042         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1043           break;
1044
1045       /* We are now the first task in queue */
1046       queue->task = newtask;
1047     }
1048     break;
1049   default:
1050     silc_free(newtask);
1051     return NULL;
1052   }
1053
1054   return newtask;
1055 }
1056
1057 /* Removes (unregisters) a task from particular task queue. This function
1058    is used internally by scheduler. This must be called holding the
1059    queue->lock. */
1060
1061 static int silc_schedule_task_remove(SilcTaskQueue queue, SilcTask task)
1062 {
1063   SilcTask first, old, next;
1064
1065   if (!queue || !task)
1066     return FALSE;
1067
1068   if (!queue->task) {
1069     return FALSE;
1070   }
1071
1072   first = queue->task;
1073
1074   /* Unregister all tasks in queue */
1075   if (task == SILC_ALL_TASKS) {
1076     SILC_LOG_DEBUG(("Removing all tasks at once"));
1077     next = first;
1078
1079     while(1) {
1080       next = next->next;
1081       silc_free(next->prev);
1082       if (next == first)
1083         break;
1084     }
1085
1086     queue->task = NULL;
1087     return TRUE;
1088   }
1089
1090   SILC_LOG_DEBUG(("Removing task"));
1091
1092   /* Unregister the task */
1093   old = first;
1094   while(1) {
1095     if (old == task) {
1096       SilcTask prev, next;
1097
1098       prev = old->prev;
1099       next = old->next;
1100       prev->next = next;
1101       next->prev = prev;
1102
1103       if (prev == old && next == old)
1104         queue->task = NULL;
1105       if (queue->task == old)
1106         queue->task = silc_task_get_first(queue, next);
1107
1108       silc_free(old);
1109       return TRUE;
1110     }
1111     old = old->prev;
1112
1113     if (old == first) {
1114       return FALSE;
1115     }
1116   }
1117 }
1118
1119 /* Compare two time values. If the first argument is smaller than the
1120    second this function returns TRUE. */
1121
1122 static int silc_schedule_task_timeout_compare(struct timeval *smaller,
1123                                               struct timeval *bigger)
1124 {
1125   if ((smaller->tv_sec < bigger->tv_sec) ||
1126       ((smaller->tv_sec == bigger->tv_sec) &&
1127        (smaller->tv_usec < bigger->tv_usec)))
1128     return TRUE;
1129
1130   return FALSE;
1131 }
1132
1133 static void silc_task_del_by_fd(SilcTaskQueue queue, uint32 fd)
1134 {
1135   SilcTask next;
1136
1137   silc_mutex_lock(queue->lock);
1138
1139   if (!queue->task) {
1140     silc_mutex_unlock(queue->lock);
1141     return;
1142   }
1143
1144   next = queue->task;
1145
1146   while(1) {
1147     if (next->fd == fd)
1148       next->valid = FALSE;
1149     if (queue->task == next->next)
1150       break;
1151     next = next->next;
1152   }
1153
1154   silc_mutex_unlock(queue->lock);
1155 }
1156
1157 static void silc_task_del_by_callback(SilcTaskQueue queue,
1158                                       SilcTaskCallback callback)
1159 {
1160   SilcTask next;
1161
1162   silc_mutex_lock(queue->lock);
1163
1164   if (!queue->task) {
1165     silc_mutex_unlock(queue->lock);
1166     return;
1167   }
1168
1169   next = queue->task;
1170
1171   while(1) {
1172     if (next->callback == callback)
1173       next->valid = FALSE;
1174     if (queue->task == next->next)
1175       break;
1176     next = next->next;
1177   }
1178
1179   silc_mutex_unlock(queue->lock);
1180 }
1181
1182 static void silc_task_del_by_context(SilcTaskQueue queue, void *context)
1183 {
1184   SilcTask next;
1185
1186   silc_mutex_lock(queue->lock);
1187
1188   if (!queue->task) {
1189     silc_mutex_unlock(queue->lock);
1190     return;
1191   }
1192
1193   next = queue->task;
1194
1195   while(1) {
1196     if (next->context == context)
1197       next->valid = FALSE;
1198     if (queue->task == next->next)
1199       break;
1200     next = next->next;
1201   }
1202
1203   silc_mutex_unlock(queue->lock);
1204 }