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