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
29using namespace clang;
30using namespace ento;
31
32namespace {
33class PaddingChecker : public Checker<check::ASTDecl<TranslationUnitDecl>> {
34private:
35 const BugType PaddingBug{this, "Excessive Padding", "Performance"};
36 mutable BugReporter *BR;
37
38public:
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(D: 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>(Val: RD))
86 if (CXXRD->field_empty() && CXXRD->getNumBases() == 1)
87 return visitRecord(RD: CXXRD->bases().begin()->getType()->getAsRecordDecl(),
88 PadMultiplier);
89
90 auto &ASTContext = RD->getASTContext();
91 const ASTRecordLayout &RL = ASTContext.getASTRecordLayout(D: RD);
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(args&: OptimalPad, args&: 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>(Val: ArrTy))
120 Elts = CArrTy->getZExtSize();
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(RD: RT->getDecl(), PadMultiplier: 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;
141 SrcMgr::CharacteristicKind Kind =
142 BR->getSourceManager().getFileCharacteristic(Loc: 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>(Val: 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 (llvm::any_of(Range: RD->fields(), P: 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;
194 CharUnits Offset = ASTContext.toCharUnitsFromBits(BitSize: RL.getFieldOffset(FieldNo: 0));
195 for (const FieldDecl *FD : RD->fields()) {
196 // Skip field that is a subobject of zero size, marked with
197 // [[no_unique_address]] or an empty bitfield, because its address can be
198 // set the same as the other fields addresses.
199 if (FD->isZeroSize(Ctx: ASTContext))
200 continue;
201 // This checker only cares about the padded size of the
202 // field, and not the data size. If the field is a record
203 // with tail padding, then we won't put that number in our
204 // total because reordering fields won't fix that problem.
205 CharUnits FieldSize = ASTContext.getTypeSizeInChars(T: FD->getType());
206 auto FieldOffsetBits = RL.getFieldOffset(FieldNo: FD->getFieldIndex());
207 CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(BitSize: FieldOffsetBits);
208 PaddingSum += (FieldOffset - Offset);
209 Offset = FieldOffset + FieldSize;
210 }
211 PaddingSum += RL.getSize() - Offset;
212 return PaddingSum;
213 }
214
215 /// Optimal padding overview:
216 /// 1. Find a close approximation to where we can place our first field.
217 /// This will usually be at offset 0.
218 /// 2. Try to find the best field that can legally be placed at the current
219 /// offset.
220 /// a. "Best" is the largest alignment that is legal, but smallest size.
221 /// This is to account for overly aligned types.
222 /// 3. If no fields can fit, pad by rounding the current offset up to the
223 /// smallest alignment requirement of our fields. Measure and track the
224 // amount of padding added. Go back to 2.
225 /// 4. Increment the current offset by the size of the chosen field.
226 /// 5. Remove the chosen field from the set of future possibilities.
227 /// 6. Go back to 2 if there are still unplaced fields.
228 /// 7. Add tail padding by rounding the current offset up to the structure
229 /// alignment. Track the amount of padding added.
230
231 static std::pair<CharUnits, SmallVector<const FieldDecl *, 20>>
232 calculateOptimalPad(const RecordDecl *RD, const ASTContext &ASTContext,
233 const ASTRecordLayout &RL) {
234 struct FieldInfo {
235 CharUnits Align;
236 CharUnits Size;
237 const FieldDecl *Field;
238 bool operator<(const FieldInfo &RHS) const {
239 // Order from small alignments to large alignments,
240 // then large sizes to small sizes.
241 // then large field indices to small field indices
242 return std::make_tuple(args: Align, args: -Size,
243 args: Field ? -static_cast<int>(Field->getFieldIndex())
244 : 0) <
245 std::make_tuple(
246 args: RHS.Align, args: -RHS.Size,
247 args: RHS.Field ? -static_cast<int>(RHS.Field->getFieldIndex())
248 : 0);
249 }
250 };
251 SmallVector<FieldInfo, 20> Fields;
252 auto GatherSizesAndAlignments = [](const FieldDecl *FD) {
253 FieldInfo RetVal;
254 RetVal.Field = FD;
255 auto &Ctx = FD->getASTContext();
256 auto Info = Ctx.getTypeInfoInChars(T: FD->getType());
257 RetVal.Size = FD->isZeroSize(Ctx) ? CharUnits::Zero() : Info.Width;
258 RetVal.Align = Info.Align;
259 assert(llvm::isPowerOf2_64(RetVal.Align.getQuantity()));
260 if (auto Max = FD->getMaxAlignment())
261 RetVal.Align = std::max(a: Ctx.toCharUnitsFromBits(BitSize: Max), b: RetVal.Align);
262 return RetVal;
263 };
264 std::transform(first: RD->field_begin(), last: RD->field_end(),
265 result: std::back_inserter(x&: Fields), unary_op: GatherSizesAndAlignments);
266 llvm::sort(C&: Fields);
267 // This lets us skip over vptrs and non-virtual bases,
268 // so that we can just worry about the fields in our object.
269 // Note that this does cause us to miss some cases where we
270 // could pack more bytes in to a base class's tail padding.
271 CharUnits NewOffset = ASTContext.toCharUnitsFromBits(BitSize: RL.getFieldOffset(FieldNo: 0));
272 CharUnits NewPad;
273 SmallVector<const FieldDecl *, 20> OptimalFieldsOrder;
274 while (!Fields.empty()) {
275 unsigned TrailingZeros =
276 llvm::countr_zero(Val: (unsigned long long)NewOffset.getQuantity());
277 // If NewOffset is zero, then countTrailingZeros will be 64. Shifting
278 // 64 will overflow our unsigned long long. Shifting 63 will turn
279 // our long long (and CharUnits internal type) negative. So shift 62.
280 long long CurAlignmentBits = 1ull << (std::min)(a: TrailingZeros, b: 62u);
281 CharUnits CurAlignment = CharUnits::fromQuantity(Quantity: CurAlignmentBits);
282 FieldInfo InsertPoint = {.Align: CurAlignment, .Size: CharUnits::Zero(), .Field: nullptr};
283
284 // In the typical case, this will find the last element
285 // of the vector. We won't find a middle element unless
286 // we started on a poorly aligned address or have an overly
287 // aligned field.
288 auto Iter = llvm::upper_bound(Range&: Fields, Value&: InsertPoint);
289 if (Iter != Fields.begin()) {
290 // We found a field that we can layout with the current alignment.
291 --Iter;
292 NewOffset += Iter->Size;
293 OptimalFieldsOrder.push_back(Elt: Iter->Field);
294 Fields.erase(CI: Iter);
295 } else {
296 // We are poorly aligned, and we need to pad in order to layout another
297 // field. Round up to at least the smallest field alignment that we
298 // currently have.
299 CharUnits NextOffset = NewOffset.alignTo(Align: Fields[0].Align);
300 NewPad += NextOffset - NewOffset;
301 NewOffset = NextOffset;
302 }
303 }
304 // Calculate tail padding.
305 CharUnits NewSize = NewOffset.alignTo(Align: RL.getAlignment());
306 NewPad += NewSize - NewOffset;
307 return {NewPad, std::move(OptimalFieldsOrder)};
308 }
309
310 void reportRecord(
311 const RecordDecl *RD, CharUnits BaselinePad, CharUnits OptimalPad,
312 const SmallVector<const FieldDecl *, 20> &OptimalFieldsOrder) const {
313 SmallString<100> Buf;
314 llvm::raw_svector_ostream Os(Buf);
315 Os << "Excessive padding in '";
316 Os << QualType::getAsString(ty: RD->getTypeForDecl(), qs: Qualifiers(),
317 Policy: LangOptions())
318 << "'";
319
320 if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(Val: RD)) {
321 // TODO: make this show up better in the console output and in
322 // the HTML. Maybe just make it show up in HTML like the path
323 // diagnostics show.
324 SourceLocation ILoc = TSD->getPointOfInstantiation();
325 if (ILoc.isValid())
326 Os << " instantiated here: "
327 << ILoc.printToString(SM: BR->getSourceManager());
328 }
329
330 Os << " (" << BaselinePad.getQuantity() << " padding bytes, where "
331 << OptimalPad.getQuantity() << " is optimal). "
332 << "Optimal fields order: ";
333 for (const auto *FD : OptimalFieldsOrder)
334 Os << FD->getName() << ", ";
335 Os << "consider reordering the fields or adding explicit padding "
336 "members.";
337
338 PathDiagnosticLocation CELoc =
339 PathDiagnosticLocation::create(D: RD, SM: BR->getSourceManager());
340 auto Report = std::make_unique<BasicBugReport>(args: PaddingBug, args: Os.str(), args&: CELoc);
341 Report->setDeclWithIssue(RD);
342 Report->addRange(R: RD->getSourceRange());
343 BR->emitReport(R: std::move(Report));
344 }
345};
346} // namespace
347
348void ento::registerPaddingChecker(CheckerManager &Mgr) {
349 auto *Checker = Mgr.registerChecker<PaddingChecker>();
350 Checker->AllowedPad = Mgr.getAnalyzerOptions()
351 .getCheckerIntegerOption(C: Checker, OptionName: "AllowedPad");
352 if (Checker->AllowedPad < 0)
353 Mgr.reportInvalidCheckerOptionValue(
354 C: Checker, OptionName: "AllowedPad", ExpectedValueDesc: "a non-negative value");
355}
356
357bool ento::shouldRegisterPaddingChecker(const CheckerManager &mgr) {
358 return true;
359}
360