1 //===-- ConstString.cpp -----------------------------------------*- C++ -*-===//
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 <inttypes.h>
25 #include <stdint.h>
26 #include <string.h>
27 
28 using namespace lldb_private;
29 
30 class Pool {
31 public:
32   typedef const char *StringPoolValueType;
33   typedef llvm::StringMap<StringPoolValueType, llvm::BumpPtrAllocator>
34       StringPool;
35   typedef llvm::StringMapEntry<StringPoolValueType> StringPoolEntryType;
36 
37   static StringPoolEntryType &
38   GetStringMapEntryFromKeyData(const char *keyData) {
39     return StringPoolEntryType::GetStringMapEntryFromKeyData(keyData);
40   }
41 
42   static size_t GetConstCStringLength(const char *ccstr) {
43     if (ccstr != nullptr) {
44       // Since the entry is read only, and we derive the entry entirely from
45       // the pointer, we don't need the lock.
46       const StringPoolEntryType &entry = GetStringMapEntryFromKeyData(ccstr);
47       return entry.getKey().size();
48     }
49     return 0;
50   }
51 
52   StringPoolValueType GetMangledCounterpart(const char *ccstr) const {
53     if (ccstr != nullptr) {
54       const uint8_t h = hash(llvm::StringRef(ccstr));
55       llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
56       return GetStringMapEntryFromKeyData(ccstr).getValue();
57     }
58     return nullptr;
59   }
60 
61   const char *GetConstCString(const char *cstr) {
62     if (cstr != nullptr)
63       return GetConstCStringWithLength(cstr, strlen(cstr));
64     return nullptr;
65   }
66 
67   const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {
68     if (cstr != nullptr)
69       return GetConstCStringWithStringRef(llvm::StringRef(cstr, cstr_len));
70     return nullptr;
71   }
72 
73   const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) {
74     if (string_ref.data()) {
75       const uint8_t h = hash(string_ref);
76 
77       {
78         llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
79         auto it = m_string_pools[h].m_string_map.find(string_ref);
80         if (it != m_string_pools[h].m_string_map.end())
81           return it->getKeyData();
82       }
83 
84       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
85       StringPoolEntryType &entry =
86           *m_string_pools[h]
87                .m_string_map.insert(std::make_pair(string_ref, nullptr))
88                .first;
89       return entry.getKeyData();
90     }
91     return nullptr;
92   }
93 
94   const char *
95   GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled,
96                                           const char *mangled_ccstr) {
97     const char *demangled_ccstr = nullptr;
98 
99     {
100       const uint8_t h = hash(demangled);
101       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
102 
103       // Make or update string pool entry with the mangled counterpart
104       StringPool &map = m_string_pools[h].m_string_map;
105       StringPoolEntryType &entry = *map.try_emplace(demangled).first;
106 
107       entry.second = mangled_ccstr;
108 
109       // Extract the const version of the demangled_cstr
110       demangled_ccstr = entry.getKeyData();
111     }
112 
113     {
114       // Now assign the demangled const string as the counterpart of the
115       // mangled const string...
116       const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
117       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
118       GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
119     }
120 
121     // Return the constant demangled C string
122     return demangled_ccstr;
123   }
124 
125   const char *GetConstTrimmedCStringWithLength(const char *cstr,
126                                                size_t cstr_len) {
127     if (cstr != nullptr) {
128       const size_t trimmed_len = strnlen(cstr, cstr_len);
129       return GetConstCStringWithLength(cstr, trimmed_len);
130     }
131     return nullptr;
132   }
133 
134   // Return the size in bytes that this object and any items in its collection
135   // of uniqued strings + data count values takes in memory.
136   size_t MemorySize() const {
137     size_t mem_size = sizeof(Pool);
138     for (const auto &pool : m_string_pools) {
139       llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
140       for (const auto &entry : pool.m_string_map)
141         mem_size += sizeof(StringPoolEntryType) + entry.getKey().size();
142     }
143     return mem_size;
144   }
145 
146 protected:
147   uint8_t hash(const llvm::StringRef &s) const {
148     uint32_t h = llvm::djbHash(s);
149     return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
150   }
151 
152   struct PoolEntry {
153     mutable llvm::sys::SmartRWMutex<false> m_mutex;
154     StringPool m_string_map;
155   };
156 
157   std::array<PoolEntry, 256> m_string_pools;
158 };
159 
160 // Frameworks and dylibs aren't supposed to have global C++ initializers so we
161 // hide the string pool in a static function so that it will get initialized on
162 // the first call to this static function.
163 //
164 // Note, for now we make the string pool a pointer to the pool, because we
165 // can't guarantee that some objects won't get destroyed after the global
166 // destructor chain is run, and trying to make sure no destructors touch
167 // ConstStrings is difficult.  So we leak the pool instead.
168 static Pool &StringPool() {
169   static llvm::once_flag g_pool_initialization_flag;
170   static Pool *g_string_pool = nullptr;
171 
172   llvm::call_once(g_pool_initialization_flag,
173                  []() { g_string_pool = new Pool(); });
174 
175   return *g_string_pool;
176 }
177 
178 ConstString::ConstString(const char *cstr)
179     : m_string(StringPool().GetConstCString(cstr)) {}
180 
181 ConstString::ConstString(const char *cstr, size_t cstr_len)
182     : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
183 
184 ConstString::ConstString(const llvm::StringRef &s)
185     : m_string(StringPool().GetConstCStringWithStringRef(s)) {}
186 
187 bool ConstString::operator<(ConstString rhs) const {
188   if (m_string == rhs.m_string)
189     return false;
190 
191   llvm::StringRef lhs_string_ref(GetStringRef());
192   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
193 
194   // If both have valid C strings, then return the comparison
195   if (lhs_string_ref.data() && rhs_string_ref.data())
196     return lhs_string_ref < rhs_string_ref;
197 
198   // Else one of them was nullptr, so if LHS is nullptr then it is less than
199   return lhs_string_ref.data() == nullptr;
200 }
201 
202 Stream &lldb_private::operator<<(Stream &s, ConstString str) {
203   const char *cstr = str.GetCString();
204   if (cstr != nullptr)
205     s << cstr;
206 
207   return s;
208 }
209 
210 size_t ConstString::GetLength() const {
211   return Pool::GetConstCStringLength(m_string);
212 }
213 
214 bool ConstString::Equals(ConstString lhs, ConstString rhs,
215                          const bool case_sensitive) {
216   if (lhs.m_string == rhs.m_string)
217     return true;
218 
219   // Since the pointers weren't equal, and identical ConstStrings always have
220   // identical pointers, the result must be false for case sensitive equality
221   // test.
222   if (case_sensitive)
223     return false;
224 
225   // perform case insensitive equality test
226   llvm::StringRef lhs_string_ref(lhs.GetStringRef());
227   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
228   return lhs_string_ref.equals_lower(rhs_string_ref);
229 }
230 
231 int ConstString::Compare(ConstString lhs, ConstString rhs,
232                          const bool case_sensitive) {
233   // If the iterators are the same, this is the same string
234   const char *lhs_cstr = lhs.m_string;
235   const char *rhs_cstr = rhs.m_string;
236   if (lhs_cstr == rhs_cstr)
237     return 0;
238   if (lhs_cstr && rhs_cstr) {
239     llvm::StringRef lhs_string_ref(lhs.GetStringRef());
240     llvm::StringRef rhs_string_ref(rhs.GetStringRef());
241 
242     if (case_sensitive) {
243       return lhs_string_ref.compare(rhs_string_ref);
244     } else {
245       return lhs_string_ref.compare_lower(rhs_string_ref);
246     }
247   }
248 
249   if (lhs_cstr)
250     return +1; // LHS isn't nullptr but RHS is
251   else
252     return -1; // LHS is nullptr but RHS isn't
253 }
254 
255 void ConstString::Dump(Stream *s, const char *fail_value) const {
256   if (s != nullptr) {
257     const char *cstr = AsCString(fail_value);
258     if (cstr != nullptr)
259       s->PutCString(cstr);
260   }
261 }
262 
263 void ConstString::DumpDebug(Stream *s) const {
264   const char *cstr = GetCString();
265   size_t cstr_len = GetLength();
266   // Only print the parens if we have a non-nullptr string
267   const char *parens = cstr ? "\"" : "";
268   s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,
269             static_cast<int>(sizeof(void *) * 2),
270             static_cast<const void *>(this), parens, cstr, parens,
271             static_cast<uint64_t>(cstr_len));
272 }
273 
274 void ConstString::SetCString(const char *cstr) {
275   m_string = StringPool().GetConstCString(cstr);
276 }
277 
278 void ConstString::SetString(const llvm::StringRef &s) {
279   m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
280 }
281 
282 void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
283                                                    ConstString mangled) {
284   m_string = StringPool().GetConstCStringAndSetMangledCounterPart(
285       demangled, mangled.m_string);
286 }
287 
288 bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {
289   counterpart.m_string = StringPool().GetMangledCounterpart(m_string);
290   return (bool)counterpart;
291 }
292 
293 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
294   m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
295 }
296 
297 void ConstString::SetTrimmedCStringWithLength(const char *cstr,
298                                               size_t cstr_len) {
299   m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);
300 }
301 
302 size_t ConstString::StaticMemorySize() {
303   // Get the size of the static string pool
304   return StringPool().MemorySize();
305 }
306 
307 void llvm::format_provider<ConstString>::format(const ConstString &CS,
308                                                 llvm::raw_ostream &OS,
309                                                 llvm::StringRef Options) {
310   format_provider<StringRef>::format(CS.AsCString(), OS, Options);
311 }
312