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
 *
 * Lock analysis. One implementation runs on the whole program or a slice:
 * analyze() is templated on the graph handle (SVFIR* or const SlicedSVFIRView*),
 * as used by "Multi-Stage On-Demand Program Slicing for Modular Analysis of
 * Multi-Threaded Programs" (ISSTA 2026).
 */
 
#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 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, class CGGraph> void analyzeIntraProcedualLock(ICFGGraph icfg, CGGraph cg);
    template<class ICFGGraph, class CGGraph> bool intraForwardTraverse(ICFGGraph icfg, CGGraph cg, const ICFGNode* lock, InstSet& unlockset, InstSet& forwardInsts);
    template<class ICFGGraph, class CGGraph> bool intraBackwardTraverse(ICFGGraph icfg, CGGraph cg, 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);
    void buildCandidateFuncSetforLock();
 
 
 
    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 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 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;
    }
 
    CxtStmtToCxtLockSet getCSTCLS()
    {
        return cxtStmtToCxtLockSet;
    }
    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);
 
    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)
    {
        CxtLockSet toBeDeleted;
        for(CxtLockSet::const_iterator it = tgrlockset.begin(), eit = tgrlockset.end(); it!=eit; ++it)
        {
            if(srclockset.find(*it)==srclockset.end())
                toBeDeleted.insert(*it);
        }
        for(CxtLockSet::const_iterator it = toBeDeleted.begin(), eit = toBeDeleted.end(); it!=eit; ++it)
        {
            tgrlockset.erase(*it);
        }
        return !toBeDeleted.empty();
    }
 
    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;
 
    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_ */