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 inline void
 243 vty_out_cpu_thread_history(struct vty* vty,
 244                            struct cpu_thread_history *a)
 245 {
 246 #ifdef HAVE_RUSAGE
 247   vty_out(vty, "%7ld.%03ld %9d %8ld %9ld %8ld %9ld",
 248           a->cpu.total/1000, a->cpu.total%1000, a->total_calls,
 249           a->cpu.total/a->total_calls, a->cpu.max,
 250           a->real.total/a->total_calls, a->real.max);
 251 #else
 252   vty_out(vty, "%7ld.%03ld %9d %8ld %9ld",
 253           a->real.total/1000, a->real.total%1000, a->total_calls,
 254           a->real.total/a->total_calls, a->real.max);
 255 #endif
 256   vty_out(vty, " %c%c%c%c%c%c %s%s",
 257           a->types & (1 << THREAD_READ) ? 'R':' ',
 258           a->types & (1 << THREAD_WRITE) ? 'W':' ',
 259           a->types & (1 << THREAD_TIMER) ? 'T':' ',
 260           a->types & (1 << THREAD_EVENT) ? 'E':' ',
 261           a->types & (1 << THREAD_EXECUTE) ? 'X':' ',
 262           a->types & (1 << THREAD_BACKGROUND) ? 'B' : ' ',
 263           a->funcname, VTY_NEWLINE);
 264 }
 265
 266 static void
 267 cpu_record_hash_print(struct hash_backet *bucket,
 268                       void *args[])
 269 {
 270   struct cpu_thread_history *totals = args[0];
 271   struct vty *vty = args[1];
 272   unsigned char *filter = args[2];
 273   struct cpu_thread_history *a = bucket->data;
 274
 275   a = bucket->data;
 276   if ( !(a->types & *filter) )
 277        return;
 278   vty_out_cpu_thread_history(vty,a);
 279   totals->total_calls += a->total_calls;
 280   totals->real.total += a->real.total;
 281   if (totals->real.max < a->real.max)
 282     totals->real.max = a->real.max;
 283 #ifdef HAVE_RUSAGE
 284   totals->cpu.total += a->cpu.total;
 285   if (totals->cpu.max < a->cpu.max)
 286     totals->cpu.max = a->cpu.max;
 287 #endif
 288 }
 289
 290 static void
 291 cpu_record_print(struct vty *vty, unsigned char filter)
 292 {
 293   struct cpu_thread_history tmp;
 294   void *args[3] = {&tmp, vty, &filter};
 295
 296   memset(&tmp, 0, sizeof tmp);
 297   tmp.funcname = "TOTAL";
 298   tmp.types = filter;
 299
 300 #ifdef HAVE_RUSAGE
 301   vty_out(vty, "%21s %18s %18s%s",
 302           "", "CPU (user+system):", "Real (wall-clock):", VTY_NEWLINE);
 303 #endif
 304   vty_out(vty, "Runtime(ms)   Invoked Avg uSec Max uSecs");
 305 #ifdef HAVE_RUSAGE
 306   vty_out(vty, " Avg uSec Max uSecs");
 307 #endif
 308   vty_out(vty, "  Type  Thread%s", VTY_NEWLINE);
 309   hash_iterate(cpu_record,
 310                (void(*)(struct hash_backet*,void*))cpu_record_hash_print,
 311                args);
 312
 313   if (tmp.total_calls > 0)
 314     vty_out_cpu_thread_history(vty, &tmp);
 315 }
 316
 317 DEFUN(show_thread_cpu,
 318       show_thread_cpu_cmd,
 319       "show thread cpu [FILTER]",
 320       SHOW_STR
 321       "Thread information\n"
 322       "Thread CPU usage\n"
 323       "Display filter (rwtexb)\n")
 324 {
 325   int i = 0;
 326   unsigned char filter = 0xff;
 327
 328   if (argc > 0)
 329     {
 330       filter = 0;
 331       while (argv[0][i] != '\0')
 332         {
 333           switch ( argv[0][i] )
 334             {
 335             case 'r':
 336             case 'R':
 337               filter |= (1 << THREAD_READ);
 338               break;
 339             case 'w':
 340             case 'W':
 341               filter |= (1 << THREAD_WRITE);
 342               break;
 343             case 't':
 344             case 'T':
 345               filter |= (1 << THREAD_TIMER);
 346               break;
 347             case 'e':
 348             case 'E':
 349               filter |= (1 << THREAD_EVENT);
 350               break;
 351             case 'x':
 352             case 'X':
 353               filter |= (1 << THREAD_EXECUTE);
 354               break;
 355             case 'b':
 356             case 'B':
 357               filter |= (1 << THREAD_BACKGROUND);
 358               break;
 359             default:
 360               break;
 361             }
 362           ++i;
 363         }
 364       if (filter == 0)
 365         {
 366           vty_out(vty, "Invalid filter \"%s\" specified,"
 367                   " must contain at least one of 'RWTEXB'%s",
 368                   argv[0], VTY_NEWLINE);
 369           return CMD_WARNING;
 370         }
 371     }
 372
 373   cpu_record_print(vty, filter);
 374   return CMD_SUCCESS;
 375 }
 376 \f
 377 /* List allocation and head/tail print out. */
 378 static void
 379 thread_list_debug (struct thread_list *list)
 380 {
 381   printf ("count [%d] head [%p] tail [%p]\n",
 382           list->count, list->head, list->tail);
 383 }
 384
 385 /* Debug print for thread_master. */
 386 static void  __attribute__ ((unused))
 387 thread_master_debug (struct thread_master *m)
 388 {
 389   printf ("-----------\n");
 390   printf ("readlist  : ");
 391   thread_list_debug (&m->read);
 392   printf ("writelist : ");
 393   thread_list_debug (&m->write);
 394   printf ("timerlist : ");
 395   thread_list_debug (&m->timer);
 396   printf ("eventlist : ");
 397   thread_list_debug (&m->event);
 398   printf ("unuselist : ");
 399   thread_list_debug (&m->unuse);
 400   printf ("bgndlist : ");
 401   thread_list_debug (&m->background);
 402   printf ("total alloc: [%ld]\n", m->alloc);
 403   printf ("-----------\n");
 404 }
 405 \f
 406 /* Allocate new thread master.  */
 407 struct thread_master *
 408 thread_master_create ()
 409 {
 410   if (cpu_record == NULL)
 411     cpu_record
 412       = hash_create_size (1011, (unsigned int (*) (void *))cpu_record_hash_key,
 413                           (int (*) (const void *, const void *))cpu_record_hash_cmp);
 414
 415   return (struct thread_master *) XCALLOC (MTYPE_THREAD_MASTER,
 416                                            sizeof (struct thread_master));
 417 }
 418
 419 /* Add a new thread to the list.  */
 420 static void
 421 thread_list_add (struct thread_list *list, struct thread *thread)
 422 {
 423   thread->next = NULL;
 424   thread->prev = list->tail;
 425   if (list->tail)
 426     list->tail->next = thread;
 427   else
 428     list->head = thread;
 429   list->tail = thread;
 430   list->count++;
 431 }
 432
 433 /* Add a new thread just before the point.  */
 434 static void
 435 thread_list_add_before (struct thread_list *list,
 436                         struct thread *point,
 437                         struct thread *thread)
 438 {
 439   thread->next = point;
 440   thread->prev = point->prev;
 441   if (point->prev)
 442     point->prev->next = thread;
 443   else
 444     list->head = thread;
 445   point->prev = thread;
 446   list->count++;
 447 }
 448
 449 /* Delete a thread from the list. */
 450 static struct thread *
 451 thread_list_delete (struct thread_list *list, struct thread *thread)
 452 {
 453   if (thread->next)
 454     thread->next->prev = thread->prev;
 455   else
 456     list->tail = thread->prev;
 457   if (thread->prev)
 458     thread->prev->next = thread->next;
 459   else
 460     list->head = thread->next;
 461   thread->next = thread->prev = NULL;
 462   list->count--;
 463   return thread;
 464 }
 465
 466 /* Move thread to unuse list. */
 467 static void
 468 thread_add_unuse (struct thread_master *m, struct thread *thread)
 469 {
 470   assert (m != NULL && thread != NULL);
 471   assert (thread->next == NULL);
 472   assert (thread->prev == NULL);
 473   assert (thread->type == THREAD_UNUSED);
 474   thread_list_add (&m->unuse, thread);
 475   /* XXX: Should we deallocate funcname here? */
 476 }
 477
 478 /* Free all unused thread. */
 479 static void
 480 thread_list_free (struct thread_master *m, struct thread_list *list)
 481 {
 482   struct thread *t;
 483   struct thread *next;
 484
 485   for (t = list->head; t; t = next)
 486     {
 487       next = t->next;
 488       XFREE (MTYPE_THREAD_FUNCNAME, t->funcname);
 489       XFREE (MTYPE_THREAD, t);
 490       list->count--;
 491       m->alloc--;
 492     }
 493 }
 494
 495 /* Stop thread scheduler. */
 496 void
 497 thread_master_free (struct thread_master *m)
 498 {
 499   thread_list_free (m, &m->read);
 500   thread_list_free (m, &m->write);
 501   thread_list_free (m, &m->timer);
 502   thread_list_free (m, &m->event);
 503   thread_list_free (m, &m->ready);
 504   thread_list_free (m, &m->unuse);
 505   thread_list_free (m, &m->background);
 506
 507   XFREE (MTYPE_THREAD_MASTER, m);
 508 }
 509
 510 /* Thread list is empty or not.  */
 511 static inline int
 512 thread_empty (struct thread_list *list)
 513 {
 514   return  list->head ? 0 : 1;
 515 }
 516
 517 /* Delete top of the list and return it. */
 518 static struct thread *
 519 thread_trim_head (struct thread_list *list)
 520 {
 521   if (!thread_empty (list))
 522     return thread_list_delete (list, list->head);
 523   return NULL;
 524 }
 525
 526 /* Return remain time in second. */
 527 unsigned long
 528 thread_timer_remain_second (struct thread *thread)
 529 {
 530   quagga_get_relative (NULL);
 531
 532   if (thread->u.sands.tv_sec - relative_time.tv_sec > 0)
 533     return thread->u.sands.tv_sec - relative_time.tv_sec;
 534   else
 535     return 0;
 536 }
 537
 538 /* Trim blankspace and "()"s */
 539 static char *
 540 strip_funcname (const char *funcname)
 541 {
 542   char buff[100];
 543   char tmp, *ret, *e, *b = buff;
 544
 545   strncpy(buff, funcname, sizeof(buff));
 546   buff[ sizeof(buff) -1] = '\0';
 547   e = buff +strlen(buff) -1;
 548
 549   /* Wont work for funcname ==  "Word (explanation)"  */
 550
 551   while (*b == ' ' || *b == '(')
 552     ++b;
 553   while (*e == ' ' || *e == ')')
 554     --e;
 555   e++;
 556
 557   tmp = *e;
 558   *e = '\0';
 559   ret  = XSTRDUP (MTYPE_THREAD_FUNCNAME, b);
 560   *e = tmp;
 561
 562   return ret;
 563 }
 564
 565 /* Get new thread.  */
 566 static struct thread *
 567 thread_get (struct thread_master *m, u_char type,
 568             int (*func) (struct thread *), void *arg, const char* funcname)
 569 {
 570   struct thread *thread;
 571
 572   if (!thread_empty (&m->unuse))
 573     {
 574       thread = thread_trim_head (&m->unuse);
 575       if (thread->funcname)
 576         XFREE(MTYPE_THREAD_FUNCNAME, thread->funcname);
 577     }
 578   else
 579     {
 580       thread = XCALLOC (MTYPE_THREAD, sizeof (struct thread));
 581       m->alloc++;
 582     }
 583   thread->type = type;
 584   thread->add_type = type;
 585   thread->master = m;
 586   thread->func = func;
 587   thread->arg = arg;
 588
 589   thread->funcname = strip_funcname(funcname);
 590
 591   return thread;
 592 }
 593
 594 /* Add new read thread. */
 595 struct thread *
 596 funcname_thread_add_read (struct thread_master *m,
 597                  int (*func) (struct thread *), void *arg, int fd, const char* funcname)
 598 {
 599   struct thread *thread;
 600
 601   assert (m != NULL);
 602
 603   if (FD_ISSET (fd, &m->readfd))
 604     {
 605       zlog (NULL, LOG_WARNING, "There is already read fd [%d]", fd);
 606       return NULL;
 607     }
 608
 609   thread = thread_get (m, THREAD_READ, func, arg, funcname);
 610   FD_SET (fd, &m->readfd);
 611   thread->u.fd = fd;
 612   thread_list_add (&m->read, thread);
 613
 614   return thread;
 615 }
 616
 617 /* Add new write thread. */
 618 struct thread *
 619 funcname_thread_add_write (struct thread_master *m,
 620                  int (*func) (struct thread *), void *arg, int fd, const char* funcname)
 621 {
 622   struct thread *thread;
 623
 624   assert (m != NULL);
 625
 626   if (FD_ISSET (fd, &m->writefd))
 627     {
 628       zlog (NULL, LOG_WARNING, "There is already write fd [%d]", fd);
 629       return NULL;
 630     }
 631
 632   thread = thread_get (m, THREAD_WRITE, func, arg, funcname);
 633   FD_SET (fd, &m->writefd);
 634   thread->u.fd = fd;
 635   thread_list_add (&m->write, thread);
 636
 637   return thread;
 638 }
 639
 640 static struct thread *
 641 funcname_thread_add_timer_timeval (struct thread_master *m,
 642                                    int (*func) (struct thread *),
 643                                   int type,
 644                                   void *arg,
 645                                   struct timeval *time_relative,
 646                                   const char* funcname)
 647 {
 648   struct thread *thread;
 649   struct thread_list *list;
 650   struct timeval alarm_time;
 651   struct thread *tt;
 652
 653   assert (m != NULL);
 654
 655   assert (type == THREAD_TIMER || type == THREAD_BACKGROUND);
 656   assert (time_relative);
 657
 658   list = ((type == THREAD_TIMER) ? &m->timer : &m->background);
 659   thread = thread_get (m, type, func, arg, funcname);
 660
 661   /* Do we need jitter here? */
 662   quagga_get_relative (NULL);
 663   alarm_time.tv_sec = relative_time.tv_sec + time_relative->tv_sec;
 664   alarm_time.tv_usec = relative_time.tv_usec + time_relative->tv_usec;
 665   thread->u.sands = timeval_adjust(alarm_time);
 666
 667   /* Sort by timeval. */
 668   for (tt = list->head; tt; tt = tt->next)
 669     if (timeval_cmp (thread->u.sands, tt->u.sands) <= 0)
 670       break;
 671
 672   if (tt)
 673     thread_list_add_before (list, tt, thread);
 674   else
 675     thread_list_add (list, thread);
 676
 677   return thread;
 678 }
 679
 680
 681 /* Add timer event thread. */
 682 struct thread *
 683 funcname_thread_add_timer (struct thread_master *m,
 684                            int (*func) (struct thread *),
 685                            void *arg, long timer, const char* funcname)
 686 {
 687   struct timeval trel;
 688
 689   assert (m != NULL);
 690
 691   trel.tv_sec = timer;
 692   trel.tv_usec = 0;
 693
 694   return funcname_thread_add_timer_timeval (m, func, THREAD_TIMER, arg,
 695                                             &trel, funcname);
 696 }
 697
 698 /* Add timer event thread with "millisecond" resolution */
 699 struct thread *
 700 funcname_thread_add_timer_msec (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 / 1000;
 709   trel.tv_usec = 1000*(timer % 1000);
 710
 711   return funcname_thread_add_timer_timeval (m, func, THREAD_TIMER,
 712                                             arg, &trel, funcname);
 713 }
 714
 715 /* Add a background thread, with an optional millisec delay */
 716 struct thread *
 717 funcname_thread_add_background (struct thread_master *m,
 718                                 int (*func) (struct thread *),
 719                                 void *arg, long delay,
 720                                 const char *funcname)
 721 {
 722   struct timeval trel;
 723
 724   assert (m != NULL);
 725
 726   if (delay)
 727     {
 728       trel.tv_sec = delay / 1000;
 729       trel.tv_usec = 1000*(delay % 1000);
 730     }
 731   else
 732     {
 733       trel.tv_sec = 0;
 734       trel.tv_usec = 0;
 735     }
 736
 737   return funcname_thread_add_timer_timeval (m, func, THREAD_BACKGROUND,
 738                                             arg, &trel, funcname);
 739 }
 740
 741 /* Add simple event thread. */
 742 struct thread *
 743 funcname_thread_add_event (struct thread_master *m,
 744                   int (*func) (struct thread *), void *arg, int val, const char* funcname)
 745 {
 746   struct thread *thread;
 747
 748   assert (m != NULL);
 749
 750   thread = thread_get (m, THREAD_EVENT, func, arg, funcname);
 751   thread->u.val = val;
 752   thread_list_add (&m->event, thread);
 753
 754   return thread;
 755 }
 756
 757 /* Cancel thread from scheduler. */
 758 void
 759 thread_cancel (struct thread *thread)
 760 {
 761   struct thread_list *list;
 762
 763   switch (thread->type)
 764     {
 765     case THREAD_READ:
 766       assert (FD_ISSET (thread->u.fd, &thread->master->readfd));
 767       FD_CLR (thread->u.fd, &thread->master->readfd);
 768       list = &thread->master->read;
 769       break;
 770     case THREAD_WRITE:
 771       assert (FD_ISSET (thread->u.fd, &thread->master->writefd));
 772       FD_CLR (thread->u.fd, &thread->master->writefd);
 773       list = &thread->master->write;
 774       break;
 775     case THREAD_TIMER:
 776       list = &thread->master->timer;
 777       break;
 778     case THREAD_EVENT:
 779       list = &thread->master->event;
 780       break;
 781     case THREAD_READY:
 782       list = &thread->master->ready;
 783       break;
 784     case THREAD_BACKGROUND:
 785       list = &thread->master->background;
 786       break;
 787     default:
 788       return;
 789       break;
 790     }
 791   thread_list_delete (list, thread);
 792   thread->type = THREAD_UNUSED;
 793   thread_add_unuse (thread->master, thread);
 794 }
 795
 796 /* Delete all events which has argument value arg. */
 797 unsigned int
 798 thread_cancel_event (struct thread_master *m, void *arg)
 799 {
 800   unsigned int ret = 0;
 801   struct thread *thread;
 802
 803   thread = m->event.head;
 804   while (thread)
 805     {
 806       struct thread *t;
 807
 808       t = thread;
 809       thread = t->next;
 810
 811       if (t->arg == arg)
 812         {
 813           ret++;
 814           thread_list_delete (&m->event, t);
 815           t->type = THREAD_UNUSED;
 816           thread_add_unuse (m, t);
 817         }
 818     }
 819   return ret;
 820 }
 821
 822 static struct timeval *
 823 thread_timer_wait (struct thread_list *tlist, struct timeval *timer_val)
 824 {
 825   if (!thread_empty (tlist))
 826     {
 827       *timer_val = timeval_subtract (tlist->head->u.sands, relative_time);
 828       return timer_val;
 829     }
 830   return NULL;
 831 }
 832
 833 static struct thread *
 834 thread_run (struct thread_master *m, struct thread *thread,
 835             struct thread *fetch)
 836 {
 837   *fetch = *thread;
 838   thread->type = THREAD_UNUSED;
 839   thread_add_unuse (m, thread);
 840   return fetch;
 841 }
 842
 843 static int
 844 thread_process_fd (struct thread_list *list, fd_set *fdset, fd_set *mfdset)
 845 {
 846   struct thread *thread;
 847   struct thread *next;
 848   int ready = 0;
 849
 850   assert (list);
 851
 852   for (thread = list->head; thread; thread = next)
 853     {
 854       next = thread->next;
 855
 856       if (FD_ISSET (THREAD_FD (thread), fdset))
 857         {
 858           assert (FD_ISSET (THREAD_FD (thread), mfdset));
 859           FD_CLR(THREAD_FD (thread), mfdset);
 860           thread_list_delete (list, thread);
 861           thread_list_add (&thread->master->ready, thread);
 862           thread->type = THREAD_READY;
 863           ready++;
 864         }
 865     }
 866   return ready;
 867 }
 868
 869 /* Add all timers that have popped to the ready list. */
 870 static unsigned int
 871 thread_timer_process (struct thread_list *list, struct timeval *timenow)
 872 {
 873   struct thread *thread;
 874   unsigned int ready = 0;
 875
 876   for (thread = list->head; thread; thread = thread->next)
 877     {
 878       if (timeval_cmp (*timenow, thread->u.sands) < 0)
 879         return ready;
 880       thread_list_delete (list, thread);
 881       thread->type = THREAD_READY;
 882       thread_list_add (&thread->master->ready, thread);
 883       ready++;
 884     }
 885   return ready;
 886 }
 887
 888 /* Fetch next ready thread. */
 889 struct thread *
 890 thread_fetch (struct thread_master *m, struct thread *fetch)
 891 {
 892   struct thread *thread;
 893   fd_set readfd;
 894   fd_set writefd;
 895   fd_set exceptfd;
 896   struct timeval timer_val;
 897   struct timeval timer_val_bg;
 898   struct timeval *timer_wait;
 899   struct timeval *timer_wait_bg;
 900
 901   while (1)
 902     {
 903       int num = 0;
 904
 905       /* Signals are highest priority */
 906       quagga_sigevent_process ();
 907
 908       /* Normal event are the next highest priority.  */
 909       if ((thread = thread_trim_head (&m->event)) != NULL)
 910         return thread_run (m, thread, fetch);
 911
 912       /* If there are any ready threads from previous scheduler runs,
 913        * process top of them.
 914        */
 915       if ((thread = thread_trim_head (&m->ready)) != NULL)
 916         return thread_run (m, thread, fetch);
 917
 918       /* Structure copy.  */
 919       readfd = m->readfd;
 920       writefd = m->writefd;
 921       exceptfd = m->exceptfd;
 922
 923       /* Calculate select wait timer if nothing else to do */
 924       quagga_get_relative (NULL);
 925       timer_wait = thread_timer_wait (&m->timer, &timer_val);
 926       timer_wait_bg = thread_timer_wait (&m->background, &timer_val_bg);
 927
 928       if (timer_wait_bg &&
 929           (!timer_wait || (timeval_cmp (*timer_wait, *timer_wait_bg) > 0)))
 930         timer_wait = timer_wait_bg;
 931
 932       num = select (FD_SETSIZE, &readfd, &writefd, &exceptfd, timer_wait);
 933
 934       /* Signals should get quick treatment */
 935       if (num < 0)
 936         {
 937           if (errno == EINTR)
 938             continue; /* signal received - process it */
 939           zlog_warn ("select() error: %s", safe_strerror (errno));
 940             return NULL;
 941         }
 942
 943       /* Check foreground timers.  Historically, they have had higher
 944          priority than I/O threads, so let's push them onto the ready
 945          list in front of the I/O threads. */
 946       quagga_get_relative (NULL);
 947       thread_timer_process (&m->timer, &relative_time);
 948
 949       /* Got IO, process it */
 950       if (num > 0)
 951         {
 952           /* Normal priority read thead. */
 953           thread_process_fd (&m->read, &readfd, &m->readfd);
 954           /* Write thead. */
 955           thread_process_fd (&m->write, &writefd, &m->writefd);
 956         }
 957
 958 #if 0
 959       /* If any threads were made ready above (I/O or foreground timer),
 960          perhaps we should avoid adding background timers to the ready
 961          list at this time.  If this is code is uncommented, then background
 962          timer threads will not run unless there is nothing else to do. */
 963       if ((thread = thread_trim_head (&m->ready)) != NULL)
 964         return thread_run (m, thread, fetch);
 965 #endif
 966
 967       /* Background timer/events, lowest priority */
 968       thread_timer_process (&m->background, &relative_time);
 969
 970       if ((thread = thread_trim_head (&m->ready)) != NULL)
 971         return thread_run (m, thread, fetch);
 972     }
 973 }
 974
 975 unsigned long
 976 thread_consumed_time (RUSAGE_T *now, RUSAGE_T *start, unsigned long *cputime)
 977 {
 978 #ifdef HAVE_RUSAGE
 979   /* This is 'user + sys' time.  */
 980   *cputime = timeval_elapsed (now->cpu.ru_utime, start->cpu.ru_utime) +
 981              timeval_elapsed (now->cpu.ru_stime, start->cpu.ru_stime);
 982 #else
 983   *cputime = 0;
 984 #endif /* HAVE_RUSAGE */
 985   return timeval_elapsed (now->real, start->real);
 986 }
 987
 988 /* We should aim to yield after THREAD_YIELD_TIME_SLOT milliseconds.
 989    Note: we are using real (wall clock) time for this calculation.
 990    It could be argued that CPU time may make more sense in certain
 991    contexts.  The things to consider are whether the thread may have
 992    blocked (in which case wall time increases, but CPU time does not),
 993    or whether the system is heavily loaded with other processes competing
 994    for CPU time.  On balance, wall clock time seems to make sense.
 995    Plus it has the added benefit that gettimeofday should be faster
 996    than calling getrusage. */
 997 int
 998 thread_should_yield (struct thread *thread)
 999 {
1000   quagga_get_relative (NULL);
1001   return (timeval_elapsed(relative_time, thread->ru.real) >
1002           THREAD_YIELD_TIME_SLOT);
1003 }
1004
1005 void
1006 thread_getrusage (RUSAGE_T *r)
1007 {
1008   quagga_get_relative (NULL);
1009 #ifdef HAVE_RUSAGE
1010   getrusage(RUSAGE_SELF, &(r->cpu));
1011 #endif
1012   r->real = relative_time;
1013
1014 #ifdef HAVE_CLOCK_MONOTONIC
1015   /* quagga_get_relative() only updates recent_time if gettimeofday
1016    * based, not when using CLOCK_MONOTONIC. As we export recent_time
1017    * and guarantee to update it before threads are run...
1018    */
1019   quagga_gettimeofday(&recent_time);
1020 #endif /* HAVE_CLOCK_MONOTONIC */
1021 }
1022
1023 /* We check thread consumed time. If the system has getrusage, we'll
1024    use that to get in-depth stats on the performance of the thread in addition
1025    to wall clock time stats from gettimeofday. */
1026 void
1027 thread_call (struct thread *thread)
1028 {
1029   unsigned long realtime, cputime;
1030   RUSAGE_T ru;
1031
1032  /* Cache a pointer to the relevant cpu history thread, if the thread
1033   * does not have it yet.
1034   *
1035   * Callers submitting 'dummy threads' hence must take care that
1036   * thread->cpu is NULL
1037   */
1038   if (!thread->hist)
1039     {
1040       struct cpu_thread_history tmp;
1041
1042       tmp.func = thread->func;
1043       tmp.funcname = thread->funcname;
1044
1045       thread->hist = hash_get (cpu_record, &tmp,
1046                     (void * (*) (void *))cpu_record_hash_alloc);
1047     }
1048
1049   GETRUSAGE (&thread->ru);
1050
1051   (*thread->func) (thread);
1052
1053   GETRUSAGE (&ru);
1054
1055   realtime = thread_consumed_time (&ru, &thread->ru, &cputime);
1056   thread->hist->real.total += realtime;
1057   if (thread->hist->real.max < realtime)
1058     thread->hist->real.max = realtime;
1059 #ifdef HAVE_RUSAGE
1060   thread->hist->cpu.total += cputime;
1061   if (thread->hist->cpu.max < cputime)
1062     thread->hist->cpu.max = cputime;
1063 #endif
1064
1065   ++(thread->hist->total_calls);
1066   thread->hist->types |= (1 << thread->add_type);
1067
1068 #ifdef CONSUMED_TIME_CHECK
1069   if (realtime > CONSUMED_TIME_CHECK)
1070     {
1071       /*
1072        * We have a CPU Hog on our hands.
1073        * Whinge about it now, so we're aware this is yet another task
1074        * to fix.
1075        */
1076       zlog_warn ("SLOW THREAD: task %s (%lx) ran for %lums (cpu time %lums)",
1077                  thread->funcname,
1078                  (unsigned long) thread->func,
1079                  realtime/1000, cputime/1000);
1080     }
1081 #endif /* CONSUMED_TIME_CHECK */
1082 }
1083
1084 /* Execute thread */
1085 struct thread *
1086 funcname_thread_execute (struct thread_master *m,
1087                 int (*func)(struct thread *),
1088                 void *arg,
1089                 int val,
1090                 const char* funcname)
1091 {
1092   struct thread dummy;
1093
1094   memset (&dummy, 0, sizeof (struct thread));
1095
1096   dummy.type = THREAD_EVENT;
1097   dummy.add_type = THREAD_EXECUTE;
1098   dummy.master = NULL;
1099   dummy.func = func;
1100   dummy.arg = arg;
1101   dummy.u.val = val;
1102   dummy.funcname = strip_funcname (funcname);
1103   thread_call (&dummy);
1104
1105   XFREE (MTYPE_THREAD_FUNCNAME, dummy.funcname);
1106
1107   return NULL;
1108 }