Как реализовать платформо-независимый сборщик мусора?

Question

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

(1) gc_alloc() выделяет память

(2) gc_realloc() перераспределяет память

(3) gc_run() запускает сборщик мусора.

Я уже взглянул на библиотеку libgc для сборки мусора, разработанную Boehm et. al., но это не зависит от платформы; это было просто перенесено на много разных систем. Я хотел бы реализовать сборщик мусора, который не содержит системно-зависимого кода. Скорость не является огромной проблемой.

Есть предложения?

Answer 1

К сожалению, на самом деле невозможно сделать действительно платформо-независимый сборщик мусора в C. Строгое чтение стандарта C позволяет любому типу (кроме unsigned char) иметь биты-ловушки - биты, которые если они имеют неправильное значение, система выдаст предупреждение об исключении (т. е. неопределенное поведение). При сканировании выделенных блоков для указателей у вас нет возможности определить, содержит ли конкретный блок памяти допустимое значение указателя или он будет перехвачен, как только вы попытаетесь посмотреть на значение в нем.

Исследование указателей как целых также не помогает - не требуется тип int для представления, совместимого с указателем. intptr_t доступен только на самых последних компиляторах, и я не верю, что его представление также должно быть совместимым. И у int могут быть биты-ловушки.

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

Но большая проблема - найти корневой набор. Bohem GC и другие, как правило, сканируют стек, а также статические данные на наличие указателей, которые должны идти в корневом наборе. Это невозможно без знания структуры памяти ОС . Поэтому вам нужно, чтобы пользователь явно пометил членов корневого набора, что побеждает точку сбора мусора.

Короче говоря, вы не можете сделать GC в по-настоящему переносной C. В принципе, вы можете сделать это, если сделаете несколько предположений:

• Предположим, что корневой набор будет явно предоставлен вам пользователем.
• Предположим, что в представлениях указателя или int нет битов прерываний.
• Предположим, intptr_t доступно или Предполагается, что все void * строго упорядочены (т. Е. < и > разумно работают с указателями из разных malloc действий)
• Предположим, что все типы указателей данных имеют представление, совместимое с void *.
• Необязательно, но дает большую прибавку в скорости: жестко закодируйте выравнивание указателей (это далеко не универсально и должно зависеть от компилятора и платформы). Это предположение позволит вам пропустить memcpy указателей на известные Выровненное местоположение, а также сократит количество потенциальных указателей для проверки.

Если вы сделаете эти предположения, вы сможете создать консервативный распределитель разметки. Используйте двоичное дерево для хранения информации о том, где находятся распределения, и просмотрите каждое возможное выровненное местоположение указателя в выделенных блоках для указателей. Однако необходимость явного предоставления корневого набора сделает все это бессмысленным - это будет malloc и free снова и снова, за исключением того, что для определенного плохо определенного набора объектов вы можете его пропустить. Не совсем то, что должен предоставить GC, но я полагаю, что оно может иметь свое место, например, как часть виртуальной машины (в этом случае корневой набор будет получен из информации, доступной для виртуальной машины).

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

Answer 2

Для алгоритма метки и развертки все, что вам действительно нужно, это вычислить, какие объекты достижимы из корневого набора, верно?(Это было некоторое время назад, так как я копался в этом ...)

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

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

Простой псевдокод, чтобы показать, что я имею в виду под подсчетом ссылок и управлением графиками:

some_object * pObject = gc_alloc(sizeof(some_object));
some_container * pContainer = gc_alloc(sizeof(some_container));

pContainer->pObject = pObject;
/* let the GC know that pContainer has a reference to pObject */
gc_object_reference(pContainer, pObject);

/* a new block of some kind */
{
    /* let the GC know we have a new reference for pObject */
    some_object * pReference = gc_reference(pObject); 

    /* do stuff */
    ...

    /* let the GC know that this reference is no longer used */
    gc_left_scope(pReference);
}

gc_left_scope(pObject);
gc_run(); /* should not be able to recycle anything, since there still is a live
           * reference to pContainer, and that has a reference to pObject
           */