clang  15.0.0git
PaddingChecker.cpp
Go to the documentation of this file.
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 
15 #include "clang/AST/CharUnits.h"
16 #include "clang/AST/DeclTemplate.h"
17 #include "clang/AST/RecordLayout.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();
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;
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 (std::any_of(RD->field_begin(), RD->field_end(), 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;
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  };
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.
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 '";
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 }
clang::ASTContext::getTypeSizeInChars
CharUnits getTypeSizeInChars(QualType T) const
Return the size of the specified (complete) type T, in characters.
Definition: ASTContext.cpp:2471
max
__DEVICE__ int max(int __a, int __b)
Definition: __clang_cuda_math.h:196
clang::Decl::getASTContext
ASTContext & getASTContext() const LLVM_READONLY
Definition: DeclBase.cpp:414
clang::Type::getAsArrayTypeUnsafe
const ArrayType * getAsArrayTypeUnsafe() const
A variant of getAs<> for array types which silently discards qualifiers from the outermost type.
Definition: Type.h:7355
clang::RecordDecl::field_begin
field_iterator field_begin() const
Definition: Decl.cpp:4683
clang::ASTRecordLayout::getFieldOffset
uint64_t getFieldOffset(unsigned FieldNo) const
getFieldOffset - Get the offset of the given field index, in bits.
Definition: RecordLayout.h:200
clang::ConstantArrayType
Represents the canonical version of C arrays with a specified constant size.
Definition: Type.h:3001
clang::TagDecl::getSourceRange
SourceRange getSourceRange() const override LLVM_READONLY
Source range that this declaration covers.
Definition: Decl.cpp:4368
llvm::SmallVector
Definition: LLVM.h:38
clang::RecordDecl::field_empty
bool field_empty() const
Definition: Decl.h:4142
clang::SourceLocation
Encodes a location in the source.
Definition: SourceLocation.h:86
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:731
clang::TypeDecl::getTypeForDecl
const Type * getTypeForDecl() const
Definition: Decl.h:3189
clang::FieldDecl
Represents a member of a struct/union/class.
Definition: Decl.h:2862
clang::Qualifiers
The collection of all-type qualifiers we support.
Definition: Type.h:147
clang::ASTRecordLayout::getSize
CharUnits getSize() const
getSize - Get the record size in characters.
Definition: RecordLayout.h:193
clang::RecordDecl::getDefinition
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
Definition: Decl.h:4119
clang::SrcMgr::CharacteristicKind
CharacteristicKind
Indicates whether a file or directory holds normal user code, system code, or system code which is im...
Definition: SourceManager.h:79
Offset
unsigned Offset
Definition: Format.cpp:2574
uint64_t
unsigned long uint64_t
Definition: hlsl_basic_types.h:24
clang::TranslationUnitDecl
The top declaration context.
Definition: Decl.h:80
min
__DEVICE__ int min(int __a, int __b)
Definition: __clang_cuda_math.h:197
clang::RecordType
A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...
Definition: Type.h:4706
BuiltinCheckerRegistration.h
DeclTemplate.h
clang::ento::PathDiagnosticLocation::create
static PathDiagnosticLocation create(const Decl *D, const SourceManager &SM)
Create a location corresponding to the given declaration.
Definition: PathDiagnostic.h:248
clang::CharUnits::fromQuantity
static CharUnits fromQuantity(QuantityType Quantity)
fromQuantity - Construct a CharUnits quantity from a raw integer type.
Definition: CharUnits.h:63
BugReporter.h
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:208
clang::ArrayType
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2955
clang::RecursiveASTVisitor
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
Definition: RecursiveASTVisitor.h:165
DriverDiagnostic.h
clang::Type::getAs
const T * getAs() const
Member-template getAs<specific type>'.
Definition: Type.h:7302
clang::index::SymbolKind::Field
@ Field
llvm::SmallString
Definition: LLVM.h:37
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:874
clang::QualType::getAsString
std::string getAsString() const
Definition: TypePrinter.cpp:2299
clang::TagDecl::isUnion
bool isUnion() const
Definition: Decl.h:3561
clang::SrcMgr::C_User
@ C_User
Definition: SourceManager.h:80
clang::CharUnits::Zero
static CharUnits Zero()
Zero - Construct a CharUnits quantity of zero.
Definition: CharUnits.h:53
clang::CharUnits::isNegative
bool isNegative() const
isNegative - Test whether the quantity is less than zero.
Definition: CharUnits.h:125
CharUnits.h
clang::ASTRecordLayout
ASTRecordLayout - This class contains layout information for one RecordDecl, which is a struct/union/...
Definition: RecordLayout.h:38
clang::syntax::NodeRole::Size
@ Size
BugType.h
clang::CharUnits::isZero
bool isZero() const
isZero - Test whether the quantity equals zero.
Definition: CharUnits.h:116
clang::Type::isIncompleteArrayType
bool isIncompleteArrayType() const
Definition: Type.h:6881
clang::RecordDecl::fields
field_range fields() const
Definition: Decl.h:4134
clang::CharUnits::alignTo
CharUnits alignTo(const CharUnits &Align) const
alignTo - Returns the next integer (mod 2**64) that is greater than or equal to this quantity and is ...
Definition: CharUnits.h:194
clang::RecordDecl::field_end
field_iterator field_end() const
Definition: Decl.h:4137
clang::LangOptions
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:78
clang::ObjCPropertyAttribute::Kind
Kind
Definition: DeclObjCCommon.h:22
int64_t
long int64_t
Definition: hlsl_basic_types.h:25
Checker.h
clang
Definition: CalledOnceCheck.h:17
clang::ASTContext::toCharUnitsFromBits
CharUnits toCharUnitsFromBits(int64_t BitSize) const
Convert a size in bits to a size in characters.
Definition: ASTContext.cpp:2460
RecursiveASTVisitor.h
clang::operator<
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Definition: DeclarationName.h:549
clang::SourceLocation::isValid
bool isValid() const
Return true if this is a valid SourceLocation object.
Definition: SourceLocation.h:110
clang::ASTRecordLayout::getAlignment
CharUnits getAlignment() const
getAlignment - Get the record alignment in characters.
Definition: RecordLayout.h:182
clang::ASTContext::getASTRecordLayout
const ASTRecordLayout & getASTRecordLayout(const RecordDecl *D) const
Get or compute information about the layout of the specified record (struct/union/class) D,...
Definition: RecordLayoutBuilder.cpp:3270
clang::RecordType::getDecl
RecordDecl * getDecl() const
Definition: Type.h:4716
clang::CharUnits
CharUnits - This is an opaque type for sizes expressed in character units.
Definition: CharUnits.h:38
clang::ValueDecl::getType
QualType getType() const
Definition: Decl.h:685
clang::ArrayType::getElementType
QualType getElementType() const
Definition: Type.h:2976
AnalysisManager.h
clang::Decl::getLocation
SourceLocation getLocation() const
Definition: DeclBase.h:432
clang::RecordDecl
Represents a struct/union/class.
Definition: Decl.h:3908
clang::CharUnits::getQuantity
QuantityType getQuantity() const
getQuantity - Get the raw integer representation of this quantity.
Definition: CharUnits.h:179
RecordLayout.h
clang::SourceLocation::printToString
std::string printToString(const SourceManager &SM) const
Definition: SourceLocation.cpp:89