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

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

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

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

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

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

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

Проверки на переполнение могут быть вручную включены или выключены независимо от типа сборки, как глобально, так и на уровне отдельных операций.
Тем не менее, на некоторые проверки вы повлиять не можете: х / 0 и MIN / -1 ^[10] (для знаковых целых чисел) и аналогично для %. Эти вычисления являются неопределённым поведением в С и 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)

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

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

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

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 ^[12], wrapping_sub ^[13], …
• saturating_add ^[14], saturating_sub ^[15], …
• overflowing_add ^[16], overflowing_sub ^[17], ..
• checked_add ^[18], checked_sub ^[19], …

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

• wrapping_... возвращают результат дополнения до двух.
• saturating_... возвращают наибольшее/наименьшее значение при возникновении переполнения.
• overflowing_... возвращают результат дополнения до двух вместе с булевым значением, сигнализирующим о возникшем переполнении.
• checked_... возвращают Option, который принимает значение None в случае переполнения.

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

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

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

Если бы хотите иметь проверки переполнения во всём коде, то вынуждены или использовать повсюду checked_add (не слишком удобно!) или явно включить их. Хотя они по умолчанию работают только в отладочном режиме, проверки переполнения можно включить передав -C debug-assertions=on rustc (компилятору Rust) или задав поле debug-assertions в cargo profile ^[24]. Также идёт работа по возможности включать их независимо от других отладочных проверок (в данный момент 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, которая содержит ошибку ^[25]. Безусловно, все эти дополнительные инструкции раздражают, так же, как и необходимость использовать 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 не интегрируется напрямую с проверками переполнения: она не устанавливает флаг состояния процессора, свидетельствующий об этом.

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

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

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

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

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

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

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

• стандартная библиотека ^[34]
• компилятор ^[35]
• встроенная инфраструктура тестирования производительности ^[36]
• Servo ^[37]
• image ^[38]
• url ^[39]
• webrender ^[40]

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

Автор: DarkEld3r

Источник ^[42]