tsan_clock.cc revision 7ac41484ea322e0ea5774df681660269f5dc321e 
1//===-- tsan_clock.cc -------------------------------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of ThreadSanitizer (TSan), a race detector.
11//
12//===----------------------------------------------------------------------===//
13#include "tsan_clock.h"
14#include "tsan_rtl.h"
15
16// It's possible to optimize clock operations for some important cases
17// so that they are O(1). The cases include singletons, once's, local mutexes.
18// First, SyncClock must be re-implemented to allow indexing by tid.
19// It must not necessarily be a full vector clock, though. For example it may
20// be a multi-level table.
21// Then, each slot in SyncClock must contain a dirty bit (it's united with
22// the clock value, so no space increase). The acquire algorithm looks
23// as follows:
24// void acquire(thr, tid, thr_clock, sync_clock) {
25//   if (!sync_clock[tid].dirty)
26//     return;  // No new info to acquire.
27//              // This handles constant reads of singleton pointers and
28//              // stop-flags.
29//   acquire_impl(thr_clock, sync_clock);  // As usual, O(N).
30//   sync_clock[tid].dirty = false;
31//   sync_clock.dirty_count--;
32// }
33// The release operation looks as follows:
34// void release(thr, tid, thr_clock, sync_clock) {
35//   // thr->sync_cache is a simple fixed-size hash-based cache that holds
36//   // several previous sync_clock's.
37//   if (thr->sync_cache[sync_clock] >= thr->last_acquire_epoch) {
38//     // The thread did no acquire operations since last release on this clock.
39//     // So update only the thread's slot (other slots can't possibly change).
40//     sync_clock[tid].clock = thr->epoch;
41//     if (sync_clock.dirty_count == sync_clock.cnt
42//         || (sync_clock.dirty_count == sync_clock.cnt - 1
43//           && sync_clock[tid].dirty == false))
44//       // All dirty flags are set, bail out.
45//       return;
46//     set all dirty bits, but preserve the thread's bit.  // O(N)
47//     update sync_clock.dirty_count;
48//     return;
49//   }
50//   release_impl(thr_clock, sync_clock);  // As usual, O(N).
51//   set all dirty bits, but preserve the thread's bit.
52//   // The previous step is combined with release_impl(), so that
53//   // we scan the arrays only once.
54//   update sync_clock.dirty_count;
55// }
56
57namespace __tsan {
58
59ThreadClock::ThreadClock() {
60  nclk_ = 0;
61  for (uptr i = 0; i < (uptr)kMaxTid; i++)
62    clk_[i] = 0;
63}
64
65void ThreadClock::acquire(const SyncClock *src) {
66  DCHECK(nclk_ <= kMaxTid);
67  DCHECK(src->clk_.Size() <= kMaxTid);
68
69  const uptr nclk = src->clk_.Size();
70  if (nclk == 0)
71    return;
72  nclk_ = max(nclk_, nclk);
73  for (uptr i = 0; i < nclk; i++) {
74    if (clk_[i] < src->clk_[i])
75      clk_[i] = src->clk_[i];
76  }
77}
78
79void ThreadClock::release(SyncClock *dst) const {
80  DCHECK(nclk_ <= kMaxTid);
81  DCHECK(dst->clk_.Size() <= kMaxTid);
82
83  if (dst->clk_.Size() < nclk_)
84    dst->clk_.Resize(nclk_);
85  for (uptr i = 0; i < nclk_; i++) {
86    if (dst->clk_[i] < clk_[i])
87      dst->clk_[i] = clk_[i];
88  }
89}
90
91void ThreadClock::acq_rel(SyncClock *dst) {
92  acquire(dst);
93  release(dst);
94}
95
96SyncClock::SyncClock()
97  : clk_(MBlockClock) {
98}
99}  // namespace __tsan
100