Сишные трюки

Крис Касперски

Хакер, номер #115, стр. 115-106-1

Реверс строки в адресном континууме

Перевернуть строку, не используя дополнительной памяти, — довольно распространенное задание для юниоров, нацеленное на знание указателей. Когда же его дают матерым программистам, над «экзаменатором» не грех и постебаться, воскликнув: «А зачем ее разворачивать? она и так уже развернута!». После чего пояснить: «В мире все относительно: где конец того начала, что есть начало конца?!». Как и многие другие, x86-процессоры поддерживают флаг направления: просто взводим его, перемещаем указатель на конец строки и движемся в обратном направлении. Некоторые проблемы создает отсутствие завершающего нуля на конце (точнее, в начале) строки, но что мешает нам запомнить ее длину? В адресном пространстве нет понятия «верха» и «низа». До сих пор не утихают споры: куда растет стек и адреса памяти. А потому, всякая последовательность байт одновременно существует в двух состояниях — прямом и развернутом.

Увы, при всей красоте этой концепции ее не объяснишь библиотечным функциям. В частности, fopen, printf, MessageBox и др. – движутся от младших адресов к старшим. Без полноценного реверса тут никак не обойтись, но мы можем воспользоваться этим «подарком» в своих собственных функциях, передавая им в качестве аргумента флаг, в каком направлении двигаться — увеличивать указатель или уменьшать его.

Кто-то может презрительно хмыкнуть: флаг направления и в чистом ассемблере редко используется, а уж на языках высокого уровня ему и вовсе не место, разве что – в академических задачках. Но зачастую массив элементов, отсортированный по возрастанию, требуется превратить в массив, отсортированный по убыванию. Реверс элементов с перемещением их по памяти – не самая быстрая операция, особенно если этих элементов у нас много, а переупорядочивать их приходится достаточно часто. Флаг направления в этом случае экономит кучу процессорных тактов ценой незначительного усложнения алгоритма.

Единственный недостаток предложенного способа — падение производительности при движении взад: от старших адресов к младшим. Так уж повелось, что вся подсистема памяти от кэш-контроллера первого уровня до DRAM-модулей ориентирована на чтение вперед, иначе она начинает тормозить, облагая нас «штрафными» тактами. А потому многократное чтение массива в обратном направлении (особенно большого массива) – это не Zen-way. Лучше затратить время на однократный «честный» реверс, а потом читать вперед, сколько влезет. Хотя реверс плюс однократное чтение массива в прямом направлении – намного медленнее однократного чтения того же массива в обратном направлении.

Принудительная проверка успешности операции

Ассеблерщикам хорошо! В их распоряжении есть флаги процессора, сплошь и рядом используемые для индикации ошибок выполнения функций. А вот на Си, если функция возвращает int (а возвращает она его предательски часто), – в качестве индикатора успешности выполнения операции приходится использовать значение, не входящее в диапазон «валидных» ответов. Применительно к malloc, — это ноль (нулевой указатель не может быть валидным, во всяком случае, в Си). Если же ноль входит в область допустимых значений, приходится возвращать -1 или выкручиваться как-то еще.

Как следствие, мы имеем полный разброд без всяких признаков стандартизации. Попробуй удержи в голове все эти подробности! Неудивительно, что многие программисты «забывают» о проверке, передавая возвращенные (некорректные) значения другой функции. В результате, программа падает или ведет себя некорректно, но даже если и падает, то совсем не в месте ошибки, а довольно далеко от него. Положение осложняется тем, что проекты зачастую пишутся кучей людей, среди которых попадаются откровенные «вредители», не выполняющие никаких проверок вообще. «Аукается» это в чужих модулях, высаживая коллег на измену.

Как гарантированно заставить «пионеров» выполнять проверки или хотя бы добиться того, чтобы программа стабильно грохалась именно в том месте, где возникает ошибка? Достаточно вместо значения возвращать указатель на память, где это значение лежит – или ноль (при ошибке). Обращение к нулевому указателю приводит к немедленному выбросу исключения, за которое «пионеру» легко надавать по ушам.

Конечно, при этом возникает «лишняя» операция обращения к памяти, но это не проблема, поскольку в общем зачете накладные расходы стремятся к нулю. Даже если функция целиком состоит из одного return и принимает параметры через регистры по fastcall-соглашению, она все равно заталкивает адрес возврата на стек, обращаясь к памяти… 50% «оверхид» на пустой функции — не такой уж плохой результат! Проблема в том, что найти место для размещения возвращаемых данных не так-то просто. Если выделять блок при помощи malloc, то это, во-первых, слишком медленно, а во-вторых, когда «пионер» забудет освободить возращенный указатель (а он забудет), память потечет рекой.

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

Точно так же, если функция возвращает данные по указателю, мы можем «навязать» проверку успешности выполнения операции путем возвращения указателя на указатель (возвращая в случае ошибки ноль).

Имитация INT

Во времена MS-DOS большинство системных функций вызывалось путем генерации программного прерывания командой INT 21h. UNIX-системы используют этот путь и сегодня (только вместо вектора 21h у них 80h). Достоинство подхода в том, что код, вызывающий INT, не имеет ни малейшего представления о том, по какому адресу находится системный обработчик. Более того, этот адрес может динамически меняться (например, в MS-DOS появился новый резидентный вирус, хе-хе).

Windows NT вплоть до XP также использовала INT в качестве «моста» между user-land и kernel-land, позволяя прикладному коду делать системные вызовы. Начиная с XP, медленная команда INT сменилась более быстрой SYSENTER/SYSCALL (Intel/AMD, соответственно), однако на прикладном уровне основным средством межмодульных вызовов стал экспорт/импорт эффективных адресов. Именно так и работают динамические библиотеки.

Экспорт/импорт прекрасно действует в рамках одной программы, но когда мы пытаемся прикрутить к ней поддержку plug-in'ов, возникает куча проблем. Фактически, основная программа, с точки зрения plag-in'а, превращается в операционную систему и необходимо как-то передать адреса всех функций, чтобы plug-in их мог вызывать. Обычно для этого используется готовый механизм, и plug-in'ы реализуются как динамические библиотеки. Это накладывает на разработчика программы множество ограничений, призванных обеспечить обратную совместимость. Но это еще что! Отсутствует возможность (легальная) написания plug-in'ов-фильтров, встраивающихся между уже загруженным plug-in'ом и основной программой.

Тут как нельзя кстати оказался бы INT, но, во-первых, это системно-зависимо и абсолютно непереносимо, а, во-вторых, вызывать INT с прикладного уровня для передачи управления на прикладной уровень — негуманно. Вот намного более элегантный способ: основная программа устанавливает обработчик исключений, а plug-in для вызова функций программы производит запись определенной структуры данных по нулевому указателю, что ведет к генерации исключения, перехватываемого (и обрабатываемого) основной программой.

Программа может динамически переназначать обработчики исключения в зависимости от текущего режима работы (например, запуске встроенного редактора), то же самое могут делать и plug-in'ы. Устанавливая свой обработчик исключения, перекрывающий предыдущий, они перехватывают общение основной программы со всей цепочкой plug-in'ов-фильтров. Ну разве не красота?

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

«Магическая» таблица, записываемая по нулевому адресу

struct leben

{

char magic[]="NZM1";

// магический "пирожок"

int syscall_id;

// номер "системного вызова"

void *list;

// указатель на список аргументов "сис. вызова"

Поясню: magic – хранит магическое слово, проверяемое обработчиком исключения, чтобы удостовериться, что это не случайная операция записи, а преднамеренный «системный вызов», номер которого хранится в syscall_id. Впрочем, вместо номера можно использовать имена «системных вызовов» — на усмотрение программиста. Аргументы передаются (и возвращаются) через указатель на область памяти (в данном случае *list), формат которой варьируется от одного «системного вызова» к другому.