Data race in list.sort() on no-gil build

[weixlu]

Bug report

Bug description:

Summary

As reported in #153852 (TSAN0014), list.sort() writes each slot of the array with a plain, non-atomic store. When another thread concurrently accesses the same list, there is a data race between the in-place sort and the reader, which will be reported by TSAN.

How to reproduce

First we need to enable thread-sanitizer

• ./configure --disable-gil --with-thread-sanitizer
• TSAN_OPTIONS="halt_on_error=1 symbolize=1 history_size=4" ./python repro.py

Then run the following repro.py

import sys, threading

size, rounds, num_threads = 2000, 1500, 32
SCRAMBLED = sorted(range(size), key=lambda x: (x * 2654435761) & 0xFFFFFFFF)
global_list = list(SCRAMBLED)
enter, leave = threading.Barrier(num_threads + 1), threading.Barrier(num_threads + 1)

def reader():
    for _ in range(rounds):
        enter.wait()
        for _x in global_list:
            pass
        leave.wait()

def main_sorter():
    for _ in range(rounds):
        global_list[:] = SCRAMBLED
        enter.wait()
        global_list.sort()
        leave.wait()

ts = [threading.Thread(target=reader) for _ in range(num_threads)]
for t in ts: 
    t.start()
main_sorter()
for t in ts: 
    t.join()

Finally we could see the log from TSan

WARNING: ThreadSanitizer: data race (pid=3143552)
  Write of size 8 at 0xffffb6b3c018 by main thread:
    #0 binarysort Objects/listobject.c:1918 (python+0x1c64bc)

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-154756: Fix data race in list.sort() #154572