Документация Engee

Статические аннотации анализатора для правильной сборки мусора в коде на C

Проведение анализа

Вместе с Julia поставляется плагин анализатора. Его исходный код можно найти в src/clangsa. Для запуска плагина требуется выполнить сборку зависимости clang. Задайте переменную BUILD_LLVM_CLANG в файле Make.user, чтобы выполнить сборку соответствующей версии clang. Может также потребоваться использовать предварительно собранные двоичные файлы с помощью параметров USE_BINARYBUILDER_LLVM.

В качестве альтернативы (или если этого недостаточно) попробуйте использовать

make -C src install-analysis-deps

из каталога Julia верхнего уровня.

После этого для анализа дерева исходного кода достаточно выполнить команду make -C src analyzegc.

Общий обзор

Так как сборка мусора в Julia является точной, необходимо иметь правильную информацию о корнях для любого значения, на которое могут существовать ссылки на момент сборки мусора. Такие места называются безопасными точками (safepoints), а в локальном контексте функции это понятие распространяется на любой вызов функции, который может рекурсивно завершаться в безопасной точке.

В сформированном коде это происходит автоматически благодаря проходу размещения корней сборки мусора (см. главу о корнях сборки мусора в документации по формированию кода LLVM для разработчиков). Однако в коде на C среде выполнения необходимо сообщать о корнях сборки мусора вручную. Делается это с помощью следующих макросов.

// The value assigned to any slot passed as an argument to these
// is rooted for the duration of this GC frame.
JL_GC_PUSH{1,...,6}(args...)
// The values assigned into the size `n` array `rts` are rooted
// for the duration of this GC frame.
JL_GC_PUSHARGS(rts, n)
// Pop a GC frame
JL_GC_POP

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

Для обеспечения правильного использования этих макросов мы применяем статический анализ (в частности, статический анализатор clang). В оставшейся части этого документа дается обзор статического анализа и описываются вспомогательные действия, необходимые для работы базы кода Julia.

Инварианты сборки мусора

Правильность инвариантов определяется двумя условиями.

  • После всех вызовов GC_PUSH должен следовать соответствующий вызов GC_POP (на практике это реализуется на уровне функции).

  • Если значение ранее не было сделано корневым в какой-либо безопасной точке, в дальнейшем на него нельзя ссылаться.

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

  • какие вызовы являются безопасными точками, а какие нет;

  • какие значения являются корневыми в той или иной безопасной точке, а какие нет;

  • когда происходит обращение к значению.

В особенности что касается второго пункта: необходимо знать, какие области памяти будут считаться корневыми во время выполнения (то есть корневыми будут значения, присвоенные этим областям). Сюда входят области, явным образом назначенные таковыми путем их передачи в один из макросов GC_PUSH, области и значения, являющиеся корневыми на глобальном уровне, а также области, доступные рекурсивно из одной из таких областей.

Алгоритм статического анализа

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

Работа статического анализатора clang заключается в построении графа состояний и его исследовании на предмет источников ошибок. Несколько узлов этого графа создаются самим анализатором (например, для обеспечения порядка выполнения), но приведенные выше определения дополняют этот граф нашими собственными состояниями.

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

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

Аннотации анализатора

Эти аннотации находятся в файле src/support/analyzer_annotations.h. Они активны, только когда используется анализатор, и расширяются либо до nothing (для аннотаций прототипов), либо до холостых операций (для аннотаций наподобие функций).

JL_NOTSAFEPOINT

Это, пожалуй, самая распространенная аннотация. Ее следует добавлять к любой функции, которая, как известно, не приведет к достижению безопасной точки сборки мусора. Как правило, безопасными операциями для таких функций являются только арифметические вычисления, обращения к памяти и вызовы функций, которые либо имеют аннотацию JL_NOTSAFEPOINT, либо, по другим имеющимся данным, не являются безопасными точками (например, это может быть функция в стандартной библиотеке C, которая жестко задана как таковая в анализаторе).

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

Пример использования:

void jl_get_one() JL_NOTSAFEPOINT {
  return 1;
}

jl_value_t *example() {
  jl_value_t *val = jl_alloc_whatever();
  // This is valid, even though `val` is unrooted, because
  // jl_get_one is not a safepoint
  jl_get_one();
  return val;
}

JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY

Когда JL_MAYBE_UNROOTED аннотируется как аргумент функции, это означает, что данный аргумент может быть передан, даже если он не является корневым. При обычном ходе событий ABI julia гарантирует, что вызывающие объекты делают значения корневыми перед их передачей вызываемым объектам. Однако некоторые функции не следуют этому правилу ABI и позволяют передавать в себя значения, даже если они не корневые. Имейте в виду, что из этого не следует автоматически, что такой аргумент будет сохраняться. Аннотация ROOTS_TEMPORARILY дает более надежную гарантию того, что значение не только может переставать быть корневым при передаче, но и будет сохраняться вызываемой стороной между внутренними безопасными точками.

Обратите внимание, что JL_NOTSAFEPOINT фактически подразумевает JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY, потому что то, является ли аргумент корневым, не имеет значения, если функция не содержит безопасных точек.

Важно также отметить, что эти аннотации применяются как на вызывающей, так и на вызываемой стороне. На вызывающей стороне они снимают ограничение на корневой характер, которое обычно действует в отношении функций ABI julia. На вызываемой стороне они имеют обратный эффект: такие аргументы не считаются корневыми неявным образом.

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

Пример использования:

JL_DLLEXPORT void JL_NORETURN jl_throw(jl_value_t *e JL_MAYBE_UNROOTED);
jl_value_t *jl_alloc_error();

void example() {
  // The return value of the allocation is unrooted. This would normally
  // be an error, but is allowed because of the above annotation.
  jl_throw(jl_alloc_error());
}

JL_PROPAGATES_ROOT

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

Пример использования:

jl_value_t *jl_svecref(jl_svec_t *t JL_PROPAGATES_ROOT, size_t i) JL_NOTSAFEPOINT;

size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_svecref(svec, 1)
  // This is valid, because, as annotated by the PROPAGATES_ROOT annotation,
  // jl_svecref propagates the rooted-ness from `svec` to `val`
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_ROOTING_ARGUMENT/JL_ROOTED_ARGUMENT

Это по сути аналог JL_PROPAGATES_ROOT для присваивания. При присваивании значения полю другого значения, которое уже является корневым, присваиваемое значение будет наследовать корень значения, которому оно присваивается.

Пример использования:

void jl_svecset(void *t JL_ROOTING_ARGUMENT, size_t i, void *x JL_ROOTED_ARGUMENT) JL_NOTSAFEPOINT


size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_box_long(10000);
  jl_svecset(svec, val);
  // This is valid, because the annotations imply that the
  // jl_svecset propagates the rooted-ness from `svec` to `val`
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_GC_DISABLED

Эта аннотация подразумевает, что данная функция вызывается только при отключении сборки мусора во время выполнения. Функции такого рода чаще всего применяются во время запуска и в самом коде сборщика мусора. Обратите внимание, что эта аннотация проверяется на соответствие вызовам включения и отключения среды выполнения, поэтому clang определит ее корректность. Это не самый лучший способ отключения обработки определенной функции, если сборка мусора на самом деле не отключена (при необходимости используйте для этого ifdef __clang_analyzer__).

Пример использования:

void jl_do_magic() JL_GC_DISABLED {
  // Wildly allocate here with no regard for roots
}

void example() {
  int en = jl_gc_enable(0);
  jl_do_magic();
  jl_gc_enable(en);
}

JL_REQUIRE_ROOTED_SLOT

Данная аннотация требует от вызывающей стороны передачи значений в слоте, который является корневым (то есть значения, присвоенные этому слоту, будут корневыми).

Пример использования:

void jl_do_processing(jl_value_t **slot JL_REQUIRE_ROOTED_SLOT) {
  *slot = jl_box_long(1);
  // Ok, only, because the slot was annotated as rooting
  jl_gc_safepoint();
}

void example() {
  jl_value_t *slot = NULL;
  JL_GC_PUSH1(&slot);
  jl_do_processing(&slot);
  JL_GC_POP();
}

JL_GLOBALLY_ROOTED

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

Пример использования:

extern JL_DLLEXPORT jl_datatype_t *jl_any_type JL_GLOBALLY_ROOTED;
jl_ast_context_t *jl_ast_ctx(fl_context_t *fl) JL_GLOBALLY_ROOTED;

JL_ALWAYS_LEAFTYPE

Эта аннотация по сути эквивалентна JL_GLOBALLY_ROOTED за тем исключением, что ее следует использовать, только если значения являются корневыми на глобальной уровне вследствие того, что относятся к конечному типу. Определение конечных типов как корневых имеет свои особенности. Обычно они делаются корневыми посредством поля cache соответствующего объекта TypeName, который сам делается корневым посредством содержащего модуля (то есть они будут корневыми, пока это верно в отношении содержащего модуля). В общем случае мы можем предположить, что конечные типы являются корневыми там, где они используются, но в будущем это свойство может быть уточнено, поэтому отдельная аннотация помогает обосновать причину корневого характера на глобальном уровне.

Анализатор также автоматически обнаруживает проверки конечного характера типов и не будет предупреждать об отсутствии корней сборки мусора по этим путям.

JL_DLLEXPORT jl_value_t *jl_apply_array_type(jl_value_t *type, size_t dim) JL_ALWAYS_LEAFTYPE;

JL_GC_PROMISE_ROOTED

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

void example() {
  jl_value_t *val = jl_alloc_something();
  if (some_condition) {
    // We happen to know for complicated external reasons
    // that val is rooted under these conditions
    JL_GC_PROMISE_ROOTED(val);
  }
}

Полнота анализа

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