//=======- PaddingChecker.cpp ------------------------------------*- C++ -*-==// | |
// | |
// The LLVM Compiler Infrastructure | |
// | |
// This file is distributed under the University of Illinois Open Source | |
// License. See LICENSE.TXT for details. | |
// | |
//===----------------------------------------------------------------------===// | |
// | |
// This file defines a checker that checks for padding that could be | |
// removed by re-ordering members. | |
// | |
//===----------------------------------------------------------------------===// | |
#include "ClangSACheckers.h" | |
#include "clang/AST/CharUnits.h" | |
#include "clang/AST/DeclTemplate.h" | |
#include "clang/AST/RecordLayout.h" | |
#include "clang/AST/RecursiveASTVisitor.h" | |
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" | |
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" | |
#include "clang/StaticAnalyzer/Core/Checker.h" | |
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" | |
#include "llvm/ADT/SmallString.h" | |
#include "llvm/Support/MathExtras.h" | |
#include "llvm/Support/raw_ostream.h" | |
#include <numeric> | |
using namespace clang; | |
using namespace ento; | |
namespace { | |
class PaddingChecker : public Checker<check::ASTDecl<TranslationUnitDecl>> { | |
private: | |
mutable std::unique_ptr<BugType> PaddingBug; | |
mutable int64_t AllowedPad; | |
mutable BugReporter *BR; | |
public: | |
void checkASTDecl(const TranslationUnitDecl *TUD, AnalysisManager &MGR, | |
BugReporter &BRArg) const { | |
BR = &BRArg; | |
AllowedPad = | |
MGR.getAnalyzerOptions().getOptionAsInteger("AllowedPad", 24, this); | |
assert(AllowedPad >= 0 && "AllowedPad option should be non-negative"); | |
// The calls to checkAST* from AnalysisConsumer don't | |
// visit template instantiations or lambda classes. We | |
// want to visit those, so we make our own RecursiveASTVisitor. | |
struct LocalVisitor : public RecursiveASTVisitor<LocalVisitor> { | |
const PaddingChecker *Checker; | |
bool shouldVisitTemplateInstantiations() const { return true; } | |
bool shouldVisitImplicitCode() const { return true; } | |
explicit LocalVisitor(const PaddingChecker *Checker) : Checker(Checker) {} | |
bool VisitRecordDecl(const RecordDecl *RD) { | |
Checker->visitRecord(RD); | |
return true; | |
} | |
bool VisitVarDecl(const VarDecl *VD) { | |
Checker->visitVariable(VD); | |
return true; | |
} | |
// TODO: Visit array new and mallocs for arrays. | |
}; | |
LocalVisitor visitor(this); | |
visitor.TraverseDecl(const_cast<TranslationUnitDecl *>(TUD)); | |
} | |
/// \brief Look for records of overly padded types. If padding * | |
/// PadMultiplier exceeds AllowedPad, then generate a report. | |
/// PadMultiplier is used to share code with the array padding | |
/// checker. | |
void visitRecord(const RecordDecl *RD, uint64_t PadMultiplier = 1) const { | |
if (shouldSkipDecl(RD)) | |
return; | |
auto &ASTContext = RD->getASTContext(); | |
const ASTRecordLayout &RL = ASTContext.getASTRecordLayout(RD); | |
assert(llvm::isPowerOf2_64(RL.getAlignment().getQuantity())); | |
CharUnits BaselinePad = calculateBaselinePad(RD, ASTContext, RL); | |
if (BaselinePad.isZero()) | |
return; | |
CharUnits OptimalPad; | |
SmallVector<const FieldDecl *, 20> OptimalFieldsOrder; | |
std::tie(OptimalPad, OptimalFieldsOrder) = | |
calculateOptimalPad(RD, ASTContext, RL); | |
CharUnits DiffPad = PadMultiplier * (BaselinePad - OptimalPad); | |
if (DiffPad.getQuantity() <= AllowedPad) { | |
assert(!DiffPad.isNegative() && "DiffPad should not be negative"); | |
// There is not enough excess padding to trigger a warning. | |
return; | |
} | |
reportRecord(RD, BaselinePad, OptimalPad, OptimalFieldsOrder); | |
} | |
/// \brief Look for arrays of overly padded types. If the padding of the | |
/// array type exceeds AllowedPad, then generate a report. | |
void visitVariable(const VarDecl *VD) const { | |
const ArrayType *ArrTy = VD->getType()->getAsArrayTypeUnsafe(); | |
if (ArrTy == nullptr) | |
return; | |
uint64_t Elts = 0; | |
if (const ConstantArrayType *CArrTy = dyn_cast<ConstantArrayType>(ArrTy)) | |
Elts = CArrTy->getSize().getZExtValue(); | |
if (Elts == 0) | |
return; | |
const RecordType *RT = ArrTy->getElementType()->getAs<RecordType>(); | |
if (RT == nullptr) | |
return; | |
// TODO: Recurse into the fields and base classes to see if any | |
// of those have excess padding. | |
visitRecord(RT->getDecl(), Elts); | |
} | |
bool shouldSkipDecl(const RecordDecl *RD) const { | |
auto Location = RD->getLocation(); | |
// If the construct doesn't have a source file, then it's not something | |
// we want to diagnose. | |
if (!Location.isValid()) | |
return true; | |
SrcMgr::CharacteristicKind Kind = | |
BR->getSourceManager().getFileCharacteristic(Location); | |
// Throw out all records that come from system headers. | |
if (Kind != SrcMgr::C_User) | |
return true; | |
// Not going to attempt to optimize unions. | |
if (RD->isUnion()) | |
return true; | |
// How do you reorder fields if you haven't got any? | |
if (RD->field_empty()) | |
return true; | |
if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD)) { | |
// Tail padding with base classes ends up being very complicated. | |
// We will skip objects with base classes for now. | |
if (CXXRD->getNumBases() != 0) | |
return true; | |
// Virtual bases are complicated, skipping those for now. | |
if (CXXRD->getNumVBases() != 0) | |
return true; | |
// Can't layout a template, so skip it. We do still layout the | |
// instantiations though. | |
if (CXXRD->getTypeForDecl()->isDependentType()) | |
return true; | |
if (CXXRD->getTypeForDecl()->isInstantiationDependentType()) | |
return true; | |
} | |
auto IsTrickyField = [](const FieldDecl *FD) -> bool { | |
// Bitfield layout is hard. | |
if (FD->isBitField()) | |
return true; | |
// Variable length arrays are tricky too. | |
QualType Ty = FD->getType(); | |
if (Ty->isIncompleteArrayType()) | |
return true; | |
return false; | |
}; | |
if (std::any_of(RD->field_begin(), RD->field_end(), IsTrickyField)) | |
return true; | |
return false; | |
} | |
static CharUnits calculateBaselinePad(const RecordDecl *RD, | |
const ASTContext &ASTContext, | |
const ASTRecordLayout &RL) { | |
CharUnits PaddingSum; | |
CharUnits Offset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0)); | |
for (const FieldDecl *FD : RD->fields()) { | |
// This checker only cares about the padded size of the | |
// field, and not the data size. If the field is a record | |
// with tail padding, then we won't put that number in our | |
// total because reordering fields won't fix that problem. | |
CharUnits FieldSize = ASTContext.getTypeSizeInChars(FD->getType()); | |
auto FieldOffsetBits = RL.getFieldOffset(FD->getFieldIndex()); | |
CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(FieldOffsetBits); | |
PaddingSum += (FieldOffset - Offset); | |
Offset = FieldOffset + FieldSize; | |
} | |
PaddingSum += RL.getSize() - Offset; | |
return PaddingSum; | |
} | |
/// Optimal padding overview: | |
/// 1. Find a close approximation to where we can place our first field. | |
/// This will usually be at offset 0. | |
/// 2. Try to find the best field that can legally be placed at the current | |
/// offset. | |
/// a. "Best" is the largest alignment that is legal, but smallest size. | |
/// This is to account for overly aligned types. | |
/// 3. If no fields can fit, pad by rounding the current offset up to the | |
/// smallest alignment requirement of our fields. Measure and track the | |
// amount of padding added. Go back to 2. | |
/// 4. Increment the current offset by the size of the chosen field. | |
/// 5. Remove the chosen field from the set of future possibilities. | |
/// 6. Go back to 2 if there are still unplaced fields. | |
/// 7. Add tail padding by rounding the current offset up to the structure | |
/// alignment. Track the amount of padding added. | |
static std::pair<CharUnits, SmallVector<const FieldDecl *, 20>> | |
calculateOptimalPad(const RecordDecl *RD, const ASTContext &ASTContext, | |
const ASTRecordLayout &RL) { | |
struct FieldInfo { | |
CharUnits Align; | |
CharUnits Size; | |
const FieldDecl *Field; | |
bool operator<(const FieldInfo &RHS) const { | |
// Order from small alignments to large alignments, | |
// then large sizes to small sizes. | |
// then large field indices to small field indices | |
return std::make_tuple(Align, -Size, | |
Field ? -static_cast<int>(Field->getFieldIndex()) | |
: 0) < | |
std::make_tuple( | |
RHS.Align, -RHS.Size, | |
RHS.Field ? -static_cast<int>(RHS.Field->getFieldIndex()) | |
: 0); | |
} | |
}; | |
SmallVector<FieldInfo, 20> Fields; | |
auto GatherSizesAndAlignments = [](const FieldDecl *FD) { | |
FieldInfo RetVal; | |
RetVal.Field = FD; | |
auto &Ctx = FD->getASTContext(); | |
std::tie(RetVal.Size, RetVal.Align) = | |
Ctx.getTypeInfoInChars(FD->getType()); | |
assert(llvm::isPowerOf2_64(RetVal.Align.getQuantity())); | |
if (auto Max = FD->getMaxAlignment()) | |
RetVal.Align = std::max(Ctx.toCharUnitsFromBits(Max), RetVal.Align); | |
return RetVal; | |
}; | |
std::transform(RD->field_begin(), RD->field_end(), | |
std::back_inserter(Fields), GatherSizesAndAlignments); | |
std::sort(Fields.begin(), Fields.end()); | |
// This lets us skip over vptrs and non-virtual bases, | |
// so that we can just worry about the fields in our object. | |
// Note that this does cause us to miss some cases where we | |
// could pack more bytes in to a base class's tail padding. | |
CharUnits NewOffset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0)); | |
CharUnits NewPad; | |
SmallVector<const FieldDecl *, 20> OptimalFieldsOrder; | |
while (!Fields.empty()) { | |
unsigned TrailingZeros = | |
llvm::countTrailingZeros((unsigned long long)NewOffset.getQuantity()); | |
// If NewOffset is zero, then countTrailingZeros will be 64. Shifting | |
// 64 will overflow our unsigned long long. Shifting 63 will turn | |
// our long long (and CharUnits internal type) negative. So shift 62. | |
long long CurAlignmentBits = 1ull << (std::min)(TrailingZeros, 62u); | |
CharUnits CurAlignment = CharUnits::fromQuantity(CurAlignmentBits); | |
FieldInfo InsertPoint = {CurAlignment, CharUnits::Zero(), nullptr}; | |
auto CurBegin = Fields.begin(); | |
auto CurEnd = Fields.end(); | |
// In the typical case, this will find the last element | |
// of the vector. We won't find a middle element unless | |
// we started on a poorly aligned address or have an overly | |
// aligned field. | |
auto Iter = std::upper_bound(CurBegin, CurEnd, InsertPoint); | |
if (Iter != CurBegin) { | |
// We found a field that we can layout with the current alignment. | |
--Iter; | |
NewOffset += Iter->Size; | |
OptimalFieldsOrder.push_back(Iter->Field); | |
Fields.erase(Iter); | |
} else { | |
// We are poorly aligned, and we need to pad in order to layout another | |
// field. Round up to at least the smallest field alignment that we | |
// currently have. | |
CharUnits NextOffset = NewOffset.alignTo(Fields[0].Align); | |
NewPad += NextOffset - NewOffset; | |
NewOffset = NextOffset; | |
} | |
} | |
// Calculate tail padding. | |
CharUnits NewSize = NewOffset.alignTo(RL.getAlignment()); | |
NewPad += NewSize - NewOffset; | |
return {NewPad, std::move(OptimalFieldsOrder)}; | |
} | |
void reportRecord( | |
const RecordDecl *RD, CharUnits BaselinePad, CharUnits OptimalPad, | |
const SmallVector<const FieldDecl *, 20> &OptimalFieldsOrder) const { | |
if (!PaddingBug) | |
PaddingBug = | |
llvm::make_unique<BugType>(this, "Excessive Padding", "Performance"); | |
SmallString<100> Buf; | |
llvm::raw_svector_ostream Os(Buf); | |
Os << "Excessive padding in '"; | |
Os << QualType::getAsString(RD->getTypeForDecl(), Qualifiers(), | |
LangOptions()) | |
<< "'"; | |
if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) { | |
// TODO: make this show up better in the console output and in | |
// the HTML. Maybe just make it show up in HTML like the path | |
// diagnostics show. | |
SourceLocation ILoc = TSD->getPointOfInstantiation(); | |
if (ILoc.isValid()) | |
Os << " instantiated here: " | |
<< ILoc.printToString(BR->getSourceManager()); | |
} | |
Os << " (" << BaselinePad.getQuantity() << " padding bytes, where " | |
<< OptimalPad.getQuantity() << " is optimal). \n" | |
<< "Optimal fields order: \n"; | |
for (const auto *FD : OptimalFieldsOrder) | |
Os << FD->getName() << ", \n"; | |
Os << "consider reordering the fields or adding explicit padding " | |
"members."; | |
PathDiagnosticLocation CELoc = | |
PathDiagnosticLocation::create(RD, BR->getSourceManager()); | |
auto Report = llvm::make_unique<BugReport>(*PaddingBug, Os.str(), CELoc); | |
Report->setDeclWithIssue(RD); | |
Report->addRange(RD->getSourceRange()); | |
BR->emitReport(std::move(Report)); | |
} | |
}; | |
} | |
void ento::registerPaddingChecker(CheckerManager &Mgr) { | |
Mgr.registerChecker<PaddingChecker>(); | |
} |