Автоматический поиск состояний гонок в ядре OC Linux (1187393), страница 2
Текст из файла (страница 2)
К ним относится, например, использование разделямой целочисленнойпеременной для подсчета статистики. Многие программисты не считают подобныесостояния гонок ошибками. Однако вследствие оптимизаций компилятора, такие состояния гонок приводят к настоящим ошибкам [8].2.1Неопределенное поведениеНекоторые ошибки приводят к неопределенному поведению (англ. undefinedbehaviour) программы. Это состояние возникает при нарушении программистом стандарта языка или спецификаций используемых программных функций или библиотек [5]. В этом случае компилятор или библиотека вправе выполнять некорректныеи неожиданные действия.Особенностью таких ошибок является то, что обычно они не имеют наблюдаемыхпоследствий, но иногда могут приводить к серьезным сбоям.
При этом условия возникновения этих ошибок могут быть трудновоспроизводимыми – например, зависетьот версии компилятора, библиотеки или операционной системы; частоты процессора, количества ядер или даже его температуры. Более того, многие такие ошибкиприводят не к мгновенным последствиям, а к порче данных, эффект от которой сможет наблюдаться лишь через некоторое время, затрудняя понимание и обнаружениеошибки.Состояния гонок относятся к ошибкам, порождающим неопределенное поведение. Начиная с версии C/C++ 11, стандарт языка явно об этом говорит [9].Для демонстрации последствий неопределенного поведения рассмотрим примерпрограммы [5], приведенный на листинге 1. В этой программе на последней, 64-й,итерации цикла происходит переполнение целочисленной знаковой переменной value.По стандарту C/C++ результат переполнения знаковых целочисленных переменныхнеопределен. Это очень распространенный тип ошибок, который нередко приводитк серьезным уязвимостям программного обеспечения [10].61# include < stdio .h >234567891011void foo ( int * array ) {int value = 0 x03020100 ;for ( int i = 0; i < 64; i ++) {printf ( " % d ␣ " , i ) ;array [ i ] = value ;value += 0 x04040404 ;}printf ( " \ n " ) ;}121314151617int main () {int values [64];foo ( values ) ;return 0;}Листинг 1: Пример программы с переполнением целочисленной переменнойОжидаемый результат работы функции foo при запуске такого кода – печатьзначений от 0 до 63, а также заполнение аргумента-массива значениями.
Этот результат действительно наблюдается при использовании компилятора GCC [11] версии 4.8.1 с настройками по умолчанию, как показано на листинге 2.12$ g ++ test . cpp && ./ a . out0 1 2 ... 61 62 63Листинг 2: Запуск программы с переполнением целочисленной переменнойОднако при включении компиляторных оптимизаций на 64-битной архитектуре результат получается другой.
В данном случае печать значений продолжаетсяи после 63 до тех пор, пока не произойдет ошибка сегментации, как показано налистинге 3.123$ g ++ - O2 test . cpp && ./ a . out0 1 2 ... 61 62 63 64 65 66 ... 2062 2063 2064Segmentation faultЛистинг 3: Запуск программы с переполнением целочисленной переменной,скомпилированной со включением компиляторных оптимизацийТакое поведение программы связано с наличием в ней неопределенного поведения, поскольку в этом случае компилятор вправе породить произвольный код после7возникновения ошибки.
При компиляции примера из листинга 1 получается ассемблерный код, приведенный в листинге 4. Видно, что в полученном коде нет условныхпереходов, которые могли бы прекратить исполнение цикла; также нет и инструкций возврата. Когда о таком поведении было сообщено разработчикам GCC, ониотказались что-либо менять, сославшись на неопределенное поведение [12].1234567891011121314151617181920. LCO :. string " % d ␣ "foo :push% r12mov% rdi , % r12push% rbpmov$0x3020100 , % ebppush% rbxxor% ebx , % ebxxchg% ax , % ax. L2 :mov% ebx , % edxmov. LCO , % esimov$0x1 , % edixor% eax , % eaxcallq __printf_chksmov% ebp , (% r12 ,% rbx ,4)add$0x4040404 , % ebpadd$0x1 , % rbxjmp. L2Листинг 4: Ассемблерный код, получаемыйпереполнением целочисленной переменнойприкомпиляциифункциисТаким образом, следует отметить, что неопределенное поведение может приводить не только к некорректному результату ошибочной операции, но и к произвольным результатам любых дальнейших операций.
Понятно, что если одна и та жеошибка по-разному проявляется при использовании одного и того же компилятора с разными настройками, то подобные ошибки могут становиться наблюдаемымипри переходе на новую версию компилятора, процессора и вообще программногои аппаратного обеспечения. Другими словами, при наличии в программе ошибки,приводящей к неопределенному поведению, даже если сегодня программа работаеткорректно, то никто не может гарантировать, что программа продолжит работатькорректно завтра.82.2Поиск состояний гонокДля поиска состояний гонок динамические детекторы отслеживают обращенияпрограммы к памяти (переменным) и использование программой примитивов синхронизации во время исполнения.
Для проверки того, находятся ли два доступа к памяти в состоянии гонки в соответствие с определением, детектору необходимо уметьпроверять возможность одновременности двух событий. Существует два классических алгоритма, используемых в динамических детекторах для поиска состоянийгонок: Lockset и Happens-before. Каждый из этих алгоритмов по-своему определяетпонятие одновременности и в соответствие со своим определением ищет состояниягонок.2.2.1Алгоритм LocksetАлгоритм Lockset строится из предположения, что каждой переменной, котораяможет быть использована из нескольких потоков, должен соответствовать синхронизирующий доступы к ней мьютекс.
Данный алгоритм был разработан для динамического детектора Eraser, применявшегося для тестирования программного обеспечения серверов поисковой компании AltaVista в середине 1990-х годов [13].Определение. Мьютекс (англ. mutex от “mutual exclusion”, “взаимное исключение”) – это такой объект, который находится в одном из двух состояний: свободный или захвачен (взят) потоком T .
Над свободным мьютексом M поток T может выполнить операцию захвата (англ. lock), а затем этот же поток можетвыполнить операцию освобождения (англ. unlock). При попытке потока T захватить мьютекс M , уже захваченный другим потоком T 0 , поток T блокируется довозможности захватить мьютекс M .Определенный таким образом мьютекс обладает свойством взаимного исключения (англ. mutual exclusion), то есть он может быть захвачен только одним потоком.Алгоритм Lockset считает, что два доступа к памяти могут произойти одновременнотогда и только тогда, когда не существует мьютекса, взятого при обоих доступах.Алгоритм Lockset работают следующим образом [5].
Алгоритм отслеживает операции взятия мьютексов и обращения к разделяемым переменным осуществляемыепотоками исполнения. Каждой разделяемой переменной V ставится в соответствие9множество мьютексов (англ. lockset) LS(V ), которые были взяты при каждом обращении к этой переменной. Первоначальное значение LS(V ) для каждой переменнойзадается как множество всех возможных мьютексов.
При каждом обращении потоком T к разделяемой переменной V в LS(V ) записывается пересечение старогозначения LS(V ) и множества взятых потоком T мьютексов. Если множество LS(V )становится пустым, то это значит, то не существует ни одного мьютекса, которыйбы синхронизировал доступы к V . В этом случае выводится сообщение об ошибке.Псевдокод алгоритма представлен в листинге 5.123function InitializeShadowValue ( V ) {LS ( V ) = GetMaximumLockset () ;}45678910function HandleMemoryAccess (T , V ) {LS ( V ) = LS ( V ) .
Intersect ( GetCurrentLockset ( T ) ) ;if ( LS ( V ) . Empty () ) {ReportRace (T , V ) ;}}Листинг 5: Псевдокод алгоритма LocksetАлгоритм Lockset не пропускает ошибок, то есть если при исполнении многопоточного кода возникло состояние гонки, оно будет обнаружено детектором. Еслинекоторый мьютекс M ∈ LS(V ), то либо он был захвачен при всех доступах к V , либок V еще не было ни одного доступа.
А значит, если алгоритм Lockset не обнаружилсостояние гонки на переменной V , то к этой переменной либо не было доступов, либопри выполнении всех доступов был захвачен хотя бы один мьютекс. Таким образом,состояние гонки невозможно по определению.К сожалению, алгоритм Lockset имеет ложные срабатывания, то есть если детектор выводит сообщение о найденной ошибке, то это не значит что ошибка на самомделе произошла. В частности ошибки происходят при использовании в программесредств синхронизации, отличных от мьютексов (семафоры, атомарные переменные,и т.д.).10T1T2T3E1E2E3Signal(P1 )E4W ait(P1 )E5Signal(P2 )E6W ait(P2 )E7Рис.
1: Иллюстрация отношения предшествования2.2.2Алгоритм Happens-beforeАлгоритм Happens-before использует отношение частичного порядка “предшествует” (англ. happens-before) для проверки одновременности событий [14]. Это отношение определяется следующим образом [5].Определение.
Событие A предшествует (англ. happens-before) событию B (A ≺B), если выполнено хотя бы одно из следующих утверждений:• A и B были выполнены одним и тем же потоком исполнения и A произошлораньше B;• A является уведомлением (англ. signal) некоторого примитива синхронизации P , при этом B является ожиданием (англ.
wait) на этом примитиве;• Существуют такие события A0 и B 0 , что A A0 ≺ B 0 B (свойство транзитивности).На рисунке 1 иллюстрируется это определение. В трех потоках исполнения T1 ,T2 и T3 происходят события E1 , E2 , ..., E7 . Кроме того, имеется два примитива синхронизации P1 и P2 на которых происходят события уведомления и ожидания.В соответствие с определением:11• E1 ≺ E4 , так как E1 произошло раньше E4 в одном потоке;• Signal(P1 ) ≺ W ait(P1 ) и Signal(P2 ) ≺ W ait(P2 ), так как события являютсяуведомлением и ожиданием на одном и том же примитиве;• E1 ≺ E7 по свойству транзитивности;• E4 ⊀ E2 , E2 ⊀ E3 , так как события не упорядочены.Детекторы, работа которых основана на этом алгоритме, во время исполненияпрограммы отслеживают доступы к памяти и использование примитивов синхронизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
