Possible race condition in RecursiveStrategy

[Stranger6667]

Hi!

I found a race condition when multiple tests share the same RecursiveStrategy instance and are executed in multiple threads.

An example:

import threading
from hypothesis import strategies as st, given, settings

STRATEGY = st.recursive(
    st.integers(),
    lambda strategy: st.lists(strategy, max_size=3)
    | st.dictionaries(st.text(), strategy, max_size=3),
)


def test():
    @given(st.data())
    @settings(max_examples=25)
    def inner(data):
        data.draw(STRATEGY)

    threads = []

    for _ in range(2):
        threads.append(threading.Thread(target=inner))

    for t in threads:
        t.start()

    for t in threads:
        t.join()

When running this sample with pytest, the following error occurs (traceback trimmed):

...
  File "/.../lib/python3.8/site-packages/hypothesis/strategies/_internal/recursive.py", line 50, in capped
    assert not self.currently_capped
AssertionError: assert not True

It happens because drawing from that shared strategy in one thread changes the shared state (currently_capped to True in the limited_base attribute) and if another thread draws from the same strategy while another one is still inside the self.limited_base.capped ctx manager it fails with AssertionError.

Some time ago, I reported a race condition in #2433, and this issue comes from the same use case - Schemathesis running with multiple workers (reported here - schemathesis/schemathesis#860).

The fix is straightforward - a lock inside RecursiveStrategy.do_draw - I can submit a patch that fixes it.

Let me know what do you think :)

[Zalathar]

I've only just glanced at this, but would it make more sense to change LimitedStrategy's capped state (currently_capped and marker) to be thread-local, rather than using a lock?

[Zac-HD]

We've already moved 'dynamic variables' (e.g. the current settings) to thread-locals, so that makes sense to me.

My main concern is whether this - even if we e.g. add st.shared() and audit for other cases - is just tweaking a fundamentally broken abstraction... On one hand I don't think we can patch our way to thread-safety; on the other I'm not going to reject useful patches either. If possible I'd like a more principled approach though, and/or explicit docs on whether or not multithreading is "really supported" - at present I assume default-yes since we have thread-safety patches, and in this case it's terribly under-tested 😱

[Stranger6667]

Thank you for your feedback!

My initial idea was to isolate that block from multithreaded access at all in a more defensive way - as far as I see, calling data.draw may involve calling arbitrary code in custom strategies that may have some state as well. Having thread-local storage won't prevent race condition down there (as base_strategy is shared), or at least it is not immediately visible to me. Also, it changes the ConjectureData state (e.g., its depth), and I am not sure whether all these underlying parts are thread-safe as well.

Therefore I thought that having a lock will prevent race conditions in this exact use-case. However, I am not sure whether it causes deadlocks or not (the example above worked with a lock). I will check this and try to get more details on which approach might work better.