LockAnalysis.h

Go to the documentation of this file.

//===- LockAnalysis.h -- Analysis of locksets-------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * LockAnalysis.h
 *
 *  Created on: 26 Aug 2015
 *      Author: pengd
 */
 
#ifndef INCLUDE_MTA_LockAnalysis_H_
#define INCLUDE_MTA_LockAnalysis_H_
 
#include "MTA/TCT.h"
 
#include <memory>
#include <vector>
 
namespace SVF
{
 
// Forward declaration for the sliced-graph handle analyze() can run on.
class SlicedSVFIRView;
 
class LockAnalysis
{
 
public:
    enum ValDomain
    {
        Empty,  // initial(dummy) state
        TDLocked,  // stmt is locked
        TDUnlocked,  //  stmt is unlocked
    };
 
    typedef CxtStmt CxtLock;
    typedef CxtProc CxtLockProc;
 
    typedef NodeBS LockSet;
    typedef TCT::InstVec InstVec;
    typedef Set<const ICFGNode*> InstSet;
    typedef InstSet CISpan;
    typedef Map<const ICFGNode*, CISpan>CILockToSpan;
    typedef Set<const FunObjVar*> FunSet;
    typedef Map<const ICFGNode*, InstSet> InstToInstSetMap;
    typedef Map<CxtStmt, ValDomain> CxtStmtToLockFlagMap;
    typedef FIFOWorkList<CxtStmt> CxtStmtWorkList;
    typedef Set<CxtStmt> LockSpan;
    typedef Set<CxtStmt> CxtStmtSet;
    typedef Set<CxtLock> CxtLockSet;
    typedef Set<CallStrCxt> CallStrCxtSet;
    typedef Map<CallStrCxt, CallStrCxtSet> ContextSuffixToContexts;
    typedef Map<const ICFGNode*, ContextSuffixToContexts> InstToContextSuffixMap;
 
    typedef Map<CxtLock, LockSpan> CxtLockToSpan;
    typedef Map<CxtLock, NodeBS> CxtLockToLockSet;
    typedef Map<const ICFGNode*, NodeBS> LockSiteToLockSet;
    typedef Map<const ICFGNode*, CxtStmtSet> InstToCxtStmtSet;
    typedef Map<CxtStmt, CxtLockSet> CxtStmtToCxtLockSet;
    typedef FIFOWorkList<CxtLockProc> CxtLockProcVec;
    typedef Set<CxtLockProc> CxtLockProcSet;
 
    LockAnalysis(TCT* t) : tct(t), lockTime(0),numOfTotalQueries(0), numOfLockedQueries(0), lockQueriesTime(0)
    {
    }
 
    ~LockAnalysis() = default;
 
    template<class ICFGGraph, class CGGraph> void analyze(ICFGGraph icfg, CGGraph cg);
    template<class ICFGGraph>
    void analyzeIntraProceduralLock(ICFGGraph icfg);
    template<class ICFGGraph>
    bool intraForwardTraverse(ICFGGraph icfg, const ICFGNode* lock,
                              InstSet& unlockSet, InstSet& forwardInsts);
    template<class ICFGGraph>
    bool intraBackwardTraverse(ICFGGraph icfg, const InstSet& unlockSet,
                               InstSet& backwardInsts);
 
    template<class ICFGGraph, class CGGraph> void collectCxtLock(ICFGGraph icfg, CGGraph cg);
    template<class ICFGGraph, class CGGraph> void analyzeLockSpanCxtStmt(ICFGGraph icfg, CGGraph cg);
 
    template<class ICFGGraph, class CGGraph> void collectLockUnlockSites(ICFGGraph icfg, CGGraph cg);
    template<class CGGraph>
    void buildCandidateFuncSetForLock(CGGraph cg);
 
 
 
    inline bool isIntraLock(const ICFGNode* lock) const
    {
        assert(lockSites.find(lock)!=lockSites.end() && "not a lock site?");
        return ciLockToSpan.find(lock)!=ciLockToSpan.end();
    }
 
    inline void addIntraLock(const ICFGNode* lockSite, const InstSet& stmts)
    {
        for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
        {
            instCILocksMap[*it].insert(lockSite);
            ciLockToSpan[lockSite].insert(*it);
        }
    }
 
    inline void addCondIntraLock(const ICFGNode* lockSite, const InstSet& stmts)
    {
        for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
        {
            instToCondCILocksMap[*it].insert(lockSite);
        }
    }
 
    inline bool isInsideIntraLock(const ICFGNode* stmt) const
    {
        return instCILocksMap.find(stmt)!=instCILocksMap.end() || isInsideCondIntraLock(stmt);
    }
 
    inline bool isInsideCondIntraLock(const ICFGNode* stmt) const
    {
        return instToCondCILocksMap.find(stmt)!=instToCondCILocksMap.end();
    }
 
    inline bool hasIntraLockSet(const ICFGNode* stmt) const
    {
        return instCILocksMap.find(stmt)!=instCILocksMap.end();
    }
 
    inline const InstSet& getIntraLockSet(const ICFGNode* stmt) const
    {
        InstToInstSetMap::const_iterator it = instCILocksMap.find(stmt);
        assert(it!=instCILocksMap.end() && "intralock not found!");
        return it->second;
    }
 
    inline const InstSet& getCondIntraLockSet(const ICFGNode* stmt) const
    {
        InstToInstSetMap::const_iterator it = instToCondCILocksMap.find(stmt);
        assert(it!=instToCondCILocksMap.end() && "conditional intralock not found!");
        return it->second;
    }
 
 
 
    inline void addCxtLock(const CallStrCxt& cxt,const ICFGNode* inst)
    {
        CxtLock cxtlock(cxt,inst);
        cxtLockSet.insert(cxtlock);
        DBOUT(DMTA, SVFUtil::outs() << "LockAnalysis Process new lock "; cxtlock.dump());
    }
 
    inline bool hasCxtLock(const CxtLock& cxtLock) const
    {
        return cxtLockSet.find(cxtLock)!=cxtLockSet.end();
    }
 
    inline bool intersects(const CxtLockSet& lockset1,const CxtLockSet& lockset2) const
    {
        for(CxtLockSet::const_iterator it = lockset1.begin(), eit = lockset1.end(); it!=eit; ++it)
        {
            const CxtLock& lock = *it;
            for(CxtLockSet::const_iterator lit = lockset2.begin(), elit = lockset2.end(); lit!=elit; ++lit)
            {
                if(lock==*lit)
                    return true;
            }
        }
        return false;
    }
    inline bool alias(const CxtLockSet& lockset1,const CxtLockSet& lockset2)
    {
        for(CxtLockSet::const_iterator it = lockset1.begin(), eit = lockset1.end(); it!=eit; ++it)
        {
            const CxtLock& lock = *it;
            for(CxtLockSet::const_iterator lit = lockset2.begin(), elit = lockset2.end(); lit!=elit; ++lit)
            {
                if(isAliasedLocks(lock,*lit))
                    return true;
            }
        }
        return false;
    }
 
    inline bool isLockCandidateFun(const FunObjVar* fun) const
    {
        return lockCandidateFuncSet.find(fun)!=lockCandidateFuncSet.end();
    }
 
 
 
    inline bool hasCxtStmtFromInst(const ICFGNode* inst) const
    {
        InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
        return (it != instToCxtStmtSet.end());
    }
    inline const CxtStmtSet& getCxtStmtsFromInst(const ICFGNode* inst) const
    {
        InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
        assert(it != instToCxtStmtSet.end());
        return it->second;
    }
    inline void indexCallsiteContext(const ICFGNode* inst, const CallStrCxt& cxt)
    {
        ContextSuffixToContexts& suffixIndex = callsiteContextSuffixIndex[inst];
        for (size_t begin = 0; begin <= cxt.size(); ++begin)
        {
            CallStrCxt suffix(cxt.begin() + begin, cxt.end());
            suffixIndex[suffix].insert(cxt);
        }
    }
    inline const CallStrCxtSet* getCallsiteContextsWithSuffix(
        const ICFGNode* inst, const CallStrCxt& suffix) const
    {
        InstToContextSuffixMap::const_iterator instIt = callsiteContextSuffixIndex.find(inst);
        if (instIt == callsiteContextSuffixIndex.end())
            return nullptr;
        ContextSuffixToContexts::const_iterator suffixIt = instIt->second.find(suffix);
        return suffixIt == instIt->second.end() ? nullptr : &suffixIt->second;
    }
    inline bool hasCxtLockFromCxtStmt(const CxtStmt& cts) const
    {
        CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
        return (it != cxtStmtToCxtLockSet.end());
    }
    inline const CxtLockSet& getCxtLockFromCxtStmt(const CxtStmt& cts) const
    {
        CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
        assert(it != cxtStmtToCxtLockSet.end());
        return it->second;
    }
    inline CxtLockSet& getCxtLockFromCxtStmt(const CxtStmt& cts)
    {
        CxtStmtToCxtLockSet::iterator it = cxtStmtToCxtLockSet.find(cts);
        assert(it != cxtStmtToCxtLockSet.end());
        return it->second;
    }
    inline bool addCxtStmtToSpan(const CxtStmt& cts, const CxtLock& cl)
    {
        cxtLockToSpan[cl].insert(cts);
        return cxtStmtToCxtLockSet[cts].insert(cl).second;
    }
    inline bool removeCxtStmtToSpan(CxtStmt& cts, const CxtLock& cl)
    {
        bool find = cxtStmtToCxtLockSet[cts].find(cl)!=cxtStmtToCxtLockSet[cts].end();
        if(find)
        {
            cxtStmtToCxtLockSet[cts].erase(cl);
            cxtLockToSpan[cl].erase(cts);
        }
        return find;
    }
 
    inline void touchCxtStmt(CxtStmt& cts)
    {
        cxtStmtToCxtLockSet[cts];
    }
    inline bool hasSpanFromCxtLock(const CxtLock& cl)
    {
        return cxtLockToSpan.find(cl) != cxtLockToSpan.end();
    }
    inline LockSpan& getSpanFromCxtLock(const CxtLock& cl)
    {
        assert(cxtLockToSpan.find(cl) != cxtLockToSpan.end());
        return cxtLockToSpan[cl];
    }
 
    inline bool hasOneCxtInLockSpan(const ICFGNode *I, LockSpan lspan) const
    {
        if(!hasCxtStmtFromInst(I))
            return false;
        const LockSpan ctsset = getCxtStmtsFromInst(I);
        for (LockSpan::const_iterator cts = ctsset.begin(), ects = ctsset.end(); cts != ects; cts++)
        {
            if(lspan.find(*cts) != lspan.end())
            {
                return true;
            }
        }
        return false;
    }
 
    inline bool hasAllCxtInLockSpan(const ICFGNode *I, LockSpan lspan) const
    {
        if(!hasCxtStmtFromInst(I))
            return false;
        const LockSpan ctsset = getCxtStmtsFromInst(I);
        for (LockSpan::const_iterator cts = ctsset.begin(), ects = ctsset.end(); cts != ects; cts++)
        {
            if (lspan.find(*cts) == lspan.end())
            {
                return false;
            }
        }
        return true;
    }
 
    bool isProtectedByCommonLock(const ICFGNode *i1, const ICFGNode *i2);
    bool isProtectedByCommonCxtLock(const ICFGNode *i1, const ICFGNode *i2);
    bool isProtectedByCommonCxtLock(const CxtStmt& cxtStmt1, const CxtStmt& cxtStmt2);
    bool isProtectedByCommonCILock(const ICFGNode *i1, const ICFGNode *i2);
 
    bool isInSameSpan(const ICFGNode *I1, const ICFGNode *I2);
    bool isInSameCSSpan(const ICFGNode *i1, const ICFGNode *i2) const;
    bool isInSameCSSpan(const CxtStmt& cxtStmt1, const CxtStmt& cxtStmt2) const;
    bool isInSameCISpan(const ICFGNode *i1, const ICFGNode *i2) const;
 
    inline u32_t getNumOfCxtLocks()
    {
        return cxtLockSet.size();
    }
    void printLocks(const CxtStmt& cts);
 
    TCT* getTCT()
    {
        return tct;
    }
protected:
    template<class ICFGGraph, class CGGraph> void handleFork(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts);
 
    template<class ICFGGraph, class CGGraph> void handleCall(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts);
 
    template<class ICFGGraph, class CGGraph> void handleRet(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts);
 
    void handleReturnAtCallsite(const CxtStmt& exitCxtStmt,
                                const FunObjVar* callee, const ICFGNode* callsite,
                                const std::vector<const ICFGNode*>& successors);
 
    template<class ICFGGraph, class CGGraph> void handleIntra(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts);
 
    template<class ICFGGraph, class CGGraph> void handleCallRelation(ICFGGraph icfg, CGGraph cg, CxtLockProc& clp, const CallGraphEdge* cgEdge, const CallICFGNode* call);
 
    bool isAliasedLocks(const CxtLock& cl1, const CxtLock& cl2)
    {
        return isAliasedLocks(cl1.getStmt(), cl2.getStmt());
    }
    bool isAliasedLocks(const ICFGNode* i1, const ICFGNode* i2);
 
 
 
    void markCxtStmtFlag(const CxtStmt& tgr, const CxtStmt& src)
    {
        const CxtLockSet& srclockset = getCxtLockFromCxtStmt(src);
        if(hasCxtLockFromCxtStmt(tgr)== false)
        {
            for(CxtLockSet::const_iterator it = srclockset.begin(), eit = srclockset.end(); it!=eit; ++it)
            {
                addCxtStmtToSpan(tgr,*it);
            }
            pushToCTSWorkList(tgr);
        }
        else
        {
            if(intersect(getCxtLockFromCxtStmt(tgr),srclockset))
            {
                pushToCTSWorkList(tgr);
            }
        }
    }
    bool intersect(CxtLockSet& tgrlockset, const CxtLockSet& srclockset)
    {
        bool changed = false;
        for (CxtLockSet::iterator it = tgrlockset.begin(); it != tgrlockset.end(); )
        {
            if (srclockset.find(*it) == srclockset.end())
            {
                it = tgrlockset.erase(it);
                changed = true;
            }
            else
                ++it;
        }
        return changed;
    }
 
    inline void clearFlagMap()
    {
        cxtStmtList.clear();
    }
 
 
    inline bool pushToCTPWorkList(const CxtLockProc& clp)
    {
        if (isVisitedCTPs(clp) == false)
        {
            visitedCTPs.insert(clp);
            return clpList.push(clp);
        }
        return false;
    }
    inline CxtLockProc popFromCTPWorkList()
    {
        CxtLockProc clp = clpList.pop();
        return clp;
    }
    inline bool isVisitedCTPs(const CxtLockProc& clp) const
    {
        return visitedCTPs.find(clp) != visitedCTPs.end();
    }
 
 
    inline bool pushToCTSWorkList(const CxtStmt& cs)
    {
        return cxtStmtList.push(cs);
    }
    inline CxtStmt popFromCTSWorkList()
    {
        CxtStmt clp = cxtStmtList.pop();
        return clp;
    }
 
 
 
    void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee);
    bool matchCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee);
    bool isContextSuffix(const CallStrCxt& lhs, const CallStrCxt& call);
 
    inline bool isTDFork(const ICFGNode* call)
    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDFork(SVFUtil::cast<CallICFGNode>(call));
    }
    inline bool isTDAcquire(const ICFGNode* call)
    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDAcquire(SVFUtil::cast<CallICFGNode>(call));
    }
    inline bool isTDRelease(const ICFGNode* call)
    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDRelease(SVFUtil::cast<CallICFGNode>(call));
    }
    inline bool isCallSite(const ICFGNode* inst)
    {
        return tct->isCallSite(inst);
    }
    inline bool isExtCall(const ICFGNode* inst)
    {
        return tct->isExtCall(inst);
    }
    inline const SVFVar* getLockVal(const ICFGNode* call)
    {
        return getTCG()->getThreadAPI()->getLockVal(call);
    }
    inline ThreadCallGraph* getTCG() const
    {
        return tct->getThreadCallGraph();
    }
 
    TCT* tct;
 
    CxtStmtWorkList cxtStmtList;
 
    InstToCxtStmtSet instToCxtStmtSet;
 
    InstToContextSuffixMap callsiteContextSuffixIndex;
 
    CxtLockSet cxtLockSet;
 
 
    CxtLockToSpan cxtLockToSpan;
    CxtStmtToCxtLockSet cxtStmtToCxtLockSet;
 
 
    CxtLockProcVec clpList; 
    CxtLockProcSet visitedCTPs; 
 
 
    InstSet lockSites;
    InstSet unlockSites;
 
 
    FunSet lockCandidateFuncSet;
 
 
    CILockToSpan ciLockToSpan;
    InstToInstSetMap instCILocksMap;
    InstToInstSetMap instToCondCILocksMap;
 
public:
    double lockTime;
    u32_t numOfTotalQueries;
    u32_t numOfLockedQueries;
    double lockQueriesTime;
};
 
} // End namespace SVF
 
#endif /* INCLUDE_MTA_LockAnalysis_H_ */