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