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 
59 static clock_t t1394_tlist_nsectohz(hrtime_t  nS);
60 static void hci1394_tlist_remove(hci1394_tlist_t *list,
61     hci1394_tlist_node_t *node);
62 static 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  */
72 void
hci1394_tlist_init(hci1394_drvinfo_t * drvinfo,hci1394_tlist_timer_t * timer,hci1394_tlist_handle_t * tlist_handle)73 hci1394_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  */
113 void
hci1394_tlist_fini(hci1394_tlist_handle_t * tlist_handle)114 hci1394_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  */
139 void
hci1394_tlist_add(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t * node)140 hci1394_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  */
199 int
hci1394_tlist_delete(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t * node)200 hci1394_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  */
236 void
hci1394_tlist_get(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t ** node)237 hci1394_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  */
265 void
hci1394_tlist_peek(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t ** node)266 hci1394_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  */
288 void
hci1394_tlist_timeout_update(hci1394_tlist_handle_t tlist_handle,hrtime_t timeout)289 hci1394_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  */
310 void
hci1394_tlist_timeout_cancel(hci1394_tlist_handle_t tlist_handle)311 hci1394_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  */
338 static void
hci1394_tlist_callback(void * tlist_handle)339 hci1394_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  */
458 static void
hci1394_tlist_remove(hci1394_tlist_t * list,hci1394_tlist_node_t * node)459 hci1394_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))
t1394_tlist_nsectohz(hrtime_t nS)507 static clock_t t1394_tlist_nsectohz(hrtime_t  nS)
508 {
509 	return (drv_usectohz(HCI1394_TLIST_nS_TO_uS(nS)));
510 }
511