clang  10.0.0svn
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  // This checker only cares about the padded size of the
197  // field, and not the data size. If the field is a record
198  // with tail padding, then we won't put that number in our
199  // total because reordering fields won't fix that problem.
200  CharUnits FieldSize = ASTContext.getTypeSizeInChars(FD->getType());
201  auto FieldOffsetBits = RL.getFieldOffset(FD->getFieldIndex());
202  CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(FieldOffsetBits);
203  PaddingSum += (FieldOffset - Offset);
204  Offset = FieldOffset + FieldSize;
205  }
206  PaddingSum += RL.getSize() - Offset;
207  return PaddingSum;
208  }
209 
210  /// Optimal padding overview:
211  /// 1. Find a close approximation to where we can place our first field.
212  /// This will usually be at offset 0.
213  /// 2. Try to find the best field that can legally be placed at the current
214  /// offset.
215  /// a. "Best" is the largest alignment that is legal, but smallest size.
216  /// This is to account for overly aligned types.
217  /// 3. If no fields can fit, pad by rounding the current offset up to the
218  /// smallest alignment requirement of our fields. Measure and track the
219  // amount of padding added. Go back to 2.
220  /// 4. Increment the current offset by the size of the chosen field.
221  /// 5. Remove the chosen field from the set of future possibilities.
222  /// 6. Go back to 2 if there are still unplaced fields.
223  /// 7. Add tail padding by rounding the current offset up to the structure
224  /// alignment. Track the amount of padding added.
225 
226  static std::pair<CharUnits, SmallVector<const FieldDecl *, 20>>
227  calculateOptimalPad(const RecordDecl *RD, const ASTContext &ASTContext,
228  const ASTRecordLayout &RL) {
229  struct FieldInfo {
230  CharUnits Align;
231  CharUnits Size;
232  const FieldDecl *Field;
233  bool operator<(const FieldInfo &RHS) const {
234  // Order from small alignments to large alignments,
235  // then large sizes to small sizes.
236  // then large field indices to small field indices
237  return std::make_tuple(Align, -Size,
238  Field ? -static_cast<int>(Field->getFieldIndex())
239  : 0) <
240  std::make_tuple(
241  RHS.Align, -RHS.Size,
242  RHS.Field ? -static_cast<int>(RHS.Field->getFieldIndex())
243  : 0);
244  }
245  };
247  auto GatherSizesAndAlignments = [](const FieldDecl *FD) {
248  FieldInfo RetVal;
249  RetVal.Field = FD;
250  auto &Ctx = FD->getASTContext();
251  std::tie(RetVal.Size, RetVal.Align) =
252  Ctx.getTypeInfoInChars(FD->getType());
253  assert(llvm::isPowerOf2_64(RetVal.Align.getQuantity()));
254  if (auto Max = FD->getMaxAlignment())
255  RetVal.Align = std::max(Ctx.toCharUnitsFromBits(Max), RetVal.Align);
256  return RetVal;
257  };
258  std::transform(RD->field_begin(), RD->field_end(),
259  std::back_inserter(Fields), GatherSizesAndAlignments);
260  llvm::sort(Fields);
261  // This lets us skip over vptrs and non-virtual bases,
262  // so that we can just worry about the fields in our object.
263  // Note that this does cause us to miss some cases where we
264  // could pack more bytes in to a base class's tail padding.
265  CharUnits NewOffset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0));
266  CharUnits NewPad;
267  SmallVector<const FieldDecl *, 20> OptimalFieldsOrder;
268  while (!Fields.empty()) {
269  unsigned TrailingZeros =
270  llvm::countTrailingZeros((unsigned long long)NewOffset.getQuantity());
271  // If NewOffset is zero, then countTrailingZeros will be 64. Shifting
272  // 64 will overflow our unsigned long long. Shifting 63 will turn
273  // our long long (and CharUnits internal type) negative. So shift 62.
274  long long CurAlignmentBits = 1ull << (std::min)(TrailingZeros, 62u);
275  CharUnits CurAlignment = CharUnits::fromQuantity(CurAlignmentBits);
276  FieldInfo InsertPoint = {CurAlignment, CharUnits::Zero(), nullptr};
277 
278  // In the typical case, this will find the last element
279  // of the vector. We won't find a middle element unless
280  // we started on a poorly aligned address or have an overly
281  // aligned field.
282  auto Iter = llvm::upper_bound(Fields, InsertPoint);
283  if (Iter != Fields.begin()) {
284  // We found a field that we can layout with the current alignment.
285  --Iter;
286  NewOffset += Iter->Size;
287  OptimalFieldsOrder.push_back(Iter->Field);
288  Fields.erase(Iter);
289  } else {
290  // We are poorly aligned, and we need to pad in order to layout another
291  // field. Round up to at least the smallest field alignment that we
292  // currently have.
293  CharUnits NextOffset = NewOffset.alignTo(Fields[0].Align);
294  NewPad += NextOffset - NewOffset;
295  NewOffset = NextOffset;
296  }
297  }
298  // Calculate tail padding.
299  CharUnits NewSize = NewOffset.alignTo(RL.getAlignment());
300  NewPad += NewSize - NewOffset;
301  return {NewPad, std::move(OptimalFieldsOrder)};
302  }
303 
304  void reportRecord(
305  const RecordDecl *RD, CharUnits BaselinePad, CharUnits OptimalPad,
306  const SmallVector<const FieldDecl *, 20> &OptimalFieldsOrder) const {
307  if (!PaddingBug)
308  PaddingBug =
309  std::make_unique<BugType>(this, "Excessive Padding", "Performance");
310 
311  SmallString<100> Buf;
312  llvm::raw_svector_ostream Os(Buf);
313  Os << "Excessive padding in '";
315  LangOptions())
316  << "'";
317 
318  if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) {
319  // TODO: make this show up better in the console output and in
320  // the HTML. Maybe just make it show up in HTML like the path
321  // diagnostics show.
322  SourceLocation ILoc = TSD->getPointOfInstantiation();
323  if (ILoc.isValid())
324  Os << " instantiated here: "
325  << ILoc.printToString(BR->getSourceManager());
326  }
327 
328  Os << " (" << BaselinePad.getQuantity() << " padding bytes, where "
329  << OptimalPad.getQuantity() << " is optimal). \n"
330  << "Optimal fields order: \n";
331  for (const auto *FD : OptimalFieldsOrder)
332  Os << FD->getName() << ", \n";
333  Os << "consider reordering the fields or adding explicit padding "
334  "members.";
335 
336  PathDiagnosticLocation CELoc =
337  PathDiagnosticLocation::create(RD, BR->getSourceManager());
338  auto Report =
339  std::make_unique<BasicBugReport>(*PaddingBug, Os.str(), CELoc);
340  Report->setDeclWithIssue(RD);
341  Report->addRange(RD->getSourceRange());
342  BR->emitReport(std::move(Report));
343  }
344 };
345 } // namespace
346 
347 void ento::registerPaddingChecker(CheckerManager &Mgr) {
348  auto *Checker = Mgr.registerChecker<PaddingChecker>();
349  Checker->AllowedPad = Mgr.getAnalyzerOptions()
350  .getCheckerIntegerOption(Checker, "AllowedPad");
351  if (Checker->AllowedPad < 0)
352  Mgr.reportInvalidCheckerOptionValue(
353  Checker, "AllowedPad", "a non-negative value");
354 }
355 
356 bool ento::shouldRegisterPaddingChecker(const LangOptions &LO) {
357  return true;
358 }
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:188
A (possibly-)qualified type.
Definition: Type.h:643
const ASTRecordLayout & getASTRecordLayout(const RecordDecl *D) const
Get or compute information about the layout of the specified record (struct/union/class) D...
const Type * getTypeForDecl() const
Definition: Decl.h:2967
Defines the C++ template declaration subclasses.
unsigned getFieldIndex() const
Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...
Definition: Decl.cpp:3992
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2860
bool isZero() const
isZero - Test whether the quantity equals zero.
Definition: CharUnits.h:116
CharUnits getAlignment() const
getAlignment - Get the record alignment in characters.
Definition: RecordLayout.h:176
QualType getElementType() const
Definition: Type.h:2881
Represents a variable declaration or definition.
Definition: Decl.h:827
const T * getAs() const
Member-template getAs<specific type>&#39;.
Definition: Type.h:6858
bool field_empty() const
Definition: Decl.h:3885
CharacteristicKind
Indicates whether a file or directory holds normal user code, system code, or system code which is im...
Definition: SourceManager.h:77
The collection of all-type qualifiers we support.
Definition: Type.h:137
Represents a struct/union/class.
Definition: Decl.h:3662
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:160
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
Definition: Decl.h:3867
field_range fields() const
Definition: Decl.h:3877
Represents a member of a struct/union/class.
Definition: Decl.h:2643
static CharUnits Zero()
Zero - Construct a CharUnits quantity of zero.
Definition: CharUnits.h:53
__DEVICE__ int max(int __a, int __b)
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
CharUnits - This is an opaque type for sizes expressed in character units.
Definition: CharUnits.h:38
const ArrayType * getAsArrayTypeUnsafe() const
A variant of getAs<> for array types which silently discards qualifiers from the outermost type...
Definition: Type.h:6909
field_iterator field_begin() const
Definition: Decl.cpp:4343
static PathDiagnosticLocation create(const Decl *D, const SourceManager &SM)
Create a location corresponding to the given declaration.
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool isNegative() const
isNegative - Test whether the quantity is less than zero.
Definition: CharUnits.h:125
QuantityType getQuantity() const
getQuantity - Get the raw integer representation of this quantity.
Definition: CharUnits.h:179
unsigned Offset
Definition: Format.cpp:1809
ASTRecordLayout - This class contains layout information for one RecordDecl, which is a struct/union/...
Definition: RecordLayout.h:38
field_iterator field_end() const
Definition: Decl.h:3880
static CharUnits fromQuantity(QuantityType Quantity)
fromQuantity - Construct a CharUnits quantity from a raw integer type.
Definition: CharUnits.h:63
std::string getAsString() const
RecordDecl * getDecl() const
Definition: Type.h:4454
uint64_t getFieldOffset(unsigned FieldNo) const
getFieldOffset - Get the offset of the given field index, in bits.
Definition: RecordLayout.h:190
Kind
Encodes a location in the source.
ASTContext & getASTContext() const LLVM_READONLY
Definition: DeclBase.cpp:377
SourceRange getSourceRange() const override LLVM_READONLY
Source range that this declaration covers.
Definition: Decl.cpp:4055
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Dataflow Directional Tag Classes.
bool isValid() const
Return true if this is a valid SourceLocation object.
CharUnits getSize() const
getSize - Get the record size in characters.
Definition: RecordLayout.h:183
bool isIncompleteArrayType() const
Definition: Type.h:6455
A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...
Definition: Type.h:4444
CharUnits toCharUnitsFromBits(int64_t BitSize) const
Convert a size in bits to a size in characters.
std::string printToString(const SourceManager &SM) const
__DEVICE__ int min(int __a, int __b)
The top declaration context.
Definition: Decl.h:107
bool isUnion() const
Definition: Decl.h:3321
CharUnits getTypeSizeInChars(QualType T) const
Return the size of the specified (complete) type T, in characters.
QualType getType() const
Definition: Decl.h:655
Represents the canonical version of C arrays with a specified constant size.
Definition: Type.h:2906
SourceLocation getLocation() const
Definition: DeclBase.h:429