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
14#include "sanitizer_common/sanitizer_placement_new.h"
15#include "tsan_rtl.h"
16
17namespace __tsan {
18
19MutexSet::MutexSet() {
20}
21
22void MutexSet::Add(u64 id, bool write, u64 epoch) {
23  // Look up existing mutex with the same id.
24  for (uptr i = 0; i < size_; i++) {
25    if (descs_[i].id == id) {
26      descs_[i].count++;
27      descs_[i].epoch = epoch;
28      return;
29    }
30  }
31  // On overflow, find the oldest mutex and drop it.
32  if (size_ == kMaxSize) {
33    u64 minepoch = (u64)-1;
34    u64 mini = (u64)-1;
35    for (uptr i = 0; i < size_; i++) {
36      if (descs_[i].epoch < minepoch) {
37        minepoch = descs_[i].epoch;
38        mini = i;
39      }
40    }
41    RemovePos(mini);
42    CHECK_EQ(size_, kMaxSize - 1);
43  }
44  // Add new mutex descriptor.
45  descs_[size_].addr = 0;
46  descs_[size_].stack_id = kInvalidStackID;
47  descs_[size_].id = id;
48  descs_[size_].write = write;
49  descs_[size_].epoch = epoch;
50  descs_[size_].seq = seq_++;
51  descs_[size_].count = 1;
52  size_++;
53}
54
55void MutexSet::Del(u64 id, bool write) {
56  for (uptr i = 0; i < size_; i++) {
57    if (descs_[i].id == id) {
58      if (--descs_[i].count == 0)
59        RemovePos(i);
60      return;
61    }
62  }
63}
64
65void MutexSet::Remove(u64 id) {
66  for (uptr i = 0; i < size_; i++) {
67    if (descs_[i].id == id) {
68      RemovePos(i);
69      return;
70    }
71  }
72}
73
74void MutexSet::AddAddr(uptr addr, StackID stack_id, bool write) {
75  // Look up existing mutex with the same id.
76  for (uptr i = 0; i < size_; i++) {
77    if (descs_[i].addr == addr) {
78      descs_[i].count++;
79      descs_[i].seq = seq_++;
80      return;
81    }
82  }
83  // On overflow, find the oldest mutex and drop it.
84  if (size_ == kMaxSize) {
85    uptr min = 0;
86    for (uptr i = 0; i < size_; i++) {
87      if (descs_[i].seq < descs_[min].seq)
88        min = i;
89    }
90    RemovePos(min);
91    CHECK_EQ(size_, kMaxSize - 1);
92  }
93  // Add new mutex descriptor.
94  descs_[size_].addr = addr;
95  descs_[size_].stack_id = stack_id;
96  descs_[size_].id = 0;
97  descs_[size_].write = write;
98  descs_[size_].epoch = 0;
99  descs_[size_].seq = seq_++;
100  descs_[size_].count = 1;
101  size_++;
102}
103
104void MutexSet::DelAddr(uptr addr, bool destroy) {
105  for (uptr i = 0; i < size_; i++) {
106    if (descs_[i].addr == addr) {
107      if (destroy || --descs_[i].count == 0)
108        RemovePos(i);
109      return;
110    }
111  }
112}
113
114void MutexSet::RemovePos(uptr i) {
115  CHECK_LT(i, size_);
116  descs_[i] = descs_[size_ - 1];
117  size_--;
118}
119
120uptr MutexSet::Size() const {
121  return size_;
122}
123
124MutexSet::Desc MutexSet::Get(uptr i) const {
125  CHECK_LT(i, size_);
126  return descs_[i];
127}
128
129DynamicMutexSet::DynamicMutexSet() : ptr_(New<MutexSet>()) {}
130DynamicMutexSet::~DynamicMutexSet() { DestroyAndFree(ptr_); }
131
132}  // namespace __tsan
133