`reversed(dict)` can read out of bounds and segfault (`dictreviter_iter_lock_held`)

[devdanzin]

Crash report

What happened?

reversed() on a dict can dereference an entry index that is far past the end of the dict's current keys table, from ordinary pure-Python code. On a release build this segfaults.

Reproducer

d = {}
for i in range(1000):
    d["k%d" % i] = i          # combined table, dk_nentries == 1000
for i in range(1, 1000):
    del d["k%d" % i]          # ma_used == 1, dk_nentries still 1000

it = reversed(d)              # di_pos = dk_nentries - 1 = 999

d.clear()                     # fresh PyDict_MINSIZE keys object
d["k0"] = 0                   # ma_used == 1 again

for k in it:                  # reads DK_UNICODE_ENTRIES(k)[999] on a 5-slot table
    pass

Under ASan:

ERROR: AddressSanitizer: heap-use-after-free
READ of size 8 at 0x6d5563df4aa0 thread T0
    #0 dictreviter_iter_lock_held  Objects/dictobject.c:6284:31
    #1 dictreviter_iternext        Objects/dictobject.c:6354:13
    #2 _PyForIter_VirtualIteratorNext  Python/ceval.c:3775:22

The out-of-bounds address happens to land in a block freed by d.clear(), so ASan labels it use-after-free; the defect is the unbounded index either way.

All five reverse-iterator entry points crash: reversed(d), d.__reversed__(), reversed(d.keys()), reversed(d.values()), reversed(d.items()), across release-gil-nojit and debug-gil-nojit.

Mechanism

dictiter_new() seeds di_pos differently per table kind (Objects/dictobject.c:5632-5637):

if (_PyDict_HasSplitTable(dict)) {
    di->di_pos = used - 1;                        /* ma_used - 1 */
}
else {
    di->di_pos = load_keys_nentries(dict) - 1;    /* dk_nentries - 1 */
}

dictreviter_iter_lock_held() then has exactly one staleness check and one bound (:6261 and :6271):

if (di->di_used != d->ma_used) {          /* :6261 — compares ma_used only */
    PyErr_SetString(PyExc_RuntimeError, "dictionary changed size during iteration");
    ...
}

Py_ssize_t i = di->di_pos;
PyDictKeysObject *k = d->ma_keys;

if (i < 0) {                              /* :6271 — the ONLY bound */
    goto fail;
}
...
    PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(k)[i];   /* :6283 */
    while (entry_ptr->me_value == NULL) {                        /* :6284 — OOB read */

The bug is the mismatch between those two: the combined branch seeds di_pos from a quantity the staleness check does not constrain. ma_used says nothing about dk_nentries, so the guard cannot see a keys object replaced by a smaller one while the element count stayed equal. d.clear() followed by a single insertion does exactly that — di_used == ma_used == 1 passes, and di_pos is still 999.

The split branch is self-consistent by contrast, and I could not break it: its seed is ma_used - 1, the very quantity the staleness check pins, and any table holding ma_used entries has at least that many slots. I tried four shapes (shrink-and-restore, clear-and-restore, forcing a combined transition, and clear-then-one-key) across both builds — 8/8 no failure, two of them correctly stopped by the staleness check. Worth noting anyway that its only bound is assert(i < mp->ma_values->size) inside get_index_from_order, which compiles out under NDEBUG; the precondition holds by construction rather than by check.

The forward iterators already have the check

All three forward iterators bound i against the current table before dereferencing — e.g. dictiter_iternextkey_lock_held (:5732 and :5740-5747):

if (_PyDict_HasSplitTable(d)) {
    if (i >= d->ma_used)
        goto fail;
    ...
}
else {
    Py_ssize_t n = k->dk_nentries;
    ...
    if (i >= n)
        goto fail;
}

They can afford a weaker seed because di_pos starts at 0 and only grows. The reverse iterator starts at the far end, so it is precisely the one that needs the bound — and it is the only one without it.

Where the check went

This is not an oversight; the bound was written, reviewed, and removed.

PR GH-16846 (bpo-38525, 2019) fixed a different reverse-iterator crash. Its final commit, bf61754, does one thing:

     if (d->ma_values) {
-        if (i < 0 || i >= d->ma_used) {
+        if (i < 0) {
             goto fail;
         }

in response to a review exchange on Objects/dictobject.c:

@serhiy-storchaka Is this change still needed?

@corona10: No, it is not needed. I removed it on the latest commit.

The removal was reasonable for the branch it was on: the same PR had just changed the split-table seed to ma_used - 1, which makes i >= ma_used redundant there given the di_used != ma_used check. It never applied to the combined branch, which is seeded from dk_nentries and is where this segfaults.

Suggested fix

Give the reverse iterator the same two-branch bound its forward twins have — for the combined branch, load n = k->dk_nentries and reject i >= n before forming the entry pointer; for the split branch, reject i >= d->ma_used before calling get_index_from_order, restoring what bf61754 removed.

Scope

I checked the other reverse iterators in the tree, and dict's is the only one that indexes a raw C array directly. The others delegate the bound to a checked accessor:

• reversed_next (Objects/enumobject.c:440, the builtin reversed()) goes through PySequence_GetItem, which bounds-checks and raises IndexError.
• listreviter_next (Objects/listobject.c:4220) goes through list_get_item_ref, which tests valid_index(i, size) and again against the allocated capacity, returning NULL.
• dequereviter_next (Modules/_collectionsmodule.c) walks a block list, not an indexed array, under a critical section.

So this looks like a single-site bug rather than a class — dict's reverse iterator forms &DK_UNICODE_ENTRIES(k)[i] itself, with nothing between i and the dereference.

Full variant reproducers

"""reversed(dict) out-of-bounds read: all entry points + the split-table probe.

Run one variant per subprocess:

    python issue_CPY-0116_variants.py {dict|dunder|keys|values|items}
    python issue_CPY-0116_variants.py split:{shrink-restore|clear-restore|combined|clear-one}

The five combined-table entry points all SIGSEGV. The split-table probes do NOT --
see the note at the bottom of this file, which is the point of including them.
"""

import sys

N = 1000


def stale_combined_iter(make):
    """A reverse iterator whose di_pos is stale by ~N against a 5-slot table.

    di_pos is seeded from dk_nentries - 1 for a COMBINED table
    (dictobject.c:5636). The only staleness check is di_used != ma_used
    (dictobject.c:6261), which compares ma_used and says nothing about
    dk_nentries -- so replacing the keys object with a smaller one while
    keeping the element count equal walks straight past it.
    """
    d = {}
    for i in range(N):
        d["k%d" % i] = i          # combined table, dk_nentries == N
    for i in range(1, N):
        del d["k%d" % i]          # ma_used == 1, dk_nentries still N

    it = make(d)                  # di_pos = dk_nentries - 1 = N-1

    d.clear()                     # fresh PyDict_MINSIZE keys object
    d["k0"] = 0                   # ma_used == 1 again -> staleness check passes
    return it


ENTRY_POINTS = {
    "dict":   lambda d: reversed(d),
    "dunder": lambda d: d.__reversed__(),
    "keys":   lambda d: reversed(d.keys()),
    "values": lambda d: reversed(d.values()),
    "items":  lambda d: reversed(d.items()),
}


class C:
    pass


def make_split(n):
    """An instance __dict__ backed by a shared (split) keys table."""
    for _ in range(3):                    # warm the shared keys
        w = C()
        for i in range(n):
            setattr(w, "a%d" % i, i)
    o = C()
    for i in range(n):
        setattr(o, "a%d" % i, i)
    return o


def split_probe(mode, n=20):
    """Try to drive the SPLIT branch (dictobject.c:6274-6279) out of bounds.

    That branch calls get_index_from_order(d, i), whose only bound is
    `assert(i < mp->ma_values->size)` -- which compiles out under NDEBUG.
    """
    o = make_split(n)
    d = o.__dict__
    it = reversed(d)                      # di_pos = ma_used - 1

    if mode == "shrink-restore":
        for i in range(1, n):
            delattr(o, "a%d" % i)         # ma_used -> 1
        for i in range(1, n):
            setattr(o, "b%d" % i, i)      # ma_used -> n again, different keys
    elif mode == "clear-restore":
        d.clear()
        for i in range(n):
            setattr(o, "c%d" % i, i)
    elif mode == "combined":
        d[object()] = 1                   # non-str key forces combined
    elif mode == "clear-one":
        d.clear()
        o.a0 = 0
    else:
        raise SystemExit("unknown split mode %r" % mode)
    return it


def main():
    which = sys.argv[1] if len(sys.argv) > 1 else "dict"
    if which.startswith("split:"):
        it = split_probe(which.split(":", 1)[1])
    else:
        it = stale_combined_iter(ENTRY_POINTS[which])
    try:
        for _ in it:
            pass
    except RuntimeError as exc:
        print("RuntimeError: %s" % exc)
        return 0
    print("survived %s" % which)
    return 0


if __name__ == "__main__":
    sys.exit(main())


# Measured on release-gil-nojit and debug-gil-nojit (CPython main, 3.16.0a0):
#
#   dict dunder keys values items    -> SIGSEGV, 10/10 (5 entry points x 2 builds)
#   split:shrink-restore             -> survived, 2/2
#   split:clear-restore              -> survived, 2/2
#   split:combined                   -> RuntimeError (staleness check fires), 2/2
#   split:clear-one                  -> RuntimeError (staleness check fires), 2/2
#
# The split branch is not reachable by this route, and the reason is worth
# stating: its seed is `ma_used - 1`, the very quantity the staleness check
# pins, and any table holding ma_used entries has at least that many slots.
# The combined seed is `dk_nentries - 1`, which the staleness check does not
# constrain at all. That asymmetry -- not the missing bound alone -- is the bug.

Found with cpython-review-toolkit; reduced, reproduced and drafted with AI assistance (Claude Code)

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

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

Python 3.16.0a0 (heads/main:a1d580430c8, Jul 18 2026, 20:21:17) [Clang 21.1.8 (6ubuntu1)]

Linked PRs

• gh-154709: Fix out-of-bounds access in dict reverse iterator #154721