3.15 regression: concurrent first imports can fail or hang without any import cycle #159963

... because parents' module locks stay held while a submodule's body runs

Bug report

(bear with me this is verbose, yes mostly model written, i tried to make sure the important info was up top - and i have a proposed fix coming) -gps

Description

Since gh-83065 (GH-137196, in 3.15.0b1 and later), _find_and_load("a.leaf") also takes the module lock of a if a isn't fully imported yet, and releases it together with the lock of a.leaf, after the body of a/leaf.py has run. So a thread whose first import of a.leaf also imports a keeps the lock of a long after a is fully initialised, for as long as the body of a.leaf runs, including everything that body imports. A second thread that found a missing or still initializing waits for that lock... Oops! 😬

This causes three failures that 3.14 and earlier don't have. None needs an import cycle, and in one thread the same imports work in either order:

1. _DeadlockError reaches user code.
2. ImportError: cannot import name 'X' from partially initialized module 'b' (most likely due to a circular import), or an AttributeError on a partially initialised module. Real packages fail this way (cryptography, protobuf, pyasn1; see below).
3. The second thread blocks for as long as the submodule's body runs. If that body waits for the second thread by anything other than an import, both hang, and no _DeadlockError is raised.

Short reproducer (failure 1)

import os, shutil, sys, tempfile, threading, time

root = tempfile.mkdtemp()
sys.path.insert(0, root)
for path, text in {
    "a/__init__.py": "import time; time.sleep(0.2)",   # any package whose __init__ takes a while
    "a/leaf.py":     "from b.leaf import X",
    "b/__init__.py": "import a",
    "b/leaf.py":     "X = 1",
}.items():
    os.makedirs(os.path.dirname(os.path.join(root, path)), exist_ok=True)
    with open(os.path.join(root, path), "w") as f:
        f.write(text + "\n")

def thread_1():
    import a.leaf

def thread_2():
    time.sleep(0.1)        # start while a/__init__.py is running
    import b.leaf

threads = [threading.Thread(target=thread_1), threading.Thread(target=thread_2)]
for t in threads: t.start()
for t in threads: t.join()
shutil.rmtree(root)
print("a.leaf imported:", "a.leaf" in sys.modules, "- b.leaf imported:", "b.leaf" in sys.modules)
sys.exit("a.leaf" not in sys.modules or "b.leaf" not in sys.modules)

The dependencies are a.leaf -> b.leaf -> b -> a, and a imports nothing, so there is no cycle. On 3.15.0:

Exception in thread Thread-1 (thread_1):
Traceback (most recent call last):
  File "threading.py", line 1218, in _bootstrap_inner
    self._context.run(self.run)
    ~~~~~~~~~~~~~~~~~^^^^^^^^^^
  File "threading.py", line 1160, in run
    self._target(*self._args, **self._kwargs)
    ~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "repro_mini.py", line 16, in thread_1
    import a.leaf
  File "a/leaf.py", line 1, in <module>
    from b.leaf import X
  File "<frozen importlib._bootstrap>", line 1347, in _find_and_load
  File "<frozen importlib._bootstrap>", line 458, in __enter__
  File "<frozen importlib._bootstrap>", line 346, in acquire
_frozen_importlib._DeadlockError: deadlock detected by _ModuleLock('b.leaf') at 140633457717456
a.leaf imported: False - b.leaf imported: True

• Expected (as on 3.11 to 3.14): both imports succeed; the script prints a.leaf imported: True - b.leaf imported: True and exits with status 0. Thread 2 needs only a, and a is complete.
• Actual (3.15.0): thread 1 raises _DeadlockError; exit status 1.

The cause shows without threads. With an empty w/__init__.py and this w/main.py:

import importlib._bootstrap as b
ref = b._module_locks.get("w"); lock = ref() if ref else None
print("lock of w held while w.main's body runs:", bool(lock and lock.locked()))

python -c "import w.main" prints True on 3.15.0 and False on 3.14.7.

directional thoughts...

• The change adding _HierarchicalLockManager` still fixed more than it added so just rolling it back to match 3.14.x and 3.13.16+ behavior doesn't feel right but would be an option.
• Workaround: import the parent in its own statement first (import a, then import a.leaf; 0 of 20 runs of reproducer 1 fail then), or make the imports on the main thread before threads start.

What happens, step by step

Line numbers are those of Lib/importlib/_bootstrap.py at tag v3.15.0.

• _find_and_load() chooses _HierarchicalLockManager(name) for a dotted name (1342-1343). Its with block (1347) spans all of _find_and_load_unlocked() (1350), which imports the parent (1277) and then runs the module's own body (1309, _load_unlocked(), exec_module at 915).
• __enter__ (448-477) takes the lock of every ancestor that is missing from sys.modules or still initialising, then the leaf's. __exit__ (479-482) releases them all, only at the end of that with block.
• The parent's own import (1277; for a top-level parent through _ModuleLockManager, 1345) takes the parent's lock a second time. When a/__init__.py is done, its release only brings the count from 2 to 1, so release() wakes nobody (378-383).
• Other threads wait for that lock because they found a missing from sys.modules or still initialising: in _lock_unlock_module() (524-538, called by import_ensure_initialized(), Python/import.c 310-337, "Wait until module is done importing"), in _ModuleLockManager.__enter__ (419-421; a plain import a that doesn't find a in sys.modules), in _HierarchicalLockManager.__enter__ (452-458), or by way of 1291-1292. All they need is that a is complete.

thread 1  wants       a
thread 1  has (1)     a
thread 1  wants       a.leaf
thread 1  has (1)     a.leaf
thread 1  wants       a
thread 1  has (2)     a
thread 2  wants       b
thread 2  has (1)     b
thread 2  wants       b.leaf
thread 2  has (1)     b.leaf
thread 2  wants       b
thread 2  has (2)     b
thread 2  wants       a
thread 1  gives back (1) a
thread 1  wants       b
thread 1  DEADLOCK    b
thread 1  wants       b.leaf
thread 1  DEADLOCK    b.leaf
thread 1  gives back (0) a.leaf
thread 1  gives back (0) a
thread 2  has (1)     a
thread 2  gives back (0) a
thread 2  gives back (1) b
thread 2  gives back (0) b.leaf
thread 2  gives back (0) b

How the three failures arise:

1. Thread 1 asks for b.leaf, which is not in sys.modules yet. __enter__ gets _DeadlockError on b and skips it (459-467), gets it again on b.leaf, and raises, because that is the leaf (460-461).
2. If the wanted module is already in sys.modules, because thread 2 is inside its body, import.c goes through _lock_unlock_module(), which swallows the _DeadlockError (533-536) and hands out the partially initialised module. importlib.import_module('b') in the same place raises _DeadlockError instead (20 of 20 runs).
3. In the hang, thread 1 isn't waiting for a module lock at all, so the deadlock detector has nothing to find.

"Parent before child" orders the locks along one dotted name, but gives no order between two chains, (a, a.leaf) and (b, b.leaf). Since a chain stays held while module bodies run, a thread can ask for a second chain while holding the first. Before 3.15, a thread inside the body of a.leaf held only the locks of a.leaf and of the modules further out on its own import stack, all really unfinished, so it could only block a thread that needed one of those. Now it also blocks every thread that needs only the finished a and happened to look before a was complete.

This trade-off (ancestors' locks held through the leaf's body) isn't discussed in the class docstring (437-441), the comment at 462-466, the two new tests, the NEWS entry (3.15.0 beta 1: "so the two threads serialise instead of raising _DeadlockError") or What's New, so it looks unintended. test_cross_package_circular_import (Lib/test/test_importlib/test_threaded_import.py, 410-414) says even of two packages that do import each other that concurrent imports of their submodules "must not raise _DeadlockError". CPython's own tests don't catch these failures: python -m test -j2 test_importlib test_import test_threading test_runpy test_pkgutil test_zipimport test_lazy_import passes on the 3.15.0 build.

"""Two threads make first imports in two packages.  No import cycle, and either
order works in one thread, yet thread 1 fails on 3.15 (passes on 3.11 to 3.14).

    python repro_error.py           -> _DeadlockError
    python repro_error.py partial   -> ImportError: cannot import name 'X' from
                                       partially initialized module 'b'
"""
import importlib._bootstrap as bootstrap
import os, shutil, sys, tempfile, threading, time, traceback, types

CASES = {
    # Needs: a.leaf -> b.leaf -> b -> a.  "a" imports nothing, so there is no cycle.
    "deadlock": ("import a.leaf", "import b.leaf", {
        "a/__init__.py": "import sync; sync.slow_init()",
        "a/leaf.py":     "from b.leaf import X",
        "b/__init__.py": "import a",
        "b/leaf.py":     "X = 1"}),
    # Needs: a.leaf -> b -> a.  No cycle either.
    "partial": ("import a.leaf", "import b", {
        "a/__init__.py": "import sync; sync.slow_init()",
        "a/leaf.py":     "from b import X",
        "b.py":          "import a; X = 1"}),
}
stmt1, stmt2, files = CASES[sys.argv[1] if len(sys.argv) > 1 else "deadlock"]

sys.dont_write_bytecode = True
root = tempfile.mkdtemp()
sys.path.insert(0, root)
for path, text in files.items():
    os.makedirs(os.path.dirname(os.path.join(root, path)), exist_ok=True)
    with open(os.path.join(root, path), "w") as f:
        f.write(text + "\n")

# "sync" is not a file: it lets a/__init__.py call back into this script.
sync = sys.modules["sync"] = types.ModuleType("sync")

# Control: one thread, both orders.
sync.slow_init = lambda: None
for order in ((stmt1, stmt2), (stmt2, stmt1)):
    for stmt in order:
        exec(stmt)
    for name in [n for n in sys.modules if n.split(".")[0] in ("a", "b")]:
        del sys.modules[name]
print("one thread, both orders: ok")

# Two threads.  a/__init__.py stands for any package whose __init__ takes a while:
# it returns once thread 2 has got as far as waiting for the module lock of "a".
# No sleep decides the order; the private _blocking_on is only read, to see that moment.
in_a = threading.Event()
failed = []

def slow_init():
    in_a.set()
    while "_ModuleLock('a')" not in repr(bootstrap._blocking_on.get(t2.ident)):
        time.sleep(0.001)
sync.slow_init = slow_init

def run(stmt, start_after=None):
    if start_after:
        start_after.wait()
    try:
        exec(stmt)
    except BaseException:
        failed.append(stmt)
        print(f"{threading.current_thread().name}, {stmt!r}:")
        traceback.print_exc(file=sys.stdout)

t1 = threading.Thread(target=run, args=(stmt1,), name="thread 1", daemon=True)
t2 = threading.Thread(target=run, args=(stmt2, in_a), name="thread 2", daemon=True)
t2.start(); t1.start()
t1.join(30); t2.join(30)
if t1.is_alive() or t2.is_alive():
    failed.append("still running after 30 s")
shutil.rmtree(root, ignore_errors=True)
print("two threads:", f"FAILED {failed}" if failed else "ok", "on", sys.version.split()[0])
sys.exit(1 if failed else 0)

$ python repro_error.py
one thread, both orders: ok
thread 1, 'import a.leaf':
Traceback (most recent call last):
  File "repro_error.py", line 62, in run
    exec(stmt)
    ~~~~^^^^^^
  File "<string>", line 1, in <module>
  File "a/leaf.py", line 1, in <module>
    from b.leaf import X
  File "<frozen importlib._bootstrap>", line 1347, in _find_and_load
  File "<frozen importlib._bootstrap>", line 458, in __enter__
  File "<frozen importlib._bootstrap>", line 346, in acquire
_frozen_importlib._DeadlockError: deadlock detected by _ModuleLock('b.leaf') at 139688739099088
two threads: FAILED ['import a.leaf'] on 3.15.0
$ python repro_error.py partial
one thread, both orders: ok
thread 1, 'import a.leaf':
Traceback (most recent call last):
  File "repro_error.py", line 62, in run
    exec(stmt)
    ~~~~^^^^^^
  File "<string>", line 1, in <module>
  File "a/leaf.py", line 1, in <module>
    from b import X
ImportError: cannot import name 'X' from partially initialized module 'b' (most likely due to a circular import) (b.py)
two threads: FAILED ['import a.leaf'] on 3.15.0

"""Thread 1 makes the first import of w.main.  Thread 2 imports w.other, and starts
while w/__init__.py is still running.  On 3.15 thread 2 then has to wait until the
BODY of w.main has ended, though "w" was complete long before.  Here that body waits
for thread 2, so both would hang forever; no _DeadlockError is raised.  The wait is
cut off after 5 s so that the script ends.  Passes on 3.11 to 3.14.
"""
import importlib._bootstrap as bootstrap
import os, shutil, sys, tempfile, threading, time, traceback, types

files = {
    "w/__init__.py": "import sync; sync.slow_init()",
    "w/main.py":     "import sync; sync.wait_for_thread_2()",
    "w/other.py":    "",
}
sys.dont_write_bytecode = True
root = tempfile.mkdtemp()
sys.path.insert(0, root)
os.mkdir(os.path.join(root, "w"))
for path, text in files.items():
    with open(os.path.join(root, path), "w") as f:
        f.write(text + "\n")

in_w = threading.Event()
thread_2_done = threading.Event()
hung = []

def slow_init():
    # Stands for any __init__ that takes a while: returns once thread 2 waits for
    # the module lock of "w" (or is done: before gh-130094 it doesn't wait at all).
    in_w.set()
    while not (thread_2_done.is_set() or
               "_ModuleLock('w')" in repr(bootstrap._blocking_on.get(t2.ident))):
        time.sleep(0.001)

def wait_for_thread_2():
    w = sys.modules["w"]
    print("w.main's body runs; w.__spec__._initializing =", w.__spec__._initializing)
    if not thread_2_done.wait(5):
        hung.append(True)
        print("after 5 s thread 2 is still here:")
        traceback.print_stack(sys._current_frames()[t2.ident], limit=4, file=sys.stdout)

# "sync" is not a file: it lets the modules call back into this script.
sync = sys.modules["sync"] = types.ModuleType("sync")
sync.slow_init, sync.wait_for_thread_2 = slow_init, wait_for_thread_2

def thread_1():
    import w.main

def thread_2():
    in_w.wait()
    t0 = time.monotonic()
    import w.other
    thread_2_done.set()
    print(f"thread 2: 'import w.other' took {time.monotonic() - t0:.1f} s")

t1 = threading.Thread(target=thread_1, daemon=True)
t2 = threading.Thread(target=thread_2, daemon=True)
t2.start(); t1.start()
t1.join(30); t2.join(30)
shutil.rmtree(root, ignore_errors=True)
print("HANG (cut off by the script)" if hung else "ok", "on", sys.version.split()[0])
sys.exit(1 if hung else 0)

$ python repro_hang.py
w.main's body runs; w.__spec__._initializing = False
after 5 s thread 2 is still here:
  File "repro_hang.py", line 53, in thread_2
    import w.other
  File "<frozen importlib._bootstrap>", line 1347, in _find_and_load
  File "<frozen importlib._bootstrap>", line 458, in __enter__
  File "<frozen importlib._bootstrap>", line 365, in acquire
thread 2: 'import w.other' took 5.1 s
HANG (cut off by the script) on 3.15.0

w.main's body runs; w.__spec__._initializing = False
thread 2: 'import w.other' took 0.0 s
ok on 3.14.7

CPython versions tested on:

CPython main branch, 3.15

Operating systems tested on:

Linux

Linked PRs

• gh-159963: Don't hold parent package import locks while a submodule executes #159965