Static analyzer annotations for GC correctness in C code

Running the analysis

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

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

make -C src install-analysis-deps

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

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

General Overview

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

В сгенерированном коде это автоматически обрабатывается проходом размещения корней сборщика мусора (см. главу о корнях сборщика мусора в документации по разработке 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 Invariants

Существует два простых инварианта корректности:

Все вызовы GC_PUSH должны сопровождаться соответствующим GC_POP (на практике мы обеспечиваем это на уровне функции)
Если значение ранее не было привязано к какой-либо контрольной точке, оно больше не может быть упомянуто впоследствии.

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

Какие вызовы являются безопасными точками, а какие нет
Какие значения находятся в корне в любой данной безопасной точке, а какие - нет
Когда значение ссылается

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

Static Analysis Algorithm

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

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

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

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

The analyzer annotations

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

`JL_NOTSAFEPOINT`

Это, возможно, самая распространенная аннотация, и ее следует размещать на любой функции, которая, как известно, не может привести к достижению точки безопасности сборщика мусора (GC). В общем, такой функции безопасно выполнять арифметические операции, доступы к памяти и вызовы функций, аннотированных 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`

Это аннотация подразумевает, что эта функция вызывается только с отключенным временем выполнения сборщика мусора (GC). Функции такого рода чаще всего встречаются во время запуска и в самом коде GC. Обратите внимание, что эта аннотация проверяется на соответствие вызовам включения/выключения времени выполнения, поэтому clang узнает, если вы обманете. Это не лучший способ отключить обработку данной функции, если GC на самом деле не отключен (используйте 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, за исключением того, что она должна использоваться только в том случае, если эти значения глобально коренятся благодаря тому, что они являются leaftype. Коренение leaftype немного усложнено. Обычно они коренятся через поле cache соответствующего TypeName, которое само коренится модулем, содержащим его (поэтому они коренятся, пока содержащий модуль в порядке), и мы можем в целом предположить, что leaftype коренятся там, где они используются, но мы можем уточнить это свойство в будущем, поэтому отдельная аннотация помогает выделить причину глобального коренения.

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

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);
  }
}

Completeness of analysis

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