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 | #ifndef NDEBUG |
96 | // Returns true if the pool entry's ref count is above zero (or if the entry |
97 | // is an empty or tombstone value). Useful for debugging and testing -- this |
98 | // method can be used to identify SymbolStringPtrs and |
99 | // NonOwningSymbolStringPtrs that are pointing to abandoned pool entries. |
100 | bool poolEntryIsAlive() const { |
101 | return isRealPoolEntry(P: S) ? S->getValue() != 0 : true; |
102 | } |
103 | #endif |
104 | |
105 | protected: |
106 | using PoolEntry = SymbolStringPool::PoolMapEntry; |
107 | using PoolEntryPtr = PoolEntry *; |
108 | |
109 | SymbolStringPtrBase(PoolEntryPtr S) : S(S) {} |
110 | |
111 | constexpr static uintptr_t EmptyBitPattern = |
112 | std::numeric_limits<uintptr_t>::max() |
113 | << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; |
114 | |
115 | constexpr static uintptr_t TombstoneBitPattern = |
116 | (std::numeric_limits<uintptr_t>::max() - 1) |
117 | << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; |
118 | |
119 | constexpr static uintptr_t InvalidPtrMask = |
120 | (std::numeric_limits<uintptr_t>::max() - 3) |
121 | << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; |
122 | |
123 | // Returns false for null, empty, and tombstone values, true otherwise. |
124 | static bool isRealPoolEntry(PoolEntryPtr P) { |
125 | return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) != |
126 | InvalidPtrMask; |
127 | } |
128 | |
129 | size_t getRefCount() const { |
130 | return isRealPoolEntry(P: S) ? size_t(S->getValue()) : size_t(0); |
131 | } |
132 | |
133 | PoolEntryPtr S = nullptr; |
134 | }; |
135 | |
136 | /// Pointer to a pooled string representing a symbol name. |
137 | class SymbolStringPtr : public SymbolStringPtrBase { |
138 | friend class SymbolStringPool; |
139 | friend class SymbolStringPoolEntryUnsafe; |
140 | friend struct DenseMapInfo<SymbolStringPtr>; |
141 | |
142 | public: |
143 | SymbolStringPtr() = default; |
144 | SymbolStringPtr(std::nullptr_t) {} |
145 | SymbolStringPtr(const SymbolStringPtr &Other) : SymbolStringPtrBase(Other.S) { |
146 | incRef(); |
147 | } |
148 | |
149 | explicit SymbolStringPtr(NonOwningSymbolStringPtr Other); |
150 | |
151 | SymbolStringPtr& operator=(const SymbolStringPtr &Other) { |
152 | decRef(); |
153 | S = Other.S; |
154 | incRef(); |
155 | return *this; |
156 | } |
157 | |
158 | SymbolStringPtr(SymbolStringPtr &&Other) { std::swap(a&: S, b&: Other.S); } |
159 | |
160 | SymbolStringPtr& operator=(SymbolStringPtr &&Other) { |
161 | decRef(); |
162 | S = nullptr; |
163 | std::swap(a&: S, b&: Other.S); |
164 | return *this; |
165 | } |
166 | |
167 | ~SymbolStringPtr() { decRef(); } |
168 | |
169 | private: |
170 | SymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) { incRef(); } |
171 | |
172 | void incRef() { |
173 | if (isRealPoolEntry(P: S)) |
174 | ++S->getValue(); |
175 | } |
176 | |
177 | void decRef() { |
178 | if (isRealPoolEntry(P: S)) { |
179 | assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count" ); |
180 | --S->getValue(); |
181 | } |
182 | } |
183 | |
184 | static SymbolStringPtr getEmptyVal() { |
185 | return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern)); |
186 | } |
187 | |
188 | static SymbolStringPtr getTombstoneVal() { |
189 | return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern)); |
190 | } |
191 | }; |
192 | |
193 | /// Provides unsafe access to ownership operations on SymbolStringPtr. |
194 | /// This class can be used to manage SymbolStringPtr instances from C. |
195 | class SymbolStringPoolEntryUnsafe { |
196 | public: |
197 | using PoolEntry = SymbolStringPool::PoolMapEntry; |
198 | |
199 | SymbolStringPoolEntryUnsafe(PoolEntry *E) : E(E) {} |
200 | |
201 | /// Create an unsafe pool entry ref without changing the ref-count. |
202 | static SymbolStringPoolEntryUnsafe from(const SymbolStringPtr &S) { |
203 | return S.S; |
204 | } |
205 | |
206 | /// Consumes the given SymbolStringPtr without releasing the pool entry. |
207 | static SymbolStringPoolEntryUnsafe take(SymbolStringPtr &&S) { |
208 | PoolEntry *E = nullptr; |
209 | std::swap(a&: E, b&: S.S); |
210 | return E; |
211 | } |
212 | |
213 | PoolEntry *rawPtr() { return E; } |
214 | |
215 | /// Creates a SymbolStringPtr for this entry, with the SymbolStringPtr |
216 | /// retaining the entry as usual. |
217 | SymbolStringPtr copyToSymbolStringPtr() { return SymbolStringPtr(E); } |
218 | |
219 | /// Creates a SymbolStringPtr for this entry *without* performing a retain |
220 | /// operation during construction. |
221 | SymbolStringPtr moveToSymbolStringPtr() { |
222 | SymbolStringPtr S; |
223 | std::swap(a&: S.S, b&: E); |
224 | return S; |
225 | } |
226 | |
227 | void retain() { ++E->getValue(); } |
228 | void release() { --E->getValue(); } |
229 | |
230 | private: |
231 | PoolEntry *E = nullptr; |
232 | }; |
233 | |
234 | /// Non-owning SymbolStringPool entry pointer. Instances are comparable with |
235 | /// SymbolStringPtr instances and guaranteed to have the same hash, but do not |
236 | /// affect the ref-count of the pooled string (and are therefore cheaper to |
237 | /// copy). |
238 | /// |
239 | /// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's |
240 | /// ref-count drops to zero, so they should only be used in contexts where a |
241 | /// corresponding SymbolStringPtr is known to exist (which will guarantee that |
242 | /// the ref-count stays above zero). E.g. in a graph where nodes are |
243 | /// represented by SymbolStringPtrs the edges can be represented by pairs of |
244 | /// NonOwningSymbolStringPtrs and this will make the introduction of deletion |
245 | /// of edges cheaper. |
246 | class NonOwningSymbolStringPtr : public SymbolStringPtrBase { |
247 | friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>; |
248 | |
249 | public: |
250 | NonOwningSymbolStringPtr() = default; |
251 | explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S) |
252 | : SymbolStringPtrBase(S) {} |
253 | |
254 | using SymbolStringPtrBase::operator=; |
255 | |
256 | private: |
257 | NonOwningSymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {} |
258 | |
259 | static NonOwningSymbolStringPtr getEmptyVal() { |
260 | return NonOwningSymbolStringPtr( |
261 | reinterpret_cast<PoolEntryPtr>(EmptyBitPattern)); |
262 | } |
263 | |
264 | static NonOwningSymbolStringPtr getTombstoneVal() { |
265 | return NonOwningSymbolStringPtr( |
266 | reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern)); |
267 | } |
268 | }; |
269 | |
270 | inline SymbolStringPtr::SymbolStringPtr(NonOwningSymbolStringPtr Other) |
271 | : SymbolStringPtrBase(Other) { |
272 | assert(poolEntryIsAlive() && |
273 | "SymbolStringPtr constructed from invalid non-owning pointer." ); |
274 | |
275 | if (isRealPoolEntry(P: S)) |
276 | ++S->getValue(); |
277 | } |
278 | |
279 | inline SymbolStringPool::~SymbolStringPool() { |
280 | #ifndef NDEBUG |
281 | clearDeadEntries(); |
282 | assert(Pool.empty() && "Dangling references at pool destruction time" ); |
283 | #endif // NDEBUG |
284 | } |
285 | |
286 | inline SymbolStringPtr SymbolStringPool::intern(StringRef S) { |
287 | std::lock_guard<std::mutex> Lock(PoolMutex); |
288 | PoolMap::iterator I; |
289 | bool Added; |
290 | std::tie(args&: I, args&: Added) = Pool.try_emplace(Key: S, Args: 0); |
291 | return SymbolStringPtr(&*I); |
292 | } |
293 | |
294 | inline void SymbolStringPool::clearDeadEntries() { |
295 | std::lock_guard<std::mutex> Lock(PoolMutex); |
296 | for (auto I = Pool.begin(), E = Pool.end(); I != E;) { |
297 | auto Tmp = I++; |
298 | if (Tmp->second == 0) |
299 | Pool.erase(I: Tmp); |
300 | } |
301 | } |
302 | |
303 | inline bool SymbolStringPool::empty() const { |
304 | std::lock_guard<std::mutex> Lock(PoolMutex); |
305 | return Pool.empty(); |
306 | } |
307 | |
308 | inline size_t |
309 | SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const { |
310 | return S.getRefCount(); |
311 | } |
312 | |
313 | } // end namespace orc |
314 | |
315 | template <> |
316 | struct DenseMapInfo<orc::SymbolStringPtr> { |
317 | |
318 | static orc::SymbolStringPtr getEmptyKey() { |
319 | return orc::SymbolStringPtr::getEmptyVal(); |
320 | } |
321 | |
322 | static orc::SymbolStringPtr getTombstoneKey() { |
323 | return orc::SymbolStringPtr::getTombstoneVal(); |
324 | } |
325 | |
326 | static unsigned getHashValue(const orc::SymbolStringPtrBase &V) { |
327 | return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(PtrVal: V.S); |
328 | } |
329 | |
330 | static bool isEqual(const orc::SymbolStringPtrBase &LHS, |
331 | const orc::SymbolStringPtrBase &RHS) { |
332 | return LHS.S == RHS.S; |
333 | } |
334 | }; |
335 | |
336 | template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> { |
337 | |
338 | static orc::NonOwningSymbolStringPtr getEmptyKey() { |
339 | return orc::NonOwningSymbolStringPtr::getEmptyVal(); |
340 | } |
341 | |
342 | static orc::NonOwningSymbolStringPtr getTombstoneKey() { |
343 | return orc::NonOwningSymbolStringPtr::getTombstoneVal(); |
344 | } |
345 | |
346 | static unsigned getHashValue(const orc::SymbolStringPtrBase &V) { |
347 | return DenseMapInfo< |
348 | orc::NonOwningSymbolStringPtr::PoolEntryPtr>::getHashValue(PtrVal: V.S); |
349 | } |
350 | |
351 | static bool isEqual(const orc::SymbolStringPtrBase &LHS, |
352 | const orc::SymbolStringPtrBase &RHS) { |
353 | return LHS.S == RHS.S; |
354 | } |
355 | }; |
356 | |
357 | } // end namespace llvm |
358 | |
359 | #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H |
360 | |