SVF::MTA Class Reference

#include <MTA.h>

Classes
struct	RaceClass
struct	RaceClassKey
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)

Private Types
using	ObjectToRaceOccurrences = Map< NodeID, std::vector< size_t > >

Static Private Member Functions
static void	collectRaceOccurrences (SVFIR *svfir, AndersenBase *pta, MHP *mhp, LockAnalysis *lockAnalysis, CallGraph *callGraph, const PointsTo &escapedObjects, std::vector< RaceOccurrence > &occurrences, ObjectToRaceOccurrences &objectToOccurrences)
	Helpers for the equivalence-class race detector.
static std::vector< RaceClass >	buildRaceClasses (const std::vector< RaceOccurrence > &occurrences, const std::vector< size_t > &occurrenceIndices)
static void	emitRacePairs (MHP *mhp, LockAnalysis *lockAnalysis, const std::vector< RaceOccurrence > &occurrences, const std::vector< RaceClass > &classes, std::set< RacePair > &outRacePairs)
static bool	occurrencesRace (MHP *mhp, const RaceOccurrence &first, const RaceOccurrence &second)
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 80 of file MTA.h.

Member Typedef Documentation

ObjectToRaceOccurrences

using SVF::MTA::ObjectToRaceOccurrences = Map<NodeID, std::vector<size_t> >

private

Definition at line 179 of file MTA.h.

Constructor & Destructor Documentation

MTA()

MTA::MTA

(

)

Constructor.

Definition at line 53 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 58 of file MTA.cpp.

{
    delete mhp;
    delete lsa;
}

Member Function Documentation

buildRaceClasses()

std::vector< MTA::RaceClass > MTA::buildRaceClasses ( const std::vector< RaceOccurrence > &  occurrences, const std::vector< size_t > &  occurrenceIndices  )

staticprivate

Definition at line 289 of file MTA.cpp.

{
    std::vector<RaceClass> classes;
    OrderedMap<RaceClassKey, size_t> keyToClass;
    for (size_t occurrenceIndex : occurrenceIndices)
    {
        const RaceOccurrence& occurrence = occurrences[occurrenceIndex];
        const RaceClassKey key
        {
            occurrence.tid, occurrence.isStore, occurrence.interleaving,
            occurrence.locked,
            occurrence.locked ? occurrence.node->getId() : 0};
        const auto found = keyToClass.find(key);
        if (found == keyToClass.end())
        {
            keyToClass[key] = classes.size();
            classes.push_back(
            {
                occurrence.isStore, occurrence.locked, occurrenceIndex,
                {occurrenceIndex}});
        }
        else
            classes[found->second].members.push_back(occurrenceIndex);
    }
    return classes;
}

collectRaceOccurrences()

void MTA::collectRaceOccurrences ( SVFIR *  svfir, AndersenBase *  pta, MHP *  mhp, LockAnalysis *  lockAnalysis, CallGraph *  callGraph, const PointsTo &  escapedObjects, std::vector< RaceOccurrence > &  occurrences, ObjectToRaceOccurrences &  objectToOccurrences  )

staticprivate

Helpers for the equivalence-class race detector.

Definition at line 229 of file MTA.cpp.

{
    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())
            {
                const MHP::NodeThreadSummary* threadSummary =
                    mhp->getThreadSummary(node);
                if (threadSummary == nullptr)
                    continue;
                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 &= escapedObjects;
                    if (objects.empty())
                        continue;
 
                    const bool locked =
                        lockAnalysis->isProtectedByCommonLock(node, node);
                    const size_t firstNewOccurrence = occurrences.size();
                    for (const auto& tidAndInterleaving :
                            threadSummary->interleavingByTid)
                        occurrences.push_back(
                    {
                        stmt, node, isStore, tidAndInterleaving.first,
                        &tidAndInterleaving.second, locked});
                    for (NodeID object : objects)
                        for (size_t index = firstNewOccurrence;
                                index < occurrences.size(); ++index)
                            objectToOccurrences[object].push_back(index);
                }
            }
    }
}

commitRacePair()

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

staticprivate

Definition at line 207 of file MTA.cpp.

{
    out.emplace(first.stmt, second.stmt);
}

computeLocksets()

LockAnalysis * MTA::computeLocksets ( TCT *  tct )

virtual

Compute locksets.

Compute lock sets

Definition at line 106 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 113 of file MTA.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("MHP analysis\n"));
    DBOUT(DMTA, outs() << pasMsg("MHP analysis\n"));
 
    DOTIMESTAT(double mhpStart = stat->getClk());
    std::unique_ptr<MHP> mhp = MHP::create(
                                   tct, PAG::getPAG()->getICFG(),
                                   const_cast<CallGraph*>(PAG::getPAG()->getCallGraph()));
    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.release();
}

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 372 of file MTA.cpp.

{
 
    outRacePairs.clear();
    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);
 
    std::vector<RaceOccurrence> occurrences;
    ObjectToRaceOccurrences objectToOccurrences;
    collectRaceOccurrences(
        svfir, pta, mhp, lockAnalysis, callGraph, escSet,
        occurrences, objectToOccurrences);
 
    // 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)
    {
        const std::vector<RaceClass> classes =
            buildRaceClasses(occurrences, objectAndOccs.second);
        emitRacePairs(
            mhp, lockAnalysis, occurrences, classes, outRacePairs);
    }
 
    for (const RacePair& pair : outRacePairs)
    {
        bugStmts.insert(pair.stmt1);
        bugStmts.insert(pair.stmt2);
    }
    return bugStmts;
}

emitRacePairs()

void MTA::emitRacePairs ( MHP *  mhp, LockAnalysis *  lockAnalysis, const std::vector< RaceOccurrence > &  occurrences, const std::vector< RaceClass > &  classes, std::set< RacePair > &  outRacePairs  )

staticprivate

Definition at line 318 of file MTA.cpp.

{
    for (size_t firstIndex = 0; firstIndex < classes.size(); ++firstIndex)
        for (size_t secondIndex = firstIndex;
                secondIndex < classes.size(); ++secondIndex)
        {
            const RaceClass& firstClass = classes[firstIndex];
            const RaceClass& secondClass = classes[secondIndex];
            if (!firstClass.isStore && !secondClass.isStore)
                continue;
 
            const RaceOccurrence& firstRepresentative =
                occurrences[firstClass.representative];
            const RaceOccurrence& secondRepresentative =
                occurrences[secondClass.representative];
            if (!occurrencesRace(
                        mhp, firstRepresentative, secondRepresentative))
                continue;
 
            if (firstIndex != secondIndex)
            {
                if (firstClass.locked && secondClass.locked &&
                        lockAnalysis->isProtectedByCommonLock(
                            firstRepresentative.node, secondRepresentative.node))
                    continue;
                for (size_t memberIndex : firstClass.members)
                    for (size_t otherIndex : secondClass.members)
                        commitRacePair(outRacePairs, occurrences[memberIndex],
                                       occurrences[otherIndex]);
            }
            else
            {
                const std::vector<size_t>& members = firstClass.members;
                if (firstClass.locked &&
                        lockAnalysis->isProtectedByCommonLock(
                            firstRepresentative.node, firstRepresentative.node))
                    continue;
                for (size_t firstPosition = 0;
                        firstPosition < members.size(); ++firstPosition)
                    for (size_t secondPosition = firstPosition;
                            secondPosition < members.size(); ++secondPosition)
                        commitRacePair(
                            outRacePairs, occurrences[members[firstPosition]],
                            occurrences[members[secondPosition]]);
            }
        }
}

getGlobalObjectVariables()

PointsTo MTA::getGlobalObjectVariables ( SVFIR *  svfir )

static

Escape/points-to helpers for the shared detector.

Definition at line 132 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 105 of file MTA.h.

    {
        return lsa;
    }

getMHP()

MHP * SVF::MTA::getMHP ( )

inline

Definition at line 100 of file MTA.h.

    {
        return mhp;
    }

getPointsToClosure()

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

static

Definition at line 161 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 1326 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

Definition at line 197 of file MTA.cpp.

{
    if (first.tid != second.tid)
        return first.interleaving->test(second.tid) &&
               second.interleaving->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 420 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 67 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 = TCT::create(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 206 of file MTA.h.

mhp

MHP* SVF::MTA::mhp

private

Definition at line 205 of file MTA.h.

stat

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

private

Definition at line 204 of file MTA.h.

tcg

ThreadCallGraph* SVF::MTA::tcg

private

Definition at line 202 of file MTA.h.

tct

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

private

Definition at line 203 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