1 //===- UDTLayout.cpp ------------------------------------------------------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/DebugInfo/PDB/UDTLayout.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/BitVector.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/DebugInfo/PDB/IPDBEnumChildren.h"
14 #include "llvm/DebugInfo/PDB/IPDBLineNumber.h"
15 #include "llvm/DebugInfo/PDB/IPDBRawSymbol.h"
16 #include "llvm/DebugInfo/PDB/IPDBSession.h"
17 #include "llvm/DebugInfo/PDB/PDBSymbol.h"
18 #include "llvm/DebugInfo/PDB/PDBSymbolData.h"
19 #include "llvm/DebugInfo/PDB/PDBSymbolFunc.h"
20 #include "llvm/DebugInfo/PDB/PDBSymbolTypeBaseClass.h"
21 #include "llvm/DebugInfo/PDB/PDBSymbolTypeBuiltin.h"
22 #include "llvm/DebugInfo/PDB/PDBSymbolTypeFunctionSig.h"
23 #include "llvm/DebugInfo/PDB/PDBSymbolTypePointer.h"
24 #include "llvm/DebugInfo/PDB/PDBSymbolTypeUDT.h"
25 #include "llvm/DebugInfo/PDB/PDBSymbolTypeVTable.h"
26 #include "llvm/DebugInfo/PDB/PDBTypes.h"
27 #include "llvm/Support/Casting.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstdint>
31 #include <memory>
32 
33 using namespace llvm;
34 using namespace llvm::pdb;
35 
36 static std::unique_ptr<PDBSymbol> getSymbolType(const PDBSymbol &Symbol) {
37   const IPDBSession &Session = Symbol.getSession();
38   const IPDBRawSymbol &RawSymbol = Symbol.getRawSymbol();
39   uint32_t TypeId = RawSymbol.getTypeId();
40   return Session.getSymbolById(TypeId);
41 }
42 
43 static uint32_t getTypeLength(const PDBSymbol &Symbol) {
44   auto SymbolType = getSymbolType(Symbol);
45   const IPDBRawSymbol &RawType = SymbolType->getRawSymbol();
46 
47   return RawType.getLength();
48 }
49 
50 LayoutItemBase::LayoutItemBase(const UDTLayoutBase *Parent,
51                                const PDBSymbol *Symbol, const std::string &Name,
52                                uint32_t OffsetInParent, uint32_t Size,
53                                bool IsElided)
54     : Symbol(Symbol), Parent(Parent), Name(Name),
55       OffsetInParent(OffsetInParent), SizeOf(Size), LayoutSize(Size),
56       IsElided(IsElided) {
57   UsedBytes.resize(SizeOf, true);
58 }
59 
60 uint32_t LayoutItemBase::deepPaddingSize() const {
61   return UsedBytes.size() - UsedBytes.count();
62 }
63 
64 uint32_t LayoutItemBase::tailPadding() const {
65   int Last = UsedBytes.find_last();
66 
67   return UsedBytes.size() - (Last + 1);
68 }
69 
70 DataMemberLayoutItem::DataMemberLayoutItem(
71     const UDTLayoutBase &Parent, std::unique_ptr<PDBSymbolData> Member)
72     : LayoutItemBase(&Parent, Member.get(), Member->getName(),
73                      Member->getOffset(), getTypeLength(*Member), false),
74       DataMember(std::move(Member)) {
75   auto Type = DataMember->getType();
76   if (auto UDT = unique_dyn_cast<PDBSymbolTypeUDT>(Type)) {
77     UdtLayout = std::make_unique<ClassLayout>(std::move(UDT));
78     UsedBytes = UdtLayout->usedBytes();
79   }
80 }
81 
82 VBPtrLayoutItem::VBPtrLayoutItem(const UDTLayoutBase &Parent,
83                                  std::unique_ptr<PDBSymbolTypeBuiltin> Sym,
84                                  uint32_t Offset, uint32_t Size)
85     : LayoutItemBase(&Parent, Sym.get(), "<vbptr>", Offset, Size, false),
86       Type(std::move(Sym)) {
87 }
88 
89 const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
90   return *cast<PDBSymbolData>(Symbol);
91 }
92 
93 bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
94 
95 const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
96   return *UdtLayout;
97 }
98 
99 VTableLayoutItem::VTableLayoutItem(const UDTLayoutBase &Parent,
100                                    std::unique_ptr<PDBSymbolTypeVTable> VT)
101     : LayoutItemBase(&Parent, VT.get(), "<vtbl>", 0, getTypeLength(*VT), false),
102       VTable(std::move(VT)) {
103   auto VTableType = cast<PDBSymbolTypePointer>(VTable->getType());
104   ElementSize = VTableType->getLength();
105 }
106 
107 UDTLayoutBase::UDTLayoutBase(const UDTLayoutBase *Parent, const PDBSymbol &Sym,
108                              const std::string &Name, uint32_t OffsetInParent,
109                              uint32_t Size, bool IsElided)
110     : LayoutItemBase(Parent, &Sym, Name, OffsetInParent, Size, IsElided) {
111   // UDT storage comes from a union of all the children's storage, so start out
112   // uninitialized.
113   UsedBytes.reset(0, Size);
114 
115   initializeChildren(Sym);
116   if (LayoutSize < Size)
117     UsedBytes.resize(LayoutSize);
118 }
119 
120 uint32_t UDTLayoutBase::tailPadding() const {
121   uint32_t Abs = LayoutItemBase::tailPadding();
122   if (!LayoutItems.empty()) {
123     const LayoutItemBase *Back = LayoutItems.back();
124     uint32_t ChildPadding = Back->LayoutItemBase::tailPadding();
125     if (Abs < ChildPadding)
126       Abs = 0;
127     else
128       Abs -= ChildPadding;
129   }
130   return Abs;
131 }
132 
133 ClassLayout::ClassLayout(const PDBSymbolTypeUDT &UDT)
134     : UDTLayoutBase(nullptr, UDT, UDT.getName(), 0, UDT.getLength(), false),
135       UDT(UDT) {
136   ImmediateUsedBytes.resize(SizeOf, false);
137   for (auto &LI : LayoutItems) {
138     uint32_t Begin = LI->getOffsetInParent();
139     uint32_t End = Begin + LI->getLayoutSize();
140     End = std::min(SizeOf, End);
141     ImmediateUsedBytes.set(Begin, End);
142   }
143 }
144 
145 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
146     : ClassLayout(*UDT) {
147   OwnedStorage = std::move(UDT);
148 }
149 
150 uint32_t ClassLayout::immediatePadding() const {
151   return SizeOf - ImmediateUsedBytes.count();
152 }
153 
154 BaseClassLayout::BaseClassLayout(const UDTLayoutBase &Parent,
155                                  uint32_t OffsetInParent, bool Elide,
156                                  std::unique_ptr<PDBSymbolTypeBaseClass> B)
157     : UDTLayoutBase(&Parent, *B, B->getName(), OffsetInParent, B->getLength(),
158                     Elide),
159       Base(std::move(B)) {
160   if (isEmptyBase()) {
161     // Special case an empty base so that it doesn't get treated as padding.
162     UsedBytes.resize(1);
163     UsedBytes.set(0);
164   }
165   IsVirtualBase = Base->isVirtualBaseClass();
166 }
167 
168 void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
169   // Handled bases first, followed by VTables, followed by data members,
170   // followed by functions, followed by other.  This ordering is necessary
171   // so that bases and vtables get initialized before any functions which
172   // may override them.
173   UniquePtrVector<PDBSymbolTypeBaseClass> Bases;
174   UniquePtrVector<PDBSymbolTypeVTable> VTables;
175   UniquePtrVector<PDBSymbolData> Members;
176   UniquePtrVector<PDBSymbolTypeBaseClass> VirtualBaseSyms;
177 
178   auto Children = Sym.findAllChildren();
179   while (auto Child = Children->getNext()) {
180     if (auto Base = unique_dyn_cast<PDBSymbolTypeBaseClass>(Child)) {
181       if (Base->isVirtualBaseClass())
182         VirtualBaseSyms.push_back(std::move(Base));
183       else
184         Bases.push_back(std::move(Base));
185     }
186     else if (auto Data = unique_dyn_cast<PDBSymbolData>(Child)) {
187       if (Data->getDataKind() == PDB_DataKind::Member)
188         Members.push_back(std::move(Data));
189       else
190         Other.push_back(std::move(Data));
191     } else if (auto VT = unique_dyn_cast<PDBSymbolTypeVTable>(Child))
192       VTables.push_back(std::move(VT));
193     else if (auto Func = unique_dyn_cast<PDBSymbolFunc>(Child))
194       Funcs.push_back(std::move(Func));
195     else {
196       Other.push_back(std::move(Child));
197     }
198   }
199 
200   // We don't want to have any re-allocations in the list of bases, so make
201   // sure to reserve enough space so that our ArrayRefs don't get invalidated.
202   AllBases.reserve(Bases.size() + VirtualBaseSyms.size());
203 
204   // Only add non-virtual bases to the class first.  Only at the end of the
205   // class, after all non-virtual bases and data members have been added do we
206   // add virtual bases.  This way the offsets are correctly aligned when we go
207   // to lay out virtual bases.
208   for (auto &Base : Bases) {
209     uint32_t Offset = Base->getOffset();
210     // Non-virtual bases never get elided.
211     auto BL = std::make_unique<BaseClassLayout>(*this, Offset, false,
212                                                  std::move(Base));
213 
214     AllBases.push_back(BL.get());
215     addChildToLayout(std::move(BL));
216   }
217   NonVirtualBases = AllBases;
218 
219   assert(VTables.size() <= 1);
220   if (!VTables.empty()) {
221     auto VTLayout =
222         std::make_unique<VTableLayoutItem>(*this, std::move(VTables[0]));
223 
224     VTable = VTLayout.get();
225 
226     addChildToLayout(std::move(VTLayout));
227   }
228 
229   for (auto &Data : Members) {
230     auto DM = std::make_unique<DataMemberLayoutItem>(*this, std::move(Data));
231 
232     addChildToLayout(std::move(DM));
233   }
234 
235   // Make sure add virtual bases before adding functions, since functions may be
236   // overrides of virtual functions declared in a virtual base, so the VTables
237   // and virtual intros need to be correctly initialized.
238   for (auto &VB : VirtualBaseSyms) {
239     int VBPO = VB->getVirtualBasePointerOffset();
240     if (!hasVBPtrAtOffset(VBPO)) {
241       if (auto VBP = VB->getRawSymbol().getVirtualBaseTableType()) {
242         auto VBPL = std::make_unique<VBPtrLayoutItem>(*this, std::move(VBP),
243                                                        VBPO, VBP->getLength());
244         VBPtr = VBPL.get();
245         addChildToLayout(std::move(VBPL));
246       }
247     }
248 
249     // Virtual bases always go at the end.  So just look for the last place we
250     // ended when writing something, and put our virtual base there.
251     // Note that virtual bases get elided unless this is a top-most derived
252     // class.
253     uint32_t Offset = UsedBytes.find_last() + 1;
254     bool Elide = (Parent != nullptr);
255     auto BL =
256         std::make_unique<BaseClassLayout>(*this, Offset, Elide, std::move(VB));
257     AllBases.push_back(BL.get());
258 
259     // Only lay this virtual base out directly inside of *this* class if this
260     // is a top-most derived class.  Keep track of it regardless, but only
261     // physically lay it out if it's a topmost derived class.
262     addChildToLayout(std::move(BL));
263   }
264   VirtualBases = makeArrayRef(AllBases).drop_front(NonVirtualBases.size());
265 
266   if (Parent != nullptr)
267     LayoutSize = UsedBytes.find_last() + 1;
268 }
269 
270 bool UDTLayoutBase::hasVBPtrAtOffset(uint32_t Off) const {
271   if (VBPtr && VBPtr->getOffsetInParent() == Off)
272     return true;
273   for (BaseClassLayout *BL : AllBases) {
274     if (BL->hasVBPtrAtOffset(Off - BL->getOffsetInParent()))
275       return true;
276   }
277   return false;
278 }
279 
280 void UDTLayoutBase::addChildToLayout(std::unique_ptr<LayoutItemBase> Child) {
281   uint32_t Begin = Child->getOffsetInParent();
282 
283   if (!Child->isElided()) {
284     BitVector ChildBytes = Child->usedBytes();
285 
286     // Suppose the child occupies 4 bytes starting at offset 12 in a 32 byte
287     // class.  When we call ChildBytes.resize(32), the Child's storage will
288     // still begin at offset 0, so we need to shift it left by offset bytes
289     // to get it into the right position.
290     ChildBytes.resize(UsedBytes.size());
291     ChildBytes <<= Child->getOffsetInParent();
292     UsedBytes |= ChildBytes;
293 
294     if (ChildBytes.count() > 0) {
295       auto Loc = llvm::upper_bound(
296           LayoutItems, Begin, [](uint32_t Off, const LayoutItemBase *Item) {
297             return (Off < Item->getOffsetInParent());
298           });
299 
300       LayoutItems.insert(Loc, Child.get());
301     }
302   }
303 
304   ChildStorage.push_back(std::move(Child));
305 }
306