Viewing file:  SymbolStringPool.h (10.4 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
//===-- SymbolStringPool.h -- Thread-safe pool for JIT symbols --*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Contains a thread-safe string pool suitable for use with ORC.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
#define LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/StringMap.h"
#include <atomic>
#include <mutex>
namespace llvm {
class raw_ostream;
namespace orc {
class SymbolStringPtrBase;
class SymbolStringPtr;
class NonOwningSymbolStringPtr;
/// String pool for symbol names used by the JIT.
class SymbolStringPool {
friend class SymbolStringPoolTest;
friend class SymbolStringPtrBase;
friend class SymbolStringPoolEntryUnsafe;
// Implemented in DebugUtils.h.
friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP);
public:
/// Destroy a SymbolStringPool.
~SymbolStringPool();
/// Create a symbol string pointer from the given string.
SymbolStringPtr intern(StringRef S);
/// Remove from the pool any entries that are no longer referenced.
void clearDeadEntries();
/// Returns true if the pool is empty.
bool empty() const;
private:
size_t getRefCount(const SymbolStringPtrBase &S) const;
using RefCountType = std::atomic<size_t>;
using PoolMap = StringMap<RefCountType>;
using PoolMapEntry = StringMapEntry<RefCountType>;
mutable std::mutex PoolMutex;
PoolMap Pool;
};
/// Base class for both owning and non-owning symbol-string ptrs.
///
/// All symbol-string ptrs are convertible to bool, dereferenceable and
/// comparable.
///
/// SymbolStringPtrBases are default-constructible and constructible
/// from nullptr to enable comparison with these values.
class SymbolStringPtrBase {
friend class SymbolStringPool;
friend struct DenseMapInfo<SymbolStringPtr>;
friend struct DenseMapInfo<NonOwningSymbolStringPtr>;
public:
SymbolStringPtrBase() = default;
SymbolStringPtrBase(std::nullptr_t) {}
explicit operator bool() const { return S; }
StringRef operator*() const { return S->first(); }
friend bool operator==(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
return LHS.S == RHS.S;
}
friend bool operator!=(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
return !(LHS == RHS);
}
friend bool operator<(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
return LHS.S < RHS.S;
}
#ifndef NDEBUG
// Returns true if the pool entry's ref count is above zero (or if the entry
// is an empty or tombstone value). Useful for debugging and testing -- this
// method can be used to identify SymbolStringPtrs and
// NonOwningSymbolStringPtrs that are pointing to abandoned pool entries.
bool poolEntryIsAlive() const {
return isRealPoolEntry(S) ? S->getValue() != 0 : true;
}
#endif
protected:
using PoolEntry = SymbolStringPool::PoolMapEntry;
using PoolEntryPtr = PoolEntry *;
SymbolStringPtrBase(PoolEntryPtr S) : S(S) {}
constexpr static uintptr_t EmptyBitPattern =
std::numeric_limits<uintptr_t>::max()
<< PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
constexpr static uintptr_t TombstoneBitPattern =
(std::numeric_limits<uintptr_t>::max() - 1)
<< PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
constexpr static uintptr_t InvalidPtrMask =
(std::numeric_limits<uintptr_t>::max() - 3)
<< PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
// Returns false for null, empty, and tombstone values, true otherwise.
static bool isRealPoolEntry(PoolEntryPtr P) {
return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
InvalidPtrMask;
}
size_t getRefCount() const {
return isRealPoolEntry(S) ? size_t(S->getValue()) : size_t(0);
}
PoolEntryPtr S = nullptr;
};
/// Pointer to a pooled string representing a symbol name.
class SymbolStringPtr : public SymbolStringPtrBase {
friend class SymbolStringPool;
friend class SymbolStringPoolEntryUnsafe;
friend struct DenseMapInfo<SymbolStringPtr>;
public:
SymbolStringPtr() = default;
SymbolStringPtr(std::nullptr_t) {}
SymbolStringPtr(const SymbolStringPtr &Other) : SymbolStringPtrBase(Other.S) {
incRef();
}
explicit SymbolStringPtr(NonOwningSymbolStringPtr Other);
SymbolStringPtr& operator=(const SymbolStringPtr &Other) {
decRef();
S = Other.S;
incRef();
return *this;
}
SymbolStringPtr(SymbolStringPtr &&Other) { std::swap(S, Other.S); }
SymbolStringPtr& operator=(SymbolStringPtr &&Other) {
decRef();
S = nullptr;
std::swap(S, Other.S);
return *this;
}
~SymbolStringPtr() { decRef(); }
private:
SymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) { incRef(); }
void incRef() {
if (isRealPoolEntry(S))
++S->getValue();
}
void decRef() {
if (isRealPoolEntry(S)) {
assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
--S->getValue();
}
}
static SymbolStringPtr getEmptyVal() {
return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
}
static SymbolStringPtr getTombstoneVal() {
return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
}
};
/// Provides unsafe access to ownership operations on SymbolStringPtr.
/// This class can be used to manage SymbolStringPtr instances from C.
class SymbolStringPoolEntryUnsafe {
public:
using PoolEntry = SymbolStringPool::PoolMapEntry;
SymbolStringPoolEntryUnsafe(PoolEntry *E) : E(E) {}
/// Create an unsafe pool entry ref without changing the ref-count.
static SymbolStringPoolEntryUnsafe from(const SymbolStringPtr &S) {
return S.S;
}
/// Consumes the given SymbolStringPtr without releasing the pool entry.
static SymbolStringPoolEntryUnsafe take(SymbolStringPtr &&S) {
PoolEntry *E = nullptr;
std::swap(E, S.S);
return E;
}
PoolEntry *rawPtr() { return E; }
/// Creates a SymbolStringPtr for this entry, with the SymbolStringPtr
/// retaining the entry as usual.
SymbolStringPtr copyToSymbolStringPtr() { return SymbolStringPtr(E); }
/// Creates a SymbolStringPtr for this entry *without* performing a retain
/// operation during construction.
SymbolStringPtr moveToSymbolStringPtr() {
SymbolStringPtr S;
std::swap(S.S, E);
return S;
}
void retain() { ++E->getValue(); }
void release() { --E->getValue(); }
private:
PoolEntry *E = nullptr;
};
/// Non-owning SymbolStringPool entry pointer. Instances are comparable with
/// SymbolStringPtr instances and guaranteed to have the same hash, but do not
/// affect the ref-count of the pooled string (and are therefore cheaper to
/// copy).
///
/// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's
/// ref-count drops to zero, so they should only be used in contexts where a
/// corresponding SymbolStringPtr is known to exist (which will guarantee that
/// the ref-count stays above zero). E.g. in a graph where nodes are
/// represented by SymbolStringPtrs the edges can be represented by pairs of
/// NonOwningSymbolStringPtrs and this will make the introduction of deletion
/// of edges cheaper.
class NonOwningSymbolStringPtr : public SymbolStringPtrBase {
friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>;
public:
NonOwningSymbolStringPtr() = default;
explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S)
: SymbolStringPtrBase(S) {}
using SymbolStringPtrBase::operator=;
private:
NonOwningSymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {}
static NonOwningSymbolStringPtr getEmptyVal() {
return NonOwningSymbolStringPtr(
reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
}
static NonOwningSymbolStringPtr getTombstoneVal() {
return NonOwningSymbolStringPtr(
reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
}
};
inline SymbolStringPtr::SymbolStringPtr(NonOwningSymbolStringPtr Other)
: SymbolStringPtrBase(Other) {
assert(poolEntryIsAlive() &&
"SymbolStringPtr constructed from invalid non-owning pointer.");
if (isRealPoolEntry(S))
++S->getValue();
}
inline SymbolStringPool::~SymbolStringPool() {
#ifndef NDEBUG
clearDeadEntries();
assert(Pool.empty() && "Dangling references at pool destruction time");
#endif // NDEBUG
}
inline SymbolStringPtr SymbolStringPool::intern(StringRef S) {
std::lock_guard<std::mutex> Lock(PoolMutex);
PoolMap::iterator I;
bool Added;
std::tie(I, Added) = Pool.try_emplace(S, 0);
return SymbolStringPtr(&*I);
}
inline void SymbolStringPool::clearDeadEntries() {
std::lock_guard<std::mutex> Lock(PoolMutex);
for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
auto Tmp = I++;
if (Tmp->second == 0)
Pool.erase(Tmp);
}
}
inline bool SymbolStringPool::empty() const {
std::lock_guard<std::mutex> Lock(PoolMutex);
return Pool.empty();
}
inline size_t
SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const {
return S.getRefCount();
}
} // end namespace orc
template <>
struct DenseMapInfo<orc::SymbolStringPtr> {
static orc::SymbolStringPtr getEmptyKey() {
return orc::SymbolStringPtr::getEmptyVal();
}
static orc::SymbolStringPtr getTombstoneKey() {
return orc::SymbolStringPtr::getTombstoneVal();
}
static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
}
static bool isEqual(const orc::SymbolStringPtrBase &LHS,
const orc::SymbolStringPtrBase &RHS) {
return LHS.S == RHS.S;
}
};
template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> {
static orc::NonOwningSymbolStringPtr getEmptyKey() {
return orc::NonOwningSymbolStringPtr::getEmptyVal();
}
static orc::NonOwningSymbolStringPtr getTombstoneKey() {
return orc::NonOwningSymbolStringPtr::getTombstoneVal();
}
static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
return DenseMapInfo<
orc::NonOwningSymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
}
static bool isEqual(const orc::SymbolStringPtrBase &LHS,
const orc::SymbolStringPtrBase &RHS) {
return LHS.S == RHS.S;
}
};
} // end namespace llvm
#endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
|