[lldb] save ConstString hash value to cache files too

[llunak]

Summary

Creating ConstString requires to compute the hash value of the string. When starting LLDB with index cache enabled and everything cached, profiling shows the computing of the hash to be ~10% of the startup time here. Saving the hash value in the cache too and reusing it can save that time. The size of cache files appear to increase by ~3%.

This requires D122974.

[llunak]

Added missing hash write to EncodeCStrMap().

[llunak]

This makes TestDecodeCStringMaps fail. Is there an easy way for me to re-generate the data for the test?

[clayborg]

A few things we might think of for this patch to improve it a bit: we use a StringTableReader and ConstStringTable to read and write a string table to disk, we could save the hashes before each string in the string table data itself. Then we don't need to change the format of any other sections (the symbol table or the manual DWARF index as we would always write out string table offsets just like before, but the offsets would be different since we would always write the hash + string into the string table data. It is ok for the string table data to contain the hashes for all strings since we store only ConstString values and we always need the hashes. This might save on some space since we would only have 1 hash per string instead of possible many hashes for the same string offset in the string table.

Then we have the option to be able to support loading older string tables in StringTableReader.

Right now when we encode the "ConstStringTable" we write out:

static const llvm::StringRef kStringTableIdentifier("STAB");

We would start writing out a newer identifier like:

static const llvm::StringRef kStringTableIdentifier("STB2");

If we wanted to support the older and newer string table formats, when we call StringTableReader::Decode, we can read the identifier and "do the right thing". On the "STAB" case we would read only the strings and then we could calculate the hashes on the fly if/when needed. In the "STB2" case, the string table would have the hash followed by the string, so if we had the string table offset for any string, we could subtract 4 from this and grab the already computed hash.

Or we can rely on updating the versions of each section. I would vote to allow us to load older and newer string tables if possible. If an older LLDB tries to load a cache file and the "STAB" string table doesn't match because it is the newer "STB2", then decoding will fail on older LLDBs.

Many times we have clients with older and newer LLDB binaries installed on the same system. I am trying to look for ways to make sure they don't keep overwriting each other's cache files. Another option would be to start using different cache file names instead of changing the version number by modifying "ManualDWARFIndex::GetCacheKey()" and Symtab::GetCacheKey() to change the cache file name a bit (use "-symtab2-" instead of "-symtab-"). I am open to suggestions.

In D124704#3484539, @llunak wrote:

This makes TestDecodeCStringMaps fail. Is there an easy way for me to re-generate the data for the test?

You can regenerate the data by:

• run yaml2obj on the YAML from the TestDecodeCStringMaps function
• start LLDB and enable the cache
• load the a.out binary from step 1 that was created by the YAML and let it save a new cache file
• grab the cache file from the cache directory for this file and run "hexdump" on it
• edit out the mod time from the signature manually, otherwise when the object file is created from yaml, mod time won't match and it will fail to load

lldb/source/Core/Mangled.cpp

435–437

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

438–439

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

443–448

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

494–495

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

497–498

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

500–502

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

lldb/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

509

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

523–527

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

585–586

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp

105–106

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

112–113

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

133–134

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

lldb/source/Symbol/Symtab.cpp

1198–1199

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

1214

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

1234

If we let the string table handle also store the string hash data, then this code doesn't need to change at all.

1241

remove

1263–1264

Remove

1316–1320

remove

[llunak]

In D124704#3486971, @clayborg wrote:

A few things we might think of for this patch to improve it a bit: we use a StringTableReader and ConstStringTable to read and write a string table to disk, we could save the hashes before each string in the string table data itself. Then we don't need to change the format of any other sections (the symbol table or the manual DWARF index as we would always write out string table offsets just like before, but the offsets would be different since we would always write the hash + string into the string table data. It is ok for the string table data to contain the hashes for all strings since we store only ConstString values and we always need the hashes. This might save on some space since we would only have 1 hash per string instead of possible many hashes for the same string offset in the string table.

Makes sense.

Many times we have clients with older and newer LLDB binaries installed on the same system. I am trying to look for ways to make sure they don't keep overwriting each other's cache files.

This does not make sense to me. I can possibly imagine it with different users on the same system, but same user? If I have a newer LLDB installed, why would I also use an older one?

Another option would be to start using different cache file names instead of changing the version number by modifying "ManualDWARFIndex::GetCacheKey()" and Symtab::GetCacheKey() to change the cache file name a bit (use "-symtab2-" instead of "-symtab-").

If really needed, then I think this is better. Caches are relatively cheap and throw-away, so IMO it doesn't make much sense to have an ability to read older versions.

[llunak]

Hashes are saved directly in string table.
Changed filenames of cache files to be different from version 1.
No support for reading old format.

[llunak]

lldb/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

509

I have changed this, because it's now also a part of the filename.

[clayborg]

Great changes, just a few fixes and this looks great!

lldb/include/lldb/Core/DataFileCache.h

216–219

I would just change these two variables "m_data" and "m_needByteSwap" to be a DataExtractor

lldb/source/Core/DataFileCache.cpp

272

I would still vote to not use this string or add the hash check.

279

Remove hash check as it isn't needed. We will bump the version if needed or change the filename again.

305–309

Remove, we can version bump or rename the cache file again if needed.

306–309

Fix comment since the empty string is now at offset 4, not zero since we emit the hash first.

309–312

If we use a "DataExtractor m_data;" as our ivar as suggested, this just becomes:

317–320

321

lldb/source/Utility/ConstString.cpp

343

Do we want to add the expensive check here?

347

Does our string pool not cache the hash? I don't believe it does, but if it does and we could access that here, it would be great.

[llunak]

lldb/source/Utility/ConstString.cpp

347

StringMap does include the full hash value, but I think one would need to have the hash value first in order to find it in the map.

[llunak]

• use DataExtractor in StringTableReader
• rely on StringMap assert to check that hash algorithm has not changed

[clayborg]

One small nit in the code you can choose to fix or not. LGTM. Thanks for the improvements!

lldb/source/Core/DataFileCache.cpp

266–267

NIT: we can combine these two lines

[llunak]

Added a unittest that explicitly checks the implementation of the hash value has not changed (+ comments on what to do if that ever happens).

lldb/include/lldb/Core/DataFileCache.h

 //===-- DataFileCache.h -----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_CORE_DATAFILECACHE_H
 #define LLDB_CORE_DATAFILECACHE_H
 
+#include "lldb/Utility/DataExtractor.h"
 #include "lldb/Utility/FileSpec.h"
 #include "lldb/Utility/Status.h"
 #include "lldb/Utility/UUID.h"
 #include "lldb/lldb-forward.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Caching.h"
 #include <mutex>
 
public:
   ///   string. Duplicate strings that get inserted will return the same
   ///   byte offset.
   uint32_t Add(ConstString s);
 
   bool Encode(DataEncoder &encoder);
 
 private:
   std::vector<ConstString> m_strings;
+  /// Note that Encode() will store uint32_t hash value before each string,
+  /// and the offset actually points to that.
   llvm::DenseMap<ConstString, uint32_t> m_string_to_offset;
-  /// Skip one byte to start the string table off with an empty string.
-  uint32_t m_next_offset = 1;
+  /// Skip one byte plus hash size to start the string table off with an empty
+  /// string.
+  uint32_t m_next_offset = 1 + sizeof(uint32_t);
 };
 
 /// Many cache files require string tables to store data efficiently. This
 /// class helps give out strings from a string table that was read from a
 /// cache file.
 class StringTableReader {
 public:
   StringTableReader() = default;
 
-  llvm::StringRef Get(uint32_t offset) const;
+  ConstString Get(lldb::offset_t offset) const;
 
   bool Decode(const DataExtractor &data, lldb::offset_t *offset_ptr);
 
 protected:
   /// All of the strings in the string table are contained in m_data.
-  llvm::StringRef m_data;
+  /// Each format is uint32_t hash value followed by null-terminated
+  /// string data.
+  DataExtractor m_data;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_CORE_DATAFILECACHE_H

lldb/include/lldb/Utility/ConstString.h

public:
   void SetCStringWithLength(const char *cstr, size_t cstr_len);
 
   /// Set the C string value with the minimum length between \a fixed_cstr_len
   /// and the actual length of the C string. This can be used for data
   /// structures that have a fixed length to store a C string where the string
   /// might not be NULL terminated if the string takes the entire buffer.
   void SetTrimmedCStringWithLength(const char *cstr, size_t fixed_cstr_len);
 
+  /// Returns a hash value of the string.
+  uint32_t GetHash() const;
+
+  /// Set with hash value of the string
+  ///
+  /// Creates as if by calling SetString, but \a hash must contain the hash
+  /// of the string from a previous call to GetHash.
+  void SetStringWithHash(const llvm::StringRef &s, uint32_t hash);
+
   /// Get the memory cost of this object.
   ///
   /// Return the size in bytes that this object takes in memory. This returns
   /// the size in bytes of this object, which does not include any the shared
   /// string values it may refer to.
   ///
   /// \return
   ///     The number of bytes that this object occupies in memory.

lldb/source/Core/DataFileCache.cpp

 //===-- DataFileCache.cpp -------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Core/DataFileCache.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Core/ModuleList.h"
 #include "lldb/Host/FileSystem.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Utility/DataEncoder.h"
+#include "lldb/Utility/Endian.h"
 #include "lldb/Utility/LLDBLog.h"
 #include "lldb/Utility/Log.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 using namespace lldb_private;
 
 DataFileCache::DataFileCache(llvm::StringRef path) {

 
 uint32_t ConstStringTable::Add(ConstString s) {
   auto pos = m_string_to_offset.find(s);
   if (pos != m_string_to_offset.end())
     return pos->second;
   const uint32_t offset = m_next_offset;
   m_strings.push_back(s);
   m_string_to_offset[s] = offset;
+  m_next_offset += sizeof(uint32_t); // hash value
   m_next_offset += s.GetLength() + 1;
   return offset;
 }
 
-static const llvm::StringRef kStringTableIdentifier("STAB");
+constexpr llvm::StringLiteral kStringTableIdentifier("STB2");
 
 bool ConstStringTable::Encode(DataEncoder &encoder) {
   // Write an 4 character code into the stream. This will help us when decoding
   // to make sure we find this identifier when decoding the string table to make
   // sure we have the rigth data. It also helps to identify the string table
   // when dumping the hex bytes in a cache file.
   encoder.AppendData(kStringTableIdentifier);
   size_t length_offset = encoder.GetByteSize();
   encoder.AppendU32(0); // Total length of all strings which will be fixed up.
   size_t strtab_offset = encoder.GetByteSize();
-  encoder.AppendU8(0); // Start the string table with with an empty string.
+  // Start the string table with an empty string (preceded by its hash).
+  encoder.AppendU32(ConstString().GetHash());
+  encoder.AppendU8(0);
   for (auto s: m_strings) {
     // Make sure all of the offsets match up with what we handed out!
     assert(m_string_to_offset.find(s)->second ==
            encoder.GetByteSize() - strtab_offset);
+    // Append the hash value, so that it doesn't have to be computed every time
+    // the cache is read.
+    encoder.AppendU32(s.GetHash());
     // Append the C string into the encoder
     encoder.AppendCString(s.GetStringRef());
   }
   // Fixup the string table length.
   encoder.PutU32(length_offset, encoder.GetByteSize() - strtab_offset);
   return true;
 }
 
 bool StringTableReader::Decode(const lldb_private::DataExtractor &data,
                                lldb::offset_t *offset_ptr) {
   llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
   if (identifier != kStringTableIdentifier)
     return false;
   const uint32_t length = data.GetU32(offset_ptr);
-  // We always have at least one byte for the empty string at offset zero.
-  if (length == 0)
+  // We always have at least one byte for the empty string at offset 4
+  // and there's uint32_t hash for it.
+  if (length < 1 + sizeof(uint32_t))
     return false;
-  const char *bytes = (const char *)data.GetData(offset_ptr, length);
-  if (bytes == nullptr)
-    return false;
-  m_data = llvm::StringRef(bytes, length);
+  m_data = DataExtractor(data, *offset_ptr, length);
+  *offset_ptr += length;
   return true;
 }
 
-llvm::StringRef StringTableReader::Get(uint32_t offset) const {
-  if (offset >= m_data.size())
-    return llvm::StringRef();
-  return llvm::StringRef(m_data.data() + offset);
+ConstString StringTableReader::Get(lldb::offset_t offset) const {
+  if (offset >= m_data.GetByteSize())
+    return ConstString();
+  ConstString cstr;
+  uint32_t hash = m_data.GetU32(&offset);
+  llvm::StringRef str(m_data.PeekCStr(offset));
+  cstr.SetStringWithHash(str, hash);
+  return cstr;
 }

lldb/source/Core/Mangled.cpp

bool Mangled::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr,
   m_mangled.Clear();
   m_demangled.Clear();
   MangledEncoding encoding = (MangledEncoding)data.GetU8(offset_ptr);
   switch (encoding) {
     case Empty:
       return true;
 
     case DemangledOnly:
-      m_demangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
+      m_demangled = strtab.Get(data.GetU32(offset_ptr));
       return true;
 
     case MangledOnly:
-      m_mangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
+      m_mangled = strtab.Get(data.GetU32(offset_ptr));
       return true;
 
     case MangledAndDemangled:
-      m_mangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
-      m_demangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
+      m_mangled = strtab.Get(data.GetU32(offset_ptr));
+      m_demangled = strtab.Get(data.GetU32(offset_ptr));
       return true;
   }
   return false;
 }
 /// The encoding format for the Mangled object is as follows:
 ///
 /// uint8_t encoding;
 /// char str1[]; (only if DemangledOnly, MangledOnly)
 /// char str2[]; (only if MangledAndDemangled)
 ///
 /// The strings are stored as NULL terminated UTF8 strings and str1 and str2
 /// are only saved if we need them based on the encoding.
 ///
void Mangled::Encode(DataEncoder &file, ConstStringTable &strtab) const {
   } else if (m_demangled) {
     encoding = DemangledOnly;
   }
   file.AppendU8(encoding);
   switch (encoding) {
     case Empty:
       break;
     case DemangledOnly:
       file.AppendU32(strtab.Add(m_demangled));
       break;
     case MangledOnly:
       file.AppendU32(strtab.Add(m_mangled));
       break;
     case MangledAndDemangled:
       file.AppendU32(strtab.Add(m_mangled));
       file.AppendU32(strtab.Add(m_demangled));
       break;
   }
 }

lldb/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

enum DataID {
   kDataIDFunctionSelectors,
   kDataIDFunctionObjcClassSelectors,
   kDataIDGlobals,
   kDataIDTypes,
   kDataIDNamespaces,
   kDataIDEnd = 255u,
 
 };
-constexpr uint32_t CURRENT_CACHE_VERSION = 1;
+constexpr uint32_t CURRENT_CACHE_VERSION = 2;
 
 bool ManualDWARFIndex::IndexSet::Decode(const DataExtractor &data,
                                         lldb::offset_t *offset_ptr) {
   StringTableReader strtab;
   // We now decode the string table for all strings in the data cache file.
   if (!strtab.Decode(data, offset_ptr))
     return false;
 
   llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
   if (identifier != kIdentifierManualDWARFIndex)
     return false;
   const uint32_t version = data.GetU32(offset_ptr);
   if (version != CURRENT_CACHE_VERSION)
     return false;
 
   bool done = false;
   while (!done) {
     switch (data.GetU8(offset_ptr)) {
     default:
       // If we got here, this is not expected, we expect the data IDs to match
       // one of the values from the DataID enumeration.
       return false;
     case kDataIDFunctionBasenames:
       if (!function_basenames.Decode(data, offset_ptr, strtab))
         return false;
       break;
     case kDataIDFunctionFullnames:
void ManualDWARFIndex::IndexSet::Encode(DataEncoder &encoder) const {
   // gather all of the strings we willl need in "strtab" as we will need to
   // write the string table out before the symbol table.
   DataEncoder index_encoder(encoder.GetByteOrder(),
                             encoder.GetAddressByteSize());
 
   index_encoder.AppendData(kIdentifierManualDWARFIndex);
   // Encode the data version.
   index_encoder.AppendU32(CURRENT_CACHE_VERSION);
 
   if (!function_basenames.IsEmpty()) {
     index_encoder.AppendU8(kDataIDFunctionBasenames);
     function_basenames.Encode(index_encoder, strtab);
   }
   if (!function_fullnames.IsEmpty()) {
     index_encoder.AppendU8(kDataIDFunctionFullnames);
     function_fullnames.Encode(index_encoder, strtab);
   }
   if (!function_methods.IsEmpty()) {
std::string ManualDWARFIndex::GetCacheKey() {
   std::string key;
   llvm::raw_string_ostream strm(key);
   // DWARF Index can come from different object files for the same module. A
   // module can have one object file as the main executable and might have
   // another object file in a separate symbol file, or we might have a .dwo file
   // that claims its module is the main executable.
   ObjectFile *objfile = m_dwarf->GetObjectFile();
   strm << objfile->GetModule()->GetCacheKey() << "-dwarf-index-"
+       << CURRENT_CACHE_VERSION << "-"
        << llvm::format_hex(objfile->GetCacheHash(), 10);
   return strm.str();
 }
 
 bool ManualDWARFIndex::LoadFromCache() {
   DataFileCache *cache = Module::GetIndexCache();
   if (!cache)
     return false;
   ObjectFile *objfile = m_dwarf->GetObjectFile();

lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp

bool NameToDIE::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr,
                        const StringTableReader &strtab) {
   m_map.Clear();
   llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
   if (identifier != kIdentifierNameToDIE)
     return false;
   const uint32_t count = data.GetU32(offset_ptr);
   m_map.Reserve(count);
   for (uint32_t i = 0; i < count; ++i) {
-    llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr)));
+    ConstString cstr(strtab.Get(data.GetU32(offset_ptr)));
     // No empty strings allowed in the name to DIE maps.
-    if (str.empty())
+    if (cstr.IsEmpty())
       return false;
     if (llvm::Optional<DIERef> die_ref = DIERef::Decode(data, offset_ptr))
-      m_map.Append(ConstString(str), die_ref.getValue());
+      m_map.Append(cstr, die_ref.getValue());
     else
       return false;
   }
   // We must sort the UniqueCStringMap after decoding it since it is a vector
   // of UniqueCStringMap::Entry objects which contain a ConstString and type T.
   // ConstString objects are sorted by "const char *" and then type T and
   // the "const char *" are point values that will depend on the order in which
   // ConstString objects are created and in which of the 256 string pools they
   // are created in. So after we decode all of the entries, we must sort the
   // name map to ensure name lookups succeed. If we encode and decode within
   // the same process we wouldn't need to sort, so unit testing didn't catch
   // this issue when first checked in.
   m_map.Sort(std::less<DIERef>());
   return true;
 }
 
 void NameToDIE::Encode(DataEncoder &encoder, ConstStringTable &strtab) const {
   encoder.AppendData(kIdentifierNameToDIE);
   encoder.AppendU32(m_map.GetSize());
   for (const auto &entry : m_map) {
     // Make sure there are no empty strings.
     assert((bool)entry.cstring);
     encoder.AppendU32(strtab.Add(entry.cstring));
     entry.value.Encode(encoder);
   }
 }
 
 bool NameToDIE::operator==(const NameToDIE &rhs) const {
   const size_t size = m_map.GetSize();
   if (size != rhs.m_map.GetSize())
     return false;
   for (size_t i = 0; i < size; ++i) {
     if (m_map.GetCStringAtIndex(i) != rhs.m_map.GetCStringAtIndex(i))
       return false;
     if (m_map.GetValueRefAtIndexUnchecked(i) !=
         rhs.m_map.GetValueRefAtIndexUnchecked(i))
       return false;
   }
   return true;
 }

lldb/source/Symbol/Symtab.cpp

for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
       const uint32_t sibling_idx = symbol->GetSiblingIndex();
       if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
         return symbol;
     }
   }
   return nullptr;
 }
 
+constexpr uint32_t CURRENT_CACHE_VERSION = 2;
+
 std::string Symtab::GetCacheKey() {
   std::string key;
   llvm::raw_string_ostream strm(key);
   // Symbol table can come from different object files for the same module. A
   // module can have one object file as the main executable and might have
   // another object file in a separate symbol file.
   strm << m_objfile->GetModule()->GetCacheKey() << "-symtab-"
+       << CURRENT_CACHE_VERSION << "-"
        << llvm::format_hex(m_objfile->GetCacheHash(), 10);
   return strm.str();
 }
 
 void Symtab::SaveToCache() {
   DataFileCache *cache = Module::GetIndexCache();
   if (!cache)
     return; // Caching is not enabled.
   InitNameIndexes(); // Init the name indexes so we can cache them as well.

 
 static void EncodeCStrMap(DataEncoder &encoder, ConstStringTable &strtab,
                           const UniqueCStringMap<uint32_t> &cstr_map) {
   encoder.AppendData(kIdentifierCStrMap);
   encoder.AppendU32(cstr_map.GetSize());
   for (const auto &entry: cstr_map) {
     // Make sure there are no empty strings.
     assert((bool)entry.cstring);
     encoder.AppendU32(strtab.Add(entry.cstring));
     encoder.AppendU32(entry.value);
   }
 }
 
 bool DecodeCStrMap(const DataExtractor &data, lldb::offset_t *offset_ptr,
                    const StringTableReader &strtab,
                    UniqueCStringMap<uint32_t> &cstr_map) {
   llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
   if (identifier != kIdentifierCStrMap)
     return false;
   const uint32_t count = data.GetU32(offset_ptr);
   cstr_map.Reserve(count);
   for (uint32_t i=0; i<count; ++i)
   {
-    llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr)));
+    ConstString cstr(strtab.Get(data.GetU32(offset_ptr)));
     uint32_t value = data.GetU32(offset_ptr);
     // No empty strings in the name indexes in Symtab
-    if (str.empty())
+    if (cstr.IsEmpty())
       return false;
-    cstr_map.Append(ConstString(str), value);
+    cstr_map.Append(cstr, value);
   }
   // We must sort the UniqueCStringMap after decoding it since it is a vector
   // of UniqueCStringMap::Entry objects which contain a ConstString and type T.
   // ConstString objects are sorted by "const char *" and then type T and
   // the "const char *" are point values that will depend on the order in which
   // ConstString objects are created and in which of the 256 string pools they
   // are created in. So after we decode all of the entries, we must sort the
   // name map to ensure name lookups succeed. If we encode and decode within
   // the same process we wouldn't need to sort, so unit testing didn't catch
   // this issue when first checked in.
   cstr_map.Sort();
   return true;
 }
 
 constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB");
-constexpr uint32_t CURRENT_CACHE_VERSION = 1;
 
 /// The encoding format for the symbol table is as follows:
 ///
 /// Signature signature;
 /// ConstStringTable strtab;
 /// Identifier four character code: 'SYMB'
 /// uint32_t version;
 /// uint32_t num_symbols;
 /// Symbol symbols[num_symbols];
 /// uint8_t num_cstr_maps;
 /// UniqueCStringMap<uint32_t> cstr_maps[num_cstr_maps]
 bool Symtab::Encode(DataEncoder &encoder) const {
   // Name indexes must be computed before calling this function.
   assert(m_name_indexes_computed);
 
   // Encode the object file's signature
   CacheSignature signature(m_objfile);
   if (!signature.Encode(encoder))
     return false;
   ConstStringTable strtab;
 
   // Encoder the symbol table into a separate encoder first. This allows us
   // gather all of the strings we willl need in "strtab" as we will need to
   // write the string table out before the symbol table.
   DataEncoder symtab_encoder(encoder.GetByteOrder(),
                               encoder.GetAddressByteSize());
   symtab_encoder.AppendData(kIdentifierSymbolTable);
   // Encode the symtab data version.
   symtab_encoder.AppendU32(CURRENT_CACHE_VERSION);
   // Encode the number of symbols.
   symtab_encoder.AppendU32(m_symbols.size());
   // Encode the symbol data for all symbols.
   for (const auto &symbol: m_symbols)
     symbol.Encode(symtab_encoder, strtab);
 
   // Emit a byte for how many C string maps we emit. We will fix this up after
   // we emit the C string maps since we skip emitting C string maps if they are
   // empty.
   size_t num_cmaps_offset = symtab_encoder.GetByteSize();
StringTableReader strtab;
 
     // And now we can decode the symbol table with string table we just decoded.
     llvm::StringRef identifier((const char *)data.GetData(offset_ptr, 4), 4);
     if (identifier != kIdentifierSymbolTable)
       return false;
     const uint32_t version = data.GetU32(offset_ptr);
     if (version != CURRENT_CACHE_VERSION)
       return false;
     const uint32_t num_symbols = data.GetU32(offset_ptr);
     if (num_symbols == 0)
       return true;
     m_symbols.resize(num_symbols);
     SectionList *sections = m_objfile->GetModule()->GetSectionList();
     for (uint32_t i=0; i<num_symbols; ++i) {
       if (!m_symbols[i].Decode(data, offset_ptr, sections, strtab))
         return false;
     }
   }
 
   { // Scope for "elapsed" object below so it can measure the time to index.
     ElapsedTime elapsed(m_objfile->GetModule()->GetSymtabIndexTime());

lldb/source/Utility/ConstString.cpp

public:
 
   const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {
     if (cstr != nullptr)
       return GetConstCStringWithStringRef(llvm::StringRef(cstr, cstr_len));
     return nullptr;
   }
 
   const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) {
+    return GetConstCStringWithStringRefAndHash(string_ref,
+                                               StringPool::hash(string_ref));
+  }
+
+  const char *
+  GetConstCStringWithStringRefAndHash(const llvm::StringRef &string_ref,
+                                      uint32_t string_hash) {
     if (string_ref.data()) {
-      const uint32_t string_hash = StringPool::hash(string_ref);
       PoolEntry &pool = selectPool(string_hash);
 
       {
         llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
         auto it = pool.m_string_map.find(string_ref, string_hash);
         if (it != pool.m_string_map.end())
           return it->getKeyData();
       }
void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
   m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
 }
 
 void ConstString::SetTrimmedCStringWithLength(const char *cstr,
                                               size_t cstr_len) {
   m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);
 }
 
+void ConstString::SetStringWithHash(const llvm::StringRef &s, uint32_t hash) {
+  // StringMap will assert that the hash value matches the string.
+  m_string = StringPool().GetConstCStringWithStringRefAndHash(s, hash);
+}
+
+uint32_t ConstString::GetHash() const {
+  return Pool::StringPool::hash(GetStringRef());
+}
+
 ConstString::MemoryStats ConstString::GetMemoryStats() {
   return StringPool().GetMemoryStats();
 }
 
 void llvm::format_provider<ConstString>::format(const ConstString &CS,
                                                 llvm::raw_ostream &OS,
                                                 llvm::StringRef Options) {
   format_provider<StringRef>::format(CS.GetStringRef(), OS, Options);

lldb/unittests/Symbol/SymtabTest.cpp

StringTable:
     - ''
     - ''
     - ''
   FunctionStarts:  [ 0x3F64, 0x3F6C, 0x3F74, 0x3F7C ]
 ...
 )");
   // This data was taken from a hex dump of the object file from the above yaml
   // and hexdumped so we can load the cache data in this test.
+  // The steps to recreate this are:
+  // - copy&paste the above ("---" is start, "..." is end) to a file
+  // - run yaml2obj on it, redirect output to new file a.out
+  // - start lldb, enable index cache
+  //     ('settings set symbols.enable-lldb-index-cache true')
+  // - load the a.out file
+  // - get the cache file from the index cache directory
+  // - hexdump it ('hexdump -e '"    " 8/1 "0x%02x, " "\n"' <file>')
+  // - add it here, remove trailing empty items
+  // - set offsets 19-23 (between 0x02 and 0xff) to 0x00
   const uint8_t symtab_cache_bytes[] = {
     0x01, 0x10, 0x3e, 0x94, 0x86, 0x6e, 0x0d, 0x1a,
     0x39, 0xbd, 0x97, 0x5b, 0x64, 0xe8, 0xf1, 0xfd,
-    0xba, 0xae, 0xff, 0x53, 0x54, 0x41, 0x42, 0x91,
-    0x00, 0x00, 0x00, 0x00, 0x2f, 0x55, 0x73, 0x65,
-    0x72, 0x73, 0x2f, 0x67, 0x63, 0x6c, 0x61, 0x79,
-    0x74, 0x6f, 0x6e, 0x2f, 0x44, 0x6f, 0x63, 0x75,
-    0x6d, 0x65, 0x6e, 0x74, 0x73, 0x2f, 0x6f, 0x62,
-    0x6a, 0x66, 0x69, 0x6c, 0x65, 0x73, 0x2f, 0x69,
-    0x6e, 0x64, 0x65, 0x78, 0x2d, 0x6e, 0x61, 0x6d,
-    0x65, 0x73, 0x2f, 0x6d, 0x61, 0x69, 0x6e, 0x2e,
-    0x63, 0x00, 0x2f, 0x55, 0x73, 0x65, 0x72, 0x73,
-    0x2f, 0x67, 0x63, 0x6c, 0x61, 0x79, 0x74, 0x6f,
-    0x6e, 0x2f, 0x44, 0x6f, 0x63, 0x75, 0x6d, 0x65,
-    0x6e, 0x74, 0x73, 0x2f, 0x6f, 0x62, 0x6a, 0x66,
-    0x69, 0x6c, 0x65, 0x73, 0x2f, 0x69, 0x6e, 0x64,
-    0x65, 0x78, 0x2d, 0x6e, 0x61, 0x6d, 0x65, 0x73,
-    0x2f, 0x6d, 0x61, 0x69, 0x6e, 0x2e, 0x6f, 0x00,
-    0x66, 0x6f, 0x6f, 0x00, 0x62, 0x61, 0x72, 0x00,
-    0x62, 0x61, 0x7a, 0x00, 0x6d, 0x61, 0x69, 0x6e,
-    0x00, 0x5f, 0x6d, 0x68, 0x5f, 0x65, 0x78, 0x65,
-    0x63, 0x75, 0x74, 0x65, 0x5f, 0x68, 0x65, 0x61,
-    0x64, 0x65, 0x72, 0x00, 0x53, 0x59, 0x4d, 0x42,
-    0x01, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x2a,
-    0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x00,
+    0xba, 0xae, 0x02, 0x00, 0x00, 0x00, 0x00, 0xff,
+    0x53, 0x54, 0x42, 0x32, 0xb1, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0xfc, 0x46, 0xb0,
+    0x3d, 0x2f, 0x55, 0x73, 0x65, 0x72, 0x73, 0x2f,
+    0x67, 0x63, 0x6c, 0x61, 0x79, 0x74, 0x6f, 0x6e,
+    0x2f, 0x44, 0x6f, 0x63, 0x75, 0x6d, 0x65, 0x6e,
+    0x74, 0x73, 0x2f, 0x6f, 0x62, 0x6a, 0x66, 0x69,
+    0x6c, 0x65, 0x73, 0x2f, 0x69, 0x6e, 0x64, 0x65,
+    0x78, 0x2d, 0x6e, 0x61, 0x6d, 0x65, 0x73, 0x2f,
+    0x6d, 0x61, 0x69, 0x6e, 0x2e, 0x63, 0x00, 0x08,
+    0x47, 0xb0, 0x3d, 0x2f, 0x55, 0x73, 0x65, 0x72,
+    0x73, 0x2f, 0x67, 0x63, 0x6c, 0x61, 0x79, 0x74,
+    0x6f, 0x6e, 0x2f, 0x44, 0x6f, 0x63, 0x75, 0x6d,
+    0x65, 0x6e, 0x74, 0x73, 0x2f, 0x6f, 0x62, 0x6a,
+    0x66, 0x69, 0x6c, 0x65, 0x73, 0x2f, 0x69, 0x6e,
+    0x64, 0x65, 0x78, 0x2d, 0x6e, 0x61, 0x6d, 0x65,
+    0x73, 0x2f, 0x6d, 0x61, 0x69, 0x6e, 0x2e, 0x6f,
+    0x00, 0xa4, 0xc0, 0x01, 0x00, 0x66, 0x6f, 0x6f,
+    0x00, 0xd5, 0xad, 0x01, 0x00, 0x62, 0x61, 0x72,
+    0x00, 0xdd, 0xad, 0x01, 0x00, 0x62, 0x61, 0x7a,
+    0x00, 0xe5, 0x6f, 0x3d, 0x00, 0x6d, 0x61, 0x69,
+    0x6e, 0x00, 0xee, 0x47, 0xd6, 0x47, 0x5f, 0x6d,
+    0x68, 0x5f, 0x65, 0x78, 0x65, 0x63, 0x75, 0x74,
+    0x65, 0x5f, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72,
+    0x00, 0x53, 0x59, 0x4d, 0x42, 0x02, 0x00, 0x00,
+    0x00, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x08, 0x2a, 0x01, 0x05, 0x00,
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x64, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x0a, 0x20, 0x01, 0x37, 0x00, 0x00, 0x00, 0x00,
-    0x7b, 0xc3, 0x69, 0x62, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x06, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x64, 0x00, 0x02,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x0a, 0x20, 0x01,
+    0x3f, 0x00, 0x00, 0x00, 0x00, 0x7b, 0xc3, 0x69,
+    0x62, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x66,
+    0x00, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
+    0x32, 0x01, 0x79, 0x00, 0x00, 0x00, 0x01, 0x64,
+    0x3f, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x08,
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x01, 0x00, 0x66, 0x00, 0x04, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x02, 0x32, 0x01, 0x6d, 0x00, 0x00,
-    0x00, 0x01, 0x64, 0x3f, 0x00, 0x00, 0x01, 0x00,
-    0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x08, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x02, 0x32, 0x01, 0x71,
-    0x00, 0x00, 0x00, 0x01, 0x6c, 0x3f, 0x00, 0x00,
-    0x01, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x00,
-    0x0c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x32,
-    0x01, 0x75, 0x00, 0x00, 0x00, 0x01, 0x74, 0x3f,
-    0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x08, 0x00,
-    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x0f, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x02, 0x32, 0x01, 0x79, 0x00, 0x00, 0x00, 0x01,
-    0x7c, 0x3f, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
-    0x34, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x0f, 0x00, 0x14, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x04, 0x12, 0x02, 0x7e, 0x00, 0x00,
-    0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00,
-    0x00, 0x00, 0x64, 0x3f, 0x00, 0x00, 0x00, 0x00,
-    0x00, 0x00, 0x10, 0x00, 0x0f, 0x00, 0x01, 0x00,
-    0x43, 0x4d, 0x41, 0x50, 0x07, 0x00, 0x00, 0x00,
-    0x6d, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
-    0x75, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00,
-    0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-    0x79, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00,
-    0x37, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
-    0x71, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00,
-    0x7e, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00, 0x00
+    0x00, 0x0f, 0x00, 0x08, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x02, 0x32, 0x01, 0x81, 0x00, 0x00, 0x00,
+    0x01, 0x6c, 0x3f, 0x00, 0x00, 0x01, 0x00, 0x00,
+    0x00, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x0f, 0x00, 0x0c, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x02, 0x32, 0x01, 0x89, 0x00,
+    0x00, 0x00, 0x01, 0x74, 0x3f, 0x00, 0x00, 0x01,
+    0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x10,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x32, 0x01,
+    0x91, 0x00, 0x00, 0x00, 0x01, 0x7c, 0x3f, 0x00,
+    0x00, 0x01, 0x00, 0x00, 0x00, 0x34, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0f,
+    0x00, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
+    0x12, 0x02, 0x9a, 0x00, 0x00, 0x00, 0x01, 0x00,
+    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x64,
+    0x3f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
+    0x00, 0x0f, 0x00, 0x01, 0x00, 0x43, 0x4d, 0x41,
+    0x50, 0x07, 0x00, 0x00, 0x00, 0x9a, 0x00, 0x00,
+    0x00, 0x06, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x3f, 0x00, 0x00,
+    0x00, 0x01, 0x00, 0x00, 0x00, 0x79, 0x00, 0x00,
+    0x00, 0x02, 0x00, 0x00, 0x00, 0x81, 0x00, 0x00,
+    0x00, 0x03, 0x00, 0x00, 0x00, 0x89, 0x00, 0x00,
+    0x00, 0x04, 0x00, 0x00, 0x00, 0x91, 0x00, 0x00,
+    0x00, 0x05, 0x00, 0x00, 0x00
   };
 
   ASSERT_THAT_EXPECTED(ExpectedFile, llvm::Succeeded());
   auto module_sp = std::make_shared<Module>(ExpectedFile->moduleSpec());
   ObjectFile *objfile = module_sp->GetObjectFile();
   ASSERT_NE(objfile, nullptr);
 
   // Test encoding and decoding an empty symbol table.