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

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

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

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

Содержание

1. Из чего состоит 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. Выделение памяти

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

1.1.2. Барьеры

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

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

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

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

1.2. Рантайм и GC

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

Сборщику мусора, в общем случае, требуется знать, что именно в Java-рантайме имеет ссылки на кучу. Эти корневые элементы, называемые GC roots, могут быть слотами на стеках потоков и локальными переменными (включая те, что находятся в JIT-скомпилированном коде!), нативными классами и класслоадерами, ссылками в JNI и так далее. Попытки определить эти элементы могут оказаться очень сложными и утомительными. Но в 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.

2. Общий план

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

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

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

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

3. Реализация ядра GC

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

3.1. Пролог

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

{
  GCTraceTime(Info, gc) time("Step 0: Prologue", NULL);

  // Выделить память на битовую карту меток. Существует несколько причин сделать это
  // до начала цикла: память не тратится, если нет сборки, память
  // «очищается» при первом использовании, а незатронутые части карты отображаются
  // на нулевую страницу, улучшая производительность на разреженных кучах.
  if (!os::commit_memory((char*)_bitmap_region.start(), _bitmap_region.byte_size(), false)) {
    log_warning(gc)("Could not commit native memory for marking bitmap, GC failed");
    return;
  }

  // Хорошо разгребаемой кучи для этого алгоритма не нужно, но хочется,
  // чтобы потоки отдали нам свои текущие TLAB-ы.
  ensure_parsability(true);

  // Сообщить разным системам рантайма о том, что мы делаем GC.
  CodeCache::gc_prologue();
  BiasedLocking::preserve_marks();

  // Косвенные ссылки будут заново искаться на фазе маркировки.
  // Нужно почистить и активировать таблицу для них.
  DerivedPointerTable::clear();
}

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

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

Не путайте TLAB и java.lang.ThreadLocal. С точки зрения 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 «вершинами» являются объекты, а «рёбрами» — ссылки между ними.

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

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

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

Глядите, 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. Подключаем GC к VM

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

Помните, нужно обойти специальные, достижимые ссылки из VM? Можно попросить каждую специальную подсистему VM обойти ссылки, спрятанные от остальных Java-объектов. Исчерпывающий список таких корневых элементов в текущей 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. Сейфпоинты и остановка мира

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

Хорошо, что мы научились делать GC по запросу, но ещё лучше, чтобы GC реагировал на переполнение кучи, когда памяти уже не осталось. На самом деле, достаточно заменить большую часть вызовов allocate_work на вот эту удобную обёртку, которая запускает 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;
}

Вот и всё!

5. Сборка

Наш патч без проблем должен накатываться поверх свежего репозитория 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

6. Тестирование

Как проверить, что наша реализация 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 сборке со включенной верификацией. Не сломалось? Уже можно на что-то надеяться.

7. Производительность

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

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

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

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

Вау, 2 миллисекунды. Это потому, что большая часть объектов в молодом поколении мертва, и такому GC здесь нечего делать. Если же мы выключим в -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

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

8. Что дальше?

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

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

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

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

   
   

9. Выводы

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

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

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