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"));
 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   for (i = 0; i < schedule->max_fd; i++)
 823     if (schedule->fd_list[i].fd == fd) {
 824       schedule->fd_list[i].fd = 0;
 825       schedule->fd_list[i].events = 0;
 826       if (schedule->last_fd == i)
 827         schedule->last_fd = schedule->max_fd - 1;
 828       break;
 829     }
 830
 831   silc_mutex_unlock(schedule->lock);
 832 }
 833
 834 /* Allocates a newtask task queue into the scheduler */
 835
 836 static void silc_task_queue_alloc(SilcTaskQueue *queue)
 837 {
 838   *queue = silc_calloc(1, sizeof(**queue));
 839   silc_mutex_alloc(&(*queue)->lock);
 840 }
 841
 842 /* Free's a task queue. */
 843
 844 static void silc_task_queue_free(SilcTaskQueue queue)
 845 {
 846   silc_mutex_free(queue->lock);
 847   silc_free(queue);
 848 }
 849
 850 /* Return task by its fd. */
 851
 852 static SilcTask silc_task_find(SilcTaskQueue queue, uint32 fd)
 853 {
 854   SilcTask next;
 855
 856   if (!queue->task)
 857     return NULL;
 858
 859   next = queue->task;
 860
 861   while (1) {
 862     if (next->fd == fd)
 863       return next;
 864     if (queue->task == next->next)
 865       return NULL;
 866     next = next->next;
 867   }
 868
 869   return NULL;
 870 }
 871
 872 /* Adds a non-timeout task into the task queue. This function is used
 873    by silc_task_register function. Returns a pointer to the registered
 874    task. */
 875
 876 static SilcTask silc_task_add(SilcTaskQueue queue, SilcTask newtask,
 877                               SilcTaskPriority priority)
 878 {
 879   SilcTask task, next, prev;
 880
 881   /* Take the first task in the queue */
 882   task = queue->task;
 883
 884   switch(priority) {
 885   case SILC_TASK_PRI_LOW:
 886     /* Lowest priority. The task is added at the end of the list. */
 887     prev = task->prev;
 888     newtask->prev = prev;
 889     newtask->next = task;
 890     prev->next = newtask;
 891     task->prev = newtask;
 892     break;
 893   case SILC_TASK_PRI_NORMAL:
 894     /* Normal priority. The task is added before lower priority tasks
 895        but after tasks with higher priority. */
 896     prev = task->prev;
 897     while(prev != task) {
 898       if (prev->priority > SILC_TASK_PRI_LOW)
 899         break;
 900       prev = prev->prev;
 901     }
 902     if (prev == task) {
 903       /* There are only lower priorities in the list, we will
 904          sit before them and become the first task in the queue. */
 905       prev = task->prev;
 906       newtask->prev = prev;
 907       newtask->next = task;
 908       task->prev = newtask;
 909       prev->next = newtask;
 910
 911       /* We are now the first task in queue */
 912       queue->task = newtask;
 913     } else {
 914       /* Found a spot from the list, add the task to the list. */
 915       next = prev->next;
 916       newtask->prev = prev;
 917       newtask->next = next;
 918       prev->next = newtask;
 919       next->prev = newtask;
 920     }
 921     break;
 922   default:
 923     silc_free(newtask);
 924     return NULL;
 925   }
 926
 927   return newtask;
 928 }
 929
 930 /* Return the timeout task with smallest timeout. */
 931
 932 static SilcTask silc_task_get_first(SilcTaskQueue queue, SilcTask first)
 933 {
 934   SilcTask prev, task;
 935
 936   prev = first->prev;
 937
 938   if (first == prev)
 939     return first;
 940
 941   task = first;
 942   while (1) {
 943     if (first == prev)
 944       break;
 945
 946     if (silc_schedule_task_timeout_compare(&prev->timeout, &task->timeout))
 947       task = prev;
 948
 949     prev = prev->prev;
 950   }
 951
 952   return task;
 953 }
 954
 955 /* Adds a timeout task into the task queue. This function is used by
 956    silc_task_register function. Returns a pointer to the registered
 957    task. Timeout tasks are sorted by their timeout value in ascending
 958    order. The priority matters if there are more than one task with
 959    same timeout. */
 960
 961 static SilcTask silc_task_add_timeout(SilcTaskQueue queue, SilcTask newtask,
 962                                       SilcTaskPriority priority)
 963 {
 964   SilcTask task, prev, next;
 965
 966   /* Take the first task in the queue */
 967   task = queue->task;
 968
 969   /* Take last task from the list */
 970   prev = task->prev;
 971
 972   switch(priority) {
 973   case SILC_TASK_PRI_LOW:
 974     /* Lowest priority. The task is added at the end of the list. */
 975     while(prev != task) {
 976
 977       /* If we have longer timeout than with the task head of us
 978          we have found our spot. */
 979       if (silc_schedule_task_timeout_compare(&prev->timeout,
 980                                              &newtask->timeout))
 981         break;
 982
 983       /* If we are equal size of timeout we will be after it. */
 984       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
 985                                               &prev->timeout))
 986         break;
 987
 988       /* We have shorter timeout, compare to next one. */
 989       prev = prev->prev;
 990     }
 991     /* Found a spot from the list, add the task to the list. */
 992     next = prev->next;
 993     newtask->prev = prev;
 994     newtask->next = next;
 995     prev->next = newtask;
 996     next->prev = newtask;
 997
 998     if (prev == task) {
 999       /* Check if we are going to be the first task in the queue */
1000       if (silc_schedule_task_timeout_compare(&prev->timeout,
1001                                              &newtask->timeout))
1002         break;
1003       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1004                                               &prev->timeout))
1005         break;
1006
1007       /* We are now the first task in queue */
1008       queue->task = newtask;
1009     }
1010     break;
1011   case SILC_TASK_PRI_NORMAL:
1012     /* Normal priority. The task is added before lower priority tasks
1013        but after tasks with higher priority. */
1014     while(prev != task) {
1015
1016       /* If we have longer timeout than with the task head of us
1017          we have found our spot. */
1018       if (silc_schedule_task_timeout_compare(&prev->timeout,
1019                                              &newtask->timeout))
1020         break;
1021
1022       /* If we are equal size of timeout, priority kicks in place. */
1023       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1024                                               &prev->timeout))
1025         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1026           break;
1027
1028       /* We have shorter timeout or higher priority, compare to next one. */
1029       prev = prev->prev;
1030     }
1031     /* Found a spot from the list, add the task to the list. */
1032     next = prev->next;
1033     newtask->prev = prev;
1034     newtask->next = next;
1035     prev->next = newtask;
1036     next->prev = newtask;
1037
1038     if (prev == task) {
1039       /* Check if we are going to be the first task in the queue */
1040       if (silc_schedule_task_timeout_compare(&prev->timeout,
1041                                              &newtask->timeout))
1042         break;
1043       if (!silc_schedule_task_timeout_compare(&newtask->timeout,
1044                                               &prev->timeout))
1045         if (prev->priority >= SILC_TASK_PRI_NORMAL)
1046           break;
1047
1048       /* We are now the first task in queue */
1049       queue->task = newtask;
1050     }
1051     break;
1052   default:
1053     silc_free(newtask);
1054     return NULL;
1055   }
1056
1057   return newtask;
1058 }
1059
1060 /* Removes (unregisters) a task from particular task queue. This function
1061    is used internally by scheduler. This must be called holding the
1062    queue->lock. */
1063
1064 static int silc_schedule_task_remove(SilcTaskQueue queue, SilcTask task)
1065 {
1066   SilcTask first, old, next;
1067
1068   if (!queue || !task)
1069     return FALSE;
1070
1071   if (!queue->task) {
1072     return FALSE;
1073   }
1074
1075   first = queue->task;
1076
1077   /* Unregister all tasks in queue */
1078   if (task == SILC_ALL_TASKS) {
1079     SILC_LOG_DEBUG(("Removing all tasks at once"));
1080     next = first;
1081
1082     while(1) {
1083       next = next->next;
1084       silc_free(next->prev);
1085       if (next == first)
1086         break;
1087     }
1088
1089     queue->task = NULL;
1090     return TRUE;
1091   }
1092
1093   SILC_LOG_DEBUG(("Removing task"));
1094
1095   /* Unregister the task */
1096   old = first;
1097   while(1) {
1098     if (old == task) {
1099       SilcTask prev, next;
1100
1101       prev = old->prev;
1102       next = old->next;
1103       prev->next = next;
1104       next->prev = prev;
1105
1106       if (prev == old && next == old)
1107         queue->task = NULL;
1108       if (queue->task == old)
1109         queue->task = silc_task_get_first(queue, next);
1110
1111       silc_free(old);
1112       return TRUE;
1113     }
1114     old = old->prev;
1115
1116     if (old == first) {
1117       return FALSE;
1118     }
1119   }
1120 }
1121
1122 /* Compare two time values. If the first argument is smaller than the
1123    second this function returns TRUE. */
1124
1125 static int silc_schedule_task_timeout_compare(struct timeval *smaller,
1126                                               struct timeval *bigger)
1127 {
1128   if ((smaller->tv_sec < bigger->tv_sec) ||
1129       ((smaller->tv_sec == bigger->tv_sec) &&
1130        (smaller->tv_usec < bigger->tv_usec)))
1131     return TRUE;
1132
1133   return FALSE;
1134 }
1135
1136 static void silc_task_del_by_fd(SilcTaskQueue queue, uint32 fd)
1137 {
1138   SilcTask next;
1139
1140   silc_mutex_lock(queue->lock);
1141
1142   if (!queue->task) {
1143     silc_mutex_unlock(queue->lock);
1144     return;
1145   }
1146
1147   next = queue->task;
1148
1149   while(1) {
1150     if (next->fd == fd)
1151       next->valid = FALSE;
1152     if (queue->task == next->next)
1153       break;
1154     next = next->next;
1155   }
1156
1157   silc_mutex_unlock(queue->lock);
1158 }
1159
1160 static void silc_task_del_by_callback(SilcTaskQueue queue,
1161                                       SilcTaskCallback callback)
1162 {
1163   SilcTask next;
1164
1165   silc_mutex_lock(queue->lock);
1166
1167   if (!queue->task) {
1168     silc_mutex_unlock(queue->lock);
1169     return;
1170   }
1171
1172   next = queue->task;
1173
1174   while(1) {
1175     if (next->callback == callback)
1176       next->valid = FALSE;
1177     if (queue->task == next->next)
1178       break;
1179     next = next->next;
1180   }
1181
1182   silc_mutex_unlock(queue->lock);
1183 }
1184
1185 static void silc_task_del_by_context(SilcTaskQueue queue, void *context)
1186 {
1187   SilcTask next;
1188
1189   silc_mutex_lock(queue->lock);
1190
1191   if (!queue->task) {
1192     silc_mutex_unlock(queue->lock);
1193     return;
1194   }
1195
1196   next = queue->task;
1197
1198   while(1) {
1199     if (next->context == context)
1200       next->valid = FALSE;
1201     if (queue->task == next->next)
1202       break;
1203     next = next->next;
1204   }
1205
1206   silc_mutex_unlock(queue->lock);
1207 }