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 const uint32_t hashes_count = m_header.bucket_count; 156 // Find the correct bucket for the using the hash value 157 const uint32_t bucket_idx = name_hash % bucket_count; 158 159 // Calculate the offset for the bucket entry for the bucket index 160 uint32_t offset = GetOffsetOfBucketEntry (bucket_idx); 161 162 // Extract the bucket entry which is a hash index. If the hash index 163 // is UINT32_MAX, then the bucket is empty. If it isn't, it is the 164 // index of the hash in the hashes array. We will then iterate through 165 // all hashes as long as they match "bucket_idx" which was calculated 166 // above 167 uint32_t hash_idx = m_data.GetU32 (&offset); 168 if (hash_idx != UINT32_MAX) 169 { 170 uint32_t hash_offset = GetOffsetOfHashValue (hash_idx); 171 172 const size_t initial_size = die_ofsets.size(); 173 uint32_t hash; 174 while (((hash = m_data.GetU32 (&hash_offset)) % bucket_count) == bucket_idx) 175 { 176 if (hash_idx >= hashes_count) 177 break; 178 179 if (hash == name_hash) 180 { 181 // The hash matches, but we still need to verify that the 182 // C string matches in case we have a hash collision. Figure 183 // out the offset for the data associated with this hash entry 184 offset = GetOffsetOfHashDataOffset (hash_idx); 185 uint32_t hash_data_offset = m_data.GetU32 (&offset); 186 uint32_t str_offset; 187 // Now we have the offset to the data for all strings that match 188 // our 32 bit hash. The format of the hash bucket is: 189 // 190 // uint32_t stroff; // string offset in .debug_str table 191 // uint32_t num_dies; // Number of DIEs in debug info that match the string that follow this 192 // uint32_t die_offsets[num_dies]; // An array of DIE offsets 193 // 194 // When a "stroff" is read and it is zero, then the data for this 195 // hash is terminated. 196 while ((str_offset = m_data.GetU32 (&hash_data_offset)) != 0) 197 { 198 // Extract the C string and comapare it 199 const char *cstr_name = m_string_table.PeekCStr(str_offset); 200 if (cstr_name) 201 { 202 if (strcmp(name_cstr, cstr_name) == 0) 203 { 204 // We have a match, now extract the DIE count 205 const uint32_t die_count = m_data.GetU32 (&hash_data_offset); 206 // Now extract "die_count" DIE offsets and put them into the 207 // results 208 for (uint32_t die_idx = 0; die_idx < die_count; ++die_idx) 209 die_ofsets.push_back(m_data.GetU32 (&hash_data_offset)); 210 } 211 } 212 } 213 } 214 ++hash_idx; 215 } 216 217 return die_ofsets.size() - initial_size; 218 } 219 } 220 } 221 return 0; 222 } 223 224 void 225 HashedNameToDIE::MemoryTable::Dump (Stream &s) 226 { 227 if (m_header.version == 1) 228 { 229 if (m_is_apple_names) 230 s.PutCString (".apple_names contents:\n"); 231 else 232 s.PutCString (".apple_types contents:\n"); 233 234 m_header.Dump (s); 235 uint32_t empty_bucket_count = 0; 236 uint32_t hash_collisions = 0; 237 uint32_t hash_idx_offset = GetOffsetOfBucketEntry (0); 238 const uint32_t bucket_count = m_header.bucket_count; 239 const uint32_t hashes_count = m_header.hashes_count; 240 for (uint32_t bucket_idx=0; bucket_idx<bucket_count; ++bucket_idx) 241 { 242 uint32_t hash_idx = m_data.GetU32 (&hash_idx_offset); 243 s.Printf("bucket[%u] ", bucket_idx); 244 245 if (hash_idx != UINT32_MAX) 246 { 247 s.Printf(" => hash[%u]\n", hash_idx); 248 249 uint32_t hash_offset = GetOffsetOfHashValue (hash_idx); 250 uint32_t data_offset = GetOffsetOfHashDataOffset (hash_idx); 251 252 uint32_t hash; 253 while (((hash = m_data.GetU32 (&hash_offset)) % bucket_count) == bucket_idx) 254 { 255 if (hash_idx >= hashes_count) 256 break; 257 258 uint32_t hash_data_offset = m_data.GetU32 (&data_offset); 259 s.Printf(" hash[%u] = 0x%8.8x\n", hash_idx, hash); 260 261 uint32_t string_count = 0; 262 uint32_t strp_offset; 263 while ((strp_offset = m_data.GetU32 (&hash_data_offset)) != 0) 264 { 265 const uint32_t num_die_offsets = m_data.GetU32 (&hash_data_offset); 266 s.Printf(" str[%u] = 0x%8.8x \"%s\", dies[%u] = {", 267 string_count, 268 strp_offset, 269 m_string_table.PeekCStr(strp_offset), 270 num_die_offsets); 271 ++string_count; 272 273 for (uint32_t die_idx=0; die_idx<num_die_offsets; ++die_idx) 274 { 275 const uint32_t die_offset = m_data.GetU32 (&hash_data_offset); 276 s.Printf(" 0x%8.8x", die_offset); 277 } 278 s.PutCString (" }\n"); 279 } 280 if (string_count > 1) 281 ++hash_collisions; 282 } 283 } 284 else 285 { 286 s.PutCString(" EMPTY\n"); 287 ++empty_bucket_count; 288 } 289 s.EOL(); 290 } 291 s.EOL(); 292 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)); 293 s.Printf ("Average hashes/non-empty bucket = %2.1f%%\n", ((float)m_header.hashes_count/(float)(m_header.bucket_count - empty_bucket_count))); 294 s.Printf ("Hash collisions = %u\n", hash_collisions); 295 } 296 } 297 298 299