updates.
[silc.git] / 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 /* XXX on multi-threads the task queue locking is missing here. */
22
23 #include "silcincludes.h"
24
25 /* System specific implementation of the select. */
26 int silc_select(int n, fd_set *readfds, fd_set *writefds,
27                 fd_set *exceptfds, struct timeval *timeout);
28
29 /* Structure holding list of file descriptors, scheduler is supposed to
30    be listenning. The max_fd field is the maximum number of possible file
31    descriptors in the list. This value is set at the initialization
32    of the scheduler and it usually is the maximum number of connections 
33    allowed. */
34 typedef struct {
35   int *fd;
36   uint32 last_fd;
37   uint32 max_fd;
38 } SilcScheduleFdList;
39
40 /* 
41    SILC Scheduler structure.
42
43    This is the actual schedule object in SILC. Both SILC client and server 
44    uses this same scheduler. Actually, this scheduler could be used by any
45    program needing scheduling.
46
47    Following short description of the fields:
48
49    SilcTaskQueue fd_queue
50
51        Task queue hook for non-timeout tasks. Usually this means that these
52        tasks perform different kind of I/O on file descriptors. File 
53        descriptors are usually network sockets but they actually can be
54        any file descriptors. This hook is initialized in silc_schedule_init
55        function. Timeout tasks should not be added to this queue because
56        they will never expire.
57
58    SilcTaskQueue timeout_queue
59
60        Task queue hook for timeout tasks. This hook is reserved specificly
61        for tasks with timeout. Non-timeout tasks should not be added to this
62        queue because they will never get scheduled. This hook is also
63        initialized in silc_schedule_init function.
64
65    SilcTaskQueue generic_queue
66
67        Task queue hook for generic tasks. This hook is reserved specificly
68        for generic tasks, tasks that apply to all file descriptors, except
69        to those that have specificly registered a non-timeout task. This hook
70        is also initialized in silc_schedule_init function.
71
72    SilcScheduleFdList fd_list
73
74        List of file descriptors the scheduler is supposed to be listenning.
75        This is updated internally.
76
77    struct timeval *timeout;
78
79        Pointer to the schedules next timeout. Value of this timeout is
80        automatically updated in the silc_schedule function.
81
82    int valid
83
84        Marks validity of the scheduler. This is a boolean value. When this
85        is false the scheduler is terminated and the program will end. This
86        set to true when the scheduler is initialized with silc_schedule_init
87        function.
88
89    fd_set in
90    fd_set out
91
92        File descriptor sets for select(). These are automatically managed
93        by the scheduler and should not be touched otherwise.
94
95    int max_fd
96
97        Number of maximum file descriptors for select(). This, as well, is
98        managed automatically by the scheduler and should be considered to 
99        be read-only field otherwise.
100
101 */
102 struct SilcScheduleStruct {
103   SilcTaskQueue fd_queue;
104   SilcTaskQueue timeout_queue;
105   SilcTaskQueue generic_queue;
106   SilcScheduleFdList fd_list;
107   struct timeval *timeout;
108   bool valid;
109   fd_set in;
110   fd_set out;
111   int max_fd;
112   SILC_MUTEX_DEFINE(lock);
113 };
114
115 /* Initializes the scheduler. Sets the non-timeout task queue hook and
116    the timeout task queue hook. This must be called before the scheduler
117    is able to work. This will allocate the queue pointers if they are
118    not allocated. Returns the scheduler context that must be freed by
119    the silc_schedule_uninit function. */
120
121 SilcSchedule silc_schedule_init(SilcTaskQueue *fd_queue,
122                                 SilcTaskQueue *timeout_queue,
123                                 SilcTaskQueue *generic_queue,
124                                 int max_fd)
125 {
126   SilcSchedule schedule;
127   int i;
128
129   SILC_LOG_DEBUG(("Initializing scheduler"));
130
131   schedule = silc_calloc(1, sizeof(*schedule));
132
133   /* Register the task queues if they are not registered already. In SILC
134      we have by default three task queues. One task queue for non-timeout
135      tasks which perform different kind of I/O on file descriptors, timeout
136      task queue for timeout tasks, and, generic non-timeout task queue whose
137      tasks apply to all connections. */
138   if (!*fd_queue)
139     silc_task_queue_alloc(schedule, fd_queue, TRUE);
140   if (!*timeout_queue)
141     silc_task_queue_alloc(schedule, timeout_queue, TRUE);
142   if (!*generic_queue)
143     silc_task_queue_alloc(schedule, generic_queue, TRUE);
144
145   /* Initialize the scheduler */
146   schedule->fd_queue = *fd_queue;
147   schedule->timeout_queue = *timeout_queue;
148   schedule->generic_queue = *generic_queue;
149   schedule->fd_list.fd = silc_calloc(max_fd, sizeof(*schedule->fd_list.fd));
150   schedule->fd_list.last_fd = 0;
151   schedule->fd_list.max_fd = max_fd;
152   schedule->timeout = NULL;
153   schedule->valid = TRUE;
154   FD_ZERO(&schedule->in);
155   FD_ZERO(&schedule->out);
156   schedule->max_fd = -1;
157   for (i = 0; i < max_fd; i++)
158     schedule->fd_list.fd[i] = -1;
159   silc_mutex_alloc(&schedule->lock);
160
161   return schedule;
162 }
163
164 /* Uninitializes the schedule. This is called when the program is ready
165    to end. This removes all tasks and task queues. Returns FALSE if the
166    scheduler could not be uninitialized. This happens when the scheduler
167    is still valid and silc_schedule_stop has not been called. */
168
169 bool silc_schedule_uninit(SilcSchedule schedule)
170 {
171
172   SILC_LOG_DEBUG(("Uninitializing scheduler"));
173
174   if (schedule->valid == TRUE)
175     return FALSE;
176
177   /* Unregister all tasks */
178   if (schedule->fd_queue)
179     silc_task_remove(schedule->fd_queue, SILC_ALL_TASKS);
180   if (schedule->timeout_queue)
181     silc_task_remove(schedule->timeout_queue, SILC_ALL_TASKS);
182   if (schedule->generic_queue)
183     silc_task_remove(schedule->generic_queue, SILC_ALL_TASKS);
184
185   /* Unregister all task queues */
186   if (schedule->fd_queue)
187     silc_task_queue_free(schedule->fd_queue);
188   if (schedule->timeout_queue)
189     silc_task_queue_free(schedule->timeout_queue);
190   if (schedule->generic_queue)
191     silc_task_queue_free(schedule->generic_queue);
192
193   /* Clear the fd list */
194   if (schedule->fd_list.fd) {
195     memset(schedule->fd_list.fd, -1, schedule->fd_list.max_fd);
196     silc_free(schedule->fd_list.fd);
197   }
198
199   silc_mutex_free(schedule->lock);
200
201   return TRUE;
202 }
203
204 /* Stops the schedule even if it is not supposed to be stopped yet. 
205    After calling this, one should call silc_schedule_uninit (after the 
206    silc_schedule has returned). */
207
208 void silc_schedule_stop(SilcSchedule schedule)
209 {
210   SILC_LOG_DEBUG(("Stopping scheduler"));
211   schedule->valid = FALSE;
212 }
213
214 /* Sets a file descriptor to be listened by select() in scheduler. One can
215    call this directly if wanted. This can be called multiple times for
216    one file descriptor to set different iomasks. */
217
218 void silc_schedule_set_listen_fd(SilcSchedule schedule, int fd, uint32 iomask)
219 {
220   silc_mutex_lock(schedule->lock);
221
222   schedule->fd_list.fd[fd] = iomask;
223   
224   if (fd > schedule->fd_list.last_fd)
225     schedule->fd_list.last_fd = fd;
226
227   silc_mutex_unlock(schedule->lock);
228 }
229
230 /* Removes a file descriptor from listen list. */
231
232 void silc_schedule_unset_listen_fd(SilcSchedule schedule, int fd)
233 {
234   silc_mutex_lock(schedule->lock);
235
236   schedule->fd_list.fd[fd] = -1;
237   
238   if (fd == schedule->fd_list.last_fd) {
239     int i;
240
241     for (i = fd; i >= 0; i--)
242       if (schedule->fd_list.fd[i] != -1)
243         break;
244
245     schedule->fd_list.last_fd = i < 0 ? 0 : i;
246   }
247
248   silc_mutex_unlock(schedule->lock);
249 }
250
251 /* Executes tasks matching the file descriptor set by select(). The task
252    remains on the task queue after execution. Invalid tasks are removed 
253    here from the task queue. This macro is used by silc_schedule function. 
254    We don't have to care about the tasks priority here because the tasks
255    are sorted in their priority order already at the registration phase. */
256
257 #define SILC_SCHEDULE_RUN_TASKS                                            \
258 do {                                                                       \
259   queue = schedule->fd_queue;                                              \
260   if (queue && queue->valid == TRUE && queue->task) {                      \
261     task = queue->task;                                                    \
262                                                                            \
263     /* Walk thorugh all tasks in the particular task queue and             \
264        execute the callback functions of those tasks matching the          \
265        fd set by select(). */                                              \
266     while(1) {                                                             \
267       /* Validity of the task is checked always before and after           \
268          execution beacuse the task might have been unregistered           \
269          in the callback function, ie. it is not valid anymore. */         \
270                                                                            \
271       if (task->valid) {                                                   \
272         /* Task ready for reading */                                       \
273         if ((FD_ISSET(task->fd, &schedule->in)) &&                         \
274             (task->iomask & (1L << SILC_TASK_READ))) {                     \
275           task->callback(queue, SILC_TASK_READ, task->context, task->fd);  \
276           is_run = TRUE;                                                   \
277         }                                                                  \
278       }                                                                    \
279                                                                            \
280       if (task->valid) {                                                   \
281         /* Task ready for writing */                                       \
282         if ((FD_ISSET(task->fd, &schedule->out)) &&                        \
283             (task->iomask & (1L << SILC_TASK_WRITE))) {                    \
284           task->callback(queue, SILC_TASK_WRITE, task->context, task->fd); \
285           is_run = TRUE;                                                   \
286         }                                                                  \
287       }                                                                    \
288                                                                            \
289       if (!task->valid) {                                                  \
290         /* Invalid (unregistered) tasks are removed from the               \
291            task queue. */                                                  \
292         if (queue->task == task->next) {                                   \
293           silc_task_remove(queue, task);                                   \
294           break;                                                           \
295         }                                                                  \
296                                                                            \
297         task = task->next;                                                 \
298         silc_task_remove(queue, task->prev);                               \
299         continue;                                                          \
300       }                                                                    \
301                                                                            \
302       /* Break if there isn't more tasks in the queue */                   \
303       if (queue->task == task->next)                                       \
304         break;                                                             \
305                                                                            \
306       task = task->next;                                                   \
307     }                                                                      \
308   }                                                                        \
309 } while(0)
310
311 /* Selects tasks to be listened by select(). These are the non-timeout
312    tasks. This checks the scheduler's fd list. This macro is used by 
313    silc_schedule function. */
314
315 #define SILC_SCHEDULE_SELECT_TASKS                              \
316 do {                                                            \
317   for (i = 0; i <= schedule->fd_list.last_fd; i++) {            \
318     if (schedule->fd_list.fd[i] != -1) {                        \
319                                                                 \
320       /* Set the max fd value for select() to listen */         \
321       if (i > schedule->max_fd)                                 \
322         schedule->max_fd = i;                                   \
323                                                                 \
324       /* Add tasks for reading */                               \
325       if ((schedule->fd_list.fd[i] & (1L << SILC_TASK_READ)))   \
326         FD_SET(i, &schedule->in);                               \
327                                                                 \
328       /* Add tasks for writing */                               \
329       if ((schedule->fd_list.fd[i] & (1L << SILC_TASK_WRITE)))  \
330         FD_SET(i, &schedule->out);                              \
331     }                                                           \
332   }                                                             \
333 } while(0)
334
335 /* Executes all tasks whose timeout has expired. The task is removed from
336    the task queue after the callback function has returned. Also, invalid
337    tasks are removed here. The current time must be get before calling this
338    macro. This macro is used by silc_schedule function. We don't have to
339    care about priorities because tasks are already sorted in their priority
340    order at the registration phase. */
341
342 #define SILC_SCHEDULE_RUN_TIMEOUT_TASKS                                 \
343 do {                                                                    \
344   queue = schedule->timeout_queue;                                      \
345   if (queue && queue->valid == TRUE && queue->task) {                   \
346     task = queue->task;                                                 \
347                                                                         \
348     /* Walk thorugh all tasks in the particular task queue              \
349        and run all the expired tasks. */                                \
350     while(1) {                                                          \
351       /* Execute the task if the timeout has expired */                 \
352       if (silc_task_timeout_compare(&task->timeout, &curtime)) {        \
353                                                                         \
354         /* Task ready for reading */                                    \
355         if (task->valid) {                                              \
356           if ((task->iomask & (1L << SILC_TASK_READ)))                  \
357             task->callback(queue, SILC_TASK_READ,                       \
358                            task->context, task->fd);                    \
359         }                                                               \
360                                                                         \
361         /* Task ready for writing */                                    \
362         if (task->valid) {                                              \
363           if ((task->iomask & (1L << SILC_TASK_WRITE)))                 \
364             task->callback(queue, SILC_TASK_WRITE,                      \
365                            task->context, task->fd);                    \
366         }                                                               \
367                                                                         \
368         /* Break if there isn't more tasks in the queue */              \
369         if (queue->task == task->next) {                                \
370           /* Remove the task from queue */                              \
371           silc_task_remove(queue, task);                                \
372           break;                                                        \
373         }                                                               \
374                                                                         \
375         task = task->next;                                              \
376                                                                         \
377         /* Remove the task from queue */                                \
378         silc_task_remove(queue, task->prev);                            \
379       } else {                                                          \
380         /* The timeout hasn't expired, check for next one */            \
381                                                                         \
382         /* Break if there isn't more tasks in the queue */              \
383         if (queue->task == task->next)                                  \
384           break;                                                        \
385                                                                         \
386         task = task->next;                                              \
387       }                                                                 \
388     }                                                                   \
389   }                                                                     \
390 } while(0)
391
392 /* Calculates next timeout for select(). This is the timeout value
393    when at earliest some of the timeout tasks expire. If this is in the
394    past, they will be run now. This macro is used by the silc_schedule
395    function. */
396
397 #define SILC_SCHEDULE_SELECT_TIMEOUT                                        \
398 do {                                                                        \
399   if (schedule->timeout_queue && schedule->timeout_queue->valid == TRUE) {  \
400     queue = schedule->timeout_queue;                                        \
401     task = NULL;                                                            \
402                                                                             \
403     /* Get the current time */                                              \
404     silc_gettimeofday(&curtime);                                            \
405     schedule->timeout = NULL;                                               \
406                                                                             \
407     /* First task in the task queue has always the smallest timeout. */     \
408     task = queue->task;                                                     \
409     while(1) {                                                              \
410       if (task && task->valid == TRUE) {                                    \
411                                                                             \
412         /* If the timeout is in past, we will run the task and all other    \
413            timeout tasks from the past. */                                  \
414         if (silc_task_timeout_compare(&task->timeout, &curtime)) {          \
415           SILC_SCHEDULE_RUN_TIMEOUT_TASKS;                                  \
416                                                                             \
417           /* The task(s) has expired and doesn't exist on the task queue    \
418              anymore. We continue with new timeout. */                      \
419           queue = schedule->timeout_queue;                                  \
420           task = queue->task;                                               \
421           if (task == NULL || task->valid == FALSE)                         \
422             break;                                                          \
423           goto cont;                                                        \
424         } else {                                                            \
425  cont:                                                                      \
426           /* Calculate the next timeout for select() */                     \
427           queue->timeout.tv_sec = task->timeout.tv_sec - curtime.tv_sec;    \
428           queue->timeout.tv_usec = task->timeout.tv_usec - curtime.tv_usec; \
429           if (queue->timeout.tv_sec < 0)                                    \
430             queue->timeout.tv_sec = 0;                                      \
431                                                                             \
432           /* We wouldn't want to go under zero, check for it. */            \
433           if (queue->timeout.tv_usec < 0) {                                 \
434             queue->timeout.tv_sec -= 1;                                     \
435             if (queue->timeout.tv_sec < 0)                                  \
436               queue->timeout.tv_sec = 0;                                    \
437             queue->timeout.tv_usec += 1000000L;                             \
438           }                                                                 \
439         }                                                                   \
440         /* We've got the timeout value */                                   \
441         break;                                                              \
442       } else {                                                              \
443         /* Task is not valid, remove it and try next one. */                \
444         silc_task_remove(queue, task);                                      \
445         task = queue->task;                                                 \
446         if (queue->task == NULL)                                            \
447           break;                                                            \
448       }                                                                     \
449     }                                                                       \
450     /* Save the timeout */                                                  \
451     if (task)                                                               \
452       schedule->timeout = &queue->timeout;                                  \
453   }                                                                         \
454 } while(0)
455
456 /* Execute generic tasks. These are executed only and only if for the
457    specific fd there wasn't other non-timeout tasks. This checks the earlier
458    set fd list, thus the generic tasks apply to all specified fd's. All the
459    generic tasks are executed at once. */
460
461 #define SILC_SCHEDULE_RUN_GENERIC_TASKS                                      \
462 do {                                                                         \
463   if (is_run == FALSE) {                                                     \
464     SILC_LOG_DEBUG(("Running generic tasks"));                               \
465     silc_mutex_lock(schedule->lock);                                         \
466     for (i = 0; i <= schedule->fd_list.last_fd; i++)                         \
467       if (schedule->fd_list.fd[i] != -1) {                                   \
468                                                                              \
469         /* Check whether this fd is select()ed. */                           \
470         if ((FD_ISSET(i, &schedule->in)) || (FD_ISSET(i, &schedule->out))) { \
471                                                                              \
472           /* It was selected. Now find the tasks from task queue and execute \
473              all generic tasks. */                                           \
474           if (schedule->generic_queue && schedule->generic_queue->valid) {   \
475             queue = schedule->generic_queue;                                 \
476                                                                              \
477             if (!queue->task)                                                \
478               break;                                                         \
479                                                                              \
480             task = queue->task;                                              \
481                                                                              \
482             while(1) {                                                       \
483               /* Validity of the task is checked always before and after     \
484                  execution beacuse the task might have been unregistered     \
485                  in the callback function, ie. it is not valid anymore. */   \
486                                                                              \
487               if (task->valid && schedule->fd_list.fd[i] != -1) {            \
488                 /* Task ready for reading */                                 \
489                 if ((schedule->fd_list.fd[i] & (1L << SILC_TASK_READ))) {    \
490                   silc_mutex_unlock(schedule->lock);                         \
491                   task->callback(queue, SILC_TASK_READ,                      \
492                                  task->context, i);                          \
493                   silc_mutex_lock(schedule->lock);                           \
494                 }                                                            \
495               }                                                              \
496                                                                              \
497               if (task->valid && schedule->fd_list.fd[i] != -1) {            \
498                 /* Task ready for writing */                                 \
499                 if ((schedule->fd_list.fd[i] & (1L << SILC_TASK_WRITE))) {   \
500                   silc_mutex_unlock(schedule->lock);                         \
501                   task->callback(queue, SILC_TASK_WRITE,                     \
502                                  task->context, i);                          \
503                   silc_mutex_lock(schedule->lock);                           \
504                 }                                                            \
505               }                                                              \
506                                                                              \
507               if (!task->valid) {                                            \
508                 /* Invalid (unregistered) tasks are removed from the         \
509                    task queue. */                                            \
510                 if (queue->task == task->next) {                             \
511                   silc_task_remove(queue, task);                             \
512                   break;                                                     \
513                 }                                                            \
514                                                                              \
515                 task = task->next;                                           \
516                 silc_task_remove(queue, task->prev);                         \
517                 continue;                                                    \
518               }                                                              \
519                                                                              \
520               /* Break if there isn't more tasks in the queue */             \
521               if (queue->task == task->next)                                 \
522                 break;                                                       \
523                                                                              \
524               task = task->next;                                             \
525             }                                                                \
526           }                                                                  \
527         }                                                                    \
528       }                                                                      \
529     silc_mutex_unlock(schedule->lock);                                       \
530   }                                                                          \
531 } while(0)
532
533 bool silc_schedule_one(SilcSchedule schedule, int timeout_usecs)
534 {
535   struct timeval timeout;
536   int is_run, i;
537   SilcTask task;
538   SilcTaskQueue queue;
539   struct timeval curtime;
540
541   SILC_LOG_DEBUG(("In scheduler loop"));
542
543   /* If the task queues aren't initialized or we aren't valid anymore
544      we will return */
545   if ((!schedule->fd_queue && !schedule->timeout_queue 
546        && !schedule->generic_queue) || schedule->valid == FALSE) {
547     SILC_LOG_DEBUG(("Scheduler not valid anymore, exiting"));
548     return FALSE;
549   }
550
551   /* Clear everything */
552   FD_ZERO(&schedule->in);
553   FD_ZERO(&schedule->out);
554   schedule->max_fd = -1;
555   is_run = FALSE;
556
557   /* Calculate next timeout for select(). This is the timeout value
558      when at earliest some of the timeout tasks expire. */
559   SILC_SCHEDULE_SELECT_TIMEOUT;
560
561   silc_mutex_lock(schedule->lock);
562
563   /* Add the file descriptors to the fd sets. These are the non-timeout
564      tasks. The select() listens to these file descriptors. */
565   SILC_SCHEDULE_SELECT_TASKS;
566
567   silc_mutex_unlock(schedule->lock);
568
569   if (schedule->max_fd == -1 && !schedule->timeout)
570     return FALSE;
571
572   if (schedule->timeout) {
573     SILC_LOG_DEBUG(("timeout: sec=%d, usec=%d", schedule->timeout->tv_sec,
574                     schedule->timeout->tv_usec));
575   }
576
577   if (timeout_usecs >= 0) {
578     timeout.tv_sec = 0;
579     timeout.tv_usec = timeout_usecs;
580     schedule->timeout = &timeout;
581   }
582
583   /* This is the main select(). The program blocks here until some
584      of the selected file descriptors change status or the selected
585      timeout expires. */
586   SILC_LOG_DEBUG(("Select"));
587   switch (silc_select(schedule->max_fd + 1, &schedule->in,
588                       &schedule->out, 0, schedule->timeout)) {
589   case -1:
590     /* Error */
591     if (errno == EINTR)
592       break;
593     SILC_LOG_ERROR(("Error in select(): %s", strerror(errno)));
594     break;
595   case 0:
596     /* Timeout */
597     SILC_LOG_DEBUG(("Running timeout tasks"));
598     silc_gettimeofday(&curtime);
599     SILC_SCHEDULE_RUN_TIMEOUT_TASKS;
600     break;
601   default:
602     /* There is some data available now */
603     SILC_LOG_DEBUG(("Running non-timeout tasks"));
604     SILC_SCHEDULE_RUN_TASKS;
605
606     SILC_SCHEDULE_RUN_GENERIC_TASKS;
607     break;
608   }
609
610   return TRUE;
611 }
612
613 /* The SILC scheduler. This is actually the main routine in SILC programs.
614    When this returns the program is to be ended. Before this function can
615    be called, one must call silc_schedule_init function. */
616
617 void silc_schedule(SilcSchedule schedule)
618 {
619   SILC_LOG_DEBUG(("Running scheduler"));
620
621   if (schedule->valid == FALSE) {
622     SILC_LOG_ERROR(("Scheduler is not valid, stopping"));
623     return;
624   }
625
626   /* Start the scheduler loop */
627   while (silc_schedule_one(schedule, -1)) 
628     ;
629 }