Главная » Статьи » Параллельное программирование

OpenMP и статический анализ кода

Авторы: Андрей Карпов, Евгений Рыжков

Дата: 10.11.2008

• Аннотация
• Введение
• Диагностические правила
  • Обобщенное исключение A
  • Правило N1
  • Правило N2
  • Правило N3
  • Правило N4
  • Правило N5
  • Правило N6
  • Правило N7
  • Правило N8
  • Правило N9
  • Правило N10
  • Правило N11
  • Правило N12
  • Правило N13
  • Правило N14
  • Правило N15
  • Правило N16
  • Правило N17
  • Правило N18
  • Правило N19
  • Правило N20
  • Правило N21
  • Правило N22
  • Правило N23
  • Правило N24
  • Правило N25
  • Правило N26
  • Правило N27
• Заключение
• Библиографический список

Аннотация

В статье рассмотрены принципы, положенные в основу реализации статического анализатора кода VivaMP. Приведенный в статье набор логических условий проверки позволяет диагностировать ряд ошибок в параллельных программах, созданных на основе технологии OpenMP.

Введение

Многие ошибки в программах, разработанных на основе технологии OpenMP, можно диагностировать с помощью статического анализа кода [1]. В данной статье приведен набор диагностических правил, выявляющих потенциально опасные места в коде, которые с высокой вероятностью содержат ошибки. Описанные ниже правила ориентированы для проверки Си и Си++ кода. Но многие из правил после небольшой модификации могут использоваться применительно и к программам на языке Fortran.

Описанные в статье правила лежат в основе статического анализатора кода VivaMP, разработанного в компании ООО "Системы программной верификации" [2]. Анализатор VivaMP предназначен для проверки кода приложений на языке Си/Си++. Анализатор интегрируется в среды разработки Visual Studio 2005/2008, а также добавляет раздел документации в справочную систему MSDN. Анализатор VivaMP включен в состав продукта PVS-Studio.

Данная статья пополняется и модифицируется вместе с развитием продукта PVS-Studio, На данный момент это третий вариант статьи, который соответствует PVS-Studio 3.40. Если в статье указано, что какие-то диагностические возможности не реализованы, то это относится к PVS-Studio 3.40. В дальнейших версиях анализатора данные возможности могут быть реализованы. Обратитесь к более новому варианту этой статьи или к документации по PVS-Studio.

Диагностические правила

Если не оговорено особо, то считается, что во всех правилах директивы используются совместно с директивой "omp". То есть описание, что используется директива "omp" опускается, чтобы сократить текст правил.

Обобщенное исключение A

Данное исключение применяется в нескольких правилах и для сокращения их текста вынесено отдельно. Общий смысл состоит в том, что мы находимся вне параллельной секции или явно указываем какой поток используется или экранируем код блокировками.

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

• Нет параллельной секции (нет директивы "parallel").
• Внутри параллельной секции используется критическая секция, заданная директивой "critical".
• Внутри параллельной секции имеется "master"-блок.
• Внутри параллельной секции имеется "single"-блок.
• Внутри параллельной секции имеется "ordered"-блок.
• Внутри параллельной секции используются функции вида omp_set_lock и произведена блокировка.

Правило N1

Опасным следует считать использование директив "for" и "sections" без директивы "parallel".

Исключения:

Директивы "for" или "sections" находятся внутри параллельной секции, заданной директивой "parallel".

Пример опасного кода:

#pragma omp for
for(int i = 0; i < 100; i++)
  ...

Пример безопасного кода:

#pragma omp parallel
{
  #pragma omp for
  for(int i = 0; i < 100; i++)
    ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1001. Missing 'parallel' keyword.

Правило N2

Опасным следует считать использование одной из директив, относящейся к OpenMP без директивы "omp".

Исключения:

Использование директивы "warning".

Пример опасного кода:

#pragma single

Пример безопасного кода:

#pragma warning(disable : 4793)

Диагностические сообщения, выдача которых основана на данном правиле:

V1002. Missing 'omp' keyword.

Правило N3

Опасным следует считать использование оператора for сразу после директивы "parallel" без директивы "for".

Пример опасного кода:

#pragma omp parallel num_threads(2)
for(int i = 0; i < 2; i++)
  ...

Пример безопасного кода:

#pragma omp parallel num_threads(2)
{
  for(int i = 0; i < 2; i++)
    ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1003. Missing 'for' keyword. Each thread will execute the entire loop.

Правило N4

Опасным следует считать создание параллельного цикла с использованием директив "parallel" и "for" внутри параллельной секции созданной директивой "parallel".

Пример опасного кода:

#pragma omp parallel
{  
  #pragma omp parallel for
  for(int i = 0; i < 100; i++)
    ...
}

Пример безопасного кода:

#pragma omp parallel
{  
  #pragma omp for
  for(int i = 0; i < 100; i++)
    ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1004. Nested parallelization of a 'for' loop.

Правило N5

Опасным следует считать совместное использование директив "for" и "ordered", если затем внутри цикла заданного оператором for не используется директива "ordered".

Пример опасного кода:

#pragma omp parallel for ordered
for(int i = 0; i < 4; i++)
{
  foo(i);
}

Пример безопасного кода:

#pragma omp parallel for ordered
for(int i = 0; i < 4; i++)
{
    #pragma omp ordered
    {
    foo(i);
  }
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1005. The 'ordered' directive is not present in an ordered loop.

Правило N6

Опасным следует считать вызов функции omp_set_num_threads внутри параллельной секции, заданной директивой "parallel".

Пример опасного кода:

#pragma omp parallel
{
  omp_set_num_threads(2);
}

Пример безопасного кода:

omp_set_num_threads(2);
#pragma omp parallel
{
  ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1101. Redefining number of threads in a parallel code.

Правило N7

Опасным следует считать нечетное использование функций omp_set_lock, omp_set_nest_lock, omp_unset_lock и omp_unset_nest_lock внутри параллельной секции

Пример опасного кода:

#pragma omp parallel sections
{
  #pragma omp section
  {
    omp_set_lock(&myLock);
  }
}

Пример безопасного кода:

#pragma omp parallel sections
{
  #pragma omp section
  {
    omp_set_lock(&myLock);
    omp_unset_lock(&myLock);
  }
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1102. Non-symmetrical use of set/unset functions for the following lock variable(s): %1%.

Правило N8

Опасным следует считать использование функции omp_get_num_threads в арифметических операциях.

Исключения:

Возвращаемое функцией omp_get_num_threads значение используется для сравнения или приравнивается переменной.

Пример опасного кода:

int lettersPerThread =
  26 / omp_get_num_threads();

Пример безопасного кода:

bool b = omp_get_num_threads() == 2;
switch(omp_get_num_threads())
{
  ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1103. Threads number dependent code. The 'omp_get_num_threads' function is used in an arithmetic expresion.

Правило N9

Опасным следует считать вызов функции omp_set_nested внутри параллельной секции, заданной директивой "parallel".

Исключения:

Функция находится во вложенном блоке, созданной директивой "master" или "single".

Пример опасного кода:

#pragma omp parallel
{
  omp_set_nested(2);
}

Пример безопасного кода:

#pragma omp parallel
{
  #pragma omp master
  {
    omp_set_nested(2);
  }
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1104. Redefining nested parallelism in a parallel code.

Правило N10

Опасным следует считать использование функций, использующих общие ресурсы. Примеры функций: printf.

Исключения:

Обобщенное исключение A.

Пример опасного кода:

#pragma omp parallel
{
  printf("abcd");
}

Пример безопасного кода:

#pragma omp parallel
{
  #pragma omp critical
  {
    printf("abcd");
  }
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1201. Concurrent usage of a shared resource via an unprotected call of the '%1%' function.

Правило N11

Опасным следует считать применение директивы flush к указателям

Пример опасного кода:

int *t;
...
#pragma omp flush(t)

Пример безопасного кода:

int t;
...
#pragma omp flush(t)

Диагностические сообщения, выдача которых основана на данном правиле:

V1202. The 'flush' directive should not be used for the '%1%' variable, because the variable has pointer type.

Правило N12

Опасным следует считать использование директивы "threadprivate".

Пример опасного кода:

#pragma omp threadprivate(var)

Диагностические сообщения, выдача которых основана на данном правиле:

V1203. Using the 'threadprivate' directive is dangerous, because it affects the entire file. Use local variables or specify access type for each parallel block explicitly instead.

Правило N13

Опасным следует считать инициализацию или модификацию объекта (переменной) в параллельной секции, если объект относительно этой секции является глобальным (общим для потоков).

Пояснение правила:

К глобальным объектам относительно параллельной секции относятся:

• Статические переменные.
• Статические члены класса (В текущей версии VivaMP данное правило не реализовано).
• Переменные, объявленные вне параллельной секции.
• При анализе кода функции, которая вызывается параллельно, глобальными объектами считаются глобальные переменные. Если анализируемая функция является членом класса, то считать члены класса глобальными или нет, зависит от того, как происходит вызов этой функции. Если вызов происходит из другой функции данного класса, то члены класса считаются глобальными. Если вызов происходит посредством оператора '.' или '->', то объекты также считаются глобальными.

Последний пункт нуждается в пояснении. Приведем пример:

class MyClass {

public:

int m_a;

void IncFoo() { a++; }

void Foo() {

#pragma omp parallel for

for (int i = 0; i < 10; i++)

IncFoo(); // Variant. A

}

};

MyClass object_1;

#pragma omp parallel for

for (int i = 0; i < 10; i++)

{

object_1.IncFoo(); // Variant. B

MyClass object_2;

object_2.IncFoo(); // Variant. C

}

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

В случае варианта B мы будем считать, что члены класса локальны и ошибки в IncFoo нет. Но будет выдано предупреждение, что параллельно вызывается не константный метод IncFoo из класса MyClass. Это поможет найти ошибку.

В случае варианта C мы будем считать, что члены класса локальны и ошибки в IncFoo нет. И ошибок действительно нет.

Объект может быть как простого типа тип, так и экземпляром класса. К операциям изменения объекта относится:

• Передача объекта в функцию по не константной ссылке.
• Передача объекта в функцию по не константному указателю (В текущей версии VivaMP данное правило не реализовано).
• Изменение объекта в ходе арифметических операций или операции присваивания.
• Вызов у объекта не константного метода.

Исключения:

• Обобщенное исключение A.
• К объекту применена директива "threadprivate", "private", "firstprivate", "lastprivate" или "reduction". Это исключение не касается статических (static) переменных и статических полей классов, которые всегда являются общими.
• Модификация объекта защищена директивой "atomic".
• Модификация объекта осуществляется внутри только одной секции, заданной директивой "section".
• Инициализация или модификация объектов осуществляется внутри распараллеленного оператора for (внутри самого оператора, а не внутри тела цикла). Такие объекты согласно спецификации OpenMP автоматически считаются локальными (private). Пример:
  int i;
  ...
  #pragma omp parallel for
  for (i = 0; i < n; i++) {}. // i - is private.

Пример опасного кода:

#pragma omp parallel
{
  static int st = 1; // V1204
}
void foo(int &) {}
...
int value;
MyObjectType obj;
#pragma omp parallel for
for(int i = 0; i < 33; i++)
{
  ++value; // V1205
  foo(value); // V1206
  obj.non_const_foo(); // V1207
}

Пример безопасного кода:

#pragma omp parallel
{
  #pragma omp critical
  {
    static int st = 1;
  }
}
void foo(const int &) {}
...
int value;
MyObjectType obj;
#pragma omp parallel for
for(int i = 0; i < 33; i++)
{
  #pragma omp atomic
  ++value;
  foo(value);
  obj.const_foo();
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1204. Data race risk. Unprotected static variable declaration in a parallel code.

V1205. Data race risk. Unprotected concurrent operation with the '%1%' variable.

V1206. Data race risk. The value of the '%1%' variable can be changed concurrently via the '%2%' function.

V1207. Data race risk. The '%1%' object can be changed concurrently by a non-const function.

Правило N14

Опасным следует считать применение директив "private", "firstprivate" и "threadprivate" к ссылкам и указателям (не массивам).

Пример опасного кода:

int *arr;
#pragma omp parallel for private(arr)

Пример безопасного кода:

int arr[4];
#pragma omp parallel for private(arr)

Диагностические сообщения, выдача которых основана на данном правиле:

V1208. The '%1%' variable of reference type cannot be private.

V1209. Warning: The '%1%' variable of pointer type should not be private.

Правило N15

Опасным следует считать отсутствие модификации переменной помеченной директивой "lastprivate" в последней секции ("section ").

Исключения:

Переменная также не модифицируется и во всех остальных секциях.

Пример опасного кода:

#pragma omp sections lastprivate(a)
{
  #pragma omp section
  {
    a = 10;
  }
  #pragma omp section
  {
  }
}

Пример безопасного кода:

#pragma omp sections lastprivate(a)
{
  #pragma omp section
  {
    a = 10;
  }
  #pragma omp section
  {
   a = 20;
  }
}

Диагностические сообщения, выдача которых основана на данном правиле:

V1210. The '%1%' variable is marked as lastprivate but is not changed in the last section.

Правило N16

Опасным следует считать использование переменной типа omp_lock_t / omp_nest_lock_t без ее предварительной инициализации в функции omp_init_lock / omp_init_nest_lock.

Под использованием понимается вызов функции omp_set_lock и так далее.

Пример опасного кода:

omp_lock_t myLock;
#pragma omp parallel num_threads(2)
{
  ...
  omp_set_lock(&myLock);
}

Пример безопасного кода:

omp_lock_t myLock;
omp_init_lock(&myLock);
#pragma omp parallel num_threads(2)
{
  ...
  omp_set_lock(&myLock);
}

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N17

Опасным следует считать использование переменных, объявленных в параллельной секции локальными с использованием директив "private" и "lastprivate" без их предварительной инициализации.

Пример опасного кода:

int a = 0;
#pragma omp parallel private(a)
{
  a++;
}

Пример безопасного кода:

int a = 0;
#pragma omp parallel private(a)
{
  a = 0;
  a++;
}

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N18

Опасным следует считать использование после параллельной секции переменных, к которым применялась директива "private", "threadprivate" или "firstprivate" без предварительной инициализации.

Пример опасного кода:

#pragma omp parallel private(a)
{
  ...
}
a++;

Пример безопасного кода:

#pragma omp parallel private(a)
{
  ...
}
a = 10;

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N19

Опасным следует считать применение директив "firstprivate" и "lastprivate" к экземплярам классов, в которых отсутствует конструктор копирования.

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N20

Неэффективным следует считать использование директивы "flush", там где оно выполняется неявно. Случаи, в которых директива "flush" присутствует неявно и в ее использовании нет смысла:

• В директиве barrier
• При входе и при выходе из параллельной секции директивы critical
• При входе и при выходе из параллельной секции директивы ordered
• При входе и при выходе из параллельной секции директивы parallel
• При выходе из параллельной секции директивы for
• При выходе из параллельной секции директивы sections
• При выходе из параллельной секции директивы single
• При входе и при выходе из параллельной секции директивы parallel for
• При входе и при выходе из параллельной секции директивы parallel sections

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N21

Неэффективным следует считать использование директивы flush для локальных переменных (объявленных в параллельной секции), а также переменных помеченных как threadprivate, private, lastprivate, firstprivate.

Пример:

int a = 1;
#pragma omp parallel for private(a)
for (int i = 10; i < 100; ++i) {
  #pragma omp flush(a);
  ...

}

Диагностические сообщения, выдача которых основана на данном правиле:

V1211. The use of 'flush' directive has no sense for private 'NN' variable, and can reduce performance.

Правило N22

Неэффективным следует считать использование критических секций или функций класса omp_set_lock, там где достаточно директивы "atomic".

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N23

Неэффективным следует считать использование директивы flush для локальных переменных (объявленных в параллельной секции), а также переменных помеченных как threadprivate, private, lastprivate, firstprivate.

Директива flush не имеет для перечисленных переменных смысла, так как эти переменные всегда содержат актуальные значения. И дополнительно снижает производительность кода.

Пример опасного кода:

int a = 1;
#pragma omp parallel for private(a)
for (int i = 10; i < 100; ++i) {
  #pragma omp flush(a);
  ...
}

Пример безопасного кода:

int a = 1;
#pragma omp parallel for
for (int i = 10; i < 100; ++i) {
  #pragma omp flush(a);
  ...
}

Диагностические сообщения, выдача которых основана на данном правиле:

В текущей версии VivaMP данное правило не реализовано.

Правило N24

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

используется оператор throw;

используется оператор new;

вызывается функция, отмеченная как throw(...);

Такой код должен быть обернут в блок try..catch внутри параллельнйо секции.

Исключения:

Используется оператор new, не бросающий исключения (new(std::nothrow) float[10000];).

Пример опасного кода:

void MyNotThrowFoo() throw() { }
...
#pragma omp parallel for num_threads(4)
for(int i = 0; i < 4; i++)
{
  ...
  throw 1;
  ...
  float *ptr = new float[10000];
  ...
  MyThrowFoo();
}

Пример безопасного кода:

size_t errCount = 0;
#pragma omp parallel for num_threads(4) reduction(+: errCount)
for(int i = 0; i < 4; i++)
{
  try {
    //...
    throw 1;
  }
  catch (...)
  {
    ++errCount;
  }
}
if (errCount != 0)
  throw 1;

Примечание. Конструкция nothrow new несколько обманчивая, так как возникает ощущение, что исключений здесь быть не может. Но следует учесть, что исключения могут быть сгенерированы в конструкторе создаваемых объектов. То есть, если выделяется хотя бы один std::string или сам класс выделяет память по new (без nothrow), то исключения при вызове new(nothrow) всё равно могут быть сгенерированы. Диагностика данных ошибок заключается в анализе тел конструкторов, (и тел конструкторов других объектов, содержащихся в классе) которые вызываются внутри параллельных секций. На данный момент данная функциональность в VivaMP не реализована.

Диагностические сообщения, выдача которых основана на данном правиле:

V1301. The 'throw' keyword cannot be used outside of a try..catch block in a parallel section.

V1302. The 'new' operator cannot be used outside of a try..catch block in a parallel section.

V1303. The '%1%' function which throws an exception cannot be used in a parallel section outside of a try..catch block.

Правило N25

Опасным следует считать отсутствие включения заголовочного файла <omp.h> в файле, где используются директивы OpenMP.

Диагностические сообщения, выдача которых основана на данном правиле:

V1006. Missing omp.h header file. Use '#include <omp.h>'.

Правило N26

Опасным следует считать наличие неиспользуемых переменных, отмеченных в директиве reduction. Это может свидетельствовать как об ошибке, так и просто о том, что какая-то директива или переменная была забыта и не удалена в процессе рефакторинга кода.

Пример, где не используется переменная abcde:

#pragma omp parallel for reduction (+:sum, abcde)
for (i=1; i<999; i++)
{ 
  sum = sum + a[i];
}

Диагностика:

В текущей версии VivaMP данное правило не реализовано.

Правило N27

Опасным следует считать незащищенный доступ в параллельной секции (образованной директивой for) к элементу массива с использованием индекса, отличного от используемого для чтения.

Примечание. Ошибка может возникнуть и в случае защищенного доступа (single, critical, ...), но сейчас для простоты считаем, что в этом случае доступ к элементам массива безопасен.

Примечание.

Исключения:

1. Индекс является константой.

Пример опасного кода:

#pragma omp parallel for
  for (int i=2; i < 10; i++) 
     array[i] = i * array[i-1]; //V1212

ПРИМЕЧАНИЕ

Пример безопасного кода:

#pragma omp parallel for
  for (int i=2; i < 10; i++)
  {
    array[i] = array [i] / 2;
    array_2[i] = i * array[i-1];
  }

Диагностические сообщения, выдача которых основана на данном правиле:

V1212. Data race risk. When accessing the array '%1%' in a parallel loop, different indexes are used for writing and reading.

Заключение

Если вы интересуетесь методологией проверки программного кода на основе статического анализа - напишите нам (support@viva64.com). Мы надеемся, что найдем общие интересы и возможности для сотрудничества!

Библиографический список

• Андрей Карпов. Тестирование параллельных программ.
• http://www.viva64.com/art-3-1-65331121.html
• Евгений Рыжков. VivaMP - инструмент для OpenMP.
• http://www.viva64.com/art-3-1-1671511269.html