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