lldb/source/Utility/ConstString.cpp

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