Как защищать границы массива без команды BOUND
Я уже плакался по поводу исключения в x86–64 команд двоично-десятичной арифметики DAA/DAS и плакался по поводу отмены команды проверки целочисленного переполнения INTO. Теперь настала очередь плакаться по поводу выброшенной команды BOUND. Как говорится, леди и джентльмены, подставляйте свои жилетки и декольте. Начинаю плач.
Команда BOUND проверки выхода индекса за границы массива по-своему уникальна в архитектуре x86. Потому что она явным образом предназначена для поддержки процессором языков высокого уровня. В этой части, пожалуй, только она одна такая и есть. Команда имеет два операнда, в первом из них указывается регистр с текущим значением индекса, а во втором — адрес в памяти «кортежа» из пары границ. Если число со знаком в первом операнде не входит в диапазон, заданный вторым операндом — генерируется исключение. Обратите внимание, что это поддержка не только одного какого-нибудь Си, так как границы массива могут быть любые, даже отрицательные.
Я столкнулся с нужностью контроля индексов в те далекие времена, когда в ходу были еще перфокарты. Однажды никак не мог понять, почему моя программа делает что-то странное. Коллега предложил включить контроль индексов. В БЭСМ-Алгол для этого была стандартная перфокарта, с пробитым символом «ромбик» и словом КОНТ. Я прямо взвился от такого предложения: «я же все просмотрел, индексы везде в порядке!» Но эту стандартную карту все-таки подложил в колоду. И — опа! — ошибка сразу нашлась! Потому что, будучи молодым и наивным программистом, я смотрел в текст своей программы и видел в нем только то, что хотел видеть, а не то, что там написано в реальности.
Вскоре случилась еще одна история. В те золотые времена разработки носителя «Энергия» был у нас сотрудник, занимавшийся расчетом динамических нагрузок. Ему приходилось обсчитывать много вариантов, а каждый расчет занимал часа полтора. Сейчас такие задачи почему-то с оттенком пренебрежения называют «числодробилками». Но в те времена почти все программы были такими. Так вот, он заказывал на каждую ночь два часа работы на БЭСМ-6, а утром забирал результат. Однажды вечером прямо в машинный зал вошли два других сотрудника в надежде быстрее прогнать свои программы и случайно спихнули ожидавшую ввода колоду того, о ком я рассказываю. Колода упала на пол и рассыпалась. Ну как рассыпалась — только несколько перфокарт отлетело. Они ее подобрали, и оказалось, что одна из отлетевших карт — та самая карта с ромбиком и текстом КОНТ. Сотрудники сообразили, что хозяин колоды, конечно же, не использует ее для своей давно отлаженной программы, а просто хранит, чтобы не искать, если начнет что-то менять. Для этого перфокарты надо было помещать в самый конец колоды за последней значащей перфокартой, которая официально называлась «конец ввода по А3», а на жаргоне даже неприлично — «длинный конец» из-за длинного пробитого столбика дырок. Вот из конца колоды она и отлетела. Карта КОНТ была вставлена на свое место за «длинным концом», инцидент был исчерпан.
Однако на следующее утро хозяин колоды бегал и спрашивал, кто и что делал с его программой? Оказалось, что он понятия не имеет ни о каких картах с ромбиками. Пару лет назад ему один раз составили «паспорт» колоды (с картой КОНТ), и он ничего никогда там не трогал. А вчера КОНТ, получается, выкинули. В результате того, что контроль индексов был выключен, его программа выдала (правильный) результат не за полтора часа, а за несколько минут.
Поэтому с самого начала я воспринял, во-первых, важность контроля индекса, поскольку неверный индекс массива — самый простой способ испортить программу. А во-вторых, то, что к проверкам нужно относиться бережливо, поскольку это дорогие (длительные) операции.
И вот, при переходе от x86 к x86–64 BOUND приказала долго жить. Я встречал в сети разные предположения, почему ее выкинули. Дескать, мешала предсказателю переходов. Но ведь генерация исключения — это вовсе не переход. Дескать, кодов не хватает, а тут занят код 62H. Тоже странно. Ну, заняли бы коды выброшенных команд PUSHAD/POPAD, их не так жалко. Дескать, границы, записанные в памяти, легко испортить вредоносной программой. Ага, а стек нельзя испортить вредоносной программой? И т.д. и т.п. Вплоть до аргумента: «ей никто не пользуется». Но это же замкнутый круг — выкинули, потому, что не пользуются, а пользоваться нельзя, потому, что выкинули.
Команде BOUND вообще как-то не везет. Например, в ее описании в официальной документации INTEL написана чушь собачья. Я не преувеличиваю. Вероятно, в результате технической ошибки пропало несколько слов и получилось, что текущее значение индекса должно быть «меньше или равно верхней границе плюс размер операнда». Прямо так английским по белому и написано »…and less than or equal to the upper bound plus the operand size in bytes».
Причем в переводе на русский в некоторых справочниках проявили творчество и заменили слово «плюс» на «сумму». Так и пишут, что индекс должен быть меньше или равен сумме верхней границы и размера операнда. Но легко убедиться, что никакого размера операнда к верхней границе в BOUND не прибавляется. Например, если граница указана в памяти 10, и индекс в регистре равен 11, BOUND даст исключение.
Но как бы я не плакался, в x86–64 никакой BOUND уже не предусмотрено и приходится жить без нее. И, как и в случае с INTO, встает вопрос: как быстрее и лучше проводить проверку выхода индекса за границы массива?
Еще в стародавние времена предлагался выход в том, чтобы задать допустимый диапазон индекса прямо в типе целой переменной, используемой для индекса. Например, если описать переменную как-нибудь как i int [1…100], указав допустимый диапазон, для использования как индекса массива с границами 1:100, то контроль индексов пойдет «сам собой». Правда, при этом проверки-то в программе все равно не исчезают. Хотя их может стать меньше, чем если проверять индекс при каждом обращении к массиву. Но тут есть и другая сложность. Например, при сортировке надо переставить i-й и i+1-й элементы массива. Даже если i и не выходит за границы массива, i+1 — может выйти, и заданный для i допустимый диапазон в этом случае не спасает. Конечно, можно завести переменную j типа i, присвоить j=i+1; и далее использовать индексы только как переменные, без выражений. Но это некрасиво, не наглядно, громоздко и требует лишних действий.
Поэтому я остановился на реализации проверки индекса при обращении к массиву, а не к переменной-индексу.
Поскольку массив — это набор одинаковых элементов, для доступа к элементу массива по индексу обязательно потребуется умножение индекса на размер элемента массива. В x86 есть удобная форма знакового умножения с тремя операндами: регистр, куда поместить результат, первый сомножитель (может быть переменной в памяти) и второй сомножитель-константа. Для доступа к элементам массива — это как раз то, что надо. Например, доступ к массиву x по индексу i в случае, если размер одного элемента массива 100 байт, осуществляется командами типа:
mov esi, offset x ;начало массива x
imul eax, i,100 ;умножаем размер элемента на индекс
add esi,eax ;получаем в esi адрес i-ого элементаТеперь в x86–64 для контроля выхода индекса за границы вместо использования BOUND требуются явные проверки. Однако добавление напрямую команд сравнения и условных переходов к каждому обращению к элементу массива слишком раздувает код. Поэтому я использовал системный вызов, которому надо передать и текущее значение индекса, и допустимые границы.
Некоторая сложность в том, что в приведенном выше примере отдельно индекс не фигурирует, он оказался прямо внутри команды умножения. Но ведь можно проверять не сам индекс, как таковой, а уже результат умножения. И тогда сверять его с границами, тоже уже умноженными во время компиляции на размер элемента. Это исключает необходимость отдельной командой доставать значение индекса из переменной. Неудобно и то, что регистр, куда пишется результат умножения imul, может быть из-за распределения регистров компилятором любым, и придется передавать, например, через стек еще и сам этот регистр.
Поэтому я решил при необходимости контролировать индекс использовать «старую добрую» imul в форме с одним операндом-сомножителем, поскольку у нее второй сомножитель всегда ax/eax/rax, и результат всегда пишется в ax: dx/eax: edx/rax: rdx. В этом случае передавать значение индекса в системный вызов не требуется — он всегда после умножения будет в этой паре регистров. А передавать в этом случае системному вызову нужно только границы-константы. Причем, старшая часть произведения, попадающая в регистр dx/edx/rdx, вообще-то всегда должна быть нулевой или полностью заполненной единичными битами (при отрицательном индексе). И поэтому ее можно как константу не передавать, а только подразумевать.
Рассмотрим простой пример. Пусть имеется массив с границами от 1 до 100 и размером каждого элемента 100 байт. Требуется присвоить некоторое значение i-ому элементу. Под индекс выделяется целочисленная переменная размером 8 байт.
dcl a(1:100) char(100);
dcl i fixed(63);
a(i)='12345678';При этом получаются вот такие команды без контроля индекса (? SMCCM — это системный вызов заполнения строки):
486B3D0028000064 imul q rdi,I,100
BEE8000000 mov q rsi,offset @000000E8h
488DBF8C000000 lea rdi,A+0FFFFFF9Ch[rdi]
B064 mov al,100
B108 mov cl,8
E800000000 call ?SMCCMТо же действие, но с контролем индекса:
6A6458 movsxq rax,100
48F72D00280000 imul q I
6A64 push 100 ;нижняя граница
6810270000 push 10000 ;верхняя граница
E800000000 call ?SERV3 ;системный вызов контроля индекса
BEE8000000 mov q rsi,offset @000000E8h
488DB88C000000 lea rdi,A+0FFFFFF9Ch[rax]
B064 mov al,100
B108 mov cl,8
E800000000 call ?SMCCMВ системный вызов ? SERV3 передаются через стек две границы, умноженные на размер элемента, при этом в RAX: RDX находится произведение индекса i на размер элемента.
Если бы нижняя граница массива начиналась с нуля, использовалась бы другая разновидность системного вызова контроля индекса, поскольку передавать нижнюю всегда нулевую границу не требуется:
6A6458 movsxq rax,100
48F72D68280000 imul q I
6810270000 push 10000 ;верхняя граница
E800000000 call ?SERV4 ;системный вызов контроля
BEE8000000 mov q rsi,offset @000000E8h
488DB8F0000000 lea rdi,A[rax]
B064 mov al,100
B108 mov cl,8
E800000000 call ?SMCCMВнутри этих системных вызовов контроля производится сравнение числа, записанного в rax: rdx на попадание в диапазон, переданный константами через стек:
PUBLIC ?SERV3:
PUSH 0 ;ДОБАВЛЯЕМ НОЛЬ
;---- НЕ НИЖЕ НИЖНЕЙ ГРАНИЦЫ ----
SUB [RSP]+18H,RAX
SBB [RSP]+000,RDX
JL @
CMP Q PTR [RSP]+18H,0
JNZ ERR
;---- НЕ ВЫШЕ ВЕРХНЕЙ ГРАНИЦЫ ----
@: MOV Q PTR [RSP],0
SUB [RSP]+10H,RAX
SBB [RSP]+000,RDX
JL ERR
;---- КОНТРОЛЬ ПРОШЕЛ ----
ADD RSP,8 ;ВЫБРОСИЛИ НОЛЬ ИЗ СТЕКА
RET 16
PUBLIC ?SERV4:
PUSH 0 ;ДОБАВЛЯЕМ НУЛИ
PUSH 0
;---- НЕ НИЖЕ НИЖНЕЙ ГРАНИЦЫ ----
SUB [RSP]+08H,RAX
SBB [RSP]+000,RDX
JL @
CMP Q PTR [RSP]+08H,0
JNZ ERR
;---- НЕ ВЫШЕ ВЕРХНЕЙ ГРАНИЦЫ ----
@: MOV Q PTR [RSP],0
SUB [RSP]+18H,RAX
SBB [RSP]+000,RDX
JL ERR
;---- КОНТРОЛЬ ПРОШЕЛ ----
ADD RSP,16 ;ВЫБРОСИЛИ ДВА НУЛЯ ИЗ СТЕКА
RET 8
Может показаться, что проверка старшей половины произведения в регистре RDX избыточна. Вряд ли на практике индекс сможет превысить 263. Однако в результате ошибок программы в переменной-индексе может оказаться и просто мешанина из нулей и единиц. Поэтому все-таки надежнее проверить и старшую половину произведения. На всякий случай.
Разумеется, есть случаи, когда контроль индексов не требуется. Например, если в программе есть цикл с заголовком
do i=lbound(a) to hbound(a);и внутри этого цикла в изменение индекса i никто не вмешивается, то использование встроенных функций lbound и hbound гарантирует, что индекс не выйдет за пределы границ массива. Проблема в том, что для доказательства этого требуется кропотливый анализ программы компилятором. Для простых компиляторов такой полный анализ часто недостижим.
Поэтому я использую более простой способ сокращения проверок, заключающийся в том, что ищутся линейные участки кода, т.е. участки, где нет вызовов подпрограмм, переходов или меток, на которые может попасть управление откуда угодно из программы. Если на таком линейном участке встречаются обращения к элементам массивов по индексу, то для первого обращения проверка индекса ставится всегда, а для следующих обращений проверяется, что это такие же границы и такой же индекс (и индекс с предыдущей проверки не изменился). В этом случаях — проверка больше не нужна, так как она уже выполнена ранее.
Например, массивы имеют разные размеры элементов, но одинаковые границы:
dcl a(1:100) char(100);
dcl b(1:100) char(50);
dcl i fixed(63);
a(i)=b(i);Тогда достаточно только одной проверки индекса, что и сокращает код и ускоряет выполнение:
6A6458 movsxq rax,100
48F72D803B0000 imul q I
488BF8 mov q rdi,rax
6A64 push 100 ;нижняя граница
6810270000 push 10000 ;верхняя граница
E800000000 call ?SERV3 ;контроль индекса
486B35803B000032 imul q rsi,I,50 ;умножение уже без контроля
488DB6C6270000 lea rsi,B+0FFFFFFCEh[rsi]
488DBF84000000 lea rdi,A+0FFFFFF9Ch[rdi]
B064 mov al,100
B132 mov cl,50
E800000000 call ?SMCCMКоличество различных команд в x86–64 уже приблизилось к тысяче. В частности, не так давно добавлены команды, связанные с контролем допустимости адресов BNDCL, BNDCU, BNDCN, BNDLDX, BNDMK, BNDMOV, BNDSTX в аббревиатурах которых угадывается слово BOUND (и, кстати, тоже генерирующих исключения при выходе проверяемого адреса из допустимого диапазона), а вот самую простую команду BOUND, единственную команду поддержки языковых конструкций высокого уровня, работавшую еще со времен 80286 на всех типах процессоров, почему-то посчитали ненужной. Хотя, на мой взгляд, рациональнее было бы просто расширить ее префиксом REX до 64-х разрядных значений.
Как и в случае DAA/DAS и INTO, команду BOUND, разумеется, можно функционально заменить совокупностью нескольких других команд. Хотя это раздувает код. Можно также оставить их в коде и обрабатывать исключения от этих команд, как от запрещенных. Хотя это замедляет выполнение. Обидно также, что прекрасная идея поддержки процессором языков высокого уровня не находит понимания.
