Understanding Data Races 2: Several currently available tools (1/3)

Introduction

This blog entry begins to describe a couple of currently available tools that detect data races in multi-threaded C/C++/Fortran programs. These tools and the categories they can be roughly put into are

  1. Static Checking
    • LockLint from Sun
    • vpara compile time check for OpenMP programs from Sun
  2. Runtime Checking - simulation based
    • Helgrind from Valgrind
  3. Runtime Checking - execution based
    • Visual Threads from HP
    • Thread Checker from Intel
    • Data Race Detection Tool from Sun

What not covered here are the tools from some research work. Some of them use combined static and runtime methods, and some use post-mortem based approaches.

Code Examples

I will reuse the following four code examples from the Tutorial of Using Sun Data Race Detection Tool. If you have downloaded and installed the Sun Studio Express June 2006, you should be able to find the example codes under

{installed-directory}/opt/SUNWspro/examples/rdt/prime.

All four codes find the prime numbers between 2 and 3000 using 4 threads. An OpenMP version and a Pthread version are provided,

  1. omp_prime.c: OpenMP version, contains data races
  2. omp_prime_fixed.c: OpenMP version, bugs fixed
  3. pthr_prime.c: Pthread version, contains data races and bugs
  4. pthr_prime_fixed.c: Pthread version, bugs fixed

Read the Tutorial to find out what the data races are and how the bugs are fixed.

omp_prime.c
    ...
    12	#include <stdio.h>
    13	#include <math.h>
    14	#include <omp.h>
    15	
    16	#define THREADS 4
    17	#define N 3000
    18	
    19	int primes[N];
    20	int pflag[N];
    21	
    22	int is_prime(int v)
    23	{
    24	    int i;
    25	    int bound = floor(sqrt(v)) + 1;
    26	    
    27	    for (i = 2; i < bound; i++) {
    28	        /\* no need to check against known composites \*/ 
    29	        if (!pflag[i]) 
    30	            continue;
    31	        if (v % i == 0) { 
    32	            pflag[v] = 0;
    33	            return 0;
    34	        }
    35	    }
    36	    return (v > 1); 
    37	}
    38	
    39	int main(int argn, char \*\*argv)
    40	{
    41	    int i;
    42	    int total = 0;
    43	
    44	#ifdef _OPENMP
    45	    omp_set_num_threads(THREADS);
    46	    omp_set_dynamic(0);
    47	#endif
    48	
    49	    for (i = 0; i < N; i++) {
    50	        pflag[i] = 1; 
    51	    }
    52	    
    53	    #pragma omp parallel for
    54	    for (i = 2; i < N; i++) {
    55	        if ( is_prime(i) ) {
    56	            primes[total] = i;
    57	            total++;
    58	        }
    59	    }
    60	    printf("Number of prime numbers between 2 and %d: %d\\n",
    61	           N, total);
    62	    for (i = 0; i < total; i++) {
    63	        printf("%d\\n", primes[i]);
    64	    }
    65	}
pthr_prime.c
    ...
    12	#include <stdio.h>
    13	#include <math.h>
    14	#include <pthread.h>
    15	
    16	#define THREADS 4
    17	#define N 3000
    18	
    19	int primes[N];
    20	int pflag[N];
    21	int total = 0;
    22	
    23	int is_prime(int v)
    24	{
    25	    int i;
    26	    int bound = floor(sqrt(v)) + 1;
    27	
    28	    for (i = 2; i < bound; i++) {
    29	        /\* no need to check against known composites \*/ 
    30	        if (!pflag[i])
    31	            continue;
    32	        if (v % i == 0) {
    33	            pflag[v] = 0;
    34	            return 0;
    35	        }
    36	    }
    37	    return (v > 1); 
    38	}
    39	
    40	void \*work(void \*arg)
    41	{
    42	    int start;
    43	    int end;
    44	    int i;
    45	
    46	    start = (N/THREADS) \* (\*(int \*)arg) ;
    47	    end = start + N/THREADS;
    48	    for (i = start; i < end; i++) {
    49	        if ( is_prime(i) ) {
    50	            primes[total] = i;
    51	            total++;        
    52	        }
    53	    }
    54	    return NULL;
    55	}
    56	
    57	int main(int argn, char \*\*argv)
    58	{
    59	    int i;
    60	    pthread_t tids[THREADS-1];
    61	
    62	    for (i = 0; i < N; i++) {
    63	        pflag[i] = 1; 
    64	    }
    65	
    66	    for (i = 0; i < THREADS-1; i++) {
    67	        pthread_create(&tids[i], NULL, work, (void \*)&i);
    68	    }
    69	
    70	    i = THREADS-1;
    71	    work((void \*)&i);
    72	    
    73	    printf("Number of prime numbers between 2 and %d: %d\\n",
    74	           N, total);
    75	    for (i = 0; i < total; i++) {
    76	        printf("%d\\n", primes[i]);
    77	    }
    78	}
omp_prime_fixed.c
    ...
    12	#include <ststdio.h>
    13	#include <math.h>
    14	#include <pthread.h>
    15	
    16	#define THREADS 4
    17	#define N 3000
    18	
    19	int primes[N];
    20	int pflag[N];
    21	int total = 0;
    22	pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
    23	
    24	int is_prime(int v)
    25	{
    26	    int i;
    27	    int bound = floor(sqrt(v)) + 1;
    28	
    29	    for (i = 2; i < bound; i++) {
    30	        /\* no need to check against known composites \*/ 
    31	        if (!pflag[i])
    32	            continue;
    33	        if (v % i == 0) {
    34	            pflag[v] = 0;
    35	            return 0;
    36	        }
    37	    }
    38	    return (v > 1); 
    39	}
    40	
    41	void \*work(void \*arg)
    42	{
    43	    int start;
    44	    int end;
    45	    int i;
    46	    
    47	    start = (N/THREADS) \* ((int)arg) ;
    48	    end = start + N/THREADS;
    49	    for (i = start; i < end; i++) {
    50	        if ( is_prime(i) ) {
    51	            pthread_mutex_lock(&mutex);
    52	            primes[total] = i;
    53	            total++;        
    54	            pthread_mutex_unlock(&mutex);
    55	        }
    56	    }
    57	    return NULL;
    58	}
    59	
    60	int main(int argn, char \*\*argv)
    61	{
    62	    int i;
    63	    pthread_t tids[THREADS-1];
    64	
    65	    for (i = 0; i < N; i++) {
    66	        pflag[i] = 1; 
    67	    }
    68	
    69	    for (i = 0; i < THREADS-1; i++) {
    70	        pthread_create(&tids[i], NULL, work, (void \*)i);
    71	    }
    72	
    73	    i = THREADS-1;
    74	    work((void \*)i);
    75	    
    76	    for (i = 0; i < THREADS-1; i++) {
    77	        pthread_join(tids[i], NULL);
    78	    }
    79	
    80	    printf("Number of prime numbers between 2 and %d: %d\\n",
    81	           N, total);
    82	    for (i = 0; i < total; i++) {
    83	        printf("%d\\n", primes[i]);
    84	    }
    85	}
pthr_prime_fixed.c
    ...
    12	#include <stdio.h>
    13	#include <math.h>
    14	#include <pthread.h>
    15	
    16	#define THREADS 4
    17	#define N 3000
    18	
    19	int primes[N];
    20	int pflag[N];
    21	int total = 0;
    22	pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
    23	
    24	int is_prime(int v)
    25	{
    26	    int i;
    27	    int bound = floor(sqrt(v)) + 1;
    28	
    29	    for (i = 2; i < bound; i++) {
    30	        /\* no need to check against known composites \*/ 
    31	        if (!pflag[i])
    32	            continue;
    33	        if (v % i == 0) {
    34	            pflag[v] = 0;
    35	            return 0;
    36	        }
    37	    }
    38	    return (v > 1); 
    39	}
    40	
    41	void \*work(void \*arg)
    42	{
    43	    int start;
    44	    int end;
    45	    int i;
    46	    
    47	    start = (N/THREADS) \* ((int)arg) ;
    48	    end = start + N/THREADS;
    49	    for (i = start; i < end; i++) {
    50	        if ( is_prime(i) ) {
    51	            pthread_mutex_lock(&mutex);
    52	            primes[total] = i;
    53	            total++;        
    54	            pthread_mutex_unlock(&mutex);
    55	        }
    56	    }
    57	    return NULL;
    58	}
    59	
    60	int main(int argn, char \*\*argv)
    61	{
    62	    int i;
    63	    pthread_t tids[THREADS-1];
    64	
    65	    for (i = 0; i < N; i++) {
    66	        pflag[i] = 1; 
    67	    }
    68	
    69	    for (i = 0; i < THREADS-1; i++) {
    70	        pthread_create(&tids[i], NULL, work, (void \*)i);
    71	    }
    72	
    73	    i = THREADS-1;
    74	    work((void \*)i);
    75	    
    76	    for (i = 0; i < THREADS-1; i++) {
    77	        pthread_join(tids[i], NULL);
    78	    }
    79	
    80	    printf("Number of prime numbers between 2 and %d: %d\\n",
    81	           N, total);
    82	    for (i = 0; i < total; i++) {
    83	        printf("%d\\n", primes[i]);
    84	    }
    85	}

Static Checking Tools

Static checking tools find data races in a program without actually executing the program.

The static checking approach has three advantages, as compared with runtime based approachs.

  1. It can be very fast and consume little memory.
  2. The analysis does not affect the behavior of program because it is performed offline.
  3. It can detect potential data races that do not happen in a particular run with a particular input data set.

Because of the above advantages, static checking can be used in situations where it is very difficult or impossible to get a runtime experiment or where it is very difficult or impossible to get a precise runtime experiment without altering the runtime result, such as OS kernels and device drivers.

The biggest disadvantage of static checking is the large amount of false positives it may generate. Static checking is always puzzled by imprecise information due pointer aliasing and vague execution paths.

Tool 1: LockLint from Sun

Sun Studio provides a utility called LockLint, which analyzes the use of mutex and reader/writer locks, and reports data races and deadlocks due to inconsistent use of locking techniques.

LockLint reports a data race when accesses to a variable are not consistently protected by at least one lock, or accesses violate assertions about which locks protect the variable.

LockLint originates from WARLOCK, which was designed to detect data races and deadlocks in Solaris kernels and device drivers. Search for warlock in opensolaris.org, and you can still find the use of it there.

The following shows the result of using LockLint on pthr_prime.c. Notice the false positive at line 63, and false negative with respect to variable i.

$ cc -mt -Zll pthr_prime.c
$ lock_lint start
$ lock_lint load pthr_prime.ll
$ lock_lint analyze -v

\* Warning: A main function was loaded with no annotations to indicate the
      presence or absence of concurrency. Lock_lint will assume concurrency.
  Please annotate source with:
      NOTE(COMPETING_THREADS_NOW) or NOTE(NO_COMPETING_THREADS_NOW)

\* Writable variable read while no locks held!
  variable = :pflag
     where = :is_prime [pthr_prime.c,30]

\* Variable written while no locks held!
  variable = :pflag
     where = :is_prime [pthr_prime.c,33]

\* Variable written while no locks held!
  variable = :pflag
     where = :main [pthr_prime.c,63]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime.c,74]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime.c,75]

\* Writable variable read while no locks held!
  variable = :primes
     where = :main [pthr_prime.c,76]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime.c,77]

\* Writable variable read while no locks held!
  variable = :total
     where = :work [pthr_prime.c,50]

\* Variable written while no locks held!
  variable = :primes
     where = :work [pthr_prime.c,50]

\* Variable written while no locks held!
  variable = :total
     where = :work [pthr_prime.c,51]

The following shows the result of using LockLint on pthr_prime_fixed.c. Notice that the data races in routine work() are now gone, but the false positives and the false negatives in the previous experiment with pthr_prime.c are still there.

$ cc -mt -Zll pthr_prime_fixed.c
$ lock_lint start
$ lock_lint load pthr_prime_fixed.ll
$ lock_lint analyze -v

\* Warning: A main function was loaded with no annotations to indicate the
      presence or absence of concurrency. Lock_lint will assume concurrency.
  Please annotate source with:
      NOTE(COMPETING_THREADS_NOW) or NOTE(NO_COMPETING_THREADS_NOW)

\* Writable variable read while no locks held!
  variable = :pflag
     where = :is_prime [pthr_prime_fixed.c,31]

\* Variable written while no locks held!
  variable = :pflag
     where = :is_prime [pthr_prime_fixed.c,34]

\* Variable written while no locks held!
  variable = :pflag
     where = :main [pthr_prime_fixed.c,66]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime_fixed.c,81]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime_fixed.c,82]

\* Writable variable read while no locks held!
  variable = :primes
     where = :main [pthr_prime_fixed.c,83]

\* Writable variable read while no locks held!
  variable = :total
     where = :main [pthr_prime_fixed.c,84]

LockLint provides a rich set of source code notations and interactive subcommands that can be used to provide more precise information to LockLint so to improve the analysis.

Tool 2: vpara option in Sun Studio Fortran/C compilers

Strickly, this is not a tool. It is a compile-time check option provided in Sun Studio Fortran and C compilers. The following is from the man page of the cc command.

     -xvpara
          Show parallelization warning messages

          Issues warnings about potential parallel programming
          related problems that may cause incorrect results when
          using OpenMP or Sun/Cray parallel directives and prag-
          mas.

          Use with -xopenmp and OpenMP API directives, or with
          -explictpar and MP parallelization directives.

          Warnings are issued when the compiler detects the fol-
          lowing situations:

          o Loops that are parallelized using MP directives when
          there are data dependencies between different loop
          iterations

          o Problematic use of OpenMP data sharing attributes
          clauses, such as declaring a variable "shared" whose
          accesses in an OpenMP parallel region may cause data
          race, or declaring a variable "private" whose value in
          a parallel region is used after the parallel region.

In short, when -xvpara is used as an option to compile an OpenMP program, the compiler is able to report problems in the source code caused by incorrect use of data sharing attribute clause. One typical problem is data race introduced by incorrectly declaring a variable "shared".

When using vpara checking on the omp_prime.c, the compiler finds the data race between the write accesses to variable total at line 57 by different threads, as illustrated below. The checking analyzes the code enclosed lexically inside an OpenMP parallel region only, therefore it does not find data races in routine is_prime(). The checking also misses the data race on array primes[] due to a technique to reduce false positives. Unfortunately, the technique introduces a false negative here.

$ cc -xopenmp -xO3 -xvpara omp_prime.c -lm
"omp_prime.c", line 53: Warning: inappropriate scoping
        variable 'total' may be scoped inappropriately as 'shared'
        . write at line 57 and write at line 57 may cause data race

$ cc -xopenmp -xO3 -xvpara omp_prime_fixed.c -lm
$

The vpara compile-time checking is based on the static non-concurrency analysis techniques for OpenMP programs, which is also used by the OpenMP autoscoping feature provided in Sun Studio compilers.

Comments:

Hi, Can the data race detection tool be used to detect races in Solaris kernel drivers/file system modules ? Thanks, Sri

Posted by sri on July 26, 2006 at 03:24 AM PDT #

Not yet. Detecting data races in kernels or drivers using the execution based online runtime approach is very difficult. Could explain the specific problem or interest you have in a bit more detail? Thanks.

Posted by Yuan on July 26, 2006 at 04:48 AM PDT #

I was wondering if the data race detection functionality was similar to the Solaris warlock kernel race/deadlock detection tool for . Although I never used warlock, I was curious to know if studio had this feature. Thats all. Thanks.

Posted by guest on July 31, 2006 at 08:00 AM PDT #

Thanks for your blog! It is very informative. I am trying use Lock_Lint and am having problems. Does Lock_Lint only work on Sun Solaris? I am using Suse Linux and have installed SunStudio 12, but can't get Lock_Lint to work. The compiler works as does Lint, but not Lock_Lint. Can you help?

Posted by Marcus on April 09, 2007 at 11:29 AM PDT #

A couple of tools in Studio 12 are currently not available on Linux. Unfortunately, lock_lint is one of them.

You may direct your request for a Linux version to the Solaris and Linux Development Tools - Sun Studio Tools Forum. Or, better, give Solaris a try :)

Posted by Yuan on April 10, 2007 at 07:47 AM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

yuanlin

Search

Archives
« August 2015
SunMonTueWedThuFriSat
      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
     
Today