enum_next and pairwise_next can result in tuple elements with zero reference count in free-threading build

[eendebakpt]

Bug report

Bug description:

The enumerate object (and also the itertools.pairwise since #118219) re-uses tuples when possible. It does this by checking the reference count to be 1:

   // from enum_next in enumobject.c
    if (Py_REFCNT(result) == 1) {
        Py_INCREF(result);
        old_index = PyTuple_GET_ITEM(result, 0);
        old_item = PyTuple_GET_ITEM(result, 1);
        PyTuple_SET_ITEM(result, 0, next_index);
        PyTuple_SET_ITEM(result, 1, next_item);
        Py_DECREF(old_index);
        Py_DECREF(old_item);
        ....

The refcount check and increment are not atomic, so in the free-threading build multiple threads can end up operating on the result object. It is possible that one thread already sets an item in the tuple, and another thread decrefs the item believing it is still an old item.

In the nogil reference implementation (https://github.com/colesbury/nogil) no changes are made to address this. So maybe the issue cannot occur?

In #120591 this problem is addressed with a lock, which might be too much overhead (see the discussion in #120496)

@colesbury @hauntsaninja

CPython versions tested on:

CPython main branch

Operating systems tested on:

Windows

Linked PRs

• gh-121464: Make concurrent iteration over enumerate safe under free-threading #125734

[eendebakpt]

There are more places in the codebase where the same issue occurs:

cpython/Modules/itertoolsmodule.c

Lines 360 to 367 in 58fdb16

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	PyObject *last_old = PyTuple_GET_ITEM(result, 0);
	PyObject *last_new = PyTuple_GET_ITEM(result, 1);
	PyTuple_SET_ITEM(result, 0, Py_NewRef(old));
	PyTuple_SET_ITEM(result, 1, Py_NewRef(new));
	Py_DECREF(last_old);
	Py_DECREF(last_new);

cpython/Modules/itertoolsmodule.c

Lines 3713 to 3736 in 58fdb16

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	for (i=0 ; i < tuplesize ; i++) {
	it = PyTuple_GET_ITEM(lz->ittuple, i);
	if (it == NULL) {
	item = Py_NewRef(lz->fillvalue);
	} else {
	item = PyIter_Next(it);
	if (item == NULL) {
	lz->numactive -= 1;
	if (lz->numactive == 0 || PyErr_Occurred()) {
	lz->numactive = 0;
	Py_DECREF(result);
	return NULL;
	} else {
	item = Py_NewRef(lz->fillvalue);
	PyTuple_SET_ITEM(lz->ittuple, i, NULL);
	Py_DECREF(it);
	}
	}
	}
	olditem = PyTuple_GET_ITEM(result, i);
	PyTuple_SET_ITEM(result, i, item);
	Py_DECREF(olditem);

cpython/Objects/enumobject.c

Lines 246 to 253 in 126910e

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	old_index = PyTuple_GET_ITEM(result, 0);
	old_item = PyTuple_GET_ITEM(result, 1);
	PyTuple_SET_ITEM(result, 0, next_index);
	PyTuple_SET_ITEM(result, 1, next_item);
	Py_DECREF(old_index);
	Py_DECREF(old_item);

cpython/Objects/enumobject.c

Lines 246 to 253 in 126910e

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	old_index = PyTuple_GET_ITEM(result, 0);
	old_item = PyTuple_GET_ITEM(result, 1);
	PyTuple_SET_ITEM(result, 0, next_index);
	PyTuple_SET_ITEM(result, 1, next_item);
	Py_DECREF(old_index);
	Py_DECREF(old_item);

cpython/Objects/enumobject.c

Lines 196 to 209 in 126910e

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	old_index = PyTuple_GET_ITEM(result, 0);
	old_item = PyTuple_GET_ITEM(result, 1);
	PyTuple_SET_ITEM(result, 0, next_index);
	PyTuple_SET_ITEM(result, 1, next_item);
	Py_DECREF(old_index);
	Py_DECREF(old_item);
	// bpo-42536: The GC may have untracked this result tuple. Since we're
	// recycling it, make sure it's tracked again:
	if (!_PyObject_GC_IS_TRACKED(result)) {
	_PyObject_GC_TRACK(result);
	}
	return result;

cpython/Python/bltinmodule.c

Lines 2974 to 2994 in 58fdb16

	if (Py_REFCNT(result) == 1) {
	Py_INCREF(result);
	for (i=0 ; i < tuplesize ; i++) {
	it = PyTuple_GET_ITEM(lz->ittuple, i);
	item = (*Py_TYPE(it)->tp_iternext)(it);
	if (item == NULL) {
	Py_DECREF(result);
	if (lz->strict) {
	goto check;
	}
	return NULL;
	}
	olditem = PyTuple_GET_ITEM(result, i);
	PyTuple_SET_ITEM(result, i, item);
	Py_DECREF(olditem);
	}
	// bpo-42536: The GC may have untracked this result tuple. Since we're
	// recycling it, make sure it's tracked again:
	if (!_PyObject_GC_IS_TRACKED(result)) {
	_PyObject_GC_TRACK(result);
	}

[rhettinger]

It would be reasonable to ifdef out the tuple reuse fast path on a free-threaded build.

[eendebakpt]

@rhettinger Disabling the re-use of the tuple solves part of the issues with free-threading.

We should also disable clearing the reference to the iterator (e.g. Py_CLEAR(po->it); inside pairwise_enum), otherwise one thread can clear the iterator (making the reference count zero) and another thread still use it. That will not impact performance or impact readability of the code. But it could subtly change behavior (see the notes in #123848 on exhausting the iterator)

And finally we have to make sure we handle updates to po->old correctly. In current main it can happen that in one thread the reference count to po->old is reduced to zero at lines

cpython/Modules/itertoolsmodule.c

Lines 382 to 383 in dd0ee20

	Py_XSETREF(po->old, new);
	Py_DECREF(old);

while in another thread a borrowed reference is obtained at

cpython/Modules/itertoolsmodule.c

Line 331 in dd0ee20

PyObject *old = po->old;

I think for pairwise we can do this with reasonably clean code.

For some other methods in itertools the situation is similar: there is an internal state that needs to be mutated during iteration. For example for itertools.product the internal state of the iterator is contained in lz->indices and lz->result and mutated in

cpython/Modules/itertoolsmodule.c

Lines 2057 to 2075 in dd0ee20

	for (i=npools-1 ; i >= 0 ; i--) {
	pool = PyTuple_GET_ITEM(pools, i);
	indices[i]++;
	if (indices[i] == PyTuple_GET_SIZE(pool)) {
	/* Roll-over and advance to next pool */
	indices[i] = 0;
	elem = PyTuple_GET_ITEM(pool, 0);
	Py_INCREF(elem);
	oldelem = PyTuple_GET_ITEM(result, i);
	PyTuple_SET_ITEM(result, i, elem);
	Py_DECREF(oldelem);
	} else {
	/* No rollover. Just increment and stop here. */
	elem = PyTuple_GET_ITEM(pool, indices[i]);
	Py_INCREF(elem);
	oldelem = PyTuple_GET_ITEM(result, i);
	PyTuple_SET_ITEM(result, i, elem);
	Py_DECREF(oldelem);
	break;

I will think a bit more about alternative options.