О «маркировке» объекта во время сборки мусора или Рихтер был не прав

Сегодня речь пойдет о бесполезной, с практической точки зрения, информации о внутренностях CLR и сборщика мусора.

Многие из нас изучали внутренности .NET и CLR по книге Джеффри Рихтера “CLR via C#”. Книга просто замечательной, глубокая, детальная и очень точная. Но, как это обычно бывает, даже Рихтер иногда ошибается (пусть и в деталях).

Вот цитата:

When the CLR starts a GC, the CLR first suspends all threads in the process. This prevents threads from accessing objects and changing their state while the CLR examines them. Then, the CLR performs what is called the marking phase of the GC. First, it walks through all the objects in the heap setting a bit (contained in the sync block index field) to 0. This indicates that all objects should be deleted. Then, the CLR looks at all active roots to see which objects they refer to. This is what makes the CLR’s GC a reference tracking GC. If a root contains null, the CLR ignores the root and moves on to examine the next root.

Any root referring to an object on the heap causes the CLR to mark that object. Marking an object means that the CLR sets the bit in the object’s sync block index to 1. When an object is marked, the CLR examines the roots inside that object and marks the objects they refer to. If the CLR is about to mark an already-marked object, then it does not examine the object’s fields again. This prevents an infinite loop from occurring in the case where you have a circular reference.

И что же здесь не так?

На самом деле, здесь две проблемы (выделены жирным).

Во-первых, mark phase реализована несколько иначе. На самом деле в начале каждой сборки никто не бегает по всем объектам для сброса некоторого бита в 0. Причина здесь простая: это было бы сильно неэффективно.

Эффективность сборки мусора обратно пропорциональная числу выживших объектов. Это означает, что чем больше мусора, тем эффективнее сборка. Практика показывает, что для большинства приложений это правило выполняется и переживают сборку мусора «детских» поколений (поколений 0 и 1) лишь небольшая часть объектов. А это означает, что значительно проще использовать такой подход:

· Признак IsMark сброшен перед сборкой мусора

· Сборщик пробегается по кусочку кучи и устанавливает IsMark в true для всех достижимых объектов. (Размер кучи определяется номером собираемого поколения + дополнительными сегментами кучи, полученными из card table, подробнее в статье Немного о сборке мусора и поколениях)

· Затем идет подметание (sweep) или перемещение выживших объектов в начало сегмента (compact), в зависимости от того, будет ли эффективной компакт кучи или нет. После чего, выжившие объекты пробегаются снова и IsMark флаг сбрасывается.

Поскольку число выживших объектов в реальных условиях сильно меньше исходного числа объектов, такой подход является существенно более предпочтительным с точки зрения эффективности (пруф. находится в гигантском gc.cpp: clear_pinned вызывается во время sweep/compact фазы, а не перед mark фазой).

Вторая особенность заключается в реализации признака IsMarked. Старина Рихтер пишет, что для этого используется бит в заголовке объекта, и с этим также согласны авторы Pro .NET Performance (Глава 4):

On a multi-processor system, since the collector marks objects by setting a bit in their header, this causes cache invalidation for other processors that have the object in their cache.

Вот как выглядит макрос clear_marked в coreclr:

#define set_marked(i) header(i)->SetMarked()
#define clear_marked(i) header(i)->ClearMarked()

Но вот как выглядит реализация метода ClearMarked:

void ClearMarked()
{
    RawSetMethodTable(GetMethodTable());
}
void SetMarked()
{
    RawSetMethodTable((MethodTable*)(((size_t)RawGetMethodTable()) | GC_MARKED));
}
MethodTable* GetMethodTable() const
{
    return( (MethodTable*) (((size_t) RawGetMethodTable()) & (~(GC_MARKED))));
}

То есть, вместо бита в заголовке объекта, используется младший бит в адресе указателя на Method Table! Это довольно умно, поскольку объекты в памяти выровнены и младшие 2 бита указателя никогда толком не используются! Тут, конечно, нужно не забыть сбросить их при доступе к Method Table, но решение заключается в разделении методов. GetMethodTable всегда возвращает «корректный» указатель, а RawGetMethodTable возвращает «указатель» с потенциально «испорченным» младшим битом. (да, GC_MARKED равен 1).

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

А если и этого мало, то вот вам несколько дополнительных ссылок:

• Garbage Collection – part 1 of N
• Garbage Collection Design by Maoni Stephens
• Немного о сборке мусора и поколениях
• CLR via C# by Jeffrey Richter
• Pro .NET Performance by Sasha Goldshtein at all