lib/thread.c

   1 /* Thread management routine
   2  * Copyright (C) 1998, 2000 Kunihiro Ishiguro <kunihiro@zebra.org>
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  18  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  */
  21
  22 /* #define DEBUG */
  23
  24 #include <zebra.h>
  25
  26 #include "thread.h"
  27 #include "memory.h"
  28 #include "log.h"
  29 #include "hash.h"
  30 #include "command.h"
  31 #include "sigevent.h"
  32 \f
  33 /* Recent absolute time of day */
  34 struct timeval recent_time;
  35 static struct timeval last_recent_time;
  36 /* Relative time, since startup */
  37 static struct timeval relative_time;
  38 static struct timeval relative_time_base;
  39 /* init flag */
  40 static unsigned short timers_inited;
  41 \f
  42 static struct hash *cpu_record = NULL;
  43 \f
  44 /* Struct timeval's tv_usec one second value.  */
  45 #define TIMER_SECOND_MICRO 1000000L
  46
  47 /* Adjust so that tv_usec is in the range [0,TIMER_SECOND_MICRO).
  48    And change negative values to 0. */
  49 static struct timeval
  50 timeval_adjust (struct timeval a)
  51 {
  52   while (a.tv_usec >= TIMER_SECOND_MICRO)
  53     {
  54       a.tv_usec -= TIMER_SECOND_MICRO;
  55       a.tv_sec++;
  56     }
  57
  58   while (a.tv_usec < 0)
  59     {
  60       a.tv_usec += TIMER_SECOND_MICRO;
  61       a.tv_sec--;
  62     }
  63
  64   if (a.tv_sec < 0)
  65       /* Change negative timeouts to 0. */
  66       a.tv_sec = a.tv_usec = 0;
  67
  68   return a;
  69 }
  70
  71 static struct timeval
  72 timeval_subtract (struct timeval a, struct timeval b)
  73 {
  74   struct timeval ret;
  75
  76   ret.tv_usec = a.tv_usec - b.tv_usec;
  77   ret.tv_sec = a.tv_sec - b.tv_sec;
  78
  79   return timeval_adjust (ret);
  80 }
  81
  82 static long
  83 timeval_cmp (struct timeval a, struct timeval b)
  84 {
  85   return (a.tv_sec == b.tv_sec
  86           ? a.tv_usec - b.tv_usec : a.tv_sec - b.tv_sec);
  87 }
  88
  89 static unsigned long
  90 timeval_elapsed (struct timeval a, struct timeval b)
  91 {
  92   return (((a.tv_sec - b.tv_sec) * TIMER_SECOND_MICRO)
  93           + (a.tv_usec - b.tv_usec));
  94 }
  95 \f
  96 #ifndef HAVE_CLOCK_MONOTONIC
  97 static void
  98 quagga_gettimeofday_relative_adjust (void)
  99 {
 100   struct timeval diff;
 101   if (timeval_cmp (recent_time, last_recent_time) < 0)
 102     {
 103       relative_time.tv_sec++;
 104       relative_time.tv_usec = 0;
 105     }
 106   else
 107     {
 108       diff = timeval_subtract (recent_time, last_recent_time);
 109       relative_time.tv_sec += diff.tv_sec;
 110       relative_time.tv_usec += diff.tv_usec;
 111       relative_time = timeval_adjust (relative_time);
 112     }
 113   last_recent_time = recent_time;
 114 }
 115 #endif /* !HAVE_CLOCK_MONOTONIC */
 116
 117 /* gettimeofday wrapper, to keep recent_time updated */
 118 static int
 119 quagga_gettimeofday (struct timeval *tv)
 120 {
 121   int ret;
 122
 123   assert (tv);
 124
 125   if (!(ret = gettimeofday (&recent_time, NULL)))
 126     {
 127       /* init... */
 128       if (!timers_inited)
 129         {
 130           relative_time_base = last_recent_time = recent_time;
 131           timers_inited = 1;
 132         }
 133       /* avoid copy if user passed recent_time pointer.. */
 134       if (tv != &recent_time)
 135         *tv = recent_time;
 136       return 0;
 137     }
 138   return ret;
 139 }
 140
 141 static int
 142 quagga_get_relative (struct timeval *tv)
 143 {
 144   int ret;
 145
 146 #ifdef HAVE_CLOCK_MONOTONIC
 147   {
 148     struct timespec tp;
 149     if (!(ret = clock_gettime (CLOCK_MONOTONIC, &tp)))
 150       {
 151         relative_time.tv_sec = tp.tv_sec;
 152         relative_time.tv_usec = tp.tv_nsec / 1000;
 153       }
 154   }
 155 #else /* !HAVE_CLOCK_MONOTONIC */
 156   if (!(ret = quagga_gettimeofday (&recent_time)))
 157     quagga_gettimeofday_relative_adjust();
 158 #endif /* HAVE_CLOCK_MONOTONIC */
 159
 160   if (tv)
 161     *tv = relative_time;
 162
 163   return ret;
 164 }
 165
 166 /* Get absolute time stamp, but in terms of the internal timer
 167  * Could be wrong, but at least won't go back.
 168  */
 169 static void
 170 quagga_real_stabilised (struct timeval *tv)
 171 {
 172   *tv = relative_time_base;
 173   tv->tv_sec += relative_time.tv_sec;
 174   tv->tv_usec += relative_time.tv_usec;
 175   *tv = timeval_adjust (*tv);
 176 }
 177
 178 /* Exported Quagga timestamp function.
 179  * Modelled on POSIX clock_gettime.
 180  */
 181 int
 182 quagga_gettime (enum quagga_clkid clkid, struct timeval *tv)
 183 {
 184   switch (clkid)
 185     {
 186       case QUAGGA_CLK_REALTIME:
 187         return quagga_gettimeofday (tv);
 188       case QUAGGA_CLK_MONOTONIC:
 189         return quagga_get_relative (tv);
 190       case QUAGGA_CLK_REALTIME_STABILISED:
 191         quagga_real_stabilised (tv);
 192         return 0;
 193       default:
 194         errno = EINVAL;
 195         return -1;
 196     }
 197 }
 198
 199 /* time_t value in terms of stabilised absolute time.
 200  * replacement for POSIX time()
 201  */
 202 time_t
 203 quagga_time (time_t *t)
 204 {
 205   struct timeval tv;
 206   quagga_real_stabilised (&tv);
 207   if (t)
 208     *t = tv.tv_sec;
 209   return tv.tv_sec;
 210 }
 211
 212 /* Public export of recent_relative_time by value */
 213 struct timeval
 214 recent_relative_time (void)
 215 {
 216   return relative_time;
 217 }
 218 \f
 219 static unsigned int
 220 cpu_record_hash_key (struct cpu_thread_history *a)
 221 {
 222   return (uintptr_t) a->func;
 223 }
 224
 225 static int
 226 cpu_record_hash_cmp (const struct cpu_thread_history *a,
 227                      const struct cpu_thread_history *b)
 228 {
 229   return a->func == b->func;
 230 }
 231
 232 static void *
 233 cpu_record_hash_alloc (struct cpu_thread_history *a)
 234 {
 235   struct cpu_thread_history *new;
 236   new = XCALLOC (MTYPE_THREAD_STATS, sizeof (struct cpu_thread_history));
 237   new->func = a->func;
 238   new->funcname = XSTRDUP(MTYPE_THREAD_FUNCNAME, a->funcname);
 239   return new;
 240 }
 241
 242 static void
 243 cpu_record_hash_free (void *a)
 244 {
 245   struct cpu_thread_history *hist = a;
 246
 247   XFREE (MTYPE_THREAD_FUNCNAME, hist->funcname);
 248   XFREE (MTYPE_THREAD_STATS, hist);
 249 }
 250
 251 static inline void
 252 vty_out_cpu_thread_history(struct vty* vty,
 253                            struct cpu_thread_history *a)
 254 {
 255 #ifdef HAVE_RUSAGE
 256   vty_out(vty, "%7ld.%03ld %9d %8ld %9ld %8ld %9ld",
 257           a->cpu.total/1000, a->cpu.total%1000, a->total_calls,
 258           a->cpu.total/a->total_calls, a->cpu.max,
 259           a->real.total/a->total_calls, a->real.max);
 260 #else
 261   vty_out(vty, "%7ld.%03ld %9d %8ld %9ld",
 262           a->real.total/1000, a->real.total%1000, a->total_calls,
 263           a->real.total/a->total_calls, a->real.max);
 264 #endif
 265   vty_out(vty, " %c%c%c%c%c%c %s%s",
 266           a->types & (1 << THREAD_READ) ? 'R':' ',
 267           a->types & (1 << THREAD_WRITE) ? 'W':' ',
 268           a->types & (1 << THREAD_TIMER) ? 'T':' ',
 269           a->types & (1 << THREAD_EVENT) ? 'E':' ',
 270           a->types & (1 << THREAD_EXECUTE) ? 'X':' ',
 271           a->types & (1 << THREAD_BACKGROUND) ? 'B' : ' ',
 272           a->funcname, VTY_NEWLINE);
 273 }
 274
 275 static void
 276 cpu_record_hash_print(struct hash_backet *bucket,
 277                       void *args[])
 278 {
 279   struct cpu_thread_history *totals = args[0];
 280   struct vty *vty = args[1];
 281   thread_type *filter = args[2];
 282   struct cpu_thread_history *a = bucket->data;
 283
 284   a = bucket->data;
 285   if ( !(a->types & *filter) )
 286        return;
 287   vty_out_cpu_thread_history(vty,a);
 288   totals->total_calls += a->total_calls;
 289   totals->real.total += a->real.total;
 290   if (totals->real.max < a->real.max)
 291     totals->real.max = a->real.max;
 292 #ifdef HAVE_RUSAGE
 293   totals->cpu.total += a->cpu.total;
 294   if (totals->cpu.max < a->cpu.max)
 295     totals->cpu.max = a->cpu.max;
 296 #endif
 297 }
 298
 299 static void
 300 cpu_record_print(struct vty *vty, thread_type filter)
 301 {
 302   struct cpu_thread_history tmp;
 303   void *args[3] = {&tmp, vty, &filter};
 304
 305   memset(&tmp, 0, sizeof tmp);
 306   tmp.funcname = "TOTAL";
 307   tmp.types = filter;
 308
 309 #ifdef HAVE_RUSAGE
 310   vty_out(vty, "%21s %18s %18s%s",
 311           "", "CPU (user+system):", "Real (wall-clock):", VTY_NEWLINE);
 312 #endif
 313   vty_out(vty, "Runtime(ms)   Invoked Avg uSec Max uSecs");
 314 #ifdef HAVE_RUSAGE
 315   vty_out(vty, " Avg uSec Max uSecs");
 316 #endif
 317   vty_out(vty, "  Type  Thread%s", VTY_NEWLINE);
 318   hash_iterate(cpu_record,
 319                (void(*)(struct hash_backet*,void*))cpu_record_hash_print,
 320                args);
 321
 322   if (tmp.total_calls > 0)
 323     vty_out_cpu_thread_history(vty, &tmp);
 324 }
 325
 326 DEFUN(show_thread_cpu,
 327       show_thread_cpu_cmd,
 328       "show thread cpu [FILTER]",
 329       SHOW_STR
 330       "Thread information\n"
 331       "Thread CPU usage\n"
 332       "Display filter (rwtexb)\n")
 333 {
 334   int i = 0;
 335   thread_type filter = (thread_type) -1U;
 336
 337   if (argc > 0)
 338     {
 339       filter = 0;
 340       while (argv[0][i] != '\0')
 341         {
 342           switch ( argv[0][i] )
 343             {
 344             case 'r':
 345             case 'R':
 346               filter |= (1 << THREAD_READ);
 347               break;
 348             case 'w':
 349             case 'W':
 350               filter |= (1 << THREAD_WRITE);
 351               break;
 352             case 't':
 353             case 'T':
 354               filter |= (1 << THREAD_TIMER);
 355               break;
 356             case 'e':
 357             case 'E':
 358               filter |= (1 << THREAD_EVENT);
 359               break;
 360             case 'x':
 361             case 'X':
 362               filter |= (1 << THREAD_EXECUTE);
 363               break;
 364             case 'b':
 365             case 'B':
 366               filter |= (1 << THREAD_BACKGROUND);
 367               break;
 368             default:
 369               break;
 370             }
 371           ++i;
 372         }
 373       if (filter == 0)
 374         {
 375           vty_out(vty, "Invalid filter \"%s\" specified,"
 376                   " must contain at least one of 'RWTEXB'%s",
 377                   argv[0], VTY_NEWLINE);
 378           return CMD_WARNING;
 379         }
 380     }
 381
 382   cpu_record_print(vty, filter);
 383   return CMD_SUCCESS;
 384 }
 385 \f
 386 /* List allocation and head/tail print out. */
 387 static void
 388 thread_list_debug (struct thread_list *list)
 389 {
 390   printf ("count [%d] head [%p] tail [%p]\n",
 391           list->count, list->head, list->tail);
 392 }
 393
 394 /* Debug print for thread_master. */
 395 static void  __attribute__ ((unused))
 396 thread_master_debug (struct thread_master *m)
 397 {
 398   printf ("-----------\n");
 399   printf ("readlist  : ");
 400   thread_list_debug (&m->read);
 401   printf ("writelist : ");
 402   thread_list_debug (&m->write);
 403   printf ("timerlist : ");
 404   thread_list_debug (&m->timer);
 405   printf ("eventlist : ");
 406   thread_list_debug (&m->event);
 407   printf ("unuselist : ");
 408   thread_list_debug (&m->unuse);
 409   printf ("bgndlist : ");
 410   thread_list_debug (&m->background);
 411   printf ("total alloc: [%ld]\n", m->alloc);
 412   printf ("-----------\n");
 413 }
 414 \f
 415 /* Allocate new thread master.  */
 416 struct thread_master *
 417 thread_master_create ()
 418 {
 419   if (cpu_record == NULL)
 420     cpu_record
 421       = hash_create_size (1011, (unsigned int (*) (void *))cpu_record_hash_key,
 422                           (int (*) (const void *, const void *))cpu_record_hash_cmp);
 423
 424   return (struct thread_master *) XCALLOC (MTYPE_THREAD_MASTER,
 425                                            sizeof (struct thread_master));
 426 }
 427
 428 /* Add a new thread to the list.  */
 429 static void
 430 thread_list_add (struct thread_list *list, struct thread *thread)
 431 {
 432   thread->next = NULL;
 433   thread->prev = list->tail;
 434   if (list->tail)
 435     list->tail->next = thread;
 436   else
 437     list->head = thread;
 438   list->tail = thread;
 439   list->count++;
 440 }
 441
 442 /* Add a new thread just before the point.  */
 443 static void
 444 thread_list_add_before (struct thread_list *list,
 445                         struct thread *point,
 446                         struct thread *thread)
 447 {
 448   thread->next = point;
 449   thread->prev = point->prev;
 450   if (point->prev)
 451     point->prev->next = thread;
 452   else
 453     list->head = thread;
 454   point->prev = thread;
 455   list->count++;
 456 }
 457
 458 /* Delete a thread from the list. */
 459 static struct thread *
 460 thread_list_delete (struct thread_list *list, struct thread *thread)
 461 {
 462   if (thread->next)
 463     thread->next->prev = thread->prev;
 464   else
 465     list->tail = thread->prev;
 466   if (thread->prev)
 467     thread->prev->next = thread->next;
 468   else
 469     list->head = thread->next;
 470   thread->next = thread->prev = NULL;
 471   list->count--;
 472   return thread;
 473 }
 474
 475 /* Move thread to unuse list. */
 476 static void
 477 thread_add_unuse (struct thread_master *m, struct thread *thread)
 478 {
 479   assert (m != NULL && thread != NULL);
 480   assert (thread->next == NULL);
 481   assert (thread->prev == NULL);
 482   assert (thread->type == THREAD_UNUSED);
 483   thread_list_add (&m->unuse, thread);
 484   /* XXX: Should we deallocate funcname here? */
 485 }
 486
 487 /* Free all unused thread. */
 488 static void
 489 thread_list_free (struct thread_master *m, struct thread_list *list)
 490 {
 491   struct thread *t;
 492   struct thread *next;
 493
 494   for (t = list->head; t; t = next)
 495     {
 496       next = t->next;
 497       if (t->funcname)
 498         XFREE (MTYPE_THREAD_FUNCNAME, t->funcname);
 499       XFREE (MTYPE_THREAD, t);
 500       list->count--;
 501       m->alloc--;
 502     }
 503 }
 504
 505 /* Stop thread scheduler. */
 506 void
 507 thread_master_free (struct thread_master *m)
 508 {
 509   thread_list_free (m, &m->read);
 510   thread_list_free (m, &m->write);
 511   thread_list_free (m, &m->timer);
 512   thread_list_free (m, &m->event);
 513   thread_list_free (m, &m->ready);
 514   thread_list_free (m, &m->unuse);
 515   thread_list_free (m, &m->background);
 516
 517   XFREE (MTYPE_THREAD_MASTER, m);
 518
 519   if (cpu_record)
 520     {
 521       hash_clean (cpu_record, cpu_record_hash_free);
 522       hash_free (cpu_record);
 523       cpu_record = NULL;
 524     }
 525 }
 526
 527 /* Thread list is empty or not.  */
 528 static inline int
 529 thread_empty (struct thread_list *list)
 530 {
 531   return  list->head ? 0 : 1;
 532 }
 533
 534 /* Delete top of the list and return it. */
 535 static struct thread *
 536 thread_trim_head (struct thread_list *list)
 537 {
 538   if (!thread_empty (list))
 539     return thread_list_delete (list, list->head);
 540   return NULL;
 541 }
 542
 543 /* Return remain time in second. */
 544 unsigned long
 545 thread_timer_remain_second (struct thread *thread)
 546 {
 547   quagga_get_relative (NULL);
 548
 549   if (thread->u.sands.tv_sec - relative_time.tv_sec > 0)
 550     return thread->u.sands.tv_sec - relative_time.tv_sec;
 551   else
 552     return 0;
 553 }
 554
 555 /* Trim blankspace and "()"s */
 556 static char *
 557 strip_funcname (const char *funcname)
 558 {
 559   char buff[100];
 560   char tmp, *ret, *e, *b = buff;
 561
 562   strncpy(buff, funcname, sizeof(buff));
 563   buff[ sizeof(buff) -1] = '\0';
 564   e = buff +strlen(buff) -1;
 565
 566   /* Wont work for funcname ==  "Word (explanation)"  */
 567
 568   while (*b == ' ' || *b == '(')
 569     ++b;
 570   while (*e == ' ' || *e == ')')
 571     --e;
 572   e++;
 573
 574   tmp = *e;
 575   *e = '\0';
 576   ret  = XSTRDUP (MTYPE_THREAD_FUNCNAME, b);
 577   *e = tmp;
 578
 579   return ret;
 580 }
 581
 582 /* Get new thread.  */
 583 static struct thread *
 584 thread_get (struct thread_master *m, u_char type,
 585             int (*func) (struct thread *), void *arg, const char* funcname)
 586 {
 587   struct thread *thread;
 588
 589   if (!thread_empty (&m->unuse))
 590     {
 591       thread = thread_trim_head (&m->unuse);
 592       if (thread->funcname)
 593         XFREE(MTYPE_THREAD_FUNCNAME, thread->funcname);
 594     }
 595   else
 596     {
 597       thread = XCALLOC (MTYPE_THREAD, sizeof (struct thread));
 598       m->alloc++;
 599     }
 600   thread->type = type;
 601   thread->add_type = type;
 602   thread->master = m;
 603   thread->func = func;
 604   thread->arg = arg;
 605
 606   thread->funcname = strip_funcname(funcname);
 607
 608   return thread;
 609 }
 610
 611 /* Add new read thread. */
 612 struct thread *
 613 funcname_thread_add_read (struct thread_master *m,
 614                  int (*func) (struct thread *), void *arg, int fd, const char* funcname)
 615 {
 616   struct thread *thread;
 617
 618   assert (m != NULL);
 619
 620   if (FD_ISSET (fd, &m->readfd))
 621     {
 622       zlog (NULL, LOG_WARNING, "There is already read fd [%d]", fd);
 623       return NULL;
 624     }
 625
 626   thread = thread_get (m, THREAD_READ, func, arg, funcname);
 627   FD_SET (fd, &m->readfd);
 628   thread->u.fd = fd;
 629   thread_list_add (&m->read, thread);
 630
 631   return thread;
 632 }
 633
 634 /* Add new write thread. */
 635 struct thread *
 636 funcname_thread_add_write (struct thread_master *m,
 637                  int (*func) (struct thread *), void *arg, int fd, const char* funcname)
 638 {
 639   struct thread *thread;
 640
 641   assert (m != NULL);
 642
 643   if (FD_ISSET (fd, &m->writefd))
 644     {
 645       zlog (NULL, LOG_WARNING, "There is already write fd [%d]", fd);
 646       return NULL;
 647     }
 648
 649   thread = thread_get (m, THREAD_WRITE, func, arg, funcname);
 650   FD_SET (fd, &m->writefd);
 651   thread->u.fd = fd;
 652   thread_list_add (&m->write, thread);
 653
 654   return thread;
 655 }
 656
 657 static struct thread *
 658 funcname_thread_add_timer_timeval (struct thread_master *m,
 659                                    int (*func) (struct thread *),
 660                                   int type,
 661                                   void *arg,
 662                                   struct timeval *time_relative,
 663                                   const char* funcname)
 664 {
 665   struct thread *thread;
 666   struct thread_list *list;
 667   struct timeval alarm_time;
 668   struct thread *tt;
 669
 670   assert (m != NULL);
 671
 672   assert (type == THREAD_TIMER || type == THREAD_BACKGROUND);
 673   assert (time_relative);
 674
 675   list = ((type == THREAD_TIMER) ? &m->timer : &m->background);
 676   thread = thread_get (m, type, func, arg, funcname);
 677
 678   /* Do we need jitter here? */
 679   quagga_get_relative (NULL);
 680   alarm_time.tv_sec = relative_time.tv_sec + time_relative->tv_sec;
 681   alarm_time.tv_usec = relative_time.tv_usec + time_relative->tv_usec;
 682   thread->u.sands = timeval_adjust(alarm_time);
 683
 684   /* Sort by timeval. */
 685   for (tt = list->head; tt; tt = tt->next)
 686     if (timeval_cmp (thread->u.sands, tt->u.sands) <= 0)
 687       break;
 688
 689   if (tt)
 690     thread_list_add_before (list, tt, thread);
 691   else
 692     thread_list_add (list, thread);
 693
 694   return thread;
 695 }
 696
 697
 698 /* Add timer event thread. */
 699 struct thread *
 700 funcname_thread_add_timer (struct thread_master *m,
 701                            int (*func) (struct thread *),
 702                            void *arg, long timer, const char* funcname)
 703 {
 704   struct timeval trel;
 705
 706   assert (m != NULL);
 707
 708   trel.tv_sec = timer;
 709   trel.tv_usec = 0;
 710
 711   return funcname_thread_add_timer_timeval (m, func, THREAD_TIMER, arg,
 712                                             &trel, funcname);
 713 }
 714
 715 /* Add timer event thread with "millisecond" resolution */
 716 struct thread *
 717 funcname_thread_add_timer_msec (struct thread_master *m,
 718                                 int (*func) (struct thread *),
 719                                 void *arg, long timer, const char* funcname)
 720 {
 721   struct timeval trel;
 722
 723   assert (m != NULL);
 724
 725   trel.tv_sec = timer / 1000;
 726   trel.tv_usec = 1000*(timer % 1000);
 727
 728   return funcname_thread_add_timer_timeval (m, func, THREAD_TIMER,
 729                                             arg, &trel, funcname);
 730 }
 731
 732 /* Add a background thread, with an optional millisec delay */
 733 struct thread *
 734 funcname_thread_add_background (struct thread_master *m,
 735                                 int (*func) (struct thread *),
 736                                 void *arg, long delay,
 737                                 const char *funcname)
 738 {
 739   struct timeval trel;
 740
 741   assert (m != NULL);
 742
 743   if (delay)
 744     {
 745       trel.tv_sec = delay / 1000;
 746       trel.tv_usec = 1000*(delay % 1000);
 747     }
 748   else
 749     {
 750       trel.tv_sec = 0;
 751       trel.tv_usec = 0;
 752     }
 753
 754   return funcname_thread_add_timer_timeval (m, func, THREAD_BACKGROUND,
 755                                             arg, &trel, funcname);
 756 }
 757
 758 /* Add simple event thread. */
 759 struct thread *
 760 funcname_thread_add_event (struct thread_master *m,
 761                   int (*func) (struct thread *), void *arg, int val, const char* funcname)
 762 {
 763   struct thread *thread;
 764
 765   assert (m != NULL);
 766
 767   thread = thread_get (m, THREAD_EVENT, func, arg, funcname);
 768   thread->u.val = val;
 769   thread_list_add (&m->event, thread);
 770
 771   return thread;
 772 }
 773
 774 /* Cancel thread from scheduler. */
 775 void
 776 thread_cancel (struct thread *thread)
 777 {
 778   struct thread_list *list;
 779
 780   switch (thread->type)
 781     {
 782     case THREAD_READ:
 783       assert (FD_ISSET (thread->u.fd, &thread->master->readfd));
 784       FD_CLR (thread->u.fd, &thread->master->readfd);
 785       list = &thread->master->read;
 786       break;
 787     case THREAD_WRITE:
 788       assert (FD_ISSET (thread->u.fd, &thread->master->writefd));
 789       FD_CLR (thread->u.fd, &thread->master->writefd);
 790       list = &thread->master->write;
 791       break;
 792     case THREAD_TIMER:
 793       list = &thread->master->timer;
 794       break;
 795     case THREAD_EVENT:
 796       list = &thread->master->event;
 797       break;
 798     case THREAD_READY:
 799       list = &thread->master->ready;
 800       break;
 801     case THREAD_BACKGROUND:
 802       list = &thread->master->background;
 803       break;
 804     default:
 805       return;
 806       break;
 807     }
 808   thread_list_delete (list, thread);
 809   thread->type = THREAD_UNUSED;
 810   thread_add_unuse (thread->master, thread);
 811 }
 812
 813 /* Delete all events which has argument value arg. */
 814 unsigned int
 815 thread_cancel_event (struct thread_master *m, void *arg)
 816 {
 817   unsigned int ret = 0;
 818   struct thread *thread;
 819
 820   thread = m->event.head;
 821   while (thread)
 822     {
 823       struct thread *t;
 824
 825       t = thread;
 826       thread = t->next;
 827
 828       if (t->arg == arg)
 829         {
 830           ret++;
 831           thread_list_delete (&m->event, t);
 832           t->type = THREAD_UNUSED;
 833           thread_add_unuse (m, t);
 834         }
 835     }
 836   return ret;
 837 }
 838
 839 static struct timeval *
 840 thread_timer_wait (struct thread_list *tlist, struct timeval *timer_val)
 841 {
 842   if (!thread_empty (tlist))
 843     {
 844       *timer_val = timeval_subtract (tlist->head->u.sands, relative_time);
 845       return timer_val;
 846     }
 847   return NULL;
 848 }
 849
 850 static struct thread *
 851 thread_run (struct thread_master *m, struct thread *thread,
 852             struct thread *fetch)
 853 {
 854   *fetch = *thread;
 855   thread->type = THREAD_UNUSED;
 856   thread->funcname = NULL;  /* thread_call will free fetch's copied pointer */
 857   thread_add_unuse (m, thread);
 858   return fetch;
 859 }
 860
 861 static int
 862 thread_process_fd (struct thread_list *list, fd_set *fdset, fd_set *mfdset)
 863 {
 864   struct thread *thread;
 865   struct thread *next;
 866   int ready = 0;
 867
 868   assert (list);
 869
 870   for (thread = list->head; thread; thread = next)
 871     {
 872       next = thread->next;
 873
 874       if (FD_ISSET (THREAD_FD (thread), fdset))
 875         {
 876           assert (FD_ISSET (THREAD_FD (thread), mfdset));
 877           FD_CLR(THREAD_FD (thread), mfdset);
 878           thread_list_delete (list, thread);
 879           thread_list_add (&thread->master->ready, thread);
 880           thread->type = THREAD_READY;
 881           ready++;
 882         }
 883     }
 884   return ready;
 885 }
 886
 887 /* Add all timers that have popped to the ready list. */
 888 static unsigned int
 889 thread_timer_process (struct thread_list *list, struct timeval *timenow)
 890 {
 891   struct thread *thread;
 892   unsigned int ready = 0;
 893
 894   for (thread = list->head; thread; thread = thread->next)
 895     {
 896       if (timeval_cmp (*timenow, thread->u.sands) < 0)
 897         return ready;
 898       thread_list_delete (list, thread);
 899       thread->type = THREAD_READY;
 900       thread_list_add (&thread->master->ready, thread);
 901       ready++;
 902     }
 903   return ready;
 904 }
 905
 906 /* Fetch next ready thread. */
 907 struct thread *
 908 thread_fetch (struct thread_master *m, struct thread *fetch)
 909 {
 910   struct thread *thread;
 911   fd_set readfd;
 912   fd_set writefd;
 913   fd_set exceptfd;
 914   struct timeval timer_val;
 915   struct timeval timer_val_bg;
 916   struct timeval *timer_wait;
 917   struct timeval *timer_wait_bg;
 918
 919   while (1)
 920     {
 921       int num = 0;
 922
 923       /* Signals are highest priority */
 924       quagga_sigevent_process ();
 925
 926       /* Normal event are the next highest priority.  */
 927       if ((thread = thread_trim_head (&m->event)) != NULL)
 928         return thread_run (m, thread, fetch);
 929
 930       /* If there are any ready threads from previous scheduler runs,
 931        * process top of them.
 932        */
 933       if ((thread = thread_trim_head (&m->ready)) != NULL)
 934         return thread_run (m, thread, fetch);
 935
 936       /* Structure copy.  */
 937       readfd = m->readfd;
 938       writefd = m->writefd;
 939       exceptfd = m->exceptfd;
 940
 941       /* Calculate select wait timer if nothing else to do */
 942       quagga_get_relative (NULL);
 943       timer_wait = thread_timer_wait (&m->timer, &timer_val);
 944       timer_wait_bg = thread_timer_wait (&m->background, &timer_val_bg);
 945
 946       if (timer_wait_bg &&
 947           (!timer_wait || (timeval_cmp (*timer_wait, *timer_wait_bg) > 0)))
 948         timer_wait = timer_wait_bg;
 949
 950       num = select (FD_SETSIZE, &readfd, &writefd, &exceptfd, timer_wait);
 951
 952       /* Signals should get quick treatment */
 953       if (num < 0)
 954         {
 955           if (errno == EINTR)
 956             continue; /* signal received - process it */
 957           zlog_warn ("select() error: %s", safe_strerror (errno));
 958             return NULL;
 959         }
 960
 961       /* Check foreground timers.  Historically, they have had higher
 962          priority than I/O threads, so let's push them onto the ready
 963          list in front of the I/O threads. */
 964       quagga_get_relative (NULL);
 965       thread_timer_process (&m->timer, &relative_time);
 966
 967       /* Got IO, process it */
 968       if (num > 0)
 969         {
 970           /* Normal priority read thead. */
 971           thread_process_fd (&m->read, &readfd, &m->readfd);
 972           /* Write thead. */
 973           thread_process_fd (&m->write, &writefd, &m->writefd);
 974         }
 975
 976 #if 0
 977       /* If any threads were made ready above (I/O or foreground timer),
 978          perhaps we should avoid adding background timers to the ready
 979          list at this time.  If this is code is uncommented, then background
 980          timer threads will not run unless there is nothing else to do. */
 981       if ((thread = thread_trim_head (&m->ready)) != NULL)
 982         return thread_run (m, thread, fetch);
 983 #endif
 984
 985       /* Background timer/events, lowest priority */
 986       thread_timer_process (&m->background, &relative_time);
 987
 988       if ((thread = thread_trim_head (&m->ready)) != NULL)
 989         return thread_run (m, thread, fetch);
 990     }
 991 }
 992
 993 unsigned long
 994 thread_consumed_time (RUSAGE_T *now, RUSAGE_T *start, unsigned long *cputime)
 995 {
 996 #ifdef HAVE_RUSAGE
 997   /* This is 'user + sys' time.  */
 998   *cputime = timeval_elapsed (now->cpu.ru_utime, start->cpu.ru_utime) +
 999              timeval_elapsed (now->cpu.ru_stime, start->cpu.ru_stime);
1000 #else
1001   *cputime = 0;
1002 #endif /* HAVE_RUSAGE */
1003   return timeval_elapsed (now->real, start->real);
1004 }
1005
1006 /* We should aim to yield after THREAD_YIELD_TIME_SLOT milliseconds.
1007    Note: we are using real (wall clock) time for this calculation.
1008    It could be argued that CPU time may make more sense in certain
1009    contexts.  The things to consider are whether the thread may have
1010    blocked (in which case wall time increases, but CPU time does not),
1011    or whether the system is heavily loaded with other processes competing
1012    for CPU time.  On balance, wall clock time seems to make sense.
1013    Plus it has the added benefit that gettimeofday should be faster
1014    than calling getrusage. */
1015 int
1016 thread_should_yield (struct thread *thread)
1017 {
1018   quagga_get_relative (NULL);
1019   return (timeval_elapsed(relative_time, thread->ru.real) >
1020           THREAD_YIELD_TIME_SLOT);
1021 }
1022
1023 void
1024 thread_getrusage (RUSAGE_T *r)
1025 {
1026   quagga_get_relative (NULL);
1027 #ifdef HAVE_RUSAGE
1028   getrusage(RUSAGE_SELF, &(r->cpu));
1029 #endif
1030   r->real = relative_time;
1031
1032 #ifdef HAVE_CLOCK_MONOTONIC
1033   /* quagga_get_relative() only updates recent_time if gettimeofday
1034    * based, not when using CLOCK_MONOTONIC. As we export recent_time
1035    * and guarantee to update it before threads are run...
1036    */
1037   quagga_gettimeofday(&recent_time);
1038 #endif /* HAVE_CLOCK_MONOTONIC */
1039 }
1040
1041 /* We check thread consumed time. If the system has getrusage, we'll
1042    use that to get in-depth stats on the performance of the thread in addition
1043    to wall clock time stats from gettimeofday. */
1044 void
1045 thread_call (struct thread *thread)
1046 {
1047   unsigned long realtime, cputime;
1048   RUSAGE_T ru;
1049
1050  /* Cache a pointer to the relevant cpu history thread, if the thread
1051   * does not have it yet.
1052   *
1053   * Callers submitting 'dummy threads' hence must take care that
1054   * thread->cpu is NULL
1055   */
1056   if (!thread->hist)
1057     {
1058       struct cpu_thread_history tmp;
1059
1060       tmp.func = thread->func;
1061       tmp.funcname = thread->funcname;
1062
1063       thread->hist = hash_get (cpu_record, &tmp,
1064                     (void * (*) (void *))cpu_record_hash_alloc);
1065     }
1066
1067   GETRUSAGE (&thread->ru);
1068
1069   (*thread->func) (thread);
1070
1071   GETRUSAGE (&ru);
1072
1073   realtime = thread_consumed_time (&ru, &thread->ru, &cputime);
1074   thread->hist->real.total += realtime;
1075   if (thread->hist->real.max < realtime)
1076     thread->hist->real.max = realtime;
1077 #ifdef HAVE_RUSAGE
1078   thread->hist->cpu.total += cputime;
1079   if (thread->hist->cpu.max < cputime)
1080     thread->hist->cpu.max = cputime;
1081 #endif
1082
1083   ++(thread->hist->total_calls);
1084   thread->hist->types |= (1 << thread->add_type);
1085
1086 #ifdef CONSUMED_TIME_CHECK
1087   if (realtime > CONSUMED_TIME_CHECK)
1088     {
1089       /*
1090        * We have a CPU Hog on our hands.
1091        * Whinge about it now, so we're aware this is yet another task
1092        * to fix.
1093        */
1094       zlog_warn ("SLOW THREAD: task %s (%lx) ran for %lums (cpu time %lums)",
1095                  thread->funcname,
1096                  (unsigned long) thread->func,
1097                  realtime/1000, cputime/1000);
1098     }
1099 #endif /* CONSUMED_TIME_CHECK */
1100
1101   XFREE (MTYPE_THREAD_FUNCNAME, thread->funcname);
1102 }
1103
1104 /* Execute thread */
1105 struct thread *
1106 funcname_thread_execute (struct thread_master *m,
1107                 int (*func)(struct thread *),
1108                 void *arg,
1109                 int val,
1110                 const char* funcname)
1111 {
1112   struct thread dummy;
1113
1114   memset (&dummy, 0, sizeof (struct thread));
1115
1116   dummy.type = THREAD_EVENT;
1117   dummy.add_type = THREAD_EXECUTE;
1118   dummy.master = NULL;
1119   dummy.func = func;
1120   dummy.arg = arg;
1121   dummy.u.val = val;
1122   dummy.funcname = strip_funcname (funcname);
1123   thread_call (&dummy);
1124
1125   XFREE (MTYPE_THREAD_FUNCNAME, dummy.funcname);
1126
1127   return NULL;
1128 }