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