1 //===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===// 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 defines some basic utility classes for use by ThreadSafetyTIL.h 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H 14 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H 15 16 #include "clang/AST/Decl.h" 17 #include "clang/Basic/LLVM.h" 18 #include "llvm/ADT/StringRef.h" 19 #include "llvm/ADT/iterator_range.h" 20 #include "llvm/Support/Allocator.h" 21 #include <cassert> 22 #include <cstddef> 23 #include <cstring> 24 #include <iterator> 25 #include <ostream> 26 #include <string> 27 #include <vector> 28 29 namespace clang { 30 31 class Expr; 32 33 namespace threadSafety { 34 namespace til { 35 36 // Simple wrapper class to abstract away from the details of memory management. 37 // SExprs are allocated in pools, and deallocated all at once. 38 class MemRegionRef { 39 private: 40 union AlignmentType { 41 double d; 42 void *p; 43 long double dd; 44 long long ii; 45 }; 46 47 public: 48 MemRegionRef() = default; 49 MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} 50 51 void *allocate(size_t Sz) { 52 return Allocator->Allocate(Sz, alignof(AlignmentType)); 53 } 54 55 template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } 56 57 template <typename T> T *allocateT(size_t NumElems) { 58 return Allocator->Allocate<T>(NumElems); 59 } 60 61 private: 62 llvm::BumpPtrAllocator *Allocator = nullptr; 63 }; 64 65 } // namespace til 66 } // namespace threadSafety 67 68 } // namespace clang 69 70 inline void *operator new(size_t Sz, 71 clang::threadSafety::til::MemRegionRef &R) { 72 return R.allocate(Sz); 73 } 74 75 namespace clang { 76 namespace threadSafety { 77 78 std::string getSourceLiteralString(const Expr *CE); 79 80 namespace til { 81 82 // A simple fixed size array class that does not manage its own memory, 83 // suitable for use with bump pointer allocation. 84 template <class T> class SimpleArray { 85 public: 86 SimpleArray() = default; 87 SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) 88 : Data(Dat), Size(Sz), Capacity(Cp) {} 89 SimpleArray(MemRegionRef A, size_t Cp) 90 : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {} 91 SimpleArray(const SimpleArray<T> &A) = delete; 92 93 SimpleArray(SimpleArray<T> &&A) 94 : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { 95 A.Data = nullptr; 96 A.Size = 0; 97 A.Capacity = 0; 98 } 99 100 SimpleArray &operator=(SimpleArray &&RHS) { 101 if (this != &RHS) { 102 Data = RHS.Data; 103 Size = RHS.Size; 104 Capacity = RHS.Capacity; 105 106 RHS.Data = nullptr; 107 RHS.Size = RHS.Capacity = 0; 108 } 109 return *this; 110 } 111 112 // Reserve space for at least Ncp items, reallocating if necessary. 113 void reserve(size_t Ncp, MemRegionRef A) { 114 if (Ncp <= Capacity) 115 return; 116 T *Odata = Data; 117 Data = A.allocateT<T>(Ncp); 118 Capacity = Ncp; 119 memcpy(Data, Odata, sizeof(T) * Size); 120 } 121 122 // Reserve space for at least N more items. 123 void reserveCheck(size_t N, MemRegionRef A) { 124 if (Capacity == 0) 125 reserve(u_max(InitialCapacity, N), A); 126 else if (Size + N < Capacity) 127 reserve(u_max(Size + N, Capacity * 2), A); 128 } 129 130 using iterator = T *; 131 using const_iterator = const T *; 132 using reverse_iterator = std::reverse_iterator<iterator>; 133 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 134 135 size_t size() const { return Size; } 136 size_t capacity() const { return Capacity; } 137 138 T &operator[](unsigned i) { 139 assert(i < Size && "Array index out of bounds."); 140 return Data[i]; 141 } 142 143 const T &operator[](unsigned i) const { 144 assert(i < Size && "Array index out of bounds."); 145 return Data[i]; 146 } 147 148 T &back() { 149 assert(Size && "No elements in the array."); 150 return Data[Size - 1]; 151 } 152 153 const T &back() const { 154 assert(Size && "No elements in the array."); 155 return Data[Size - 1]; 156 } 157 158 iterator begin() { return Data; } 159 iterator end() { return Data + Size; } 160 161 const_iterator begin() const { return Data; } 162 const_iterator end() const { return Data + Size; } 163 164 const_iterator cbegin() const { return Data; } 165 const_iterator cend() const { return Data + Size; } 166 167 reverse_iterator rbegin() { return reverse_iterator(end()); } 168 reverse_iterator rend() { return reverse_iterator(begin()); } 169 170 const_reverse_iterator rbegin() const { 171 return const_reverse_iterator(end()); 172 } 173 174 const_reverse_iterator rend() const { 175 return const_reverse_iterator(begin()); 176 } 177 178 void push_back(const T &Elem) { 179 assert(Size < Capacity); 180 Data[Size++] = Elem; 181 } 182 183 // drop last n elements from array 184 void drop(unsigned n = 0) { 185 assert(Size > n); 186 Size -= n; 187 } 188 189 void setValues(unsigned Sz, const T& C) { 190 assert(Sz <= Capacity); 191 Size = Sz; 192 for (unsigned i = 0; i < Sz; ++i) { 193 Data[i] = C; 194 } 195 } 196 197 template <class Iter> unsigned append(Iter I, Iter E) { 198 size_t Osz = Size; 199 size_t J = Osz; 200 for (; J < Capacity && I != E; ++J, ++I) 201 Data[J] = *I; 202 Size = J; 203 return J - Osz; 204 } 205 206 llvm::iterator_range<reverse_iterator> reverse() { 207 return llvm::make_range(rbegin(), rend()); 208 } 209 210 llvm::iterator_range<const_reverse_iterator> reverse() const { 211 return llvm::make_range(rbegin(), rend()); 212 } 213 214 private: 215 // std::max is annoying here, because it requires a reference, 216 // thus forcing InitialCapacity to be initialized outside the .h file. 217 size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; } 218 219 static const size_t InitialCapacity = 4; 220 221 T *Data = nullptr; 222 size_t Size = 0; 223 size_t Capacity = 0; 224 }; 225 226 } // namespace til 227 228 // A copy on write vector. 229 // The vector can be in one of three states: 230 // * invalid -- no operations are permitted. 231 // * read-only -- read operations are permitted. 232 // * writable -- read and write operations are permitted. 233 // The init(), destroy(), and makeWritable() methods will change state. 234 template<typename T> 235 class CopyOnWriteVector { 236 class VectorData { 237 public: 238 unsigned NumRefs = 1; 239 std::vector<T> Vect; 240 241 VectorData() = default; 242 VectorData(const VectorData &VD) : Vect(VD.Vect) {} 243 }; 244 245 public: 246 CopyOnWriteVector() = default; 247 CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } 248 249 CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { 250 destroy(); 251 Data = V.Data; 252 V.Data = nullptr; 253 return *this; 254 } 255 256 // No copy constructor or copy assignment. Use clone() with move assignment. 257 CopyOnWriteVector(const CopyOnWriteVector &) = delete; 258 CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete; 259 260 ~CopyOnWriteVector() { destroy(); } 261 262 // Returns true if this holds a valid vector. 263 bool valid() const { return Data; } 264 265 // Returns true if this vector is writable. 266 bool writable() const { return Data && Data->NumRefs == 1; } 267 268 // If this vector is not valid, initialize it to a valid vector. 269 void init() { 270 if (!Data) { 271 Data = new VectorData(); 272 } 273 } 274 275 // Destroy this vector; thus making it invalid. 276 void destroy() { 277 if (!Data) 278 return; 279 if (Data->NumRefs <= 1) 280 delete Data; 281 else 282 --Data->NumRefs; 283 Data = nullptr; 284 } 285 286 // Make this vector writable, creating a copy if needed. 287 void makeWritable() { 288 if (!Data) { 289 Data = new VectorData(); 290 return; 291 } 292 if (Data->NumRefs == 1) 293 return; // already writeable. 294 --Data->NumRefs; 295 Data = new VectorData(*Data); 296 } 297 298 // Create a lazy copy of this vector. 299 CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } 300 301 using const_iterator = typename std::vector<T>::const_iterator; 302 303 const std::vector<T> &elements() const { return Data->Vect; } 304 305 const_iterator begin() const { return elements().cbegin(); } 306 const_iterator end() const { return elements().cend(); } 307 308 const T& operator[](unsigned i) const { return elements()[i]; } 309 310 unsigned size() const { return Data ? elements().size() : 0; } 311 312 // Return true if V and this vector refer to the same data. 313 bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; } 314 315 // Clear vector. The vector must be writable. 316 void clear() { 317 assert(writable() && "Vector is not writable!"); 318 Data->Vect.clear(); 319 } 320 321 // Push a new element onto the end. The vector must be writable. 322 void push_back(const T &Elem) { 323 assert(writable() && "Vector is not writable!"); 324 Data->Vect.push_back(Elem); 325 } 326 327 // Gets a mutable reference to the element at index(i). 328 // The vector must be writable. 329 T& elem(unsigned i) { 330 assert(writable() && "Vector is not writable!"); 331 return Data->Vect[i]; 332 } 333 334 // Drops elements from the back until the vector has size i. 335 void downsize(unsigned i) { 336 assert(writable() && "Vector is not writable!"); 337 Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); 338 } 339 340 private: 341 CopyOnWriteVector(VectorData *D) : Data(D) { 342 if (!Data) 343 return; 344 ++Data->NumRefs; 345 } 346 347 VectorData *Data = nullptr; 348 }; 349 350 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { 351 return ss.write(str.data(), str.size()); 352 } 353 354 } // namespace threadSafety 355 } // namespace clang 356 357 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H 358