Настройка указателей на нуль для предотвращения утечки памяти в Golang

Question

Я учусь Go, и в качестве упражнения я хотел реализовать связанный список. Для справки я посмотрел официальный код Go (https://golang.org/src/container/list/list.go). Одна вещь, которая застряла со мной эти строки:

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 } 

Я любопытно, как же установка указателей на ноль в этом случае предотвратить утечку памяти? Если возможно, я хотел бы построить программу, которая имеет этот недостаток и увидеть ее во время профилирования с помощью pprof (я бы использовал модифицированный вариант list.go без этой установки указателя nil).

---

Для ясности ответа: Если один из узлов имеет внешний указатель на него, а затем все соседние узлы удалены будут иметь активную ссылку через этот указатель и не будут удалены.

1. Мы создаем внешний указатель, указывающий на Node2
2. Снимают узлы 2-4 из списка
3. Вы ожидали бы в этот момент только для узла 1,2 & 5, чтобы быть живыми а остальные - GC-ed. Однако из-за Node2 все еще , указывая на Node3 & и т. Д., Вся цепочка остается неповрежденной.

Answer 1

Ваши предположения верны. Если есть группа указателей, указывающих друг на друга, но нет ссылки/указателя на любой член этой группы, группа будет обнаружена как недосягаемая сборщиком мусора и будет освобождена должным образом.

Но объяснение утечки памяти прост. Мы можем получить обертки list.Element из списка, которые содержат указатели Element.next и Element.prev на следующий и предыдущие элементы в списке.

При удалении элемента из списка, если эти указатели не будут установлены в nil, они будут содержать ссылки на следующие и предыдущие обертки элементов, включая значения, связанные с этими элементами.

Смотрите этот пример:

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 
} 

В listTest() мы строим список с 3-х элементов, и мы сохраняем 2-го элемента в глобальной переменной e2. Затем мы удалим этот элемент. Теперь мы ожидаем, что за исключением e2 (и значения, завернутого в него) все остальное получает сбор мусора, когда возвращается listTest(), потому что список недоступен вне функции listTest(). Да, у нас есть указатель в e2 на элемент, но e2 имеет (должен иметь) больше ничего общего с этим списком, поскольку мы его удалили.

Если prev и next указателей в e2 не будут установлены nil значение, завернутое в элементах указывали на них никогда не может быть освобождено, рекурсивно. Но так как List.Remove() правильно устанавливает их на nil, в приведенном выше примере e1 и e3 - со значениями, завернутыми в них, будут освобождены (при следующем запуске коллекции мусора).

Answer 2

Сборщик мусора Golang основан на трехцветном алгоритме маркировки и развертки. Короче говоря, каждая используемая вами память связана с цветом. Цвет определяет, должна ли память быть мусорной или нет.

Этот алгоритм будет отмечать освобождаемую память, если эта память не упоминается где-то (прямо и косвенно). Но если мы посмотрим на код:

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

Эта копия указатель в E.NEXT в e.prev.next. Предположим, вы хотите обновить e.prev.next новым полностью созданным элементом.

Ранее удаленный элемент не будет мусором, поскольку он по-прежнему ссылается на e.next.

Вот почему существуют эти строки:

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

Это предотвратить оставляя старые ссылки, и, таким образом, предотвратить утечки памяти.