Handles syscall-event overflow in pthreads
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 12 May 2011 01:29:36 +0000 (18:29 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:02 +0000 (17:36 -0700)
Most 2LSs that handle blocking threads and syscalls like pthreads will
need to do something similar.  Actually, they'll need to do something
more advanced!

This code knows how to recover from event overflow, which means that the
event message containing the struct syscall * was lost.

Recovery is a bit expensive, I think, so under heavy amounts of lost
messages, we'll want to do something smarter, like switch to a polling
mechanism, or find a way to use larger BCQs.

Documentation/async_events.txt
tests/block_test.c
user/parlib/event.c
user/parlib/include/event.h
user/parlib/include/uthread.h
user/parlib/uthread.c
user/pthread/pthread.c

index 0bf95c3..7f83521 100644 (file)
@@ -87,6 +87,8 @@ buffer is full).  This means that a process can produce for one of its ev_qs
 
 2. Async Syscalls and I/O
 ====================
+2.1 Basics
+----------------------------------------------
 The syscall struct is the contract for work with the kernel, including async
 I/O.  Lots of current OS async packages use epoll or other polling systems.
 Note the distinction between Polling and Async I/O.  Polling is about finding
@@ -127,6 +129,128 @@ notification event.  Some calls, like AIO or bulk accept, exist for a while
 and slowly get filled in / completed.  In the future, we'll also want a way to
 abort the in-progress syscalls (possibly any syscall!).
 
+2.2 Uthreads Blocking on Syscalls
+----------------------------------------------
+Many threading libraries will want some notion of a synchronous, blocking
+thread.  These threads use regular I/O calls, which are async under the hood,
+but don't want to bother with call backs or other details of async I/O.  In
+this section, I'll talk a bit about how this works, esp regarding
+uthreads/pthreads.
+
+'Blocking' refers to user threads, and has nothing to do with an actual
+process blocking/waiting on some kernel event.  The kernel does not know
+anything about what goes on here.  While a bit confusing, this allows
+applications to do whatever they want on top of an async interface, and is a
+consequence of decoupling cores from user-threads from kthreads.
+
+2.2.1 Basics of Uthread Blocking
+---------------
+When a thread calls a glibc function that makes a system call, if the syscall
+is not yet complete when the kernel returns to userspace, glibc will check for
+the existence of a second level scheduler and attempt to use it to yield its
+uthread.  If there is no 2LS, the code just spins for now.  Eventually, it
+will try to suspend/yield the process for a while (til the call is done), aka,
+block in the kernel.
+
+If there is a 2LS, the current thread will yield, and call out to the 2LS's
+blockon_sysc() method, which needs a way to stop the thread and be able to
+restart it when the syscall completes.  Specifically, the pthread 2LS puts the
+thread on a "syscall pending" list and registers the syscall to respond to an
+event (described in detail elsewhere in this doc).  When the event comes in,
+meaning the syscall is complete, the thread is put on the runnable list.
+
+Details:
+- A pointer to the struct pthread is stored in the syscall's void*.  You need
+  to be on the pending list before registering for the event (due to how we
+  handle event overflow recovery).  When the syscall is done, we normally get
+  a message from the kernel, and the payload tells us the syscall is done,
+  which tells us which thread to unblock. 
+- The pthread code also always asks for an IPI and event message for every
+  syscall that completes.  This is far from ideal.  Still, the basics are the
+  same for any threading library.  Once you know a thread is done, you need to
+  do something about it.
+- The pthread code does syscall blocking/ pending lists and event notification
+  on a per-core basis.
+- There's a race between the 2LS trying to sign up for events and the kernel
+  finishing the event.  We handle this in uthread code, so use the helper to
+  register_evq(), which does the the right thing (atomics, careful ordering
+  with writes, etc).
+- If as syscall has an ev_q*, it is on the pending list.  It can be on the
+  pending list without an ev_q.
+
+2.2.1 Recovering from Event Overflow
+---------------
+The pthread code expects to receive an event somehow to unblock a thread
+once its syscall is done.  One limitation to our messaging systems is that you
+can't send an infinite amount of event messages.  (By messages, I mean a chunk
+of memory with a payload, in this case consisting of a struct syscall *).
+Event delivery degrades to a bit in the case of the message queue being full
+(more details on that later).
+
+The pthread code (and any similar 2LS) needs to handle waking up syscalls when
+the event message was lost and all we know is that some syscall that was meant
+to have a message sent to a particular event queue (per-core in the case of
+pthread stuff (actually the VCPD for now)).  The basic idea is to poll all
+outstanding system calls and unblock whoever is done.
+
+The key problem is due to a race: for a given syscall we don't know if we're
+going to get a message for a syscall or not.  There could be a completion
+message in the queue for the syscall while we are going through the list of
+blocked threads.  If we assume we already got the message (or it was lost in
+the overflow), but didn't really, then if we finish as SC and free its memory
+(free or return up the stack), we could later get a message for it, and all
+sorts of things would go wrong (like trying to unblock a pointer that is
+gibberish).
+
+Here's what we do:
+1) Set a "handling overflow" flag so we don't recurse.
+2) Turn off event delivery for all syscalls on our list
+3) Handle any event messages.  This is how we make a distinction between
+finished syscalls that had a message sent and those that didn't.  We're doing
+the message-sent ones here.
+4) For any left on the list, check to see if they are done.  We actually do
+this by attempting to turn on event delivery for them.  Turning on event
+delivery can fail if the call is already done.  So if it fails, they are done
+and we unblock them (similar to how we block the threads in the first place).
+If it doesn't fail, they are now ready to receive messages.  This can be
+tweaked a bit.
+5) Unset the overflow-handling flag.
+
+There are a couple implications of this style.  If you have a shared event
+queue (with other event sources), those events can get mixed in with the
+recovery.  Don't leave the vcore context due to other events.  This'll
+probably need work.  The other thing is that completed syscalls can get
+handled in a different order than they were signaled.  Shouldn't be a big
+deal.
+
+Note on the overflow handling flag and unsetting it.  There should not be any
+races with this.  The flag prevented us from handling overflows on the event
+queue.  Other than when we checked for events that had been succesfully sent,
+we didn't try to handle events.  We can unset the flag, and at that point we
+can start handling missed events.  If there was an overflow after we last
+checked the list, but before we cleared the overflow-handling flag, we'll
+still catch it since we haven't tried handling events in between checking the
+list and clearing the flag.  That flag doesn't even matter until we want to
+handle_events, so we aren't missing anything.  the next handle_events() will
+deal with everything from scratch.
+
+For blocking threads that block concurrently with the overflow handling: in
+the pthread case, this can't happen since everything is per-vcore.  If you do
+have process-wide thread blocking/syscall management, we can add new ones, but
+they must have event delivery turned off when they are added to the list.  And
+you'll need to lock the list, etc.  This should work in part due to new
+syscalls being added to the end of the list, and the overflow-handler
+proceeding linearly through the list.
+
+Also note that we shouldn't handle the event for unblocking a syscall on a
+different core than the one it was submitted to.  This could result in
+concurrent modifications to the original core's TAILQ (bad).  This restriction
+is dependent on how a 2LS does its thread handling/blocking.
+
+Eventually, we'll want a way to detect and handle excessive overflow, since
+it's probably quite expensive.  Perhaps turn it off and periodically poll the
+syscalls for completion (but don't bother turning on the ev_q).
+
 3. Event Delivery / Notification
 ====================
 3.1 Basics
index b43b92e..f790d38 100644 (file)
@@ -11,7 +11,7 @@ pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
        printf(__VA_ARGS__); \
        pthread_mutex_unlock(&lock);
 
-#define NUM_TEST_THREADS 1
+#define NUM_TEST_THREADS 20
 #define NUM_TEST_LOOPS 1000
 
 pthread_t my_threads[NUM_TEST_THREADS];
@@ -23,7 +23,7 @@ void *block_thread(void* arg)
        assert(!in_vcore_context());
        for (int i = 0; i < NUM_TEST_LOOPS; i++) {
                printf_safe("[A] pthread %d on vcore %d\n", pthread_self()->id, vcore_id());
-               sys_block(5000);
+               sys_block(5000 + pthread_self()->id);
        }
        return (void*)(pthread_self()->id);
 }
index 7e23e8e..88b49bd 100644 (file)
@@ -159,29 +159,44 @@ unsigned int get_event_type(struct event_mbox *ev_mbox)
  * 0. */
 handle_event_t ev_handlers[MAX_NR_EVENT] = {[EV_EVENT] handle_ev_ev, 0};
 
-/* Handle an mbox.  This is the receive-side processing of an event_queue.  It
- * takes an ev_mbox, since the vcpd mbox isn't a regular ev_q.  For now, we
- * check for preemptions between each event handler. */
-static int handle_mbox(struct event_mbox *ev_mbox, unsigned int flags)
+/* Handles all the messages in the mbox, but not the single bits.  Currently
+ * this doesn't tell the handler about overflow, since you should be handling
+ * that because of the bits.  Returns the number handled. */
+int handle_mbox_msgs(struct event_mbox *ev_mbox)
 {
+       int retval = 0;
        struct event_msg local_msg;
        unsigned int ev_type;
-       bool overflow = FALSE;
-       int retval = 0;
        uint32_t vcoreid = vcore_id();
-
-       if (!event_activity(ev_mbox, flags))
-               return retval;
-       /* Try to dequeue, dispatch whatever you get.  TODO consider checking for
-        * overflow first */
+       /* Try to dequeue, dispatch whatever you get. */
        while (!bcq_dequeue(&ev_mbox->ev_msgs, &local_msg, NR_BCQ_EVENTS)) {
                ev_type = local_msg.ev_type;
                printd("BCQ: ev_type: %d\n", ev_type);
                if (ev_handlers[ev_type])
-                       ev_handlers[ev_type](&local_msg, ev_type, overflow);
+                       ev_handlers[ev_type](&local_msg, ev_type, FALSE);       /* no overflow*/
                check_preempt_pending(vcoreid);
                retval++;
        }
+       return retval;
+}
+
+/* Handle an mbox.  This is the receive-side processing of an event_queue.  It
+ * takes an ev_mbox, since the vcpd mbox isn't a regular ev_q.  For now, we
+ * check for preemptions between each event handler. */
+static int handle_mbox(struct event_mbox *ev_mbox, unsigned int flags)
+{
+       bool overflow = FALSE;
+       int retval = 0;
+       uint32_t vcoreid = vcore_id();
+
+       /* TODO: This may be unnecessary anymore.  All it does is save the effort of
+        * checking the bitmask, though if we send EVENT_NOMSG, we'll have to check
+        * the bitmask anyway (the flag means you could get bit events that aren't
+        * overflow. */
+       if (!event_activity(ev_mbox, flags))
+               return retval;
+       /* Handle full messages.  Will deal with overflow and bits later. */
+       retval = handle_mbox_msgs(ev_mbox);
        /* Race here with another core clearing overflows/bits.  Don't have more
         * than one vcore work on an mbox without being more careful of overflows
         * (as in, assume any overflow means all bits must be checked, since someone
index fe0bb03..022ee60 100644 (file)
@@ -36,5 +36,6 @@ void handle_ev_ev(struct event_msg *ev_msg, unsigned int ev_type,
                   bool overflow);
 int handle_events(uint32_t vcoreid);
 void handle_event_q(struct event_queue *ev_q);
+int handle_mbox_msgs(struct event_mbox *ev_mbox);
 
 #endif /* _EVENT_H */
index acc8ad4..1356b93 100644 (file)
@@ -58,7 +58,10 @@ void ros_syscall_blockon(struct syscall *sysc);
 
 /* Utility function.  Event code also calls this. */
 bool check_preempt_pending(uint32_t vcoreid);
+
 bool register_evq(struct syscall *sysc, struct event_queue *ev_q);
+void deregister_sysc(struct syscall *sysc);
+bool reregister_sysc(struct syscall *sysc);
 
 /* Helpers, which sched_entry() can call */
 void run_current_uthread(void);
index d09c068..0161384 100644 (file)
@@ -320,7 +320,9 @@ bool check_preempt_pending(uint32_t vcoreid)
 }
 
 /* Attempts to register ev_q with sysc, so long as sysc is not done/progress.
- * Returns true if it succeeded, and false otherwise. */
+ * Returns true if it succeeded, and false otherwise.  False means that the
+ * syscall is done, and does not need an event set (and should be handled
+ * accordingly)*/
 bool register_evq(struct syscall *sysc, struct event_queue *ev_q)
 {
        int old_flags;
@@ -339,6 +341,43 @@ bool register_evq(struct syscall *sysc, struct event_queue *ev_q)
        return TRUE;
 }
 
+/* De-registers a syscall, so that the kernel will not send an event when it is
+ * done.  The call could already be SC_DONE, or could even finish while we try
+ * to unset SC_UEVENT.
+ *
+ * There is a chance the kernel sent an event if you didn't do this in time, but
+ * once it is done, the kernel won't send a message.  You can later turn it back
+ * on with reregister_sysc (which doesn't need to know the ev_q. */
+void deregister_sysc(struct syscall *sysc)
+{
+       int old_flags;
+       /* Try and unset the SC_UEVENT flag */
+       do {
+               old_flags = sysc->flags;
+               /* Note we don't care if the SC_DONE flag is getting set.  We just need
+                * to avoid clobbering flags */
+       } while (!atomic_comp_swap(&sysc->flags, old_flags, old_flags & ~SC_UEVENT));
+}
+
+/* Turns SC handling back on.  Returns true if it succeeded, and false
+ * otherwise.  False means that the syscall is done, and does not need an event
+ * set (and should be handled accordingly). */
+bool reregister_sysc(struct syscall *sysc)
+{
+       int old_flags;
+       /* Try and set the SC_UEVENT flag (so the kernel knows to look at ev_q) */
+       do {
+               old_flags = sysc->flags;
+               /* If the kernel finishes while we are trying to sign up for an event,
+                * we need to bail out */
+               if (old_flags & (SC_DONE | SC_PROGRESS)) {
+                       sysc->ev_q = 0;         /* not necessary, but might help with bugs */
+                       return FALSE;
+               }
+       } while (!atomic_comp_swap(&sysc->flags, old_flags, old_flags | SC_UEVENT));
+       return TRUE;
+}
+
 /* TLS helpers */
 static int __uthread_allocate_tls(struct uthread *uthread)
 {
index 8075fd4..45d38d2 100644 (file)
@@ -273,34 +273,61 @@ static void restart_thread(struct syscall *sysc)
        uthread_runnable(ut_restartee);
 }
 
-/* Handles syscall overflow */
-static void handle_sysc_overflow(void)
-{
-       struct sysc_mgmt *vc_sysc_mgmt = &sysc_mgmt[vcore_id()];
-       /* if we're currently handling it on this vcore, bail out */
-       if (vc_sysc_mgmt->handling_overflow)
-               return;
-       /* Actually handle stuff (TODO) */
-       vc_sysc_mgmt->handling_overflow = TRUE;
-       printf("FUUUUUUUUUUUUUUUUCK, OVERFLOW!!!!!!!\n");
-}
-
 /* This handler is usually run in vcore context, though I can imagine it being
  * called by a uthread in some other threading library. */
 static void pth_handle_syscall(struct event_msg *ev_msg, unsigned int ev_type,
                                bool overflow)
 {
+       uint32_t vcoreid = vcore_id();
+       struct sysc_mgmt *vc_sysc_mgmt = &sysc_mgmt[vcoreid];
        struct syscall *sysc;
+       struct pthread_tcb *i, *temp;
        assert(in_vcore_context());
-       if (overflow) {
-               handle_sysc_overflow();
+       /* Handle overflow: (if we haven't started handling it yet): */
+       if (overflow && !vc_sysc_mgmt->handling_overflow) {
+               vc_sysc_mgmt->handling_overflow = TRUE;
+               printd("[pthread] handling syscall overflow on vcore %d\n", vcoreid);
+               /* Turn off event handling for all syscs on our list.  Note they remain
+                * on the pending_sysc list. */
+               TAILQ_FOREACH(i, &sysc_mgmt[vcoreid].pending_syscs, next) {
+                       sysc = ((struct uthread*)i)->sysc;
+                       deregister_sysc(sysc);
+               }
+               /* Handle event msgs, to get any syscs that sent messages.  We don't
+                * care about bits, since we're dealing with overflow already.  Note
+                * that pthreads currently uses an ev_q shared by a bunch of message
+                * types, so other things could also run (careful with them!). */  
+               handle_mbox_msgs(vc_sysc_mgmt->ev_q.ev_mbox);
+               /* Try to manually handle all syscs, turning on the ev_q if they are not
+                * done, and handling them if they are done.  This deals with the same
+                * issues we dealt with in pth_blockon_sysc().
+                *
+                * This might end up sucking, since we could get more overflow because
+                * of the early turning-on of events.  Alternatively, we could loop
+                * through and simply check for completion (and handle), and then do
+                * this loop. */
+               TAILQ_FOREACH_SAFE(i, &sysc_mgmt[vcoreid].pending_syscs, next, temp) {
+                       sysc = ((struct uthread*)i)->sysc;
+                       if (!reregister_sysc(sysc)) {
+                               /* They are already done, can't sign up for events, just like
+                                * when we blocked on them the first time. */
+                               restart_thread(sysc);
+                       }
+               }
+               /* Done dealing with overflow */
+               vc_sysc_mgmt->handling_overflow = FALSE;
+               /* The original sysc in an ev_msg, if any, has already been done. */
+               return;
        }
+       /* It's a bug if we don't have a msg (we are handling a syscall bit-event)
+        * while still dealing with overflow.  The only bit events should be for the
+        * first (or subsequent) overflow. */
        if (!ev_msg) {
-               /* Probably a bug somewhere if we had no ev_msg and no overflow */
-               if (!overflow)
-                       printf("[pthread] crap, no ev_msg!!\n");
+               printf("[pthread] crap, no ev_msg, overflow: %d, handling: %d!!\n",
+                      overflow, vc_sysc_mgmt->handling_overflow);
                return;
        }
+       /* Normal path: get the sysc from the message and just restart it */
        sysc = ev_msg->ev_arg3;
        assert(sysc);
        restart_thread(sysc);