#include <LockAnalysis.h>

Public Types
enum	ValDomain { Empty , TDLocked , TDUnlocked }
	semilattice Empty==>TDUnlocked==>TDLocked More...

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

Public Member Functions
	LockAnalysis (TCT *t)

void	analyze ()

void	analyzeIntraProcedualLock ()

bool	intraForwardTraverse (const ICFGNode *lock, InstSet &unlockset, InstSet &forwardInsts)

bool	intraBackwardTraverse (const InstSet &unlockset, InstSet &backwardInsts)

void	collectCxtLock ()

void	analyzeLockSpanCxtStmt ()

void	collectLockUnlocksites ()

void	buildCandidateFuncSetforLock ()

bool	isIntraLock (const ICFGNode *lock) const
	Intraprocedural locks.

void	addIntraLock (const ICFGNode *lockSite, const InstSet &stmts)
	Add intra-procedural lock.

void	addCondIntraLock (const ICFGNode *lockSite, const InstSet &stmts)
	Add intra-procedural lock.

bool	isInsideIntraLock (const ICFGNode *stmt) const
	Return true if a statement is inside an intra-procedural lock.

bool	isInsideCondIntraLock (const ICFGNode *stmt) const
	Return true if a statement is inside a partial lock/unlock pair (conditional lock with unconditional unlock)

const InstSet &	getIntraLockSet (const ICFGNode *stmt) const

void	addCxtLock (const CallStrCxt &cxt, const ICFGNode *inst)
	Context-sensitive locks.

bool	hasCxtLock (const CxtLock &cxtLock) const
	Get context-sensitive lock.

bool	intersects (const CxtLockSet &lockset1, const CxtLockSet &lockset2) const
	Return true if the intersection of two locksets is not empty.

bool	alias (const CxtLockSet &lockset1, const CxtLockSet &lockset2)
	Return true if two locksets has at least one alias lock.

bool	isLockCandidateFun (const FunObjVar *fun) const
	Return true if it is a candidate function.

bool	hasCxtStmtFromInst (const ICFGNode *inst) const
	Context-sensitive statement and lock spans.

const CxtStmtSet &	getCxtStmtsFromInst (const ICFGNode *inst) const

bool	hasCxtLockfromCxtStmt (const CxtStmt &cts) const

const CxtLockSet &	getCxtLockfromCxtStmt (const CxtStmt &cts) const

CxtLockSet &	getCxtLockfromCxtStmt (const CxtStmt &cts)

bool	addCxtStmtToSpan (const CxtStmt &cts, const CxtLock &cl)
	Add context-sensitive statement.

bool	removeCxtStmtToSpan (CxtStmt &cts, const CxtLock &cl)
	Add context-sensitive statement.

CxtStmtToCxtLockSet	getCSTCLS ()

void	touchCxtStmt (CxtStmt &cts)
	Touch this context statement.

bool	hasSpanfromCxtLock (const CxtLock &cl)

LockSpan &	getSpanfromCxtLock (const CxtLock &cl)

bool	hasOneCxtInLockSpan (const ICFGNode *I, LockSpan lspan) const
	Check if one instruction's context stmt is in a lock span.

bool	hasAllCxtInLockSpan (const ICFGNode *I, LockSpan lspan) const

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

u32_t	getNumOfCxtLocks ()

void	printLocks (const CxtStmt &cts)
	Print locks and spans.

TCT *	getTCT ()
	Get tct.

Public Attributes
double	lockTime

u32_t	numOfTotalQueries

u32_t	numOfLockedQueries

double	lockQueriesTime

Private Member Functions
void	handleFork (const CxtStmt &cts)
	Handle fork.

void	handleCall (const CxtStmt &cts)
	Handle call.

void	handleRet (const CxtStmt &cts)
	Handle return.

void	handleIntra (const CxtStmt &cts)
	Handle intra.

void	handleCallRelation (CxtLockProc &clp, const CallGraphEdge cgEdge, const CallICFGNode call)
	Handle call relations.

bool	isAliasedLocks (const CxtLock &cl1, const CxtLock &cl2)
	Return true it a lock matches an unlock.

bool	isAliasedLocks (const ICFGNode i1, const ICFGNode i2)

void	markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src)
	Mark thread flags for cxtStmt.

bool	intersect (CxtLockSet &tgrlockset, const CxtLockSet &srclockset)

void	clearFlagMap ()
	Clear flags.

bool	pushToCTPWorkList (const CxtLockProc &clp)
	WorkList helper functions.

CxtLockProc	popFromCTPWorkList ()

bool	isVisitedCTPs (const CxtLockProc &clp) const

bool	pushToCTSWorkList (const CxtStmt &cs)
	Worklist operations.

CxtStmt	popFromCTSWorkList ()

void	pushCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Context helper functions.

bool	matchCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Match context.

bool	isContextSuffix (const CallStrCxt &lhs, const CallStrCxt &call)
	If lhs is a suffix of rhs, including equal.

bool	isTDFork (const ICFGNode *call)
	Whether it is a lock site.

bool	isTDAcquire (const ICFGNode *call)
	Whether it is a lock site.

bool	isTDRelease (const ICFGNode *call)
	Whether it is a unlock site.

bool	isCallSite (const ICFGNode *inst)
	Whether it is a callsite.

bool	isExtCall (const ICFGNode *inst)
	Whether it is calling an external function.

const SVFVar *	getLockVal (const ICFGNode *call)
	Get lock value.

ThreadCallGraph *	getTCG () const
	ThreadCallGraph.

Private Attributes
TCT *	tct
	TCT.

CxtStmtWorkList	cxtStmtList
	context-sensitive statement worklist

InstToCxtStmtSet	instToCxtStmtSet
	Map a statement to all its context-sensitive statements.

CxtLockSet	cxtLockset
	Context-sensitive locks.

CxtLockToSpan	cxtLocktoSpan

CxtStmtToCxtLockSet	cxtStmtToCxtLockSet

CxtLockProcVec	clpList
	Following data structures are used for collecting context-sensitive locks.

CxtLockProcSet	visitedCTPs
	CxtLockProc List.

InstSet	locksites
	Record all visited clps.

InstSet	unlocksites

FunSet	lockcandidateFuncSet
	Candidate functions which relevant to locks/unlocks.

CILockToSpan	ciLocktoSpan
	Used for context-insensitive intra-procedural locks.

InstToInstSetMap	instCILocksMap

InstToInstSetMap	instTocondCILocksMap

Detailed Description

Lock analysis

Definition at line 44 of file LockAnalysis.h.

Member Typedef Documentation

◆ CILockToSpan

typedef Map<const ICFGNode*, CISpan> SVF::LockAnalysis::CILockToSpan

Definition at line 63 of file LockAnalysis.h.

◆ CISpan

typedef InstSet SVF::LockAnalysis::CISpan

Definition at line 62 of file LockAnalysis.h.

◆ CxtLock

typedef CxtStmt SVF::LockAnalysis::CxtLock

Definition at line 56 of file LockAnalysis.h.

◆ CxtLockProc

typedef CxtProc SVF::LockAnalysis::CxtLockProc

Definition at line 57 of file LockAnalysis.h.

◆ CxtLockProcSet

typedef Set<CxtLockProc> SVF::LockAnalysis::CxtLockProcSet

Definition at line 78 of file LockAnalysis.h.

◆ CxtLockProcVec

typedef FIFOWorkList<CxtLockProc> SVF::LockAnalysis::CxtLockProcVec

Definition at line 77 of file LockAnalysis.h.

◆ CxtLockSet

typedef Set<CxtLock> SVF::LockAnalysis::CxtLockSet

Definition at line 70 of file LockAnalysis.h.

◆ CxtLockToLockSet

typedef Map<CxtLock, NodeBS> SVF::LockAnalysis::CxtLockToLockSet

Definition at line 73 of file LockAnalysis.h.

◆ CxtLockToSpan

typedef Map<CxtLock, LockSpan> SVF::LockAnalysis::CxtLockToSpan

Definition at line 72 of file LockAnalysis.h.

◆ CxtStmtSet

typedef Set<CxtStmt> SVF::LockAnalysis::CxtStmtSet

Definition at line 69 of file LockAnalysis.h.

◆ CxtStmtToCxtLockSet

typedef Map<CxtStmt, CxtLockSet> SVF::LockAnalysis::CxtStmtToCxtLockSet

Definition at line 76 of file LockAnalysis.h.

◆ CxtStmtToLockFlagMap

typedef Map<CxtStmt, ValDomain> SVF::LockAnalysis::CxtStmtToLockFlagMap

Definition at line 66 of file LockAnalysis.h.

◆ CxtStmtWorkList

typedef FIFOWorkList<CxtStmt> SVF::LockAnalysis::CxtStmtWorkList

Definition at line 67 of file LockAnalysis.h.

◆ FunSet

typedef Set<const FunObjVar*> SVF::LockAnalysis::FunSet

Definition at line 64 of file LockAnalysis.h.

◆ InstSet

typedef Set<const ICFGNode*> SVF::LockAnalysis::InstSet

Definition at line 61 of file LockAnalysis.h.

◆ InstToCxtStmtSet

typedef Map<const ICFGNode*, CxtStmtSet> SVF::LockAnalysis::InstToCxtStmtSet

Definition at line 75 of file LockAnalysis.h.

◆ InstToInstSetMap

typedef Map<const ICFGNode*, InstSet> SVF::LockAnalysis::InstToInstSetMap

Definition at line 65 of file LockAnalysis.h.

◆ InstVec

typedef TCT::InstVec SVF::LockAnalysis::InstVec

Definition at line 60 of file LockAnalysis.h.

◆ LockSet

typedef NodeBS SVF::LockAnalysis::LockSet

Definition at line 59 of file LockAnalysis.h.

◆ LockSiteToLockSet

typedef Map<const ICFGNode*, NodeBS> SVF::LockAnalysis::LockSiteToLockSet

Definition at line 74 of file LockAnalysis.h.

◆ LockSpan

typedef Set<CxtStmt> SVF::LockAnalysis::LockSpan

Definition at line 68 of file LockAnalysis.h.

Member Enumeration Documentation

◆ ValDomain

enum SVF::LockAnalysis::ValDomain

semilattice Empty==>TDUnlocked==>TDLocked

Enumerator
Empty
TDLocked
TDUnlocked

Definition at line 49 of file LockAnalysis.h.

    {
        Empty,  // initial(dummy) state
        TDLocked,  // stmt is locked
        TDUnlocked,  //  stmt is unlocked
    };

Constructor & Destructor Documentation

◆ LockAnalysis()

SVF::LockAnalysis::LockAnalysis ( TCT * t )

inline

Definition at line 80 of file LockAnalysis.h.

                         : tct(t), lockTime(0),numOfTotalQueries(0), numOfLockedQueries(0), lockQueriesTime(0)
    {
    }

Member Function Documentation

◆ addCondIntraLock()

void SVF::LockAnalysis::addCondIntraLock	(	const ICFGNode *	lockSite,
		const InstSet &	stmts
	)

inline

Add intra-procedural lock.

Definition at line 118 of file LockAnalysis.h.

    {
        for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
        {
            instTocondCILocksMap[*it].insert(lockSite);
        }
    }

◆ addCxtLock()

void SVF::LockAnalysis::addCxtLock	(	const CallStrCxt &	cxt,
		const ICFGNode *	inst
	)

inline

Context-sensitive locks.

Add inter-procedural context-sensitive lock

Definition at line 149 of file LockAnalysis.h.

    {
        CxtLock cxtlock(cxt,inst);
        cxtLockset.insert(cxtlock);
        DBOUT(DMTA, SVFUtil::outs() << "LockAnalysis Process new lock "; cxtlock.dump());
    }

◆ addCxtStmtToSpan()

bool SVF::LockAnalysis::addCxtStmtToSpan	(	const CxtStmt &	cts,
		const CxtLock &	cl
	)

inline

Add context-sensitive statement.

Definition at line 230 of file LockAnalysis.h.

    {
        cxtLocktoSpan[cl].insert(cts);
        return cxtStmtToCxtLockSet[cts].insert(cl).second;
    }

◆ addIntraLock()

void SVF::LockAnalysis::addIntraLock	(	const ICFGNode *	lockSite,
		const InstSet &	stmts
	)

inline

Add intra-procedural lock.

Definition at line 108 of file LockAnalysis.h.

    {
        for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
        {
            instCILocksMap[*it].insert(lockSite);
            ciLocktoSpan[lockSite].insert(*it);
        }
    }

◆ alias()

bool SVF::LockAnalysis::alias	(	const CxtLockSet &	lockset1,
		const CxtLockSet &	lockset2
	)

inline

Return true if two locksets has at least one alias lock.

Definition at line 177 of file LockAnalysis.h.

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

◆ analyze()

void LockAnalysis::analyze ( )

context-sensitive forward traversal from each lock site. Generate following results (1) context-sensitive lock site, (2) maps a context-sensitive lock site to its corresponding lock span.

Definition at line 41 of file LockAnalysis.cpp.

{
 
    collectLockUnlocksites();
    buildCandidateFuncSetforLock();
 
    DOTIMESTAT(double lockStart = PTAStat::getClk(true));
 
    DBOUT(DGENERAL, outs() << "\tIntra-procedural LockAnalysis\n");
    DBOUT(DMTA, outs() << "\tIntra-procedural LockAnalysis\n");
    analyzeIntraProcedualLock();
 
    DBOUT(DGENERAL, outs() << "\tCollect context-sensitive locks\n");
    DBOUT(DMTA, outs() << "\tCollect context-sensitive locks\n");
    collectCxtLock();
 
    DBOUT(DGENERAL, outs() << "\tInter-procedural LockAnalysis\n");
    DBOUT(DMTA, outs() << "\tInter-procedural LockAnalysis\n");
    analyzeLockSpanCxtStmt();
 
    DOTIMESTAT(double lockEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockTime += (lockEnd - lockStart) / TIMEINTERVAL);
}

◆ analyzeIntraProcedualLock()

void LockAnalysis::analyzeIntraProcedualLock ( )

Analyze intraprocedural locks A lock is intraprocedural if its lock span is within a procedural

FIXME:Should we intersect forwardInsts and backwardInsts?

Definition at line 145 of file LockAnalysis.cpp.

{
 
    // Identify the protected Instructions.
    for (InstSet::const_iterator it = locksites.begin(), ie = locksites.end(); it != ie; ++it)
    {
        const ICFGNode* lockSite = *it;
        assert(isCallSite(lockSite) && "Lock acquire instruction must be a CallSite");
 
        // Perform forward traversal
        InstSet forwardInsts;
        InstSet backwardInsts;
        InstSet unlockSet;
 
        bool forward = intraForwardTraverse(lockSite,unlockSet,forwardInsts);
        bool backward = intraBackwardTraverse(unlockSet,backwardInsts);
 
        if(forward && backward)
            addIntraLock(lockSite,forwardInsts);
        else if(forward && !backward)
            addCondIntraLock(lockSite,forwardInsts);
    }
}

◆ analyzeLockSpanCxtStmt()

void LockAnalysis::analyzeLockSpanCxtStmt ( )

Definition at line 332 of file LockAnalysis.cpp.

{
 
    FunSet entryFuncSet = tct->getEntryProcs();
    for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
    {
        if (!isLockCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        const ICFGNode* frontInst = (*it)->getEntryBlock()->front();
        CxtStmt cxtstmt(cxt, frontInst);
        pushToCTSWorkList(cxtstmt);
    }
 
    while (!cxtStmtList.empty())
    {
        CxtStmt cts = popFromCTSWorkList();
 
        touchCxtStmt(cts);
        const ICFGNode* curInst = cts.getStmt();
        instToCxtStmtSet[curInst].insert(cts);
 
        DBOUT(DMTA, outs() << "\nVisit cxtStmt: ");
        DBOUT(DMTA, cts.dump());
 
        DBOUT(DMTA, outs() << "\nIts cxt lock sets: ");
        DBOUT(DMTA, printLocks(cts));
 
        if (isTDFork(curInst))
        {
            handleFork(cts);
        }
        else if (isTDAcquire(curInst))
        {
            assert(hasCxtLock(cts) && "context-sensitive lock not found!!");
            if(addCxtStmtToSpan(cts,cts))
                handleIntra(cts);
        }
        else if (isTDRelease(curInst))
        {
            if(removeCxtStmtToSpan(cts,cts))
                handleIntra(cts);
        }
        else if (isCallSite(curInst) && !isExtCall(curInst))
        {
            handleCall(cts);
        }
        else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
        {
            handleRet(cts);
        }
        else
        {
            handleIntra(cts);
        }
 
    }
 
}

◆ buildCandidateFuncSetforLock()

void LockAnalysis::buildCandidateFuncSetforLock ( )

Collect candidate functions for context-sensitive lock analysis

Definition at line 97 of file LockAnalysis.cpp.

{
 
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    TCT::PTACGNodeSet visited;
    FIFOWorkList<const CallGraphNode*> worklist;
 
    for (InstSet::iterator it = locksites.begin(), eit = locksites.end(); it != eit; ++it)
    {
        const FunObjVar* fun=(*it)->getFun();
        CallGraphNode* cgnode = tcg->getCallGraphNode(fun);
        if (visited.find(cgnode) == visited.end())
        {
            worklist.push(cgnode);
            visited.insert(cgnode);
        }
    }
    for (InstSet::iterator it = unlocksites.begin(), eit = unlocksites.end(); it != eit; ++it)
    {
        const FunObjVar* fun = (*it)->getFun();
        CallGraphNode* cgnode = tcg->getCallGraphNode(fun);
        if (visited.find(cgnode) == visited.end())
        {
            worklist.push(cgnode);
            visited.insert(cgnode);
        }
    }
    while (!worklist.empty())
    {
        const CallGraphNode* node = worklist.pop();
        lockcandidateFuncSet.insert(node->getFunction());
        for (CallGraphNode::const_iterator nit = node->InEdgeBegin(), neit = node->InEdgeEnd(); nit != neit; nit++)
        {
            const CallGraphNode* srcNode = (*nit)->getSrcNode();
            if (visited.find(srcNode) == visited.end())
            {
                visited.insert(srcNode);
                worklist.push(srcNode);
            }
        }
    }
}

◆ clearFlagMap()

void SVF::LockAnalysis::clearFlagMap ( )

inlineprivate

Clear flags.

Definition at line 389 of file LockAnalysis.h.

    {
        cxtStmtList.clear();
    }

◆ collectCxtLock()

void LockAnalysis::collectCxtLock ( )

Definition at line 261 of file LockAnalysis.cpp.

{
    FunSet entryFuncSet = tct->getEntryProcs();
    for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
    {
        if (!isLockCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        CxtLockProc t(cxt, *it);
        pushToCTPWorkList(t);
    }
 
    while (!clpList.empty())
    {
        CxtLockProc clp = popFromCTPWorkList();
        CallGraphNode* cgNode = getTCG()->getCallGraphNode(clp.getProc());
        // lzh TODO.
        if (!isLockCandidateFun(cgNode->getFunction()))
            continue;
 
        for (CallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit != neit; nit++)
        {
            const CallGraphEdge* cgEdge = (*nit);
 
            for (CallGraphEdge::CallInstSet::const_iterator cit = cgEdge->directCallsBegin(), ecit = cgEdge->directCallsEnd();
                    cit != ecit; ++cit)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling direct call:" << **cit << "\t" << cgEdge->getSrcNode()->getFunction()->getName()
                      << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                handleCallRelation(clp, cgEdge, *cit);
            }
            for (CallGraphEdge::CallInstSet::const_iterator ind = cgEdge->indirectCallsBegin(), eind = cgEdge->indirectCallsEnd();
                    ind != eind; ++ind)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling indirect call:" << **ind << "\t"
                      << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName()
                      << "\n");
                handleCallRelation(clp, cgEdge, *ind);
            }
        }
    }
}

◆ collectLockUnlocksites()

void LockAnalysis::collectLockUnlocksites ( )

Collect lock/unlock sites

Definition at line 69 of file LockAnalysis.cpp.

{
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    for (const auto& item : *PAG::getPAG()->getCallGraph())
    {
        const FunObjVar* F = item.second->getFunction();
        for (auto it : *F)
        {
            const SVFBasicBlock* bb = it.second;
            for (const ICFGNode* icfgNode : bb->getICFGNodeList())
            {
                if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDRelease(cast<CallICFGNode>(icfgNode)))
                {
                    unlocksites.insert(icfgNode);
                }
                if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDAcquire(cast<CallICFGNode>(icfgNode)))
                {
                    locksites.insert(icfgNode);
                }
            }
        }
    }
}

◆ getCSTCLS()

CxtStmtToCxtLockSet SVF::LockAnalysis::getCSTCLS ( )

inline

Definition at line 247 of file LockAnalysis.h.

    {
        return cxtStmtToCxtLockSet;
    }

◆ getCxtLockfromCxtStmt() [1/2]

CxtLockSet & SVF::LockAnalysis::getCxtLockfromCxtStmt ( const CxtStmt & cts )

inline

Definition at line 223 of file LockAnalysis.h.

    {
        CxtStmtToCxtLockSet::iterator it = cxtStmtToCxtLockSet.find(cts);
        assert(it != cxtStmtToCxtLockSet.end());
        return it->second;
    }

◆ getCxtLockfromCxtStmt() [2/2]

const CxtLockSet & SVF::LockAnalysis::getCxtLockfromCxtStmt ( const CxtStmt & cts ) const

inline

Definition at line 217 of file LockAnalysis.h.

    {
        CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
        assert(it != cxtStmtToCxtLockSet.end());
        return it->second;
    }

◆ getCxtStmtsFromInst()

const CxtStmtSet & SVF::LockAnalysis::getCxtStmtsFromInst ( const ICFGNode * inst ) const

inline

Definition at line 206 of file LockAnalysis.h.

    {
        InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
        assert(it != instToCxtStmtSet.end());
        return it->second;
    }

◆ getIntraLockSet()

const InstSet & SVF::LockAnalysis::getIntraLockSet ( const ICFGNode * stmt ) const

inline

Definition at line 138 of file LockAnalysis.h.

    {
        InstToInstSetMap::const_iterator it = instCILocksMap.find(stmt);
        assert(it!=instCILocksMap.end() && "intralock not found!");
        return it->second;
    }

◆ getLockVal()

const SVFVar * SVF::LockAnalysis::getLockVal ( const ICFGNode * call )

inlineprivate

Get lock value.

Definition at line 472 of file LockAnalysis.h.

    {
        return getTCG()->getThreadAPI()->getLockVal(call);
    }

◆ getNumOfCxtLocks()

u32_t SVF::LockAnalysis::getNumOfCxtLocks ( )

inline

Definition at line 314 of file LockAnalysis.h.

    {
        return cxtLockset.size();
    }

◆ getSpanfromCxtLock()

LockSpan & SVF::LockAnalysis::getSpanfromCxtLock ( const CxtLock & cl )

inline

Definition at line 260 of file LockAnalysis.h.

    {
        assert(cxtLocktoSpan.find(cl) != cxtLocktoSpan.end());
        return cxtLocktoSpan[cl];
    }

◆ getTCG()

ThreadCallGraph * SVF::LockAnalysis::getTCG ( ) const

inlineprivate

ThreadCallGraph.

Definition at line 477 of file LockAnalysis.h.

    {
        return tct->getThreadCallGraph();
    }

◆ getTCT()

TCT * SVF::LockAnalysis::getTCT ( )

inline

Get tct.

Definition at line 322 of file LockAnalysis.h.

    {
        return tct;
    }

◆ handleCall()

void LockAnalysis::handleCall ( const CxtStmt & cts )

private

Handle call.

Definition at line 430 of file LockAnalysis.cpp.

{
 
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    if (getTCG()->hasCallGraphEdge(call))
    {
        for (CallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(call), ecgIt = getTCG()->getCallEdgeEnd(call);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (SVFUtil::isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, call, svfcallee);
            const ICFGNode* svfInst = svfcallee->getEntryBlock()->front();
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
}

◆ handleCallRelation()

void LockAnalysis::handleCallRelation	(	CxtLockProc &	clp,
		const CallGraphEdge *	cgEdge,
		const CallICFGNode *	cs
	)

private

Handle call relations.

Handling call relations when collecting context-sensitive locks

Definition at line 310 of file LockAnalysis.cpp.

{
 
    CallStrCxt cxt(clp.getContext());
    const ICFGNode* curNode = cs;
    if (isTDAcquire(curNode))
    {
        addCxtLock(cxt,curNode);
        return;
    }
    const FunObjVar* svfcallee = cgEdge->getDstNode()->getFunction();
    pushCxt(cxt, SVFUtil::cast<CallICFGNode>(curNode), svfcallee);
 
    CxtLockProc newclp(cxt, svfcallee);
    if (pushToCTPWorkList(newclp))
    {
        DBOUT(DMTA, outs() << "LockAnalysis Process CallRet old clp --"; clp.dump());
        DBOUT(DMTA, outs() << "LockAnalysis Process CallRet new clp --"; newclp.dump());
    }
 
}

◆ handleFork()

void LockAnalysis::handleFork ( const CxtStmt & cts )

private

Handle fork.

Definition at line 409 of file LockAnalysis.cpp.

{
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    if(getTCG()->hasThreadForkEdge(call))
    {
        for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(call),
                ecgIt = getTCG()->getForkEdgeEnd(call); cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt,call,svfcallee);
            const ICFGNode* svfInst = svfcallee->getEntryBlock()->front();
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
    handleIntra(cts);
}

◆ handleIntra()

void LockAnalysis::handleIntra ( const CxtStmt & cts )

private

Handle intra.

Definition at line 526 of file LockAnalysis.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    for(const ICFGEdge* outEdge : curInst->getOutEdges())
    {
        if(outEdge->getDstNode()->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, outEdge->getDstNode());
            markCxtStmtFlag(newCts, cts);
        }
    }
}

◆ handleRet()

void LockAnalysis::handleRet ( const CxtStmt & cts )

private

Handle return.

Definition at line 453 of file LockAnalysis.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const FunObjVar* svffun = curInst->getFun();
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(svffun);
 
    for (CallGraphNode::const_iterator it = curFunNode->getInEdges().begin(), eit = curFunNode->getInEdges().end(); it != eit; ++it)
    {
        CallGraphEdge* edge = *it;
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(), ecit = (edge)->directCallsEnd(); cit != ecit;
                ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* inst = *cit;
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curInst->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(), ecit = (edge)->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* inst = *cit;
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curInst->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

◆ hasAllCxtInLockSpan()

bool SVF::LockAnalysis::hasAllCxtInLockSpan	(	const ICFGNode *	I,
		LockSpan	lspan
	)		const

inline

Definition at line 285 of file LockAnalysis.h.

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

◆ hasCxtLock()

bool SVF::LockAnalysis::hasCxtLock ( const CxtLock & cxtLock ) const

inline

Get context-sensitive lock.

Definition at line 157 of file LockAnalysis.h.

    {
        return cxtLockset.find(cxtLock)!=cxtLockset.end();
    }

◆ hasCxtLockfromCxtStmt()

bool SVF::LockAnalysis::hasCxtLockfromCxtStmt ( const CxtStmt & cts ) const

inline

Definition at line 212 of file LockAnalysis.h.

    {
        CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
        return (it != cxtStmtToCxtLockSet.end());
    }

◆ hasCxtStmtFromInst()

bool SVF::LockAnalysis::hasCxtStmtFromInst ( const ICFGNode * inst ) const

inline

Context-sensitive statement and lock spans.

Get LockSet and LockSpan

Definition at line 201 of file LockAnalysis.h.

    {
        InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
        return (it != instToCxtStmtSet.end());
    }

◆ hasOneCxtInLockSpan()

bool SVF::LockAnalysis::hasOneCxtInLockSpan	(	const ICFGNode *	I,
		LockSpan	lspan
	)		const

inline

Check if one instruction's context stmt is in a lock span.

Definition at line 270 of file LockAnalysis.h.

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

◆ hasSpanfromCxtLock()

bool SVF::LockAnalysis::hasSpanfromCxtLock ( const CxtLock & cl )

inline

Definition at line 256 of file LockAnalysis.h.

    {
        return cxtLocktoSpan.find(cl) != cxtLocktoSpan.end();
    }

◆ intersect()

bool SVF::LockAnalysis::intersect	(	CxtLockSet &	tgrlockset,
		const CxtLockSet &	srclockset
	)

inlineprivate

Definition at line 373 of file LockAnalysis.h.

    {
        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();
    }

◆ intersects()

bool SVF::LockAnalysis::intersects	(	const CxtLockSet &	lockset1,
		const CxtLockSet &	lockset2
	)		const

inline

Return true if the intersection of two locksets is not empty.

Definition at line 163 of file LockAnalysis.h.

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

◆ intraBackwardTraverse()

bool LockAnalysis::intraBackwardTraverse	(	const InstSet &	unlockSet,
		InstSet &	backwardInsts
	)

Intra-procedural backward traversal

Definition at line 217 of file LockAnalysis.cpp.

{
 
    InstVec worklist;
    for(InstSet::const_iterator it = unlockSet.begin(), eit = unlockSet.end(); it!=eit; ++it)
    {
        const ICFGNode* unlockSite = *it;
        const ICFGNode* entryInst = unlockSite->getFun()->getEntryBlock()->back();
        worklist.push_back(*it);
 
        while (!worklist.empty())
        {
            const ICFGNode *I = worklist.back();
            worklist.pop_back();
 
            if(entryInst == I)
                return false;
 
            // Skip the visited Instructions.
            if (backwardInsts.find(I)!=backwardInsts.end())
                continue;
            backwardInsts.insert(I);
 
            if (isTDAcquire(I) && isAliasedLocks(unlockSite, I))
            {
                DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << I->getSourceLoc()<<"\n");
                DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << unlockSite->getSourceLoc()<<"\n");
                continue;
            }
 
            for(const ICFGEdge* inEdge : I->getInEdges())
            {
                if(inEdge->getSrcNode()->getFun() == I->getFun())
                {
                    worklist.push_back(inEdge->getSrcNode());
                }
            }
        }
    }
 
    return true;
}

◆ intraForwardTraverse()

bool LockAnalysis::intraForwardTraverse	(	const ICFGNode *	lockSite,
		InstSet &	unlockSet,
		InstSet &	forwardInsts
	)

Intra-procedural forward traversal

Definition at line 173 of file LockAnalysis.cpp.

{
 
    const FunObjVar* svfFun = lockSite->getFun();
 
    InstVec worklist;
    worklist.push_back(lockSite);
    while (!worklist.empty())
    {
        const ICFGNode *I = worklist.back();
        worklist.pop_back();
        const ICFGNode* exitInst = svfFun->getExitBB()->back();
        if(exitInst == I)
            return false;
 
        // Skip the visited Instructions.
        if (forwardInsts.find(I)!=forwardInsts.end())
            continue;
        forwardInsts.insert(I);
 
        if (isTDRelease(I) && isAliasedLocks(lockSite, I))
        {
            unlockSet.insert(I);
            DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << lockSite->getSourceLoc()<<"\n");
            DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << I->getSourceLoc()<<"\n");
            continue;
        }
 
        for(const ICFGEdge* outEdge : I->getOutEdges())
        {
            if(outEdge->getDstNode()->getFun() == I->getFun())
            {
                worklist.push_back(outEdge->getDstNode());
            }
        }
    }
 
    return true;
}

◆ isAliasedLocks() [1/2]

bool SVF::LockAnalysis::isAliasedLocks	(	const CxtLock &	cl1,
		const CxtLock &	cl2
	)

inlineprivate

Return true it a lock matches an unlock.

Definition at line 343 of file LockAnalysis.h.

    {
        return isAliasedLocks(cl1.getStmt(), cl2.getStmt());
    }

◆ isAliasedLocks() [2/2]

bool SVF::LockAnalysis::isAliasedLocks	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

inlineprivate

todo: must alias

Definition at line 347 of file LockAnalysis.h.

    {
        return tct->getPTA()->alias(getLockVal(i1)->getId(), getLockVal(i2)->getId());
    }

◆ isCallSite()

bool SVF::LockAnalysis::isCallSite ( const ICFGNode * inst )

inlineprivate

Whether it is a callsite.

Definition at line 462 of file LockAnalysis.h.

    {
        return tct->isCallSite(inst);
    }

◆ isContextSuffix()

bool LockAnalysis::isContextSuffix	(	const CallStrCxt &	lhs,
		const CallStrCxt &	call
	)

private

If lhs is a suffix of rhs, including equal.

Definition at line 571 of file LockAnalysis.cpp.

{
    return tct->isContextSuffix(lhs,call);
}

◆ isExtCall()

bool SVF::LockAnalysis::isExtCall ( const ICFGNode * inst )

inlineprivate

Whether it is calling an external function.

Definition at line 467 of file LockAnalysis.h.

    {
        return tct->isExtCall(inst);
    }

◆ isInSameCISpan()

bool LockAnalysis::isInSameCISpan	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)		const

Return true if two instructions are inside same context-insensitive lock span

Definition at line 673 of file LockAnalysis.cpp.

{
    if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
    {
        const InstSet& lockset1 = getIntraLockSet(i1);
        const InstSet& lockset2 = getIntraLockSet(i2);
        for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
        {
            for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
            {
                if (*cil1==*cil2)
                    return true;
            }
        }
    }
    return false;
}

◆ isInSameCSSpan() [1/2]

bool LockAnalysis::isInSameCSSpan	(	const CxtStmt &	cxtStmt1,
		const CxtStmt &	cxtStmt2
	)		const

Return true if two context-sensitive instructions are inside same context-insensitive lock spa

Definition at line 694 of file LockAnalysis.cpp.

{
    if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
        return true;
    const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
    const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
    return intersects(lockset1,lockset2);
}

◆ isInSameCSSpan() [2/2]

bool LockAnalysis::isInSameCSSpan	(	const ICFGNode *	I1,
		const ICFGNode *	I2
	)		const

Return true if two instructions are inside at least one common context-sensitive lock span

Definition at line 705 of file LockAnalysis.cpp.

{
    if(!hasCxtStmtFromInst(I1) || !hasCxtStmtFromInst(I2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(I1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(I2);
 
    for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
    {
        const CxtStmt& cxtStmt1 = *cts1;
        for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
        {
            const CxtStmt& cxtStmt2 = *cts2;
            if(cxtStmt1==cxtStmt2) continue;
            if(isInSameCSSpan(cxtStmt1,cxtStmt2)==false)
                return false;
        }
    }
    return true;
}

◆ isInSameSpan()

bool LockAnalysis::isInSameSpan	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Return true if two instructions are inside at least one common lock span

Definition at line 655 of file LockAnalysis.cpp.

{
    DOTIMESTAT(double queryStart = PTAStat::getClk(true));
 
    bool sameSpan = false;
    if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
        sameSpan = isInSameCISpan(i1, i2);
    else
        sameSpan = isInSameCSSpan(i1, i2);
 
    DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
    return sameSpan;
}

◆ isInsideCondIntraLock()

bool SVF::LockAnalysis::isInsideCondIntraLock ( const ICFGNode * stmt ) const

inline

Return true if a statement is inside a partial lock/unlock pair (conditional lock with unconditional unlock)

Definition at line 133 of file LockAnalysis.h.

    {
        return instTocondCILocksMap.find(stmt)!=instTocondCILocksMap.end();
    }

◆ isInsideIntraLock()

bool SVF::LockAnalysis::isInsideIntraLock ( const ICFGNode * stmt ) const

inline

Return true if a statement is inside an intra-procedural lock.

Definition at line 127 of file LockAnalysis.h.

    {
        return instCILocksMap.find(stmt)!=instCILocksMap.end() || isInsideCondIntraLock(stmt);
    }

◆ isIntraLock()

bool SVF::LockAnalysis::isIntraLock ( const ICFGNode * lock ) const

inline

Intraprocedural locks.

Return true if the lock is an intra-procedural lock

Definition at line 101 of file LockAnalysis.h.

    {
        assert(locksites.find(lock)!=locksites.end() && "not a lock site?");
        return ciLocktoSpan.find(lock)!=ciLocktoSpan.end();
    }

◆ isLockCandidateFun()

bool SVF::LockAnalysis::isLockCandidateFun ( const FunObjVar * fun ) const

inline

Return true if it is a candidate function.

Definition at line 193 of file LockAnalysis.h.

    {
        return lockcandidateFuncSet.find(fun)!=lockcandidateFuncSet.end();
    }

◆ isProtectedByCommonCILock()

bool LockAnalysis::isProtectedByCommonCILock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Protected by at least one common context-insensitive lock

Definition at line 597 of file LockAnalysis.cpp.

{
 
    if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
    {
        const InstSet& lockset1 = getIntraLockSet(i1);
        const InstSet& lockset2 = getIntraLockSet(i2);
        for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
        {
            for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
            {
                if (isAliasedLocks(*cil1, *cil2))
                    return true;
            }
        }
    }
    return false;
}

◆ isProtectedByCommonCxtLock() [1/2]

bool LockAnalysis::isProtectedByCommonCxtLock	(	const CxtStmt &	cxtStmt1,
		const CxtStmt &	cxtStmt2
	)

Protected by at least one common context-sensitive lock

Definition at line 619 of file LockAnalysis.cpp.

{
    if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
        return true;
    const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
    const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
    return alias(lockset1,lockset2);
}

◆ isProtectedByCommonCxtLock() [2/2]

bool LockAnalysis::isProtectedByCommonCxtLock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Protected by at least one common context-sensitive lock under each context

Definition at line 631 of file LockAnalysis.cpp.

{
    if(!hasCxtStmtFromInst(i1) || !hasCxtStmtFromInst(i2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(i1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(i2);
    for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
    {
        const CxtStmt& cxtStmt1 = *cts1;
        for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
        {
            const CxtStmt& cxtStmt2 = *cts2;
            if(cxtStmt1==cxtStmt2) continue;
            if(isProtectedByCommonCxtLock(cxtStmt1,cxtStmt2)==false)
                return false;
        }
    }
    return true;
}

◆ isProtectedByCommonLock()

bool LockAnalysis::isProtectedByCommonLock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Check if two Instructions are protected by common locks echo inst may have multiple cxt stmt we check whether every cxt stmt of instructions is protected by a common lock.

Protected by at least one common lock under every context

Definition at line 580 of file LockAnalysis.cpp.

{
    numOfTotalQueries++;
    bool commonlock = false;
    DOTIMESTAT(double queryStart = PTAStat::getClk(true));
    if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
        commonlock = isProtectedByCommonCILock(i1,i2) ;
    else
        commonlock = isProtectedByCommonCxtLock(i1,i2);
    DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
    return commonlock;
}

◆ isTDAcquire()

bool SVF::LockAnalysis::isTDAcquire ( const ICFGNode * call )

inlineprivate

Whether it is a lock site.

Definition at line 448 of file LockAnalysis.h.

    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDAcquire(SVFUtil::cast<CallICFGNode>(call));
    }

◆ isTDFork()

bool SVF::LockAnalysis::isTDFork ( const ICFGNode * call )

inlineprivate

Whether it is a lock site.

Definition at line 441 of file LockAnalysis.h.

    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDFork(SVFUtil::cast<CallICFGNode>(call));
    }

◆ isTDRelease()

bool SVF::LockAnalysis::isTDRelease ( const ICFGNode * call )

inlineprivate

Whether it is a unlock site.

Definition at line 455 of file LockAnalysis.h.

    {
        if(SVFUtil::isa<CallICFGNode>(call) == false)
            return false;
        return getTCG()->getThreadAPI()->isTDRelease(SVFUtil::cast<CallICFGNode>(call));
    }

◆ isVisitedCTPs()

bool SVF::LockAnalysis::isVisitedCTPs ( const CxtLockProc & clp ) const

inlineprivate

Definition at line 411 of file LockAnalysis.h.

    {
        return visitedCTPs.find(clp) != visitedCTPs.end();
    }

◆ markCxtStmtFlag()

void SVF::LockAnalysis::markCxtStmtFlag	(	const CxtStmt &	tgr,
		const CxtStmt &	src
	)

inlineprivate

Mark thread flags for cxtStmt.

Transfer function for marking context-sensitive statement

Definition at line 356 of file LockAnalysis.h.

    {
        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);
        }
    }

◆ matchCxt()

bool LockAnalysis::matchCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const FunObjVar *	callee
	)

private

Match context.

partial match

Definition at line 547 of file LockAnalysis.cpp.

{
    const FunObjVar* svfcaller = call->getFun();
    CallSiteID csId = getTCG()->getCallSiteID(call, callee);
 
//    /// handle calling context for candidate functions only
//    if (isLockCandidateFun(caller) == false)
//        return true;
 
    if (cxt.empty())
        return true;
 
    if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) == false)
    {
        if (cxt.back() == csId)
            cxt.pop_back();
        else
            return false;
        DBOUT(DMTA, tct->dumpCxt(cxt));
    }
    return true;
}

◆ popFromCTPWorkList()

CxtLockProc SVF::LockAnalysis::popFromCTPWorkList ( )

inlineprivate

Definition at line 406 of file LockAnalysis.h.

    {
        CxtLockProc clp = clpList.pop();
        return clp;
    }

◆ popFromCTSWorkList()

CxtStmt SVF::LockAnalysis::popFromCTSWorkList ( )

inlineprivate

Definition at line 423 of file LockAnalysis.h.

    {
        CxtStmt clp = cxtStmtList.pop();
        return clp;
    }

◆ printLocks()

void LockAnalysis::printLocks ( const CxtStmt & cts )

Print locks and spans.

Print context-insensitive and context-sensitive locks

Definition at line 396 of file LockAnalysis.cpp.

{
    const CxtLockSet & lockset = getCxtLockfromCxtStmt(cts);
    outs() << "\nlock sets size = " << lockset.size() << "\n";
    for (CxtLockSet::const_iterator it = lockset.begin(), eit = lockset.end(); it != eit; ++it)
    {
        (*it).dump();
    }
}

◆ pushCxt()

void LockAnalysis::pushCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const FunObjVar *	callee
	)

private

Context helper functions.

Push calling context

Definition at line 542 of file LockAnalysis.cpp.

{
    tct->pushCxt(cxt,call,callee);
}

◆ pushToCTPWorkList()

bool SVF::LockAnalysis::pushToCTPWorkList ( const CxtLockProc & clp )

inlineprivate

WorkList helper functions.

Definition at line 397 of file LockAnalysis.h.

    {
        if (isVisitedCTPs(clp) == false)
        {
            visitedCTPs.insert(clp);
            return clpList.push(clp);
        }
        return false;
    }

◆ pushToCTSWorkList()

bool SVF::LockAnalysis::pushToCTSWorkList ( const CxtStmt & cs )

inlineprivate

Worklist operations.

Definition at line 419 of file LockAnalysis.h.

    {
        return cxtStmtList.push(cs);
    }

◆ removeCxtStmtToSpan()

bool SVF::LockAnalysis::removeCxtStmtToSpan	(	CxtStmt &	cts,
		const CxtLock &	cl
	)

inline

Add context-sensitive statement.

Definition at line 236 of file LockAnalysis.h.

    {
        bool find = cxtStmtToCxtLockSet[cts].find(cl)!=cxtStmtToCxtLockSet[cts].end();
        if(find)
        {
            cxtStmtToCxtLockSet[cts].erase(cl);
            cxtLocktoSpan[cl].erase(cts);
        }
        return find;
    }

◆ touchCxtStmt()

void SVF::LockAnalysis::touchCxtStmt ( CxtStmt & cts )

inline

Touch this context statement.

Definition at line 252 of file LockAnalysis.h.

    {
        cxtStmtToCxtLockSet[cts];
    }

Member Data Documentation

◆ ciLocktoSpan

CILockToSpan SVF::LockAnalysis::ciLocktoSpan

private

Used for context-insensitive intra-procedural locks.

Definition at line 521 of file LockAnalysis.h.

◆ clpList

CxtLockProcVec SVF::LockAnalysis::clpList

private

Following data structures are used for collecting context-sensitive locks.

Definition at line 504 of file LockAnalysis.h.

◆ cxtLockset

CxtLockSet SVF::LockAnalysis::cxtLockset

private

Context-sensitive locks.

Definition at line 493 of file LockAnalysis.h.

◆ cxtLocktoSpan

CxtLockToSpan SVF::LockAnalysis::cxtLocktoSpan

private

Map a context-sensitive lock to its lock span statements Map a context-sensitive statement to its context-sensitive lock

Definition at line 498 of file LockAnalysis.h.

◆ cxtStmtList

CxtStmtWorkList SVF::LockAnalysis::cxtStmtList

private

context-sensitive statement worklist

Definition at line 486 of file LockAnalysis.h.

◆ cxtStmtToCxtLockSet

CxtStmtToCxtLockSet SVF::LockAnalysis::cxtStmtToCxtLockSet

private

Definition at line 499 of file LockAnalysis.h.

◆ instCILocksMap

InstToInstSetMap SVF::LockAnalysis::instCILocksMap

private

Definition at line 522 of file LockAnalysis.h.

◆ instTocondCILocksMap

InstToInstSetMap SVF::LockAnalysis::instTocondCILocksMap

private

Definition at line 523 of file LockAnalysis.h.

◆ instToCxtStmtSet

InstToCxtStmtSet SVF::LockAnalysis::instToCxtStmtSet

private

Map a statement to all its context-sensitive statements.

Definition at line 489 of file LockAnalysis.h.

◆ lockcandidateFuncSet

FunSet SVF::LockAnalysis::lockcandidateFuncSet

private

Candidate functions which relevant to locks/unlocks.

Definition at line 516 of file LockAnalysis.h.

◆ lockQueriesTime

double SVF::LockAnalysis::lockQueriesTime

Definition at line 531 of file LockAnalysis.h.

◆ locksites

InstSet SVF::LockAnalysis::locksites

private

Record all visited clps.

Collecting lock/unlock sites

Definition at line 510 of file LockAnalysis.h.

◆ lockTime

double SVF::LockAnalysis::lockTime

Definition at line 528 of file LockAnalysis.h.

◆ numOfLockedQueries

u32_t SVF::LockAnalysis::numOfLockedQueries

Definition at line 530 of file LockAnalysis.h.

◆ numOfTotalQueries

u32_t SVF::LockAnalysis::numOfTotalQueries

Definition at line 529 of file LockAnalysis.h.

◆ tct

TCT* SVF::LockAnalysis::tct

private

TCT.

Definition at line 483 of file LockAnalysis.h.

◆ unlocksites

InstSet SVF::LockAnalysis::unlocksites

private

Definition at line 511 of file LockAnalysis.h.

◆ visitedCTPs

CxtLockProcSet SVF::LockAnalysis::visitedCTPs

private

CxtLockProc List.

Definition at line 505 of file LockAnalysis.h.

The documentation for this class was generated from the following files:

/home/runner/work/SVF/SVF/svf/include/MTA/LockAnalysis.h
/home/runner/work/SVF/SVF/svf/lib/MTA/LockAnalysis.cpp

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CILockToSpan

◆ CISpan

◆ CxtLock

◆ CxtLockProc

◆ CxtLockProcSet

◆ CxtLockProcVec

◆ CxtLockSet

◆ CxtLockToLockSet

◆ CxtLockToSpan

◆ CxtStmtSet

◆ CxtStmtToCxtLockSet

◆ CxtStmtToLockFlagMap

◆ CxtStmtWorkList

◆ FunSet

◆ InstSet

◆ InstToCxtStmtSet

◆ InstToInstSetMap

◆ InstVec

◆ LockSet

◆ LockSiteToLockSet

◆ LockSpan

Member Enumeration Documentation

◆ ValDomain

Constructor & Destructor Documentation

◆ LockAnalysis()

Member Function Documentation

◆ addCondIntraLock()

◆ addCxtLock()

◆ addCxtStmtToSpan()

◆ addIntraLock()

◆ alias()

◆ analyze()

◆ analyzeIntraProcedualLock()

◆ analyzeLockSpanCxtStmt()

◆ buildCandidateFuncSetforLock()

◆ clearFlagMap()

◆ collectCxtLock()

◆ collectLockUnlocksites()

◆ getCSTCLS()

◆ getCxtLockfromCxtStmt() [1/2]

◆ getCxtLockfromCxtStmt() [2/2]

◆ getCxtStmtsFromInst()

◆ getIntraLockSet()

◆ getLockVal()

◆ getNumOfCxtLocks()

◆ getSpanfromCxtLock()

◆ getTCG()

◆ getTCT()

◆ handleCall()

◆ handleCallRelation()

◆ handleFork()

◆ handleIntra()

◆ handleRet()

◆ hasAllCxtInLockSpan()

◆ hasCxtLock()

◆ hasCxtLockfromCxtStmt()

◆ hasCxtStmtFromInst()

◆ hasOneCxtInLockSpan()

◆ hasSpanfromCxtLock()

◆ intersect()

◆ intersects()

◆ intraBackwardTraverse()

◆ intraForwardTraverse()

◆ isAliasedLocks() [1/2]

◆ isAliasedLocks() [2/2]

◆ isCallSite()

◆ isContextSuffix()

◆ isExtCall()

◆ isInSameCISpan()

◆ isInSameCSSpan() [1/2]

◆ isInSameCSSpan() [2/2]

◆ isInSameSpan()

◆ isInsideCondIntraLock()