xref: /illumos-gate/usr/src/uts/common/io/1394/adapters/hci1394_tlist.c (revision 2570281c)

/*
 * 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 (c) 1999-2000 by Sun Microsystems, Inc.
 * All rights reserved.
 */

/*
 * hci1394_tlist.c
 *   This implements a timed double linked list.
 *   This list supports:
 *	- addition of node to the end of the list
 *	- atomic deletion of node anywhere in list
 *	- get and remove node from head of list
 *	- enable/disable of timeout feature
 *	- timeout feature, if enabled, will remove each node on the list which
 *	  has been on the list for > timeout.  The callback provided will be
 *	  called for each node removed. The worst case time is around
 *	  timer_resolution after the timeout has occurred (i.e. if you set the
 *	  timer resolution to 50uS and the timeout to 100uS, you could get the
 *	  callback anywhere from 100uS to 150uS from when you added the node to
 *	  the list.  This is a general statement and ignores things like
 *	  interrupt latency, context switching, etc.  So if you see a time
 *	  around 155uS, don't complain :-)
 *	- The timer is only used when something is on the list
 */

#include <sys/kmem.h>
#include <sys/types.h>
#include <sys/conf.h>
#include <sys/ddi.h>
#include <sys/sunddi.h>
#include <sys/types.h>

#include <sys/1394/adapters/hci1394.h>


static clock_t t1394_tlist_nsectohz(hrtime_t  nS);
static void hci1394_tlist_remove(hci1394_tlist_t *list,
    hci1394_tlist_node_t *node);
static void hci1394_tlist_callback(void *tlist_handle);


/*
 * hci1394_tlist_init()
 *    Initialize the tlist.  The list will be protected by a mutex at the
 *    iblock_cookie passed in.  init() returns a handle to be used for the rest
 *    of the functions. If you do not wish to use the timeout feature, set
 *    (hci1394_timer_t *) to null.
 */
void
hci1394_tlist_init(hci1394_drvinfo_t *drvinfo, hci1394_tlist_timer_t *timer,
    hci1394_tlist_handle_t *tlist_handle)
{
	hci1394_tlist_t *list;


	ASSERT(tlist_handle != NULL);

	/* try to alloc the space to keep track of the list */
	list = kmem_alloc(sizeof (hci1394_tlist_t), KM_SLEEP);

	/* setup the return parameter */
	*tlist_handle = list;

	/* initialize the list structure */
	list->tl_drvinfo = drvinfo;
	list->tl_state = HCI1394_TLIST_TIMEOUT_OFF;
	list->tl_head = NULL;
	list->tl_tail = NULL;
	if (timer == NULL) {
		list->tl_timer_enabled = B_FALSE;
	} else {
		ASSERT(timer->tlt_callback != NULL);
		list->tl_timer_enabled = B_TRUE;
		list->tl_timer_info = *timer;
	}
	mutex_init(&list->tl_mutex, NULL, MUTEX_DRIVER,
	    drvinfo->di_iblock_cookie);
}


/*
 * hci1394_tlist_fini()
 *    Frees up the space allocated in init().  Notice that a pointer to the
 *    handle is used for the parameter.  fini() will set your handle to NULL
 *    before returning. Make sure that any pending timeouts are canceled.
 */
void
hci1394_tlist_fini(hci1394_tlist_handle_t *tlist_handle)
{
	hci1394_tlist_t *list;


	ASSERT(tlist_handle != NULL);

	list = (hci1394_tlist_t *)*tlist_handle;
	hci1394_tlist_timeout_cancel(list);
	mutex_destroy(&list->tl_mutex);
	kmem_free(list, sizeof (hci1394_tlist_t));

	/* set handle to null.  This helps catch bugs. */
	*tlist_handle = NULL;
}


/*
 * hci1394_tlist_add()
 *    Add the node to the tail of the linked list. The list is protected by a
 *    mutex at the iblock_cookie passed in during init.
 */
void
hci1394_tlist_add(hci1394_tlist_handle_t tlist_handle,
    hci1394_tlist_node_t *node)
{
	ASSERT(tlist_handle != NULL);
	ASSERT(node != NULL);

	mutex_enter(&tlist_handle->tl_mutex);

	/* add's always go at the end of the list */
	node->tln_next = NULL;

	/* Set state that this node is currently on the tlist */
	node->tln_on_list = B_TRUE;

	/* enter in the expire time (in uS) */
	if (tlist_handle->tl_timer_enabled == B_TRUE) {
		node->tln_expire_time = gethrtime() +
		    tlist_handle->tl_timer_info.tlt_timeout;
	}

	/* if there is nothing in the list */
	if (tlist_handle->tl_tail == NULL) {
		tlist_handle->tl_head = node;
		tlist_handle->tl_tail = node;
		node->tln_prev = NULL;

		if ((tlist_handle->tl_timer_enabled == B_TRUE) &&
		    (tlist_handle->tl_state == HCI1394_TLIST_TIMEOUT_OFF)) {
			/* turn the timer on */
			tlist_handle->tl_timeout_id = timeout(
			    hci1394_tlist_callback, tlist_handle,
			    t1394_tlist_nsectohz(
			    tlist_handle->tl_timer_info.tlt_timer_resolution));
			tlist_handle->tl_state = HCI1394_TLIST_TIMEOUT_ON;
		}
	} else {
		/* put the node on the end of the list */
		tlist_handle->tl_tail->tln_next = node;
		node->tln_prev = tlist_handle->tl_tail;
		tlist_handle->tl_tail = node;
		/*
		 * if timeouts are enabled,  we don't have to call
		 * timeout() because the timer is already on.
		 */
	}

	mutex_exit(&tlist_handle->tl_mutex);
}


/*
 * hci1394_tlist_delete()
 *    Remove the node from the list.  The node can be anywhere in the list. Make
 *    sure that the node is only removed once since different threads maybe
 *    trying to delete the same node at the same time.
 */
int
hci1394_tlist_delete(hci1394_tlist_handle_t tlist_handle,
    hci1394_tlist_node_t *node)
{
	ASSERT(tlist_handle != NULL);
	ASSERT(node != NULL);

	mutex_enter(&tlist_handle->tl_mutex);

	/*
	 * check for race condition.  Someone else may have already removed this
	 * node from the list. hci1394_tlist_delete() supports two threads
	 * trying to delete the node at the same time. The "losing" thread will
	 * have DDI_FAILURE returned.
	 */
	if (node->tln_on_list == B_FALSE) {
		mutex_exit(&tlist_handle->tl_mutex);
		return (DDI_FAILURE);
	}

	hci1394_tlist_remove(tlist_handle, node);
	mutex_exit(&tlist_handle->tl_mutex);

	return (DDI_SUCCESS);
}


/*
 * hci1394_tlist_get()
 *    get the node at the head of the linked list. This function also removes
 *    the node from the list.
 */
void
hci1394_tlist_get(hci1394_tlist_handle_t tlist_handle,
    hci1394_tlist_node_t **node)
{
	ASSERT(tlist_handle != NULL);
	ASSERT(node != NULL);

	mutex_enter(&tlist_handle->tl_mutex);

	/* set the return parameter */
	*node = tlist_handle->tl_head;

	/* remove the node from the tlist */
	if (*node != NULL) {
		hci1394_tlist_remove(tlist_handle, *node);
	}

	mutex_exit(&tlist_handle->tl_mutex);
}


/*
 * hci1394_tlist_peek()
 *    get the node at the head of the linked list. This function does not
 *    remove the node from the list.
 */
void
hci1394_tlist_peek(hci1394_tlist_handle_t tlist_handle,
    hci1394_tlist_node_t **node)
{
	ASSERT(tlist_handle != NULL);
	ASSERT(node != NULL);

	mutex_enter(&tlist_handle->tl_mutex);
	*node = tlist_handle->tl_head;
	mutex_exit(&tlist_handle->tl_mutex);
}


/*
 * hci1394_tlist_timeout_update()
 *    update the timeout to a different value. timeout is in uS.  The update
 *    does not happen immediately.  The new timeout will not take effect until
 *    the all of nodes currently present in the list are gone. It only makes
 *    sense to call this function when you have the timeout feature enabled.
 */
void
hci1394_tlist_timeout_update(hci1394_tlist_handle_t tlist_handle,
    hrtime_t timeout)
{
	ASSERT(tlist_handle != NULL);

	/* set timeout to the new timeout */
	tlist_handle->tl_timer_info.tlt_timeout = timeout;
}


/*
 * hci1394_tlist_timeout_cancel()
 *    cancel any scheduled timeouts.  This should be called after the list is
 *    empty and there is no chance for any other nodes to be placed on the list.
 *    This function is meant to be called during a suspend or detach.
 */
void
hci1394_tlist_timeout_cancel(hci1394_tlist_handle_t tlist_handle)
{
	ASSERT(tlist_handle != NULL);

	/*
	 * Cancel the timeout. Do NOT use the tlist mutex here. It could cause a
	 * deadlock.
	 */
	if (tlist_handle->tl_state == HCI1394_TLIST_TIMEOUT_ON) {
		(void) untimeout(tlist_handle->tl_timeout_id);
		tlist_handle->tl_state = HCI1394_TLIST_TIMEOUT_OFF;
	}
}


/*
 * hci1394_tlist_callback()
 *    The callback we use for the timeout() function. See if there are any nodes
 *    on the list which have timed out. If so, call the registered callback for
 *    each timed out node. We always start looking at the top of the list since
 *    the list is time sorted (oldest at the top).
 */
static void
hci1394_tlist_callback(void *tlist_handle)
{
	hci1394_tlist_t *list;
	hci1394_tlist_node_t *node;
	hrtime_t current_time;


	ASSERT(tlist_handle != NULL);

	list = (hci1394_tlist_t *)tlist_handle;

	mutex_enter(&list->tl_mutex);

	/*
	 * if there is something on the list, check to see if the oldest has
	 * expired.  If there is nothing on the list, there is no reason to
	 * renew the timeout.
	 */
	node = list->tl_head;
	current_time = gethrtime();
	while (node != NULL) {
		/*
		 * if current time is greater than the time the command expires,
		 * AND, the expire time has not rolled over, then the command
		 * has timed out.
		 */
		if (((uint64_t)current_time >=
		    (uint64_t)node->tln_expire_time) &&
		    (((uint64_t)node->tln_expire_time -
		    (uint64_t)list->tl_timer_info.tlt_timeout) <
		    (uint64_t)node->tln_expire_time)) {
			/* remove the node from the tlist */
			hci1394_tlist_remove(list, node);

			/*
			 * Call the timeout callback. We unlock the the mutex
			 * around the callback so that other transactions will
			 * not be blocked while the callback is running. This
			 * is OK to do here because we have already removed this
			 * entry from our list. This code should not reference
			 * "node" again after the callback! After the callback
			 * returns, we need to resync node to the head of the
			 * list since we released/acquired the list mutex around
			 * the callback.
			 */
			mutex_exit(&list->tl_mutex);
			list->tl_timer_info.tlt_callback(node,
			    list->tl_timer_info.tlt_callback_arg);
			mutex_enter(&list->tl_mutex);
			node = list->tl_head;

		/*
		 * else, if current time is greater than the time the command
		 * expires, AND, current_time is not about to rollover. (this
		 * works since it is in the else and we periodically sample
		 * well below the rollover time)
		 */
		} else if ((uint64_t)(current_time >=
		    (uint64_t)node->tln_expire_time) &&
		    (((uint64_t)current_time +
		    (uint64_t)list->tl_timer_info.tlt_timeout) >
		    (uint64_t)current_time)) {
			/* remove the node from the tlist */
			hci1394_tlist_remove(list, node);

			/*
			 * Call the timeout callback. We unlock the the mutex
			 * around the callback so that other transactions will
			 * not be blocked while the callback is running. This
			 * is OK to do here because we have already removed this
			 * entry from our list. This code should not reference
			 * "node" again after the callback! After the callback
			 * returns, we need to resync node to the head of the
			 * list since we released/acquired the list mutex around
			 * the callback.
			 */
			mutex_exit(&list->tl_mutex);
			list->tl_timer_info.tlt_callback(node,
			    list->tl_timer_info.tlt_callback_arg);
			mutex_enter(&list->tl_mutex);
			node = list->tl_head;

		} else {
			/*
			 * this command has not timed out.
			 * Since this list is time sorted, we are
			 * done looking for nodes that have expired
			 */
			break;
		}
	}

	/*
	 * if there are nodes still on the pending list, kick
	 * off the timer again.
	 */
	if (node != NULL) {
		list->tl_timeout_id = timeout(hci1394_tlist_callback, list,
		    t1394_tlist_nsectohz(
		    list->tl_timer_info.tlt_timer_resolution));
		list->tl_state = HCI1394_TLIST_TIMEOUT_ON;
	} else {
		list->tl_state = HCI1394_TLIST_TIMEOUT_OFF;
	}

	mutex_exit(&list->tl_mutex);
}


/*
 * hci1394_tlist_remove()
 *    This is an internal function which removes the given node from the list.
 *    The list MUST be locked before calling this function.
 */
static void
hci1394_tlist_remove(hci1394_tlist_t *list, hci1394_tlist_node_t *node)
{
	ASSERT(list != NULL);
	ASSERT(node != NULL);
	ASSERT(node->tln_on_list == B_TRUE);
	ASSERT(MUTEX_HELD(&list->tl_mutex));

	/* if this is the only node on the list */
	if ((list->tl_head == node) &&
	    (list->tl_tail == node)) {
		list->tl_head = NULL;
		list->tl_tail = NULL;

	/* if the node is at the head of the list */
	} else if (list->tl_head == node) {
		list->tl_head = node->tln_next;
		node->tln_next->tln_prev = NULL;

	/* if the node is at the tail of the list */
	} else if (list->tl_tail == node) {
		list->tl_tail = node->tln_prev;
		node->tln_prev->tln_next = NULL;

	/* if the node is in the middle of the list */
	} else {
		node->tln_prev->tln_next = node->tln_next;
		node->tln_next->tln_prev = node->tln_prev;
	}

	/* Set state that this node has been removed from the list */
	node->tln_on_list = B_FALSE;

	/* cleanup the node's link pointers */
	node->tln_prev = NULL;
	node->tln_next = NULL;
}


/*
 * t1394_tlist_nsectohz()
 *     Convert nS to hz.  This allows us to call timeout() but keep our time
 *     reference in nS.
 */
#define	HCI1394_TLIST_nS_TO_uS(nS)  ((clock_t)(nS / 1000))
static clock_t t1394_tlist_nsectohz(hrtime_t  nS)
{
	return (drv_usectohz(HCI1394_TLIST_nS_TO_uS(nS)));
}