summaryrefslogtreecommitdiff
path: root/server/timer.c
blob: 932c819bb4f6a0c150baf99ece7f5e101d95249a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
/* This file is part of the Project Athena Zephyr Notification System.
 * It contains functions for managing multiple timeouts.
 *
 *      Created by:     John T. Kohl
 *      Derived from timer_manager_ by Ken Raeburn
 *
 *      $Id$
 *
 */

#include "zserver.h"

#ifndef SABER
#ifndef lint
static const char rcsid[] =
"$Id$";
#endif /* lint */
#endif /* SABER */

/*
 * timer_manager_ -- routines for handling timers in login_shell
 * (and elsewhere)
 *
 * Copyright 1986 Student Information Processing Board,
 * Massachusetts Institute of Technology
 *
 * written by Ken Raeburn
 
 Permission to use, copy, modify, and distribute this
 software and its documentation for any purpose and without
 fee is hereby granted, provided that the above copyright
 notice appear in all copies and that both that copyright
 notice and this permission notice appear in supporting
 documentation, and that the name of M.I.T. and the Student
 Information Processing Board not be used in
 advertising or publicity pertaining to distribution of the
 software without specific, written prior permission.
 M.I.T. and the Student Information Processing Board
 make no representations about the suitability of
 this software for any purpose.  It is provided "as is"
 without express or implied warranty.
 
 */


/*
 * External functions:
 *
 * Timer *timer_set_rel (time_rel, proc, arg)
 *      long time_rel;
 *      void (*proc)();
 *      void *arg;
 * Timer *timer_set_abs (time_abs, proc, arg)
 *      long time_abs;
 *      void (*proc)();
 *      void *arg;
 *
 * void timer_reset(tmr)
 *      Timer *tmr;
 *
 * void timer_process()
 *
 */

/* DELTA is just an offset to keep the size a bit less than a power 
 * of two.  It's measured in pointers, so it's 32 bytes on most
 * systems. */
#define DELTA 8
#define INITIAL_HEAP_SIZE (1024 - DELTA)

/* We have three operations which we need to be able to perform
 * quickly: adding a timer, deleting a timer given a pointer to
 * it, and determining which timer will be the next to go off.  A
 * heap is an ideal data structure for these purposes, so we use
 * one.  The heap is an array of pointers to timers, and each timer
 * knows the position of its pointer in the heap.
 *
 * Okay, what is the heap, exactly?  It's a data structure,
 * represented as an array, with the invariant condition that
 * the timeout of heap[i] is less than or equal to the timeout of
 * heap[i * 2 + 1] and heap[i * 2 + 2] (assuming i * 2 + 1 and
 * i * 2 + 2 are valid * indices).  An obvious consequence of this
 * is that heap[0] has the lowest timer value, so finding the first
 * timer to go off is easy.  We say that an index i has "children"
 * i * 2 + 1 and i * 2 + 1, and the "parent" (i - 1) / 2.
 *
 * To add a timer to the heap, we start by adding it to the end, and
 * then keep swapping it with its parent until it has a parent with
 * a timer value less than its value.  With a little bit of thought,
 * you can see that this preserves the heap property on all indices
 * of the array.
 *
 * To delete a timer at position i from the heap, we discard it and
 * fill in its position with the last timer in the heap.  In order
 * to restore the heap, we have to consider two cases: the timer
 * value at i is less than that of its parent, or the timer value at
 * i is greater than that of one of its children.  In the first case,
 * we propagate the timer at i up the tree, swapping it with its
 * parent, until the heap is restored; in the second case, we
 * propagate the timer down the tree, swapping it with its least
 * child, until the heap is restored. */

/* In order to ensure that the back pointers from timers are consistent
 * with the heap pointers, all heap assignments should be done with the
 * HEAP_ASSIGN() macro, which sets the back pointer and updates the
 * heap at the same time. */
#define PARENT(i) (((i) - 1) / 2)
#define CHILD1(i) ((i) * 2 + 1)
#define CHILD2(i) ((i) * 2 + 2)
#define TIME(i) (heap[i]->abstime)
#define HEAP_ASSIGN(pos, tmr) ((heap[pos] = (tmr))->heap_pos = (pos))

static Timer **heap;
static int num_timers = 0;
static int heap_size = 0;

static void timer_botch (void*);
static Timer *add_timer (Timer *);

Timer *
timer_set_rel(long time_rel,
	      void (*proc)(void *),
	      void *arg)
{
    Timer *new_t;

    new_t = (Timer *) malloc(sizeof(*new_t));
    if (new_t == NULL)
	return(NULL);
    new_t->abstime = time_rel + NOW;
    new_t->func = proc;
    new_t->arg = arg;
    return add_timer(new_t);
}

void
timer_reset(Timer *tmr)
{
    int pos, min;

    /* Free the timer, saving its heap position. */
    pos = tmr->heap_pos;
    free(tmr);

    if (pos != num_timers - 1) {
	/* Replace the timer with the last timer in the heap and
	 * restore the heap, propagating the timer either up or
	 * down, depending on which way it violates the heap
	 * property to insert the last timer in place of the
	 * deleted timer. */
	if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
	    do {
		HEAP_ASSIGN(pos, heap[PARENT(pos)]);
		pos = PARENT(pos);
	    } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
	    HEAP_ASSIGN(pos, heap[num_timers - 1]);
	} else {
	    while (CHILD2(pos) < num_timers) {
		min = num_timers - 1;
		if (TIME(CHILD1(pos)) < TIME(min))
		    min = CHILD1(pos);
		if (TIME(CHILD2(pos)) < TIME(min))
		    min = CHILD2(pos);
		HEAP_ASSIGN(pos, heap[min]);
		pos = min;
	    }
	    if (pos != num_timers - 1)
		HEAP_ASSIGN(pos, heap[num_timers - 1]);
	}
    }
    num_timers--;
}


#define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))

static Timer *
add_timer(Timer *new)
{
    int pos;

    /* Create or resize the heap as necessary. */
    if (heap_size == 0) {
	heap_size = INITIAL_HEAP_SIZE;
	heap = (Timer **) malloc(heap_size * sizeof(Timer *));
    } else if (num_timers >= heap_size) {
	heap_size = heap_size * 2 + DELTA;
	heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
    }
    if (!heap) {
	free(new);
	return NULL;
    }

    /* Insert the Timer *into the heap. */
    pos = num_timers;
    while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
	HEAP_ASSIGN(pos, heap[PARENT(pos)]);
	pos = PARENT(pos);
    }
    HEAP_ASSIGN(pos, new);
    num_timers++;

    return new;
}

void
timer_process(void)
{
    Timer *t;
    timer_proc func;
    void *arg;

    if (num_timers == 0 || heap[0]->abstime > NOW)
	return;

    /* Remove the first timer from the heap, remembering its
     * function and argument. */
    t = heap[0];
    func = t->func;
    arg = t->arg;
    t->func = timer_botch;
    t->arg = NULL;
    timer_reset(t);
	
    /* Run the function. */
    func(arg);
}

struct timeval *
timer_timeout(struct timeval *tvbuf)
{
    if (num_timers > 0) {
	tvbuf->tv_sec = heap[0]->abstime - NOW;
	if (tvbuf->tv_sec < 0)
	    tvbuf->tv_sec = 0;
	tvbuf->tv_usec = 0;
	return tvbuf;
    } else {
	return NULL;
    }
}

static void
timer_botch(void *arg)
{
    syslog(LOG_CRIT, "timer botch\n");
    abort();
}