Adding checker to detect excess padding in records

[bcraig]

Summary

The intent of this checker is to generate a report for any class / structure that could reduce its padding by reordering the fields. This results in a very noisy checker. To reduce the noise, this checker will currently only warn when the number of bytes over "optimal" is more than 24. This value is configurable with -analyzer-config performance.Padding:AllowedPad=N. Small values of AllowedPad have the potential to generate hundreds of reports, and gigabytes of HTML reports.

The checker searches for padding violations in two main ways. First, it goes record by record. A report is generated if the fields could be reordered in a way that reduces the padding by more than AllowedPad bytes. Second, the checker will generate a report if an array will cause more than AllowedPad padding bytes to be generated.

The record checker currently skips many ABI specific cases. Classes with base classes are skipped because base class tail padding is ABI specific. Bitfields are just plain hard, and duplicating that code seems like a bad idea. VLAs are both uncommon and non-trivial to fix.

The array checker isn't very thorough right now. It only checks to see if the element type's fields could be reordered, and it doesn't recursively check to see if any of the fields' fields could be reordered. At some point in the future, it would be nice if "arrays" could also look at array new usages and malloc patterns that appear to be creating arrays.

[Eugene.Zelenko]

I may be mistaken, but this check looks more appropriate for Clang-tidy.

[zaks.anna]

I may be mistaken, but this check looks more appropriate for Clang-tidy.

This is a syntactic check. Both clang-tidy as well as the clang static analyzer contain this type of checks. If we move all syntactic checks to clang-tidy, the users that use the analyzer but do not use clang-tidy will not receive the warnings. There is an issue in the opposite direction as well.

[bcraig]

In D14779#292066, @zaks.anna wrote:

I may be mistaken, but this check looks more appropriate for Clang-tidy.

This is a syntactic check. Both clang-tidy as well as the clang static analyzer contain this type of checks. If we move all syntactic checks to clang-tidy, the users that use the analyzer but do not use clang-tidy will not receive the warnings. There is an issue in the opposite direction as well.

I am looking into clang-tidy, and if that's the way we need to go, then I'll do it, but I have a preference for this to exist in the static analyzer side of things.

Note that clang-tidy users get this "for free". With no changes to clang tidy code, -checks=clang-analyzer-performance* will get you padding warnings.

[zaks.anna]

This is a partial review. I did not look at the padding calculations closely.

Have you run this over codebases other than clang? Are there any false positives?

Even with the default of 8, this checker is too noisy to justify turning on by default. Clang+LLVM has
hundreds of violations.

How did you pick the default? Should it be higher?
My main concern is that if the checker is too noisy on most codebases, people might just try it once and keep it turned off. Having a higher default will report less issues but they will be more interesting.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

12

Nit: Please, use proper punctuation in comments (in the implementation and test files).

34

This comment is redundant.

49

'Self' is a bit confusing since it's not LocalVisitor but the PaddingChecker class.

57

Why do we need to implement the visitation here? Can PaddingChecker just implement checkASTDecl(const RecordDecl *RD, ...) and checkASTDecl(const VarDecl *RD, ...)?

72

I'd just make the BugReporter and AllowedPad members to avoid passing them around.

89

This would be better expressed with assert(!DiffPad.isNegative() && "DiffPad should not be negative");

98

nit: Please, use doxygen style comments.

115

Should the rest of the function implementation be moved into a subroutine? Looks like copy and paste from visitRecord.

145

Do you get reports from system headers without this check?

210

Are you intentionally not using getTypeInfoDataSizeInChars? Can this lead to false positives? A comment would be helpful.

326

Why are you not testing for the full message in the tests? It is important to ensure that the information provided here does not regress.

[bcraig]

In D14779#292513, @zaks.anna wrote:

This is a partial review. I did not look at the padding calculations closely.

Have you run this over codebases other than clang? Are there any false positives?

I ran this over a large C code base, then spot checked the top dozen of so issues. I haven't seen a "real" false positive with the current implementation. I have seen plenty of structures where the specific layout was important and couldn't be changed. I haven't seen any cases where the checker reported excess padding when it wasn't true.

One of the reasons that I do not attempt to handle base classes is because of the fear of false positives.

Even with the default of 8, this checker is too noisy to justify turning on by default. Clang+LLVM has
hundreds of violations.

How did you pick the default? Should it be higher?
My main concern is that if the checker is too noisy on most codebases, people might just try it once and keep it turned off. Having a higher default will report less issues but they will be more interesting.

The number was picked by looking at the data. A huge portion of the results were in the general area of 8 bytes or lower. These generally felt like noisy reports unless I had more specific justification for them (like evidence of an array of the elements).

Should it be higher? As I get better at detecting arrays, then I think it makes sense to bump the raw value higher.

I think I'm fine with people only running this checker on occasion. It feels like a profiler in many ways, and the information doesn't go stale.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

57

I wanted to be able to visit template instantiations and the class portion of a lambda, and the AnalysisConsumer class that calls the varios checkAST* functions doesn't do that. Once I added this custom visitor, I stuck with it for the VarDecl.

I will add a comment mentioning my rationale.

72

I'm fine doing that, but I was under the impression that the checker was supposed to be as close to stateless as possible.

115

I'll make an attempt to do that. The two functions use BaselinePad and OptimalPad a little differently, which complicates things.

145

Yes. Turns out the structures for flock and flock64 have extra padding. And since those are in commonly included headers, you get that message a lot...

210

It is intentional, and I will add a comment.

In most cases, it doesn't matter what the data size of a field is, just what the aligned size is. In general, you can't put one object in another's tail padding. Note that my goal isn't to say how much padding there is in a structure, but how much you can reduce the padding by reordering the fields. Knowing the tail padding of a structure doesn't further that goal.

326

I wanted the tests to be fairly portable. The specific numbers change a fair amount between x86, x64, and Arm, and Hexagon. Any recommendation here? Maybe make a processor specific fork that has the full message?

[bcraig]

Addressed the bulk of Anna's review comments.

[zaks.anna]

I have seen plenty of structures where the specific layout was important and couldn't be changed.

Can you give specific examples of these? Can we develop heuristics for them?

These generally felt like noisy reports unless I had more specific justification for them (like evidence of
an array of the elements). Should it be higher? As I get better at detecting arrays, then I think it makes
sense to bump the raw value higher.

I think it's better to report many fewer issues that are real problems to "advertise" the checker. Once people see it's value, they can lower the threshold. If we report hundreds of issues, it will scare people off.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

73

That's true, but it does not matter for the syntactic checkers much.

146

I wonder why the analyzer diagnostic reporting mechanism does not take care of this.

323

I think it is important to check the numbers to make sure that logic does not regress. Maybe you could create one clone for x86 or only test on x86? Is testing on each architecture tests the code you wrote?

[bcraig]

In D14779#293236, @zaks.anna wrote:

I have seen plenty of structures where the specific layout was important and couldn't be changed.

Can you give specific examples of these? Can we develop heuristics for them?

The previously mentioned flock and flock64 structures are one example. These structures have ABI significance for that client, as they cross .so / .dll boundaries. Other general examples would be structures that mimic the layout of on-disk and on-network structures that people use for memcpy based serialization. I don't know of a good way to make a heuristic for those structures, but the warnings can be suppressed without breaking ABI by adding explicit padding members.

These generally felt like noisy reports unless I had more specific justification for them (like evidence of
an array of the elements). Should it be higher? As I get better at detecting arrays, then I think it makes
sense to bump the raw value higher.

I think it's better to report many fewer issues that are real problems to "advertise" the checker. Once people see it's value, they can lower the threshold. If we report hundreds of issues, it will scare people off.

I will bump the threshold from 8 to 24, then rerun against clang + llvm. I'm guessing that that will get the number of reports down below 50.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

323

I will do a partial fork of these tests on x64 to validate the numbers coming out. Running an older versions of these tests on multiple platforms alerted me to the craziness of base class layout and tail padding. Here's an example of the crazy...

struct Base {
  virtual ~Base() {}
  int i;
  char c;
};

struct Derived : public Base {
  char c1;
  short i1;
  char c2;
};

On some ABI's, the amount of padding in the Derived portion is 2 bytes (optimal 0), and other ABIs, the observed amount is 3 bytes (optimal 3). My padding calculation code at the time managed to hit my assert that "optimal" was worse than baseline.

[zaks.anna]

can be suppressed without breaking ABI by adding explicit padding members.

We should convey the suppression mechanism as part of the diagnostic.

[bcraig]

In D14779#293339, @zaks.anna wrote:

can be suppressed without breaking ABI by adding explicit padding members.

We should convey the suppression mechanism as part of the diagnostic.

I can make the diagnostic longer. Alternatively, is there a way to provide "Note" style diagnostics in the analyzer? If so, then that seems like the best place to put that information.

[bcraig]

Adding a test to validate non-trivial message components.
Adding recommendations to the diagnostic on how to fix and / or suppress the generated report.
Changing default padding allowance to reduce initial static analysis shock.
An analysis of llvm+clang+compiler-rt now only generates 16 excessive padding reports in index.html.

[zaks.anna]

An analysis of llvm+clang+compiler-rt now only generates 16 excessive padding reports in index.html.

Should those be fixed or are they all false positives?

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

49

Wording is off here.
Would it be possible to provide a checkAST method that does visit temple instantiations and lambdas? What if another checker wants the same functionality?

71

Could you add a comment explaining what is PadMultiplier and why it is needed?

197

Is this doing more than just accumulating the padding for every field in the record? For example, it seems we could do it with a simple loop the does:

PadSum += Current.Offset - (Prev.Offset + Prev.Size)

214

Please, add a high-level description of how optimal pad is calculated.

224

The second comment is unclear. Which vector are you talking about here?

I think it would be better to just move the comments to the places where the action is performed; ex std::sort(Fields.begin(), Fields.end()) in this case.

231

Please, pick a more descriptive name.

250

Is NewPad initialized?

[bcraig]

Somehow, I thought I was waiting on Anna, but I missed the Dec 1 update during the Thanksgiving break, and nothing was blocking me. An updated patch should be posted soon.

In D14779#299895, @zaks.anna wrote:

An analysis of llvm+clang+compiler-rt now only generates 16 excessive padding reports in index.html.

Should those be fixed or are they all false positives?

All of them are real problems.

• 6 of them would be straightforward to fix
• 9 of them are the exact same (difficult to fix) issue that gets duplicated because the filenames appear different
  • projects/compiler-rt/lib/tsan/../sanitizer_common/sanitizer_flags.h vs. projects/compiler-rt/lib/asan/../sanitizer_common/sanitizer_flags.h
  • It's a difficult fix because it is a structure where the elements are defined via a preprocessor x-macro.
• 1 is in gtest-internal-inl.h, and would be straightforward to fix, but I don't know if we would because it might be considered external code.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

49

Fixed the wording.
I don't know of a good way to make the Analysis consumer just pass template instantiations and implicit code to only the checkers that want them.

The root of a template instantiation or implicit code tree could be pretty straightforward, but once the children of those nodes start to be examined, it becomes a lot more difficult to determine if a particular call to malloc (for example) should be dispatched to a particular checker.

I'm not opposed to the idea, but I would expect that kind of change to go in a different patch.

197

Switched to raw loop.

There has been some advice floating around the C++ community for a little while suggesting that developers should avoid raw loops and use STL and STL like algorithms instead. ( https://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning ).

To be honest though, the raw loop is a lot easier to read (IMO) than the two lambas + functional programming algorithm. The raw loop is certainly shorter.

250

CharUnits has a default constructor that initializes the value to 0.

[bcraig]

Anna Zaks last round of review requests.

[zaks.anna]

With respect to the issues this checker found, I suggest submitting patches for the clang issues that can be fixed. Can the x-macro case be suppressed with the recommended suppression? I'd also submit a patch to gtest. Submitting patches with the fixes provides a good evaluation of new checkers:)

lib/StaticAnalyzer/Checkers/Checkers.td

49

I think Performance should be in the OptIn package.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

195

It's not 100% clear what the "lowest aligned field" is.

197

Punctuation is missing in 4, 5, 6.

201

Extra space before "Track"?

[bcraig]

In D14779#309170, @zaks.anna wrote:

With respect to the issues this checker found, I suggest submitting patches for the clang issues that can be fixed. Can the x-macro case be suppressed with the recommended suppression? I'd also submit a patch to gtest. Submitting patches with the fixes provides a good evaluation of new checkers:)

I will get some NFC changes for the easy fixes in the LLVM and Clang repositories. The x-macro case is in compiler-rt.

The short answer to the x-macro suppression question is "no". The longer answer is "yes, but...". Here are the first few relevant parts of the compiler-rt x-macro...

COMMON_FLAG(
    bool, symbolize, true,
    "If set, use the online symbolizer from common sanitizer runtime to turn "
    "virtual addresses to file/line locations.")
COMMON_FLAG(
    const char *, external_symbolizer_path, 0,
    "Path to external symbolizer. If empty, the tool will search $PATH for "
    "the symbolizer.")

Nothing would break if I reorganized all the "COMMON_FLAG" calls such that the const char * versions came before all the bool versions. It would cause these two options to become more distant in both the code, and in the help. That seems bad.

Alternatively, we could change the other side of the xmacro to generate an anonymous union of TYPE and void *, and that would suppress the warning and work correctly. However, that would increase the amount of dead-space in the object. That seems counter to the goal of the checker.

If there were inline notations for suppressing warnings, then that would be the best way to handle this case.

Note that this kind of issue comes up to a lesser degree in very large hand written classes as well (i.e. not x-macro based). clang::Sema in clang/include/clang/Sema/Sema.h is almost 9000 lines long, and a lot of the members are grouped by usage instead of by alignment. Re-ordering those fields would likely be detrimental to the readability of that class.

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

195

Adjusting the comment. "Round up to at least the smallest field alignment that we currently have"

[zaks.anna]

lib/StaticAnalyzer/Checkers/Checkers.td

49

What do you think about this one?

[bcraig]

Submitted to r255545

lib/StaticAnalyzer/Checkers/CMakeLists.txt

   ObjCMissingSuperCallChecker.cpp
   ObjCSelfInitChecker.cpp
   ObjCUnusedIVarsChecker.cpp
+  PaddingChecker.cpp
   PointerArithChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp

lib/StaticAnalyzer/Checkers/Checkers.td

 def DeadCode : Package<"deadcode">;
 def DeadCodeAlpha : Package<"deadcode">, InPackage<Alpha>, Hidden;
 
+def Performance : Package<"performance">, InPackage<OptIn>;
+
 def Security : Package <"security">;
 def InsecureAPI : Package<"insecureAPI">, InPackage<Security>;
 def SecurityAlpha : Package<"security">, InPackage<Alpha>, Hidden;

 } // end "alpha.deadcode"
 
 //===----------------------------------------------------------------------===//
+// Performance checkers.
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = Performance in {
+
+def PaddingChecker : Checker<"Padding">,
+  HelpText<"Check for excessively padded structs.">,
+  DescFile<"PaddingChecker.cpp">;
+
+} // end: "padding"
+
+//===----------------------------------------------------------------------===//
 // Security checkers.
 //===----------------------------------------------------------------------===//
 

lib/StaticAnalyzer/Checkers/PaddingChecker.cpp

+//=======- PaddingChecker.cpp ------------------------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a checker that checks for padding that could be
+//  removed by re-ordering members.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/CharUnits.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/RecordLayout.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include <numeric>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+class PaddingChecker : public Checker<check::ASTDecl<TranslationUnitDecl>> {
+private:
+  mutable std::unique_ptr<BugType> PaddingBug;
+  mutable int64_t AllowedPad;
+  mutable BugReporter *BR;
+
+public:
+  void checkASTDecl(const TranslationUnitDecl *TUD, AnalysisManager &MGR,
+                    BugReporter &BRArg) const {
+    BR = &BRArg;
+    AllowedPad =
+        MGR.getAnalyzerOptions().getOptionAsInteger("AllowedPad", 24, this);
+    assert(AllowedPad >= 0 && "AllowedPad option should be non-negative");
+
+    // The calls to checkAST* from AnalysisConsumer don't
+    // visit template instantiations or lambda classes. We
+    // want to visit those, so we make our own RecursiveASTVisitor.
+    struct LocalVisitor : public RecursiveASTVisitor<LocalVisitor> {
+      const PaddingChecker *Checker;
+      bool shouldVisitTemplateInstantiations() const { return true; }
+      bool shouldVisitImplicitCode() const { return true; }
+      explicit LocalVisitor(const PaddingChecker *Checker) : Checker(Checker) {}
+      bool VisitRecordDecl(const RecordDecl *RD) {
+        Checker->visitRecord(RD);
+        return true;
+      }
+      bool VisitVarDecl(const VarDecl *VD) {
+        Checker->visitVariable(VD);
+        return true;
+      }
+      // TODO: Visit array new and mallocs for arrays.
+    };
+
+    LocalVisitor visitor(this);
+    visitor.TraverseDecl(const_cast<TranslationUnitDecl *>(TUD));
+  }
+
+  /// \brief Look for records of overly padded types. If padding *
+  /// PadMultiplier exceeds AllowedPad, then generate a report.
+  /// PadMultiplier is used to share code with the array padding
+  /// checker.
+  void visitRecord(const RecordDecl *RD, uint64_t PadMultiplier = 1) const {
+    if (shouldSkipDecl(RD))
+      return;
+
+    auto &ASTContext = RD->getASTContext();
+    const ASTRecordLayout &RL = ASTContext.getASTRecordLayout(RD);
+    assert(llvm::isPowerOf2_64(RL.getAlignment().getQuantity()));
+
+    CharUnits BaselinePad = calculateBaselinePad(RD, ASTContext, RL);
+    if (BaselinePad.isZero())
+      return;
+    CharUnits OptimalPad = calculateOptimalPad(RD, ASTContext, RL);
+
+    CharUnits DiffPad = PadMultiplier * (BaselinePad - OptimalPad);
+    if (DiffPad.getQuantity() <= AllowedPad) {
+      assert(!DiffPad.isNegative() && "DiffPad should not be negative");
+      // There is not enough excess padding to trigger a warning.
+      return;
+    }
+    reportRecord(RD, BaselinePad, OptimalPad);
+  }
+
+  /// \brief Look for arrays of overly padded types. If the padding of the
+  /// array type exceeds AllowedPad, then generate a report.
+  void visitVariable(const VarDecl *VD) const {
+    const ArrayType *ArrTy = VD->getType()->getAsArrayTypeUnsafe();
+    if (ArrTy == nullptr)
+      return;
+    uint64_t Elts = 0;
+    if (const ConstantArrayType *CArrTy = dyn_cast<ConstantArrayType>(ArrTy))
+      Elts = CArrTy->getSize().getZExtValue();
+    if (Elts == 0)
+      return;
+    const RecordType *RT = ArrTy->getElementType()->getAs<RecordType>();
+    if (RT == nullptr)
+      return;
+
+    // TODO: Recurse into the fields and base classes to see if any
+    // of those have excess padding.
+    visitRecord(RT->getDecl(), Elts);
+  }
+
+  bool shouldSkipDecl(const RecordDecl *RD) const {
+    auto Location = RD->getLocation();
+    // If the construct doesn't have a source file, then it's not something
+    // we want to diagnose.
+    if (!Location.isValid())
+      return true;
+    SrcMgr::CharacteristicKind Kind =
+        BR->getSourceManager().getFileCharacteristic(Location);
+    // Throw out all records that come from system headers.
+    if (Kind != SrcMgr::C_User)
+      return true;
+
+    // Not going to attempt to optimize unions.
+    if (RD->isUnion())
+      return true;
+    // How do you reorder fields if you haven't got any?
+    if (RD->field_empty())
+      return true;
+    if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD)) {
+      // Tail padding with base classes ends up being very complicated.
+      // We will skip objects with base classes for now.
+      if (CXXRD->getNumBases() != 0)
+        return true;
+      // Virtual bases are complicated, skipping those for now.
+      if (CXXRD->getNumVBases() != 0)
+        return true;
+      // Can't layout a template, so skip it. We do still layout the
+      // instantiations though.
+      if (CXXRD->getTypeForDecl()->isDependentType())
+        return true;
+      if (CXXRD->getTypeForDecl()->isInstantiationDependentType())
+        return true;
+    }
+    auto IsTrickyField = [](const FieldDecl *FD) -> bool {
+      // Bitfield layout is hard.
+      if (FD->isBitField())
+        return true;
+
+      // Variable length arrays are tricky too.
+      QualType Ty = FD->getType();
+      if (Ty->isIncompleteArrayType())
+        return true;
+      return false;
+    };
+
+    if (std::any_of(RD->field_begin(), RD->field_end(), IsTrickyField))
+      return true;
+    return false;
+  }
+
+  static CharUnits calculateBaselinePad(const RecordDecl *RD,
+                                        const ASTContext &ASTContext,
+                                        const ASTRecordLayout &RL) {
+    CharUnits PaddingSum;
+    CharUnits Offset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0));
+    for (const auto &FD : RD->fields()) {
+      // This checker only cares about the padded size of the
+      // field, and not the data size. If the field is a record
+      // with tail padding, then we won't put that number in our
+      // total because reordering fields won't fix that problem.
+      CharUnits FieldSize = ASTContext.getTypeSizeInChars(FD->getType());
+      auto FieldOffsetBits = RL.getFieldOffset(FD->getFieldIndex());
+      CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(FieldOffsetBits);
+      PaddingSum += (FieldOffset - Offset);
+      Offset = FieldOffset + FieldSize;
+    }
+    PaddingSum += RL.getSize() - Offset;
+    return PaddingSum;
+  }
+
+  /// Optimal padding overview:
+  /// 1.  Find a close approximation to where we can place our first field.
+  ///     This will usually be at offset 0.
+  /// 2.  Try to find the best field that can legally be placed at the current
+  ///     offset.
+  ///   a.  "Best" is the largest alignment that is legal, but smallest size.
+  ///       This is to account for overly aligned types.
+  /// 3.  If no fields can fit, pad by rounding the current offset up to the
+  ///     smallest alignment requirement of our fields. Measure and track the
+  //      amount of padding added. Go back to 2.
+  /// 4.  Increment the current offset by the size of the chosen field.
+  /// 5.  Remove the chosen field from the set of future possibilities.
+  /// 6.  Go back to 2 if there are still unplaced fields.
+  /// 7.  Add tail padding by rounding the current offset up to the structure
+  ///     alignment. Track the amount of padding added.
+
+  static CharUnits calculateOptimalPad(const RecordDecl *RD,
+                                       const ASTContext &ASTContext,
+                                       const ASTRecordLayout &RL) {
+    struct CharUnitPair {
+      CharUnits Align;
+      CharUnits Size;
+      bool operator<(const CharUnitPair &RHS) const {
+        // Order from small alignments to large alignments,
+        // then large sizes to small sizes.
+        return std::make_pair(Align, -Size) <
+               std::make_pair(RHS.Align, -RHS.Size);
+      }
+    };
+    SmallVector<CharUnitPair, 20> Fields;
+    auto GatherSizesAndAlignments = [](const FieldDecl *FD) {
+      CharUnitPair RetVal;
+      auto &Ctx = FD->getASTContext();
+      std::tie(RetVal.Size, RetVal.Align) =
+          Ctx.getTypeInfoInChars(FD->getType());
+      assert(llvm::isPowerOf2_64(RetVal.Align.getQuantity()));
+      if (auto Max = FD->getMaxAlignment())
+        RetVal.Align = std::max(Ctx.toCharUnitsFromBits(Max), RetVal.Align);
+      return RetVal;
+    };
+    std::transform(RD->field_begin(), RD->field_end(),
+                   std::back_inserter(Fields), GatherSizesAndAlignments);
+    std::sort(Fields.begin(), Fields.end());
+
+    // This lets us skip over vptrs and non-virtual bases,
+    // so that we can just worry about the fields in our object.
+    // Note that this does cause us to miss some cases where we
+    // could pack more bytes in to a base class's tail padding.
+    CharUnits NewOffset = ASTContext.toCharUnitsFromBits(RL.getFieldOffset(0));
+    CharUnits NewPad;
+
+    while (!Fields.empty()) {
+      unsigned TrailingZeros =
+          llvm::countTrailingZeros((unsigned long long)NewOffset.getQuantity());
+      // If NewOffset is zero, then countTrailingZeros will be 64. Shifting
+      // 64 will overflow our unsigned long long. Shifting 63 will turn
+      // our long long (and CharUnits internal type) negative. So shift 62.
+      long long CurAlignmentBits = 1ull << (std::min)(TrailingZeros, 62u);
+      CharUnits CurAlignment = CharUnits::fromQuantity(CurAlignmentBits);
+      CharUnitPair InsertPoint = {CurAlignment, CharUnits::Zero()};
+      auto CurBegin = Fields.begin();
+      auto CurEnd = Fields.end();
+
+      // In the typical case, this will find the last element
+      // of the vector. We won't find a middle element unless
+      // we started on a poorly aligned address or have an overly
+      // aligned field.
+      auto Iter = std::upper_bound(CurBegin, CurEnd, InsertPoint);
+      if (Iter != CurBegin) {
+        // We found a field that we can layout with the current alignment.
+        --Iter;
+        NewOffset += Iter->Size;
+        Fields.erase(Iter);
+      } else {
+        // We are poorly aligned, and we need to pad in order to layout another
+        // field. Round up to at least the smallest field alignment that we
+        // currently have.
+        CharUnits NextOffset = NewOffset.RoundUpToAlignment(Fields[0].Align);
+        NewPad += NextOffset - NewOffset;
+        NewOffset = NextOffset;
+      }
+    }
+    // Calculate tail padding.
+    CharUnits NewSize = NewOffset.RoundUpToAlignment(RL.getAlignment());
+    NewPad += NewSize - NewOffset;
+    return NewPad;
+  }
+
+  void reportRecord(const RecordDecl *RD, CharUnits BaselinePad,
+                    CharUnits TargetPad) const {
+    if (!PaddingBug)
+      PaddingBug =
+          llvm::make_unique<BugType>(this, "Excessive Padding", "Performance");
+
+    SmallString<100> Buf;
+    llvm::raw_svector_ostream Os(Buf);
+
+    Os << "Excessive padding in '";
+    Os << QualType::getAsString(RD->getTypeForDecl(), Qualifiers()) << "'";
+
+    if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) {
+      // TODO: make this show up better in the console output and in
+      // the HTML. Maybe just make it show up in HTML like the path
+      // diagnostics show.
+      SourceLocation ILoc = TSD->getPointOfInstantiation();
+      if (ILoc.isValid())
+        Os << " instantiated here: "
+           << ILoc.printToString(BR->getSourceManager());
+    }
+
+    Os << " (" << BaselinePad.getQuantity() << " padding bytes, where "
+       << TargetPad.getQuantity() << " is optimal). Consider reordering "
+       << "the fields or adding explicit padding members.";
+
+    PathDiagnosticLocation CELoc =
+        PathDiagnosticLocation::create(RD, BR->getSourceManager());
+
+    auto Report = llvm::make_unique<BugReport>(*PaddingBug, Os.str(), CELoc);
+    Report->setDeclWithIssue(RD);
+    Report->addRange(RD->getSourceRange());
+
+    BR->emitReport(std::move(Report));
+  }
+};
+}
+
+void ento::registerPaddingChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<PaddingChecker>();
+}

test/Analysis/padding_c.c

+// RUN: %clang_cc1 -analyze -analyzer-checker=optin.performance -analyzer-config optin.performance.Padding:AllowedPad=2 -verify %s
+
+#if __has_include(<stdalign.h>)
+#include <stdalign.h>
+#endif
+
+#if __has_include(<stdalign.h>) || defined(__cplusplus)
+// expected-warning@+1{{Excessive padding in 'struct FieldAttrAlign' (6 padding}}
+struct FieldAttrAlign {
+  char c1;
+  alignas(4) int i;
+  char c2;
+};
+
+// expected-warning@+1{{Excessive padding in 'struct FieldAttrOverAlign' (10 padding}}
+struct FieldAttrOverAlign {
+  char c1;
+  alignas(8) int i;
+  char c2;
+};
+
+#endif // __has_include(<stdalign.h>) || defined(__cplusplus)
+
+// Re-ordering members of these structs won't reduce padding, so don't warn
+struct LeadingChar { // no-warning
+  char c;
+  int i;
+};
+
+struct TrailingChar { // no-warning
+  int i;
+  char c;
+};
+
+struct Helpless { // no-warning
+  struct TrailingChar i1;
+  struct LeadingChar i2;
+  char c;
+};
+
+#pragma pack(push)
+#pragma pack(1)
+struct SquishedIntSandwich { // no-warning
+  char c1;
+  int i;
+  char c2;
+};
+#pragma pack(pop)
+
+// Re-ordering members of these structs will reduce padding, so warn
+struct IntSandwich { // expected-warning{{Excessive padding in 'struct IntSandwich'}}
+  char c1;
+  int i;
+  char c2;
+};
+
+struct TurDuckHen { // expected-warning{{Excessive padding in 'struct TurDuckHen'}}
+  char c1;
+  struct IntSandwich i;
+  char c2;
+};
+
+#pragma pack(push)
+#pragma pack(2)
+struct SmallIntSandwich { // expected-warning{{Excessive padding in 'struct SmallIntSandwich'}}
+  char c1;
+  int i1;
+  char c2;
+  int i2;
+  char c3;
+  int i3;
+  char c4;
+};
+#pragma pack(pop)
+
+union SomeUnion { // no-warning
+  char c;
+  short s;
+  int i;
+};
+
+struct HoldsAUnion { // expected-warning{{Excessive padding in 'struct HoldsAUnion'}}
+  char c1;
+  union SomeUnion u;
+  char c2;
+};
+
+struct BigCharArray { // no-warning
+  char c[129];
+};
+
+struct SmallCharArray { // no-warning
+  char c[5];
+};
+
+struct MediumIntArray { // no-warning
+  int i[5];
+};
+
+struct LargeSizeToSmallSize { // expected-warning{{Excessive padding in 'struct LargeSizeToSmallSize'}}
+  struct BigCharArray b;
+  struct MediumIntArray m;
+  struct SmallCharArray s;
+};
+
+struct LargeAlignToSmallAlign { // no-warning
+  struct MediumIntArray m;
+  struct BigCharArray b;
+  struct SmallCharArray s;
+};
+
+// Currently ignoring VLA padding problems.  Still need to make sure we don't
+// choke on VLAs though
+struct HoldsVLA { // no-warning
+  char c1;
+  int x;
+  char c2;
+  int vla[];
+};
+
+// Currently ignoring bitfield padding problems.  Still need to make sure we
+// don't choke on bitfields though
+struct HoldsBitfield { // no-warning
+  char c1;
+  int x;
+  char c2;
+  unsigned char b1 : 3;
+  unsigned char b2 : 3;
+  unsigned char b3 : 2;
+};
+
+typedef struct { // expected-warning{{Excessive padding in 'TypedefSandwich'}}
+  char c1;
+  int i;
+  char c2;
+} TypedefSandwich;
+
+// expected-warning@+1{{Excessive padding in 'struct StructAttrAlign' (10 padding}}
+struct StructAttrAlign {
+  char c1;
+  int i;
+  char c2;
+} __attribute__((aligned(8)));
+
+struct CorrectOverlyAlignedChar { // no-warning
+  char c __attribute__((aligned(4096)));
+  char c1;
+  int x1;
+  char c2;
+  int x2;
+  char c3;
+};
+
+struct OverlyAlignedChar { // expected-warning{{Excessive padding in 'struct OverlyAlignedChar'}}
+  char c1;
+  int x;
+  char c2;
+  char c __attribute__((aligned(4096)));
+};
+
+struct HoldsOverlyAlignedChar { // expected-warning{{Excessive padding in 'struct HoldsOverlyAlignedChar'}}
+  char c1;
+  struct OverlyAlignedChar o;
+  char c2;
+};
+
+void internalStructFunc() {
+  struct X { // expected-warning{{Excessive padding in 'struct X'}}
+    char c1;
+    int t;
+    char c2;
+  };
+  struct X obj;
+}
+
+void typedefStructFunc() {
+  typedef struct { // expected-warning{{Excessive padding in 'S'}}
+    char c1;
+    int t;
+    char c2;
+  } S;
+  S obj;
+}
+
+void anonStructFunc() {
+  struct { // expected-warning{{Excessive padding in 'struct (anonymous}}
+    char c1;
+    int t;
+    char c2;
+  } obj;
+}
+
+// expected-warning@+1{{Excessive padding in 'struct DefaultAttrAlign'}}
+struct DefaultAttrAlign {
+  char c1;
+  long long i;
+  char c2;
+} __attribute__((aligned));
+
+struct CorrectDefaultAttrAlign { // no-warning
+  long long i;
+  char c1;
+  char c2;
+} __attribute__((aligned));
+
+struct TooSmallShortSandwich { // no-warning
+  char c1;
+  short s;
+  char c2;
+};
+
+// expected-warning@+1{{Excessive padding in 'struct SmallArrayShortSandwich'}}
+struct SmallArrayShortSandwich {
+  char c1;
+  short s;
+  char c2;
+} ShortArray[20];
+
+// expected-warning@+1{{Excessive padding in 'struct SmallArrayInFunc'}}
+struct SmallArrayInFunc {
+  char c1;
+  short s;
+  char c2;
+};
+
+void arrayHolder() {
+  struct SmallArrayInFunc Arr[15];
+}
+
+// xxxexpected-warning@+1{{Excessive padding in 'struct SmallArrayInStruct'}}
+struct SmallArrayInStruct {
+  char c1;
+  short s;
+  char c2;
+};
+
+struct HoldsSmallArray {
+  struct SmallArrayInStruct Field[20];
+} HoldsSmallArrayElt;
+
+void nestedPadding() {
+  struct HoldsSmallArray Arr[15];
+}

test/Analysis/padding_cpp.cpp

+// RUN: %clang_cc1 -std=c++14 -analyze -analyzer-checker=optin.performance -analyzer-config optin.performance.Padding:AllowedPad=2 -verify %s
+
+// Make sure that the C cases still work fine, even when compiled as C++.
+#include "padding_c.c"
+
+struct BigCharArray2 { // no-warning
+  char c[129];
+};
+
+// xxxexpected-warning@+1{{Excessive padding in 'struct LowAlignmentBase'}}
+struct LowAlignmentBase : public BigCharArray2 {
+  int i;
+  char c;
+};
+
+struct CorrectLowAlignmentBase : public BigCharArray2 { // no-warning
+  char c;
+  int i;
+};
+
+// xxxexpected-warning@+1{{Excessive padding in 'struct LowAlignmentBase2'}}
+struct LowAlignmentBase2 : public BigCharArray2 {
+  char c1;
+  int i;
+  char c2;
+};
+
+class PaddedA { // expected-warning{{Excessive padding in 'class PaddedA'}}
+  char c1;
+  int i;
+  char c2;
+};
+
+class VirtualPaddedA : public PaddedA { // no-warning
+  virtual void foo() {}
+};
+
+class VirtualIntSandwich { // expected-warning{{Excessive padding in 'class VirtualIntSandwich'}}
+  virtual void foo() {}
+  char c1;
+  int i;
+  char c2;
+};
+
+// constructed so as not to have tail padding
+class InnerPaddedB { // expected-warning{{Excessive padding in 'class InnerPaddedB'}}
+  char c1;
+  int i1;
+  char c2;
+  int i2;
+};
+
+class TailPaddedB { // expected-warning{{Excessive padding in 'class TailPaddedB'}}
+  char c1;
+  int i1;
+  char c2;
+};
+
+class SI : public PaddedA { // no-warning
+  char c;
+};
+
+class SI2 : public PaddedA { // xxxexpected-warning{{Excessive padding in 'class SI2'}}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class VirtualSI : virtual public PaddedA { // no-warning
+  char c;
+};
+
+// currently not checked for
+class VirtualSI2 : virtual public PaddedA { // no-warning
+  char c10;
+  int i10;
+  char c11;
+};
+
+class VtblSI : public PaddedA { // no-warning
+  virtual void foo() {}
+  char c;
+};
+
+class VtblSI2 : public PaddedA { // xxxexpected-warning{{Excessive padding in 'class VtblSI2'}}
+  virtual void foo() {}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class VtblSI3 : public VirtualPaddedA { // xxxexpected-warning{{Excessive padding in 'class VtblSI3'}}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class MI : public PaddedA, public InnerPaddedB { // no-warning
+  char c;
+};
+
+class MI2 : public PaddedA, public InnerPaddedB { // xxxexpected-warning{{Excessive padding in 'class MI2'}}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class VtblMI : public PaddedA, public InnerPaddedB { // xxxexpected-warning{{Excessive padding in 'class VtblMI'}}
+  virtual void foo() {}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class VtblMI2 : public VirtualPaddedA, public InnerPaddedB { // xxxexpected-warning{{Excessive padding in 'class VtblMI2'}}
+  char c10;
+  int i10;
+  char c11;
+};
+
+class Empty {}; // no-warning
+
+class LotsOfSpace { // expected-warning{{Excessive padding in 'class LotsOfSpace'}}
+  Empty e1;
+  int i;
+  Empty e2;
+};
+
+class EBO1 : public Empty { // xxxexpected-warning{{Excessive padding in 'class EBO1'}}
+  char c1;
+  int i;
+  char c2;
+};
+
+class EBO2 : public Empty { // xxxexpected-warning{{Excessive padding in 'class EBO2'}}
+  Empty c1;
+  int i;
+  Empty c2;
+};
+
+template <typename T>
+class TemplateSandwich { // expected-warning{{Excessive padding in 'class TemplateSandwich<int>' instantiated here}}
+  char c1;
+  T t;
+  char c2;
+};
+
+template <typename T>
+class TemplateSandwich<T *> { // expected-warning{{Excessive padding in 'class TemplateSandwich<void *>' instantiated here}}
+  char c1;
+  T *t;
+  char c2;
+};
+
+template <>
+class TemplateSandwich<long long> { // expected-warning{{Excessive padding in 'class TemplateSandwich<long long>' (}}
+  char c1;
+  long long t;
+  char c2;
+};
+
+class Holder1 { // no-warning
+  TemplateSandwich<int> t1;
+  TemplateSandwich<char> t2;
+  TemplateSandwich<void *> t3;
+};
+
+typedef struct { // expected-warning{{Excessive padding in 'TypedefSandwich2'}}
+  char c1;
+  typedef struct { // expected-warning{{Excessive padding in 'TypedefSandwich2::NestedTypedef'}}
+    char c1;
+    int i;
+    char c2;
+  } NestedTypedef;
+  NestedTypedef t;
+  char c2;
+} TypedefSandwich2;
+
+template <typename T>
+struct Foo {
+  // expected-warning@+1{{Excessive padding in 'struct Foo<int>::Nested'}}
+  struct Nested {
+    char c1;
+    T t;
+    char c2;
+  };
+};
+
+struct Holder { // no-warning
+  Foo<int>::Nested t1;
+  Foo<char>::Nested t2;
+};
+
+struct GlobalsForLambda { // no-warning
+  int i;
+  char c1;
+  char c2;
+} G;
+
+// expected-warning@+1{{Excessive padding in 'class (lambda}}
+auto lambda1 = [ c1 = G.c1, i = G.i, c2 = G.c2 ]{};
+auto lambda2 = [ i = G.i, c1 = G.c1, c2 = G.c2 ]{}; // no-warning

test/Analysis/padding_message.cpp

+// RUN: %clang_cc1 -triple x86_64-unknown-linux -std=c++14 -analyze -analyzer-checker=optin.performance -analyzer-config optin.performance.Padding:AllowedPad=2 -verify %s
+
+// expected-warning@+1{{Excessive padding in 'struct IntSandwich' (6 padding bytes, where 2 is optimal)}}
+struct IntSandwich {
+  char c1;
+  int i;
+  char c2;
+};
+
+// expected-warning@+1{{Excessive padding in 'struct TurDuckHen' (6 padding bytes, where 2 is optimal)}}
+struct TurDuckHen {
+  char c1;
+  struct IntSandwich i;
+  char c2;
+};
+
+#pragma pack(push)
+#pragma pack(2)
+// expected-warning@+1{{Excessive padding in 'struct SmallIntSandwich' (4 padding bytes, where 0 is optimal)}}
+struct SmallIntSandwich {
+  char c1;
+  int i1;
+  char c2;
+  int i2;
+  char c3;
+  int i3;
+  char c4;
+};
+#pragma pack(pop)
+
+union SomeUnion { // no-warning
+  char c;
+  short s;
+  int i;
+};
+
+// expected-warning@+1{{Excessive padding in 'struct HoldsAUnion' (6 padding bytes, where 2 is optimal)}}
+struct HoldsAUnion {
+  char c1;
+  union SomeUnion u;
+  char c2;
+};
+
+struct SmallCharArray { // no-warning
+  char c[5];
+};
+
+struct MediumIntArray { // no-warning
+  int i[5];
+};
+
+// expected-warning@+1{{Excessive padding in 'struct StructSandwich' (6 padding bytes, where 2 is optimal)}}
+struct StructSandwich {
+  struct SmallCharArray s;
+  struct MediumIntArray m;
+  struct SmallCharArray s2;
+};
+
+// expected-warning@+1{{Excessive padding in 'TypedefSandwich' (6 padding bytes, where 2 is optimal)}}
+typedef struct {
+  char c1;
+  int i;
+  char c2;
+} TypedefSandwich;
+
+// expected-warning@+1{{Excessive padding in 'struct StructAttrAlign' (10 padding bytes, where 2 is optimal)}}
+struct StructAttrAlign {
+  char c1;
+  int i;
+  char c2;
+} __attribute__((aligned(8)));
+
+// expected-warning@+1{{Excessive padding in 'struct OverlyAlignedChar' (8185 padding bytes, where 4089 is optimal)}}
+struct OverlyAlignedChar {
+  char c1;
+  int x;
+  char c2;
+  char c __attribute__((aligned(4096)));
+};
+
+// expected-warning@+1{{Excessive padding in 'struct HoldsOverlyAlignedChar' (8190 padding bytes, where 4094 is optimal)}}
+struct HoldsOverlyAlignedChar {
+  char c1;
+  struct OverlyAlignedChar o;
+  char c2;
+};
+
+void internalStructFunc() {
+  // expected-warning@+1{{Excessive padding in 'struct X' (6 padding bytes, where 2 is optimal)}}
+  struct X {
+    char c1;
+    int t;
+    char c2;
+  };
+  struct X obj;
+}
+
+void typedefStructFunc() {
+  // expected-warning@+1{{Excessive padding in 'S' (6 padding bytes, where 2 is optimal)}}
+  typedef struct {
+    char c1;
+    int t;
+    char c2;
+  } S;
+  S obj;
+}
+
+// expected-warning@+1{{Excessive padding in 'struct DefaultAttrAlign' (22 padding bytes, where 6 is optimal)}}
+struct DefaultAttrAlign {
+  char c1;
+  long long i;
+  char c2;
+} __attribute__((aligned));
+
+// expected-warning@+1{{Excessive padding in 'struct SmallArrayShortSandwich' (2 padding bytes, where 0 is optimal)}}
+struct SmallArrayShortSandwich {
+  char c1;
+  short s;
+  char c2;
+} ShortArray[20];
+
+// expected-warning@+1{{Excessive padding in 'struct SmallArrayInFunc' (2 padding bytes, where 0 is optimal)}}
+struct SmallArrayInFunc {
+  char c1;
+  short s;
+  char c2;
+};
+
+void arrayHolder() {
+  struct SmallArrayInFunc Arr[15];
+}
+
+// expected-warning@+1{{Excessive padding in 'class VirtualIntSandwich' (10 padding bytes, where 2 is optimal)}}
+class VirtualIntSandwich {
+  virtual void foo() {}
+  char c1;
+  int i;
+  char c2;
+};
+
+// constructed so as not to have tail padding
+// expected-warning@+1{{Excessive padding in 'class InnerPaddedB' (6 padding bytes, where 2 is optimal)}}
+class InnerPaddedB {
+  char c1;
+  int i1;
+  char c2;
+  int i2;
+};
+
+class Empty {}; // no-warning
+
+// expected-warning@+1{{Excessive padding in 'class LotsOfSpace' (6 padding bytes, where 2 is optimal)}}
+class LotsOfSpace {
+  Empty e1;
+  int i;
+  Empty e2;
+};
+
+// expected-warning@+1{{Excessive padding in 'TypedefSandwich2' (6 padding bytes, where 2 is optimal)}}
+typedef struct {
+  char c1;
+  // expected-warning@+1{{Excessive padding in 'TypedefSandwich2::NestedTypedef' (6 padding bytes, where 2 is optimal)}}
+  typedef struct {
+    char c1;
+    int i;
+    char c2;
+  } NestedTypedef;
+  NestedTypedef t;
+  char c2;
+} TypedefSandwich2;
+
+template <typename T>
+struct Foo {
+  // expected-warning@+1{{Excessive padding in 'struct Foo<int>::Nested' (6 padding bytes, where 2 is optimal)}}
+  struct Nested {
+    char c1;
+    T t;
+    char c2;
+  };
+};
+
+struct Holder { // no-warning
+  Foo<int>::Nested t1;
+  Foo<char>::Nested t2;
+};