16391978657ed7a2b50727375778699b8fb95255
[dragonfly.git] / sys / kern / kern_timeout.c
1 /*
2  * Copyright (c) 2004 The DragonFly Project.  All rights reserved.
3  * 
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  * 
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 /*
35  * Copyright (c) 1982, 1986, 1991, 1993
36  *      The Regents of the University of California.  All rights reserved.
37  * (c) UNIX System Laboratories, Inc.
38  * All or some portions of this file are derived from material licensed
39  * to the University of California by American Telephone and Telegraph
40  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
41  * the permission of UNIX System Laboratories, Inc.
42  *
43  * Redistribution and use in source and binary forms, with or without
44  * modification, are permitted provided that the following conditions
45  * are met:
46  * 1. Redistributions of source code must retain the above copyright
47  *    notice, this list of conditions and the following disclaimer.
48  * 2. Redistributions in binary form must reproduce the above copyright
49  *    notice, this list of conditions and the following disclaimer in the
50  *    documentation and/or other materials provided with the distribution.
51  * 3. All advertising materials mentioning features or use of this software
52  *    must display the following acknowledgement:
53  *      This product includes software developed by the University of
54  *      California, Berkeley and its contributors.
55  * 4. Neither the name of the University nor the names of its contributors
56  *    may be used to endorse or promote products derived from this software
57  *    without specific prior written permission.
58  *
59  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69  * SUCH DAMAGE.
70  *
71  *      From: @(#)kern_clock.c  8.5 (Berkeley) 1/21/94
72  * $FreeBSD: src/sys/kern/kern_timeout.c,v 1.59.2.1 2001/11/13 18:24:52 archie Exp $
73  * $DragonFly: src/sys/kern/kern_timeout.c,v 1.27 2007/11/14 18:27:52 swildner Exp $
74  */
75 /*
76  * DRAGONFLY BGL STATUS
77  *
78  *      All the API functions should be MP safe.
79  *
80  *      The callback functions will be flagged as being MP safe if the
81  *      timeout structure is initialized with callout_init_mp() instead of
82  *      callout_init().
83  *
84  *      The helper threads cannot be made preempt-capable until after we
85  *      clean up all the uses of splsoftclock() and related interlocks (which
86  *      require the related functions to be MP safe as well).
87  */
88 /*
89  * The callout mechanism is based on the work of Adam M. Costello and 
90  * George Varghese, published in a technical report entitled "Redesigning
91  * the BSD Callout and Timer Facilities" and modified slightly for inclusion
92  * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
93  * used in this implementation was published by G. Varghese and T. Lauck in
94  * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for
95  * the Efficient Implementation of a Timer Facility" in the Proceedings of
96  * the 11th ACM Annual Symposium on Operating Systems Principles,
97  * Austin, Texas Nov 1987.
98  *
99  * The per-cpu augmentation was done by Matthew Dillon.
100  */
101
102 #include <sys/param.h>
103 #include <sys/systm.h>
104 #include <sys/callout.h>
105 #include <sys/kernel.h>
106 #include <sys/interrupt.h>
107 #include <sys/thread.h>
108
109 #include <sys/thread2.h>
110 #include <sys/mplock2.h>
111
112 #ifndef MAX_SOFTCLOCK_STEPS
113 #define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */
114 #endif
115
116
117 struct softclock_pcpu {
118         struct callout_tailq *callwheel;
119         struct callout * volatile next;
120         int softticks;          /* softticks index */
121         int curticks;           /* per-cpu ticks counter */
122         int isrunning;
123         struct thread thread;
124
125 };
126
127 typedef struct softclock_pcpu *softclock_pcpu_t;
128
129 /*
130  * TODO:
131  *      allocate more timeout table slots when table overflows.
132  */
133 static MALLOC_DEFINE(M_CALLOUT, "callout", "callout structures");
134 static int callwheelsize;
135 static int callwheelbits;
136 static int callwheelmask;
137 static struct softclock_pcpu softclock_pcpu_ary[MAXCPU];
138
139 static void softclock_handler(void *arg);
140
141 static void
142 swi_softclock_setup(void *arg)
143 {
144         int cpu;
145         int i;
146
147         /*
148          * Figure out how large a callwheel we need.  It must be a power of 2.
149          */
150         callwheelsize = 1;
151         callwheelbits = 0;
152         while (callwheelsize < ncallout) {
153                 callwheelsize <<= 1;
154                 ++callwheelbits;
155         }
156         callwheelmask = callwheelsize - 1;
157
158         /*
159          * Initialize per-cpu data structures.
160          */
161         for (cpu = 0; cpu < ncpus; ++cpu) {
162                 softclock_pcpu_t sc;
163
164                 sc = &softclock_pcpu_ary[cpu];
165
166                 sc->callwheel = kmalloc(sizeof(*sc->callwheel) * callwheelsize,
167                                         M_CALLOUT, M_WAITOK|M_ZERO);
168                 for (i = 0; i < callwheelsize; ++i)
169                         TAILQ_INIT(&sc->callwheel[i]);
170
171                 /*
172                  * Mark the softclock handler as being an interrupt thread
173                  * even though it really isn't, but do not allow it to
174                  * preempt other threads (do not assign td_preemptable).
175                  *
176                  * Kernel code now assumes that callouts do not preempt
177                  * the cpu they were scheduled on.
178                  */
179                 lwkt_create(softclock_handler, sc, NULL,
180                             &sc->thread, TDF_STOPREQ|TDF_INTTHREAD, cpu,
181                             "softclock %d", cpu);
182         }
183 }
184
185 /*
186  * Must occur after ncpus has been initialized.
187  */
188 SYSINIT(softclock_setup, SI_BOOT2_SOFTCLOCK, SI_ORDER_SECOND,
189         swi_softclock_setup, NULL);
190
191 /*
192  * This routine is called from the hardclock() (basically a FASTint/IPI) on
193  * each cpu in the system.  sc->curticks is this cpu's notion of the timebase.
194  * It IS NOT NECESSARILY SYNCHRONIZED WITH 'ticks'!  sc->softticks is where
195  * the callwheel is currently indexed.
196  *
197  * WARNING!  The MP lock is not necessarily held on call, nor can it be
198  * safely obtained.
199  *
200  * sc->softticks is adjusted by either this routine or our helper thread
201  * depending on whether the helper thread is running or not.
202  */
203 void
204 hardclock_softtick(globaldata_t gd)
205 {
206         softclock_pcpu_t sc;
207
208         sc = &softclock_pcpu_ary[gd->gd_cpuid];
209         ++sc->curticks;
210         if (sc->isrunning)
211                 return;
212         if (sc->softticks == sc->curticks) {
213                 /*
214                  * in sync, only wakeup the thread if there is something to
215                  * do.
216                  */
217                 if (TAILQ_FIRST(&sc->callwheel[sc->softticks & callwheelmask]))
218                 {
219                         sc->isrunning = 1;
220                         lwkt_schedule(&sc->thread);
221                 } else {
222                         ++sc->softticks;
223                 }
224         } else {
225                 /*
226                  * out of sync, wakeup the thread unconditionally so it can
227                  * catch up.
228                  */
229                 sc->isrunning = 1;
230                 lwkt_schedule(&sc->thread);
231         }
232 }
233
234 /*
235  * This procedure is the main loop of our per-cpu helper thread.  The
236  * sc->isrunning flag prevents us from racing hardclock_softtick() and
237  * a critical section is sufficient to interlock sc->curticks and protect
238  * us from remote IPI's / list removal.
239  *
240  * The thread starts with the MP lock held and not in a critical section.
241  * The loop itself is MP safe while individual callbacks may or may not
242  * be, so we obtain or release the MP lock as appropriate.
243  */
244 static void
245 softclock_handler(void *arg)
246 {
247         softclock_pcpu_t sc;
248         struct callout *c;
249         struct callout_tailq *bucket;
250         void (*c_func)(void *);
251         void *c_arg;
252 #ifdef SMP
253         int mpsafe = 0;
254 #endif
255
256         lwkt_setpri_self(TDPRI_SOFT_NORM);
257
258         sc = arg;
259         crit_enter();
260 loop:
261         while (sc->softticks != (int)(sc->curticks + 1)) {
262                 bucket = &sc->callwheel[sc->softticks & callwheelmask];
263
264                 for (c = TAILQ_FIRST(bucket); c; c = sc->next) {
265                         if (c->c_time != sc->softticks) {
266                                 sc->next = TAILQ_NEXT(c, c_links.tqe);
267                                 continue;
268                         }
269 #ifdef SMP
270                         if (c->c_flags & CALLOUT_MPSAFE) {
271                                 if (mpsafe == 0) {
272                                         mpsafe = 1;
273                                         rel_mplock();
274                                 }
275                         } else {
276                                 /*
277                                  * The request might be removed while we 
278                                  * are waiting to get the MP lock.  If it
279                                  * was removed sc->next will point to the
280                                  * next valid request or NULL, loop up.
281                                  */
282                                 if (mpsafe) {
283                                         mpsafe = 0;
284                                         sc->next = c;
285                                         get_mplock();
286                                         if (c != sc->next)
287                                                 continue;
288                                 }
289                         }
290 #endif
291                         sc->next = TAILQ_NEXT(c, c_links.tqe);
292                         TAILQ_REMOVE(bucket, c, c_links.tqe);
293
294                         c_func = c->c_func;
295                         c_arg = c->c_arg;
296                         c->c_func = NULL;
297                         KKASSERT(c->c_flags & CALLOUT_DID_INIT);
298                         c->c_flags &= ~CALLOUT_PENDING;
299                         crit_exit();
300                         c_func(c_arg);
301                         crit_enter();
302                         /* NOTE: list may have changed */
303                 }
304                 ++sc->softticks;
305         }
306         sc->isrunning = 0;
307         lwkt_deschedule_self(&sc->thread);      /* == curthread */
308         lwkt_switch();
309         goto loop;
310         /* NOT REACHED */
311 }
312
313 /*
314  * New interface; clients allocate their own callout structures.
315  *
316  * callout_reset() - establish or change a timeout
317  * callout_stop() - disestablish a timeout
318  * callout_init() - initialize a callout structure so that it can
319  *                      safely be passed to callout_reset() and callout_stop()
320  * callout_init_mp() - same but any installed functions must be MP safe.
321  *
322  * <sys/callout.h> defines three convenience macros:
323  *
324  * callout_active() - returns truth if callout has not been serviced
325  * callout_pending() - returns truth if callout is still waiting for timeout
326  * callout_deactivate() - marks the callout as having been serviced
327  */
328
329 /*
330  * Start or restart a timeout.  Install the callout structure in the 
331  * callwheel.  Callers may legally pass any value, even if 0 or negative,
332  * but since the sc->curticks index may have already been processed a
333  * minimum timeout of 1 tick will be enforced.
334  *
335  * The callout is installed on and will be processed on the current cpu's
336  * callout wheel.
337  *
338  * WARNING! This function may be called from any cpu but the caller must
339  * serialize callout_stop() and callout_reset() calls on the passed
340  * structure regardless of cpu.
341  */
342 void
343 callout_reset(struct callout *c, int to_ticks, void (*ftn)(void *), 
344                 void *arg)
345 {
346         softclock_pcpu_t sc;
347         globaldata_t gd;
348
349 #ifdef INVARIANTS
350         if ((c->c_flags & CALLOUT_DID_INIT) == 0) {
351                 callout_init(c);
352                 kprintf(
353                     "callout_reset(%p) from %p: callout was not initialized\n",
354                     c, ((int **)&c)[-1]);
355                 print_backtrace(-1);
356         }
357 #endif
358         gd = mycpu;
359         sc = &softclock_pcpu_ary[gd->gd_cpuid];
360         crit_enter_gd(gd);
361
362         if (c->c_flags & CALLOUT_PENDING)
363                 callout_stop(c);
364
365         if (to_ticks <= 0)
366                 to_ticks = 1;
367
368         c->c_arg = arg;
369         c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING);
370         c->c_func = ftn;
371         c->c_time = sc->curticks + to_ticks;
372 #ifdef SMP
373         c->c_gd = gd;
374 #endif
375
376         TAILQ_INSERT_TAIL(&sc->callwheel[c->c_time & callwheelmask], 
377                           c, c_links.tqe);
378         crit_exit_gd(gd);
379 }
380
381 /*
382  * Stop a running timer.  WARNING!  If called on a cpu other then the one
383  * the callout was started on this function will liveloop on its IPI to
384  * the target cpu to process the request.  It is possible for the callout
385  * to execute in that case.
386  *
387  * WARNING! This function may be called from any cpu but the caller must
388  * serialize callout_stop() and callout_reset() calls on the passed
389  * structure regardless of cpu.
390  *
391  * WARNING! This routine may be called from an IPI
392  */
393 int
394 callout_stop(struct callout *c)
395 {
396         globaldata_t gd = mycpu;
397 #ifdef SMP
398         globaldata_t tgd;
399 #endif
400         softclock_pcpu_t sc;
401
402 #ifdef INVARIANTS
403         if ((c->c_flags & CALLOUT_DID_INIT) == 0) {
404                 callout_init(c);
405                 kprintf(
406                     "callout_stop(%p) from %p: callout was not initialized\n",
407                     c, ((int **)&c)[-1]);
408                 print_backtrace(-1);
409         }
410 #endif
411         crit_enter_gd(gd);
412
413         /*
414          * Don't attempt to delete a callout that's not on the queue.  The
415          * callout may not have a cpu assigned to it.  Callers do not have
416          * to be on the issuing cpu but must still serialize access to the
417          * callout structure.
418          *
419          * We are not cpu-localized here and cannot safely modify the
420          * flags field in the callout structure.  Note that most of the
421          * time CALLOUT_ACTIVE will be 0 if CALLOUT_PENDING is also 0.
422          *
423          * If we race another cpu's dispatch of this callout it is possible
424          * for CALLOUT_ACTIVE to be set with CALLOUT_PENDING unset.  This
425          * will cause us to fall through and synchronize with the other
426          * cpu.
427          */
428         if ((c->c_flags & CALLOUT_PENDING) == 0) {
429 #ifdef SMP
430                 if ((c->c_flags & CALLOUT_ACTIVE) == 0) {
431                         crit_exit_gd(gd);
432                         return (0);
433                 }
434                 if (c->c_gd == NULL || c->c_gd == gd) {
435                         c->c_flags &= ~CALLOUT_ACTIVE;
436                         crit_exit_gd(gd);
437                         return (0);
438                 }
439                 /* fall-through to the cpu-localization code. */
440 #else
441                 c->c_flags &= ~CALLOUT_ACTIVE;
442                 crit_exit_gd(gd);
443                 return (0);
444 #endif
445         }
446 #ifdef SMP
447         if ((tgd = c->c_gd) != gd) {
448                 /*
449                  * If the callout is owned by a different CPU we have to
450                  * execute the function synchronously on the target cpu.
451                  */
452                 int seq;
453
454                 cpu_ccfence();  /* don't let tgd alias c_gd */
455                 seq = lwkt_send_ipiq(tgd, (void *)callout_stop, c);
456                 lwkt_wait_ipiq(tgd, seq);
457         } else 
458 #endif
459         {
460                 /*
461                  * If the callout is owned by the same CPU we can
462                  * process it directly, but if we are racing our helper
463                  * thread (sc->next), we have to adjust sc->next.  The
464                  * race is interlocked by a critical section.
465                  */
466                 sc = &softclock_pcpu_ary[gd->gd_cpuid];
467
468                 c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
469                 if (sc->next == c)
470                         sc->next = TAILQ_NEXT(c, c_links.tqe);
471
472                 TAILQ_REMOVE(&sc->callwheel[c->c_time & callwheelmask], 
473                                 c, c_links.tqe);
474                 c->c_func = NULL;
475         }
476         crit_exit_gd(gd);
477         return (1);
478 }
479
480 /*
481  * Prepare a callout structure for use by callout_reset() and/or 
482  * callout_stop().  The MP version of this routine requires that the callback
483  * function installed by callout_reset() be MP safe.
484  *
485  * The init functions can be called from any cpu and do not have to be
486  * called from the cpu that the timer will eventually run on.
487  */
488 void
489 callout_init(struct callout *c)
490 {
491         bzero(c, sizeof *c);
492         c->c_flags = CALLOUT_DID_INIT;
493 }
494
495 void
496 callout_init_mp(struct callout *c)
497 {
498         callout_init(c);
499         c->c_flags |= CALLOUT_MPSAFE;
500 }
501
502 /* What, are you joking?  This is nuts! -Matt */
503 #if 0
504 #ifdef APM_FIXUP_CALLTODO
505 /* 
506  * Adjust the kernel calltodo timeout list.  This routine is used after 
507  * an APM resume to recalculate the calltodo timer list values with the 
508  * number of hz's we have been sleeping.  The next hardclock() will detect 
509  * that there are fired timers and run softclock() to execute them.
510  *
511  * Please note, I have not done an exhaustive analysis of what code this
512  * might break.  I am motivated to have my select()'s and alarm()'s that
513  * have expired during suspend firing upon resume so that the applications
514  * which set the timer can do the maintanence the timer was for as close
515  * as possible to the originally intended time.  Testing this code for a 
516  * week showed that resuming from a suspend resulted in 22 to 25 timers 
517  * firing, which seemed independant on whether the suspend was 2 hours or
518  * 2 days.  Your milage may vary.   - Ken Key <key@cs.utk.edu>
519  */
520 void
521 adjust_timeout_calltodo(struct timeval *time_change)
522 {
523         struct callout *p;
524         unsigned long delta_ticks;
525
526         /* 
527          * How many ticks were we asleep?
528          * (stolen from tvtohz()).
529          */
530
531         /* Don't do anything */
532         if (time_change->tv_sec < 0)
533                 return;
534         else if (time_change->tv_sec <= LONG_MAX / 1000000)
535                 delta_ticks = (time_change->tv_sec * 1000000 +
536                                time_change->tv_usec + (tick - 1)) / tick + 1;
537         else if (time_change->tv_sec <= LONG_MAX / hz)
538                 delta_ticks = time_change->tv_sec * hz +
539                               (time_change->tv_usec + (tick - 1)) / tick + 1;
540         else
541                 delta_ticks = LONG_MAX;
542
543         if (delta_ticks > INT_MAX)
544                 delta_ticks = INT_MAX;
545
546         /* 
547          * Now rip through the timer calltodo list looking for timers
548          * to expire.
549          */
550
551         /* don't collide with softclock() */
552         crit_enter();
553         for (p = calltodo.c_next; p != NULL; p = p->c_next) {
554                 p->c_time -= delta_ticks;
555
556                 /* Break if the timer had more time on it than delta_ticks */
557                 if (p->c_time > 0)
558                         break;
559
560                 /* take back the ticks the timer didn't use (p->c_time <= 0) */
561                 delta_ticks = -p->c_time;
562         }
563         crit_exit();
564
565         return;
566 }
567 #endif /* APM_FIXUP_CALLTODO */
568 #endif
569