PyLongObject内存泄漏

Question

我的encode方法中存在内存泄漏

static const size_t _bits_per_digit = sizeof(digit) * CHAR_BIT;

/**
 * Returns a Python int storing the bitstream of the Elias gamma encoded input list.
 */
static PyObject *
encode(PyObject *self, PyObject *obj)
{
    if (!PyList_Check(obj)) {
        PyErr_SetString(PyExc_TypeError, "Input to encode must be a list");
        return NULL;
    }

    const Py_ssize_t list_length = PyList_GET_SIZE(obj);
    size_t size = _ceil_div((size_t) PyList_GET_SIZE(obj), _bits_per_digit);

    size_t current_digit = 0;
    size_t current_bit = 0;

    PyLongObject *bstream = _PyLong_New(size);
    if (bstream == NULL) {
        return NULL; // _PyLong_New sets errors
    }

    for (Py_ssize_t i = 0; i < list_length; i++)
    {
        PyObject *item = PyList_GET_ITEM(obj, i);
        unsigned long number = PyLong_AsUnsignedLong(item);
        if (PyErr_Occurred()) { // number overflowed or was negative
            PyErr_Format(PyExc_ValueError, "Number at list index %zd was negative or too large", i);
            return NULL;
        } else if (number == 0) { // unencodable
            PyErr_Format(PyExc_ValueError, "Zero at list index %zd", i);
            return NULL;
        }
        size_t N = _fast_floor_log2(number);
        size_t required_size = _ceil_div(current_digit * _bits_per_digit + current_bit + N * 2 + 1 + list_length - i - 1, _bits_per_digit);
        if (size < required_size) {
            size = required_size;
            PyLongObject *new = (PyLongObject *) PyObject_Realloc(bstream, offsetof(PyLongObject, ob_digit) + size * _bits_per_digit);
            if(new == NULL) {
                PyObject_Free(bstream);
                return PyErr_NoMemory();
            }
            bstream = new;
            PyObject_InitVar((PyVarObject*)bstream, &PyLong_Type, size);
        }
        // write leading zeroes
        size_t zeroes_left = N;
        while (zeroes_left > 0) {
            if (PyErr_CheckSignals()) {
                return NULL;
            }
            if (current_bit == 0) {
                bstream->ob_digit[current_digit] = (digit) 0;
                if (zeroes_left > _bits_per_digit) {
                    zeroes_left -= _bits_per_digit;
                    ++current_digit;
                } else {
                    current_bit += zeroes_left;
                    if (current_bit == _bits_per_digit) {
                        current_bit = 0;
                        ++current_digit;
                    }
                    zeroes_left = 0;
                }
            } else {
                digit mask = ~((digit)-1 >> current_bit); // enable the current_bit most significant bits
                bstream->ob_digit[current_digit] &= mask; // set remainder of this digit to zeroes
                digit zeroes_written = _bits_per_digit - current_bit;
                if (zeroes_left > zeroes_written) {
                    zeroes_left -= zeroes_written;
                    current_bit = 0;
                    ++current_digit;
                } else {
                    current_bit += zeroes_left;
                    if (current_bit == _bits_per_digit) {
                        current_bit = 0;
                        ++current_digit;
                    }
                    zeroes_left = 0;
                }
            }
        }
        // write the binary representation of number
        size_t bits_left = N + 1;
        while (bits_left > 0) {
            if (PyErr_CheckSignals()) {
                return NULL;
            }
            unsigned long mask = 1UL << (bits_left - 1);
            if (number & mask) {
                bstream->ob_digit[current_digit] |= ~((digit) -1 >> 1) >> current_bit;
            } else {
                bstream->ob_digit[current_digit] &= ~(~((digit) -1 >> 1) >> current_bit);
            }
            ++current_bit;
            if (current_bit == _bits_per_digit) {
                current_bit = 0;
                ++current_digit;
            }
            --bits_left;
            mask >>= 1;
        }
    }

    // remove unused digits
    if ((size - current_digit) > 1) {
        size = current_digit + 1;
        PyLongObject *new = (PyLongObject *) PyObject_Realloc(bstream, offsetof(PyLongObject, ob_digit) + size * _bits_per_digit);
        if(new == NULL) {
            PyObject_Free(bstream);
            return PyErr_NoMemory();
        }
        bstream = new;
        PyObject_InitVar((PyVarObject*)bstream, &PyLong_Type, size);
    }

    // fill leftover with zeroes, overwrite malloc randomness
    digit mask = ~((digit) -1 >> current_bit);
    bstream->ob_digit[current_digit] &= mask;

    return (PyObject *) bstream;
}

用Python

tracemalloc.start()
encoded = encode(numbers)
sleep(3) # give garbage collection time to run
size, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
print("size, peak", size, peak)
print(sys.getsizeof(encoded))

印刷品

size, peak 17053496 17053496
2131708

而不是预期的

size, peak 2131708 ...
2131708

---

使用我自己的类型而不是PyLongObject，它看起来和我的眼睛一样，完全不会导致内存泄漏和输出

size, peak 2131309 2131309
2131309

这是具有该输出的类型

typedef struct {
    PyObject_VAR_HEAD
    uint8_t data[1];
} BitStream;

static PyTypeObject BitStreamType = {
    PyVarObject_HEAD_INIT(NULL, 0)
    .tp_name = "elias_gamma_code.BitStream",
    .tp_dealloc = 0,
    .tp_free = PyObject_Del,
    .tp_basicsize = offsetof(BitStream, data),
    .tp_itemsize = sizeof(uint8_t),
    .tp_flags = Py_TPFLAGS_DEFAULT,
};

因此，使用PyLongObject有一些特别之处，特别是它会导致大量内存使用

我猜是因为PyObject_Realloc，所以我在这里问：Use PyObject_Realloc correctly

但显然

if a non-null pointer was returned, then obj was already freed

事实上，使用PyObject_Free(previous_obj)会导致pointer being freed was not allocatedmalloc错误

---

Elias gamma编码将非零正二进制整数表示为N个前导零，N是数字-1的位长度（与floor（log2（num））相同），后跟数字本身

+--------+---------------+
| Number |  γ encoding   |
+--------+---------------+
|      1 |             1 |
|      2 |          0 10 |
|      3 |          0 11 |
|      4 |        00 100 |
|      5 |        00 101 |
|    ... |               |
|     15 |      000 1111 |
|     16 |   0000 1 0000 |
|    ... |               |
|     31 |   0000 1 1111 |
|     32 | 00000 10 0000 |

列表中的所有数字都可以这样编码和连接。生成的比特流可以毫不含糊地解码到原始列表

Answer 1

在错误路径中，给定

PyLongObject *bstream = _PyLong_New(size);

你必须减少对它的引用。但您没有这样做，例如：

if (PyErr_Occurred()) { // number overflowed or was negative
    PyErr_Format(PyExc_ValueError, "Number at list index %zd was negative or too large", i);
    return NULL;
} else if (number == 0) { // unencodable
    PyErr_Format(PyExc_ValueError, "Zero at list index %zd", i);
    return NULL;
}

正确的C习惯用法是goto到错误处理标签：

    PyLongObject *bstream = NULL;

    if (!(bstream = _PyLong_New(size))) {
        goto error;
    }

    if (! some other check) {
        goto error;
    }
    
    ...
    return bstream;

error:
    // xdecref requires that the pointer is initialized in all
    // code paths, either to null or pointing to a valid live PyObject 

    Py_XDECREF(bstream);
    return NULL;
}

---

另一个问题是，在Python中是否允许realloc一个长对象。。。将来它可能会崩溃

---

最后这个看起来有点奇怪：

size * _bits_per_digit

PyObject_Realloc将新大小设为字节，那么为什么要将每个数字乘以位——而必须乘以数字类型的宽度（sizeof）