![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to timeout.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / streams / src|
Return to timeout.c CVS log | Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / streams / src |
1.1 root 1: #define _DDI_DKI 1
2: #define _DDI_DKI_IMPL 1
3: #define _SYSV4 1
4:
5: /*
6: * This file contains functions relating to the implementation of DDI/DKI
7: * timeout functions.
8: */
9: /*
10: *-IMPORTS:
11: * <common/ccompat.h>
12: * __USE_PROTO__
13: * __ARGS ()
14: * <kernel/ddi_glob.h>
15: * ddi_global_data ()
16: * <kernel/ddi_cpu.h>
17: * ddi_cpu_ref ()
18: * ddi_cpu_unref ()
19: * ddi_cpu_id ()
20: * <kernel/ddi_lock.h>
21: * timeout_global_hierarchy
22: * timeout_global_priority
23: * <kernel/defer.h>
24: * defer_int_cpu ()
25: * defer_int_here ()
26: * <sys/debug.h>
27: * ASSERT ()
28: * <sys/types.h>
29: * plhi
30: * pl_t
31: * toid_t
32: * __tfuncp_t
33: * <sys/inline.h>
34: * splx ()
35: * <sys/ksynch.h>
36: * LOCK_ALLOC ()
37: * LOCK_DEALLOC ()
38: * LOCK ()
39: * UNLOCK ()
40: * <sys/kmem.h>
41: * KM_NOSLEEP
42: * kmem_alloc ()
43: * kmem_free ()
44: * <sys/cmn_err.h>
45: * CE_PANIC
46: * cmn_err ()
47: */
48:
49: #include <common/ccompat.h>
50: #include <kernel/ddi_glob.h>
51: #include <kernel/ddi_cpu.h>
52: #include <kernel/ddi_lock.h>
53: #include <kernel/defer.h>
54: #include <sys/debug.h>
55: #include <sys/types.h>
56: #include <sys/inline.h>
57: #include <sys/ksynch.h>
58: #include <sys/kmem.h>
59: #include <sys/cmn_err.h>
60:
61: /*
62: * This code doesn't (yet) use the ddi_global_data () and ddi_cpu_data ()
63: * mechanisms. It will need to in order to support the dtimeout () call to
64: * bind a timeout to a specific CPU. However, this has been left pending
65: * investigation of how we want to specify CPU ids...
66: *
67: * So, at some stage the TIMEOUT_GLOBAL_... (), SCHEDULE_TIMEOUT () and
68: * STREAMS_TIMEOUT () functions may be parameterized.
69: */
70:
71:
72: /*
73: * All the global data this file uses in one handy place.
74: *
75: * How to do timeouts? I've always been a big fan of delta-queues.
76: * How to manage untimeout ()?
77: *
78: * The cancellation procedure is seriously complicated by the need for cancel
79: * attempts to block until completion if the timeout has begun. What we
80: * implement here is similar to a ticket lock, although we use a single global
81: * basic lock to guarantee write atomicity rather than a test-and-set lock.
82: * t_ticket t_ticket_holder
83: * 0 0 Cell pending activation.
84: * 1 0 Cell activated.
85: * 1 1 Cell processed.
86: * m n m != n, cancel attempts n + 1
87: * through m pending.
88: *
89: * Whoever finds "t_ticket" and "t_ticket_holder" equal (to their number, of
90: * course) has responsibility for deallocating the lock structure. The timeout
91: * activation code always has responsibility for dequeuing the lock once it has
92: * been activated; this avoids having the pending cancels rescan the list to
93: * dequeue the cell, and also ensures that untimeout () calls will simply
94: * return rather than joining the queue if the timeout function has finished.
95: *
96: * Using a simple state code might seem simpler... but we have a special
97: * problem here, in that we want to return the memory occupied by the event
98: * cell (and its state code) to the heap. Using the ticket system, we get
99: * acknowledgement from all the contexts that were interested in the state of
100: * the cell that they are no longer interested in it.
101: */
102:
103: struct timeout {
104: timeout_t * t_next;
105: __clock_t t_delta;
106: toid_t t_id;
107: processorid_t t_cpu;
108:
109: atomic_uchar_t t_ticket; /* next ticket */
110: atomic_uchar_t t_ticket_holder; /* who holds the ticket */
111:
112: __tfuncp_t t_funcp; /* function to call */
113: _VOID * t_arg; /* argument for function */
114: lock_t * t_lockp; /* basic lock to acquire */
115: pl_t t_pl; /* priority level for call */
116: };
117:
118: __LOCAL__ lkinfo_t _timeout_lkinfo = {
119: "timeout global lock", INTERNAL_LOCK
120: };
121:
122:
123: #define TIMEDATA() (& ddi_global_data ()->dg_timeouts)
124:
125: #define TIMEOUT_GLOBAL_LOCK() \
126: (ASSERT (TIMEDATA ()->td_lock != NULL), \
127: LOCK (TIMEDATA ()->td_lock, timeout_global_priority))
128:
129: #define TIMEOUT_GLOBAL_UNLOCK(p) UNLOCK (TIMEDATA ()->td_lock, (p))
130:
131:
132:
133: /*
134: * This internal function is called whenever there are timeout routines
135: * waiting to be processed by a particular CPU.
136: */
137:
138: #if __USE_PROTO__
139: __LOCAL__ void (RUN_TIMEOUTS) (void)
140: #else
141: __LOCAL__ void
142: RUN_TIMEOUTS __ARGS (())
143: #endif
144: {
145: pl_t prev_pl;
146: timeout_t * scan;
147: timeout_t * next;
148: timeout_t * free_list;
149: processorid_t my_id = ddi_cpu_id ();
150: int lock_failed = 0;
151:
152: prev_pl = TIMEOUT_GLOBAL_LOCK ();
153:
154:
155: /*
156: * Run all the events that belong to this CPU.
157: */
158:
159: for (scan = TIMEDATA ()->td_run ; scan != TIMEDATA ()->td_first ;
160: scan = scan->t_next) {
161:
162: if (scan->t_cpu != my_id)
163: continue;
164:
165: if (ATOMIC_FETCH_UCHAR (scan->t_ticket) > 0) {
166: /*
167: * This entry is going to be deleted. Don't run it.
168: */
169:
170: continue;
171: }
172:
173:
174: /*
175: * Before we commit to running the timeout function, we need
176: * to check that the timeout function can acquire the basic
177: * lock that it needs.
178: */
179:
180: if (scan->t_lockp != NULL &&
181: TRYLOCK (scan->t_lockp, plhi) == invpl) {
182: /*
183: * Try the next event cell, after we remember that an
184: * event cell failed to get a lock.
185: */
186:
187: lock_failed = 1;
188: continue;
189: }
190:
191:
192: /*
193: * OK, stop other CPUs from processing this entry and make
194: * cancel requests block until we are finished.
195: */
196:
197: ATOMIC_STORE_UCHAR (scan->t_ticket, 1);
198:
199: TIMEOUT_GLOBAL_UNLOCK (scan->t_pl);
200:
201:
202: /*
203: * Now execute the user function as requested. Note that we
204: * set the interrupt priority level to "scan->t_pl" even
205: * though we passed that value to UNLOCK (), since an
206: * implementation is permitted to ignore the "pl" argument to
207: * UNLOCK ().
208: *
209: * If we acquired a lock on behalf of the timeout function, we
210: * release it after the function runs.
211: */
212:
213: (void) splx (scan->t_pl);
214:
215: (* scan->t_funcp) (scan->t_arg);
216:
217: if (scan->t_lockp != NULL)
218: UNLOCK (scan->t_lockp, prev_pl);
219:
220: (void) splx (prev_pl);
221:
222:
223: /*
224: * Now we relock the list and mark this cell as finished. If
225: * a delete request for the cell has come in, let it proceed
226: * now that the function has been run.
227: */
228:
229: prev_pl = TIMEOUT_GLOBAL_LOCK ();
230:
231: ATOMIC_STORE_UCHAR (scan->t_ticket_holder, 1);
232: }
233:
234:
235: /*
236: * Run over the list of expired events and move any that have been
237: * completed to a work list for deletion.
238: */
239:
240: free_list = NULL;
241:
242: for (scan = TIMEDATA ()->td_run ; scan != TIMEDATA ()->td_first ;
243: scan = next) {
244:
245: /*
246: * If this event cell is in the throes of deletion, try again
247: * later. If there is an event which has not yet been run,
248: * don't clean up any more.
249: */
250:
251: if (ATOMIC_FETCH_UCHAR (scan->t_ticket_holder) !=
252: ATOMIC_FETCH_UCHAR (scan->t_ticket)) {
253:
254: lock_failed = 1;
255: break;
256: }
257:
258: if (ATOMIC_FETCH_UCHAR (scan->t_ticket) == 0)
259: break;
260:
261: /*
262: * Move the cell to the work list.
263: */
264:
265: next = scan->t_next;
266: scan->t_next = free_list;
267: free_list = scan;
268: }
269:
270: TIMEDATA ()->td_run = scan;
271:
272:
273: /*
274: * If we have run (and freed) all the events that we can, clear the
275: * run flag, otherwise defer this function again by way of backing off
276: * from the locks we failed.
277: */
278:
279: if (lock_failed)
280: defer_int_here (RUN_TIMEOUTS);
281: else
282: ATOMIC_STORE_UCHAR (ddi_cpu_data ()->dc_run_timeouts, 0);
283:
284: TIMEOUT_GLOBAL_UNLOCK (prev_pl);
285:
286:
287: /*
288: * Free any timeout cells that we were able to reap.
289: */
290:
291: while ((scan = free_list) != NULL) {
292:
293: free_list = scan->t_next;
294:
295: kmem_free (scan, sizeof (* scan));
296: }
297: }
298:
299:
300: /*
301: * Code from STREAMS_TIMEOUT () to schedule a single timeout event, factored
302: * out here to keep STREAMS_TIMEOUT () manageable.
303: */
304:
305: #if __USE_PROTO__
306: __LOCAL__ __INLINE__ void SCHEDULE_TIMEOUT (timeout_t * timep)
307: #else
308: __LOCAL__ __INLINE__ void
309: SCHEDULE_TIMEOUT __ARGS ((timep))
310: timeout_t * timep;
311: #endif
312: {
313: dcdata_t * dcdatap;
314:
315: if (timep->t_cpu == NOCPU)
316: timep->t_cpu = ddi_cpu_id ();
317:
318: dcdatap = ddi_cpu_ref (timep->t_cpu);
319:
320: ASSERT (dcdatap != NULL);
321:
322: if (ATOMIC_FETCH_UCHAR (dcdatap->dc_run_timeouts) == 0) {
323: /*
324: * Schedule the routine to actually run the timeouts.
325: */
326:
327: defer_int_cpu (RUN_TIMEOUTS, timep->t_cpu);
328: ATOMIC_STORE_UCHAR (dcdatap->dc_run_timeouts, 1);
329: }
330: }
331:
332:
333: /*
334: * This internal function is called once for each clock tick of real time that
335: * passes in the system overall. It may be that several instances get to run
336: * simultaneously in different CPUs if things get bogged down, but the basic
337: * idea is that the function gets called once per clock tick.
338: */
339:
340: __EXTERN_C__
341: #if __USE_PROTO__
342: void (STREAMS_TIMEOUT) (void)
343: #else
344: void
345: STREAMS_TIMEOUT __ARGS (())
346: #endif
347: {
348: pl_t prev_pl;
349: timeout_t * scan;
350:
351: prev_pl = TIMEOUT_GLOBAL_LOCK ();
352:
353: /*
354: * Now that we have the timeout queue locked, decrement the delta
355: * value of the entry at the front of the queue. After that, work out
356: * whether any entries have been triggered as a result.
357: */
358:
359: if ((scan = TIMEDATA ()->td_first) != NULL) {
360:
361: ASSERT (scan->t_delta > 0);
362:
363: if (-- scan->t_delta == 0) {
364:
365: if (TIMEDATA ()->td_run == NULL)
366: TIMEDATA ()->td_run = scan;
367:
368: /*
369: * At least one entry has been set off. Loop over the
370: * entries, notifying each CPU that has an event bound
371: * to it. If an event is not bound to any CPU, bind it
372: * to the current CPU.
373: */
374:
375: do
376: SCHEDULE_TIMEOUT (scan);
377: while ((scan = scan->t_next) != NULL &&
378: scan->t_delta == 0);
379:
380: TIMEDATA ()->td_first = scan;
381: }
382: }
383:
384: TIMEOUT_GLOBAL_UNLOCK (prev_pl);
385: }
386:
387:
388: /*
389: * This internal function factors out the common elements of timer event
390: * scheduling from itimeout () and ltimeout ().
391: */
392:
393: #if __USE_PROTO__
394: __LOCAL__ toid_t (QUEUE_TIMEOUT) (__tfuncp_t fn, _VOID * arg, __clock_t ticks,
395: lock_t * lockp, processorid_t cpu, pl_t pl)
396: #else
397: __LOCAL__ toid_t
398: QUEUE_TIMEOUT __ARGS ((fn, arg, ticks, lockp, cpu, pl))
399: __tfuncp_t fn;
400: _VOID * arg;
401: __clock_t ticks;
402: lock_t * lockp;
403: processorid_t cpu;
404: pl_t pl;
405: #endif
406: {
407: pl_t prev_pl;
408: timeout_t * timep;
409: timeout_t * scan;
410: timeout_t * prev;
411:
412: if ((timep = (timeout_t *) kmem_alloc (sizeof (* timep),
413: KM_NOSLEEP)) == NULL)
414: return 0;
415:
416: timep->t_funcp = fn;
417: timep->t_arg = arg;
418: timep->t_pl = pl;
419: timep->t_lockp = lockp;
420: timep->t_cpu = cpu;
421: ATOMIC_STORE_UCHAR (timep->t_ticket, 0);
422: ATOMIC_STORE_UCHAR (timep->t_ticket_holder, 0);
423:
424: if (ticks == 0)
425: ticks = 1;
426:
427: /*
428: * Having created and mostly filled in the timeout structure, we now
429: * lock the delta-queue and try and find the place where our structure
430: * needs to be inserted.
431: *
432: * We also use the delta-queue lock to protect our access to the
433: * timeout ID generator. Since it is in theory possible to wrap around
434: * the ID space, the delta-queue walk will look for a duplicate ID.
435: * We make the simplifying assumption that anything that has lived
436: * that long isn't going to be cancelled anytime soon, so that it
437: * suffices to protect the newer entry from having it's cancel code
438: * shadowed.
439: */
440:
441: prev_pl = TIMEOUT_GLOBAL_LOCK ();
442:
443: id_scan:
444: if (TIMEDATA ()->td_id == 0)
445: TIMEDATA ()->td_id = 1;
446:
447: timep->t_id = TIMEDATA ()->td_id ++;
448:
449: /*
450: * We have to deal with the fact that the true first element in the
451: * timeout delta-queue may be represented by either of two pointers.
452: * Since timeouts that have been scheduled to run have a zero
453: * "t_delta", searching those entries won't disrupt the delta-queue,
454: * and until they have been dequeued their timeout id's are still
455: * valid.
456: */
457:
458: if ((scan = TIMEDATA ()->td_run) == NULL)
459: scan = TIMEDATA ()->td_first;
460:
461: for (prev = NULL ; scan != NULL ; scan = (prev = scan)->t_next) {
462:
463: if (scan->t_id == timep->t_id)
464: goto id_scan;
465:
466: if (ticks < scan->t_delta) {
467: /*
468: * OK, we have found our spot. Now we insert our new
469: * cell in front of the one we have just found.
470: */
471:
472: scan->t_delta -= ticks;
473: break;
474: }
475:
476: ticks -= scan->t_delta;
477: }
478:
479: timep->t_delta = ticks;
480: timep->t_next = scan;
481:
482: if (scan == TIMEDATA ()->td_first)
483: TIMEDATA ()->td_first = timep;
484:
485: if (prev != NULL)
486: prev->t_next = timep;
487:
488: TIMEOUT_GLOBAL_UNLOCK (prev_pl);
489:
490: return timep->t_id;
491: }
492:
493:
494: /*
495: * This internal function is a direct equivalent to itimeout (), with the
496: * following additional behaviour; the caller supplies the address of a basic
497: * lock which this code will attempt to acquire before running the timeout
498: * function. If the lock cannot be acquired immediately, the next timeout
499: * function will be considered.
500: *
501: * This behaviour allows untimeout () to be safely used to cancel the timeout
502: * request while holding the basic lock that this function will attempt to
503: * acquire.
504: *
505: * A "timeout" value of NULL yields identical behaviour to itimeout ().
506: */
507:
508: #if __USE_PROTO__
509: toid_t (ltimeout) (__tfuncp_t fn, _VOID * arg, __clock_t ticks,
510: lock_t * lockp, pl_t pl)
511: #else
512: toid_t
513: ltimeout __ARGS ((fn, arg, ticks, lockp, pl))
514: __tfuncp_t fn;
515: _VOID * arg;
516: __clock_t ticks;
517: lock_t * lockp;
518: pl_t pl;
519: #endif
520: {
521: ASSERT (fn != (__tfuncp_t) NULL);
522: ASSERT (lockp != NULL);
523:
524: return QUEUE_TIMEOUT (fn, arg, ticks, lockp, NOCPU, pl);
525: }
526:
527:
528: /*
529: *-STATUS:
530: * DDI/DKI
531: *
532: *-NAME:
533: * itimeout Execute a function after a specified length of time.
534: *
535: *-SYNOPSIS:
536: * #include <sys/types.h>
537: *
538: * toid_t itimeout (void (* fn) (), void * arg, long ticks, pl_t pl);
539: *
540: *-ARGUMENTS:
541: * fn Function to execute when the time interval expires.
542: *
543: * arg Argument to the function.
544: *
545: * ticks Number of clock ticks to wait before the function is
546: * called.
547: *
548: * pl The interrupt priority level at which the function
549: * will be called. "pl" must specify a priority level
550: * greater than or equal to "pltimeout"; thus, "plbase"
551: * cannot not be used. See LOCK_ALLOC () for a list of
552: * values for "pl".
553: *
554: *-DESCRIPTION:
555: * itimeout () causes the function specified by "fn" to be called after
556: * the time interval specified by "ticks", at the interrupt priority
557: * specified by "pl". "arg" will be passed as the only argument to
558: * function "fn". The itimeout () call returns immediately without
559: * waiting for the specified function to execute.
560: *
561: * The length of time before the function is called is not guaranteed to
562: * be exactly equal to the requested time, but will be at least "ticks-1"
563: * clock ticks in length. The function specified by "fn" must neither
564: * sleep nor reference process context.
565: *
566: *-RETURN VALUE:
567: * If the function specfied by "fn" is successfully scheduled,
568: * itimeout () returns a non-zero identifier that can be passed to
569: * untimeout () to cancel the request. If the function could not be
570: * scheduled, itimeout () returns a value of 0.
571: *
572: *-LEVEL:
573: * Base or Interrupt.
574: *
575: *-NOTES:
576: * Does not sleep.
577: *
578: * Driver-defined basic locks, read/write locks, and sleep locks may be
579: * held across calls to this function.
580: *
581: * Drivers should be careful to cancel any pending itimeout () functions
582: * that access data structures before these structures are de-initialized
583: * or deallocated.
584: *
585: * After the time interval has expired, "fn" only runs if the processor
586: * is at base level. Otherwise, "fn" is deferred until sometime in the
587: * near future.
588: *
589: * If itimeout () is called holding a lock that is contended for by "fn",
590: * the caller must hold the lock at a processor level greater than the
591: * base processor level.
592: *
593: * A "ticks" argument of 0 has the same effect as a "ticks" argument of
594: * 1. Both will result in an approximate wait of between 0 and 1 tick
595: * (possibly longer).
596: *
597: *-SEE ALSO:
598: * LOCK_ALLOC (), untimeout ()
599: */
600:
601: #if __USE_PROTO__
602: toid_t (itimeout) (__tfuncp_t fn, _VOID * arg, __clock_t ticks, pl_t pl)
603: #else
604: toid_t
605: itimeout __ARGS ((fn, arg, ticks, pl))
606: __tfuncp_t * fn;
607: _VOID * arg;
608: __clock_t ticks;
609: pl_t pl;
610: #endif
611: {
612: ASSERT (fn != (__tfuncp_t) NULL);
613:
614: return QUEUE_TIMEOUT (fn, arg, ticks, NULL, NOCPU, pl);
615: }
616:
617:
618: /*
619: *-STATUS:
620: * DDI/DKI
621: *
622: *-NAME:
623: * untimeout Cancel previous timeout request.
624: *
625: *-SYNOPSIS:
626: * #include <sys/types.h>
627: *
628: * void untimeout (toid_t id);
629: *
630: *-ARGUMENTS:
631: * id Identifier returned from a previous call to
632: * itimeout ().
633: *
634: *-DESCRIPTION:
635: * untimeout () cancels a previous timeout request. If the untimeout ()
636: * is called while the function is running, then untimeout () will not
637: * return until the function has completed. The function that runs as a
638: * result of itimeout () cannot use untimeout () to cancel itself.
639: *
640: *-RETURN VALUE:
641: * None.
642: *
643: *-LEVEL:
644: * Base or interrupt, with the following exception; the untimeout () can
645: * only be performed from interrupt levels less than, or equal to, the
646: * level specified when the function was scheduled.
647: *
648: *-NOTES:
649: * Does not sleep.
650: *
651: * Driver-defined basic locks, read/write locks, and sleep locks may not
652: * be held across calls to this function if these locks are contended by
653: * the function being scheduled.
654: *
655: *-SEE ALSO:
656: * delay (), itimeout (), unbufcall ()
657: */
658:
659: #if __USE_PROTO__
660: void (untimeout) (toid_t id)
661: #else
662: void
663: untimeout __ARGS ((id))
664: toid_t id;
665: #endif
666: {
667: pl_t prev_pl;
668: timeout_t * scan;
669:
670: prev_pl = TIMEOUT_GLOBAL_LOCK ();
671:
672: for (scan = TIMEDATA ()->td_first ; scan != NULL ;
673: scan = scan->t_next) {
674: unsigned short ticket;
675:
676: if (scan->t_id != id)
677: continue;
678:
679: /*
680: * Take a ticket, and wait for the cell's event routine to
681: * finish. If it was not running before we took a ticket, it
682: * never will.
683: */
684:
685: ticket = ATOMIC_FETCH_UCHAR (scan->t_ticket);
686: ATOMIC_STORE_UCHAR (scan->t_ticket, ticket + 1);
687:
688: scan->t_cpu = ddi_cpu_id ();
689:
690: if (ticket != ATOMIC_FETCH_UCHAR (scan->t_ticket_holder)) {
691: /*
692: * Wait for the event routine to complete.
693: */
694:
695: TIMEOUT_GLOBAL_UNLOCK (prev_pl);
696:
697: while (ATOMIC_FETCH_UCHAR (scan->t_ticket_holder)
698: != ticket)
699: ; /* DO NOTHING */
700:
701:
702: prev_pl = TIMEOUT_GLOBAL_LOCK ();
703: }
704:
705:
706: /*
707: * Pass it on to the next guy.
708: */
709:
710: ATOMIC_STORE_UCHAR (scan->t_ticket_holder, ticket + 1);
711: }
712:
713: TIMEOUT_GLOBAL_UNLOCK (prev_pl);
714: }
715:
716:
717: /*
718: * Set up the timeout globals. This function is called via the 'mdevice' init
719: * function table.
720: */
721:
722: __EXTERN_C__
723: #if __USE_PROTO__
724: int (timeout_init) (void)
725: #else
726: int
727: timeout_init __ARGS (())
728: #endif
729: {
730: TIMEDATA ()->td_lock = LOCK_ALLOC (timeout_global_hierarchy,
731: timeout_global_priority,
732: & _timeout_lkinfo, KM_SLEEP);
733:
734: return TIMEDATA ()->td_lock == NULL;
735: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.