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 
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>
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) const {
81  if (ccstr != nullptr) {
82  const uint8_t h = hash(llvm::StringRef(ccstr));
83  llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].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(const llvm::StringRef &string_ref) {
102  if (string_ref.data()) {
103  const uint8_t h = hash(string_ref);
104 
105  {
106  llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
107  auto it = m_string_pools[h].m_string_map.find(string_ref);
108  if (it != m_string_pools[h].m_string_map.end())
109  return it->getKeyData();
110  }
111 
112  llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
113  StringPoolEntryType &entry =
114  *m_string_pools[h]
115  .m_string_map.insert(std::make_pair(string_ref, nullptr))
116  .first;
117  return entry.getKeyData();
118  }
119  return nullptr;
120  }
121 
122  const char *
123  GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled,
124  const char *mangled_ccstr) {
125  const char *demangled_ccstr = nullptr;
126 
127  {
128  const uint8_t h = hash(demangled);
129  llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
130 
131  // Make or update string pool entry with the mangled counterpart
132  StringPool &map = m_string_pools[h].m_string_map;
133  StringPoolEntryType &entry = *map.try_emplace(demangled).first;
134 
135  entry.second = mangled_ccstr;
136 
137  // Extract the const version of the demangled_cstr
138  demangled_ccstr = entry.getKeyData();
139  }
140 
141  {
142  // Now assign the demangled const string as the counterpart of the
143  // mangled const string...
144  const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
145  llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
146  GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
147  }
148 
149  // Return the constant demangled C string
150  return demangled_ccstr;
151  }
152 
153  const char *GetConstTrimmedCStringWithLength(const char *cstr,
154  size_t cstr_len) {
155  if (cstr != nullptr) {
156  const size_t trimmed_len = strnlen(cstr, cstr_len);
157  return GetConstCStringWithLength(cstr, trimmed_len);
158  }
159  return nullptr;
160  }
161 
162  // Return the size in bytes that this object and any items in its collection
163  // of uniqued strings + data count values takes in memory.
164  size_t MemorySize() const {
165  size_t mem_size = sizeof(Pool);
166  for (const auto &pool : m_string_pools) {
167  llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
168  for (const auto &entry : pool.m_string_map)
169  mem_size += sizeof(StringPoolEntryType) + entry.getKey().size();
170  }
171  return mem_size;
172  }
173 
176  for (const auto &pool : m_string_pools) {
177  llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
178  const Allocator &alloc = pool.m_string_map.getAllocator();
179  stats.bytes_total += alloc.getTotalMemory();
180  stats.bytes_used += alloc.getBytesAllocated();
181  }
182  return stats;
183  }
184 
185 protected:
186  uint8_t hash(const llvm::StringRef &s) const {
187  uint32_t h = llvm::djbHash(s);
188  return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
189  }
190 
191  struct PoolEntry {
192  mutable llvm::sys::SmartRWMutex<false> m_mutex;
194  };
195 
196  std::array<PoolEntry, 256> m_string_pools;
197 };
198 
199 // Frameworks and dylibs aren't supposed to have global C++ initializers so we
200 // hide the string pool in a static function so that it will get initialized on
201 // the first call to this static function.
202 //
203 // Note, for now we make the string pool a pointer to the pool, because we
204 // can't guarantee that some objects won't get destroyed after the global
205 // destructor chain is run, and trying to make sure no destructors touch
206 // ConstStrings is difficult. So we leak the pool instead.
207 static Pool &StringPool() {
208  static llvm::once_flag g_pool_initialization_flag;
209  static Pool *g_string_pool = nullptr;
210 
211  llvm::call_once(g_pool_initialization_flag,
212  []() { g_string_pool = new Pool(); });
213 
214  return *g_string_pool;
215 }
216 
217 ConstString::ConstString(const char *cstr)
218  : m_string(StringPool().GetConstCString(cstr)) {}
219 
220 ConstString::ConstString(const char *cstr, size_t cstr_len)
221  : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
222 
223 ConstString::ConstString(const llvm::StringRef &s)
224  : m_string(StringPool().GetConstCStringWithStringRef(s)) {}
225 
227  if (m_string == rhs.m_string)
228  return false;
229 
230  llvm::StringRef lhs_string_ref(GetStringRef());
231  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
232 
233  // If both have valid C strings, then return the comparison
234  if (lhs_string_ref.data() && rhs_string_ref.data())
235  return lhs_string_ref < rhs_string_ref;
236 
237  // Else one of them was nullptr, so if LHS is nullptr then it is less than
238  return lhs_string_ref.data() == nullptr;
239 }
240 
242  const char *cstr = str.GetCString();
243  if (cstr != nullptr)
244  s << cstr;
245 
246  return s;
247 }
248 
249 size_t ConstString::GetLength() const {
251 }
252 
254  const bool case_sensitive) {
255  if (lhs.m_string == rhs.m_string)
256  return true;
257 
258  // Since the pointers weren't equal, and identical ConstStrings always have
259  // identical pointers, the result must be false for case sensitive equality
260  // test.
261  if (case_sensitive)
262  return false;
263 
264  // perform case insensitive equality test
265  llvm::StringRef lhs_string_ref(lhs.GetStringRef());
266  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
267  return lhs_string_ref.equals_insensitive(rhs_string_ref);
268 }
269 
271  const bool case_sensitive) {
272  // If the iterators are the same, this is the same string
273  const char *lhs_cstr = lhs.m_string;
274  const char *rhs_cstr = rhs.m_string;
275  if (lhs_cstr == rhs_cstr)
276  return 0;
277  if (lhs_cstr && rhs_cstr) {
278  llvm::StringRef lhs_string_ref(lhs.GetStringRef());
279  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
280 
281  if (case_sensitive) {
282  return lhs_string_ref.compare(rhs_string_ref);
283  } else {
284  return lhs_string_ref.compare_insensitive(rhs_string_ref);
285  }
286  }
287 
288  if (lhs_cstr)
289  return +1; // LHS isn't nullptr but RHS is
290  else
291  return -1; // LHS is nullptr but RHS isn't
292 }
293 
294 void ConstString::Dump(Stream *s, const char *fail_value) const {
295  if (s != nullptr) {
296  const char *cstr = AsCString(fail_value);
297  if (cstr != nullptr)
298  s->PutCString(cstr);
299  }
300 }
301 
303  const char *cstr = GetCString();
304  size_t cstr_len = GetLength();
305  // Only print the parens if we have a non-nullptr string
306  const char *parens = cstr ? "\"" : "";
307  s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,
308  static_cast<int>(sizeof(void *) * 2),
309  static_cast<const void *>(this), parens, cstr, parens,
310  static_cast<uint64_t>(cstr_len));
311 }
312 
313 void ConstString::SetCString(const char *cstr) {
315 }
316 
317 void ConstString::SetString(const llvm::StringRef &s) {
318  m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
319 }
320 
321 void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
322  ConstString mangled) {
324  demangled, mangled.m_string);
325 }
326 
329  return (bool)counterpart;
330 }
331 
332 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
333  m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
334 }
335 
337  size_t cstr_len) {
339 }
340 
342  // Get the size of the static string pool
343  return StringPool().MemorySize();
344 }
345 
347  return StringPool().GetMemoryStats();
348 }
349 
350 void llvm::format_provider<ConstString>::format(const ConstString &CS,
351  llvm::raw_ostream &OS,
352  llvm::StringRef Options) {
353  format_provider<StringRef>::format(CS.GetStringRef(), OS, Options);
354 }
355 
356 void llvm::yaml::ScalarTraits<ConstString>::output(const ConstString &Val,
357  void *, raw_ostream &Out) {
358  Out << Val.GetStringRef();
359 }
360 
361 llvm::StringRef
362 llvm::yaml::ScalarTraits<ConstString>::input(llvm::StringRef Scalar, void *,
363  ConstString &Val) {
364  Val = ConstString(Scalar);
365  return {};
366 }
Pool::GetConstCStringWithLength
const char * GetConstCStringWithLength(const char *cstr, size_t cstr_len)
Definition: ConstString.cpp:95
Pool::m_string_pools
std::array< PoolEntry, 256 > m_string_pools
Definition: ConstString.cpp:196
Pool::PoolEntry
Definition: ConstString.cpp:191
lldb_private::ConstString::MemoryStats::bytes_used
size_t bytes_used
Definition: ConstString.h:416
Pool::PoolEntry::m_string_map
StringPool m_string_map
Definition: ConstString.cpp:193
lldb_private::ConstString::Compare
static int Compare(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Compare two string objects.
Definition: ConstString.cpp:270
Pool
Definition: ConstString.cpp:30
lldb_private::Scalar
Definition: Scalar.h:34
lldb_private::ConstString::GetMangledCounterpart
bool GetMangledCounterpart(ConstString &counterpart) const
Retrieve the mangled or demangled counterpart for a mangled or demangled ConstString.
Definition: ConstString.cpp:327
Pool::StringPoolEntryType
llvm::StringMapEntry< StringPoolValueType > StringPoolEntryType
Definition: ConstString.cpp:63
lldb_private::ConstString::SetCString
void SetCString(const char *cstr)
Set the C string value.
Definition: ConstString.cpp:313
lldb_private::ConstString::AsCString
const char * AsCString(const char *value_if_empty=nullptr) const
Get the string value as a C string.
Definition: ConstString.h:193
lldb_private::Stream
Definition: Stream.h:28
lldb_private::ConstString::MemoryStats
Definition: ConstString.h:411
Pool::GetConstCStringAndSetMangledCounterPart
const char * GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled, const char *mangled_ccstr)
Definition: ConstString.cpp:123
lldb_private::ConstString::ConstString
ConstString()=default
Default constructor.
Pool::Allocator
llvm::BumpPtrAllocatorImpl< llvm::MallocAllocator, AllocatorSlabSize, SizeThreshold, AllocatorGrowthDelay > Allocator
Definition: ConstString.cpp:60
Pool::GetConstCStringWithStringRef
const char * GetConstCStringWithStringRef(const llvm::StringRef &string_ref)
Definition: ConstString.cpp:101
StringPool
static Pool & StringPool()
Definition: ConstString.cpp:207
lldb_private::Options
Definition: Options.h:57
lldb_private::ConstString::SetString
void SetString(const llvm::StringRef &s)
Definition: ConstString.cpp:317
lldb_private::ConstString::GetStringRef
llvm::StringRef GetStringRef() const
Get the string value as a llvm::StringRef.
Definition: ConstString.h:202
Pool::GetConstCStringLength
static size_t GetConstCStringLength(const char *ccstr)
Definition: ConstString.cpp:70
Pool::hash
uint8_t hash(const llvm::StringRef &s) const
Definition: ConstString.cpp:186
Pool::GetConstTrimmedCStringWithLength
const char * GetConstTrimmedCStringWithLength(const char *cstr, size_t cstr_len)
Definition: ConstString.cpp:153
lldb_private::ConstString::SetCStringWithLength
void SetCStringWithLength(const char *cstr, size_t cstr_len)
Set the C string value with length.
Definition: ConstString.cpp:332
lldb_private::ConstString
Definition: ConstString.h:40
lldb_private::ConstString::SetTrimmedCStringWithLength
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 ...
Definition: ConstString.cpp:336
Pool::StringPool
llvm::StringMap< StringPoolValueType, Allocator > StringPool
Definition: ConstString.cpp:62
lldb_private::ConstString::MemoryStats::bytes_total
size_t bytes_total
Definition: ConstString.h:415
Pool::GetMemoryStats
ConstString::MemoryStats GetMemoryStats() const
Definition: ConstString.cpp:174
lldb_private::ConstString::GetLength
size_t GetLength() const
Get the length in bytes of string value.
Definition: ConstString.cpp:249
lldb_private::ConstString::DumpDebug
void DumpDebug(Stream *s) const
Dump the object debug description to a stream.
Definition: ConstString.cpp:302
lldb_private::ConstString::Dump
void Dump(Stream *s, const char *value_if_empty=nullptr) const
Dump the object description to a stream.
Definition: ConstString.cpp:294
Pool::GetMangledCounterpart
StringPoolValueType GetMangledCounterpart(const char *ccstr) const
Definition: ConstString.cpp:80
Pool::MemorySize
size_t MemorySize() const
Definition: ConstString.cpp:164
lldb_private::ConstString::operator<
bool operator<(ConstString rhs) const
Definition: ConstString.cpp:226
lldb_private::ConstString::Equals
static bool Equals(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Equal to operator.
Definition: ConstString.cpp:253
uint32_t
lldb_private::operator<<
Stream & operator<<(Stream &s, const SourceLocationSpec &loc)
Dump a SourceLocationSpec object to a stream.
Definition: SourceLocationSpec.cpp:40
Pool::GetConstCString
const char * GetConstCString(const char *cstr)
Definition: ConstString.cpp:89
lldb_private::ConstString::GetMemoryStats
static MemoryStats GetMemoryStats()
Definition: ConstString.cpp:346
lldb_private::ConstString::SetStringWithMangledCounterpart
void SetStringWithMangledCounterpart(llvm::StringRef demangled, ConstString mangled)
Set the C string value and its mangled counterpart.
Definition: ConstString.cpp:321
lldb_private::ConstString::GetCString
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:216
lldb_private::Stream::Printf
size_t Printf(const char *format,...) __attribute__((format(printf
Output printf formatted output to the stream.
Definition: Stream.cpp:107
lldb_private::ConstString::StaticMemorySize
static size_t StaticMemorySize()
Get the size in bytes of the current global string pool.
Definition: ConstString.cpp:341
lldb_private
A class that represents a running process on the host machine.
Definition: SBCommandInterpreterRunOptions.h:16
ConstString.h
Stream.h
Pool::PoolEntry::m_mutex
llvm::sys::SmartRWMutex< false > m_mutex
Definition: ConstString.cpp:192
lldb_private::Stream::PutCString
size_t PutCString(llvm::StringRef cstr)
Output a C string to the stream.
Definition: Stream.cpp:63
Pool::StringPoolValueType
const typedef char * StringPoolValueType
Definition: ConstString.cpp:61
lldb_private::ConstString::m_string
const char * m_string
Definition: ConstString.h:430
Pool::GetStringMapEntryFromKeyData
static StringPoolEntryType & GetStringMapEntryFromKeyData(const char *keyData)
Definition: ConstString.cpp:66