344 lines · cpp
1//===-- ConstString.cpp ---------------------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "lldb/Utility/ConstString.h"10 11#include "lldb/Utility/Stream.h"12 13#include "llvm/ADT/StringMap.h"14#include "llvm/ADT/iterator.h"15#include "llvm/Support/Allocator.h"16#include "llvm/Support/DJB.h"17#include "llvm/Support/FormatProviders.h"18#include "llvm/Support/RWMutex.h"19#include "llvm/Support/Threading.h"20 21#include <array>22#include <utility>23 24#include <cinttypes>25#include <cstdint>26#include <cstring>27 28using namespace lldb_private;29 30class Pool {31public:32 /// The default BumpPtrAllocatorImpl slab size.33 static const size_t AllocatorSlabSize = 4096;34 static const size_t SizeThreshold = AllocatorSlabSize;35 /// Every Pool has its own allocator which receives an equal share of36 /// the ConstString allocations. This means that when allocating many37 /// ConstStrings, every allocator sees only its small share of allocations and38 /// assumes LLDB only allocated a small amount of memory so far. In reality39 /// LLDB allocated a total memory that is N times as large as what the40 /// allocator sees (where N is the number of string pools). This causes that41 /// the BumpPtrAllocator continues a long time to allocate memory in small42 /// chunks which only makes sense when allocating a small amount of memory43 /// (which is true from the perspective of a single allocator). On some44 /// systems doing all these small memory allocations causes LLDB to spend45 /// a lot of time in malloc, so we need to force all these allocators to46 /// behave like one allocator in terms of scaling their memory allocations47 /// with increased demand. To do this we set the growth delay for each single48 /// allocator to a rate so that our pool of allocators scales their memory49 /// allocations similar to a single BumpPtrAllocatorImpl.50 ///51 /// Currently we have 256 string pools and the normal growth delay of the52 /// BumpPtrAllocatorImpl is 128 (i.e., the memory allocation size increases53 /// every 128 full chunks), so by changing the delay to 1 we get a54 /// total growth delay in our allocator collection of 256/1 = 256. This is55 /// still only half as fast as a normal allocator but we can't go any faster56 /// without decreasing the number of string pools.57 static const size_t AllocatorGrowthDelay = 1;58 typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, AllocatorSlabSize,59 SizeThreshold, AllocatorGrowthDelay>60 Allocator;61 typedef const char *StringPoolValueType;62 typedef llvm::StringMap<StringPoolValueType, Allocator> StringPool;63 typedef llvm::StringMapEntry<StringPoolValueType> StringPoolEntryType;64 65 static StringPoolEntryType &66 GetStringMapEntryFromKeyData(const char *keyData) {67 return StringPoolEntryType::GetStringMapEntryFromKeyData(keyData);68 }69 70 static size_t GetConstCStringLength(const char *ccstr) {71 if (ccstr != nullptr) {72 // Since the entry is read only, and we derive the entry entirely from73 // the pointer, we don't need the lock.74 const StringPoolEntryType &entry = GetStringMapEntryFromKeyData(ccstr);75 return entry.getKey().size();76 }77 return 0;78 }79 80 StringPoolValueType GetMangledCounterpart(const char *ccstr) {81 if (ccstr != nullptr) {82 const PoolEntry &pool = selectPool(llvm::StringRef(ccstr));83 llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);84 return GetStringMapEntryFromKeyData(ccstr).getValue();85 }86 return nullptr;87 }88 89 const char *GetConstCString(const char *cstr) {90 if (cstr != nullptr)91 return GetConstCStringWithLength(cstr, strlen(cstr));92 return nullptr;93 }94 95 const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {96 if (cstr != nullptr)97 return GetConstCStringWithStringRef(llvm::StringRef(cstr, cstr_len));98 return nullptr;99 }100 101 const char *GetConstCStringWithStringRef(llvm::StringRef string_ref) {102 if (string_ref.data()) {103 const uint32_t string_hash = StringPool::hash(string_ref);104 PoolEntry &pool = selectPool(string_hash);105 106 {107 llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);108 auto it = pool.m_string_map.find(string_ref, string_hash);109 if (it != pool.m_string_map.end())110 return it->getKeyData();111 }112 113 llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);114 StringPoolEntryType &entry =115 *pool.m_string_map116 .insert(std::make_pair(string_ref, nullptr), string_hash)117 .first;118 return entry.getKeyData();119 }120 return nullptr;121 }122 123 const char *124 GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled,125 const char *mangled_ccstr) {126 const char *demangled_ccstr = nullptr;127 128 {129 const uint32_t demangled_hash = StringPool::hash(demangled);130 PoolEntry &pool = selectPool(demangled_hash);131 llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);132 133 // Make or update string pool entry with the mangled counterpart134 StringPool &map = pool.m_string_map;135 StringPoolEntryType &entry =136 *map.try_emplace_with_hash(demangled, demangled_hash).first;137 138 entry.second = mangled_ccstr;139 140 // Extract the const version of the demangled_cstr141 demangled_ccstr = entry.getKeyData();142 }143 144 {145 // Now assign the demangled const string as the counterpart of the146 // mangled const string...147 PoolEntry &pool = selectPool(llvm::StringRef(mangled_ccstr));148 llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);149 GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);150 }151 152 // Return the constant demangled C string153 return demangled_ccstr;154 }155 156 const char *GetConstTrimmedCStringWithLength(const char *cstr,157 size_t cstr_len) {158 if (cstr != nullptr) {159 const size_t trimmed_len = strnlen(cstr, cstr_len);160 return GetConstCStringWithLength(cstr, trimmed_len);161 }162 return nullptr;163 }164 165 ConstString::MemoryStats GetMemoryStats() const {166 ConstString::MemoryStats stats;167 for (const auto &pool : m_string_pools) {168 llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);169 const Allocator &alloc = pool.m_string_map.getAllocator();170 stats.bytes_total += alloc.getTotalMemory();171 stats.bytes_used += alloc.getBytesAllocated();172 }173 return stats;174 }175 176protected:177 struct PoolEntry {178 mutable llvm::sys::SmartRWMutex<false> m_mutex;179 StringPool m_string_map;180 };181 182 std::array<PoolEntry, 256> m_string_pools;183 184 PoolEntry &selectPool(const llvm::StringRef &s) {185 return selectPool(StringPool::hash(s));186 }187 188 PoolEntry &selectPool(uint32_t h) {189 return m_string_pools[((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff];190 }191};192 193// Frameworks and dylibs aren't supposed to have global C++ initializers so we194// hide the string pool in a static function so that it will get initialized on195// the first call to this static function.196//197// Note, for now we make the string pool a pointer to the pool, because we198// can't guarantee that some objects won't get destroyed after the global199// destructor chain is run, and trying to make sure no destructors touch200// ConstStrings is difficult. So we leak the pool instead.201static Pool &StringPool() {202 static llvm::once_flag g_pool_initialization_flag;203 static Pool *g_string_pool = nullptr;204 205 llvm::call_once(g_pool_initialization_flag,206 []() { g_string_pool = new Pool(); });207 208 return *g_string_pool;209}210 211ConstString::ConstString(const char *cstr)212 : m_string(StringPool().GetConstCString(cstr)) {}213 214ConstString::ConstString(const char *cstr, size_t cstr_len)215 : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}216 217ConstString::ConstString(llvm::StringRef s)218 : m_string(StringPool().GetConstCStringWithStringRef(s)) {}219 220bool ConstString::operator<(ConstString rhs) const {221 if (m_string == rhs.m_string)222 return false;223 224 llvm::StringRef lhs_string_ref(GetStringRef());225 llvm::StringRef rhs_string_ref(rhs.GetStringRef());226 227 // If both have valid C strings, then return the comparison228 if (lhs_string_ref.data() && rhs_string_ref.data())229 return lhs_string_ref < rhs_string_ref;230 231 // Else one of them was nullptr, so if LHS is nullptr then it is less than232 return lhs_string_ref.data() == nullptr;233}234 235Stream &lldb_private::operator<<(Stream &s, ConstString str) {236 const char *cstr = str.GetCString();237 if (cstr != nullptr)238 s << cstr;239 240 return s;241}242 243size_t ConstString::GetLength() const {244 return Pool::GetConstCStringLength(m_string);245}246 247bool ConstString::Equals(ConstString lhs, ConstString rhs,248 const bool case_sensitive) {249 if (lhs.m_string == rhs.m_string)250 return true;251 252 // Since the pointers weren't equal, and identical ConstStrings always have253 // identical pointers, the result must be false for case sensitive equality254 // test.255 if (case_sensitive)256 return false;257 258 // perform case insensitive equality test259 llvm::StringRef lhs_string_ref(lhs.GetStringRef());260 llvm::StringRef rhs_string_ref(rhs.GetStringRef());261 return lhs_string_ref.equals_insensitive(rhs_string_ref);262}263 264int ConstString::Compare(ConstString lhs, ConstString rhs,265 const bool case_sensitive) {266 // If the iterators are the same, this is the same string267 const char *lhs_cstr = lhs.m_string;268 const char *rhs_cstr = rhs.m_string;269 if (lhs_cstr == rhs_cstr)270 return 0;271 if (lhs_cstr && rhs_cstr) {272 llvm::StringRef lhs_string_ref(lhs.GetStringRef());273 llvm::StringRef rhs_string_ref(rhs.GetStringRef());274 275 if (case_sensitive) {276 return lhs_string_ref.compare(rhs_string_ref);277 } else {278 return lhs_string_ref.compare_insensitive(rhs_string_ref);279 }280 }281 282 if (lhs_cstr)283 return +1; // LHS isn't nullptr but RHS is284 else285 return -1; // LHS is nullptr but RHS isn't286}287 288void ConstString::Dump(Stream *s, const char *fail_value) const {289 if (s != nullptr) {290 const char *cstr = AsCString(fail_value);291 if (cstr != nullptr)292 s->PutCString(cstr);293 }294}295 296void ConstString::DumpDebug(Stream *s) const {297 const char *cstr = GetCString();298 size_t cstr_len = GetLength();299 // Only print the parens if we have a non-nullptr string300 const char *parens = cstr ? "\"" : "";301 s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,302 static_cast<int>(sizeof(void *) * 2),303 static_cast<const void *>(this), parens, cstr, parens,304 static_cast<uint64_t>(cstr_len));305}306 307void ConstString::SetCString(const char *cstr) {308 m_string = StringPool().GetConstCString(cstr);309}310 311void ConstString::SetString(llvm::StringRef s) {312 m_string = StringPool().GetConstCStringWithStringRef(s);313}314 315void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,316 ConstString mangled) {317 m_string = StringPool().GetConstCStringAndSetMangledCounterPart(318 demangled, mangled.m_string);319}320 321bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {322 counterpart.m_string = StringPool().GetMangledCounterpart(m_string);323 return (bool)counterpart;324}325 326void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {327 m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);328}329 330void ConstString::SetTrimmedCStringWithLength(const char *cstr,331 size_t cstr_len) {332 m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);333}334 335ConstString::MemoryStats ConstString::GetMemoryStats() {336 return StringPool().GetMemoryStats();337}338 339void llvm::format_provider<ConstString>::format(const ConstString &CS,340 llvm::raw_ostream &OS,341 llvm::StringRef Options) {342 format_provider<StringRef>::format(CS.GetStringRef(), OS, Options);343}344