qio: Fix race with multiple blockers
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 8 Feb 2017 21:17:54 +0000 (16:17 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Thu, 9 Feb 2017 17:31:00 +0000 (12:31 -0500)
commit64b7407e3ba015e21587b4374c0663face8d47d8
treef99c54f650b38181a3c58fe1fae8ef5e35c5b871
parent35ac94714808bccdc524eb62e468b463605769b7
qio: Fix race with multiple blockers

It was possible for multiple readers (or writers) to block on an empty (or
full) queue, but for one of them to never wake up.  This was broken in
commit 9ec41115cb83 ("qio: Clean up locking").

The qlock that used to be there made it so that there was only one
*blocking* reader (or writer) at a time.  That made the usage of Qstarve
(and Qflow) safe as a signal for the other writer (or reader) to wake any
sleepers.  However, with more concurrency due to the lack of the qlock,
that flag isn't sufficient anymore.  You could have two threads both set
Qstarve, then try to sleep.  A waker could come in, see the flag, wake one
of them, but not the other.  Then the other's rendez condition fails (e.g.
the queue is still empty), but Qstarve isn't set.

The right fix for this is to not use Qflow and Qstarve - just check the
rendez if we transitioned an edge.  After all, that's the rendez condition
(e.g., is_empty), not 'is Qflow still set.'  After doing so, it actually
cleans up things a little, since we're firing taps based on the edge
condition too.  Perhaps the old Qstarve/Qflow byte check saved us the
hassle of checking the rendez if we didn't know someone was there, but that
overhead isn't worth the qlock-all-blocking-readers policy.  Yes, the qlock
only applied to *blocking* threads.

Note that kicks may fire more frequently now, since they fire on edge
transitions instead of edge transitions that also had a sleeper.  If this
breaks anything, that thing needs to be changed to handle spurious kicks.
It'd be a bad design otherwise.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/ns.h
kern/src/ns/qio.c