Главная » Хабрахабр » [Перевод] Самодельный сборщик мусора для OpenJDK

[Перевод] Самодельный сборщик мусора для OpenJDK

О любых опечатках и других багах сообщайте в личку — мы их поправим. Это перевод статьи Алексея Шипилёва «Do It Yourself (OpenJDK) Garbage Collector», публикуется с согласия автора.

По крайней мере, создание первой версии! Процесс создания чего-нибудь в рантайме языка — весёлое упражнение. Построить надежную, высокопроизводительную, устойчивую к отказам подсистему рантайма, поведение которой можно удобно наблюдать и отлаживать — очень, очень сложная задача.

Роман Кеннке на FOSDEM 2019 сделал доклад и демо под названием «Пишем GC за 20 минут», используя более раннюю версию этого патча. Сделать простой сборщик мусора — обманчиво просто, и вот этим хочется заняться в данной статье. Несмотря на то, что реализованный там код многое демонстрирует и обильно откомментирован, ощущается необходимость в хорошем высокоуровневом описании происходящего — именно так и появилась эта статья.

В статье будут использоваться специфика и идеи в конкретной реализации HotSpot, но вводного курса по конструированию GC здесь не будет. Базовое понимание работы сборщиков мусора сильно поможет в понимании написанного здесь. Возьмите GC Handbook и прочитайте первые главы про самые основы GC, а ещё быстрей позволит начать статья на Википедии.

Скрытый текст

Сейчас, когда написано много различных GC, довольно просто сделать и свой собственный — много уже написанных элементов можно (пере)использовать, чтобы переложить часть забот о деталях реализации на проверенный и протестированный код.

1.1. Epsilon GC

Его задача состоит в том, чтобы предоставить минимальную реализацию для случая, когда освобождение памяти не нужно или даже запрещено. В OpenJDK 11 появился новый JEP 318: «Epsilon: A No-Op Garbage Collector (Experimental)». В JEP-е более подробно обсуждается, зачем может оказаться полезным.

Epsilon GC реализует только «выделение», а «освобождением» не занимается вообще. С точки зрения реализации, «сборщик мусора» — плохое название, правильней было бы использовать термин «автоматический менеджер памяти», отвечающий как за выделение, так и за освобождение памяти. Поэтому можно взять Epsilon GC и начать реализовывать алгоритмы «освобождения» с чистого листа.

1.1.1. Выделение памяти

Она обслуживает внешние запросы на выделение памяти произвольного размера и создание Thread-Local Allocation Buffer (TLAB) нужного размера. Наиболее проработанная часть Epsilon GC отвечает за выделение памяти. Сама реализация пытается не расширять TLAB слишком уж сильно, поскольку освобождения памяти не будет и потерянные байты никто больше не вернёт.

1.1.2. Барьеры

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

Обрабатывать это каждый раз повсюду может быть утомительно. Epsilon не требует барьеров, но рантайму и компилятору всё равно хочется знать, что барьеры ничего не делают. В частности, barrier set в Epsilon пуст, и всю тривиальную работу — save, load, CAS, arraycopy — можно делегировать реализациям тривиальных барьеров из уже существующего суперкласса. К счастью, начиная с OpenJDK 11, существует новый JEP-304: «Garbage Collection Interface», благодаря которому вставлять барьеры стало гораздо, гораздо проще. Если вы делаете GC, которому точно так же не нужно барьеров, можно просто переиспользовать код из Epsilon.

1.1.3. Подключение к мониторингу

Epsilon уже сделал всё это за вас. Последняя утомительная часть реализации GC — хуки на кучу механизмов мониторинга внутри JVM: должны работать MX-бины, диагностические команды и т.п.

1.2. Рантайм и GC

1.2.1. Корневые элементы

Эти корневые элементы, называемые GC roots, могут быть слотами на стеках потоков и локальными переменными (включая те, что находятся в JIT-скомпилированном коде!), нативными классами и класслоадерами, ссылками в JNI и так далее. Сборщику мусора, в общем случае, требуется знать, что именно в Java-рантайме имеет ссылки на кучу. Но в Hotspot все они отслеживаются с помощью соответствующих подсистем VM, поэтому можно просто изучить, как с ними работают существующие реализации GC. Попытки определить эти элементы могут оказаться очень сложными и утомительными. Дальше по тексту мы это увидим.

1.2.2. Обход объектов

Эта операция встречается повсюду, поэтому общие части рантайма предоставляют готовые инструменты обхода, самому писать ничего не надо. Сборщик мусора должен обойти исходящие ссылки в Java-объектах. Ниже по тексту будет раздел с конкретной реализацией, и там можно встретить, например, вызовы obj→oop_iterate.

1.2.3. Перемещения

Есть несколько мест, куда можно писать эти данные о перемещениях (forwarding data). Перемещающему сборщику мусора нужно куда-то записывать новые адреса перемещаемых объектов.

  1. Можно переиспользовать «маркерное слово» («mark word») в самом объекте (Serial, Parallel и т.п.). После остановки мира все доступы к объекту контролируются, и гарантируется, что ни один Java-поток не сможет увидеть временные данные, которые мы решили вписать в маркерное слово. Можно переиспользовать его для хранения forwarding data.
  2. Можно поддерживать отдельную нативную таблицу перемещений (ZGC, C4 и другие). Это полностью изолирует GC от рантайма и всего остального приложения, поскольку только GC знает о существовании такой таблицы. Конкурентные сборщики обычно используют именно такую схему — не хотят мучиться с кучей ненужных проблем.
  3. Можно добавить еще одно слово в объект (Shenandoah и другие). Эта комбинация двух предыдущих подходов не только даёт рантайму и приложению без проблем работать с существующими заголовками, но и сохраняет forwarding data.

1.2.4. Маркерные данные

И опять, есть несколько способов сохранить их: Сборщику мусора куда-то нужно писать метки о достижимости данных (marking data).

  1. Можно переиспользовать маркерное слово в самом объекте (Serial, Parallel и т.п.). Опять же, в режиме остановки мира можно использовать биты в маркерном слове, чтобы закодировать факт наличия метки. Дальше, если нужно обойти все живые объекты, мы идём по куче, объект за объектом — это возможно благодаря тому, что куча разбираема (parsable).
  2. Можно поддерживать отдельную структуру для хранения marking data (G1, Shenandoah и т.п.). Обычно это делается с помощью отдельной битовой карты, которая отображает каждые N байтов кучи на 1 бит карты. Обычно, Java-объекты выровнены на 8 байт, поэтому карта отображает каждые 64 бита из кучи на 1 бит карты, занимая 1/64 размера кучи в нативной памяти. Эти накладные расходы хорошо окупаются при сканировании кучи на предмет наличия живых объектов, особенно — разреженных: обход карты зачастую сильно быстрей, чем обход разбираемой кучи объект за объектом.
  3. Закодировать метки в сами ссылки (ZGC, C4 и другие). Для этого требуется координация с приложением, нужно вырезать потом все эти метки из ссылок или выполнить ещё какие-нибудь фокусы для поддержания корректности. Другими словами, нужны или барьеры, или ещё какая-то дополнительная работа со стороны GC.

Основная идея этого GC описана как в Википедии, так и в GC Handbook (глава 3. Скорее всего, самым простым в реализации поверх Epsilon является Mark-Compact, в стиле LISP2. Набросок алгоритма будет в разделе с реализацией ниже по тексту, но я всячески рекомендую прочитать немного Википедии или GC Handbook, чтобы понять, что мы вообще собираемся сделать. 2).

У него есть свои плюсы и минусы: Алгоритм, о котором идёт речь — это сдвигающий GC: перемещаемые объекты двигаются скопом в самое начало кучи.

  • Он поддерживает порядок выделений памяти. Это очень хорошо для контроля раскладки в памяти, если вам это важно (контрол-фрики, пришёл ваш час!). Минус в том, что автоматической локальности ссылок так не получишь.
  • Его сложность — O(N) от числа объектов. Тем не менее, линейность имеет свою цену: от GC требуется обходить кучу 4 раза на каждый цикл сборки.
  • Он не требует свободной памяти в куче! Нет никакой необходимости резервировать память в куче для эвакуации живых объектов, поэтому можно работать даже с кучей, переполненной на 99.(9)%. Если же мы возьмёмся за другие идеи простых сборщиков, например, за падальщика с полу-кучами (semi-space scavenger), придётся слегка переписать представление кучи и зарезервировать немного места для эвакуации, но это выходит за рамки данного упражнения.
  • Если немного поработать над вопросом, можно добиться нулевого потребления памяти и времени в периоды, когда GC не активен. Он запускается на памяти, находящейся в произвольном состоянии, и останавливается, значительно её уплотнив. Это очень хорошо ложится на то, как работает Epsilon: он просто продолжает выделять сразу после последнего объекта. Это же и является минусом: несколько мёртвых объектов в начале кучи приводят к большому количеству перемещений.
  • Он просто не требует новых барьеров, можно переиспользовать EpsilonBarrierSet как есть.

Для этого случая имеет смысл использовать битовую карту для хранения пометок и переиспользовать маркерное слово для хранения данных о перемещениях. Для простоты, реализация GC будет использовать полную остановку мира (stop-the-world, STW), в ней не будет поколений и многопоточности.

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

3.1. Пролог

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

// Хорошо разгребаемой кучи для этого алгоритма не нужно, но хочется, // чтобы потоки отдали нам свои текущие TLAB-ы. ensure_parsability(true); // Сообщить разным системам рантайма о том, что мы делаем GC. CodeCache::gc_prologue(); BiasedLocking::preserve_marks(); // Косвенные ссылки будут заново искаться на фазе маркировки. // Нужно почистить и активировать таблицу для них. DerivedPointerTable::clear();
}

Или в нашем случае, поскольку мы преследуем цель никогда не запрашивать ресурсы до запуска цикла GC, придётся заранее закоммитить битовую карту в память. Поскольку мы используем битовую карту для отслеживания достижимости объектов, необходимо очистить её перед использованием. Это дает несколько интересных преимуществ, по крайней мере, на Linux, где большая часть битовой карты будет указывать на нулевую страницу, особенно для разреженных куч.

Потоки должны освободить свои TLAB и попросить у GC новые, после того как сборка завершится.

ThreadLocal. Не путайте TLAB и java.lang. С точки зрения GC, ThreadLocal-ы — обычные объекты, и они не будут собраны GC, если обратного специально не потребовать в Java-коде.

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

3.2. Маркировка

Маркировка проходит довольно стандартно, и скорей всего, во многих реализациях GC является первым шагом. Маркировка в режиме остановки мира становится довольно простой, когда почти всё уже сделано за нас.

{ GCTraceTime(Info, gc) time("Step 1: Mark", NULL); // Маркировочный стек и замыкание, которое делает большую часть работы. Замыкание // просканирует исходящие ссылки, пометит их, и протолкнет свежепомеченные // объекты на стек для дальнейшей обработки. EpsilonMarkStack stack; EpsilonScanOopClosure cl(&stack, &_bitmap); // Засеять маркировку ссылками из корневых элементов. process_roots(&cl); stat_reachable_roots = stack.size(); // Сканировать оставшуюся часть кучи, пока объекты не закончатся. // Этот процесс гарантировано закончится, поскольку существует момент, // когда все живые объекты окажутся помеченными. while (!stack.is_empty()) { oop obj = stack.pop(); obj->oop_iterate(&cl); stat_reachable_heap++; } // После завершения маркировки косвенных ссылок не осталось. DerivedPointerTable::set_active(false);
}

Обход продолжается до тех пор, пока не закончатся все непосещённые вершины. Это работает в точности так же, как и для любого другого графа: вы начинаете обход с изначального набора достижимых вершин, идете по исходящим рёбрам и записываете все посещённые вершины. В GC «вершинами» являются объекты, а «рёбрами» — ссылки между ними.

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

Сейчас не стоит останавливаться на том, что такое process_roots, об этом будет позже. Изначальный набор достижимых объектов — это GC roots. Сейчас просто скажем, что он обходит все достижимые ссылки со стороны VM.

Реальная работа происходит в EpsilonScanOopClosure, он применяется ко всем интересным объектам и итерируется по всем ссылкам выбранного объекта. Битовая карта с отметками служит и как инструмент для записи фронта маркировки (marking wavefront) (множество уже посещённых объектов), и под конец — как хранилище желаемого результата, набора всех достижимых объектов.

Глядите, Java умела в замыкания (closure) до того, как это стало модно!

class EpsilonScanOopClosure : public BasicOopIterateClosure {
private: EpsilonMarkStack* const _stack; MarkBitMap* const _bitmap; template <class T> void do_oop_work(T* p) { // p - это ссылка на место памяти, где расположен oop, нужно загрузить // оттуда значение и распаковать сжатую ссылку, если необходимо: T o = RawAccess<>::oop_load(p); if (!CompressedOops::is_null(o)) { oop obj = CompressedOops::decode_not_null(o); // Объект найден. Посмотреть, отмечен ли он. Если нет, // пометить и сбросить на маркировочный для дальнейшего обхода. // Здесь подойдёт неатомарная проверка+запись, // поскольку замыкание выполняется строго в одном треде. if (!_bitmap->is_marked(obj)) { _bitmap->mark((HeapWord*)obj); _stack->push(obj); } } }
};

Благодаря этому есть возможность обойти все живые объекты, например: После завершения этого шага, _bitmap содержит биты, указывающие на местоположение живых объектов.

// Пройти по маркировочному битмапу и позвать замыкание на каждый помеченный объект.
// Это гораздо быстрее, чем пообъектный обход (очень разреженной) разбираемой кучи, но // на размещение битмапа тратится вплоть до 1/64 размера кучи.
void EpsilonHeap::walk_bitmap(ObjectClosure* cl) { HeapWord* limit = _space->top(); HeapWord* addr = _bitmap.get_next_marked_addr(_space->bottom(), limit); while (addr < limit) { oop obj = oop(addr); assert(_bitmap.is_marked(obj), "sanity"); cl->do_object(obj); addr += 1; if (addr < limit) { addr = _bitmap.get_next_marked_addr(addr, limit); } }
}

3.3. Вычисляем новые адреса

Это тоже довольно простой шаг, и он реализует в точности то, что говорится в алгоритме.

// Мы собираемся хранить forwarding data (место, где размещена новая копия)
// в маркировочном слове. Часть этих маркировочных слов нужно очень аккуратно сохранить.
// Здесь мы будем хранить и поддерживать список таких специальных слов.
PreservedMarks preserved_marks; // Новый конец памяти после GC.
HeapWord* new_top; { GCTraceTime(Info, gc) time("Step 2: Calculate new locations", NULL); // Обойти все живые объекты, вычислить их новые адреса и сохранить эти // адреса в маркировочные слова. Возможно, сохранить какие-то отметки. EpsilonCalcNewLocationObjectClosure cl(_space->bottom(), &preserved_marks); walk_bitmap(&cl); // После вычисления адресов мы знаем положение новой вершины памяти. // Мы не можем прямо сейчас использовать её, ибо внутренние проверки // в следующих фазах всё ещё ожидают, что объекты всё ещё лежат "ниже" // этой вершины. new_top = cl.compact_point(); stat_preserved_marks = preserved_marks.size();
}

К счастью, такие нетривиальные маркировочные слова достаточно редки, и мы можем просто хранить их отдельно, если это вообще нужно: именно для этого используется PreservedMarks. Единственное, что здесь бросается в глаза — мы решили хранить новые адреса в маркировочном слове джавовых объектов, и это слово может уже быть занято под что-то важное, например, под информацию о блокировках.

Реальную алгоритмическую работу делает EpsilonCalcNewLocationObjectClosure:

class EpsilonCalcNewLocationObjectClosure : public ObjectClosure {
private: HeapWord* _compact_point; PreservedMarks* const _preserved_marks; public: EpsilonCalcNewLocationObjectClosure(HeapWord* start, PreservedMarks* pm) : _compact_point(start), _preserved_marks(pm) {} void do_object(oop obj) { // Записываем новое местоположение объекта: это текущая точка уплотнения. // Если объект остаётся на том же месте (это верно для объектов в плотном префиксе, // которое обычно и получается), не стоит беспокоиться о записи перемещения, // позволим последующему коду проигнорировать его. if ((HeapWord*)obj != _compact_point) { markOop mark = obj->mark_raw(); if (mark->must_be_preserved(obj)) { _preserved_marks->push(obj, mark); } obj->forward_to(oop(_compact_point)); } _compact_point += obj->size(); } HeapWord* compact_point() { return _compact_point; }
};

Это понадобится на следующих шагах. forward_to — самая важная часть, поскольку хранит «адрес перемещения» в маркерном слове объекта.

3.4. Исправляем указатели

Теперь нужно снова пройти по куче и перезаписать все ссылки их новыми адресами согласно следующему алгоритму:

{ GCTraceTime(Info, gc) time("Step 3: Adjust pointers", NULL); // Пройти все живые объекты _и их ссылочные поля_, и записать в них // «новые адреса». Мы знаем новые адреса из forwarding data, // хранящейся в маркировочном слове. Вначале позаботимся об объектах на куче. EpsilonAdjustPointersObjectClosure cl; walk_bitmap(&cl); // Теперь сделаем то же самое, но для всех корневых элементов VM, которые // самостоятельно держат ссылки на объекты: все эти ссылки тоже нужно обновить. EpsilonAdjustPointersOopClosure cli; process_roots(&cli); // Ну и наконец, нужно сообщить сохранённым меткам о том, // что объекты скоро начнут двигаться. preserved_marks.adjust_during_full_gc();
}

Обновить нужно оба класса ссылок. Есть два вида ссылок на сдвигаемые объекты: исходящие либо из объектов на самой куче, или из GC roots. PreservedMarks знает, как это делать, потому что ожидает «forwarding data» в том же месте, где мы её сохранили, в маркировочном слове объекта. Некоторые сохранённые метки тоже хранят ссылки на объекты, поэтому необходимо попросить их обновиться.

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

class EpsilonAdjustPointersOopClosure : public BasicOopIterateClosure {
private: template <class T> void do_oop_work(T* p) { // p - указатель на адрес в памяти, где расположен oop. // нужно загрузить оттуда значение и распаковать сжатую ссылку, если нужно: T o = RawAccess<>::oop_load(p); if (!CompressedOops::is_null(o)) { oop obj = CompressedOops::decode_not_null(o); // Перезаписать текущий указатель на объект на его новое положение. // Пропустить запись, если обновление не требуется. if (obj->is_forwarded()) { oop fwd = obj->forwardee(); assert(fwd != NULL, "just checking"); RawAccess<>::oop_store(p, fwd); } } }
}; class EpsilonAdjustPointersObjectClosure : public ObjectClosure {
private: EpsilonAdjustPointersOopClosure _cl;
public: void do_object(oop obj) { //Выполнить обновление для всех ссылок, достижимых из текущего объекта: obj->oop_iterate(&_cl); }
};

Давайте починим это! После выполнения этого шага мы, по сути, сломали кучу: ссылки указывают на «неправильные» адреса, по которым ещё не лежат объекты.

3.5. Двигаем объекты

Время двигать объекты по новым адресам, в соответствии с алгоритмом:

Снова обходим кучи и применяем замыкание EpsilonMoveObjectsObjectClosure ко всем живым объектам:

{ GCTraceTime(Info, gc) time("Step 4: Move objects", NULL); // Передвинуть все живые объекты на новые адреса. // Все ссылки уже переписаны на эти адреса в предыдущем шаге. EpsilonMoveObjectsObjectClosure cl; walk_bitmap(&cl); stat_moved = cl.moved(); // Так как все объекты уже передвинуты по новым адресам, можно урезать // «верх» кучи ровно до конца уплотнённого префикса. _space->set_top(new_top);
}

Сразу после этого можно перетащить курсор кучи точки уплотнения, дав возможность выделять память прямо с этого места, сразу же как закончится цикл сборки мусора.

Заметьте, что в сдвигающей сборке мы можем перезаписывать содержимые существующих объектов, но поскольку сканирование идёт в одном и том же направлении, перезаписанные объекты уже скопированы в правильное место.

Например, если вы сдвинете 100-байтовый объект на 8 байт. Старое и новое месторасположение одного и того же объекта могут пересекаться. Процедура копирования должна это отработать сама, и пересекающееся содержимое должно быть скопировано корректно, обратите внимание на Copy::aligned_*conjoint*_words.

Само же замыкание просто передвинет перемещаемые объекты по новым адресам:

class EpsilonMoveObjectsObjectClosure : public ObjectClosure {
public: void do_object(oop obj) { // Копируем объект по новому адресу, если нужно. Этот шаг - последний, // поэтому необходимо ре-инициализировать его mark word, // и выбросить из него всю forwarding data. if (obj->is_forwarded()) { oop fwd = obj->forwardee(); assert(fwd != NULL, "just checking"); Copy::aligned_conjoint_words((HeapWord*)obj, (HeapWord*)fwd, obj->size()); fwd->init_mark_raw(); } }
};

3.6. Эпилог

Сборка мусора закончена, куча снова почти консистентна, остались последние завершающие штрихи:

{ GCTraceTime(Info, gc) time("Step 5: Epilogue", NULL); // Восстановить специальные маркерные слова. preserved_marks.restore(); // Сообщить остальному рантайму, что мы завершили сборку. DerivedPointerTable::update_pointers(); BiasedLocking::restore_marks(); CodeCache::gc_epilogue(); JvmtiExport::gc_epilogue(); // Карта маркировки больше не нужна. if (!os::uncommit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size())) { log_warning(gc)("Could not uncommit native memory for marking bitmap"); } // Вернуть назад всю память, если нужно. // На больших хипах это может занять кучу времени. if (EpsilonUncommit) { _virtual_space.shrink_by((_space->end() - new_top) * HeapWordSize); _space->set_end((HeapWord*)_virtual_space.high()); }
}

Восстанавливаем специальные маркерные слова, которые мы сохранили ранее. Оповещаем остальные части рантайма, что им стоит запустить послесборочные процедуры. Прощальный поцелуй нашей маркерной карте — больше она не нужна.

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

4.1. Обход корневых элементов

Можно попросить каждую специальную подсистему VM обойти ссылки, спрятанные от остальных Java-объектов. Помните, нужно обойти специальные, достижимые ссылки из VM? Исчерпывающий список таких корневых элементов в текущей Hotspot выглядит как-то так:

void EpsilonHeap::do_roots(OopClosure* cl) { // Нужно сказать рантайму, что мы собираемся обходить корневые элементы в 1 потоке. StrongRootsScope scope(1); // Нужно применить замыкание к нескольким специальным видам корневых элементов. CLDToOopClosure clds(cl, ClassLoaderData::_claim_none); MarkingCodeBlobClosure blobs(cl, CodeBlobToOopClosure::FixRelocations); // Обходим всевозможные части корневых элементов рантайма. // Некоторые элементы требуют держать блокировку в момент обхода. { MutexLockerEx lock(CodeCache_lock, Mutex::_no_safepoint_check_flag); CodeCache::blobs_do(&blobs); } { MutexLockerEx lock(ClassLoaderDataGraph_lock); ClassLoaderDataGraph::cld_do(&clds); } Universe::oops_do(cl); Management::oops_do(cl); JvmtiExport::oops_do(cl); JNIHandles::oops_do(cl); WeakProcessor::oops_do(cl); ObjectSynchronizer::oops_do(cl); SystemDictionary::oops_do(cl); Threads::possibly_parallel_oops_do(false, cl, &blobs);
}

Для нашего однопоточного GC достаточно и простого обхода. Существуют расширения, которые могут обходить корневые элементы конкурентно или параллельно.

4.2. Сейфпоинты и остановка мира

В Hotspot это достигается реализацией новой VM_Operation, которая позовёт код нашего GC и попросит специальный VM-поток его выполнить: Поскольку наш GC работает в режиме остановки мира, нужно попросить VM выполнить эту самую паузу остановки мира.

// VM_operation, выполняющая цикл сборки под сейфпоинтом
class VM_EpsilonCollect: public VM_Operation {
private: const GCCause::Cause _cause; EpsilonHeap* const _heap; static size_t _last_used;
public: VM_EpsilonCollect(GCCause::Cause cause) : VM_Operation(), _cause(cause), _heap(EpsilonHeap::heap()) {}; VM_Operation::VMOp_Type type() const { return VMOp_EpsilonCollect; } const char* name() const { return "Epsilon Collection"; } virtual bool doit_prologue() { // Перед тем как управлять хранилищем, нужно взять блокировку на кучу. // Это естественным образом приводит к сериализации запросов к GC, // позволяя объединять запросы на обработку кончившейся памяти из нескольких потоков. // Можно проигнорировать запросы, до которого не прошло аллокаций со времен прошлой // полной сборки. Если перед началом сборки подождать, // пока куча заполнится хотя бы на 1%, это, скорей всего, // решит большинство проблем с гонками. Heap_lock->lock(); size_t used = _heap->used(); size_t capacity = _heap->capacity(); size_t allocated = used > _last_used ? used - _last_used : 0; if (_cause != GCCause::_allocation_failure || allocated > capacity / 100) { return true; } else { Heap_lock->unlock(); return false; } } virtual void doit() { _heap->entry_collect(_cause); } virtual void doit_epilogue() { _last_used = _heap->used(); Heap_lock->unlock(); }
}; size_t VM_EpsilonCollect::_last_used = 0; void EpsilonHeap::vmentry_collect(GCCause::Cause cause) { VM_EpsilonCollect vmop(cause); VMThread::execute(&vmop);
}

А ещё это поможет разрешить несколько гонок, когда все треды одновременно хотят сделать GC — что обычно и происходит, когда память подходит к концу.

4.3. Ошибки выделения памяти

На самом деле, достаточно заменить большую часть вызовов allocate_work на вот эту удобную обёртку, которая запускает GC в момент ошибки выделения памяти: Хорошо, что мы научились делать GC по запросу, но ещё лучше, чтобы GC реагировал на переполнение кучи, когда памяти уже не осталось.

HeapWord* EpsilonHeap::allocate_or_collect_work(size_t size) { HeapWord* res = allocate_work(size); if (res == NULL && EpsilonSlidingGC) { vmentry_collect(GCCause::_allocation_failure); res = allocate_work(size); } return res;
}

Вот и всё!

Наш патч без проблем должен накатываться поверх свежего репозитория OpenJDK.

$ hg clone https://hg.openjdk.java.net/jdk/jdk/ jdk-jdk
$ cd jdk-jdk
$ curl https://shipilev.net/jvm/diy-gc/webrev/jdk-jdk-epsilon.changeset | patch -p1

Ну и потом собираем OpenJDK как обычно:

$ ./configure --with-debug-level=fastdebug
$ make images

Запускаем тоже обычным образом:

$ build/linux-x86_64-server-fastdebug/images/jdk/bin/java -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC -version openjdk version "13-internal" 2019-09-17
OpenJDK Runtime Environment (build 13-internal+0-adhoc.shade.jdk-jdk-epsilon)
OpenJDK 64-Bit Server VM (build 13-internal+0-adhoc.shade.jdk-jdk-epsilon, mixed mode, sharing

Есть несколько полезных инструментов: Как проверить, что наша реализация GC не сломана?

  1. Ассерты. Куча ассертов. В коде Hotspot уже есть множество ассертов, поэтому запуск JVM в режиме fastdebug обычно показывает кучу интересных ошибок там и здесь, в том числе и относящихся к поломке GC.
  2. Внутренние проверки. Наш патч реализует последний шаг в цикле сборки, который проходит по всем живым объектам и проверяет их правильность. Обычно, так можно наткнуться на самые вопиющие ошибки (разломанную кучу) ещё до того, как рантайм или приложение увидят их по завершению цикла сборки.
  3. Тесты. Ассерты и проверки бесполезны, если код, где они написаны, вообще не запустился. Полезно иметь порядочное количество юнит-тестов и интеграционных тестов, и запускать их как можно раньше и чаще.

Например, вот как можно проверить, что наш патч не развалился чудовищным образом:

$ CONF=linux-x86_64-server-fastdebug make images run-test TEST=gc/epsilon/
Building targets 'images run-test' in configuration 'linux-x86_64-server-fastdebug'
Test selection 'gc/epsilon/', will run:
* jtreg:test/hotspot/jtreg/gc/epsilon Running test 'jtreg:test/hotspot/jtreg/gc/epsilon'
Passed: gc/epsilon/TestAlwaysPretouch.java
Passed: gc/epsilon/TestAlignment.java
Passed: gc/epsilon/TestElasticTLAB.java
Passed: gc/epsilon/TestEpsilonEnabled.java
Passed: gc/epsilon/TestHelloWorld.java
Passed: gc/epsilon/TestLogTrace.java
Passed: gc/epsilon/TestDieDefault.java
Passed: gc/epsilon/TestDieWithOnError.java
Passed: gc/epsilon/TestMemoryPools.java
Passed: gc/epsilon/TestMaxTLAB.java
Passed: gc/epsilon/TestPrintHeapSteps.java
Passed: gc/epsilon/TestArraycopyCheckcast.java
Passed: gc/epsilon/TestClasses.java
Passed: gc/epsilon/TestUpdateCountersSteps.java
Passed: gc/epsilon/TestDieWithHeapDump.java
Passed: gc/epsilon/TestByteArrays.java
Passed: gc/epsilon/TestManyThreads.java
Passed: gc/epsilon/TestRefArrays.java
Passed: gc/epsilon/TestObjects.java
Passed: gc/epsilon/TestElasticTLABDecay.java
Passed: gc/epsilon/TestSlidingGC.java
Test results: passed: 21
TEST SUCCESS

Теперь попробуйте запустить реальное приложение на fastdebug сборке со включенной верификацией. Довольны? Уже можно на что-то надеяться. Не сломалось?

В этом тесте будет совсем немного живых данных, поэтому неважно, есть ли в нашем GC поколения. Давайте-ка запустим spring-petclinic, загрузим Apache Bench и подключим наш игрушечный GC!

Запускать надо с параметрами: -Xlog:gc -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC -XX:+EpsilonSlidingGC:

Выхлоп:

Heap: 20480M reserved, 20480M (100.00%) committed, 19497M (95.20%) used
GC(2) Step 0: Prologue 2.085ms
GC(2) Step 1: Mark 51.005ms
GC(2) Step 2: Calculate new locations 71.207ms
GC(2) Step 3: Adjust pointers 49.671ms
GC(2) Step 4: Move objects 22.839ms
GC(2) Step 5: Epilogue 1.008ms
GC(2) GC Stats: 70561 (8.63%) reachable from roots, 746676 (91.37%) reachable from heap, 91055 (11.14%) moved, 2237 (0.27%) markwords preserved
GC(2) Heap: 20480M reserved, 20480M (100.00%) committed, 37056K (0.18%) used
GC(2) Lisp2-style Mark-Compact (Allocation Failure) 20479M->36M(20480M) 197.940ms

Совсем неплохо для написанного на коленке однопоточного GC! 200 миллисекунд? На самом деле, если вы поиграете с различным заполнением кучи и её размером, то заметите закономерность: увеличение количества живых данных означает значительное замедление сборки (последовательно достучаться до всех живых объектов — невесёлая процедура, если их действительно много). Как можно видеть, все четыре основных фазы выполняются за время одного порядка. Увеличение размера кучи замедляет сборку только чуть-чуть (бег на длинные дистанции даже по разрешенной куче имеет свою цену и свой вклад в потоковую производительность).

Например, давайте запустим -Xlog:gc -XX:+UseSerialGC — он собирает, в основном, молодое поколение: Для сравнения, GC с поколениями или падальщики легко справятся и с такой нагрузкой.

GC(46) Pause Young (Allocation Failure) 575M->39M(1943M) 2.603ms
GC(47) Pause Young (Allocation Failure) 575M->39M(1943M) 2.606ms
GC(48) Pause Young (Allocation Failure) 575M->39M(1943M) 2.747ms
GC(49) Pause Young (Allocation Failure) 575M->39M(1943M) 2.578ms

Это потому, что большая часть объектов в молодом поколении мертва, и такому GC здесь нечего делать. Вау, 2 миллисекунды. Если же мы выключим в -Xlog:gc -XX:+UseSerialGC расширения, отвечающие за поколения и запустим полную сборку, то увидим куда менее радужную картинку:

GC(3) Pause Full (Allocation Failure) 16385M->34M(18432M) 1969.694ms
GC(4) Pause Full (Allocation Failure) 16385M->34M(18432M) 2261.405ms
GC(5) Pause Full (Allocation Failure) 16385M->34M(18432M) 2327.577ms
GC(6) Pause Full (Allocation Failure) 16385M->34M(18432M) 2328.976ms

Считайте это домашним заданием. Есть куча метрик и сценариев, с которыми можно поиграться.

Многие из этих путей будут строить то, что уже умеют GC из OpenJDK — и то, что уже хорошо протестировано, и поэтому относиться к таким улучшениям стоит в образовательном ключе. Дальше можно пойти разными путями.

Что можно улучшить:

  1. Текущая реализация игнорирует тот факт, что существуют мягкие/слабые/фантомные ссылки. Реализовать обработку слабых ссылок. Это не идеально по производительности, но довольно безопасно с точки зрения корректности, поскольку общий код «всего лишь» считает все такие ссылки за всегда достижимые, поэтому они будут двигаться и обновляться так же, как любые другие.
    Ещё она игнорирует существование финализируемых объектов.

    Reference.referent — это просто ещё одно Java-поле, всегда доступное, за исключением случая, когда мы обходим кучу каким-то специальным способом. С точки зрения GC, java.lang.ref. Финализируемые объекты имеют собственные синтетические обёртки FinalReference, которые за них держатся.

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

  2. Текущая реализация никогда не выгружает классы и никогда не подчищает структуры данных внутри VM, которые держат объекты, недоступные из кучи, и поэтому наверняка там есть что почистить. Реализовать выгрузку классов и другие способы чистки VM. По умолчанию, маркировке подвергаются только сильные корневые элементы, и впоследствии, если по окончании маркировки какие-то из слабых элементов остались неотмеченными, их можно будет снести. Реализация всего этого потребует заботы о слабых и сильных корневых элементах.

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

    Параллельные версии этого mark-compact GC реализованы как Full GC fallbacks в Shenandoah (начиная с OpenJDK 8) и G1 (начиная с OpenJDK 10, сразу после выхода JEP 307: «Parallel Full GC for G1»).

  4. Часто бывает, что после нескольких сборок в куче образуется «осадочный» слой из всегда доступных объектов, поэтому можно сэкономить пару циклов, указав, что какой-то префикс кучи не двигается вообще. Реализовать обработку плотного префикса. Тем не менее, нам всё ещё нужно маркировать её и исправлять там указатели. Тогда можно избежать вычисления адресов и смещения объектов в эту зону.

  5. Добавив немного работы с барьерами, можно определить, какая часть префикса наиболее интересна, и тем самым сэкономить время на её маркировку и подмену указателей. Расширить плотный префикс до полноценной сборки с поколениями. В конце концов, всё это закончится изобретением «поколений» — мы будем собирать «молодое» поколение сразу после префикса и иногда делать «полную» сборку, чтобы уплотнить и сам префикс тоже.

  6. Взять какой-нибудь алгоритм из GC Handbook и попытаться самостоятельно его реализовать.

Реализация игрушечного GC — это весело, познавательно, и возможно, даже хорошая идея для университетского курса по GC. Какие выводы можно сделать из этого упражнения?

Примечательно, что если продолжать разработку дальше, эта реализация в конце концов превратится в один из уже существующих GC (например, Serial GC или Parallel GC), что делает такие усилия чуть менее чем полностью бесполезными. Продуктизация же такой реализации будет утомительным и трудоемким процессом, поэтому легче взять какой-нибудь готовый GC и настраивать его.

Через месяц, 5-6 апреля 2019, пройдёт JPoint — крупнейшая в России Java-конференция. Минутка рекламы. Ознакомиться с программой и приобрести билеты можно на официальном сайте. В программе ожидается множество докладов о подробностях работы современных технологий — OpenJDK, GraalVM, Kotlin и других.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Из песочницы] ВИЧ – методы лечения от первых лекарств до сегодняшнего дня

Прежде, чем приступить к изложению материала, хотелось бы сказать несколько слов о себе: участник сообществ по борьбе с отрицанием ВИЧ („ВИЧ/СПИД диссидентством“): в 2016-2018 годах „ВИЧ/СПИД диссиденты и их дети“, с 2018 года – „ВИЧ/СПИД отрицание и альтернативная медицина“. Это ...

Изюминки прошедшей Moscow Python Conf++ 2019: трансформация в площадку для общения

Самыми горячими темами Moscow Python Conf++ оказались асинхронная разработка, а также сопоставление Python, его лучших практик и инструментария с аналогами из других языков, и его место в ландшафте современной разработки. Плюс мы пригласили выступить Бенджамина Петерсона, одного из разработчиков CPython, ...