xref: /llvm-project/llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h (revision 3e11ae69abd17a80759ae1d9565d555f6a869304) 
1 //===-- SymbolStringPool.h -- Thread-safe pool for JIT symbols --*- 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 // Contains a thread-safe string pool suitable for use with ORC.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
14 #define LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/StringMap.h"
18 #include <atomic>
19 #include <mutex>
20 
21 namespace llvm {
22 
23 class raw_ostream;
24 
25 namespace orc {
26 
27 class SymbolStringPtrBase;
28 class SymbolStringPtr;
29 class NonOwningSymbolStringPtr;
30 
31 /// String pool for symbol names used by the JIT.
32 class SymbolStringPool {
33   friend class SymbolStringPoolTest;
34   friend class SymbolStringPtrBase;
35   friend class SymbolStringPoolEntryUnsafe;
36 
37   // Implemented in DebugUtils.h.
38   friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP);
39 
40 public:
41   /// Destroy a SymbolStringPool.
42   ~SymbolStringPool();
43 
44   /// Create a symbol string pointer from the given string.
45   SymbolStringPtr intern(StringRef S);
46 
47   /// Remove from the pool any entries that are no longer referenced.
48   void clearDeadEntries();
49 
50   /// Returns true if the pool is empty.
51   bool empty() const;
52 
53 private:
54   size_t getRefCount(const SymbolStringPtrBase &S) const;
55 
56   using RefCountType = std::atomic<size_t>;
57   using PoolMap = StringMap<RefCountType>;
58   using PoolMapEntry = StringMapEntry<RefCountType>;
59   mutable std::mutex PoolMutex;
60   PoolMap Pool;
61 };
62 
63 /// Base class for both owning and non-owning symbol-string ptrs.
64 ///
65 /// All symbol-string ptrs are convertible to bool, dereferenceable and
66 /// comparable.
67 ///
68 /// SymbolStringPtrBases are default-constructible and constructible
69 /// from nullptr to enable comparison with these values.
70 class SymbolStringPtrBase {
71   friend class SymbolStringPool;
72   friend struct DenseMapInfo<SymbolStringPtr>;
73   friend struct DenseMapInfo<NonOwningSymbolStringPtr>;
74 
75 public:
76   SymbolStringPtrBase() = default;
77   SymbolStringPtrBase(std::nullptr_t) {}
78 
79   explicit operator bool() const { return S; }
80 
81   StringRef operator*() const { return S->first(); }
82 
83   friend bool operator==(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
84     return LHS.S == RHS.S;
85   }
86 
87   friend bool operator!=(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
88     return !(LHS == RHS);
89   }
90 
91   friend bool operator<(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
92     return LHS.S < RHS.S;
93   }
94 
95   friend raw_ostream &operator<<(raw_ostream &OS,
96                                  const SymbolStringPtrBase &Sym);
97 
98 #ifndef NDEBUG
99   // Returns true if the pool entry's ref count is above zero (or if the entry
100   // is an empty or tombstone value). Useful for debugging and testing -- this
101   // method can be used to identify SymbolStringPtrs and
102   // NonOwningSymbolStringPtrs that are pointing to abandoned pool entries.
103   bool poolEntryIsAlive() const {
104     return isRealPoolEntry(S) ? S->getValue() != 0 : true;
105   }
106 #endif
107 
108 protected:
109   using PoolEntry = SymbolStringPool::PoolMapEntry;
110   using PoolEntryPtr = PoolEntry *;
111 
112   SymbolStringPtrBase(PoolEntryPtr S) : S(S) {}
113 
114   constexpr static uintptr_t EmptyBitPattern =
115       std::numeric_limits<uintptr_t>::max()
116       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
117 
118   constexpr static uintptr_t TombstoneBitPattern =
119       (std::numeric_limits<uintptr_t>::max() - 1)
120       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
121 
122   constexpr static uintptr_t InvalidPtrMask =
123       (std::numeric_limits<uintptr_t>::max() - 3)
124       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
125 
126   // Returns false for null, empty, and tombstone values, true otherwise.
127   static bool isRealPoolEntry(PoolEntryPtr P) {
128     return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
129            InvalidPtrMask;
130   }
131 
132   size_t getRefCount() const {
133     return isRealPoolEntry(S) ? size_t(S->getValue()) : size_t(0);
134   }
135 
136   PoolEntryPtr S = nullptr;
137 };
138 
139 /// Pointer to a pooled string representing a symbol name.
140 class SymbolStringPtr : public SymbolStringPtrBase {
141   friend class SymbolStringPool;
142   friend class SymbolStringPoolEntryUnsafe;
143   friend struct DenseMapInfo<SymbolStringPtr>;
144 
145 public:
146   SymbolStringPtr() = default;
147   SymbolStringPtr(std::nullptr_t) {}
148   SymbolStringPtr(const SymbolStringPtr &Other) : SymbolStringPtrBase(Other.S) {
149     incRef();
150   }
151 
152   explicit SymbolStringPtr(NonOwningSymbolStringPtr Other);
153 
154   SymbolStringPtr& operator=(const SymbolStringPtr &Other) {
155     decRef();
156     S = Other.S;
157     incRef();
158     return *this;
159   }
160 
161   SymbolStringPtr(SymbolStringPtr &&Other) { std::swap(S, Other.S); }
162 
163   SymbolStringPtr& operator=(SymbolStringPtr &&Other) {
164     decRef();
165     S = nullptr;
166     std::swap(S, Other.S);
167     return *this;
168   }
169 
170   ~SymbolStringPtr() { decRef(); }
171 
172 private:
173   SymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) { incRef(); }
174 
175   void incRef() {
176     if (isRealPoolEntry(S))
177       ++S->getValue();
178   }
179 
180   void decRef() {
181     if (isRealPoolEntry(S)) {
182       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
183       --S->getValue();
184     }
185   }
186 
187   static SymbolStringPtr getEmptyVal() {
188     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
189   }
190 
191   static SymbolStringPtr getTombstoneVal() {
192     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
193   }
194 };
195 
196 /// Provides unsafe access to ownership operations on SymbolStringPtr.
197 /// This class can be used to manage SymbolStringPtr instances from C.
198 class SymbolStringPoolEntryUnsafe {
199 public:
200   using PoolEntry = SymbolStringPool::PoolMapEntry;
201 
202   SymbolStringPoolEntryUnsafe(PoolEntry *E) : E(E) {}
203 
204   /// Create an unsafe pool entry ref without changing the ref-count.
205   static SymbolStringPoolEntryUnsafe from(const SymbolStringPtr &S) {
206     return S.S;
207   }
208 
209   /// Consumes the given SymbolStringPtr without releasing the pool entry.
210   static SymbolStringPoolEntryUnsafe take(SymbolStringPtr &&S) {
211     PoolEntry *E = nullptr;
212     std::swap(E, S.S);
213     return E;
214   }
215 
216   PoolEntry *rawPtr() { return E; }
217 
218   /// Creates a SymbolStringPtr for this entry, with the SymbolStringPtr
219   /// retaining the entry as usual.
220   SymbolStringPtr copyToSymbolStringPtr() { return SymbolStringPtr(E); }
221 
222   /// Creates a SymbolStringPtr for this entry *without* performing a retain
223   /// operation during construction.
224   SymbolStringPtr moveToSymbolStringPtr() {
225     SymbolStringPtr S;
226     std::swap(S.S, E);
227     return S;
228   }
229 
230   void retain() { ++E->getValue(); }
231   void release() { --E->getValue(); }
232 
233 private:
234   PoolEntry *E = nullptr;
235 };
236 
237 /// Non-owning SymbolStringPool entry pointer. Instances are comparable with
238 /// SymbolStringPtr instances and guaranteed to have the same hash, but do not
239 /// affect the ref-count of the pooled string (and are therefore cheaper to
240 /// copy).
241 ///
242 /// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's
243 /// ref-count drops to zero, so they should only be used in contexts where a
244 /// corresponding SymbolStringPtr is known to exist (which will guarantee that
245 /// the ref-count stays above zero). E.g. in a graph where nodes are
246 /// represented by SymbolStringPtrs the edges can be represented by pairs of
247 /// NonOwningSymbolStringPtrs and this will make the introduction of deletion
248 /// of edges cheaper.
249 class NonOwningSymbolStringPtr : public SymbolStringPtrBase {
250   friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>;
251 
252 public:
253   NonOwningSymbolStringPtr() = default;
254   explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S)
255       : SymbolStringPtrBase(S) {}
256 
257   using SymbolStringPtrBase::operator=;
258 
259 private:
260   NonOwningSymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {}
261 
262   static NonOwningSymbolStringPtr getEmptyVal() {
263     return NonOwningSymbolStringPtr(
264         reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
265   }
266 
267   static NonOwningSymbolStringPtr getTombstoneVal() {
268     return NonOwningSymbolStringPtr(
269         reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
270   }
271 };
272 
273 inline SymbolStringPtr::SymbolStringPtr(NonOwningSymbolStringPtr Other)
274     : SymbolStringPtrBase(Other) {
275   assert(poolEntryIsAlive() &&
276          "SymbolStringPtr constructed from invalid non-owning pointer.");
277 
278   if (isRealPoolEntry(S))
279     ++S->getValue();
280 }
281 
282 inline SymbolStringPool::~SymbolStringPool() {
283 #ifndef NDEBUG
284   clearDeadEntries();
285   assert(Pool.empty() && "Dangling references at pool destruction time");
286 #endif // NDEBUG
287 }
288 
289 inline SymbolStringPtr SymbolStringPool::intern(StringRef S) {
290   std::lock_guard<std::mutex> Lock(PoolMutex);
291   PoolMap::iterator I;
292   bool Added;
293   std::tie(I, Added) = Pool.try_emplace(S, 0);
294   return SymbolStringPtr(&*I);
295 }
296 
297 inline void SymbolStringPool::clearDeadEntries() {
298   std::lock_guard<std::mutex> Lock(PoolMutex);
299   for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
300     auto Tmp = I++;
301     if (Tmp->second == 0)
302       Pool.erase(Tmp);
303   }
304 }
305 
306 inline bool SymbolStringPool::empty() const {
307   std::lock_guard<std::mutex> Lock(PoolMutex);
308   return Pool.empty();
309 }
310 
311 inline size_t
312 SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const {
313   return S.getRefCount();
314 }
315 
316 } // end namespace orc
317 
318 template <>
319 struct DenseMapInfo<orc::SymbolStringPtr> {
320 
321   static orc::SymbolStringPtr getEmptyKey() {
322     return orc::SymbolStringPtr::getEmptyVal();
323   }
324 
325   static orc::SymbolStringPtr getTombstoneKey() {
326     return orc::SymbolStringPtr::getTombstoneVal();
327   }
328 
329   static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
330     return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
331   }
332 
333   static bool isEqual(const orc::SymbolStringPtrBase &LHS,
334                       const orc::SymbolStringPtrBase &RHS) {
335     return LHS.S == RHS.S;
336   }
337 };
338 
339 template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> {
340 
341   static orc::NonOwningSymbolStringPtr getEmptyKey() {
342     return orc::NonOwningSymbolStringPtr::getEmptyVal();
343   }
344 
345   static orc::NonOwningSymbolStringPtr getTombstoneKey() {
346     return orc::NonOwningSymbolStringPtr::getTombstoneVal();
347   }
348 
349   static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
350     return DenseMapInfo<
351         orc::NonOwningSymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
352   }
353 
354   static bool isEqual(const orc::SymbolStringPtrBase &LHS,
355                       const orc::SymbolStringPtrBase &RHS) {
356     return LHS.S == RHS.S;
357   }
358 };
359 
360 } // end namespace llvm
361 
362 #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
363