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