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