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