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

Start by running the supplied threading harness on a CPython free-threading build and inspect the set-operation entry points involved in intersection_update and symmetric_difference_update. Reproduce the incorrect {1, 5} result, then add a focused regression test covering concurrent updates; done means only the two documented results, {7, 8, 9} or {}, are observed.