Differential D9791 Diff 25806 sys/kern/subr_sleepqueue.c

Changeset View

Standalone View

sys/kern/subr_sleepqueue.c

Show All 20 Lines
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.		* SUCH DAMAGE.
*/		*/

/*		/*
* Implementation of sleep queues used to hold queue of threads blocked on		* Implementation of sleep queues used to hold queue of threads blocked on
* a wait channel. Sleep queues different from turnstiles in that wait		* a wait channel. Sleep queues are different from turnstiles in that wait
* channels are not owned by anyone, so there is no priority propagation.		* channels are not owned by anyone, so there is no priority propagation.
* Sleep queues can also provide a timeout and can also be interrupted by		* Sleep queues can also provide a timeout and can also be interrupted by
* signals. That said, there are several similarities between the turnstile		* signals. That said, there are several similarities between the turnstile
* and sleep queue implementations. (Note: turnstiles were implemented		* and sleep queue implementations. (Note: turnstiles were implemented
* first.) For example, both use a hash table of the same size where each		* first.) For example, both use a hash table of the same size where each
* bucket is referred to as a "chain" that contains both a spin lock and		* bucket is referred to as a "chain" that contains both a spin lock and
* a linked list of queues. An individual queue is located by using a hash		* a linked list of queues. An individual queue is located by using a hash
* to pick a chain, locking the chain, and then walking the chain searching		* to pick a chain, locking the chain, and then walking the chain searching
* for the queue. This means that a wait channel object does not need to		* for the queue. This means that a wait channel object does not need to
* embed it's queue head just as locks do not embed their turnstile queue		* embed its queue head just as locks do not embed their turnstile queue
* head. Threads also carry around a sleep queue that they lend to the		* head. Threads also carry around a sleep queue that they lend to the
* wait channel when blocking. Just as in turnstiles, the queue includes		* wait channel when blocking. Just as in turnstiles, the queue includes
* a free list of the sleep queues of other threads blocked on the same		* a free list of the sleep queues of other threads blocked on the same
* wait channel in the case of multiple waiters.		* wait channel in the case of multiple waiters.
*		*
* Some additional functionality provided by sleep queues include the		* Some additional functionality provided by sleep queues include the
* ability to set a timeout. The timeout is managed using a per-thread		* ability to set a timeout. The timeout is managed using a per-thread
* callout that resumes a thread if it is asleep. A thread may also		* callout that resumes a thread if it is asleep. A thread may also
Show All 25 Lines
#include <sys/proc.h>		#include <sys/proc.h>
#include <sys/sbuf.h>		#include <sys/sbuf.h>
#include <sys/sched.h>		#include <sys/sched.h>
#include <sys/sdt.h>		#include <sys/sdt.h>
#include <sys/signalvar.h>		#include <sys/signalvar.h>
#include <sys/sleepqueue.h>		#include <sys/sleepqueue.h>
#include <sys/stack.h>		#include <sys/stack.h>
#include <sys/sysctl.h>		#include <sys/sysctl.h>
		#include <sys/time.h>

		#include <machine/atomic.h>

#include <vm/uma.h>		#include <vm/uma.h>

#ifdef DDB		#ifdef DDB
#include <ddb/ddb.h>		#include <ddb/ddb.h>
#endif		#endif


/*		/*
* Constants for the hash table of sleep queue chains.		* Constants for the hash table of sleep queue chains.
* SC_TABLESIZE must be a power of two for SC_MASK to work properly.		* SC_TABLESIZE must be a power of two for SC_MASK to work properly.
*/		*/
#define SC_TABLESIZE 256 /* Must be power of 2. */		#define SC_TABLESIZE 256 /* Must be power of 2. */
#define SC_MASK (SC_TABLESIZE - 1)		#define SC_MASK (SC_TABLESIZE - 1)
#define SC_SHIFT 8		#define SC_SHIFT 8
#define SC_HASH(wc) ((((uintptr_t)(wc) >> SC_SHIFT) ^ (uintptr_t)(wc)) & \		#define SC_HASH(wc) ((((uintptr_t)(wc) >> SC_SHIFT) ^ (uintptr_t)(wc)) & \
SC_MASK)		SC_MASK)
#define SC_LOOKUP(wc) &sleepq_chains[SC_HASH(wc)]		#define SC_LOOKUP(wc) &sleepq_chains[SC_HASH(wc)]
#define NR_SLEEPQS 2		#define NR_SLEEPQS 2
/*		/*
* There two different lists of sleep queues. Both lists are connected		* There are two different lists of sleep queues. Both lists are connected
* via the sq_hash entries. The first list is the sleep queue chain list		* via the sq_hash entries. The first list is the sleep queue chain list
* that a sleep queue is on when it is attached to a wait channel. The		* that a sleep queue is on when it is attached to a wait channel. The
* second list is the free list hung off of a sleep queue that is attached		* second list is the free list hung off of a sleep queue that is attached
* to a wait channel.		* to a wait channel.
*		*
* Each sleep queue also contains the wait channel it is attached to, the		* Each sleep queue also contains the wait channel it is attached to, the
* list of threads blocked on that wait channel, flags specific to the		* list of threads blocked on that wait channel, flags specific to the
* wait channel, and the lock used to synchronize with a wait channel.		* wait channel, and the lock used to synchronize with a wait channel.
▲ Show 20 Lines • Show All 424 Lines • ▼ Show 20 Lines
* Returns with thread lock.		* Returns with thread lock.
*/		*/
static void		static void
sleepq_switch(void *wchan, int pri)		sleepq_switch(void *wchan, int pri)
{		{
struct sleepqueue_chain *sc;		struct sleepqueue_chain *sc;
struct sleepqueue *sq;		struct sleepqueue *sq;
struct thread *td;		struct thread *td;
		bool rtc_changed;

td = curthread;		td = curthread;
sc = SC_LOOKUP(wchan);		sc = SC_LOOKUP(wchan);
mtx_assert(&sc->sc_lock, MA_OWNED);		mtx_assert(&sc->sc_lock, MA_OWNED);
THREAD_LOCK_ASSERT(td, MA_OWNED);		THREAD_LOCK_ASSERT(td, MA_OWNED);

/*		/*
* If we have a sleep queue, then we've already been woken up, so		* If we have a sleep queue, then we've already been woken up, so
* just return.		* just return.
*/		*/
if (td->td_sleepqueue != NULL) {		if (td->td_sleepqueue != NULL) {
mtx_unlock_spin(&sc->sc_lock);		mtx_unlock_spin(&sc->sc_lock);
return;		return;
}		}

/*		/*
* If TDF_TIMEOUT is set, then our sleep has been timed out		* If TDF_TIMEOUT is set, then our sleep has been timed out
* already but we are still on the sleep queue, so dequeue the		* already but we are still on the sleep queue, so dequeue the
* thread and return.		* thread and return. Do the same if the real-time clock has
		* been adjusted since this thread calculated its timeout
		* based on that clock.
		kibUnsubmitted Done Inline Actions I think this is a right place to provide some reasoning why the code correctly covers the race where tc_windup()->sleeping_on_old_rtc() missed us. Some note about sleepq lock used as interlock there is due, IMO. kib: I think this is a right place to provide some reasoning why the code correctly covers the race…
		vangyzenAuthorUnsubmitted Done Inline Actions Will do. vangyzen: Will do.
*/		*/
if (td->td_flags & TDF_TIMEOUT) {		rtc_changed = (td->td_flags & TDF_SLEEPRTC) &&
		td->td_rtcgen != atomic_load_acq_int(&rtc_generation);
		if ((td->td_flags & TDF_TIMEOUT) \|\| rtc_changed) {
		if (rtc_changed) {
		td->td_flags &= ~TDF_SLEEPRTC;
		kibUnsubmitted Not Done Inline Actions I think it is a prereq for the race that Ts is not put to sleep yet. In fact, there is very fine difference between TD_ON_SLEEPQ() which means that sleepq_add() was done, and TD_IS_SLEEPING(), which mean that the thread is really asleep. TD_IS_SLEEPING() condition is set as the last action in sleepq_switch() (this function) right before the call to mi_switch(). When I asked for the comment, I mean just mention this race and also to explain how the use of sleep chain spinlocks makes the td_rtcgen accesses correctly synchronized. kib: I think it is a prereq for the race that Ts is not put to sleep yet. In fact, there is very…
		}
MPASS(TD_ON_SLEEPQ(td));		MPASS(TD_ON_SLEEPQ(td));
sq = sleepq_lookup(wchan);		sq = sleepq_lookup(wchan);
if (sleepq_resume_thread(sq, td, 0)) {		if (sleepq_resume_thread(sq, td, 0)) {
#ifdef INVARIANTS		#ifdef INVARIANTS
/*		/*
* This thread hasn't gone to sleep yet, so it		* This thread hasn't gone to sleep yet, so it
* should not be swapped out.		* should not be swapped out.
*/		*/
panic("not waking up swapper");		panic("not waking up swapper");
#endif		#endif
}		}
mtx_unlock_spin(&sc->sc_lock);		mtx_unlock_spin(&sc->sc_lock);
return;		return;
		kibUnsubmitted Done Inline Actions As I asked before, please commit the style and comment grammar fixes now. kib: As I asked before, please commit the style and comment grammar fixes now.
}		}
#ifdef SLEEPQUEUE_PROFILING		#ifdef SLEEPQUEUE_PROFILING
if (prof_enabled)		if (prof_enabled)
sleepq_profile(td->td_wmesg);		sleepq_profile(td->td_wmesg);
#endif		#endif
MPASS(td->td_sleepqueue == NULL);		MPASS(td->td_sleepqueue == NULL);
sched_sleep(td, pri);		sched_sleep(td, pri);
thread_lock_set(td, &sc->sc_lock);		thread_lock_set(td, &sc->sc_lock);
▲ Show 20 Lines • Show All 300 Lines • ▼ Show 20 Lines	sleepq_signal(void *wchan, int flags, int pri, int queue)
wakeup_swapper = sleepq_resume_thread(sq, besttd, pri);		wakeup_swapper = sleepq_resume_thread(sq, besttd, pri);
thread_unlock(besttd);		thread_unlock(besttd);
return (wakeup_swapper);		return (wakeup_swapper);
}		}

/*		/*
* Resume all threads sleeping on a specified wait channel.		* Resume all threads sleeping on a specified wait channel.
*/		*/
int		int
		kibUnsubmitted Done Inline Actions Style(9) requires a blank line after the '{' if no local vars is defined. kib: Style(9) requires a blank line after the '{' if no local vars is defined.
sleepq_broadcast(void *wchan, int flags, int pri, int queue)		sleepq_broadcast(void *wchan, int flags, int pri, int queue)
{		{
struct sleepqueue *sq;		struct sleepqueue *sq;
struct thread td, tdn;
int wakeup_swapper;

CTR2(KTR_PROC, "sleepq_broadcast(%p, %d)", wchan, flags);		CTR2(KTR_PROC, "sleepq_broadcast(%p, %d)", wchan, flags);
KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__));		KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__));
MPASS((queue >= 0) && (queue < NR_SLEEPQS));		MPASS((queue >= 0) && (queue < NR_SLEEPQS));
sq = sleepq_lookup(wchan);		sq = sleepq_lookup(wchan);
if (sq == NULL)		if (sq == NULL)
return (0);		return (0);
KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE),		KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE),
("%s: mismatch between sleep/wakeup and cv_*", __func__));		("%s: mismatch between sleep/wakeup and cv_*", __func__));

		return (sleepq_remove_matching(sq, queue, NULL, pri));
		kibUnsubmitted Done Inline Actions I would prefer to remove special case for matcher == NULL and instead provided a trivial matcher always returning true there. kib: I would prefer to remove special case for matcher == NULL and instead provided a trivial…
		}

/*		/*
* Resume all blocked threads on the sleep queue. The last thread will		* Resume threads on the sleep queue that match the given predicate,
* be given ownership of sq and may re-enqueue itself before		* or all threads if the predicate is NULL.
* sleepq_resume_thread() returns, so we must cache the "next" queue
* item at the beginning of the final iteration.
*/		*/
		int
		sleepq_remove_matching(struct sleepqueue *sq, int queue,
		bool (matches)(struct thread ), int pri)
		{
		struct thread td, tdn;
		int wakeup_swapper;

		/*
		* The last thread will be given ownership of sq and may
		* re-enqueue itself before sleepq_resume_thread() returns,
		* so we must cache the "next" queue item at the beginning
		* of the final iteration.
		*/
wakeup_swapper = 0;		wakeup_swapper = 0;
TAILQ_FOREACH_SAFE(td, &sq->sq_blocked[queue], td_slpq, tdn) {		TAILQ_FOREACH_SAFE(td, &sq->sq_blocked[queue], td_slpq, tdn) {
thread_lock(td);		thread_lock(td);
		if (matches == NULL \|\| matches(td))
wakeup_swapper \|= sleepq_resume_thread(sq, td, pri);		wakeup_swapper \|= sleepq_resume_thread(sq, td, pri);
thread_unlock(td);		thread_unlock(td);
}		}

return (wakeup_swapper);		return (wakeup_swapper);
}		}

/*		/*
* Time sleeping threads out. When the timeout expires, the thread is		* Time sleeping threads out. When the timeout expires, the thread is
* removed from the sleep queue and made runnable if it is still asleep.		* removed from the sleep queue and made runnable if it is still asleep.
*/		*/
static void		static void
▲ Show 20 Lines • Show All 117 Lines • ▼ Show 20 Lines	if (!TD_IS_SLEEPING(td))
return (0);		return (0);
wchan = td->td_wchan;		wchan = td->td_wchan;
MPASS(wchan != NULL);		MPASS(wchan != NULL);
sq = sleepq_lookup(wchan);		sq = sleepq_lookup(wchan);
MPASS(sq != NULL);		MPASS(sq != NULL);

/* Thread is asleep on sleep queue sq, so wake it up. */		/* Thread is asleep on sleep queue sq, so wake it up. */
return (sleepq_resume_thread(sq, td, 0));		return (sleepq_resume_thread(sq, td, 0));
		}

		void
		sleepq_chains_remove_matching(bool (matches)(struct thread ))
		{
		struct sleepqueue_chain *sc;
		struct sleepqueue *sq;
		int i, wakeup_swapper;

		wakeup_swapper = 0;
		for (sc = &sleepq_chains[0]; sc < sleepq_chains + SC_TABLESIZE; ++sc) {
		if (LIST_EMPTY(&sc->sc_queues)) {
		continue;
		}
		mtx_lock_spin(&sc->sc_lock);
		LIST_FOREACH(sq, &sc->sc_queues, sq_hash) {
		for (i = 0; i < NR_SLEEPQS; ++i) {
		wakeup_swapper \|= sleepq_remove_matching(sq, i,
		matches, 0);
		kibUnsubmitted Done Inline Actions I suggest to re-factor this code fragment from sleepq_broadcast() and reuse the call. kib: I suggest to re-factor this code fragment from sleepq_broadcast() and reuse the call.
		vangyzenAuthorUnsubmitted Done Inline Actions Good idea. Done. vangyzen: Good idea. Done.
		}
		}
		mtx_unlock_spin(&sc->sc_lock);
		}
		if (wakeup_swapper) {
		kibUnsubmitted Done Inline Actions No need in {}. kib: No need in {}.
		vangyzenAuthorUnsubmitted Done Inline Actions True, but I very strongly prefer using such braces. vangyzen: True, but I very strongly prefer using such braces.
		kick_proc0();
		}
}		}

/*		/*
* Prints the stacks of all threads presently sleeping on wchan/queue to		* Prints the stacks of all threads presently sleeping on wchan/queue to
* the sbuf sb. Sets count_stacks_printed to the number of stacks actually		* the sbuf sb. Sets count_stacks_printed to the number of stacks actually
* printed. Typically, this will equal the number of threads sleeping on the		* printed. Typically, this will equal the number of threads sleeping on the
		kibUnsubmitted Done Inline Actions It is enough to do one kick_proc0() after waking up all chains. kib: It is enough to do one kick_proc0() after waking up all chains.
		vangyzenAuthorUnsubmitted Done Inline Actions I was wondering about that. Thanks. vangyzen: I was wondering about that. Thanks.
* queue, but may be less if sb overflowed before all stacks were printed.		* queue, but may be less if sb overflowed before all stacks were printed.
*/		*/
#ifdef STACK		#ifdef STACK
int		int
sleepq_sbuf_print_stacks(struct sbuf sb, void wchan, int queue,		sleepq_sbuf_print_stacks(struct sbuf sb, void wchan, int queue,
int *count_stacks_printed)		int *count_stacks_printed)
{		{
struct thread td, td_next;		struct thread td, td_next;
▲ Show 20 Lines • Show All 316 Lines • Show Last 20 Lines