Memory leak with linked lists

[Jon_D]

Hello,

My original Fortran code runs for a while and eventually crashes with an "insufficient virtual memory" error. I am using the latest Intel Fortran compiler under Windows OS. Process Explorer indeed shows the Private Bytes increasing over the course of the execution. After some investigation, I believe the issue arises from repeated creation and deletion of linked lists. 

Below is a simpler code that demonstrates the issue. The idea is to create a linked list that stores 50000 double precision values, then delete the linked list, and repeat the process for 30000 times (list nodes in my original code are more complex with larger memory footprint, so it doesn't take 30000 iterations to run into memory problems) . This program starts with 12.5 MB Private Bytes and ends up with 18.2 MB, a 50% increase in memory (according to both Process Explorer and Memory Usage diagnostic tool built into Visual Studio).

I cannot find what I might be doing wrong, particularly in deleting the linked list, that might be causing a memory leak. I would really appreciate any help with this. 

Thanks in advance,

Jon

module class_GenericLinkedList
    implicit none
    
    private
    public :: GenericLinkedListType
    
    type LLNodeType
        class(*),allocatable     :: Value
        type(LLNodeType),pointer :: pNext => null()
    end type LLNodeType
    
    type GenericLinkedListType
        private
        integer                  :: iNNodes  = 0
        type(LLNodeType),pointer :: pHead    => null()
        type(LLNodeType),pointer :: pTail    => null()
    contains
        procedure,non_overridable,pass :: AddNode
        procedure,non_overridable,pass :: DeleteList
    end type GenericLinkedListType
    
contains
    
    subroutine AddNode(List,value)
        class(GenericLinkedListType),intent(inout) :: List
        class(*),intent(in)                        :: value
        
        if (List%iNNodes .eq. 0) then
            allocate (List%pHead)
            allocate (List%pHead%Value , source=value)
            List%pTail => List%pHead
        else
            allocate (List%pTail%pNext)
            allocate (List%pTail%pNext%Value , source=value)
            List%pTail => List%pTail%pNext
        end if
        
        List%iNNodes = List%iNNodes + 1
        
    end subroutine AddNode
    
    
    subroutine DeleteList(List)
        class(GenericLinkedListType),target,intent(inout) :: List
        
        integer                  :: indx
        type(LLNodeType),pointer :: pNext
        
        do indx=1,List%iNNodes-1
            pNext => List%pHead%pNext
            deallocate (List%pHead%value)
            nullify(List%pHead%pNext)
            deallocate (List%pHead)
            List%pHead => pNext
        end do
        deallocate (List%pHead%value)
        nullify(List%pHead%pNext)
        nullify(List%pTail)
        
        List%iNNodes = 0
        
    end subroutine DeleteList
    
end module class_GenericLinkedList    
    
    
!Private Bytes start at 12.5 MB and ends at 18.1 MB
program main
    use class_GenericLinkedList
    implicit none
   
    type,extends(GenericLinkedListType) :: Real8ListType
    end type Real8ListType        
    type(Real8ListType) :: MyList
    integer :: indx1,indx
    
    !Loop to test memory management 
    do indx1=1,30000
        !Create list
        do indx=1,50000
            call MyList%AddNode(REAL(indx,8))
        end do
        
        !Delete list
        call MyList%DeleteList()
        
        write (*,*) indx1
    end do    
   
end program main

[IanH · Accepted solution]

You never deallocate the last head node - the thing associated with List%pHead at line 57.

To illustrate another way - consider the case when you call MyList%AddNode once, then call MyList%DeleteList.  Two ALLOCATES called during list creation (lines 29 and 30), during list deletion the loop at line 49 doesn't iterate at all, only one DEALLOCATE called (line 56), uh oh.

~~~

Note that you can just use assignment to set the value component (i.e List%pHead%Value = value), rather than sourced allocation; because the Value component is allocatable it gets automatically deallocated when its containing node gets deallocated; and more typical implementation of DeleteList would walk the list while the various pointers were associated, rather than iterating by index.

...
  do while (associated(List%pHead))
    pNext => List%pHead%pNext
    deallocate (List%pHead)
    List%pHead => pNext
  end do