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