//=======- 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 = 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);
}
/// \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 auto &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 CharUnits calculateOptimalPad(const RecordDecl *RD,
const ASTContext &ASTContext,
const ASTRecordLayout &RL) {
struct CharUnitPair {
CharUnits Align;
CharUnits Size;
bool operator<(const CharUnitPair &RHS) const {
// Order from small alignments to large alignments,
// then large sizes to small sizes.
return std::make_pair(Align, -Size) <
std::make_pair(RHS.Align, -RHS.Size);
}
};
SmallVector<CharUnitPair, 20> Fields;
auto GatherSizesAndAlignments = [](const FieldDecl *FD) {
CharUnitPair RetVal;
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;
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);
CharUnitPair InsertPoint = {CurAlignment, CharUnits::Zero()};
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;
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.RoundUpToAlignment(Fields[0].Align);
NewPad += NextOffset - NewOffset;
NewOffset = NextOffset;
}
}
// Calculate tail padding.
CharUnits NewSize = NewOffset.RoundUpToAlignment(RL.getAlignment());
NewPad += NewSize - NewOffset;
return NewPad;
}
void reportRecord(const RecordDecl *RD, CharUnits BaselinePad,
CharUnits TargetPad) 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()) << "'";
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 "
<< TargetPad.getQuantity() << " is optimal). 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>();
}