Back to index

glibc  2.9
timer_routines.c
Go to the documentation of this file.
00001 /* Helper code for POSIX timer implementation on NPTL.
00002    Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Contributed by Kaz Kylheku <kaz@ashi.footprints.net>.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public License as
00008    published by the Free Software Foundation; either version 2.1 of the
00009    License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; see the file COPYING.LIB.  If not,
00018    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00019    Boston, MA 02111-1307, USA.  */
00020 
00021 #include <assert.h>
00022 #include <errno.h>
00023 #include <pthread.h>
00024 #include <stddef.h>
00025 #include <stdlib.h>
00026 #include <string.h>
00027 #include <sysdep.h>
00028 #include <time.h>
00029 #include <unistd.h>
00030 #include <sys/syscall.h>
00031 
00032 #include "posix-timer.h"
00033 #include <pthreadP.h>
00034 
00035 
00036 /* Number of threads used.  */
00037 #define THREAD_MAXNODES     16
00038 
00039 /* Array containing the descriptors for the used threads.  */
00040 static struct thread_node thread_array[THREAD_MAXNODES];
00041 
00042 /* Static array with the structures for all the timers.  */
00043 struct timer_node __timer_array[TIMER_MAX];
00044 
00045 /* Global lock to protect operation on the lists.  */
00046 pthread_mutex_t __timer_mutex = PTHREAD_MUTEX_INITIALIZER;
00047 
00048 /* Variable to protext initialization.  */
00049 pthread_once_t __timer_init_once_control = PTHREAD_ONCE_INIT;
00050 
00051 /* Nonzero if initialization of timer implementation failed.  */
00052 int __timer_init_failed;
00053 
00054 /* Node for the thread used to deliver signals.  */
00055 struct thread_node __timer_signal_thread_rclk;
00056 
00057 /* Lists to keep free and used timers and threads.  */
00058 struct list_links timer_free_list;
00059 struct list_links thread_free_list;
00060 struct list_links thread_active_list;
00061 
00062 
00063 #ifdef __NR_rt_sigqueueinfo
00064 extern int __syscall_rt_sigqueueinfo (int, int, siginfo_t *);
00065 #endif
00066 
00067 
00068 /* List handling functions.  */
00069 static inline void
00070 list_init (struct list_links *list)
00071 {
00072   list->next = list->prev = list;
00073 }
00074 
00075 static inline void
00076 list_append (struct list_links *list, struct list_links *newp)
00077 {
00078   newp->prev = list->prev;
00079   newp->next = list;
00080   list->prev->next = newp;
00081   list->prev = newp;
00082 }
00083 
00084 static inline void
00085 list_insbefore (struct list_links *list, struct list_links *newp)
00086 {
00087   list_append (list, newp);
00088 }
00089 
00090 /*
00091  * Like list_unlink_ip, except that calling it on a node that
00092  * is already unlinked is disastrous rather than a noop.
00093  */
00094 
00095 static inline void
00096 list_unlink (struct list_links *list)
00097 {
00098   struct list_links *lnext = list->next, *lprev = list->prev;
00099 
00100   lnext->prev = lprev;
00101   lprev->next = lnext;
00102 }
00103 
00104 static inline struct list_links *
00105 list_first (struct list_links *list)
00106 {
00107   return list->next;
00108 }
00109 
00110 static inline struct list_links *
00111 list_null (struct list_links *list)
00112 {
00113   return list;
00114 }
00115 
00116 static inline struct list_links *
00117 list_next (struct list_links *list)
00118 {
00119   return list->next;
00120 }
00121 
00122 static inline int
00123 list_isempty (struct list_links *list)
00124 {
00125   return list->next == list;
00126 }
00127 
00128 
00129 /* Functions build on top of the list functions.  */
00130 static inline struct thread_node *
00131 thread_links2ptr (struct list_links *list)
00132 {
00133   return (struct thread_node *) ((char *) list
00134                              - offsetof (struct thread_node, links));
00135 }
00136 
00137 static inline struct timer_node *
00138 timer_links2ptr (struct list_links *list)
00139 {
00140   return (struct timer_node *) ((char *) list
00141                             - offsetof (struct timer_node, links));
00142 }
00143 
00144 
00145 /* Initialize a newly allocated thread structure.  */
00146 static void
00147 thread_init (struct thread_node *thread, const pthread_attr_t *attr, clockid_t clock_id)
00148 {
00149   if (attr != NULL)
00150     thread->attr = *attr;
00151   else
00152     {
00153       pthread_attr_init (&thread->attr);
00154       pthread_attr_setdetachstate (&thread->attr, PTHREAD_CREATE_DETACHED);
00155     }
00156 
00157   thread->exists = 0;
00158   list_init (&thread->timer_queue);
00159   pthread_cond_init (&thread->cond, 0);
00160   thread->current_timer = 0;
00161   thread->captured = pthread_self ();
00162   thread->clock_id = clock_id;
00163 }
00164 
00165 
00166 /* Initialize the global lists, and acquire global resources.  Error
00167    reporting is done by storing a non-zero value to the global variable
00168    timer_init_failed.  */
00169 static void
00170 init_module (void)
00171 {
00172   int i;
00173 
00174   list_init (&timer_free_list);
00175   list_init (&thread_free_list);
00176   list_init (&thread_active_list);
00177 
00178   for (i = 0; i < TIMER_MAX; ++i)
00179     {
00180       list_append (&timer_free_list, &__timer_array[i].links);
00181       __timer_array[i].inuse = TIMER_FREE;
00182     }
00183 
00184   for (i = 0; i < THREAD_MAXNODES; ++i)
00185     list_append (&thread_free_list, &thread_array[i].links);
00186 
00187   thread_init (&__timer_signal_thread_rclk, 0, CLOCK_REALTIME);
00188 }
00189 
00190 
00191 /* This is a handler executed in a child process after a fork()
00192    occurs.  It reinitializes the module, resetting all of the data
00193    structures to their initial state.  The mutex is initialized in
00194    case it was locked in the parent process.  */
00195 static void
00196 reinit_after_fork (void)
00197 {
00198   init_module ();
00199   pthread_mutex_init (&__timer_mutex, 0);
00200 }
00201 
00202 
00203 /* Called once form pthread_once in timer_init. This initializes the
00204    module and ensures that reinit_after_fork will be executed in any
00205    child process.  */
00206 void
00207 __timer_init_once (void)
00208 {
00209   init_module ();
00210   pthread_atfork (0, 0, reinit_after_fork);
00211 }
00212 
00213 
00214 /* Deinitialize a thread that is about to be deallocated.  */
00215 static void
00216 thread_deinit (struct thread_node *thread)
00217 {
00218   assert (list_isempty (&thread->timer_queue));
00219   pthread_cond_destroy (&thread->cond);
00220 }
00221 
00222 
00223 /* Allocate a thread structure from the global free list.  Global
00224    mutex lock must be held by caller.  The thread is moved to
00225    the active list. */
00226 struct thread_node *
00227 __timer_thread_alloc (const pthread_attr_t *desired_attr, clockid_t clock_id)
00228 {
00229   struct list_links *node = list_first (&thread_free_list);
00230 
00231   if (node != list_null (&thread_free_list))
00232     {
00233       struct thread_node *thread = thread_links2ptr (node);
00234       list_unlink (node);
00235       thread_init (thread, desired_attr, clock_id);
00236       list_append (&thread_active_list, node);
00237       return thread;
00238     }
00239 
00240   return 0;
00241 }
00242 
00243 
00244 /* Return a thread structure to the global free list.  Global lock
00245    must be held by caller.  */
00246 void
00247 __timer_thread_dealloc (struct thread_node *thread)
00248 {
00249   thread_deinit (thread);
00250   list_unlink (&thread->links);
00251   list_append (&thread_free_list, &thread->links);
00252 }
00253 
00254 
00255 /* Each of our threads which terminates executes this cleanup
00256    handler. We never terminate threads ourselves; if a thread gets here
00257    it means that the evil application has killed it.  If the thread has
00258    timers, these require servicing and so we must hire a replacement
00259    thread right away.  We must also unblock another thread that may
00260    have been waiting for this thread to finish servicing a timer (see
00261    timer_delete()).  */
00262 
00263 static void
00264 thread_cleanup (void *val)
00265 {
00266   if (val != NULL)
00267     {
00268       struct thread_node *thread = val;
00269 
00270       /* How did the signal thread get killed?  */
00271       assert (thread != &__timer_signal_thread_rclk);
00272 
00273       pthread_mutex_lock (&__timer_mutex);
00274 
00275       thread->exists = 0;
00276 
00277       /* We are no longer processing a timer event.  */
00278       thread->current_timer = 0;
00279 
00280       if (list_isempty (&thread->timer_queue))
00281        __timer_thread_dealloc (thread);
00282       else
00283        (void) __timer_thread_start (thread);
00284 
00285       pthread_mutex_unlock (&__timer_mutex);
00286 
00287       /* Unblock potentially blocked timer_delete().  */
00288       pthread_cond_broadcast (&thread->cond);
00289     }
00290 }
00291 
00292 
00293 /* Handle a timer which is supposed to go off now.  */
00294 static void
00295 thread_expire_timer (struct thread_node *self, struct timer_node *timer)
00296 {
00297   self->current_timer = timer; /* Lets timer_delete know timer is running. */
00298 
00299   pthread_mutex_unlock (&__timer_mutex);
00300 
00301   switch (__builtin_expect (timer->event.sigev_notify, SIGEV_SIGNAL))
00302     {
00303     case SIGEV_NONE:
00304       break;
00305 
00306     case SIGEV_SIGNAL:
00307 #ifdef __NR_rt_sigqueueinfo
00308       {
00309        siginfo_t info;
00310 
00311        /* First, clear the siginfo_t structure, so that we don't pass our
00312           stack content to other tasks.  */
00313        memset (&info, 0, sizeof (siginfo_t));
00314        /* We must pass the information about the data in a siginfo_t
00315            value.  */
00316        info.si_signo = timer->event.sigev_signo;
00317        info.si_code = SI_TIMER;
00318        info.si_pid = timer->creator_pid;
00319        info.si_uid = getuid ();
00320        info.si_value = timer->event.sigev_value;
00321 
00322        INLINE_SYSCALL (rt_sigqueueinfo, 3, info.si_pid, info.si_signo, &info);
00323       }
00324 #else
00325       if (pthread_kill (self->captured, timer->event.sigev_signo) != 0)
00326        {
00327          if (pthread_kill (self->id, timer->event.sigev_signo) != 0)
00328            abort ();
00329         }
00330 #endif
00331       break;
00332 
00333     case SIGEV_THREAD:
00334       timer->event.sigev_notify_function (timer->event.sigev_value);
00335       break;
00336 
00337     default:
00338       assert (! "unknown event");
00339       break;
00340     }
00341 
00342   pthread_mutex_lock (&__timer_mutex);
00343 
00344   self->current_timer = 0;
00345 
00346   pthread_cond_broadcast (&self->cond);
00347 }
00348 
00349 
00350 /* Thread function; executed by each timer thread. The job of this
00351    function is to wait on the thread's timer queue and expire the
00352    timers in chronological order as close to their scheduled time as
00353    possible.  */
00354 static void
00355 __attribute__ ((noreturn))
00356 thread_func (void *arg)
00357 {
00358   struct thread_node *self = arg;
00359 
00360   /* Register cleanup handler, in case rogue application terminates
00361      this thread.  (This cannot happen to __timer_signal_thread, which
00362      doesn't invoke application callbacks). */
00363 
00364   pthread_cleanup_push (thread_cleanup, self);
00365 
00366   pthread_mutex_lock (&__timer_mutex);
00367 
00368   while (1)
00369     {
00370       struct list_links *first;
00371       struct timer_node *timer = NULL;
00372 
00373       /* While the timer queue is not empty, inspect the first node.  */
00374       first = list_first (&self->timer_queue);
00375       if (first != list_null (&self->timer_queue))
00376        {
00377          struct timespec now;
00378 
00379          timer = timer_links2ptr (first);
00380 
00381          /* This assumes that the elements of the list of one thread
00382             are all for the same clock.  */
00383          clock_gettime (timer->clock, &now);
00384 
00385          while (1)
00386            {
00387              /* If the timer is due or overdue, remove it from the queue.
00388                If it's a periodic timer, re-compute its new time and
00389                requeue it.  Either way, perform the timer expiry. */
00390              if (timespec_compare (&now, &timer->expirytime) < 0)
00391               break;
00392 
00393              list_unlink_ip (first);
00394 
00395              if (__builtin_expect (timer->value.it_interval.tv_sec, 0) != 0
00396                 || timer->value.it_interval.tv_nsec != 0)
00397               {
00398                 timer->overrun_count = 0;
00399                 timespec_add (&timer->expirytime, &timer->expirytime,
00400                             &timer->value.it_interval);
00401                 while (timespec_compare (&timer->expirytime, &now) < 0)
00402                   {
00403                     timespec_add (&timer->expirytime, &timer->expirytime,
00404                                 &timer->value.it_interval);
00405                     if (timer->overrun_count < DELAYTIMER_MAX)
00406                      ++timer->overrun_count;
00407                   }
00408                 __timer_thread_queue_timer (self, timer);
00409               }
00410 
00411              thread_expire_timer (self, timer);
00412 
00413              first = list_first (&self->timer_queue);
00414              if (first == list_null (&self->timer_queue))
00415               break;
00416 
00417              timer = timer_links2ptr (first);
00418            }
00419        }
00420 
00421       /* If the queue is not empty, wait until the expiry time of the
00422         first node.  Otherwise wait indefinitely.  Insertions at the
00423         head of the queue must wake up the thread by broadcasting
00424         this condition variable.  */
00425       if (timer != NULL)
00426        pthread_cond_timedwait (&self->cond, &__timer_mutex,
00427                             &timer->expirytime);
00428       else
00429        pthread_cond_wait (&self->cond, &__timer_mutex);
00430     }
00431   /* This macro will never be executed since the while loop loops
00432      forever - but we have to add it for proper nesting.  */
00433   pthread_cleanup_pop (1);
00434 }
00435 
00436 
00437 /* Enqueue a timer in wakeup order in the thread's timer queue.
00438    Returns 1 if the timer was inserted at the head of the queue,
00439    causing the queue's next wakeup time to change. */
00440 
00441 int
00442 __timer_thread_queue_timer (struct thread_node *thread,
00443                          struct timer_node *insert)
00444 {
00445   struct list_links *iter;
00446   int athead = 1;
00447 
00448   for (iter = list_first (&thread->timer_queue);
00449        iter != list_null (&thread->timer_queue);
00450         iter = list_next (iter))
00451     {
00452       struct timer_node *timer = timer_links2ptr (iter);
00453 
00454       if (timespec_compare (&insert->expirytime, &timer->expirytime) < 0)
00455          break;
00456       athead = 0;
00457     }
00458 
00459   list_insbefore (iter, &insert->links);
00460   return athead;
00461 }
00462 
00463 
00464 /* Start a thread and associate it with the given thread node.  Global
00465    lock must be held by caller.  */
00466 int
00467 __timer_thread_start (struct thread_node *thread)
00468 {
00469   int retval = 1;
00470 
00471   assert (!thread->exists);
00472   thread->exists = 1;
00473 
00474   if (pthread_create (&thread->id, &thread->attr,
00475                     (void *(*) (void *)) thread_func, thread) != 0)
00476     {
00477       thread->exists = 0;
00478       retval = -1;
00479     }
00480 
00481   return retval;
00482 }
00483 
00484 
00485 void
00486 __timer_thread_wakeup (struct thread_node *thread)
00487 {
00488   pthread_cond_broadcast (&thread->cond);
00489 }
00490 
00491 
00492 /* Compare two pthread_attr_t thread attributes for exact equality.
00493    Returns 1 if they are equal, otherwise zero if they are not equal
00494    or contain illegal values.  This version is NPTL-specific for
00495    performance reason.  One could use the access functions to get the
00496    values of all the fields of the attribute structure.  */
00497 static int
00498 thread_attr_compare (const pthread_attr_t *left, const pthread_attr_t *right)
00499 {
00500   struct pthread_attr *ileft = (struct pthread_attr *) left;
00501   struct pthread_attr *iright = (struct pthread_attr *) right;
00502 
00503   return (ileft->flags == iright->flags
00504          && ileft->schedpolicy == iright->schedpolicy
00505          && (ileft->schedparam.sched_priority
00506              == iright->schedparam.sched_priority)
00507          && ileft->guardsize == iright->guardsize
00508          && ileft->stackaddr == iright->stackaddr
00509          && ileft->stacksize == iright->stacksize
00510          && ((ileft->cpuset == NULL && iright->cpuset == NULL)
00511              || (ileft->cpuset != NULL && iright->cpuset != NULL
00512                 && ileft->cpusetsize == iright->cpusetsize
00513                 && memcmp (ileft->cpuset, iright->cpuset,
00514                           ileft->cpusetsize) == 0)));
00515 }
00516 
00517 
00518 /* Search the list of active threads and find one which has matching
00519    attributes.  Global mutex lock must be held by caller.  */
00520 struct thread_node *
00521 __timer_thread_find_matching (const pthread_attr_t *desired_attr,
00522                            clockid_t desired_clock_id)
00523 {
00524   struct list_links *iter = list_first (&thread_active_list);
00525 
00526   while (iter != list_null (&thread_active_list))
00527     {
00528       struct thread_node *candidate = thread_links2ptr (iter);
00529 
00530       if (thread_attr_compare (desired_attr, &candidate->attr)
00531          && desired_clock_id == candidate->clock_id)
00532        return candidate;
00533 
00534       iter = list_next (iter);
00535     }
00536 
00537   return NULL;
00538 }
00539 
00540 
00541 /* Grab a free timer structure from the global free list.  The global
00542    lock must be held by the caller.  */
00543 struct timer_node *
00544 __timer_alloc (void)
00545 {
00546   struct list_links *node = list_first (&timer_free_list);
00547 
00548   if (node != list_null (&timer_free_list))
00549     {
00550       struct timer_node *timer = timer_links2ptr (node);
00551       list_unlink_ip (node);
00552       timer->inuse = TIMER_INUSE;
00553       timer->refcount = 1;
00554       return timer;
00555     }
00556 
00557   return NULL;
00558 }
00559 
00560 
00561 /* Return a timer structure to the global free list.  The global lock
00562    must be held by the caller.  */
00563 void
00564 __timer_dealloc (struct timer_node *timer)
00565 {
00566   assert (timer->refcount == 0);
00567   timer->thread = NULL;     /* Break association between timer and thread.  */
00568   timer->inuse = TIMER_FREE;
00569   list_append (&timer_free_list, &timer->links);
00570 }
00571 
00572 
00573 /* Thread cancellation handler which unlocks a mutex.  */
00574 void
00575 __timer_mutex_cancel_handler (void *arg)
00576 {
00577   pthread_mutex_unlock (arg);
00578 }