src/util/scheduler.c

   1 /*
   2       This file is part of GNUnet
   3       (C) 2009 Christian Grothoff (and other contributing authors)
   4
   5       GNUnet is free software; you can redistribute it and/or modify
   6       it under the terms of the GNU General Public License as published
   7       by the Free Software Foundation; either version 2, or (at your
   8       option) any later version.
   9
  10       GNUnet is distributed in the hope that it will be useful, but
  11       WITHOUT ANY WARRANTY; without even the implied warranty of
  12       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13       General Public License for more details.
  14
  15       You should have received a copy of the GNU General Public License
  16       along with GNUnet; see the file COPYING.  If not, write to the
  17       Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18       Boston, MA 02111-1307, USA.
  19  */
  20
  21 /**
  22  * @file util/scheduler.c
  23  * @brief schedule computations using continuation passing style
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_common.h"
  28 #include "gnunet_os_lib.h"
  29 #include "gnunet_scheduler_lib.h"
  30 #include "gnunet_signal_lib.h"
  31 #include "gnunet_time_lib.h"
  32 #ifdef LINUX
  33 #include "execinfo.h"
  34 /**
  35  * Obtain trace information for all scheduler calls that schedule tasks.
  36  */
  37 #define EXECINFO GNUNET_NO
  38
  39 /**
  40  * Depth of the traces collected via EXECINFO.
  41  */
  42 #define MAX_TRACE_DEPTH 50
  43 #endif
  44
  45 #define DEBUG_TASKS GNUNET_NO
  46
  47 /**
  48  * Should we figure out which tasks are delayed for a while
  49  * before they are run? (Consider using in combination with EXECINFO).
  50  */
  51 #define PROFILE_DELAYS GNUNET_NO
  52
  53 /**
  54  * Task that were in the queue for longer than this are reported if
  55  * PROFILE_DELAYS is active.
  56  */
  57 #define DELAY_THRESHOLD GNUNET_TIME_UNIT_SECONDS
  58
  59 /**
  60  * Linked list of pending tasks.
  61  */
  62 struct Task
  63 {
  64   /**
  65    * This is a linked list.
  66    */
  67   struct Task *next;
  68
  69   /**
  70    * Function to run when ready.
  71    */
  72   GNUNET_SCHEDULER_Task callback;
  73
  74   /**
  75    * Closure for the callback.
  76    */
  77   void *callback_cls;
  78
  79   /**
  80    * Set of file descriptors this task is waiting
  81    * for for reading.  Once ready, this is updated
  82    * to reflect the set of file descriptors ready
  83    * for operation.
  84    */
  85   struct GNUNET_NETWORK_FDSet *read_set;
  86
  87   /**
  88    * Set of file descriptors this task is waiting for for writing.
  89    * Once ready, this is updated to reflect the set of file
  90    * descriptors ready for operation.
  91    */
  92   struct GNUNET_NETWORK_FDSet *write_set;
  93
  94   /**
  95    * Unique task identifier.
  96    */
  97   GNUNET_SCHEDULER_TaskIdentifier id;
  98
  99   /**
 100    * Identifier of a prerequisite task.
 101    */
 102   GNUNET_SCHEDULER_TaskIdentifier prereq_id;
 103
 104   /**
 105    * Absolute timeout value for the task, or
 106    * GNUNET_TIME_UNIT_FOREVER_ABS for "no timeout".
 107    */
 108   struct GNUNET_TIME_Absolute timeout;
 109
 110 #if PROFILE_DELAYS
 111   /**
 112    * When was the task scheduled?
 113    */
 114   struct GNUNET_TIME_Absolute start_time;
 115 #endif
 116
 117   /**
 118    * Why is the task ready?  Set after task is added to ready queue.
 119    * Initially set to zero.  All reasons that have already been
 120    * satisfied (i.e.  read or write ready) will be set over time.
 121    */
 122   enum GNUNET_SCHEDULER_Reason reason;
 123
 124   /**
 125    * Task priority.
 126    */
 127   enum GNUNET_SCHEDULER_Priority priority;
 128
 129 #if EXECINFO
 130   /**
 131    * Array of strings which make up a backtrace from the point when this
 132    * task was scheduled (essentially, who scheduled the task?)
 133    */
 134   char **backtrace_strings;
 135
 136   /**
 137    * Size of the backtrace_strings array
 138    */
 139   int num_backtrace_strings;
 140 #endif
 141
 142 };
 143
 144
 145 /**
 146  * Handle for the scheduling service.
 147  */
 148 struct GNUNET_SCHEDULER_Handle
 149 {
 150
 151   /**
 152    * List of tasks waiting for an event.
 153    */
 154   struct Task *pending;
 155
 156   /**
 157    * ID of the task that is running right now.
 158    */
 159   struct Task *active_task;
 160
 161   /**
 162    * List of tasks ready to run right now,
 163    * grouped by importance.
 164    */
 165   struct Task *ready[GNUNET_SCHEDULER_PRIORITY_COUNT];
 166
 167   /**
 168    * Identity of the last task queued.  Incremented for each task to
 169    * generate a unique task ID (it is virtually impossible to start
 170    * more than 2^64 tasks during the lifetime of a process).
 171    */
 172   GNUNET_SCHEDULER_TaskIdentifier last_id;
 173
 174   /**
 175    * Highest number so that all tasks with smaller identifiers
 176    * have already completed.  Also the lowest number of a task
 177    * still waiting to be executed.
 178    */
 179   GNUNET_SCHEDULER_TaskIdentifier lowest_pending_id;
 180
 181   /**
 182    * Number of tasks on the ready list.
 183    */
 184   unsigned int ready_count;
 185
 186   /**
 187    * How many tasks have we run so far?
 188    */
 189   unsigned long long tasks_run;
 190
 191   /**
 192    * Priority of the task running right now.  Only
 193    * valid while a task is running.
 194    */
 195   enum GNUNET_SCHEDULER_Priority current_priority;
 196
 197   /**
 198    * How 'nice' are we right now?
 199    */
 200   int nice_level;
 201
 202 };
 203
 204
 205 /**
 206  * Check that the given priority is legal (and return it).
 207  *
 208  * @param p priority value to check
 209  * @return p on success, 0 on error
 210  */
 211 static enum GNUNET_SCHEDULER_Priority
 212 check_priority (enum GNUNET_SCHEDULER_Priority p)
 213 {
 214   if ((p >= 0) && (p < GNUNET_SCHEDULER_PRIORITY_COUNT))
 215     return p;
 216   GNUNET_assert (0);
 217   return 0;                     /* make compiler happy */
 218 }
 219
 220
 221 /**
 222  * Is a task with this identifier still pending?  Also updates
 223  * "lowest_pending_id" as a side-effect (for faster checks in the
 224  * future), but only if the return value is "GNUNET_NO" (and
 225  * the "lowest_pending_id" check failed).
 226  *
 227  * @param sched the scheduler
 228  * @param id which task are we checking for
 229  * @return GNUNET_YES if so, GNUNET_NO if not
 230  */
 231 static int
 232 is_pending (struct GNUNET_SCHEDULER_Handle *sched,
 233             GNUNET_SCHEDULER_TaskIdentifier id)
 234 {
 235   struct Task *pos;
 236   enum GNUNET_SCHEDULER_Priority p;
 237   GNUNET_SCHEDULER_TaskIdentifier min;
 238
 239   if (id < sched->lowest_pending_id)
 240     return GNUNET_NO;
 241   min = -1;                     /* maximum value */
 242   pos = sched->pending;
 243   while (pos != NULL)
 244     {
 245       if (pos->id == id)
 246         return GNUNET_YES;
 247       if (pos->id < min)
 248         min = pos->id;
 249       pos = pos->next;
 250     }
 251   for (p = 0; p < GNUNET_SCHEDULER_PRIORITY_COUNT; p++)
 252     {
 253       pos = sched->ready[p];
 254       while (pos != NULL)
 255         {
 256           if (pos->id == id)
 257             return GNUNET_YES;
 258           if (pos->id < min)
 259             min = pos->id;
 260           pos = pos->next;
 261         }
 262     }
 263   sched->lowest_pending_id = min;
 264   return GNUNET_NO;
 265 }
 266
 267
 268 /**
 269  * Update all sets and timeout for select.
 270  *
 271  * @param sched the scheduler
 272  * @param rs read-set, set to all FDs we would like to read (updated)
 273  * @param ws write-set, set to all FDs we would like to write (updated)
 274  * @param timeout next timeout (updated)
 275  */
 276 static void
 277 update_sets (struct GNUNET_SCHEDULER_Handle *sched,
 278              struct GNUNET_NETWORK_FDSet *rs,
 279              struct GNUNET_NETWORK_FDSet *ws,
 280              struct GNUNET_TIME_Relative *timeout)
 281 {
 282   struct Task *pos;
 283
 284   pos = sched->pending;
 285   while (pos != NULL)
 286     {
 287       if ((pos->prereq_id != GNUNET_SCHEDULER_NO_TASK) &&
 288           (GNUNET_YES == is_pending (sched, pos->prereq_id)))
 289         {
 290           pos = pos->next;
 291           continue;
 292         }
 293
 294       if (pos->timeout.value != GNUNET_TIME_UNIT_FOREVER_ABS.value)
 295         {
 296           struct GNUNET_TIME_Relative to;
 297
 298           to = GNUNET_TIME_absolute_get_remaining (pos->timeout);
 299           if (timeout->value > to.value)
 300             *timeout = to;
 301         }
 302       if (pos->read_set != NULL)
 303         GNUNET_NETWORK_fdset_add (rs, pos->read_set);
 304       if (pos->write_set != NULL)
 305         GNUNET_NETWORK_fdset_add (ws, pos->write_set);
 306       if (pos->reason != 0)
 307         *timeout = GNUNET_TIME_UNIT_ZERO;
 308       pos = pos->next;
 309     }
 310 }
 311
 312
 313 /**
 314  * Check if the ready set overlaps with the set we want to have ready.
 315  * If so, update the want set (set all FDs that are ready).  If not,
 316  * return GNUNET_NO.
 317  *
 318  * @param ready set that is ready
 319  * @param want set that we want to be ready
 320  * @return GNUNET_YES if there was some overlap
 321  */
 322 static int
 323 set_overlaps (const struct GNUNET_NETWORK_FDSet *ready,
 324               struct GNUNET_NETWORK_FDSet *want)
 325 {
 326   if (NULL == want)
 327     return GNUNET_NO;
 328   if (GNUNET_NETWORK_fdset_overlap (ready, want))
 329     {
 330       /* copy all over (yes, there maybe unrelated bits,
 331          but this should not hurt well-written clients) */
 332       GNUNET_NETWORK_fdset_copy (want, ready);
 333       return GNUNET_YES;
 334     }
 335   return GNUNET_NO;
 336 }
 337
 338
 339 /**
 340  * Check if the given task is eligible to run now.
 341  * Also set the reason why it is eligible.
 342  *
 343  * @param sched the scheduler
 344  * @param task task to check if it is ready
 345  * @param now the current time
 346  * @param rs set of FDs ready for reading
 347  * @param ws set of FDs ready for writing
 348  * @return GNUNET_YES if we can run it, GNUNET_NO if not.
 349  */
 350 static int
 351 is_ready (struct GNUNET_SCHEDULER_Handle *sched,
 352           struct Task *task,
 353           struct GNUNET_TIME_Absolute now,
 354           const struct GNUNET_NETWORK_FDSet *rs,
 355           const struct GNUNET_NETWORK_FDSet *ws)
 356 {
 357   if (now.value >= task->timeout.value)
 358     task->reason |= GNUNET_SCHEDULER_REASON_TIMEOUT;
 359   if ((0 == (task->reason & GNUNET_SCHEDULER_REASON_READ_READY)) &&
 360       (rs != NULL) && (set_overlaps (rs, task->read_set)))
 361     task->reason |= GNUNET_SCHEDULER_REASON_READ_READY;
 362   if ((0 == (task->reason & GNUNET_SCHEDULER_REASON_WRITE_READY)) &&
 363       (ws != NULL) && (set_overlaps (ws, task->write_set)))
 364     task->reason |= GNUNET_SCHEDULER_REASON_WRITE_READY;
 365   if (task->reason == 0)
 366     return GNUNET_NO;           /* not ready */
 367   if (task->prereq_id != GNUNET_SCHEDULER_NO_TASK)
 368     {
 369       if (GNUNET_YES == is_pending (sched, task->prereq_id))
 370         return GNUNET_NO;       /* prereq waiting */
 371       task->reason |= GNUNET_SCHEDULER_REASON_PREREQ_DONE;
 372     }
 373   return GNUNET_YES;
 374 }
 375
 376
 377 /**
 378  * Put a task that is ready for execution into the ready queue.
 379  *
 380  * @param handle the scheduler
 381  * @param task task ready for execution
 382  */
 383 static void
 384 queue_ready_task (struct GNUNET_SCHEDULER_Handle *handle, struct Task *task)
 385 {
 386   enum GNUNET_SCHEDULER_Priority p = task->priority;
 387   if (0 != (task->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 388     p = GNUNET_SCHEDULER_PRIORITY_SHUTDOWN;
 389   task->next = handle->ready[check_priority (p)];
 390   handle->ready[check_priority (p)] = task;
 391   handle->ready_count++;
 392 }
 393
 394
 395 /**
 396  * Check which tasks are ready and move them
 397  * to the respective ready queue.
 398  *
 399  * @param handle the scheduler
 400  * @param rs FDs ready for reading
 401  * @param ws FDs ready for writing
 402  */
 403 static void
 404 check_ready (struct GNUNET_SCHEDULER_Handle *handle,
 405              const struct GNUNET_NETWORK_FDSet *rs,
 406              const struct GNUNET_NETWORK_FDSet *ws)
 407 {
 408   struct Task *pos;
 409   struct Task *prev;
 410   struct Task *next;
 411   struct GNUNET_TIME_Absolute now;
 412
 413   now = GNUNET_TIME_absolute_get ();
 414   prev = NULL;
 415   pos = handle->pending;
 416   while (pos != NULL)
 417     {
 418 #if DEBUG_TASKS
 419       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 420                   "Checking readiness of task: %llu / %p\n",
 421                   pos->id, pos->callback_cls);
 422 #endif
 423       next = pos->next;
 424       if (GNUNET_YES == is_ready (handle, pos, now, rs, ws))
 425         {
 426           if (prev == NULL)
 427             handle->pending = next;
 428           else
 429             prev->next = next;
 430           queue_ready_task (handle, pos);
 431           pos = next;
 432           continue;
 433         }
 434       prev = pos;
 435       pos = next;
 436     }
 437 }
 438
 439
 440 /**
 441  * Request the shutdown of a scheduler.  Marks all currently
 442  * pending tasks as ready because of shutdown.  This will
 443  * cause all tasks to run (as soon as possible, respecting
 444  * priorities and prerequisite tasks).  Note that tasks
 445  * scheduled AFTER this call may still be delayed arbitrarily.
 446  *
 447  * @param sched the scheduler
 448  */
 449 void
 450 GNUNET_SCHEDULER_shutdown (struct GNUNET_SCHEDULER_Handle *sched)
 451 {
 452   struct Task *pos;
 453   int i;
 454
 455   pos = sched->pending;
 456   while (pos != NULL)
 457     {
 458       pos->reason |= GNUNET_SCHEDULER_REASON_SHUTDOWN;
 459       /* we don't move the task into the ready queue yet; check_ready
 460          will do that later, possibly adding additional
 461          readiness-factors */
 462       pos = pos->next;
 463     }
 464   for (i=0;i<GNUNET_SCHEDULER_PRIORITY_COUNT;i++)
 465     {
 466       pos = sched->ready[i];
 467       while (pos != NULL)
 468         {
 469           pos->reason |= GNUNET_SCHEDULER_REASON_SHUTDOWN;
 470           /* we don't move the task into the ready queue yet; check_ready
 471              will do that later, possibly adding additional
 472              readiness-factors */
 473           pos = pos->next;
 474         }
 475     }
 476 }
 477
 478
 479 /**
 480  * Destroy a task (release associated resources)
 481  *
 482  * @param t task to destroy
 483  */
 484 static void
 485 destroy_task (struct Task *t)
 486 {
 487   if (NULL != t->read_set)
 488     GNUNET_NETWORK_fdset_destroy (t->read_set);
 489   if (NULL != t->write_set)
 490     GNUNET_NETWORK_fdset_destroy (t->write_set);
 491 #if EXECINFO
 492   GNUNET_free (t->backtrace_strings);
 493 #endif
 494   GNUNET_free (t);
 495 }
 496
 497
 498 /**
 499  * Run at least one task in the highest-priority queue that is not
 500  * empty.  Keep running tasks until we are either no longer running
 501  * "URGENT" tasks or until we have at least one "pending" task (which
 502  * may become ready, hence we should select on it).  Naturally, if
 503  * there are no more ready tasks, we also return.
 504  *
 505  * @param sched the scheduler
 506  */
 507 static void
 508 run_ready (struct GNUNET_SCHEDULER_Handle *sched)
 509 {
 510   enum GNUNET_SCHEDULER_Priority p;
 511   struct Task *pos;
 512   struct GNUNET_SCHEDULER_TaskContext tc;
 513
 514   do
 515     {
 516       if (sched->ready_count == 0)
 517         return;
 518       GNUNET_assert (sched->ready[GNUNET_SCHEDULER_PRIORITY_KEEP] == NULL);
 519       /* yes, p>0 is correct, 0 is "KEEP" which should
 520          always be an empty queue (see assertion)! */
 521       for (p = GNUNET_SCHEDULER_PRIORITY_COUNT - 1; p > 0; p--)
 522         {
 523           pos = sched->ready[p];
 524           if (pos != NULL)
 525             break;
 526         }
 527       GNUNET_assert (pos != NULL);      /* ready_count wrong? */
 528       sched->ready[p] = pos->next;
 529       sched->ready_count--;
 530       if (sched->current_priority != pos->priority)
 531         {
 532           sched->current_priority = pos->priority;
 533           (void) GNUNET_OS_set_process_priority (0, pos->priority);
 534         }
 535       sched->active_task = pos;
 536 #if PROFILE_DELAYS
 537       if (GNUNET_TIME_absolute_get_duration (pos->start_time).value >
 538           DELAY_THRESHOLD.value)
 539         {
 540           GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 541                       "Task %u took %llums to be scheduled\n",
 542                       pos->id,
 543                       (unsigned long long) GNUNET_TIME_absolute_get_duration (pos->start_time).value);
 544 #if EXECINFO
 545           int i;
 546           for (i=0;i<pos->num_backtrace_strings;i++)
 547             GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 548                         "Task %u trace %d: %s\n",
 549                         pos->id,
 550                         i,
 551                         pos->backtrace_strings[i]);
 552 #endif
 553         }
 554 #endif
 555       tc.sched = sched;
 556       tc.reason = pos->reason;
 557       tc.read_ready = pos->read_set;
 558       tc.write_ready = pos->write_set;
 559       pos->callback (pos->callback_cls, &tc);
 560 #if DEBUG_TASKS
 561       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 562                   "Running task: %llu / %p\n", pos->id, pos->callback_cls);
 563 #endif
 564       sched->active_task = NULL;
 565       destroy_task (pos);
 566       sched->tasks_run++;
 567     }
 568   while ((sched->pending == NULL) || (p == GNUNET_SCHEDULER_PRIORITY_URGENT));
 569 }
 570
 571 /**
 572  * Pipe used to communicate shutdown via signal.
 573  */
 574 static struct GNUNET_DISK_PipeHandle *sigpipe;
 575
 576
 577 /**
 578  * Signal handler called for signals that should cause us to shutdown.
 579  */
 580 static void
 581 sighandler_shutdown ()
 582 {
 583   static char c;
 584
 585   GNUNET_DISK_file_write (GNUNET_DISK_pipe_handle
 586                           (sigpipe, GNUNET_DISK_PIPE_END_WRITE), &c,
 587                           sizeof (c));
 588 }
 589
 590
 591 /**
 592  * Initialize and run scheduler.  This function will return when all
 593  * tasks have completed.  On systems with signals, receiving a SIGTERM
 594  * (and other similar signals) will cause "GNUNET_SCHEDULER_shutdown"
 595  * to be run after the active task is complete.  As a result, SIGTERM
 596  * causes all active tasks to be scheduled with reason
 597  * "GNUNET_SCHEDULER_REASON_SHUTDOWN".  (However, tasks added
 598  * afterwards will execute normally!). Note that any particular signal
 599  * will only shut down one scheduler; applications should always only
 600  * create a single scheduler.
 601  *
 602  * @param task task to run immediately
 603  * @param task_cls closure of task
 604  */
 605 void
 606 GNUNET_SCHEDULER_run (GNUNET_SCHEDULER_Task task, void *task_cls)
 607 {
 608   struct GNUNET_SCHEDULER_Handle sched;
 609   struct GNUNET_NETWORK_FDSet *rs;
 610   struct GNUNET_NETWORK_FDSet *ws;
 611   struct GNUNET_TIME_Relative timeout;
 612   int ret;
 613   struct GNUNET_SIGNAL_Context *shc_int;
 614   struct GNUNET_SIGNAL_Context *shc_term;
 615   struct GNUNET_SIGNAL_Context *shc_quit;
 616   struct GNUNET_SIGNAL_Context *shc_hup;
 617   unsigned long long last_tr;
 618   unsigned int busy_wait_warning;
 619   const struct GNUNET_DISK_FileHandle *pr;
 620   char c;
 621
 622   rs = GNUNET_NETWORK_fdset_create ();
 623   ws = GNUNET_NETWORK_fdset_create ();
 624   GNUNET_assert (sigpipe == NULL);
 625   sigpipe = GNUNET_DISK_pipe (GNUNET_NO);
 626   GNUNET_assert (sigpipe != NULL);
 627   pr = GNUNET_DISK_pipe_handle (sigpipe, GNUNET_DISK_PIPE_END_READ);
 628   GNUNET_assert (pr != NULL);
 629   shc_int = GNUNET_SIGNAL_handler_install (SIGINT, &sighandler_shutdown);
 630   shc_term = GNUNET_SIGNAL_handler_install (SIGTERM, &sighandler_shutdown);
 631 #ifndef MINGW
 632   shc_quit = GNUNET_SIGNAL_handler_install (SIGQUIT, &sighandler_shutdown);
 633   shc_hup = GNUNET_SIGNAL_handler_install (SIGHUP, &sighandler_shutdown);
 634 #endif
 635   memset (&sched, 0, sizeof (sched));
 636   sched.current_priority = GNUNET_SCHEDULER_PRIORITY_DEFAULT;
 637   GNUNET_SCHEDULER_add_continuation (&sched,
 638                                      task,
 639                                      task_cls,
 640                                      GNUNET_SCHEDULER_REASON_STARTUP);
 641   last_tr = 0;
 642   busy_wait_warning = 0;
 643   while ((sched.pending != NULL) || (sched.ready_count > 0))
 644     {
 645       GNUNET_NETWORK_fdset_zero (rs);
 646       GNUNET_NETWORK_fdset_zero (ws);
 647       timeout = GNUNET_TIME_UNIT_FOREVER_REL;
 648       update_sets (&sched, rs, ws, &timeout);
 649       GNUNET_NETWORK_fdset_handle_set (rs, pr);
 650       if (sched.ready_count > 0)
 651         {
 652           /* no blocking, more work already ready! */
 653           timeout = GNUNET_TIME_UNIT_ZERO;
 654         }
 655       ret = GNUNET_NETWORK_socket_select (rs, ws, NULL, timeout);
 656       if (ret == GNUNET_SYSERR)
 657         {
 658           if (errno == EINTR)
 659             continue;
 660           GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "select");
 661           abort ();
 662           break;
 663         }
 664       if (GNUNET_NETWORK_fdset_handle_isset (rs, pr))
 665         {
 666           /* consume the signal */
 667           GNUNET_DISK_file_read (pr, &c, sizeof (c));
 668           /* mark all active tasks as ready due to shutdown */
 669           GNUNET_SCHEDULER_shutdown (&sched);
 670         }
 671       if (last_tr == sched.tasks_run)
 672         {
 673           busy_wait_warning++;
 674         }
 675       else
 676         {
 677           last_tr = sched.tasks_run;
 678           busy_wait_warning = 0;
 679         }
 680       if ((ret == 0) && (timeout.value == 0) && (busy_wait_warning > 16))
 681         {
 682           GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 683                       _("Looks like we're busy waiting...\n"));
 684           sleep (1);            /* mitigate */
 685         }
 686       check_ready (&sched, rs, ws);
 687       run_ready (&sched);
 688     }
 689   GNUNET_SIGNAL_handler_uninstall (shc_int);
 690   GNUNET_SIGNAL_handler_uninstall (shc_term);
 691 #ifndef MINGW
 692   GNUNET_SIGNAL_handler_uninstall (shc_quit);
 693   GNUNET_SIGNAL_handler_uninstall (shc_hup);
 694 #endif
 695   GNUNET_DISK_pipe_close (sigpipe);
 696   sigpipe = NULL;
 697   GNUNET_NETWORK_fdset_destroy (rs);
 698   GNUNET_NETWORK_fdset_destroy (ws);
 699 }
 700
 701
 702 /**
 703  * Obtain the reason code for why the current task was
 704  * started.  Will return the same value as
 705  * the GNUNET_SCHEDULER_TaskContext's reason field.
 706  *
 707  * @param sched scheduler to query
 708  * @return reason(s) why the current task is run
 709  */
 710 enum GNUNET_SCHEDULER_Reason
 711 GNUNET_SCHEDULER_get_reason (struct GNUNET_SCHEDULER_Handle *sched)
 712 {
 713   return sched->active_task->reason;
 714 }
 715
 716
 717 /**
 718  * Get information about the current load of this scheduler.  Use this
 719  * function to determine if an elective task should be added or simply
 720  * dropped (if the decision should be made based on the number of
 721  * tasks ready to run).
 722  *
 723  * @param sched scheduler to query
 724  * @param p priority level to look at
 725  * @return number of tasks pending right now
 726  */
 727 unsigned int
 728 GNUNET_SCHEDULER_get_load (struct GNUNET_SCHEDULER_Handle *sched,
 729                            enum GNUNET_SCHEDULER_Priority p)
 730 {
 731   struct Task *pos;
 732   unsigned int ret;
 733
 734   if (p == GNUNET_SCHEDULER_PRIORITY_COUNT)
 735     return sched->ready_count;
 736   if (p == GNUNET_SCHEDULER_PRIORITY_KEEP)
 737     p = sched->current_priority;
 738   ret = 0;
 739   pos = sched->ready[p];
 740   while (pos != NULL)
 741     {
 742       pos = pos->next;
 743       ret++;
 744     }
 745   return ret;
 746 }
 747
 748
 749 /**
 750  * Cancel the task with the specified identifier.
 751  * The task must not yet have run.
 752  *
 753  * @param sched scheduler to use
 754  * @param task id of the task to cancel
 755  * @return original closure of the task
 756  */
 757 void *
 758 GNUNET_SCHEDULER_cancel (struct GNUNET_SCHEDULER_Handle *sched,
 759                          GNUNET_SCHEDULER_TaskIdentifier task)
 760 {
 761   struct Task *t;
 762   struct Task *prev;
 763   enum GNUNET_SCHEDULER_Priority p;
 764   void *ret;
 765
 766   prev = NULL;
 767   t = sched->pending;
 768   while (t != NULL)
 769     {
 770       if (t->id == task)
 771         break;
 772       prev = t;
 773       t = t->next;
 774     }
 775   p = 0;
 776   while (t == NULL)
 777     {
 778       p++;
 779       GNUNET_assert (p < GNUNET_SCHEDULER_PRIORITY_COUNT);
 780       prev = NULL;
 781       t = sched->ready[p];
 782       while (t != NULL)
 783         {
 784           if (t->id == task)
 785             {
 786               sched->ready_count--;
 787               break;
 788             }
 789           prev = t;
 790           t = t->next;
 791         }
 792     }
 793   if (prev == NULL)
 794     {
 795       if (p == 0)
 796         sched->pending = t->next;
 797       else
 798         sched->ready[p] = t->next;
 799     }
 800   else
 801     prev->next = t->next;
 802   ret = t->callback_cls;
 803 #if DEBUG_TASKS
 804   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 805               "Canceling task: %llu / %p\n", task, t->callback_cls);
 806 #endif
 807   destroy_task (t);
 808   return ret;
 809 }
 810
 811
 812 /**
 813  * Continue the current execution with the given function.  This is
 814  * similar to the other "add" functions except that there is no delay
 815  * and the reason code can be specified.
 816  *
 817  * @param sched scheduler to use
 818  * @param task main function of the task
 819  * @param task_cls closure for 'main'
 820  * @param reason reason for task invocation
 821  */
 822 void
 823 GNUNET_SCHEDULER_add_continuation (struct GNUNET_SCHEDULER_Handle *sched,
 824                                    GNUNET_SCHEDULER_Task task,
 825                                    void *task_cls,
 826                                    enum GNUNET_SCHEDULER_Reason reason)
 827 {
 828   struct Task *t;
 829 #if EXECINFO
 830   void *backtrace_array[50];
 831 #endif
 832   t = GNUNET_malloc (sizeof (struct Task));
 833 #if EXECINFO
 834   t->num_backtrace_strings = backtrace(backtrace_array, 50);
 835   t->backtrace_strings = backtrace_symbols(backtrace_array, t->num_backtrace_strings);
 836 #endif
 837   t->callback = task;
 838   t->callback_cls = task_cls;
 839   t->id = ++sched->last_id;
 840 #if PROFILE_DELAYS
 841   t->start_time = GNUNET_TIME_absolute_get ();
 842 #endif
 843   t->reason = reason;
 844   t->priority = sched->current_priority;
 845 #if DEBUG_TASKS
 846   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 847               "Adding continuation task: %llu / %p\n",
 848               t->id, t->callback_cls);
 849 #endif
 850   queue_ready_task (sched, t);
 851 }
 852
 853
 854
 855 /**
 856  * Schedule a new task to be run after the specified prerequisite task
 857  * has completed. It will be run with the priority of the calling
 858  * task.
 859  *
 860  * @param sched scheduler to use
 861  * @param prerequisite_task run this task after the task with the given
 862  *        task identifier completes (and any of our other
 863  *        conditions, such as delay, read or write-readiness
 864  *        are satisfied).  Use  GNUNET_SCHEDULER_NO_TASK to not have any dependency
 865  *        on completion of other tasks (this will cause the task to run as
 866  *        soon as possible).
 867  * @param task main function of the task
 868  * @param task_cls closure of task
 869  * @return unique task identifier for the job
 870  *         only valid until "task" is started!
 871  */
 872 GNUNET_SCHEDULER_TaskIdentifier
 873 GNUNET_SCHEDULER_add_after (struct GNUNET_SCHEDULER_Handle *sched,
 874                             GNUNET_SCHEDULER_TaskIdentifier prerequisite_task,
 875                             GNUNET_SCHEDULER_Task task, void *task_cls)
 876 {
 877   return GNUNET_SCHEDULER_add_select (sched,
 878                                       GNUNET_SCHEDULER_PRIORITY_KEEP,
 879                                       prerequisite_task,
 880                                       GNUNET_TIME_UNIT_ZERO,
 881                                       NULL, NULL, task, task_cls);
 882 }
 883
 884
 885 /**
 886  * Schedule a new task to be run with a specified priority.
 887  *
 888  * @param sched scheduler to use
 889  * @param prio how important is the new task?
 890  * @param task main function of the task
 891  * @param task_cls closure of task
 892  * @return unique task identifier for the job
 893  *         only valid until "task" is started!
 894  */
 895 GNUNET_SCHEDULER_TaskIdentifier
 896 GNUNET_SCHEDULER_add_with_priority (struct GNUNET_SCHEDULER_Handle * sched,
 897                                     enum GNUNET_SCHEDULER_Priority prio,
 898                                     GNUNET_SCHEDULER_Task task,
 899                                     void *task_cls)
 900 {
 901   return GNUNET_SCHEDULER_add_select (sched,
 902                                       prio,
 903                                       GNUNET_SCHEDULER_NO_TASK,
 904                                       GNUNET_TIME_UNIT_ZERO,
 905                                       NULL, NULL, task, task_cls);
 906 }
 907
 908
 909
 910 /**
 911  * Schedule a new task to be run with a specified delay.  The task
 912  * will be scheduled for execution once the delay has expired. It
 913  * will be run with the priority of the calling task.
 914  *
 915  * @param sched scheduler to use
 916  * @param delay when should this operation time out? Use
 917  *        GNUNET_TIME_UNIT_FOREVER_REL for "on shutdown"
 918  * @param task main function of the task
 919  * @param task_cls closure of task
 920  * @return unique task identifier for the job
 921  *         only valid until "task" is started!
 922  */
 923 GNUNET_SCHEDULER_TaskIdentifier
 924 GNUNET_SCHEDULER_add_delayed (struct GNUNET_SCHEDULER_Handle * sched,
 925                               struct GNUNET_TIME_Relative delay,
 926                               GNUNET_SCHEDULER_Task task, void *task_cls)
 927 {
 928   return GNUNET_SCHEDULER_add_select (sched,
 929                                       GNUNET_SCHEDULER_PRIORITY_KEEP,
 930                                       GNUNET_SCHEDULER_NO_TASK, delay,
 931                                       NULL, NULL, task, task_cls);
 932 }
 933
 934
 935
 936 /**
 937  * Schedule a new task to be run as soon as possible. The task
 938  * will be run with the priority of the calling task.
 939  *
 940  * @param sched scheduler to use
 941  * @param task main function of the task
 942  * @param task_cls closure of task
 943  * @return unique task identifier for the job
 944  *         only valid until "task" is started!
 945  */
 946 GNUNET_SCHEDULER_TaskIdentifier
 947 GNUNET_SCHEDULER_add_now (struct GNUNET_SCHEDULER_Handle *sched,
 948                           GNUNET_SCHEDULER_Task task,
 949                           void *task_cls)
 950 {
 951   return GNUNET_SCHEDULER_add_select (sched,
 952                                       GNUNET_SCHEDULER_PRIORITY_KEEP,
 953                                       GNUNET_SCHEDULER_NO_TASK,
 954                                       GNUNET_TIME_UNIT_ZERO,
 955                                       NULL, NULL, task, task_cls);
 956 }
 957
 958
 959
 960 /**
 961  * Schedule a new task to be run with a specified delay or when the
 962  * specified file descriptor is ready for reading.  The delay can be
 963  * used as a timeout on the socket being ready.  The task will be
 964  * scheduled for execution once either the delay has expired or the
 965  * socket operation is ready.  It will be run with the priority of
 966  * the calling task.
 967  *
 968  * @param sched scheduler to use
 969  * @param delay when should this operation time out? Use
 970  *        GNUNET_TIME_UNIT_FOREVER_REL for "on shutdown"
 971  * @param rfd read file-descriptor
 972  * @param task main function of the task
 973  * @param task_cls closure of task
 974  * @return unique task identifier for the job
 975  *         only valid until "task" is started!
 976  */
 977 GNUNET_SCHEDULER_TaskIdentifier
 978 GNUNET_SCHEDULER_add_read_net (struct GNUNET_SCHEDULER_Handle * sched,
 979                                struct GNUNET_TIME_Relative delay,
 980                                struct GNUNET_NETWORK_Handle * rfd,
 981                                GNUNET_SCHEDULER_Task task, void *task_cls)
 982 {
 983   struct GNUNET_NETWORK_FDSet *rs;
 984   GNUNET_SCHEDULER_TaskIdentifier ret;
 985
 986   GNUNET_assert (rfd != NULL);
 987   rs = GNUNET_NETWORK_fdset_create ();
 988   GNUNET_NETWORK_fdset_set (rs, rfd);
 989   ret = GNUNET_SCHEDULER_add_select (sched,
 990                                      GNUNET_SCHEDULER_PRIORITY_KEEP,
 991                                      GNUNET_SCHEDULER_NO_TASK,
 992                                      delay, rs, NULL, task, task_cls);
 993   GNUNET_NETWORK_fdset_destroy (rs);
 994   return ret;
 995 }
 996
 997
 998 /**
 999  * Schedule a new task to be run with a specified delay or when the
1000  * specified file descriptor is ready for writing.  The delay can be
1001  * used as a timeout on the socket being ready.  The task will be
1002  * scheduled for execution once either the delay has expired or the
1003  * socket operation is ready.  It will be run with the priority of
1004  * the calling task.
1005  *
1006  * @param sched scheduler to use
1007  * @param delay when should this operation time out? Use
1008  *        GNUNET_TIME_UNIT_FOREVER_REL for "on shutdown"
1009  * @param wfd write file-descriptor
1010  * @param task main function of the task
1011  * @param task_cls closure of task
1012  * @return unique task identifier for the job
1013  *         only valid until "task" is started!
1014  */
1015 GNUNET_SCHEDULER_TaskIdentifier
1016 GNUNET_SCHEDULER_add_write_net (struct GNUNET_SCHEDULER_Handle * sched,
1017                                 struct GNUNET_TIME_Relative delay,
1018                                 struct GNUNET_NETWORK_Handle * wfd,
1019                                 GNUNET_SCHEDULER_Task task, void *task_cls)
1020 {
1021   struct GNUNET_NETWORK_FDSet *ws;
1022   GNUNET_SCHEDULER_TaskIdentifier ret;
1023
1024   GNUNET_assert (wfd != NULL);
1025   ws = GNUNET_NETWORK_fdset_create ();
1026   GNUNET_NETWORK_fdset_set (ws, wfd);
1027   ret = GNUNET_SCHEDULER_add_select (sched,
1028                                      GNUNET_SCHEDULER_PRIORITY_KEEP,
1029                                      GNUNET_SCHEDULER_NO_TASK, delay,
1030                                      NULL, ws, task, task_cls);
1031   GNUNET_NETWORK_fdset_destroy (ws);
1032   return ret;
1033 }
1034
1035
1036 /**
1037  * Schedule a new task to be run with a specified delay or when the
1038  * specified file descriptor is ready for reading.  The delay can be
1039  * used as a timeout on the socket being ready.  The task will be
1040  * scheduled for execution once either the delay has expired or the
1041  * socket operation is ready. It will be run with the priority of
1042  * the calling task.
1043  *
1044  * @param sched scheduler to use
1045  * @param delay when should this operation time out? Use
1046  *        GNUNET_TIME_UNIT_FOREVER_REL for "on shutdown"
1047  * @param rfd read file-descriptor
1048  * @param task main function of the task
1049  * @param task_cls closure of task
1050  * @return unique task identifier for the job
1051  *         only valid until "task" is started!
1052  */
1053 GNUNET_SCHEDULER_TaskIdentifier
1054 GNUNET_SCHEDULER_add_read_file (struct GNUNET_SCHEDULER_Handle * sched,
1055                                 struct GNUNET_TIME_Relative delay,
1056                                 const struct GNUNET_DISK_FileHandle * rfd,
1057                                 GNUNET_SCHEDULER_Task task, void *task_cls)
1058 {
1059   struct GNUNET_NETWORK_FDSet *rs;
1060   GNUNET_SCHEDULER_TaskIdentifier ret;
1061
1062   GNUNET_assert (rfd != NULL);
1063   rs = GNUNET_NETWORK_fdset_create ();
1064   GNUNET_NETWORK_fdset_handle_set (rs, rfd);
1065   ret = GNUNET_SCHEDULER_add_select (sched,
1066                                      GNUNET_SCHEDULER_PRIORITY_KEEP,
1067                                      GNUNET_SCHEDULER_NO_TASK, delay,
1068                                      rs, NULL, task, task_cls);
1069   GNUNET_NETWORK_fdset_destroy (rs);
1070   return ret;
1071 }
1072
1073
1074 /**
1075  * Schedule a new task to be run with a specified delay or when the
1076  * specified file descriptor is ready for writing.  The delay can be
1077  * used as a timeout on the socket being ready.  The task will be
1078  * scheduled for execution once either the delay has expired or the
1079  * socket operation is ready. It will be run with the priority of
1080  * the calling task.
1081  *
1082  * @param sched scheduler to use
1083  * @param delay when should this operation time out? Use
1084  *        GNUNET_TIME_UNIT_FOREVER_REL for "on shutdown"
1085  * @param wfd write file-descriptor
1086  * @param task main function of the task
1087  * @param task_cls closure of task
1088  * @return unique task identifier for the job
1089  *         only valid until "task" is started!
1090  */
1091 GNUNET_SCHEDULER_TaskIdentifier
1092 GNUNET_SCHEDULER_add_write_file (struct GNUNET_SCHEDULER_Handle * sched,
1093                                  struct GNUNET_TIME_Relative delay,
1094                                  const struct GNUNET_DISK_FileHandle * wfd,
1095                                  GNUNET_SCHEDULER_Task task, void *task_cls)
1096 {
1097   struct GNUNET_NETWORK_FDSet *ws;
1098   GNUNET_SCHEDULER_TaskIdentifier ret;
1099
1100   GNUNET_assert (wfd != NULL);
1101   ws = GNUNET_NETWORK_fdset_create ();
1102   GNUNET_NETWORK_fdset_handle_set (ws, wfd);
1103   ret = GNUNET_SCHEDULER_add_select (sched,
1104                                      GNUNET_SCHEDULER_PRIORITY_KEEP,
1105                                      GNUNET_SCHEDULER_NO_TASK,
1106                                      delay, NULL, ws, task, task_cls);
1107   GNUNET_NETWORK_fdset_destroy (ws);
1108   return ret;
1109 }
1110
1111
1112
1113 /**
1114  * Schedule a new task to be run with a specified delay or when any of
1115  * the specified file descriptor sets is ready.  The delay can be used
1116  * as a timeout on the socket(s) being ready.  The task will be
1117  * scheduled for execution once either the delay has expired or any of
1118  * the socket operations is ready.  This is the most general
1119  * function of the "add" family.  Note that the "prerequisite_task"
1120  * must be satisfied in addition to any of the other conditions.  In
1121  * other words, the task will be started when
1122  * <code>
1123  * (prerequisite-run)
1124  * && (delay-ready
1125  *     || any-rs-ready
1126  *     || any-ws-ready
1127  *     || (shutdown-active && run-on-shutdown) )
1128  * </code>
1129  *
1130  * @param sched scheduler to use
1131  * @param prio how important is this task?
1132  * @param prerequisite_task run this task after the task with the given
1133  *        task identifier completes (and any of our other
1134  *        conditions, such as delay, read or write-readiness
1135  *        are satisfied).  Use GNUNET_SCHEDULER_NO_TASK to not have any dependency
1136  *        on completion of other tasks.
1137  * @param delay how long should we wait? Use GNUNET_TIME_UNIT_FOREVER_REL for "forever",
1138  *        which means that the task will only be run after we receive SIGTERM
1139  * @param rs set of file descriptors we want to read (can be NULL)
1140  * @param ws set of file descriptors we want to write (can be NULL)
1141  * @param task main function of the task
1142  * @param task_cls closure of task
1143  * @return unique task identifier for the job
1144  *         only valid until "task" is started!
1145  */
1146 GNUNET_SCHEDULER_TaskIdentifier
1147 GNUNET_SCHEDULER_add_select (struct GNUNET_SCHEDULER_Handle * sched,
1148                              enum GNUNET_SCHEDULER_Priority prio,
1149                              GNUNET_SCHEDULER_TaskIdentifier
1150                              prerequisite_task,
1151                              struct GNUNET_TIME_Relative delay,
1152                              const struct GNUNET_NETWORK_FDSet * rs,
1153                              const struct GNUNET_NETWORK_FDSet * ws,
1154                              GNUNET_SCHEDULER_Task task, void *task_cls)
1155 {
1156   struct Task *t;
1157 #if EXECINFO
1158   void *backtrace_array[MAX_TRACE_DEPTH];
1159 #endif
1160
1161   GNUNET_assert (NULL != task);
1162   t = GNUNET_malloc (sizeof (struct Task));
1163   t->callback = task;
1164   t->callback_cls = task_cls;
1165 #if EXECINFO
1166   t->num_backtrace_strings = backtrace(backtrace_array, MAX_TRACE_DEPTH);
1167   t->backtrace_strings = backtrace_symbols(backtrace_array, t->num_backtrace_strings);
1168 #endif
1169   if (rs != NULL)
1170     {
1171       t->read_set = GNUNET_NETWORK_fdset_create ();
1172       GNUNET_NETWORK_fdset_copy (t->read_set, rs);
1173     }
1174   if (ws != NULL)
1175     {
1176       t->write_set = GNUNET_NETWORK_fdset_create ();
1177       GNUNET_NETWORK_fdset_copy (t->write_set, ws);
1178     }
1179   t->id = ++sched->last_id;
1180 #if PROFILE_DELAYS
1181   t->start_time = GNUNET_TIME_absolute_get ();
1182 #endif
1183   t->prereq_id = prerequisite_task;
1184   t->timeout = GNUNET_TIME_relative_to_absolute (delay);
1185   t->priority =
1186     check_priority ((prio ==
1187                      GNUNET_SCHEDULER_PRIORITY_KEEP) ? sched->current_priority
1188                     : prio);
1189   t->next = sched->pending;
1190   sched->pending = t;
1191 #if DEBUG_TASKS
1192   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1193               "Adding task: %llu / %p\n", t->id, t->callback_cls);
1194 #endif
1195   return t->id;
1196 }
1197
1198 /* end of scheduler.c */