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 \f
  30 /* Struct timeval's tv_usec one second value.  */
  31 #define TIMER_SECOND_MICRO 1000000L
  32
  33 struct timeval
  34 timeval_adjust (struct timeval a)
  35 {
  36   while (a.tv_usec >= TIMER_SECOND_MICRO)
  37     {
  38       a.tv_usec -= TIMER_SECOND_MICRO;
  39       a.tv_sec++;
  40     }
  41
  42   while (a.tv_usec < 0)
  43     {
  44       a.tv_usec += TIMER_SECOND_MICRO;
  45       a.tv_sec--;
  46     }
  47
  48   if (a.tv_sec < 0)
  49     {
  50       a.tv_sec = 0;
  51       a.tv_usec = 10;
  52     }
  53
  54   if (a.tv_sec > TIMER_SECOND_MICRO)
  55     a.tv_sec = TIMER_SECOND_MICRO;
  56
  57   return a;
  58 }
  59
  60 static struct timeval
  61 timeval_subtract (struct timeval a, struct timeval b)
  62 {
  63   struct timeval ret;
  64
  65   ret.tv_usec = a.tv_usec - b.tv_usec;
  66   ret.tv_sec = a.tv_sec - b.tv_sec;
  67
  68   return timeval_adjust (ret);
  69 }
  70
  71 static int
  72 timeval_cmp (struct timeval a, struct timeval b)
  73 {
  74   return (a.tv_sec == b.tv_sec
  75           ? a.tv_usec - b.tv_usec : a.tv_sec - b.tv_sec);
  76 }
  77
  78 static unsigned long
  79 timeval_elapsed (struct timeval a, struct timeval b)
  80 {
  81   return (((a.tv_sec - b.tv_sec) * TIMER_SECOND_MICRO)
  82           + (a.tv_usec - b.tv_usec));
  83 }
  84 \f
  85 /* List allocation and head/tail print out. */
  86 static void
  87 thread_list_debug (struct thread_list *list)
  88 {
  89   printf ("count [%d] head [%p] tail [%p]\n",
  90           list->count, list->head, list->tail);
  91 }
  92
  93 /* Debug print for thread_master. */
  94 void
  95 thread_master_debug (struct thread_master *m)
  96 {
  97   printf ("-----------\n");
  98   printf ("readlist  : ");
  99   thread_list_debug (&m->read);
 100   printf ("writelist : ");
 101   thread_list_debug (&m->write);
 102   printf ("timerlist : ");
 103   thread_list_debug (&m->timer);
 104   printf ("eventlist : ");
 105   thread_list_debug (&m->event);
 106   printf ("unuselist : ");
 107   thread_list_debug (&m->unuse);
 108   printf ("total alloc: [%ld]\n", m->alloc);
 109   printf ("-----------\n");
 110 }
 111 \f
 112 /* Allocate new thread master.  */
 113 struct thread_master *
 114 thread_master_create ()
 115 {
 116   return (struct thread_master *) XCALLOC (MTYPE_THREAD_MASTER,
 117                                            sizeof (struct thread_master));
 118 }
 119
 120 /* Add a new thread to the list.  */
 121 static void
 122 thread_list_add (struct thread_list *list, struct thread *thread)
 123 {
 124   thread->next = NULL;
 125   thread->prev = list->tail;
 126   if (list->tail)
 127     list->tail->next = thread;
 128   else
 129     list->head = thread;
 130   list->tail = thread;
 131   list->count++;
 132 }
 133
 134 /* Add a new thread just before the point.  */
 135 static void
 136 thread_list_add_before (struct thread_list *list,
 137                         struct thread *point,
 138                         struct thread *thread)
 139 {
 140   thread->next = point;
 141   thread->prev = point->prev;
 142   if (point->prev)
 143     point->prev->next = thread;
 144   else
 145     list->head = thread;
 146   point->prev = thread;
 147   list->count++;
 148 }
 149
 150 /* Delete a thread from the list. */
 151 static struct thread *
 152 thread_list_delete (struct thread_list *list, struct thread *thread)
 153 {
 154   if (thread->next)
 155     thread->next->prev = thread->prev;
 156   else
 157     list->tail = thread->prev;
 158   if (thread->prev)
 159     thread->prev->next = thread->next;
 160   else
 161     list->head = thread->next;
 162   thread->next = thread->prev = NULL;
 163   list->count--;
 164   return thread;
 165 }
 166
 167 /* Move thread to unuse list. */
 168 static void
 169 thread_add_unuse (struct thread_master *m, struct thread *thread)
 170 {
 171   assert (m != NULL);
 172   assert (thread->next == NULL);
 173   assert (thread->prev == NULL);
 174   assert (thread->type == THREAD_UNUSED);
 175   thread_list_add (&m->unuse, thread);
 176 }
 177
 178 /* Free all unused thread. */
 179 static void
 180 thread_list_free (struct thread_master *m, struct thread_list *list)
 181 {
 182   struct thread *t;
 183   struct thread *next;
 184
 185   for (t = list->head; t; t = next)
 186     {
 187       next = t->next;
 188       XFREE (MTYPE_THREAD, t);
 189       list->count--;
 190       m->alloc--;
 191     }
 192 }
 193
 194 /* Stop thread scheduler. */
 195 void
 196 thread_master_free (struct thread_master *m)
 197 {
 198   thread_list_free (m, &m->read);
 199   thread_list_free (m, &m->write);
 200   thread_list_free (m, &m->timer);
 201   thread_list_free (m, &m->event);
 202   thread_list_free (m, &m->ready);
 203   thread_list_free (m, &m->unuse);
 204
 205   XFREE (MTYPE_THREAD_MASTER, m);
 206 }
 207
 208 /* Delete top of the list and return it. */
 209 static struct thread *
 210 thread_trim_head (struct thread_list *list)
 211 {
 212   if (list->head)
 213     return thread_list_delete (list, list->head);
 214   return NULL;
 215 }
 216
 217 /* Thread list is empty or not.  */
 218 int
 219 thread_empty (struct thread_list *list)
 220 {
 221   return  list->head ? 0 : 1;
 222 }
 223
 224 /* Return remain time in second. */
 225 unsigned long
 226 thread_timer_remain_second (struct thread *thread)
 227 {
 228   struct timeval timer_now;
 229
 230   gettimeofday (&timer_now, NULL);
 231
 232   if (thread->u.sands.tv_sec - timer_now.tv_sec > 0)
 233     return thread->u.sands.tv_sec - timer_now.tv_sec;
 234   else
 235     return 0;
 236 }
 237
 238 /* Get new thread.  */
 239 static struct thread *
 240 thread_get (struct thread_master *m, u_char type,
 241             int (*func) (struct thread *), void *arg)
 242 {
 243   struct thread *thread;
 244
 245   if (m->unuse.head)
 246     thread = thread_trim_head (&m->unuse);
 247   else
 248     {
 249       thread = XCALLOC (MTYPE_THREAD, sizeof (struct thread));
 250       m->alloc++;
 251     }
 252   thread->type = type;
 253   thread->master = m;
 254   thread->func = func;
 255   thread->arg = arg;
 256
 257   return thread;
 258 }
 259
 260 /* Add new read thread. */
 261 struct thread *
 262 thread_add_read (struct thread_master *m,
 263                  int (*func) (struct thread *), void *arg, int fd)
 264 {
 265   struct thread *thread;
 266
 267   assert (m != NULL);
 268
 269   if (FD_ISSET (fd, &m->readfd))
 270     {
 271       zlog (NULL, LOG_WARNING, "There is already read fd [%d]", fd);
 272       return NULL;
 273     }
 274
 275   thread = thread_get (m, THREAD_READ, func, arg);
 276   FD_SET (fd, &m->readfd);
 277   thread->u.fd = fd;
 278   thread_list_add (&m->read, thread);
 279
 280   return thread;
 281 }
 282
 283 /* Add new write thread. */
 284 struct thread *
 285 thread_add_write (struct thread_master *m,
 286                  int (*func) (struct thread *), void *arg, int fd)
 287 {
 288   struct thread *thread;
 289
 290   assert (m != NULL);
 291
 292   if (FD_ISSET (fd, &m->writefd))
 293     {
 294       zlog (NULL, LOG_WARNING, "There is already write fd [%d]", fd);
 295       return NULL;
 296     }
 297
 298   thread = thread_get (m, THREAD_WRITE, func, arg);
 299   FD_SET (fd, &m->writefd);
 300   thread->u.fd = fd;
 301   thread_list_add (&m->write, thread);
 302
 303   return thread;
 304 }
 305
 306 /* Add timer event thread. */
 307 struct thread *
 308 thread_add_timer (struct thread_master *m,
 309                   int (*func) (struct thread *), void *arg, long timer)
 310 {
 311   struct timeval timer_now;
 312   struct thread *thread;
 313 #ifndef TIMER_NO_SORT
 314   struct thread *tt;
 315 #endif /* TIMER_NO_SORT */
 316
 317   assert (m != NULL);
 318
 319   thread = thread_get (m, THREAD_TIMER, func, arg);
 320
 321   /* Do we need jitter here? */
 322   gettimeofday (&timer_now, NULL);
 323   timer_now.tv_sec += timer;
 324   thread->u.sands = timer_now;
 325
 326   /* Sort by timeval. */
 327 #ifdef TIMER_NO_SORT
 328   thread_list_add (&m->timer, thread);
 329 #else
 330   for (tt = m->timer.head; tt; tt = tt->next)
 331     if (timeval_cmp (thread->u.sands, tt->u.sands) <= 0)
 332       break;
 333
 334   if (tt)
 335     thread_list_add_before (&m->timer, tt, thread);
 336   else
 337     thread_list_add (&m->timer, thread);
 338 #endif /* TIMER_NO_SORT */
 339
 340   return thread;
 341 }
 342
 343 /* Add simple event thread. */
 344 struct thread *
 345 thread_add_event (struct thread_master *m,
 346                   int (*func) (struct thread *), void *arg, int val)
 347 {
 348   struct thread *thread;
 349
 350   assert (m != NULL);
 351
 352   thread = thread_get (m, THREAD_EVENT, func, arg);
 353   thread->u.val = val;
 354   thread_list_add (&m->event, thread);
 355
 356   return thread;
 357 }
 358
 359 /* Cancel thread from scheduler. */
 360 void
 361 thread_cancel (struct thread *thread)
 362 {
 363   switch (thread->type)
 364     {
 365     case THREAD_READ:
 366       assert (FD_ISSET (thread->u.fd, &thread->master->readfd));
 367       FD_CLR (thread->u.fd, &thread->master->readfd);
 368       thread_list_delete (&thread->master->read, thread);
 369       break;
 370     case THREAD_WRITE:
 371       assert (FD_ISSET (thread->u.fd, &thread->master->writefd));
 372       FD_CLR (thread->u.fd, &thread->master->writefd);
 373       thread_list_delete (&thread->master->write, thread);
 374       break;
 375     case THREAD_TIMER:
 376       thread_list_delete (&thread->master->timer, thread);
 377       break;
 378     case THREAD_EVENT:
 379       thread_list_delete (&thread->master->event, thread);
 380       break;
 381     case THREAD_READY:
 382       thread_list_delete (&thread->master->ready, thread);
 383       break;
 384     default:
 385       break;
 386     }
 387   thread->type = THREAD_UNUSED;
 388   thread_add_unuse (thread->master, thread);
 389 }
 390
 391 /* Delete all events which has argument value arg. */
 392 void
 393 thread_cancel_event (struct thread_master *m, void *arg)
 394 {
 395   struct thread *thread;
 396
 397   thread = m->event.head;
 398   while (thread)
 399     {
 400       struct thread *t;
 401
 402       t = thread;
 403       thread = t->next;
 404
 405       if (t->arg == arg)
 406         {
 407           thread_list_delete (&m->event, t);
 408           t->type = THREAD_UNUSED;
 409           thread_add_unuse (m, t);
 410         }
 411     }
 412 }
 413
 414 #ifdef TIMER_NO_SORT
 415 struct timeval *
 416 thread_timer_wait (struct thread_master *m, struct timeval *timer_val)
 417 {
 418   struct timeval timer_now;
 419   struct timeval timer_min;
 420   struct timeval *timer_wait;
 421
 422   gettimeofday (&timer_now, NULL);
 423
 424   timer_wait = NULL;
 425   for (thread = m->timer.head; thread; thread = thread->next)
 426     {
 427       if (! timer_wait)
 428         timer_wait = &thread->u.sands;
 429       else if (timeval_cmp (thread->u.sands, *timer_wait) < 0)
 430         timer_wait = &thread->u.sands;
 431     }
 432
 433   if (m->timer.head)
 434     {
 435       timer_min = *timer_wait;
 436       timer_min = timeval_subtract (timer_min, timer_now);
 437       if (timer_min.tv_sec < 0)
 438         {
 439           timer_min.tv_sec = 0;
 440           timer_min.tv_usec = 10;
 441         }
 442       timer_wait = &timer_min;
 443     }
 444   else
 445     timer_wait = NULL;
 446
 447   if (timer_wait)
 448     {
 449       *timer_val = timer_wait;
 450       return timer_val;
 451     }
 452   return NULL;
 453 }
 454 #else /* ! TIMER_NO_SORT */
 455 struct timeval *
 456 thread_timer_wait (struct thread_master *m, struct timeval *timer_val)
 457 {
 458   struct timeval timer_now;
 459   struct timeval timer_min;
 460
 461   if (m->timer.head)
 462     {
 463       gettimeofday (&timer_now, NULL);
 464       timer_min = m->timer.head->u.sands;
 465       timer_min = timeval_subtract (timer_min, timer_now);
 466       if (timer_min.tv_sec < 0)
 467         {
 468           timer_min.tv_sec = 0;
 469           timer_min.tv_usec = 10;
 470         }
 471       *timer_val = timer_min;
 472       return timer_val;
 473     }
 474   return NULL;
 475 }
 476 #endif /* TIMER_NO_SORT */
 477
 478 struct thread *
 479 thread_run (struct thread_master *m, struct thread *thread,
 480             struct thread *fetch)
 481 {
 482   *fetch = *thread;
 483   thread->type = THREAD_UNUSED;
 484   thread_add_unuse (m, thread);
 485   return fetch;
 486 }
 487
 488 int
 489 thread_process_fd (struct thread_master *m, struct thread_list *list,
 490                    fd_set *fdset, fd_set *mfdset)
 491 {
 492   struct thread *thread;
 493   struct thread *next;
 494   int ready = 0;
 495
 496   for (thread = list->head; thread; thread = next)
 497     {
 498       next = thread->next;
 499
 500       if (FD_ISSET (THREAD_FD (thread), fdset))
 501         {
 502           assert (FD_ISSET (THREAD_FD (thread), mfdset));
 503           FD_CLR(THREAD_FD (thread), mfdset);
 504           thread_list_delete (list, thread);
 505           thread_list_add (&m->ready, thread);
 506           thread->type = THREAD_READY;
 507           ready++;
 508         }
 509     }
 510   return ready;
 511 }
 512
 513 /* Fetch next ready thread. */
 514 struct thread *
 515 thread_fetch (struct thread_master *m, struct thread *fetch)
 516 {
 517   int num;
 518   int ready;
 519   struct thread *thread;
 520   fd_set readfd;
 521   fd_set writefd;
 522   fd_set exceptfd;
 523   struct timeval timer_now;
 524   struct timeval timer_val;
 525   struct timeval *timer_wait;
 526   struct timeval timer_nowait;
 527
 528   timer_nowait.tv_sec = 0;
 529   timer_nowait.tv_usec = 0;
 530
 531   while (1)
 532     {
 533       /* Normal event is the highest priority.  */
 534       if ((thread = thread_trim_head (&m->event)) != NULL)
 535         return thread_run (m, thread, fetch);
 536
 537       /* Execute timer.  */
 538       gettimeofday (&timer_now, NULL);
 539
 540       for (thread = m->timer.head; thread; thread = thread->next)
 541         if (timeval_cmp (timer_now, thread->u.sands) >= 0)
 542           {
 543             thread_list_delete (&m->timer, thread);
 544             return thread_run (m, thread, fetch);
 545           }
 546
 547       /* If there are any ready threads, process top of them.  */
 548       if ((thread = thread_trim_head (&m->ready)) != NULL)
 549         return thread_run (m, thread, fetch);
 550
 551       /* Structure copy.  */
 552       readfd = m->readfd;
 553       writefd = m->writefd;
 554       exceptfd = m->exceptfd;
 555
 556       /* Calculate select wait timer. */
 557       timer_wait = thread_timer_wait (m, &timer_val);
 558
 559       num = select (FD_SETSIZE, &readfd, &writefd, &exceptfd, timer_wait);
 560
 561       if (num == 0)
 562         continue;
 563
 564       if (num < 0)
 565         {
 566           if (errno == EINTR)
 567             continue;
 568
 569           zlog_warn ("select() error: %s", strerror (errno));
 570           return NULL;
 571         }
 572
 573       /* Normal priority read thead. */
 574       ready = thread_process_fd (m, &m->read, &readfd, &m->readfd);
 575
 576       /* Write thead. */
 577       ready = thread_process_fd (m, &m->write, &writefd, &m->writefd);
 578
 579       if ((thread = thread_trim_head (&m->ready)) != NULL)
 580         return thread_run (m, thread, fetch);
 581     }
 582 }
 583
 584 static unsigned long
 585 thread_consumed_time (RUSAGE_T *now, RUSAGE_T *start)
 586 {
 587   unsigned long thread_time;
 588
 589 #ifdef HAVE_RUSAGE
 590   /* This is 'user + sys' time.  */
 591   thread_time = timeval_elapsed (now->ru_utime, start->ru_utime);
 592   thread_time += timeval_elapsed (now->ru_stime, start->ru_stime);
 593 #else
 594   /* When rusage is not available, simple elapsed time is used.  */
 595   thread_time = timeval_elapsed (*now, *start);
 596 #endif /* HAVE_RUSAGE */
 597
 598   return thread_time;
 599 }
 600
 601 /* We should aim to yield after THREAD_YIELD_TIME_SLOT
 602    milliseconds.  */
 603 int
 604 thread_should_yield (struct thread *thread)
 605 {
 606   RUSAGE_T ru;
 607
 608   GETRUSAGE (&ru);
 609
 610   if (thread_consumed_time (&ru, &thread->ru) > THREAD_YIELD_TIME_SLOT)
 611     return 1;
 612   else
 613     return 0;
 614 }
 615
 616 /* We check thread consumed time. If the system has getrusage, we'll
 617    use that to get indepth stats on the performance of the thread.  If
 618    not - we'll use gettimeofday for some guestimation.  */
 619 void
 620 thread_call (struct thread *thread)
 621 {
 622   unsigned long thread_time;
 623   RUSAGE_T ru;
 624
 625   GETRUSAGE (&thread->ru);
 626
 627   (*thread->func) (thread);
 628
 629   GETRUSAGE (&ru);
 630
 631   thread_time = thread_consumed_time (&ru, &thread->ru);
 632
 633 #ifdef THREAD_CONSUMED_TIME_CHECK
 634   if (thread_time > 200000L)
 635     {
 636       /*
 637        * We have a CPU Hog on our hands.
 638        * Whinge about it now, so we're aware this is yet another task
 639        * to fix.
 640        */
 641       zlog_err ("CPU HOG task %lx ran for %ldms",
 642                 /* FIXME: report the name of the function somehow */
 643                 (unsigned long) thread->func,
 644                 thread_time / 1000L);
 645     }
 646 #endif /* THREAD_CONSUMED_TIME_CHECK */
 647 }
 648
 649 /* Execute thread */
 650 struct thread *
 651 thread_execute (struct thread_master *m,
 652                 int (*func)(struct thread *),
 653                 void *arg,
 654                 int val)
 655 {
 656   struct thread dummy;
 657
 658   memset (&dummy, 0, sizeof (struct thread));
 659
 660   dummy.type = THREAD_EVENT;
 661   dummy.master = NULL;
 662   dummy.func = func;
 663   dummy.arg = arg;
 664   dummy.u.val = val;
 665   thread_call (&dummy);
 666
 667   return NULL;
 668 }