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