/*
* 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.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_init_enter, HCI1394_TNF_HAL_STACK, "");
/* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_init_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_fini_enter, HCI1394_TNF_HAL_STACK, "");
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;
TNF_PROBE_0_DEBUG(hci1394_tlist_fini_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_add_enter, HCI1394_TNF_HAL_STACK, "");
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);
TNF_PROBE_0_DEBUG(hci1394_tlist_add_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_delete_enter,
HCI1394_TNF_HAL_STACK, "");
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);
TNF_PROBE_0_DEBUG(hci1394_tlist_delete_exit,
HCI1394_TNF_HAL_STACK, "");
return (DDI_FAILURE);
}
hci1394_tlist_remove(tlist_handle, node);
mutex_exit(&tlist_handle->tl_mutex);
TNF_PROBE_0_DEBUG(hci1394_tlist_delete_exit, HCI1394_TNF_HAL_STACK, "");
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);
TNF_PROBE_0_DEBUG(hci1394_tlist_get_enter, HCI1394_TNF_HAL_STACK, "");
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);
TNF_PROBE_0_DEBUG(hci1394_tlist_get_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_peek_enter, HCI1394_TNF_HAL_STACK, "");
mutex_enter(&tlist_handle->tl_mutex);
*node = tlist_handle->tl_head;
mutex_exit(&tlist_handle->tl_mutex);
TNF_PROBE_0_DEBUG(hci1394_tlist_peek_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_update_timeout_enter,
HCI1394_TNF_HAL_STACK, "");
/* set timeout to the new timeout */
tlist_handle->tl_timer_info.tlt_timeout = timeout;
TNF_PROBE_0_DEBUG(hci1394_tlist_update_timeout_exit,
HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_timeout_cancel_enter,
HCI1394_TNF_HAL_STACK, "");
/*
* 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;
}
TNF_PROBE_0_DEBUG(hci1394_tlist_timeout_cancel_exit,
HCI1394_TNF_HAL_STACK, "");
}
/*
* 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);
TNF_PROBE_0_DEBUG(hci1394_tlist_callback_enter,
HCI1394_TNF_HAL_STACK, "");
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);
TNF_PROBE_0_DEBUG(hci1394_tlist_callback_exit,
HCI1394_TNF_HAL_STACK, "");
}
/*
* 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));
TNF_PROBE_0_DEBUG(hci1394_tlist_remove_enter,
HCI1394_TNF_HAL_STACK, "");
/* 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;
TNF_PROBE_0_DEBUG(hci1394_tlist_remove_exit, HCI1394_TNF_HAL_STACK, "");
}
/*
* 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)));
}