Improve detection of `Py_DECREF` on dictionaries in freelist

[hansingt]

Crash report

What happened?

After updating my extension library from Python 3.11 to 3.14, I had a strage segmentation fault raised by my tests. The analysis of this issue took me about a week. The problem here was the introduction of freelists for Python Dictionaries:

When a Python dictionary is freed (refcnt == 0), it get's appended to a list of "free" objects, which may get reused by subsequent PyDict_New() calls. This freelist is implemented as a linked LIFO list. The link between the elements in this list is done by "reusing" the reference counter of the dictionary and storing the address of the next elements in the list in it. This can be problematic because of two reasons:

First of all, if I accidentally Py_DECREF a dictionary too many times, the reference counter does not become negative and hence, this issue is not detected. This is, because the reference counter will container a pointer to the next element as soon as it gets zero. Hence, the next call of Py_DECREF will read the pointer address as integer and assume it is just very large (or in best case negative, in which case it may fail).
This is bad, as it hardens bug detection in debug builds.

But the real problem araises, if the integer representation of the pointer in this dict is not larget than the minimum reference count for immortals: If the integer is larger than this value, the dict is counted as immortal and nothing happens - happy case. If not, Py_DECREF (or Py_INCREF) will modify the reference count and thus, accidentally modifies the pointer! At this point the pointer is off by one and the freelist is broken.

Now, if two new dictionaries are requested, this can cause a segmentation fault on the second dict, because the process might read one byte behind its memory. In best case, this pops up near to the place, where the dict was decref'd, but in worse case, this situation can linger for a long time in the program and pop up in a completely unrelated place. E.g. even when doing d = {} in the Python code.

The following code tries to demonstrate this problem:

#include <Python.h>

void main() {
    PyObject *d1, *d2, *dict;
    Py_Initialize();

    // populate the freelist with two dicts
    d1 = PyDict_New();
    Py_DECREF(d1);

    d2 = PyDict_New();
    Py_DECREF(d2);

    // Now decref a dict too many times
    // For this, first create a new dict. It will take the first entry from the freelist (d2).
    dict = PyDict_New();
    assert(dict == d2);
    assert(Py_REFCNT(dict) == 1);

    // Now if we decref this dict, the reference counter will be overwritten
    // with the next element in the freelist (d1).
    Py_DECREF(dict);
    assert(Py_REFCNT(dict) == (Py_ssize_t)d1);

    // Now comes the bug: 
    // IFF (int)d1 < _Py_IMMORTAL_MINIMUM_REFCNT, the dict is not considered immortal
    // and a Py_DECREF will accidentally modify the address pointer
    Py_DECREF(dict);
    assert(PyUnstable_IsImmortal(dict) || Py_REFCNT(dict) == (Py_ssize_t)d1 - 1);
}

The output of this depends on the address of d1 and whether it's integer representation is larger than _Py_IMMORTAL_MINIMUM_REFCNT or not.

CPython versions tested on:

3.14

Operating systems tested on:

Linux, Windows

Output from running 'python -VV' on the command line:

Python 3.14.1 (main, Dec 2 2025, 19:40:56) [Clang 21.1.4 ]

[sergey-miryanov]

First of all, your code is not safe.
assert(Py_REFCNT(dict) == (Py_ssize_t)d1); is not safe, because dict maybe be freed after previous Py_DECREF.

Second, we have Py_REF_DEBUG configuration option. In this case, if refcounter goes negative we get an assert. Is this option useful for you?

[hansingt]

First of all, your code is not safe.
assert(Py_REFCNT(dict) == (Py_ssize_t)d1); is not safe, because dict maybe be freed after previous Py_DECREF.

This is just an example to demonstrate the issue. With the introduction of freelists for dicts, a dictionary will exactly not be freed, as long as the freelist is not full. If the freelist is full, the issue does not occurr.

Second, we have Py_REF_DEBUG configuration option. In this case, if refcounter goes negative we get an assert. Is this option useful for you?

That's exactly, what I was trying to tell: It may not get negative, because the reference counter stores the address of the next element in the freelist and will be interpreted as Py_ssize_t in Py_DECREF. Hence, if the integer representaion of the address in the reference counter is not negative, this is not recognized by Py_DECREF, even with Py_REF_DEBUG enabled. That's exactly the first part of my issue here.

The second part then is, if the integer representation of this address is not large enough for the dict to be considered immortal, it does even get modified by Py_DECREF, corrupting the freelist.

[sergey-miryanov]

Ough, I see that you mean.

It is where we update linked lists:

cpython/Include/internal/pycore_freelist.h

Lines 55 to 61 in 53ec7c8

	if (fl->size < maxsize && fl->size >= 0) {
	FT_ATOMIC_STORE_PTR_RELAXED(*(void **)obj, fl->freelist);
	fl->freelist = obj;
	fl->size++;
	OBJECT_STAT_INC(to_freelist);
	return 1;
	}

[sergey-miryanov]

@colesbury Could you please take a look?

[colesbury]

After updating my extension library from Python 3.11 to 3.14, I had a strage segmentation fault raised by my tests

So if I understand correctly, your extension called Py_DECREF on freed dictionaries and this wasn't detected on 3.11. On 3.14, this routinely crashed. That seems fine?

We had freelists for dictionaries before 3.14. They were just implemented differently and 3.14 unified the freelist implementation across many objects.

Using the first word of a freed memory block for the freelist is a very normal thing for allocators to do. We can consider adding extra detection for freelist corruption, but you should expect that your program will crash or misbehave if you call Py_DECREF on a freed object.

[sergey-miryanov]

@colesbury I agree with you. However, it seems that Py_REF_DEBUG has become less useful. Even if we aren't crashing the freelist, we can decref an object that we don't own.

[colesbury]

Here is a relatively simple idea: In Py_REF_DEBUG, invert (~) the pointer used for the freelist. That will make typically positive pointers look like negative refcounts.

[hansingt]

So if I understand correctly, your extension called Py_DECREF on freed dictionaries and this wasn't detected on 3.11. On 3.14, this routinely crashed. That seems fine?

Of course not. I know, that this is a bug in our software and that it can cause misbegaviour or crashes. I don't know. why we did not detect it in 3.11, but at least with 3.14, we couldn't detect it with Py_REF_DEBUG.

Here is a relatively simple idea: In Py_REF_DEBUG, invert (~) the pointer used for the freelist. That will make typically positive pointers look like negative refcounts.

Integer representations of pointers can be negative as well, of the memory address is high enough. You won't detect these then.

What I know, what other allocators so in these cases is using a tagged pointer: The memory blocks do have some alignment you know at compile time. This leaves some of the lower bits unused. Theseccan then be used to differentiate between a pointer and a reference count. Of course, this would "steal" one bit from reference counting, but I don't think hat this is problematic, as everything above 2^30 is counted as immutable anyway I think. So there are two bits left.