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, SilcUInt32 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, SilcUInt32 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, SilcUInt32 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   SilcUInt32 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    SilcUInt32 max_fd
 135    SilcUInt32 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   SilcUInt32 max_fd;
 176   SilcUInt32 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   if (!max_tasks)
 204     max_tasks = 200;
 205
 206   /* Initialize the scheduler */
 207   schedule->fd_list = silc_calloc(max_tasks, sizeof(*schedule->fd_list));
 208   schedule->max_fd = max_tasks;
 209   schedule->timeout = NULL;
 210   schedule->valid = TRUE;
 211
 212   /* Allocate scheduler lock */
 213   silc_mutex_alloc(&schedule->lock);
 214
 215   /* Initialize the wakeup, for multi-threads support */
 216   schedule->wakeup = silc_schedule_wakeup_init(schedule);
 217
 218   return schedule;
 219 }
 220
 221 /* Uninitializes the schedule. This is called when the program is ready
 222    to end. This removes all tasks and task queues. Returns FALSE if the
 223    scheduler could not be uninitialized. This happens when the scheduler
 224    is still valid and silc_schedule_stop has not been called. */
 225
 226 bool silc_schedule_uninit(SilcSchedule schedule)
 227 {
 228   SILC_LOG_DEBUG(("Uninitializing scheduler"));
 229
 230   if (schedule->valid == TRUE)
 231     return FALSE;
 232
 233   /* Unregister all tasks */
 234   silc_schedule_task_remove(schedule->fd_queue, SILC_ALL_TASKS);
 235   silc_schedule_task_remove(schedule->timeout_queue, SILC_ALL_TASKS);
 236   silc_schedule_task_remove(schedule->generic_queue, SILC_ALL_TASKS);
 237
 238   /* Unregister all task queues */
 239   silc_task_queue_free(schedule->fd_queue);
 240   silc_task_queue_free(schedule->timeout_queue);
 241   silc_task_queue_free(schedule->generic_queue);
 242
 243   silc_free(schedule->fd_list);
 244
 245   /* Uninit the wakeup */
 246   silc_schedule_wakeup_uninit(schedule->wakeup);
 247
 248   silc_mutex_free(schedule->lock);
 249
 250   return TRUE;
 251 }
 252
 253 /* Enlarge the capabilities of the scheduler to handle tasks to `max_tasks'. */
 254
 255 bool silc_schedule_reinit(SilcSchedule schedule, int max_tasks)
 256 {
 257   silc_mutex_lock(schedule->lock);
 258   if (schedule->max_fd <= max_tasks)
 259     return FALSE;
 260   schedule->fd_list = silc_realloc(schedule->fd_list,
 261                                    (sizeof(*schedule->fd_list) * max_tasks));
 262   schedule->max_fd = max_tasks;
 263   silc_mutex_unlock(schedule->lock);
 264   return TRUE;
 265 }
 266
 267 /* Stops the schedule even if it is not supposed to be stopped yet.
 268    After calling this, one should call silc_schedule_uninit (after the
 269    silc_schedule has returned). */
 270
 271 void silc_schedule_stop(SilcSchedule schedule)
 272 {
 273   SILC_LOG_DEBUG(("Stopping scheduler"));
 274   schedule->valid = FALSE;
 275 }
 276
 277 /* Executes nontimeout tasks. It then checks whether any of ther fd tasks
 278    was signaled by the silc_select. If some task was not signaled then
 279    all generic tasks are executed for that task. The generic tasks are
 280    never executed for task that has explicit fd task set. */
 281 /* This holds the schedule->lock and the queue locks. */
 282
 283 static void silc_schedule_dispatch_nontimeout(SilcSchedule schedule)
 284 {
 285   SilcTask task;
 286   int i, last_fd = schedule->last_fd;
 287   SilcUInt32 fd;
 288
 289   for (i = 0; i <= last_fd; i++) {
 290     if (schedule->fd_list[i].events == 0)
 291       continue;
 292
 293     fd = schedule->fd_list[i].fd;
 294
 295     /* First check whether this fd has task in the fd queue */
 296     silc_mutex_lock(schedule->fd_queue->lock);
 297     task = silc_task_find(schedule->fd_queue, fd);
 298
 299     /* If the task was found then execute its callbacks. If not then
 300        execute all generic tasks for that fd. */
 301     if (task) {
 302       /* Validity of the task is checked always before and after
 303          execution beacuse the task might have been unregistered
 304          in the callback function, ie. it is not valid anymore. */
 305
 306       /* Is the task ready for reading */
 307       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 308         silc_mutex_unlock(schedule->fd_queue->lock);
 309         silc_mutex_unlock(schedule->lock);
 310         task->callback(schedule, SILC_TASK_READ, task->fd, task->context);
 311         silc_mutex_lock(schedule->lock);
 312         silc_mutex_lock(schedule->fd_queue->lock);
 313       }
 314
 315       /* Is the task ready for writing */
 316       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 317         silc_mutex_unlock(schedule->fd_queue->lock);
 318         silc_mutex_unlock(schedule->lock);
 319         task->callback(schedule, SILC_TASK_WRITE, task->fd, task->context);
 320         silc_mutex_lock(schedule->lock);
 321         silc_mutex_lock(schedule->fd_queue->lock);
 322       }
 323
 324       if (!task->valid)
 325         silc_schedule_task_remove(schedule->fd_queue, task);
 326
 327       silc_mutex_unlock(schedule->fd_queue->lock);
 328     } else {
 329       /* Run generic tasks for this fd. */
 330
 331       silc_mutex_unlock(schedule->fd_queue->lock);
 332
 333       silc_mutex_lock(schedule->generic_queue->lock);
 334       if (!schedule->generic_queue->task) {
 335         silc_mutex_unlock(schedule->generic_queue->lock);
 336         continue;
 337       }
 338
 339       task = schedule->generic_queue->task;
 340       while(1) {
 341         /* Validity of the task is checked always before and after
 342            execution beacuse the task might have been unregistered
 343            in the callback function, ie. it is not valid anymore. */
 344
 345         /* Is the task ready for reading */
 346         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 347           silc_mutex_unlock(schedule->generic_queue->lock);
 348           silc_mutex_unlock(schedule->lock);
 349           task->callback(schedule, SILC_TASK_READ, fd, task->context);
 350           silc_mutex_lock(schedule->lock);
 351           silc_mutex_lock(schedule->generic_queue->lock);
 352         }
 353
 354         /* Is the task ready for writing */
 355         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 356           silc_mutex_unlock(schedule->generic_queue->lock);
 357           silc_mutex_unlock(schedule->lock);
 358           task->callback(schedule, SILC_TASK_WRITE, fd, task->context);
 359           silc_mutex_lock(schedule->lock);
 360           silc_mutex_lock(schedule->generic_queue->lock);
 361         }
 362
 363         if (!task->valid) {
 364           /* Invalid (unregistered) tasks are removed from the
 365              task queue. */
 366           if (schedule->generic_queue->task == task->next) {
 367             silc_schedule_task_remove(schedule->generic_queue, task);
 368             silc_mutex_unlock(schedule->generic_queue->lock);
 369             break;
 370           }
 371
 372           task = task->next;
 373           silc_schedule_task_remove(schedule->generic_queue, task);
 374           continue;
 375         }
 376
 377         /* Break if there isn't more tasks in the queue */
 378         if (schedule->generic_queue->task == task->next)
 379           break;
 380
 381         task = task->next;
 382       }
 383
 384       silc_mutex_unlock(schedule->generic_queue->lock);
 385     }
 386   }
 387 }
 388
 389 /* Executes all tasks whose timeout has expired. The task is removed from
 390    the task queue after the callback function has returned. Also, invalid
 391    tasks are removed here. We don't have to care about priorities because
 392    tasks are already sorted in their priority order at the registration
 393    phase. */
 394 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 395
 396 static void silc_schedule_dispatch_timeout(SilcSchedule schedule)
 397 {
 398   SilcTaskQueue queue = schedule->timeout_queue;
 399   SilcTask task;
 400   struct timeval curtime;
 401
 402   SILC_LOG_DEBUG(("Running timeout tasks"));
 403
 404   silc_gettimeofday(&curtime);
 405
 406   queue = schedule->timeout_queue;
 407   if (queue && queue->task) {
 408     task = queue->task;
 409
 410     /* Walk thorugh all tasks in the particular task queue and run all
 411        the expired tasks. */
 412     while(1) {
 413       /* Execute the task if the timeout has expired */
 414       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 415         if (task->valid) {
 416           silc_mutex_unlock(queue->lock);
 417           silc_mutex_unlock(schedule->lock);
 418           task->callback(schedule, SILC_TASK_EXPIRE, task->fd, task->context);
 419           silc_mutex_lock(schedule->lock);
 420           silc_mutex_lock(queue->lock);
 421         }
 422
 423         /* Break if there isn't more tasks in the queue */
 424         if (queue->task == task->next) {
 425           silc_schedule_task_remove(queue, task);
 426           break;
 427         }
 428
 429         task = task->next;
 430
 431         /* Remove the task from queue */
 432         silc_schedule_task_remove(queue, task->prev);
 433       } else {
 434         /* The timeout hasn't expired, check for next one */
 435
 436         /* Break if there isn't more tasks in the queue */
 437         if (queue->task == task->next)
 438           break;
 439
 440         task = task->next;
 441       }
 442     }
 443   }
 444 }
 445
 446 /* Calculates next timeout for select(). This is the timeout value
 447    when at earliest some of the timeout tasks expire. If this is in the
 448    past, they will be run now. */
 449 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 450
 451 static void silc_schedule_select_timeout(SilcSchedule schedule)
 452 {
 453   SilcTaskQueue queue = schedule->timeout_queue;
 454   SilcTask task;
 455   struct timeval curtime;
 456
 457   /* Get the current time */
 458   silc_gettimeofday(&curtime);
 459   schedule->timeout = NULL;
 460
 461   /* First task in the task queue has always the smallest timeout. */
 462   task = queue->task;
 463   while(1) {
 464     if (task && task->valid == TRUE) {
 465       /* If the timeout is in past, we will run the task and all other
 466          timeout tasks from the past. */
 467       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 468         silc_schedule_dispatch_timeout(schedule);
 469
 470         /* The task(s) has expired and doesn't exist on the task queue
 471            anymore. We continue with new timeout. */
 472         queue = schedule->timeout_queue;
 473         task = queue->task;
 474         if (task == NULL || task->valid == FALSE)
 475           break;
 476       }
 477
 478       /* Calculate the next timeout for select() */
 479       queue->timeout.tv_sec = task->timeout.tv_sec - curtime.tv_sec;
 480       queue->timeout.tv_usec = task->timeout.tv_usec - curtime.tv_usec;
 481       if (queue->timeout.tv_sec < 0)
 482         queue->timeout.tv_sec = 0;
 483
 484       /* We wouldn't want to go under zero, check for it. */
 485       if (queue->timeout.tv_usec < 0) {
 486         queue->timeout.tv_sec -= 1;
 487         if (queue->timeout.tv_sec < 0)
 488           queue->timeout.tv_sec = 0;
 489         queue->timeout.tv_usec += 1000000L;
 490       }
 491
 492       /* We've got the timeout value */
 493       break;
 494     } else {
 495       /* Task is not valid, remove it and try next one. */
 496       silc_schedule_task_remove(queue, task);
 497       task = queue->task;
 498       if (queue->task == NULL)
 499         break;
 500     }
 501   }
 502
 503   /* Save the timeout */
 504   if (task) {
 505     schedule->timeout = &queue->timeout;
 506     SILC_LOG_DEBUG(("timeout: sec=%d, usec=%d", schedule->timeout->tv_sec,
 507                     schedule->timeout->tv_usec));
 508   }
 509 }
 510
 511 /* Runs the scheduler once and then returns. */
 512
 513 bool silc_schedule_one(SilcSchedule schedule, int timeout_usecs)
 514 {
 515   struct timeval timeout;
 516   int ret;
 517
 518   SILC_LOG_DEBUG(("In scheduler loop"));
 519
 520   if (!schedule->is_locked)
 521     silc_mutex_lock(schedule->lock);
 522
 523   /* If the task queues aren't initialized or we aren't valid anymore
 524      we will return */
 525   if ((!schedule->fd_queue && !schedule->timeout_queue
 526        && !schedule->generic_queue) || schedule->valid == FALSE) {
 527     SILC_LOG_DEBUG(("Scheduler not valid anymore, exiting"));
 528     if (!schedule->is_locked)
 529       silc_mutex_unlock(schedule->lock);
 530     return FALSE;
 531   }
 532
 533   /* Calculate next timeout for silc_select(). This is the timeout value
 534      when at earliest some of the timeout tasks expire. */
 535   silc_mutex_lock(schedule->timeout_queue->lock);
 536   silc_schedule_select_timeout(schedule);
 537   silc_mutex_unlock(schedule->timeout_queue->lock);
 538
 539   if (timeout_usecs >= 0) {
 540     timeout.tv_sec = 0;
 541     timeout.tv_usec = timeout_usecs;
 542     schedule->timeout = &timeout;
 543   }
 544
 545   silc_mutex_unlock(schedule->lock);
 546
 547   /* This is the main select(). The program blocks here until some
 548      of the selected file descriptors change status or the selected
 549      timeout expires. */
 550   SILC_LOG_DEBUG(("Select"));
 551   ret = silc_select(schedule->fd_list, schedule->last_fd + 1,
 552                     schedule->timeout);
 553
 554   silc_mutex_lock(schedule->lock);
 555
 556   switch (ret) {
 557   case -1:
 558     /* Error */
 559     if (errno == EINTR)
 560       break;
 561     SILC_LOG_ERROR(("Error in select(): %s", strerror(errno)));
 562     break;
 563   case 0:
 564     /* Timeout */
 565     silc_mutex_lock(schedule->timeout_queue->lock);
 566     silc_schedule_dispatch_timeout(schedule);
 567     silc_mutex_unlock(schedule->timeout_queue->lock);
 568     break;
 569   default:
 570     /* There is some data available now */
 571     SILC_LOG_DEBUG(("Running non-timeout tasks"));
 572     silc_schedule_dispatch_nontimeout(schedule);
 573     break;
 574   }
 575
 576   if (!schedule->is_locked)
 577     silc_mutex_unlock(schedule->lock);
 578
 579   return TRUE;
 580 }
 581
 582 /* The SILC scheduler. This is actually the main routine in SILC programs.
 583    When this returns the program is to be ended. Before this function can
 584    be called, one must call silc_schedule_init function. */
 585
 586 void silc_schedule(SilcSchedule schedule)
 587 {
 588   SILC_LOG_DEBUG(("Running scheduler"));
 589
 590   if (schedule->valid == FALSE) {
 591     SILC_LOG_ERROR(("Scheduler is not valid, stopping"));
 592     return;
 593   }
 594
 595   silc_mutex_lock(schedule->lock);
 596   schedule->is_locked = TRUE;
 597
 598   /* Start the scheduler loop */
 599   while (silc_schedule_one(schedule, -1))
 600     ;
 601
 602   silc_mutex_unlock(schedule->lock);
 603 }
 604
 605 /* Wakes up the scheduler. This is used only in multi-threaded
 606    environments where threads may add new tasks or remove old tasks
 607    from task queues. This is called to wake up the scheduler in the
 608    main thread so that it detects the changes in the task queues.
 609    If threads support is not compiled in this function has no effect.
 610    Implementation of this function is platform specific. */
 611
 612 void silc_schedule_wakeup(SilcSchedule schedule)
 613 {
 614 #ifdef SILC_THREADS
 615   SILC_LOG_DEBUG(("Wakeup scheduler"));
 616   silc_mutex_lock(schedule->lock);
 617   silc_schedule_wakeup_internal(schedule->wakeup);
 618   silc_mutex_unlock(schedule->lock);
 619 #endif
 620 }
 621
 622 /* Add new task to the scheduler */
 623
 624 SilcTask silc_schedule_task_add(SilcSchedule schedule, SilcUInt32 fd,
 625                                 SilcTaskCallback callback, void *context,
 626                                 long seconds, long useconds,
 627                                 SilcTaskType type,
 628                                 SilcTaskPriority priority)
 629 {
 630   SilcTask newtask;
 631   SilcTaskQueue queue;
 632   int timeout = FALSE;
 633
 634   SILC_LOG_DEBUG(("Registering new task, fd=%d type=%d priority=%d", fd,
 635                   type, priority));
 636
 637   queue = SILC_SCHEDULE_GET_QUEUE(type);
 638
 639   /* If the task is generic task, we check whether this task has already
 640      been registered. Generic tasks are registered only once and after that
 641      the same task applies to all file descriptors to be registered. */
 642   if (type == SILC_TASK_GENERIC) {
 643     silc_mutex_lock(queue->lock);
 644
 645     if (queue->task) {
 646       SilcTask task = queue->task;
 647       while(1) {
 648         if ((task->callback == callback) && (task->context == context)) {
 649           SILC_LOG_DEBUG(("Found matching generic task, using the match"));
 650
 651           silc_mutex_unlock(queue->lock);
 652
 653           /* Add the fd to be listened, the task found now applies to this
 654              fd as well. */
 655           silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 656           return task;
 657         }
 658
 659         if (queue->task == task->next)
 660           break;
 661
 662         task = task->next;
 663       }
 664     }
 665
 666     silc_mutex_unlock(queue->lock);
 667   }
 668
 669   newtask = silc_calloc(1, sizeof(*newtask));
 670   newtask->fd = fd;
 671   newtask->context = context;
 672   newtask->callback = callback;
 673   newtask->valid = TRUE;
 674   newtask->priority = priority;
 675   newtask->type = type;
 676   newtask->next = newtask;
 677   newtask->prev = newtask;
 678
 679   /* Create timeout if marked to be timeout task */
 680   if (((seconds + useconds) > 0) && (type == SILC_TASK_TIMEOUT)) {
 681     silc_gettimeofday(&newtask->timeout);
 682     newtask->timeout.tv_sec += seconds + (useconds / 1000000L);
 683     newtask->timeout.tv_usec += (useconds % 1000000L);
 684     if (newtask->timeout.tv_usec > 999999L) {
 685       newtask->timeout.tv_sec += 1;
 686       newtask->timeout.tv_usec -= 1000000L;
 687     }
 688     timeout = TRUE;
 689   }
 690
 691   /* If the task is non-timeout task we have to tell the scheduler that we
 692      would like to have these tasks scheduled at some odd distant future. */
 693   if (type != SILC_TASK_TIMEOUT)
 694     silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 695
 696   silc_mutex_lock(queue->lock);
 697
 698   /* Is this first task of the queue? */
 699   if (queue->task == NULL) {
 700     queue->task = newtask;
 701     silc_mutex_unlock(queue->lock);
 702     return newtask;
 703   }
 704
 705   if (timeout)
 706     newtask = silc_task_add_timeout(queue, newtask, priority);
 707   else
 708     newtask = silc_task_add(queue, newtask, priority);
 709
 710   silc_mutex_unlock(queue->lock);
 711
 712   return newtask;
 713 }
 714
 715 /* Removes a task from the scheduler */
 716
 717 void silc_schedule_task_del(SilcSchedule schedule, SilcTask task)
 718 {
 719   SilcTaskQueue queue = SILC_SCHEDULE_GET_QUEUE(task->type);
 720
 721   /* Unregister all tasks */
 722   if (task == SILC_ALL_TASKS) {
 723     SilcTask next;
 724     SILC_LOG_DEBUG(("Unregistering all tasks at once"));
 725
 726     silc_mutex_lock(queue->lock);
 727
 728     if (!queue->task) {
 729       silc_mutex_unlock(queue->lock);
 730       return;
 731     }
 732
 733     next = queue->task;
 734
 735     while(1) {
 736       if (next->valid)
 737         next->valid = FALSE;
 738       if (queue->task == next->next)
 739         break;
 740       next = next->next;
 741     }
 742
 743     silc_mutex_unlock(queue->lock);
 744     return;
 745   }
 746
 747   SILC_LOG_DEBUG(("Unregistering task"));
 748
 749   silc_mutex_lock(queue->lock);
 750
 751   /* Unregister the specific task */
 752   if (task->valid)
 753     task->valid = FALSE;
 754
 755   silc_mutex_unlock(queue->lock);
 756 }
 757
 758 /* Remove task by fd */
 759
 760 void silc_schedule_task_del_by_fd(SilcSchedule schedule, SilcUInt32 fd)
 761 {
 762   SILC_LOG_DEBUG(("Unregister task by fd %d", fd));
 763
 764   silc_task_del_by_fd(schedule->timeout_queue, fd);
 765   silc_task_del_by_fd(schedule->fd_queue, fd);
 766 }
 767
 768 /* Remove task by task callback. */
 769
 770 void silc_schedule_task_del_by_callback(SilcSchedule schedule,
 771                                         SilcTaskCallback callback)
 772 {
 773   SILC_LOG_DEBUG(("Unregister task by callback"));
 774
 775   silc_task_del_by_callback(schedule->timeout_queue, callback);
 776   silc_task_del_by_callback(schedule->fd_queue, callback);
 777   silc_task_del_by_callback(schedule->generic_queue, callback);
 778 }
 779
 780 /* Remove task by context. */
 781
 782 void silc_schedule_task_del_by_context(SilcSchedule schedule, void *context)
 783 {
 784   SILC_LOG_DEBUG(("Unregister task by context"));
 785
 786   silc_task_del_by_context(schedule->timeout_queue, context);
 787   silc_task_del_by_context(schedule->fd_queue, context);
 788   silc_task_del_by_context(schedule->generic_queue, context);
 789 }
 790
 791 /* Sets a file descriptor to be listened by select() in scheduler. One can
 792    call this directly if wanted. This can be called multiple times for
 793    one file descriptor to set different iomasks. */
 794
 795 void silc_schedule_set_listen_fd(SilcSchedule schedule,
 796                                  SilcUInt32 fd, SilcTaskEvent iomask)
 797 {
 798   int i;
 799   bool found = FALSE;
 800
 801   silc_mutex_lock(schedule->lock);
 802
 803   for (i = 0; i < schedule->max_fd; i++)
 804     if (schedule->fd_list[i].fd == fd) {
 805       schedule->fd_list[i].fd = fd;
 806       schedule->fd_list[i].events = iomask;
 807       if (i > schedule->last_fd)
 808         schedule->last_fd = i;
 809       found = TRUE;
 810       break;
 811     }
 812
 813   if (!found)
 814     for (i = 0; i < schedule->max_fd; i++)
 815       if (schedule->fd_list[i].events == 0) {
 816         schedule->fd_list[i].fd = fd;
 817         schedule->fd_list[i].events = iomask;
 818         if (i > schedule->last_fd)
 819           schedule->last_fd = i;
 820         break;
 821       }
 822
 823   silc_mutex_unlock(schedule->lock);
 824 }
 825
 826 /* Removes a file descriptor from listen list. */
 827
 828 void silc_schedule_unset_listen_fd(SilcSchedule schedule, SilcUInt32 fd)
 829 {
 830   int i;
 831
 832   silc_mutex_lock(schedule->lock);
 833
 834   SILC_LOG_DEBUG(("Unset listen fd %d", fd));
 835
 836   for (i = 0; i < schedule->max_fd; i++)
 837     if (schedule->fd_list[i].fd == fd) {
 838       schedule->fd_list[i].fd = 0;
 839       schedule->fd_list[i].events = 0;
 840       if (schedule->last_fd == i)
 841         schedule->last_fd = schedule->max_fd - 1;
 842       break;
 843     }
 844
 845   silc_mutex_unlock(schedule->lock);
 846 }
 847
 848 /* Allocates a newtask task queue into the scheduler */
 849
 850 static void silc_task_queue_alloc(SilcTaskQueue *queue)
 851 {
 852   *queue = silc_calloc(1, sizeof(**queue));
 853   silc_mutex_alloc(&(*queue)->lock);
 854 }
 855
 856 /* Free's a task queue. */
 857
 858 static void silc_task_queue_free(SilcTaskQueue queue)
 859 {
 860   silc_mutex_free(queue->lock);
 861   silc_free(queue);
 862 }
 863
 864 /* Return task by its fd. */
 865
 866 static SilcTask silc_task_find(SilcTaskQueue queue, SilcUInt32 fd)
 867 {
 868   SilcTask next;
 869
 870   if (!queue->task)
 871     return NULL;
 872
 873   next = queue->task;
 874
 875   while (1) {
 876     if (next->fd == fd)
 877       return next;
 878     if (queue->task == next->next)
 879       return NULL;
 880     next = next->next;
 881   }
 882
 883   return NULL;
 884 }
 885
 886 /* Adds a non-timeout task into the task queue. This function is used
 887    by silc_task_register function. Returns a pointer to the registered
 888    task. */
 889
 890 static SilcTask silc_task_add(SilcTaskQueue queue, SilcTask newtask,
 891                               SilcTaskPriority priority)
 892 {
 893   SilcTask task, next, prev;
 894
 895   /* Take the first task in the queue */
 896   task = queue->task;
 897
 898   switch(priority) {
 899   case SILC_TASK_PRI_LOW:
 900     /* Lowest priority. The task is added at the end of the list. */
 901     prev = task->prev;
 902     newtask->prev = prev;
 903     newtask->next = task;
 904     prev->next = newtask;
 905     task->prev = newtask;
 906     break;
 907   case SILC_TASK_PRI_NORMAL:
 908     /* Normal priority. The task is added before lower priority tasks
 909        but after tasks with higher priority. */
 910     prev = task->prev;
 911     while(prev != task) {
 912       if (prev->priority > SILC_TASK_PRI_LOW)
 913         break;
 914       prev = prev->prev;
 915     }
 916     if (prev == task) {
 917       /* There are only lower priorities in the list, we will
 918          sit before them and become the first task in the queue. */
 919       prev = task->prev;
 920       newtask->prev = prev;
 921       newtask->next = task;
 922       task->prev = newtask;
 923       prev->next = newtask;
 924
 925       /* We are now the first task in queue */
 926       queue->task = newtask;
 927     } else {
 928       /* Found a spot from the list, add the task to the list. */
 929       next = prev->next;
 930       newtask->prev = prev;
 931       newtask->next = next;
 932       prev->next = newtask;
 933       next->prev = newtask;
 934     }
 935     break;
 936   default:
 937     silc_free(newtask);
 938     return NULL;
 939   }
 940
 941   return newtask;
 942 }
 943
 944 /* Return the timeout task with smallest timeout. */
 945
 946 static SilcTask silc_task_get_first(SilcTaskQueue queue, SilcTask first)
 947 {
 948   SilcTask prev, task;
 949
 950   prev = first->prev;
 951
 952   if (first == prev)
 953     return first;
 954
 955   task = first;
 956   while (1) {
 957     if (first == prev)
 958       break;
 959
 960     if (silc_schedule_task_timeout_compare(&prev->timeout, &task->timeout))
 961       task = prev;
 962
 963     prev = prev->prev;
 964   }
 965
 966   return task;
 967 }
 968
 969 /* Adds a timeout task into the task queue. This function is used by
 970    silc_task_register function. Returns a pointer to the registered
 971    task. Timeout tasks are sorted by their timeout value in ascending
 972    order. The priority matters if there are more than one task with
 973    same timeout. */
 974
 975 static SilcTask silc_task_add_timeout(SilcTaskQueue queue, SilcTask newtask,
 976                                       SilcTaskPriority priority)
 977 {
 978   SilcTask task, prev, next;
 979
 980   /* Take the first task in the queue */
 981   task = queue->task;
 982
 983   /* Take last task from the list */
 984   prev = task->prev;
 985
 986   switch(priority) {
 987   case SILC_TASK_PRI_LOW:
 988     /* Lowest priority. The task is added at the end of the list. */
 989     while(prev != task) {
 990
 991       /* If we have longer timeout than with the task head of us
 992          we have found our spot. */
 993       if (silc_schedule_task_timeout_compare(&prev->timeout,
 994                                              &newtask->timeout))
 995         break;
 996
 997       /* If we are equal size of timeout we will be after it. */
 998       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
 999                                               &prev->timeout))
1000         break;
1001
1002       /* We have shorter timeout, compare to next one. */
1003       prev = prev->prev;
1004     }
1005     /* Found a spot from the list, add the task to the list. */
1006     next = prev->next;
1007     newtask->prev = prev;
1008     newtask->next = next;
1009     prev->next = newtask;
1010     next->prev = newtask;
1011
1012     if (prev == task) {
1013       /* Check if we are going to be the first task in the queue */
1014       if (silc_schedule_task_timeout_compare(&prev->timeout,
1015                                              &newtask->timeout))
1016         break;
1017       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1018                                               &prev->timeout))
1019         break;
1020
1021       /* We are now the first task in queue */
1022       queue->task = newtask;
1023     }
1024     break;
1025   case SILC_TASK_PRI_NORMAL:
1026     /* Normal priority. The task is added before lower priority tasks
1027        but after tasks with higher priority. */
1028     while(prev != task) {
1029
1030       /* If we have longer timeout than with the task head of us
1031          we have found our spot. */
1032       if (silc_schedule_task_timeout_compare(&prev->timeout,
1033                                              &newtask->timeout))
1034         break;
1035
1036       /* If we are equal size of timeout, priority kicks in place. */
1037       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1038                                               &prev->timeout))
1039         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1040           break;
1041
1042       /* We have shorter timeout or higher priority, compare to next one. */
1043       prev = prev->prev;
1044     }
1045     /* Found a spot from the list, add the task to the list. */
1046     next = prev->next;
1047     newtask->prev = prev;
1048     newtask->next = next;
1049     prev->next = newtask;
1050     next->prev = newtask;
1051
1052     if (prev == task) {
1053       /* Check if we are going to be the first task in the queue */
1054       if (silc_schedule_task_timeout_compare(&prev->timeout,
1055                                              &newtask->timeout))
1056         break;
1057       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1058                                               &prev->timeout))
1059         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1060           break;
1061
1062       /* We are now the first task in queue */
1063       queue->task = newtask;
1064     }
1065     break;
1066   default:
1067     silc_free(newtask);
1068     return NULL;
1069   }
1070
1071   return newtask;
1072 }
1073
1074 /* Removes (unregisters) a task from particular task queue. This function
1075    is used internally by scheduler. This must be called holding the
1076    queue->lock. */
1077
1078 static int silc_schedule_task_remove(SilcTaskQueue queue, SilcTask task)
1079 {
1080   SilcTask first, old, next;
1081
1082   if (!queue || !task)
1083     return FALSE;
1084
1085   if (!queue->task) {
1086     return FALSE;
1087   }
1088
1089   first = queue->task;
1090
1091   /* Unregister all tasks in queue */
1092   if (task == SILC_ALL_TASKS) {
1093     SILC_LOG_DEBUG(("Removing all tasks at once"));
1094     next = first;
1095
1096     while(1) {
1097       next = next->next;
1098       silc_free(next->prev);
1099       if (next == first)
1100         break;
1101     }
1102
1103     queue->task = NULL;
1104     return TRUE;
1105   }
1106
1107   SILC_LOG_DEBUG(("Removing task"));
1108
1109   /* Unregister the task */
1110   old = first;
1111   while(1) {
1112     if (old == task) {
1113       SilcTask prev, next;
1114
1115       prev = old->prev;
1116       next = old->next;
1117       prev->next = next;
1118       next->prev = prev;
1119
1120       if (prev == old && next == old)
1121         queue->task = NULL;
1122       if (queue->task == old)
1123         queue->task = silc_task_get_first(queue, next);
1124
1125       silc_free(old);
1126       return TRUE;
1127     }
1128     old = old->prev;
1129
1130     if (old == first) {
1131       return FALSE;
1132     }
1133   }
1134 }
1135
1136 /* Compare two time values. If the first argument is smaller than the
1137    second this function returns TRUE. */
1138
1139 static int silc_schedule_task_timeout_compare(struct timeval *smaller,
1140                                               struct timeval *bigger)
1141 {
1142   if ((smaller->tv_sec < bigger->tv_sec) ||
1143       ((smaller->tv_sec == bigger->tv_sec) &&
1144        (smaller->tv_usec < bigger->tv_usec)))
1145     return TRUE;
1146
1147   return FALSE;
1148 }
1149
1150 static void silc_task_del_by_fd(SilcTaskQueue queue, SilcUInt32 fd)
1151 {
1152   SilcTask next;
1153
1154   silc_mutex_lock(queue->lock);
1155
1156   if (!queue->task) {
1157     silc_mutex_unlock(queue->lock);
1158     return;
1159   }
1160
1161   next = queue->task;
1162
1163   while(1) {
1164     if (next->fd == fd)
1165       next->valid = FALSE;
1166     if (queue->task == next->next)
1167       break;
1168     next = next->next;
1169   }
1170
1171   silc_mutex_unlock(queue->lock);
1172 }
1173
1174 static void silc_task_del_by_callback(SilcTaskQueue queue,
1175                                       SilcTaskCallback callback)
1176 {
1177   SilcTask next;
1178
1179   silc_mutex_lock(queue->lock);
1180
1181   if (!queue->task) {
1182     silc_mutex_unlock(queue->lock);
1183     return;
1184   }
1185
1186   next = queue->task;
1187
1188   while(1) {
1189     if (next->callback == callback)
1190       next->valid = FALSE;
1191     if (queue->task == next->next)
1192       break;
1193     next = next->next;
1194   }
1195
1196   silc_mutex_unlock(queue->lock);
1197 }
1198
1199 static void silc_task_del_by_context(SilcTaskQueue queue, void *context)
1200 {
1201   SilcTask next;
1202
1203   silc_mutex_lock(queue->lock);
1204
1205   if (!queue->task) {
1206     silc_mutex_unlock(queue->lock);
1207     return;
1208   }
1209
1210   next = queue->task;
1211
1212   while(1) {
1213     if (next->context == context)
1214       next->valid = FALSE;
1215     if (queue->task == next->next)
1216       break;
1217     next = next->next;
1218   }
1219
1220   silc_mutex_unlock(queue->lock);
1221 }