SVF::MTA Class Reference

#include <MTA.h>

Classes
struct	RaceOccurrence
	One occurrence of a memory access under one thread instance. More...
struct	RacePair
	A race pair: two statements that may race. More...

Public Member Functions
	MTA ()
	Constructor.
virtual	~MTA ()
	Destructor.
virtual bool	runOnModule (SVFIR *module)
	We start the pass here.
virtual MHP *	computeMHP (TCT *tct)
	Compute MHP.
virtual LockAnalysis *	computeLocksets (TCT *tct)
	Compute locksets.
virtual void	reportRaces ()
	Run the shared detector and print a race report.
MHP *	getMHP ()
LockAnalysis *	getLockAnalysis ()

Static Public Member Functions
static std::set< const SVFStmt * >	detectRace (SVFIR *svfIr, AndersenBase *pta, MHP *mhp, LockAnalysis *lockAnalysis, CallGraph *callGraph, std::set< RacePair > &outRacePairs)
static PointsTo	getGlobalObjectVariables (SVFIR *svfIr)
	Escape/points-to helpers for the shared detector.
static PointsTo	getPointsToClosure (AndersenBase *pta, const PointsTo &pts)
static bool	hasThreadFunctions (CallGraph *callGraph)

Static Private Member Functions
static bool	occurrencesRace (MHP *mhp, const RaceOccurrence &first, const RaceOccurrence &second)
	Helpers for the equivalence-class race detector.
static void	commitRacePair (std::set< RacePair > &out, const RaceOccurrence &first, const RaceOccurrence &second)

Private Attributes
ThreadCallGraph *	tcg
std::unique_ptr< TCT >	tct
std::unique_ptr< MTAStat >	stat
MHP *	mhp
LockAnalysis *	lsa

Detailed Description

Base data race detector

Definition at line 85 of file MTA.h.

Constructor & Destructor Documentation

MTA()

MTA::MTA

(

)

Constructor.

Definition at line 58 of file MTA.cpp.

         : tcg(nullptr), tct(nullptr), mhp(nullptr), lsa(nullptr)
{
    stat = std::make_unique<MTAStat>();
}

~MTA()

MTA::~MTA ( )

virtual

Destructor.

Definition at line 63 of file MTA.cpp.

{
    if (tcg)
        delete tcg;
 
    delete mhp;
    delete lsa;
}

Member Function Documentation

commitRacePair()

void MTA::commitRacePair ( std::set< RacePair > &  out, const RaceOccurrence &  first, const RaceOccurrence &  second  )

staticprivate

Definition at line 210 of file MTA.cpp.

{
    const SVFStmt* stmt1 = first.stmt;
    const SVFStmt* stmt2 = second.stmt;
    if (stmt2 < stmt1) std::swap(stmt1, stmt2);
    out.insert(RacePair(stmt1, stmt2));
}

computeLocksets()

LockAnalysis * MTA::computeLocksets ( TCT *  tct )

virtual

Compute locksets.

Compute lock sets

Definition at line 114 of file MTA.cpp.

{
    LockAnalysis* lsa = new LockAnalysis(tct);
    lsa->analyze(PAG::getPAG()->getICFG(), const_cast<CallGraph*>(PAG::getPAG()->getCallGraph()));
    return lsa;
}

computeMHP()

MHP * MTA::computeMHP ( TCT *  tct )

virtual

Compute MHP.

Definition at line 121 of file MTA.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("MHP analysis\n"));
    DBOUT(DMTA, outs() << pasMsg("MHP analysis\n"));
 
    DOTIMESTAT(double mhpStart = stat->getClk());
    MHP* mhp = new MHP(tct);
    mhp->analyze(PAG::getPAG()->getICFG(), const_cast<CallGraph*>(PAG::getPAG()->getCallGraph()));
    DOTIMESTAT(double mhpEnd = stat->getClk());
    DOTIMESTAT(stat->MHPTime += (mhpEnd - mhpStart) / TIMEINTERVAL);
 
    DBOUT(DGENERAL, outs() << pasMsg("MHP analysis finish\n"));
    DBOUT(DMTA, outs() << pasMsg("MHP analysis finish\n"));
    return mhp;
}

detectRace()

std::set< const SVFStmt * > MTA::detectRace ( SVFIR *  svfIr, AndersenBase *  pta, MHP *  mhp, LockAnalysis *  lockAnalysis, CallGraph *  callGraph, std::set< RacePair > &  outRacePairs  )

static

Shared equivalence-class race detector (used by both MTA::reportRaces and the SlicedMTA pipeline). Returns the racy statements and fills outRacePairs.

Definition at line 221 of file MTA.cpp.

{
 
    std::set<const SVFStmt*> bugStmts;
 
    // Escape set: objects shared across threads. Seed from globals + the actual
    // argument at each fork site (the spawner's value, which a spawnee-formal
    // closure can miss), then take the transitive points-to closure.
    PointsTo seed = getGlobalObjectVariables(svfIr);
    if (ThreadCallGraph* tcg = SVFUtil::dyn_cast<ThreadCallGraph>(callGraph))
    {
        const ThreadAPI* tapi = tcg->getThreadAPI();
        for (auto it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
            if (const CallICFGNode* cs = SVFUtil::dyn_cast<CallICFGNode>(*it))
                if (const ValVar* actual = tapi->getActualParmAtForkSite(cs))
                    seed |= pta->getPts(actual->getId());
    }
    const PointsTo escSet = getPointsToClosure(pta, seed);
 
    // One occurrence per (statement, thread instance), indexed by object (C1 ->
    // "same bucket") as collected, so the points-to set is consumed straight into
    // the buckets and never stored per occurrence.
    std::vector<RaceOccurrence> occurrences;
    Map<NodeID, std::vector<size_t>> objectToOccurrences;
    for (const auto& item : *callGraph)
    {
        const FunObjVar* fun = item.second->getFunction();
        if (!fun || !fun->hasBasicBlock()) continue;
        for (auto bbIt : *fun)
            for (const ICFGNode* node : bbIt.second->getICFGNodeList())
            {
                if (!mhp->hasThreadStmtSet(node)) continue;          // screen 1: concurrent?
                for (const SVFStmt* stmt : svfIr->getSVFStmtList(node))
                {
                    NodeID accessedPtr;
                    bool isStore;
                    if (const LoadStmt* load = SVFUtil::dyn_cast<LoadStmt>(stmt))
                    {
                        accessedPtr = load->getRHSVarID();
                        isStore = false;
                    }
                    else if (const StoreStmt* store = SVFUtil::dyn_cast<StoreStmt>(stmt))
                    {
                        accessedPtr = store->getLHSVarID();
                        isStore = true;
                    }
                    else continue;
                    PointsTo objects = pta->getPts(accessedPtr);
                    objects &= escSet;                               // screen 2: touches shared object?
                    if (objects.empty()) continue;
                    bool locked = lockAnalysis->isProtectedByCommonLock(node, node);
                    const size_t firstNew = occurrences.size();
                    for (const CxtThreadStmt& threadStmt : mhp->getThreadStmtSet(node))
                        occurrences.push_back({stmt, node, isStore, threadStmt.getTid(),
                                               mhp->getInterleavingThreads(threadStmt), locked});
                    for (NodeID object : objects)
                        for (size_t k = firstNew; k < occurrences.size(); ++k)
                            objectToOccurrences[object].push_back(k);
                }
            }
    }
 
    // Within each object, occurrences sharing the race predicate's inputs (tid,
    // interleaving, isStore, lock sig) race the same partners, so collapse into a
    // class and judge C2/C3/C4 once per class pair -- O(classes^2) not O(occ^2).
    for (const auto& objectAndOccs : objectToOccurrences)
    {
        struct RaceClass
        {
            bool isStore, locked;
            size_t rep;
            std::vector<size_t> members;
        };
        struct RaceKey
        {
            NodeID tid;
            bool isStore;
            NodeBS interleav;
            const ICFGNode* lockNode;
 
            bool operator<(const RaceKey& other) const
            {
                if (tid != other.tid)
                    return tid < other.tid;
                if (isStore != other.isStore)
                    return isStore < other.isStore;
                if (SVFUtil::cmpNodeBS(interleav, other.interleav))
                    return true;
                if (SVFUtil::cmpNodeBS(other.interleav, interleav))
                    return false;
                return lockNode < other.lockNode;
            }
        };
        std::vector<RaceClass> classes;
        OrderedMap<RaceKey, size_t> keyToClass;
        for (size_t occIdx : objectAndOccs.second)
        {
            const RaceOccurrence& occ = occurrences[occIdx];
            RaceKey key{occ.tid, occ.isStore, occ.interleav, occ.locked ? occ.node : nullptr};
            auto found = keyToClass.find(key);
            if (found == keyToClass.end())
            {
                keyToClass[key] = classes.size();
                classes.push_back({occ.isStore, occ.locked, occIdx, {occIdx}});
            }
            else
                classes[found->second].members.push_back(occIdx);
        }
        for (size_t firstIdx = 0; firstIdx < classes.size(); ++firstIdx)
            for (size_t secondIdx = firstIdx; secondIdx < classes.size(); ++secondIdx)
            {
                RaceClass& firstClass = classes[firstIdx];
                RaceClass& secondClass = classes[secondIdx];
                if (!firstClass.isStore && !secondClass.isStore) continue;   // C2: >=1 write
                const RaceOccurrence& firstRep = occurrences[firstClass.rep];
                const RaceOccurrence& secondRep = occurrences[secondClass.rep];
                if (!occurrencesRace(mhp, firstRep, secondRep)) continue;    // C3
                // C4 + emit. Lock relation is uniform per class (the reps decide it),
                // so emit a statement-COVERING set -- every racy member as an endpoint.
                if (firstIdx != secondIdx)
                {
                    if (firstClass.locked && secondClass.locked &&
                            lockAnalysis->isProtectedByCommonLock(firstRep.node, secondRep.node))
                        continue;
                    for (size_t memberIdx : firstClass.members)
                        commitRacePair(outRacePairs, occurrences[memberIdx],
                                       occurrences[secondClass.members[0]]);
                    for (size_t memberIdx : secondClass.members)
                        commitRacePair(outRacePairs, occurrences[firstClass.members[0]],
                                       occurrences[memberIdx]);
                }
                else
                {
                    const std::vector<size_t>& members = firstClass.members;
                    // Multiforked self-race: every member self-races a concurrent
                    // instance of itself, independent of any cross-race below.
                    for (size_t memberIdx : members)
                        if (!firstClass.locked ||
                                !lockAnalysis->isProtectedByCommonLock(occurrences[memberIdx].node,
                                        occurrences[memberIdx].node))
                            commitRacePair(outRacePairs, occurrences[memberIdx], occurrences[memberIdx]);
                    // Cross-race needs >=2 members: two distinct occurrences to pair.
                    if (members.size() >= 2 &&
                            (!firstClass.locked ||
                             !lockAnalysis->isProtectedByCommonLock(occurrences[members[0]].node,
                                     occurrences[members[1]].node)))
                        for (size_t pos = 0; pos < members.size(); ++pos)
                            commitRacePair(outRacePairs, occurrences[members[pos]],
                                           occurrences[members[pos == 0 ? 1 : 0]]);
                }
            }
    }
 
    for (const RacePair& r : outRacePairs)
    {
        bugStmts.insert(r.stmt1);
        bugStmts.insert(r.stmt2);
    }
    return bugStmts;
}

getGlobalObjectVariables()

PointsTo MTA::getGlobalObjectVariables ( SVFIR *  svfIr )

static

Escape/points-to helpers for the shared detector.

Definition at line 138 of file MTA.cpp.

{
    PointsTo globalObjVars;
    const ICFGNode* globalICFGNode = svfIr->getICFG()->getGlobalICFGNode();
 
    for (const SVFStmt* stmt : globalICFGNode->getSVFStmts())
    {
        const AddrStmt* addrStmt = SVFUtil::dyn_cast<AddrStmt>(stmt);
        if (addrStmt != nullptr)
        {
            const GlobalValVar* globalVar = SVFUtil::dyn_cast<GlobalValVar>(addrStmt->getLHSVar());
            if (globalVar != nullptr)
            {
                globalObjVars.set(addrStmt->getRHSVarID());
            }
        }
    }
 
    return globalObjVars;
}

getLockAnalysis()

LockAnalysis * SVF::MTA::getLockAnalysis ( )

inline

Definition at line 113 of file MTA.h.

    {
        return lsa;
    }

getMHP()

MHP * SVF::MTA::getMHP ( )

inline

Definition at line 108 of file MTA.h.

    {
        return mhp;
    }

getPointsToClosure()

PointsTo MTA::getPointsToClosure ( AndersenBase *  pta, const PointsTo &  pts  )

static

Definition at line 166 of file MTA.cpp.

{
    SVFIR* pag = pta->getPAG();
    PointsTo ptsClosure = pts;
    std::deque<NodeID> worklist;
    for (NodeID pt : pts)
    {
        worklist.push_back(pt);
    }
 
    while (!worklist.empty())
    {
        NodeID obj = worklist.front();
        worklist.pop_front();
 
        for (NodeID target : pta->getPts(obj))           // points-to
            if (!ptsClosure.test(target))
            {
                ptsClosure.set(target);
                worklist.push_back(target);
            }
 
        if (pag->getBaseObject(obj) != nullptr)          // containment (object nodes only)
            for (NodeID field : pta->getAllFieldsObjVars(pta->getBaseObjVarID(obj)))
                if (!ptsClosure.test(field))
                {
                    ptsClosure.set(field);
                    worklist.push_back(field);
                }
    }
 
    return ptsClosure;
}

hasThreadFunctions()

bool MTA::hasThreadFunctions ( CallGraph *  callGraph )

static

Whether the program has any thread (fork-target) function reachable via a fork edge.

Definition at line 1039 of file MTA.cpp.

{
    for (CallGraph::iterator it = callGraph->begin(), eit = callGraph->end(); it != eit; ++it)
    {
        const CallGraphNode* node = it->second;
        for (const CallGraphEdge* edge : node->getOutEdges())
        {
            if (edge->getEdgeKind() == CallGraphEdge::TDForkEdge &&
                    edge->getDstNode()->getFunction() != nullptr)
            {
                return true;
            }
        }
    }
    return false;
}

occurrencesRace()

bool MTA::occurrencesRace ( MHP *  mhp, const RaceOccurrence &  first, const RaceOccurrence &  second  )

staticprivate

Helpers for the equivalence-class race detector.

Definition at line 202 of file MTA.cpp.

{
    if (first.tid != second.tid)
        return first.interleav.test(second.tid) && second.interleav.test(first.tid);
    return mhp->getTCT()->getTCTNode(first.tid)->isMultiforked();
}

reportRaces()

void MTA::reportRaces ( )

virtual

Run the shared detector and print a race report.

Definition at line 385 of file MTA.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("Starting Race Detection\n"));
 
    SVFIR* pag = SVFIR::getPAG();
    AndersenBase* pta = AndersenWaveDiff::createAndersenWaveDiff(pag);
    CallGraph* callGraph = pta->getCallGraph();
 
    // Shared equivalence-class detector (the same one the slicing pipeline uses),
    // run over the Andersen pre-analysis with this MTA's MHP/lock results.
    std::set<RacePair> racePairs;
    detectRace(pag, pta, mhp, lsa, callGraph, racePairs);
 
    for (const RacePair& rp : racePairs)
        outs() << SVFUtil::bugMsg1("race pair(") << " stmt1: " << rp.stmt1->toString()
               << ", stmt2: " << rp.stmt2->toString() << SVFUtil::bugMsg1(")") << "\n";
}

runOnModule()

bool MTA::runOnModule ( SVFIR *  pag )

virtual

We start the pass here.

Perform data race detection

Definition at line 75 of file MTA.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("MTA analysis\n"));
    DBOUT(DMTA, outs() << pasMsg("MTA analysis\n"));
 
    PointerAnalysis* pta = AndersenWaveDiff::createAndersenWaveDiff(pag);
    if (Options::DumpMTAGraphs())
        pta->getCallGraph()->dump("ptacg");
    pag->getICFG()->updateCallGraph(pta->getCallGraph());
 
    DBOUT(DGENERAL, outs() << pasMsg("Build TCT\n"));
    DBOUT(DMTA, outs() << pasMsg("Build TCT\n"));
    DOTIMESTAT(double tctStart = stat->getClk());
    tct = std::make_unique<TCT>(pta);
    tcg = tct->getThreadCallGraph();
    DOTIMESTAT(double tctEnd = stat->getClk());
    DOTIMESTAT(stat->TCTTime += (tctEnd - tctStart) / TIMEINTERVAL);
 
    if (pta->printStat())
    {
        stat->performThreadCallGraphStat(tcg);
        stat->performTCTStat(tct.get());
    }
 
    if (Options::DumpMTAGraphs())
        tcg->dump("tcg");
 
    mhp = computeMHP(tct.get());
    lsa = computeLocksets(tct.get());
 
    // MTA's only client is race detection; always report.
    reportRaces();
 
    return false;
}

Member Data Documentation

lsa

LockAnalysis* SVF::MTA::lsa

private

Definition at line 168 of file MTA.h.

mhp

MHP* SVF::MTA::mhp

private

Definition at line 167 of file MTA.h.

stat

std::unique_ptr<MTAStat> SVF::MTA::stat

private

Definition at line 166 of file MTA.h.

tcg

ThreadCallGraph* SVF::MTA::tcg

private

Definition at line 164 of file MTA.h.

tct

std::unique_ptr<TCT> SVF::MTA::tct

private

Definition at line 165 of file MTA.h.

---

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

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