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 ExplodedNode *generateNode(const ProgramState *State, 37 ExplodedNode *Pred, const CallExpr *Statement, 38 StmtNodeBuilder &B, ExplodedNodeSet &Dst) const; 39 }; 40 } 41 42 bool OSAtomicChecker::inlineCall(const CallExpr *CE, 43 ExprEngine &Eng, 44 ExplodedNode *Pred, 45 ExplodedNodeSet &Dst) const { 46 const ProgramState *state = Pred->getState(); 47 const Expr *Callee = CE->getCallee(); 48 SVal L = state->getSVal(Callee); 49 50 const FunctionDecl *FD = L.getAsFunctionDecl(); 51 if (!FD) 52 return false; 53 54 const IdentifierInfo *II = FD->getIdentifier(); 55 if (!II) 56 return false; 57 58 StringRef FName(II->getName()); 59 60 // Check for compare and swap. 61 if (FName.startswith("OSAtomicCompareAndSwap") || 62 FName.startswith("objc_atomicCompareAndSwap")) 63 return evalOSAtomicCompareAndSwap(CE, Eng, Pred, Dst); 64 65 // FIXME: Other atomics. 66 return false; 67 } 68 69 ExplodedNode *OSAtomicChecker::generateNode(const ProgramState *State, 70 ExplodedNode *Pred, 71 const CallExpr *Statement, 72 StmtNodeBuilder &B, 73 ExplodedNodeSet &Dst) const { 74 ExplodedNode *N = B.generateNode(Statement, State, Pred, this); 75 if (N) 76 Dst.Add(N); 77 return N; 78 } 79 80 bool OSAtomicChecker::evalOSAtomicCompareAndSwap(const CallExpr *CE, 81 ExprEngine &Eng, 82 ExplodedNode *Pred, 83 ExplodedNodeSet &Dst) const { 84 // Not enough arguments to match OSAtomicCompareAndSwap? 85 if (CE->getNumArgs() != 3) 86 return false; 87 88 StmtNodeBuilder &Builder = Eng.getBuilder(); 89 ASTContext &Ctx = Eng.getContext(); 90 const Expr *oldValueExpr = CE->getArg(0); 91 QualType oldValueType = Ctx.getCanonicalType(oldValueExpr->getType()); 92 93 const Expr *newValueExpr = CE->getArg(1); 94 QualType newValueType = Ctx.getCanonicalType(newValueExpr->getType()); 95 96 // Do the types of 'oldValue' and 'newValue' match? 97 if (oldValueType != newValueType) 98 return false; 99 100 const Expr *theValueExpr = CE->getArg(2); 101 const PointerType *theValueType=theValueExpr->getType()->getAs<PointerType>(); 102 103 // theValueType not a pointer? 104 if (!theValueType) 105 return false; 106 107 QualType theValueTypePointee = 108 Ctx.getCanonicalType(theValueType->getPointeeType()).getUnqualifiedType(); 109 110 // The pointee must match newValueType and oldValueType. 111 if (theValueTypePointee != newValueType) 112 return false; 113 114 static SimpleProgramPointTag OSAtomicLoadTag("OSAtomicChecker : Load"); 115 static SimpleProgramPointTag OSAtomicStoreTag("OSAtomicChecker : Store"); 116 117 // Load 'theValue'. 118 const ProgramState *state = Pred->getState(); 119 ExplodedNodeSet Tmp; 120 SVal location = state->getSVal(theValueExpr); 121 // Here we should use the value type of the region as the load type, because 122 // we are simulating the semantics of the function, not the semantics of 123 // passing argument. So the type of theValue expr is not we are loading. 124 // But usually the type of the varregion is not the type we want either, 125 // we still need to do a CastRetrievedVal in store manager. So actually this 126 // LoadTy specifying can be omitted. But we put it here to emphasize the 127 // semantics. 128 QualType LoadTy; 129 if (const TypedValueRegion *TR = 130 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 131 LoadTy = TR->getValueType(); 132 } 133 Eng.evalLoad(Tmp, theValueExpr, Pred, 134 state, location, &OSAtomicLoadTag, LoadTy); 135 136 if (Tmp.empty()) { 137 // If no nodes were generated, other checkers must generated sinks. But 138 // since the builder state was restored, we set it manually to prevent 139 // auto transition. 140 // FIXME: there should be a better approach. 141 Builder.BuildSinks = true; 142 return true; 143 } 144 145 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); 146 I != E; ++I) { 147 148 ExplodedNode *N = *I; 149 const ProgramState *stateLoad = N->getState(); 150 151 // Use direct bindings from the environment since we are forcing a load 152 // from a location that the Environment would typically not be used 153 // to bind a value. 154 SVal theValueVal_untested = stateLoad->getSVal(theValueExpr, true); 155 156 SVal oldValueVal_untested = stateLoad->getSVal(oldValueExpr); 157 158 // FIXME: Issue an error. 159 if (theValueVal_untested.isUndef() || oldValueVal_untested.isUndef()) { 160 return false; 161 } 162 163 DefinedOrUnknownSVal theValueVal = 164 cast<DefinedOrUnknownSVal>(theValueVal_untested); 165 DefinedOrUnknownSVal oldValueVal = 166 cast<DefinedOrUnknownSVal>(oldValueVal_untested); 167 168 SValBuilder &svalBuilder = Eng.getSValBuilder(); 169 170 // Perform the comparison. 171 DefinedOrUnknownSVal Cmp = 172 svalBuilder.evalEQ(stateLoad,theValueVal,oldValueVal); 173 174 const ProgramState *stateEqual = stateLoad->assume(Cmp, true); 175 176 // Were they equal? 177 if (stateEqual) { 178 // Perform the store. 179 ExplodedNodeSet TmpStore; 180 SVal val = stateEqual->getSVal(newValueExpr); 181 182 // Handle implicit value casts. 183 if (const TypedValueRegion *R = 184 dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { 185 val = svalBuilder.evalCast(val,R->getValueType(), newValueExpr->getType()); 186 } 187 188 Eng.evalStore(TmpStore, NULL, theValueExpr, N, 189 stateEqual, location, val, &OSAtomicStoreTag); 190 191 if (TmpStore.empty()) { 192 // If no nodes were generated, other checkers must generated sinks. But 193 // since the builder state was restored, we set it manually to prevent 194 // auto transition. 195 // FIXME: there should be a better approach. 196 Builder.BuildSinks = true; 197 return true; 198 } 199 200 // Now bind the result of the comparison. 201 for (ExplodedNodeSet::iterator I2 = TmpStore.begin(), 202 E2 = TmpStore.end(); I2 != E2; ++I2) { 203 ExplodedNode *predNew = *I2; 204 const ProgramState *stateNew = predNew->getState(); 205 // Check for 'void' return type if we have a bogus function prototype. 206 SVal Res = UnknownVal(); 207 QualType T = CE->getType(); 208 if (!T->isVoidType()) 209 Res = Eng.getSValBuilder().makeTruthVal(true, T); 210 generateNode(stateNew->BindExpr(CE, Res), predNew, CE, Builder, Dst); 211 } 212 } 213 214 // Were they not equal? 215 if (const ProgramState *stateNotEqual = stateLoad->assume(Cmp, false)) { 216 // Check for 'void' return type if we have a bogus function prototype. 217 SVal Res = UnknownVal(); 218 QualType T = CE->getType(); 219 if (!T->isVoidType()) 220 Res = Eng.getSValBuilder().makeTruthVal(false, CE->getType()); 221 generateNode(stateNotEqual->BindExpr(CE, Res), N, CE, Builder, Dst); 222 } 223 } 224 225 return true; 226 } 227 228 void ento::registerOSAtomicChecker(CheckerManager &mgr) { 229 mgr.registerChecker<OSAtomicChecker>(); 230 } 231
