Understanding Data Races 2: Several currently available tools (1/3)
Thursday Jul 06, 2006
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
- Static Checking
- LockLint from Sun
- vpara compile time check for OpenMP programs from Sun
- Runtime Checking - simulation based
- Helgrind from Valgrind
- Runtime Checking - execution based
- Visual Threads from HP
- Thread Checker from Intel
- Data Race Detection Tool from Sun
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,
- omp_prime.c: OpenMP version, contains data races
- omp_prime_fixed.c: OpenMP version, bugs fixed
- pthr_prime.c: Pthread version, contains data races and bugs
- 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.
- It can be very fast and consume little memory.
- The analysis does not affect the behavior of program because it is performed offline.
- 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.
|
|
|
|
A couple of tools in Studio 12 are currently not a...