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

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

Аннотация

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

Введение

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

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

Написание статьи приблизительно совпадает с выпуском VivaMP версии 1.0, к которой реализованы не все правила диагностики. Поэтому для правил указано, какие диагностические сообщения выдает анализатор на их основе, а какие будут реализованы в следующих версиях.

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

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

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

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

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

  1. Нет параллельного блока (нет директивы "parallel").
  2. Внутри параллельного блока используется критическая секиця, заданная директивой "critical".
  3. Внутри параллельного блока имеется "master"-блок.
  4. Внутри параллельного блока имеется "single"-блок.
  5. Внутри параллельного блока используются функции вида 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

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

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

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

  1. Статические переменные.
  2. Статические члены класса (В версии VivaMP 1.0 не реализовано).
  3. Переменные, объявленные вне параллельного блока.

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

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

Исключения:

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

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

#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 1.0 данное правило не реализовано.

Правило N17

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

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

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

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

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

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

В версии VivaMP 1.0 данное правило не реализовано.

Правило N18

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

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

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

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

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

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

В версии VivaMP 1.0 данное правило не реализовано.

Правило N19

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

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

В версии VivaMP 1.0 данное правило не реализовано.

Правило N20

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

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

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

В версии VivaMP 1.0 данное правило не реализовано.

Правило N21

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

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

В версии VivaMP 1.0 данное правило не реализовано.

Заключение

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

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

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


Андрей Карпов
ООО "СиПроВер"
Евгений Рыжков
ООО "СиПроВер"
Ноябрь 2008


Опубликовал admin
22 Фев, Воскресенье 2009г.



Программирование для чайников.