Автоматический поиск состояний гонок в ядре OC Linux (1187393), страница 5
Текст из файла (страница 5)
Однако она появляется при использовании барьероввместе с атомарными операциями, поскольку барьеры изменяют их семантику. Например последовательное использование барьера записи (англ. write barrier) и атомарной операции записи с семантикой relaxed эквивалентно осуществлению атомарной операции записи с семантикой release.
Аналогично, последовательное использование атомарной операции чтения с семантикой relaxed и барьера чтения (англ.read barrier) эквивалентно осуществлению атомарной операции чтения с семантикой acquire. Более того, один барьер может изменить семантику сразу несколькихпредшествующих или последующих атомарных обращений к памяти.Для того, чтобы обрабатывать синхронизацию, осуществляемую с помощью барьеров и атомарных операций, был предложен следующий метод.
Его основная идеясостоит в том, чтобы воздействие на векторные часы потока и примитива синхронизации при последовательном использовании атомарной операции и барьера доступак памяти было таким же, как и при использовании атомарной операции с семантикой release или acquire. Для этого кроме обычных векторных часов каждому потокусоответствует еще пара векторных часов: release векторные часы и acquire векторные часы. Процедура обновления этих дополнительных векторных часов показана влистингах 9 и 10.
Семантикой барьера доступа к памяти считается release, если этобарьер записи, и acquire, если это барьер чтения. Под операцией Acquire для векторных часов понимается операция уведомления, то есть V C1 .Acquire(V C2 ) означаетуведомление векторных часов V C1 векторными часами V C2 .231234function OnMemoryBarrier ( thread , memoryOrder ) {if ( memoryOrder == Acquire || memoryOrder == AcquireRelease ) {thread . vectorClock . Acquire ( thread . acquireVectorClock ) ;}5DoMemoryBarrier ( memoryOrder ) ;67if ( memoryOrder == Release || memoryOrder == AcquireRelease ) {thread .
releaseVectorClock . Acquire ( thread . vectorClock ) ;}891011}Листинг 9: Аннотации барьеров доступов к памяти в детекторе KernelThreadSanitizer1234567function BeforeAtomicAccess ( thread , atomic , memoryOrder , isWrite ) {if ( memoryOrder == Release || memoryOrder == AcquireRelease ) {atomic .
vectorClock . Acquire ( thread . vectorClock ) ;} else if ( isWrite ) {atomic . vectorClock . Acquire ( thread . releaseVectorClock ) ;}}89101112131415function AfterAtomicAccess ( thread , atomic , memoryOrder , isWrite ) {if ( memoryOrder == Acquire || memoryOrder == AcquireRelease ) {thread . vectorClock . Acquire ( atomic . vectorClock ) ;} else if (! isWrite ) {thread . acquireVectorClock . Acquire ( atomic .
vectorClock ) ;}}Листинг 10: Аннотации атомарных операций в детекторе KernelThreadSanitizerДля того, чтобы подробнее понять, каким образом работают данные аннотации рассмотрим пример. Пусть поток последовательно исполняет барьер записи иатомарную запись с семантикой relaxed. Данная последовательность действий эквивалентна атомарной операции записи с семантикой release. В соответствие с используемыми аннотациями, во время барьера записи, который является барьеромс семантикой release, обычные векторные часы потока уведомят release векторныечасы потока. Далее, во время атомарной операции записи, release векторные часыпотока уведомят векторные часы примива синхронизации.
Данная последовательность уведомлений эквивалентна уведомлению векторных часов примива синхронизации векторными часами потока, что и происходит при атомарной операции записи24с семантикой release. Аналогично можно рассмотреть пример, в котором поток последовательно совершает атомарную операцию чтения с семантикой relaxed и барьерчтения.Данная реализация аннотаций позволят корректно обработать атомарные операции и барьеры доступов к памяти и не допустить ложных срабатываний. Однакоона имеет небольшой недостаток: она может приводить к лишней, паразитной синхронизации с точки зрения детектора.
Например, это происходит, когда поток послебарьера записи спустя какое-то время совершает не связанную логически с барьером атомарную операцию записи с семантикой relaxed. Для того, чтобы уменьшитьнегативный эффект от подобной паразитной синхронизации, была применена следующая эвристика: спустя несколько (на данный момент 3) входов и выходов из функций после барьера записи, содержимое release векторных часов потока очищается.Аналогичная операция осуществляется для acquire векторных часов потока.В ядре Linux присутствует большое количество функций для работы с атомарными переменными. Семантики атомарных доступов к памяти выполняемых некоторыми из этих функций незадокументированы ни в коде ядра, ни в сопутствующейдокументации.
Не смотря на это проводятся попытки формально описать модель памяти ядра Linux [32], в соответствие с которыми и были реализованы аннотации дляатомарных переменных.4.1.4Обработка обращения к памятиПеред каждым обращенем к памяти детектор осуществляет проверку на возможность состояния гонки между этим обращением и одним из предыдущих обращенийк той же ячейки памяти. Для этого сначала детектор проверяет, пересекаются лиучастки памяти в пределах 8-байтовой ячейки, к которой произошли обращения. Если это условие выполняется, то дальнейшие проверки производятся в соответствие сопределением состояния гонки.
Осуществляется проверка того, что обращения произошли в разных потоках, что хотя бы одно из обращений является операцией записии что обращения произошли без синхронизации. Проверка на наличие синхронизации делается с помощью векторных часов. В случае, если состояние гонки возможнопо определению, то печатается сообщение об ошибке. Псевдокод, иллюстрирующийалгоритм обработки обращения к памяти в детекторе KernelThreadSanitizer показан25на листинге 11.12345678910111213function OnMemoryAccess ( access ) {shadow = AddrToShadow ( access . addr ) ;for ( previousAccess in shadow ) {if ( accessesIntersect ( access , previousAccess ) &&( access . threadId != previousAccess .
threadId ) &&access . isWrite || previousAccess . isWrite &&(! access . isAtomic || ! previousAccess . isAtomic ) &&! HappensBefore ( previousAccess , access ) ) {ReportDataRace ( access , previousAccess ) ;}}UpdateShadow ( shadow , access ) ;}1415161718function HappensBefore ( previousAccess , access ) {oldThread = GetThread ( previousAccess . threadId ) ;return previousAccess . clock <=oldThread .
vectorClock [ access . threadId ) ;}Листинг 11: Обработка обращения к памяти в детекторе KernelThreadSanitizerСледует отметить, что состояние гонки будет найдено не только в том случае,если оно привело к каким-либо реальных ошибкам во время исполнения. Оно будетнайдено, если оно потенциально возможно при наблюдаемой последовательности обращений к памяти и использования примитивов синхронизации, которые осуществляют потоки.Проверка на возможность состояния гонки с текущим доступом к памяти осуществляется не для всех обращений, которые произошли к этой ячейке за все времяработы ядра до текущего момента, а только для тех, чье описание хранится в соответствующих ячейках теневой памяти.
При очередном обращении к памяти содержимоетеневой памяти необходимо обновить. Процедура обновления содержимого ячеек теневой памяти показана на листинге 12. Идея алгоритма обновления состоит в том,чтобы пытаться перезаписывать те ячейки, которые описывают более слабые с точкизрения алгоритма поиска состояний гонок доступы к памяти. В случае, если такаяячейка не найдена, то переписывается одна из случайных ячеек.261234567891011121314151617181920212223function UpdateShadow ( shadow , access ) {for ( slot in shadow ) {if ( slot . IsEmpty () ) {slot = shadow ;return ;}previousAccess = slot ;stored = false ;if ( access . offset == previousAccess . offset &&offset .
size == previousAccess . size ) {if ( access . threadId == previousAccess . threadId ||HappensBefore ( previousAccess , access ) ) {if ( AccessWeakerOrEqual ( previousAccess , access ) ) {slot = shadow ;stored = true ;}}break ;}}if (! stored )shadow [ Random () % 4] = access ;}24252627function AccessWeakerOrEqual ( first , second ) {return (( first . isAtomic << 1) + ( first . isWrite ^ 1) ) >=(( second . isAtomic << 1) + ( second .
isWrite ^ 1) )}Листинг 12: Обновление ячеек теневой памяти в детекторе KernelThreadSanitizer4.1.5Поиск ошибок в планировщикеПо сути, ядро представляет собой код, который исполняется на ядрах процессора. В ядре существует понятие задания (англ. task), определенное в его исходномкоде, которое представляет собой поток исполнения внутри ядра. Часть ядра, которая называется планировщиком (англ. scheduler), осуществляет периодическое переключение исполнения кода на каждом ядре процессора на одно из ожидающихисполнения заданий.В обычном режиме, детектор KernelThreadSanitizer, полагает, что задание – этои есть поток с точки зрения своего алгоритма. То есть состояния гонок ищутся между заданиями в ядре. При переключении заданий планировщик использует различ27ные примитивы синхронизации, которые детектору KernelThreadSanitizer приходится игнорировать.
В противном случае задания, которые последовательно запускаются планировщиком на одном ядре, окажутся синхронизированными. Кроме того,детектор игнорирует и обращения к памяти, которые происходят внутри планировщика. Игнорирование этих событий объясняется еще и тем, что неясно к какомупотоку эти события относить, ведь они происходят между заданиями при их переключении. При таком подходе поиск состояний гонок в планировщике становитсяневозможным.Тем не менее, возможен и другой подход, который позволяет искать состояниягонок в планировщике. Этот подход был реализован как отдельный режим в детекторе KernelThreadSanitizer и называется per-cpu режим.
Основная его идея состоитв том, что детектор с точки зрения своего алгоритма считает потоком не задание, аядро процессора. В результате с точки зрения детектора в ядре Linux всегда исполняется фиксированное количество потоков, которое равно количеству ядер процессора.При таком подходе становится неважно, что планировщик заданий являетсячастью ядра. Сами понятия планировщика и задания являются деталями реализациитестируемого кода и не влияют особенным образом на процесс обработки событийсинхронизации и обращений к памяти.Существенным преимуществом per-cpu режима является возможность поискаошибок в планировщике.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
