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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22/* 23 * Copyright (c) 1999-2000 by Sun Microsystems, Inc. 24 * All rights reserved. 25 */ 26 27#pragma ident "%Z%%M% %I% %E% SMI" 28 29/* 30 * hci1394_tlist.c 31 * This implements a timed double linked list. 32 * This list supports: 33 * - addition of node to the end of the list 34 * - atomic deletion of node anywhere in list 35 * - get and remove node from head of list 36 * - enable/disable of timeout feature 37 * - timeout feature, if enabled, will remove each node on the list which 38 * has been on the list for > timeout. The callback provided will be 39 * called for each node removed. The worst case time is around 40 * timer_resolution after the timeout has occurred (i.e. if you set the 41 * timer resolution to 50uS and the timeout to 100uS, you could get the 42 * callback anywhere from 100uS to 150uS from when you added the node to 43 * the list. This is a general statement and ignores things like 44 * interrupt latency, context switching, etc. So if you see a time 45 * around 155uS, don't complain :-) 46 * - The timer is only used when something is on the list 47 */ 48 49#include <sys/kmem.h> 50#include <sys/types.h> 51#include <sys/conf.h> 52#include <sys/ddi.h> 53#include <sys/sunddi.h> 54#include <sys/types.h> 55 56#include <sys/1394/adapters/hci1394.h> 57 58 59static clock_t t1394_tlist_nsectohz(hrtime_t nS); 60static void hci1394_tlist_remove(hci1394_tlist_t *list, 61 hci1394_tlist_node_t *node); 62static void hci1394_tlist_callback(void *tlist_handle); 63 64 65/* 66 * hci1394_tlist_init() 67 * Initialize the tlist. The list will be protected by a mutex at the 68 * iblock_cookie passed in. init() returns a handle to be used for the rest 69 * of the functions. If you do not wish to use the timeout feature, set 70 * (hci1394_timer_t *) to null. 71 */ 72void 73hci1394_tlist_init(hci1394_drvinfo_t *drvinfo, hci1394_tlist_timer_t *timer, 74 hci1394_tlist_handle_t *tlist_handle) 75{ 76 hci1394_tlist_t *list; 77 78 79 ASSERT(tlist_handle != NULL); 80 TNF_PROBE_0_DEBUG(hci1394_tlist_init_enter, HCI1394_TNF_HAL_STACK, ""); 81 82 /* try to alloc the space to keep track of the list */ 83 list = kmem_alloc(sizeof (hci1394_tlist_t), KM_SLEEP); 84 85 /* setup the return parameter */ 86 *tlist_handle = list; 87 88 /* initialize the list structure */ 89 list->tl_drvinfo = drvinfo; 90 list->tl_state = HCI1394_TLIST_TIMEOUT_OFF; 91 list->tl_head = NULL; 92 list->tl_tail = NULL; 93 if (timer == NULL) { 94 list->tl_timer_enabled = B_FALSE; 95 } else { 96 ASSERT(timer->tlt_callback != NULL); 97 list->tl_timer_enabled = B_TRUE; 98 list->tl_timer_info = *timer; 99 } 100 mutex_init(&list->tl_mutex, NULL, MUTEX_DRIVER, 101 drvinfo->di_iblock_cookie); 102 103 TNF_PROBE_0_DEBUG(hci1394_tlist_init_exit, HCI1394_TNF_HAL_STACK, ""); 104} 105 106 107/* 108 * hci1394_tlist_fini() 109 * Frees up the space allocated in init(). Notice that a pointer to the 110 * handle is used for the parameter. fini() will set your handle to NULL 111 * before returning. Make sure that any pending timeouts are canceled. 112 */ 113void 114hci1394_tlist_fini(hci1394_tlist_handle_t *tlist_handle) 115{ 116 hci1394_tlist_t *list; 117 118 119 ASSERT(tlist_handle != NULL); 120 TNF_PROBE_0_DEBUG(hci1394_tlist_fini_enter, HCI1394_TNF_HAL_STACK, ""); 121 122 list = (hci1394_tlist_t *)*tlist_handle; 123 hci1394_tlist_timeout_cancel(list); 124 mutex_destroy(&list->tl_mutex); 125 kmem_free(list, sizeof (hci1394_tlist_t)); 126 127 /* set handle to null. This helps catch bugs. */ 128 *tlist_handle = NULL; 129 130 TNF_PROBE_0_DEBUG(hci1394_tlist_fini_exit, HCI1394_TNF_HAL_STACK, ""); 131} 132 133 134/* 135 * hci1394_tlist_add() 136 * Add the node to the tail of the linked list. The list is protected by a 137 * mutex at the iblock_cookie passed in during init. 138 */ 139void 140hci1394_tlist_add(hci1394_tlist_handle_t tlist_handle, 141 hci1394_tlist_node_t *node) 142{ 143 ASSERT(tlist_handle != NULL); 144 ASSERT(node != NULL); 145 TNF_PROBE_0_DEBUG(hci1394_tlist_add_enter, HCI1394_TNF_HAL_STACK, ""); 146 147 mutex_enter(&tlist_handle->tl_mutex); 148 149 /* add's always go at the end of the list */ 150 node->tln_next = NULL; 151 152 /* Set state that this node is currently on the tlist */ 153 node->tln_on_list = B_TRUE; 154 155 /* enter in the expire time (in uS) */ 156 if (tlist_handle->tl_timer_enabled == B_TRUE) { 157 node->tln_expire_time = gethrtime() + 158 tlist_handle->tl_timer_info.tlt_timeout; 159 } 160 161 /* if there is nothing in the list */ 162 if (tlist_handle->tl_tail == NULL) { 163 tlist_handle->tl_head = node; 164 tlist_handle->tl_tail = node; 165 node->tln_prev = NULL; 166 167 if ((tlist_handle->tl_timer_enabled == B_TRUE) && 168 (tlist_handle->tl_state == HCI1394_TLIST_TIMEOUT_OFF)) { 169 /* turn the timer on */ 170 tlist_handle->tl_timeout_id = timeout( 171 hci1394_tlist_callback, tlist_handle, 172 t1394_tlist_nsectohz( 173 tlist_handle->tl_timer_info.tlt_timer_resolution)); 174 tlist_handle->tl_state = HCI1394_TLIST_TIMEOUT_ON; 175 } 176 } else { 177 /* put the node on the end of the list */ 178 tlist_handle->tl_tail->tln_next = node; 179 node->tln_prev = tlist_handle->tl_tail; 180 tlist_handle->tl_tail = node; 181 /* 182 * if timeouts are enabled, we don't have to call 183 * timeout() because the timer is already on. 184 */ 185 } 186 187 mutex_exit(&tlist_handle->tl_mutex); 188 189 TNF_PROBE_0_DEBUG(hci1394_tlist_add_exit, HCI1394_TNF_HAL_STACK, ""); 190} 191 192 193/* 194 * hci1394_tlist_delete() 195 * Remove the node from the list. The node can be anywhere in the list. Make 196 * sure that the node is only removed once since different threads maybe 197 * trying to delete the same node at the same time. 198 */ 199int 200hci1394_tlist_delete(hci1394_tlist_handle_t tlist_handle, 201 hci1394_tlist_node_t *node) 202{ 203 ASSERT(tlist_handle != NULL); 204 ASSERT(node != NULL); 205 TNF_PROBE_0_DEBUG(hci1394_tlist_delete_enter, 206 HCI1394_TNF_HAL_STACK, ""); 207 208 mutex_enter(&tlist_handle->tl_mutex); 209 210 /* 211 * check for race condition. Someone else may have already removed this 212 * node from the list. hci1394_tlist_delete() supports two threads 213 * trying to delete the node at the same time. The "losing" thread will 214 * have DDI_FAILURE returned. 215 */ 216 if (node->tln_on_list == B_FALSE) { 217 mutex_exit(&tlist_handle->tl_mutex); 218 TNF_PROBE_0_DEBUG(hci1394_tlist_delete_exit, 219 HCI1394_TNF_HAL_STACK, ""); 220 return (DDI_FAILURE); 221 } 222 223 hci1394_tlist_remove(tlist_handle, node); 224 mutex_exit(&tlist_handle->tl_mutex); 225 226 TNF_PROBE_0_DEBUG(hci1394_tlist_delete_exit, HCI1394_TNF_HAL_STACK, ""); 227 return (DDI_SUCCESS); 228} 229 230 231/* 232 * hci1394_tlist_get() 233 * get the node at the head of the linked list. This function also removes 234 * the node from the list. 235 */ 236void 237hci1394_tlist_get(hci1394_tlist_handle_t tlist_handle, 238 hci1394_tlist_node_t **node) 239{ 240 ASSERT(tlist_handle != NULL); 241 ASSERT(node != NULL); 242 TNF_PROBE_0_DEBUG(hci1394_tlist_get_enter, HCI1394_TNF_HAL_STACK, ""); 243 244 mutex_enter(&tlist_handle->tl_mutex); 245 246 /* set the return parameter */ 247 *node = tlist_handle->tl_head; 248 249 /* remove the node from the tlist */ 250 if (*node != NULL) { 251 hci1394_tlist_remove(tlist_handle, *node); 252 } 253 254 mutex_exit(&tlist_handle->tl_mutex); 255 256 TNF_PROBE_0_DEBUG(hci1394_tlist_get_exit, HCI1394_TNF_HAL_STACK, ""); 257} 258 259 260/* 261 * hci1394_tlist_peek() 262 * get the node at the head of the linked list. This function does not 263 * remove the node from the list. 264 */ 265void 266hci1394_tlist_peek(hci1394_tlist_handle_t tlist_handle, 267 hci1394_tlist_node_t **node) 268{ 269 ASSERT(tlist_handle != NULL); 270 ASSERT(node != NULL); 271 TNF_PROBE_0_DEBUG(hci1394_tlist_peek_enter, HCI1394_TNF_HAL_STACK, ""); 272 273 mutex_enter(&tlist_handle->tl_mutex); 274 *node = tlist_handle->tl_head; 275 mutex_exit(&tlist_handle->tl_mutex); 276 277 TNF_PROBE_0_DEBUG(hci1394_tlist_peek_exit, HCI1394_TNF_HAL_STACK, ""); 278} 279 280 281/* 282 * hci1394_tlist_timeout_update() 283 * update the timeout to a different value. timeout is in uS. The update 284 * does not happen immediately. The new timeout will not take effect until 285 * the all of nodes currently present in the list are gone. It only makes 286 * sense to call this function when you have the timeout feature enabled. 287 */ 288void 289hci1394_tlist_timeout_update(hci1394_tlist_handle_t tlist_handle, 290 hrtime_t timeout) 291{ 292 ASSERT(tlist_handle != NULL); 293 TNF_PROBE_0_DEBUG(hci1394_tlist_update_timeout_enter, 294 HCI1394_TNF_HAL_STACK, ""); 295 296 /* set timeout to the new timeout */ 297 tlist_handle->tl_timer_info.tlt_timeout = timeout; 298 299 TNF_PROBE_0_DEBUG(hci1394_tlist_update_timeout_exit, 300 HCI1394_TNF_HAL_STACK, ""); 301} 302 303 304/* 305 * hci1394_tlist_timeout_cancel() 306 * cancel any scheduled timeouts. This should be called after the list is 307 * empty and there is no chance for any other nodes to be placed on the list. 308 * This function is meant to be called during a suspend or detach. 309 */ 310void 311hci1394_tlist_timeout_cancel(hci1394_tlist_handle_t tlist_handle) 312{ 313 ASSERT(tlist_handle != NULL); 314 TNF_PROBE_0_DEBUG(hci1394_tlist_timeout_cancel_enter, 315 HCI1394_TNF_HAL_STACK, ""); 316 317 /* 318 * Cancel the timeout. Do NOT use the tlist mutex here. It could cause a 319 * deadlock. 320 */ 321 if (tlist_handle->tl_state == HCI1394_TLIST_TIMEOUT_ON) { 322 (void) untimeout(tlist_handle->tl_timeout_id); 323 tlist_handle->tl_state = HCI1394_TLIST_TIMEOUT_OFF; 324 } 325 326 TNF_PROBE_0_DEBUG(hci1394_tlist_timeout_cancel_exit, 327 HCI1394_TNF_HAL_STACK, ""); 328} 329 330 331/* 332 * hci1394_tlist_callback() 333 * The callback we use for the timeout() function. See if there are any nodes 334 * on the list which have timed out. If so, call the registered callback for 335 * each timed out node. We always start looking at the top of the list since 336 * the list is time sorted (oldest at the top). 337 */ 338static void 339hci1394_tlist_callback(void *tlist_handle) 340{ 341 hci1394_tlist_t *list; 342 hci1394_tlist_node_t *node; 343 hrtime_t current_time; 344 345 346 ASSERT(tlist_handle != NULL); 347 TNF_PROBE_0_DEBUG(hci1394_tlist_callback_enter, 348 HCI1394_TNF_HAL_STACK, ""); 349 350 list = (hci1394_tlist_t *)tlist_handle; 351 352 mutex_enter(&list->tl_mutex); 353 354 /* 355 * if there is something on the list, check to see if the oldest has 356 * expired. If there is nothing on the list, there is no reason to 357 * renew the timeout. 358 */ 359 node = list->tl_head; 360 current_time = gethrtime(); 361 while (node != NULL) { 362 /* 363 * if current time is greater than the time the command expires, 364 * AND, the expire time has not rolled over, then the command 365 * has timed out. 366 */ 367 if (((uint64_t)current_time >= 368 (uint64_t)node->tln_expire_time) && 369 (((uint64_t)node->tln_expire_time - 370 (uint64_t)list->tl_timer_info.tlt_timeout) < 371 (uint64_t)node->tln_expire_time)) { 372 /* remove the node from the tlist */ 373 hci1394_tlist_remove(list, node); 374 375 /* 376 * Call the timeout callback. We unlock the the mutex 377 * around the callback so that other transactions will 378 * not be blocked while the callback is running. This 379 * is OK to do here because we have already removed this 380 * entry from our list. This code should not reference 381 * "node" again after the callback! After the callback 382 * returns, we need to resync node to the head of the 383 * list since we released/acquired the list mutex around 384 * the callback. 385 */ 386 mutex_exit(&list->tl_mutex); 387 list->tl_timer_info.tlt_callback(node, 388 list->tl_timer_info.tlt_callback_arg); 389 mutex_enter(&list->tl_mutex); 390 node = list->tl_head; 391 392 /* 393 * else, if current time is greater than the time the command 394 * expires, AND, current_time is not about to rollover. (this 395 * works since it is in the else and we periodically sample 396 * well below the rollover time) 397 */ 398 } else if ((uint64_t)(current_time >= 399 (uint64_t)node->tln_expire_time) && 400 (((uint64_t)current_time + 401 (uint64_t)list->tl_timer_info.tlt_timeout) > 402 (uint64_t)current_time)) { 403 /* remove the node from the tlist */ 404 hci1394_tlist_remove(list, node); 405 406 /* 407 * Call the timeout callback. We unlock the the mutex 408 * around the callback so that other transactions will 409 * not be blocked while the callback is running. This 410 * is OK to do here because we have already removed this 411 * entry from our list. This code should not reference 412 * "node" again after the callback! After the callback 413 * returns, we need to resync node to the head of the 414 * list since we released/acquired the list mutex around 415 * the callback. 416 */ 417 mutex_exit(&list->tl_mutex); 418 list->tl_timer_info.tlt_callback(node, 419 list->tl_timer_info.tlt_callback_arg); 420 mutex_enter(&list->tl_mutex); 421 node = list->tl_head; 422 423 } else { 424 /* 425 * this command has not timed out. 426 * Since this list is time sorted, we are 427 * done looking for nodes that have expired 428 */ 429 break; 430 } 431 } 432 433 /* 434 * if there are nodes still on the pending list, kick 435 * off the timer again. 436 */ 437 if (node != NULL) { 438 list->tl_timeout_id = timeout(hci1394_tlist_callback, list, 439 t1394_tlist_nsectohz( 440 list->tl_timer_info.tlt_timer_resolution)); 441 list->tl_state = HCI1394_TLIST_TIMEOUT_ON; 442 } else { 443 list->tl_state = HCI1394_TLIST_TIMEOUT_OFF; 444 } 445 446 mutex_exit(&list->tl_mutex); 447 448 TNF_PROBE_0_DEBUG(hci1394_tlist_callback_exit, 449 HCI1394_TNF_HAL_STACK, ""); 450} 451 452 453/* 454 * hci1394_tlist_remove() 455 * This is an internal function which removes the given node from the list. 456 * The list MUST be locked before calling this function. 457 */ 458static void 459hci1394_tlist_remove(hci1394_tlist_t *list, hci1394_tlist_node_t *node) 460{ 461 ASSERT(list != NULL); 462 ASSERT(node != NULL); 463 ASSERT(node->tln_on_list == B_TRUE); 464 ASSERT(MUTEX_HELD(&list->tl_mutex)); 465 TNF_PROBE_0_DEBUG(hci1394_tlist_remove_enter, 466 HCI1394_TNF_HAL_STACK, ""); 467 468 /* if this is the only node on the list */ 469 if ((list->tl_head == node) && 470 (list->tl_tail == node)) { 471 list->tl_head = NULL; 472 list->tl_tail = NULL; 473 474 /* if the node is at the head of the list */ 475 } else if (list->tl_head == node) { 476 list->tl_head = node->tln_next; 477 node->tln_next->tln_prev = NULL; 478 479 /* if the node is at the tail of the list */ 480 } else if (list->tl_tail == node) { 481 list->tl_tail = node->tln_prev; 482 node->tln_prev->tln_next = NULL; 483 484 /* if the node is in the middle of the list */ 485 } else { 486 node->tln_prev->tln_next = node->tln_next; 487 node->tln_next->tln_prev = node->tln_prev; 488 } 489 490 /* Set state that this node has been removed from the list */ 491 node->tln_on_list = B_FALSE; 492 493 /* cleanup the node's link pointers */ 494 node->tln_prev = NULL; 495 node->tln_next = NULL; 496 497 TNF_PROBE_0_DEBUG(hci1394_tlist_remove_exit, HCI1394_TNF_HAL_STACK, ""); 498} 499 500 501/* 502 * t1394_tlist_nsectohz() 503 * Convert nS to hz. This allows us to call timeout() but keep our time 504 * reference in nS. 505 */ 506#define HCI1394_TLIST_nS_TO_uS(nS) ((clock_t)(nS / 1000)) 507static clock_t t1394_tlist_nsectohz(hrtime_t nS) 508{ 509 return (drv_usectohz(HCI1394_TLIST_nS_TO_uS(nS))); 510} 511