ev_qs can request fallback to active vcores (XCC)
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 15 Aug 2011 22:02:27 +0000 (15:02 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:06 +0000 (17:36 -0700)
Fallback allows vcores to yield and not worry about missed INDIR events.
Read the documentation.

2LS writers can use vcore_yield() in a loop to try and yield properly.
Note that this will return.  Check the pthread code for an example of
how to handle this.

Reinstall your kernel headers.

Documentation/async_events.txt
kern/include/ros/event.h
kern/include/ros/procdata.h
kern/src/event.c
kern/src/process.c
user/parlib/vcore.c
user/pthread/pthread.c

index 49a4ef9..e1b04ce 100644 (file)
@@ -359,12 +359,15 @@ vcore is offline.
 
 3.3.2: Fallback
 ---------------
 
 3.3.2: Fallback
 ---------------
-Both IPI and INDIR need an actual vcore.  If that vcore is offline and if
-EVENT_FALLBACK is set, the kernel will pick an online vcore and send the
-messages there.  This allows an ev_q to be set up to handle work when the vcore
-is online, while allowing the program to handle events when that core goes
-offline: perhaps due to a yield or a preemption, without having to reset all of
-its ev_qs to point to "known" online vcores (and avoiding those races).
+Both IPI and INDIR need an actual vcore.  If that vcore is unavailable and if
+EVENT_FALLBACK is set, the kernel will pick another vcore and send the messages
+there.  This allows an ev_q to be set up to handle work when the vcore is
+online, while allowing the program to handle events when that core yields,
+without having to reset all of its ev_qs to point to "known" available vcores
+(and avoiding those races).  Note 'online' is synonymous with 'mapped', when
+talking about vcores.  A vcore technically isn't always online, only destined to
+be online, when it is mapped to a pcore (kmsg on the way, etc).  It's easiest to
+think of it being online for the sake of this discussion.
 
 One question is whether or not 2LSs need a FALLBACK flag for their ev_qs.  The
 main use for FALLBACK is so that vcores can yield.  (Note that fallback won't
 
 One question is whether or not 2LSs need a FALLBACK flag for their ev_qs.  The
 main use for FALLBACK is so that vcores can yield.  (Note that fallback won't
@@ -377,6 +380,36 @@ is that other vcores will build up a list of ev_qs that they aren't aware of,
 which will be hard to deal with when *they* yield.  FALLBACK avoids all of those
 problems.
 
 which will be hard to deal with when *they* yield.  FALLBACK avoids all of those
 problems.
 
+An important aspect of FALLBACK is that it works with yielded vcores, not
+preempted vcores.  It could be that there are no cores that are online, but
+there should always be at least one core that *will* be online in the future, a
+core that the process didn't want to lose and will deal with in the future.  If
+not for this distinction, FALLBACK could fail.  An older idea would be to have
+fallback send the msg to the desired vcore if there were no others.  This would
+not work if the vcore yielded and then the entire process was preempted or
+otherwise not running.  Another way to put this is that we need a field to
+determine whether a vcore is offline temporarily or permanently.
+
+This is why we have the VCPD field 'can_rcv_msg'.  It tells the kernel's event
+delivery code that the vcore will check the messages: it is an acceptable
+destination for a FALLBACK.  There are two reasons to put this in VCPD:
+1) Userspace can remotely turn off a vcore's msg reception.  This is necessary
+for handling preemption of a vcore that was in uthread context, so that we can
+remotely 'yield' the core without having to sys_change_vcore() (which I discuss
+below, and is meant to 'unstick' a vcore).
+2) Yield is simplified.  The kernel no longer races with itself nor has to worry
+about turning off that flag - userspace can do it when it wants to yield.  (turn
+off the flag, check messages, then yield).
+
+Two aspects of the code make this work nicely.  The 'can_rcv_msg' flag greatly
+simplifies the kernel's job.  There are a lot of weird races we'd have to deal
+with, such as process state (RUNNING_M), whether a mass preempt is going on, or
+just one core, or a bunch of cores, mass yields, etc.  A flag that does one
+thing well helps a lot - esp since preemption is not the same as yielding.  The
+other useful thing is being able to handle spurious events.  Vcore code can
+handle extra IPIs and INDIRs to non-VCPD ev_qs.  Any vcore can handle an ev_q
+that is "non-VCPD business".
+
 Also, in case this comes up, there's a slight race on changing the mbox* and the
 vcore number within the event_q.  The message could have gone to the wrong (old)
 vcore, but not the IPI.  Not a big deal - IPIs can be spurious, and the other
 Also, in case this comes up, there's a slight race on changing the mbox* and the
 vcore number within the event_q.  The message could have gone to the wrong (old)
 vcore, but not the IPI.  Not a big deal - IPIs can be spurious, and the other
index f53050e..1eacd68 100644 (file)
@@ -91,6 +91,7 @@ struct preempt_data {
        uintptr_t                                       transition_stack;       /* advertised by the user */
        bool                                            notif_enabled;          /* vcore willing to recv */
        bool                                            notif_pending;          /* notif k_msg on the way */
        uintptr_t                                       transition_stack;       /* advertised by the user */
        bool                                            notif_enabled;          /* vcore willing to recv */
        bool                                            notif_pending;          /* notif k_msg on the way */
+       bool                                            can_rcv_msg;            /* can receive FALLBACK */
        seq_ctr_t                                       preempt_tf_valid;
        struct event_mbox                       ev_mbox;
 };
        seq_ctr_t                                       preempt_tf_valid;
        struct event_mbox                       ev_mbox;
 };
index 4c61c6f..80a1ae5 100644 (file)
@@ -33,9 +33,7 @@ typedef struct procdata {
 
 #define PROCDATA_NUM_PAGES  ((sizeof(procdata_t)-1)/PGSIZE + 1)
 
 
 #define PROCDATA_NUM_PAGES  ((sizeof(procdata_t)-1)/PGSIZE + 1)
 
-// this is how user programs access the procdata page
-#ifndef ROS_KERNEL
-# define __procdata (*(procdata_t*)UDATA)
-#endif
+/* TODO: I dislike having this not be a pointer (for kernel programming) */
+#define __procdata (*(procdata_t*)UDATA)
 
 
-#endif // !ROS_PROCDATA_H
+#endif /* ROS_PROCDATA_H */
index 14d14d8..e2c1b2b 100644 (file)
@@ -20,8 +20,7 @@
  * current loaded to access this, and it will work for any process. */
 static struct event_mbox *get_proc_ev_mbox(uint32_t vcoreid)
 {
  * current loaded to access this, and it will work for any process. */
 static struct event_mbox *get_proc_ev_mbox(uint32_t vcoreid)
 {
-       struct procdata *pd = (struct procdata*)UDATA;
-       return &pd->vcore_preempt_data[vcoreid].ev_mbox;
+       return &__procdata.vcore_preempt_data[vcoreid].ev_mbox;
 }
 
 /* Posts a message to the mbox, subject to flags.  Feel free to send 0 for the
 }
 
 /* Posts a message to the mbox, subject to flags.  Feel free to send 0 for the
@@ -44,6 +43,112 @@ static void post_ev_msg(struct event_mbox *mbox, struct event_msg *msg,
        }
 }
 
        }
 }
 
+/* Can we alert the vcore?  (Will it check its messages).  Note this checks
+ * procdata via the user pointer. */
+static bool can_alert_vcore(struct proc *p, uint32_t vcoreid)
+{
+       struct preempt_data *vcpd = &__procdata.vcore_preempt_data[vcoreid];
+       return vcpd->can_rcv_msg;
+}
+
+/* Scans the vcoremap, looking for an alertable vcore (returing that vcoreid).
+ * If this fails, it's userspace's fault, so we'll complain loudly.  
+ *
+ * It is possible for a vcore to yield and toggle this flag off before we post
+ * the indir, which is why we have that loop in alert_vcore().
+ *
+ * Note this checks procdata via the user pointer. */
+uint32_t find_alertable_vcore(struct proc *p, uint32_t start_loc)
+{
+       struct procinfo *pi = p->procinfo;
+       for (uint32_t i = start_loc; i < pi->max_vcores; i++) {
+               if (can_alert_vcore(p, i)) {
+                       return i;
+               }
+       }
+       /* if we're here, the program is likely fucked.  buggy at least */
+       printk("[kernel] no vcores can recv messages!  (user bug)\n");
+       return 0;       /* vcore 0 is the most likely to come back online */
+}
+
+/* Helper to send an indir, called from a couple places */
+static void send_indir_to_vcore(struct event_queue *ev_q, uint32_t vcoreid)
+{
+       struct event_msg local_msg = {0};
+       local_msg.ev_type = EV_EVENT;
+       local_msg.ev_arg3 = ev_q;
+       post_ev_msg(get_proc_ev_mbox(vcoreid), &local_msg, 0);
+}
+
+/* Helper that alerts a vcore, by IPI and/or INDIR, that it needs to check the
+ * ev_q.  Handles FALLBACK and other tricky things.  Returns which vcore was
+ * alerted.  The only caller of this is send_event(), and this makes it a little
+ * clearer/easier.
+ *
+ * One of the goals of FALLBACK (and this func) is to allow processes to yield
+ * cores without fear of losing messages (INDIR messages, btw (aka, non-vcore
+ * business)).
+ *
+ * The plan for dealing with FALLBACK is that we get a good vcoreid (can recv
+ * messages), then do the IPI/INDIRs, and then check to make sure the vcore is
+ * still good.  If the vcore is no longer available, we find another.  Userspace
+ * will make sure to turn off the can_recv_msg flag (and then check for messages
+ * again) before yielding.
+ *
+ * I don't particularly care if the vcore is offline or not for INDIRs.  There
+ * is a small window when a vcore is offline but can receive messages AND that
+ * another vcore is online.  This would only happen when a vcore doesn't respond
+ * to a preemption.  This would NOT happen when the entire process was preempted
+ * (which is when I would want to send to the initial offline vcore anyway).  In
+ * short, if can_recv is set, I'll send it there, and let userspace handle the
+ * rare "unresponsive" preemption.  There are a lot of legit reasons why a vcore
+ * would be offline (or preempt_pending) and have can_recv set.
+ *
+ * IPIs don't matter as much.  We'll send them to the (fallback) vcore, but
+ * never send them to an offline vcore.  If we lose a race and try to IPI an
+ * offline core, proc_notify can handle it.  I do the checks here to avoid some
+ * future pain (for now). */
+static uint32_t alert_vcore(struct proc *p, struct event_queue *ev_q,
+                            uint32_t vcoreid)
+{
+       int num_loops = 0;
+       /* Don't care about FALLBACK, just send and be done with it */
+       if (!ev_q->ev_flags & EVENT_FALLBACK) {
+               if (ev_q->ev_flags & EVENT_INDIR)
+                       send_indir_to_vcore(ev_q, vcoreid);
+               /* Don't bother with the IPI if the vcore is offline */
+               if ((ev_q->ev_flags & EVENT_IPI) && vcore_is_mapped(p, vcoreid))
+                       proc_notify(p, vcoreid);
+               return vcoreid;
+       }
+       /* If we're here, we care about FALLBACK.  Loop, trying vcores til we don't
+        * lose the race.  It's a user bug (which we'll comment on in a helper) if
+        * there are no vcores willing to rcv a message. */
+       do {
+               /* Sanity check.  Should never happen, unless we're buggy */
+               if (num_loops++ > MAX_NUM_CPUS)
+                       warn("Having a hard time finding an online vcore");
+               /* Preemptively try to get a 'good' vcoreid.  The vcore might actually
+                * be offline. */
+               if (!can_alert_vcore(p, vcoreid)) {
+                       vcoreid = 0;    /* start the search from 0, more likely to be on */
+                       vcoreid = find_alertable_vcore(p, vcoreid);
+               }
+               /* If we're here, we think the vcore can recv the INDIR */
+               if (ev_q->ev_flags & EVENT_INDIR)
+                       send_indir_to_vcore(ev_q, vcoreid);
+               /* Only send the IPI if it is also online (optimization) */
+               if ((ev_q->ev_flags & EVENT_IPI) && vcore_is_mapped(p, vcoreid))
+                       proc_notify(p, vcoreid);
+               wmb();
+               /* If the vcore now can't receive the message, we probably lost the
+                * race, so let's loop and try with another.  Some vcore is getting
+                * spurious messages, but those are not incorrect (just slows things a
+                * bit if we lost the race). */
+       } while (!can_alert_vcore(p, vcoreid));
+       return vcoreid;
+}
+
 /* Send an event to ev_q, based on the parameters in ev_q's flag.  We don't
  * accept null ev_qs, since the caller ought to be checking before bothering to
  * make a msg and send it to the event_q.  Vcoreid is who the kernel thinks the
 /* Send an event to ev_q, based on the parameters in ev_q's flag.  We don't
  * accept null ev_qs, since the caller ought to be checking before bothering to
  * make a msg and send it to the event_q.  Vcoreid is who the kernel thinks the
@@ -54,8 +159,7 @@ void send_event(struct proc *p, struct event_queue *ev_q, struct event_msg *msg,
                 uint32_t vcoreid)
 {
        struct proc *old_proc;
                 uint32_t vcoreid)
 {
        struct proc *old_proc;
-       struct event_mbox *ev_mbox = 0, *vcore_mbox;
-       struct event_msg local_msg = {0};
+       struct event_mbox *ev_mbox = 0;
        assert(p);
        printd("[kernel] sending msg to proc %08p, ev_q %08p\n", p, ev_q);
        if (!ev_q) {
        assert(p);
        printd("[kernel] sending msg to proc %08p, ev_q %08p\n", p, ev_q);
        if (!ev_q) {
@@ -115,19 +219,13 @@ void send_event(struct proc *p, struct event_queue *ev_q, struct event_msg *msg,
         * vehicle for sending the ev_type. */
        assert(msg);
        post_ev_msg(ev_mbox, msg, ev_q->ev_flags);
         * vehicle for sending the ev_type. */
        assert(msg);
        post_ev_msg(ev_mbox, msg, ev_q->ev_flags);
-       /* Vcore options: IPIs and INDIRs */
-       if (ev_q->ev_flags & EVENT_INDIR) {
-               vcore_mbox = get_proc_ev_mbox(vcoreid);
-               /* Help out userspace, since we can detect this bug:*/
-               if (ev_mbox == vcore_mbox)
-                       printk("[kernel] EVENT_INDIR requested for a VCPD mbox!\n");
-               /* Actually post the INDIR */
-               local_msg.ev_type = EV_EVENT;
-               local_msg.ev_arg3 = ev_q;
-               post_ev_msg(vcore_mbox, &local_msg, 0);
-       }
-       if (ev_q->ev_flags & EVENT_IPI)
-               proc_notify(p, vcoreid);
+       /* Prod/alert a vcore with an IPI or INDIR, if desired */
+       if ((ev_q->ev_flags & (EVENT_IPI | EVENT_INDIR)))
+               alert_vcore(p, ev_q, vcoreid);
+       /* TODO: If the whole proc is offline, this is where we can check and make
+        * it runnable (if we want).  Alternatively, we can do this only if they
+        * asked for IPIs or INDIRs. */
+
        /* Fall through */
 out:
        /* Return to the old address space. */
        /* Fall through */
 out:
        /* Return to the old address space. */
index 81d55c8..afa5a50 100644 (file)
@@ -870,14 +870,14 @@ void proc_notify(struct proc *p, uint32_t vcoreid)
                if (vcpd->notif_enabled) {
                        /* GIANT WARNING: we aren't using the proc-lock to protect the
                         * vcoremap.  We want to be able to use this from interrupt context,
                if (vcpd->notif_enabled) {
                        /* GIANT WARNING: we aren't using the proc-lock to protect the
                         * vcoremap.  We want to be able to use this from interrupt context,
-                        * and don't want the proc_lock to be an irqsave. */
+                        * and don't want the proc_lock to be an irqsave.  Spurious
+                        * __notify() kmsgs are okay (it checks to see if the right receiver
+                        * is current). */
                        if ((p->state & PROC_RUNNING_M) && // TODO: (VC#) (_S state)
                                      vcore_is_mapped(p, vcoreid)) {
                                printd("[kernel] sending notif to vcore %d\n", vcoreid);
                                send_kernel_message(get_pcoreid(p, vcoreid), __notify, (long)p,
                                                    0, 0, KMSG_ROUTINE);
                        if ((p->state & PROC_RUNNING_M) && // TODO: (VC#) (_S state)
                                      vcore_is_mapped(p, vcoreid)) {
                                printd("[kernel] sending notif to vcore %d\n", vcoreid);
                                send_kernel_message(get_pcoreid(p, vcoreid), __notify, (long)p,
                                                    0, 0, KMSG_ROUTINE);
-                       } else { // TODO: think about this, fallback, etc
-                               warn("Vcore unmapped, not receiving an active notif");
                        }
                }
        }
                        }
                }
        }
@@ -1406,9 +1406,15 @@ void __startcore(struct trapframe *tf, uint32_t srcid, long a0, long a1, long a2
                proc_decref(p_to_run);
        vcoreid = get_vcoreid(p_to_run, pcoreid);
        vcpd = &p_to_run->procdata->vcore_preempt_data[vcoreid];
                proc_decref(p_to_run);
        vcoreid = get_vcoreid(p_to_run, pcoreid);
        vcpd = &p_to_run->procdata->vcore_preempt_data[vcoreid];
+       /* We could let userspace do this, though they come into vcore entry many
+        * times, and we just need this to happen when the cores comes online the
+        * first time.  That, and they want this turned on as soon as we know a
+        * vcore *WILL* be online.  We could also do this earlier, when we map the
+        * vcore to its pcore, though we don't always have current loaded or
+        * otherwise mess with the VCPD in those code paths. */
+       vcpd->can_rcv_msg = TRUE;
        printd("[kernel] startcore on physical core %d for process %d's vcore %d\n",
               pcoreid, p_to_run->pid, vcoreid);
        printd("[kernel] startcore on physical core %d for process %d's vcore %d\n",
               pcoreid, p_to_run->pid, vcoreid);
-
        if (seq_is_locked(vcpd->preempt_tf_valid)) {
                __seq_end_write(&vcpd->preempt_tf_valid); /* mark tf as invalid */
                restore_fp_state(&vcpd->preempt_anc);
        if (seq_is_locked(vcpd->preempt_tf_valid)) {
                __seq_end_write(&vcpd->preempt_tf_valid); /* mark tf as invalid */
                restore_fp_state(&vcpd->preempt_anc);
index 79dbb69..e052a8d 100644 (file)
@@ -184,8 +184,19 @@ fail:
        return ret;
 }
 
        return ret;
 }
 
+/* This can return, if you failed to yield due to a concurrent event. */
 void vcore_yield()
 {
 void vcore_yield()
 {
+       uint32_t vcoreid = vcore_id();
+       struct preempt_data *vcpd = &__procdata.vcore_preempt_data[vcoreid];
+       vcpd->can_rcv_msg = FALSE;
+       wmb();
+       if (handle_events(vcoreid)) {
+               /* we handled outstanding events, turn the flag back on and return */
+               vcpd->can_rcv_msg = TRUE;
+               return;
+       }
+       /* o/w, we can safely yield */
        sys_yield(0);
 }
 
        sys_yield(0);
 }
 
index f8ce256..5a8f916 100644 (file)
@@ -95,7 +95,7 @@ struct uthread *pth_init(void)
        for (int i = 0; i < max_vcores(); i++) {
                /* Each vcore needs to point to a non-VCPD ev_q */
                sysc_mgmt[i].ev_q = get_big_event_q_raw();
        for (int i = 0; i < max_vcores(); i++) {
                /* Each vcore needs to point to a non-VCPD ev_q */
                sysc_mgmt[i].ev_q = get_big_event_q_raw();
-               sysc_mgmt[i].ev_q->ev_flags = EVENT_IPI | EVENT_INDIR;  /* up to you */
+               sysc_mgmt[i].ev_q->ev_flags = EVENT_IPI | EVENT_INDIR | EVENT_FALLBACK;
                sysc_mgmt[i].ev_q->ev_vcore = i;
                ucq_init_raw(&sysc_mgmt[i].ev_q->ev_mbox->ev_msgs, 
                             mmap_block + (2 * i    ) * PGSIZE, 
                sysc_mgmt[i].ev_q->ev_vcore = i;
                ucq_init_raw(&sysc_mgmt[i].ev_q->ev_mbox->ev_msgs, 
                             mmap_block + (2 * i    ) * PGSIZE, 
@@ -115,7 +115,7 @@ struct uthread *pth_init(void)
        ucq_init_raw(&sysc_mbox->ev_msgs, two_pages, two_pages + PGSIZE);
        for (int i = 0; i < max_vcores(); i++) {
                sysc_mgmt[i].ev_q = get_event_q();
        ucq_init_raw(&sysc_mbox->ev_msgs, two_pages, two_pages + PGSIZE);
        for (int i = 0; i < max_vcores(); i++) {
                sysc_mgmt[i].ev_q = get_event_q();
-               sysc_mgmt[i].ev_q->ev_flags = EVENT_IPI | EVENT_INDIR;
+               sysc_mgmt[i].ev_q->ev_flags = EVENT_IPI | EVENT_INDIR | EVENT_FALLBACK;
                sysc_mgmt[i].ev_q->ev_vcore = i;
                sysc_mgmt[i].ev_q->ev_mbox = sysc_mbox;
        }
                sysc_mgmt[i].ev_q->ev_vcore = i;
                sysc_mgmt[i].ev_q->ev_mbox = sysc_mbox;
        }
@@ -152,11 +152,10 @@ void __attribute__((noreturn)) pth_sched_entry(void)
        /* no one currently running, so lets get someone from the ready queue */
        struct pthread_tcb *new_thread = NULL;
        struct mcs_lock_qnode local_qn = {0};
        /* no one currently running, so lets get someone from the ready queue */
        struct pthread_tcb *new_thread = NULL;
        struct mcs_lock_qnode local_qn = {0};
-       /* For now, let's spin and handle events til we get a thread to run.  This
-        * will help catch races, instead of only having one core ever run a thread
-        * (if there is just one, etc).  Also, we don't need the EVENT_IPIs for this
-        * to work (since we poll handle_events() */
-       while (!new_thread) {
+       /* Try to get a thread.  If we get one, we'll break out and run it.  If not,
+        * we'll try to yield.  vcore_yield() might return, if we lost a race and
+        * had a new event come in, one that may make us able to get a new_thread */
+       do {
                handle_events(vcoreid);
                mcs_lock_notifsafe(&queue_lock, &local_qn);
                new_thread = TAILQ_FIRST(&ready_queue);
                handle_events(vcoreid);
                mcs_lock_notifsafe(&queue_lock, &local_qn);
                new_thread = TAILQ_FIRST(&ready_queue);
@@ -165,21 +164,16 @@ void __attribute__((noreturn)) pth_sched_entry(void)
                        TAILQ_INSERT_TAIL(&active_queue, new_thread, next);
                        threads_active++;
                        threads_ready--;
                        TAILQ_INSERT_TAIL(&active_queue, new_thread, next);
                        threads_active++;
                        threads_ready--;
+                       mcs_unlock_notifsafe(&queue_lock, &local_qn);
+                       break;
                }
                mcs_unlock_notifsafe(&queue_lock, &local_qn);
                }
                mcs_unlock_notifsafe(&queue_lock, &local_qn);
-       }
-       /* Instead of yielding, you could spin, turn off the core, set an alarm,
-        * whatever.  You want some logic to decide this.  Uthread code wil have
-        * helpers for this (like how we provide run_uthread()) */
-       if (!new_thread) {
-               /* Note, we currently don't get here (due to the while loop) */
+               /* no new thread, try to yield */
                printd("[P] No threads, vcore %d is yielding\n", vcore_id());
                printd("[P] No threads, vcore %d is yielding\n", vcore_id());
-               /* Not actually yielding - just spin for now, so we can get syscall
-                * unblocking events */
-               vcore_idle();
-               //sys_yield(0);
-               assert(0);
-       }
+               /* TODO: you can imagine having something smarter here, like spin for a
+                * bit before yielding (or not at all if you want to be greedy). */
+               vcore_yield();
+       } while (1);
        assert(((struct uthread*)new_thread)->state != UT_RUNNING);
        run_uthread((struct uthread*)new_thread);
        assert(0);
        assert(((struct uthread*)new_thread)->state != UT_RUNNING);
        run_uthread((struct uthread*)new_thread);
        assert(0);