356 lines · cpp
1//=======- PaddingChecker.cpp ------------------------------------*- C++ -*-==//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a checker that checks for padding that could be10// removed by re-ordering members.11//12//===----------------------------------------------------------------------===//13 14#include "clang/AST/CharUnits.h"15#include "clang/AST/DeclTemplate.h"16#include "clang/AST/DynamicRecursiveASTVisitor.h"17#include "clang/AST/RecordLayout.h"18#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"19#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"20#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"21#include "clang/StaticAnalyzer/Core/Checker.h"22#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"23#include "llvm/Support/MathExtras.h"24#include "llvm/Support/raw_ostream.h"25 26using namespace clang;27using namespace ento;28 29namespace {30class PaddingChecker : public Checker<check::ASTDecl<TranslationUnitDecl>> {31private:32 const BugType PaddingBug{this, "Excessive Padding", "Performance"};33 mutable BugReporter *BR;34 35public:36 int64_t AllowedPad;37 38 void checkASTDecl(const TranslationUnitDecl *TUD, AnalysisManager &MGR,39 BugReporter &BRArg) const {40 BR = &BRArg;41 42 // The calls to checkAST* from AnalysisConsumer don't43 // visit template instantiations or lambda classes. We44 // want to visit those, so we make our own RecursiveASTVisitor.45 struct LocalVisitor : DynamicRecursiveASTVisitor {46 const PaddingChecker *Checker;47 explicit LocalVisitor(const PaddingChecker *Checker) : Checker(Checker) {48 ShouldVisitTemplateInstantiations = true;49 ShouldVisitImplicitCode = true;50 }51 bool VisitRecordDecl(RecordDecl *RD) override {52 Checker->visitRecord(RD);53 return true;54 }55 bool VisitVarDecl(VarDecl *VD) override {56 Checker->visitVariable(VD);57 return true;58 }59 // TODO: Visit array new and mallocs for arrays.60 };61 62 LocalVisitor visitor(this);63 visitor.TraverseDecl(const_cast<TranslationUnitDecl *>(TUD));64 }65 66 /// Look for records of overly padded types. If padding *67 /// PadMultiplier exceeds AllowedPad, then generate a report.68 /// PadMultiplier is used to share code with the array padding69 /// checker.70 void visitRecord(const RecordDecl *RD, uint64_t PadMultiplier = 1) const {71 if (shouldSkipDecl(RD))72 return;73 74 // TODO: Figure out why we are going through declarations and not only75 // definitions.76 if (!(RD = RD->getDefinition()))77 return;78 79 // This is the simplest correct case: a class with no fields and one base80 // class. Other cases are more complicated because of how the base classes81 // & fields might interact, so we don't bother dealing with them.82 // TODO: Support other combinations of base classes and fields.83 if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD))84 if (CXXRD->field_empty() && CXXRD->getNumBases() == 1)85 return visitRecord(CXXRD->bases().begin()->getType()->getAsRecordDecl(),86 PadMultiplier);87 88 auto &ASTContext = RD->getASTContext();89 const ASTRecordLayout &RL = ASTContext.getASTRecordLayout(RD);90 assert(llvm::isPowerOf2_64(RL.getAlignment().getQuantity()));91 92 CharUnits BaselinePad = calculateBaselinePad(RD, ASTContext, RL);93 if (BaselinePad.isZero())94 return;95 96 CharUnits OptimalPad;97 SmallVector<const FieldDecl *, 20> OptimalFieldsOrder;98 std::tie(OptimalPad, OptimalFieldsOrder) =99 calculateOptimalPad(RD, ASTContext, RL);100 101 CharUnits DiffPad = PadMultiplier * (BaselinePad - OptimalPad);102 if (DiffPad.getQuantity() <= AllowedPad) {103 assert(!DiffPad.isNegative() && "DiffPad should not be negative");104 // There is not enough excess padding to trigger a warning.105 return;106 }107 reportRecord(ASTContext, RD, BaselinePad, OptimalPad, OptimalFieldsOrder);108 }109 110 /// Look for arrays of overly padded types. If the padding of the111 /// array type exceeds AllowedPad, then generate a report.112 void visitVariable(const VarDecl *VD) const {113 const ArrayType *ArrTy = VD->getType()->getAsArrayTypeUnsafe();114 if (ArrTy == nullptr)115 return;116 uint64_t Elts = 0;117 if (const ConstantArrayType *CArrTy = dyn_cast<ConstantArrayType>(ArrTy))118 Elts = CArrTy->getZExtSize();119 if (Elts == 0)120 return;121 const auto *RD = ArrTy->getElementType()->getAsRecordDecl();122 if (!RD)123 return;124 125 // TODO: Recurse into the fields to see if they have excess padding.126 visitRecord(RD, Elts);127 }128 129 bool shouldSkipDecl(const RecordDecl *RD) const {130 // TODO: Figure out why we are going through declarations and not only131 // definitions.132 if (!(RD = RD->getDefinition()))133 return true;134 auto Location = RD->getLocation();135 // If the construct doesn't have a source file, then it's not something136 // we want to diagnose.137 if (!Location.isValid())138 return true;139 SrcMgr::CharacteristicKind Kind =140 BR->getSourceManager().getFileCharacteristic(Location);141 // Throw out all records that come from system headers.142 if (Kind != SrcMgr::C_User)143 return true;144 145 // Not going to attempt to optimize unions.146 if (RD->isUnion())147 return true;148 if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD)) {149 // Tail padding with base classes ends up being very complicated.150 // We will skip objects with base classes for now, unless they do not151 // have fields.152 // TODO: Handle more base class scenarios.153 if (!CXXRD->field_empty() && CXXRD->getNumBases() != 0)154 return true;155 if (CXXRD->field_empty() && CXXRD->getNumBases() != 1)156 return true;157 // Virtual bases are complicated, skipping those for now.158 if (CXXRD->getNumVBases() != 0)159 return true;160 // Can't layout a template, so skip it. We do still layout the161 // instantiations though.162 if (CXXRD->isDependentType())163 return true;164 }165 // How do you reorder fields if you haven't got any?166 else if (RD->field_empty())167 return true;168 169 auto IsTrickyField = [](const FieldDecl *FD) -> bool {170 // Bitfield layout is hard.171 if (FD->isBitField())172 return true;173 174 // Variable length arrays are tricky too.175 QualType Ty = FD->getType();176 if (Ty->isIncompleteArrayType())177 return true;178 return false;179 };180 181 if (llvm::any_of(RD->fields(), IsTrickyField))182 return true;183 return false;184 }185 186 static CharUnits calculateBaselinePad(const RecordDecl *RD,187 const ASTContext &ASTContext,188 const ASTRecordLayout &RL) {189 CharUnits PaddingSum;190 CharUnits Offset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0));191 for (const FieldDecl *FD : RD->fields()) {192 // Skip field that is a subobject of zero size, marked with193 // [[no_unique_address]] or an empty bitfield, because its address can be194 // set the same as the other fields addresses.195 if (FD->isZeroSize(ASTContext))196 continue;197 // This checker only cares about the padded size of the198 // field, and not the data size. If the field is a record199 // with tail padding, then we won't put that number in our200 // total because reordering fields won't fix that problem.201 CharUnits FieldSize = ASTContext.getTypeSizeInChars(FD->getType());202 auto FieldOffsetBits = RL.getFieldOffset(FD->getFieldIndex());203 CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(FieldOffsetBits);204 PaddingSum += (FieldOffset - Offset);205 Offset = FieldOffset + FieldSize;206 }207 PaddingSum += RL.getSize() - Offset;208 return PaddingSum;209 }210 211 /// Optimal padding overview:212 /// 1. Find a close approximation to where we can place our first field.213 /// This will usually be at offset 0.214 /// 2. Try to find the best field that can legally be placed at the current215 /// offset.216 /// a. "Best" is the largest alignment that is legal, but smallest size.217 /// This is to account for overly aligned types.218 /// 3. If no fields can fit, pad by rounding the current offset up to the219 /// smallest alignment requirement of our fields. Measure and track the220 // amount of padding added. Go back to 2.221 /// 4. Increment the current offset by the size of the chosen field.222 /// 5. Remove the chosen field from the set of future possibilities.223 /// 6. Go back to 2 if there are still unplaced fields.224 /// 7. Add tail padding by rounding the current offset up to the structure225 /// alignment. Track the amount of padding added.226 227 static std::pair<CharUnits, SmallVector<const FieldDecl *, 20>>228 calculateOptimalPad(const RecordDecl *RD, const ASTContext &ASTContext,229 const ASTRecordLayout &RL) {230 struct FieldInfo {231 CharUnits Align;232 CharUnits Size;233 const FieldDecl *Field;234 bool operator<(const FieldInfo &RHS) const {235 // Order from small alignments to large alignments,236 // then large sizes to small sizes.237 // then large field indices to small field indices238 return std::make_tuple(Align, -Size,239 Field ? -static_cast<int>(Field->getFieldIndex())240 : 0) <241 std::make_tuple(242 RHS.Align, -RHS.Size,243 RHS.Field ? -static_cast<int>(RHS.Field->getFieldIndex())244 : 0);245 }246 };247 SmallVector<FieldInfo, 20> Fields;248 auto GatherSizesAndAlignments = [](const FieldDecl *FD) {249 FieldInfo RetVal;250 RetVal.Field = FD;251 auto &Ctx = FD->getASTContext();252 auto Info = Ctx.getTypeInfoInChars(FD->getType());253 RetVal.Size = FD->isZeroSize(Ctx) ? CharUnits::Zero() : Info.Width;254 RetVal.Align = Info.Align;255 assert(llvm::isPowerOf2_64(RetVal.Align.getQuantity()));256 if (auto Max = FD->getMaxAlignment())257 RetVal.Align = std::max(Ctx.toCharUnitsFromBits(Max), RetVal.Align);258 return RetVal;259 };260 std::transform(RD->field_begin(), RD->field_end(),261 std::back_inserter(Fields), GatherSizesAndAlignments);262 llvm::sort(Fields);263 // This lets us skip over vptrs and non-virtual bases,264 // so that we can just worry about the fields in our object.265 // Note that this does cause us to miss some cases where we266 // could pack more bytes in to a base class's tail padding.267 CharUnits NewOffset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0));268 CharUnits NewPad;269 SmallVector<const FieldDecl *, 20> OptimalFieldsOrder;270 while (!Fields.empty()) {271 unsigned TrailingZeros =272 llvm::countr_zero((unsigned long long)NewOffset.getQuantity());273 // If NewOffset is zero, then countTrailingZeros will be 64. Shifting274 // 64 will overflow our unsigned long long. Shifting 63 will turn275 // our long long (and CharUnits internal type) negative. So shift 62.276 long long CurAlignmentBits = 1ull << (std::min)(TrailingZeros, 62u);277 CharUnits CurAlignment = CharUnits::fromQuantity(CurAlignmentBits);278 FieldInfo InsertPoint = {CurAlignment, CharUnits::Zero(), nullptr};279 280 // In the typical case, this will find the last element281 // of the vector. We won't find a middle element unless282 // we started on a poorly aligned address or have an overly283 // aligned field.284 auto Iter = llvm::upper_bound(Fields, InsertPoint);285 if (Iter != Fields.begin()) {286 // We found a field that we can layout with the current alignment.287 --Iter;288 NewOffset += Iter->Size;289 OptimalFieldsOrder.push_back(Iter->Field);290 Fields.erase(Iter);291 } else {292 // We are poorly aligned, and we need to pad in order to layout another293 // field. Round up to at least the smallest field alignment that we294 // currently have.295 CharUnits NextOffset = NewOffset.alignTo(Fields[0].Align);296 NewPad += NextOffset - NewOffset;297 NewOffset = NextOffset;298 }299 }300 // Calculate tail padding.301 CharUnits NewSize = NewOffset.alignTo(RL.getAlignment());302 NewPad += NewSize - NewOffset;303 return {NewPad, std::move(OptimalFieldsOrder)};304 }305 306 void reportRecord(307 const ASTContext &Ctx, const RecordDecl *RD, CharUnits BaselinePad,308 CharUnits OptimalPad,309 const SmallVector<const FieldDecl *, 20> &OptimalFieldsOrder) const {310 SmallString<100> Buf;311 llvm::raw_svector_ostream Os(Buf);312 Os << "Excessive padding in '";313 QualType(Ctx.getCanonicalTagType(RD)).print(Os, LangOptions());314 Os << "'";315 316 if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) {317 // TODO: make this show up better in the console output and in318 // the HTML. Maybe just make it show up in HTML like the path319 // diagnostics show.320 SourceLocation ILoc = TSD->getPointOfInstantiation();321 if (ILoc.isValid())322 Os << " instantiated here: "323 << ILoc.printToString(BR->getSourceManager());324 }325 326 Os << " (" << BaselinePad.getQuantity() << " padding bytes, where "327 << OptimalPad.getQuantity() << " is optimal). "328 << "Optimal fields order: ";329 for (const auto *FD : OptimalFieldsOrder)330 Os << FD->getName() << ", ";331 Os << "consider reordering the fields or adding explicit padding "332 "members.";333 334 PathDiagnosticLocation CELoc =335 PathDiagnosticLocation::create(RD, BR->getSourceManager());336 auto Report = std::make_unique<BasicBugReport>(PaddingBug, Os.str(), CELoc);337 Report->setDeclWithIssue(RD);338 Report->addRange(RD->getSourceRange());339 BR->emitReport(std::move(Report));340 }341};342} // namespace343 344void ento::registerPaddingChecker(CheckerManager &Mgr) {345 auto *Checker = Mgr.registerChecker<PaddingChecker>();346 Checker->AllowedPad = Mgr.getAnalyzerOptions()347 .getCheckerIntegerOption(Checker, "AllowedPad");348 if (Checker->AllowedPad < 0)349 Mgr.reportInvalidCheckerOptionValue(350 Checker, "AllowedPad", "a non-negative value");351}352 353bool ento::shouldRegisterPaddingChecker(const CheckerManager &mgr) {354 return true;355}356