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 = ArrayRef(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