В основном, для достижения точной маркировки вам нужны метаданные, указывающие, какие слова используются в качестве указателей, а какие нет.
Эти метаданные могут храниться по ссылке, как это делает emacs. Если для вашего языка / реализации вы не заботитесь об использовании памяти, вы можете даже делать ссылки больше, чем слова (возможно, в два раза больше), чтобы каждая ссылка могла нести информацию о типе, а также данные из одного слова. Таким образом, вы можете получить фиксированный номер полного размера 32-битного указателя, за счет того, что все ссылки будут 64-битными.
В качестве альтернативы, метаданные могут храниться вместе с информацией другого типа. Так, например, класс может содержать, как и обычную таблицу указателей на функцию, один бит на слово макета данных, указывающий, содержит ли слово ссылку, за которой должен следовать сборщик мусора. Если ваш язык имеет виртуальные вызовы, то у вас уже должны быть средства для определения из объекта, какие адреса функций использовать, поэтому тот же механизм позволит вам определить, какие данные маркировки использовать - обычно вы добавляете дополнительный секретный указатель на начало каждого отдельного объекта, указывающего на класс, который составляет его тип времени выполнения. Очевидно, что с некоторыми динамическими языками данные типа, на которые указывают данные, должны быть скопированы при записи, поскольку они могут быть изменены.
Стек может делать то же самое - хранить точную информацию о маркировке в разделах данных самого кода, и сборщик мусора проверяет счетчик хранимой программы и / или указатели ссылок в стеке и / или другую информацию, размещенную на стека с помощью кода для цели, чтобы определить, к какому коду относится каждый бит стека и, следовательно, какие слова являются указателями. Облегченные механизмы исключений, как правило, делают аналогичные вещи для хранения информации о том, где происходит попытка / отловка в коде, и, конечно, отладчики также должны иметь возможность интерпретировать стек, так что это вполне возможно сложить с кучей других вещей. вы уже будете заниматься внедрением любого языка, в том числе со встроенным сборщиком мусора.
Обратите внимание, что сборка мусора не обязательно требует точной маркировки. Вы можете рассматривать каждое слово как указатель, независимо от того, действительно ли оно или нет, поискать его в «большом списке всего» вашего сборщика мусора, чтобы решить, может ли оно правдоподобно ссылаться на объект, который еще не был помечен, и если так относитесь к нему как к ссылке на этот объект. Это просто, но цена, конечно, в том, что он находится где-то между «довольно медленным» и «очень медленным», в зависимости от того, какие структуры данных ваш gc использует для поиска. Кроме того, иногда целочисленное значение имеет то же значение, что и адрес объекта, на который нет ссылок, и заставляет вас хранить целую кучу объектов, которые должны были быть собраны. Поэтому такой сборщик мусора не может дать надежных гарантий относительно когда-либо собранных объектов, на которые нет ссылок. Это может быть хорошо для игрушечной реализации или первой рабочей версии, но вряд ли будет популярным среди пользователей.
Смешанный подход может, скажем, делать точную маркировку объектов, но не областей стека, где вещи становятся особенно волосатыми. Например, если вы пишете JIT, который может создать код, в котором адрес объекта, на который ссылаются, появляется только в регистрах, а не в ваших обычных слотах стека, тогда вам может потребоваться не точно следовать области стека, где ОС хранит регистры, когда она отменил запланированный поток для запуска сборщика мусора. Что, вероятно, довольно неудобно, поэтому разумным подходом (потенциально приводящим к более медленному коду) было бы требование, чтобы JIT всегда сохранял копию всех значений указателя, которые он использует, в точно маркированном стеке.