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   schedule->valid = FALSE;
 261 }
 262
 263 /* Executes nontimeout tasks. It then checks whether any of ther fd tasks
 264    was signaled by the silc_select. If some task was not signaled then
 265    all generic tasks are executed for that task. The generic tasks are
 266    never executed for task that has explicit fd task set. */
 267 /* This holds the schedule->lock and the queue locks. */
 268
 269 static void silc_schedule_dispatch_nontimeout(SilcSchedule schedule)
 270 {
 271   SilcTask task;
 272   int i, last_fd = schedule->last_fd;
 273   uint32 fd;
 274
 275   for (i = 0; i <= last_fd; i++) {
 276     if (schedule->fd_list[i].events == 0)
 277       continue;
 278
 279     fd = schedule->fd_list[i].fd;
 280
 281     /* First check whether this fd has task in the fd queue */
 282     silc_mutex_lock(schedule->fd_queue->lock);
 283     task = silc_task_find(schedule->fd_queue, fd);
 284
 285     /* If the task was found then execute its callbacks. If not then
 286        execute all generic tasks for that fd. */
 287     if (task) {
 288       /* Validity of the task is checked always before and after
 289          execution beacuse the task might have been unregistered
 290          in the callback function, ie. it is not valid anymore. */
 291
 292       /* Is the task ready for reading */
 293       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 294         silc_mutex_unlock(schedule->fd_queue->lock);
 295         silc_mutex_unlock(schedule->lock);
 296         task->callback(schedule, SILC_TASK_READ, task->fd, task->context);
 297         silc_mutex_lock(schedule->lock);
 298         silc_mutex_lock(schedule->fd_queue->lock);
 299       }
 300
 301       /* Is the task ready for writing */
 302       if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 303         silc_mutex_unlock(schedule->fd_queue->lock);
 304         silc_mutex_unlock(schedule->lock);
 305         task->callback(schedule, SILC_TASK_WRITE, task->fd, task->context);
 306         silc_mutex_lock(schedule->lock);
 307         silc_mutex_lock(schedule->fd_queue->lock);
 308       }
 309
 310       if (!task->valid)
 311         silc_schedule_task_remove(schedule->fd_queue, task);
 312
 313       silc_mutex_unlock(schedule->fd_queue->lock);
 314     } else {
 315       /* Run generic tasks for this fd. */
 316
 317       silc_mutex_unlock(schedule->fd_queue->lock);
 318
 319       silc_mutex_lock(schedule->generic_queue->lock);
 320       if (!schedule->generic_queue->task) {
 321         silc_mutex_unlock(schedule->generic_queue->lock);
 322         continue;
 323       }
 324
 325       task = schedule->generic_queue->task;
 326       while(1) {
 327         /* Validity of the task is checked always before and after
 328            execution beacuse the task might have been unregistered
 329            in the callback function, ie. it is not valid anymore. */
 330
 331         /* Is the task ready for reading */
 332         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_READ) {
 333           silc_mutex_unlock(schedule->generic_queue->lock);
 334           silc_mutex_unlock(schedule->lock);
 335           task->callback(schedule, SILC_TASK_READ, fd, task->context);
 336           silc_mutex_lock(schedule->lock);
 337           silc_mutex_lock(schedule->generic_queue->lock);
 338         }
 339
 340         /* Is the task ready for writing */
 341         if (task->valid && schedule->fd_list[i].revents & SILC_TASK_WRITE) {
 342           silc_mutex_unlock(schedule->generic_queue->lock);
 343           silc_mutex_unlock(schedule->lock);
 344           task->callback(schedule, SILC_TASK_WRITE, fd, task->context);
 345           silc_mutex_lock(schedule->lock);
 346           silc_mutex_lock(schedule->generic_queue->lock);
 347         }
 348
 349         if (!task->valid) {
 350           /* Invalid (unregistered) tasks are removed from the
 351              task queue. */
 352           if (schedule->generic_queue->task == task->next) {
 353             silc_schedule_task_remove(schedule->generic_queue, task);
 354             silc_mutex_unlock(schedule->generic_queue->lock);
 355             break;
 356           }
 357
 358           task = task->next;
 359           silc_schedule_task_remove(schedule->generic_queue, task);
 360           continue;
 361         }
 362
 363         /* Break if there isn't more tasks in the queue */
 364         if (schedule->generic_queue->task == task->next)
 365           break;
 366
 367         task = task->next;
 368       }
 369
 370       silc_mutex_unlock(schedule->generic_queue->lock);
 371     }
 372   }
 373 }
 374
 375 /* Executes all tasks whose timeout has expired. The task is removed from
 376    the task queue after the callback function has returned. Also, invalid
 377    tasks are removed here. We don't have to care about priorities because
 378    tasks are already sorted in their priority order at the registration
 379    phase. */
 380 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 381
 382 static void silc_schedule_dispatch_timeout(SilcSchedule schedule)
 383 {
 384   SilcTaskQueue queue = schedule->timeout_queue;
 385   SilcTask task;
 386   struct timeval curtime;
 387
 388   SILC_LOG_DEBUG(("Running timeout tasks"));
 389
 390   silc_gettimeofday(&curtime);
 391
 392   queue = schedule->timeout_queue;
 393   if (queue && queue->task) {
 394     task = queue->task;
 395
 396     /* Walk thorugh all tasks in the particular task queue and run all
 397        the expired tasks. */
 398     while(1) {
 399       /* Execute the task if the timeout has expired */
 400       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 401         if (task->valid) {
 402           silc_mutex_unlock(queue->lock);
 403           silc_mutex_unlock(schedule->lock);
 404           task->callback(schedule, SILC_TASK_EXPIRE, task->fd, task->context);
 405           silc_mutex_lock(schedule->lock);
 406           silc_mutex_lock(queue->lock);
 407         }
 408
 409         /* Break if there isn't more tasks in the queue */
 410         if (queue->task == task->next) {
 411           silc_schedule_task_remove(queue, task);
 412           break;
 413         }
 414
 415         task = task->next;
 416
 417         /* Remove the task from queue */
 418         silc_schedule_task_remove(queue, task->prev);
 419       } else {
 420         /* The timeout hasn't expired, check for next one */
 421
 422         /* Break if there isn't more tasks in the queue */
 423         if (queue->task == task->next)
 424           break;
 425
 426         task = task->next;
 427       }
 428     }
 429   }
 430 }
 431
 432 /* Calculates next timeout for select(). This is the timeout value
 433    when at earliest some of the timeout tasks expire. If this is in the
 434    past, they will be run now. */
 435 /* This holds the schedule->lock and the schedule->timeout_queue->lock */
 436
 437 static void silc_schedule_select_timeout(SilcSchedule schedule)
 438 {
 439   SilcTaskQueue queue = schedule->timeout_queue;
 440   SilcTask task;
 441   struct timeval curtime;
 442
 443   /* Get the current time */
 444   silc_gettimeofday(&curtime);
 445   schedule->timeout = NULL;
 446
 447   /* First task in the task queue has always the smallest timeout. */
 448   task = queue->task;
 449   while(1) {
 450     if (task && task->valid == TRUE) {
 451       /* If the timeout is in past, we will run the task and all other
 452          timeout tasks from the past. */
 453       if (silc_schedule_task_timeout_compare(&task->timeout, &curtime)) {
 454         silc_schedule_dispatch_timeout(schedule);
 455
 456         /* The task(s) has expired and doesn't exist on the task queue
 457            anymore. We continue with new timeout. */
 458         queue = schedule->timeout_queue;
 459         task = queue->task;
 460         if (task == NULL || task->valid == FALSE)
 461           break;
 462       }
 463
 464       /* Calculate the next timeout for select() */
 465       queue->timeout.tv_sec = task->timeout.tv_sec - curtime.tv_sec;
 466       queue->timeout.tv_usec = task->timeout.tv_usec - curtime.tv_usec;
 467       if (queue->timeout.tv_sec < 0)
 468         queue->timeout.tv_sec = 0;
 469
 470       /* We wouldn't want to go under zero, check for it. */
 471       if (queue->timeout.tv_usec < 0) {
 472         queue->timeout.tv_sec -= 1;
 473         if (queue->timeout.tv_sec < 0)
 474           queue->timeout.tv_sec = 0;
 475         queue->timeout.tv_usec += 1000000L;
 476       }
 477
 478       /* We've got the timeout value */
 479       break;
 480     } else {
 481       /* Task is not valid, remove it and try next one. */
 482       silc_schedule_task_remove(queue, task);
 483       task = queue->task;
 484       if (queue->task == NULL)
 485         break;
 486     }
 487   }
 488
 489   /* Save the timeout */
 490   if (task) {
 491     schedule->timeout = &queue->timeout;
 492     SILC_LOG_DEBUG(("timeout: sec=%d, usec=%d", schedule->timeout->tv_sec,
 493                     schedule->timeout->tv_usec));
 494   }
 495 }
 496
 497 /* Runs the scheduler once and then returns. */
 498
 499 bool silc_schedule_one(SilcSchedule schedule, int timeout_usecs)
 500 {
 501   struct timeval timeout;
 502   int ret;
 503
 504   SILC_LOG_DEBUG(("In scheduler loop"));
 505
 506   if (!schedule->is_locked)
 507     silc_mutex_lock(schedule->lock);
 508
 509   /* If the task queues aren't initialized or we aren't valid anymore
 510      we will return */
 511   if ((!schedule->fd_queue && !schedule->timeout_queue
 512        && !schedule->generic_queue) || schedule->valid == FALSE) {
 513     SILC_LOG_DEBUG(("Scheduler not valid anymore, exiting"));
 514     if (!schedule->is_locked)
 515       silc_mutex_unlock(schedule->lock);
 516     return FALSE;
 517   }
 518
 519   /* Calculate next timeout for silc_select(). This is the timeout value
 520      when at earliest some of the timeout tasks expire. */
 521   silc_mutex_lock(schedule->timeout_queue->lock);
 522   silc_schedule_select_timeout(schedule);
 523   silc_mutex_unlock(schedule->timeout_queue->lock);
 524
 525   if (timeout_usecs >= 0) {
 526     timeout.tv_sec = 0;
 527     timeout.tv_usec = timeout_usecs;
 528     schedule->timeout = &timeout;
 529   }
 530
 531   silc_mutex_unlock(schedule->lock);
 532
 533   /* This is the main select(). The program blocks here until some
 534      of the selected file descriptors change status or the selected
 535      timeout expires. */
 536   SILC_LOG_DEBUG(("Select"));
 537   ret = silc_select(schedule->fd_list, schedule->last_fd + 1,
 538                     schedule->timeout);
 539
 540   silc_mutex_lock(schedule->lock);
 541
 542   switch (ret) {
 543   case -1:
 544     /* Error */
 545     if (errno == EINTR)
 546       break;
 547     SILC_LOG_ERROR(("Error in select(): %s", strerror(errno)));
 548     break;
 549   case 0:
 550     /* Timeout */
 551     silc_mutex_lock(schedule->timeout_queue->lock);
 552     silc_schedule_dispatch_timeout(schedule);
 553     silc_mutex_unlock(schedule->timeout_queue->lock);
 554     break;
 555   default:
 556     /* There is some data available now */
 557     SILC_LOG_DEBUG(("Running non-timeout tasks"));
 558     silc_schedule_dispatch_nontimeout(schedule);
 559     break;
 560   }
 561
 562   if (!schedule->is_locked)
 563     silc_mutex_unlock(schedule->lock);
 564
 565   return TRUE;
 566 }
 567
 568 /* The SILC scheduler. This is actually the main routine in SILC programs.
 569    When this returns the program is to be ended. Before this function can
 570    be called, one must call silc_schedule_init function. */
 571
 572 void silc_schedule(SilcSchedule schedule)
 573 {
 574   SILC_LOG_DEBUG(("Running scheduler"));
 575
 576   if (schedule->valid == FALSE) {
 577     SILC_LOG_ERROR(("Scheduler is not valid, stopping"));
 578     return;
 579   }
 580
 581   silc_mutex_lock(schedule->lock);
 582   schedule->is_locked = TRUE;
 583
 584   /* Start the scheduler loop */
 585   while (silc_schedule_one(schedule, -1))
 586     ;
 587
 588   silc_mutex_unlock(schedule->lock);
 589 }
 590
 591 /* Wakes up the scheduler. This is used only in multi-threaded
 592    environments where threads may add new tasks or remove old tasks
 593    from task queues. This is called to wake up the scheduler in the
 594    main thread so that it detects the changes in the task queues.
 595    If threads support is not compiled in this function has no effect.
 596    Implementation of this function is platform specific. */
 597
 598 void silc_schedule_wakeup(SilcSchedule schedule)
 599 {
 600 #ifdef SILC_THREADS
 601   SILC_LOG_DEBUG(("Wakeup scheduler"));
 602   silc_mutex_lock(schedule->lock);
 603   silc_schedule_wakeup_internal(schedule->wakeup);
 604   silc_mutex_unlock(schedule->lock);
 605 #endif
 606 }
 607
 608 /* Add new task to the scheduler */
 609
 610 SilcTask silc_schedule_task_add(SilcSchedule schedule, uint32 fd,
 611                                 SilcTaskCallback callback, void *context,
 612                                 long seconds, long useconds,
 613                                 SilcTaskType type,
 614                                 SilcTaskPriority priority)
 615 {
 616   SilcTask newtask;
 617   SilcTaskQueue queue;
 618   int timeout = FALSE;
 619
 620   SILC_LOG_DEBUG(("Registering new task, fd=%d type=%d priority=%d", fd,
 621                   type, priority));
 622
 623   queue = SILC_SCHEDULE_GET_QUEUE(type);
 624
 625   /* If the task is generic task, we check whether this task has already
 626      been registered. Generic tasks are registered only once and after that
 627      the same task applies to all file descriptors to be registered. */
 628   if (type == SILC_TASK_GENERIC) {
 629     silc_mutex_lock(queue->lock);
 630
 631     if (queue->task) {
 632       SilcTask task = queue->task;
 633       while(1) {
 634         if ((task->callback == callback) && (task->context == context)) {
 635           SILC_LOG_DEBUG(("Found matching generic task, using the match"));
 636
 637           silc_mutex_unlock(queue->lock);
 638
 639           /* Add the fd to be listened, the task found now applies to this
 640              fd as well. */
 641           silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 642           return task;
 643         }
 644
 645         if (queue->task == task->next)
 646           break;
 647
 648         task = task->next;
 649       }
 650     }
 651
 652     silc_mutex_unlock(queue->lock);
 653   }
 654
 655   newtask = silc_calloc(1, sizeof(*newtask));
 656   newtask->fd = fd;
 657   newtask->context = context;
 658   newtask->callback = callback;
 659   newtask->valid = TRUE;
 660   newtask->priority = priority;
 661   newtask->type = type;
 662   newtask->next = newtask;
 663   newtask->prev = newtask;
 664
 665   /* Create timeout if marked to be timeout task */
 666   if (((seconds + useconds) > 0) && (type == SILC_TASK_TIMEOUT)) {
 667     silc_gettimeofday(&newtask->timeout);
 668     newtask->timeout.tv_sec += seconds + (useconds / 1000000L);
 669     newtask->timeout.tv_usec += (useconds % 1000000L);
 670     if (newtask->timeout.tv_usec > 999999L) {
 671       newtask->timeout.tv_sec += 1;
 672       newtask->timeout.tv_usec -= 1000000L;
 673     }
 674     timeout = TRUE;
 675   }
 676
 677   /* If the task is non-timeout task we have to tell the scheduler that we
 678      would like to have these tasks scheduled at some odd distant future. */
 679   if (type != SILC_TASK_TIMEOUT)
 680     silc_schedule_set_listen_fd(schedule, fd, SILC_TASK_READ);
 681
 682   silc_mutex_lock(queue->lock);
 683
 684   /* Is this first task of the queue? */
 685   if (queue->task == NULL) {
 686     queue->task = newtask;
 687     silc_mutex_unlock(queue->lock);
 688     return newtask;
 689   }
 690
 691   if (timeout)
 692     newtask = silc_task_add_timeout(queue, newtask, priority);
 693   else
 694     newtask = silc_task_add(queue, newtask, priority);
 695
 696   silc_mutex_unlock(queue->lock);
 697
 698   return newtask;
 699 }
 700
 701 /* Removes a task from the scheduler */
 702
 703 void silc_schedule_task_del(SilcSchedule schedule, SilcTask task)
 704 {
 705   SilcTaskQueue queue = SILC_SCHEDULE_GET_QUEUE(task->type);
 706
 707   /* Unregister all tasks */
 708   if (task == SILC_ALL_TASKS) {
 709     SilcTask next;
 710     SILC_LOG_DEBUG(("Unregistering all tasks at once"));
 711
 712     silc_mutex_lock(queue->lock);
 713
 714     if (!queue->task) {
 715       silc_mutex_unlock(queue->lock);
 716       return;
 717     }
 718
 719     next = queue->task;
 720
 721     while(1) {
 722       if (next->valid)
 723         next->valid = FALSE;
 724       if (queue->task == next->next)
 725         break;
 726       next = next->next;
 727     }
 728
 729     silc_mutex_unlock(queue->lock);
 730     return;
 731   }
 732
 733   SILC_LOG_DEBUG(("Unregistering task"));
 734
 735   silc_mutex_lock(queue->lock);
 736
 737   /* Unregister the specific task */
 738   if (task->valid)
 739     task->valid = FALSE;
 740
 741   silc_mutex_unlock(queue->lock);
 742 }
 743
 744 /* Remove task by fd */
 745
 746 void silc_schedule_task_del_by_fd(SilcSchedule schedule, uint32 fd)
 747 {
 748   SILC_LOG_DEBUG(("Unregister task by fd %d", fd));
 749
 750   silc_task_del_by_fd(schedule->timeout_queue, fd);
 751   silc_task_del_by_fd(schedule->fd_queue, fd);
 752 }
 753
 754 /* Remove task by task callback. */
 755
 756 void silc_schedule_task_del_by_callback(SilcSchedule schedule,
 757                                         SilcTaskCallback callback)
 758 {
 759   SILC_LOG_DEBUG(("Unregister task by callback"));
 760
 761   silc_task_del_by_callback(schedule->timeout_queue, callback);
 762   silc_task_del_by_callback(schedule->fd_queue, callback);
 763   silc_task_del_by_callback(schedule->generic_queue, callback);
 764 }
 765
 766 /* Remove task by context. */
 767
 768 void silc_schedule_task_del_by_context(SilcSchedule schedule, void *context)
 769 {
 770   SILC_LOG_DEBUG(("Unregister task by context"));
 771
 772   silc_task_del_by_context(schedule->timeout_queue, context);
 773   silc_task_del_by_context(schedule->fd_queue, context);
 774   silc_task_del_by_context(schedule->generic_queue, context);
 775 }
 776
 777 /* Sets a file descriptor to be listened by select() in scheduler. One can
 778    call this directly if wanted. This can be called multiple times for
 779    one file descriptor to set different iomasks. */
 780
 781 void silc_schedule_set_listen_fd(SilcSchedule schedule,
 782                                  uint32 fd, SilcTaskEvent iomask)
 783 {
 784   int i;
 785   bool found = FALSE;
 786
 787   silc_mutex_lock(schedule->lock);
 788
 789   for (i = 0; i < schedule->max_fd; i++)
 790     if (schedule->fd_list[i].fd == fd) {
 791       schedule->fd_list[i].fd = fd;
 792       schedule->fd_list[i].events = iomask;
 793       if (i > schedule->last_fd)
 794         schedule->last_fd = i;
 795       found = TRUE;
 796       break;
 797     }
 798
 799   if (!found)
 800     for (i = 0; i < schedule->max_fd; i++)
 801       if (schedule->fd_list[i].events == 0) {
 802         schedule->fd_list[i].fd = fd;
 803         schedule->fd_list[i].events = iomask;
 804         if (i > schedule->last_fd)
 805           schedule->last_fd = i;
 806         break;
 807       }
 808
 809   silc_mutex_unlock(schedule->lock);
 810 }
 811
 812 /* Removes a file descriptor from listen list. */
 813
 814 void silc_schedule_unset_listen_fd(SilcSchedule schedule, uint32 fd)
 815 {
 816   int i;
 817
 818   silc_mutex_lock(schedule->lock);
 819
 820   SILC_LOG_DEBUG(("Unset listen fd %d", fd));
 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 }