Tools for finding scheduler-dependent "heisenbugs"

[njsmith]

Race conditions suck, but they're a common kind of bug in concurrent programs. We should help people test for them if we can.

Some interesting research out of MSR:

• CHESS
• GAMBIT

CHESS assumes you have a preemptive multitasking system and works by hooking synchronization primitives, and explores different legal paths through the resulting happens-before graph. This makes it tricky to find data races, i.e., places where two threads access the same variable without using any synchronization primitive; you really want to be able to try schedules where threads get preempted in the middle of these. In practice, it sounds like the way they do this (see page 7) is to first run some heavyweight data race detector that instruments memory reads and writes, and then use the result to add new annotations for the CHESS scheduler.

For us, we don't AFAIK have any reasonable way to do data race detection in Python (maybe you could write something with PyPy? it's non-trivial), but we do have direct access to the scheduler, so we can in principle explore all possible preemption decisions directly instead of having to infer them from synchronization points. However, this is likely to be somewhat inefficient – for CHESS it really needs to cut down the space of preemption points because otherwise it has to consider a preemption at every instruction which is ridiculously intractable, and we're in a better position then that, but the average program does still have lots of cases where two tasks that aren't interacting at all have some preemption points and this generates an exponential space of boring possible schedules.

They have a lot of interesting stuff in the paper (section 4) about how to structure a search, recovering from non-determinism in the code-under-test, some (not enough) detail about fair scheduling (they want to handle code with spin-locks). It looks like this is the fair scheduling paper; it looks like the main idea is that if a thread calls sched_yield or equivalent then it means it can't make progress, so you should lower its priority. That's... not a good signal in the trio context. Fortunately it's not clear that anyone wants to write spin-locks anyway... (we use the equivalent a few times in our test suite, but mostly only in the earliest tests I wrote before we had much infrastructure, and certainly it's a terrible thing to do in real code).

Possibly useful citation: "ConTest [15] is a lightweight testing tool that attempts to create scheduling variance without resorting to systematic generation of all executions. In contrast, CHESS obtains greater control over thread scheduling to offer higher coverage guarantees and better reproducibility."

GAMBIT then adds a smarter best-first search algorithm on top of the basic CHESS framework. A lot of the cleverness in GAMBIT is about figuring out which states are equivalent and thus can be collapsed, which we don't really have access to. But the overall ideas are probably relevant. (It's also possible that we could use something like instrumented synchronization primitives plus the DPOR algorithm to pick "interesting" schedules to try first, and then fall back on more brute-force randomized search.)

I suspect there are two general approaches that are likely to be most useful in our context:

• Hypothesis-style randomized exploration of the space of scheduling decisions, with some clever heuristics to guide the search towards edge cases that are likely to find bugs, and maybe even hypothesis-style minimization. (The papers above have some citations to other papers showing that low-preemption traces are often sufficient to demonstrate bugs in practice.)

• Providing some sort of mechanism for users to explicitly guide the exploration to a subset of cases that they've identified as a problem (either by intuition or especially for regression tests and increasing coverage). You can imagine relatively simple things like "use these priorities until task 3 hits the yield point on line 72 and then switch to task 5", maybe?

An intermediate form between these is one of the heuristics mentioned in the GAMBIT paper, of letting the programmer name some specific functions they want to "focus" on, and using that to increase the number of preemptions that happen within those functions. (This is sort of mentioned in the CHESS paper too when talking about their state space reduction techniques.)

Possibly implementation for scheduler control: call an instrument hook before scheduling a batch, with a list of runnable tasks (useful as a general notification anyway), and let them optionally return something to control the scheduling of this batch.

See also: #77

[njsmith]

An interesting question is how this might relate to testing network protocols. We already have some mechanisms in the memory-stream code to make tests where data trickles in on a weird schedule; one way to think of this is that when one task calls send_all and another is blocked in receive_some, there is a whole space of possible synchronization options there where some amount of the send_all becomes available to the receive_some, and maybe you want to re-use the same schedule exploration logic to explore those too.

Right now we use ad hoc randomized sleeps for this kind of thing, which is a bit cumbersome in general, and I especially struggled when writing the ssl tests to get them to give good coverage over all the weird scheduling/network interactions that can happen there. In particular one problem is that if you have one task that does 1 sleep, and another task that does 3 sleeps, then it's very rare that the second task will ever complete first, just because P(X) > P(X1 + X2 + X3) is not high when X, X1, X2, X3, are all equidistributed. A more systematic state exploration system with some global view of the test could potentially do much better here.

[njsmith]

Here's an interesting, well-posed but non-obvious question: if you just go ahead and run the same test lots of times ("stress testing"), then this isn't very effective because you mostly explore the same interleavings over and over. Is there some algorithm that generates uniform samples from the space of interleavings?

(Obviously this would have to be a stateful algorithm whose long-term stationary distribution has this property.)

[njsmith]

Some first-order objections to the "uniform samples from space of interleavings" idea:

• This would clearly have to be an asymptotic algorithm, since there's no guarantee that you can even find all the interleavings in any bounded time. (You might have to schedule one particular sequence of interleavings that suddenly causes a new task to spawn and it turns out that the vast majority of all interleavings start with this prefix... but you don't know that unless you happen to stumble on this prefix, which might take an exponentially long time). So as usual for asymptotic algorithms, you might hope that having good asymptotic properties will help it have good short-run properties, but you don't really know.

• Is the counting measure really what we want here? It has the nice property that it's well-defined. But in practice it seems likely that you can have some sequence like:

async def t1():
    global x
    x = 1
    for _ in range(10):
        await yield_briefly()

async def t2():
    for _ in range(10):
        await yield_briefly()
    global x
    x = 2

async with trio.open_nursery() as nursery:
    nursery.spawn(t1)
    nursery.spawn(t2)

assert x == 2

In the vast, vast majority of interleavings (including all the ones you'd see during regular testing), this works. There's exactly one interleaving where it fails, which is the one where t2 runs to completion before t1 even starts. To find this kind of thing we need to find unusual interleavings, not just arbitrary interleavings – the ones that are "far" from the average interleaving in some sense.

The ctrigger paper has some interesting discussion of what makes interleavings more or less similar. Not sure how applicable it is.

[njsmith]

Here's some notes from roc on making this work in practice on a firefox heisenbug that CHESS couldn't catch, with a practical heuristic algorithm: http://robert.ocallahan.org/2016/02/introducing-rr-chaos-mode.html

[njsmith]

There's also: https://github.com/osrg/namazu (from the comments on the post above)

[njsmith]

@ssanderson has an interesting scheme he's implemented in gevent, where he annotates his actual logic with calls like await trace("some-event-happened"), and then in tests he can inject code at a particular trace event to do things like control ordering. Which is pretty useful! And it also provides useful information about high-level events that might help a heuristically evil scheduler better explore the space of interleavings.

[Edit: here's what it might look like in Trio: #533]

[Zac-HD]

Hypothesis-style randomized exploration of the space of scheduling decisions, with some clever heuristics to guide the search towards edge cases that are likely to find bugs, and maybe even hypothesis-style minimization.

This sounds like a case for writing a scheduler on top of Hypothesis! Check out generic state machines - if you can define a steps() method that returns (a sampled_from strategy of) a sequence of possible tasks to schedule, and an execute_step(task) method that schedules that task, Hypothesis will do the rest 😄

Of course, that means that most of the work has just moved one layer up...

• The fundamental part is the code to take an async function and output a steps() and execute_step(step) implementation. At this point it should "just work", and though it could be more powerful I would expect to find some real bugs if you leave it running.
• Improve the steps() method from arbitrary order to an ordering based on useful heuristics. This may involve writing a strategy that acts more like weighted decision tree than sampling from a list, and/or working out ways to observe more information we can use to bias the schedule.
• Consider fault injection, e.g. for anything that would usually hit the network. Add arbitrary delays or back-pressure, make the network go down (and come up) unexpectedly, etc; may be related to It'd be nice if we had a test helper for systematically injecting cancellations #77.

And at this point the result could accurately be described as a state-of-the-art fuzzing scheduler 🚀

[njsmith]

Oh, happened to be re-reading roc's post above, and noticed that he also has some followups:

• https://robert.ocallahan.org/2016/02/deeper-into-chaos.html

• https://robert.ocallahan.org/2018/05/rr-chaos-mode-improvements.html

It looks like there's also a talk here, for those who are into that kind of thing: https://air.mozilla.org/chaos-mode-and-rr/

(In case it's not clear, I think these are probably the most useful posts to look at first, because they are relentlessly practical in a way that all the other links in this thread are not.)

If/when we seriously attempt this we should probably send him a ping to check if he has any other insights to share.

[Zac-HD]

trio/trio/_core/_run.py

Lines 1424 to 1436 in 3877632

	# Also, we randomize the order of each batch to avoid assumptions
	# about scheduling order sneaking in. In the long run, I suspect we'll
	# either (a) use strict FIFO ordering and document that for
	# predictability/determinism, or (b) implement a more sophisticated
	# scheduler (e.g. some variant of fair queueing), for better behavior
	# under load. For now, this is the worst of both worlds - but it keeps
	# our options open. (If we do decide to go all in on deterministic
	# scheduling, then there are other things that will probably need to
	# change too, like the deadlines tie-breaker and the non-deterministic
	# ordering of task._notify_queues.)
	batch = list(runner.runq)
	runner.runq.clear()
	runner.r.shuffle(batch)

One of the major problems in reproducing scheduler-dependent bugs is that the scheduler is in fact non-deterministic even if task timing and behavior is fully deterministic, because each Runner creates it's own independent random.Random instance.

Is there any strong reason not to use the global random.shuffle(), so that for e.g. HypothesisWorks/hypothesis#1709 we can force an arbitrary but reproducible order using random.seed()?

---

(revisiting this long after: we've had hypothesis.register_random() for years now, so while it takes a little coordination under the hood, pytest-trio can hook up everything as-is)