Мифы и легенды о переполнении целых чисел в Rust

• оригинал: Huon Wilson • перевод: Станислав Ткач • обучение • поддержите на Patreon

Примитивные целочисленные типы, поддерживаемые процессорами, являются ограниченным приближением к бесконечному набору целых чисел, которыми мы привыкли оперировать в реальной жизни. Это ограниченное представление не всегда совпадает с «реальными» числами, например 255_u8 + 1 == 0. Зачастую программист забывает об этой разнице, что легко может приводить к багам.

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

Переполнение в Rust

Политика обнаружения и предотвращения переполнения в Rust менялась несколько раз на пути к релизу 1.0.0, состоявшемуся в прошлом году. В итоге, присутствует недопонимание того, как переполнение обрабатывается и какие последствия вызывает.

До версии 1.0.0-alpha переполнение было циклическим и результат соответствовал использованию дополнения до двух (как и поступает большинство современных процессоров). Однако, такое решение не оптимально: неожиданное и незамеченное переполнение часто приводит к ошибкам. Это особенно плохо в С и С++ из-за того, что переполнение знаковых целых чисел является неопределённым поведением (undefined behaviour), что вместе с недостаточной защитой от нарушения безопасности работы с памятью может легко приводить к её повреждению. Впрочем, в более заботящихся о безопасности языках, таких как Rust, это всё ещё вызывает проблемы: существует много примеров переполнения, они обнаруживаются в видеоиграх (экономике, индикаторах здоровья и т. д.), реализациях двоичного поиска и даже в программном обеспечении для авиации. Проще говоря, код наподобие max(x - y, z) периодически встречается и может давать неправильные результаты, если числа являются беззнаковыми и x - y вызывает переполнение. Как результат, возникло желание сделать Rust более безопасным в отношении переполнения целых чисел.

Нынешнее состояние дел определено в RFC 560:

Проверки на переполнение могут быть вручную включены или выключены независимо от типа сборки, как глобально, так и на уровне отдельных операций. Тем не менее, на некоторые проверки вы повлиять не можете: х / 0 и MIN / -1 (для знаковых целых чисел) и аналогично для %. Эти вычисления являются неопределённым поведением в С и LLVM, что и стало причиной поведения rustc, хотя мне кажется, что Rust теоретически мог бы рассматривать MIN / -1 как нормальное переполнение и возвращать MIN при отключённых проверках.

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

Миф: результат переполнения не определён (undefined)

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

1
2
3
4
5
6
// Псевдо-Rust
let x = undefined;

let y = x;
let z = x;
assert_eq!(y, z); // потенциальная проблема

Это приведёт к катастрофическим последствиям, если от такого значения зависит безопасность. Например, при проверке выхода за границы массива foo[x]:

1
2
3
4
5
6
7
8
9
let x = undefined;

// let y = foo[x]; // что эквивалентно следующему:

let y = if x < foo.len() {
    unsafe { *foo.get_unchecked(x) }
} else {
    panic!("index out of bounds")
};

Если значение переменной х различается при сравнении x < foo.len() и при непосредственном доступе к массиву, то гарантии могут быть нарушены: в сравнении может оказаться 0 < foo.len(), а при доступе по индексу получится foo.get_unchecked(123456789). Непорядок!

Таким образом, в отличие от целых чисел со знаком в С, в Rust переполнение не может быть неопределённым. Другими словами, компилятор должен предполагать, что переполнение может произойти, если только он не может доказать обратное. Это влечёт за собой неочевидные последствия: x + 1 > x не всегда истинно, в то время как компиляторы С предполагают, что данное условие всегда выполняется, если х является целым со знаком.

«Но как же производительность?» Я уже предчувствую этот вопрос. Действительно, неопределённое поведение упрощает оптимизации, позволяя компилятору делать предположения. Следовательно, отказ от такого поведения может влиять на скорость. Неопределённость переполнения целых чисел особенно полезна в С потому, что такие числа часто используются как индуктивные переменные в циклах, соответственно, возможность строить предположения, позволяет более точный анализ количества итераций цикла: for (int i = 0; i < n; i++) будет выполняться n раз так как можно предположить, что n не содержит отрицательное значение. Rust обходит большинство таких проблем используя положительные числа в качестве индексов (0..n всегда даст n шагов) и допуская легковесные итераторы для прямого обхода структур данных, например for x in some_array { ... }. Эти итераторы могут использовать знания о внутреннем устройстве структур данных, не заставляя пользователя иметь дело с неопределённым поведением.

Также Rust, в отличии от С, не может свести x * 2 / 2 просто к x, если x являет целым со знаком. Данная оптимизация не применяется (если только вы вручную не напишете x вместо сложного арифметического выражения), однако в моей практике подобные выражения наиболее часто встречаются, когда x известен во время компиляции, а значит всё выражение будет заменено константой.

Миф: результат переполнения не специфицирован (unspecified)

Результат переполнения мог бы быть не специфицирован, в этом случае компилятор был бы обязан предполагать, что оно может произойти, но имел бы право вернуть в результате любое значение (или не возвращать его вовсе). И в самом деле, в первой версии RFC 560 по проверке переполнения целых чисел было предложено:

Изменить поведение на возврат неспецифицированного значения или вызов паники, в зависимости от того, проверяется ли переполнение. […]

  • Теоретически реализация возвращает неспецифицированное значение. На практике, однако, результат будет аналогичен циклическому переполнению. Реализациям следует избегать излишней непредсказуемости и неожиданного поведения, чтобы не провоцировать ошибки.
  • И самое важное: это не неопределённое поведение в понимании С. Неспецифицированным будет исключительно результат операции, а не поведение всей программы целиком, как в С. Программист не может полагаться на какое-то конкретное значение при переполнении, но компилятор не имеет права использовать предположение о том, что переполнение не возникнет, для оптимизации.

RFC и и «неспецифицированный» результат переполнения (то есть 127_i8 + 1 может вернуть -128 или 0 или 127 или любое другое значение) стал предметом оживлённых дискуссий, которые повлекли за собой его изменение.

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

Операции +, -, * могут приводить к переполнению (overflow) или исчезновению порядка (underflow). Если проверки включены, тогда произойдёт паника. В противном случае результатом будет циклическое переполнение.

Зафиксированный результат переполнения — защитная мера: ошибки могут не иметь последствий, даже если переполнение не обнаружено. Выражение x - y + z вычисляется как (x - y) + z и, следовательно, вычитание может приводить к переполнению (например, x = 0 и y = 1, оба беззнаковые), но если z достаточно большое (в нашем примере z >= 1), результат будет аналогичен использованию «чисел из реального мира».

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

Миф: программист не может управлять обработкой переполнения

Одним из аргументов против введения проверки переполнения было существование программ и алгоритмов, которые полагаются на цикличное переполнение, таких как: алгоритмы вычисления хеша, некоторые структуры данных (например, кольцевой буфер) и даже кодеки. Для данных алгоритмов использование + в отладочном режиме будет некорректным: произойдёт паника, хотя такое использование переполнения было сознательным. К тому же в отдельных случаях может возникнуть желание включить проверки не только для отладочной сборки.

RFC и стандартная библиотека предоставляют четыре набора методов, помимо обычных операторов:

Это должно покрывать все «особые случаи»:

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

Если вы действительно хотите использовать циклическое переполнение, тогда можете написать что-то вроде x.wrapping_sub(y).wrapping_add(z). Это даст ожидаемый результат, а многословность может быть уменьшена путём использования типа из стандартной библиотеки Wrapping.

Возможно, это ещё не финальное состояние: в RFC также упоминаются потенциальные улучшения. В будущем в Rust могут быть добавлены операторы, подобные циклическому &+ из Swift. Это не было сделано сразу, так как Rust пытается быть консервативным и, в разумной степени, минималистичным, а также из-за потенциальной возможности отключать проверки переполнения (например, отдельная функция может быть явно помеченной и в её коде будут отсутствовать проверки во всех режимах). В частности, в последнем заинтересованы самые активные (потенциальные) пользователи Servo и Gecko.

Если бы хотите иметь проверки переполнения во всём коде, то вынуждены или использовать повсюду checked_add (не слишком удобно!) или явно включить их. Хотя они по умолчанию работают только в отладочном режиме, проверки переполнения можно включить передав -C debug-assertions=on rustc (компилятору Rust) или задав поле debug-assertions в cargo profile. Также идёт работа по возможности включать их независимо от других отладочных проверок (в данный момент rustc поддерживает нестабильную опцию -Z force-overflow-checks flag).

Миф: выбранный подход к проверкам переполнения замедляет код

Rust стремится быть настолько быстрым, насколько это возможно, и при разработке проверок переполнения вопросы производительности рассматривались очень серьёзно. Производительность — одна из основных причин, по которым проверки были отключены для релизных сборок по умолчанию. Разумеется, это значит, что скорость не была принесена в жертву удобству обнаружения ошибок во время разработки.

К сожалению, проверки на переполнение требуют больше кода и инструкций:

1
2
3
4
5
6
7
8
9
[no_mangle]
pub fn unchecked(x: i32, y: i32) -> i32 {
    x.wrapping_add(y)
}

#[no_mangle]
pub fn checked(x: i32, y: i32) -> i32 {
    x + y
}

С -O -Z force-overflow-checks на x86 (на 32-bit ARM LLVM в данный момент генерирует избыточные сравнения и манипуляции с регистрами, так что потеря в производительности даже больше!) это компилируется в следующее (с некоторыми изменениями для ясности):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unchecked:
	leal (%rdi,%rsi), %eax
	retq

checked:
	pushq	%rax
	addl	%esi, %edi
	jo	.overflow_occurred
	movl	%edi, %eax
	popq	%rcx
	retq
.overflow_occurred:
	leaq	panic_loc2994(%rip), %rdi
	callq	_ZN9panicking5panic20h4265c0105caa1121SaME@PLT

Тут больше инструкций, чем должно быть при условии, что checked встраивается (что и должно происходить): в этом случае работа с регистрами с помощью pushq/pop/movl не обязательна. Я полагаю, что даже без встраивания управление стеком с помощью pushq/popq не требуется, но, к сожалению, сейчас Rust использует версию LLVM, которая содержит ошибку. Безусловно, все эти дополнительные инструкции раздражают, так же, как и необходимость использовать add вместо lea.

На x86 использование lea (load effective address) для арифметики может быть очень полезным: она позволяет производить относительно сложные вычисления и, как правило, вычисляется в отдельной части CPU и его конвейера, в отличии от add, что способствует более высокому параллелизму на уровне инструкций. x86 ISA разрешает разыменование результата сложных вычислений с указателями: общая форма A(r1, r2, B) (в AT& T синтаксисе), что эквивалентно r1 + B * r2 + A где r1 и r2 — регистры, а A и B — константы. Как правило, это используется напрямую в инструкциях по работе с памятью, таких как mov. Например, let y = array_of_u32[x]; может скомпилироваться во что-то вроде mov (array_of_u32.as_ptr(), x, 4), y, так как каждый элемент имеет размер 4. Но leaпозволяет выполнить арифметику не затрагивая память. В общем, возможность использовать lea для арифметики довольно полезна. Недостаток заключается в том, что lea не интегрируется напрямую с проверками переполнения: она не устанавливает флаг состояния процессора, свидетельствующий об этом.

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

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

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

В RFC о переполнении заложена возможность дополнительных оптимизаций: разрешается «отложенная паника», то есть реализации могут выполнять последовательность операций a + b + c + d и паниковать один раз в самом конце, если любое из вычислений привело к переполнению, вместо того чтобы проверять каждую отдельную операцию tmp = a + b, затем tmp + c и т. д. Хотя на данный момент это не реализовано, такая возможность есть.

Миф: проверки не обнаруживают ошибки

Все усилия по разработке, обсуждению и реализации этой схемы обработки целочисленных переполнений были бы напрасны, если бы они не помогали обнаружить ошибки на практике. Лично я нашёл несколько проблем в своём коде с выражениями вроде cmp::max(x - y, z) (они не попали в интернет, так что ссылок не будет) практически сразу после написания, особенно в сочетании с инфраструктурой тестирования, такой как quickcheck.

Проверки переполнения обнаружили ошибки в нашей экосистеме, например, такие (список не полный!):

За пределами Rust существует много других примеров опасности ошибок переполнения. В 2011 году они попали в список 25 самых частых ошибок CWE/SANS. Некоторые языки, например Swift, всегда осуществляют проверки переполнения, а другие, такие как Python 3 и Haskell, избегают переполнения, по умолчанию используя числа с произвольной точностью. Более того, некоторые компиляторы C поддерживают опции, заменяющие неопределённое поведение на циклическое переполнение (-fwrapv) и помогающие обнаружить переполнение (-fsanitize=signed-integer-overflow).

patreon Поддержите на Patreon