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
30/* Struct timeval's tv_usec one second value.  */
31#define TIMER_SECOND_MICRO 1000000L
32
33static struct timeval
34timeval_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
50static int
51timeval_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
57static unsigned long
58timeval_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
64#ifdef FOX_RIP_DEBUG
65/* List allocation and head/tail print out. */
66static void
67thread_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. */
74void
75thread_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 FOX_RIP_DEBUG */
92
93/* Allocate new thread master.  */
94struct thread_master *
95thread_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.  */
102static void
103thread_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.  */
116static void
117thread_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. */
132static struct thread *
133thread_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. */
149static void
150thread_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. */
160static void
161thread_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. */
176void
177thread_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. */
190static struct thread *
191thread_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.  */
199int
200thread_empty (struct thread_list *list)
201{
202  return  list->head ? 0 : 1;
203}
204
205/* Return remain time in second. */
206unsigned long
207thread_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
219/* Get new thread.  */
220static struct thread *
221thread_get (struct thread_master *m, u_char type,
222	    int (*func) (struct thread *), void *arg)
223{
224  struct thread *thread;
225
226  if (m->unuse.head)
227    thread = thread_trim_head (&m->unuse);
228  else
229    {
230      thread = XCALLOC (MTYPE_THREAD, sizeof (struct thread));
231      m->alloc++;
232    }
233  thread->type = type;
234  thread->master = m;
235  thread->func = func;
236  thread->arg = arg;
237
238  return thread;
239}
240
241/* Add new read thread. */
242struct thread *
243thread_add_read (struct thread_master *m,
244		 int (*func) (struct thread *), void *arg, int fd)
245{
246  struct thread *thread;
247
248  assert (m != NULL);
249
250  if (FD_ISSET (fd, &m->readfd))
251    {
252#ifdef FOX_RIP_DEBUG
253      zlog (NULL, LOG_WARNING, "There is already read fd [%d]", fd);
254#endif /* FOX_RIP_DEBUG */
255      return NULL;
256    }
257
258  thread = thread_get (m, THREAD_READ, func, arg);
259  FD_SET (fd, &m->readfd);
260  thread->u.fd = fd;
261  thread_list_add (&m->read, thread);
262
263  return thread;
264}
265
266/* Add new write thread. */
267struct thread *
268thread_add_write (struct thread_master *m,
269		 int (*func) (struct thread *), void *arg, int fd)
270{
271  struct thread *thread;
272
273  assert (m != NULL);
274
275  if (FD_ISSET (fd, &m->writefd))
276    {
277#ifdef FOX_RIP_DEBUG
278      zlog (NULL, LOG_WARNING, "There is already write fd [%d]", fd);
279#endif
280      return NULL;
281    }
282
283  thread = thread_get (m, THREAD_WRITE, func, arg);
284  FD_SET (fd, &m->writefd);
285  thread->u.fd = fd;
286  thread_list_add (&m->write, thread);
287
288  return thread;
289}
290
291/* Add timer event thread. */
292struct thread *
293thread_add_timer (struct thread_master *m,
294		  int (*func) (struct thread *), void *arg, long timer)
295{
296  struct timeval timer_now;
297  struct thread *thread;
298#ifndef TIMER_NO_SORT
299  struct thread *tt;
300#endif /* TIMER_NO_SORT */
301
302  assert (m != NULL);
303
304  thread = thread_get (m, THREAD_TIMER, func, arg);
305
306  /* Do we need jitter here? */
307  gettimeofday (&timer_now, NULL);
308  timer_now.tv_sec += timer;
309  thread->u.sands = timer_now;
310
311  /* Sort by timeval. */
312#ifdef TIMER_NO_SORT
313  thread_list_add (&m->timer, thread);
314#else
315  for (tt = m->timer.head; tt; tt = tt->next)
316    if (timeval_cmp (thread->u.sands, tt->u.sands) <= 0)
317      break;
318
319  if (tt)
320    thread_list_add_before (&m->timer, tt, thread);
321  else
322    thread_list_add (&m->timer, thread);
323#endif /* TIMER_NO_SORT */
324
325  return thread;
326}
327
328/* Add simple event thread. */
329struct thread *
330thread_add_event (struct thread_master *m,
331		  int (*func) (struct thread *), void *arg, int val)
332{
333  struct thread *thread;
334
335  assert (m != NULL);
336
337  thread = thread_get (m, THREAD_EVENT, func, arg);
338  thread->u.val = val;
339  thread_list_add (&m->event, thread);
340
341  return thread;
342}
343
344/* Cancel thread from scheduler. */
345void
346thread_cancel (struct thread *thread)
347{
348  switch (thread->type)
349    {
350    case THREAD_READ:
351      assert (FD_ISSET (thread->u.fd, &thread->master->readfd));
352      FD_CLR (thread->u.fd, &thread->master->readfd);
353      thread_list_delete (&thread->master->read, thread);
354      break;
355    case THREAD_WRITE:
356      assert (FD_ISSET (thread->u.fd, &thread->master->writefd));
357      FD_CLR (thread->u.fd, &thread->master->writefd);
358      thread_list_delete (&thread->master->write, thread);
359      break;
360    case THREAD_TIMER:
361      thread_list_delete (&thread->master->timer, thread);
362      break;
363    case THREAD_EVENT:
364      thread_list_delete (&thread->master->event, thread);
365      break;
366    case THREAD_READY:
367      thread_list_delete (&thread->master->ready, thread);
368      break;
369    default:
370      break;
371    }
372  thread->type = THREAD_UNUSED;
373  thread_add_unuse (thread->master, thread);
374}
375
376/* Delete all events which has argument value arg. */
377void
378thread_cancel_event (struct thread_master *m, void *arg)
379{
380  struct thread *thread;
381
382  thread = m->event.head;
383  while (thread)
384    {
385      struct thread *t;
386
387      t = thread;
388      thread = t->next;
389
390      if (t->arg == arg)
391	{
392	  thread_list_delete (&m->event, t);
393	  t->type = THREAD_UNUSED;
394	  thread_add_unuse (m, t);
395	}
396    }
397}
398
399#ifdef TIMER_NO_SORT
400struct timeval *
401thread_timer_wait (struct thread_master *m, struct timeval *timer_val)
402{
403  struct timeval timer_now;
404  struct timeval timer_min;
405  struct timeval *timer_wait;
406
407  gettimeofday (&timer_now, NULL);
408
409  timer_wait = NULL;
410  for (thread = m->timer.head; thread; thread = thread->next)
411    {
412      if (! timer_wait)
413	timer_wait = &thread->u.sands;
414      else if (timeval_cmp (thread->u.sands, *timer_wait) < 0)
415	timer_wait = &thread->u.sands;
416    }
417
418  if (m->timer.head)
419    {
420      timer_min = *timer_wait;
421      timer_min = timeval_subtract (timer_min, timer_now);
422      if (timer_min.tv_sec < 0)
423	{
424	  timer_min.tv_sec = 0;
425	  timer_min.tv_usec = 10;
426	}
427      timer_wait = &timer_min;
428    }
429  else
430    timer_wait = NULL;
431
432  if (timer_wait)
433    {
434      *timer_val = timer_wait;
435      return timer_val;
436    }
437  return NULL;
438}
439#else /* ! TIMER_NO_SORT */
440struct timeval *
441thread_timer_wait (struct thread_master *m, struct timeval *timer_val)
442{
443  struct timeval timer_now;
444  struct timeval timer_min;
445
446  if (m->timer.head)
447    {
448      gettimeofday (&timer_now, NULL);
449      timer_min = m->timer.head->u.sands;
450      timer_min = timeval_subtract (timer_min, timer_now);
451      if (timer_min.tv_sec < 0)
452	{
453	  timer_min.tv_sec = 0;
454	  timer_min.tv_usec = 10;
455	}
456      *timer_val = timer_min;
457      return timer_val;
458    }
459  return NULL;
460}
461#endif /* TIMER_NO_SORT */
462
463struct thread *
464thread_run (struct thread_master *m, struct thread *thread,
465	    struct thread *fetch)
466{
467  *fetch = *thread;
468  thread->type = THREAD_UNUSED;
469  thread_add_unuse (m, thread);
470  return fetch;
471}
472
473int
474thread_process_fd (struct thread_master *m, struct thread_list *list,
475		   fd_set *fdset, fd_set *mfdset)
476{
477  struct thread *thread;
478  struct thread *next;
479  int ready = 0;
480
481  for (thread = list->head; thread; thread = next)
482    {
483      next = thread->next;
484
485      if (FD_ISSET (THREAD_FD (thread), fdset))
486	{
487	  assert (FD_ISSET (THREAD_FD (thread), mfdset));
488	  FD_CLR(THREAD_FD (thread), mfdset);
489	  thread_list_delete (list, thread);
490	  thread_list_add (&m->ready, thread);
491	  thread->type = THREAD_READY;
492	  ready++;
493	}
494    }
495  return ready;
496}
497
498/* Fetch next ready thread. */
499struct thread *
500thread_fetch (struct thread_master *m, struct thread *fetch)
501{
502  int num;
503  int ready;
504  struct thread *thread;
505  fd_set readfd;
506  fd_set writefd;
507  fd_set exceptfd;
508  struct timeval timer_now;
509  struct timeval timer_val;
510  struct timeval *timer_wait;
511  struct timeval timer_nowait;
512
513  timer_nowait.tv_sec = 0;
514  timer_nowait.tv_usec = 0;
515
516  while (1)
517    {
518      /* Normal event is the highest priority.  */
519      if ((thread = thread_trim_head (&m->event)) != NULL)
520	return thread_run (m, thread, fetch);
521
522      /* Execute timer.  */
523      gettimeofday (&timer_now, NULL);
524
525      for (thread = m->timer.head; thread; thread = thread->next)
526	if (timeval_cmp (timer_now, thread->u.sands) >= 0)
527	  {
528	    thread_list_delete (&m->timer, thread);
529	    return thread_run (m, thread, fetch);
530	  }
531
532      /* If there are any ready threads, process top of them.  */
533      if ((thread = thread_trim_head (&m->ready)) != NULL)
534	return thread_run (m, thread, fetch);
535
536      /* Structure copy.  */
537      readfd = m->readfd;
538      writefd = m->writefd;
539      exceptfd = m->exceptfd;
540
541      /* Calculate select wait timer. */
542      timer_wait = thread_timer_wait (m, &timer_val);
543
544      num = select (FD_SETSIZE, &readfd, &writefd, &exceptfd, timer_wait);
545
546      if (num == 0)
547	continue;
548
549      if (num < 0)
550	{
551	  if (errno == EINTR)
552	    continue;
553#ifdef FOX_RIP_DEBUG
554	  zlog_warn ("select() error: %s", strerror (errno));
555#endif /* FOX_RIP_DEBUG */
556	  return NULL;
557	}
558
559      /* Normal priority read thead. */
560      ready = thread_process_fd (m, &m->read, &readfd, &m->readfd);
561
562      /* Write thead. */
563      ready = thread_process_fd (m, &m->write, &writefd, &m->writefd);
564
565      if ((thread = thread_trim_head (&m->ready)) != NULL)
566	return thread_run (m, thread, fetch);
567    }
568}
569
570static unsigned long
571thread_consumed_time (RUSAGE_T *now, RUSAGE_T *start)
572{
573  unsigned long thread_time;
574
575#ifdef HAVE_RUSAGE
576  /* This is 'user + sys' time.  */
577  thread_time = timeval_elapsed (now->ru_utime, start->ru_utime);
578  thread_time += timeval_elapsed (now->ru_stime, start->ru_stime);
579#else
580  /* When rusage is not available, simple elapsed time is used.  */
581  thread_time = timeval_elapsed (*now, *start);
582#endif /* HAVE_RUSAGE */
583
584  return thread_time;
585}
586
587/* We should aim to yield after THREAD_YIELD_TIME_SLOT
588   milliseconds.  */
589int
590thread_should_yield (struct thread *thread)
591{
592  RUSAGE_T ru;
593
594  GETRUSAGE (&ru);
595
596  if (thread_consumed_time (&ru, &thread->ru) > THREAD_YIELD_TIME_SLOT)
597    return 1;
598  else
599    return 0;
600}
601
602/* We check thread consumed time. If the system has getrusage, we'll
603   use that to get indepth stats on the performance of the thread.  If
604   not - we'll use gettimeofday for some guestimation.  */
605void
606thread_call (struct thread *thread)
607{
608  unsigned long thread_time;
609  RUSAGE_T ru;
610
611  GETRUSAGE (&thread->ru);
612
613  (*thread->func) (thread);
614
615  GETRUSAGE (&ru);
616
617  thread_time = thread_consumed_time (&ru, &thread->ru);
618
619#ifdef THREAD_CONSUMED_TIME_CHECK
620  if (thread_time > 200000L)
621    {
622      /*
623       * We have a CPU Hog on our hands.
624       * Whinge about it now, so we're aware this is yet another task
625       * to fix.
626       */
627#ifdef FOX_RIP_DEBUG
628      zlog_err ("CPU HOG task %lx ran for %ldms",
629                /* FIXME: report the name of the function somehow */
630		(unsigned long) thread->func,
631		thread_time / 1000L);
632#endif /* FOX_RIP_DEBUG */
633    }
634#endif /* THREAD_CONSUMED_TIME_CHECK */
635}
636
637/* Execute thread */
638struct thread *
639thread_execute (struct thread_master *m,
640                int (*func)(struct thread *),
641                void *arg,
642                int val)
643{
644  struct thread dummy;
645
646  memset (&dummy, 0, sizeof (struct thread));
647
648  dummy.type = THREAD_EVENT;
649  dummy.master = NULL;
650  dummy.func = func;
651  dummy.arg = arg;
652  dummy.u.val = val;
653  thread_call (&dummy);
654
655  return NULL;
656}
657