Coverage Report

Created: 2019-07-24 05:18

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