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