zephyr/server/timer.c

   1 /* This file is part of the Project Athena Zephyr Notification System.
   2  * It contains functions for managing multiple timeouts.
   3  *
   4  *      Created by:     John T. Kohl
   5  *      Derived from timer_manager_ by Ken Raeburn
   6  *
   7  *      $Id$
   8  *
   9  */
  10
  11 #include "zserver.h"
  12
  13 #ifndef SABER
  14 #ifndef lint
  15 static const char rcsid[] =
  16 "$Id$";
  17 #endif /* lint */
  18 #endif /* SABER */
  19
  20 /*
  21  * timer_manager_ -- routines for handling timers in login_shell
  22  * (and elsewhere)
  23  *
  24  * Copyright 1986 Student Information Processing Board,
  25  * Massachusetts Institute of Technology
  26  *
  27  * written by Ken Raeburn
  28
  29  Permission to use, copy, modify, and distribute this
  30  software and its documentation for any purpose and without
  31  fee is hereby granted, provided that the above copyright
  32  notice appear in all copies and that both that copyright
  33  notice and this permission notice appear in supporting
  34  documentation, and that the name of M.I.T. and the Student
  35  Information Processing Board not be used in
  36  advertising or publicity pertaining to distribution of the
  37  software without specific, written prior permission.
  38  M.I.T. and the Student Information Processing Board
  39  make no representations about the suitability of
  40  this software for any purpose.  It is provided "as is"
  41  without express or implied warranty.
  42
  43  */
  44
  45
  46 /*
  47  * External functions:
  48  *
  49  * Timer *timer_set_rel (time_rel, proc, arg)
  50  *      long time_rel;
  51  *      void (*proc)();
  52  *      caddr_t arg;
  53  * Timer *timer_set_abs (time_abs, proc, arg)
  54  *      long time_abs;
  55  *      void (*proc)();
  56  *      caddr_t arg;
  57  *
  58  * void timer_reset(tmr)
  59  *      Timer *tmr;
  60  *
  61  * void timer_process()
  62  *
  63  */
  64
  65 /* DELTA is just an offset to keep the size a bit less than a power
  66  * of two.  It's measured in pointers, so it's 32 bytes on most
  67  * systems. */
  68 #define DELTA 8
  69 #define INITIAL_HEAP_SIZE (1024 - DELTA)
  70
  71 /* We have three operations which we need to be able to perform
  72  * quickly: adding a timer, deleting a timer given a pointer to
  73  * it, and determining which timer will be the next to go off.  A
  74  * heap is an ideal data structure for these purposes, so we use
  75  * one.  The heap is an array of pointers to timers, and each timer
  76  * knows the position of its pointer in the heap.
  77  *
  78  * Okay, what is the heap, exactly?  It's a data structure,
  79  * represented as an array, with the invariant condition that
  80  * the timeout of heap[i] is less than or equal to the timeout of
  81  * heap[i * 2 + 1] and heap[i * 2 + 2] (assuming i * 2 + 1 and
  82  * i * 2 + 2 are valid * indices).  An obvious consequence of this
  83  * is that heap[0] has the lowest timer value, so finding the first
  84  * timer to go off is easy.  We say that an index i has "children"
  85  * i * 2 + 1 and i * 2 + 1, and the "parent" (i - 1) / 2.
  86  *
  87  * To add a timer to the heap, we start by adding it to the end, and
  88  * then keep swapping it with its parent until it has a parent with
  89  * a timer value less than its value.  With a little bit of thought,
  90  * you can see that this preserves the heap property on all indices
  91  * of the array.
  92  *
  93  * To delete a timer at position i from the heap, we discard it and
  94  * fill in its position with the last timer in the heap.  In order
  95  * to restore the heap, we have to consider two cases: the timer
  96  * value at i is less than that of its parent, or the timer value at
  97  * i is greater than that of one of its children.  In the first case,
  98  * we propagate the timer at i up the tree, swapping it with its
  99  * parent, until the heap is restored; in the second case, we
 100  * propagate the timer down the tree, swapping it with its least
 101  * child, until the heap is restored. */
 102
 103 /* In order to ensure that the back pointers from timers are consistent
 104  * with the heap pointers, all heap assignments should be done with the
 105  * HEAP_ASSIGN() macro, which sets the back pointer and updates the
 106  * heap at the same time. */
 107 #define PARENT(i) (((i) - 1) / 2)
 108 #define CHILD1(i) ((i) * 2 + 1)
 109 #define CHILD2(i) ((i) * 2 + 2)
 110 #define TIME(i) (heap[i]->abstime)
 111 #define HEAP_ASSIGN(pos, tmr) ((heap[pos] = (tmr))->heap_pos = (pos))
 112
 113 static Timer **heap;
 114 static int num_timers = 0;
 115 static int heap_size = 0;
 116
 117 static void timer_botch __P((void*));
 118 static Timer *add_timer __P((Timer *));
 119
 120 Timer *timer_set_rel(time_rel, proc, arg)
 121     long time_rel;
 122     void (*proc) __P((void *));
 123     void *arg;
 124 {
 125     Timer *new_t;
 126
 127     new_t = (Timer *) malloc(sizeof(*new_t));
 128     if (new_t == NULL)
 129         return(NULL);
 130     new_t->abstime = time_rel + NOW;
 131     new_t->func = proc;
 132     new_t->arg = arg;
 133     return add_timer(new_t);
 134 }
 135
 136 void
 137 timer_reset(tmr)
 138     Timer *tmr;
 139 {
 140     int pos, min;
 141
 142     /* Free the timer, saving its heap position. */
 143     pos = tmr->heap_pos;
 144     free(tmr);
 145
 146     if (pos != num_timers - 1) {
 147         /* Replace the timer with the last timer in the heap and
 148          * restore the heap, propagating the timer either up or
 149          * down, depending on which way it violates the heap
 150          * property to insert the last timer in place of the
 151          * deleted timer. */
 152         if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
 153             do {
 154                 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 155                 pos = PARENT(pos);
 156             } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
 157             HEAP_ASSIGN(pos, heap[num_timers - 1]);
 158         } else {
 159             while (CHILD2(pos) < num_timers) {
 160                 min = num_timers - 1;
 161                 if (TIME(CHILD1(pos)) < TIME(min))
 162                     min = CHILD1(pos);
 163                 if (TIME(CHILD2(pos)) < TIME(min))
 164                     min = CHILD2(pos);
 165                 HEAP_ASSIGN(pos, heap[min]);
 166                 pos = min;
 167             }
 168             if (pos != num_timers - 1)
 169                 HEAP_ASSIGN(pos, heap[num_timers - 1]);
 170         }
 171     }
 172     num_timers--;
 173 }
 174
 175
 176 #define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))
 177
 178 static Timer *
 179 add_timer(new)
 180     Timer *new;
 181 {
 182     int pos;
 183
 184     /* Create or resize the heap as necessary. */
 185     if (heap_size == 0) {
 186         heap_size = INITIAL_HEAP_SIZE;
 187         heap = (Timer **) malloc(heap_size * sizeof(Timer *));
 188     } else if (num_timers >= heap_size) {
 189         heap_size = heap_size * 2 + DELTA;
 190         heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
 191     }
 192     if (!heap) {
 193         free(new);
 194         return NULL;
 195     }
 196
 197     /* Insert the Timer *into the heap. */
 198     pos = num_timers;
 199     while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
 200         HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 201         pos = PARENT(pos);
 202     }
 203     HEAP_ASSIGN(pos, new);
 204     num_timers++;
 205
 206     return new;
 207 }
 208
 209 void
 210 timer_process()
 211 {
 212     Timer *t;
 213     timer_proc func;
 214     void *arg;
 215     int valid = 0;
 216
 217     if (num_timers == 0 || heap[0]->abstime > NOW)
 218         return;
 219
 220     /* Remove the first timer from the heap, remembering its
 221      * function and argument. */
 222     t = heap[0];
 223     func = t->func;
 224     arg = t->arg;
 225     t->func = timer_botch;
 226     t->arg = NULL;
 227     timer_reset(t);
 228
 229     /* Run the function. */
 230     func(arg);
 231 }
 232
 233 struct timeval *
 234 timer_timeout(tvbuf)
 235     struct timeval *tvbuf;
 236 {
 237     if (num_timers > 0) {
 238         tvbuf->tv_sec = heap[0]->abstime - NOW;
 239         if (tvbuf->tv_sec < 0)
 240             tvbuf->tv_sec = 0;
 241         tvbuf->tv_usec = 0;
 242         return tvbuf;
 243     } else {
 244         return NULL;
 245     }
 246 }
 247
 248 static void
 249 timer_botch(arg)
 250     void *arg;
 251 {
 252     syslog(LOG_CRIT, "timer botch\n");
 253     abort();
 254 }
 255