Python extension creates invalid pointers when manipulating large lists

Question

I managed to implement a Fisher–Yates shuffle function for python lists as an exercise for getting used to extending python. It works perfectly for relatively small lists, unless I run the function several times.

Whenever the list size goes over about 100, I get all kinds of memory problems:

>>>import evosutil
>>> a=[i for i in range(100)]
>>> evosutil.shuffle(a)
>>> a
[52, 66, 0, 58, 41, 18, 50, 37, 81, 43, 74, 49, 90, 20, 63, 32, 89, 60, 2, 44, 3, 80, 15, 24, 22, 69, 86, 31, 56, 68, 34, 13, 38, 26, 14, 91, 73, 79, 39, 65, 5, 75, 84, 55, 7, 53, 93, 42, 40, 9, 51, 82, 29, 30, 99, 64, 33, 97, 27, 11, 6, 67, 16, 94, 95, 62, 57, 17, 78, 77, 71, 98, 72, 8, 88, 36, 85, 59, 21, 96, 23, 46, 10, 12, 48, 83, 4, 92, 45, 54, 1, 25, 19, 70, 35, 61, 47, 28, 87, 76]
>>> (Ctrl-D)
*** Error in `python3': free(): invalid next size (fast): 0x083fe680 ***

Or, when trying to operate on a list with 1000 elements:

*** Error in `python3': munmap_chunk(): invalid pointer: 0x083ff0e0 ***

Or,

Segmentation fault (core dumped)

Here's my code for the module that produces the error:

inline void _List_SwapItems(PyObject* list, Py_ssize_t i1, Py_ssize_t i2){
    PyObject* tmp=PyList_GetItem(list, i2);
    PyList_SetItem(list, i2, PyList_GetItem(list, i1));
    PyList_SetItem(list, i1, tmp);
}

//Naive Fisher–Yates shuffle
static PyObject* shuffle(PyObject* self, PyObject* args){
    PyObject* list;
    PyArg_ParseTuple(args,"O", &list);
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::minstd_rand0 rand(seed);
    Py_ssize_t size = PyList_Size(list);
    for(int i=0; i<size;++i){
        int randIndex = rand()%size;
        _List_SwapItems(list, randIndex, i);
    }
    Py_RETURN_NONE;
}

I feel like I should be able to solve this either with free() or with Py_DECREF() somewhere, but I don't see where. I don't think I'm creating any objects, just moving them around. So where is the memory problem coming from?

Answer 1

You need to Py_XINCREF() both objects before passing them to PyList_SetItem(). Further, catch the special case where i1 == i2:

inline void _List_SwapItems(PyObject* list, Py_ssize_t i1, Py_ssize_t i2){
    if (i1 == i2) {
        return;
    }
    PyObject* obj1=PyList_GetItem(list, i1);
    PyObject* obj2=PyList_GetItem(list, i2);
    Py_XINCREF(obj1);
    Py_XINCREF(obj2);
    PyList_SetItem(list, i2, obj1);
    PyList_SetItem(list, i1, obj2);
}

PyList_GetItem() returns a borrowed reference, i.e. it doesn't INCREF the object it returns. If you don't hold any other references, the refcount will be 1 (as it is only referenced from the list). When you call PyList_SetItem(list, i2, ...), the list Py_XDECREF()'s the object previously stored at i2 (which you keep in tmp). At that point, the refcount reaches 0 and the object is freed. Whoops.

Similarly, you can't just call PyList_SetItem(list, i, PyList_GetItem()), because SetItem steals the reference you pass to it. You don't own the reference, however, the 'old' list does. So you need an Py_XINCREF here as well.

See the list API documentation for more details.

As a further suggestion, you might consider not programming directly against the Python extension API. It takes a lot of code to get anything done and it's subtly difficult to keep the refcounts correct. By now, there are multiple other ways to interface Python with C or C++. CFFI seems to be the low-level interface the Python ecosystem will standardize on. SIP and SWIG may offer better support for C++, though. For a SIP example, see this answer.

Answer 2

There are more problems in your extension function beyond the reference counting errors, more of them below:

---

While the PyList_SetItem with proper reference counting is the preferred way, an (ugly) option is to use the PyList_SET_ITEM macro that gets away with doing INCREFs:

void PyList_SET_ITEM(PyObject *list, Py_ssize_t i, PyObject *o)

Macro form of PyList_SetItem() without error checking. This is normally only used to fill in new lists where there is no previous content.

Note

This macro “steals” a reference to item, and, unlike PyList_SetItem(), does not discard a reference to any item that is being replaced; any reference in list at position i will be leaked.

Thus the PyList_SET_ITEM neither increments nor decrements any reference counters, which is suitable for us since both initially and finally the elements are in the same list.

inline void _List_SwapItems(PyObject* list, Py_ssize_t i1, Py_ssize_t i2){
    PyObject* tmp = PyList_GET_ITEM(list, i2);
    PyList_SET_ITEM(list, i2, PyList_GET_ITEM(list, i1));
    PyList_SET_ITEM(list, i1, tmp);
}

Notice that this does not do any error checking at all, so you need to ensure that your index is within the bounds (which the for loop takes care of).

---

Your code has another bad problem that is not discussed yet - total lack of error checking. For example, when passed in a non-list object, you ought to raise a TypeError. Now the code will fail at PyList_Size, returning -1 and setting an internal exception, this can lead to erroneous behaviour of all future C extensions:

Likewise PyArg_ParseTuple can and will fail if incorrect number of arguments is passed in, thus you must check its return value; in this case the list can be uninitialized and your code will have totally undefined behaviour.

The C-API documentation states the following:

When a function must fail because some function it called failed, it generally doesn’t set the error indicator; the function it called already set it. It is responsible for either handling the error and clearing the exception or returning after cleaning up any resources it holds (such as object references or memory allocations); it should not continue normally if it is not prepared to handle the error. If returning due to an error, it is important to indicate to the caller that an error has been set. If the error is not handled or carefully propagated, additional calls into the Python/C API may not behave as intended and may fail in mysterious ways.

Thus here is the correct way to write your extension function:

static PyObject* shuffle(PyObject* self, PyObject* args){
    PyObject* list;
    if (! PyArg_ParseTuple(args, "O", &list)) {
        // PyArg_ParseTuple set the proper exception
        return NULL;
    }

    if (! PyList_Check(list)) {
        PyErr_SetString(PyExc_TypeError,
            "bad argument to shuffle; list expected");
        return NULL;
    }

    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::minstd_rand0 rand(seed);

    Py_ssize_t size = PyList_Size(list);
    for(int i=0; i<size;++i){
        int randIndex = rand()%size;
        _List_SwapItems(list, randIndex, i);
    }
    Py_RETURN_NONE;
}