news.shamcode.ru | Go: сборщик мусора там, где его не ждут

Всем привет! Меня зовут Нина Пакшина, и я уже 5 лет пишу на Go.

Пару лет назад я готовилась к докладу и глубоко изучала исходники runtime Go. Там я наткнулась на очень интересный код.

На время я о нём забыла, но сейчас наконец смогла погрузиться. Теперь я хочу поделиться этим с вами, чтобы мы стали понимать Go чуточку глубже.

Когда мы говорим о сборщике мусора, то сразу думаем о куче. Зачем сборщик мусора нужен в стеке? Переменная попала на стек, функция завершила исполнение — стек вжух! — и очистился.

Но оказывается на стеке Go тоже есть свой мини-сборщик мусора. Звучит неожиданно? Зачем он там? Давайте разбираться.

Как все началось

В октябре 2017 года в репозитории golang/go на GitHub зарегистрировали задачу №22350.

Автор задачи указал используемую версию Go (1.9.1), системные параметры и привел небольшой кусок кода.

Он ожидал, что программа будет работать нормально. Вместо этого получил результат, который описал так:

Память не освобождается, пока всё не перестанет работать. А потом я просто выключаю компьютер. -_-

Мы не будем углубляться в этот код, потому что следом пришел контрибьютор языка Go Дейв Чейни (davecheney) и привел

...меньший воспроизводимый пример, который растёт линейно на моей машине:

package main

type Node struct {
        next    *Node
        payload [64]byte
}

func main() {
        curr := new(Node)
        for {
                curr.next = new(Node)
                curr = curr.next
        }
}

Этот кусок кода приводит к быстрой утечке памяти.

Но давайте проверим сами! Запустим этот же код с небольшими правками для отображения статистики в контейнере с версией Go 1.9.1. Посмотреть код и команды для запуска можете в моем репозитории.

Как мы видим, несмотря на периодический вызов сборщика мусора GC, куча не очищается. И в какой-то момент контейнер падает с ошибкой OOM (Out-of-memory, Error 137).

Рис.1. Результат исполнения проблемного кода.

Хочу сразу обратить внимание, что в моем примере используется не new(T), а оператор взятия адреса &T{}. Согласно документации Effective Go эти две операции эквивалентны:

The expressions new(File) and &File{} are equivalent.

В настоящий момент идиома &T{} более популярна, было даже предложение убрать new, но сообщество эту идею не поддержало. Кстати, на Stack Overflow и Reddit встречала мнение, что new(T) гарантирует размещение в куче, но дальше вы увидите, что это не так.

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

…Я долго смотрел на этот код, и мне кажется, что на каждой итерации curr заменяется на curr.next, так что на предыдущее значение curr больше не ссылается.

Как может переполняться память, если мы просто перезаписываем прежний указатель новым? У нас в памяти хранится всего две переменные! По крайней мере, так выглядит ситуация для программиста. Но для компилятора картина явно иная.

Что же здесь происходит?

В самом первом случае new(Node) создает новый указатель. Первый вызов new(Node) никогда не выходит за пределы функции, поэтому компилятор выделяет его на стеке.

Мы, кстати, можем это проверить командой:

go build -gcflags="-m" initial/main.go

Рис.2. Escape-анализ кода с утечкой памяти.

На 9 строчке main.go escape-анализ выводит сообщение: new(Node) does not escape, что означает, что самый первый указатель не "утекает в кучу", а остается на стеке.

Последующие curr.next = new(Node) создают объекты в куче, но стековый указатель curr всегда ссылается на первый узел, удерживая и помечая всю цепочку указателей живой для GC.

Как подчеркнул один из контрибьюторов языка Go — ianlancetaylor, отсюда можно сделать интересные выводы:

Использование в Go одной и той же переменной не значит, что компилятор будет делать то же самое.
Вызов new не гарантирует выделение на куче.

Данный баг довольно серьезный, хоть и встречался не очень часто. Лишь в 2018 году, в релизе 1.12, появляется решение, оформленное в файле mgcstack.go пакета runtime с названием “Сборщик мусора: объекты стека и трассировка стека”.

Оно живое!

С обычными переменными компилятор очень просто может понять, когда она жива. Для этого используется liveness analysis — это анализ жизни переменных в компиляторе Go. Например:

func foo() {
    a := 15              // переменная `a` используется
    fmt.Println(a)       // здесь обращаемся к `a`
    // после этого к `a` не обращаются, значит `a` мертва
}

Но все усложняется, если мы берем адрес от переменной:

func foo() {
    a := 15
    p := &a              // берем адрес `a`
    nextFunction(p)      // передаем адрес в другую функцию
    // Живет ли `a` еще? Кто читает ее через указатель?
    // nextFunction может сохранить этот адрес где-то,
    // передать его дальше, использовать позже...
}

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

Потому что указатель может быть сохранен в другой переменной, передан в неизвестное количество функций и так далее.

До появления сборщика мусора на стеке компилятор видел, что адрес p был взят (через &a), и решал, что p всегда живой в этой функции. Даже когда в цикле p указывал уже не на переменную a, сборщик мусора всё равно сканировал ВСЕ указатели внутри a на предмет объектов кучи, которые через них (указатели) остаются живыми.

Это создавало ложные положительные результаты — объекты кучи оставались в памяти, потому что на них ссылались через мертвую локальную переменную.

Трассировка стека

Трассировка стека организована как мини‑сборка мусора, но специально для объектов стека.

Объект стека (stack object) — это переменная на стеке горутины, адрес которой был взят и которая сама содержит указатели.

Рассмотрим на примерах:

func example() {
    // Обычная переменная (не объект стека) 
    x := 42
    
    // Переменная с указателем, но она сама не хранит указатель, поэтому не объект стека
    p := &x
    
    // Структура, которая хранит указатель — потенциальный объект стека
    type Node struct {
        next  *Node
        value int
    }
    
    node1 := Node{value: 1}
    node2 := Node{value: 2, next: &node1}
    
    // Адрес node2 хранит указатель, 
    // передан в функцию node2,
    // поэтому становится объектом стека.
    processNode(&node2)
}

func processNode(n *Node) {
    ...
}

Давайте рассмотрим, как работает алгоритм сборки мусора на стеке. Будем рассматривать версию Go 1.25. В качестве "документации" будем использовать файлы пакета runtime mgcmark.go, mgcstack.go, mgc.go.

Сам алгоритм scanstack интегрирован в работу основного сборщика мусора и вызывается во время фазы маркировки GC как часть сканирования корневых объектов (markroot).

Рис. 3. Примерный алгоритм работы сборки мусора в Go.

Подготовка к началу сканирования стека

В начале очередного цикла GC (gcStart) подготавливаются и ставятся в очередь задачи по сканированию корневых объектов — стеков, глобальных переменных и других данных. Инициализируется состояние, связанное со сканированием «корня» (gcPrepareMarkRoots).
Подготавливаются горутины, на которых будут работать воркеры маркировки (gcBgMarkStartWorkers). Эти горутины не запускаются до тех пор, пока не начнётся стадия маркировки.
Затем происходит Stop-The-World — короткая пауза выполнения всех горутин (stopTheWorldWithSema). Все горутины останавливаются, завершаются необходимые действия по очистке и освобождению спанов памяти, оставшихся после предыдущего цикла. После чего мир снова запускается — Start-The-World (startTheWorldWithSema).
Небольшое напоминание: сама стадия маркировки выполняется конкурентно с пользовательским кодом. Это ключевое изменение появилось в GC языка Go в версии 1.5. Продолжительность маркировки растёт с увеличением размера кучи и стеков, но вместо продолжительного Stop-The-World, маркировка выполняется параллельно. Благодаря этому, даже при большом числе объектов для сканирования приложение продолжает работать.
Перед запуском сканирования стека горутина должна быть приостановлена (так называемый preemptive suspension). Это необходимо, чтобы «заморозить» изменения в стеке — например, выделение новой памяти или изменение указателей.
Это также позволяет воркерам маркировки безопасно сканировать стеки друг друга, избегая взаимных блокировок. При этом горутина не может сканировать собственный стек.

После этого запускается сканирование стека scanstack.

Сканирование стека

Состояние этапа трассировки стека каждой горутины хранится в специальной структуре stackScanState. Например, здесь задаётся LIFO-очередь указателей на объекты стека, хранятся границы стека для проверки указателей на валидность.

Также здесь задаётся корень бинарного дерева поиска BST, которое строится после добавления всех объектов стека в очередь и обеспечивает быстрый поиск объекта по его адресу за O(log⁡N).

Шаги сканирование стека:

Во время трассировки стека (scanframeworker) находятся все объекты стека.
Все статистически живые указатели, которые могут указывать на стек, сохраняются в очередь указателей.
После этого строится бинарное дерево BST всех объектов для быстрого поиска объекта по адресу.
Каждый указатель из очереди обрабатывается, чтобы проверить, указывает ли он на какой‑нибудь объект стека.
Как только все указатели обработаны, по сути, найдены все объекты стека, которые живы. Все объекты кучи, на которые смотрят эти указатели, считаются живыми и не будут удаляться сборщиком мусора. А те объекты, которые не достигаются трассировкой стека, могут быть удалены из кучи.
Рассмотрим на примере:
Рис. 4. Пример сканирования объектов стека
У нас есть несколько функций f1, f2 и f3, которые содержат указатели на объекты других функций.
В функции f1 существует локальная переменная F, которая указывает на E. Сканирование начнётся с указателя в переменной F.
С F переходим на E, затем на C функции f2, на который указывает E.
Далее переходим на локальный объект D в f2.
Затем на объект A функции f3.
В результате объекты E, C, D, A отмечены как живые.
А вот объект B функции f1 никогда не сканируется, потому что нет живого указателя, который бы вёл к нему.
Поэтому, если B статически мёртв (то есть в функции f3 больше нет обращений к B после вызова f3), то указатели B в куче не считаются живыми. Соответственно, объект в куче, на который указывает B, может быть удалён во время фазы очистки (sweep).
Сами мёртвые объекты стека (именно то, что хранится на стеке) остаются в «спящем» состоянии до тех пор, пока кадр стека не будет удалён. Это может произойти после завершения горутины или, например, после уменьшения размера стека. Как известно, стек горутины может увеличиваться во время выполнения, но также может уменьшаться при определённых условиях (shrinkstack). Это происходит, если выполняются специальные условия, о которых не буду рассказывать в этой статье.
Вот таким образом работает мини-сборщик мусора Go на стеке.

Объявляем охоту на объекты стека?

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

Звучит логично. Но давайте не будем спешить.

В изначальном обсуждении данного бага предлагалось реализовать обнаружение объектов стека через go vet. Эта идея не встретила поддержки. Также сейчас нет линтеров, которые могли бы обнаружить такие объекты.

До реализации сборщика мусора на стеке мы могли косвенно обнаружить объекты стека за счет утечки памяти. Сейчас максимум мы можем увидеть с помощью escape-анализа, что указатель на объект, который имеет ссылку на другой объект, остаётся на стеке. И это по сути объект стека.

Также есть вопросы относительно оценки времени сканирования стека. В пакете metrics есть метрика /cpu/classes/gc/total:cpu-seconds — это общее время CPU, потраченное на все задачи сборщика мусора. Это метрика включает время на scanstack, но также учитывает нагрузку от всех других задач (другие метрики /cpu/classes/gc/ включают в себя scanstack, но также косвенно).

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

Но давайте вернемся к изначальному коду, который порождает огромное количество объектов стека, и попробуем его оптимизировать.

Сравним две функции (полный код тут).

Первая функция создаёт цепочку из n отдельных стековых Node объектов. Вместо неё можно использовать слайс []Node — один объект на стеке вместо n.

type Node struct {
	next    *Node
	payload [64]byte
}

func badManyStackObjects(n int) interface{} {
	var head Node
	current := &head

	for i := 1; i < n; i++ {
		next := Node{}
		current.next = &next
		current = &next
	}

	return &head
}

func goodOneStackObject(n int) interface{} {
	nodes := make([]Node, n)

	for i := range nodes {
		if i > 0 {
			nodes[i].next = &nodes[i-1]
		}
	}

	return nodes
}

Здесь функция badManyStackObjects создаёт n объектов стека.

Функция goodOneStackObject использует слайс []Node для хранения узлов и не генерирует цепочку объектов на стеке.

Давайте посмотрим с помощью bench-тестов, что же будет работать эффективнее. Код для запуска бенчмарков можно посмотреть тут. Запустим бенчмарки с одинаковым количеством операций:

go test -bench=. -benchmem -benchtime=50000x ./recomendation/

Рис. 5. Сравнение выполнения двух функций. — Рис. 5. Сравнение выполне��ия двух функций.

Мы видим что goodOneStackObjectпроизводительнее, чем badManyStackObjects примерно в 3,5 раза (37708 ns/op и 10775 ns/op).

Суммарное время работы сборщика мусора gc-total-s во втором случае также меньше.

Стали ли лучше результаты только за счет того, что уменьшилось количество объектов стека? Скорее всего это тоже повлияло.

Но также нужно учесть, что в примере goodOneStackObject нет лишних аллокаций, создается один массив для множества отдельных объектов. Также есть быстрый доступ по индексу, без обхода указателей.

Через рефакторинг приложения мы можем улучшить производительность кода и уменьшить нагрузку на сборщик мусора. Но мы точно не можем знать, только ли за счёт уменьшения времени сканирования стека, или благодаря более оптимальному дизайну.

Резюмируя

В Go существует мини-сборщик мусора на стеке, который является частью "большого" GC. И это очень интересное решение нетривиальной проблемы.

В качестве решения изначальной проблемы, кстати, предлагались и другие варианты, например, всегда выделять в кучу переменные, которые содержат адрес, и чей адрес берется. Но это убило бы ключевую эффективность Go для целого класса объектов.

Другой вариант, который был получен в результате brainstorm, — это доработать escape и liveness анализ, чтобы определять мертвые объекты. Но эта часть компилятора и так очень сложна, а доработка принесла бы еще больше боли.

Поэтому наиболее разумным вариантом оказалось сделать дополнительное сканирование стека как часть мини-сборку мусора.

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

Источники: