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 }
  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 }