Примитивные целочисленные типы, поддерживаемые процессорами, являются ограниченным приближением к бесконечному набору целых чисел, которыми мы привыкли оперировать в реальной жизни. Это ограниченное представление не всегда совпадает с "реальными" числами, например 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 — обеспечивать безопасность работы с памятью, а такая неопределённость (аналогичная неопределённому поведению в С) явно противоречит этой цели. Переменная, содержащая неопределённое значение, не обязана сохранять одинаковое значение между использованиями:
// Псевдо-Rust
let x = undefined;
let y = x;
let z = x;
assert_eq!(y, z); // потенциальная проблемаЭто приведёт к катастрофическим последствиям, если от такого значения зависит безопасность. Например, при проверке выхода за границы массива foo[x]:
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 и стандартная библиотека предоставляют четыре набора методов, помимо обычных операторов:
- wrapping_add, wrapping_sub, …
- saturating_add, saturating_sub, …
- overflowing_add, overflowing_sub, ..
- checked_add, checked_sub, …
Это должно покрывать все "особые случаи":
wrapping_...возвращают результат дополнения до двух.saturating_...возвращают наибольшее/наименьшее значение при возникновении переполнения.overflowing_...возвращают результат дополнения до двух вместе с булевым значением, сигнализирующим о возникшем переполнении.checked_...возвращаютOption, который принимает значениеNoneв случае переполнения.
Все эти операции могли бы быть реализованы в терминах 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 стремится быть настолько быстрым, насколько это возможно, и при разработке проверок переполнения вопросы производительности рассматривались очень серьёзно. Производительность — одна из основных причин, по которым проверки были отключены для релизных сборок по умолчанию. Разумеется, это значит, что скорость не была принесена в жертву удобству обнаружения ошибок во время разработки.
К сожалению, проверки на переполнение требуют больше кода и инструкций:
[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 в данный момент генерирует избыточные сравнения и манипуляции с регистрами, так что потеря в производительности даже больше!) это компилируется в следующее (с некоторыми изменениями для ясности):
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.
Проверки переполнения обнаружили ошибки в нашей экосистеме, например, такие (список не полный!):
- стандартная библиотека
- компилятор
- встроенная инфраструктура тестирования производительности
- Servo
- image
- url
- webrender
За пределами Rust существует много других примеров опасности ошибок переполнения. В 2011 году они попали в список 25 самых частых ошибок CWE/SANS. Некоторые языки, например Swift, всегда осуществляют проверки переполнения, а другие, такие как Python 3 и Haskell, избегают переполнения, по умолчанию используя числа с произвольной точностью. Более того, некоторые компиляторы C поддерживают опции, заменяющие неопределённое поведение на циклическое переполнение (-fwrapv) и помогающие обнаружить переполнение (-fsanitize=signed-integer-overflow).
Автор: DarkEld3r
