Можно писать на Java, вообще не задумываясь, как работает сборка мусора: «ну оно же там само собой происходит как-то». Однако разобраться как следует — не только интересно, но и полезно: например, какой из подходов к GC лучше соответствует конкретно вашему проекту?

На нашей конференции JPoint 2024 был доклад Дмитрия Силина (Сбер) об этом, участникам он понравился, и мы решили сделать для Хабра текстовую версию. Публикуем и текст, и видеозапись.

JVM и области взаимодействия

Поговорим о том, как уживаются Java-приложения и сборщик мусора, и постараемся выстроить цельную картинку. А уживаются они внутри виртуальной машины Java, которая запущена в операционной системе и представляет собой процесс.

В рамках процесса работают потоки. Часть выполняет бизнес-логику приложения, часть — собирает мусор.

Потоки конкурируют за разделяемые ресурсы, такие как CPU, доступы к памяти. Есть и то, что их объединяет, — управляемая память, aka managed heap. Когда кусочки памяти перестают быть достижимыми в программе, сборщик мусора сам позаботится об их освобождении. Достижимость определяется ссылками — они и есть точки соприкосновения GC и приложения. Взаимодействие с ними описывает возникающие конфликты.

Применительно к классическому многопоточному приложению есть два фундаментальных подхода:

• Один построен на примитивах синхронизации, различных блокировках, в виртуальной машине есть некоторый аналог mutex. Этот режим называется «stop the world» (STW). С ним ассоциировано понятие safepoint.

• Другой — неблокирующие алгоритмы, lock-free. Он построен на абстракции «барьер», и этот режим называется concurrent, то есть сборщик мусора работает одновременно с приложением.

Разберём поочерёдно оба.

Mutex и JVM

Когда сборщик понимает, что память заканчивается, ему нужно собрать мусор. Он останавливает приложение, захватывая некоторые mutex’ы. Находит живые объекты, куда-то перекладывает их по своей логике. Потом сборщик мусора обновляет все ссылки, до которых может добраться приложение, чтобы они указывали на новые места перемещенных объектов, и возвращает управление приложению. Для приложения это выглядит как точка: всё шло себе, в определенный момент остановилось, постояло и запустилось дальше. Поэтому и называется safepoint, «безопасная точка». В более широком смысле это означает, что мы не исполняем Java-код во время сборки мусора.

Safepoint — очень базовый механизм виртуальной машины. На конференции JavaOne спикер сравнил его с «мандалой» виртуальной машины, это такая «центральная точка симметрии», потому что многие подсистемы построены вокруг него.

А Safepoint — это тот самый «stop the world»: пришли в эту точку и выполняем там какую-то операцию (сборку мусора или что-то ещё).

Обсудим, как устроен механизм достижения safepoint. У каждого Java-потока есть свой mutex, который называется jvm_lock. Перед тем, как собрать мусор, сборщик пытается привести всех к safepoint, захватывая эти jvm_lock’и. В этой задаче сборщику мусора помогает специальный поток JVM — VM-поток, именно он собирает все потоки на safepoint, захватывая их jvm_lock’и. Собрав всех, VM-поток передаёт управление GC для сборки мусора. После сборки VM-поток отпустит jvm_lock'и, и Java-потоки продолжат исполнение.

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

[1] Если Java-поток не владеет jvm_lock, то потоку нельзя трогать управляемую память, исполнять Java-код. Он вынужден ждать, когда jvm_lock освободится.

Кое-что он может продолжать делать и без jvm_lock 'а — например исполнять нативный код, провалившись в JNI. Нативный код знать не знает про управляемую память. Есть исключения (JNI Critical), но речь сейчас не о них. Другой пример работы, где потоку не требуется jvm_lock, — выполнение тяжеловесных операций, которым не нужны ссылки на управляемую память внутри самой JVM. Например, когда мы запрашиваем выделение физических страниц у операционной системы.

[2] Если Java-поток владеет jvm_lock, тогда всё хорошо, можно работать с объектами в управляемой памяти: читать, писать, исполнять Java-код. Это нормальное состояние Java-потока, в котором он проводит большую часть времени.

Для того, чтобы VM -поток мог захватить jvm_lock’и потоки, каждый Java-поток регулярно проверяет, не надо ли отдать jvm_lock. Такие проверки называются safepoint poll. Посмотрим, как они выполняются в коде.

Safepoint poll [interpreter]

Исполнять Java-код можно разными способами: в интерпретаторе, в C1, С2. Интерпретатор наиболее наглядный. 

Интерпретатор генерирует фрагменты кода, которые умеют обрабатывать конкретные байт‑коды. Диспатчер читает байт‑код, передает управление нужному обработчику, тот обрабатывает байт-код и возвращает управление и так далее.

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

Примеры взяты из JDK22 sources.

В интерпретаторе есть функция, которая генерирует обработчик байт-кода goto().

void TemplateTable::_goto() {
	transition(vtos, vtos);
	branch(false, false);

Идем вглубь:

void TemplateTable:branch(bool is_jsr, bool is_wide) {
…
	__dispatch_only(vtos, true);
	…
}

Аргумент всегда true.

Попадаем в диспатчер:

void InterpreterMacrosAssembler::dispatch_only(
				TosState_state,
				bool generate_poll {
	dispatch_base(state,
			Interpreter::dispatch_table(state),
			true,
			generate_poll);
}

Видим, что аргумент, который передали в качестве true, разрезолвится вgenerate_poll.

Доходим до генератора. В терминах макроассемблера мы генерируем код сниппета, который обрабатывает наш байт-код goto().

void InterpreterMacroAssembler::dispatch_base(...,
						bool generate_poll {
…
Label no_safepoint, dispatch;
if (table != safepoint_table && generate_poll) {
	NOT_PRODUCT(block_comment(“Thread-local safepoint poll”)):
	test(Address(r15_thread, JavaThread::polling_word_offset()),
			SafepointMechanism::poll_bit());

    jccb(Assembler::zero, no_safepoint);
    lea(rscratch1, ExternalAddress((address)safepoint_table));
    jmpb(dispatch);
  }
  …
}

Если стоит флажок generate_poll, мы идем вглубь и смотрим переменную r15_thread. В виртуальной машине с каждым Java-потоком ассоциирован некоторый C++ объект, он описывает поток. В нем есть бит, который выставляет верный поток, когда вы просите прийти на safepoint. То есть он вводит бит, а поток его периодически проверяет. Если бит не стоит, то все хорошо — прыгаем на no_safepoint. Если бит стоит, то идем в другую таблицу, где те же самые обработчики, но в них вставлен реальный safepoint poll, который приведет нас в С++ код на JVM. По сути, мы проверили флажок, а дальше уходим в С++, если он срабатывает.

Механизмы синхронизации

Давайте визуализируем то, что мы обсудили. Нашему safepoint предшествует процедура прихода туда. Когда GC решил собрать мусор, он попросил VM thread собрать всех на safepoint. Через некоторое время потоки остановились, это называется time to safepoint (TTSP), и его можно увидеть в GC-логах. В Azul это считали частью паузы, потому что поток мог остановиться в самом начале, и паузой для него будет суммарно TTSP и время на самом safepoint. 

Рассмотрим пример, где кружками обозначены safepoint poll’ы. Они не обязательно находятся на равном расстоянии. Их стараются расставлять часто, чтобы TTSP не был большим, но интервалы условно случайные.

Нижний поток, на картинке выше, выполняет обычный Java-код. После того, как GC решает собрать мусор, этот поток на ближайшем safepoint poll останавливается и блокируется. Зачет идет по последнему пришедшему: как только все потоки заблокировались, начинается сам safepoint. 

Как еще может быть? Посмотрим на средний поток: он в какой-то момент отпустил jvm_lock и ушел в натив (красный пунктир). Мы вызвали код на С++, который знать не знает ни о каком safepoint. Тогда VM-поток приходит к этому потоку, видит, что его jvm_lock свободен, и забирает его себе. На этом можно считать, что Java-поток готов к safepoint. Если он решит вернуться в процессе выполнения safepoint операции, из натива в Java, то первым делом ему потребуется захватить собственный jvm_lock. Однако этот jvm_lock уже захвачен VM-потоком, соответственно, поток будет вынужден ожидать, то есть встанет на паузу. В конце safepoint, на синей отметке, VM-поток отпустит jvm_lock. Java-поток заберет его и продолжит исполнение.

И верхний пример: если же Java-поток ушел очень глубоко в натив и не возвращался, пока был safepoint, то он его в принципе не заметил. Он спокойно работал. В это время к нему пришел VM thread, взял jvm_lock, произошел safepoint, мы сделали сборку мусора, вернули jvm_lock обратно. Если Java-поток в будущем решит вернуться в Java-код, то lock будет свободен, никаких пауз для него не возникало.

Stack

Когда мы говорим, что в какой-то момент jvm_lock взят или не взят, то это моментальное состояние. Также у нас есть стек, который соответствует нашему исполнению. Где-то мы вызываем Java-код, дальше можем вызвать JNI-код, из него getter в Java, потом вернуться. 

Когда мы попросили всех остановиться, они дошли до ближайшего safepoint poll и остановились:

Здесь JIT вызвал некоторый vm: resolve_call(), который сделал внутри себя safepoint poll. Внутри виртуальной машины тоже есть safepoint poll’ы. Виртуальная машина тоже работает с указателями на управляемую память. Когда нужно разрезолвить, куда пойдет вызов виртуальной java функции, мы достаём указатель на класс, указатель на метод, и это всё Java-объекты.

В определенный момент мы остановились, VM-поток всех собрал, GC-поток знает все Java-потоки и начинает их обходить.

// Thread Safe Memory Reclamation (Thread-SMR) support.
class ThreadsSMRSupport : AllStatic {
	…
	static ThreadsList* volatile _java_thread_list:
	…
}

Oop

Перед тем как продолжить, давайте познакомимся с понятием oop — ordinary object pointer, или дословно «обычный указатель на объекты». Это указатель, который обладает двумя свойствами:

• указывает на управляемую память;

• указывает на начало объекта.

Внутри виртуальной машины мы часто сталкиваемся с этой абстракцией, и для неё придумали специально имя «oop».

Find anchor

После того как GC собрал всех на safepoint, первым делом ему нужно найти все живые (достижимые) oop’ы. Для этого GC берет потоки по очереди и обходит каждый из них. У объекта, представляющего абстракцию thread в VM, есть функция обработки ссылок, которые лежат на фреймах: oops_do_frames(). Она начинает с проверки наличия Java-фрейма. Если его нет, то на этом все заканчивается. В противном случае указатель показывает на верхний Java frame в стеке. Начиная с него и пользуясь специальным API для обхода frame’ов, GC может обойти весь стек выбранного Java-потока. API обхода умеет «проскакивать» нативные frame’ы, которые могут быть на стеке вперемешку с Java frame’ами.

void JavaThread: :oops_do_frames(OopClosure* f,
					CodeBlobClosure* cf) {
if (!has_last_Java_frame()) {
	return;
}
…
// Traverse the execution stack
for (StackFrameStream fst(this, …);
				!fst.is_done();
				fst.next()) {
	fst.current()->oops_do(f, cf, fst.register_map()):
	}
}

Do frame

Когда мы дошли до конкретного фрейма, то вызываем аналогичную рутину oops_do() на конкретном фрейме: пожалуйста, обработай все Oop внутри фрейма.

void JavaThread::oops_do_frames(OopClosure* f, 
					CodeBlobClosure* cf) {
  if (has_last_Java_frame()) {
  return;
  }
  …
  // Traverse the execution stack
  for (StackFrameStream fst(this, …);
				!fst.isdone();
				fst.nest()) {
		fst.current()->oops_do(f, cf, fst.register_map());
  }
}

Frame structure

Ключевыми полями абстракции frame в JVM являются: 

• stack pointer, который указывает, где в памяти лежат ассоциированные с этим фреймом структуры;

• program counter, следующий после вызова, который помогает понять, какой код работал.

class frame {
	// stack pointer
	// from Thread::last_Java_sp
	intptr_t* _sp;

	// program counter
	// the next instruction after the call
	address    _pc;
	…
};

Inside frame

Заглянем глубже в поиск oop’ов внутри frame. Здесь стоит проверка: какой это фрейм? Кто его сгенерировал? По program counter мы можем понять, был ли это интерпретатор, С1, С2, потому что мы сами сгенерировали этот код и знаем, по каким адресам он лежит.

void frame::oops_do_internal(OopClosure* f,
				CodeBlobClosure* cf,
				…) const {
  …
  if (is_interpreted_frame()) {
		oops_interpreted_do(f, …);
  } else if (is_entry_frame()) {
	oops_entry_do(f, map);
  } else if (is_upcall_stub_frame()) {
	_cb->as_upcall_stub()->oops_do(f, *this
  } else if (CodeCache::contains(pc()) {
	oops_code_blob_do(f, cf, derived_
  } else {
	ShouldNotReachHere();
  }
}

Идем глубже и для каждого вида знаем layout этого фрейма и по каким смещениям в данный момент лежат oop’ы. Компиляторы генерируют oopmap, которая отвечает на эти вопросы. У интерпретатора свой контракт, и таким образом мы находим все oop’ы. В итоге GC может найти живые объекты на стеке. Таким же образом GC может обновить все эти oop’ы после перемещения, чтобы можно было отпустить поток после safepoint.

Есть еще VM-фреймы и JNI-фреймы. что с ними? Давайте познакомимся с понятием handle.

VM Handles

Handle — очень простое понятие, которое сообщает нам, что есть кусок памяти, в котором написан oop, некая обертка.

VM-фреймы не хранят в себе oop, а складывают их в так называемую Handle Area. Это такая «арена» с аллокатором и watermark, когда watermark разрушается, то всё аллоцированое после нее считается невалидным, и туда GC не ходит. Handle Area выделяется в c-heap (неуправляемой памяти), статична, и по ней GC может спокойно бегать. Приложение может через нее читать и получать актуальные oop’ы через dereference. Эта структура подвешена к Java-потоку.

Похожая история — JNI Handles. Они немного по-другому кодируются, есть strong handle и weak handle. Здесь нарезается Handle Block фиксированного размера, который потом нарезается на oop’ы.

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

Когда мы вызываем JNI-код и пытаемся отдать туда объект, то заворачиваем это в обертку, которая никуда не двигается. Указатель на эту обертку хранится у JNI-вызова. Если он решит его разыменовать, то ему придется вызвать Java. Он возьмет обратно jvm_lock, и ему разрешат разыменовывать указатель на управляемую память. Сам нативный код этого делать не должен. 

Структуры VM Handles и JNI Handles подвешены не к самим фреймам, а к объекту Java-потока. Давайте посмотрим, как они обходятся. 

Do no frames

По аналогии с oops_do_frames() у VM, у Java-потока есть другая функция: это C++ код самой JVM, который говорит «обработай oop’ы, которые не лежат на фреймах». 

void JavaThread::oops_do_no_frames(
				OopClosure* f,
				CodeBlobClosure* cf) {
	…
  // Traverse the GCHandles
  Thread::oops_do_no_frames(f, cf);

  if active_handles() != nullptr) {
		active_handles()->oops_do(f);
  }
  …
}

Она делает много всего. Мы посмотрим два основных момента, где лежит большинство oop’ов. Она вызывает в базовом классе oops_do_no_frames. Если мы заглянем внутрь, то увидим ту самую handle_area, где лежат VM-Oop’ы и handle’ы, ассоциированные с ее фреймами.

void Thread::oops_do_no_frames(
				OopClosure* f,
				CodeBlobClosure* cf) {
	// Do oop  for ThreadShadow
	f->do_oop((oop*)&_pending_exception);
	handle_area()->oops_do(f);
}

Есть ещё active_handles. Не очень говорящая штука, но если мы заглянем внутрь, то увидим, что это тот самый JNIHandleBlock.

class JavaThread: public Thread {
	…
	// Active_handles points to a block of handles
	JNIHandleBlock* _active_handles;
	…
}

Таким образом, мы увидели, как GC может найти все oop'ы, ассоциированные с определенным Java-потоком. О чем это говорит? Мы остановили приложение, нашли все oop’ы, собрали мусор, всё актуализировали, выпустили приложение. Дальше оно может бесшовно работать. Да, значения будут другими, но сырое значение указателя никак не доступно в Java.

Checkpoint = thread-local handshake (JEP 312)

В завершение первой части хочется рассказать о чекпойнте, или thread-local handshake. Он пришел к нам с JEP 312 в Java 10 вместе с ZGC. Теперь используется много где для оптимизации.

Суть в том, что не всегда обязательно останавливать все потоки, чтобы выполнить операцию. Иногда можно просто сделать операцию над потоком. Это реализует чекпойнт. Те же самые механизмы входа: мы взводимв тот же бит, и на следующем safepoint poll поток замечает, реагирует на это, и бит прыгает в С++ код, где мы проверяем, хотим ли мы safepoint или checkpoint. Если хотим второе, то выполняем операцию и отпускаем поток, а дальше он продолжает работать. Да, у него есть пауза на работу чекпойнта. Если поток был в нативе и решил вернуться к чекпойнту, то все хорошо: он взял jvm_lock, увидел этот бит, отработал операцию и продолжил исполнение.

Если поток долго не возвращается, то к нему опять приходит VM-поток, забирает у него lock, делает за него операцию. И сейфпойнт, и чекпойнт можно сделать «за поток». Если в момент, когда VM-поток делал операцию, Java-поток решил вернуться из натива, то мы понимаем, что jvm_lock взят, останавливаемся. Прелесть в том, что длина паузы не превышает длину операции. Снова зачет по последнему: как только мы забираем последний lock, чекпойнт заканчивается. 

Мы поговорили о том, что такое режим stop the world, как он достигается, как происходит синхронизация между Java-приложением, как оно останавливается, как выглядит пауза (по сути это safepoint + time to safepoint). Также мы обсудили, что делает GC и что такое checkpoint.

Переходим ко второй части.

Часть 2: алгоритмы lock-free, барьеры и concurrent-режим 

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

В контексте виртуальной машины и доступа к управляемой памяти барьеры появляются, когда мы загружаем значение (то есть это load-барьеры или read-барьеры) или когда сохраняем его (есть pre-store и post-store, то есть перед тем или после того, как записали). Рассмотрим на примере.

oop load_oop(oop* addr) {
	oop x = *addr;
	… load  barrier …
	return x;
}

void store_oop(oop val, oop* addr)
} … pre-store barrier …
	*addr= val:
	… post-store barrier …
}

Барьеры не связаны со сборщиком мусора напрямую. Давайте рассмотрим несколько примеров.

Compressed oops (-XX:+UseCompressedOops)

Представим, что у нас есть объект с заголовком и полями — int, пара oop-указателей, еще пара int... На 64-битной платформе указатели занимают 64 бита, а хотелось бы поменьше — чтобы heap получался поменьше, оперативной памяти требовалось меньше, чтобы были дешевле сервера... Как вместо 64 битов можно хранить 32?

Во-первых, младшие три бита обычно нули. В виртуальной машине используется natural alignment, который требуется, чтобы операции над полями были атомарными с точки зрения процессоров. Alignment управляемый, то есть его можно задать флажком, но по умолчанию три последних бита не используются. Их можно не хранить. Если мы добавляем еще 32 бита, которые мы будем хранить, мы получаем 35 битов. Они позволяют нам адресовать 32 ГБ адресного пространства. 

Также есть фокус со старшими битами. Они называются базой/смещением/сдвигом и позволяют избежать пересечения с объектами, которые были выделены в виртуальном адресном пространстве в процессе загрузки JVM до того, как JVM добралась до резервирования пространства под Java heap. Перед резервированием Java heap мы находим и фиксируем для этого процесса JVM такое значение сдвига, чтобы интервал [base, base + 32GB] был полностью свободен.

Посмотрим на примере псевдокода, как выглядит этот барьер. Местами ниже реальный код, местами псевдокод. 

oop load_oop(narrowOop* addr) {
	narrowOop x = *addr;
	oop val = compressedOops::base()
        + ((oop)x << CompressedOops::shift())
    return val;
}

void store_oop(oop val, oop* addr) {
	narrowOop x = (val - CompressedOops::base())
		>> CompressedOops::shift();
	*addr = x;
}

Когда мы загружаем oop, то читаем 32-битное значение, сдвигаем его на эти три бита (CompressedOops::shift()) и добавляем к нему базу (CompressedOops::base()). Если хотим сохранить, то вычитаем базу, делаем shift, получаем 32-битное значение, записываем его в память. Но этот код обычно не вызывается: и в интерпретаторе, и в С1, и в С2 барьеры инлайнятся в код. 

Cross generation references

Еще одна история про барьер — ссылки между поколениями. Напомню контекст.

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

Для борьбы с этой неэффективностью придумали разделить объекты на поколения — долгоживущие (old gen) и молодые (new gen). Появился новый формат сборки мусора, когда мы предполагаем, что все долгоживущие объекты живы, и не обходим их. Чтобы правильно обойти молодые объекты, нам как-то надо знать все ссылки, ведущие из долгоживущих в молодые.

Для этого, когда мы создаем ссылку из old gen в new gen, нам надо это запомнить.

void store_oop(oop val, oop* addr) {
	*addr = val;
	if (Oop::is_old(addr) && Oop::is_new(val)) {
		… add to remembered set …
  }
}

Это пример store-барьера. Если мы пишем в поле объект из old gen, значение из new gen, то мы это запоминаем. Нам ещё встретится этот псевдокод далее.

Откуда берутся барьеры

Посмотрим снова на примере интерпретатора. В частности заглянем в реализацию байт-кода aastore, который сохраняет объект в массив объектов. 

TemplateTable:: aastore() //templateTable_x86.cpp
do_oop_store() //templateTable_x86.cpp
MacroAssembler::store_heap_oop() //templateTable_x86.cpp
MacroAssembler::access_store_at() { //templateTable_x86.cpp
	…
	BarrierSet::barrier_set()->barrier_set_assembler()->store_at(...)
	…
}

ZBarrierSetAssembler::store_at() //zBarrierSetAssembler_x86.cpp

Мы видим, что эта история платформоспецифичная, здесь она у нас под x86, работа ведется в терминах ассемблера. Через несколько прыжков попадаем в функцию, которая говорит «MacroAssembler, сгенерируй нам store».

MacroAssembler обращается к глобальной переменной barrier_set, которая содержит все активные барьеры виртуальной машины. Он говорит: «barrier_set, пожалуйста, сгенерируй ассемблер для стора». GC, который был инициализирован, в момент запуска виртуальной машины прописал себя в barrier_set. Если, например, у нас был ZGC, то мы попадем в ZBarrierSetAssembler::store_at(). 

А это реальный код:

void ZBarrierSetAssembler::store_at(...)
	//Do ZGC work
	{
		store_barrier_fast(...)
		…
		store_barrier_medium(...)
		…
		__ MacroAssembler::call_VM_leaf(..., ZBarrierSetRuntime::
			store_barrier_on_oop_field_without_healing_addr());
		…
	}
	__ bind(done);
	// Store value
	BarrierSetAssembler::store_at(masm, …);
}

Мы видим два крупных блока. Начнем со второго. 

Второй — это generic-барьер. Вызываем базовый класс BarrierSetAssembler и просим его сгенерировать store. Здесь будут сгенерированы барьеры для compressed oops (хотя с ZGC они несовместимы, а почему — обсудим позже). В этом шаге выполняются общие барьеры VM. 

А ZGC выполняет специфичную работу в первом блоке, в prestore-барьере. Здесь мы можем увидеть термины fast path и medium path. Fast path — это когда мы быстро проверили, нужно ли что-то делать или можно идти дальше. Medium path — это когда нужно что-то сделать, но это достаточно просто, чтобы мы могли запрограммировать это на ассемблере. 

Конечно, там не совсем ассемблер, а обертки вокруг него; уровень инструкций, которые пишет JVM-разработчик, — это lea (load effective address), movptr, xorq, lock, pop, push. То есть это кодогенератор, и его очень сложно писать и поддерживать, еще и под каждую платформу. И если логика становится очень сложной, то мы из сгенерированного кода вставляем jump в код на C++. 

Через несколько прыжков мы попадаем в самый медленный путь. 

ZBarrierSetRuntime::store_barrier_on_oop_field_without_healing_addr()
ZBarrierSetRuntime::store_barrier_on_oop_field_without_healing()
ZBarrier::store_barrier_on_heap_oop_field()
ZBarrier::heap_store_slow_path // zBarrier.cpp

zaddress ZBarrier::heap_store_slow_path(...) {
	ZStoreBarrierBuffer* buffer = 
ZStoreBarrierBuffer::buffer_for_store(heal);
	if (buffer != nullptr) {
		// Buffer store barriers whenever possible
		buffer->add(p, prev);
	} else {
		mark_and_remember(p, addr);
	}
	return addr;
}

Здесь происходит барьер snapshot at the beginning, о котором мы поговорим чуть позже. Мы пытаемся сохранить ссылку, которую будем затирать. У потока есть локальный буфер, в который нужно записать старое значение. Если буфера нет, то нужно попытаться его создать и положить туда нашу информацию. Если не получилось, то для корректности работу всё равно придется сделать. То есть поток непосредственно делает нужную обработку объкта самостоятельно: помечает его живым и добавляет в глобальный буфер — mark_and_remember.

Marking

Теперь хочется поговорить о барьерах на примерах реального concurrent marking, но сначала вспомним, что такое marking. 

Допустим, мы работаем в режиме stop the world, то есть останавливаем приложение. Есть root set, куда входят те самые Java-потоки, которые мы посмотрели, их стеки, регистры. Мы начинаем обходить oops, которые там лежат. Они описывают граф в оперативной памяти, которая у нас лежит в части, замаппленной под Java heap. Здесь используется классический алгоритм, который используют почти все коллекторы: красим вершины в серый, объявляем их как working set, из working set берем элементы, помечаем их как живые, раскрашивая в черный, добавляем всех соседей в working set. Таким алгоритмом обходим весь граф и находим живые объекты, то есть достижимые из root set.

При переходе к сценарию concurrent marking, то есть marking одновременно с работой приложения, в игру вступают потоки.

Они могут создать новое ребро BD, а могут стереть существующее CD, например, в ref1 записать null или другое значение, отличное от D. Без дополнительной синхронизации возможно, что сборщик мусора замер в каком-то состоянии, пришел Java-поток и сделал изменения, после которых классический алгоритм поиска живых объектов перестаёт работать. Вершину В мы уже посетили, и вершину D никак найти не сможем. Далее рассмотрим пару способов борьбы с такими ситуациями с помощью барьеров в реальных сборщиках мусора.

SATB

Snapshot at the beginning — очень популярная история в OpenJDK. Сегодня ее использует G1, Shenandoah и ZGC, CMS — все, кто делают concurrent marking. 

Идея очень простая. Мы начинаем concurrent marking на safepoint, обходим roots на паузе. У нас есть graph, давайте его зафиксируем и сделаем полностью доступным для сборщика мусора. Когда поток что-то стирает, то мы запомним, что он стер ребро CD, и скажем об этом GC. Когда придет коллектор и будет обходить вершину С, то он увидит, что нет прямого ребра CD, но вершина лежит в дополнительной структуре, и нам про нее известно. Таким образом он найдет вершину D и пометит её живой. 

С точки зрения псевдокода все максимально просто:

void store_oop(oop x, oop* addr) {
	GC::remember(/*from*/addr, /*to*/*addr);
	*addr = x;
}

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

LVB

Вторая история основана на load value barrier, используется в GPGC(C4) Azul Prime.

Чтобы Java-поток нарисовал новую ссылку, он должен сначала «взять» объект, в который ссылка будет вести. В этот момент «взятия» поток сообщает о нём сборщику мусора. Таким образом, все новые ссылки, которые будут нарисованы, ведут на живые объекты, о которых знает GC.

В итоге объекты либо новые и живые, либо они часть старого графа, то есть графа, который был в момент начала сборки мусора. Последние, если они должны быть помечены как живые, должны быть достижимы по рёбрам (либо старым, либо новым).

Если последнее ребро в маршруте достижимости из списка «старых» рёбер, то их находит классический алгоритм. Если из «новых», то какой-то Java-поток «брал» этот объект и сообщал о нем сборщику мусора. Концепт очень удобен тем, что у Java-потока все «взятые» указатели, то есть на регистрах и на стеке, находятся в актуальном состоянии. На уровне псевдокода барьера это выглядит так:

oop load_oop(oop* addr) {
	oop x = *addr;
	GC::mark(x);
	return x;
}

Читаем значение, велим GC запомнить. Возвращаем значение и продолжаем работать.

Сравним два подхода:

SATB — продуктовый подход, который используется в ZGC, Shenandoah, CMS. Хорош тем, что работа выполняется на store-операциях. В целом наши программы устроены таким образом, что мы зачитываем много данных, обрабатываем и выдаем, то есть сохраняем, результат меньшего размера. Так как источником store-операции является Java-программа пользователя, то наблюдения обычно справедливы. Таким образом store’ов обычно существенно меньше, чем load’ов, и делать дополнительную работу каждый раз амортизировано выгоднее на store, чем на load-барьере.

LVB хорош тем, что если мы говорим про concurrent marking, то 500 GB heap — вполне продуктовая история. Marking может длиться порядка сотни секунд, и в это время объекты продолжают умирать, то есть перестают быть достижимыми. Однако если используется подход snapshot at the beginning, то он не дает умереть объекту, который был в изначальном графе. А в LVB-подходе умершие объекты могут быть не найдены коллектором и будут собраны как мусор. Потенциально при таком подходе больше собранного мусора, и сборку можно делать реже.

Стоимость барьеров

Поговорим о стоимости барьеров. Есть fast path, когда мы проверяем, надо ли что-то делать или нет, а есть slow path, когда нужно что-то сделать. Иногда есть medium path, но о нем в этот раз говорить не будем. Fast path по моему опыту стоит 1–10%. Хотя это зависит от барьера, приложения и компилятора.

Много это или мало? Что сделано в JVM для того, чтобы fast path был быстрым? Поговорим о colored oops, nopping и self heal.

Colored oops

Рассмотрим платформу x64, платформу с 64-битными указателями. Oop — это указатель, то есть адрес начала объекта управляемой памяти. Предположим, что мы можем зарезервировать несколько битов в этом указателе под свои нужды. Что бы мы могли туда положить?

Например, мы можем сохранить информацию, сообщали ли мы сборщику мусора об этом объекте на текущем цикле сборки или нет. Можем сохранить информацию, к какому поколению принадлежит объект new/old.

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

Для is_old легко добиться консистентности, чтобы все ссылки показывали правильное значение. Если делать явное перемещение объекта между поколениями, то в момент «актуализации» ссылки мы будем вынуждены искать запись о том, куда был перемещён объект. Поскольку поток перемещаемых объектов относительно мал, мы можем себе это позволить. А вот с is_marked обычно добиться консистентности сложно. Так как обходим мы весь граф, то объектов много, и в этом случае они не «перемещаются». В какой-то момент мы помаркали объект, но не можем мгновенно обновить сотню других ссылок на него. С этим можно жить. То есть если на ссылке написано, что объект помаркан, то его уже не нужно смотреть — оптимизация! Если не написано — посмотрим, в итоге вызовем mark столько раз, сколько ссылок ведёт в этот объект. И то, только если Java-поток попробует доступиться через них до объекта.

Вернемся к нашему указателю. Он указывает на виртуальную память, которая через специальную структуру PageTable резолвится в физический. PageTable уникальна для процесса и заполняется операционной системой. У нее есть четкая спецификация, потому что процессор должен понимать, как ходить по этой структуре. Указатель на структуру PageTable хранится в специальном регистре. 

Процессор идет в эту таблицу, когда ему требуется прочитать память по виртуальному адресу, находит там mapping, который показывает, какая физическая страница соответствует целевому виртуальному адресу. Layout может быть устроен по-разному, есть четырех- и пятиуровневые структуры. Пятиуровневая структура более молодая. Четырехуровневая больше о продакшене. Давайте посмотрим на нее в деталях.

Четырехуровневая структура организации памяти позволяет нам использовать 48 битов как адрес нашего указателя. Старшие биты зарезервированы системой. 

Если мы воспользуемся битами не из этих 48, то каждый раз перед тем как делать доступ, нам придется стирать или маскировать свои биты, иначе при попытке доступа процессор будет генерировать сигналы о нарушении состояния зарезервированных битов. Маскирование действительно создает дополнительные накладные расходы, но такой подход активно используется, например, в ZGC. В Risc-V процессорах рассматривают возможность резервирования битов под нужды приложения — Pointer Masking.

Можно и по-другому: воспользоваться битами из числа 48. В этом случае мы немного пожертвуем адресным пространством, но у нас остаётся всё ещё довольно много, так как 48 битов давали нам возможность адресовать 256 ТБ. Это значительно больше, чем физический объем оперативной памяти в большинстве систем.

Как это работает? Посмотрим на адресное виртуальное пространство между адресами 0xCA0000000000 и 0xCAFFFFFFFFFF. Они задают некоторый диапазон виртуального пространства в 1 ТБ. Следом идёт 0xCB0000000000 и 0xCBFFFFFFFFFF в 1 ТБ. И так далее.

В Linux есть механизмы, которые позволяют нам добавлять в PageTables записи, где несколько страниц из виртуального адресного пространства ставятся в соответствие одной и той же странице физической памяти. Этот механизм называется multi-mapping и доступен через mmap с флагом MAP_SHARED.

В терминах нашего указателя это значит, что если мы замаппили все виртуальные диапазоны на один физический, то можем писать любые значения в биты, которые влияют на номер диапазона. Здесь хочется сослаться на предыдущие слайды, где мы говорили, что ZGC не работает с compressed oops. Compressed oops сжимает указатель всего до 32 битов. То есть у нас их не 48, а всего 32+3. Если какие-то мы резервируем под свои нужды, то каждый бит в два раза уменьшает объемы адресуемой памяти. Так как в compressed oops мы можем адресовать только 32 ГБ виртуального пространства, то когда мы зарезервируем 4 бита, максимальный размер уменьшается в 16 раз, и максимально возможный heap станет 2 ГБ, что очень мало.

Как зарезервированные биты помогают оптимизировать fast path? Давайте вспомним барьер, где мы пытались сохранять ссылки из old в new:

void store_oop(oop val, oop* addr) {
	*addr = val;
	if(Oop::is_old(addr) && Oop::is_new(val)) {
		… add to remembered set …
	}
}

Мы хотели проверить, принадлежит ли объект, в котором мы пишем, к old generation. Эта информация должна где-то лежать. Может, надо сходить в HashMap и что-нибудь поискать. А что, если мы это напишем на самом адресе? Он уже у нас уже зачитан при входе в функцию, ничего из памяти читать будет не надо:

void store_oop(oop val, oop* addr) {
	*addr = val;
	if ((addr & Oop::is_old_bit) && (val & Oop::is_new_bit)) {
	… add to remembered set …
	}
}

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

Self heal (LVB)

Работает на slow path, но ускоряет fast path. Давайте вспомним псевдокод, который использовался в LVB:

oop load_oop(oop* addr) {
	oop x = *addr;
	GC::mark(x);
	return x;
}

Мы сказали GC, что надо помаркать объект, и двигаемся дальше. 

oop load_oop(oop* addr) {
	oop x = *addr;
	// check color
	if (!(x & GC::marked_bit)) {
		GC::mark(x);
		// self heal
		cmpxcng(addr, x, x | GC::marked_bit);
	}
	return x;
}

Здесь мы применили комбинацию colored oops и self heal. При помощи colored oops мы зарезервировали бит, который будет говорить, помаркан ли целевой объект. Если бит выставлен, то дополнительных действий не требуется. Если нет, то сообщаем сборщику мусора об объекте, а потом при помощи атомарной операции cmpxchg выставляем наш служебный бит. Таким образом, при следующем чтении объекта по этой ссылке сработает быстрый путь.

Да, ссылок может быть сотня. По каждой из ссылок мы придем и попытаемся отдать объект коллектору, он разберется. Но зато по каждой ссылке мы сделаем это всего один раз. Такая вот классная оптимизация.

NOP LVB

У нас есть абстрактный барьер, связанный с GC. Мы читаем trap_mask, которая меняется каждый раз, проверяем текущий oop. Если где-то биты пересекаются, то нужно что-то с этим делать и наворачивать дополнительную логику.

oop load_oop(oop* addr) {
	oop x = *addr;
	if (x & GC::trap_mask) {
		GC::lvb_slowpath(addr, x);
	}
	return x;
}

А если GC не работает, нам вообще надо что-то проверять? Если это барьер, чтобы хранить ссылки между несколькими поколениями, то нам, конечно, придется исполнять барьеры. Но барьеры, ассоциированные с маркингом, исполнять не нужно. Мы можем их выключить!

oop load_oop(oop* addr) {
	oop x = *addr;
	if (x & GC::trap_mask) {
		GC::lvb_slowpath(addr, x);
	}
}

А как их выключить? Мы же сами сгенерировали код с этим барьером, интерпретатор, С1, С2. Мы могли положить его по выровненным адресам, а потом атомарно пропатчить. Мы патчим на специальные инструкции — nop, которые ничего не делают. Раньше там была загрузка (trap_mask) и условный переход (if). Их убрали и вставили nop.

Мы не убрали весь overhead от барьера. Остались nop’ы, которые все равно едят некоторое количество процессорного времени, да и сам барьер немного мешал компиляторам в плане оптимизации, когда мы изначально создавали этот код. Если бы барьера изначально не было, возможно, компилятор справился бы ещё лучше.

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

Что в итоге

Как соотносятся STW и concurrent-сборщики мусора? В общем случае это компромисс между throughput и latency. STW-коллекторы всегда дают лучший throughput, потому что они делают работу, когда остальное приложение на паузе, и таким образом им нужно меньше работы для синхронизации с приложением. 

С другой стороны, concurrent-коллекторы прекрасны тем, что у них лучше latency. Однако им приходится заботиться о синхронизации с приложением, чтобы работать одновременно с ним.

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

Когда мы включаем concurrent-коллектор, то сразу получаем до 10% ухудшения пропускной способности, то есть увеличения длительности бизнес-операции за счет того, что выполняем барьеры fast path.

Если операция пересечется с циклом GC, то стоимость издержек начнет расти, можно получить и 30%. Но процентами легче управлять: оптимизировать код, выставлять с запасом SLA. В общем, история процентная, и этим она прекрасна. В итоге время пропорционально сложности бизнес-операции.

С STW-коллекторами ситуация иная: в момент операции может появиться GC-пауза или даже несколько. Она зависит не от длины бизнес-операции, а от размера heap. 

Поэтому обращайте внимание на следующее:

• длительность бизнес-операции; 

• SLA;

• какой результат хотите получить.

Хочется сказать еще об одной особенности, которая, казалось бы, не относится напрямую к GС-алгоритмам, — CPU starvation. Приложения обычно работают в рамках какого-то контейнера с ограничением на используемые CPU. В случае STW приложение останавливается, и все CPU-ядра становятся доступны коллектору. Он может собирать мусор на полной скорости. В случае concurrent-коллекторов потоки GC начинают конкурировать за CPU с потоками приложения. В случае нехватки планировщик вынужден периодически вытеснять некоторые процессы, и они не получат времени.

А раз бизнес-операцию не выполняют, то она не прогрессирует. Для примера допустим лимит в 10 CPU и наличие 10 активных потоков приложения. Что случится, если придёт GC и запустит ещё 5 потоков? Выделяемое планировщиком потоку время снизится со 10 / 10 = 100%, до 10 / (10+5) = 66.6%, т.е. на одну треть,, и мы получим дополнительно +50% к длительности бизнес операции только из за нехватки CPU.

В окружениях с достаточным количеством CPU и памяти concurrent-коллекторы показывают себя хорошо, устраняя связанные с паузами инциденты.