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 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>(RD)) 86 if (CXXRD->field_empty() && CXXRD->getNumBases() == 1) 87 return visitRecord(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, RL); 95 if (BaselinePad.isZero()) 96 return; 97 98 CharUnits OptimalPad; 99 SmallVector<const FieldDecl *, 20> OptimalFieldsOrder; 100 std::tie(OptimalPad, 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>(ArrTy)) 120 Elts = CArrTy->getSize().getZExtValue(); 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(RT->getDecl(), 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(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>(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(RD->fields(), 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(RL.getFieldOffset(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(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(FD->getFieldIndex()); 207 CharUnits FieldOffset = ASTContext.toCharUnitsFromBits(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(Align, -Size, 243 Field ? -static_cast<int>(Field->getFieldIndex()) 244 : 0) < 245 std::make_tuple( 246 RHS.Align, -RHS.Size, 247 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) ? 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(RD->field_begin(), RD->field_end(), 265 std::back_inserter(Fields), GatherSizesAndAlignments); 266 llvm::sort(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(RL.getFieldOffset(0)); 272 CharUnits NewPad; 273 SmallVector<const FieldDecl *, 20> OptimalFieldsOrder; 274 while (!Fields.empty()) { 275 unsigned TrailingZeros = 276 llvm::countTrailingZeros((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)(TrailingZeros, 62u); 281 CharUnits CurAlignment = CharUnits::fromQuantity(CurAlignmentBits); 282 FieldInfo InsertPoint = {CurAlignment, CharUnits::Zero(), 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(Fields, 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(Iter->Field); 294 Fields.erase(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(Fields[0].Align); 300 NewPad += NextOffset - NewOffset; 301 NewOffset = NextOffset; 302 } 303 } 304 // Calculate tail padding. 305 CharUnits NewSize = NewOffset.alignTo(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 if (!PaddingBug) 314 PaddingBug = 315 std::make_unique<BugType>(this, "Excessive Padding", "Performance"); 316 317 SmallString<100> Buf; 318 llvm::raw_svector_ostream Os(Buf); 319 Os << "Excessive padding in '"; 320 Os << QualType::getAsString(RD->getTypeForDecl(), Qualifiers(), 321 LangOptions()) 322 << "'"; 323 324 if (auto *TSD = dyn_cast<ClassTemplateSpecializationDecl>(RD)) { 325 // TODO: make this show up better in the console output and in 326 // the HTML. Maybe just make it show up in HTML like the path 327 // diagnostics show. 328 SourceLocation ILoc = TSD->getPointOfInstantiation(); 329 if (ILoc.isValid()) 330 Os << " instantiated here: " 331 << ILoc.printToString(BR->getSourceManager()); 332 } 333 334 Os << " (" << BaselinePad.getQuantity() << " padding bytes, where " 335 << OptimalPad.getQuantity() << " is optimal). " 336 << "Optimal fields order: "; 337 for (const auto *FD : OptimalFieldsOrder) 338 Os << FD->getName() << ", "; 339 Os << "consider reordering the fields or adding explicit padding " 340 "members."; 341 342 PathDiagnosticLocation CELoc = 343 PathDiagnosticLocation::create(RD, BR->getSourceManager()); 344 auto Report = 345 std::make_unique<BasicBugReport>(*PaddingBug, Os.str(), CELoc); 346 Report->setDeclWithIssue(RD); 347 Report->addRange(RD->getSourceRange()); 348 BR->emitReport(std::move(Report)); 349 } 350 }; 351 } // namespace 352 353 void ento::registerPaddingChecker(CheckerManager &Mgr) { 354 auto *Checker = Mgr.registerChecker<PaddingChecker>(); 355 Checker->AllowedPad = Mgr.getAnalyzerOptions() 356 .getCheckerIntegerOption(Checker, "AllowedPad"); 357 if (Checker->AllowedPad < 0) 358 Mgr.reportInvalidCheckerOptionValue( 359 Checker, "AllowedPad", "a non-negative value"); 360 } 361 362 bool ento::shouldRegisterPaddingChecker(const CheckerManager &mgr) { 363 return true; 364 } 365