Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 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 | |
Argyrios Kyrtzidis | f029366 | 2011-02-28 01:27:02 +0000 | [diff] [blame] | 14 | #include "ClangSACheckers.h" |
Argyrios Kyrtzidis | ec8605f | 2011-03-01 01:16:21 +0000 | [diff] [blame] | 15 | #include "clang/StaticAnalyzer/Core/Checker.h" |
Argyrios Kyrtzidis | f029366 | 2011-02-28 01:27:02 +0000 | [diff] [blame] | 16 | #include "clang/StaticAnalyzer/Core/CheckerManager.h" |
| 17 | #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 18 | #include "clang/Basic/Builtins.h" |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 19 | |
| 20 | using namespace clang; |
Ted Kremenek | 9ef6537 | 2010-12-23 07:20:52 +0000 | [diff] [blame] | 21 | using namespace ento; |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 22 | |
| 23 | namespace { |
| 24 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 25 | class OSAtomicChecker : public Checker<eval::InlineCall> { |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 26 | public: |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 27 | bool inlineCall(const CallExpr *CE, ExprEngine &Eng, |
| 28 | ExplodedNode *Pred, ExplodedNodeSet &Dst) const; |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 29 | |
| 30 | private: |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 31 | bool evalOSAtomicCompareAndSwap(const CallExpr *CE, |
| 32 | ExprEngine &Eng, |
| 33 | ExplodedNode *Pred, |
| 34 | ExplodedNodeSet &Dst) const; |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 35 | }; |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 36 | } |
| 37 | |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 38 | static StringRef getCalleeName(ProgramStateRef State, |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 39 | const CallExpr *CE, |
| 40 | const LocationContext *LCtx) { |
Anna Zaks | b805c8f | 2011-12-01 05:57:37 +0000 | [diff] [blame] | 41 | const Expr *Callee = CE->getCallee(); |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 42 | SVal L = State->getSVal(Callee, LCtx); |
Anna Zaks | b805c8f | 2011-12-01 05:57:37 +0000 | [diff] [blame] | 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 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 52 | bool OSAtomicChecker::inlineCall(const CallExpr *CE, |
| 53 | ExprEngine &Eng, |
| 54 | ExplodedNode *Pred, |
| 55 | ExplodedNodeSet &Dst) const { |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 56 | StringRef FName = getCalleeName(Pred->getState(), |
| 57 | CE, Pred->getLocationContext()); |
Anna Zaks | b805c8f | 2011-12-01 05:57:37 +0000 | [diff] [blame] | 58 | if (FName.empty()) |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 59 | return false; |
| 60 | |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 61 | // Check for compare and swap. |
Ted Kremenek | a0f7727 | 2009-12-16 06:03:24 +0000 | [diff] [blame] | 62 | if (FName.startswith("OSAtomicCompareAndSwap") || |
| 63 | FName.startswith("objc_atomicCompareAndSwap")) |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 64 | return evalOSAtomicCompareAndSwap(CE, Eng, Pred, Dst); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 65 | |
| 66 | // FIXME: Other atomics. |
| 67 | return false; |
| 68 | } |
| 69 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 70 | bool OSAtomicChecker::evalOSAtomicCompareAndSwap(const CallExpr *CE, |
| 71 | ExprEngine &Eng, |
| 72 | ExplodedNode *Pred, |
| 73 | ExplodedNodeSet &Dst) const { |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 74 | // Not enough arguments to match OSAtomicCompareAndSwap? |
| 75 | if (CE->getNumArgs() != 3) |
| 76 | return false; |
| 77 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 78 | ASTContext &Ctx = Eng.getContext(); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 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 | |
Ted Kremenek | ca80453 | 2011-08-12 23:04:46 +0000 | [diff] [blame] | 103 | static SimpleProgramPointTag OSAtomicLoadTag("OSAtomicChecker : Load"); |
| 104 | static SimpleProgramPointTag OSAtomicStoreTag("OSAtomicChecker : Store"); |
| 105 | |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 106 | // Load 'theValue'. |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 107 | ProgramStateRef state = Pred->getState(); |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 108 | const LocationContext *LCtx = Pred->getLocationContext(); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 109 | ExplodedNodeSet Tmp; |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 110 | SVal location = state->getSVal(theValueExpr, LCtx); |
Zhongxing Xu | 71f219a | 2010-06-23 02:06:56 +0000 | [diff] [blame] | 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 |
Zhongxing Xu | 2470446 | 2010-06-23 02:12:00 +0000 | [diff] [blame] | 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. |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 118 | QualType LoadTy; |
Ted Kremenek | 9697934 | 2011-08-12 20:02:48 +0000 | [diff] [blame] | 119 | if (const TypedValueRegion *TR = |
| 120 | dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { |
Zhongxing Xu | 018220c | 2010-08-11 06:10:55 +0000 | [diff] [blame] | 121 | LoadTy = TR->getValueType(); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 122 | } |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 123 | Eng.evalLoad(Tmp, theValueExpr, Pred, |
Ted Kremenek | ca80453 | 2011-08-12 23:04:46 +0000 | [diff] [blame] | 124 | state, location, &OSAtomicLoadTag, LoadTy); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 125 | |
| 126 | if (Tmp.empty()) { |
Anna Zaks | f185cc1 | 2011-10-24 21:19:43 +0000 | [diff] [blame] | 127 | // If no nodes were generated, other checkers must have generated sinks. |
| 128 | // We return an empty Dst. |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 129 | return true; |
| 130 | } |
| 131 | |
| 132 | for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); |
| 133 | I != E; ++I) { |
| 134 | |
| 135 | ExplodedNode *N = *I; |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 136 | ProgramStateRef stateLoad = N->getState(); |
Ted Kremenek | 6b4f567 | 2011-04-27 05:34:09 +0000 | [diff] [blame] | 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. |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 141 | SVal theValueVal_untested = stateLoad->getSVal(theValueExpr, LCtx, true); |
Ted Kremenek | 6b4f567 | 2011-04-27 05:34:09 +0000 | [diff] [blame] | 142 | |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 143 | SVal oldValueVal_untested = stateLoad->getSVal(oldValueExpr, LCtx); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 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 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 155 | SValBuilder &svalBuilder = Eng.getSValBuilder(); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 156 | |
| 157 | // Perform the comparison. |
Ted Kremenek | ca80453 | 2011-08-12 23:04:46 +0000 | [diff] [blame] | 158 | DefinedOrUnknownSVal Cmp = |
| 159 | svalBuilder.evalEQ(stateLoad,theValueVal,oldValueVal); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 160 | |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 161 | ProgramStateRef stateEqual = stateLoad->assume(Cmp, true); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 162 | |
| 163 | // Were they equal? |
| 164 | if (stateEqual) { |
| 165 | // Perform the store. |
| 166 | ExplodedNodeSet TmpStore; |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 167 | SVal val = stateEqual->getSVal(newValueExpr, LCtx); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 168 | |
| 169 | // Handle implicit value casts. |
Ted Kremenek | 9697934 | 2011-08-12 20:02:48 +0000 | [diff] [blame] | 170 | if (const TypedValueRegion *R = |
| 171 | dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) { |
Ted Kremenek | 9c14953 | 2010-12-01 21:57:22 +0000 | [diff] [blame] | 172 | val = svalBuilder.evalCast(val,R->getValueType(), newValueExpr->getType()); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 173 | } |
| 174 | |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 175 | Eng.evalStore(TmpStore, NULL, theValueExpr, N, |
Ted Kremenek | ca80453 | 2011-08-12 23:04:46 +0000 | [diff] [blame] | 176 | stateEqual, location, val, &OSAtomicStoreTag); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 177 | |
| 178 | if (TmpStore.empty()) { |
Anna Zaks | f185cc1 | 2011-10-24 21:19:43 +0000 | [diff] [blame] | 179 | // If no nodes were generated, other checkers must have generated sinks. |
| 180 | // We return an empty Dst. |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 181 | return true; |
| 182 | } |
Anna Zaks | f185cc1 | 2011-10-24 21:19:43 +0000 | [diff] [blame] | 183 | |
Anna Zaks | aa0aeb1 | 2011-10-24 21:19:59 +0000 | [diff] [blame] | 184 | StmtNodeBuilder B(TmpStore, Dst, Eng.getBuilderContext()); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 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; |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 189 | ProgramStateRef stateNew = predNew->getState(); |
Ted Kremenek | c50e6df | 2010-01-11 02:33:26 +0000 | [diff] [blame] | 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()) |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 194 | Res = Eng.getSValBuilder().makeTruthVal(true, T); |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 195 | B.generateNode(CE, predNew, stateNew->BindExpr(CE, LCtx, Res), |
| 196 | false, this); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 197 | } |
| 198 | } |
| 199 | |
| 200 | // Were they not equal? |
Ted Kremenek | 8bef823 | 2012-01-26 21:29:00 +0000 | [diff] [blame] | 201 | if (ProgramStateRef stateNotEqual = stateLoad->assume(Cmp, false)) { |
Ted Kremenek | c50e6df | 2010-01-11 02:33:26 +0000 | [diff] [blame] | 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()) |
Anna Zaks | dff6ef9 | 2011-10-05 23:37:30 +0000 | [diff] [blame] | 206 | Res = Eng.getSValBuilder().makeTruthVal(false, CE->getType()); |
Anna Zaks | aa0aeb1 | 2011-10-24 21:19:59 +0000 | [diff] [blame] | 207 | StmtNodeBuilder B(N, Dst, Eng.getBuilderContext()); |
Ted Kremenek | 5eca482 | 2012-01-06 22:09:28 +0000 | [diff] [blame] | 208 | B.generateNode(CE, N, stateNotEqual->BindExpr(CE, LCtx, Res), |
| 209 | false, this); |
Zhongxing Xu | 1ec4e97 | 2009-12-09 12:23:28 +0000 | [diff] [blame] | 210 | } |
| 211 | } |
| 212 | |
| 213 | return true; |
| 214 | } |
Argyrios Kyrtzidis | f029366 | 2011-02-28 01:27:02 +0000 | [diff] [blame] | 215 | |
| 216 | void ento::registerOSAtomicChecker(CheckerManager &mgr) { |
| 217 | mgr.registerChecker<OSAtomicChecker>(); |
| 218 | } |