contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

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