Add an upper bound of each slice node to be in the working list to prevent deadlock
[dyninst.git] / parseAPI / src / BoundFactCalculator.C
1 #include "IndirectControlFlow.h"
2 #include "IndirectASTVisitor.h"
3 #include "debug_parse.h"
4
5 bool BoundFactsCalculator::CalculateBoundedFacts() {    
6     /* We use a dataflow analysis to calculate what registers are bounded 
7      * at each node. The key points of the dataflow analysis are how
8      * to calculate the meet and how to calculate the transfer function.
9      * 1. The meet should be simply an intersection of all the bounded facts 
10      * along all paths. 
11      * 2. To calculate the transfer function, we first get the symbolic expression
12      * of the instrution for the node. Then depending on the instruction operation
13      * and the meet result, we know what are still bounded. For example, loading 
14      * memory is always unbounded; doing and operation on a register with a constant
15      * makes the register bounded. 
16      */
17     
18
19     queue<Node::Ptr> workingList;
20     map<Node::Ptr, int> inQueueLimit;
21
22     NodeIterator nbegin, nend;
23     slice->allNodes(nbegin, nend);
24
25     for (; nbegin != nend; ++nbegin) {
26         workingList.push(*nbegin);
27     }
28
29
30     while (!workingList.empty()) {
31         Node::Ptr curNode = workingList.front();
32         workingList.pop();
33
34         ++inQueueLimit[curNode];
35         if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
36
37         BoundFact* oldFact = GetBoundFact(curNode);
38         BoundFact* newFact = Meet(curNode);
39         CalcTransferFunction(curNode, newFact);
40
41         if (oldFact == NULL || *oldFact != *newFact) {
42             if (oldFact != NULL) delete oldFact;
43             boundFacts[curNode] = newFact;
44             curNode->outs(nbegin, nend);
45             for (; nbegin != nend; ++nbegin)
46                 workingList.push(*nbegin);
47         }
48     }
49
50     return true;
51 }
52
53
54 void BoundFactsCalculator::ConditionalJumpBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
55
56     /* This function checks whether any potential table guard is between the two nodes
57      * that we are calculating the meet. Essentially, if there is a conditional jump 
58      * between the two nodes, we know extra bound information.     
59      */   
60
61     ParseAPI::Block *srcBlock;
62     if (src == Node::Ptr()) 
63         srcBlock = func->entry();
64     else {
65         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
66         srcBlock = srcNode->block();
67
68     }
69     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
70     ParseAPI::Block *trgBlock = trgNode->block();
71
72     for (auto git = guards.begin(); git != guards.end(); ++git) {
73         parsing_printf("Checking guard at %lx\n", git->jmpInsnAddr);
74         if (!git->constantBound) {
75             parsing_printf("\t not a constant bound, skip\n");
76             continue;
77         }           
78
79         ParseAPI::Block *guardBlock = git->block;
80         // Note that the guardBlock and the srcBlock can be the same, 
81         // but since the conditional jump will always be the last instruction
82         // in the block, if they are in the same block, the src can reach the guard
83         if (src != Node::Ptr() && rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) {
84             parsing_printf("\t this guard is not between the source block %lx and the target %lx, skip\n", srcBlock->start(), guardBlock->start());
85             continue;
86         }           
87         bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
88         bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
89         parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
90         // If both branches reach the trg node, then this conditional jump 
91         // does not bound any variable for the trg node.
92         if (pred_taken ^ pred_ft) {
93             // Here I need to figure out which branch bounds the variable and 
94             // check it is the bounded path that reaches the trg node.
95             AST::Ptr cmpAST;
96             bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
97             if (   (boundedOnTakenBranch && pred_taken)
98                 // In thic case, we jump when the variable is smaller than the constant.
99                 // So the condition taken path is the path that bounds the value.
100                 || (!boundedOnTakenBranch && pred_ft) ) {
101                 // In thic case, we jump when the variable is larger than the constant.
102                 // So the fallthrough path is the path that bounds the value.
103
104                 if (curFact->cmpBoundFactLive == false || git->cmpBound > curFact->cmpBound) {
105                     curFact->cmpAST = git->cmpAST;
106                     curFact->cmpBound = git->cmpBound;
107                     curFact->cmpBoundFactLive = true;
108                     curFact->cmpUsedRegs = git->usedRegs;
109                 }
110             }
111         }
112     }
113     if (!curFact->cmpBoundFactLive && firstBlock) {
114         // If this is indirect jump is in the first block,
115         // it is possible that it is a jump table for a function 
116         // with variable number of arguments. Then the convention
117         // is that al contains the number of argument.
118         curFact->cmpAST = VariableAST::create(Variable(Absloc(x86_64::rax)));
119         curFact->cmpBound = 8;
120         curFact->cmpUsedRegs.insert(x86_64::rax);
121         curFact->cmpBoundFactLive = true;
122     }
123 }
124
125
126 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
127
128     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode); 
129     parsing_printf("Calculate Meet for %lx\n", node->addr());
130
131     NodeIterator gbegin, gend;
132     curNode->ins(gbegin, gend);    
133     BoundFact* newFact = new BoundFact();
134
135     if (gbegin != gend) {
136         bool first = true;      
137         for (; gbegin != gend; ++gbegin) {
138             SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin); 
139             BoundFact *prevFact = GetBoundFact(*gbegin);            
140             if (prevFact == NULL) {
141                 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
142                 continue;
143             }
144             prevFact = new BoundFact(*prevFact);
145             parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
146
147             ConditionalJumpBound(prevFact, *gbegin, curNode);
148             if (first) {
149                 first = false;
150                 *newFact = *prevFact;
151             } else {
152                 newFact->Intersect(*prevFact);
153             }
154             parsing_printf("New fact after the change is\n");
155             newFact->Print();
156
157         }
158     } else {
159         ConditionalJumpBound(newFact, Node::Ptr(), curNode);
160         parsing_printf("Meet no incoming nodes\n");
161         newFact->Print();
162     }
163     return newFact;
164 }
165
166 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
167
168     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
169     AbsRegion &ar = node->assign()->out();
170
171     parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
172     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
173
174     if (expandRet.first == NULL) {
175         // If the instruction is outside the set of instrutions we
176         // add instruction semantics. We assume this instruction
177         // kills all bound fact.
178         parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
179         return;
180     }
181     parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
182
183     AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
184
185     parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
186     parsing_printf("Calculating transfer function: Input facts\n");
187     newFact->Print();
188
189     BoundCalcVisitor bcv(*newFact);
190     calculation->accept(&bcv);
191
192     if (bcv.IsResultBounded(calculation)) { 
193         parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
194         newFact->GenFact(ar.absloc(), new BoundValue(*bcv.GetResultBound(calculation)));
195     }
196     else {
197         parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
198         newFact->KillFact(ar.absloc());
199     }
200     parsing_printf("Calculating transfer function: Output facts\n");
201     newFact->Print();
202
203 }                                               
204
205 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
206     auto fit = boundFacts.find(node);
207     if (fit == boundFacts.end())
208         return NULL;
209     else
210         return fit->second;
211 }
212
213 BoundFactsCalculator::~BoundFactsCalculator() {
214     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
215         if (fit->second != NULL)
216             delete fit->second;
217     boundFacts.clear();
218 }
219
220