Как сборщик мусора может узнать об объектных ссылках, сделанных из стека?

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

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

Как это делается на самом деле?

Ответ 1

Существуют GC, которые предполагают, что каждый бит-шаблон, который является адресом того, что управляет GC, на самом деле является указателем (и поэтому не выпускает что-то). Это может работать очень хорошо, потому что указатели вызовов обычно больше, чем маленькие общие целые числа, и обычно их нужно выровнять. Но да, это может привести к задержке сбора некоторых объектов. Коллекционер Boehm для C работает таким образом, потому что он основан на библиотеке и поэтому не получает никакой конкретной помощи от компилятора.

Существуют также GC, которые более тесно связаны с языком, на котором они используются, и фактически знают структуру объектов в памяти. Я никогда не читал специально в обработке кадров стека, но вы могли записывать информацию, чтобы помочь GC, если компилятор и GC предназначены для совместной работы. Один трюк мог бы объединить все ссылки указателя и использовать одно слово для каждого стека, чтобы записать, сколько их есть, что не является таким огромным накладным расходами. Если вы можете определить, какая функция соответствует каждому кадру стека, не добавляя слова, говорящего так, тогда вы могли бы скомпилировать карту раскладки фреймов для каждой функции. Другой вариант - использовать теги с тегами, где вы устанавливаете низкий уровень бит порядка слов, которые не являются указателями на 1, которые (из-за выравнивания адреса) никогда не нужны для указателей, поэтому вы можете рассказать их обособленно. Это означает, что вам нужно сдвинуть unboxed значения, чтобы использовать их, хотя.

Ответ 2

Некоторые коллекторы предполагают, что все в стеке является потенциальным указателем (например, Boehm GC). Это оказывается не так плохо, как можно было бы ожидать, но явно субоптимально. Чаще всего на управляемых языках дополнительная информация по тегам остается со стеком, чтобы помочь сборщику выяснить, где указатели.

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

"Растровый" подход - это один из способов сделать это. Каждый бит растрового изображения соответствует одному слову в стеке. Если бит равен 1, то местоположение в стеке является указателем, а если оно равно 0, то местоположение - это просто номер с точки зрения коллектора (или что-то вдоль этих строк). Исключительно хорошо написанная среда исполнения GGC и вызывающие соглашения используют макет одного слова для большинства функций, так что несколько бит обмениваются размером фрейма стека, а остальное служит как растровое изображение. Для больших кадров стека требуется многословная структура, но идея одинаков.

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

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

Интересно, что попытка получить эту управляющую информацию в стеке создает множество проблем, связанных с взаимодействием с C. Например, суб-оптимальным является компиляция языков высокого уровня на C, поскольку, хотя C переносима, трудно переносить такую информацию. Оптимизация компиляторов, разработанных для C-подобных языков (GCC, LLVM), может реструктурировать фрейм стека, создавая проблемы, поэтому сервер GHC LLVM использует свой собственный стек, а не стек LLVM, который стоит для некоторых оптимизаций. Аналогично, граница между кодом C и "управляемым" кодом должна быть построена тщательно, чтобы не путать GC.

По этой причине при создании нового потока на JVM вы фактически создаете два стека (один для Java, один для C).

Ответ 3

В стеке Haskell используется одно слово памяти в каждом кадре стека, описывающее (с растровым изображением), какие из значений в этом стеке кадра являются указателями, а какие нет. Подробнее см. В статье "Макет стека" и "Растровое изображение макет" из комментария GHC.

Чтобы быть справедливым, одно слово памяти действительно не так дорого, все рассмотрено. Вы можете думать об этом как о простом добавлении одной переменной к каждому методу; что не все так плохо.

Ответ 4

Важно понять, что GHC поддерживает свой собственный стек и не использует C-стек (кроме вызовов FFI). Нет никакого переносного способа доступа ко всему содержимому стека C (например, в SPARC некоторые из них скрыты в окнах регистрации), поэтому GHC поддерживает стек, где он имеет полный контроль. После того как вы сохраните свой собственный стек, вы можете выбрать любую схему, чтобы отличать указатели от не указателей в стеке (например, используя растровое изображение).