Setting pointers to nil to prevent memory leak in Golang

Question

I'm learning Go, and as an exercise I wanted to implement a linked list. For reference I looked at the official Go code (https://golang.org/src/container/list/list.go) . One thing that stuck with me are these lines:

   108  // remove removes e from its list, decrements l.len, and returns e.
   109  func (l *List) remove(e *Element) *Element {
   110      e.prev.next = e.next
   111      e.next.prev = e.prev
   112      e.next = nil // avoid memory leaks
   113      e.prev = nil // avoid memory leaks
   114      e.list = nil
   115      l.len--
   116      return e
   117  } 

I am curious as to how does setting pointers to nil in this case prevent memory leaks? If possible I would like to construct a program which has this flaw and see it while profiling with pprof (I would use a modified verion of the list.go without this nil pointer setting).

---

For clarity of answer: If one of the nodes has an external pointer to it, then all of the adjacent removed nodes will have an active reference through that pointer and won't be removed.

1. We create an external pointer pointing to Node2
2. We remove nodes 2-4 from the list
3. You would expect at this point only for the Node 1,2 & 5 to be alive and the rest to be GC-ed. However, due to Node2 still pointing to Node3 & etc., the entire chain remains uncollected.

Campagna

Answer 1

Your assumptions are correct. If there is a group of pointers pointing to each other, but there is no reference / pointer to any member of this group, the group will be detected as unreachable by the garbage collector and will be freed properly.

But the explanation to memory leak is simple. We can get the list.Element wrappers from the list which contain the unexported Element.next and Element.prev pointers to the next and previous elements in the list.

When removing an element from the list if these pointers would not be set to nil, they would held references to the next and previous element wrappers, including the values associated with those elements.

See this example:

var e2 *list.Element

func main() {
    listTest()
    fmt.Println(e2.Value)
    // At this point we expect everything from the list to be
    // garbage collected at any time, we only have reference to e2.
    // If e2.prev and e2.next would not be set to nil,
    // e1 and e3 could not be freed!
}

func listTest() {
    l := list.New()
    e1 := l.PushBack(1)
    e2 = l.PushBack(2)
    e3 := l.PushBack(3)
    // List is now [1, 2, 3]
    fmt.Println(e1.Value, e2.Value, e3.Value)
    l.Remove(e2)
    // Now list is [1, 3], it does not contain e2
}

In listTest() we build a list with 3 elements, and we store the 2nd element in a global variable e2. Then we remove this element. Now we would expect that except e2 (and the value wrapped in it) everything else gets garbage collected when listTest() returns, because the list is not accessible outside the listTest() function. Yes, we have a pointer in e2 to an element, but e2 has (should have) nothing to do with the list anymore as we removed it.

If the prev and next pointers in e2 would not be set to nil, values wrapped in elements pointed by them could never be freed, recursively. But since List.Remove() properly sets those to nil, in the above example e1 and e3 –along with the values wrapped in them– will be freed (on next garbage collection run).

Sybilla

I ammended the question with the picture of what you are describing, please correct me if I am wrong. I actually tried this out with a modified (with the memory leak bug) version of list and I can see it not releasing the memory. – Campagna

Answer 2

Golang garbage collector is based on the tri-color mark-and-sweep algorithm. In short, every memory you're program use is associated to a color. The color determine if the memory shall be garbaged or not.

This algorithm will flag a memory to be freed if this memory is not referenced somewhere (directly and indirectly). But if we take a look at the code:

e.prev.next = e.next
e.next.prev = e.prev

This copy the pointer in e.next into e.prev.next. Now, let's say you want to update e.prev.next by a new fully created element.

The previously removed element won't be garbaged because it is still referenced by e.next.

This is why those lines exist:

e.next = nil // avoid memory leaks
e.prev = nil // avoid memory leaks

This prevent from leaving old references, and thus prevent from memory leaks.

Koziol

I've added a comment above explaining what I believe happens. I'm not sure what you mean by "removed element is still referenced by e.next", isn't e the removed element? – Campagna