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 | const BugType PaddingBug{this, "Excessive Padding" , "Performance" }; |
36 | mutable BugReporter *BR; |
37 | |
38 | public: |
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(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(RD); |
92 | assert(llvm::isPowerOf2_64(RL.getAlignment().getQuantity())); |
93 | |
94 | CharUnits BaselinePad = calculateBaselinePad(RD, ASTContext: 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: 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(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(FD->getType()); |
257 | RetVal.Size = FD->isZeroSize(Ctx: 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(Ctx.toCharUnitsFromBits(Max), 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(RD->getTypeForDecl(), Qualifiers(), |
317 | 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(RD, BR->getSourceManager()); |
340 | auto Report = std::make_unique<BasicBugReport>(args: PaddingBug, args: Os.str(), args&: CELoc); |
341 | Report->setDeclWithIssue(RD); |
342 | Report->addRange(RD->getSourceRange()); |
343 | BR->emitReport(R: std::move(Report)); |
344 | } |
345 | }; |
346 | } // namespace |
347 | |
348 | void 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 | |
357 | bool ento::shouldRegisterPaddingChecker(const CheckerManager &mgr) { |
358 | return true; |
359 | } |
360 | |