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 
164  for (const auto &pool : m_string_pools) {
165  llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
166  const Allocator &alloc = pool.m_string_map.getAllocator();
167  stats.bytes_total += alloc.getTotalMemory();
168  stats.bytes_used += alloc.getBytesAllocated();
169  }
170  return stats;
171  }
172 
173 protected:
174  uint8_t hash(const llvm::StringRef &s) const {
175  uint32_t h = llvm::djbHash(s);
176  return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
177  }
178 
179  struct PoolEntry {
180  mutable llvm::sys::SmartRWMutex<false> m_mutex;
182  };
183 
184  std::array<PoolEntry, 256> m_string_pools;
185 };
186 
187 // Frameworks and dylibs aren't supposed to have global C++ initializers so we
188 // hide the string pool in a static function so that it will get initialized on
189 // the first call to this static function.
190 //
191 // Note, for now we make the string pool a pointer to the pool, because we
192 // can't guarantee that some objects won't get destroyed after the global
193 // destructor chain is run, and trying to make sure no destructors touch
194 // ConstStrings is difficult. So we leak the pool instead.
195 static Pool &StringPool() {
196  static llvm::once_flag g_pool_initialization_flag;
197  static Pool *g_string_pool = nullptr;
198 
199  llvm::call_once(g_pool_initialization_flag,
200  []() { g_string_pool = new Pool(); });
201 
202  return *g_string_pool;
203 }
204 
205 ConstString::ConstString(const char *cstr)
206  : m_string(StringPool().GetConstCString(cstr)) {}
207 
208 ConstString::ConstString(const char *cstr, size_t cstr_len)
209  : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
210 
211 ConstString::ConstString(const llvm::StringRef &s)
212  : m_string(StringPool().GetConstCStringWithStringRef(s)) {}
213 
215  if (m_string == rhs.m_string)
216  return false;
217 
218  llvm::StringRef lhs_string_ref(GetStringRef());
219  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
220 
221  // If both have valid C strings, then return the comparison
222  if (lhs_string_ref.data() && rhs_string_ref.data())
223  return lhs_string_ref < rhs_string_ref;
224 
225  // Else one of them was nullptr, so if LHS is nullptr then it is less than
226  return lhs_string_ref.data() == nullptr;
227 }
228 
230  const char *cstr = str.GetCString();
231  if (cstr != nullptr)
232  s << cstr;
233 
234  return s;
235 }
236 
237 size_t ConstString::GetLength() const {
239 }
240 
242  const bool case_sensitive) {
243  if (lhs.m_string == rhs.m_string)
244  return true;
245 
246  // Since the pointers weren't equal, and identical ConstStrings always have
247  // identical pointers, the result must be false for case sensitive equality
248  // test.
249  if (case_sensitive)
250  return false;
251 
252  // perform case insensitive equality test
253  llvm::StringRef lhs_string_ref(lhs.GetStringRef());
254  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
255  return lhs_string_ref.equals_insensitive(rhs_string_ref);
256 }
257 
259  const bool case_sensitive) {
260  // If the iterators are the same, this is the same string
261  const char *lhs_cstr = lhs.m_string;
262  const char *rhs_cstr = rhs.m_string;
263  if (lhs_cstr == rhs_cstr)
264  return 0;
265  if (lhs_cstr && rhs_cstr) {
266  llvm::StringRef lhs_string_ref(lhs.GetStringRef());
267  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
268 
269  if (case_sensitive) {
270  return lhs_string_ref.compare(rhs_string_ref);
271  } else {
272  return lhs_string_ref.compare_insensitive(rhs_string_ref);
273  }
274  }
275 
276  if (lhs_cstr)
277  return +1; // LHS isn't nullptr but RHS is
278  else
279  return -1; // LHS is nullptr but RHS isn't
280 }
281 
282 void ConstString::Dump(Stream *s, const char *fail_value) const {
283  if (s != nullptr) {
284  const char *cstr = AsCString(fail_value);
285  if (cstr != nullptr)
286  s->PutCString(cstr);
287  }
288 }
289 
291  const char *cstr = GetCString();
292  size_t cstr_len = GetLength();
293  // Only print the parens if we have a non-nullptr string
294  const char *parens = cstr ? "\"" : "";
295  s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,
296  static_cast<int>(sizeof(void *) * 2),
297  static_cast<const void *>(this), parens, cstr, parens,
298  static_cast<uint64_t>(cstr_len));
299 }
300 
301 void ConstString::SetCString(const char *cstr) {
303 }
304 
305 void ConstString::SetString(const llvm::StringRef &s) {
306  m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
307 }
308 
309 void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
310  ConstString mangled) {
312  demangled, mangled.m_string);
313 }
314 
317  return (bool)counterpart;
318 }
319 
320 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
321  m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
322 }
323 
325  size_t cstr_len) {
327 }
328 
330  return StringPool().GetMemoryStats();
331 }
332 
333 void llvm::format_provider<ConstString>::format(const ConstString &CS,
334  llvm::raw_ostream &OS,
335  llvm::StringRef Options) {
336  format_provider<StringRef>::format(CS.GetStringRef(), OS, Options);
337 }
338 
339 void llvm::yaml::ScalarTraits<ConstString>::output(const ConstString &Val,
340  void *, raw_ostream &Out) {
341  Out << Val.GetStringRef();
342 }
343 
344 llvm::StringRef
345 llvm::yaml::ScalarTraits<ConstString>::input(llvm::StringRef Scalar, void *,
346  ConstString &Val) {
347  Val = ConstString(Scalar);
348  return {};
349 }
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:184
Pool::PoolEntry
Definition: ConstString.cpp:179
lldb_private::ConstString::MemoryStats::bytes_used
size_t bytes_used
Definition: ConstString.h:404
Pool::PoolEntry::m_string_map
StringPool m_string_map
Definition: ConstString.cpp:181
lldb_private::ConstString::Compare
static int Compare(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Compare two string objects.
Definition: ConstString.cpp:258
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:315
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:301
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:399
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:195
lldb_private::Options
Definition: Options.h:57
lldb_private::ConstString::SetString
void SetString(const llvm::StringRef &s)
Definition: ConstString.cpp:305
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:174
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:320
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:324
Pool::StringPool
llvm::StringMap< StringPoolValueType, Allocator > StringPool
Definition: ConstString.cpp:62
lldb_private::ConstString::MemoryStats::bytes_total
size_t bytes_total
Definition: ConstString.h:403
Pool::GetMemoryStats
ConstString::MemoryStats GetMemoryStats() const
Definition: ConstString.cpp:162
lldb_private::ConstString::GetLength
size_t GetLength() const
Get the length in bytes of string value.
Definition: ConstString.cpp:237
lldb_private::ConstString::DumpDebug
void DumpDebug(Stream *s) const
Dump the object debug description to a stream.
Definition: ConstString.cpp:290
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:282
Pool::GetMangledCounterpart
StringPoolValueType GetMangledCounterpart(const char *ccstr) const
Definition: ConstString.cpp:80
lldb_private::ConstString::operator<
bool operator<(ConstString rhs) const
Definition: ConstString.cpp:214
lldb_private::ConstString::Equals
static bool Equals(ConstString lhs, ConstString rhs, const bool case_sensitive=true)
Equal to operator.
Definition: ConstString.cpp:241
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:329
lldb_private::ConstString::SetStringWithMangledCounterpart
void SetStringWithMangledCounterpart(llvm::StringRef demangled, ConstString mangled)
Set the C string value and its mangled counterpart.
Definition: ConstString.cpp:309
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
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:180
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:418
Pool::GetStringMapEntryFromKeyData
static StringPoolEntryType & GetStringMapEntryFromKeyData(const char *keyData)
Definition: ConstString.cpp:66