Расширение Python создает недопустимые указатели при манипулировании большими списками

Question

Мне удалось реализовать функцию Shuffle для Fisher-Yates для списков python в качестве упражнения для привыкания к расширению python. Он отлично работает для относительно небольших списков, если я не запускаю функцию несколько раз.

Всякий раз, когда размер списка переходит около 100, я получаю все виды проблем с памятью:

>>>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 *** 

Или, при попытке работать в списке 1000 элементов:

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

Или,

Segmentation fault (core dumped) 

Вот мой код модуля, который производит ошибку:

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; 
} 

Мне кажется, что я смогу решить это либо с помощью free(), либо с помощью Py_DECREF(), но я не вижу, где. Я не думаю, что создаю какие-то объекты, просто перемещая их. Так где же проблема памяти?

Answer 1

Перед тем как передать их до PyList_SetItem(), вам необходимо связаться с Py_XINCREF(). Кроме того, поймать особый случай, когда 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() возвращает ссылку заимствованную, т.е. он не INCREF объект возвращается. Если вы не держите другие ссылки, refcount будет 1 (так как он ссылается только на список). Когда вы вызываете PyList_SetItem(list, i2, ...), список Py_XDECREF() - объект, ранее сохраненный в i2 (который вы храните в tmp). В этот момент пересчет достигает 0, и объект освобождается. Упс.

Аналогичным образом вы не можете просто позвонить PyList_SetItem(list, i, PyList_GetItem()), потому что SetItem крадет ссылку, которую вы передаете. Вы не владеете ссылкой, однако, это «старый» список. Поэтому вам также нужен Py_XINCREF.

Для получения более подробной информации см. list API documentation.

В качестве дополнительного предложения вы можете подумать о том, чтобы не программировать прямо против API расширения Python. Для получения чего-либо требуется много кода, и было бы сложно сохранить правильность пересчетов. К настоящему времени существует несколько других способов взаимодействия Python с C или C++. CFFI, похоже, является интерфейсом низкого уровня, на котором стандартизируется экосистема Python. SIP и SWIG могут предложить лучшую поддержку для C++. Пример SIP см. В разделе this answer.

Answer 2

Есть больше проблем в вашей функции расширения за ошибки подсчета ссылок на более из них ниже:

---

Хотя PyList_SetItem с правильным подсчетом ссылок является предпочтительным способом, ап (некрасиво) вариант заключается в использовании PyList_SET_ITEM макрос, который сходит с рук делают 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.

Таким образом PyList_SET_ITEM ни приращения, ни декрементирует любые ссылочные счетчики, которая подходит для нас, так как первоначально и наконец, элементы находятся в одном списке.

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); 
} 

Обратите внимание, что это не производит никакой проверки ошибок на всех, так что вы должны убедиться, что ваш индекс находится в пределах границ (что петля for заботится о).

---

У вашего кода есть еще одна плохая проблема, которая еще не обсуждается - полное отсутствие проверки ошибок. Например, при передаче в объекте, не являющемся списком, вы должны поднять TypeError. Теперь код потерпит неудачу в PyList_Size, возвращая -1 и установив внутреннее исключение, это может привести к ошибочному поведению всех будущих расширений C:

Аналогично PyArg_ParseTuple может и потерпят неудачу, если неправильное количество аргументов передаются в, таким образом, вы должны проверить его возвращаемое значение; в этом случае list может быть неинициализирован, и ваш код будет полностью неопределенным.

Документация C-API 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.

Так вот правильный способ написать функцию расширения:

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; 
}