sched_pin() bug in SCHED_ULE

[mdf at FreeBSD.org]

On Thu, Aug 26, 2010 at 1:49 PM, John Baldwin <jhb at freebsd.org> wrote:
> On Thursday, August 26, 2010 4:03:38 pm mdf at freebsd.org wrote:
>> Back at the beginning of August I posted about issues with sched_pin()
>> and witness_warn():
>>
>> http://lists.freebsd.org/pipermail/freebsd-hackers/2010-August/032553.html
>>
>> After a lot of debugging I think I've basically found the issue.  I
>> found this bug on stable/7, but looking at the commit log for CURRENT
>> I don't see any reason the bug doesn't exist there.  This analysis is
>> specific to amd64/i386 but the problem is likely to exist on most
>> arches.
>>
>> The basic problem is that in both tdq_move() and sched_setcpu() can
>> manipulate the ts->ts_cpu variable of another process, which may be
>> running.  This means that a process running on CPU N may be set to run
>> on CPU M the next context switch.
>>
>> Then, that process may call sched_pin(), then grab a PCPU variable.
>> An IPI_PREEMPT can come in, causing the thread to call mi_switch() in
>> ipi_bitmap_handler().  sched_switch() will then notice that ts->ts_cpu
>> is not PCPU_GET(cpuid), and call sched_switch_migrate(), migrating the
>> thread to the intended CPU.  Thus after sched_pin() and potentially
>> before using any PCPU variable the process can get migrated to another
>> CPU, and now it is using a PCPU variable for the wrong processor.
>>
>> Given that ts_cpu can be set by other threads, it doesn't seem worth
>> checking at sched_pin time whether ts_cpu is not the same as td_oncpu,
>> because to make the check would require taking the thread_lock.
>> Instead, I propose adding a check for !THREAD_CAN_MIGRATE() before
>> calling sched_switch_migrate().  However, sched_pin() is also used by
>> sched_bind(9) to force the thread to stay on the intended cpu.  I
>> would handle this by adding a TSF_BINDING state that is different from
>> TSF_BOUND.
>>
>> The thing that has me wondering whether this is all correct is that I
>> don't see any checks in tdq_move() or sched_setcpu() for either
>> TSF_BOUND or THREAD_CAN_MIGRATE().  Perhaps that logic is managed in
>> the various calling functions; in that case I would propose adding
>> asserts that the thread is THREAD_CAN_MIGRATE() unless it's marked
>> TSF_BINDING.
>>
>> Does this analysis seem correct?
>
> Calling code does check THREAD_CAN_MIGRATE(), but the problem is that it is
> not safe to call that on anything but curthread as td_pinned is not locked.
> It is assumed that only curthread would ever check td_pinned, not other
> threads.  I suspect what is happening is that another CPU is seeing a stale
> value of td_pinned.  You could fix this by grabbing the thread lock in
> sched_pin()/unpin() for ULE, but that is a bit expensive perhaps.

I tried making sched_pin() a real function which used
intr_disable/intr_restore around saving off td->td_oncpu,
td->td_lastcpu and ts->ts_cpu, and the stack at the time of call.  In
sched_switch when I saw an unexpected migration I printed all that
out.  I found that on my boxes, at sched_pin() time ts_cpu was already
different from td->td_oncpu, so the specific problem I was having was
that while another thread can change ts_cpu it has no way to force
that thread to immediately migrate.

I believe the below patch fixes the issue, though I'm open to other methods:


Index: kern/sched_ule.c
===================================================================
--- kern/sched_ule.c	(.../head/src/sys)	(revision 158279)
+++ kern/sched_ule.c	(.../branches/BR_BUG_67957/src/sys)	(revision 158279)
@@ -112,6 +112,7 @@
 /* flags kept in ts_flags */
 #define	TSF_BOUND	0x0001		/* Thread can not migrate. */
 #define	TSF_XFERABLE	0x0002		/* Thread was added as transferable. */
+#define	TSF_BINDING	0x0004		/* Thread is being bound. */

 static struct td_sched td_sched0;

@@ -1859,6 +1858,7 @@
 	struct mtx *mtx;
 	int srqflag;
 	int cpuid;
+	int do_switch;

 	THREAD_LOCK_ASSERT(td, MA_OWNED);

@@ -1888,10 +1888,21 @@
 		srqflag = (flags & SW_PREEMPT) ?
 		    SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
 		    SRQ_OURSELF|SRQ_YIELDING;
-		if (ts->ts_cpu == cpuid)
+		/*
+		 * Allow the switch to another processor as requested
+		 * only if the thread can migrate or we are in the
+		 * middle of binding for sched_bind(9).  This keeps
+		 * sched_pin() quick, since other threads can
+		 * manipulate ts_cpu.
+		 */
+		do_switch = (ts->ts_cpu != cpuid);
+		if (!THREAD_CAN_MIGRATE(td) &&
+		    (ts->ts_flags & TSF_BINDING) == 0)
+			do_switch = 0;
+		if (do_switch)
+			mtx = sched_switch_migrate(tdq, td, srqflag);
+		else
 			tdq_add(tdq, td, srqflag);
-		else
-			mtx = sched_switch_migrate(tdq, td, srqflag);
 	} else {
 		/* This thread must be going to sleep. */
 		TDQ_LOCK(tdq);
@@ -1938,12 +1949,25 @@
 		 */
 		cpuid = PCPU_GET(cpuid);
 		tdq = TDQ_CPU(cpuid);
+		KASSERT(THREAD_CAN_MIGRATE(td) ||
+		    (ts->ts_flags & TSF_BINDING) != 0 ||
+		     cpuid == td->td_lastcpu,
+		    ("Non-migratable thread %p migrated from %d to %d",
+		     td, td->td_lastcpu, cpuid));
 #ifdef	HWPMC_HOOKS
 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
 #endif
 	} else
 		thread_unblock_switch(td, mtx);
+
+	if ((ts->ts_flags & TSF_BINDING) != 0) {
+		ts->ts_flags &= ~TSF_BINDING;
+		ts->ts_flags |= TSF_BOUND;
+	}
+	KASSERT((ts->ts_flags & TSF_BOUND) == 0 || ts->ts_cpu == cpuid,
+	    ("Bound thread %p on %d not %d", td, cpuid, ts->ts_cpu));
+
 	/*
 	 * Assert that all went well and return.
 	 */
@@ -2607,15 +2631,21 @@
 	ts = td->td_sched;
 	if (ts->ts_flags & TSF_BOUND)
 		sched_unbind(td);
-	ts->ts_flags |= TSF_BOUND;
+	KASSERT(THREAD_CAN_MIGRATE(td),
+	    ("%s called on non-migratable thread %p", __func__, td));
 #ifdef SMP
+	ts->ts_flags |= TSF_BINDING;
 	sched_pin();
 	if (PCPU_GET(cpuid) == cpu)
 		return;
 	ts->ts_cpu = cpu;
 	/* When we return from mi_switch we'll be on the correct cpu. */
 	mi_switch(SW_VOL, NULL);
+#else
+	ts->ts_flags |= TSF_BOUND;
 #endif
+	KASSERT((ts->ts_flags & TSF_BOUND) != 0 && cpu == PCPU_GET(cpuid),
+	    ("Should be bound to %d", cpu));
 }

 /*
@@ -2640,7 +2670,7 @@
 sched_is_bound(struct thread *td)
 {
 	THREAD_LOCK_ASSERT(td, MA_OWNED);
-	return (td->td_sched->ts_flags & TSF_BOUND);
+	return ((td->td_sched->ts_flags & (TSF_BOUND | TSF_BINDING)) != 0);
 }

 /*