Я уверен, что у многих из нас при отладке приложений периодически возникает желание отступить на шаг (или два, десять...) назад от текущей строки, чтобы увидеть причины происходящего в ней неправильного поведения. Чаще всего для этого приходится перезапускать отладку с начала и пытаться остановить исполнение программы чуть раньше, чем на предыдущей попытке. Затем надо пошагово приблизиться к предполагаемому месту с проблемой… упс, опять перешагнули! Начинаем всё по новой, ведь в дебаггере уже нельзя отступить назад даже на один шаг. Или можно?
В одном из своих предыдущих постов я запланировал описать, как программная симуляция цифровых систем позволяет делать то, что невозможно в реальности, а именно — обращать вспять течение времени для нужд отладки. Об этом и пойдёт речь в этой заметке.
Автор фото: Иван Андреев
Сначала немного общих соображений. Зачем вообще нужно прямое, т.е. «нормальное» исполнение программ? Чтобы получить результат некоторого вычисления, которое нежелательно/трудно/невозможно выполнять вручную. Расчёт полёта ракеты — это вычисления. Просмотр котиков на сайте — это вычисления. Процесс вычисления может быть формализован с помощью представления его в форме алгоритма.
Зачем обращать исполнение
Для чего может понадобиться обратное исполнение (англ. reverse execution)? Для того, чтобы облегчить себе понимание того, как вычисления внутри программы привели к тому или иному результату, правильному или неправильному.
Поддержку функции обращения течения программы возможно включать в различные инструменты, используемые программистами. Далее в основном речь пойдёт о симуляторах. В этом контексте эта идея получает два варианта развития. Первое — это отладка исполняющегося внутри модели кода симулируемого BIOS/Firmware, ОС, приложения..., что интересно конечному пользователю симулятора — разработчику ПО. Второе применение — это отладка непосредственно симулятора (он тоже является программой). Это важно уже для разработчика моделей устройств.
Отладка
Исполнение любого алгоритма (в традиционном понимании этого термина), записанного в той или иной форме, можно разбить на отдельные шаги, буде то операторы языка высокого уровня, машинные инструкции, движения каретки машины Тьюринга и т.п. Процесс отладки начинается с поиска шага в реализации алгоритма, на котором что-то пошло не так, как ожидалось программистом. Как правило при этом известно две точки в исполнении: на первой состояние всё ещё «хорошее», ожидаемое, а во второй уже наблюдается некорректное поведение или состояние.
Необходимо минимизировать расстояние между точками с известным «хорошим» и «плохим» состоянием до одного шага. Этот процесс можно проводить по-разному. Например, линейным образом перебирать все шаги внутри отрезка, каждый раз стартуя из начала алгоритма. Это оправдано, только если сам отрезок очень короткий.
Можно прибегнуть к дихотомии, сокращая длину отрезка в два раза на каждом заходе.
Число итераций при этом будет существенно меньше, чем при линейном переборе. Однако остаётся необходимость каждый раз перезапускать программу сначала. Хорошо, если при этом баг проявляет себя почти сразу после старта. А если до его возникновения каждый раз проходит несколько часов? Продуктивность отладки при этом всё ещё оставляет желать лучшего.
Отладка внутри симуляции
Как симуляция цифровых систем может помочь с отладкой? Выделю два приёма, которые, как будет показано далее, тесно связаны друг с другом.
Создание точек сохранения. Симулятор позволяет сохранить состояние всех моделей устройств: содержимое памяти, регистров ЦПУ и устройств, — на диск в виде файла. Затем из такой точки сохранения (англ. checkpoint или savepoint) можно неоднократно восстанавливать сценарий исполнения, экономя время на «добегании» от начала программы к интересующему региону. Я уверен, что читающие это игроки в компьютерные игры не раз пользовались механизмом сохранений для того, чтобы не начинать сложный уровень сначала.
Postal 2
Чувак: «Эту игру смогла бы пройти даже моя бабка, если бы она сохранялась столько же, сколько и ты!»
Обращение времени. Перезапуск симуляции из точки сохранения необходим, если обнаружено, что в процессе поиска мы переступили точку возникновения проблемы, и она уже проявилась. Вот было бы здорово, если бы можно было отойти на несколько шагов назад! Это дополнительно ускорило бы процесс. В таком случае поиск ошибочного шага выглядит примерно так:
Требования на симуляцию
Далеко не все процессы в реальном мире можно обратить вспять. Каждый, кто пытался вдавить зубную пасту обратно в тюбик, подтвердит это. Поэтому и не в каждой симуляции это возможно: требуются некоторые свойства от участвующих программных моделей и усилия их авторов, направленные на обеспечение ряда гарантий.
1. Возможность инспектирования состояния модели
Для создания точек сохранения, пригодных для последующего восстановления, каждая входящая в симуляцию модель устройства должна уметь достаточно детально представлять своё внутреннее состояние в некотором формате. Кроме архитектурного состояния (регистры, память) при восстановлении требуется знать о том, как отдельные устройства соединялись друг с другом.
Некоторые элементы состояния модели можно не сохранять, если они не отражают архитектуру представляемого ею устройства и могут быть однозначно восстановлены в будущем. Например, содержимое кэшей симулятора (но не кэшей моделируемого устройства!) используется только для ускорения работы модели и потому чаще всего может быть отброшено при сохранении. Кроме того, при восстановлении симуляции необходимо гарантировать, что такие кэши не будут содержать устаревшей информации, связанной с архитектурным состоянием модели до восстановления.
2. Детерминистичность
Под этим странным словом подразумевается повторяемость исполнения некоторого процесса для любых двух его прогонов с одинаковым исходным состоянием. Для однопоточной программы повторяемость считается ожидаемым свойством, если она написана без использования внешних генераторов случайных последовательностей и не имеет ошибок типа «обращение к неинициализированным данным». Для параллельных приложений повторяемость также возможна, но требует особенно аккуратного программирования. Для программных параллельных симуляторов я более подробно описал условия здесь.
Детерминистичность в сочетании с точками сохранения позволяет реализовать обратное исполнение.
Как это работает
Идея очень проста. В процессе прямого исполнения симулятор периодически создаёт точки сохранения (необязательно на диске, они могут храниться и в памяти, т.е. быть снимками состояния, англ. snapshot). При необходимости откатиться на несколько шагов назад сперва восстанавливается точка, ближайшая слева к желаемой позиции, и из неё происходит прямое исполнение до требуемого места. После этого благодаря детерминированности модели её состояние выглядит так, как будто симулируемое время действительно откатилось назад.
Допустим, состояние симуляции находится в точке с Tsim=100 (время измеряем в шагах алгоритма; это могут быть такты, инструкции или другие дискретные единицы). Из этой точки необходимо просимулировать время назад на 20 шагов. При этом ближайшее сохранение было сделано в момент Ts=50.
- Восстанавливается точка сохранения. После этого Tsim = Ts = 50.
- Происходит прямая симуляция в течение 30 шагов. После этого Tsim = 80.
Особенности и компромиссы
Практическая ценность обратного исполнения как инструмента ускорения отладки при симуляции зависит от частоты создания снимков. Чем чаще они делаются, там быстрее будет работать обратное исполнение. При этом прямую симуляцию необходимо будет так же часто прерывать, чтобы сохранять её состояние, что негативно скажется на её скорости. Кроме того, сами точки надо где-то хранить, в памяти или на диске, а они являются ограниченными ресурсами.
Здесь перед создающими reverse execution программистами открывается масса возможностей по реализации всевозможных эвристик: инкрементальные точки сохранения, удаление «старых» точек, изменяющийся интервал между снимками, прозрачное сжатие данных для экономии места и т.д.
Боремся с неповторяемостью
Два требования, обозначенные выше, достаточны, если все данные, необходимые для симуляции, уже содержатся внутри неё, т.е. она самодостаточна. Но часто оказывается, что в процессе работы симуляция взаимодействует с внешним миром, который совсем не расположен к повторяемости.
Пример такого «неповторимого» внешнего источника — человек. То есть оператор, взаимодействующий с компьютером и нажимающий кнопки на клавиатуре тогда, когда ему вздумается. Ни о какой воспроизводимости вводимых данных говорить не приходится; на постоянство длин временных интервалов между отдельными нажатиями надеяться не приходится и т.д. Однако повторяемость ввода критична для многих сценариев симуляции — прерывания, приходящие в ином порядке, вызовут совершенно иное исполнение кода ОС и пользовательских приложений. Другой источник — сетевые пакеты в ситуациях, когда реальная и симулируемая сети имеют точки соприкосновения.
Решение состоит в записи трассы потока данных от всех внешних источников при первой прямой симуляции. В последующих воспроизведениях внешние события берутся из этой трассы, а не из реальности. Пользователь/сеть при этом отключены от систем ввода.
Практическая реализация
Симуляторы
Ещё раз подчеркну: обратное исполнение возможно, если симулятор 1) может создавать точки сохранения и 2) детерминистичен. Если модель должна взаимодействовать с внешним миром, присущий ему индетерминизм может быть «скомпенсирован» записью трассы.
Многие из известных симуляторов умеют создавать точки сохранения/снимки. Лишь несколько примеров: Oracle VirtualBox, Qemu, Bochs, FCEUX (эмулятор NES/Dendy). В случае виртуальных машин снимки часто используются для обеспечения миграции между хозяйскими системами.
Детерминистичность симуляции гарантируется значительно меньшим числом программных симуляторов. Из открытых проектов мне на ум приходит только FCEUX. Буду признателен, если в комментариях мне укажут на другие примеры.
Механизм reverse execution, как он описан в этой статье, реализован в полноплатформенном функциональном симуляторе Wind River Simics. В следующем видео я демонстрирую загрузку ядра Linux внутри Simics, затем использую обратное исполнение для возвращения состояния симуляции к точке в прошлом [Для того, чтобы на видео можно было разобрать буквы, рекомендуется смотреть его с настройками 720p].
Классические отладчики
Обращение времени является довольно общей идеей, применимой для нужд отладки, поэтому она, без сомнений, может быть реализована и в классических дебаггерах. Возможности обращения времени при отладке доступны в отладчике TotalView от RogueWave (статья), хотя я им лично не пользовался.
Если у читателей есть информация о других инструментах, поддерживающих что-то похожее, то просьба написать об этом в комментариях.
P.S. Я сам с нетерпением жду появления подобной функциональности в GDB. И кажется, есть даже надежда.
