Memory leak in pointer

Masrul · ‎01-25-2016

Dear All:

I am trying to understand using pointer locally in fortran subroutine. That's why i wrote a simple code, where subroutine is called several times, to find out list of odd numbers from a given rang. Basically i used a linked list to save odd numbers and then copied linked list to output of subroutine(I know there are a lot of ways to do this job but that is not concern right now, rather i would like to understand memory leak issue). My code contains some memory leak issues. Would somebody help to figure out the problem?.

program pointer_test
    implicit none
    integer,allocatable::odd_list(:)
    integer::i
    call find_odd(odd_list,1,23)
    print*,'Odd list after first call',odd_list
    call find_odd(odd_list,5,17)
    print*,'Odd list after second call',odd_list
    call find_odd(odd_list,6,19)
    print*,'Odd list after third call',odd_list
    contains

    subroutine find_odd(odd_list,low_bound,high_bound)
        implicit none
        integer,allocatable,intent(out)::odd_list(:)
        integer,intent(in)::low_bound,high_bound
        integer::count,index,i
        type node
            integer:: info
            type(node),pointer::next
        end type node

        type(node),pointer::head,current,temp

        if (associated(head))nullify(head)
        if (associated(current))nullify(current)
        if (associated(temp))nullify(temp)

        do i=low_bound,high_bound
            if (mod(i,2) .ne. 0) then
                if (.not. associated(head))then
                    allocate(head)
                    head%info=i
                    nullify(head%next)
                    current=>head
                else
                    allocate(current%next)
                    current%next%info=i
                    nullify(current%next%next)
                    current=>current%next
                end if
            end if
        end do

        temp=>head
        count=0
        do while(associated(temp))
            count=count+1
            temp=>temp%next
        end do

        allocate(odd_list(count))

        nullify(temp)
        temp=>head
        index=0
        do while(associated(temp))
            index=index+1
            odd_list(index)=temp%info
            temp=>temp%next
        end do


    end
end

Regards

Masrul

JVanB · ‎01-25-2016

Your code is mostly OK for a crude linked list. The only two real bugs are at the start of subroutine find_odd, you are using the ASSOCIATED intrinsic on pointers whose association status is undefined. What you should have done is to unconditionally set their association statuses via:

nullify(head, current, temp)

The second bug is that you didn't explicitly deallocate your linked list. Now, there's a nifty way to do this automatically using finalizers, but that may be a bit fancy for today's exercise. Just put another loop at the end that steps through your linked list and wipes it out. Something like:

temp => head
do while(associated(temp))
   temp => temp%next
   deallocate(head)
   head => temp
end do

Masrul · ‎01-26-2016

Dear Repeat,

Thanks a lot. Actually, i could superficially guess that i was doing these two mistakes, but could not figure out how to resolve it. I have little confusion about child pointer of each node that locates locally in subroutine of fortran, and subroutine will be called multiple times. Then which of following is correct form of declaration:

Option 1:

type node
    integer:: info
    type(node),pointer::next
end type node

Option 2:

type node
    integer:: info
    type(node),pointer::next=>null()
end type node

Another question, If a child pointer is pointing something, What would be its status if i nullify/deallocate its parent pointer.

Regards

Masrul

JVanB · ‎01-26-2016

Option 2 above would have simplified your code quite a bit because you would not have had to nullify the next component of each node when you allocated it.

Nullifying a pointer changes the pointer association status of that pointer but has no effect on its target. Hopefully by the time you nullify a pointer its target has been already deallocated or another pointer has been pointed at it because if there is no longer any way to access a target it will just be taking up memory uselessly, causing a memory leak as you saw in Quote #1.

Deallocating a pointer actually causes its target to be deallocated, but if that target has any pointer components no action is taken on their targets, sort of like the situation that would occur if such pointer components were nullified. If you want pointer components to be also deallocated, the thing to do is to create a user-defined type to hold such pointer components and give that user-defined type a finalizer that does the deallocation. You have to do this in Fortran but not in C because Fortran doesn't have the rich syntax C does for describing what you mean when you refer to a pointer (&p = address where the pointer's value is stored; p = the address the pointer points at; *p = the data at the address the pointer points at.)

Since in real life you almost always want linked lists and related data structures to have this extra level of indirection because the alternative is to add more special cases each time a node is touched, I will show what your code might look like with this change.

module NodeDefn
   implicit none
! Type to contain a pointer to a node
   type nodePtr
      type(node), pointer :: ptr => NULL()
      contains
         final :: nodePtrFinalizer
   end type nodePtr
   type node
      integer :: info
      type(nodePtr) :: next
   end type node
   contains
      subroutine NodePtrFinalizer(x)
         type(nodePtr) x
         if(associated(x%ptr)) deallocate(x%ptr)
      end subroutine NodePtrFinalizer
end module NodeDefn

program pointer_test
    implicit none
    integer,allocatable::odd_list(:)
    integer::i
    call find_odd(odd_list,1,23)
    print*,'Odd list after first call',odd_list
    call find_odd(odd_list,5,17)
    print*,'Odd list after second call',odd_list
    call find_odd(odd_list,6,19)
    print*,'Odd list after third call',odd_list
    contains

    subroutine find_odd(odd_list,low_bound,high_bound)
        use NodeDefn
        implicit none
        integer,allocatable,intent(out)::odd_list(:)
        integer,intent(in)::low_bound,high_bound
        integer::count,index,i
        type(nodePtr)::temp
        type(nodePtr), target :: head
        type(nodePtr), pointer :: current

        current => head
        do i=low_bound,high_bound
            if (mod(i,2) .ne. 0) then
                allocate(current%ptr)
                current%ptr%info = i
                current => current%ptr%next
            end if
        end do

        temp = head
        count=0
        do while(associated(temp%ptr))
            count=count+1
            temp = temp%ptr%next
        end do

        allocate(odd_list(count))

        temp = head
        index=0
        do while(associated(temp%ptr))
            index=index+1
            odd_list(index)=temp%ptr%info
            temp = temp%ptr%next
        end do

    end
end

When subroutine find_odd returns, local variables temp and head, since they aren't pointers, will be finalized as they go out of scope. Since temp has been left dissociated, the finalizer won't do anything to it, but head still has a pointer to the start of the linked list so the finalizer will take action and deallocate the target of head%ptr. Deallocation will cause the target of head%ptr to go out of scope, and it has a component head&ptr%next that has a finalizer ... and so it goes.

The way the linked list is set up you have to be careful if you remove a node because if you don't nullify its next%ptr before deallocating the node, it will wipe out everything below it in the linked list!

The above code looks correct to me and compiled and ran OK with gfortran, but dies for some reason in ifort. Is that due to a problem with my code or with ifort?

Masrul · ‎01-26-2016

Hi Repeat,

I tried to compile with gfortran and encountered following error,

  type nodePtr
               1
Error: Finalization at (1) is not yet implemented

And i tried with ifort, it compiled fine but ended up getting segmentation fault. I can not make comment on your code, still i am newbie to using pointer in fortran :)

--Masrul

JVanB · ‎01-26-2016

Your problem with gfortran is that you have an old version and should upgrade. My example worked on gfortran 5.2.0.

I am using ifort 16.0.0.110 Build 20150815 and get the segfault. What version of ifort are you using?

Masrul · ‎01-26-2016

Hi,

I tried couple of versions in our HPC;

1)ifort v 11.1 => compilation error

2) ifort v 13.1.0 => compilation error

3) ifort v15.0.2 => compilation is fine but segmentation fault

and pgfortran v 10.3=> compilation error

--Masrul

JVanB · ‎01-26-2016

OK, I found the problem with my program. It seems that finalizers for linked lists are more dangerous than I though. The line

temp = temp%ptr%next

is bad because it causes evaluation of the expression temp%ptr%next, then finalization of temp, then assignment of the value of that expression into temp, but by this time temp, hence the whole linked list, has already been finalized. I have code that will now work on both gfortran and ifort.

module NodeDefn
   implicit none
! Type to contain a pointer to a node
   type nodePtr
      type(node), pointer :: ptr => NULL()
      contains
         final :: nodePtrFinalizer
   end type nodePtr
   type node
      integer :: info
      type(nodePtr) :: next
   end type node
   contains
      subroutine NodePtrFinalizer(x)
         type(nodePtr) x
         if(associated(x%ptr)) deallocate(x%ptr)
      end subroutine NodePtrFinalizer
end module NodeDefn

program pointer_test
    implicit none
    integer,allocatable::odd_list(:)
    integer::i
    call find_odd(odd_list,1,23)
    print*,'Odd list after first call',odd_list
    call find_odd(odd_list,5,17)
    print*,'Odd list after second call',odd_list
    call find_odd(odd_list,6,19)
    print*,'Odd list after third call',odd_list
    contains

    subroutine find_odd(odd_list,low_bound,high_bound)
        use NodeDefn
        implicit none
        integer,allocatable,intent(out)::odd_list(:)
        integer,intent(in)::low_bound,high_bound
        integer::count,index,i
        type(nodePtr), target :: head
        type(nodePtr), pointer :: current

        current => head
        do i=low_bound,high_bound
            if (mod(i,2) .ne. 0) then
                allocate(current%ptr)
                current%ptr%info = i
                current => current%ptr%next
            end if
        end do

        current => head
        count=0
        do while(associated(current%ptr))
            count=count+1
            current => current%ptr%next
        end do

        allocate(odd_list(count))

        current => head
        index=0
        do while(associated(current%ptr))
            index=index+1
            odd_list(index)=current%ptr%info
            current => current%ptr%next
        end do

    end
end

Is there an idiom that allows automatic finalization of a linked list but is not as dangerous as this?

Masrul · ‎01-26-2016

Thanks a lot again. I do not know such idiom

--Masrul

Cristian_P_ · ‎01-27-2016

Masrul, to further explain RepeatOffender's rejection of his first code, default assignment temp = expression first causes temp to be finalized, and then re-assigned (F2003 convention). The process of finalization destroyed the list, invalidating subsequent operations on it. To understand how the finalization happens, please decorate RepeatOffender's final subroutine as follows:

subroutine NodePtrFinalizer(x)
       type(nodePtr) x

       integer, save :: count = 0
       if(associated(x%ptr)) then
            count = count + 1
            print "('I am deallocating ', i4, '''th time.')", count
            deallocate(x%ptr)
       end if
end subroutine NodePtrFinalizer

Use also the version:

subroutine NodePtrFinalizer(x)
       type(nodePtr) x

       integer, save :: count = 0
       if(associated(x%ptr)) then
            count = count + 1
            deallocate(x%ptr)
            print "('I am deallocating ', i4, '''th time.')", count
       end if
end subroutine NodePtrFinalizer

and try to understand why the numbers are displayed in reverse order in the second version.

Cristian_P_ · ‎01-27-2016

RepeatOffender, after some Googling around, I found out that F2008 addresses the nuisances of such lists by allowing "Allocatable components of recursive type" (see Section 5.3 in ftp://ftp.nag.co.uk/sc22wg5/n1801-n1850/n1828.pdf). I tried to modify your code, but ifort 16.0.0 says "error #8541: Not yet implemented: type containing ALLOCATABLE field of same type. Use POINTER instead." The code is much tinnier though, always a good sign.

JVanB · ‎01-27-2016

I am not sure that allocatable components of recursive type solves the more interesting problem of data structure where you might want to delete some stuff in the middle or just remap the connectivity as in an RB tree. If that proves to be the case then Fortran code will still profit from the idiom of pointers wrapped in structures like type(nodePtr) in Quote #8 above. I suppose ASSIGNMENT(=) for type(nodePtr) could have been overridden with a subroutine that just performed a shallow copy without finalization. That way typing "=" instead of "=>" would not lead to potentially difficult to debug failures.