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 22 namespace llvm { 23 24 class raw_ostream; 25 26 namespace orc { 27 28 class SymbolStringPtrBase; 29 class SymbolStringPtr; 30 class NonOwningSymbolStringPtr; 31 32 /// String pool for symbol names used by the JIT. 33 class 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 42 public: 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 55 private: 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. 72 class SymbolStringPtrBase { 73 friend class SymbolStringPool; 74 friend struct DenseMapInfo<SymbolStringPtr>; 75 friend struct DenseMapInfo<NonOwningSymbolStringPtr>; 76 77 public: 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 110 protected: 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(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. 142 class SymbolStringPtr : public SymbolStringPtrBase { 143 friend class SymbolStringPool; 144 friend class SymbolStringPoolEntryUnsafe; 145 friend struct DenseMapInfo<SymbolStringPtr>; 146 147 public: 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(S, Other.S); } 164 165 SymbolStringPtr& operator=(SymbolStringPtr &&Other) { 166 decRef(); 167 S = nullptr; 168 std::swap(S, Other.S); 169 return *this; 170 } 171 172 ~SymbolStringPtr() { decRef(); } 173 174 private: 175 SymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) { incRef(); } 176 177 void incRef() { 178 if (isRealPoolEntry(S)) 179 ++S->getValue(); 180 } 181 182 void decRef() { 183 if (isRealPoolEntry(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. 200 class SymbolStringPoolEntryUnsafe { 201 public: 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(E, 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(S.S, E); 229 return S; 230 } 231 232 void retain() { ++E->getValue(); } 233 void release() { --E->getValue(); } 234 235 private: 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. 251 class NonOwningSymbolStringPtr : public SymbolStringPtrBase { 252 friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>; 253 254 public: 255 NonOwningSymbolStringPtr() = default; 256 explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S) 257 : SymbolStringPtrBase(S) {} 258 259 using SymbolStringPtrBase::operator=; 260 261 private: 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 275 inline SymbolStringPtr::SymbolStringPtr(NonOwningSymbolStringPtr Other) 276 : SymbolStringPtrBase(Other) { 277 assert(poolEntryIsAlive() && 278 "SymbolStringPtr constructed from invalid non-owning pointer."); 279 280 if (isRealPoolEntry(S)) 281 ++S->getValue(); 282 } 283 284 inline SymbolStringPool::~SymbolStringPool() { 285 #ifndef NDEBUG 286 clearDeadEntries(); 287 assert(Pool.empty() && "Dangling references at pool destruction time"); 288 #endif // NDEBUG 289 } 290 291 inline SymbolStringPtr SymbolStringPool::intern(StringRef S) { 292 std::lock_guard<std::mutex> Lock(PoolMutex); 293 PoolMap::iterator I; 294 bool Added; 295 std::tie(I, Added) = Pool.try_emplace(S, 0); 296 return SymbolStringPtr(&*I); 297 } 298 299 inline 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(Tmp); 305 } 306 } 307 308 inline bool SymbolStringPool::empty() const { 309 std::lock_guard<std::mutex> Lock(PoolMutex); 310 return Pool.empty(); 311 } 312 313 inline size_t 314 SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const { 315 return S.getRefCount(); 316 } 317 318 LLVM_ABI raw_ostream &operator<<(raw_ostream &OS, 319 const SymbolStringPtrBase &Sym); 320 321 } // end namespace orc 322 323 template <> 324 struct 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(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 344 template <> 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(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