[issue35091] Objects/listobject.c: gallop functions rely on signed integer overflow

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

This doesn't actually matter - the code can never trigger.  It would be fine to replace it with an assert to that effect (see below for a specific suggestion).

The reason:  The indices in this code are into vectors of PyObject*.  These vectors can't contain more than

    floor(PY_SSIZE_T_MAX / sizeof(PyObject*))

pointers (see listobject.c & Python's heap allocation routines).  So the largest legit index this code can ever see is 1 less than that.  Since pointers are at least 4 bytes on all machines Python runs on, that implies (with room to spare) that

    assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);

can't fail.  Which in turn implies that, mathematically,

    2*ofs + 1 <= PY_SSIZE_T_MAX

So

       if (ofs <= 0)                   /* int overflow */

can't happen, regardless of how the platform C treats signed overflow (signed overflow can't happen to begin with).  The existing `while (ofs < maxofs)` check already ensures that `ofs` is a legit index, and _any_ legit index into a PyObject* vector can be doubled and incremented without overflowing Py_ssize_t.

In fact, that would remain so even if listobject.c allowed its PyObject* vectors to contain twice as many pointers as they actually can contain now.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue35091>
_______________________________________