1/*
2  This file is part of Valgrind, a dynamic binary instrumentation
3  framework.
4
5  Copyright (C) 2008-2008 Google Inc
6     opensource@google.com
7
8  This program is free software; you can redistribute it and/or
9  modify it under the terms of the GNU General Public License as
10  published by the Free Software Foundation; either version 2 of the
11  License, or (at your option) any later version.
12
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  General Public License for more details.
17
18  You should have received a copy of the GNU General Public License
19  along with this program; if not, write to the Free Software
20  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21  02111-1307, USA.
22
23  The GNU General Public License is contained in the file COPYING.
24*/
25
26// Author: Konstantin Serebryany <opensource@google.com>
27//
28// This file contains a set of unit tests for a data race detection tool.
29//
30//
31//
32// This test can be compiled with pthreads (default) or
33// with any other library that supports threads, locks, cond vars, etc.
34//
35// To compile with pthreads:
36//   g++  racecheck_unittest.cc dynamic_annotations.cc
37//        -lpthread -g -DDYNAMIC_ANNOTATIONS=1
38//
39// To compile with different library:
40//   1. cp thread_wrappers_pthread.h thread_wrappers_yourlib.h
41//   2. edit thread_wrappers_yourlib.h
42//   3. add '-DTHREAD_WRAPPERS="thread_wrappers_yourlib.h"' to your compilation.
43//
44//
45
46// This test must not include any other file specific to threading library,
47// everything should be inside THREAD_WRAPPERS.
48#ifndef THREAD_WRAPPERS
49# define THREAD_WRAPPERS "thread_wrappers_pthread.h"
50#endif
51#include THREAD_WRAPPERS
52
53#ifndef NEEDS_SEPERATE_RW_LOCK
54#define RWLock Mutex // Mutex does work as an rw-lock.
55#define WriterLockScoped MutexLock
56#define ReaderLockScoped ReaderMutexLock
57#endif // !NEEDS_SEPERATE_RW_LOCK
58
59
60// Helgrind memory usage testing stuff
61// If not present in dynamic_annotations.h/.cc - ignore
62#ifndef ANNOTATE_RESET_STATS
63#define ANNOTATE_RESET_STATS() do { } while(0)
64#endif
65#ifndef ANNOTATE_PRINT_STATS
66#define ANNOTATE_PRINT_STATS() do { } while(0)
67#endif
68#ifndef ANNOTATE_PRINT_MEMORY_USAGE
69#define ANNOTATE_PRINT_MEMORY_USAGE(a) do { } while(0)
70#endif
71//
72
73// A function that allows to suppress gcc's warnings about
74// unused return values in a portable way.
75template <typename T>
76static inline void IGNORE_RETURN_VALUE(T v)
77{ }
78
79#include <vector>
80#include <string>
81#include <map>
82#include <queue>
83#include <algorithm>
84#include <cstring>      // strlen(), index(), rindex()
85#include <ctime>
86#include <sys/time.h>
87#include <sys/types.h>
88#include <sys/stat.h>
89#include <fcntl.h>
90#include <sys/mman.h>  // mmap
91#include <errno.h>
92#include <stdint.h>    // uintptr_t
93#include <stdlib.h>
94#include <dirent.h>
95
96#ifndef VGO_darwin
97#include <malloc.h>
98#endif
99
100// The tests are
101// - Stability tests (marked STAB)
102// - Performance tests (marked PERF)
103// - Feature tests
104//   - TN (true negative) : no race exists and the tool is silent.
105//   - TP (true positive) : a race exists and reported.
106//   - FN (false negative): a race exists but not reported.
107//   - FP (false positive): no race exists but the tool reports it.
108//
109// The feature tests are marked according to the behavior of helgrind 3.3.0.
110//
111// TP and FP tests are annotated with ANNOTATE_EXPECT_RACE,
112// so, no error reports should be seen when running under helgrind.
113//
114// When some of the FP cases are fixed in helgrind we'll need
115// to update this test.
116//
117// Each test resides in its own namespace.
118// Namespaces are named test01, test02, ...
119// Please, *DO NOT* change the logic of existing tests nor rename them.
120// Create a new test instead.
121//
122// Some tests use sleep()/usleep().
123// This is not a synchronization, but a simple way to trigger
124// some specific behaviour of the race detector's scheduler.
125
126// Globals and utilities used by several tests. {{{1
127CondVar CV;
128int     COND = 0;
129
130
131typedef void (*void_func_void_t)(void);
132enum TEST_FLAG {
133  FEATURE           = 1 << 0,
134  STABILITY         = 1 << 1,
135  PERFORMANCE       = 1 << 2,
136  EXCLUDE_FROM_ALL  = 1 << 3,
137  NEEDS_ANNOTATIONS = 1 << 4,
138  RACE_DEMO         = 1 << 5,
139  MEMORY_USAGE      = 1 << 6,
140  PRINT_STATS       = 1 << 7
141};
142
143// Put everything into stderr.
144Mutex printf_mu;
145#define printf(args...) \
146    do{ \
147      printf_mu.Lock();\
148      fprintf(stderr, args);\
149      printf_mu.Unlock(); \
150    }while(0)
151
152long GetTimeInMs() {
153   struct timeval tv;
154   gettimeofday(&tv, NULL);
155   return (tv.tv_sec * 1000L) + (tv.tv_usec / 1000L);
156}
157
158struct Test{
159  void_func_void_t f_;
160  int flags_;
161  Test(void_func_void_t f, int flags)
162    : f_(f)
163    , flags_(flags)
164  {}
165  Test() : f_(0), flags_(0) {}
166  void Run() {
167     ANNOTATE_RESET_STATS();
168     if (flags_ & PERFORMANCE) {
169        long start = GetTimeInMs();
170        f_();
171        long end = GetTimeInMs();
172        printf ("Time: %4ldms\n", end-start);
173     } else
174        f_();
175     if (flags_ & PRINT_STATS)
176        ANNOTATE_PRINT_STATS();
177     if (flags_ & MEMORY_USAGE)
178        ANNOTATE_PRINT_MEMORY_USAGE(0);
179  }
180};
181std::map<int, Test> TheMapOfTests;
182
183#define NOINLINE __attribute__ ((noinline))
184extern "C" void NOINLINE AnnotateSetVerbosity(const char *, int, int) {};
185
186
187struct TestAdder {
188  TestAdder(void_func_void_t f, int id, int flags = FEATURE) {
189    // AnnotateSetVerbosity(__FILE__, __LINE__, 0);
190    CHECK(TheMapOfTests.count(id) == 0);
191    TheMapOfTests[id] = Test(f, flags);
192  }
193};
194
195#define REGISTER_TEST(f, id)         TestAdder add_test_##id (f, id);
196#define REGISTER_TEST2(f, id, flags) TestAdder add_test_##id (f, id, flags);
197
198static bool ArgIsOne(int *arg) { return *arg == 1; };
199static bool ArgIsZero(int *arg) { return *arg == 0; };
200static bool ArgIsTrue(bool *arg) { return *arg == true; };
201
202// Call ANNOTATE_EXPECT_RACE only if 'machine' env variable is defined.
203// Useful to test against several different machines.
204// Supported machines so far:
205//   MSM_HYBRID1             -- aka MSMProp1
206//   MSM_HYBRID1_INIT_STATE  -- aka MSMProp1 with --initialization-state=yes
207//   MSM_THREAD_SANITIZER    -- ThreadSanitizer's state machine
208#define ANNOTATE_EXPECT_RACE_FOR_MACHINE(mem, descr, machine) \
209    while(getenv(machine)) {\
210      ANNOTATE_EXPECT_RACE(mem, descr); \
211      break;\
212    }\
213
214#define ANNOTATE_EXPECT_RACE_FOR_TSAN(mem, descr) \
215    ANNOTATE_EXPECT_RACE_FOR_MACHINE(mem, descr, "MSM_THREAD_SANITIZER")
216
217inline bool Tsan_PureHappensBefore() {
218  return true;
219}
220
221inline bool Tsan_FastMode()           {
222  return getenv("TSAN_FAST_MODE") != NULL;
223}
224
225// Initialize *(mem) to 0 if Tsan_FastMode.
226#define FAST_MODE_INIT(mem) do { if (Tsan_FastMode()) { *(mem) = 0; } } while(0)
227
228#ifndef MAIN_INIT_ACTION
229#define MAIN_INIT_ACTION
230#endif
231
232
233
234int main(int argc, char** argv) { // {{{1
235  MAIN_INIT_ACTION;
236  printf("FLAGS [phb=%i, fm=%i]\n", Tsan_PureHappensBefore(), Tsan_FastMode());
237  if (argc == 2 && !strcmp(argv[1], "benchmark")) {
238     for (std::map<int,Test>::iterator it = TheMapOfTests.begin();
239         it != TheMapOfTests.end(); ++it) {
240       if(!(it->second.flags_ & PERFORMANCE)) continue;
241       it->second.Run();
242     }
243  } else if (argc == 2 && !strcmp(argv[1], "demo")) {
244     for (std::map<int,Test>::iterator it = TheMapOfTests.begin();
245         it != TheMapOfTests.end();  ++it) {
246       if(!(it->second.flags_ & RACE_DEMO)) continue;
247       it->second.Run();
248     }
249  } else if (argc > 1) {
250    // the tests are listed in command line flags
251    for (int i = 1; i < argc; i++) {
252      int f_num = atoi(argv[i]);
253      CHECK(TheMapOfTests.count(f_num));
254      TheMapOfTests[f_num].Run();
255    }
256  } else {
257    bool run_tests_with_annotations = false;
258    if (getenv("DRT_ALLOW_ANNOTATIONS")) {
259      run_tests_with_annotations = true;
260    }
261    for (std::map<int,Test>::iterator it = TheMapOfTests.begin();
262        it != TheMapOfTests.end();
263        ++it) {
264      if(it->second.flags_ & EXCLUDE_FROM_ALL) continue;
265      if(it->second.flags_ & RACE_DEMO) continue;
266      if((it->second.flags_ & NEEDS_ANNOTATIONS)
267         && run_tests_with_annotations == false) continue;
268      it->second.Run();
269    }
270  }
271}
272
273#ifdef THREAD_WRAPPERS_PTHREAD_H
274#endif
275
276
277// An array of threads. Create/start/join all elements at once. {{{1
278class MyThreadArray {
279 public:
280  static const int kSize = 5;
281  typedef void (*F) (void);
282  MyThreadArray(F f1, F f2 = NULL, F f3 = NULL, F f4 = NULL, F f5 = NULL) {
283    ar_[0] = new MyThread(f1);
284    ar_[1] = f2 ? new MyThread(f2) : NULL;
285    ar_[2] = f3 ? new MyThread(f3) : NULL;
286    ar_[3] = f4 ? new MyThread(f4) : NULL;
287    ar_[4] = f5 ? new MyThread(f5) : NULL;
288  }
289  void Start() {
290    for(int i = 0; i < kSize; i++) {
291      if(ar_[i]) {
292        ar_[i]->Start();
293        usleep(10);
294      }
295    }
296  }
297
298  void Join() {
299    for(int i = 0; i < kSize; i++) {
300      if(ar_[i]) {
301        ar_[i]->Join();
302      }
303    }
304  }
305
306  ~MyThreadArray() {
307    for(int i = 0; i < kSize; i++) {
308      delete ar_[i];
309    }
310  }
311 private:
312  MyThread *ar_[kSize];
313};
314
315
316
317// test00: {{{1
318namespace test00 {
319int     GLOB = 0;
320void Run() {
321  printf("test00: negative\n");
322  printf("\tGLOB=%d\n", GLOB);
323}
324REGISTER_TEST(Run, 00)
325}  // namespace test00
326
327
328// test01: TP. Simple race (write vs write). {{{1
329namespace test01 {
330int     GLOB = 0;
331void Worker() {
332  GLOB = 1;
333}
334
335void Parent() {
336  MyThread t(Worker);
337  t.Start();
338  const timespec delay = { 0, 100 * 1000 * 1000 };
339  nanosleep(&delay, 0);
340  GLOB = 2;
341  t.Join();
342}
343void Run() {
344  FAST_MODE_INIT(&GLOB);
345  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test01. TP.");
346  ANNOTATE_TRACE_MEMORY(&GLOB);
347  printf("test01: positive\n");
348  Parent();
349  const int tmp = GLOB;
350  printf("\tGLOB=%d\n", tmp);
351}
352REGISTER_TEST(Run, 1);
353}  // namespace test01
354
355
356// test02: TN. Synchronization via CondVar. {{{1
357namespace test02 {
358int     GLOB = 0;
359// Two write accesses to GLOB are synchronized because
360// the pair of CV.Signal() and CV.Wait() establish happens-before relation.
361//
362// Waiter:                      Waker:
363// 1. COND = 0
364// 2. Start(Waker)
365// 3. MU.Lock()                 a. write(GLOB)
366//                              b. MU.Lock()
367//                              c. COND = 1
368//                         /--- d. CV.Signal()
369//  4. while(COND)        /     e. MU.Unlock()
370//       CV.Wait(MU) <---/
371//  5. MU.Unlock()
372//  6. write(GLOB)
373Mutex   MU;
374
375void Waker() {
376  usleep(100000);  // Make sure the waiter blocks.
377  GLOB = 1;
378
379  MU.Lock();
380  COND = 1;
381  CV.Signal();
382  MU.Unlock();
383}
384
385void Waiter() {
386  ThreadPool pool(1);
387  pool.StartWorkers();
388  COND = 0;
389  pool.Add(NewCallback(Waker));
390  MU.Lock();
391  while(COND != 1)
392    CV.Wait(&MU);
393  MU.Unlock();
394  GLOB = 2;
395}
396void Run() {
397  printf("test02: negative\n");
398  Waiter();
399  printf("\tGLOB=%d\n", GLOB);
400}
401REGISTER_TEST(Run, 2);
402}  // namespace test02
403
404
405// test03: TN. Synchronization via LockWhen, signaller gets there first. {{{1
406namespace test03 {
407int     GLOB = 0;
408// Two write accesses to GLOB are synchronized via conditional critical section.
409// Note that LockWhen() happens first (we use sleep(1) to make sure)!
410//
411// Waiter:                           Waker:
412// 1. COND = 0
413// 2. Start(Waker)
414//                                   a. write(GLOB)
415//                                   b. MU.Lock()
416//                                   c. COND = 1
417//                              /--- d. MU.Unlock()
418// 3. MU.LockWhen(COND==1) <---/
419// 4. MU.Unlock()
420// 5. write(GLOB)
421Mutex   MU;
422
423void Waker() {
424  usleep(100000);  // Make sure the waiter blocks.
425  GLOB = 1;
426
427  MU.Lock();
428  COND = 1; // We are done! Tell the Waiter.
429  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
430}
431void Waiter() {
432  ThreadPool pool(1);
433  pool.StartWorkers();
434  COND = 0;
435  pool.Add(NewCallback(Waker));
436  MU.LockWhen(Condition(&ArgIsOne, &COND));  // calls ANNOTATE_CONDVAR_WAIT
437  MU.Unlock();  // Waker is done!
438
439  GLOB = 2;
440}
441void Run() {
442  printf("test03: negative\n");
443  Waiter();
444  printf("\tGLOB=%d\n", GLOB);
445}
446REGISTER_TEST2(Run, 3, FEATURE|NEEDS_ANNOTATIONS);
447}  // namespace test03
448
449// test04: TN. Synchronization via PCQ. {{{1
450namespace test04 {
451int     GLOB = 0;
452ProducerConsumerQueue Q(INT_MAX);
453// Two write accesses to GLOB are separated by PCQ Put/Get.
454//
455// Putter:                        Getter:
456// 1. write(GLOB)
457// 2. Q.Put() ---------\          .
458//                      \-------> a. Q.Get()
459//                                b. write(GLOB)
460
461
462void Putter() {
463  GLOB = 1;
464  Q.Put(NULL);
465}
466
467void Getter() {
468  Q.Get();
469  GLOB = 2;
470}
471
472void Run() {
473  printf("test04: negative\n");
474  MyThreadArray t(Putter, Getter);
475  t.Start();
476  t.Join();
477  printf("\tGLOB=%d\n", GLOB);
478}
479REGISTER_TEST(Run, 4);
480}  // namespace test04
481
482
483// test05: FP. Synchronization via CondVar, but waiter does not block. {{{1
484// Since CondVar::Wait() is not called, we get a false positive.
485namespace test05 {
486int     GLOB = 0;
487// Two write accesses to GLOB are synchronized via CondVar.
488// But race detector can not see it.
489// See this for details:
490// http://www.valgrind.org/docs/manual/hg-manual.html#hg-manual.effective-use.
491//
492// Waiter:                                  Waker:
493// 1. COND = 0
494// 2. Start(Waker)
495// 3. MU.Lock()                             a. write(GLOB)
496//                                          b. MU.Lock()
497//                                          c. COND = 1
498//                                          d. CV.Signal()
499//  4. while(COND)                          e. MU.Unlock()
500//       CV.Wait(MU) <<< not called
501//  5. MU.Unlock()
502//  6. write(GLOB)
503Mutex   MU;
504
505void Waker() {
506  GLOB = 1;
507  MU.Lock();
508  COND = 1;
509  CV.Signal();
510  MU.Unlock();
511}
512
513void Waiter() {
514  ThreadPool pool(1);
515  pool.StartWorkers();
516  COND = 0;
517  pool.Add(NewCallback(Waker));
518  usleep(100000);  // Make sure the signaller gets first.
519  MU.Lock();
520  while(COND != 1)
521    CV.Wait(&MU);
522  MU.Unlock();
523  GLOB = 2;
524}
525void Run() {
526  FAST_MODE_INIT(&GLOB);
527  if (!Tsan_PureHappensBefore())
528    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test05. FP. Unavoidable in hybrid scheme.");
529  printf("test05: unavoidable false positive\n");
530  Waiter();
531  printf("\tGLOB=%d\n", GLOB);
532}
533REGISTER_TEST(Run, 5);
534}  // namespace test05
535
536
537// test06: TN. Synchronization via CondVar, but Waker gets there first.  {{{1
538namespace test06 {
539int     GLOB = 0;
540// Same as test05 but we annotated the Wait() loop.
541//
542// Waiter:                                            Waker:
543// 1. COND = 0
544// 2. Start(Waker)
545// 3. MU.Lock()                                       a. write(GLOB)
546//                                                    b. MU.Lock()
547//                                                    c. COND = 1
548//                                           /------- d. CV.Signal()
549//  4. while(COND)                          /         e. MU.Unlock()
550//       CV.Wait(MU) <<< not called        /
551//  6. ANNOTATE_CONDVAR_WAIT(CV, MU) <----/
552//  5. MU.Unlock()
553//  6. write(GLOB)
554
555Mutex   MU;
556
557void Waker() {
558  GLOB = 1;
559  MU.Lock();
560  COND = 1;
561  CV.Signal();
562  MU.Unlock();
563}
564
565void Waiter() {
566  ThreadPool pool(1);
567  pool.StartWorkers();
568  COND = 0;
569  pool.Add(NewCallback(Waker));
570  usleep(100000);  // Make sure the signaller gets first.
571  MU.Lock();
572  while(COND != 1)
573    CV.Wait(&MU);
574  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
575
576  MU.Unlock();
577  GLOB = 2;
578}
579void Run() {
580  printf("test06: negative\n");
581  Waiter();
582  printf("\tGLOB=%d\n", GLOB);
583}
584REGISTER_TEST2(Run, 6, FEATURE|NEEDS_ANNOTATIONS);
585}  // namespace test06
586
587
588// test07: TN. Synchronization via LockWhen(), Signaller is observed first. {{{1
589namespace test07 {
590int     GLOB = 0;
591bool    COND = 0;
592// Two write accesses to GLOB are synchronized via conditional critical section.
593// LockWhen() is observed after COND has been set (due to sleep).
594// Unlock() calls ANNOTATE_CONDVAR_SIGNAL().
595//
596// Waiter:                           Signaller:
597// 1. COND = 0
598// 2. Start(Signaller)
599//                                   a. write(GLOB)
600//                                   b. MU.Lock()
601//                                   c. COND = 1
602//                              /--- d. MU.Unlock calls ANNOTATE_CONDVAR_SIGNAL
603// 3. MU.LockWhen(COND==1) <---/
604// 4. MU.Unlock()
605// 5. write(GLOB)
606
607Mutex   MU;
608void Signaller() {
609  GLOB = 1;
610  MU.Lock();
611  COND = true; // We are done! Tell the Waiter.
612  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
613}
614void Waiter() {
615  COND = false;
616  MyThread t(Signaller);
617  t.Start();
618  usleep(100000);  // Make sure the signaller gets there first.
619
620  MU.LockWhen(Condition(&ArgIsTrue, &COND));  // calls ANNOTATE_CONDVAR_WAIT
621  MU.Unlock();  // Signaller is done!
622
623  GLOB = 2; // If LockWhen didn't catch the signal, a race may be reported here.
624  t.Join();
625}
626void Run() {
627  printf("test07: negative\n");
628  Waiter();
629  printf("\tGLOB=%d\n", GLOB);
630}
631REGISTER_TEST2(Run, 7, FEATURE|NEEDS_ANNOTATIONS);
632}  // namespace test07
633
634// test08: TN. Synchronization via thread start/join. {{{1
635namespace test08 {
636int     GLOB = 0;
637// Three accesses to GLOB are separated by thread start/join.
638//
639// Parent:                        Worker:
640// 1. write(GLOB)
641// 2. Start(Worker) ------------>
642//                                a. write(GLOB)
643// 3. Join(Worker) <------------
644// 4. write(GLOB)
645void Worker() {
646  GLOB = 2;
647}
648
649void Parent() {
650  MyThread t(Worker);
651  GLOB = 1;
652  t.Start();
653  t.Join();
654  GLOB = 3;
655}
656void Run() {
657  printf("test08: negative\n");
658  Parent();
659  printf("\tGLOB=%d\n", GLOB);
660}
661REGISTER_TEST(Run, 8);
662}  // namespace test08
663
664
665// test09: TP. Simple race (read vs write). {{{1
666namespace test09 {
667int     GLOB = 0;
668// A simple data race between writer and reader.
669// Write happens after read (enforced by sleep).
670// Usually, easily detectable by a race detector.
671void Writer() {
672  usleep(100000);
673  GLOB = 3;
674}
675void Reader() {
676  CHECK(GLOB != -777);
677}
678
679void Run() {
680  ANNOTATE_TRACE_MEMORY(&GLOB);
681  FAST_MODE_INIT(&GLOB);
682  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test09. TP.");
683  printf("test09: positive\n");
684  MyThreadArray t(Writer, Reader);
685  t.Start();
686  t.Join();
687  printf("\tGLOB=%d\n", GLOB);
688}
689REGISTER_TEST(Run, 9);
690}  // namespace test09
691
692
693// test10: FN. Simple race (write vs read). {{{1
694namespace test10 {
695int     GLOB = 0;
696// A simple data race between writer and reader.
697// Write happens before Read (enforced by sleep),
698// otherwise this test is the same as test09.
699//
700// Writer:                    Reader:
701// 1. write(GLOB)             a. sleep(long enough so that GLOB
702//                                is most likely initialized by Writer)
703//                            b. read(GLOB)
704//
705//
706// Eraser algorithm does not detect the race here,
707// see Section 2.2 of http://citeseer.ist.psu.edu/savage97eraser.html.
708//
709void Writer() {
710  GLOB = 3;
711}
712void Reader() {
713  usleep(100000);
714  CHECK(GLOB != -777);
715}
716
717void Run() {
718  FAST_MODE_INIT(&GLOB);
719  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test10. TP. FN in MSMHelgrind.");
720  printf("test10: positive\n");
721  MyThreadArray t(Writer, Reader);
722  t.Start();
723  t.Join();
724  printf("\tGLOB=%d\n", GLOB);
725}
726REGISTER_TEST(Run, 10);
727}  // namespace test10
728
729
730// test11: FP. Synchronization via CondVar, 2 workers. {{{1
731// This test is properly synchronized, but currently (Dec 2007)
732// helgrind reports a false positive.
733//
734// Parent:                              Worker1, Worker2:
735// 1. Start(workers)                    a. read(GLOB)
736// 2. MU.Lock()                         b. MU.Lock()
737// 3. while(COND != 2)        /-------- c. CV.Signal()
738//      CV.Wait(&MU) <-------/          d. MU.Unlock()
739// 4. MU.Unlock()
740// 5. write(GLOB)
741//
742namespace test11 {
743int     GLOB = 0;
744Mutex   MU;
745void Worker() {
746  usleep(200000);
747  CHECK(GLOB != 777);
748
749  MU.Lock();
750  COND++;
751  CV.Signal();
752  MU.Unlock();
753}
754
755void Parent() {
756  COND = 0;
757
758  MyThreadArray t(Worker, Worker);
759  t.Start();
760
761  MU.Lock();
762  while(COND != 2) {
763    CV.Wait(&MU);
764  }
765  MU.Unlock();
766
767  GLOB = 2;
768
769  t.Join();
770}
771
772void Run() {
773//  ANNOTATE_EXPECT_RACE(&GLOB, "test11. FP. Fixed by MSMProp1.");
774  printf("test11: negative\n");
775  Parent();
776  printf("\tGLOB=%d\n", GLOB);
777}
778REGISTER_TEST(Run, 11);
779}  // namespace test11
780
781
782// test12: FP. Synchronization via Mutex, then via PCQ. {{{1
783namespace test12 {
784int     GLOB = 0;
785// This test is properly synchronized, but currently (Dec 2007)
786// helgrind reports a false positive.
787//
788// First, we write to GLOB under MU, then we synchronize via PCQ,
789// which is essentially a semaphore.
790//
791// Putter:                       Getter:
792// 1. MU.Lock()                  a. MU.Lock()
793// 2. write(GLOB) <---- MU ----> b. write(GLOB)
794// 3. MU.Unlock()                c. MU.Unlock()
795// 4. Q.Put()   ---------------> d. Q.Get()
796//                               e. write(GLOB)
797
798ProducerConsumerQueue Q(INT_MAX);
799Mutex   MU;
800
801void Putter() {
802  MU.Lock();
803  GLOB++;
804  MU.Unlock();
805
806  Q.Put(NULL);
807}
808
809void Getter() {
810  MU.Lock();
811  GLOB++;
812  MU.Unlock();
813
814  Q.Get();
815  GLOB++;
816}
817
818void Run() {
819//  ANNOTATE_EXPECT_RACE(&GLOB, "test12. FP. Fixed by MSMProp1.");
820  printf("test12: negative\n");
821  MyThreadArray t(Putter, Getter);
822  t.Start();
823  t.Join();
824  printf("\tGLOB=%d\n", GLOB);
825}
826REGISTER_TEST(Run, 12);
827}  // namespace test12
828
829
830// test13: FP. Synchronization via Mutex, then via LockWhen. {{{1
831namespace test13 {
832int     GLOB = 0;
833// This test is essentially the same as test12, but uses LockWhen
834// instead of PCQ.
835//
836// Waker:                                     Waiter:
837// 1. MU.Lock()                               a. MU.Lock()
838// 2. write(GLOB) <---------- MU ---------->  b. write(GLOB)
839// 3. MU.Unlock()                             c. MU.Unlock()
840// 4. MU.Lock()                               .
841// 5. COND = 1                                .
842// 6. ANNOTATE_CONDVAR_SIGNAL -------\        .
843// 7. MU.Unlock()                     \       .
844//                                     \----> d. MU.LockWhen(COND == 1)
845//                                            e. MU.Unlock()
846//                                            f. write(GLOB)
847Mutex   MU;
848
849void Waker() {
850  MU.Lock();
851  GLOB++;
852  MU.Unlock();
853
854  MU.Lock();
855  COND = 1;
856  ANNOTATE_CONDVAR_SIGNAL(&MU);
857  MU.Unlock();
858}
859
860void Waiter() {
861  MU.Lock();
862  GLOB++;
863  MU.Unlock();
864
865  MU.LockWhen(Condition(&ArgIsOne, &COND));
866  MU.Unlock();
867  GLOB++;
868}
869
870void Run() {
871//  ANNOTATE_EXPECT_RACE(&GLOB, "test13. FP. Fixed by MSMProp1.");
872  printf("test13: negative\n");
873  COND = 0;
874
875  MyThreadArray t(Waker, Waiter);
876  t.Start();
877  t.Join();
878
879  printf("\tGLOB=%d\n", GLOB);
880}
881REGISTER_TEST2(Run, 13, FEATURE|NEEDS_ANNOTATIONS);
882}  // namespace test13
883
884
885// test14: FP. Synchronization via PCQ, reads, 2 workers. {{{1
886namespace test14 {
887int     GLOB = 0;
888// This test is properly synchronized, but currently (Dec 2007)
889// helgrind reports a false positive.
890//
891// This test is similar to test11, but uses PCQ (semaphore).
892//
893// Putter2:                  Putter1:                     Getter:
894// 1. read(GLOB)             a. read(GLOB)
895// 2. Q2.Put() ----\         b. Q1.Put() -----\           .
896//                  \                          \--------> A. Q1.Get()
897//                   \----------------------------------> B. Q2.Get()
898//                                                        C. write(GLOB)
899ProducerConsumerQueue Q1(INT_MAX), Q2(INT_MAX);
900
901void Putter1() {
902  CHECK(GLOB != 777);
903  Q1.Put(NULL);
904}
905void Putter2() {
906  CHECK(GLOB != 777);
907  Q2.Put(NULL);
908}
909void Getter() {
910  Q1.Get();
911  Q2.Get();
912  GLOB++;
913}
914void Run() {
915//  ANNOTATE_EXPECT_RACE(&GLOB, "test14. FP. Fixed by MSMProp1.");
916  printf("test14: negative\n");
917  MyThreadArray t(Getter, Putter1, Putter2);
918  t.Start();
919  t.Join();
920  printf("\tGLOB=%d\n", GLOB);
921}
922REGISTER_TEST(Run, 14);
923}  // namespace test14
924
925
926// test15: TN. Synchronization via LockWhen. One waker and 2 waiters. {{{1
927namespace test15 {
928// Waker:                                   Waiter1, Waiter2:
929// 1. write(GLOB)
930// 2. MU.Lock()
931// 3. COND = 1
932// 4. ANNOTATE_CONDVAR_SIGNAL ------------> a. MU.LockWhen(COND == 1)
933// 5. MU.Unlock()                           b. MU.Unlock()
934//                                          c. read(GLOB)
935
936int     GLOB = 0;
937Mutex   MU;
938
939void Waker() {
940  GLOB = 2;
941
942  MU.Lock();
943  COND = 1;
944  ANNOTATE_CONDVAR_SIGNAL(&MU);
945  MU.Unlock();
946};
947
948void Waiter() {
949  MU.LockWhen(Condition(&ArgIsOne, &COND));
950  MU.Unlock();
951  CHECK(GLOB != 777);
952}
953
954
955void Run() {
956  COND = 0;
957  printf("test15: negative\n");
958  MyThreadArray t(Waker, Waiter, Waiter);
959  t.Start();
960  t.Join();
961  printf("\tGLOB=%d\n", GLOB);
962}
963REGISTER_TEST(Run, 15);
964}  // namespace test15
965
966
967// test16: FP. Barrier (emulated by CV), 2 threads. {{{1
968namespace test16 {
969// Worker1:                                     Worker2:
970// 1. MU.Lock()                                 a. MU.Lock()
971// 2. write(GLOB) <------------ MU ---------->  b. write(GLOB)
972// 3. MU.Unlock()                               c. MU.Unlock()
973// 4. MU2.Lock()                                d. MU2.Lock()
974// 5. COND--                                    e. COND--
975// 6. ANNOTATE_CONDVAR_SIGNAL(MU2) ---->V       .
976// 7. MU2.Await(COND == 0) <------------+------ f. ANNOTATE_CONDVAR_SIGNAL(MU2)
977// 8. MU2.Unlock()                      V-----> g. MU2.Await(COND == 0)
978// 9. read(GLOB)                                h. MU2.Unlock()
979//                                              i. read(GLOB)
980//
981//
982// TODO: This way we may create too many edges in happens-before graph.
983// Arndt Mühlenfeld in his PhD (TODO: link) suggests creating special nodes in
984// happens-before graph to reduce the total number of edges.
985// See figure 3.14.
986//
987//
988int     GLOB = 0;
989Mutex   MU;
990Mutex MU2;
991
992void Worker() {
993  MU.Lock();
994  GLOB++;
995  MU.Unlock();
996
997  MU2.Lock();
998  COND--;
999  ANNOTATE_CONDVAR_SIGNAL(&MU2);
1000  MU2.Await(Condition(&ArgIsZero, &COND));
1001  MU2.Unlock();
1002
1003  CHECK(GLOB == 2);
1004}
1005
1006void Run() {
1007//  ANNOTATE_EXPECT_RACE(&GLOB, "test16. FP. Fixed by MSMProp1 + Barrier support.");
1008  COND = 2;
1009  printf("test16: negative\n");
1010  MyThreadArray t(Worker, Worker);
1011  t.Start();
1012  t.Join();
1013  printf("\tGLOB=%d\n", GLOB);
1014}
1015REGISTER_TEST2(Run, 16, FEATURE|NEEDS_ANNOTATIONS);
1016}  // namespace test16
1017
1018
1019// test17: FP. Barrier (emulated by CV), 3 threads. {{{1
1020namespace test17 {
1021// Same as test16, but with 3 threads.
1022int     GLOB = 0;
1023Mutex   MU;
1024Mutex MU2;
1025
1026void Worker() {
1027  MU.Lock();
1028  GLOB++;
1029  MU.Unlock();
1030
1031  MU2.Lock();
1032  COND--;
1033  ANNOTATE_CONDVAR_SIGNAL(&MU2);
1034  MU2.Await(Condition(&ArgIsZero, &COND));
1035  MU2.Unlock();
1036
1037  CHECK(GLOB == 3);
1038}
1039
1040void Run() {
1041//  ANNOTATE_EXPECT_RACE(&GLOB, "test17. FP. Fixed by MSMProp1 + Barrier support.");
1042  COND = 3;
1043  printf("test17: negative\n");
1044  MyThreadArray t(Worker, Worker, Worker);
1045  t.Start();
1046  t.Join();
1047  printf("\tGLOB=%d\n", GLOB);
1048}
1049REGISTER_TEST2(Run, 17, FEATURE|NEEDS_ANNOTATIONS);
1050}  // namespace test17
1051
1052
1053// test18: TN. Synchronization via Await(), signaller gets there first. {{{1
1054namespace test18 {
1055int     GLOB = 0;
1056Mutex   MU;
1057// Same as test03, but uses Mutex::Await() instead of Mutex::LockWhen().
1058
1059void Waker() {
1060  usleep(100000);  // Make sure the waiter blocks.
1061  GLOB = 1;
1062
1063  MU.Lock();
1064  COND = 1; // We are done! Tell the Waiter.
1065  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
1066}
1067void Waiter() {
1068  ThreadPool pool(1);
1069  pool.StartWorkers();
1070  COND = 0;
1071  pool.Add(NewCallback(Waker));
1072
1073  MU.Lock();
1074  MU.Await(Condition(&ArgIsOne, &COND));  // calls ANNOTATE_CONDVAR_WAIT
1075  MU.Unlock();  // Waker is done!
1076
1077  GLOB = 2;
1078}
1079void Run() {
1080  printf("test18: negative\n");
1081  Waiter();
1082  printf("\tGLOB=%d\n", GLOB);
1083}
1084REGISTER_TEST2(Run, 18, FEATURE|NEEDS_ANNOTATIONS);
1085}  // namespace test18
1086
1087// test19: TN. Synchronization via AwaitWithTimeout(). {{{1
1088namespace test19 {
1089int     GLOB = 0;
1090// Same as test18, but with AwaitWithTimeout. Do not timeout.
1091Mutex   MU;
1092void Waker() {
1093  usleep(100000);  // Make sure the waiter blocks.
1094  GLOB = 1;
1095
1096  MU.Lock();
1097  COND = 1; // We are done! Tell the Waiter.
1098  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
1099}
1100void Waiter() {
1101  ThreadPool pool(1);
1102  pool.StartWorkers();
1103  COND = 0;
1104  pool.Add(NewCallback(Waker));
1105
1106  MU.Lock();
1107  CHECK(MU.AwaitWithTimeout(Condition(&ArgIsOne, &COND), INT_MAX));
1108  MU.Unlock();
1109
1110  GLOB = 2;
1111}
1112void Run() {
1113  printf("test19: negative\n");
1114  Waiter();
1115  printf("\tGLOB=%d\n", GLOB);
1116}
1117REGISTER_TEST2(Run, 19, FEATURE|NEEDS_ANNOTATIONS);
1118}  // namespace test19
1119
1120// test20: TP. Incorrect synchronization via AwaitWhen(), timeout. {{{1
1121namespace test20 {
1122int     GLOB = 0;
1123Mutex   MU;
1124// True race. We timeout in AwaitWhen.
1125void Waker() {
1126  GLOB = 1;
1127  usleep(100 * 1000);
1128}
1129void Waiter() {
1130  ThreadPool pool(1);
1131  pool.StartWorkers();
1132  COND = 0;
1133  pool.Add(NewCallback(Waker));
1134
1135  MU.Lock();
1136  CHECK(!MU.AwaitWithTimeout(Condition(&ArgIsOne, &COND), 100));
1137  MU.Unlock();
1138
1139  GLOB = 2;
1140}
1141void Run() {
1142  FAST_MODE_INIT(&GLOB);
1143  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test20. TP.");
1144  printf("test20: positive\n");
1145  Waiter();
1146  printf("\tGLOB=%d\n", GLOB);
1147}
1148REGISTER_TEST2(Run, 20, FEATURE|NEEDS_ANNOTATIONS);
1149}  // namespace test20
1150
1151// test21: TP. Incorrect synchronization via LockWhenWithTimeout(). {{{1
1152namespace test21 {
1153int     GLOB = 0;
1154// True race. We timeout in LockWhenWithTimeout().
1155Mutex   MU;
1156void Waker() {
1157  GLOB = 1;
1158  usleep(100 * 1000);
1159}
1160void Waiter() {
1161  ThreadPool pool(1);
1162  pool.StartWorkers();
1163  COND = 0;
1164  pool.Add(NewCallback(Waker));
1165
1166  CHECK(!MU.LockWhenWithTimeout(Condition(&ArgIsOne, &COND), 100));
1167  MU.Unlock();
1168
1169  GLOB = 2;
1170}
1171void Run() {
1172  FAST_MODE_INIT(&GLOB);
1173  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test21. TP.");
1174  printf("test21: positive\n");
1175  Waiter();
1176  printf("\tGLOB=%d\n", GLOB);
1177}
1178REGISTER_TEST2(Run, 21, FEATURE|NEEDS_ANNOTATIONS);
1179}  // namespace test21
1180
1181// test22: TP. Incorrect synchronization via CondVar::WaitWithTimeout(). {{{1
1182namespace test22 {
1183int     GLOB = 0;
1184Mutex   MU;
1185// True race. We timeout in CondVar::WaitWithTimeout().
1186void Waker() {
1187  GLOB = 1;
1188  usleep(100 * 1000);
1189}
1190void Waiter() {
1191  ThreadPool pool(1);
1192  pool.StartWorkers();
1193  COND = 0;
1194  pool.Add(NewCallback(Waker));
1195
1196  int64_t ms_left_to_wait = 100;
1197  int64_t deadline_ms = GetCurrentTimeMillis() + ms_left_to_wait;
1198  MU.Lock();
1199  while(COND != 1 && ms_left_to_wait > 0) {
1200    CV.WaitWithTimeout(&MU, ms_left_to_wait);
1201    ms_left_to_wait = deadline_ms - GetCurrentTimeMillis();
1202  }
1203  MU.Unlock();
1204
1205  GLOB = 2;
1206}
1207void Run() {
1208  FAST_MODE_INIT(&GLOB);
1209  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test22. TP.");
1210  printf("test22: positive\n");
1211  Waiter();
1212  printf("\tGLOB=%d\n", GLOB);
1213}
1214REGISTER_TEST(Run, 22);
1215}  // namespace test22
1216
1217// test23: TN. TryLock, ReaderLock, ReaderTryLock. {{{1
1218namespace test23 {
1219// Correct synchronization with TryLock, Lock, ReaderTryLock, ReaderLock.
1220int     GLOB = 0;
1221Mutex   MU;
1222void Worker_TryLock() {
1223  for (int i = 0; i < 20; i++) {
1224    while (true) {
1225      if (MU.TryLock()) {
1226        GLOB++;
1227        MU.Unlock();
1228        break;
1229      }
1230      usleep(1000);
1231    }
1232  }
1233}
1234
1235void Worker_ReaderTryLock() {
1236  for (int i = 0; i < 20; i++) {
1237    while (true) {
1238      if (MU.ReaderTryLock()) {
1239        CHECK(GLOB != 777);
1240        MU.ReaderUnlock();
1241        break;
1242      }
1243      usleep(1000);
1244    }
1245  }
1246}
1247
1248void Worker_ReaderLock() {
1249  for (int i = 0; i < 20; i++) {
1250    MU.ReaderLock();
1251    CHECK(GLOB != 777);
1252    MU.ReaderUnlock();
1253    usleep(1000);
1254  }
1255}
1256
1257void Worker_Lock() {
1258  for (int i = 0; i < 20; i++) {
1259    MU.Lock();
1260    GLOB++;
1261    MU.Unlock();
1262    usleep(1000);
1263  }
1264}
1265
1266void Run() {
1267  printf("test23: negative\n");
1268  MyThreadArray t(Worker_TryLock,
1269                  Worker_ReaderTryLock,
1270                  Worker_ReaderLock,
1271                  Worker_Lock
1272                  );
1273  t.Start();
1274  t.Join();
1275  printf("\tGLOB=%d\n", GLOB);
1276}
1277REGISTER_TEST(Run, 23);
1278}  // namespace test23
1279
1280// test24: TN. Synchronization via ReaderLockWhen(). {{{1
1281namespace test24 {
1282int     GLOB = 0;
1283Mutex   MU;
1284// Same as test03, but uses ReaderLockWhen().
1285
1286void Waker() {
1287  usleep(100000);  // Make sure the waiter blocks.
1288  GLOB = 1;
1289
1290  MU.Lock();
1291  COND = 1; // We are done! Tell the Waiter.
1292  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
1293}
1294void Waiter() {
1295  ThreadPool pool(1);
1296  pool.StartWorkers();
1297  COND = 0;
1298  pool.Add(NewCallback(Waker));
1299  MU.ReaderLockWhen(Condition(&ArgIsOne, &COND));
1300  MU.ReaderUnlock();
1301
1302  GLOB = 2;
1303}
1304void Run() {
1305  printf("test24: negative\n");
1306  Waiter();
1307  printf("\tGLOB=%d\n", GLOB);
1308}
1309REGISTER_TEST2(Run, 24, FEATURE|NEEDS_ANNOTATIONS);
1310}  // namespace test24
1311
1312// test25: TN. Synchronization via ReaderLockWhenWithTimeout(). {{{1
1313namespace test25 {
1314int     GLOB = 0;
1315Mutex   MU;
1316// Same as test24, but uses ReaderLockWhenWithTimeout().
1317// We do not timeout.
1318
1319void Waker() {
1320  usleep(100000);  // Make sure the waiter blocks.
1321  GLOB = 1;
1322
1323  MU.Lock();
1324  COND = 1; // We are done! Tell the Waiter.
1325  MU.Unlock(); // calls ANNOTATE_CONDVAR_SIGNAL;
1326}
1327void Waiter() {
1328  ThreadPool pool(1);
1329  pool.StartWorkers();
1330  COND = 0;
1331  pool.Add(NewCallback(Waker));
1332  CHECK(MU.ReaderLockWhenWithTimeout(Condition(&ArgIsOne, &COND), INT_MAX));
1333  MU.ReaderUnlock();
1334
1335  GLOB = 2;
1336}
1337void Run() {
1338  printf("test25: negative\n");
1339  Waiter();
1340  printf("\tGLOB=%d\n", GLOB);
1341}
1342REGISTER_TEST2(Run, 25, FEATURE|NEEDS_ANNOTATIONS);
1343}  // namespace test25
1344
1345// test26: TP. Incorrect synchronization via ReaderLockWhenWithTimeout(). {{{1
1346namespace test26 {
1347int     GLOB = 0;
1348Mutex   MU;
1349// Same as test25, but we timeout and incorrectly assume happens-before.
1350
1351void Waker() {
1352  GLOB = 1;
1353  usleep(10000);
1354}
1355void Waiter() {
1356  ThreadPool pool(1);
1357  pool.StartWorkers();
1358  COND = 0;
1359  pool.Add(NewCallback(Waker));
1360  CHECK(!MU.ReaderLockWhenWithTimeout(Condition(&ArgIsOne, &COND), 100));
1361  MU.ReaderUnlock();
1362
1363  GLOB = 2;
1364}
1365void Run() {
1366  FAST_MODE_INIT(&GLOB);
1367  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test26. TP");
1368  printf("test26: positive\n");
1369  Waiter();
1370  printf("\tGLOB=%d\n", GLOB);
1371}
1372REGISTER_TEST2(Run, 26, FEATURE|NEEDS_ANNOTATIONS);
1373}  // namespace test26
1374
1375
1376// test27: TN. Simple synchronization via SpinLock. {{{1
1377namespace test27 {
1378#ifndef NO_SPINLOCK
1379int     GLOB = 0;
1380SpinLock MU;
1381void Worker() {
1382  MU.Lock();
1383  GLOB++;
1384  MU.Unlock();
1385  usleep(10000);
1386}
1387
1388void Run() {
1389  printf("test27: negative\n");
1390  MyThreadArray t(Worker, Worker, Worker, Worker);
1391  t.Start();
1392  t.Join();
1393  printf("\tGLOB=%d\n", GLOB);
1394}
1395REGISTER_TEST2(Run, 27, FEATURE|NEEDS_ANNOTATIONS);
1396#endif // NO_SPINLOCK
1397}  // namespace test27
1398
1399
1400// test28: TN. Synchronization via Mutex, then PCQ. 3 threads {{{1
1401namespace test28 {
1402// Putter1:                       Getter:                         Putter2:
1403// 1. MU.Lock()                                                   A. MU.Lock()
1404// 2. write(GLOB)                                                 B. write(GLOB)
1405// 3. MU.Unlock()                                                 C. MU.Unlock()
1406// 4. Q.Put() ---------\                                 /------- D. Q.Put()
1407// 5. MU.Lock()         \-------> a. Q.Get()            /         E. MU.Lock()
1408// 6. read(GLOB)                  b. Q.Get() <---------/          F. read(GLOB)
1409// 7. MU.Unlock()                   (sleep)                       G. MU.Unlock()
1410//                                c. read(GLOB)
1411ProducerConsumerQueue Q(INT_MAX);
1412int     GLOB = 0;
1413Mutex   MU;
1414
1415void Putter() {
1416  MU.Lock();
1417  GLOB++;
1418  MU.Unlock();
1419
1420  Q.Put(NULL);
1421
1422  MU.Lock();
1423  CHECK(GLOB != 777);
1424  MU.Unlock();
1425}
1426
1427void Getter() {
1428  Q.Get();
1429  Q.Get();
1430  usleep(100000);
1431  CHECK(GLOB == 2);
1432}
1433
1434void Run() {
1435  printf("test28: negative\n");
1436  MyThreadArray t(Getter, Putter, Putter);
1437  t.Start();
1438  t.Join();
1439  printf("\tGLOB=%d\n", GLOB);
1440}
1441REGISTER_TEST(Run, 28);
1442}  // namespace test28
1443
1444
1445// test29: TN. Synchronization via Mutex, then PCQ. 4 threads. {{{1
1446namespace test29 {
1447// Similar to test28, but has two Getters and two PCQs.
1448ProducerConsumerQueue *Q1, *Q2;
1449Mutex   MU;
1450int     GLOB = 0;
1451
1452void Putter(ProducerConsumerQueue *q) {
1453  MU.Lock();
1454  GLOB++;
1455  MU.Unlock();
1456
1457  q->Put(NULL);
1458  q->Put(NULL);
1459
1460  MU.Lock();
1461  CHECK(GLOB != 777);
1462  MU.Unlock();
1463
1464}
1465
1466void Putter1() { Putter(Q1); }
1467void Putter2() { Putter(Q2); }
1468
1469void Getter() {
1470  Q1->Get();
1471  Q2->Get();
1472  usleep(100000);
1473  CHECK(GLOB == 2);
1474  usleep(48000); //  TODO: remove this when FP in test32 is fixed.
1475}
1476
1477void Run() {
1478  printf("test29: negative\n");
1479  Q1 = new ProducerConsumerQueue(INT_MAX);
1480  Q2 = new ProducerConsumerQueue(INT_MAX);
1481  MyThreadArray t(Getter, Getter, Putter1, Putter2);
1482  t.Start();
1483  t.Join();
1484  printf("\tGLOB=%d\n", GLOB);
1485  delete Q1;
1486  delete Q2;
1487}
1488REGISTER_TEST(Run, 29);
1489}  // namespace test29
1490
1491
1492// test30: TN. Synchronization via 'safe' race. Writer vs multiple Readers. {{{1
1493namespace test30 {
1494// This test shows a very risky kind of synchronization which is very easy
1495// to get wrong. Actually, I am not sure I've got it right.
1496//
1497// Writer:                                 Reader1, Reader2, ..., ReaderN:
1498// 1. write(GLOB[i]: i >= BOUNDARY)        a. n = BOUNDARY
1499// 2. HAPPENS_BEFORE(BOUNDARY+1)  -------> b. HAPPENS_AFTER(n)
1500// 3. BOUNDARY++;                          c. read(GLOB[i]: i < n)
1501//
1502// Here we have a 'safe' race on accesses to BOUNDARY and
1503// no actual races on accesses to GLOB[]:
1504// Writer writes to GLOB[i] where i>=BOUNDARY and then increments BOUNDARY.
1505// Readers read BOUNDARY and read GLOB[i] where i<BOUNDARY.
1506//
1507// I am not completely sure that this scheme guaranties no race between
1508// accesses to GLOB since compilers and CPUs
1509// are free to rearrange memory operations.
1510// I am actually sure that this scheme is wrong unless we use
1511// some smart memory fencing...
1512
1513
1514const int N = 48;
1515static int GLOB[N];
1516volatile int BOUNDARY = 0;
1517
1518void Writer() {
1519  for (int i = 0; i < N; i++) {
1520    CHECK(BOUNDARY == i);
1521    for (int j = i; j < N; j++) {
1522      GLOB[j] = j;
1523    }
1524    ANNOTATE_HAPPENS_BEFORE(reinterpret_cast<void*>(BOUNDARY+1));
1525    BOUNDARY++;
1526    usleep(1000);
1527  }
1528}
1529
1530void Reader() {
1531  int n;
1532  do {
1533    n = BOUNDARY;
1534    if (n == 0) continue;
1535    ANNOTATE_HAPPENS_AFTER(reinterpret_cast<void*>(n));
1536    for (int i = 0; i < n; i++) {
1537      CHECK(GLOB[i] == i);
1538    }
1539    usleep(100);
1540  } while(n < N);
1541}
1542
1543void Run() {
1544  FAST_MODE_INIT(&BOUNDARY);
1545  ANNOTATE_EXPECT_RACE((void*)(&BOUNDARY), "test30. Sync via 'safe' race.");
1546  printf("test30: negative\n");
1547  MyThreadArray t(Writer, Reader, Reader, Reader);
1548  t.Start();
1549  t.Join();
1550  printf("\tGLOB=%d\n", GLOB[N-1]);
1551}
1552REGISTER_TEST2(Run, 30, FEATURE|NEEDS_ANNOTATIONS);
1553}  // namespace test30
1554
1555
1556// test31: TN. Synchronization via 'safe' race. Writer vs Writer. {{{1
1557namespace test31 {
1558// This test is similar to test30, but
1559// it has one Writer instead of mulitple Readers.
1560//
1561// Writer1:                                Writer2
1562// 1. write(GLOB[i]: i >= BOUNDARY)        a. n = BOUNDARY
1563// 2. HAPPENS_BEFORE(BOUNDARY+1)  -------> b. HAPPENS_AFTER(n)
1564// 3. BOUNDARY++;                          c. write(GLOB[i]: i < n)
1565//
1566
1567const int N = 48;
1568static int GLOB[N];
1569volatile int BOUNDARY = 0;
1570
1571void Writer1() {
1572  for (int i = 0; i < N; i++) {
1573    CHECK(BOUNDARY == i);
1574    for (int j = i; j < N; j++) {
1575      GLOB[j] = j;
1576    }
1577    ANNOTATE_HAPPENS_BEFORE(reinterpret_cast<void*>(BOUNDARY+1));
1578    BOUNDARY++;
1579    usleep(1000);
1580  }
1581}
1582
1583void Writer2() {
1584  int n;
1585  do {
1586    n = BOUNDARY;
1587    if (n == 0) continue;
1588    ANNOTATE_HAPPENS_AFTER(reinterpret_cast<void*>(n));
1589    for (int i = 0; i < n; i++) {
1590      if(GLOB[i] == i) {
1591        GLOB[i]++;
1592      }
1593    }
1594    usleep(100);
1595  } while(n < N);
1596}
1597
1598void Run() {
1599  FAST_MODE_INIT(&BOUNDARY);
1600  ANNOTATE_EXPECT_RACE((void*)(&BOUNDARY), "test31. Sync via 'safe' race.");
1601  printf("test31: negative\n");
1602  MyThreadArray t(Writer1, Writer2);
1603  t.Start();
1604  t.Join();
1605  printf("\tGLOB=%d\n", GLOB[N-1]);
1606}
1607REGISTER_TEST2(Run, 31, FEATURE|NEEDS_ANNOTATIONS);
1608}  // namespace test31
1609
1610
1611// test32: FP. Synchronization via thread create/join. W/R. {{{1
1612namespace test32 {
1613// This test is well synchronized but helgrind 3.3.0 reports a race.
1614//
1615// Parent:                   Writer:               Reader:
1616// 1. Start(Reader) -----------------------\       .
1617//                                          \      .
1618// 2. Start(Writer) ---\                     \     .
1619//                      \---> a. MU.Lock()    \--> A. sleep(long enough)
1620//                            b. write(GLOB)
1621//                      /---- c. MU.Unlock()
1622// 3. Join(Writer) <---/
1623//                                                 B. MU.Lock()
1624//                                                 C. read(GLOB)
1625//                                   /------------ D. MU.Unlock()
1626// 4. Join(Reader) <----------------/
1627// 5. write(GLOB)
1628//
1629//
1630// The call to sleep() in Reader is not part of synchronization,
1631// it is required to trigger the false positive in helgrind 3.3.0.
1632//
1633int     GLOB = 0;
1634Mutex   MU;
1635
1636void Writer() {
1637  MU.Lock();
1638  GLOB = 1;
1639  MU.Unlock();
1640}
1641
1642void Reader() {
1643  usleep(480000);
1644  MU.Lock();
1645  CHECK(GLOB != 777);
1646  MU.Unlock();
1647}
1648
1649void Parent() {
1650  MyThread r(Reader);
1651  MyThread w(Writer);
1652  r.Start();
1653  w.Start();
1654
1655  w.Join();  // 'w' joins first.
1656  r.Join();
1657
1658  GLOB = 2;
1659}
1660
1661void Run() {
1662//  ANNOTATE_EXPECT_RACE(&GLOB, "test32. FP. Fixed by MSMProp1.");
1663  printf("test32: negative\n");
1664  Parent();
1665  printf("\tGLOB=%d\n", GLOB);
1666}
1667
1668REGISTER_TEST(Run, 32);
1669}  // namespace test32
1670
1671
1672// test33: STAB. Stress test for the number of thread sets (TSETs). {{{1
1673namespace test33 {
1674int     GLOB = 0;
1675// Here we access N memory locations from within log(N) threads.
1676// We do it in such a way that helgrind creates nearly all possible TSETs.
1677// Then we join all threads and start again (N_iter times).
1678const int N_iter = 48;
1679const int Nlog  = 15;
1680const int N     = 1 << Nlog;
1681static int ARR[N];
1682Mutex   MU;
1683
1684void Worker() {
1685  MU.Lock();
1686  int n = ++GLOB;
1687  MU.Unlock();
1688
1689  n %= Nlog;
1690  for (int i = 0; i < N; i++) {
1691    // ARR[i] is accessed by threads from i-th subset
1692    if (i & (1 << n)) {
1693        CHECK(ARR[i] == 0);
1694    }
1695  }
1696}
1697
1698void Run() {
1699  printf("test33:\n");
1700
1701  std::vector<MyThread*> vec(Nlog);
1702
1703  for (int j = 0; j < N_iter; j++) {
1704    // Create and start Nlog threads
1705    for (int i = 0; i < Nlog; i++) {
1706      vec[i] = new MyThread(Worker);
1707    }
1708    for (int i = 0; i < Nlog; i++) {
1709      vec[i]->Start();
1710    }
1711    // Join all threads.
1712    for (int i = 0; i < Nlog; i++) {
1713      vec[i]->Join();
1714      delete vec[i];
1715    }
1716    printf("------------------\n");
1717  }
1718
1719  printf("\tGLOB=%d; ARR[1]=%d; ARR[7]=%d; ARR[N-1]=%d\n",
1720         GLOB, ARR[1], ARR[7], ARR[N-1]);
1721}
1722REGISTER_TEST2(Run, 33, STABILITY|EXCLUDE_FROM_ALL);
1723}  // namespace test33
1724
1725
1726// test34: STAB. Stress test for the number of locks sets (LSETs). {{{1
1727namespace test34 {
1728// Similar to test33, but for lock sets.
1729int     GLOB = 0;
1730const int N_iter = 48;
1731const int Nlog = 10;
1732const int N    = 1 << Nlog;
1733static int ARR[N];
1734static Mutex *MUs[Nlog];
1735
1736void Worker() {
1737    for (int i = 0; i < N; i++) {
1738      // ARR[i] is protected by MUs from i-th subset of all MUs
1739      for (int j = 0; j < Nlog; j++)  if (i & (1 << j)) MUs[j]->Lock();
1740      CHECK(ARR[i] == 0);
1741      for (int j = 0; j < Nlog; j++)  if (i & (1 << j)) MUs[j]->Unlock();
1742    }
1743}
1744
1745void Run() {
1746  printf("test34:\n");
1747  for (int iter = 0; iter < N_iter; iter++) {
1748    for (int i = 0; i < Nlog; i++) {
1749      MUs[i] = new Mutex;
1750    }
1751    MyThreadArray t(Worker, Worker);
1752    t.Start();
1753    t.Join();
1754    for (int i = 0; i < Nlog; i++) {
1755      delete MUs[i];
1756    }
1757    printf("------------------\n");
1758  }
1759  printf("\tGLOB=%d\n", GLOB);
1760}
1761REGISTER_TEST2(Run, 34, STABILITY|EXCLUDE_FROM_ALL);
1762}  // namespace test34
1763
1764
1765// test35: PERF. Lots of mutexes and lots of call to free().  {{{1
1766namespace test35 {
1767// Helgrind 3.3.0 has very slow in shadow_mem_make_NoAccess(). Fixed locally.
1768// With the fix helgrind runs this test about a minute.
1769// Without the fix -- about 5 minutes. (on c2d 2.4GHz).
1770//
1771// TODO: need to figure out the best way for performance testing.
1772int **ARR;
1773const int N_mu   = 25000;
1774const int N_free = 48000;
1775
1776void Worker() {
1777  for (int i = 0; i < N_free; i++)
1778    CHECK(777 == *ARR[i]);
1779}
1780
1781void Run() {
1782  printf("test35:\n");
1783  std::vector<Mutex*> mus;
1784
1785  ARR = new int *[N_free];
1786  for (int i = 0; i < N_free; i++) {
1787    const int c = N_free / N_mu;
1788    if ((i % c) == 0) {
1789      mus.push_back(new Mutex);
1790      mus.back()->Lock();
1791      mus.back()->Unlock();
1792    }
1793    ARR[i] = new int(777);
1794  }
1795
1796  // Need to put all ARR[i] into shared state in order
1797  // to trigger the performance bug.
1798  MyThreadArray t(Worker, Worker);
1799  t.Start();
1800  t.Join();
1801
1802  for (int i = 0; i < N_free; i++) delete ARR[i];
1803  delete [] ARR;
1804
1805  for (size_t i = 0; i < mus.size(); i++) {
1806    delete mus[i];
1807  }
1808}
1809REGISTER_TEST2(Run, 35, PERFORMANCE|EXCLUDE_FROM_ALL);
1810}  // namespace test35
1811
1812
1813// test36: TN. Synchronization via Mutex, then PCQ. 3 threads. W/W {{{1
1814namespace test36 {
1815// variation of test28 (W/W instead of W/R)
1816
1817// Putter1:                       Getter:                         Putter2:
1818// 1. MU.Lock();                                                  A. MU.Lock()
1819// 2. write(GLOB)                                                 B. write(GLOB)
1820// 3. MU.Unlock()                                                 C. MU.Unlock()
1821// 4. Q.Put() ---------\                                 /------- D. Q.Put()
1822// 5. MU1.Lock()        \-------> a. Q.Get()            /         E. MU1.Lock()
1823// 6. MU.Lock()                   b. Q.Get() <---------/          F. MU.Lock()
1824// 7. write(GLOB)                                                 G. write(GLOB)
1825// 8. MU.Unlock()                                                 H. MU.Unlock()
1826// 9. MU1.Unlock()                  (sleep)                       I. MU1.Unlock()
1827//                                c. MU1.Lock()
1828//                                d. write(GLOB)
1829//                                e. MU1.Unlock()
1830ProducerConsumerQueue Q(INT_MAX);
1831int     GLOB = 0;
1832Mutex   MU, MU1;
1833
1834void Putter() {
1835  MU.Lock();
1836  GLOB++;
1837  MU.Unlock();
1838
1839  Q.Put(NULL);
1840
1841  MU1.Lock();
1842  MU.Lock();
1843  GLOB++;
1844  MU.Unlock();
1845  MU1.Unlock();
1846}
1847
1848void Getter() {
1849  Q.Get();
1850  Q.Get();
1851  usleep(100000);
1852  MU1.Lock();
1853  GLOB++;
1854  MU1.Unlock();
1855}
1856
1857void Run() {
1858  printf("test36: negative \n");
1859  MyThreadArray t(Getter, Putter, Putter);
1860  t.Start();
1861  t.Join();
1862  printf("\tGLOB=%d\n", GLOB);
1863}
1864REGISTER_TEST(Run, 36);
1865}  // namespace test36
1866
1867
1868// test37: TN. Simple synchronization (write vs read). {{{1
1869namespace test37 {
1870int     GLOB = 0;
1871Mutex   MU;
1872// Similar to test10, but properly locked.
1873// Writer:             Reader:
1874// 1. MU.Lock()
1875// 2. write
1876// 3. MU.Unlock()
1877//                    a. MU.Lock()
1878//                    b. read
1879//                    c. MU.Unlock();
1880
1881void Writer() {
1882  MU.Lock();
1883  GLOB = 3;
1884  MU.Unlock();
1885}
1886void Reader() {
1887  usleep(100000);
1888  MU.Lock();
1889  CHECK(GLOB != -777);
1890  MU.Unlock();
1891}
1892
1893void Run() {
1894  printf("test37: negative\n");
1895  MyThreadArray t(Writer, Reader);
1896  t.Start();
1897  t.Join();
1898  printf("\tGLOB=%d\n", GLOB);
1899}
1900REGISTER_TEST(Run, 37);
1901}  // namespace test37
1902
1903
1904// test38: TN. Synchronization via Mutexes and PCQ. 4 threads. W/W {{{1
1905namespace test38 {
1906// Fusion of test29 and test36.
1907
1908// Putter1:            Putter2:           Getter1:       Getter2:
1909//    MU1.Lock()          MU1.Lock()
1910//    write(GLOB)         write(GLOB)
1911//    MU1.Unlock()        MU1.Unlock()
1912//    Q1.Put()            Q2.Put()
1913//    Q1.Put()            Q2.Put()
1914//    MU1.Lock()          MU1.Lock()
1915//    MU2.Lock()          MU2.Lock()
1916//    write(GLOB)         write(GLOB)
1917//    MU2.Unlock()        MU2.Unlock()
1918//    MU1.Unlock()        MU1.Unlock()     sleep          sleep
1919//                                         Q1.Get()       Q1.Get()
1920//                                         Q2.Get()       Q2.Get()
1921//                                         MU2.Lock()     MU2.Lock()
1922//                                         write(GLOB)    write(GLOB)
1923//                                         MU2.Unlock()   MU2.Unlock()
1924//
1925
1926
1927ProducerConsumerQueue *Q1, *Q2;
1928int     GLOB = 0;
1929Mutex   MU, MU1, MU2;
1930
1931void Putter(ProducerConsumerQueue *q) {
1932  MU1.Lock();
1933  GLOB++;
1934  MU1.Unlock();
1935
1936  q->Put(NULL);
1937  q->Put(NULL);
1938
1939  MU1.Lock();
1940  MU2.Lock();
1941  GLOB++;
1942  MU2.Unlock();
1943  MU1.Unlock();
1944
1945}
1946
1947void Putter1() { Putter(Q1); }
1948void Putter2() { Putter(Q2); }
1949
1950void Getter() {
1951  usleep(100000);
1952  Q1->Get();
1953  Q2->Get();
1954
1955  MU2.Lock();
1956  GLOB++;
1957  MU2.Unlock();
1958
1959  usleep(48000); //  TODO: remove this when FP in test32 is fixed.
1960}
1961
1962void Run() {
1963  printf("test38: negative\n");
1964  Q1 = new ProducerConsumerQueue(INT_MAX);
1965  Q2 = new ProducerConsumerQueue(INT_MAX);
1966  MyThreadArray t(Getter, Getter, Putter1, Putter2);
1967  t.Start();
1968  t.Join();
1969  printf("\tGLOB=%d\n", GLOB);
1970  delete Q1;
1971  delete Q2;
1972}
1973REGISTER_TEST(Run, 38);
1974}  // namespace test38
1975
1976// test39: FP. Barrier. {{{1
1977namespace test39 {
1978#ifndef NO_BARRIER
1979// Same as test17 but uses Barrier class (pthread_barrier_t).
1980int     GLOB = 0;
1981const int N_threads = 3;
1982Barrier barrier(N_threads);
1983Mutex   MU;
1984
1985void Worker() {
1986  MU.Lock();
1987  GLOB++;
1988  MU.Unlock();
1989  barrier.Block();
1990  CHECK(GLOB == N_threads);
1991}
1992void Run() {
1993  ANNOTATE_TRACE_MEMORY(&GLOB);
1994//  ANNOTATE_EXPECT_RACE(&GLOB, "test39. FP. Fixed by MSMProp1. Barrier.");
1995  printf("test39: negative\n");
1996  {
1997    ThreadPool pool(N_threads);
1998    pool.StartWorkers();
1999    for (int i = 0; i < N_threads; i++) {
2000      pool.Add(NewCallback(Worker));
2001    }
2002  } // all folks are joined here.
2003  printf("\tGLOB=%d\n", GLOB);
2004}
2005REGISTER_TEST(Run, 39);
2006#endif // NO_BARRIER
2007}  // namespace test39
2008
2009
2010// test40: FP. Synchronization via Mutexes and PCQ. 4 threads. W/W {{{1
2011namespace test40 {
2012// Similar to test38 but with different order of events (due to sleep).
2013
2014// Putter1:            Putter2:           Getter1:       Getter2:
2015//    MU1.Lock()          MU1.Lock()
2016//    write(GLOB)         write(GLOB)
2017//    MU1.Unlock()        MU1.Unlock()
2018//    Q1.Put()            Q2.Put()
2019//    Q1.Put()            Q2.Put()
2020//                                        Q1.Get()       Q1.Get()
2021//                                        Q2.Get()       Q2.Get()
2022//                                        MU2.Lock()     MU2.Lock()
2023//                                        write(GLOB)    write(GLOB)
2024//                                        MU2.Unlock()   MU2.Unlock()
2025//
2026//    MU1.Lock()          MU1.Lock()
2027//    MU2.Lock()          MU2.Lock()
2028//    write(GLOB)         write(GLOB)
2029//    MU2.Unlock()        MU2.Unlock()
2030//    MU1.Unlock()        MU1.Unlock()
2031
2032
2033ProducerConsumerQueue *Q1, *Q2;
2034int     GLOB = 0;
2035Mutex   MU, MU1, MU2;
2036
2037void Putter(ProducerConsumerQueue *q) {
2038  MU1.Lock();
2039  GLOB++;
2040  MU1.Unlock();
2041
2042  q->Put(NULL);
2043  q->Put(NULL);
2044  usleep(100000);
2045
2046  MU1.Lock();
2047  MU2.Lock();
2048  GLOB++;
2049  MU2.Unlock();
2050  MU1.Unlock();
2051
2052}
2053
2054void Putter1() { Putter(Q1); }
2055void Putter2() { Putter(Q2); }
2056
2057void Getter() {
2058  Q1->Get();
2059  Q2->Get();
2060
2061  MU2.Lock();
2062  GLOB++;
2063  MU2.Unlock();
2064
2065  usleep(48000); //  TODO: remove this when FP in test32 is fixed.
2066}
2067
2068void Run() {
2069//  ANNOTATE_EXPECT_RACE(&GLOB, "test40. FP. Fixed by MSMProp1. Complex Stuff.");
2070  printf("test40: negative\n");
2071  Q1 = new ProducerConsumerQueue(INT_MAX);
2072  Q2 = new ProducerConsumerQueue(INT_MAX);
2073  MyThreadArray t(Getter, Getter, Putter1, Putter2);
2074  t.Start();
2075  t.Join();
2076  printf("\tGLOB=%d\n", GLOB);
2077  delete Q1;
2078  delete Q2;
2079}
2080REGISTER_TEST(Run, 40);
2081}  // namespace test40
2082
2083// test41: TN. Test for race that appears when loading a dynamic symbol. {{{1
2084namespace test41 {
2085void Worker() {
2086  ANNOTATE_NO_OP(NULL); // An empty function, loaded from dll.
2087}
2088void Run() {
2089  printf("test41: negative\n");
2090  MyThreadArray t(Worker, Worker, Worker);
2091  t.Start();
2092  t.Join();
2093}
2094REGISTER_TEST2(Run, 41, FEATURE|NEEDS_ANNOTATIONS);
2095}  // namespace test41
2096
2097
2098// test42: TN. Using the same cond var several times. {{{1
2099namespace test42 {
2100int GLOB = 0;
2101int COND = 0;
2102int N_threads = 3;
2103Mutex   MU;
2104
2105void Worker1() {
2106  GLOB=1;
2107
2108  MU.Lock();
2109  COND = 1;
2110  CV.Signal();
2111  MU.Unlock();
2112
2113  MU.Lock();
2114  while (COND != 0)
2115    CV.Wait(&MU);
2116  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
2117  MU.Unlock();
2118
2119  GLOB=3;
2120
2121}
2122
2123void Worker2() {
2124
2125  MU.Lock();
2126  while (COND != 1)
2127    CV.Wait(&MU);
2128  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
2129  MU.Unlock();
2130
2131  GLOB=2;
2132
2133  MU.Lock();
2134  COND = 0;
2135  CV.Signal();
2136  MU.Unlock();
2137
2138}
2139
2140void Run() {
2141//  ANNOTATE_EXPECT_RACE(&GLOB, "test42. TN. debugging.");
2142  printf("test42: negative\n");
2143  MyThreadArray t(Worker1, Worker2);
2144  t.Start();
2145  t.Join();
2146  printf("\tGLOB=%d\n", GLOB);
2147}
2148REGISTER_TEST2(Run, 42, FEATURE|NEEDS_ANNOTATIONS);
2149}  // namespace test42
2150
2151
2152
2153// test43: TN. {{{1
2154namespace test43 {
2155//
2156// Putter:            Getter:
2157// 1. write
2158// 2. Q.Put() --\     .
2159// 3. read       \--> a. Q.Get()
2160//                    b. read
2161int     GLOB = 0;
2162ProducerConsumerQueue Q(INT_MAX);
2163void Putter() {
2164  GLOB = 1;
2165  Q.Put(NULL);
2166  CHECK(GLOB == 1);
2167}
2168void Getter() {
2169  Q.Get();
2170  usleep(100000);
2171  CHECK(GLOB == 1);
2172}
2173void Run() {
2174  printf("test43: negative\n");
2175  MyThreadArray t(Putter, Getter);
2176  t.Start();
2177  t.Join();
2178  printf("\tGLOB=%d\n", GLOB);
2179}
2180REGISTER_TEST(Run, 43)
2181}  // namespace test43
2182
2183
2184// test44: FP. {{{1
2185namespace test44 {
2186//
2187// Putter:            Getter:
2188// 1. read
2189// 2. Q.Put() --\     .
2190// 3. MU.Lock()  \--> a. Q.Get()
2191// 4. write
2192// 5. MU.Unlock()
2193//                    b. MU.Lock()
2194//                    c. write
2195//                    d. MU.Unlock();
2196int     GLOB = 0;
2197Mutex   MU;
2198ProducerConsumerQueue Q(INT_MAX);
2199void Putter() {
2200  CHECK(GLOB == 0);
2201  Q.Put(NULL);
2202  MU.Lock();
2203  GLOB = 1;
2204  MU.Unlock();
2205}
2206void Getter() {
2207  Q.Get();
2208  usleep(100000);
2209  MU.Lock();
2210  GLOB = 1;
2211  MU.Unlock();
2212}
2213void Run() {
2214//  ANNOTATE_EXPECT_RACE(&GLOB, "test44. FP. Fixed by MSMProp1.");
2215  printf("test44: negative\n");
2216  MyThreadArray t(Putter, Getter);
2217  t.Start();
2218  t.Join();
2219  printf("\tGLOB=%d\n", GLOB);
2220}
2221REGISTER_TEST(Run, 44)
2222}  // namespace test44
2223
2224
2225// test45: TN. {{{1
2226namespace test45 {
2227//
2228// Putter:            Getter:
2229// 1. read
2230// 2. Q.Put() --\     .
2231// 3. MU.Lock()  \--> a. Q.Get()
2232// 4. write
2233// 5. MU.Unlock()
2234//                    b. MU.Lock()
2235//                    c. read
2236//                    d. MU.Unlock();
2237int     GLOB = 0;
2238Mutex   MU;
2239ProducerConsumerQueue Q(INT_MAX);
2240void Putter() {
2241  CHECK(GLOB == 0);
2242  Q.Put(NULL);
2243  MU.Lock();
2244  GLOB++;
2245  MU.Unlock();
2246}
2247void Getter() {
2248  Q.Get();
2249  usleep(100000);
2250  MU.Lock();
2251  CHECK(GLOB <= 1);
2252  MU.Unlock();
2253}
2254void Run() {
2255  printf("test45: negative\n");
2256  MyThreadArray t(Putter, Getter);
2257  t.Start();
2258  t.Join();
2259  printf("\tGLOB=%d\n", GLOB);
2260}
2261REGISTER_TEST(Run, 45)
2262}  // namespace test45
2263
2264
2265// test46: FN. {{{1
2266namespace test46 {
2267//
2268// First:                             Second:
2269// 1. write
2270// 2. MU.Lock()
2271// 3. write
2272// 4. MU.Unlock()                      (sleep)
2273//                                    a. MU.Lock()
2274//                                    b. write
2275//                                    c. MU.Unlock();
2276int     GLOB = 0;
2277Mutex   MU;
2278void First() {
2279  GLOB++;
2280  MU.Lock();
2281  GLOB++;
2282  MU.Unlock();
2283}
2284void Second() {
2285  usleep(480000);
2286  MU.Lock();
2287  GLOB++;
2288  MU.Unlock();
2289
2290  // just a print.
2291  // If we move it to Run()  we will get report in MSMHelgrind
2292  // due to its false positive (test32).
2293  MU.Lock();
2294  printf("\tGLOB=%d\n", GLOB);
2295  MU.Unlock();
2296}
2297void Run() {
2298  ANNOTATE_TRACE_MEMORY(&GLOB);
2299  MyThreadArray t(First, Second);
2300  t.Start();
2301  t.Join();
2302}
2303REGISTER_TEST(Run, 46)
2304}  // namespace test46
2305
2306
2307// test47: TP. Not detected by pure happens-before detectors. {{{1
2308namespace test47 {
2309// A true race that can not be detected by a pure happens-before
2310// race detector.
2311//
2312// First:                             Second:
2313// 1. write
2314// 2. MU.Lock()
2315// 3. MU.Unlock()                      (sleep)
2316//                                    a. MU.Lock()
2317//                                    b. MU.Unlock();
2318//                                    c. write
2319int     GLOB = 0;
2320Mutex   MU;
2321void First() {
2322  GLOB=1;
2323  MU.Lock();
2324  MU.Unlock();
2325}
2326void Second() {
2327  usleep(480000);
2328  MU.Lock();
2329  MU.Unlock();
2330  GLOB++;
2331}
2332void Run() {
2333  FAST_MODE_INIT(&GLOB);
2334  if (!Tsan_PureHappensBefore())
2335    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test47. TP. Not detected by pure HB.");
2336  printf("test47: positive\n");
2337  MyThreadArray t(First, Second);
2338  t.Start();
2339  t.Join();
2340  printf("\tGLOB=%d\n", GLOB);
2341}
2342REGISTER_TEST(Run, 47)
2343}  // namespace test47
2344
2345
2346// test48: FN. Simple race (single write vs multiple reads). {{{1
2347namespace test48 {
2348int     GLOB = 0;
2349// same as test10 but with single writer and  multiple readers
2350// A simple data race between single writer and  multiple readers.
2351// Write happens before Reads (enforced by sleep(1)),
2352
2353//
2354// Writer:                    Readers:
2355// 1. write(GLOB)             a. sleep(long enough so that GLOB
2356//                                is most likely initialized by Writer)
2357//                            b. read(GLOB)
2358//
2359//
2360// Eraser algorithm does not detect the race here,
2361// see Section 2.2 of http://citeseer.ist.psu.edu/savage97eraser.html.
2362//
2363void Writer() {
2364  GLOB = 3;
2365}
2366void Reader() {
2367  usleep(100000);
2368  CHECK(GLOB != -777);
2369}
2370
2371void Run() {
2372  FAST_MODE_INIT(&GLOB);
2373  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test48. TP. FN in MSMHelgrind.");
2374  printf("test48: positive\n");
2375  MyThreadArray t(Writer, Reader,Reader,Reader);
2376  t.Start();
2377  t.Join();
2378  printf("\tGLOB=%d\n", GLOB);
2379}
2380REGISTER_TEST(Run, 48)
2381}  // namespace test48
2382
2383
2384// test49: FN. Simple race (single write vs multiple reads). {{{1
2385namespace test49 {
2386int     GLOB = 0;
2387// same as test10 but with multiple read operations done by a single reader
2388// A simple data race between writer and readers.
2389// Write happens before Read (enforced by sleep(1)),
2390//
2391// Writer:                    Reader:
2392// 1. write(GLOB)             a. sleep(long enough so that GLOB
2393//                                is most likely initialized by Writer)
2394//                            b. read(GLOB)
2395//                            c. read(GLOB)
2396//                            d. read(GLOB)
2397//                            e. read(GLOB)
2398//
2399//
2400// Eraser algorithm does not detect the race here,
2401// see Section 2.2 of http://citeseer.ist.psu.edu/savage97eraser.html.
2402//
2403void Writer() {
2404  GLOB = 3;
2405}
2406void Reader() {
2407  usleep(100000);
2408  CHECK(GLOB != -777);
2409  CHECK(GLOB != -777);
2410  CHECK(GLOB != -777);
2411  CHECK(GLOB != -777);
2412}
2413
2414void Run() {
2415  FAST_MODE_INIT(&GLOB);
2416  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test49. TP. FN in MSMHelgrind.");
2417  printf("test49: positive\n");
2418  MyThreadArray t(Writer, Reader);
2419  t.Start();
2420  t.Join();
2421  printf("\tGLOB=%d\n", GLOB);
2422}
2423REGISTER_TEST(Run, 49);
2424}  // namespace test49
2425
2426
2427// test50: TP. Synchronization via CondVar. {{{1
2428namespace test50 {
2429int     GLOB = 0;
2430Mutex   MU;
2431// Two last write accesses to GLOB are not synchronized
2432//
2433// Waiter:                      Waker:
2434// 1. COND = 0
2435// 2. Start(Waker)
2436// 3. MU.Lock()                 a. write(GLOB)
2437//                              b. MU.Lock()
2438//                              c. COND = 1
2439//                         /--- d. CV.Signal()
2440//  4. while(COND != 1)   /     e. MU.Unlock()
2441//       CV.Wait(MU) <---/
2442//  5. MU.Unlock()
2443//  6. write(GLOB)              f. MU.Lock()
2444//                              g. write(GLOB)
2445//                              h. MU.Unlock()
2446
2447
2448void Waker() {
2449  usleep(100000);  // Make sure the waiter blocks.
2450
2451  GLOB = 1;
2452
2453  MU.Lock();
2454  COND = 1;
2455  CV.Signal();
2456  MU.Unlock();
2457
2458  usleep(100000);
2459  MU.Lock();
2460  GLOB = 3;
2461  MU.Unlock();
2462}
2463
2464void Waiter() {
2465  ThreadPool pool(1);
2466  pool.StartWorkers();
2467  COND = 0;
2468  pool.Add(NewCallback(Waker));
2469
2470  MU.Lock();
2471  while(COND != 1)
2472    CV.Wait(&MU);
2473  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
2474  MU.Unlock();
2475
2476  GLOB = 2;
2477}
2478void Run() {
2479  FAST_MODE_INIT(&GLOB);
2480  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test50. TP.");
2481  printf("test50: positive\n");
2482  Waiter();
2483  printf("\tGLOB=%d\n", GLOB);
2484}
2485REGISTER_TEST2(Run, 50, FEATURE|NEEDS_ANNOTATIONS);
2486}  // namespace test50
2487
2488
2489// test51: TP. Synchronization via CondVar: problem with several signals. {{{1
2490namespace test51 {
2491int     GLOB = 0;
2492int     COND = 0;
2493Mutex   MU;
2494
2495
2496// scheduler dependent results because of several signals
2497// second signal will be lost
2498//
2499// Waiter:                      Waker:
2500// 1. Start(Waker)
2501// 2. MU.Lock()
2502// 3. while(COND)
2503//       CV.Wait(MU)<-\         .
2504// 4. MU.Unlock()      \        .
2505// 5. write(GLOB)       \       a. write(GLOB)
2506//                       \      b. MU.Lock()
2507//                        \     c. COND = 1
2508//                         \--- d. CV.Signal()
2509//                              e. MU.Unlock()
2510//
2511//                              f. write(GLOB)
2512//
2513//                              g. MU.Lock()
2514//                              h. COND = 1
2515//                    LOST<---- i. CV.Signal()
2516//                              j. MU.Unlock()
2517
2518void Waker() {
2519
2520  usleep(10000);  // Make sure the waiter blocks.
2521
2522  GLOB = 1;
2523
2524  MU.Lock();
2525  COND = 1;
2526  CV.Signal();
2527  MU.Unlock();
2528
2529  usleep(10000);  // Make sure the waiter is signalled.
2530
2531  GLOB = 2;
2532
2533  MU.Lock();
2534  COND = 1;
2535  CV.Signal();   //Lost Signal
2536  MU.Unlock();
2537}
2538
2539void Waiter() {
2540
2541  ThreadPool pool(1);
2542  pool.StartWorkers();
2543  pool.Add(NewCallback(Waker));
2544
2545  MU.Lock();
2546  while(COND != 1)
2547    CV.Wait(&MU);
2548  MU.Unlock();
2549
2550
2551  GLOB = 3;
2552}
2553void Run() {
2554  FAST_MODE_INIT(&GLOB);
2555  ANNOTATE_EXPECT_RACE(&GLOB, "test51. TP.");
2556  printf("test51: positive\n");
2557  Waiter();
2558  printf("\tGLOB=%d\n", GLOB);
2559}
2560REGISTER_TEST(Run, 51);
2561}  // namespace test51
2562
2563
2564// test52: TP. Synchronization via CondVar: problem with several signals. {{{1
2565namespace test52 {
2566int     GLOB = 0;
2567int     COND = 0;
2568Mutex   MU;
2569
2570// same as test51 but the first signal will be lost
2571// scheduler dependent results because of several signals
2572//
2573// Waiter:                      Waker:
2574// 1. Start(Waker)
2575//                              a. write(GLOB)
2576//                              b. MU.Lock()
2577//                              c. COND = 1
2578//                    LOST<---- d. CV.Signal()
2579//                              e. MU.Unlock()
2580//
2581// 2. MU.Lock()
2582// 3. while(COND)
2583//       CV.Wait(MU)<-\         .
2584// 4. MU.Unlock()      \        f. write(GLOB)
2585// 5. write(GLOB)       \       .
2586//                       \      g. MU.Lock()
2587//                        \     h. COND = 1
2588//                         \--- i. CV.Signal()
2589//                              j. MU.Unlock()
2590
2591void Waker() {
2592
2593  GLOB = 1;
2594
2595  MU.Lock();
2596  COND = 1;
2597  CV.Signal();    //lost signal
2598  MU.Unlock();
2599
2600  usleep(20000);  // Make sure the waiter blocks
2601
2602  GLOB = 2;
2603
2604  MU.Lock();
2605  COND = 1;
2606  CV.Signal();
2607  MU.Unlock();
2608}
2609
2610void Waiter() {
2611  ThreadPool pool(1);
2612  pool.StartWorkers();
2613  pool.Add(NewCallback(Waker));
2614
2615  usleep(10000);  // Make sure the first signal will be lost
2616
2617  MU.Lock();
2618  while(COND != 1)
2619    CV.Wait(&MU);
2620  MU.Unlock();
2621
2622  GLOB = 3;
2623}
2624void Run() {
2625  FAST_MODE_INIT(&GLOB);
2626  ANNOTATE_EXPECT_RACE(&GLOB, "test52. TP.");
2627  printf("test52: positive\n");
2628  Waiter();
2629  printf("\tGLOB=%d\n", GLOB);
2630}
2631REGISTER_TEST(Run, 52);
2632}  // namespace test52
2633
2634
2635// test53: FP. Synchronization via implicit semaphore. {{{1
2636namespace test53 {
2637// Correctly synchronized test, but the common lockset is empty.
2638// The variable FLAG works as an implicit semaphore.
2639// MSMHelgrind still does not complain since it does not maintain the lockset
2640// at the exclusive state. But MSMProp1 does complain.
2641// See also test54.
2642//
2643//
2644// Initializer:                  Users
2645// 1. MU1.Lock()
2646// 2. write(GLOB)
2647// 3. FLAG = true
2648// 4. MU1.Unlock()
2649//                               a. MU1.Lock()
2650//                               b. f = FLAG;
2651//                               c. MU1.Unlock()
2652//                               d. if (!f) goto a.
2653//                               e. MU2.Lock()
2654//                               f. write(GLOB)
2655//                               g. MU2.Unlock()
2656//
2657
2658int     GLOB = 0;
2659bool    FLAG = false;
2660Mutex   MU1, MU2;
2661
2662void Initializer() {
2663  MU1.Lock();
2664  GLOB = 1000;
2665  FLAG = true;
2666  MU1.Unlock();
2667  usleep(100000); // just in case
2668}
2669
2670void User() {
2671  bool f = false;
2672  while(!f) {
2673    MU1.Lock();
2674    f = FLAG;
2675    MU1.Unlock();
2676    usleep(10000);
2677  }
2678  // at this point Initializer will not access GLOB again
2679  MU2.Lock();
2680  CHECK(GLOB >= 1000);
2681  GLOB++;
2682  MU2.Unlock();
2683}
2684
2685void Run() {
2686  FAST_MODE_INIT(&GLOB);
2687  if (!Tsan_PureHappensBefore())
2688    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test53. FP. Implicit semaphore");
2689  printf("test53: FP. false positive, Implicit semaphore\n");
2690  MyThreadArray t(Initializer, User, User);
2691  t.Start();
2692  t.Join();
2693  printf("\tGLOB=%d\n", GLOB);
2694}
2695REGISTER_TEST(Run, 53)
2696}  // namespace test53
2697
2698
2699// test54: TN. Synchronization via implicit semaphore. Annotated {{{1
2700namespace test54 {
2701// Same as test53, but annotated.
2702int     GLOB = 0;
2703bool    FLAG = false;
2704Mutex   MU1, MU2;
2705
2706void Initializer() {
2707  MU1.Lock();
2708  GLOB = 1000;
2709  FLAG = true;
2710  ANNOTATE_CONDVAR_SIGNAL(&GLOB);
2711  MU1.Unlock();
2712  usleep(100000); // just in case
2713}
2714
2715void User() {
2716  bool f = false;
2717  while(!f) {
2718    MU1.Lock();
2719    f = FLAG;
2720    MU1.Unlock();
2721    usleep(10000);
2722  }
2723  // at this point Initializer will not access GLOB again
2724  ANNOTATE_CONDVAR_WAIT(&GLOB);
2725  MU2.Lock();
2726  CHECK(GLOB >= 1000);
2727  GLOB++;
2728  MU2.Unlock();
2729}
2730
2731void Run() {
2732  printf("test54: negative\n");
2733  MyThreadArray t(Initializer, User, User);
2734  t.Start();
2735  t.Join();
2736  printf("\tGLOB=%d\n", GLOB);
2737}
2738REGISTER_TEST2(Run, 54, FEATURE|NEEDS_ANNOTATIONS)
2739}  // namespace test54
2740
2741
2742// test55: FP. Synchronization with TryLock. Not easy for race detectors {{{1
2743namespace test55 {
2744// "Correct" synchronization with TryLock and Lock.
2745//
2746// This scheme is actually very risky.
2747// It is covered in detail in this video:
2748// http://youtube.com/watch?v=mrvAqvtWYb4 (slide 36, near 50-th minute).
2749int     GLOB = 0;
2750Mutex   MU;
2751
2752void Worker_Lock() {
2753  GLOB = 1;
2754  MU.Lock();
2755}
2756
2757void Worker_TryLock() {
2758  while (true) {
2759    if (!MU.TryLock()) {
2760      MU.Unlock();
2761      break;
2762    }
2763    else
2764      MU.Unlock();
2765    usleep(100);
2766  }
2767  GLOB = 2;
2768}
2769
2770void Run() {
2771  printf("test55:\n");
2772  MyThreadArray t(Worker_Lock, Worker_TryLock);
2773  t.Start();
2774  t.Join();
2775  printf("\tGLOB=%d\n", GLOB);
2776}
2777REGISTER_TEST2(Run, 55, FEATURE|EXCLUDE_FROM_ALL);
2778}  // namespace test55
2779
2780
2781
2782// test56: TP. Use of ANNOTATE_BENIGN_RACE. {{{1
2783namespace test56 {
2784// For whatever reason the user wants to treat
2785// a race on GLOB as a benign race.
2786int     GLOB = 0;
2787int     GLOB2 = 0;
2788
2789void Worker() {
2790  GLOB++;
2791}
2792
2793void Run() {
2794  ANNOTATE_BENIGN_RACE(&GLOB, "test56. Use of ANNOTATE_BENIGN_RACE.");
2795  ANNOTATE_BENIGN_RACE(&GLOB2, "No race. The tool should be silent");
2796  printf("test56: positive\n");
2797  MyThreadArray t(Worker, Worker, Worker, Worker);
2798  t.Start();
2799  t.Join();
2800  printf("\tGLOB=%d\n", GLOB);
2801}
2802REGISTER_TEST2(Run, 56, FEATURE|NEEDS_ANNOTATIONS)
2803}  // namespace test56
2804
2805
2806// test57: TN: Correct use of atomics. {{{1
2807namespace test57 {
2808int     GLOB = 0;
2809void Writer() {
2810  for (int i = 0; i < 10; i++) {
2811    AtomicIncrement(&GLOB, 1);
2812    usleep(1000);
2813  }
2814}
2815void Reader() {
2816  while (GLOB < 20) usleep(1000);
2817}
2818void Run() {
2819  printf("test57: negative\n");
2820  MyThreadArray t(Writer, Writer, Reader, Reader);
2821  t.Start();
2822  t.Join();
2823  CHECK(GLOB == 20);
2824  printf("\tGLOB=%d\n", GLOB);
2825}
2826REGISTER_TEST(Run, 57)
2827}  // namespace test57
2828
2829
2830// test58: TN. User defined synchronization. {{{1
2831namespace test58 {
2832int     GLOB1 = 1;
2833int     GLOB2 = 2;
2834int     FLAG1 = 0;
2835int     FLAG2 = 0;
2836
2837// Correctly synchronized test, but the common lockset is empty.
2838// The variables FLAG1 and FLAG2 used for synchronization and as
2839// temporary variables for swapping two global values.
2840// Such kind of synchronization is rarely used (Excluded from all tests??).
2841
2842void Worker2() {
2843  FLAG1=GLOB2;
2844
2845  while(!FLAG2)
2846    ;
2847  GLOB2=FLAG2;
2848}
2849
2850void Worker1() {
2851  FLAG2=GLOB1;
2852
2853  while(!FLAG1)
2854    ;
2855  GLOB1=FLAG1;
2856}
2857
2858void Run() {
2859  printf("test58:\n");
2860  MyThreadArray t(Worker1, Worker2);
2861  t.Start();
2862  t.Join();
2863  printf("\tGLOB1=%d\n", GLOB1);
2864  printf("\tGLOB2=%d\n", GLOB2);
2865}
2866REGISTER_TEST2(Run, 58, FEATURE|EXCLUDE_FROM_ALL)
2867}  // namespace test58
2868
2869
2870
2871// test59: TN. User defined synchronization. Annotated {{{1
2872namespace test59 {
2873int     COND1 = 0;
2874int     COND2 = 0;
2875int     GLOB1 = 1;
2876int     GLOB2 = 2;
2877int     FLAG1 = 0;
2878int     FLAG2 = 0;
2879// same as test 58 but annotated
2880
2881void Worker2() {
2882  FLAG1=GLOB2;
2883  ANNOTATE_CONDVAR_SIGNAL(&COND2);
2884  while(!FLAG2) usleep(1);
2885  ANNOTATE_CONDVAR_WAIT(&COND1);
2886  GLOB2=FLAG2;
2887}
2888
2889void Worker1() {
2890  FLAG2=GLOB1;
2891  ANNOTATE_CONDVAR_SIGNAL(&COND1);
2892  while(!FLAG1) usleep(1);
2893  ANNOTATE_CONDVAR_WAIT(&COND2);
2894  GLOB1=FLAG1;
2895}
2896
2897void Run() {
2898  printf("test59: negative\n");
2899  ANNOTATE_BENIGN_RACE(&FLAG1, "synchronization via 'safe' race");
2900  ANNOTATE_BENIGN_RACE(&FLAG2, "synchronization via 'safe' race");
2901  MyThreadArray t(Worker1, Worker2);
2902  t.Start();
2903  t.Join();
2904  printf("\tGLOB1=%d\n", GLOB1);
2905  printf("\tGLOB2=%d\n", GLOB2);
2906}
2907REGISTER_TEST2(Run, 59, FEATURE|NEEDS_ANNOTATIONS)
2908}  // namespace test59
2909
2910
2911// test60: TN. Correct synchronization using signal-wait {{{1
2912namespace test60 {
2913int     COND1 = 0;
2914int     COND2 = 0;
2915int     GLOB1 = 1;
2916int     GLOB2 = 2;
2917int     FLAG2 = 0;
2918int     FLAG1 = 0;
2919Mutex   MU;
2920// same as test 59 but synchronized with signal-wait.
2921
2922void Worker2() {
2923  FLAG1=GLOB2;
2924
2925  MU.Lock();
2926  COND1 = 1;
2927  CV.Signal();
2928  MU.Unlock();
2929
2930  MU.Lock();
2931  while(COND2 != 1)
2932    CV.Wait(&MU);
2933  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
2934  MU.Unlock();
2935
2936  GLOB2=FLAG2;
2937}
2938
2939void Worker1() {
2940  FLAG2=GLOB1;
2941
2942  MU.Lock();
2943  COND2 = 1;
2944  CV.Signal();
2945  MU.Unlock();
2946
2947  MU.Lock();
2948  while(COND1 != 1)
2949    CV.Wait(&MU);
2950  ANNOTATE_CONDVAR_LOCK_WAIT(&CV, &MU);
2951  MU.Unlock();
2952
2953  GLOB1=FLAG1;
2954}
2955
2956void Run() {
2957  printf("test60: negative\n");
2958  MyThreadArray t(Worker1, Worker2);
2959  t.Start();
2960  t.Join();
2961  printf("\tGLOB1=%d\n", GLOB1);
2962  printf("\tGLOB2=%d\n", GLOB2);
2963}
2964REGISTER_TEST2(Run, 60, FEATURE|NEEDS_ANNOTATIONS)
2965}  // namespace test60
2966
2967
2968// test61: TN. Synchronization via Mutex as in happens-before, annotated. {{{1
2969namespace test61 {
2970Mutex MU;
2971int     GLOB = 0;
2972int     *P1 = NULL, *P2 = NULL;
2973
2974// In this test Mutex lock/unlock operations introduce happens-before relation.
2975// We annotate the code so that MU is treated as in pure happens-before detector.
2976
2977
2978void Putter() {
2979  ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&MU);
2980  MU.Lock();
2981  if (P1 == NULL) {
2982    P1 = &GLOB;
2983    *P1 = 1;
2984  }
2985  MU.Unlock();
2986}
2987
2988void Getter() {
2989  bool done  = false;
2990  while (!done) {
2991    MU.Lock();
2992    if (P1) {
2993      done = true;
2994      P2 = P1;
2995      P1 = NULL;
2996    }
2997    MU.Unlock();
2998  }
2999  *P2 = 2;
3000}
3001
3002
3003void Run() {
3004  printf("test61: negative\n");
3005  MyThreadArray t(Putter, Getter);
3006  t.Start();
3007  t.Join();
3008  printf("\tGLOB=%d\n", GLOB);
3009}
3010REGISTER_TEST2(Run, 61, FEATURE|NEEDS_ANNOTATIONS)
3011}  // namespace test61
3012
3013
3014// test62: STAB. Create as many segments as possible. {{{1
3015namespace test62 {
3016// Helgrind 3.3.0 will fail as it has a hard limit of < 2^24 segments.
3017// A better scheme is to implement garbage collection for segments.
3018ProducerConsumerQueue Q(INT_MAX);
3019const int N = 1 << 22;
3020
3021void Putter() {
3022  for (int i = 0; i < N; i++){
3023    if ((i % (N / 8)) == 0) {
3024      printf("i=%d\n", i);
3025    }
3026    Q.Put(NULL);
3027  }
3028}
3029
3030void Getter() {
3031  for (int i = 0; i < N; i++)
3032    Q.Get();
3033}
3034
3035void Run() {
3036  printf("test62:\n");
3037  MyThreadArray t(Putter, Getter);
3038  t.Start();
3039  t.Join();
3040}
3041REGISTER_TEST2(Run, 62, STABILITY|EXCLUDE_FROM_ALL)
3042}  // namespace test62
3043
3044
3045// test63: STAB. Create as many segments as possible and do it fast. {{{1
3046namespace test63 {
3047// Helgrind 3.3.0 will fail as it has a hard limit of < 2^24 segments.
3048// A better scheme is to implement garbage collection for segments.
3049const int N = 1 << 24;
3050int C = 0;
3051
3052void Putter() {
3053  for (int i = 0; i < N; i++){
3054    if ((i % (N / 8)) == 0) {
3055      printf("i=%d\n", i);
3056    }
3057    ANNOTATE_CONDVAR_SIGNAL(&C);
3058  }
3059}
3060
3061void Getter() {
3062}
3063
3064void Run() {
3065  printf("test63:\n");
3066  MyThreadArray t(Putter, Getter);
3067  t.Start();
3068  t.Join();
3069}
3070REGISTER_TEST2(Run, 63, STABILITY|EXCLUDE_FROM_ALL)
3071}  // namespace test63
3072
3073
3074// test64: TP. T2 happens-before T3, but T1 is independent. Reads in T1/T2. {{{1
3075namespace test64 {
3076// True race between T1 and T3:
3077//
3078// T1:                   T2:                   T3:
3079// 1. read(GLOB)         (sleep)
3080//                       a. read(GLOB)
3081//                       b. Q.Put() ----->    A. Q.Get()
3082//                                            B. write(GLOB)
3083//
3084//
3085
3086int     GLOB = 0;
3087ProducerConsumerQueue Q(INT_MAX);
3088
3089void T1() {
3090  CHECK(GLOB == 0);
3091}
3092
3093void T2() {
3094  usleep(100000);
3095  CHECK(GLOB == 0);
3096  Q.Put(NULL);
3097}
3098
3099void T3() {
3100  Q.Get();
3101  GLOB = 1;
3102}
3103
3104
3105void Run() {
3106  FAST_MODE_INIT(&GLOB);
3107  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test64: TP.");
3108  printf("test64: positive\n");
3109  MyThreadArray t(T1, T2, T3);
3110  t.Start();
3111  t.Join();
3112  printf("\tGLOB=%d\n", GLOB);
3113}
3114REGISTER_TEST(Run, 64)
3115}  // namespace test64
3116
3117
3118// test65: TP. T2 happens-before T3, but T1 is independent. Writes in T1/T2. {{{1
3119namespace test65 {
3120// Similar to test64.
3121// True race between T1 and T3:
3122//
3123// T1:                   T2:                   T3:
3124// 1. MU.Lock()
3125// 2. write(GLOB)
3126// 3. MU.Unlock()         (sleep)
3127//                       a. MU.Lock()
3128//                       b. write(GLOB)
3129//                       c. MU.Unlock()
3130//                       d. Q.Put() ----->    A. Q.Get()
3131//                                            B. write(GLOB)
3132//
3133//
3134
3135int     GLOB = 0;
3136Mutex   MU;
3137ProducerConsumerQueue Q(INT_MAX);
3138
3139void T1() {
3140  MU.Lock();
3141  GLOB++;
3142  MU.Unlock();
3143}
3144
3145void T2() {
3146  usleep(100000);
3147  MU.Lock();
3148  GLOB++;
3149  MU.Unlock();
3150  Q.Put(NULL);
3151}
3152
3153void T3() {
3154  Q.Get();
3155  GLOB = 1;
3156}
3157
3158
3159void Run() {
3160  FAST_MODE_INIT(&GLOB);
3161  if (!Tsan_PureHappensBefore())
3162    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test65. TP.");
3163  printf("test65: positive\n");
3164  MyThreadArray t(T1, T2, T3);
3165  t.Start();
3166  t.Join();
3167  printf("\tGLOB=%d\n", GLOB);
3168}
3169REGISTER_TEST(Run, 65)
3170}  // namespace test65
3171
3172
3173// test66: TN. Two separate pairs of signaller/waiter using the same CV. {{{1
3174namespace test66 {
3175int     GLOB1 = 0;
3176int     GLOB2 = 0;
3177int     C1 = 0;
3178int     C2 = 0;
3179Mutex   MU;
3180
3181void Signaller1() {
3182  GLOB1 = 1;
3183  MU.Lock();
3184  C1 = 1;
3185  CV.Signal();
3186  MU.Unlock();
3187}
3188
3189void Signaller2() {
3190  GLOB2 = 1;
3191  usleep(100000);
3192  MU.Lock();
3193  C2 = 1;
3194  CV.Signal();
3195  MU.Unlock();
3196}
3197
3198void Waiter1() {
3199  MU.Lock();
3200  while (C1 != 1) CV.Wait(&MU);
3201  ANNOTATE_CONDVAR_WAIT(&CV);
3202  MU.Unlock();
3203  GLOB1 = 2;
3204}
3205
3206void Waiter2() {
3207  MU.Lock();
3208  while (C2 != 1) CV.Wait(&MU);
3209  ANNOTATE_CONDVAR_WAIT(&CV);
3210  MU.Unlock();
3211  GLOB2 = 2;
3212}
3213
3214void Run() {
3215  printf("test66: negative\n");
3216  MyThreadArray t(Signaller1, Signaller2, Waiter1, Waiter2);
3217  t.Start();
3218  t.Join();
3219  printf("\tGLOB=%d/%d\n", GLOB1, GLOB2);
3220}
3221REGISTER_TEST2(Run, 66, FEATURE|NEEDS_ANNOTATIONS)
3222}  // namespace test66
3223
3224
3225// test67: FN. Race between Signaller1 and Waiter2 {{{1
3226namespace test67 {
3227// Similar to test66, but there is a real race here.
3228//
3229// Here we create a happens-before arc between Signaller1 and Waiter2
3230// even though there should be no such arc.
3231// However, it's probably improssible (or just very hard) to avoid it.
3232int     GLOB = 0;
3233int     C1 = 0;
3234int     C2 = 0;
3235Mutex   MU;
3236
3237void Signaller1() {
3238  GLOB = 1;
3239  MU.Lock();
3240  C1 = 1;
3241  CV.Signal();
3242  MU.Unlock();
3243}
3244
3245void Signaller2() {
3246  usleep(100000);
3247  MU.Lock();
3248  C2 = 1;
3249  CV.Signal();
3250  MU.Unlock();
3251}
3252
3253void Waiter1() {
3254  MU.Lock();
3255  while (C1 != 1) CV.Wait(&MU);
3256  ANNOTATE_CONDVAR_WAIT(&CV);
3257  MU.Unlock();
3258}
3259
3260void Waiter2() {
3261  MU.Lock();
3262  while (C2 != 1) CV.Wait(&MU);
3263  ANNOTATE_CONDVAR_WAIT(&CV);
3264  MU.Unlock();
3265  GLOB = 2;
3266}
3267
3268void Run() {
3269  FAST_MODE_INIT(&GLOB);
3270  ANNOTATE_EXPECT_RACE(&GLOB, "test67. FN. Race between Signaller1 and Waiter2");
3271  printf("test67: positive\n");
3272  MyThreadArray t(Signaller1, Signaller2, Waiter1, Waiter2);
3273  t.Start();
3274  t.Join();
3275  printf("\tGLOB=%d\n", GLOB);
3276}
3277REGISTER_TEST2(Run, 67, FEATURE|NEEDS_ANNOTATIONS|EXCLUDE_FROM_ALL)
3278}  // namespace test67
3279
3280
3281// test68: TP. Writes are protected by MU, reads are not. {{{1
3282namespace test68 {
3283// In this test, all writes to GLOB are protected by a mutex
3284// but some reads go unprotected.
3285// This is certainly a race, but in some cases such code could occur in
3286// a correct program. For example, the unprotected reads may be used
3287// for showing statistics and are not required to be precise.
3288int     GLOB = 0;
3289int     COND = 0;
3290const int N_writers = 3;
3291Mutex MU, MU1;
3292
3293void Writer() {
3294  for (int i = 0; i < 100; i++) {
3295    MU.Lock();
3296    GLOB++;
3297    MU.Unlock();
3298  }
3299
3300  // we are done
3301  MU1.Lock();
3302  COND++;
3303  MU1.Unlock();
3304}
3305
3306void Reader() {
3307  bool cont = true;
3308  while (cont) {
3309    CHECK(GLOB >= 0);
3310
3311    // are we done?
3312    MU1.Lock();
3313    if (COND == N_writers)
3314      cont = false;
3315    MU1.Unlock();
3316    usleep(100);
3317  }
3318}
3319
3320void Run() {
3321  FAST_MODE_INIT(&GLOB);
3322  ANNOTATE_EXPECT_RACE(&GLOB, "TP. Writes are protected, reads are not.");
3323  printf("test68: positive\n");
3324  MyThreadArray t(Reader, Writer, Writer, Writer);
3325  t.Start();
3326  t.Join();
3327  printf("\tGLOB=%d\n", GLOB);
3328}
3329REGISTER_TEST(Run, 68)
3330}  // namespace test68
3331
3332
3333// test69:  {{{1
3334namespace test69 {
3335// This is the same as test68, but annotated.
3336// We do not want to annotate GLOB as a benign race
3337// because we want to allow racy reads only in certain places.
3338//
3339// TODO:
3340int     GLOB = 0;
3341int     COND = 0;
3342const int N_writers = 3;
3343int     FAKE_MU = 0;
3344Mutex MU, MU1;
3345
3346void Writer() {
3347  for (int i = 0; i < 10; i++) {
3348    MU.Lock();
3349    GLOB++;
3350    MU.Unlock();
3351  }
3352
3353  // we are done
3354  MU1.Lock();
3355  COND++;
3356  MU1.Unlock();
3357}
3358
3359void Reader() {
3360  bool cont = true;
3361  while (cont) {
3362    ANNOTATE_IGNORE_READS_BEGIN();
3363    CHECK(GLOB >= 0);
3364    ANNOTATE_IGNORE_READS_END();
3365
3366    // are we done?
3367    MU1.Lock();
3368    if (COND == N_writers)
3369      cont = false;
3370    MU1.Unlock();
3371    usleep(100);
3372  }
3373}
3374
3375void Run() {
3376  printf("test69: negative\n");
3377  MyThreadArray t(Reader, Writer, Writer, Writer);
3378  t.Start();
3379  t.Join();
3380  printf("\tGLOB=%d\n", GLOB);
3381}
3382REGISTER_TEST(Run, 69)
3383}  // namespace test69
3384
3385// test70: STAB. Check that TRACE_MEMORY works. {{{1
3386namespace test70 {
3387int     GLOB = 0;
3388void Run() {
3389  printf("test70: negative\n");
3390  ANNOTATE_TRACE_MEMORY(&GLOB);
3391  GLOB = 1;
3392  printf("\tGLOB=%d\n", GLOB);
3393}
3394REGISTER_TEST(Run, 70)
3395}  // namespace test70
3396
3397
3398
3399// test71: TN. strlen, index. {{{1
3400namespace test71 {
3401// This test is a reproducer for a benign race in strlen (as well as index, etc).
3402// Some implementations of strlen may read up to 7 bytes past the end of the string
3403// thus touching memory which may not belong to this string.
3404// Such race is benign because the data read past the end of the string is not used.
3405//
3406// Here, we allocate a 8-byte aligned string str and initialize first 5 bytes.
3407// Then one thread calls strlen(str) (as well as index & rindex)
3408// and another thread initializes str[5]..str[7].
3409//
3410// This can be fixed in Helgrind by intercepting strlen and replacing it
3411// with a simpler implementation.
3412
3413char    *str;
3414void WorkerX() {
3415  usleep(100000);
3416  CHECK(strlen(str) == 4);
3417  CHECK(index(str, 'X') == str);
3418  CHECK(index(str, 'x') == str+1);
3419  CHECK(index(str, 'Y') == NULL);
3420  CHECK(rindex(str, 'X') == str+2);
3421  CHECK(rindex(str, 'x') == str+3);
3422  CHECK(rindex(str, 'Y') == NULL);
3423}
3424void WorkerY() {
3425  str[5] = 'Y';
3426  str[6] = 'Y';
3427  str[7] = '\0';
3428}
3429
3430void Run() {
3431  str = new char[8];
3432  str[0] = 'X';
3433  str[1] = 'x';
3434  str[2] = 'X';
3435  str[3] = 'x';
3436  str[4] = '\0';
3437
3438  printf("test71: negative (strlen & index)\n");
3439  MyThread t1(WorkerY);
3440  MyThread t2(WorkerX);
3441  t1.Start();
3442  t2.Start();
3443  t1.Join();
3444  t2.Join();
3445  printf("\tstrX=%s; strY=%s\n", str, str+5);
3446}
3447REGISTER_TEST(Run, 71)
3448}  // namespace test71
3449
3450
3451// test72: STAB. Stress test for the number of segment sets (SSETs). {{{1
3452namespace test72 {
3453#ifndef NO_BARRIER
3454// Variation of test33.
3455// Instead of creating Nlog*N_iter threads,
3456// we create Nlog threads and do N_iter barriers.
3457int     GLOB = 0;
3458const int N_iter = 30;
3459const int Nlog  = 16;
3460const int N     = 1 << Nlog;
3461static int64_t ARR1[N];
3462static int64_t ARR2[N];
3463Barrier *barriers[N_iter];
3464Mutex   MU;
3465
3466void Worker() {
3467  MU.Lock();
3468  int n = ++GLOB;
3469  MU.Unlock();
3470
3471  n %= Nlog;
3472
3473  long t0 = clock();
3474  long t __attribute__((unused)) = t0;
3475
3476  for (int it = 0; it < N_iter; it++) {
3477    if(n == 0) {
3478      //printf("Iter: %d; %ld %ld\n", it, clock() - t, clock() - t0);
3479      t = clock();
3480    }
3481    // Iterate N_iter times, block on barrier after each iteration.
3482    // This way Helgrind will create new segments after each barrier.
3483
3484    for (int x = 0; x < 2; x++) {
3485      // run the inner loop twice.
3486      // When a memory location is accessed second time it is likely
3487      // that the state (SVal) will be unchanged.
3488      // The memory machine may optimize this case.
3489      for (int i = 0; i < N; i++) {
3490        // ARR1[i] and ARR2[N-1-i] are accessed by threads from i-th subset
3491        if (i & (1 << n)) {
3492          CHECK(ARR1[i] == 0);
3493          CHECK(ARR2[N-1-i] == 0);
3494        }
3495      }
3496    }
3497    barriers[it]->Block();
3498  }
3499}
3500
3501
3502void Run() {
3503  printf("test72:\n");
3504
3505  std::vector<MyThread*> vec(Nlog);
3506
3507  for (int i = 0; i < N_iter; i++)
3508    barriers[i] = new Barrier(Nlog);
3509
3510  // Create and start Nlog threads
3511  for (int i = 0; i < Nlog; i++) {
3512    vec[i] = new MyThread(Worker);
3513    vec[i]->Start();
3514  }
3515
3516  // Join all threads.
3517  for (int i = 0; i < Nlog; i++) {
3518    vec[i]->Join();
3519    delete vec[i];
3520  }
3521  for (int i = 0; i < N_iter; i++)
3522    delete barriers[i];
3523
3524  /*printf("\tGLOB=%d; ARR[1]=%d; ARR[7]=%d; ARR[N-1]=%d\n",
3525         GLOB, (int)ARR1[1], (int)ARR1[7], (int)ARR1[N-1]);*/
3526}
3527REGISTER_TEST2(Run, 72, STABILITY|PERFORMANCE|EXCLUDE_FROM_ALL);
3528#endif // NO_BARRIER
3529}  // namespace test72
3530
3531
3532// test73: STAB. Stress test for the number of (SSETs), different access sizes. {{{1
3533namespace test73 {
3534#ifndef NO_BARRIER
3535// Variation of test72.
3536// We perform accesses of different sizes to the same location.
3537int     GLOB = 0;
3538const int N_iter = 2;
3539const int Nlog  = 16;
3540const int N     = 1 << Nlog;
3541union uint64_union {
3542  uint64_t u64[1];
3543  uint32_t u32[2];
3544  uint16_t u16[4];
3545  uint8_t  u8 [8];
3546};
3547static uint64_union ARR1[N];
3548union uint32_union {
3549  uint32_t u32[1];
3550  uint16_t u16[2];
3551  uint8_t  u8 [4];
3552};
3553static uint32_union ARR2[N];
3554Barrier *barriers[N_iter];
3555Mutex   MU;
3556
3557void Worker() {
3558  MU.Lock();
3559  int n = ++GLOB;
3560  MU.Unlock();
3561
3562  n %= Nlog;
3563
3564  for (int it = 0; it < N_iter; it++) {
3565    // Iterate N_iter times, block on barrier after each iteration.
3566    // This way Helgrind will create new segments after each barrier.
3567
3568    for (int x = 0; x < 4; x++) {
3569      for (int i = 0; i < N; i++) {
3570        // ARR1[i] are accessed by threads from i-th subset
3571        if (i & (1 << n)) {
3572          for (int off = 0; off < (1 << x); off++) {
3573            switch(x) {
3574              case 0: CHECK(ARR1[i].u64[off] == 0); break;
3575              case 1: CHECK(ARR1[i].u32[off] == 0); break;
3576              case 2: CHECK(ARR1[i].u16[off] == 0); break;
3577              case 3: CHECK(ARR1[i].u8 [off] == 0); break;
3578            }
3579            switch(x) {
3580              case 1: CHECK(ARR2[i].u32[off] == 0); break;
3581              case 2: CHECK(ARR2[i].u16[off] == 0); break;
3582              case 3: CHECK(ARR2[i].u8 [off] == 0); break;
3583            }
3584          }
3585        }
3586      }
3587    }
3588    barriers[it]->Block();
3589  }
3590}
3591
3592
3593
3594void Run() {
3595  printf("test73:\n");
3596
3597  std::vector<MyThread*> vec(Nlog);
3598
3599  for (int i = 0; i < N_iter; i++)
3600    barriers[i] = new Barrier(Nlog);
3601
3602  // Create and start Nlog threads
3603  for (int i = 0; i < Nlog; i++) {
3604    vec[i] = new MyThread(Worker);
3605    vec[i]->Start();
3606  }
3607
3608  // Join all threads.
3609  for (int i = 0; i < Nlog; i++) {
3610    vec[i]->Join();
3611    delete vec[i];
3612  }
3613  for (int i = 0; i < N_iter; i++)
3614    delete barriers[i];
3615
3616  /*printf("\tGLOB=%d; ARR[1]=%d; ARR[7]=%d; ARR[N-1]=%d\n",
3617         GLOB, (int)ARR1[1], (int)ARR1[7], (int)ARR1[N-1]);*/
3618}
3619REGISTER_TEST2(Run, 73, STABILITY|PERFORMANCE|EXCLUDE_FROM_ALL);
3620#endif // NO_BARRIER
3621}  // namespace test73
3622
3623
3624// test74: PERF. A lot of lock/unlock calls. {{{1
3625namespace    test74 {
3626const int N = 100000;
3627Mutex   MU;
3628void Run() {
3629  printf("test74: perf\n");
3630  for (int i = 0; i < N; i++ ) {
3631    MU.Lock();
3632    MU.Unlock();
3633  }
3634}
3635REGISTER_TEST(Run, 74)
3636}  // namespace test74
3637
3638
3639// test75: TN. Test for sem_post, sem_wait, sem_trywait. {{{1
3640namespace test75 {
3641int     GLOB = 0;
3642sem_t   sem[2];
3643
3644void Poster() {
3645  GLOB = 1;
3646  sem_post(&sem[0]);
3647  sem_post(&sem[1]);
3648}
3649
3650void Waiter() {
3651  sem_wait(&sem[0]);
3652  CHECK(GLOB==1);
3653}
3654void TryWaiter() {
3655  usleep(500000);
3656  sem_trywait(&sem[1]);
3657  CHECK(GLOB==1);
3658}
3659
3660void Run() {
3661#ifndef DRT_NO_SEM
3662  sem_init(&sem[0], 0, 0);
3663  sem_init(&sem[1], 0, 0);
3664
3665  printf("test75: negative\n");
3666  {
3667    MyThreadArray t(Poster, Waiter);
3668    t.Start();
3669    t.Join();
3670  }
3671  GLOB = 2;
3672  {
3673    MyThreadArray t(Poster, TryWaiter);
3674    t.Start();
3675    t.Join();
3676  }
3677  printf("\tGLOB=%d\n", GLOB);
3678
3679  sem_destroy(&sem[0]);
3680  sem_destroy(&sem[1]);
3681#endif
3682}
3683REGISTER_TEST(Run, 75)
3684}  // namespace test75
3685
3686// RefCountedClass {{{1
3687struct RefCountedClass {
3688 public:
3689  RefCountedClass() {
3690    annotate_unref_ = false;
3691    ref_ = 0;
3692    data_ = 0;
3693  }
3694
3695  ~RefCountedClass() {
3696    CHECK(ref_ == 0);     // race may be reported here
3697    int data_val = data_; // and here
3698                          // if MU is not annotated
3699    data_ = 0;
3700    ref_ = -1;
3701    printf("\tRefCountedClass::data_ = %d\n", data_val);
3702  }
3703
3704  void AccessData() {
3705    this->mu_.Lock();
3706    this->data_++;
3707    this->mu_.Unlock();
3708  }
3709
3710  void Ref() {
3711    MU.Lock();
3712    CHECK(ref_ >= 0);
3713    ref_++;
3714    MU.Unlock();
3715  }
3716
3717  void Unref() {
3718    MU.Lock();
3719    CHECK(ref_ > 0);
3720    ref_--;
3721    bool do_delete = ref_ == 0;
3722    if (annotate_unref_) {
3723      ANNOTATE_CONDVAR_SIGNAL(this);
3724    }
3725    MU.Unlock();
3726    if (do_delete) {
3727      if (annotate_unref_) {
3728        ANNOTATE_CONDVAR_WAIT(this);
3729      }
3730      delete this;
3731    }
3732  }
3733
3734  static void Annotate_MU() {
3735    ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&MU);
3736  }
3737  void AnnotateUnref() {
3738    annotate_unref_ = true;
3739  }
3740  void Annotate_Race() {
3741    ANNOTATE_BENIGN_RACE(&this->data_, "needs annotation");
3742    ANNOTATE_BENIGN_RACE(&this->ref_, "needs annotation");
3743  }
3744 private:
3745  bool annotate_unref_;
3746
3747  int data_;
3748  Mutex mu_; // protects data_
3749
3750  int ref_;
3751  static Mutex MU; // protects ref_
3752};
3753
3754Mutex RefCountedClass::MU;
3755
3756// test76: FP. Ref counting, no annotations. {{{1
3757namespace test76 {
3758#ifndef NO_BARRIER
3759int     GLOB = 0;
3760Barrier barrier(4);
3761RefCountedClass *object = NULL;
3762void Worker() {
3763  object->Ref();
3764  barrier.Block();
3765  object->AccessData();
3766  object->Unref();
3767}
3768void Run() {
3769  printf("test76: false positive (ref counting)\n");
3770  object = new RefCountedClass;
3771  object->Annotate_Race();
3772  MyThreadArray t(Worker, Worker, Worker, Worker);
3773  t.Start();
3774  t.Join();
3775}
3776REGISTER_TEST2(Run, 76, FEATURE)
3777#endif // NO_BARRIER
3778}  // namespace test76
3779
3780
3781
3782// test77: TN. Ref counting, MU is annotated. {{{1
3783namespace test77 {
3784#ifndef NO_BARRIER
3785// same as test76, but RefCountedClass::MU is annotated.
3786int     GLOB = 0;
3787Barrier barrier(4);
3788RefCountedClass *object = NULL;
3789void Worker() {
3790  object->Ref();
3791  barrier.Block();
3792  object->AccessData();
3793  object->Unref();
3794}
3795void Run() {
3796  printf("test77: true negative (ref counting), mutex is annotated\n");
3797  RefCountedClass::Annotate_MU();
3798  object = new RefCountedClass;
3799  MyThreadArray t(Worker, Worker, Worker, Worker);
3800  t.Start();
3801  t.Join();
3802}
3803REGISTER_TEST(Run, 77)
3804#endif // NO_BARRIER
3805}  // namespace test77
3806
3807
3808
3809// test78: TN. Ref counting, Unref is annotated. {{{1
3810namespace test78 {
3811#ifndef NO_BARRIER
3812// same as test76, but RefCountedClass::Unref is annotated.
3813int     GLOB = 0;
3814Barrier barrier(4);
3815RefCountedClass *object = NULL;
3816void Worker() {
3817  object->Ref();
3818  barrier.Block();
3819  object->AccessData();
3820  object->Unref();
3821}
3822void Run() {
3823  printf("test78: true negative (ref counting), Unref is annotated\n");
3824  RefCountedClass::Annotate_MU();
3825  object = new RefCountedClass;
3826  MyThreadArray t(Worker, Worker, Worker, Worker);
3827  t.Start();
3828  t.Join();
3829}
3830REGISTER_TEST(Run, 78)
3831#endif // NO_BARRIER
3832}  // namespace test78
3833
3834
3835
3836// test79 TN. Swap. {{{1
3837namespace test79 {
3838#if 0
3839typedef __gnu_cxx::hash_map<int, int> map_t;
3840#else
3841typedef std::map<int, int> map_t;
3842#endif
3843map_t   MAP;
3844Mutex   MU;
3845
3846// Here we use swap to pass MAP between threads.
3847// The synchronization is correct, but w/o ANNOTATE_MUTEX_IS_USED_AS_CONDVAR
3848// Helgrind will complain.
3849
3850void Worker1() {
3851  map_t tmp;
3852  MU.Lock();
3853  // We swap the new empty map 'tmp' with 'MAP'.
3854  MAP.swap(tmp);
3855  MU.Unlock();
3856  // tmp (which is the old version of MAP) is destroyed here.
3857}
3858
3859void Worker2() {
3860  MU.Lock();
3861  MAP[1]++;  // Just update MAP under MU.
3862  MU.Unlock();
3863}
3864
3865void Worker3() { Worker1(); }
3866void Worker4() { Worker2(); }
3867
3868void Run() {
3869  ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&MU);
3870  printf("test79: negative\n");
3871  MyThreadArray t(Worker1, Worker2, Worker3, Worker4);
3872  t.Start();
3873  t.Join();
3874}
3875REGISTER_TEST(Run, 79)
3876}  // namespace test79
3877
3878
3879// AtomicRefCountedClass. {{{1
3880// Same as RefCountedClass, but using atomic ops instead of mutex.
3881struct AtomicRefCountedClass {
3882 public:
3883  AtomicRefCountedClass() {
3884    annotate_unref_ = false;
3885    ref_ = 0;
3886    data_ = 0;
3887  }
3888
3889  ~AtomicRefCountedClass() {
3890    CHECK(ref_ == 0);     // race may be reported here
3891    int data_val = data_; // and here
3892    data_ = 0;
3893    ref_ = -1;
3894    printf("\tRefCountedClass::data_ = %d\n", data_val);
3895  }
3896
3897  void AccessData() {
3898    this->mu_.Lock();
3899    this->data_++;
3900    this->mu_.Unlock();
3901  }
3902
3903  void Ref() {
3904    AtomicIncrement(&ref_, 1);
3905  }
3906
3907  void Unref() {
3908    // DISCLAIMER: I am not sure I've implemented this correctly
3909    // (might require some memory barrier, etc).
3910    // But this implementation of reference counting is enough for
3911    // the purpose of Helgrind demonstration.
3912    AtomicIncrement(&ref_, -1);
3913    if (annotate_unref_) { ANNOTATE_CONDVAR_SIGNAL(this); }
3914    if (ref_ == 0) {
3915      if (annotate_unref_) { ANNOTATE_CONDVAR_WAIT(this); }
3916      delete this;
3917    }
3918  }
3919
3920  void AnnotateUnref() {
3921    annotate_unref_ = true;
3922  }
3923  void Annotate_Race() {
3924    ANNOTATE_BENIGN_RACE(&this->data_, "needs annotation");
3925  }
3926 private:
3927  bool annotate_unref_;
3928
3929  Mutex mu_;
3930  int data_; // under mu_
3931
3932  int ref_;  // used in atomic ops.
3933};
3934
3935// test80: FP. Ref counting with atomics, no annotations. {{{1
3936namespace test80 {
3937#ifndef NO_BARRIER
3938int     GLOB = 0;
3939Barrier barrier(4);
3940AtomicRefCountedClass *object = NULL;
3941void Worker() {
3942  object->Ref();
3943  barrier.Block();
3944  object->AccessData();
3945  object->Unref(); // All the tricky stuff is here.
3946}
3947void Run() {
3948  printf("test80: false positive (ref counting)\n");
3949  object = new AtomicRefCountedClass;
3950  object->Annotate_Race();
3951  MyThreadArray t(Worker, Worker, Worker, Worker);
3952  t.Start();
3953  t.Join();
3954}
3955REGISTER_TEST2(Run, 80, FEATURE|EXCLUDE_FROM_ALL)
3956#endif // NO_BARRIER
3957}  // namespace test80
3958
3959
3960// test81: TN. Ref counting with atomics, Unref is annotated. {{{1
3961namespace test81 {
3962#ifndef NO_BARRIER
3963// same as test80, but Unref is annotated.
3964int     GLOB = 0;
3965Barrier barrier(4);
3966AtomicRefCountedClass *object = NULL;
3967void Worker() {
3968  object->Ref();
3969  barrier.Block();
3970  object->AccessData();
3971  object->Unref(); // All the tricky stuff is here.
3972}
3973void Run() {
3974  printf("test81: negative (annotated ref counting)\n");
3975  object = new AtomicRefCountedClass;
3976  object->AnnotateUnref();
3977  MyThreadArray t(Worker, Worker, Worker, Worker);
3978  t.Start();
3979  t.Join();
3980}
3981REGISTER_TEST2(Run, 81, FEATURE|EXCLUDE_FROM_ALL)
3982#endif // NO_BARRIER
3983}  // namespace test81
3984
3985
3986// test82: Object published w/o synchronization. {{{1
3987namespace test82 {
3988
3989// Writer creates a new object and makes the pointer visible to the Reader.
3990// Reader waits until the object pointer is non-null and reads the object.
3991//
3992// On Core 2 Duo this test will sometimes (quite rarely) fail in
3993// the CHECK below, at least if compiled with -O2.
3994//
3995// The sequence of events::
3996// Thread1:                  Thread2:
3997//   a. arr_[...] = ...
3998//   b. foo[i]    = ...
3999//                           A. ... = foo[i]; // non NULL
4000//                           B. ... = arr_[...];
4001//
4002//  Since there is no proper synchronization, during the even (B)
4003//  Thread2 may not see the result of the event (a).
4004//  On x86 and x86_64 this happens due to compiler reordering instructions.
4005//  On other arcitectures it may also happen due to cashe inconsistency.
4006
4007class FOO {
4008 public:
4009  FOO() {
4010    idx_ = rand() % 1024;
4011    arr_[idx_] = 77777;
4012  //   __asm__ __volatile__("" : : : "memory"); // this fixes!
4013  }
4014  static void check(volatile FOO *foo) {
4015    CHECK(foo->arr_[foo->idx_] == 77777);
4016  }
4017 private:
4018  int idx_;
4019  int arr_[1024];
4020};
4021
4022const int N = 100000;
4023static volatile FOO *foo[N];
4024Mutex   MU;
4025
4026void Writer() {
4027  for (int i = 0; i < N; i++) {
4028    foo[i] = new FOO;
4029    usleep(100);
4030  }
4031}
4032
4033void Reader() {
4034  for (int i = 0; i < N; i++) {
4035    while (!foo[i]) {
4036      MU.Lock();   // this is NOT a synchronization,
4037      MU.Unlock(); // it just helps foo[i] to become visible in Reader.
4038    }
4039    if ((i % 100) == 0) {
4040      printf("rd %d\n", i);
4041    }
4042    // At this point Reader() sees the new value of foo[i]
4043    // but in very rare cases will not see the new value of foo[i]->arr_.
4044    // Thus this CHECK will sometimes fail.
4045    FOO::check(foo[i]);
4046  }
4047}
4048
4049void Run() {
4050  printf("test82: positive\n");
4051  MyThreadArray t(Writer, Reader);
4052  t.Start();
4053  t.Join();
4054}
4055REGISTER_TEST2(Run, 82, FEATURE|EXCLUDE_FROM_ALL)
4056}  // namespace test82
4057
4058
4059// test83: Object published w/o synchronization (simple version){{{1
4060namespace test83 {
4061// A simplified version of test83 (example of a wrong code).
4062// This test, though incorrect, will almost never fail.
4063volatile static int *ptr = NULL;
4064Mutex   MU;
4065
4066void Writer() {
4067  usleep(100);
4068  ptr = new int(777);
4069}
4070
4071void Reader() {
4072  while(!ptr) {
4073    MU.Lock(); // Not a synchronization!
4074    MU.Unlock();
4075  }
4076  CHECK(*ptr == 777);
4077}
4078
4079void Run() {
4080//  printf("test83: positive\n");
4081  MyThreadArray t(Writer, Reader);
4082  t.Start();
4083  t.Join();
4084}
4085REGISTER_TEST2(Run, 83, FEATURE|EXCLUDE_FROM_ALL)
4086}  // namespace test83
4087
4088
4089// test84: TP. True race (regression test for a bug related to atomics){{{1
4090namespace test84 {
4091// Helgrind should not create HB arcs for the bus lock even when
4092// --pure-happens-before=yes is used.
4093// Bug found in by Bart Van Assche, the test is taken from
4094// valgrind file drd/tests/atomic_var.c.
4095static int s_x = 0;
4096/* s_dummy[] ensures that s_x and s_y are not in the same cache line. */
4097static char s_dummy[512] = {0};
4098static int s_y;
4099
4100void thread_func_1()
4101{
4102  s_y = 1;
4103  AtomicIncrement(&s_x, 1);
4104}
4105
4106void thread_func_2()
4107{
4108  while (AtomicIncrement(&s_x, 0) == 0)
4109    ;
4110  printf("y = %d\n", s_y);
4111}
4112
4113
4114void Run() {
4115  CHECK(s_dummy[0] == 0);  // Avoid compiler warning about 's_dummy unused'.
4116  printf("test84: positive\n");
4117  FAST_MODE_INIT(&s_y);
4118  ANNOTATE_EXPECT_RACE_FOR_TSAN(&s_y, "test84: TP. true race.");
4119  MyThreadArray t(thread_func_1, thread_func_2);
4120  t.Start();
4121  t.Join();
4122}
4123REGISTER_TEST(Run, 84)
4124}  // namespace test84
4125
4126
4127// test85: Test for RunningOnValgrind(). {{{1
4128namespace  test85 {
4129int     GLOB = 0;
4130void Run() {
4131  printf("test85: RunningOnValgrind() = %d\n", RunningOnValgrind());
4132}
4133REGISTER_TEST(Run, 85)
4134}  // namespace test85
4135
4136
4137// test86: Test for race inside DTOR: racey write to vptr. Benign. {{{1
4138namespace test86 {
4139// This test shows a racey access to vptr (the pointer to vtbl).
4140// We have class A and class B derived from A.
4141// Both classes have a virtual function f() and a virtual DTOR.
4142// We create an object 'A *a = new B'
4143// and pass this object from Thread1 to Thread2.
4144// Thread2 calls a->f(). This call reads a->vtpr.
4145// Thread1 deletes the object. B::~B waits untill the object can be destroyed
4146// (flag_stopped == true) but at the very beginning of B::~B
4147// a->vptr is written to.
4148// So, we have a race on a->vptr.
4149// On this particular test this race is benign, but test87 shows
4150// how such race could harm.
4151//
4152//
4153//
4154// Threa1:                                            Thread2:
4155// 1. A a* = new B;
4156// 2. Q.Put(a); ------------\                         .
4157//                           \-------------------->   a. a = Q.Get();
4158//                                                    b. a->f();
4159//                                       /---------   c. flag_stopped = true;
4160// 3. delete a;                         /
4161//    waits untill flag_stopped <------/
4162//    inside the dtor
4163//
4164
4165bool flag_stopped = false;
4166Mutex mu;
4167
4168ProducerConsumerQueue Q(INT_MAX);  // Used to pass A* between threads.
4169
4170struct A {
4171  A()  { printf("A::A()\n"); }
4172  virtual ~A() { printf("A::~A()\n"); }
4173  virtual void f() { }
4174
4175  uintptr_t padding[15];
4176} __attribute__ ((aligned (64)));
4177
4178struct B: A {
4179  B()  { printf("B::B()\n"); }
4180  virtual ~B() {
4181    // The race is here.    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4182    printf("B::~B()\n");
4183    // wait until flag_stopped is true.
4184    mu.LockWhen(Condition(&ArgIsTrue, &flag_stopped));
4185    mu.Unlock();
4186    printf("B::~B() done\n");
4187  }
4188  virtual void f() { }
4189};
4190
4191void Waiter() {
4192  A *a = new B;
4193  if (!Tsan_FastMode())
4194    ANNOTATE_EXPECT_RACE(a, "test86: expected race on a->vptr");
4195  printf("Waiter: B created\n");
4196  Q.Put(a);
4197  usleep(100000); // so that Worker calls a->f() first.
4198  printf("Waiter: deleting B\n");
4199  delete a;
4200  printf("Waiter: B deleted\n");
4201  usleep(100000);
4202  printf("Waiter: done\n");
4203}
4204
4205void Worker() {
4206  A *a = reinterpret_cast<A*>(Q.Get());
4207  printf("Worker: got A\n");
4208  a->f();
4209
4210  mu.Lock();
4211  flag_stopped = true;
4212  mu.Unlock();
4213  usleep(200000);
4214  printf("Worker: done\n");
4215}
4216
4217void Run() {
4218  printf("test86: positive, race inside DTOR\n");
4219  MyThreadArray t(Waiter, Worker);
4220  t.Start();
4221  t.Join();
4222}
4223REGISTER_TEST(Run, 86)
4224}  // namespace test86
4225
4226
4227// test87: Test for race inside DTOR: racey write to vptr. Harmful.{{{1
4228namespace test87 {
4229// A variation of test86 where the race is harmful.
4230// Here we have class C derived from B.
4231// We create an object 'A *a = new C' in Thread1 and pass it to Thread2.
4232// Thread2 calls a->f().
4233// Thread1 calls 'delete a'.
4234// It first calls C::~C, then B::~B where it rewrites the vptr to point
4235// to B::vtbl. This is a problem because Thread2 might not have called a->f()
4236// and now it will call B::f instead of C::f.
4237//
4238bool flag_stopped = false;
4239Mutex mu;
4240
4241ProducerConsumerQueue Q(INT_MAX);  // Used to pass A* between threads.
4242
4243struct A {
4244  A()  { printf("A::A()\n"); }
4245  virtual ~A() { printf("A::~A()\n"); }
4246  virtual void f() = 0; // pure virtual.
4247};
4248
4249struct B: A {
4250  B()  { printf("B::B()\n"); }
4251  virtual ~B() {
4252    // The race is here.    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4253    printf("B::~B()\n");
4254    // wait until flag_stopped is true.
4255    mu.LockWhen(Condition(&ArgIsTrue, &flag_stopped));
4256    mu.Unlock();
4257    printf("B::~B() done\n");
4258  }
4259  virtual void f() = 0; // pure virtual.
4260};
4261
4262struct C: B {
4263  C()  { printf("C::C()\n"); }
4264  virtual ~C() { printf("C::~C()\n"); }
4265  virtual void f() { }
4266};
4267
4268void Waiter() {
4269  A *a = new C;
4270  Q.Put(a);
4271  delete a;
4272}
4273
4274void Worker() {
4275  A *a = reinterpret_cast<A*>(Q.Get());
4276  a->f();
4277
4278  mu.Lock();
4279  flag_stopped = true;
4280  ANNOTATE_CONDVAR_SIGNAL(&mu);
4281  mu.Unlock();
4282}
4283
4284void Run() {
4285  printf("test87: positive, race inside DTOR\n");
4286  MyThreadArray t(Waiter, Worker);
4287  t.Start();
4288  t.Join();
4289}
4290REGISTER_TEST2(Run, 87, FEATURE|EXCLUDE_FROM_ALL)
4291}  // namespace test87
4292
4293
4294// test88: Test for ANNOTATE_IGNORE_WRITES_*{{{1
4295namespace test88 {
4296// a recey write annotated with ANNOTATE_IGNORE_WRITES_BEGIN/END.
4297int     GLOB = 0;
4298void Worker() {
4299  ANNOTATE_IGNORE_WRITES_BEGIN();
4300  GLOB = 1;
4301  ANNOTATE_IGNORE_WRITES_END();
4302}
4303void Run() {
4304  printf("test88: negative, test for ANNOTATE_IGNORE_WRITES_*\n");
4305  MyThread t(Worker);
4306  t.Start();
4307  GLOB = 1;
4308  t.Join();
4309  printf("\tGLOB=%d\n", GLOB);
4310}
4311REGISTER_TEST(Run, 88)
4312}  // namespace test88
4313
4314
4315// test89: Test for debug info. {{{1
4316namespace test89 {
4317// Simlpe races with different objects (stack, heap globals; scalars, structs).
4318// Also, if run with --trace-level=2 this test will show a sequence of
4319// CTOR and DTOR calls.
4320struct STRUCT {
4321  int a, b, c;
4322};
4323
4324struct A {
4325  int a;
4326  A() {
4327    ANNOTATE_TRACE_MEMORY(&a);
4328    a = 1;
4329  }
4330  virtual ~A() {
4331    a = 4;
4332  }
4333};
4334
4335struct B : A {
4336  B()  { CHECK(a == 1); }
4337  virtual ~B() { CHECK(a == 3); }
4338};
4339struct C : B {
4340  C()  { a = 2; }
4341  virtual ~C() { a = 3; }
4342};
4343
4344int            GLOBAL = 0;
4345int           *STACK  = 0;
4346STRUCT         GLOB_STRUCT;
4347STRUCT        *STACK_STRUCT;
4348STRUCT        *HEAP_STRUCT;
4349
4350void Worker() {
4351  GLOBAL = 1;
4352  *STACK = 1;
4353  GLOB_STRUCT.b   = 1;
4354  STACK_STRUCT->b = 1;
4355  HEAP_STRUCT->b  = 1;
4356}
4357
4358void Run() {
4359  int stack_var = 0;
4360  STACK = &stack_var;
4361
4362  STRUCT stack_struct;
4363  STACK_STRUCT = &stack_struct;
4364
4365  HEAP_STRUCT = new STRUCT;
4366
4367  printf("test89: negative\n");
4368  MyThreadArray t(Worker, Worker);
4369  t.Start();
4370  t.Join();
4371
4372  delete HEAP_STRUCT;
4373
4374  A *a = new C;
4375  printf("Using 'a->a':  %d\n", a->a);
4376  delete a;
4377}
4378REGISTER_TEST2(Run, 89, FEATURE|EXCLUDE_FROM_ALL)
4379}  // namespace test89
4380
4381
4382// test90: FP. Test for a safely-published pointer (read-only). {{{1
4383namespace test90 {
4384// The Publisher creates an object and safely publishes it under a mutex.
4385// Readers access the object read-only.
4386// See also test91.
4387//
4388// Without annotations Helgrind will issue a false positive in Reader().
4389//
4390// Choices for annotations:
4391//   -- ANNOTATE_CONDVAR_SIGNAL/ANNOTATE_CONDVAR_WAIT
4392//   -- ANNOTATE_MUTEX_IS_USED_AS_CONDVAR
4393//   -- ANNOTATE_PUBLISH_MEMORY_RANGE.
4394
4395int     *GLOB = 0;
4396Mutex   MU;
4397
4398void Publisher() {
4399  MU.Lock();
4400  GLOB = (int*)memalign(64, sizeof(int));
4401  *GLOB = 777;
4402  if (!Tsan_PureHappensBefore() && !Tsan_FastMode())
4403    ANNOTATE_EXPECT_RACE_FOR_TSAN(GLOB, "test90. FP. This is a false positve");
4404  MU.Unlock();
4405  usleep(200000);
4406}
4407
4408void Reader() {
4409  usleep(10000);
4410  while (true) {
4411    MU.Lock();
4412    int *p = GLOB;
4413    MU.Unlock();
4414    if (p) {
4415      CHECK(*p == 777);  // Race is reported here.
4416      break;
4417    }
4418  }
4419}
4420
4421void Run() {
4422  printf("test90: false positive (safely published pointer).\n");
4423  MyThreadArray t(Publisher, Reader, Reader, Reader);
4424  t.Start();
4425  t.Join();
4426  printf("\t*GLOB=%d\n", *GLOB);
4427  free(GLOB);
4428}
4429REGISTER_TEST(Run, 90)
4430}  // namespace test90
4431
4432
4433// test91: FP. Test for a safely-published pointer (read-write). {{{1
4434namespace test91 {
4435// Similar to test90.
4436// The Publisher creates an object and safely publishes it under a mutex MU1.
4437// Accessors get the object under MU1 and access it (read/write) under MU2.
4438//
4439// Without annotations Helgrind will issue a false positive in Accessor().
4440//
4441
4442int     *GLOB = 0;
4443Mutex   MU, MU1, MU2;
4444
4445void Publisher() {
4446  MU1.Lock();
4447  GLOB = (int*)memalign(64, sizeof(int));
4448  *GLOB = 777;
4449  if (!Tsan_PureHappensBefore() && !Tsan_FastMode())
4450    ANNOTATE_EXPECT_RACE_FOR_TSAN(GLOB, "test91. FP. This is a false positve");
4451  MU1.Unlock();
4452}
4453
4454void Accessor() {
4455  usleep(10000);
4456  while (true) {
4457    MU1.Lock();
4458    int *p = GLOB;
4459    MU1.Unlock();
4460    if (p) {
4461      MU2.Lock();
4462      (*p)++;  // Race is reported here.
4463      CHECK(*p >  777);
4464      MU2.Unlock();
4465      break;
4466    }
4467  }
4468}
4469
4470void Run() {
4471  printf("test91: false positive (safely published pointer, read/write).\n");
4472  MyThreadArray t(Publisher, Accessor, Accessor, Accessor);
4473  t.Start();
4474  t.Join();
4475  printf("\t*GLOB=%d\n", *GLOB);
4476  free(GLOB);
4477}
4478REGISTER_TEST(Run, 91)
4479}  // namespace test91
4480
4481
4482// test92: TN. Test for a safely-published pointer (read-write), annotated. {{{1
4483namespace test92 {
4484// Similar to test91, but annotated with ANNOTATE_PUBLISH_MEMORY_RANGE.
4485//
4486//
4487// Publisher:                                       Accessors:
4488//
4489// 1. MU1.Lock()
4490// 2. Create GLOB.
4491// 3. ANNOTATE_PUBLISH_...(GLOB) -------\            .
4492// 4. MU1.Unlock()                       \           .
4493//                                        \          a. MU1.Lock()
4494//                                         \         b. Get GLOB
4495//                                          \        c. MU1.Unlock()
4496//                                           \-->    d. Access GLOB
4497//
4498//  A happens-before arc is created between ANNOTATE_PUBLISH_MEMORY_RANGE and
4499//  accesses to GLOB.
4500
4501struct ObjType {
4502  int arr[10];
4503};
4504
4505ObjType *GLOB = 0;
4506Mutex   MU, MU1, MU2;
4507
4508void Publisher() {
4509  MU1.Lock();
4510  GLOB = new ObjType;
4511  for (int i = 0; i < 10; i++) {
4512    GLOB->arr[i] = 777;
4513  }
4514  // This annotation should go right before the object is published.
4515  ANNOTATE_PUBLISH_MEMORY_RANGE(GLOB, sizeof(*GLOB));
4516  MU1.Unlock();
4517}
4518
4519void Accessor(int index) {
4520  while (true) {
4521    MU1.Lock();
4522    ObjType *p = GLOB;
4523    MU1.Unlock();
4524    if (p) {
4525      MU2.Lock();
4526      p->arr[index]++;  // W/o the annotations the race will be reported here.
4527      CHECK(p->arr[index] ==  778);
4528      MU2.Unlock();
4529      break;
4530    }
4531  }
4532}
4533
4534void Accessor0() { Accessor(0); }
4535void Accessor5() { Accessor(5); }
4536void Accessor9() { Accessor(9); }
4537
4538void Run() {
4539  printf("test92: safely published pointer, read/write, annotated.\n");
4540  MyThreadArray t(Publisher, Accessor0, Accessor5, Accessor9);
4541  t.Start();
4542  t.Join();
4543  printf("\t*GLOB=%d\n", GLOB->arr[0]);
4544}
4545REGISTER_TEST(Run, 92)
4546}  // namespace test92
4547
4548
4549// test93: TP. Test for incorrect usage of ANNOTATE_PUBLISH_MEMORY_RANGE. {{{1
4550namespace test93 {
4551int     GLOB = 0;
4552
4553void Reader() {
4554  CHECK(GLOB == 0);
4555}
4556
4557void Publisher() {
4558  usleep(10000);
4559  // Incorrect, used after the memory has been accessed in another thread.
4560  ANNOTATE_PUBLISH_MEMORY_RANGE(&GLOB, sizeof(GLOB));
4561}
4562
4563void Run() {
4564  printf("test93: positive, misuse of ANNOTATE_PUBLISH_MEMORY_RANGE\n");
4565  MyThreadArray t(Reader, Publisher);
4566  t.Start();
4567  t.Join();
4568  printf("\tGLOB=%d\n", GLOB);
4569}
4570REGISTER_TEST2(Run, 93, FEATURE|EXCLUDE_FROM_ALL)
4571}  // namespace test93
4572
4573
4574// test94: TP. Check do_cv_signal/fake segment logic {{{1
4575namespace test94 {
4576int     GLOB;
4577
4578int COND  = 0;
4579int COND2 = 0;
4580Mutex MU, MU2;
4581CondVar CV, CV2;
4582
4583void Thr1() {
4584  usleep(10000);  // Make sure the waiter blocks.
4585
4586  GLOB = 1; // WRITE
4587
4588  MU.Lock();
4589  COND = 1;
4590  CV.Signal();
4591  MU.Unlock();
4592}
4593void Thr2() {
4594  usleep(1000*1000); // Make sure CV2.Signal() "happens after" CV.Signal()
4595  usleep(10000);  // Make sure the waiter blocks.
4596
4597  MU2.Lock();
4598  COND2 = 1;
4599  CV2.Signal();
4600  MU2.Unlock();
4601}
4602void Thr3() {
4603  MU.Lock();
4604  while(COND != 1)
4605    CV.Wait(&MU);
4606  MU.Unlock();
4607}
4608void Thr4() {
4609  MU2.Lock();
4610  while(COND2 != 1)
4611    CV2.Wait(&MU2);
4612  MU2.Unlock();
4613  GLOB = 2; // READ: no HB-relation between CV.Signal and CV2.Wait !
4614}
4615void Run() {
4616  FAST_MODE_INIT(&GLOB);
4617  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test94: TP.");
4618  printf("test94: TP. Check do_cv_signal/fake segment logic\n");
4619  MyThreadArray mta(Thr1, Thr2, Thr3, Thr4);
4620  mta.Start();
4621  mta.Join();
4622  printf("\tGLOB=%d\n", GLOB);
4623}
4624REGISTER_TEST(Run, 94);
4625}  // namespace test94
4626
4627// test95: TP. Check do_cv_signal/fake segment logic {{{1
4628namespace test95 {
4629int     GLOB = 0;
4630
4631int COND  = 0;
4632int COND2 = 0;
4633Mutex MU, MU2;
4634CondVar CV, CV2;
4635
4636void Thr1() {
4637  usleep(1000*1000); // Make sure CV2.Signal() "happens before" CV.Signal()
4638  usleep(10000);  // Make sure the waiter blocks.
4639
4640  GLOB = 1; // WRITE
4641
4642  MU.Lock();
4643  COND = 1;
4644  CV.Signal();
4645  MU.Unlock();
4646}
4647void Thr2() {
4648  usleep(10000);  // Make sure the waiter blocks.
4649
4650  MU2.Lock();
4651  COND2 = 1;
4652  CV2.Signal();
4653  MU2.Unlock();
4654}
4655void Thr3() {
4656  MU.Lock();
4657  while(COND != 1)
4658    CV.Wait(&MU);
4659  MU.Unlock();
4660}
4661void Thr4() {
4662  MU2.Lock();
4663  while(COND2 != 1)
4664    CV2.Wait(&MU2);
4665  MU2.Unlock();
4666  GLOB = 2; // READ: no HB-relation between CV.Signal and CV2.Wait !
4667}
4668void Run() {
4669  FAST_MODE_INIT(&GLOB);
4670  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test95: TP.");
4671  printf("test95: TP. Check do_cv_signal/fake segment logic\n");
4672  MyThreadArray mta(Thr1, Thr2, Thr3, Thr4);
4673  mta.Start();
4674  mta.Join();
4675  printf("\tGLOB=%d\n", GLOB);
4676}
4677REGISTER_TEST(Run, 95);
4678}  // namespace test95
4679
4680// test96: TN. tricky LockSet behaviour {{{1
4681// 3 threads access the same memory with three different
4682// locksets: {A, B}, {B, C}, {C, A}.
4683// These locksets have empty intersection
4684namespace test96 {
4685int     GLOB = 0;
4686
4687Mutex A, B, C;
4688
4689void Thread1() {
4690  MutexLock a(&A);
4691  MutexLock b(&B);
4692  GLOB++;
4693}
4694
4695void Thread2() {
4696  MutexLock b(&B);
4697  MutexLock c(&C);
4698  GLOB++;
4699}
4700
4701void Thread3() {
4702  MutexLock a(&A);
4703  MutexLock c(&C);
4704  GLOB++;
4705}
4706
4707void Run() {
4708  printf("test96: FP. tricky LockSet behaviour\n");
4709  ANNOTATE_TRACE_MEMORY(&GLOB);
4710  MyThreadArray mta(Thread1, Thread2, Thread3);
4711  mta.Start();
4712  mta.Join();
4713  CHECK(GLOB == 3);
4714  printf("\tGLOB=%d\n", GLOB);
4715}
4716REGISTER_TEST(Run, 96);
4717}  // namespace test96
4718
4719// test97: This test shows false negative with --fast-mode=yes {{{1
4720namespace test97 {
4721const int HG_CACHELINE_SIZE = 64;
4722
4723Mutex MU;
4724
4725const int ARRAY_SIZE = HG_CACHELINE_SIZE * 4 / sizeof(int);
4726int array[ARRAY_SIZE];
4727int * GLOB = &array[ARRAY_SIZE/2];
4728/*
4729  We use sizeof(array) == 4 * HG_CACHELINE_SIZE to be sure that GLOB points
4730  to a memory inside a CacheLineZ which is inside array's memory range
4731 */
4732
4733void Reader() {
4734  usleep(500000);
4735  CHECK(777 == *GLOB);
4736}
4737
4738void Run() {
4739  MyThreadArray t(Reader);
4740  if (!Tsan_FastMode())
4741    ANNOTATE_EXPECT_RACE_FOR_TSAN(GLOB, "test97: TP. FN with --fast-mode=yes");
4742  printf("test97: This test shows false negative with --fast-mode=yes\n");
4743
4744  t.Start();
4745  *GLOB = 777;
4746  t.Join();
4747}
4748
4749REGISTER_TEST2(Run, 97, FEATURE)
4750}  // namespace test97
4751
4752// test98: Synchronization via read/write (or send/recv). {{{1
4753namespace test98 {
4754// The synchronization here is done by a pair of read/write calls
4755// that create a happens-before arc. Same may be done with send/recv.
4756// Such synchronization is quite unusual in real programs
4757// (why would one synchronizae via a file or socket?), but
4758// quite possible in unittests where one threads runs for producer
4759// and one for consumer.
4760//
4761// A race detector has to create a happens-before arcs for
4762// {read,send}->{write,recv} even if the file descriptors are different.
4763//
4764int     GLOB = 0;
4765int fd_out = -1;
4766int fd_in  = -1;
4767
4768void Writer() {
4769  usleep(1000);
4770  GLOB = 1;
4771  const char *str = "Hey there!\n";
4772  IGNORE_RETURN_VALUE(write(fd_out, str, strlen(str) + 1));
4773}
4774
4775void Reader() {
4776  char buff[100];
4777  while (read(fd_in, buff, 100) == 0)
4778    sleep(1);
4779  printf("read: %s\n", buff);
4780  GLOB = 2;
4781}
4782
4783void Run() {
4784  printf("test98: negative, synchronization via I/O\n");
4785  char in_name[100];
4786  char out_name[100];
4787  // we open two files, on for reading and one for writing,
4788  // but the files are actually the same (symlinked).
4789  sprintf(out_name, "/tmp/racecheck_unittest_out.%d", getpid());
4790  fd_out = creat(out_name, O_WRONLY | S_IRWXU);
4791#ifdef VGO_darwin
4792  // symlink() is not supported on Darwin. Copy the output file name.
4793  strcpy(in_name, out_name);
4794#else
4795  sprintf(in_name,  "/tmp/racecheck_unittest_in.%d", getpid());
4796  IGNORE_RETURN_VALUE(symlink(out_name, in_name));
4797#endif
4798  fd_in  = open(in_name, 0, O_RDONLY);
4799  CHECK(fd_out >= 0);
4800  CHECK(fd_in  >= 0);
4801  MyThreadArray t(Writer, Reader);
4802  t.Start();
4803  t.Join();
4804  printf("\tGLOB=%d\n", GLOB);
4805  // cleanup
4806  close(fd_in);
4807  close(fd_out);
4808  unlink(in_name);
4809  unlink(out_name);
4810}
4811REGISTER_TEST(Run, 98)
4812}  // namespace test98
4813
4814
4815// test99: TP. Unit test for a bug in LockWhen*. {{{1
4816namespace test99 {
4817
4818
4819bool GLOB = false;
4820Mutex mu;
4821
4822static void Thread1() {
4823  for (int i = 0; i < 100; i++) {
4824    mu.LockWhenWithTimeout(Condition(&ArgIsTrue, &GLOB), 5);
4825    GLOB = false;
4826    mu.Unlock();
4827    usleep(10000);
4828  }
4829}
4830
4831static void Thread2() {
4832  for (int i = 0; i < 100; i++) {
4833    mu.Lock();
4834    mu.Unlock();
4835    usleep(10000);
4836  }
4837}
4838
4839void Run() {
4840  printf("test99: regression test for LockWhen*\n");
4841  MyThreadArray t(Thread1, Thread2);
4842  t.Start();
4843  t.Join();
4844}
4845REGISTER_TEST(Run, 99);
4846}  // namespace test99
4847
4848
4849// test100: Test for initialization bit. {{{1
4850namespace test100 {
4851int     G1 = 0;
4852int     G2 = 0;
4853int     G3 = 0;
4854int     G4 = 0;
4855
4856void Creator() {
4857  G1 = 1; CHECK(G1);
4858  G2 = 1;
4859  G3 = 1; CHECK(G3);
4860  G4 = 1;
4861}
4862
4863void Worker1() {
4864  usleep(100000);
4865  CHECK(G1);
4866  CHECK(G2);
4867  G3 = 3;
4868  G4 = 3;
4869}
4870
4871void Worker2() {
4872
4873}
4874
4875
4876void Run() {
4877  printf("test100: test for initialization bit. \n");
4878  MyThreadArray t(Creator, Worker1, Worker2);
4879  ANNOTATE_TRACE_MEMORY(&G1);
4880  ANNOTATE_TRACE_MEMORY(&G2);
4881  ANNOTATE_TRACE_MEMORY(&G3);
4882  ANNOTATE_TRACE_MEMORY(&G4);
4883  t.Start();
4884  t.Join();
4885}
4886REGISTER_TEST2(Run, 100, FEATURE|EXCLUDE_FROM_ALL)
4887}  // namespace test100
4888
4889
4890// test101: TN. Two signals and two waits. {{{1
4891namespace test101 {
4892Mutex MU;
4893CondVar CV;
4894int     GLOB = 0;
4895
4896int C1 = 0, C2 = 0;
4897
4898void Signaller() {
4899  usleep(100000);
4900  MU.Lock();
4901  C1 = 1;
4902  CV.Signal();
4903  printf("signal\n");
4904  MU.Unlock();
4905
4906  GLOB = 1;
4907
4908  usleep(500000);
4909  MU.Lock();
4910  C2 = 1;
4911  CV.Signal();
4912  printf("signal\n");
4913  MU.Unlock();
4914}
4915
4916void Waiter() {
4917  MU.Lock();
4918  while(!C1)
4919    CV.Wait(&MU);
4920  printf("wait\n");
4921  MU.Unlock();
4922
4923  MU.Lock();
4924  while(!C2)
4925    CV.Wait(&MU);
4926  printf("wait\n");
4927  MU.Unlock();
4928
4929  GLOB = 2;
4930
4931}
4932
4933void Run() {
4934  printf("test101: negative\n");
4935  MyThreadArray t(Waiter, Signaller);
4936  t.Start();
4937  t.Join();
4938  printf("\tGLOB=%d\n", GLOB);
4939}
4940REGISTER_TEST(Run, 101)
4941}  // namespace test101
4942
4943// test102: --fast-mode=yes vs. --initialization-bit=yes {{{1
4944namespace test102 {
4945const int HG_CACHELINE_SIZE = 64;
4946
4947Mutex MU;
4948
4949const int ARRAY_SIZE = HG_CACHELINE_SIZE * 4 / sizeof(int);
4950int array[ARRAY_SIZE + 1];
4951int * GLOB = &array[ARRAY_SIZE/2];
4952/*
4953  We use sizeof(array) == 4 * HG_CACHELINE_SIZE to be sure that GLOB points
4954  to a memory inside a CacheLineZ which is inside array's memory range
4955*/
4956
4957void Reader() {
4958  usleep(200000);
4959  CHECK(777 == GLOB[0]);
4960  usleep(400000);
4961  CHECK(777 == GLOB[1]);
4962}
4963
4964void Run() {
4965  MyThreadArray t(Reader);
4966  if (!Tsan_FastMode())
4967    ANNOTATE_EXPECT_RACE_FOR_TSAN(GLOB+0, "test102: TP. FN with --fast-mode=yes");
4968  ANNOTATE_EXPECT_RACE_FOR_TSAN(GLOB+1, "test102: TP");
4969  printf("test102: --fast-mode=yes vs. --initialization-bit=yes\n");
4970
4971  t.Start();
4972  GLOB[0] = 777;
4973  usleep(400000);
4974  GLOB[1] = 777;
4975  t.Join();
4976}
4977
4978REGISTER_TEST2(Run, 102, FEATURE)
4979}  // namespace test102
4980
4981// test103: Access different memory locations with different LockSets {{{1
4982namespace test103 {
4983const int N_MUTEXES = 6;
4984const int LOCKSET_INTERSECTION_SIZE = 3;
4985
4986int data[1 << LOCKSET_INTERSECTION_SIZE] = {0};
4987Mutex MU[N_MUTEXES];
4988
4989inline int LS_to_idx (int ls) {
4990  return (ls >> (N_MUTEXES - LOCKSET_INTERSECTION_SIZE))
4991      & ((1 << LOCKSET_INTERSECTION_SIZE) - 1);
4992}
4993
4994void Worker() {
4995  for (int ls = 0; ls < (1 << N_MUTEXES); ls++) {
4996    if (LS_to_idx(ls) == 0)
4997      continue;
4998    for (int m = 0; m < N_MUTEXES; m++)
4999      if (ls & (1 << m))
5000        MU[m].Lock();
5001
5002    data[LS_to_idx(ls)]++;
5003
5004    for (int m = N_MUTEXES - 1; m >= 0; m--)
5005      if (ls & (1 << m))
5006        MU[m].Unlock();
5007  }
5008}
5009
5010void Run() {
5011  printf("test103: Access different memory locations with different LockSets\n");
5012  MyThreadArray t(Worker, Worker, Worker, Worker);
5013  t.Start();
5014  t.Join();
5015}
5016REGISTER_TEST2(Run, 103, FEATURE)
5017}  // namespace test103
5018
5019// test104: TP. Simple race (write vs write). Heap mem. {{{1
5020namespace test104 {
5021int     *GLOB = NULL;
5022void Worker() {
5023  *GLOB = 1;
5024}
5025
5026void Parent() {
5027  MyThread t(Worker);
5028  t.Start();
5029  usleep(100000);
5030  *GLOB = 2;
5031  t.Join();
5032}
5033void Run() {
5034  GLOB = (int*)memalign(64, sizeof(int));
5035  *GLOB = 0;
5036  ANNOTATE_EXPECT_RACE(GLOB, "test104. TP.");
5037  ANNOTATE_TRACE_MEMORY(GLOB);
5038  printf("test104: positive\n");
5039  Parent();
5040  printf("\tGLOB=%d\n", *GLOB);
5041  free(GLOB);
5042}
5043REGISTER_TEST(Run, 104);
5044}  // namespace test104
5045
5046
5047// test105: Checks how stack grows. {{{1
5048namespace test105 {
5049int     GLOB = 0;
5050
5051void F1() {
5052  int ar[32] __attribute__((unused));
5053//  ANNOTATE_TRACE_MEMORY(&ar[0]);
5054//  ANNOTATE_TRACE_MEMORY(&ar[31]);
5055  ar[0] = 1;
5056  ar[31] = 1;
5057}
5058
5059void Worker() {
5060  int ar[32] __attribute__((unused));
5061//  ANNOTATE_TRACE_MEMORY(&ar[0]);
5062//  ANNOTATE_TRACE_MEMORY(&ar[31]);
5063  ar[0] = 1;
5064  ar[31] = 1;
5065  F1();
5066}
5067
5068void Run() {
5069  printf("test105: negative\n");
5070  Worker();
5071  MyThread t(Worker);
5072  t.Start();
5073  t.Join();
5074  printf("\tGLOB=%d\n", GLOB);
5075}
5076REGISTER_TEST(Run, 105)
5077}  // namespace test105
5078
5079
5080// test106: TN. pthread_once. {{{1
5081namespace test106 {
5082int     *GLOB = NULL;
5083static pthread_once_t once = PTHREAD_ONCE_INIT;
5084void Init() {
5085  GLOB = new int;
5086  ANNOTATE_TRACE_MEMORY(GLOB);
5087  *GLOB = 777;
5088}
5089
5090void Worker0() {
5091  pthread_once(&once, Init);
5092}
5093void Worker1() {
5094  usleep(100000);
5095  pthread_once(&once, Init);
5096  CHECK(*GLOB == 777);
5097}
5098
5099
5100void Run() {
5101  printf("test106: negative\n");
5102  MyThreadArray t(Worker0, Worker1, Worker1, Worker1);
5103  t.Start();
5104  t.Join();
5105  printf("\tGLOB=%d\n", *GLOB);
5106}
5107REGISTER_TEST2(Run, 106, FEATURE)
5108}  // namespace test106
5109
5110
5111// test107: Test for ANNOTATE_EXPECT_RACE {{{1
5112namespace test107 {
5113int     GLOB = 0;
5114void Run() {
5115  printf("test107: negative\n");
5116  ANNOTATE_EXPECT_RACE(&GLOB, "No race in fact. Just checking the tool.");
5117  printf("\tGLOB=%d\n", GLOB);
5118}
5119REGISTER_TEST2(Run, 107, FEATURE|EXCLUDE_FROM_ALL)
5120}  // namespace test107
5121
5122
5123// test108: TN. initialization of static object. {{{1
5124namespace test108 {
5125// Here we have a function-level static object.
5126// Starting from gcc 4 this is therad safe,
5127// but is is not thread safe with many other compilers.
5128//
5129// Helgrind supports this kind of initialization by
5130// intercepting __cxa_guard_acquire/__cxa_guard_release
5131// and ignoring all accesses between them.
5132// Helgrind also intercepts pthread_once in the same manner.
5133class Foo {
5134 public:
5135  Foo() {
5136    ANNOTATE_TRACE_MEMORY(&a_);
5137    a_ = 42;
5138  }
5139  void Check() const { CHECK(a_ == 42); }
5140 private:
5141  int a_;
5142};
5143
5144const Foo *GetFoo() {
5145  static const Foo *foo = new Foo();
5146  return foo;
5147}
5148void Worker0() {
5149  GetFoo();
5150}
5151
5152void Worker() {
5153  usleep(200000);
5154  const Foo *foo = GetFoo();
5155  foo->Check();
5156}
5157
5158
5159void Run() {
5160  printf("test108: negative, initialization of static object\n");
5161  MyThreadArray t(Worker0, Worker, Worker);
5162  t.Start();
5163  t.Join();
5164}
5165REGISTER_TEST2(Run, 108, FEATURE)
5166}  // namespace test108
5167
5168
5169// test109: TN. Checking happens before between parent and child threads. {{{1
5170namespace test109 {
5171// Check that the detector correctly connects
5172//   pthread_create with the new thread
5173// and
5174//   thread exit with pthread_join
5175const int N = 32;
5176static int GLOB[N];
5177
5178void Worker(void *a) {
5179  usleep(10000);
5180//  printf("--Worker : %ld %p\n", (int*)a - GLOB, (void*)pthread_self());
5181  int *arg = (int*)a;
5182  (*arg)++;
5183}
5184
5185void Run() {
5186  printf("test109: negative\n");
5187  MyThread *t[N];
5188  for (int i  = 0; i < N; i++) {
5189    t[i] = new MyThread(Worker, &GLOB[i]);
5190  }
5191  for (int i  = 0; i < N; i++) {
5192    ANNOTATE_TRACE_MEMORY(&GLOB[i]);
5193    GLOB[i] = 1;
5194    t[i]->Start();
5195//    printf("--Started: %p\n", (void*)t[i]->tid());
5196  }
5197  for (int i  = 0; i < N; i++) {
5198//    printf("--Joining: %p\n", (void*)t[i]->tid());
5199    t[i]->Join();
5200//    printf("--Joined : %p\n", (void*)t[i]->tid());
5201    GLOB[i]++;
5202  }
5203  for (int i  = 0; i < N; i++) delete t[i];
5204
5205  printf("\tGLOB=%d\n", GLOB[13]);
5206}
5207REGISTER_TEST(Run, 109)
5208}  // namespace test109
5209
5210
5211// test110: TP. Simple races with stack, global and heap objects. {{{1
5212namespace test110 {
5213int        GLOB = 0;
5214static int STATIC;
5215
5216int       *STACK = 0;
5217
5218int       *MALLOC;
5219int       *CALLOC;
5220int       *REALLOC;
5221int       *VALLOC;
5222int       *PVALLOC;
5223int       *MEMALIGN;
5224union pi_pv_union { int* pi; void* pv; } POSIX_MEMALIGN;
5225int       *MMAP;
5226
5227int       *NEW;
5228int       *NEW_ARR;
5229
5230void Worker() {
5231  GLOB++;
5232  STATIC++;
5233
5234  (*STACK)++;
5235
5236  (*MALLOC)++;
5237  (*CALLOC)++;
5238  (*REALLOC)++;
5239  (*VALLOC)++;
5240  (*PVALLOC)++;
5241  (*MEMALIGN)++;
5242  (*(POSIX_MEMALIGN.pi))++;
5243  (*MMAP)++;
5244
5245  (*NEW)++;
5246  (*NEW_ARR)++;
5247}
5248void Run() {
5249  int x = 0;
5250  STACK = &x;
5251
5252  MALLOC = (int*)malloc(sizeof(int));
5253  CALLOC = (int*)calloc(1, sizeof(int));
5254  REALLOC = (int*)realloc(NULL, sizeof(int));
5255  VALLOC = (int*)valloc(sizeof(int));
5256  PVALLOC = (int*)valloc(sizeof(int));  // TODO: pvalloc breaks helgrind.
5257  MEMALIGN = (int*)memalign(64, sizeof(int));
5258  CHECK(0 == posix_memalign(&POSIX_MEMALIGN.pv, 64, sizeof(int)));
5259  MMAP = (int*)mmap(NULL, sizeof(int), PROT_READ | PROT_WRITE,
5260                    MAP_PRIVATE | MAP_ANON, -1, 0);
5261
5262  NEW     = new int;
5263  NEW_ARR = new int[10];
5264
5265
5266  FAST_MODE_INIT(STACK);
5267  ANNOTATE_EXPECT_RACE(STACK, "real race on stack object");
5268  FAST_MODE_INIT(&GLOB);
5269  ANNOTATE_EXPECT_RACE(&GLOB, "real race on global object");
5270  FAST_MODE_INIT(&STATIC);
5271  ANNOTATE_EXPECT_RACE(&STATIC, "real race on a static global object");
5272  FAST_MODE_INIT(MALLOC);
5273  ANNOTATE_EXPECT_RACE(MALLOC, "real race on a malloc-ed object");
5274  FAST_MODE_INIT(CALLOC);
5275  ANNOTATE_EXPECT_RACE(CALLOC, "real race on a calloc-ed object");
5276  FAST_MODE_INIT(REALLOC);
5277  ANNOTATE_EXPECT_RACE(REALLOC, "real race on a realloc-ed object");
5278  FAST_MODE_INIT(VALLOC);
5279  ANNOTATE_EXPECT_RACE(VALLOC, "real race on a valloc-ed object");
5280  FAST_MODE_INIT(PVALLOC);
5281  ANNOTATE_EXPECT_RACE(PVALLOC, "real race on a pvalloc-ed object");
5282  FAST_MODE_INIT(MEMALIGN);
5283  ANNOTATE_EXPECT_RACE(MEMALIGN, "real race on a memalign-ed object");
5284  FAST_MODE_INIT(POSIX_MEMALIGN.pi);
5285  ANNOTATE_EXPECT_RACE(POSIX_MEMALIGN.pi, "real race on a posix_memalign-ed object");
5286  FAST_MODE_INIT(MMAP);
5287  ANNOTATE_EXPECT_RACE(MMAP, "real race on a mmap-ed object");
5288
5289  FAST_MODE_INIT(NEW);
5290  ANNOTATE_EXPECT_RACE(NEW, "real race on a new-ed object");
5291  FAST_MODE_INIT(NEW_ARR);
5292  ANNOTATE_EXPECT_RACE(NEW_ARR, "real race on a new[]-ed object");
5293
5294  MyThreadArray t(Worker, Worker, Worker);
5295  t.Start();
5296  t.Join();
5297  printf("test110: positive (race on a stack object)\n");
5298  printf("\tSTACK=%d\n", *STACK);
5299  CHECK(GLOB <= 3);
5300  CHECK(STATIC <= 3);
5301
5302  free(MALLOC);
5303  free(CALLOC);
5304  free(REALLOC);
5305  free(VALLOC);
5306  free(PVALLOC);
5307  free(MEMALIGN);
5308  free(POSIX_MEMALIGN.pv);
5309  munmap(MMAP, sizeof(int));
5310  delete NEW;
5311  delete [] NEW_ARR;
5312}
5313REGISTER_TEST(Run, 110)
5314}  // namespace test110
5315
5316
5317// test111: TN. Unit test for a bug related to stack handling. {{{1
5318namespace test111 {
5319char     *GLOB = 0;
5320bool COND = false;
5321Mutex mu;
5322const int N = 3000;
5323
5324void write_to_p(char *p, int val) {
5325  for (int i = 0; i < N; i++)
5326    p[i] = val;
5327}
5328
5329static bool ArgIsTrue(bool *arg) {
5330//  printf("ArgIsTrue: %d tid=%d\n", *arg, (int)pthread_self());
5331  return *arg == true;
5332}
5333
5334void f1() {
5335  char some_stack[N];
5336  write_to_p(some_stack, 1);
5337  mu.LockWhen(Condition(&ArgIsTrue, &COND));
5338  mu.Unlock();
5339}
5340
5341void f2() {
5342  char some_stack[N];
5343  char some_more_stack[N];
5344  write_to_p(some_stack, 2);
5345  write_to_p(some_more_stack, 2);
5346}
5347
5348void f0() { f2(); }
5349
5350void Worker1() {
5351  f0();
5352  f1();
5353  f2();
5354}
5355
5356void Worker2() {
5357  usleep(100000);
5358  mu.Lock();
5359  COND = true;
5360  mu.Unlock();
5361}
5362
5363void Run() {
5364  printf("test111: regression test\n");
5365  MyThreadArray t(Worker1, Worker1, Worker2);
5366//  AnnotateSetVerbosity(__FILE__, __LINE__, 3);
5367  t.Start();
5368  t.Join();
5369//  AnnotateSetVerbosity(__FILE__, __LINE__, 1);
5370}
5371REGISTER_TEST2(Run, 111, FEATURE)
5372}  // namespace test111
5373
5374// test112: STAB. Test for ANNOTATE_PUBLISH_MEMORY_RANGE{{{1
5375namespace test112 {
5376char     *GLOB = 0;
5377const int N = 64 * 5;
5378Mutex mu;
5379bool ready = false; // under mu
5380int beg, end; // under mu
5381
5382Mutex mu1;
5383
5384void Worker() {
5385
5386  bool is_ready = false;
5387  int b, e;
5388  while (!is_ready) {
5389    mu.Lock();
5390    is_ready = ready;
5391    b = beg;
5392    e = end;
5393    mu.Unlock();
5394    usleep(1000);
5395  }
5396
5397  mu1.Lock();
5398  for (int i = b; i < e; i++) {
5399    GLOB[i]++;
5400  }
5401  mu1.Unlock();
5402}
5403
5404void PublishRange(int b, int e) {
5405  MyThreadArray t(Worker, Worker);
5406  ready = false; // runs before other threads
5407  t.Start();
5408
5409  ANNOTATE_NEW_MEMORY(GLOB + b, e - b);
5410  ANNOTATE_TRACE_MEMORY(GLOB + b);
5411  for (int j = b; j < e; j++) {
5412    GLOB[j] = 0;
5413  }
5414  ANNOTATE_PUBLISH_MEMORY_RANGE(GLOB + b, e - b);
5415
5416  // hand off
5417  mu.Lock();
5418  ready = true;
5419  beg = b;
5420  end = e;
5421  mu.Unlock();
5422
5423  t.Join();
5424}
5425
5426void Run() {
5427  printf("test112: stability (ANNOTATE_PUBLISH_MEMORY_RANGE)\n");
5428  GLOB = new char [N];
5429
5430  PublishRange(0, 10);
5431  PublishRange(3, 5);
5432
5433  PublishRange(12, 13);
5434  PublishRange(10, 14);
5435
5436  PublishRange(15, 17);
5437  PublishRange(16, 18);
5438
5439  // do few more random publishes.
5440  for (int i = 0; i < 20; i++) {
5441    const int begin = rand() % N;
5442    const int size = (rand() % (N - begin)) + 1;
5443    CHECK(size > 0);
5444    CHECK(begin + size <= N);
5445    PublishRange(begin, begin + size);
5446  }
5447
5448  printf("GLOB = %d\n", (int)GLOB[0]);
5449}
5450REGISTER_TEST2(Run, 112, STABILITY)
5451}  // namespace test112
5452
5453
5454// test113: PERF. A lot of lock/unlock calls. Many locks {{{1
5455namespace    test113 {
5456const int kNumIter = 100000;
5457const int kNumLocks = 7;
5458Mutex   MU[kNumLocks];
5459void Run() {
5460  printf("test113: perf\n");
5461  for (int i = 0; i < kNumIter; i++ ) {
5462    for (int j = 0; j < kNumLocks; j++) {
5463      if (i & (1 << j)) MU[j].Lock();
5464    }
5465    for (int j = kNumLocks - 1; j >= 0; j--) {
5466      if (i & (1 << j)) MU[j].Unlock();
5467    }
5468  }
5469}
5470REGISTER_TEST(Run, 113)
5471}  // namespace test113
5472
5473
5474// test114: STAB. Recursive lock. {{{1
5475namespace    test114 {
5476int Bar() {
5477  static int bar = 1;
5478  return bar;
5479}
5480int Foo() {
5481  static int foo = Bar();
5482  return foo;
5483}
5484void Worker() {
5485  static int x = Foo();
5486  CHECK(x == 1);
5487}
5488void Run() {
5489  printf("test114: stab\n");
5490  MyThreadArray t(Worker, Worker);
5491  t.Start();
5492  t.Join();
5493}
5494REGISTER_TEST(Run, 114)
5495}  // namespace test114
5496
5497
5498// test115: TN. sem_open. {{{1
5499namespace    test115 {
5500int tid = 0;
5501Mutex mu;
5502const char *kSemName = "drt-test-sem";
5503
5504int GLOB = 0;
5505
5506sem_t *DoSemOpen() {
5507  // TODO: there is some race report inside sem_open
5508  // for which suppressions do not work... (???)
5509  ANNOTATE_IGNORE_WRITES_BEGIN();
5510  sem_t *sem = sem_open(kSemName, O_CREAT, 0600, 3);
5511  ANNOTATE_IGNORE_WRITES_END();
5512  return sem;
5513}
5514
5515void Worker() {
5516  mu.Lock();
5517  int my_tid = tid++;
5518  mu.Unlock();
5519
5520  if (my_tid == 0) {
5521    GLOB = 1;
5522  }
5523
5524  // if the detector observes a happens-before arc between
5525  // sem_open and sem_wait, it will be silent.
5526  sem_t *sem = DoSemOpen();
5527  usleep(100000);
5528  CHECK(sem != SEM_FAILED);
5529  CHECK(sem_wait(sem) == 0);
5530
5531  if (my_tid > 0) {
5532    CHECK(GLOB == 1);
5533  }
5534}
5535
5536void Run() {
5537  printf("test115: stab (sem_open())\n");
5538
5539  // just check that sem_open is not completely broken
5540  sem_unlink(kSemName);
5541  sem_t* sem = DoSemOpen();
5542  CHECK(sem != SEM_FAILED);
5543  CHECK(sem_wait(sem) == 0);
5544  sem_unlink(kSemName);
5545
5546  // check that sem_open and sem_wait create a happens-before arc.
5547  MyThreadArray t(Worker, Worker, Worker);
5548  t.Start();
5549  t.Join();
5550  // clean up
5551  sem_unlink(kSemName);
5552}
5553REGISTER_TEST(Run, 115)
5554}  // namespace test115
5555
5556
5557// test116: TN. some operations with string<> objects. {{{1
5558namespace test116 {
5559
5560void Worker() {
5561  string A[10], B[10], C[10];
5562  for (int i = 0; i < 1000; i++) {
5563    for (int j = 0; j < 10; j++) {
5564      string &a = A[j];
5565      string &b = B[j];
5566      string &c = C[j];
5567      a = "sdl;fkjhasdflksj df";
5568      b = "sdf sdf;ljsd ";
5569      c = "'sfdf df";
5570      c = b;
5571      a = c;
5572      b = a;
5573      swap(a,b);
5574      swap(b,c);
5575    }
5576    for (int j = 0; j < 10; j++) {
5577      string &a = A[j];
5578      string &b = B[j];
5579      string &c = C[j];
5580      a.clear();
5581      b.clear();
5582      c.clear();
5583    }
5584  }
5585}
5586
5587void Run() {
5588  printf("test116: negative (strings)\n");
5589  MyThreadArray t(Worker, Worker, Worker);
5590  t.Start();
5591  t.Join();
5592}
5593REGISTER_TEST2(Run, 116, FEATURE|EXCLUDE_FROM_ALL)
5594}  // namespace test116
5595
5596// test117: TN. Many calls to function-scope static init. {{{1
5597namespace test117 {
5598const int N = 50;
5599
5600int Foo() {
5601  usleep(20000);
5602  return 1;
5603}
5604
5605void Worker(void *a) {
5606  static int foo = Foo();
5607  CHECK(foo == 1);
5608}
5609
5610void Run() {
5611  printf("test117: negative\n");
5612  MyThread *t[N];
5613  for (int i  = 0; i < N; i++) {
5614    t[i] = new MyThread(Worker);
5615  }
5616  for (int i  = 0; i < N; i++) {
5617    t[i]->Start();
5618  }
5619  for (int i  = 0; i < N; i++) {
5620    t[i]->Join();
5621  }
5622  for (int i  = 0; i < N; i++) delete t[i];
5623}
5624REGISTER_TEST(Run, 117)
5625}  // namespace test117
5626
5627
5628
5629// test118 PERF: One signal, multiple waits. {{{1
5630namespace   test118 {
5631int     GLOB = 0;
5632const int kNumIter = 2000000;
5633void Signaller() {
5634  usleep(50000);
5635  ANNOTATE_CONDVAR_SIGNAL(&GLOB);
5636}
5637void Waiter() {
5638  for (int i = 0; i < kNumIter; i++) {
5639    ANNOTATE_CONDVAR_WAIT(&GLOB);
5640    if (i == kNumIter / 2)
5641      usleep(100000);
5642  }
5643}
5644void Run() {
5645  printf("test118: perf\n");
5646  MyThreadArray t(Signaller, Waiter, Signaller, Waiter);
5647  t.Start();
5648  t.Join();
5649  printf("\tGLOB=%d\n", GLOB);
5650}
5651REGISTER_TEST(Run, 118)
5652}  // namespace test118
5653
5654
5655// test119: TP. Testing that malloc does not introduce any HB arc. {{{1
5656namespace test119 {
5657int     GLOB = 0;
5658void Worker1() {
5659  GLOB = 1;
5660  free(malloc(123));
5661}
5662void Worker2() {
5663  usleep(100000);
5664  free(malloc(345));
5665  GLOB = 2;
5666}
5667void Run() {
5668  printf("test119: positive (checking if malloc creates HB arcs)\n");
5669  FAST_MODE_INIT(&GLOB);
5670  if (!(Tsan_PureHappensBefore() && kMallocUsesMutex))
5671    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "true race");
5672  MyThreadArray t(Worker1, Worker2);
5673  t.Start();
5674  t.Join();
5675  printf("\tGLOB=%d\n", GLOB);
5676}
5677REGISTER_TEST(Run, 119)
5678}  // namespace test119
5679
5680
5681// test120: TP. Thread1: write then read. Thread2: read. {{{1
5682namespace test120 {
5683int     GLOB = 0;
5684
5685void Thread1() {
5686  GLOB = 1;           // write
5687  CHECK(GLOB);        // read
5688}
5689
5690void Thread2() {
5691  usleep(100000);
5692  CHECK(GLOB >= 0);   // read
5693}
5694
5695void Run() {
5696  FAST_MODE_INIT(&GLOB);
5697  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "TP (T1: write then read, T2: read)");
5698  printf("test120: positive\n");
5699  MyThreadArray t(Thread1, Thread2);
5700  GLOB = 1;
5701  t.Start();
5702  t.Join();
5703  printf("\tGLOB=%d\n", GLOB);
5704}
5705REGISTER_TEST(Run, 120)
5706}  // namespace test120
5707
5708
5709// test121: TP. Example of double-checked-locking  {{{1
5710namespace test121 {
5711struct Foo {
5712  uintptr_t a, b[15];
5713} __attribute__ ((aligned (64)));
5714
5715static Mutex mu;
5716static Foo  *foo;
5717
5718void InitMe() {
5719  if (!foo) {
5720    MutexLock lock(&mu);
5721    if (!foo) {
5722      ANNOTATE_EXPECT_RACE_FOR_TSAN(&foo, "test121. Double-checked locking (ptr)");
5723      foo = new Foo;
5724      if (!Tsan_FastMode())
5725        ANNOTATE_EXPECT_RACE_FOR_TSAN(&foo->a, "test121. Double-checked locking (obj)");
5726      foo->a = 42;
5727    }
5728  }
5729}
5730
5731void UseMe() {
5732  InitMe();
5733  CHECK(foo && foo->a == 42);
5734}
5735
5736void Worker1() { UseMe(); }
5737void Worker2() { UseMe(); }
5738void Worker3() { UseMe(); }
5739
5740
5741void Run() {
5742  FAST_MODE_INIT(&foo);
5743  printf("test121: TP. Example of double-checked-locking\n");
5744  MyThreadArray t1(Worker1, Worker2, Worker3);
5745  t1.Start();
5746  t1.Join();
5747  delete foo;
5748}
5749REGISTER_TEST(Run, 121)
5750}  // namespace test121
5751
5752// test122 TP: Simple test with RWLock {{{1
5753namespace  test122 {
5754int     VAR1 = 0;
5755int     VAR2 = 0;
5756RWLock mu;
5757
5758void WriteWhileHoldingReaderLock(int *p) {
5759  usleep(100000);
5760  ReaderLockScoped lock(&mu);  // Reader lock for writing. -- bug.
5761  (*p)++;
5762}
5763
5764void CorrectWrite(int *p) {
5765  WriterLockScoped lock(&mu);
5766  (*p)++;
5767}
5768
5769void Thread1() { WriteWhileHoldingReaderLock(&VAR1); }
5770void Thread2() { CorrectWrite(&VAR1); }
5771void Thread3() { CorrectWrite(&VAR2); }
5772void Thread4() { WriteWhileHoldingReaderLock(&VAR2); }
5773
5774
5775void Run() {
5776  printf("test122: positive (rw-lock)\n");
5777  VAR1 = 0;
5778  VAR2 = 0;
5779  ANNOTATE_TRACE_MEMORY(&VAR1);
5780  ANNOTATE_TRACE_MEMORY(&VAR2);
5781  if (!Tsan_PureHappensBefore()) {
5782    ANNOTATE_EXPECT_RACE_FOR_TSAN(&VAR1, "test122. TP. ReaderLock-ed while writing");
5783    ANNOTATE_EXPECT_RACE_FOR_TSAN(&VAR2, "test122. TP. ReaderLock-ed while writing");
5784  }
5785  MyThreadArray t(Thread1, Thread2, Thread3, Thread4);
5786  t.Start();
5787  t.Join();
5788}
5789REGISTER_TEST(Run, 122)
5790}  // namespace test122
5791
5792
5793// test123 TP: accesses of different sizes. {{{1
5794namespace test123 {
5795
5796union uint_union {
5797  uint64_t u64[1];
5798  uint32_t u32[2];
5799  uint16_t u16[4];
5800  uint8_t  u8[8];
5801};
5802
5803uint_union MEM[8];
5804
5805// Q. Hey dude, why so many functions?
5806// A. I need different stack traces for different accesses.
5807
5808void Wr64_0() { MEM[0].u64[0] = 1; }
5809void Wr64_1() { MEM[1].u64[0] = 1; }
5810void Wr64_2() { MEM[2].u64[0] = 1; }
5811void Wr64_3() { MEM[3].u64[0] = 1; }
5812void Wr64_4() { MEM[4].u64[0] = 1; }
5813void Wr64_5() { MEM[5].u64[0] = 1; }
5814void Wr64_6() { MEM[6].u64[0] = 1; }
5815void Wr64_7() { MEM[7].u64[0] = 1; }
5816
5817void Wr32_0() { MEM[0].u32[0] = 1; }
5818void Wr32_1() { MEM[1].u32[1] = 1; }
5819void Wr32_2() { MEM[2].u32[0] = 1; }
5820void Wr32_3() { MEM[3].u32[1] = 1; }
5821void Wr32_4() { MEM[4].u32[0] = 1; }
5822void Wr32_5() { MEM[5].u32[1] = 1; }
5823void Wr32_6() { MEM[6].u32[0] = 1; }
5824void Wr32_7() { MEM[7].u32[1] = 1; }
5825
5826void Wr16_0() { MEM[0].u16[0] = 1; }
5827void Wr16_1() { MEM[1].u16[1] = 1; }
5828void Wr16_2() { MEM[2].u16[2] = 1; }
5829void Wr16_3() { MEM[3].u16[3] = 1; }
5830void Wr16_4() { MEM[4].u16[0] = 1; }
5831void Wr16_5() { MEM[5].u16[1] = 1; }
5832void Wr16_6() { MEM[6].u16[2] = 1; }
5833void Wr16_7() { MEM[7].u16[3] = 1; }
5834
5835void Wr8_0() { MEM[0].u8[0] = 1; }
5836void Wr8_1() { MEM[1].u8[1] = 1; }
5837void Wr8_2() { MEM[2].u8[2] = 1; }
5838void Wr8_3() { MEM[3].u8[3] = 1; }
5839void Wr8_4() { MEM[4].u8[4] = 1; }
5840void Wr8_5() { MEM[5].u8[5] = 1; }
5841void Wr8_6() { MEM[6].u8[6] = 1; }
5842void Wr8_7() { MEM[7].u8[7] = 1; }
5843
5844void WriteAll64() {
5845  Wr64_0();
5846  Wr64_1();
5847  Wr64_2();
5848  Wr64_3();
5849  Wr64_4();
5850  Wr64_5();
5851  Wr64_6();
5852  Wr64_7();
5853}
5854
5855void WriteAll32() {
5856  Wr32_0();
5857  Wr32_1();
5858  Wr32_2();
5859  Wr32_3();
5860  Wr32_4();
5861  Wr32_5();
5862  Wr32_6();
5863  Wr32_7();
5864}
5865
5866void WriteAll16() {
5867  Wr16_0();
5868  Wr16_1();
5869  Wr16_2();
5870  Wr16_3();
5871  Wr16_4();
5872  Wr16_5();
5873  Wr16_6();
5874  Wr16_7();
5875}
5876
5877void WriteAll8() {
5878  Wr8_0();
5879  Wr8_1();
5880  Wr8_2();
5881  Wr8_3();
5882  Wr8_4();
5883  Wr8_5();
5884  Wr8_6();
5885  Wr8_7();
5886}
5887
5888void W00() { WriteAll64(); }
5889void W01() { WriteAll64(); }
5890void W02() { WriteAll64(); }
5891
5892void W10() { WriteAll32(); }
5893void W11() { WriteAll32(); }
5894void W12() { WriteAll32(); }
5895
5896void W20() { WriteAll16(); }
5897void W21() { WriteAll16(); }
5898void W22() { WriteAll16(); }
5899
5900void W30() { WriteAll8(); }
5901void W31() { WriteAll8(); }
5902void W32() { WriteAll8(); }
5903
5904typedef void (*F)(void);
5905
5906void TestTwoSizes(F f1, F f2) {
5907  // first f1, then f2
5908  ANNOTATE_NEW_MEMORY(&MEM, sizeof(MEM));
5909  memset(&MEM, 0, sizeof(MEM));
5910  MyThreadArray t1(f1, f2);
5911  t1.Start();
5912  t1.Join();
5913  // reverse order
5914  ANNOTATE_NEW_MEMORY(&MEM, sizeof(MEM));
5915  memset(&MEM, 0, sizeof(MEM));
5916  MyThreadArray t2(f2, f1);
5917  t2.Start();
5918  t2.Join();
5919}
5920
5921void Run() {
5922  printf("test123: positive (different sizes)\n");
5923  TestTwoSizes(W00, W10);
5924//  TestTwoSizes(W01, W20);
5925//  TestTwoSizes(W02, W30);
5926//  TestTwoSizes(W11, W21);
5927//  TestTwoSizes(W12, W31);
5928//  TestTwoSizes(W22, W32);
5929
5930}
5931REGISTER_TEST2(Run, 123, FEATURE|EXCLUDE_FROM_ALL)
5932}  // namespace test123
5933
5934
5935// test124: What happens if we delete an unlocked lock? {{{1
5936namespace test124 {
5937// This test does not worg with pthreads (you can't call
5938// pthread_mutex_destroy on a locked lock).
5939int     GLOB = 0;
5940const int N = 1000;
5941void Worker() {
5942  Mutex *a_large_local_array_of_mutexes;
5943  a_large_local_array_of_mutexes = new Mutex[N];
5944  for (int i = 0; i < N; i++) {
5945    a_large_local_array_of_mutexes[i].Lock();
5946  }
5947  delete []a_large_local_array_of_mutexes;
5948  GLOB = 1;
5949}
5950
5951void Run() {
5952  printf("test124: negative\n");
5953  MyThreadArray t(Worker, Worker, Worker);
5954  t.Start();
5955  t.Join();
5956  printf("\tGLOB=%d\n", GLOB);
5957}
5958REGISTER_TEST2(Run, 124, FEATURE|EXCLUDE_FROM_ALL)
5959}  // namespace test124
5960
5961
5962// test125 TN: Backwards lock (annotated). {{{1
5963namespace test125 {
5964// This test uses "Backwards mutex" locking protocol.
5965// We take a *reader* lock when writing to a per-thread data
5966// (GLOB[thread_num])  and we take a *writer* lock when we
5967// are reading from the entire array at once.
5968//
5969// Such locking protocol is not understood by ThreadSanitizer's
5970// hybrid state machine. So, you either have to use a pure-happens-before
5971// detector ("tsan --pure-happens-before") or apply pure happens-before mode
5972// to this particular lock by using ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&mu).
5973
5974const int n_threads = 3;
5975RWLock   mu;
5976int     GLOB[n_threads];
5977
5978int adder_num; // updated atomically.
5979
5980void Adder() {
5981  int my_num = AtomicIncrement(&adder_num, 1);
5982
5983  ReaderLockScoped lock(&mu);
5984  GLOB[my_num]++;
5985}
5986
5987void Aggregator() {
5988  int sum = 0;
5989  {
5990    WriterLockScoped lock(&mu);
5991    for (int i = 0; i < n_threads; i++) {
5992      sum += GLOB[i];
5993    }
5994  }
5995  printf("sum=%d\n", sum);
5996}
5997
5998void Run() {
5999  printf("test125: negative\n");
6000
6001  ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&mu);
6002
6003  // run Adders, then Aggregator
6004  {
6005    MyThreadArray t(Adder, Adder, Adder, Aggregator);
6006    t.Start();
6007    t.Join();
6008  }
6009
6010  // Run Aggregator first.
6011  adder_num = 0;
6012  {
6013    MyThreadArray t(Aggregator, Adder, Adder, Adder);
6014    t.Start();
6015    t.Join();
6016  }
6017
6018}
6019REGISTER_TEST(Run, 125)
6020}  // namespace test125
6021
6022// test126 TN: test for BlockingCounter {{{1
6023namespace  test126 {
6024BlockingCounter *blocking_counter;
6025int     GLOB = 0;
6026void Worker() {
6027  CHECK(blocking_counter);
6028  CHECK(GLOB == 0);
6029  blocking_counter->DecrementCount();
6030}
6031void Run() {
6032  printf("test126: negative\n");
6033  MyThreadArray t(Worker, Worker, Worker);
6034  blocking_counter = new BlockingCounter(3);
6035  t.Start();
6036  blocking_counter->Wait();
6037  GLOB = 1;
6038  t.Join();
6039  printf("\tGLOB=%d\n", GLOB);
6040}
6041REGISTER_TEST(Run, 126)
6042}  // namespace test126
6043
6044
6045// test127. Bad code: unlocking a mutex locked by another thread. {{{1
6046namespace test127 {
6047Mutex mu;
6048void Thread1() {
6049  mu.Lock();
6050}
6051void Thread2() {
6052  usleep(100000);
6053  mu.Unlock();
6054}
6055void Run() {
6056  printf("test127: unlocking a mutex locked by another thread.\n");
6057  MyThreadArray t(Thread1, Thread2);
6058  t.Start();
6059  t.Join();
6060}
6061REGISTER_TEST(Run, 127)
6062}  // namespace test127
6063
6064// test128. Suppressed code in concurrent accesses {{{1
6065// Please use --suppressions=unittest.supp flag when running this test.
6066namespace test128 {
6067Mutex mu;
6068int GLOB = 0;
6069void Worker() {
6070  usleep(100000);
6071  mu.Lock();
6072  GLOB++;
6073  mu.Unlock();
6074}
6075void ThisFunctionShouldBeSuppressed() {
6076  GLOB++;
6077}
6078void Run() {
6079  printf("test128: Suppressed code in concurrent accesses.\n");
6080  MyThreadArray t(Worker, ThisFunctionShouldBeSuppressed);
6081  t.Start();
6082  t.Join();
6083}
6084REGISTER_TEST2(Run, 128, FEATURE | EXCLUDE_FROM_ALL)
6085}  // namespace test128
6086
6087// test129: TN. Synchronization via ReaderLockWhen(). {{{1
6088namespace test129 {
6089int     GLOB = 0;
6090Mutex   MU;
6091bool WeirdCondition(int* param) {
6092  *param = GLOB;  // a write into Waiter's memory
6093  return GLOB > 0;
6094}
6095void Waiter() {
6096  int param = 0;
6097  MU.ReaderLockWhen(Condition(WeirdCondition, &param));
6098  MU.ReaderUnlock();
6099  CHECK(GLOB > 0);
6100  CHECK(param > 0);
6101}
6102void Waker() {
6103  usleep(100000);  // Make sure the waiter blocks.
6104  MU.Lock();
6105  GLOB++;
6106  MU.Unlock();     // calls ANNOTATE_CONDVAR_SIGNAL;
6107}
6108void Run() {
6109  printf("test129: Synchronization via ReaderLockWhen()\n");
6110  MyThread mt(Waiter, NULL, "Waiter Thread");
6111  mt.Start();
6112  Waker();
6113  mt.Join();
6114  printf("\tGLOB=%d\n", GLOB);
6115}
6116REGISTER_TEST2(Run, 129, FEATURE);
6117}  // namespace test129
6118
6119// test130: TN. Per-thread. {{{1
6120namespace test130 {
6121#ifndef NO_TLS
6122// This test verifies that the race detector handles
6123// thread-local storage (TLS) correctly.
6124// As of 09-03-30 ThreadSanitizer has a bug:
6125//   - Thread1 starts
6126//   - Thread1 touches per_thread_global
6127//   - Thread1 ends
6128//   - Thread2 starts (and there is no happens-before relation between it and
6129//   Thread1)
6130//   - Thread2 touches per_thread_global
6131// It may happen so that Thread2 will have per_thread_global in the same address
6132// as Thread1. Since there is no happens-before relation between threads,
6133// ThreadSanitizer reports a race.
6134//
6135// test131 does the same for stack.
6136
6137static __thread int per_thread_global[10] = {0};
6138
6139void RealWorker() {  // Touch per_thread_global.
6140  per_thread_global[1]++;
6141  errno++;
6142}
6143
6144void Worker() {  // Spawn few threads that touch per_thread_global.
6145  MyThreadArray t(RealWorker, RealWorker);
6146  t.Start();
6147  t.Join();
6148}
6149void Worker0() { sleep(0); Worker(); }
6150void Worker1() { sleep(1); Worker(); }
6151void Worker2() { sleep(2); Worker(); }
6152void Worker3() { sleep(3); Worker(); }
6153
6154void Run() {
6155  printf("test130: Per-thread\n");
6156  MyThreadArray t1(Worker0, Worker1, Worker2, Worker3);
6157  t1.Start();
6158  t1.Join();
6159  printf("\tper_thread_global=%d\n", per_thread_global[1]);
6160}
6161REGISTER_TEST(Run, 130)
6162#endif // NO_TLS
6163}  // namespace test130
6164
6165
6166// test131: TN. Stack. {{{1
6167namespace test131 {
6168// Same as test130, but for stack.
6169
6170void RealWorker() {  // Touch stack.
6171  int stack_var = 0;
6172  stack_var++;
6173}
6174
6175void Worker() {  // Spawn few threads that touch stack.
6176  MyThreadArray t(RealWorker, RealWorker);
6177  t.Start();
6178  t.Join();
6179}
6180void Worker0() { sleep(0); Worker(); }
6181void Worker1() { sleep(1); Worker(); }
6182void Worker2() { sleep(2); Worker(); }
6183void Worker3() { sleep(3); Worker(); }
6184
6185void Run() {
6186  printf("test131: stack\n");
6187  MyThreadArray t(Worker0, Worker1, Worker2, Worker3);
6188  t.Start();
6189  t.Join();
6190}
6191REGISTER_TEST(Run, 131)
6192}  // namespace test131
6193
6194
6195// test132: TP. Simple race (write vs write). Works in fast-mode. {{{1
6196namespace test132 {
6197int     GLOB = 0;
6198void Worker() { GLOB = 1; }
6199
6200void Run1() {
6201  FAST_MODE_INIT(&GLOB);
6202  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test132");
6203  printf("test132: positive; &GLOB=%p\n", &GLOB);
6204  ANNOTATE_TRACE_MEMORY(&GLOB);
6205  GLOB = 7;
6206  MyThreadArray t(Worker, Worker);
6207  t.Start();
6208  t.Join();
6209}
6210
6211void Run() {
6212  Run1();
6213}
6214REGISTER_TEST(Run, 132);
6215}  // namespace test132
6216
6217
6218// test133: TP. Simple race (write vs write). Works in fast mode. {{{1
6219namespace test133 {
6220// Same as test132, but everything is run from a separate thread spawned from
6221// the main thread.
6222int     GLOB = 0;
6223void Worker() { GLOB = 1; }
6224
6225void Run1() {
6226  FAST_MODE_INIT(&GLOB);
6227  ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "test133");
6228  printf("test133: positive; &GLOB=%p\n", &GLOB);
6229  ANNOTATE_TRACE_MEMORY(&GLOB);
6230  GLOB = 7;
6231  MyThreadArray t(Worker, Worker);
6232  t.Start();
6233  t.Join();
6234}
6235void Run() {
6236  MyThread t(Run1);
6237  t.Start();
6238  t.Join();
6239}
6240REGISTER_TEST(Run, 133);
6241}  // namespace test133
6242
6243
6244// test134 TN. Swap. Variant of test79. {{{1
6245namespace test134 {
6246#if 0
6247typedef __gnu_cxx::hash_map<int, int> map_t;
6248#else
6249typedef std::map<int, int> map_t;
6250#endif
6251map_t   map;
6252Mutex   mu;
6253// Here we use swap to pass map between threads.
6254// The synchronization is correct, but w/o the annotation
6255// any hybrid detector will complain.
6256
6257// Swap is very unfriendly to the lock-set (and hybrid) race detectors.
6258// Since tmp is destructed outside the mutex, we need to have a happens-before
6259// arc between any prior access to map and here.
6260// Since the internals of tmp are created ouside the mutex and are passed to
6261// other thread, we need to have a h-b arc between here and any future access.
6262// These arcs can be created by HAPPENS_{BEFORE,AFTER} annotations, but it is
6263// much simpler to apply pure-happens-before mode to the mutex mu.
6264void Swapper() {
6265  map_t tmp;
6266  MutexLock lock(&mu);
6267  ANNOTATE_HAPPENS_AFTER(&map);
6268  // We swap the new empty map 'tmp' with 'map'.
6269  map.swap(tmp);
6270  ANNOTATE_HAPPENS_BEFORE(&map);
6271  // tmp (which is the old version of map) is destroyed here.
6272}
6273
6274void Worker() {
6275  MutexLock lock(&mu);
6276  ANNOTATE_HAPPENS_AFTER(&map);
6277  map[1]++;
6278  ANNOTATE_HAPPENS_BEFORE(&map);
6279}
6280
6281void Run() {
6282  printf("test134: negative (swap)\n");
6283  // ********************** Shorter way: ***********************
6284  // ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&mu);
6285  MyThreadArray t(Worker, Worker, Swapper, Worker, Worker);
6286  t.Start();
6287  t.Join();
6288}
6289REGISTER_TEST(Run, 134)
6290}  // namespace test134
6291
6292// test135 TN. Swap. Variant of test79. {{{1
6293namespace test135 {
6294
6295void SubWorker() {
6296  const long SIZE = 65536;
6297  for (int i = 0; i < 32; i++) {
6298    int *ptr = (int*)mmap(NULL, SIZE, PROT_READ | PROT_WRITE,
6299                          MAP_PRIVATE | MAP_ANON, -1, 0);
6300    *ptr = 42;
6301    munmap(ptr, SIZE);
6302  }
6303}
6304
6305void Worker() {
6306  MyThreadArray t(SubWorker, SubWorker, SubWorker, SubWorker);
6307  t.Start();
6308  t.Join();
6309}
6310
6311void Run() {
6312  printf("test135: negative (mmap)\n");
6313  MyThreadArray t(Worker, Worker, Worker, Worker);
6314  t.Start();
6315  t.Join();
6316}
6317REGISTER_TEST(Run, 135)
6318}  // namespace test135
6319
6320// test136. Unlock twice. {{{1
6321namespace test136 {
6322void Run() {
6323  printf("test136: unlock twice\n");
6324  pthread_mutexattr_t attr;
6325  CHECK(0 == pthread_mutexattr_init(&attr));
6326  CHECK(0 == pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK));
6327
6328  pthread_mutex_t mu;
6329  CHECK(0 == pthread_mutex_init(&mu, &attr));
6330  CHECK(0 == pthread_mutex_lock(&mu));
6331  CHECK(0 == pthread_mutex_unlock(&mu));
6332  int ret_unlock = pthread_mutex_unlock(&mu);  // unlocking twice.
6333  int ret_destroy = pthread_mutex_destroy(&mu);
6334  printf("  pthread_mutex_unlock returned %d\n", ret_unlock);
6335  printf("  pthread_mutex_destroy returned %d\n", ret_destroy);
6336
6337}
6338
6339REGISTER_TEST(Run, 136)
6340}  // namespace test136
6341
6342// test137 TP. Races on stack variables. {{{1
6343namespace test137 {
6344int GLOB = 0;
6345ProducerConsumerQueue q(10);
6346
6347void Worker() {
6348  int stack;
6349  int *tmp = (int*)q.Get();
6350  (*tmp)++;
6351  int *racey = &stack;
6352  q.Put(racey);
6353  (*racey)++;
6354  usleep(150000);
6355  // We may miss the races if we sleep less due to die_memory events...
6356}
6357
6358void Run() {
6359  int tmp = 0;
6360  printf("test137: TP. Races on stack variables.\n");
6361  q.Put(&tmp);
6362  MyThreadArray t(Worker, Worker, Worker, Worker);
6363  t.Start();
6364  t.Join();
6365  q.Get();
6366}
6367
6368REGISTER_TEST2(Run, 137, FEATURE | EXCLUDE_FROM_ALL)
6369}  // namespace test137
6370
6371// test138 FN. Two closures hit the same thread in ThreadPool. {{{1
6372namespace test138 {
6373int GLOB = 0;
6374
6375void Worker() {
6376  usleep(100000);
6377  GLOB++;
6378}
6379
6380void Run() {
6381  FAST_MODE_INIT(&GLOB);
6382  printf("test138: FN. Two closures hit the same thread in ThreadPool.\n");
6383
6384  // When using thread pools, two concurrent callbacks might be scheduled
6385  // onto the same executor thread. As a result, unnecessary happens-before
6386  // relation may be introduced between callbacks.
6387  // If we set the number of executor threads to 1, any known data
6388  // race detector will be silent. However, the same situation may happen
6389  // with any number of executor threads (with some probability).
6390  ThreadPool tp(1);
6391  tp.StartWorkers();
6392  tp.Add(NewCallback(Worker));
6393  tp.Add(NewCallback(Worker));
6394}
6395
6396REGISTER_TEST2(Run, 138, FEATURE)
6397}  // namespace test138
6398
6399// test139: FN. A true race hidden by reference counting annotation. {{{1
6400namespace test139 {
6401int GLOB = 0;
6402RefCountedClass *obj;
6403
6404void Worker1() {
6405  GLOB++;  // First access.
6406  obj->Unref();
6407}
6408
6409void Worker2() {
6410  usleep(100000);
6411  obj->Unref();
6412  GLOB++;  // Second access.
6413}
6414
6415void Run() {
6416  FAST_MODE_INIT(&GLOB);
6417  printf("test139: FN. A true race hidden by reference counting annotation.\n");
6418
6419  obj = new RefCountedClass;
6420  obj->AnnotateUnref();
6421  obj->Ref();
6422  obj->Ref();
6423  MyThreadArray mt(Worker1, Worker2);
6424  mt.Start();
6425  mt.Join();
6426}
6427
6428REGISTER_TEST2(Run, 139, FEATURE)
6429}  // namespace test139
6430
6431// test140 TN. Swap. Variant of test79 and test134. {{{1
6432namespace test140 {
6433#if 0
6434typedef __gnu_cxx::hash_map<int, int> Container;
6435#else
6436typedef std::map<int,int>             Container;
6437#endif
6438Mutex mu;
6439static Container container;
6440
6441// Here we use swap to pass a Container between threads.
6442// The synchronization is correct, but w/o the annotation
6443// any hybrid detector will complain.
6444//
6445// Unlike the test134, we try to have a minimal set of annotations
6446// so that extra h-b arcs do not hide other races.
6447
6448// Swap is very unfriendly to the lock-set (and hybrid) race detectors.
6449// Since tmp is destructed outside the mutex, we need to have a happens-before
6450// arc between any prior access to map and here.
6451// Since the internals of tmp are created ouside the mutex and are passed to
6452// other thread, we need to have a h-b arc between here and any future access.
6453//
6454// We want to be able to annotate swapper so that we don't need to annotate
6455// anything else.
6456void Swapper() {
6457  Container tmp;
6458  tmp[1] = tmp[2] = tmp[3] = 0;
6459  {
6460    MutexLock lock(&mu);
6461    container.swap(tmp);
6462    // we are unpublishing the old container.
6463    ANNOTATE_UNPUBLISH_MEMORY_RANGE(&container, sizeof(container));
6464    // we are publishing the new container.
6465    ANNOTATE_PUBLISH_MEMORY_RANGE(&container, sizeof(container));
6466  }
6467  tmp[1]++;
6468  tmp[2]++;
6469  // tmp (which is the old version of container) is destroyed here.
6470}
6471
6472void Worker() {
6473  MutexLock lock(&mu);
6474  container[1]++;
6475  int *v = &container[2];
6476  for (int i = 0; i < 10; i++) {
6477    // if uncommented, this will break ANNOTATE_UNPUBLISH_MEMORY_RANGE():
6478    // ANNOTATE_HAPPENS_BEFORE(v);
6479    if (i % 3) {
6480      (*v)++;
6481    }
6482  }
6483}
6484
6485void Run() {
6486  printf("test140: negative (swap) %p\n", &container);
6487  MyThreadArray t(Worker, Worker, Swapper, Worker, Worker);
6488  t.Start();
6489  t.Join();
6490}
6491REGISTER_TEST(Run, 140)
6492}  // namespace test140
6493
6494// test141 FP. unlink/fopen, rmdir/opendir. {{{1
6495namespace test141 {
6496int GLOB1 = 0,
6497    GLOB2 = 0;
6498char *dir_name = NULL,
6499     *filename = NULL;
6500
6501void Waker1() {
6502  usleep(100000);
6503  GLOB1 = 1;  // Write
6504  // unlink deletes a file 'filename'
6505  // which exits spin-loop in Waiter1().
6506  printf("  Deleting file...\n");
6507  CHECK(unlink(filename) == 0);
6508}
6509
6510void Waiter1() {
6511  FILE *tmp;
6512  while ((tmp = fopen(filename, "r")) != NULL) {
6513    fclose(tmp);
6514    usleep(10000);
6515  }
6516  printf("  ...file has been deleted\n");
6517  GLOB1 = 2;  // Write
6518}
6519
6520void Waker2() {
6521  usleep(100000);
6522  GLOB2 = 1;  // Write
6523  // rmdir deletes a directory 'dir_name'
6524  // which exit spin-loop in Waker().
6525  printf("  Deleting directory...\n");
6526  CHECK(rmdir(dir_name) == 0);
6527}
6528
6529void Waiter2() {
6530  DIR *tmp;
6531  while ((tmp = opendir(dir_name)) != NULL) {
6532    closedir(tmp);
6533    usleep(10000);
6534  }
6535  printf("  ...directory has been deleted\n");
6536  GLOB2 = 2;
6537}
6538
6539void Run() {
6540  FAST_MODE_INIT(&GLOB1);
6541  FAST_MODE_INIT(&GLOB2);
6542  printf("test141: FP. unlink/fopen, rmdir/opendir.\n");
6543
6544  dir_name = strdup("/tmp/tsan-XXXXXX");
6545  IGNORE_RETURN_VALUE(mkdtemp(dir_name));
6546
6547  filename = strdup((std::string() + dir_name + "/XXXXXX").c_str());
6548  const int fd = mkstemp(filename);
6549  CHECK(fd >= 0);
6550  close(fd);
6551
6552  MyThreadArray mta1(Waker1, Waiter1);
6553  mta1.Start();
6554  mta1.Join();
6555
6556  MyThreadArray mta2(Waker2, Waiter2);
6557  mta2.Start();
6558  mta2.Join();
6559  free(filename);
6560  filename = 0;
6561  free(dir_name);
6562  dir_name = 0;
6563}
6564REGISTER_TEST(Run, 141)
6565}  // namespace test141
6566
6567
6568// Simple FIFO queue annotated with PCQ annotations. {{{1
6569class FifoMessageQueue {
6570 public:
6571  FifoMessageQueue() { ANNOTATE_PCQ_CREATE(this); }
6572  ~FifoMessageQueue() { ANNOTATE_PCQ_DESTROY(this); }
6573  // Send a message. 'message' should be positive.
6574  void Put(int message) {
6575    CHECK(message);
6576    MutexLock lock(&mu_);
6577    ANNOTATE_PCQ_PUT(this);
6578    q_.push(message);
6579  }
6580  // Return the message from the queue and pop it
6581  // or return 0 if there are no messages.
6582  int Get() {
6583    MutexLock lock(&mu_);
6584    if (q_.empty()) return 0;
6585    int res = q_.front();
6586    q_.pop();
6587    ANNOTATE_PCQ_GET(this);
6588    return res;
6589  }
6590 private:
6591  Mutex mu_;
6592  queue<int> q_;
6593};
6594
6595
6596// test142: TN. Check PCQ_* annotations. {{{1
6597namespace test142 {
6598// Putter writes to array[i] and sends a message 'i'.
6599// Getters receive messages and read array[message].
6600// PCQ_* annotations calm down the hybrid detectors.
6601
6602const int N = 1000;
6603int array[N+1];
6604
6605FifoMessageQueue q;
6606
6607void Putter() {
6608  for (int i = 1; i <= N; i++) {
6609    array[i] = i*i;
6610    q.Put(i);
6611    usleep(1000);
6612  }
6613}
6614
6615void Getter() {
6616  int non_zero_received  = 0;
6617  for (int i = 1; i <= N; i++) {
6618    int res = q.Get();
6619    if (res > 0) {
6620      CHECK(array[res] = res * res);
6621      non_zero_received++;
6622    }
6623    usleep(1000);
6624  }
6625  printf("T=%zd: non_zero_received=%d\n",
6626         (size_t)pthread_self(), non_zero_received);
6627}
6628
6629void Run() {
6630  printf("test142: tests PCQ annotations\n");
6631  MyThreadArray t(Putter, Getter, Getter);
6632  t.Start();
6633  t.Join();
6634}
6635REGISTER_TEST(Run, 142)
6636}  // namespace test142
6637
6638
6639// test143: TP. Check PCQ_* annotations. {{{1
6640namespace test143 {
6641// True positive.
6642// We have a race on GLOB between Putter and one of the Getters.
6643// Pure h-b will not see it.
6644// If FifoMessageQueue was annotated using HAPPENS_BEFORE/AFTER, the race would
6645// be missed too.
6646// PCQ_* annotations do not hide this race.
6647int     GLOB = 0;
6648
6649FifoMessageQueue q;
6650
6651void Putter() {
6652  GLOB = 1;
6653  q.Put(1);
6654}
6655
6656void Getter() {
6657  usleep(10000);
6658  q.Get();
6659  CHECK(GLOB == 1);  // Race here
6660}
6661
6662void Run() {
6663  q.Put(1);
6664  if (!Tsan_PureHappensBefore()) {
6665    ANNOTATE_EXPECT_RACE_FOR_TSAN(&GLOB, "true races");
6666  }
6667  printf("test143: tests PCQ annotations (true positive)\n");
6668  MyThreadArray t(Putter, Getter, Getter);
6669  t.Start();
6670  t.Join();
6671}
6672REGISTER_TEST(Run, 143);
6673}  // namespace test143
6674
6675
6676
6677
6678// test300: {{{1
6679namespace test300 {
6680int     GLOB = 0;
6681void Run() {
6682}
6683REGISTER_TEST2(Run, 300, RACE_DEMO)
6684}  // namespace test300
6685
6686// test301: Simple race.  {{{1
6687namespace test301 {
6688Mutex mu1;  // This Mutex guards var.
6689Mutex mu2;  // This Mutex is not related to var.
6690int   var;  // GUARDED_BY(mu1)
6691
6692void Thread1() {  // Runs in thread named 'test-thread-1'.
6693  MutexLock lock(&mu1);  // Correct Mutex.
6694  var = 1;
6695}
6696
6697void Thread2() {  // Runs in thread named 'test-thread-2'.
6698  MutexLock lock(&mu2);  // Wrong Mutex.
6699  var = 2;
6700}
6701
6702void Run() {
6703  var = 0;
6704  printf("test301: simple race.\n");
6705  MyThread t1(Thread1, NULL, "test-thread-1");
6706  MyThread t2(Thread2, NULL, "test-thread-2");
6707  t1.Start();
6708  t2.Start();
6709  t1.Join();
6710  t2.Join();
6711}
6712REGISTER_TEST2(Run, 301, RACE_DEMO)
6713}  // namespace test301
6714
6715// test302: Complex race which happens at least twice.  {{{1
6716namespace test302 {
6717// In this test we have many different accesses to GLOB and only one access
6718// is not synchronized properly.
6719int     GLOB = 0;
6720
6721Mutex MU1;
6722Mutex MU2;
6723void Worker() {
6724  for(int i = 0; i < 100; i++) {
6725    switch(i % 4) {
6726      case 0:
6727        // This read is protected correctly.
6728        MU1.Lock(); CHECK(GLOB >= 0); MU1.Unlock();
6729        break;
6730      case 1:
6731        // Here we used the wrong lock! The reason of the race is here.
6732        MU2.Lock(); CHECK(GLOB >= 0); MU2.Unlock();
6733        break;
6734      case 2:
6735        // This read is protected correctly.
6736        MU1.Lock(); CHECK(GLOB >= 0); MU1.Unlock();
6737        break;
6738      case 3:
6739        // This write is protected correctly.
6740        MU1.Lock(); GLOB++; MU1.Unlock();
6741        break;
6742    }
6743    // sleep a bit so that the threads interleave
6744    // and the race happens at least twice.
6745    usleep(100);
6746  }
6747}
6748
6749void Run() {
6750  printf("test302: Complex race that happens twice.\n");
6751  MyThread t1(Worker), t2(Worker);
6752  t1.Start();
6753  t2.Start();
6754  t1.Join();   t2.Join();
6755}
6756REGISTER_TEST2(Run, 302, RACE_DEMO)
6757}  // namespace test302
6758
6759
6760// test303: Need to trace the memory to understand the report. {{{1
6761namespace test303 {
6762int     GLOB = 0;
6763
6764Mutex MU;
6765void Worker1() { CHECK(GLOB >= 0); }
6766void Worker2() { MU.Lock(); GLOB=1;  MU.Unlock();}
6767
6768void Run() {
6769  printf("test303: a race that needs annotations.\n");
6770  ANNOTATE_TRACE_MEMORY(&GLOB);
6771  MyThreadArray t(Worker1, Worker2);
6772  t.Start();
6773  t.Join();
6774}
6775REGISTER_TEST2(Run, 303, RACE_DEMO)
6776}  // namespace test303
6777
6778
6779
6780// test304: Can not trace the memory, since it is a library object. {{{1
6781namespace test304 {
6782string *STR;
6783Mutex   MU;
6784
6785void Worker1() {
6786  sleep(0);
6787  ANNOTATE_CONDVAR_SIGNAL((void*)0xDEADBEAF);
6788  MU.Lock(); CHECK(STR->length() >= 4); MU.Unlock();
6789}
6790void Worker2() {
6791  sleep(1);
6792  ANNOTATE_CONDVAR_SIGNAL((void*)0xDEADBEAF);
6793  CHECK(STR->length() >= 4); // Unprotected!
6794}
6795void Worker3() {
6796  sleep(2);
6797  ANNOTATE_CONDVAR_SIGNAL((void*)0xDEADBEAF);
6798  MU.Lock(); CHECK(STR->length() >= 4); MU.Unlock();
6799}
6800void Worker4() {
6801  sleep(3);
6802  ANNOTATE_CONDVAR_SIGNAL((void*)0xDEADBEAF);
6803  MU.Lock(); *STR += " + a very very long string"; MU.Unlock();
6804}
6805
6806void Run() {
6807  STR = new string ("The String");
6808  printf("test304: a race where memory tracing does not work.\n");
6809  MyThreadArray t(Worker1, Worker2, Worker3, Worker4);
6810  t.Start();
6811  t.Join();
6812
6813  printf("%s\n", STR->c_str());
6814  delete STR;
6815}
6816REGISTER_TEST2(Run, 304, RACE_DEMO)
6817}  // namespace test304
6818
6819
6820
6821// test305: A bit more tricky: two locks used inconsistenly. {{{1
6822namespace test305 {
6823int     GLOB = 0;
6824
6825// In this test GLOB is protected by MU1 and MU2, but inconsistently.
6826// The TRACES observed by helgrind are:
6827// TRACE[1]: Access{T2/S2 wr} -> new State{Mod; #LS=2; #SS=1; T2/S2}
6828// TRACE[2]: Access{T4/S9 wr} -> new State{Mod; #LS=1; #SS=2; T2/S2, T4/S9}
6829// TRACE[3]: Access{T5/S13 wr} -> new State{Mod; #LS=1; #SS=3; T2/S2, T4/S9, T5/S13}
6830// TRACE[4]: Access{T6/S19 wr} -> new State{Mod; #LS=0; #SS=4; T2/S2, T4/S9, T5/S13, T6/S19}
6831//
6832// The guilty access is either Worker2() or Worker4(), depending on
6833// which mutex is supposed to protect GLOB.
6834Mutex MU1;
6835Mutex MU2;
6836void Worker1() { MU1.Lock(); MU2.Lock(); GLOB=1; MU2.Unlock(); MU1.Unlock(); }
6837void Worker2() { MU1.Lock();             GLOB=2;               MU1.Unlock(); }
6838void Worker3() { MU1.Lock(); MU2.Lock(); GLOB=3; MU2.Unlock(); MU1.Unlock(); }
6839void Worker4() {             MU2.Lock(); GLOB=4; MU2.Unlock();               }
6840
6841void Run() {
6842  ANNOTATE_TRACE_MEMORY(&GLOB);
6843  printf("test305: simple race.\n");
6844  MyThread t1(Worker1), t2(Worker2), t3(Worker3), t4(Worker4);
6845  t1.Start(); usleep(100);
6846  t2.Start(); usleep(100);
6847  t3.Start(); usleep(100);
6848  t4.Start(); usleep(100);
6849  t1.Join(); t2.Join(); t3.Join(); t4.Join();
6850}
6851REGISTER_TEST2(Run, 305, RACE_DEMO)
6852}  // namespace test305
6853
6854// test306: Two locks are used to protect a var.  {{{1
6855namespace test306 {
6856int     GLOB = 0;
6857// Thread1 and Thread2 access the var under two locks.
6858// Thread3 uses no locks.
6859
6860Mutex MU1;
6861Mutex MU2;
6862void Worker1() { MU1.Lock(); MU2.Lock(); GLOB=1; MU2.Unlock(); MU1.Unlock(); }
6863void Worker2() { MU1.Lock(); MU2.Lock(); GLOB=3; MU2.Unlock(); MU1.Unlock(); }
6864void Worker3() {                         GLOB=4;               }
6865
6866void Run() {
6867  ANNOTATE_TRACE_MEMORY(&GLOB);
6868  printf("test306: simple race.\n");
6869  MyThread t1(Worker1), t2(Worker2), t3(Worker3);
6870  t1.Start(); usleep(100);
6871  t2.Start(); usleep(100);
6872  t3.Start(); usleep(100);
6873  t1.Join(); t2.Join(); t3.Join();
6874}
6875REGISTER_TEST2(Run, 306, RACE_DEMO)
6876}  // namespace test306
6877
6878// test307: Simple race, code with control flow  {{{1
6879namespace test307 {
6880int     *GLOB = 0;
6881volatile /*to fake the compiler*/ bool some_condition = true;
6882
6883
6884void SomeFunc() { }
6885
6886int FunctionWithControlFlow() {
6887  int unrelated_stuff = 0;
6888  unrelated_stuff++;
6889  SomeFunc();                // "--keep-history=1" will point somewhere here.
6890  if (some_condition) {      // Or here
6891    if (some_condition) {
6892      unrelated_stuff++;     // Or here.
6893      unrelated_stuff++;
6894      (*GLOB)++;             // "--keep-history=2" will point here (experimental).
6895    }
6896  }
6897  usleep(100000);
6898  return unrelated_stuff;
6899}
6900
6901void Worker1() { FunctionWithControlFlow(); }
6902void Worker2() { Worker1(); }
6903void Worker3() { Worker2(); }
6904void Worker4() { Worker3(); }
6905
6906void Run() {
6907  GLOB = new int;
6908  *GLOB = 1;
6909  printf("test307: simple race, code with control flow\n");
6910  MyThreadArray t1(Worker1, Worker2, Worker3, Worker4);
6911  t1.Start();
6912  t1.Join();
6913}
6914REGISTER_TEST2(Run, 307, RACE_DEMO)
6915}  // namespace test307
6916
6917// test308: Example of double-checked-locking  {{{1
6918namespace test308 {
6919struct Foo {
6920  int a;
6921};
6922
6923static int   is_inited = 0;
6924static Mutex lock;
6925static Foo  *foo;
6926
6927void InitMe() {
6928  if (!is_inited) {
6929    lock.Lock();
6930      if (!is_inited) {
6931        foo = new Foo;
6932        foo->a = 42;
6933        is_inited = 1;
6934      }
6935    lock.Unlock();
6936  }
6937}
6938
6939void UseMe() {
6940  InitMe();
6941  CHECK(foo && foo->a == 42);
6942}
6943
6944void Worker1() { UseMe(); }
6945void Worker2() { UseMe(); }
6946void Worker3() { UseMe(); }
6947
6948
6949void Run() {
6950  ANNOTATE_TRACE_MEMORY(&is_inited);
6951  printf("test308: Example of double-checked-locking\n");
6952  MyThreadArray t1(Worker1, Worker2, Worker3);
6953  t1.Start();
6954  t1.Join();
6955}
6956REGISTER_TEST2(Run, 308, RACE_DEMO)
6957}  // namespace test308
6958
6959// test309: Simple race on an STL object.  {{{1
6960namespace test309 {
6961string  GLOB;
6962
6963void Worker1() {
6964  GLOB="Thread1";
6965}
6966void Worker2() {
6967  usleep(100000);
6968  GLOB="Booooooooooo";
6969}
6970
6971void Run() {
6972  printf("test309: simple race on an STL object.\n");
6973  MyThread t1(Worker1), t2(Worker2);
6974  t1.Start();
6975  t2.Start();
6976  t1.Join();   t2.Join();
6977}
6978REGISTER_TEST2(Run, 309, RACE_DEMO)
6979}  // namespace test309
6980
6981// test310: One more simple race.  {{{1
6982namespace test310 {
6983int     *PTR = NULL;  // GUARDED_BY(mu1)
6984
6985Mutex mu1;  // Protects PTR.
6986Mutex mu2;  // Unrelated to PTR.
6987Mutex mu3;  // Unrelated to PTR.
6988
6989void Writer1() {
6990  MutexLock lock3(&mu3);  // This lock is unrelated to PTR.
6991  MutexLock lock1(&mu1);  // Protect PTR.
6992  *PTR = 1;
6993}
6994
6995void Writer2() {
6996  MutexLock lock2(&mu2);  // This lock is unrelated to PTR.
6997  MutexLock lock1(&mu1);  // Protect PTR.
6998  int some_unrelated_stuff = 0;
6999  if (some_unrelated_stuff == 0)
7000    some_unrelated_stuff++;
7001  *PTR = 2;
7002}
7003
7004
7005void Reader() {
7006  MutexLock lock2(&mu2);  // Oh, gosh, this is a wrong mutex!
7007  CHECK(*PTR <= 2);
7008}
7009
7010// Some functions to make the stack trace non-trivial.
7011void DoWrite1() { Writer1();  }
7012void Thread1()  { DoWrite1(); }
7013
7014void DoWrite2() { Writer2();  }
7015void Thread2()  { DoWrite2(); }
7016
7017void DoRead()  { Reader();  }
7018void Thread3() { DoRead();  }
7019
7020void Run() {
7021  printf("test310: simple race.\n");
7022  PTR = new int;
7023  ANNOTATE_TRACE_MEMORY(PTR);
7024  *PTR = 0;
7025  MyThread t1(Thread1, NULL, "writer1"),
7026           t2(Thread2, NULL, "writer2"),
7027           t3(Thread3, NULL, "buggy reader");
7028  t1.Start();
7029  t2.Start();
7030  usleep(100000);  // Let the writers go first.
7031  t3.Start();
7032
7033  t1.Join();
7034  t2.Join();
7035  t3.Join();
7036}
7037REGISTER_TEST2(Run, 310, RACE_DEMO)
7038}  // namespace test310
7039
7040// test311: Yet another simple race.  {{{1
7041namespace test311 {
7042int     *PTR = NULL;  // GUARDED_BY(mu1)
7043
7044Mutex mu1;  // Protects PTR.
7045Mutex mu2;  // Unrelated to PTR.
7046Mutex mu3;  // Unrelated to PTR.
7047
7048void GoodWriter1() {
7049  MutexLock lock3(&mu3);  // This lock is unrelated to PTR.
7050  MutexLock lock1(&mu1);  // Protect PTR.
7051  *PTR = 1;
7052}
7053
7054void GoodWriter2() {
7055  MutexLock lock2(&mu2);  // This lock is unrelated to PTR.
7056  MutexLock lock1(&mu1);  // Protect PTR.
7057  *PTR = 2;
7058}
7059
7060void GoodReader() {
7061  MutexLock lock1(&mu1);  // Protect PTR.
7062  CHECK(*PTR >= 0);
7063}
7064
7065void BuggyWriter() {
7066  MutexLock lock2(&mu2);  // Wrong mutex!
7067  *PTR = 3;
7068}
7069
7070// Some functions to make the stack trace non-trivial.
7071void DoWrite1() { GoodWriter1();  }
7072void Thread1()  { DoWrite1(); }
7073
7074void DoWrite2() { GoodWriter2();  }
7075void Thread2()  { DoWrite2(); }
7076
7077void DoGoodRead()  { GoodReader();  }
7078void Thread3()     { DoGoodRead();  }
7079
7080void DoBadWrite()  { BuggyWriter(); }
7081void Thread4()     { DoBadWrite(); }
7082
7083void Run() {
7084  printf("test311: simple race.\n");
7085  PTR = new int;
7086  ANNOTATE_TRACE_MEMORY(PTR);
7087  *PTR = 0;
7088  MyThread t1(Thread1, NULL, "good writer1"),
7089           t2(Thread2, NULL, "good writer2"),
7090           t3(Thread3, NULL, "good reader"),
7091           t4(Thread4, NULL, "buggy writer");
7092  t1.Start();
7093  t3.Start();
7094  // t2 goes after t3. This way a pure happens-before detector has no chance.
7095  usleep(10000);
7096  t2.Start();
7097  usleep(100000);  // Let the good folks go first.
7098  t4.Start();
7099
7100  t1.Join();
7101  t2.Join();
7102  t3.Join();
7103  t4.Join();
7104}
7105REGISTER_TEST2(Run, 311, RACE_DEMO)
7106}  // namespace test311
7107
7108// test312: A test with a very deep stack. {{{1
7109namespace test312 {
7110int     GLOB = 0;
7111void RaceyWrite() { GLOB++; }
7112void Func1() { RaceyWrite(); }
7113void Func2() { Func1(); }
7114void Func3() { Func2(); }
7115void Func4() { Func3(); }
7116void Func5() { Func4(); }
7117void Func6() { Func5(); }
7118void Func7() { Func6(); }
7119void Func8() { Func7(); }
7120void Func9() { Func8(); }
7121void Func10() { Func9(); }
7122void Func11() { Func10(); }
7123void Func12() { Func11(); }
7124void Func13() { Func12(); }
7125void Func14() { Func13(); }
7126void Func15() { Func14(); }
7127void Func16() { Func15(); }
7128void Func17() { Func16(); }
7129void Func18() { Func17(); }
7130void Func19() { Func18(); }
7131void Worker() { Func19(); }
7132void Run() {
7133  printf("test312: simple race with deep stack.\n");
7134  MyThreadArray t(Worker, Worker, Worker);
7135  t.Start();
7136  t.Join();
7137}
7138REGISTER_TEST2(Run, 312, RACE_DEMO)
7139}  // namespace test312
7140
7141// test313 TP: test for thread graph output {{{1
7142namespace  test313 {
7143BlockingCounter *blocking_counter;
7144int     GLOB = 0;
7145
7146// Worker(N) will do 2^N increments of GLOB, each increment in a separate thread
7147void Worker(long depth) {
7148  CHECK(depth >= 0);
7149  if (depth > 0) {
7150    ThreadPool pool(2);
7151    pool.StartWorkers();
7152    pool.Add(NewCallback(Worker, depth-1));
7153    pool.Add(NewCallback(Worker, depth-1));
7154  } else {
7155    GLOB++; // Race here
7156  }
7157}
7158void Run() {
7159  printf("test313: positive\n");
7160  Worker(4);
7161  printf("\tGLOB=%d\n", GLOB);
7162}
7163REGISTER_TEST2(Run, 313, RACE_DEMO)
7164}  // namespace test313
7165
7166
7167
7168// test400: Demo of a simple false positive. {{{1
7169namespace test400 {
7170static Mutex mu;
7171static vector<int> *vec; // GUARDED_BY(mu);
7172
7173void InitAllBeforeStartingThreads() {
7174  vec = new vector<int>;
7175  vec->push_back(1);
7176  vec->push_back(2);
7177}
7178
7179void Thread1() {
7180  MutexLock lock(&mu);
7181  vec->pop_back();
7182}
7183
7184void Thread2() {
7185  MutexLock lock(&mu);
7186  vec->pop_back();
7187}
7188
7189//---- Sub-optimal code ---------
7190size_t NumberOfElementsLeft() {
7191  MutexLock lock(&mu);
7192  return vec->size();
7193}
7194
7195void WaitForAllThreadsToFinish_InefficientAndTsanUnfriendly() {
7196  while(NumberOfElementsLeft()) {
7197    ; // sleep or print or do nothing.
7198  }
7199  // It is now safe to access vec w/o lock.
7200  // But a hybrid detector (like ThreadSanitizer) can't see it.
7201  // Solutions:
7202  //   1. Use pure happens-before detector (e.g. "tsan --pure-happens-before")
7203  //   2. Call ANNOTATE_MUTEX_IS_USED_AS_CONDVAR(&mu)
7204  //      in InitAllBeforeStartingThreads()
7205  //   3. (preferred) Use WaitForAllThreadsToFinish_Good() (see below).
7206  CHECK(vec->empty());
7207  delete vec;
7208}
7209
7210//----- Better code -----------
7211
7212bool NoElementsLeft(vector<int> *v) {
7213  return v->empty();
7214}
7215
7216void WaitForAllThreadsToFinish_Good() {
7217  mu.LockWhen(Condition(NoElementsLeft, vec));
7218  mu.Unlock();
7219
7220  // It is now safe to access vec w/o lock.
7221  CHECK(vec->empty());
7222  delete vec;
7223}
7224
7225
7226void Run() {
7227  MyThreadArray t(Thread1, Thread2);
7228  InitAllBeforeStartingThreads();
7229  t.Start();
7230  WaitForAllThreadsToFinish_InefficientAndTsanUnfriendly();
7231//  WaitForAllThreadsToFinish_Good();
7232  t.Join();
7233}
7234REGISTER_TEST2(Run, 400, RACE_DEMO)
7235}  // namespace test400
7236
7237// test401: Demo of false positive caused by reference counting. {{{1
7238namespace test401 {
7239// A simplified example of reference counting.
7240// DecRef() does ref count increment in a way unfriendly to race detectors.
7241// DecRefAnnotated() does the same in a friendly way.
7242
7243static vector<int> *vec;
7244static int ref_count;
7245
7246void InitAllBeforeStartingThreads(int number_of_threads) {
7247  vec = new vector<int>;
7248  vec->push_back(1);
7249  ref_count = number_of_threads;
7250}
7251
7252// Correct, but unfriendly to race detectors.
7253int DecRef() {
7254  return AtomicIncrement(&ref_count, -1);
7255}
7256
7257// Correct and friendly to race detectors.
7258int DecRefAnnotated() {
7259  ANNOTATE_CONDVAR_SIGNAL(&ref_count);
7260  int res = AtomicIncrement(&ref_count, -1);
7261  if (res == 0) {
7262    ANNOTATE_CONDVAR_WAIT(&ref_count);
7263  }
7264  return res;
7265}
7266
7267void ThreadWorker() {
7268  CHECK(ref_count > 0);
7269  CHECK(vec->size() == 1);
7270  if (DecRef() == 0) {  // Use DecRefAnnotated() instead!
7271    // No one uses vec now ==> delete it.
7272    delete vec;  // A false race may be reported here.
7273    vec = NULL;
7274  }
7275}
7276
7277void Run() {
7278  MyThreadArray t(ThreadWorker, ThreadWorker, ThreadWorker);
7279  InitAllBeforeStartingThreads(3 /*number of threads*/);
7280  t.Start();
7281  t.Join();
7282  CHECK(vec == 0);
7283}
7284REGISTER_TEST2(Run, 401, RACE_DEMO)
7285}  // namespace test401
7286
7287// test501: Manually call PRINT_* annotations {{{1
7288namespace test501 {
7289int  COUNTER = 0;
7290int     GLOB = 0;
7291Mutex muCounter, muGlob[65];
7292
7293void Worker() {
7294   muCounter.Lock();
7295   int myId = ++COUNTER;
7296   muCounter.Unlock();
7297
7298   usleep(100);
7299
7300   muGlob[myId].Lock();
7301   muGlob[0].Lock();
7302   GLOB++;
7303   muGlob[0].Unlock();
7304   muGlob[myId].Unlock();
7305}
7306
7307void Worker_1() {
7308   MyThreadArray ta (Worker, Worker, Worker, Worker);
7309   ta.Start();
7310   usleep(500000);
7311   ta.Join ();
7312}
7313
7314void Worker_2() {
7315   MyThreadArray ta (Worker_1, Worker_1, Worker_1, Worker_1);
7316   ta.Start();
7317   usleep(300000);
7318   ta.Join ();
7319}
7320
7321void Run() {
7322   ANNOTATE_RESET_STATS();
7323   printf("test501: Manually call PRINT_* annotations.\n");
7324   MyThreadArray ta (Worker_2, Worker_2, Worker_2, Worker_2);
7325   ta.Start();
7326   usleep(100000);
7327   ta.Join ();
7328   ANNOTATE_PRINT_MEMORY_USAGE(0);
7329   ANNOTATE_PRINT_STATS();
7330}
7331
7332REGISTER_TEST2(Run, 501, FEATURE | EXCLUDE_FROM_ALL)
7333}  // namespace test501
7334
7335// test502: produce lots of segments without cross-thread relations {{{1
7336namespace test502 {
7337
7338/*
7339 * This test produces ~1Gb of memory usage when run with the following options:
7340 *
7341 * --tool=helgrind
7342 * --trace-after-race=0
7343 * --num-callers=2
7344 * --more-context=no
7345 */
7346
7347Mutex MU;
7348int     GLOB = 0;
7349
7350void TP() {
7351   for (int i = 0; i < 750000; i++) {
7352      MU.Lock();
7353      GLOB++;
7354      MU.Unlock();
7355   }
7356}
7357
7358void Run() {
7359   MyThreadArray t(TP, TP);
7360   printf("test502: produce lots of segments without cross-thread relations\n");
7361
7362   t.Start();
7363   t.Join();
7364}
7365
7366REGISTER_TEST2(Run, 502, MEMORY_USAGE | PRINT_STATS | EXCLUDE_FROM_ALL
7367                              | PERFORMANCE)
7368}  // namespace test502
7369
7370// test503: produce lots of segments with simple HB-relations {{{1
7371// HB cache-miss rate is ~55%
7372namespace test503 {
7373
7374//  |- |  |  |  |  |
7375//  | \|  |  |  |  |
7376//  |  |- |  |  |  |
7377//  |  | \|  |  |  |
7378//  |  |  |- |  |  |
7379//  |  |  | \|  |  |
7380//  |  |  |  |- |  |
7381//  |  |  |  | \|  |
7382//  |  |  |  |  |- |
7383//  |  |  |  |  | \|
7384//  |  |  |  |  |  |----
7385//->|  |  |  |  |  |
7386//  |- |  |  |  |  |
7387//  | \|  |  |  |  |
7388//     ...
7389
7390const int N_threads = 32;
7391const int ARRAY_SIZE = 128;
7392int       GLOB[ARRAY_SIZE];
7393ProducerConsumerQueue *Q[N_threads];
7394int GLOB_limit = 100000;
7395int count = -1;
7396
7397void Worker(){
7398   int myId = AtomicIncrement(&count, 1);
7399
7400   ProducerConsumerQueue &myQ = *Q[myId], &nextQ = *Q[(myId+1) % N_threads];
7401
7402   // this code produces a new SS with each new segment
7403   while (myQ.Get() != NULL) {
7404      for (int i = 0; i < ARRAY_SIZE; i++)
7405         GLOB[i]++;
7406