Обращая симулируемое время

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

^{Автор фото: Иван Андреев}

Я уверен, что у многих читателей при отладке приложений периодически возникает желание отступить на шаг (или два, десять…) назад от текущей строки, чтобы увидеть причины происходящего. Чаще всего ради этого приходится перезапускать отладку с начала и пытаться поймать исполнение чуть раньше

Сначала немного философии. Зачем вообще нужно прямое, т.е. «нормальное» прямое исполнение программ? Чтобы получить результат некоторого вычисления, который нежелательно/трудно/невозможно выполнять вручную. Расчёт полёта ракеты — это вычисления. Просмотр котиков на сайте — это вычисления. Процесс вычисления может быть формализован с помощью представления его в форме алгоритма.

Для чего это нужно

Для чего может понадобиться исполнение обратное? Для того, чтобы помочь понять, почему вычисления привели к тому или иному результату.

Поддержку функциональности обращения течения программы возможно включать в различные инструменты, используемые программистами. Далее в основном речь пойдёт об её реализации в симуляторах. В этом контексте эта идея получает два варианта развития. Первое — это отладка исполняющегося внутри модели кода симулируемого BIOS/Firmware, ОС, приложения…, что интересно конечному пользователю симулятора — разработчику ПО. Второе применение — это отладка непосредственно симулятора (он тоже является программой). Это важно уже для разработчика моделей устройств, участвующих в процессе моделирования.

Отладка

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

Необходимо минимизировать расстояние между точками с известным «хорошим» и «плохим» состоянием до одного шага. Этот поиск можно проводить по-разному. Например, линейным образом перебирать все шаги внутри отрезка, каждый раз стартуя из начала алгоритма.

Это оправдано, только если сам отрезок очень короткий.

Можно прибегнуть к дихотомии, сокращая длину отрезка в два раза.

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

Отладка в симуляции

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

Создание точек сохранения. Симулятор позволяет сохранить состояние всех моделей устройств: содержимое памяти, регистров ЦПУ и устройств, — на диск в виде файла. Затем из такой точки сохранения (англ. checkpoint или savepoint) можно неоднократно восстанавливать сценарий исполнения, экономя время на «добегании» от начала программы к интересующему региону. Я уверен, что читающие это игроки в компьютерные игры не раз пользовались механизмом сохранений для того, чтобы не начинать сложный уровень сначала.

Обращение времени. Перезапуск симуляции из точки сохранения необходим, если обнаружено, что в процессе поиска мы переступили точку возникновения проблемы, и она уже проявилась. Вот было бы здорово, если бы можно было отойти на несколько шагов назад! И симуляция позволяет это делать!
Поиск точки с ошибкой при отладке под управлением симулятора выглядит примерно так:

Требования на симуляцию

Далеко не все процессы в реальном мире можно обратить вспять. Каждый, кто пытался вдавить зубную пасту обратно в тюбик, подтвердит это. Поэтому и не в каждой симуляции это возможно: требуются некоторые гарантии от программных моделей и усилия от их авторов.

Возможность инспектирования состояния модели

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

Детерминистичность

Под этим странным словом подразумевается повторяемость исполнения некоторого процесса для любых двух его прогонов с одинаковым исходным состоянием. Для однопоточной программы повторяемость считается чем-то само собой разумеющимся, при условии, что она работает без использования внешних генераторов случайных последовательностей и не имеет ошибок типа «обращение к неинициализированным данным». Для параллельных приложений повторяемость также возможна, но требует особенно аккуратного программирования.

Детерминистичность в сочетании с точками сохранения позволяет реализовать обратное исполнение.

Реализация

Боремся с неповторяемостью

Пример такого источника — человек. То есть оператор, взаимодействующий с компьютером и нажимающий кнопки на клавиатуре тогда, когда ему вздумается. Естественно, ни о какой воспроизводимости с его стороны надеяться не приходится.

Пример использования

Для Wind River Simics

Видео