1 //=== OSAtomicChecker.cpp - OSAtomic functions evaluator --------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This checker evaluates OSAtomic functions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "ClangSACheckers.h" 15 #include "clang/StaticAnalyzer/Core/Checker.h" 16 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 17 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 18 #include "clang/Basic/Builtins.h" 19 20 using namespace clang; 21 using namespace ento; 22 23 namespace { 24 25 class OSAtomicChecker : public Checker<eval::InlineCall> { 26 public: 27 bool inlineCall(const CallExpr *CE, ExprEngine &Eng, 28 ExplodedNode *Pred, ExplodedNodeSet &Dst) const; 29 30 private: 31 bool evalOSAtomicCompareAndSwap(const CallExpr *CE, 32 ExprEngine &Eng, 33 ExplodedNode *Pred, 34 ExplodedNodeSet &Dst) const; 35 }; 36 } 37 38 static StringRef getCalleeName(ProgramStateRef State, 39 const CallExpr *CE, 40 const LocationContext *LCtx) { 41 const Expr *Callee = CE->getCallee(); 42 SVal L = State->getSVal(Callee, LCtx); 43 const FunctionDecl *funDecl = L.getAsFunctionDecl(); 44 if (!funDecl) 45 return StringRef(); 46 IdentifierInfo *funI = funDecl->getIdentifier(); 47 if (!funI) 48 return StringRef(); 49 return funI->getName(); 50 } 51 52 bool OSAtomicChecker::inlineCall(const CallExpr *CE, 53 ExprEngine &Eng, 54 ExplodedNode *Pred, 55 ExplodedNodeSet &Dst) const { 56 StringRef FName = getCalleeName(Pred->getState(), 57 CE, Pred->getLocationContext()); 58 if (FName.empty()) 59 return false; 60 61 // Check for compare and swap. 62 if (FName.startswith("OSAtomicCompareAndSwap") || 63 FName.startswith("objc_atomicCompareAndSwap")) 64 return evalOSAtomicCompareAndSwap(CE, Eng, Pred, Dst); 65 66 // FIXME: Other atomics. 67 return false; 68 } 69 70 bool OSAtomicChecker::evalOSAtomicCompareAndSwap(const CallExpr *CE, 71 ExprEngine &Eng, 72 ExplodedNode *Pred, 73 ExplodedNodeSet &Dst) const { 74 // Not enough arguments to match OSAtomicCompareAndSwap? 75 if (CE->getNumArgs() != 3) 76 return false; 77 78 ASTContext &Ctx = Eng.getContext(); 79 const Expr *oldValueExpr = CE->getArg(0); 80 QualType oldValueType = Ctx.getCanonicalType(oldValueExpr->getType()); 81 82 const Expr *newValueExpr = CE->getArg(1); 83 QualType newValueType = Ctx.getCanonicalType(newValueExpr->getType()); 84 85 // Do the types of 'oldValue' and 'newValue' match? 86 if (oldValueType != newValueType) 87 return false; 88 89 const Expr *theValueExpr = CE->getArg(2); 90 const PointerType *theValueType=theValueExpr->getType()->getAs<PointerType>(); 91 92 // theValueType not a pointer? 93 if (!theValueType) 94 return false; 95 96 QualType theValueTypePointee = 97 Ctx.getCanonicalType(theValueType->getPointeeType()).getUnqualifiedType(); 98 99 // The pointee must match newValueType and oldValueType. 100 if (theValueTypePointee != newValueType) 101 return false; 102 103 static SimpleProgramPointTag OSAtomicLoadTag("OSAtomicChecker : Load"); 104 static SimpleProgramPointTag OSAtomicStoreTag("OSAtomicChecker : Store"); 105 106 // Load 'theValue'. 107 ProgramStateRef state = Pred->getState(); 108 const LocationContext *LCtx = Pred->getLocationContext(); 109 ExplodedNodeSet Tmp; 110 SVal location = state->getSVal(theValueExpr, LCtx); 111 // Here we should use the value type of the region as the load type, because 112 // we are simulating the semantics of the function, not the semantics of 113 // passing argument. So the type of theValue expr is not we are loading. 114 // But usually the type of the varregion is not the type we want either, 115 // we still need to do a CastRetrievedVal in store manager. So actually this 116 // LoadTy specifying can be omitted. But we put it here to emphasize the 117 // semantics. 118 QualType LoadTy; 119 if (const TypedValueRegion *TR = 120 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 121 LoadTy = TR->getValueType(); 122 } 123 Eng.evalLoad(Tmp, CE, theValueExpr, Pred, 124 state, location, &OSAtomicLoadTag, LoadTy); 125 126 if (Tmp.empty()) { 127 // If no nodes were generated, other checkers must have generated sinks. 128 // We return an empty Dst. 129 return true; 130 } 131 132 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); 133 I != E; ++I) { 134 135 ExplodedNode *N = *I; 136 ProgramStateRef stateLoad = N->getState(); 137 138 // Use direct bindings from the environment since we are forcing a load 139 // from a location that the Environment would typically not be used 140 // to bind a value. 141 SVal theValueVal_untested = stateLoad->getSVal(theValueExpr, LCtx, true); 142 143 SVal oldValueVal_untested = stateLoad->getSVal(oldValueExpr, LCtx); 144 145 // FIXME: Issue an error. 146 if (theValueVal_untested.isUndef() || oldValueVal_untested.isUndef()) { 147 return false; 148 } 149 150 DefinedOrUnknownSVal theValueVal = 151 cast<DefinedOrUnknownSVal>(theValueVal_untested); 152 DefinedOrUnknownSVal oldValueVal = 153 cast<DefinedOrUnknownSVal>(oldValueVal_untested); 154 155 SValBuilder &svalBuilder = Eng.getSValBuilder(); 156 157 // Perform the comparison. 158 DefinedOrUnknownSVal Cmp = 159 svalBuilder.evalEQ(stateLoad,theValueVal,oldValueVal); 160 161 ProgramStateRef stateEqual = stateLoad->assume(Cmp, true); 162 163 // Were they equal? 164 if (stateEqual) { 165 // Perform the store. 166 ExplodedNodeSet TmpStore; 167 SVal val = stateEqual->getSVal(newValueExpr, LCtx); 168 169 // Handle implicit value casts. 170 if (const TypedValueRegion *R = 171 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 172 val = svalBuilder.evalCast(val,R->getValueType(), newValueExpr->getType()); 173 } 174 175 Eng.evalStore(TmpStore, CE, theValueExpr, N, 176 stateEqual, location, val, &OSAtomicStoreTag); 177 178 if (TmpStore.empty()) { 179 // If no nodes were generated, other checkers must have generated sinks. 180 // We return an empty Dst. 181 return true; 182 } 183 184 StmtNodeBuilder B(TmpStore, Dst, Eng.getBuilderContext()); 185 // Now bind the result of the comparison. 186 for (ExplodedNodeSet::iterator I2 = TmpStore.begin(), 187 E2 = TmpStore.end(); I2 != E2; ++I2) { 188 ExplodedNode *predNew = *I2; 189 ProgramStateRef stateNew = predNew->getState(); 190 // Check for 'void' return type if we have a bogus function prototype. 191 SVal Res = UnknownVal(); 192 QualType T = CE->getType(); 193 if (!T->isVoidType()) 194 Res = Eng.getSValBuilder().makeTruthVal(true, T); 195 B.generateNode(CE, predNew, stateNew->BindExpr(CE, LCtx, Res), 196 false, this); 197 } 198 } 199 200 // Were they not equal? 201 if (ProgramStateRef stateNotEqual = stateLoad->assume(Cmp, false)) { 202 // Check for 'void' return type if we have a bogus function prototype. 203 SVal Res = UnknownVal(); 204 QualType T = CE->getType(); 205 if (!T->isVoidType()) 206 Res = Eng.getSValBuilder().makeTruthVal(false, CE->getType()); 207 StmtNodeBuilder B(N, Dst, Eng.getBuilderContext()); 208 B.generateNode(CE, N, stateNotEqual->BindExpr(CE, LCtx, Res), 209 false, this); 210 } 211 } 212 213 return true; 214 } 215 216 void ento::registerOSAtomicChecker(CheckerManager &mgr) { 217 mgr.registerChecker<OSAtomicChecker>(); 218 } 219