Confusing reference ownership: how to properly deallocate (via P

ghz 12hours ago ⋅ 1 views

Confusing reference ownership: how to properly deallocate (via Py_DECREF) objects of an object?

I was analysing the following code, which compiles and runs correctly, but generates a memory leak.

The cfiboheap is a C implementation of a Fibonacci Heap and the following code is a Cython wrapper (a part of it) for cfiboheap.

My doubts starts on the insert function. The object data has been created somewhere and passed to the function insert(). Since the function wants to add this object to the fiboheap it increases its reference count. But afterwards? To whom the ownership goes? In my understanding, the C function fh_insertkey() just borrows the ownership. Then it returns a proprietary pointer that needs to be incapsulated, and then returned by insert(). Cool. But my object data and its ref count? By creating the capsule I'm creating a new object, but I'm not decreasing the ref count of data. This produces the memory leak.

(Note that commenting out Py_INCREF or adding Py_DECREF before the return of insert() results in a segmentation fault.)

My questions are:

\1) Why is it necessary to increment the ref count of data during the insert()?

\2) Why is it not necessary to use a Py_DECREF during the extract()?

\3) More generally, how can I exactly keep track of the reference ownership when jumping between C and Python?

\4) How to properly deallocate an object like this FiboHeap? Should I use preventively a Py_XDECREF in __dealloc__() and, if yes, how?

Thanks!

cimport cfiboheap
from cpython.pycapsule cimport PyCapsule_New, PyCapsule_GetPointer
from python_ref cimport Py_INCREF, Py_DECREF 

cdef inline object convert_fibheap_el_to_pycapsule(cfiboheap.fibheap_el* element):
    return PyCapsule_New(element, NULL, NULL)

cdef class FiboHeap:

    def __cinit__(FiboHeap self):
        self.treeptr = cfiboheap.fh_makekeyheap()
        if self.treeptr is NULL:
            raise MemoryError()

    def __dealloc__(FiboHeap self):
        if self.treeptr is not NULL:
            cfiboheap.fh_deleteheap(self.treeptr)

    cpdef object insert(FiboHeap self, double key, object data=None):
        Py_INCREF(data)
        cdef cfiboheap.fibheap_el* retValue = cfiboheap.fh_insertkey(self.treeptr, key, <void*>data)
        if retValue is NULL:
            raise MemoryError()

        return convert_fibheap_el_to_pycapsule(retValue)

    cpdef object extract(FiboHeap self):
        cdef void* ret = cfiboheap.fh_extractmin(self.treeptr)
        if ret is NULL:
            raise IndexError("FiboHeap is empty")

        return <object> ret

    cpdef object decrease_key(FiboHeap self,  object element, double newKey):
        cdef void* ret = cfiboheap.fh_replacekey(self.treeptr, convert_pycapsule_to_fibheap_el(element), newKey)
        if ret is NULL:
            raise IndexError("New Key is Bigger")

        return <object> ret

Note that this hasn't been written by me, but I'm using this example to better understand obj referencing and to stop the leak (since I am actually using the code).

The main code that makes use of FiboHeap (and where the leak happens) looks like this:

cdef dijkstra(Graph G, int start_idx, int end_idx):

    cdef np.ndarray[object, ndim=1] fiboheap_nodes = np.empty([G.num_nodes], dtype=object) # holds all of our FiboHeap Nodes Pointers
    Q = FiboHeap()
    fiboheap_nodes[start_idx] = Q.insert(0, start_idx)
    # Then occasionally:
    Q.insert(...)
    Q.decrease_key(...)
    Q.extract()

    return

extract is not a peek, but a proper pop, so it is deleting the C element in the C fiboheap.

In conclusion: it seems clear that the ref count of data causes a memory leak, but why? And how to stop it?

Answer

In the scenario you're describing, there are several important concepts regarding reference counting and memory management in Cython when dealing with both C and Python objects. Let's break down your concerns and questions step by step to clarify the issue and provide a solution.

1) Why is it necessary to increment the ref count of data during insert()?

The reason you need to increment the reference count of data is that you're passing a Python object (data) to C, where it's being stored in the Fibonacci heap. When you pass data into the C function fh_insertkey(), you are not transferring ownership of the object. Instead, the C function is borrowing it, meaning that the object should not be deleted or garbage-collected while it is still in use by the heap.

In Python, when an object’s reference count reaches zero, the object is deallocated. By calling Py_INCREF(data) before passing it to the C function, you are ensuring that Python knows there is still a reference to the object, preventing it from being garbage-collected prematurely.

2) Why is it not necessary to use a Py_DECREF during the extract()?

In the extract() function, you return a void* pointer that points to the C data structure, but you don't directly deal with the Python object (data) that was inserted into the Fibonacci heap.

When you perform fh_extractmin(), it returns a pointer to the C object inside the heap (which likely contains a reference to data). The C function likely doesn't alter the reference count of the Python object (data) directly when it extracts the object. So, there is no need to call Py_DECREF on the extracted object.

However, in this case, the object is still being referenced in the Fibonacci heap (via the capsule or some other internal structure). The extract() function just removes the C object from the heap and doesn’t handle Python reference counts directly.

If the object is being removed from the heap and is no longer needed by the heap, you might need to explicitly decrease the reference count on the extracted object (i.e., call Py_DECREF), but that depends on the memory management strategy of your C code and whether the data object is still being used elsewhere.

3) More generally, how can I exactly keep track of reference ownership when jumping between C and Python?

This is one of the trickier aspects when working with Cython. Here are some key points to keep in mind:

  • Python object ownership: When a C function receives a Python object, it generally doesn't own the object, unless explicitly stated in the function's documentation. In your case, fh_insertkey likely borrows the object.

  • Memory management in C: When returning a Python object from C (e.g., via PyCapsule_New), the C function typically doesn't increment the reference count of the object that’s encapsulated unless it's intended to "own" that object. If it doesn’t own it, the reference count should not be incremented, and it is up to the caller (in this case, the Cython wrapper) to manage the reference count.

  • Cython and C object conversion: When wrapping C functions that interact with Python objects, you need to be clear about who owns the object at each stage. You are correct that the insert() function should encapsulate the data object in a capsule and ensure that Python’s reference count is correctly managed.

  • When to Py_INCREF and Py_DECREF:

    • Py_INCREF should be used when you're passing an object to C and you're not transferring ownership.
    • Py_DECREF should be used when you know you're no longer using the object and want to allow Python's garbage collector to reclaim it.

4) How to properly deallocate an object like this FiboHeap? Should I use a Py_XDECREF in __dealloc__() and, if yes, how?

When you deallocate a Cython class or object, you typically call __dealloc__() to release resources, including cleaning up any Python references.

In your case, since you're storing Python objects (data) inside C objects (the Fibonacci heap), you'll need to ensure that the reference counts of these objects are properly decremented when the heap is deleted. This should happen in __dealloc__().

  • You need to decrease the reference count of any Python object that was inserted into the heap before deleting the heap itself.

  • Since data is encapsulated in a PyCapsule, you might need to use Py_XDECREF to handle the capsules and decrement their reference counts when the heap is deleted. This ensures that Python’s garbage collector properly handles the memory when the C object is destroyed.

Here's an updated version of your __dealloc__() method that ensures proper reference management:

def __dealloc__(FiboHeap self):
    if self.treeptr is not NULL:
        # Iterate through the heap and decrement ref counts of the encapsulated Python objects.
        cdef cfiboheap.fibheap_el* element = self.treeptr
        while element is not NULL:
            # Assuming the capsule holds a reference to the Python object (`data`)
            cdef object py_object = PyCapsule_GetPointer(element, NULL)
            Py_XDECREF(py_object)  # Decrease ref count of encapsulated Python object
            # Move to the next element in the heap
            element = element.next

        # Now delete the C heap
        cfiboheap.fh_deleteheap(self.treeptr)

In summary:

  • Py_INCREF is necessary when you pass a Python object into C (via the C API), because the C function does not take ownership of the object but may temporarily hold a reference.

  • Py_DECREF is typically not needed in the extract() function, because the heap (C side) doesn't alter the reference count of the Python object directly.

  • Memory management when crossing the C-Python boundary can be tricky. Keep track of ownership by ensuring that:

    • You increment reference counts when passing objects to C, and
    • You decrement reference counts when cleaning up C objects that were holding onto Python objects.

  • Deallocation: Ensure you clean up the Python references properly in __dealloc__() using Py_XDECREF for any encapsulated Python objects (e.g., inside capsules), to avoid memory leaks.

By following these guidelines, you should be able to avoid the memory leak in your Fibonacci heap implementation.

#py