1 //===-- tsan_mutexset.cpp -------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of ThreadSanitizer (TSan), a race detector.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "tsan_mutexset.h"
13 #include "tsan_rtl.h"
14 
15 namespace __tsan {
16 
17 MutexSet::MutexSet() {
18 }
19 
20 void MutexSet::Add(u64 id, bool write, u64 epoch) {
21   // Look up existing mutex with the same id.
22   for (uptr i = 0; i < size_; i++) {
23     if (descs_[i].id == id) {
24       descs_[i].count++;
25       descs_[i].epoch = epoch;
26       return;
27     }
28   }
29   // On overflow, find the oldest mutex and drop it.
30   if (size_ == kMaxSize) {
31     u64 minepoch = (u64)-1;
32     u64 mini = (u64)-1;
33     for (uptr i = 0; i < size_; i++) {
34       if (descs_[i].epoch < minepoch) {
35         minepoch = descs_[i].epoch;
36         mini = i;
37       }
38     }
39     RemovePos(mini);
40     CHECK_EQ(size_, kMaxSize - 1);
41   }
42   // Add new mutex descriptor.
43   descs_[size_].addr = 0;
44   descs_[size_].stack_id = kInvalidStackID;
45   descs_[size_].id = id;
46   descs_[size_].write = write;
47   descs_[size_].epoch = epoch;
48   descs_[size_].seq = seq_++;
49   descs_[size_].count = 1;
50   size_++;
51 }
52 
53 void MutexSet::Del(u64 id, bool write) {
54   for (uptr i = 0; i < size_; i++) {
55     if (descs_[i].id == id) {
56       if (--descs_[i].count == 0)
57         RemovePos(i);
58       return;
59     }
60   }
61 }
62 
63 void MutexSet::Remove(u64 id) {
64   for (uptr i = 0; i < size_; i++) {
65     if (descs_[i].id == id) {
66       RemovePos(i);
67       return;
68     }
69   }
70 }
71 
72 void MutexSet::AddAddr(uptr addr, StackID stack_id, bool write) {
73   // Look up existing mutex with the same id.
74   for (uptr i = 0; i < size_; i++) {
75     if (descs_[i].addr == addr) {
76       descs_[i].count++;
77       descs_[i].seq = seq_++;
78       return;
79     }
80   }
81   // On overflow, find the oldest mutex and drop it.
82   if (size_ == kMaxSize) {
83     uptr min = 0;
84     for (uptr i = 0; i < size_; i++) {
85       if (descs_[i].seq < descs_[min].seq)
86         min = i;
87     }
88     RemovePos(min);
89     CHECK_EQ(size_, kMaxSize - 1);
90   }
91   // Add new mutex descriptor.
92   descs_[size_].addr = addr;
93   descs_[size_].stack_id = stack_id;
94   descs_[size_].id = 0;
95   descs_[size_].write = write;
96   descs_[size_].epoch = 0;
97   descs_[size_].seq = seq_++;
98   descs_[size_].count = 1;
99   size_++;
100 }
101 
102 void MutexSet::DelAddr(uptr addr, bool destroy) {
103   for (uptr i = 0; i < size_; i++) {
104     if (descs_[i].addr == addr) {
105       if (destroy || --descs_[i].count == 0)
106         RemovePos(i);
107       return;
108     }
109   }
110 }
111 
112 void MutexSet::RemovePos(uptr i) {
113   CHECK_LT(i, size_);
114   descs_[i] = descs_[size_ - 1];
115   size_--;
116 }
117 
118 uptr MutexSet::Size() const {
119   return size_;
120 }
121 
122 MutexSet::Desc MutexSet::Get(uptr i) const {
123   CHECK_LT(i, size_);
124   return descs_[i];
125 }
126 
127 }  // namespace __tsan
128