Динамический анализ по-гугловски

ВВЕДЕНИЕ

Гонка сигналов, применительно к вычислительным системам, – это состояние, возникающее, когда два потока пытаются одновременно получить доступ к общему участку памяти (разделяемому ресурсу), и при этом хотя бы один из них пытается получить доступ на запись.

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

Задача точного определения гонок относится к классу NP-сложных. Тем не менее, вычислительно разрешимой является задача определения гонок сигналов с приемлемой точностью (некоторые гонки все же будут пропускаться; возможны также и ложные срабатывания).

Практически все современные программные средства используют механизмы многопоточных вычислений. Безусловно, их код можно проверять и простым модульным тестированием, и навороченным интеграционным, или же регрессионным тестированием. Недостатком подобного подхода, конечно же, будут являться большие затраты по времени (в случае модульного тестирования) сложность разработки и привлечения специалистов, способных проводить такое тестирование (в случае регрессионного или итерационного тестирования), а также отсутствие какой-либо автоматизации тестирований.

Именно поэтому специалисты компании Google решили, наконец, разработать утилиту, способную воспроизводить непрерывный поиск гонок сигналов в реальном времени.

ОПИСАНИЕ подхода компании Google к решению проблемы.

Имеется ряд подходов выявления гонок. Однако, для них можно выделить три основных метода: статический (static), реального времени (onthefly), и, «посмертный» (postmortem). Последние два также можно озаглавить как динамические методы выявления гонок.

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

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

Большинство программ, реализующих динамические методы определения гонок, базируются на использовании следующих алгоритмов:

—        алгоритм «произошло-до» (англ. — happens before; алгоритм определяет отношение частичного порядка для событий, его использование позволяет установить причинно-следственную связь между событиями)

—       алгоритм набора блокировки (англ. — lockset or both; алгоритм набора блокирования выявляет потенциально возможные гонки при одновременном доступе нескольких потоков к памяти без захвата общей блокировки)

О РЕАЛИЗАЦИИ

Поначалу в Google использовали Helgrind, в которой реализован гибридный алгоритм. Его показатели ошибок первого и второго рода оказались неудовлетворительными, и было принято решение видоизменить гибридный алгоритм, а также добавить режим функционирования с использованием классического алгоритма happens before. Алгоритм happens before в его новой реализации, по сравнению с изначальным алгоритмом Helgrind’a реже определял безопасные реализации критических секций уязвимыми ошибочно, однако пропускал гораздо больше действительно уязвимых участков кода.

Главным преимуществом утилиты перед аналогами является реализация happens-before алгоритма, позволяющая хранить данные о всех предыдущих произошедших блокировках.

Итак, поскольку Helgrind не устраивал разработчиков Google, на свет появилась новая (также базирующаяся на Valgrind) утилита от Google. Ее назвали «ThreadSanitizer». Быстрая, однако точная и с интуитивно понятным интерфейсом.

Оригинал статьи можно найти на странице проекта.