[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

434–436

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

440–445

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

448–453

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

506–508

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

510–512

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

514–518

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.

524–528

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

591–592

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

104–106

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

110–111

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

125–127

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

1195–1196

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

1210

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

1224

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

1232

remove

1255–1256

Remove

1310–1314

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

217–218 ↗

(On Diff #427107)

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

lldb/source/Core/DataFileCache.cpp

272 ↗

(On Diff #427107)

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

280 ↗

(On Diff #427107)

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

307–311 ↗

(On Diff #427107)

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

313–314 ↗

(On Diff #427107)

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

317–321 ↗

(On Diff #427107)

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

329–332 ↗

(On Diff #427107)

333 ↗

(On Diff #427107)

lldb/source/Utility/ConstString.cpp

342

Do we want to add the expensive check here?

346

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

346

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 ↗

(On Diff #431217)

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/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/Mangled.cpp

bool Mangled::Decode(const DataExtractor &data, lldb::offset_t *offset_ptr,
                      const StringTableReader &strtab) {
   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)));
+    case DemangledOnly: {
+      uint32_t str_offset = data.GetU32(offset_ptr);
+      uint32_t hash = data.GetU32(offset_ptr);
+      m_demangled.SetStringWithHash(strtab.Get(str_offset), hash);
       return true;
+    }
 
-    case MangledOnly:
-      m_mangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
+    case MangledOnly: {
+      uint32_t str_offset = data.GetU32(offset_ptr);
+      uint32_t hash = data.GetU32(offset_ptr);
+      m_mangled.SetStringWithHash(strtab.Get(str_offset), hash);
       return true;
+    }
 
-    case MangledAndDemangled:
-      m_mangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
-      m_demangled.SetString(strtab.Get(data.GetU32(offset_ptr)));
+    case MangledAndDemangled: {
+      uint32_t str_offset = data.GetU32(offset_ptr);
+      uint32_t hash = data.GetU32(offset_ptr);
+      m_mangled.SetStringWithHash(strtab.Get(str_offset), hash);
+      str_offset = data.GetU32(offset_ptr);
+      hash = data.GetU32(offset_ptr);
+      m_demangled.SetStringWithHash(strtab.Get(str_offset), hash);
       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)
 ///
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));
+      file.AppendU32(m_demangled.GetHash());
       break;
     case MangledOnly:
       file.AppendU32(strtab.Add(m_mangled));
+      file.AppendU32(m_mangled.GetHash());
       break;
     case MangledAndDemangled:
       file.AppendU32(strtab.Add(m_mangled));
+      file.AppendU32(m_mangled.GetHash());
       file.AppendU32(strtab.Add(m_demangled));
+      file.AppendU32(m_demangled.GetHash());
       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;
+constexpr llvm::StringLiteral kCheckHashString("a test string for hash check");
 
 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;
+  // Check that implementation of ConstString::GetHash() has not changed.
+  uint32_t checkHash = data.GetU32(offset_ptr);
+  ConstString checkString(kCheckHashString);
+  if (checkHash != checkString.GetHash())
+    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;
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);
+  // Encode check hash value.
+  index_encoder.AppendU32(ConstString(kCheckHashString).GetHash());
 
   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);

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);
   for (uint32_t i = 0; i < count; ++i) {
     llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr)));
+    uint32_t hash = data.GetU32(offset_ptr);
     // No empty strings allowed in the name to DIE maps.
     if (str.empty())
       return false;
-    if (llvm::Optional<DIERef> die_ref = DIERef::Decode(data, offset_ptr))
-      m_map.Append(ConstString(str), die_ref.getValue());
-    else
+    if (llvm::Optional<DIERef> die_ref = DIERef::Decode(data, offset_ptr)) {
+      ConstString cstr;
+      cstr.SetStringWithHash(str, hash);
+      m_map.Append(cstr, die_ref.getValue());
+    } else
       return false;
   }
   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));
+    encoder.AppendU32(entry.cstring.GetHash());
     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

 
 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);
   for (uint32_t i=0; i<count; ++i)
   {
     llvm::StringRef str(strtab.Get(data.GetU32(offset_ptr)));
+    uint32_t hash = data.GetU32(offset_ptr);
     uint32_t value = data.GetU32(offset_ptr);
     // No empty strings in the name indexes in Symtab
     if (str.empty())
       return false;
-    cstr_map.Append(ConstString(str), value);
+    ConstString cstr;
+    cstr.SetStringWithHash(str, hash);
+    cstr_map.Append(cstr, value);
   }
   return true;
 }
 
 constexpr llvm::StringLiteral kIdentifierSymbolTable("SYMB");
-constexpr uint32_t CURRENT_CACHE_VERSION = 1;
+constexpr uint32_t CURRENT_CACHE_VERSION = 2;
+constexpr llvm::StringLiteral kCheckHashString("a test string for hash check");
 
 /// The encoding format for the symbol table is as follows:
 ///
 /// Signature signature;
 /// ConstStringTable strtab;
 /// Identifier four character code: 'SYMB'
 /// uint32_t version;
+/// uint32_t check_hash;
 /// 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 check hash value.
+  symtab_encoder.AppendU32(ConstString(kCheckHashString).GetHash());
   // 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
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;
+    // Check that implementation of ConstString::GetHash() has not changed.
+    uint32_t checkHash = data.GetU32(offset_ptr);
+    ConstString checkString(kCheckHashString);
+    if (checkHash != checkString.GetHash())
+      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;

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);
       const uint8_t h = hash(string_hash);
 
       {
         llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
         auto it = m_string_pools[h].m_string_map.find(string_ref, string_hash);
         if (it != m_string_pools[h].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) {
+  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);