1 //===- SymbolStringPool.h - Multi-threaded 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 multi-threaded 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 SymbolStringPtr;
28 
29 /// String pool for symbol names used by the JIT.
30 class SymbolStringPool {
31   friend class SymbolStringPtr;
32 
33   // Implemented in DebugUtils.h.
34   friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP);
35 
36 public:
37   /// Destroy a SymbolStringPool.
38   ~SymbolStringPool();
39 
40   /// Create a symbol string pointer from the given string.
41   SymbolStringPtr intern(StringRef S);
42 
43   /// Remove from the pool any entries that are no longer referenced.
44   void clearDeadEntries();
45 
46   /// Returns true if the pool is empty.
47   bool empty() const;
48 private:
49   using RefCountType = std::atomic<size_t>;
50   using PoolMap = StringMap<RefCountType>;
51   using PoolMapEntry = StringMapEntry<RefCountType>;
52   mutable std::mutex PoolMutex;
53   PoolMap Pool;
54 };
55 
56 /// Pointer to a pooled string representing a symbol name.
57 class SymbolStringPtr {
58   friend class OrcV2CAPIHelper;
59   friend class SymbolStringPool;
60   friend struct DenseMapInfo<SymbolStringPtr>;
61 
62 public:
63   SymbolStringPtr() = default;
64   SymbolStringPtr(std::nullptr_t) {}
65   SymbolStringPtr(const SymbolStringPtr &Other)
66     : S(Other.S) {
67     if (isRealPoolEntry(S))
68       ++S->getValue();
69   }
70 
71   SymbolStringPtr& operator=(const SymbolStringPtr &Other) {
72     if (isRealPoolEntry(S)) {
73       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
74       --S->getValue();
75     }
76     S = Other.S;
77     if (isRealPoolEntry(S))
78       ++S->getValue();
79     return *this;
80   }
81 
82   SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) {
83     std::swap(S, Other.S);
84   }
85 
86   SymbolStringPtr& operator=(SymbolStringPtr &&Other) {
87     if (isRealPoolEntry(S)) {
88       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
89       --S->getValue();
90     }
91     S = nullptr;
92     std::swap(S, Other.S);
93     return *this;
94   }
95 
96   ~SymbolStringPtr() {
97     if (isRealPoolEntry(S)) {
98       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
99       --S->getValue();
100     }
101   }
102 
103   explicit operator bool() const { return S; }
104 
105   StringRef operator*() const { return S->first(); }
106 
107   friend bool operator==(const SymbolStringPtr &LHS,
108                          const SymbolStringPtr &RHS) {
109     return LHS.S == RHS.S;
110   }
111 
112   friend bool operator!=(const SymbolStringPtr &LHS,
113                          const SymbolStringPtr &RHS) {
114     return !(LHS == RHS);
115   }
116 
117   friend bool operator<(const SymbolStringPtr &LHS,
118                         const SymbolStringPtr &RHS) {
119     return LHS.S < RHS.S;
120   }
121 
122 private:
123   using PoolEntry = SymbolStringPool::PoolMapEntry;
124   using PoolEntryPtr = PoolEntry *;
125 
126   SymbolStringPtr(SymbolStringPool::PoolMapEntry *S)
127       : S(S) {
128     if (isRealPoolEntry(S))
129       ++S->getValue();
130   }
131 
132   // Returns false for null, empty, and tombstone values, true otherwise.
133   bool isRealPoolEntry(PoolEntryPtr P) {
134     return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
135            InvalidPtrMask;
136   }
137 
138   static SymbolStringPtr getEmptyVal() {
139     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
140   }
141 
142   static SymbolStringPtr getTombstoneVal() {
143     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
144   }
145 
146   constexpr static uintptr_t EmptyBitPattern =
147       std::numeric_limits<uintptr_t>::max()
148       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
149 
150   constexpr static uintptr_t TombstoneBitPattern =
151       (std::numeric_limits<uintptr_t>::max() - 1)
152       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
153 
154   constexpr static uintptr_t InvalidPtrMask =
155       (std::numeric_limits<uintptr_t>::max() - 3)
156       << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
157 
158   PoolEntryPtr S = nullptr;
159 };
160 
161 inline SymbolStringPool::~SymbolStringPool() {
162 #ifndef NDEBUG
163   clearDeadEntries();
164   assert(Pool.empty() && "Dangling references at pool destruction time");
165 #endif // NDEBUG
166 }
167 
168 inline SymbolStringPtr SymbolStringPool::intern(StringRef S) {
169   std::lock_guard<std::mutex> Lock(PoolMutex);
170   PoolMap::iterator I;
171   bool Added;
172   std::tie(I, Added) = Pool.try_emplace(S, 0);
173   return SymbolStringPtr(&*I);
174 }
175 
176 inline void SymbolStringPool::clearDeadEntries() {
177   std::lock_guard<std::mutex> Lock(PoolMutex);
178   for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
179     auto Tmp = I++;
180     if (Tmp->second == 0)
181       Pool.erase(Tmp);
182   }
183 }
184 
185 inline bool SymbolStringPool::empty() const {
186   std::lock_guard<std::mutex> Lock(PoolMutex);
187   return Pool.empty();
188 }
189 
190 } // end namespace orc
191 
192 template <>
193 struct DenseMapInfo<orc::SymbolStringPtr> {
194 
195   static orc::SymbolStringPtr getEmptyKey() {
196     return orc::SymbolStringPtr::getEmptyVal();
197   }
198 
199   static orc::SymbolStringPtr getTombstoneKey() {
200     return orc::SymbolStringPtr::getTombstoneVal();
201   }
202 
203   static unsigned getHashValue(const orc::SymbolStringPtr &V) {
204     return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
205   }
206 
207   static bool isEqual(const orc::SymbolStringPtr &LHS,
208                       const orc::SymbolStringPtr &RHS) {
209     return LHS.S == RHS.S;
210   }
211 };
212 
213 } // end namespace llvm
214 
215 #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
216