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