Автоматический поиск состояний гонок в ядре OC Linux (1187393), страница 4
Текст из файла (страница 4)
Даже еслиповторять процедуру прерывания очень часто, это событие довольно маловероятно.Однако RaceHound можно использовать для того, чтобы подтвердить потенциальноесостояние гонки, на которое укажет какой-нибудь другой детектор.Детектор KernelStrider [29] использует динамическую инструментацию для сбора информации об анализируемом модуле ядра в процессе его работы. Он отслеживает такие события как обращения к памяти и использование примитивов синхронизации и сохраняет последовательность событий для последующего анализа с помощьюдетектора ThreadSanitizer [6].К сожалению, при использовании динамической бинарной инструментации невозможно отследить использование некоторых низкоуровневых примитивов синхронизации (атомарные операции, барьеры доступов к памяти), поскольку часть информации теряется на этапе компиляции. Вследствие этого, KernelStrider имеет ложныесрабатывания, для устранения которых необходимо добавлять в код анализируемогомодуля специальные аннотации.
Кроме ложных срабатываний, недостатками детектора KernelStrider являются сложность настройки и запуска, а также возможностьанализировать только отдельные модули.Детектор CPALockator [30], построенный на основе CPAchecker [31], используетстатический анализ. Этот детектор использует алгоритм Lockset для поиска состояний гонок для поиска состояний гонок. Недостатком детектора CPALockator являетсяналичие ложных срабатываний вследствие использования статического анализа.184Детектор KernelThreadSanitizerСуществующие детекторы состояний гонок в ядре обладают существенныминедостатками.
Они нетривиальны в использовании, имеют ложные срабатывания испособны находить состояния гонок лишь в отдельных компонентах ядра. Эти недостатки были устранены в разработанном детекторе KernelThreadSanitizer, алгоритмкоторого основан на алгоритме детектора состояний гонок для приложений пользователя ThreadSanitizer, хорошо показавшего себя на практике.4.1Устройство детектора KernelThreadSanitizerДетектор KernelThreadSanitizer состоит из двух частей: одна является составля-ющей компилятора, а другая является компонентом ядра. Компиляторная составляющая осуществляет интрументацию доступов к памяти, а компонент ядра содержитв себе аннотации для используемых в ядре примитивов синхронизации и реализациюанализирующего алгоритма. Во время исполнения ядра детектор отслеживает обращения к памяти и использование примитивов синхронизации, которые происходят вядре, и передает их анализирующему алгоритму.
Анализирующий алгоритм основанна алгоритме Happens-before и использует концепцию векторных часов.4.1.1Теневая памятьKernelThreadSanitizer использует теневую память для хранения дополнительнойинформации о памяти ядра. На каждую 8-байтную ячейку памяти ядра, детекторхранит 32 байта теневой памяти. Эти 32 байта предсталуют собой 4 ячейки по 8 байт,каждая из которых описывает одно из последних обращений к соответствующийячейке памяти ядра.На данный момент теневая память выделяется каждый раз, когда ядро выделяеткакое-либо количество страниц физической памяти с помощью внутреннего распределителя памяти. Таким образом, каждому блоку выделенных страниц соответствуетсвой блок страниц теневой памяти.
Система адресации может быть реализована иболее оптимально: теневая память может быть выделена непрерывным участком,который отображается на память ядра сжатием со сдвигом.Каждая из ячеек теневой памяти описывает несколько параметров обращения к19памяти. Структура ячейки показана на листинге 6. Эта структура включает в себяидентификатор потока, совершившего доступ к памяти, его собственное время вовремя доступа, сдвиг от начала 8-байтовой ячейки памяти, соответствующий адресу обращения, размер доступа и два флага, говорящих о том, является ли доступоперацией записи или чтения и является ли доступ атомарным.12345678struct kt_shadow_s {unsigned long threadIdunsigned long clockunsigned long offsetunsigned long sizeunsigned long isWriteunsigned long isAtomic};::::::12;42;3;2;1;1;Листинг 6: Структура ячейки теневой памяти в детекторе KernelThreadSanitizerПод идентификатор потока в ячейке теневой памяти отводится 12 бит.
Это означает, что максимальное количество одновременно существующих потоков, котороедетектор способен обрабатывать равно 212 = 4096. Этого количества достаточно,чтобы проводить тестирование ядра и поиск состояний гонок с помощью рандомизированного тестирования, однако на реальных системах оно может достигать и больших значений.В следующем поле структуры хранится собственное время потока, совершившего доступ к памяти на момент этого доступа. Ограничение в 42 бита означает, чтомаксимальное значение собственного времени, которое поддерживает детектор равно242 . Это значение никогда не достигалось при тестировании, однако на практике этовозможно. На данный момент детектор необходимо перезапустить, если это произошло. Возможно реализовать специальные процедуры, которые будут обрабатыватьэто переполнение.При каждом обращении к ячейке памяти, соответствующие ячейки теневой памяти должным образом обновляются.
Однако это не означает, что в четырех ячейкахтеневой памяти хранятся четыре самые последние обращения к ячейке памяти ядра.Процедура обновления содержимого ячеек теневой памяти описана ниже. Размерячейки в 8 байт позволяет эффективно осуществлять действия с ячейкой теневойпамяти с помощью одной операции записи или чтения.204.1.2ИнструментацияKernelThreadSanitizer использует компляторную инструментацию, реализованную как проход компилятора GCC [11]. Компиляторный модуль инструментируетобращения к памяти и входы и выходы из функций. Инструментация обращенийк памяти необходима непосредственно для поиска состояний гонок, а инструментация функций необходима для печати содержательного сообщения об ошибке. Примеринструментации приведен на листинге 7.12void foo ( int * p ) {__tsan_func_entry ( __b uilt in_ retu rn_a ddre ss (0) ) ;3__tsan_write4 ( p ) ;* p = 42;456__tsan_func_exit () ;78}Листинг7:ПримерKernelThreadSanitizer4.1.3компиляторнойинструментациивдетектореАннотации примитивов синхронизацииВ ядре Linux используется немало различных примитивов синхронизации:• мьютексы (mutex, rwsem, percpu_rwsem),• спинлоки (spinlock, rwlock),• семафоры (sema, completion),• атомарные обращения к памяти и барьеры доступов к памяти,• и т.д.Для того, чтобы детектор мог отслеживать их использование, в код ядра былидобавлены так называемые аннотации (англ.
annotation). Аннотации представляютсобой вызовы функций детектора, которые никак не влияют на работу самих примитивов синхронизации. Важно отметить, что аннотации для примитивов синхронизации были добавлены разработчиками детектора, и пользователю их добавлять21не требуется до тех пор, пока он не использует в тестируемом коде собственноручнореализованные низкоуровневые примитивы синхронизации.Примитивов синхронизации в ядре очень много и их все необходимо аннотировать. Отсутствие аннотаций или неправильные аннотации хотя бы для одного изпримитивов будут приводить к ложным срабатываниям детектора.Функции, вызов которых добавлен в виде аннотаций в реализацию примитивовсинхронизации, осуществляют операции над векторными часами потока и векторными часами примитива синхронизации. Трактовка событий, связанных со спинлоками,мьютексами и семафорами не вызывает вопросов и соответствует приведенной приописании алгоритма Happens-before.
Пример аннотаций, добавленных в функциювзятия и освобождения мьютекса в ядре, можно увидеть на листинге 8.Можно заметить, что для аннотирования мьютекса было добавлено сразу двавызова функций детектора: до осуществления блокировки и после. Функция, вызываемая после блокировки, совершает операцию над векторными часами потокаи мьютекса. Наличие вызова функции до блокировки необходимо для того, чтобыотключить обработку событий использования примитивов синхронизации текущимпотоком на время блокировки мьютекса. Это связано с тем, что внутренняя реализация мьютекса использует несколько более низкоуровневых примитивов синхронизации.
Их обработка не привнесла бы никаких негативных эффектов с точки зрениявоздействия на векторные часы, но она была отключена с целью экономии памяти.12345678void __sched mutex_lock ( struct mutex * lock ){might_sleep () ;ktsan_mtx_pre_lock ( lock , true , false ) ; // Annotation .__mutex_fastpath_lock (& lock - > count , __mutex_lock_slowpath ) ;mutex_set_owner ( lock ) ;ktsan_mtx_post_lock ( lock , true , false , true ) ; // Annotation .}9101112131415void __sched mutex_unlock ( struct mutex * lock ){ktsan_mtx_pre_unlock ( lock , true ) ; // Annotation .__mutex_fastpath_ unlock (& lock - > count , __mutex _unlock_slo wpath ) ;ktsan_mtx_post_unlock ( lock , true ) ; // Annotation .}Листинг 8: Аннотации для мьютекса в детекторе KernelThreadSanitizer22События, связанные с атомарными (англ. atomic) доступами к памяти трактуются следующим образом.
Каждая атомарная переменная является примитивом синхронизации. Осуществление атомарной операции с семантикой (англ. memory order)release соответствует уведомлению примитива, осуществление атомарной операции ссемантикой acquire – ожиданию примитива, а осуществление операции с семантикойrelease-acquire – ожиданию и уведомлению примитива. В функции и макросы в ядре,выполняющие атомарные операции с семантиками release, acquire и release-acquire,были добавлены соответствующие аннотации.Особую сложность вызывает аннотирование барьеров доступов к памяти (англ.memory barriers). Дело в том, что сам по себе барьер доступа к памяти не осуществляет никакой синхронизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
