?

Log in

Программистское: статистическая и доказательная стратегии защиты от ошибок - Не кинокритик. Не палеонтолог.

июл. 30, 2009

11:14 am - Программистское: статистическая и доказательная стратегии защиты от ошибок

Previous Entry Поделиться Next Entry

Расскажу об одном интересном баге из моего геймдевелоперского прошлого.

Хотя нет, сначала будет мораль, а сама история потом.

Как всем известно, от ошибок можно защищаться runtime-тестированием, а можно - build-time проверками. К первой группе относятся monkey testing, ассерты, функциональные и регрессионные тесты, и некоторые более экзотические практики. Ко второй группе относятся проверки типов на этапе компиляции, инструменты, проводящие анализ кода (например, lint и т.п.), и unit-тесты. В геймдеве к этой группе также относятся проверки, производимые на этапе сборки ресурсов редактором в бинарное внутриигровое представление (см. на эту тему хорошую статью aruslan'а, за шесть лет не потерявшую своей актуальности).

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

Скажем, компилятор С++ или Java гарантирует нам, что объект "не того типа" не может быть передан в качестве параметра функции, а у объекта не может быть вызван несуществующий метод. В Python проверить то же самое можно с помощью юниттестов, регрессионных и функциональных тестов, а также прославленным в веках методом "несколько раз запустить и посмотреть, не упадет ли". Хотя оба подхода на практике могут обеспечивать надежность, которая всех устраивает, отличие между ними довольно резкое: никакие тесты не покроют все множество возможных ситуаций. Всегда остается крохотная возможность того, что пользователь программы сделает что-то такое экзотическое, и скрытый баг вылезет наружу.

Конечно, тут вам не математика, и даже "доказательства" при помощи компилятора не могут быть абсолютно надежными. Теоретически, например, в нем самом может содержаться редкая ошибка. На практике, однако, подобной возможностью можно смело пренебрегать. Причин тому масса: компиляторы в среднем гораздо надежнее, нежели "обычные программы", а их поведение гораздо строже регламентировано; даже если компилятор "умолчал об ошибке", она вскроется при небольшом изменении в коде; мы говорим не об одном редком событии, а о стечении сразу двух маловероятных обстоятельств (компилятор не заметил ошибку программиста, которая при этом она крайне редко проявляется); ну и т.д и т.п.

Уже несколько раз в разных обсуждениях на эту тему я приводил такой вот пример. Полтора года назад, когда мы в Vogster'е доделывали Robocalypse на DS, тестировщики нашли рассинхронизацию в multiplayer'е. Это крайне неприятный тип ошибки. Многопользовательская игра у нас была организована по p2p-схеме: разные DS-ки передавали друг другу только команды пользователей, и каждая просчитывает состояние всего мира. Это идеальная для RTS схема, позволяющая организовать богатую фичами игру на основе очень узкого канала передачи данных и минимального "языка общения". Основной ее недостаток в том, что вся игровая логика должна быть абсолютно детерминированной, то есть, получая один и тот же набор команд, на выходе всегда иметь одинаковое состояние игрового мира. То есть нельзя никакого random'а, никакой зависимости от системного таймера, никаких шалостей с битами округления, никаких неинициализированных переменных и т.п. Как только рассинхронизация произошла, она уже фатальна: расхождения, даже начинающиеся с одного бита, быстро накапливаются, и скоро оба игрока видят совершенно разные картины происходящего (как правило, оба выигрывают с огромным перевесом). При помощи подсчета контрольных сумм факт рассинхронизации можно установить с точностью до такта просчета игровой логики, а вот дальше уже нужно целое расследование. Если вы можете себе позволить сериализовать все игровые данные с какими-то аннотациями, а затем сравнить два дампа с разных компьютеров/консолей, расследование того, что именно произошло, несколько упрощается. К сожалению, у нас и этой возможности не было.

Описание бага, которое я получил от тестера, выглядело так: "Иногда при невыясненных обстоятельствах происходит рассинхронизация. Что именно к ней приводит, непонятно. Reproduce: создать игру на 4 человек, и играть до посинения, активно пользуясь героями и их возможностями. Если игра закончилась, и все хорошо, повторить. Рано или поздно, сейчас или через день, она случится".

Зашибись. В попытках повторить баг я провел пару часов, но лишь убедился, что да, "оно случается". Что делать?

Хорошо, а почему вообще игра может рассинхронизироваться? Насчет неинициализированных переменных, к счастью, можно было не волноваться - у нас было собственное управление памятью, геймплейные данные всегда лежали в отдельном месте, изначально заполненном нулями, так что их состояния в отсутствие рассинхронизации совпадали бы до бита, даже если бы неинициализированные переменные встречались. На самом деле я к тому же был почти уверен, что их нет, поскольку регулярно проверял на этот счет код специальным анализатором (нивальцы, возможно, помнят, его ранний аналог Arch). Значит, кто-то совершил святотатство - позвал из игровой логики функцию, которая не обязана работать синхронно; например, обратился к интерфейсу. Строго говоря, сделать это не так-то просто: для этого нужно как минимум написать внутри игровой логики #include <../../interface/blah-blah.h> и ни о чем в этот момент не задуматься. Простой поиск регулярного выражения в коде показал, что такую глупость никто не совершал.

В этот момент я осознал, что передо мной задача проверки типизации. Не очень, правда, распространенная: меня интересовали не типы в смысле языка, а "логические типы" функций. Какой-нибудь Haskell не видит особенных различий между этими понятиями, и правильно делает, но у нас-то C++.

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

Что здесь важно:
1) в коде содержались какие-то нарушения этих правил, иначе ошибка не возникала бы
2) вовсе не любое такое нарушение будет приводить к рассинхронизации, но если их не будет, то отсутствие рассинхронизаций будет математически строго доказуемо

Отлично, оставалось поработать заместителем компилятора, и явным образом переименовать все фунции doSmth на границе между игровым миром, интерфейсом и графикой либо в doSmthSync, либо doSmthAsync, параллельно отслеживая, кто кого вызывает. Не прошло и часа, как все нарушения "типизации" были ликвидированы, а я смог восстановить цепочку событий, приводящих к рассинхронизации.

Ошибка оказалась в том месте, где интерпретировалась команда сбрасывания наковальни (это в Robocalypse такой мультяшный аналог ядерного оружия). Чтобы проверить, сброшена она куда-то в пустую точку игрового поля, или же наведена на конкретного юнита, по ошибке использовалась конструкция isVisible(getCurrentPlayer()), а не isVisible(игрок, который сбрасывает наковальню).

Вот как воспроизводился баг: одному игроку нужно было построить Скаута, сделать его невидимым, и пойти на вражескую базу. Второму нужно было построить снайпера и использовать способность "сбросить наковальню" на точку, в которой стоит (или через которую проходит) невидимый скаут (вернее, на верхнюю половину его туловища). Эта команда на одной DS-ке означала "сбросить наковальню в точку за торсом скаута", а на другой - "сбросить наковальню на этого скаута" (то есть в точку у него под ногами). Мало того, важно было при этом не подходить черезчур близко к нему, чтобы не "заметить" его и не вывести из состояния невидимости.

Я не представляю себе юнит-, да и какой угодно еще тест, который был бы способен отловить подобное фантастическое стечение обстоятельств. Чтобы в игре не было подобных ошибок, необходимы живые самоотверженные тестировщики, и крайне желательна математическая строгость кода.

Tags: ,

Comments:

[User Picture]
From:sim0nsays
Date:Июль 30, 2009 06:35 pm
(Link)
Механизм реплея бы в идеале. Ну и вообще говоря случайные долгие стрессы могут и не такое найти :)
(Ответить) (Thread)
[User Picture]
From:miniversum
Date:Июль 30, 2009 06:44 pm

Вопрос

(Link)
""Это идеальная для RTS схема, позволяющая организовать богатую фичами игру на основе очень узкого канала передачи данных и минимального "языка общения". ""

Скажите, а почему "узкого", там же вайфай? Какие там ограничения канала?
(Ответить) (Thread)
[User Picture]
From:orvind
Date:Июль 31, 2009 02:56 pm

Re: Вопрос

(Link)
Там не вайфай, там довольно хитрый и ограниченный закрытый нинтендовский протокол. Мы потребляли 128 байт за кадр (fps около 50). Большая часть команд была сильно меньшего размера, но экономить трафик смысла не имело.
В данном случае узкий канал - это когда вы не успеваете за такт логики передать 2 координаты и кучу внутренних параметров всех юнитов.
(Ответить) (Parent) (Thread)
[User Picture]
From:alll
Date:Июль 30, 2009 07:04 pm

(void*)

(Link)
> Скажем, компилятор С++ или Java гарантирует нам, что объект "не того типа" не
> может быть передан в качестве параметра функции, а у объекта не может быть
> вызван несуществующий метод.

Компилятор C++ не "гарантирует", а "позволяет необоснованно надеятся".
(Ответить) (Thread)
[User Picture]
From:aruslan
Date:Июль 30, 2009 09:51 pm

Re: (void*)

(Link)
В корень зришь!
(Ответить) (Parent) (Thread)
From:ext_72902
Date:Июль 31, 2009 04:32 am

Re: (void*)

(Link)
Да уж. Сколько из-за этого траблов было...
(Ответить) (Parent) (Thread)
From:sleepy_drago
Date:Июль 30, 2009 07:47 pm
(Link)
к компилятору плюсов есть море пожеланий :)
буквально два часа назад я захотел warning на throw; написанный вне блока catch.

зы.Выглядело это так - сосед как обычно ловит креш в отладчике и смотрит стек. И совешенно офигевает от увиденного и спрашивает меня wtf. С помощью мата и пинков отладчика выясняем что прога перед смертью вызвала конструктор stlport::NamedException и благополучно ушла в kernel32.dll. У товарища как на радость символов этого кернела не было (он про них благополучно не знал) и пинками нашли исходник этого NamedException и смогли посмотреть что за аргумент - ага щазз "Bad Ptr" в общем сидим в шоке.
И тут идея - ну ка поищем throw. Нашли 2 штуки. И один из них просто "throw;" :D просто так на ровном месте. Вот такая вот "жесть как она есть" :) и это обычный день ++ разработчика ))
(Ответить) (Thread)
(Удалённый комментарий)
From:sleepy_drago
Date:Август 1, 2009 03:00 pm
(Link)
просто как раз подвернулось. Обычно сосед получает нормальный стек и меня не трогает, а тут вот так вот.
А тут люди мечтают о доказательстве каких то там свойств программы.
Мне на рсдне в дискуссии по депендент типам понравилась шутка практиков - "багов не бывает тк баг это отклонение от формальной спеки. А формальную спеку можно было бы преобразовать в программу автомагически. Поэтому никакая типизация не устранит то что юзер называет багом."
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]
From:strangeraven
Date:Июль 30, 2009 09:21 pm
(Link)
Баги с рассинхронизацией и правда мерзкие.

Есть еще одна природа их возникновения - указатели. Например, использовать адрес объекта как ключ в хэш-таблице. В java похожая подляна получается, если не перекрыть hashCode у Object - они от запуска к запуску недетерминированы.
(Ответить) (Thread)