Kernel scheduler tracks procs 'cradle to grave'
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 20 Apr 2012 21:20:02 +0000 (14:20 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 23 Apr 2012 23:03:27 +0000 (16:03 -0700)
Previously, the ksched would only know about processes whenever it
needed to make a decisions.  For MCPs, this was always.  For SCPs, it
was only when runnable.  Now it knows about them from register_proc()
(called during proc creation) until proc_destroy(), which recently
became a ksched function (this was part of the motivation for that).

This also allows the ksched to not need to poll the queues to detect if
someone is dying or not.  That messiness is gone, and the ksched just
gets called for proc_destroy().

Documentation/kref.txt
kern/include/env.h
kern/include/process.h
kern/include/schedule.h
kern/src/process.c
kern/src/schedule.c

index 17e2473..7cb11c0 100644 (file)
@@ -33,7 +33,7 @@ kref_get_not_zero().  You must have an internal reference for this.  And to
 protect that *internal* reference, you often need to lock or otherwise sync
 around the source of that internal reference (usually a list-like structure
 (LLS)), unless that ref is otherwise protected from concurrent freeing.
-4. If you plan to ressurect an object (make its refcnt go from 0 to 1), you
+4. If you plan to resurrect an object (make its refcnt go from 0 to 1), you
 need to use some other form of sync between the final freeing and the
 resurrection.
 
@@ -46,7 +46,7 @@ put the release function in the kref, which is what Linux used to do.  We do it
 to cut down on the number of places the function pointer is writen, since I
 expect those to change a lot as subsystems use krefs.  Finally, we only use
 krefs to trigger an object's release function, which might not free them
-forever.  They can be "ressurectd" back to having an external reference.  You
+forever.  They can be "resurrected" back to having an external reference.  You
 can do similar things in Linux, but it's not clear (to me) how separate that
 idea is from a kref.
 
@@ -133,7 +133,7 @@ which then the cache reader gets instead of failing at trying to get the
 original object.  The kref refcount only helps when the refcount goes from 1 to
 0, and on triggering the followup/release action.
 
-To ressurect, we can't just do:
+To resurrect, we can't just do:
        if (!kref_refcnt(&dentry->d_kref))
                kref_init(&dentry->d_kref, dentry_release, 1);
        else
@@ -143,7 +143,7 @@ There is a race on reading the refcnt and mucking with it.  If it is
 concurrently going from 1 -> 0, and we read 0, it is okay.  We still up it to 1.
 However, if we go from 1 -> 0 and read 1, we'll panic when we try to kref_get a
 0'd kref.  Also, doing this would be dangerous going from 0 -> 1 if other code
-would ressurect (which it does not!).  The solution is to use a kref_get that
+would resurrect (which it does not!).  The solution is to use a kref_get that
 doesn't care about 0 (__kref_get()).
 
 Elsewhere in this documentation, we talk about kref_get_not_zero().  That one
@@ -154,7 +154,7 @@ what we want.
 Trickiness with lockless data structures:
 ----------------------------
 Ideally, we want concurrent access to the dentry cache (or whatever cache has
-krefd objects that we want to ressurect).  Perhaps this is with CAS on linked
+krefd objects that we want to resurrect).  Perhaps this is with CAS on linked
 lists, or locks per hash bucket.  Since we need to prevent the resurrection of
 objects from proceeding while another thread could be trying to remove them, we
 need some sync between readers and writers.  Both threads in the scenario we've
index 35c5459..71920d3 100644 (file)
 #include <atomic.h>
 #include <mm.h>
 #include <vfs.h>
+#include <schedule.h>
 
 /* List def for the three vcore lists */
 TAILQ_HEAD(vcore_tailq, vcore);
 
 // TODO: clean this up.
 struct proc {
-       TAILQ_ENTRY(proc) proc_link NOINIT;     // Free list link pointers
        TAILQ_ENTRY(proc) proc_arsc_link NOINIT; // Free list link pointers for the arsc list
        spinlock_t proc_lock;
        trapframe_t env_tf;                                             // Saved registers
@@ -42,6 +42,8 @@ struct proc {
        struct vcore_tailq online_vcs;
        struct vcore_tailq bulk_preempted_vcs;
        struct vcore_tailq inactive_vcs;
+       /* Scheduler mgmt (info, data, whatever) */
+       struct sched_proc_data ksched_data;
 
        /* Cache color map: bitmap of the cache colors currently allocated to this
         * process */
index ed15ea6..20fe682 100644 (file)
@@ -52,8 +52,6 @@
 
 #include <env.h>
 
-TAILQ_HEAD(proc_list, proc);           /* Declares 'struct proc_list' */
-
 /* Can use a htable iterator to iterate through all active procs */
 extern struct hashtable *pid_hash;
 extern spinlock_t pid_hash_lock;
index 5b5754c..30f86a3 100644 (file)
 #define ROS_KERN_SCHEDULE_H
 
 #include <ros/common.h>
+#include <sys/queue.h>
 
 struct proc;   /* process.h includes us, but we need pointers now */
+TAILQ_HEAD(proc_list, proc);           /* Declares 'struct proc_list' */
+
+/* One of these embedded in every struct proc */
+struct sched_proc_data {
+       TAILQ_ENTRY(proc)                       proc_link;                      /* tailq linkage */
+       struct proc_list                        *cur_list;                      /* which tailq we're on */
+};
 
 void schedule_init(void);
 
 /************** Process registration **************/
-/* _S procs will get 'scheduled' every time they become RUNNABLE.  MCPs will get
- * registered on creation, and then that's it.  They will get removed from the
- * lists 'naturally' when proc_destroy() sets their state to DYING.  The ksched
- * needs to notice that, remove them from its lists, and decref. */
-/* _S is runnable, tell the ksched to try to run it. */
+/* Tell the ksched about the process, which it will track cradle-to-grave */
+void register_proc(struct proc *p);
+
+/* _S is now runnable, tell the ksched to try to run it. */
 void schedule_scp(struct proc *p);
-/* _M exists.  Tell the ksched about it. */
+
+/* p is now an _M.  Tell the ksched about it. */
 void register_mcp(struct proc *p);
 
 /* The ksched starts the death process (lock ordering issue), which calls back
index 3ed127e..63ce36d 100644 (file)
@@ -306,6 +306,8 @@ error_t proc_alloc(struct proc **pp, struct proc *parent)
  * push setting the state to CREATED into here. */
 void __proc_ready(struct proc *p)
 {
+       /* Tell the ksched about us */
+       register_proc(p);
        spin_lock(&pid_hash_lock);
        hashtable_insert(pid_hash, (void*)(long)p->pid, p);
        spin_unlock(&pid_hash_lock);
index ff8d04e..d32ce0c 100644 (file)
@@ -19,7 +19,9 @@
 #include <alarm.h>
 #include <sys/queue.h>
 
-/* Process Lists */
+/* Process Lists.  'unrunnable' is a holding list for SCPs that are running or
+ * waiting or otherwise not considered for sched decisions. */
+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;
@@ -40,6 +42,10 @@ uint32_t num_mgmtcores = 1;
 /* Helper, defined below */
 static void __core_request(struct proc *p);
 static void __put_idle_cores(uint32_t *pc_arr, uint32_t num);
+static void add_to_list(struct proc *p, struct proc_list *list);
+static void remove_from_list(struct proc *p, struct proc_list *list);
+static void switch_lists(struct proc *p, struct proc_list *old,
+                         struct proc_list *new);
 
 /* Alarm struct, for our example 'timer tick' */
 struct alarm_waiter ksched_waiter;
@@ -130,25 +136,63 @@ void schedule_init(void)
        return;
 }
 
-/* TODO: the proc lock is currently held for sched and register, though not
- * currently in any situations that can deadlock */
-/* _S procs are scheduled like in traditional systems */
+/* Round-robins on whatever list it's on */
+static void add_to_list(struct proc *p, struct proc_list *new)
+{
+       TAILQ_INSERT_TAIL(new, p, ksched_data.proc_link);
+       p->ksched_data.cur_list = new;
+}
+
+static void remove_from_list(struct proc *p, struct proc_list *old)
+{
+       assert(p->ksched_data.cur_list == old);
+       TAILQ_REMOVE(old, p, ksched_data.proc_link);
+}
+
+static void switch_lists(struct proc *p, struct proc_list *old,
+                         struct proc_list *new)
+{
+       remove_from_list(p, old);
+       add_to_list(p, new);
+}
+
+/* Removes from whatever list p is on */
+static void remove_from_any_list(struct proc *p)
+{
+       assert(p->ksched_data.cur_list);
+       TAILQ_REMOVE(p->ksched_data.cur_list, p, ksched_data.proc_link);
+}
+
+void register_proc(struct proc *p)
+{
+       /* one ref for the proc's existence, cradle-to-grave */
+       proc_incref(p, 1);      /* need at least this OR the 'one for existing' */
+       spin_lock(&sched_lock);
+       add_to_list(p, &unrunnable_scps);
+       spin_unlock(&sched_lock);
+}
+
+/* TODO: the proc lock is currently held for sched and register */
+/* sched_scp tells us to try and run the scp
+ * TODO: change this horrible name */
 void schedule_scp(struct proc *p)
 {
-       /* up the refcnt since we are storing the reference */
-       proc_incref(p, 1);
        spin_lock(&sched_lock);
        printd("Scheduling PID: %d\n", p->pid);
-       TAILQ_INSERT_TAIL(&runnable_scps, p, proc_link);
+       switch_lists(p, &unrunnable_scps, &runnable_scps);
        spin_unlock(&sched_lock);
 }
 
-/* important to only call this on RUNNING_S, for now */
+/* Tells us the proc is now an mcp.  Assuming it was RUNNING before */
+/* TODO: the proc lock is currently held for sched and register */
 void register_mcp(struct proc *p)
 {
-       proc_incref(p, 1);
        spin_lock(&sched_lock);
-       TAILQ_INSERT_TAIL(&all_mcps, p, proc_link);
+       /* For now, this should only ever be called on an unrunnable.  It's probably
+        * a bug, at this stage in development, to do o/w. */
+       remove_from_list(p, &unrunnable_scps);
+       //remove_from_any_list(p);      /* ^^ instead of this */
+       add_to_list(p, &all_mcps);
        spin_unlock(&sched_lock);
        //poke_ksched(p, RES_CORES);
 }
@@ -170,8 +214,11 @@ void proc_destroy(struct proc *p)
        if (__proc_destroy(p, pc_arr, &nr_cores_revoked)) {
                /* Do our cleanup.  note that proc_free won't run since we have an
                 * external reference, passed in */
-               /* TODO: pull from lists (no list polling), free structs, etc. */
 
+               /* Remove from whatever list we are on */
+               remove_from_any_list(p);
+               /* Drop the cradle-to-the-grave reference, jet-li */
+               proc_decref(p);
                /* Put the cores back on the idlecore map.  For future changes, be
                 * careful with the idle_lock.  It's safe to call this here or outside
                 * the sched lock (for now). */
@@ -191,42 +238,33 @@ static bool __schedule_scp(void)
        uint32_t pcoreid = core_id();
        struct per_cpu_info *pcpui = &per_cpu_info[pcoreid];
        int8_t state = 0;
-       /* prune any dying SCPs at the head of the queue and maybe sched our core
-        * (let all the cores do this, whoever happens to be running schedule()). */
-       while ((p = TAILQ_FIRST(&runnable_scps))) {
-               if (p->state == PROC_DYING) {
-                       TAILQ_REMOVE(&runnable_scps, p, proc_link);
-                       proc_decref(p);
-               } else {
-                       /* protect owning proc, cur_tf, etc.  note this nests with the
-                        * calls in proc_yield_s */
-                       disable_irqsave(&state);
-                       /* someone is currently running, dequeue them */
-                       if (pcpui->owning_proc) {
-                               printd("Descheduled %d in favor of %d\n",
-                                      pcpui->owning_proc->pid, p->pid);
-                               __proc_yield_s(pcpui->owning_proc, pcpui->cur_tf);
-                               /* round-robin the SCPs */
-                               TAILQ_INSERT_TAIL(&runnable_scps, pcpui->owning_proc,
-                                                 proc_link);
-                               /* could optimize the refcnting if we cared */
-                               proc_incref(pcpui->owning_proc, 1);
-                               clear_owning_proc(pcoreid);
-                               /* Note we abandon core.  It's not strictly necessary.  If
-                                * we didn't, the TLB would still be loaded with the old
-                                * one, til we proc_run_s, and the various paths in
-                                * proc_run_s would pick it up.  This way is a bit safer for
-                                * future changes, but has an extra (empty) TLB flush.  */
-                               abandon_core();
-                       } 
-                       /* Run the new proc */
-                       TAILQ_REMOVE(&runnable_scps, p, proc_link);
-                       printd("PID of the SCP i'm running: %d\n", p->pid);
-                       proc_run_s(p);  /* gives it core we're running on */
-                       proc_decref(p);
-                       enable_irqsave(&state);
-                       return TRUE;
-               }
+       /* if there are any runnables, run them here and put any currently running
+        * SCP on the tail of the runnable queue. */
+       if ((p = TAILQ_FIRST(&runnable_scps))) {
+               /* protect owning proc, cur_tf, etc.  note this nests with the
+                * calls in proc_yield_s */
+               disable_irqsave(&state);
+               /* someone is currently running, dequeue them */
+               if (pcpui->owning_proc) {
+                       printd("Descheduled %d in favor of %d\n", pcpui->owning_proc->pid,
+                              p->pid);
+                       __proc_yield_s(pcpui->owning_proc, pcpui->cur_tf);
+                       /* round-robin the SCPs (inserts at the end of the queue) */
+                       switch_lists(pcpui->owning_proc, &unrunnable_scps, &runnable_scps);
+                       clear_owning_proc(pcoreid);
+                       /* Note we abandon core.  It's not strictly necessary.  If
+                        * we didn't, the TLB would still be loaded with the old
+                        * one, til we proc_run_s, and the various paths in
+                        * proc_run_s would pick it up.  This way is a bit safer for
+                        * future changes, but has an extra (empty) TLB flush.  */
+                       abandon_core();
+               } 
+               /* Run the new proc */
+               switch_lists(p, &runnable_scps, &unrunnable_scps);
+               printd("PID of the SCP i'm running: %d\n", p->pid);
+               proc_run_s(p);  /* gives it core we're running on */
+               enable_irqsave(&state);
+               return TRUE;
        }
        return FALSE;
 }
@@ -241,17 +279,8 @@ void schedule(void)
        spin_lock(&sched_lock);
        /* trivially try to handle the needs of all our MCPS.  smarter schedulers
         * would do something other than FCFS */
-       TAILQ_FOREACH_SAFE(p, &all_mcps, proc_link, temp) {
+       TAILQ_FOREACH_SAFE(p, &all_mcps, ksched_data.proc_link, temp) {
                printd("Ksched has MCP %08p (%d)\n", p, p->pid);
-               /* If they are dying, abort.  There's a bit of a race here.  If they
-                * start dying right after the check, core_request/give_cores would
-                * start dealing with a DYING proc.  The code can handle it, but this
-                * will probably change. */
-               if (p->state == PROC_DYING) {
-                       TAILQ_REMOVE(&all_mcps, p, proc_link);
-                       proc_decref(p);
-                       continue;
-               }
                if (!num_idlecores)
                        break;
                /* TODO: might use amt_wanted as a proxy.  right now, they have
@@ -436,10 +465,14 @@ static void __core_request(struct proc *p)
 void sched_diag(void)
 {
        struct proc *p;
-       TAILQ_FOREACH(p, &runnable_scps, proc_link)
-               printk("_S PID: %d\n", p->pid);
-       TAILQ_FOREACH(p, &all_mcps, proc_link)
+       spin_lock(&sched_lock);
+       TAILQ_FOREACH(p, &runnable_scps, ksched_data.proc_link)
+               printk("Runnable _S PID: %d\n", p->pid);
+       TAILQ_FOREACH(p, &unrunnable_scps, ksched_data.proc_link)
+               printk("Unrunnable _S PID: %d\n", p->pid);
+       TAILQ_FOREACH(p, &all_mcps, ksched_data.proc_link)
                printk("MCP PID: %d\n", p->pid);
+       spin_unlock(&sched_lock);
        return;
 }