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

Я изучаю 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).

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

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

Ответы

Ответ 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 - со значениями, они будут освобождены (при следующем запуске коллекции мусора).

Ответ 2

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

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

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

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