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
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,
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(keyData: 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(s: llvm::StringRef(ccstr));
83 llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
84 return GetStringMapEntryFromKeyData(keyData: ccstr).getValue();
85 }
86 return nullptr;
87 }
88
89 const char *GetConstCString(const char *cstr) {
90 if (cstr != nullptr)
91 return GetConstCStringWithLength(cstr, cstr_len: strlen(s: cstr));
92 return nullptr;
93 }
94
95 const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {
96 if (cstr != nullptr)
97 return GetConstCStringWithStringRef(string_ref: 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(Key: string_ref);
104 PoolEntry &pool = selectPool(h: string_hash);
105
106 {
107 llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
108 auto it = pool.m_string_map.find(Key: string_ref, FullHashValue: 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(KV: std::make_pair(x&: string_ref, y: nullptr), FullHashValue: 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(Key: demangled);
130 PoolEntry &pool = selectPool(h: 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(Key: demangled, FullHashValue: 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(s: llvm::StringRef(mangled_ccstr));
148 llvm::sys::SmartScopedWriter<false> wlock(pool.m_mutex);
149 GetStringMapEntryFromKeyData(keyData: 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(string: cstr, maxlen: cstr_len);
160 return GetConstCStringWithLength(cstr, cstr_len: 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(h: StringPool::hash(Key: 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(flag&: g_pool_initialization_flag,
206 F: []() { 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(string_ref: 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 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
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(ccstr: 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 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: 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 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: rhs_string_ref);
277 } else {
278 return lhs_string_ref.compare_insensitive(RHS: 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(value_if_empty: 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 string
300 const char *parens = cstr ? "\"" : "";
301 s->Printf(format: "%*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(string_ref: s);
313}
314
315void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
316 ConstString mangled) {
317 m_string = StringPool().GetConstCStringAndSetMangledCounterPart(
318 demangled, mangled_ccstr: mangled.m_string);
319}
320
321bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {
322 counterpart.m_string = StringPool().GetMangledCounterpart(ccstr: 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(V: CS.GetStringRef(), Stream&: OS, Style: Options);
343}
344

source code of lldb/source/Utility/ConstString.cpp