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