lib/silcutil/silcschedule.c

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