1 files changed, 438 insertions, 0 deletions
diff --git a/usr/src/lib/libinetutil/common/tq.c b/usr/src/lib/libinetutil/common/tq.c
new file mode 100644
index 0000000000..78505462bd
--- /dev/null
+++ b/usr/src/lib/libinetutil/common/tq.c
@@ -0,0 +1,438 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+#include <stdlib.h>
+#include <limits.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <sys/sysmacros.h>
+#include <sys/stropts.h>	/* INFTIM */
+
+#include <libinetutil.h>
+#include "libinetutil_impl.h"
+
+static iu_timer_node_t	*pending_delete_chain = NULL;
+
+static void		destroy_timer(iu_tq_t *, iu_timer_node_t *);
+static iu_timer_id_t	get_timer_id(iu_tq_t *);
+static void		release_timer_id(iu_tq_t *, iu_timer_id_t);
+
+/*
+ * iu_tq_create(): creates, initializes and returns a timer queue for use
+ *
+ *   input: void
+ *  output: iu_tq_t *: the new timer queue
+ */
+
+iu_tq_t *
+iu_tq_create(void)
+{
+	return (calloc(1, sizeof (iu_tq_t)));
+}
+
+/*
+ * iu_tq_destroy(): destroys an existing timer queue
+ *
+ *   input: iu_tq_t *: the timer queue to destroy
+ *  output: void
+ */
+
+void
+iu_tq_destroy(iu_tq_t *tq)
+{
+	iu_timer_node_t *node, *next_node;
+
+	for (node = tq->iutq_head; node != NULL; node = next_node) {
+		next_node = node->iutn_next;
+		destroy_timer(tq, node);
+	}
+
+	free(tq);
+}
+
+/*
+ * insert_timer(): inserts a timer node into a tq's timer list
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    iu_timer_node_t *: the timer node to insert into the list
+ *	    uint64_t: the number of milliseconds before this timer fires
+ *  output: void
+ */
+
+static void
+insert_timer(iu_tq_t *tq, iu_timer_node_t *node, uint64_t msec)
+{
+	iu_timer_node_t	*after = NULL;
+
+	/*
+	 * find the node to insert this new node "after".  we do this
+	 * instead of the more intuitive "insert before" because with
+	 * the insert before approach, a null `before' node pointer
+	 * is overloaded in meaning (it could be null because there
+	 * are no items in the list, or it could be null because this
+	 * is the last item on the list, which are very different cases).
+	 */
+
+	node->iutn_abs_timeout = gethrtime() + (msec * (NANOSEC / MILLISEC));
+
+	if (tq->iutq_head != NULL &&
+	    tq->iutq_head->iutn_abs_timeout < node->iutn_abs_timeout)
+		for (after = tq->iutq_head; after->iutn_next != NULL;
+		    after = after->iutn_next)
+			if (after->iutn_next->iutn_abs_timeout >
+			    node->iutn_abs_timeout)
+				break;
+
+	node->iutn_next = after ? after->iutn_next : tq->iutq_head;
+	node->iutn_prev = after;
+	if (after == NULL)
+		tq->iutq_head = node;
+	else
+		after->iutn_next = node;
+
+	if (node->iutn_next != NULL)
+		node->iutn_next->iutn_prev = node;
+}
+
+/*
+ * remove_timer(): removes a timer node from the tq's timer list
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    iu_timer_node_t *: the timer node to remove from the list
+ *  output: void
+ */
+
+static void
+remove_timer(iu_tq_t *tq, iu_timer_node_t *node)
+{
+	if (node->iutn_next != NULL)
+		node->iutn_next->iutn_prev = node->iutn_prev;
+	if (node->iutn_prev != NULL)
+		node->iutn_prev->iutn_next = node->iutn_next;
+	else
+		tq->iutq_head = node->iutn_next;
+}
+
+/*
+ * destroy_timer(): destroy a timer node
+ *
+ *  input: iu_tq_t *: the timer queue the timer node is associated with
+ *	   iu_timer_node_t *: the node to free
+ * output: void
+ */
+
+static void
+destroy_timer(iu_tq_t *tq, iu_timer_node_t *node)
+{
+	release_timer_id(tq, node->iutn_timer_id);
+
+	/*
+	 * if we're in expire, don't delete the node yet, since it may
+	 * still be referencing it (through the expire_next pointers)
+	 */
+
+	if (tq->iutq_in_expire) {
+		node->iutn_pending_delete++;
+		node->iutn_next = pending_delete_chain;
+		pending_delete_chain = node;
+	} else
+		free(node);
+
+}
+
+/*
+ * iu_schedule_timer(): creates and inserts a timer in the tq's timer list
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    uint32_t: the number of seconds before this timer fires
+ *	    iu_tq_callback_t *: the function to call when the timer fires
+ *	    void *: an argument to pass to the called back function
+ *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
+ */
+
+iu_timer_id_t
+iu_schedule_timer(iu_tq_t *tq, uint32_t sec, iu_tq_callback_t *callback,
+    void *arg)
+{
+	return (iu_schedule_timer_ms(tq, sec * MILLISEC, callback, arg));
+}
+
+/*
+ * iu_schedule_ms_timer(): creates and inserts a timer in the tq's timer list,
+ *			   using millisecond granularity
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    uint64_t: the number of milliseconds before this timer fires
+ *	    iu_tq_callback_t *: the function to call when the timer fires
+ *	    void *: an argument to pass to the called back function
+ *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
+ */
+iu_timer_id_t
+iu_schedule_timer_ms(iu_tq_t *tq, uint64_t ms, iu_tq_callback_t *callback,
+    void *arg)
+{
+	iu_timer_node_t	*node = calloc(1, sizeof (iu_timer_node_t));
+
+	if (node == NULL)
+		return (-1);
+
+	node->iutn_callback	= callback;
+	node->iutn_arg	= arg;
+	node->iutn_timer_id	= get_timer_id(tq);
+	if (node->iutn_timer_id == -1) {
+		free(node);
+		return (-1);
+	}
+
+	insert_timer(tq, node, ms);
+
+	return (node->iutn_timer_id);
+}
+
+/*
+ * iu_cancel_timer(): cancels a pending timer from a timer queue's timer list
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    iu_timer_id_t: the timer id returned from iu_schedule_timer
+ *	    void **: if non-NULL, a place to return the argument passed to
+ *		     iu_schedule_timer
+ *  output: int: 1 on success, 0 on failure
+ */
+
+int
+iu_cancel_timer(iu_tq_t *tq, iu_timer_id_t timer_id, void **arg)
+{
+	iu_timer_node_t	*node;
+
+	if (timer_id == -1)
+		return (0);
+
+	for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
+		if (node->iutn_timer_id == timer_id) {
+			if (arg != NULL)
+				*arg = node->iutn_arg;
+			remove_timer(tq, node);
+			destroy_timer(tq, node);
+			return (1);
+		}
+	}
+	return (0);
+}
+
+/*
+ * iu_adjust_timer(): adjusts the fire time of a timer in the tq's timer list
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    iu_timer_id_t: the timer id returned from iu_schedule_timer
+ *	    uint32_t: the number of seconds before this timer fires
+ *  output: int: 1 on success, 0 on failure
+ */
+
+int
+iu_adjust_timer(iu_tq_t *tq, iu_timer_id_t timer_id, uint32_t sec)
+{
+	iu_timer_node_t	*node;
+
+	if (timer_id == -1)
+		return (0);
+
+	for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
+		if (node->iutn_timer_id == timer_id) {
+			remove_timer(tq, node);
+			insert_timer(tq, node, sec * MILLISEC);
+			return (1);
+		}
+	}
+	return (0);
+}
+
+/*
+ * iu_earliest_timer(): returns the time until the next timer fires on a tq
+ *
+ *   input: iu_tq_t *: the timer queue
+ *  output: int: the number of milliseconds until the next timer (up to
+ *	    a maximum value of INT_MAX), or INFTIM if no timers are pending.
+ */
+
+int
+iu_earliest_timer(iu_tq_t *tq)
+{
+	unsigned long long	timeout_interval;
+	hrtime_t		current_time = gethrtime();
+
+	if (tq->iutq_head == NULL)
+		return (INFTIM);
+
+	/*
+	 * event might've already happened if we haven't gotten a chance to
+	 * run in a while; return zero and pretend it just expired.
+	 */
+
+	if (tq->iutq_head->iutn_abs_timeout <= current_time)
+		return (0);
+
+	/*
+	 * since the timers are ordered in absolute time-to-fire, just
+	 * subtract from the head of the list.
+	 */
+
+	timeout_interval =
+	    (tq->iutq_head->iutn_abs_timeout - current_time) / 1000000;
+
+	return (MIN(timeout_interval, INT_MAX));
+}
+
+/*
+ * iu_expire_timers(): expires all pending timers on a given timer queue
+ *
+ *   input: iu_tq_t *: the timer queue
+ *  output: int: the number of timers expired
+ */
+
+int
+iu_expire_timers(iu_tq_t *tq)
+{
+	iu_timer_node_t	*node, *next_node;
+	int		n_expired = 0;
+	hrtime_t	current_time = gethrtime();
+
+	/*
+	 * in_expire is in the iu_tq_t instead of being passed through as
+	 * an argument to remove_timer() below since the callback
+	 * function may call iu_cancel_timer() itself as well.
+	 */
+
+	tq->iutq_in_expire++;
+
+	/*
+	 * this function builds another linked list of timer nodes
+	 * through `expire_next' because the normal linked list
+	 * may be changed as a result of callbacks canceling and
+	 * scheduling timeouts, and thus can't be trusted.
+	 */
+
+	for (node = tq->iutq_head; node != NULL; node = node->iutn_next)
+		node->iutn_expire_next = node->iutn_next;
+
+	for (node = tq->iutq_head; node != NULL;
+	    node = node->iutn_expire_next) {
+
+		if (node->iutn_abs_timeout > current_time)
+			break;
+
+		/*
+		 * fringe condition: two timers fire at the "same
+		 * time" (i.e., they're both scheduled called back in
+		 * this loop) and one cancels the other.  in this
+		 * case, the timer which has already been "cancelled"
+		 * should not be called back.
+		 */
+
+		if (node->iutn_pending_delete)
+			continue;
+
+		/*
+		 * we remove the timer before calling back the callback
+		 * so that a callback which accidentally tries to cancel
+		 * itself (through whatever means) doesn't succeed.
+		 */
+
+		n_expired++;
+		remove_timer(tq, node);
+		destroy_timer(tq, node);
+		node->iutn_callback(tq, node->iutn_arg);
+	}
+
+	tq->iutq_in_expire--;
+
+	/*
+	 * any cancels that took place whilst we were expiring timeouts
+	 * ended up on the `pending_delete_chain'.  delete them now
+	 * that it's safe.
+	 */
+
+	for (node = pending_delete_chain; node != NULL; node = next_node) {
+		next_node = node->iutn_next;
+		free(node);
+	}
+	pending_delete_chain = NULL;
+
+	return (n_expired);
+}
+
+/*
+ * get_timer_id(): allocates a timer id from the pool
+ *
+ *   input: iu_tq_t *: the timer queue
+ *  output: iu_timer_id_t: the allocated timer id, or -1 if none available
+ */
+
+static iu_timer_id_t
+get_timer_id(iu_tq_t *tq)
+{
+	unsigned int	map_index;
+	unsigned char	map_bit;
+	boolean_t	have_wrapped = B_FALSE;
+
+	for (; ; tq->iutq_next_timer_id++) {
+
+		if (tq->iutq_next_timer_id >= IU_TIMER_ID_MAX) {
+			if (have_wrapped)
+				return (-1);
+
+			have_wrapped = B_TRUE;
+			tq->iutq_next_timer_id = 0;
+		}
+
+		map_index = tq->iutq_next_timer_id / CHAR_BIT;
+		map_bit   = tq->iutq_next_timer_id % CHAR_BIT;
+
+		if ((tq->iutq_timer_id_map[map_index] & (1 << map_bit)) == 0)
+			break;
+	}
+
+	tq->iutq_timer_id_map[map_index] |= (1 << map_bit);
+	return (tq->iutq_next_timer_id++);
+}
+
+/*
+ * release_timer_id(): releases a timer id back into the pool
+ *
+ *   input: iu_tq_t *: the timer queue
+ *	    iu_timer_id_t: the timer id to release
+ *  output: void
+ */
+
+static void
+release_timer_id(iu_tq_t *tq, iu_timer_id_t timer_id)
+{
+	unsigned int	map_index = timer_id / CHAR_BIT;
+	unsigned char	map_bit	  = timer_id % CHAR_BIT;
+
+	tq->iutq_timer_id_map[map_index] &= ~(1 << map_bit);
+}