1 //===- DWARFUnitIndex.cpp -------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/ADT/StringRef.h"
12 #include "llvm/Support/ErrorHandling.h"
13 #include "llvm/Support/Format.h"
14 #include "llvm/Support/raw_ostream.h"
20 bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
21 uint32_t *OffsetPtr) {
22 if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))
24 Version = IndexData.getU32(OffsetPtr);
25 NumColumns = IndexData.getU32(OffsetPtr);
26 NumUnits = IndexData.getU32(OffsetPtr);
27 NumBuckets = IndexData.getU32(OffsetPtr);
31 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
32 OS << format("version = %u slots = %u\n\n", Version, NumBuckets);
35 bool DWARFUnitIndex::parse(DataExtractor IndexData) {
36 bool b = parseImpl(IndexData);
38 // Make sure we don't try to dump anything
39 Header.NumBuckets = 0;
40 // Release any partially initialized data.
47 bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
49 if (!Header.parse(IndexData, &Offset))
52 if (!IndexData.isValidOffsetForDataOfSize(
53 Offset, Header.NumBuckets * (8 + 4) +
54 (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
57 Rows = llvm::make_unique<Entry[]>(Header.NumBuckets);
59 llvm::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);
60 ColumnKinds = llvm::make_unique<DWARFSectionKind[]>(Header.NumColumns);
62 // Read Hash Table of Signatures
63 for (unsigned i = 0; i != Header.NumBuckets; ++i)
64 Rows[i].Signature = IndexData.getU64(&Offset);
66 // Read Parallel Table of Indexes
67 for (unsigned i = 0; i != Header.NumBuckets; ++i) {
68 auto Index = IndexData.getU32(&Offset);
72 Rows[i].Contributions =
73 llvm::make_unique<Entry::SectionContribution[]>(Header.NumColumns);
74 Contribs[Index - 1] = Rows[i].Contributions.get();
77 // Read the Column Headers
78 for (unsigned i = 0; i != Header.NumColumns; ++i) {
79 ColumnKinds[i] = static_cast<DWARFSectionKind>(IndexData.getU32(&Offset));
80 if (ColumnKinds[i] == InfoColumnKind) {
90 // Read Table of Section Offsets
91 for (unsigned i = 0; i != Header.NumUnits; ++i) {
92 auto *Contrib = Contribs[i];
93 for (unsigned i = 0; i != Header.NumColumns; ++i)
94 Contrib[i].Offset = IndexData.getU32(&Offset);
97 // Read Table of Section Sizes
98 for (unsigned i = 0; i != Header.NumUnits; ++i) {
99 auto *Contrib = Contribs[i];
100 for (unsigned i = 0; i != Header.NumColumns; ++i)
101 Contrib[i].Length = IndexData.getU32(&Offset);
107 StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
121 llvm_unreachable("unknown DWARFSectionKind");
124 void DWARFUnitIndex::dump(raw_ostream &OS) const {
129 OS << "Index Signature ";
130 for (unsigned i = 0; i != Header.NumColumns; ++i)
131 OS << ' ' << left_justify(getColumnHeader(ColumnKinds[i]), 24);
132 OS << "\n----- ------------------";
133 for (unsigned i = 0; i != Header.NumColumns; ++i)
134 OS << " ------------------------";
136 for (unsigned i = 0; i != Header.NumBuckets; ++i) {
138 if (auto *Contribs = Row.Contributions.get()) {
139 OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
140 for (unsigned i = 0; i != Header.NumColumns; ++i) {
141 auto &Contrib = Contribs[i];
142 OS << format("[0x%08x, 0x%08x) ", Contrib.Offset,
143 Contrib.Offset + Contrib.Length);
150 const DWARFUnitIndex::Entry::SectionContribution *
151 DWARFUnitIndex::Entry::getOffset(DWARFSectionKind Sec) const {
153 for (; i != Index->Header.NumColumns; ++i)
154 if (Index->ColumnKinds[i] == Sec)
155 return &Contributions[i];
159 const DWARFUnitIndex::Entry::SectionContribution *
160 DWARFUnitIndex::Entry::getOffset() const {
161 return &Contributions[Index->InfoColumn];
164 const DWARFUnitIndex::Entry *
165 DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
166 if (OffsetLookup.empty()) {
167 for (uint32_t i = 0; i != Header.NumBuckets; ++i)
168 if (Rows[i].Contributions)
169 OffsetLookup.push_back(&Rows[i]);
170 llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
171 return E1->Contributions[InfoColumn].Offset <
172 E2->Contributions[InfoColumn].Offset;
175 auto I = partition_point(OffsetLookup, [&](Entry *E2) {
176 return E2->Contributions[InfoColumn].Offset <= Offset;
178 if (I == OffsetLookup.begin())
182 const auto &InfoContrib = E->Contributions[InfoColumn];
183 if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
188 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
189 uint64_t Mask = Header.NumBuckets - 1;
192 auto HP = ((S >> 32) & Mask) | 1;
193 while (Rows[H].getSignature() != S && Rows[H].getSignature() != 0)
196 if (Rows[H].getSignature() != S)