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