kernel - Implement new callout*() core
authorMatthew Dillon <dillon@apollo.backplane.com>
Tue, 25 Nov 2014 18:15:42 +0000 (10:15 -0800)
committerMatthew Dillon <dillon@apollo.backplane.com>
Tue, 25 Nov 2014 18:15:42 +0000 (10:15 -0800)
* Rewrite the callout*() function core to run more efficiently.
  This has a much better mechanism for locking a callout to a
  cpu and for dealing with synchronous waits for callbacks to
  complete.

  The IPI busy/wait loop has been removed for remote-cpu operations.
  The code now blocks normally and callers will have to understand that.
  This will make it a lot easier to debug races.

* Add callout_init_lk() which implements auto-locking similar
  to FreeBSD.  Several FreeBSD mechanisms already depend on it
  and it will make porting easier.  And it works pretty well.

* Preparation for a more synchronous interface.

* Note that the new API is roughly similar to the old
  except callout_reset() now issues a synchronous stop
  instead of an asynchronous stop.  Soon we will also
  switch around the function names to make MP operation
  and synchronous operation the default across the
  board.

sys/kern/kern_timeout.c
sys/netinet/sctp_callout.h
sys/sys/callout.h

index 4086737..a8b262e 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2004 The DragonFly Project.  All rights reserved.
+ * Copyright (c) 2004,2014 The DragonFly Project.  All rights reserved.
  * 
  * This code is derived from software contributed to The DragonFly Project
  * by Matthew Dillon <dillon@backplane.com>
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
- *
- *     From: @(#)kern_clock.c  8.5 (Berkeley) 1/21/94
- * $FreeBSD: src/sys/kern/kern_timeout.c,v 1.59.2.1 2001/11/13 18:24:52 archie Exp $
  */
 /*
- * DRAGONFLY BGL STATUS
- *
- *     All the API functions should be MP safe.
- *
- *     The callback functions will be flagged as being MP safe if the
- *     timeout structure is initialized with callout_init_mp() instead of
- *     callout_init().
- *
- *     The helper threads cannot be made preempt-capable until after we
- *     clean up all the uses of splsoftclock() and related interlocks (which
- *     require the related functions to be MP safe as well).
- */
-/*
- * The callout mechanism is based on the work of Adam M. Costello and 
- * George Varghese, published in a technical report entitled "Redesigning
+ * The original callout mechanism was based on the work of Adam M. Costello
+ * and George Varghese, published in a technical report entitled "Redesigning
  * the BSD Callout and Timer Facilities" and modified slightly for inclusion
  * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
  * used in this implementation was published by G. Varghese and T. Lauck in
 #include <sys/thread2.h>
 #include <sys/mplock2.h>
 
-#ifndef MAX_SOFTCLOCK_STEPS
-#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */
-#endif
-
-
 struct softclock_pcpu {
        struct callout_tailq *callwheel;
        struct callout * volatile next;
-       struct callout *running;/* currently running callout */
+       intptr_t running;       /* NOTE! Bit 0 used to flag wakeup */
        int softticks;          /* softticks index */
        int curticks;           /* per-cpu ticks counter */
        int isrunning;
        struct thread thread;
-
 };
 
 typedef struct softclock_pcpu *softclock_pcpu_t;
 
-/*
- * TODO:
- *     allocate more timeout table slots when table overflows.
- */
 static MALLOC_DEFINE(M_CALLOUT, "callout", "callout structures");
-static int callwheelsize;
-static int callwheelmask;
+static int cwheelsize;
+static int cwheelmask;
 static struct softclock_pcpu softclock_pcpu_ary[MAXCPU];
 
 static void softclock_handler(void *arg);
 static void slotimer_callback(void *arg);
+static void callout_reset_ipi(void *arg);
+static void callout_stop_ipi(void *arg, int issync, struct intrframe *frame);
+
 
 static void
 swi_softclock_setup(void *arg)
@@ -149,10 +126,10 @@ swi_softclock_setup(void *arg)
         */
        target = ncallout / ncpus + 16;
 
-       callwheelsize = 1;
-       while (callwheelsize < target)
-               callwheelsize <<= 1;
-       callwheelmask = callwheelsize - 1;
+       cwheelsize = 1;
+       while (cwheelsize < target)
+               cwheelsize <<= 1;
+       cwheelmask = cwheelsize - 1;
 
        /*
         * Initialize per-cpu data structures.
@@ -162,9 +139,9 @@ swi_softclock_setup(void *arg)
 
                sc = &softclock_pcpu_ary[cpu];
 
-               sc->callwheel = kmalloc(sizeof(*sc->callwheel) * callwheelsize,
+               sc->callwheel = kmalloc(sizeof(*sc->callwheel) * cwheelsize,
                                        M_CALLOUT, M_WAITOK|M_ZERO);
-               for (i = 0; i < callwheelsize; ++i)
+               for (i = 0; i < cwheelsize; ++i)
                        TAILQ_INIT(&sc->callwheel[i]);
 
                /*
@@ -187,6 +164,33 @@ swi_softclock_setup(void *arg)
 SYSINIT(softclock_setup, SI_BOOT2_SOFTCLOCK, SI_ORDER_SECOND,
        swi_softclock_setup, NULL);
 
+/*
+ * Clear PENDING and, if possible, also clear ARMED and WAITING.  Returns
+ * the flags prior to the clear, atomically (used to check for WAITING).
+ *
+ * Clearing the cpu association (ARMED) can significantly improve the
+ * performance of the next callout_reset*() call.
+ */
+static __inline
+int
+callout_unpend_disarm(struct callout *c)
+{
+       int flags;
+       int nflags;
+
+       for (;;) {
+               flags = c->c_flags;
+               cpu_ccfence();
+               nflags = flags & ~(CALLOUT_PENDING | CALLOUT_WAITING);
+               if ((flags & CALLOUT_IPI_MASK) == 0)
+                       nflags &= ~CALLOUT_ARMED;
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags)) {
+                       break;
+               }
+       }
+       return flags;
+}
+
 /*
  * This routine is called from the hardclock() (basically a FASTint/IPI) on
  * each cpu in the system.  sc->curticks is this cpu's notion of the timebase.
@@ -210,11 +214,10 @@ hardclock_softtick(globaldata_t gd)
                return;
        if (sc->softticks == sc->curticks) {
                /*
-                * in sync, only wakeup the thread if there is something to
+                * In sync, only wakeup the thread if there is something to
                 * do.
                 */
-               if (TAILQ_FIRST(&sc->callwheel[sc->softticks & callwheelmask]))
-               {
+               if (TAILQ_FIRST(&sc->callwheel[sc->softticks & cwheelmask])) {
                        sc->isrunning = 1;
                        lwkt_schedule(&sc->thread);
                } else {
@@ -247,9 +250,8 @@ softclock_handler(void *arg)
        struct callout *c;
        struct callout_tailq *bucket;
        struct callout slotimer;
-       void (*c_func)(void *);
-       void *c_arg;
        int mpsafe = 1;
+       int flags;
 
        /*
         * Setup pcpu slow clocks which we want to run from the callout
@@ -264,18 +266,23 @@ softclock_handler(void *arg)
         */
        /*lwkt_setpri_self(TDPRI_SOFT_NORM);*/
 
+       /*
+        * Loop critical section against ipi operations to this cpu.
+        */
        sc = arg;
        crit_enter();
 loop:
        while (sc->softticks != (int)(sc->curticks + 1)) {
-               bucket = &sc->callwheel[sc->softticks & callwheelmask];
+               bucket = &sc->callwheel[sc->softticks & cwheelmask];
 
                for (c = TAILQ_FIRST(bucket); c; c = sc->next) {
                        if (c->c_time != sc->softticks) {
                                sc->next = TAILQ_NEXT(c, c_links.tqe);
                                continue;
                        }
-                       if (c->c_flags & CALLOUT_MPSAFE) {
+
+                       flags = c->c_flags;
+                       if (flags & CALLOUT_MPSAFE) {
                                if (mpsafe == 0) {
                                        mpsafe = 1;
                                        rel_mplock();
@@ -295,19 +302,97 @@ loop:
                                                continue;
                                }
                        }
+
+                       /*
+                        * Queue protection only exists while we hold the
+                        * critical section uninterrupted.
+                        *
+                        * Adjust sc->next when removing (c) from the queue,
+                        * note that an IPI on this cpu may make further
+                        * adjustments to sc->next.
+                        */
                        sc->next = TAILQ_NEXT(c, c_links.tqe);
                        TAILQ_REMOVE(bucket, c, c_links.tqe);
 
-                       sc->running = c;
-                       c_func = c->c_func;
-                       c_arg = c->c_arg;
-                       c->c_func = NULL;
-                       KKASSERT(c->c_flags & CALLOUT_DID_INIT);
-                       c->c_flags &= ~CALLOUT_PENDING;
-                       crit_exit();
-                       c_func(c_arg);
-                       crit_enter();
-                       sc->running = NULL;
+                       /*
+                        * Once CALLOUT_PENDING is cleared, sc->running
+                        * protects the callout structure's existance but
+                        * only until we call c_func().  A callout_stop()
+                        * or callout_reset() issued from within c_func()
+                        * will not block.  The callout can also be kfree()d
+                        * by c_func().
+                        *
+                        * We set EXECUTED before calling c_func() so a
+                        * callout_stop() issued from within c_func() returns
+                        * the correct status.
+                        */
+
+                       if ((flags & (CALLOUT_AUTOLOCK | CALLOUT_ACTIVE)) ==
+                           (CALLOUT_AUTOLOCK | CALLOUT_ACTIVE)) {
+                               void (*c_func)(void *);
+                               void *c_arg;
+                               struct lock *c_lk;
+                               int error;
+
+                               /*
+                                * NOTE: sc->running must be set prior to
+                                *       CALLOUT_PENDING being cleared to
+                                *       avoid missed CANCELs and *_stop()
+                                *       races.
+                                */
+                               sc->running = (intptr_t)c;
+                               c_func = c->c_func;
+                               c_arg = c->c_arg;
+                               c_lk = c->c_lk;
+                               c->c_func = NULL;
+                               KKASSERT(c->c_flags & CALLOUT_DID_INIT);
+                               flags = callout_unpend_disarm(c);
+                               error = lockmgr(c_lk, LK_EXCLUSIVE |
+                                                     LK_CANCELABLE);
+                               if (error == 0) {
+                                       atomic_set_int(&c->c_flags,
+                                                      CALLOUT_EXECUTED);
+                                       crit_exit();
+                                       c_func(c_arg);
+                                       crit_enter();
+                                       lockmgr(c_lk, LK_RELEASE);
+                               }
+                       } else if (flags & CALLOUT_ACTIVE) {
+                               void (*c_func)(void *);
+                               void *c_arg;
+
+                               sc->running = (intptr_t)c;
+                               c_func = c->c_func;
+                               c_arg = c->c_arg;
+                               c->c_func = NULL;
+                               KKASSERT(c->c_flags & CALLOUT_DID_INIT);
+                               flags = callout_unpend_disarm(c);
+                               atomic_set_int(&c->c_flags, CALLOUT_EXECUTED);
+                               crit_exit();
+                               c_func(c_arg);
+                               crit_enter();
+                       } else {
+                               flags = callout_unpend_disarm(c);
+                       }
+
+                       /*
+                        * Read and clear sc->running.  If bit 0 was set,
+                        * a callout_stop() is likely blocked waiting for
+                        * the callback to complete.
+                        *
+                        * The sigclear above also cleared CALLOUT_WAITING
+                        * and returns the contents of flags prior to clearing
+                        * any bits.
+                        *
+                        * Interlock wakeup any _stop's waiting on us.  Note
+                        * that once c_func() was called, the callout
+                        * structure (c) pointer may no longer be valid.  It
+                        * can only be used for the wakeup.
+                        */
+                       if ((atomic_readandclear_ptr(&sc->running) & 1) ||
+                           (flags & CALLOUT_WAITING)) {
+                               wakeup(c);
+                       }
                        /* NOTE: list may have changed */
                }
                ++sc->softticks;
@@ -341,37 +426,16 @@ slotimer_callback(void *arg)
 }
 
 /*
- * New interface; clients allocate their own callout structures.
- *
- * callout_reset() - establish or change a timeout
- * callout_stop() - disestablish a timeout
- * callout_init() - initialize a callout structure so that it can
- *                     safely be passed to callout_reset() and callout_stop()
- * callout_init_mp() - same but any installed functions must be MP safe.
- *
- * <sys/callout.h> defines three convenience macros:
- *
- * callout_active() - returns truth if callout has not been serviced
- * callout_pending() - returns truth if callout is still waiting for timeout
- * callout_deactivate() - marks the callout as having been serviced
- */
-
-/*
- * Start or restart a timeout.  Install the callout structure in the 
+ * Start or restart a timeout.  Installs the callout structure on the
  * callwheel.  Callers may legally pass any value, even if 0 or negative,
  * but since the sc->curticks index may have already been processed a
  * minimum timeout of 1 tick will be enforced.
  *
- * The callout is installed on and will be processed on the current cpu's
- * callout wheel.
- *
- * WARNING! This function may be called from any cpu but the caller must
- * serialize callout_stop() and callout_reset() calls on the passed
- * structure regardless of cpu.
+ * This function will block if the callout is currently queued to a different
+ * cpu or the callback is currently running in another thread.
  */
 void
-callout_reset(struct callout *c, int to_ticks, void (*ftn)(void *), 
-               void *arg)
+callout_reset(struct callout *c, int to_ticks, void (*ftn)(void *), void *arg)
 {
        softclock_pcpu_t sc;
        globaldata_t gd;
@@ -389,87 +453,223 @@ callout_reset(struct callout *c, int to_ticks, void (*ftn)(void *),
        sc = &softclock_pcpu_ary[gd->gd_cpuid];
        crit_enter_gd(gd);
 
-       if (c->c_flags & CALLOUT_ACTIVE)
-               callout_stop(c);
+       /*
+        * Our cpu must gain ownership of the callout and cancel anything
+        * still running, which is complex.  The easiest way to do it is to
+        * issue a callout_stop().
+        *
+        * Clearing bits on flags is a way to guarantee they are not set,
+        * as the cmpset atomic op will fail otherwise.
+        *
+        */
+       for (;;) {
+               int flags;
+               int nflags;
+
+               callout_stop_sync(c);
+               flags = c->c_flags & ~CALLOUT_PENDING;
+               nflags = (flags & ~(CALLOUT_CPU_MASK |
+                                   CALLOUT_EXECUTED)) |
+                        CALLOUT_CPU_TO_FLAGS(gd->gd_cpuid) |
+                        CALLOUT_ARMED |
+                        CALLOUT_PENDING |
+                        CALLOUT_ACTIVE;
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags))
+                       break;
+       }
+
 
        if (to_ticks <= 0)
                to_ticks = 1;
 
        c->c_arg = arg;
-       c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING);
        c->c_func = ftn;
        c->c_time = sc->curticks + to_ticks;
-       c->c_gd = gd;
 
-       TAILQ_INSERT_TAIL(&sc->callwheel[c->c_time & callwheelmask], 
+       TAILQ_INSERT_TAIL(&sc->callwheel[c->c_time & cwheelmask],
                          c, c_links.tqe);
        crit_exit_gd(gd);
 }
 
-struct callout_remote_arg {
-       struct callout  *c;
-       void            (*ftn)(void *);
-       void            *arg;
-       int             to_ticks;
-};
-
-static void
-callout_reset_ipi(void *arg)
+/*
+ * Setup a callout to run on the specified cpu.  Should generally be used
+ * to run a callout on a specific cpu which does not nominally change.
+ */
+void
+callout_reset_bycpu(struct callout *c, int to_ticks, void (*ftn)(void *),
+                   void *arg, int cpuid)
 {
-       struct callout_remote_arg *rmt = arg;
+       globaldata_t gd;
+       globaldata_t tgd;
+
+#ifdef INVARIANTS
+        if ((c->c_flags & CALLOUT_DID_INIT) == 0) {
+               callout_init(c);
+               kprintf(
+                   "callout_reset(%p) from %p: callout was not initialized\n",
+                   c, ((int **)&c)[-1]);
+               print_backtrace(-1);
+       }
+#endif
+       gd = mycpu;
+       crit_enter_gd(gd);
+
+       tgd = globaldata_find(cpuid);
+
+       /*
+        * Our cpu must temporarily gain ownership of the callout and cancel
+        * anything still running, which is complex.  The easiest way to do
+        * it is to issue a callout_stop().
+        *
+        * Clearing bits on flags (vs nflags) is a way to guarantee they were
+        * not previously set, by forcing the atomic op to fail.
+        */
+       for (;;) {
+               int flags;
+               int nflags;
+
+               callout_stop_sync(c);
+               flags = c->c_flags & ~CALLOUT_PENDING;
+               nflags = (flags & ~(CALLOUT_CPU_MASK |
+                                   CALLOUT_EXECUTED)) |
+                        CALLOUT_CPU_TO_FLAGS(tgd->gd_cpuid) |
+                        CALLOUT_ARMED |
+                        CALLOUT_ACTIVE;
+               nflags = nflags + 1;            /* bump IPI count */
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags))
+                       break;
+               cpu_pause();
+       }
+
+       /*
+        * Even though we are not the cpu that now owns the callout, our
+        * bumping of the IPI count (and in a situation where the callout is
+        * not queued to the callwheel) will prevent anyone else from
+        * depending on or acting on the contents of the callout structure.
+        */
+       if (to_ticks <= 0)
+               to_ticks = 1;
 
-       callout_reset(rmt->c, rmt->to_ticks, rmt->ftn, rmt->arg);
+       c->c_arg = arg;
+       c->c_func = ftn;
+       c->c_load = to_ticks;   /* IPI will add curticks */
+
+       lwkt_send_ipiq(tgd, callout_reset_ipi, c);
+       crit_exit_gd(gd);
 }
 
-void
-callout_reset_bycpu(struct callout *c, int to_ticks, void (*ftn)(void *),
-    void *arg, int cpuid)
+/*
+ * Remote IPI for callout_reset_bycpu().  The operation is performed only
+ * on the 1->0 transition of the counter, otherwise there are callout_stop()s
+ * pending after us.
+ *
+ * The IPI counter and PENDING flags must be set atomically with the
+ * 1->0 transition.  The ACTIVE flag was set prior to the ipi being
+ * sent and we do not want to race a caller on the original cpu trying
+ * to deactivate() the flag concurrent with our installation of the
+ * callout.
+ */
+static void
+callout_reset_ipi(void *arg)
 {
-       KASSERT(cpuid >= 0 && cpuid < ncpus, ("invalid cpuid %d", cpuid));
+       struct callout *c = arg;
+       globaldata_t gd = mycpu;
+       globaldata_t tgd;
+       int flags;
+       int nflags;
 
-       if (cpuid == mycpuid) {
-               callout_reset(c, to_ticks, ftn, arg);
-       } else {
-               struct globaldata *target_gd;
-               struct callout_remote_arg rmt;
-               int seq;
+       for (;;) {
+               flags = c->c_flags;
+               cpu_ccfence();
+               KKASSERT((flags & CALLOUT_IPI_MASK) > 0);
 
-               rmt.c = c;
-               rmt.ftn = ftn;
-               rmt.arg = arg;
-               rmt.to_ticks = to_ticks;
+               /*
+                * We should already be armed for our cpu, if armed to another
+                * cpu, chain the IPI.  If for some reason we are not armed,
+                * we can arm ourselves.
+                */
+               if (flags & CALLOUT_ARMED) {
+                       if (CALLOUT_FLAGS_TO_CPU(flags) != gd->gd_cpuid) {
+                               tgd = globaldata_find(
+                                               CALLOUT_FLAGS_TO_CPU(flags));
+                               lwkt_send_ipiq(tgd, callout_reset_ipi, c);
+                               return;
+                       }
+                       nflags = (flags & ~CALLOUT_EXECUTED);
+               } else {
+                       nflags = (flags & ~(CALLOUT_CPU_MASK |
+                                           CALLOUT_EXECUTED)) |
+                                CALLOUT_ARMED |
+                                CALLOUT_CPU_TO_FLAGS(gd->gd_cpuid);
+               }
 
-               target_gd = globaldata_find(cpuid);
+               /*
+                * Decrement the IPI count, retain and clear the WAITING
+                * status, clear EXECUTED.
+                *
+                * NOTE: It is possible for the callout to already have been
+                *       marked pending due to SMP races.
+                */
+               nflags = nflags - 1;
+               if ((flags & CALLOUT_IPI_MASK) == 1) {
+                       nflags &= ~(CALLOUT_WAITING | CALLOUT_EXECUTED);
+                       nflags |= CALLOUT_PENDING;
+               }
 
-               seq = lwkt_send_ipiq(target_gd, callout_reset_ipi, &rmt);
-               lwkt_wait_ipiq(target_gd, seq);
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags)) {
+                       /*
+                        * Only install the callout on the 1->0 transition
+                        * of the IPI count, and only if PENDING was not
+                        * already set.  The latter situation should never
+                        * occur but we check anyway.
+                        */
+                       if ((flags & (CALLOUT_PENDING|CALLOUT_IPI_MASK)) == 1) {
+                               softclock_pcpu_t sc;
+
+                               sc = &softclock_pcpu_ary[gd->gd_cpuid];
+                               c->c_time = sc->curticks + c->c_load;
+                               TAILQ_INSERT_TAIL(
+                                       &sc->callwheel[c->c_time & cwheelmask],
+                                       c, c_links.tqe);
+                       }
+                       break;
+               }
+               /* retry */
+               cpu_pause();
        }
+
+       /*
+        * Issue wakeup if requested.
+        */
+       if (flags & CALLOUT_WAITING)
+               wakeup(c);
 }
 
 /*
- * Stop a running timer.  WARNING!  If called on a cpu other then the one
- * the callout was started on this function will liveloop on its IPI to
- * the target cpu to process the request.  It is possible for the callout
- * to execute in that case.
- *
- * WARNING! This function may be called from any cpu but the caller must
- * serialize callout_stop() and callout_reset() calls on the passed
- * structure regardless of cpu.
+ * Stop a running timer and ensure that any running callout completes before
+ * returning.  If the timer is running on another cpu this function may block
+ * to interlock against the callout.  If the callout is currently executing
+ * or blocked in another thread this function may also block to interlock
+ * against the callout.
  *
- * WARNING! This routine may be called from an IPI
+ * The caller must be careful to avoid deadlocks, either by using
+ * callout_init_lk() (which uses the lockmgr lock cancelation feature),
+ * by using tokens and dealing with breaks in the serialization, or using
+ * the lockmgr lock cancelation feature yourself in the callout callback
+ * function.
  *
- * WARNING! This function can return while it's c_func is still running
- *         in the callout thread, a secondary check may be needed.
- *         Use callout_stop_sync() to wait for any callout function to
- *         complete before returning, being sure that no deadlock is
- *         possible if you do.
+ * callout_stop() returns non-zero if the callout was pending.
  */
-int
-callout_stop(struct callout *c)
+static int
+_callout_stop(struct callout *c, int issync)
 {
        globaldata_t gd = mycpu;
        globaldata_t tgd;
        softclock_pcpu_t sc;
+       int flags;
+       int nflags;
+       int rc;
+       int cpuid;
 
 #ifdef INVARIANTS
         if ((c->c_flags & CALLOUT_DID_INIT) == 0) {
@@ -483,136 +683,322 @@ callout_stop(struct callout *c)
        crit_enter_gd(gd);
 
        /*
-        * Don't attempt to delete a callout that's not on the queue.  The
-        * callout may not have a cpu assigned to it.  Callers do not have
-        * to be on the issuing cpu but must still serialize access to the
-        * callout structure.
-        *
-        * We are not cpu-localized here and cannot safely modify the
-        * flags field in the callout structure.  Note that most of the
-        * time CALLOUT_ACTIVE will be 0 if CALLOUT_PENDING is also 0.
+        * Fast path operations:
         *
-        * If we race another cpu's dispatch of this callout it is possible
-        * for CALLOUT_ACTIVE to be set with CALLOUT_PENDING unset.  This
-        * will cause us to fall through and synchronize with the other
-        * cpu.
+        * If ARMED and owned by our cpu, or not ARMED, and other simple
+        * conditions are met, we can just clear ACTIVE and EXECUTED
+        * and we are done.
         */
-       if ((c->c_flags & CALLOUT_PENDING) == 0) {
-               if ((c->c_flags & CALLOUT_ACTIVE) == 0) {
-                       crit_exit_gd(gd);
-                       return (0);
-               }
-               if (c->c_gd == NULL || c->c_gd == gd) {
-                       c->c_flags &= ~CALLOUT_ACTIVE;
-                       crit_exit_gd(gd);
-                       return (0);
+       for (;;) {
+               flags = c->c_flags;
+               cpu_ccfence();
+
+               cpuid = CALLOUT_FLAGS_TO_CPU(flags);
+
+               /*
+                * Can't handle an armed callout in the fast path if it is
+                * not on the current cpu.  We must atomically increment the
+                * IPI count for the IPI we intend to send and break out of
+                * the fast path to enter the slow path.
+                */
+               if (flags & CALLOUT_ARMED) {
+                       if (gd->gd_cpuid != cpuid) {
+                               nflags = flags + 1;
+                               if (atomic_cmpset_int(&c->c_flags,
+                                                     flags, nflags)) {
+                                       /* break to slow path */
+                                       break;
+                               }
+                               continue;       /* retry */
+                       }
+               } else {
+                       cpuid = gd->gd_cpuid;
+                       KKASSERT((flags & CALLOUT_IPI_MASK) == 0);
                }
-       }
-       if ((tgd = c->c_gd) != gd) {
+
                /*
-                * If the callout is owned by a different CPU we have to
-                * execute the function synchronously on the target cpu.
+                * Process pending IPIs and retry (only if not called from
+                * an IPI).
                 */
-               int seq;
+               if (flags & CALLOUT_IPI_MASK) {
+                       lwkt_process_ipiq();
+                       continue;       /* retry */
+               }
 
-               cpu_ccfence();  /* don't let tgd alias c_gd */
-               seq = lwkt_send_ipiq(tgd, (void *)callout_stop, c);
-               lwkt_wait_ipiq(tgd, seq);
-       } else {
                /*
-                * If the callout is owned by the same CPU we can
-                * process it directly, but if we are racing our helper
-                * thread (sc->next), we have to adjust sc->next.  The
-                * race is interlocked by a critical section.
+                * Transition to the stopped state, recover the EXECUTED
+                * status.  If pending we cannot clear ARMED until after
+                * we have removed (c) from the callwheel.
+                *
+                * NOTE: The callout might already not be armed but in this
+                *       case it should also not be pending.
                 */
-               sc = &softclock_pcpu_ary[gd->gd_cpuid];
+               nflags = flags & ~(CALLOUT_ACTIVE |
+                                  CALLOUT_EXECUTED |
+                                  CALLOUT_WAITING |
+                                  CALLOUT_PENDING);
+               if ((flags & CALLOUT_PENDING) == 0)
+                       nflags &= ~CALLOUT_ARMED;
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags)) {
+                       if (flags & CALLOUT_PENDING) {
+                               sc = &softclock_pcpu_ary[gd->gd_cpuid];
+                               if (sc->next == c)
+                                       sc->next = TAILQ_NEXT(c, c_links.tqe);
+                               TAILQ_REMOVE(
+                                       &sc->callwheel[c->c_time & cwheelmask],
+                                       c,
+                                       c_links.tqe);
+                               c->c_func = NULL;
 
-               c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
-               if (sc->next == c)
-                       sc->next = TAILQ_NEXT(c, c_links.tqe);
+                               /*
+                                * NOTE: Can't clear ARMED until we have
+                                *       physically removed (c) from the
+                                *       callwheel.
+                                *
+                                * NOTE: WAITING bit race exists when doing
+                                *       unconditional bit clears.
+                                */
+                               atomic_clear_int(&c->c_flags, CALLOUT_ARMED);
+                               if (c->c_flags & CALLOUT_WAITING)
+                                       flags |= CALLOUT_WAITING;
+                       }
+
+                       /*
+                        * ARMED has been cleared at this point and (c)
+                        * might now be stale.  Only good for wakeup()s.
+                        */
+                       if (flags & CALLOUT_WAITING)
+                               wakeup(c);
 
-               TAILQ_REMOVE(&sc->callwheel[c->c_time & callwheelmask], 
-                               c, c_links.tqe);
-               c->c_func = NULL;
+                       goto skip_slow;
+               }
+               /* retry */
        }
+
+       /*
+        * Slow path (and not called via an IPI).
+        *
+        * When ARMED to a different cpu the stop must be processed on that
+        * cpu.  Issue the IPI and wait for completion.  We have already
+        * incremented the IPI count.
+        */
+       tgd = globaldata_find(cpuid);
+       lwkt_send_ipiq3(tgd, callout_stop_ipi, c, issync);
+
+       for (;;) {
+               int flags;
+               int nflags;
+
+               flags = c->c_flags;
+               cpu_ccfence();
+               if ((flags & CALLOUT_IPI_MASK) == 0)    /* fast path */
+                       break;
+               nflags = flags | CALLOUT_WAITING;
+               tsleep_interlock(c, 0);
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags)) {
+                       tsleep(c, PINTERLOCKED, "cstp1", 0);
+               }
+       }
+
+skip_slow:
+       /*
+        * If (issync) we must also wait for any in-progress callbacks to
+        * complete, unless the stop is being executed from the callback
+        * itself.  The EXECUTED flag is set prior to the callback
+        * being made so our existing flags status already has it.
+        *
+        * If auto-lock mode is being used, this is where we cancel any
+        * blocked lock that is potentially preventing the target cpu
+        * from completing the callback.
+        */
+       while (issync) {
+               intptr_t *runp;
+               intptr_t runco;
+
+               sc = &softclock_pcpu_ary[cpuid];
+               if (gd->gd_curthread == &sc->thread)    /* stop from cb */
+                       break;
+               runp = &sc->running;
+               runco = *runp;
+               cpu_ccfence();
+               if ((runco & ~(intptr_t)1) != (intptr_t)c)
+                       break;
+               if (c->c_flags & CALLOUT_AUTOLOCK)
+                       lockmgr(c->c_lk, LK_CANCEL_BEG);
+               tsleep_interlock(c, 0);
+               if (atomic_cmpset_long(runp, runco, runco | 1))
+                       tsleep(c, PINTERLOCKED, "cstp3", 0);
+               if (c->c_flags & CALLOUT_AUTOLOCK)
+                       lockmgr(c->c_lk, LK_CANCEL_END);
+       }
+
        crit_exit_gd(gd);
-       return (1);
+       rc = (flags & CALLOUT_EXECUTED) != 0;
+
+       return rc;
 }
 
-/*
- * Issue a callout_stop() and ensure that any callout race completes
- * before returning.  Does NOT de-initialized the callout.
- */
+static
 void
-callout_stop_sync(struct callout *c)
+callout_stop_ipi(void *arg, int issync, struct intrframe *frame)
 {
+       globaldata_t gd = mycpu;
+       struct callout *c = arg;
        softclock_pcpu_t sc;
 
-       while (c->c_flags & CALLOUT_DID_INIT) {
-               callout_stop(c);
-               if (c->c_gd) {
-                       sc = &softclock_pcpu_ary[c->c_gd->gd_cpuid];
-                       if (sc->running == c) {
-                               while (sc->running == c)
-                                       tsleep(&sc->running, 0, "crace", 1);
-                       }
+       sc = &softclock_pcpu_ary[gd->gd_cpuid];
+
+       /*
+        * Only the fast path can run in an IPI.  Chain the stop request
+        * if we are racing cpu changes.
+        */
+       for (;;) {
+               globaldata_t tgd;
+               int flags;
+               int nflags;
+               int cpuid;
+
+               flags = c->c_flags;
+               cpu_ccfence();
+
+               cpuid = CALLOUT_FLAGS_TO_CPU(flags);
+
+               /*
+                * Can't handle an armed callout in the fast path if it is
+                * not on the current cpu.  We must atomically increment the
+                * IPI count and break out of the fast path.
+                *
+                * If called from an IPI we chain the IPI instead.
+                */
+               if ((flags & CALLOUT_ARMED) && gd->gd_cpuid != cpuid) {
+                       tgd = globaldata_find(cpuid);
+                       lwkt_send_ipiq3(tgd, callout_stop_ipi, c, issync);
+                       break;
                }
-               if ((c->c_flags & (CALLOUT_PENDING | CALLOUT_ACTIVE)) == 0)
+
+               /*
+                * NOTE: As an IPI ourselves we cannot wait for other IPIs
+                *       to complete, and we are being executed in-order.
+                */
+
+               /*
+                * Transition to the stopped state, recover the EXECUTED
+                * status, decrement the IPI count.  If pending we cannot
+                * clear ARMED until after we have removed (c) from the
+                * callwheel.
+                */
+               nflags = flags & ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
+               nflags = nflags - 1;                    /* dec ipi count */
+               if ((flags & CALLOUT_PENDING) == 0)
+                       nflags &= ~CALLOUT_ARMED;
+               if ((flags & CALLOUT_IPI_MASK) == 1)
+                       nflags &= ~(CALLOUT_WAITING | CALLOUT_EXECUTED);
+
+               if (atomic_cmpset_int(&c->c_flags, flags, nflags)) {
+                       /*
+                        * Can only remove from callwheel if currently
+                        * pending.
+                        */
+                       if (flags & CALLOUT_PENDING) {
+                               if (sc->next == c)
+                                       sc->next = TAILQ_NEXT(c, c_links.tqe);
+                               TAILQ_REMOVE(
+                                       &sc->callwheel[c->c_time & cwheelmask],
+                                       c,
+                                       c_links.tqe);
+                               c->c_func = NULL;
+
+                               /*
+                                * NOTE: Can't clear ARMED until we have
+                                *       physically removed (c) from the
+                                *       callwheel.
+                                *
+                                * NOTE: WAITING bit race exists when doing
+                                *       unconditional bit clears.
+                                */
+                               atomic_clear_int(&c->c_flags, CALLOUT_ARMED);
+                               if (c->c_flags & CALLOUT_WAITING)
+                                       flags |= CALLOUT_WAITING;
+                       }
+
+                       /*
+                        * ARMED has been cleared at this point and (c)
+                        * might now be stale.  Only good for wakeup()s.
+                        */
+                       if (flags & CALLOUT_WAITING)
+                               wakeup(c);
                        break;
-               kprintf("Warning: %s: callout race\n", curthread->td_comm);
+               }
+               /* retry */
        }
 }
 
-/*
- * Terminate a callout
- *
- * This function will stop any pending callout and also block while the
- * callout's function is running.  It should only be used in cases where
- * no deadlock is possible (due to the callout function acquiring locks
- * that the current caller of callout_terminate() already holds), when
- * the caller is ready to destroy the callout structure.
- *
- * This function clears the CALLOUT_DID_INIT flag.
- *
- * lwkt_token locks are ok.
- */
+int
+callout_stop(struct callout *c)
+{
+       return _callout_stop(c, 0);
+}
+
+int
+callout_stop_sync(struct callout *c)
+{
+       return _callout_stop(c, 1);
+}
+
 void
-callout_terminate(struct callout *c)
+callout_stop_async(struct callout *c)
 {
-       softclock_pcpu_t sc;
+       _callout_stop(c, 0);
+}
 
-       if (c->c_flags & CALLOUT_DID_INIT) {
-               callout_stop(c);
-               if (c->c_gd) {
-                       sc = &softclock_pcpu_ary[c->c_gd->gd_cpuid];
-                       if (sc->running == c) {
-                               while (sc->running == c)
-                                       tsleep(&sc->running, 0, "crace", 1);
-                       }
-               }
-               KKASSERT((c->c_flags & (CALLOUT_PENDING|CALLOUT_ACTIVE)) == 0);
-               c->c_flags &= ~CALLOUT_DID_INIT;
-       }
+void
+callout_terminate(struct callout *c)
+{
+       _callout_stop(c, 1);
+       atomic_clear_int(&c->c_flags, CALLOUT_DID_INIT);
 }
 
 /*
  * Prepare a callout structure for use by callout_reset() and/or 
- * callout_stop().  The MP version of this routine requires that the callback
+ * callout_stop().
+ *
+ * The MP version of this routine requires that the callback
  * function installed by callout_reset() be MP safe.
  *
+ * The LK version of this routine is also MPsafe and will automatically
+ * acquire the specified lock for the duration of the function call,
+ * and release it after the function returns.  In addition, when autolocking
+ * is used, callout_stop() becomes synchronous if the caller owns the lock.
+ * callout_reset(), callout_stop(), and callout_stop_sync() will block
+ * normally instead of spinning when a cpu race occurs.  Lock cancelation
+ * is used to avoid deadlocks against the callout ring dispatch.
+ *
  * The init functions can be called from any cpu and do not have to be
  * called from the cpu that the timer will eventually run on.
  */
+static __inline
 void
-callout_init(struct callout *c)
+_callout_init(struct callout *c, int flags)
 {
        bzero(c, sizeof *c);
-       c->c_flags = CALLOUT_DID_INIT;
+       c->c_flags = flags;
+}
+
+void
+callout_init(struct callout *c)
+{
+       _callout_init(c, CALLOUT_DID_INIT);
 }
 
 void
 callout_init_mp(struct callout *c)
 {
-       callout_init(c);
-       c->c_flags |= CALLOUT_MPSAFE;
+       _callout_init(c, CALLOUT_DID_INIT | CALLOUT_MPSAFE);
+}
+
+void
+callout_init_lk(struct callout *c, struct lock *lk)
+{
+       _callout_init(c, CALLOUT_DID_INIT | CALLOUT_MPSAFE | CALLOUT_AUTOLOCK);
+       c->c_lk = lk;
 }
index 6030507..bdac4ac 100644 (file)
@@ -8,6 +8,8 @@
 #include <sys/queue.h>
 #endif
 
+#error "sctp_callout.h should never be used by dragonfly"
+
 /*
  * Copyright (C) 2002, 2003, 2004 Cisco Systems Inc,
  * All rights reserved.
index 27fa28e..7254e33 100644 (file)
@@ -1,7 +1,41 @@
-/*-
+/*
+ * Copyright (c) 2014 The DragonFly Project.  All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+/*
  * Copyright (c) 1990, 1993
  *     The Regents of the University of California.  All rights reserved.
  * (c) UNIX System Laboratories, Inc.
+ *
  * All or some portions of this file are derived from material licensed
  * to the University of California by American Telephone and Telegraph
  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
- *
- *     @(#)callout.h   8.2 (Berkeley) 1/21/94
- * $FreeBSD: src/sys/sys/callout.h,v 1.15.2.1 2001/11/13 18:24:52 archie Exp $
  */
 
 #ifndef _SYS_CALLOUT_H_
 #define _SYS_CALLOUT_H_
 
+#ifndef _SYS_QUEUE_H_
 #include <sys/queue.h>
+#endif
+#ifndef _SYS_LOCK_H_
+#include <sys/lock.h>
+#endif
+#ifndef _CPU_ATOMIC_H_
+#include <machine/atomic.h>
+#endif
 
 SLIST_HEAD(callout_list, callout);
 TAILQ_HEAD(callout_tailq, callout);
 
+/*
+ * Callwheel linkages are only adjusted on the target cpu.  All other
+ * actions are handled with atomic ops on any cpu.  callout_reset() and
+ * callout_stop() are always synchronous and will interlock against a
+ * running callout.  The caller might block, and a deadlock is possible
+ * if the caller does not use callout_init_lk() or is not careful with
+ * locks acquired in the callout function.
+ *
+ * Programers should note that our lockmgr locks have a cancelation feature
+ * which can be used to avoid deadlocks.  callout_init_lk() also uses this
+ * feature.
+ *
+ * callout_deactivate() is asynchronous and will not interlock against
+ * callout which is already running.
+ */
 struct callout {
        union {
                SLIST_ENTRY(callout) sle;
                TAILQ_ENTRY(callout) tqe;
        } c_links;
-       int     c_time;                 /* ticks to the event */
+       int     c_time;                 /* match tick on event */
+       int     c_load;                 /* load value for reset ipi */
        void    *c_arg;                 /* function argument */
        void    (*c_func) (void *);     /* function to call */
        int     c_flags;                /* state of this entry */
-       struct globaldata *c_gd;
+       int     c_unused02;
+       struct lock *c_lk;              /* auto-lock */
 };
 
-#define CALLOUT_LOCAL_ALLOC    0x0001 /* was allocated from callfree */
-#define CALLOUT_ACTIVE         0x0002 /* callout is currently active */
-#define CALLOUT_PENDING                0x0004 /* callout is waiting for timeout */
-#define CALLOUT_MPSAFE         0x0008 /* callout does not need the BGL */
-#define CALLOUT_DID_INIT       0x0010 /* safety check */
-#define CALLOUT_RUNNING                0x0020 /* function execution in progress */
+#define CALLOUT_ACTIVE         0x80000000 /* quick [de]activation flag */
+#define CALLOUT_PENDING                0x40000000 /* callout is on callwheel */
+#define CALLOUT_MPSAFE         0x20000000 /* callout does not need the BGL */
+#define CALLOUT_DID_INIT       0x10000000 /* safety check */
+#define CALLOUT_AUTOLOCK       0x08000000 /* auto locking / cancel feature */
+#define CALLOUT_WAITING                0x04000000 /* interlocked waiter */
+#define CALLOUT_EXECUTED       0x02000000 /* (generates stop status) */
+#define CALLOUT_ARMED          0x01000000 /* callout is assigned to cpu */
+#define CALLOUT_IPI_MASK       0x00000FFF /* ipi in-flight count mask */
+#define CALLOUT_CPU_MASK       0x00FFF000 /* ipi in-flight count mask */
+
+#define CALLOUT_FLAGS_TO_CPU(flags)    (((flags) & CALLOUT_CPU_MASK) >> 12)
+#define CALLOUT_CPU_TO_FLAGS(cpuid)    ((cpuid) << 12)
 
 struct callout_handle {
        struct callout *callout;
 };
 
 /*
- * WARNING!  These macros may only be used when the state of the callout
- * structure is stable, meaning from within the callback function or after
- * the callback function has been called but the timer has not yet been reset.
+ * WARNING! The caller is responsible for stabilizing the callout state,
+ *         our suggestion is to either manage the callout on the same cpu
+ *         or to use the callout_init_lk() feature and hold the lock while
+ *         making callout_*() calls.  The lock will be held automatically
+ *         by the callout wheel for any call-back and the callout wheel
+ *         will handle any callout_stop() deadlocks properly.
+ *
+ * active  -   Indicates that the callout is armed.  The callout can be in
+ *             any state other than a stopped state.  That is, the callout
+ *             reset could still be inflight to the target cpu and not yet
+ *             pending on the target cpu's callwheel, could be pending on
+ *             the callwheel, may have already executed (but not have been
+ *             stopped), or might be executing concurrently.
+ *
+ * deactivate -        Disarm the callout, preventing it from being executed if it
+ *             is queued or the queueing operation is in-flight.  Has no
+ *             effect if the callout has already been dispatched.  Does not
+ *             dequeue the callout.  Does not affect the status returned
+ *             by callout_stop().
+ *
+ *             Not serialized, caller must be careful when racing a new
+ *             callout_reset() that might be issued by the callback, which
+ *             will re-arm the callout.
+ *
+ * pending -   Only useful for same-cpu callouts, indicates that the callout
+ *             is pending on the callwheel or that a callout_reset() ipi
+ *             is in-flight.
  */
 #define        callout_active(c)       ((c)->c_flags & CALLOUT_ACTIVE)
-#define        callout_deactivate(c)   ((c)->c_flags &= ~CALLOUT_ACTIVE)
-#define        callout_pending(c)      ((c)->c_flags & CALLOUT_PENDING)
+
+#define        callout_deactivate(c)   atomic_clear_int(&(c)->c_flags, CALLOUT_ACTIVE)
+
+#define        callout_pending(c)      ((c)->c_flags & (CALLOUT_PENDING |      \
+                                                CALLOUT_IPI_MASK))
 
 #ifdef _KERNEL
 extern int     ncallout;
@@ -87,9 +177,11 @@ struct globaldata;
 void   hardclock_softtick(struct globaldata *);
 void   callout_init (struct callout *);
 void   callout_init_mp (struct callout *);
+void   callout_init_lk (struct callout *, struct lock *);
 void   callout_reset (struct callout *, int, void (*)(void *), void *);
 int    callout_stop (struct callout *);
-void   callout_stop_sync (struct callout *);
+void   callout_stop_async (struct callout *);
+int    callout_stop_sync (struct callout *);
 void   callout_terminate (struct callout *);
 void   callout_reset_bycpu (struct callout *, int, void (*)(void *), void *,
            int);