1 //===-- HashedNameToDIE.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 "HashedNameToDIE.h" 11 #include "lldb/Core/ConstString.h" 12 #include "lldb/Core/DataExtractor.h" 13 #include "lldb/Core/Stream.h" 14 #include "lldb/Core/StreamString.h" 15 #include "lldb/Core/RegularExpression.h" 16 #include "lldb/Symbol/ObjectFile.h" 17 18 #include "DWARFCompileUnit.h" 19 #include "DWARFDebugInfo.h" 20 #include "DWARFDebugInfoEntry.h" 21 #include "DWARFDefines.h" 22 #include "SymbolFileDWARF.h" 23 using namespace lldb; 24 using namespace lldb_private; 25 26 static uint32_t 27 dl_new_hash (const char *s) 28 { 29 uint32_t h = 5381; 30 31 for (unsigned char c = *s; c; c = *++s) 32 h = ((h << 5) + h) + c; 33 34 return h; 35 } 36 37 38 void 39 HashedNameToDIE::Header::Dump (Stream &s) 40 { 41 s.Printf ("header.magic = 0x%8.8x", magic); 42 s.Printf ("header.version = 0x%4.4x", version); 43 s.Printf ("header.addr_bytesize = 0x%2.2x", addr_bytesize); 44 s.Printf ("header.hash_function = 0x%2.2x", hash_function); 45 s.Printf ("header.bucket_count = 0x%8.8x %u", bucket_count, bucket_count); 46 s.Printf ("header.hashes_count = 0x%8.8x %u", hashes_count, hashes_count); 47 s.Printf ("header.prologue_length = 0x%8.8x %u", prologue_length, prologue_length); 48 } 49 50 uint32_t 51 HashedNameToDIE::Header::Read (const DataExtractor &data, uint32_t offset) 52 { 53 magic = data.GetU32 (&offset); 54 if (magic != HASH_MAGIC) 55 { 56 // Magic bytes didn't match 57 version = 0; 58 return UINT32_MAX; 59 } 60 61 version = data.GetU16 (&offset); 62 if (version != 1) 63 { 64 // Unsupported version 65 return UINT32_MAX; 66 } 67 addr_bytesize = data.GetU8 (&offset); 68 hash_function = data.GetU8 (&offset); 69 bucket_count = data.GetU32 (&offset); 70 hashes_count = data.GetU32 (&offset); 71 prologue_length = data.GetU32 (&offset); 72 return offset; 73 } 74 75 void 76 HashedNameToDIE::DWARF::Header::Dump (Stream &s) 77 { 78 HashedNameToDIE::Header::Dump (s); 79 dwarf_prologue.Dump (s); 80 } 81 82 uint32_t 83 HashedNameToDIE::DWARF::Header::Read (const DataExtractor &data, uint32_t offset) 84 { 85 offset = HashedNameToDIE::Header::Read (data, offset); 86 if (offset != UINT32_MAX) 87 offset = dwarf_prologue.Read (data, offset); 88 else 89 dwarf_prologue.Clear(); 90 return offset; 91 } 92 93 void 94 HashedNameToDIE::DWARF::Prologue::Dump (Stream &s) 95 { 96 s.Printf ("dwarf_prologue.die_base_offset = 0x%8.8x\n", die_base_offset); 97 const size_t num_atoms = atoms.size(); 98 for (size_t i = 0; i < num_atoms; ++i) 99 { 100 s.Printf ("dwarf_prologue.atom[%zi] = %17s %s\n", 101 i, 102 GetAtomTypeName (atoms[i].type), 103 DW_FORM_value_to_name(atoms[i].form)); 104 } 105 } 106 107 uint32_t 108 HashedNameToDIE::DWARF::Prologue::Read (const DataExtractor &data, uint32_t offset) 109 { 110 Clear(); 111 die_base_offset = data.GetU32 (&offset); 112 Atom atom; 113 while (offset != UINT32_MAX) 114 { 115 atom.type = data.GetU16 (&offset); 116 atom.form = data.GetU16 (&offset); 117 if (atom.type == eAtomTypeNULL) 118 break; 119 atoms.push_back(atom); 120 } 121 return offset; 122 } 123 124 125 HashedNameToDIE::MemoryTable::MemoryTable (SymbolFileDWARF *dwarf, 126 const lldb_private::DataExtractor &data, 127 bool is_apple_names) : 128 m_data (data), 129 m_string_table (dwarf->get_debug_str_data ()), 130 m_is_apple_names (is_apple_names), 131 m_header () 132 { 133 } 134 135 bool 136 HashedNameToDIE::MemoryTable::Initialize () 137 { 138 uint32_t offset = 0; 139 offset = m_header.Read (m_data, offset); 140 return m_header.version == 1; 141 } 142 143 144 size_t 145 HashedNameToDIE::MemoryTable::Find (const char *name_cstr, DIEArray &die_ofsets) const 146 { 147 if (m_header.version == 1) 148 { 149 if (name_cstr && name_cstr[0]) 150 { 151 // Hash the C string 152 const uint32_t name_hash = dl_new_hash (name_cstr); 153 154 const uint32_t bucket_count = m_header.bucket_count; 155 // Find the correct bucket for the using the hash value 156 const uint32_t bucket_idx = name_hash % bucket_count; 157 158 // Calculate the offset for the bucket entry for the bucket index 159 uint32_t offset = GetOffsetOfBucketEntry (bucket_idx); 160 161 // Extract the bucket entry which is a hash index. If the hash index 162 // is UINT32_MAX, then the bucket is empty. If it isn't, it is the 163 // index of the hash in the hashes array. We will then iterate through 164 // all hashes as long as they match "bucket_idx" which was calculated 165 // above 166 uint32_t hash_idx = m_data.GetU32 (&offset); 167 if (hash_idx != UINT32_MAX) 168 { 169 uint32_t hash_offset = GetOffsetOfHashValue (hash_idx); 170 171 const size_t initial_size = die_ofsets.size(); 172 uint32_t hash; 173 while (((hash = m_data.GetU32 (&hash_offset)) % bucket_count) == bucket_idx) 174 { 175 if (hash == name_hash) 176 { 177 // The hash matches, but we still need to verify that the 178 // C string matches in case we have a hash collision. Figure 179 // out the offset for the data associated with this hash entry 180 offset = GetOffsetOfHashDataOffset (hash_idx); 181 uint32_t hash_data_offset = m_data.GetU32 (&offset); 182 uint32_t str_offset; 183 // Now we have the offset to the data for all strings that match 184 // our 32 bit hash. The format of the hash bucket is: 185 // 186 // uint32_t stroff; // string offset in .debug_str table 187 // uint32_t num_dies; // Number of DIEs in debug info that match the string that follow this 188 // uint32_t die_offsets[num_dies]; // An array of DIE offsets 189 // 190 // When a "stroff" is read and it is zero, then the data for this 191 // hash is terminated. 192 while ((str_offset = m_data.GetU32 (&hash_data_offset)) != 0) 193 { 194 // Extract the C string and comapare it 195 const char *cstr_name = m_string_table.PeekCStr(str_offset); 196 if (cstr_name) 197 { 198 if (strcmp(name_cstr, cstr_name) == 0) 199 { 200 // We have a match, now extract the DIE count 201 const uint32_t die_count = m_data.GetU32 (&hash_data_offset); 202 // Now extract "die_count" DIE offsets and put them into the 203 // results 204 for (uint32_t die_idx = 0; die_idx < die_count; ++die_idx) 205 die_ofsets.push_back(m_data.GetU32 (&hash_data_offset)); 206 } 207 } 208 } 209 } 210 ++hash_idx; 211 } 212 213 return die_ofsets.size() - initial_size; 214 } 215 } 216 } 217 return 0; 218 } 219 220 void 221 HashedNameToDIE::MemoryTable::Dump (Stream &s) 222 { 223 if (m_header.version == 1) 224 { 225 if (m_is_apple_names) 226 s.PutCString (".apple_names contents:\n"); 227 else 228 s.PutCString (".apple_types contents:\n"); 229 230 m_header.Dump (s); 231 uint32_t empty_bucket_count = 0; 232 uint32_t hash_collisions = 0; 233 uint32_t hash_idx_offset = GetOffsetOfBucketEntry (0); 234 const uint32_t bucket_count = m_header.bucket_count; 235 for (uint32_t bucket_idx=0; bucket_idx<bucket_count; ++bucket_idx) 236 { 237 uint32_t hash_idx = m_data.GetU32 (&hash_idx_offset); 238 s.Printf("bucket[%u] ", bucket_idx); 239 240 if (hash_idx != UINT32_MAX) 241 { 242 s.Printf(" => hash[%u]\n", hash_idx); 243 244 uint32_t hash_offset = GetOffsetOfHashValue (hash_idx); 245 uint32_t data_offset = GetOffsetOfHashDataOffset (hash_idx); 246 247 uint32_t hash; 248 while (((hash = m_data.GetU32 (&hash_offset)) % bucket_count) == bucket_idx) 249 { 250 uint32_t hash_data_offset = m_data.GetU32 (&data_offset); 251 s.Printf(" hash[%u] = 0x%8.8x\n", hash_idx, hash); 252 253 uint32_t string_count = 0; 254 uint32_t strp_offset; 255 while ((strp_offset = m_data.GetU32 (&hash_data_offset)) != 0) 256 { 257 const uint32_t num_die_offsets = m_data.GetU32 (&hash_data_offset); 258 s.Printf(" str[%u] = 0x%8.8x \"%s\", dies[%u] = {", 259 string_count, 260 strp_offset, 261 m_string_table.PeekCStr(strp_offset), 262 num_die_offsets); 263 ++string_count; 264 265 for (uint32_t die_idx=0; die_idx<num_die_offsets; ++die_idx) 266 { 267 const uint32_t die_offset = m_data.GetU32 (&hash_data_offset); 268 s.Printf(" 0x%8.8x", die_offset); 269 } 270 s.PutCString (" }\n"); 271 } 272 if (string_count > 1) 273 ++hash_collisions; 274 } 275 } 276 else 277 { 278 s.PutCString(" EMPTY\n"); 279 ++empty_bucket_count; 280 } 281 s.EOL(); 282 } 283 s.EOL(); 284 s.Printf ("%u of %u buckets empty (%2.1f%%)\n", empty_bucket_count, bucket_count, (((float)empty_bucket_count/(float)m_header.bucket_count)*100.0f)); 285 s.Printf ("Average hashes/non-empty bucket = %2.1f%%\n", ((float)m_header.hashes_count/(float)(m_header.bucket_count - empty_bucket_count))); 286 s.Printf ("Hash collisions = %u\n", hash_collisions); 287 } 288 } 289 290 291