Реализация сборки мусора на скомпилированных языках

Question

При реализации точной сборки мусора всегда возникает проблема выяснения, какие слова в стеке являются указателями, а какие - другими типами данных, такими как целые числа или числа с плавающей запятой.Интерпретируемые языки обычно решают эту проблему, делая все указателем;компиляторы для некоторых языков, таких как Lisp, обычно решают эту проблему, используя биты тегов, чтобы различать указатели и целые числа.

Но как насчет JIT-компиляторов для языков, таких как Java и C #, которые поддерживают полные целые числа без машинных слов и с плавающей точкойномера?Как они говорят, какое из содержимого стека и регистров ЦП являются указателями?

Answer 1

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

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

Безопасная точка GC - это место в коде, где безопасно прерывать поток, чтобы запланировать другой поток или выполнить сборку мусора. В безопасных точках GC у нас есть необходимые метаданные, чтобы узнать, какие регистры содержат указатели, а какие нет. Например, в JVM Hotspot цикл всегда содержит чтение из специального места в памяти. Результат этого чтения не используется, но если адрес, с которого читает инструкция, защищен от чтения, возникает ошибка страницы. Это можно использовать для прерывания потока в произвольные моменты времени, просто установив эту страницу только для чтения. Когда поток прерывается, мы смотрим на счетчик программы и ищем метаданные, скажем, в хеш-таблице.

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

Редактировать: обратите внимание, что использование точек, безопасных для ГХ, является лишь одним из многих вариантов. Другой вариант, как упоминала SK-logic, - использовать отдельные стеки для указателей и не указателей. Тогда становится ясно, что во время GC необходимо перебрать все элементы одного стека, но ни один из остальных. Вы все равно должны быть осторожны с указателями в регистрах. Например, всякий раз, когда в регистре есть живой указатель, этот же указатель также должен существовать в стеке.

Третьим вариантом является использование стека теней , который содержит связанный список указателей для укладки корней, живущих в реальном стеке. Подробнее см. Статью Фергуса Хендерсона «Точная уборка мусора в неработающей среде» (PDF) .

Answer 2

Языки, такие как Java и C #, определены таким образом, что они не требуют точного сбора. Реализация может использовать консервативный сборщик, где шаблоны битов, которые выглядят как указатель, обрабатываются как указатель (но на самом деле это может быть целое число или число с плавающей запятой). Например, Boehm сборщик является консервативным сборщиком, который можно использовать для языков JIT.