Post-and-poke style sync for the ksched
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 9 May 2012 02:45:27 +0000 (19:45 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Wed, 5 Sep 2012 21:43:57 +0000 (14:43 -0700)
Might change some of the details of the "poke-style", but I definitely
want at least a generic version of it (and all of its mb()s) to be
kernel-wide.

This is the same style of sync used in vcore_request(), though that one
is built in directly.

Note that we still use the ksched lock within in poke func - all this
commit does is create the poke style and use it to trigger the sched
mcp.  I'll deal with the lock holding shortly.

kern/include/atomic.h
kern/src/atomic.c
kern/src/schedule.c

index a25ccaf..2f7ce24 100644 (file)
@@ -99,6 +99,23 @@ static inline void write_sequnlock(seqlock_t *lock);
 static inline seq_ctr_t read_seqbegin(seqlock_t *lock);
 static inline bool read_seqretry(seqlock_t *lock, seq_ctr_t ctr);
 
+/* Post work and poke synchronization.  This is a wait-free way to make sure
+ * some code is run, usually by the calling core, but potentially by any core.
+ * Under contention, everyone just posts work, and one core will carry out the
+ * work.  Callers post work (the meaning of which is particular to their
+ * subsystem), then call this function.  The function is not run concurrently
+ * with itself.
+ *
+ * In the future, this may send RKMs to LL cores to ensure the work is done
+ * somewhere, but not necessarily on the calling core.  Will reserve 'flags'
+ * for that. */
+struct poke_tracker {
+       atomic_t                        need_to_run;
+       atomic_t                        run_in_progress;
+       void                            (*func)(void *);
+};
+void poke(struct poke_tracker *tracker, void *arg);
+
 /* Arch-specific implementations / declarations go here */
 #include <arch/atomic.h>
 
index e8e1147..dac394c 100644 (file)
@@ -60,6 +60,49 @@ void hash_unlock_irqsave(struct hashlock *hl, long key)
        spin_unlock_irqsave(get_spinlock(hl, key));
 }
 
+/* This is the 'post (work) and poke' style of sync.  We make sure the poke
+ * tracker's function runs.  Once this returns, the func either has run or is
+ * currently running (in case someone else is running now).  We won't wait or
+ * spin or anything, and it is safe to call this recursively (deeper in the
+ * call-graph).
+ *
+ * It's up to the caller to somehow post its work.  We'll also pass arg to the
+ * func, ONLY IF the caller is the one to execute it - so there's no guarantee
+ * the func(specific_arg) combo will actually run.  It's more for info
+ * purposes/optimizations/etc.  If no one uses it, I'll get rid of it. */
+void poke(struct poke_tracker *tracker, void *arg)
+{
+       atomic_set(&tracker->need_to_run, TRUE);
+       /* will need to repeatedly do it if someone keeps posting work */
+       do {
+               /* want an wrmb() btw posting work/need_to_run and in_progress.  the
+                * swap provides the HW mb. just need a cmb, which we do in the loop to
+                * cover the iterations (even though i can't imagine the compiler
+                * reordering the check it needed to do for the branch).. */
+               cmb();
+               /* poke / make sure someone does it.  if we get a TRUE (1) back, someone
+                * is already running and will deal with the posted work.  (probably on
+                * their next loop).  if we got a 0 back, we won the race and have the
+                * 'lock'. */
+               if (atomic_swap(&tracker->run_in_progress, TRUE))
+                       return;
+               /* if we're here, then we're the one who needs to run the func. */
+               /* clear the 'need to run', since we're running it now.  new users will
+                * set it again.  this write needs to be wmb()'d after in_progress.  the
+                * swap provided the HW mb(). */
+               cmb();
+               atomic_set(&tracker->need_to_run, FALSE);       /* no internal HW mb */
+               /* run the actual function.  the poke sync makes sure only one caller is
+                * in that func at a time. */
+               assert(tracker->func);
+               tracker->func(arg);
+               wmb();  /* ensure the in_prog write comes after the run_again. */
+               atomic_set(&tracker->run_in_progress, FALSE);   /* no internal HW mb */
+               /* in_prog write must come before run_again read */
+               wrmb();
+       } while (atomic_read(&tracker->need_to_run));   /* while there's more work*/
+}
+
 // Must be called in a pair with waiton_checklist
 int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask)
 {
index 6e9616e..4fbb946 100644 (file)
@@ -25,7 +25,6 @@
 struct proc_list unrunnable_scps = TAILQ_HEAD_INITIALIZER(unrunnable_scps);
 struct proc_list runnable_scps = TAILQ_HEAD_INITIALIZER(runnable_scps);
 struct proc_list all_mcps = TAILQ_HEAD_INITIALIZER(all_mcps);
-spinlock_t sched_lock = SPINLOCK_INITIALIZER;
 
 /* The pcores in the system.  (array gets alloced in init()).  */
 struct sched_pcore *all_pcores;
@@ -47,6 +46,37 @@ static void __prov_track_alloc(struct proc *p, uint32_t pcoreid);
 static void __prov_track_dealloc(struct proc *p, uint32_t pcoreid);
 static void __prov_track_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
                                       uint32_t nr_cores);
+static void __run_mcp_ksched(void *arg);       /* don't call directly */
+
+/* Locks / sync tools */
+
+/* poke-style ksched - ensures the MCP ksched only runs once at a time.  since
+ * only one mcp ksched runs at a time, while this is set, the ksched knows no
+ * cores are being allocated by other code (though they could be dealloc, due to
+ * yield). 
+ *
+ * The main value to this sync method is to make the 'make sure the ksched runs
+ * only once at a time and that it actually runs' invariant/desire wait-free, so
+ * that it can be called anywhere (deep event code, etc).
+ *
+ * As the ksched gets smarter, we'll probably embedd this poker in a bigger
+ * struct that can handle the posting of different types of work. */
+struct poke_tracker ksched_poker = {0, 0, __run_mcp_ksched};
+
+/* this 'big ksched lock' protects a bunch of things, which i may make fine
+ * grained: */
+/* - protects the integrity of proc tailqs/structures, as well as the membership
+ * of a proc on those lists.  proc lifetime within the ksched but outside this
+ * lock is protected by the proc kref. */
+//spinlock_t proclist_lock = SPINLOCK_INITIALIZER; /* subsumed by bksl */
+/* - protects the provisioning assignment, membership of sched_pcores in
+ * provision lists, and the integrity of all prov lists (the lists of each
+ * proc).  does NOT protect spc->alloc_proc. */
+//spinlock_t prov_lock = SPINLOCK_INITIALIZER;
+/* - protects allocation structures: spc->alloc_proc, the integrity and
+ * membership of the idelcores tailq. */
+//spinlock_t alloc_lock = SPINLOCK_INITIALIZER;
+spinlock_t sched_lock = SPINLOCK_INITIALIZER;
 
 /* Alarm struct, for our example 'timer tick' */
 struct alarm_waiter ksched_waiter;
@@ -199,6 +229,8 @@ int proc_change_to_m(struct proc *p)
  * grab whatever lock you have, then call the proc helper. */
 void proc_wakeup(struct proc *p)
 {
+       /* catch current shitty deadlock... */
+       assert(!per_cpu_info[core_id()].lock_depth);
        spin_lock(&sched_lock);
        /* will trigger one of the __sched_.cp_wakeup()s */
        __proc_wakeup(p);
@@ -308,13 +340,14 @@ static bool __schedule_scp(void)
        return FALSE;
 }
 
-/* Something has changed, and for whatever reason the scheduler should
- * reevaluate things. 
- *
- * Don't call this from interrupt context (grabs proclocks). */
-void schedule(void)
+/* Actual work of the MCP kscheduler.  if we were called by poke_ksched, *arg
+ * might be the process who wanted special service.  this would be the case if
+ * we weren't already running the ksched.  Sort of a ghetto way to "post work",
+ * such that it's an optimization. */
+static void __run_mcp_ksched(void *arg)
 {
        struct proc *p, *temp;
+       /* TODO: don't hold the sched_lock the whole time */
        spin_lock(&sched_lock);
        /* trivially try to handle the needs of all our MCPS.  smarter schedulers
         * would do something other than FCFS */
@@ -327,37 +360,42 @@ void schedule(void)
                        continue;
                __core_request(p);
        }
-       if (management_core())
-               __schedule_scp();
        spin_unlock(&sched_lock);
 }
 
+/* Something has changed, and for whatever reason the scheduler should
+ * reevaluate things. 
+ *
+ * Don't call this from interrupt context (grabs proclocks). */
+void schedule(void)
+{
+       /* MCP scheduling: post work, then poke.  for now, i just want the func to
+        * run again, so merely a poke is sufficient. */
+       poke(&ksched_poker, 0);
+       if (management_core()) {
+               spin_lock(&sched_lock);
+               __schedule_scp();
+               spin_unlock(&sched_lock);
+       }
+}
+
 /* A process is asking the ksched to look at its resource desires.  The
  * scheduler is free to ignore this, for its own reasons, so long as it
  * eventually gets around to looking at resource desires. */
 void poke_ksched(struct proc *p, int res_type)
 {
-       /* TODO: probably want something to trigger all res_types */
-       spin_lock(&sched_lock);
-       switch (res_type) {
-               case RES_CORES:
-                       /* ignore core requests from non-mcps (note we have races if we ever
-                        * allow procs to switch back). */
-                       if (!__proc_is_mcp(p))
-                               break;
-                       __core_request(p);
-                       break;
-               default:
-                       break;
-       }
-       spin_unlock(&sched_lock);
+       /* ignoring res_type for now.  could post that if we wanted (would need some
+        * other structs/flags) */
+       if (!__proc_is_mcp(p))
+               return;
+       poke(&ksched_poker, p);
 }
 
 /* ksched callbacks.  p just woke up, is unlocked, and the ksched lock is held */
 void __sched_mcp_wakeup(struct proc *p)
 {
-       /* the essence of poke_ksched for RES_CORES */
-       __core_request(p);
+       /* could try and prioritize p somehow (move it to the front of the list) */
+       poke(&ksched_poker, p);
 }
 
 /* ksched callbacks.  p just woke up, is unlocked, and the ksched lock is held */