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