contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/OSAtomicChecker.cpp

   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 }