xref: /illumos-gate/usr/src/uts/common/io/1394/adapters/hci1394_tlist.c (revision 2570281cf351044b6936651ce26dbe1f801dcbd8)
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
hci1394_tlist_init(hci1394_drvinfo_t * drvinfo,hci1394_tlist_timer_t * timer,hci1394_tlist_handle_t * tlist_handle)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
hci1394_tlist_fini(hci1394_tlist_handle_t * tlist_handle)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
hci1394_tlist_add(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t * node)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
hci1394_tlist_delete(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t * node)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
hci1394_tlist_get(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t ** node)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
hci1394_tlist_peek(hci1394_tlist_handle_t tlist_handle,hci1394_tlist_node_t ** node)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
hci1394_tlist_timeout_update(hci1394_tlist_handle_t tlist_handle,hrtime_t timeout)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
hci1394_tlist_timeout_cancel(hci1394_tlist_handle_t tlist_handle)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
hci1394_tlist_callback(void * tlist_handle)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
hci1394_tlist_remove(hci1394_tlist_t * list,hci1394_tlist_node_t * node)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))
t1394_tlist_nsectohz(hrtime_t nS)466 static clock_t t1394_tlist_nsectohz(hrtime_t  nS)
467 {
468 	return (drv_usectohz(HCI1394_TLIST_nS_TO_uS(nS)));
469 }
470