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