Сужение данных. Продолжение борьбы с переполнением

Все началось с глупой ошибки. В тексте программы вместо оператора x=20; где x – целая переменная со знаком и размером в байт, случайно написали x=200;

И компилятор, что называется не моргнув глазом, сформировал команду записи в переменную x константы 0C8H, что вообще-то соответствовало оператору x=-56; Выяснилось, что за долгие годы эксплуатации этого компилятора ни одна собака ни один пользователь (включая и нас самих) никогда не писал подобных ляпов и поэтому ошибка в компиляторе оставалась незамеченной. А виноваты оказались команды сужения данных.

На самом деле, конечно, никаких команд сужения в x86 нет. Это я их так называю по аналогии с существующими командами расширения.

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

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

Т.е. вот так писать было можно:

p=addr(x); return(p);

А вот так уже получали ошибку компиляции:

return(addr(x))

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

Ошибка второй категории в компиляторе была найдена в индексированных метках. Язык позволяет писать в тексте метки с индексами, например, m(1): m(2): и т.п. и переходить на них оператором goto m(i). Мы использовали такой механизм, к примеру, для написания сложных конечных автоматов, но не суть. Выяснилось, что если случайно в тексте поставили несколько меток с одинаковым индексом, компилятор берет адрес только последней из них.

Казалось бы, ну какие могут быть категории у подобных багов? Плохое тестирование вот и все. Однако в первом случае компилятор дал ошибку на правильный фрагмент, а во втором не сообщил об ошибке в неправильном фрагменте. На мой взгляд, в этом и есть принципиальная разница.

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

Во втором же случае – число возможных ошибок в тексте потенциально безгранично. Как там у Стругацких в понедельнике, который начинается в субботу? Познание бесконечности требует бесконечного времени? А потому работай не работай (или в данном случае тестируй не тестируй) – все едино. Все ошибки второй категории все равно не выявишь.

На самом деле, безграничное число возможных ошибок в тексте программы вовсе не повод отказываться от тестов, содержащих заведомые ошибки для проверки, реагирует ли на них компилятор. Но отчасти пропущенная ошибка компилятора в операторе x=200; связана именно со сложностью придумывания специально ошибочных тестов и со сложностью их формализации.

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

Вернемся к теме статьи. В своей предыдущей заметке я упоминал, что компилятор в своей работе использует лишь 90 команд x86-64 без учета команд FPU.

При этом часть из этих 90 вовсе не команды, а удобные абстракции для компилятора, вроде меток или псевдокоманды func, которая нужна лишь для выявления выхода из функции без вычисления результата. И вот среди этих псевдокоманд есть и команды сужения данных, как я их называю. Они внутри компилятора и названы соответственно cwb и cdw по аналогии с реальными командами расширения cbw и cwd.

Поскольку большинство читателей не очень ориентируется в системе команд x86, приведу небольшую справку.

Еще со времен процессора 8086 были предусмотрены две команды расширения операнда cbw и cwd, являющиеся, по сути, просто подготовкой к делению целых, которая требует для делимого всегда пару регистров al:ah или ax:dx. Поэтому cbw заполняет регистр ah знаком регистра al, а cwd – знаком ax/eax заполняет регистр dx/edx. По мере развития x86 появились удобные команды расширения операнда уже не для деления, а просто для манипулирования объектами разного размера, причем команда movsx расширяет операнд со знаком, а команда movzx – заполняет оставшуюся часть большего объекта нулями.

Например, команда movsx ebx,al преобразует регистр ebx, так, что младший байт ebx (т.е. регистр bl) станет равным регистру al, а остальные три байта ebx будут заполнены нулями или единицами в зависимости от знакового разряда al.

В компиляторе есть обработка обобщенной операции присваивания/пересылки. Если она имеет операнды целого типа, то они могут быть размером 1, 2, 4 или 8 байт. Таким образом, в этой операции всего может быть 16 разных комбинаций размеров двух операндов. Четыре варианта (равенство размеров) не требуют дополнительных действий, что приятно. В остальных случаях требуется или шесть видов расширения операнда или шесть видов «сужения» операнда, что и приводит к генерации пока виртуальных команд расширения или сужения.

Виртуальные команды расширения, в конце концов, порождают реальные команды расширения movzx или movsx, например код movsx ebx,al. А вот обратное действие, т.е. сужение в виде команды movsx al,ebx не создается, поскольку такой команды в x86 нет, вместо нее применяются обычные пересылки, например в виде команды mov al,bl.

Если не заморачиваться какими-нибудь очень экзотическими случаями объектов, занимающее нецелое число байт, то такая система расширений-сужений прекрасно работает. Но есть нюанс. Если при расширении целочисленного операнда переполнения не может быть по определению, то при сужении операнда – может и быть.

Ошибка компилятора при анализе оператора x=200; заключалась не столько в том, что он решил поместить младший байт константы в переменную x, сколько в том, что он не проверил, а «лезет» ли такая знаковая константа в переменную. И в данном случае компилятору надо было бы сообщить о переполнении, причем это легко сделать, поскольку константы известны на этапе компиляции, и их можно сразу проверять на допустимый диапазон.

Сложнее обстоит дело с проверками при выполнении программы. Прежде всего, а как быстро проверить переполнение? Да так, как в младших классах заставляют проверять деление умножением, т.е. обратным действием. Так и здесь, «суженый» операнд надо опять расширить до размера исходного и сравнить с исходным. Если они равны – такое сужение правомерно, иначе возникает то самое переполнение.

Например, пусть в программе требуется присвоить целой знаковой переменной y размером в байт значение целой знаковой переменной x размером 4 байта.

Без контроля переполнения компилятор генерирует простые пересылки:

mov   al,x
mov   y,al

С контролем переполнения генерируются команды:

   mov    eax,x       ;достаем содержимое переменной x
   push   rax         ;помещаем ее в стек
   movsx  eax,al      ;расширяем младший байт
   cmp    eax,[rsp]   ;получилось исходное значение ?
   pop    rax         ;очищаем стек
   jz     m           ;все в порядке, x помещается в y
   into               ;иначе сигнал переполнения
m: mov y,al           ;пересылка в y

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

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

Хотя в используемом нами подмножестве языка явно задаваемого беззнакового целого типа нет, но неявно такой тип все равно возникает. Например, в языке имеется встроенная функция ascii, возвращающая символ ASCII-набора, заданный его порядковым номером (так, ascii(140) вернет символ «M»). Поэтому, если параметр такой функции – это переменная размером два и более байт, при сужении требуется учитывать допустимый диапазон 0-255, а не -128+127. В этом случае вместо movsx и применяется movzx.

После внесения в компилятор таких дополнительных проверок переполнения при сужении, даже старое и давно работающее ПО стало вдруг показывать ошибки. Например, в одной из программ при выделении подстроки из строки была указана начальная позиция как length(s)-2, где length(s) – текущая длина строки. Однако все-таки возникал случай пустой строки и тогда начальная позиция превращалась в недопустимые -2. Естественно, в языке имеется контроль правильности позиций подстроки (с исключительной ситуацией StringRange). Но из-за команды сужения без проверки переполнения недопустимые -2 легким движением руки превращались в допустимые 254 и имевшаяся проверка подстроки проходила. Правда далее пустая строка все равно отбрасывалась и последствий не возникало, из-за чего, собственно, эту ошибку и не замечали. Но нельзя рассчитывать, что всегда так обойдется.

Дополнительные проверки увеличили размер кода и замедлили работу, но зато повысили надежность программ. Я считаю такую плату за надежность вполне оправданной, к тому же сужение данных в программах требуется все же не так часто, как расширение. Конечно жаль, что в x86 нет команд сужения типа mov al,ebx, которые выполняли бы просто пересылку регистра bl в al, но при этом еще и устанавливали бы флаг переполнения в случае, если регистр ebx «не помещается» в al. Такие команды очень помогли бы компилировать компактный и быстрый код с проверками переполнений.

Если все-таки в каком-то случае требуется просто передать часть большего операнда в меньший без проверки, то это можно реализовать разными способами помимо просто отключения проверок в компиляторе. Например, в языке PL/1 имеется возможность «наложить» одну переменную на другую в памяти:

declare x fixed(31), y fixed(7) defined(x); // x и y имеют один адрес в памяти

при таком наложении оператор y=x; даже и не нужен, в переменной y и так всегда будет младший байт значения x. Никаких команд сужения, а, значит, и проверок переполнения здесь нет. Компилятор лишь проверяет, что всегда объект меньшего размера наложен на объект большего размера, а не наоборот, поскольку память выделяется только для одного объекта. Но такой обман компилятора – это все-таки редкий случай. Чаще при пересылках контроль переполнения естественен и необходим.

Много лет я использую язык, в котором очень мало «неопределенного поведения». Еще 55 лет назад стандарт языка однозначно определил множество исключительных ситуаций типа SubScriptRange (выход индекса за границы), StringRange (выход позиции за пределы строки) и других, включая, конечно, и FixedOverflow (целочисленное переполнение). Такой подход делает поведение программ предсказуемым и очень облегчает отладку и сопровождение ПО. А теперь еще и дополнительные проверки окончательно прикрыли от ошибок переполнения, незакрытую, как выяснилось, «боковую калитку» в компиляторе в виде команд сужения данных.

И это гораздо лучше, чем, как в некоторых языках ошибки и алгоритмов и программистов, связанные с переполнением, просто заметать под коврик с надписью «undefined behavior».