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-exception 6 // 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 28 using namespace lldb_private; 29 30 class Pool { 31 public: 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 of 36 /// the ConstString allocations. This means that when allocating many 37 /// ConstStrings, every allocator sees only its small share of allocations and 38 /// assumes LLDB only allocated a small amount of memory so far. In reality 39 /// LLDB allocated a total memory that is N times as large as what the 40 /// allocator sees (where N is the number of string pools). This causes that 41 /// the BumpPtrAllocator continues a long time to allocate memory in small 42 /// chunks which only makes sense when allocating a small amount of memory 43 /// (which is true from the perspective of a single allocator). On some 44 /// systems doing all these small memory allocations causes LLDB to spend 45 /// a lot of time in malloc, so we need to force all these allocators to 46 /// behave like one allocator in terms of scaling their memory allocations 47 /// with increased demand. To do this we set the growth delay for each single 48 /// allocator to a rate so that our pool of allocators scales their memory 49 /// allocations similar to a single BumpPtrAllocatorImpl. 50 /// 51 /// Currently we have 256 string pools and the normal growth delay of the 52 /// BumpPtrAllocatorImpl is 128 (i.e., the memory allocation size increases 53 /// every 128 full chunks), so by changing the delay to 1 we get a 54 /// total growth delay in our allocator collection of 256/1 = 256. This is 55 /// still only half as fast as a normal allocator but we can't go any faster 56 /// 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 from 73 // 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_map 116 .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 counterpart 134 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_cstr 141 demangled_ccstr = entry.getKeyData(); 142 } 143 144 { 145 // Now assign the demangled const string as the counterpart of the 146 // 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 string 153 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 176 protected: 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 we 194 // hide the string pool in a static function so that it will get initialized on 195 // the first call to this static function. 196 // 197 // Note, for now we make the string pool a pointer to the pool, because we 198 // can't guarantee that some objects won't get destroyed after the global 199 // destructor chain is run, and trying to make sure no destructors touch 200 // ConstStrings is difficult. So we leak the pool instead. 201 static 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 211 ConstString::ConstString(const char *cstr) 212 : m_string(StringPool().GetConstCString(cstr)) {} 213 214 ConstString::ConstString(const char *cstr, size_t cstr_len) 215 : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {} 216 217 ConstString::ConstString(llvm::StringRef s) 218 : m_string(StringPool().GetConstCStringWithStringRef(s)) {} 219 220 bool 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 comparison 228 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 than 232 return lhs_string_ref.data() == nullptr; 233 } 234 235 Stream &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 243 size_t ConstString::GetLength() const { 244 return Pool::GetConstCStringLength(m_string); 245 } 246 247 bool 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 have 253 // identical pointers, the result must be false for case sensitive equality 254 // test. 255 if (case_sensitive) 256 return false; 257 258 // perform case insensitive equality test 259 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 264 int ConstString::Compare(ConstString lhs, ConstString rhs, 265 const bool case_sensitive) { 266 // If the iterators are the same, this is the same string 267 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 is 284 else 285 return -1; // LHS is nullptr but RHS isn't 286 } 287 288 void 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 296 void 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 string 300 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 307 void ConstString::SetCString(const char *cstr) { 308 m_string = StringPool().GetConstCString(cstr); 309 } 310 311 void ConstString::SetString(llvm::StringRef s) { 312 m_string = StringPool().GetConstCStringWithStringRef(s); 313 } 314 315 void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled, 316 ConstString mangled) { 317 m_string = StringPool().GetConstCStringAndSetMangledCounterPart( 318 demangled, mangled.m_string); 319 } 320 321 bool ConstString::GetMangledCounterpart(ConstString &counterpart) const { 322 counterpart.m_string = StringPool().GetMangledCounterpart(m_string); 323 return (bool)counterpart; 324 } 325 326 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) { 327 m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len); 328 } 329 330 void ConstString::SetTrimmedCStringWithLength(const char *cstr, 331 size_t cstr_len) { 332 m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len); 333 } 334 335 ConstString::MemoryStats ConstString::GetMemoryStats() { 336 return StringPool().GetMemoryStats(); 337 } 338 339 void 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