nogil violation of atomicity on set operations

Bug report

Bug description:

Hi,

We're a research group focused on testing concurrent runtimes. Our work-in-progress prototype found a violation of atomicity on the current nogil build when using concurrent operations on the same set. The program below shows the wrong behavior.

from threading import Thread,Barrier

def t1(b1,s):
    b1.wait()
    s.intersection_update({1,5})

def t2(b1,s):
    b1.wait()
    s.symmetric_difference_update({1, 8, 7, 5, 9})

def normalSetTest(i):

    s = {1,2,3,4,5,6}
    setCombos = [{7,8,9}, set()] # all possible results
    barrier = Barrier(2)
    threads = [ Thread(target= t1, args=(barrier,s,)), Thread(target= t2, args=(barrier,s,)) ]


    for t in threads:
        t.start()
    for t in threads:
        t.join()
    if s not in setCombos:
        print("\tfound bug on iter " + str(i) + ": " + str(s))


print("test begin...")

for n in range(0,2000):
    threads = []

    if n % 100 == 0:
        print(n)

    for i in range(0,100):
        threads.append(Thread(target= normalSetTest, args=(n,)))

    for t in threads:
        t.start()

    for t in threads:
        t.join()

print("test done")

A set starts with {1,2,3,4,5,6} and two threads each make a concurrent operation on it: intersection_update({1,5}) and symmetric_difference_update({1, 8, 7, 5, 9}).

Depending on the order of execution, the possible results are either {7,8,9} or {} (the empty set).

Running the test harness above shows that the (incorrect) result {1, 5} is sometimes possible.

If you have trouble observing this behavior, feel free to increase the first range's last argument to a large integer (e.g., from 2000 to 10000).

We replicated this bug on 3 different machines with varying numbers of cores; and we were able to find it even using a single pair of threads (i.e., the second range's argument from 100 to 1). The current harness uses 100 pairs of threads operating on unrelated sets to speed up bug discovery.

We're happy to provide more details about this bug, and to help developers reproducing it.

Output of python -VV: Python 3.14.0a1+ experimental free-threading build (heads/main:faa3272fb8d, Oct 29 2024, 09:14:25) [GCC 14.2.1 20240805]

Example output:

test begin...
0
100
200
300
        found bug on iter 346: {1, 5}
400
500
600
700
800
900
1000
1100
1200
1300
1400
1500
1600
        found bug on iter 1678: {1, 5}
1700
1800
        found bug on iter 1864: {1, 5}
        found bug on iter 1882: {1, 5}
1900
test Done

@flypoodles and @overlorde are part of the team, adding them so they get notified about further discussion.

CPython versions tested on:

3.13, 3.14, CPython main branch

Operating systems tested on:

Linux

まず、提供された threading harness を CPython free-threading build で実行し、intersection_update と symmetric_difference_update に関係する集合操作のエントリーポイントを調べます。誤った結果 {1, 5} を再現し、その後、並行更新を対象とする絞り込んだ回帰テストを追加します。完了とみなされるのは、文書化された 2 つの結果である {7, 8, 9} または {} のみが観測される場合です。