Автоматический поиск состояний гонок в ядре OC Linux (1187393), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

В процессе исполнения, детектор строит определенное выше отношениепредшествования на множестве произошедших событий. Если обнаруживаются двадоступа по одному адресу памяти, хотя бы один из которых является записью и ниодин из них не предшествует другому, выводится сообщение о состоянии гонки.Существует несколько способов реализации вычисления отношения предшествования на множестве произошедших событий. Один из них – это построение ориентированного графа событий. Ребра проводятся между последовально происходящими событиями отдельных потоков, а также между парами событий уведомлениеожидание.

Для проверки отношения предшествования для двух отдельно взятых событий остается обойти этот граф. К сожалению обход графа для проверки каждогодоступа к памяти приводит к большим численным расходам.Существуют и другие алгоритмы вычисления отношения предшествования, эквивалентные обходу графа событий. Чаще всего используются более эффективныеалгоритмы, использующие векторные часы (англ. vector clock):Определение. Векторное время (англ. vector clock) V – это отображение измножества потоков во множество неотрицательных целых чисел V : τ → Z+ .Переменные, хранящие значение типа векторное время, будем называть векторными часами.Каждому потоку в программе T ставятся в соответствие свои векторныечасы VT .

Кроме того, каждому примитиву синхронизации P в программе также ставятся в соответствие свои векторные часы VP . Число, которое являетсяобразом VT (T ) для потока T и его векторных часов VT называется собственнымвременем этого потока.12Значения векторных часов определяются следующим образом:• При создании потока T его векторные часы получают значение1, t = T,VT (t) =0, t 6= T.• При обработке доступа к памяти, совершенного потоком T , часы этого потока «тикают» (собственное время потока инкрементируется):VT (t) + 1, t = T,0VT (t) = T ick(VT , T )(t) =VT (t), t 6= T.• При создании нового примитива синхронизации P , его векторные часы хранятнулевое значение для всех потоков:VP (t) = 0, ∀ t ∈ τ.• При уведомлении примитива P потоком T , векторные часы этого примитиваобновляется следующим образом:VP0 (t) = Join(VT , VP )(t) ≡ max(VP (t), VT (t)), ∀ t ∈ τ.Эта операция называется «объединением» векторных часов.

В этом случаеговорят, что векторные часы потока T уведомляют векторные часы примитива P .После этого часы самого потока T «тикают»:VT0 = T ick(VT , T ).• При возникновении события ожидания на примитиве P потоком T , новоезначение векторных часов потока равноVT0 = Join(VT , VP )В этом случае говорят, что векторные часы потока T ожидают векторныечасы примитива P .13Важной деталью реализации детекторов, основанных на алгоритме Happensbefore, является трактовка событий, связанных с операциями на мьютексах. Обычносчитается, что событие освобождения мьютекса U nlock(m) является уведомлениемпримитива m, а событие взятия Lock(m) является ожиданием m.

Векторные часы вэтих случаях обновляются соответственно.Фактически, элементу векторных часов VT (t), соответствующих потоку T , который является образом другого потока t, соответствует собственное время потокаt на тот момент, когда поток T последний раз с ним синхронизировался. Пользуясьэтим, возможно осуществить проверку того, являются ли два события синхронизированными в соответствии с алгоритмом Happens-before:Утверждение. Пусть события A и B произошли в потоках T1 и T2 соответственно, а VT1 и VT2 - это их векторные часы на момент возникновения событий. Тогда:(A ≺ B) <=> VT1 (T1 ) < VT2 (T1 )33.1Обзор динамических детекторовПрименение детекторовОбнаружение ошибки с помощью динамического анализатора возможно толь-ко во время исполнения участка кода, в котором эта ошибка допущена.

Вследствиеэтого для эффективного применения динамического тестирования необходимо иметьвозможность исполнять максимальное количество различных участков кода, относящихся к программе.Одним из возможных способов исполнения различных участков кода являетсяиспользование автоматического модульного тестирования (англ. unit testing).

Модульные тесты – это небольшие программы или специальные функции программытеста, которые обычно выполняют небольшое количество простых действий с программной компонентой, после чего сравнивают полученный результат с ожидаемым [5]. Модульные тесты хороши тем, что их можно многократно перезапустить вслучае возникновения недетерминированных ложных срабатываний или пропусковошибок. К сожалению, такой подход наследует от модульного тестирования основнойнедостаток – невозможность нахождения ошибок в коде, не исполняемом тестами.14Другим способом является использование рандомизированного тестирования(англ. fuzz testing). Рандомизированное тестирование заключается в автоматическойгенерации случайных данных, передаче их на вход программе и дальнейшее отслеживание появления исключительных ситуаций, например аварийного завершения [15].Особенностью такого подхода является возможность находить ошибки, происходящие при определенных сложных условиях, которые не удается придумать программистам и тестировщикам.При тестировании программ сами детекторы могут совершать ошибки.

В соответствии с классификацией ошибок [5], ошибкой первого рода или ложным срабатыванием (англ. false positive) называется такая ситуация, когда в результате работыдетектора пользователь получает отчет об ошибке, которой на самом деле в программе нет. Ошибкой второго рода или пропуском ошибки (англ. false negative) называетсятакая ситуация, когда в результате работы детектора пользователь не получает отчета об ошибке, которая на самом деле в программе есть. Следует отметить, что подошибками первого и второго рода подразумеваются особенности поведения конкретного алгоритма детектора, а не ошибки в исследуемых программах.Ложные срабатывания затрудняют применение детекторов, поскольку на анализкаждого отчета о найденной ошибке человек может тратить значительное количество времени.

Пропуски ошибок, в свою очередь, снижают пользу от использованиядетекторов, так как означают, что некоторые ошибки так и не будут найдены.3.2Внутреннее устройство детекторовМногие динамические детекторы ошибок работают следующим образом. Детек-тор отслеживает и анализирует осуществляемые программой действия при исполнении. В зависимости от информации, необходимой для поиска того или иного типаошибки, он может отслеживать различные события: обращения к памяти, выделениеи освобождение участков памяти, использование примитивов синхронизации и т.д.При обнаружении ошибки детектор выводит отчет, сообщающий о найденной ошибкеи содержащий информацию, полезную для локализации и исправления этой ошибки.153.2.1Теневая памятьМногие детекторы для каждой ячейки памяти приложения хранят связанные сней дополнительные данные.

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

Такой вариант устройства теневой памяти используется в детекторах AddressSanitizer [16] и ThreadSanitizer [6].Другие детекторы [17] могут использовать более сложную многоуровневую системуорганизации теневой памяти.3.2.2ИнструментацияПри каждом приложения к памяти детекторы часто осуществляют работу сданными, хранящимися в теневой памяти. Обычно, для этого перед каждым такимобращением добавляется дополнительный код. Процесс внедрения дополнительногокода в программу без изменения ее основной функциональности называется инструментированием или инструментацией (англ.

instrumentation) [5].Инструментация выполняется либо во время компиляции, либо перед исполнением программы, либо во время ее исполнения, и называется компиляторной, статической и динамической инструментацией, соответственно [5]. Для приложений пользователя известными примерами систем, использующих динамическую инструментацию, являются Valgrind [18], Pin [19] и DynamoRIO [20], популярными примерамииспользования компиляторной инструментации являются утилита исследования покрытия кода тестами gcov [21] и детектор ошибок mudflap [22], а в качестве примера16использования статической инструментации можно привести PEBIL [23].

Для ядраLinux примерами использования динамической инструментации являются PinOS [24],Kprobes [25] и KernInst [26], а в качестве примера использования компиляторной инструментации можно привести ftrace [27].3.2.3Библиотека времени исполненияДля работы детектора в тестируемое приложение необходимо включить реализацию алгоритма детектора.

Кроме того, при запуске приложения надо выделитьи подготовить к использованию теневую память. Зачастую для этих целей однойтолько инструментации недостаточно. В программу необходимо также встроить библиотеку времени исполнения (англ. runtime library). Она может содержать новыефункции и заменять реализации существующих.Новые функции встраиваются в программу для того, чтобы их можно было вызывать из внедренного инструментацией кода. Примером такой функции являетсяфункция печати отчета о найденной ошибке. Замена существующих функций бываетполезна, когда проще предоставить новую реализацию, чем заниматься инструментацией.Библиотека времени исполнения может внедряться в программу на стадии компиляции (при использовании компиляторной инструментации), на стадии компоновки (например при использовании статической инструментации) или при запуске (прииспользовании динамической инструментации) [5].3.3Существующие детекторы в пространстве ядраСуществует несколько детекторов состояний гонок в ядре Linux.

ДетекторыRaceHound [28] и KernelStrider [29] используют динамический анализ. Существуетстатический детектор состояний гонок CPALockator [30]. Этим детекторам присущиследующие недостатки: возможность искать состояния гонок только в отдельныхкомпонентах ядра, а не во всем ядре в целом, наличие сложных срабатываний исложность использования.Детектор RaceHound [28] работает следующим образом.

Во время исполненияядро прерывается в случайные моменты времени при обращении к памяти. Послепрерывания, на адрес памяти, к которому осуществляет доступ текущая инструкция,17ставится аппаратная точка прерывания (англ. hardware breakpoint). Далее делаетсянебольшая задержка в ожидании того, что какой-нибудь другой поток обратится кэтой области памяти. Если это произойдет, то аппаратная точка прерывания сработает и RaceHound сообщит о найденном состоянии гонки.Подход, используемый RaceHound, плохо работает для поиска состояний гонокв больших по размеру модулях ядра. Дело в том, что, чтобы RaceHound нашел состояние гонки, ядро должно быть прервано в том момент, когда исполняется однаиз инструкций, осуществляющая несинхронизованный доступ к памяти.

Характеристики

Список файлов ВКР