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