LLDB mainline
ConstString.cpp
Go to the documentation of this file.
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
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 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,
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.
75 return entry.getKey().size();
76 }
77 return 0;
78 }
79
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 *
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
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;
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.
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
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
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
236 const char *cstr = str.GetCString();
237 if (cstr != nullptr)
238 s << cstr;
239
240 return s;
241}
242
245}
246
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
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
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
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
307void ConstString::SetCString(const char *cstr) {
309}
310
311void ConstString::SetString(llvm::StringRef s) {
313}
314
315void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
316 ConstString mangled) {
318 demangled, mangled.m_string);
319}
320
323 return (bool)counterpart;
324}
325
326void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
328}
329
331 size_t cstr_len) {
333}
334
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}
static Pool & StringPool()
PoolEntry & selectPool(const llvm::StringRef &s)
static const size_t SizeThreshold
Definition: ConstString.cpp:34
static StringPoolEntryType & GetStringMapEntryFromKeyData(const char *keyData)
Definition: ConstString.cpp:66
const char * GetConstCStringWithStringRef(llvm::StringRef string_ref)
static const size_t AllocatorSlabSize
The default BumpPtrAllocatorImpl slab size.
Definition: ConstString.cpp:33
llvm::StringMap< StringPoolValueType, Allocator > StringPool
Definition: ConstString.cpp:62
const char * GetConstCStringWithLength(const char *cstr, size_t cstr_len)
Definition: ConstString.cpp:95
const char * GetConstTrimmedCStringWithLength(const char *cstr, size_t cstr_len)
ConstString::MemoryStats GetMemoryStats() const
llvm::BumpPtrAllocatorImpl< llvm::MallocAllocator, AllocatorSlabSize, SizeThreshold, AllocatorGrowthDelay > Allocator
Definition: ConstString.cpp:60
std::array< PoolEntry, 256 > m_string_pools
const char * GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled, const char *mangled_ccstr)
llvm::StringMapEntry< StringPoolValueType > StringPoolEntryType
Definition: ConstString.cpp:63
const char * GetConstCString(const char *cstr)
Definition: ConstString.cpp:89
PoolEntry & selectPool(uint32_t h)
static const size_t AllocatorGrowthDelay
Every Pool has its own allocator which receives an equal share of the ConstString allocations.
Definition: ConstString.cpp:57
const char * StringPoolValueType
Definition: ConstString.cpp:61
StringPoolValueType GetMangledCounterpart(const char *ccstr)
Definition: ConstString.cpp:80
static size_t GetConstCStringLength(const char *ccstr)
Definition: ConstString.cpp:70
A uniqued constant string class.
Definition: ConstString.h:40
bool GetMangledCounterpart(ConstString &counterpart) const
Retrieve the mangled or demangled counterpart for a mangled or demangled ConstString.
static MemoryStats GetMemoryStats()
void SetCStringWithLength(const char *cstr, size_t cstr_len)
Set the C string value with length.
void SetCString(const char *cstr)
Set the C string value.
static int Compare(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Compare two string objects.
ConstString()=default
Default constructor.
const char * AsCString(const char *value_if_empty=nullptr) const
Get the string value as a C string.
Definition: ConstString.h:188
void Dump(Stream *s, const char *value_if_empty=nullptr) const
Dump the object description to a stream.
static bool Equals(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Equal to operator.
void DumpDebug(Stream *s) const
Dump the object debug description to a stream.
void SetTrimmedCStringWithLength(const char *cstr, size_t fixed_cstr_len)
Set the C string value with the minimum length between fixed_cstr_len and the actual length of the C ...
size_t GetLength() const
Get the length in bytes of string value.
llvm::StringRef GetStringRef() const
Get the string value as a llvm::StringRef.
Definition: ConstString.h:197
void SetString(llvm::StringRef s)
bool operator<(ConstString rhs) const
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:214
void SetStringWithMangledCounterpart(llvm::StringRef demangled, ConstString mangled)
Set the C string value and its mangled counterpart.
A command line option parsing protocol class.
Definition: Options.h:58
A stream class that can stream formatted output to a file.
Definition: Stream.h:28
size_t Printf(const char *format,...) __attribute__((format(printf
Output printf formatted output to the stream.
Definition: Stream.cpp:134
size_t PutCString(llvm::StringRef cstr)
Output a C string to the stream.
Definition: Stream.cpp:65
A class that represents a running process on the host machine.
Definition: SBAttachInfo.h:14
Stream & operator<<(Stream &s, const Mangled &obj)
StringPool m_string_map
llvm::sys::SmartRWMutex< false > m_mutex