xref: /illumos-gate/usr/src/lib/libinetutil/common/tq.c (revision 19449258)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include <stdlib.h>
27 #include <limits.h>
28 #include <sys/time.h>
29 #include <sys/types.h>
30 #include <sys/sysmacros.h>
31 #include <sys/stropts.h>	/* INFTIM */
32 
33 #include <libinetutil.h>
34 #include "libinetutil_impl.h"
35 
36 static iu_timer_node_t	*pending_delete_chain = NULL;
37 
38 static void		destroy_timer(iu_tq_t *, iu_timer_node_t *);
39 static iu_timer_id_t	get_timer_id(iu_tq_t *);
40 static void		release_timer_id(iu_tq_t *, iu_timer_id_t);
41 
42 /*
43  * iu_tq_create(): creates, initializes and returns a timer queue for use
44  *
45  *   input: void
46  *  output: iu_tq_t *: the new timer queue
47  */
48 
49 iu_tq_t *
iu_tq_create(void)50 iu_tq_create(void)
51 {
52 	return (calloc(1, sizeof (iu_tq_t)));
53 }
54 
55 /*
56  * iu_tq_destroy(): destroys an existing timer queue
57  *
58  *   input: iu_tq_t *: the timer queue to destroy
59  *  output: void
60  */
61 
62 void
iu_tq_destroy(iu_tq_t * tq)63 iu_tq_destroy(iu_tq_t *tq)
64 {
65 	iu_timer_node_t *node, *next_node;
66 
67 	for (node = tq->iutq_head; node != NULL; node = next_node) {
68 		next_node = node->iutn_next;
69 		destroy_timer(tq, node);
70 	}
71 
72 	free(tq);
73 }
74 
75 /*
76  * insert_timer(): inserts a timer node into a tq's timer list
77  *
78  *   input: iu_tq_t *: the timer queue
79  *	    iu_timer_node_t *: the timer node to insert into the list
80  *	    uint64_t: the number of milliseconds before this timer fires
81  *  output: void
82  */
83 
84 static void
insert_timer(iu_tq_t * tq,iu_timer_node_t * node,uint64_t msec)85 insert_timer(iu_tq_t *tq, iu_timer_node_t *node, uint64_t msec)
86 {
87 	iu_timer_node_t	*after = NULL;
88 
89 	/*
90 	 * find the node to insert this new node "after".  we do this
91 	 * instead of the more intuitive "insert before" because with
92 	 * the insert before approach, a null `before' node pointer
93 	 * is overloaded in meaning (it could be null because there
94 	 * are no items in the list, or it could be null because this
95 	 * is the last item on the list, which are very different cases).
96 	 */
97 
98 	node->iutn_abs_timeout = gethrtime() + MSEC2NSEC(msec);
99 
100 	if (tq->iutq_head != NULL &&
101 	    tq->iutq_head->iutn_abs_timeout < node->iutn_abs_timeout)
102 		for (after = tq->iutq_head; after->iutn_next != NULL;
103 		    after = after->iutn_next)
104 			if (after->iutn_next->iutn_abs_timeout >
105 			    node->iutn_abs_timeout)
106 				break;
107 
108 	node->iutn_next = after ? after->iutn_next : tq->iutq_head;
109 	node->iutn_prev = after;
110 	if (after == NULL)
111 		tq->iutq_head = node;
112 	else
113 		after->iutn_next = node;
114 
115 	if (node->iutn_next != NULL)
116 		node->iutn_next->iutn_prev = node;
117 }
118 
119 /*
120  * remove_timer(): removes a timer node from the tq's timer list
121  *
122  *   input: iu_tq_t *: the timer queue
123  *	    iu_timer_node_t *: the timer node to remove from the list
124  *  output: void
125  */
126 
127 static void
remove_timer(iu_tq_t * tq,iu_timer_node_t * node)128 remove_timer(iu_tq_t *tq, iu_timer_node_t *node)
129 {
130 	if (node->iutn_next != NULL)
131 		node->iutn_next->iutn_prev = node->iutn_prev;
132 	if (node->iutn_prev != NULL)
133 		node->iutn_prev->iutn_next = node->iutn_next;
134 	else
135 		tq->iutq_head = node->iutn_next;
136 }
137 
138 /*
139  * destroy_timer(): destroy a timer node
140  *
141  *  input: iu_tq_t *: the timer queue the timer node is associated with
142  *	   iu_timer_node_t *: the node to free
143  * output: void
144  */
145 
146 static void
destroy_timer(iu_tq_t * tq,iu_timer_node_t * node)147 destroy_timer(iu_tq_t *tq, iu_timer_node_t *node)
148 {
149 	release_timer_id(tq, node->iutn_timer_id);
150 
151 	/*
152 	 * if we're in expire, don't delete the node yet, since it may
153 	 * still be referencing it (through the expire_next pointers)
154 	 */
155 
156 	if (tq->iutq_in_expire) {
157 		node->iutn_pending_delete++;
158 		node->iutn_next = pending_delete_chain;
159 		pending_delete_chain = node;
160 	} else
161 		free(node);
162 
163 }
164 
165 /*
166  * iu_schedule_timer(): creates and inserts a timer in the tq's timer list
167  *
168  *   input: iu_tq_t *: the timer queue
169  *	    uint32_t: the number of seconds before this timer fires
170  *	    iu_tq_callback_t *: the function to call when the timer fires
171  *	    void *: an argument to pass to the called back function
172  *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
173  */
174 
175 iu_timer_id_t
iu_schedule_timer(iu_tq_t * tq,uint32_t sec,iu_tq_callback_t * callback,void * arg)176 iu_schedule_timer(iu_tq_t *tq, uint32_t sec, iu_tq_callback_t *callback,
177     void *arg)
178 {
179 	return (iu_schedule_timer_ms(tq, sec * MILLISEC, callback, arg));
180 }
181 
182 /*
183  * iu_schedule_ms_timer(): creates and inserts a timer in the tq's timer list,
184  *			   using millisecond granularity
185  *
186  *   input: iu_tq_t *: the timer queue
187  *	    uint64_t: the number of milliseconds before this timer fires
188  *	    iu_tq_callback_t *: the function to call when the timer fires
189  *	    void *: an argument to pass to the called back function
190  *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
191  */
192 iu_timer_id_t
iu_schedule_timer_ms(iu_tq_t * tq,uint64_t ms,iu_tq_callback_t * callback,void * arg)193 iu_schedule_timer_ms(iu_tq_t *tq, uint64_t ms, iu_tq_callback_t *callback,
194     void *arg)
195 {
196 	iu_timer_node_t	*node = calloc(1, sizeof (iu_timer_node_t));
197 
198 	if (node == NULL)
199 		return (-1);
200 
201 	node->iutn_callback	= callback;
202 	node->iutn_arg	= arg;
203 	node->iutn_timer_id	= get_timer_id(tq);
204 	if (node->iutn_timer_id == -1) {
205 		free(node);
206 		return (-1);
207 	}
208 
209 	insert_timer(tq, node, ms);
210 
211 	return (node->iutn_timer_id);
212 }
213 
214 /*
215  * iu_cancel_timer(): cancels a pending timer from a timer queue's timer list
216  *
217  *   input: iu_tq_t *: the timer queue
218  *	    iu_timer_id_t: the timer id returned from iu_schedule_timer
219  *	    void **: if non-NULL, a place to return the argument passed to
220  *		     iu_schedule_timer
221  *  output: int: 1 on success, 0 on failure
222  */
223 
224 int
iu_cancel_timer(iu_tq_t * tq,iu_timer_id_t timer_id,void ** arg)225 iu_cancel_timer(iu_tq_t *tq, iu_timer_id_t timer_id, void **arg)
226 {
227 	iu_timer_node_t	*node;
228 
229 	if (timer_id == -1)
230 		return (0);
231 
232 	for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
233 		if (node->iutn_timer_id == timer_id) {
234 			if (arg != NULL)
235 				*arg = node->iutn_arg;
236 			remove_timer(tq, node);
237 			destroy_timer(tq, node);
238 			return (1);
239 		}
240 	}
241 	return (0);
242 }
243 
244 /*
245  * iu_adjust_timer(): adjusts the fire time of a timer in the tq's timer list
246  *
247  *   input: iu_tq_t *: the timer queue
248  *	    iu_timer_id_t: the timer id returned from iu_schedule_timer
249  *	    uint32_t: the number of seconds before this timer fires
250  *  output: int: 1 on success, 0 on failure
251  */
252 
253 int
iu_adjust_timer(iu_tq_t * tq,iu_timer_id_t timer_id,uint32_t sec)254 iu_adjust_timer(iu_tq_t *tq, iu_timer_id_t timer_id, uint32_t sec)
255 {
256 	iu_timer_node_t	*node;
257 
258 	if (timer_id == -1)
259 		return (0);
260 
261 	for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
262 		if (node->iutn_timer_id == timer_id) {
263 			remove_timer(tq, node);
264 			insert_timer(tq, node, sec * MILLISEC);
265 			return (1);
266 		}
267 	}
268 	return (0);
269 }
270 
271 /*
272  * iu_earliest_timer(): returns the time until the next timer fires on a tq
273  *
274  *   input: iu_tq_t *: the timer queue
275  *  output: int: the number of milliseconds until the next timer (up to
276  *	    a maximum value of INT_MAX), or INFTIM if no timers are pending.
277  */
278 
279 int
iu_earliest_timer(iu_tq_t * tq)280 iu_earliest_timer(iu_tq_t *tq)
281 {
282 	unsigned long long	timeout_interval;
283 	hrtime_t		current_time = gethrtime();
284 
285 	if (tq->iutq_head == NULL)
286 		return (INFTIM);
287 
288 	/*
289 	 * event might've already happened if we haven't gotten a chance to
290 	 * run in a while; return zero and pretend it just expired.
291 	 */
292 
293 	if (tq->iutq_head->iutn_abs_timeout <= current_time)
294 		return (0);
295 
296 	/*
297 	 * since the timers are ordered in absolute time-to-fire, just
298 	 * subtract from the head of the list.
299 	 */
300 
301 	timeout_interval =
302 	    (tq->iutq_head->iutn_abs_timeout - current_time) / 1000000;
303 
304 	return (MIN(timeout_interval, INT_MAX));
305 }
306 
307 /*
308  * iu_expire_timers(): expires all pending timers on a given timer queue
309  *
310  *   input: iu_tq_t *: the timer queue
311  *  output: int: the number of timers expired
312  */
313 
314 int
iu_expire_timers(iu_tq_t * tq)315 iu_expire_timers(iu_tq_t *tq)
316 {
317 	iu_timer_node_t	*node, *next_node;
318 	int		n_expired = 0;
319 	hrtime_t	current_time = gethrtime();
320 
321 	/*
322 	 * in_expire is in the iu_tq_t instead of being passed through as
323 	 * an argument to remove_timer() below since the callback
324 	 * function may call iu_cancel_timer() itself as well.
325 	 */
326 
327 	tq->iutq_in_expire++;
328 
329 	/*
330 	 * this function builds another linked list of timer nodes
331 	 * through `expire_next' because the normal linked list
332 	 * may be changed as a result of callbacks canceling and
333 	 * scheduling timeouts, and thus can't be trusted.
334 	 */
335 
336 	for (node = tq->iutq_head; node != NULL; node = node->iutn_next)
337 		node->iutn_expire_next = node->iutn_next;
338 
339 	for (node = tq->iutq_head; node != NULL;
340 	    node = node->iutn_expire_next) {
341 
342 		/*
343 		 * If the timeout is within 1 millisec of current time,
344 		 * consider it as expired already.  We do this because
345 		 * iu_earliest_timer() only has millisec granularity.
346 		 * So we should also use millisec grandularity in
347 		 * comparing timeout values.
348 		 */
349 		if (node->iutn_abs_timeout - current_time > 1000000)
350 			break;
351 
352 		/*
353 		 * fringe condition: two timers fire at the "same
354 		 * time" (i.e., they're both scheduled called back in
355 		 * this loop) and one cancels the other.  in this
356 		 * case, the timer which has already been "cancelled"
357 		 * should not be called back.
358 		 */
359 
360 		if (node->iutn_pending_delete)
361 			continue;
362 
363 		/*
364 		 * we remove the timer before calling back the callback
365 		 * so that a callback which accidentally tries to cancel
366 		 * itself (through whatever means) doesn't succeed.
367 		 */
368 
369 		n_expired++;
370 		remove_timer(tq, node);
371 		destroy_timer(tq, node);
372 		node->iutn_callback(tq, node->iutn_arg);
373 	}
374 
375 	tq->iutq_in_expire--;
376 
377 	/*
378 	 * any cancels that took place whilst we were expiring timeouts
379 	 * ended up on the `pending_delete_chain'.  delete them now
380 	 * that it's safe.
381 	 */
382 
383 	for (node = pending_delete_chain; node != NULL; node = next_node) {
384 		next_node = node->iutn_next;
385 		free(node);
386 	}
387 	pending_delete_chain = NULL;
388 
389 	return (n_expired);
390 }
391 
392 /*
393  * get_timer_id(): allocates a timer id from the pool
394  *
395  *   input: iu_tq_t *: the timer queue
396  *  output: iu_timer_id_t: the allocated timer id, or -1 if none available
397  */
398 
399 static iu_timer_id_t
get_timer_id(iu_tq_t * tq)400 get_timer_id(iu_tq_t *tq)
401 {
402 	unsigned int	map_index;
403 	unsigned char	map_bit;
404 	boolean_t	have_wrapped = B_FALSE;
405 
406 	for (; ; tq->iutq_next_timer_id++) {
407 
408 		if (tq->iutq_next_timer_id >= IU_TIMER_ID_MAX) {
409 			if (have_wrapped)
410 				return (-1);
411 
412 			have_wrapped = B_TRUE;
413 			tq->iutq_next_timer_id = 0;
414 		}
415 
416 		map_index = tq->iutq_next_timer_id / CHAR_BIT;
417 		map_bit   = tq->iutq_next_timer_id % CHAR_BIT;
418 
419 		if ((tq->iutq_timer_id_map[map_index] & (1 << map_bit)) == 0)
420 			break;
421 	}
422 
423 	tq->iutq_timer_id_map[map_index] |= (1 << map_bit);
424 	return (tq->iutq_next_timer_id++);
425 }
426 
427 /*
428  * release_timer_id(): releases a timer id back into the pool
429  *
430  *   input: iu_tq_t *: the timer queue
431  *	    iu_timer_id_t: the timer id to release
432  *  output: void
433  */
434 
435 static void
release_timer_id(iu_tq_t * tq,iu_timer_id_t timer_id)436 release_timer_id(iu_tq_t *tq, iu_timer_id_t timer_id)
437 {
438 	unsigned int	map_index = timer_id / CHAR_BIT;
439 	unsigned char	map_bit	  = timer_id % CHAR_BIT;
440 
441 	tq->iutq_timer_id_map[map_index] &= ~(1 << map_bit);
442 }
443