/* ### * IP: GHIDRA * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include "flow.hh" /// Prepare for tracing flow for a new function. /// The Funcdata object and references to its internal containers must be explicitly given. /// \param d is the new function to trace /// \param o is the internal p-code container for the function /// \param b is the internal basic block container /// \param q is the internal container of call sites FlowInfo::FlowInfo(Funcdata &d,PcodeOpBank &o,BlockGraph &b,vector &q) : data(d), obank(o), bblocks(b), qlst(q), baddr(d.getAddress().getSpace(),0), eaddr(d.getAddress().getSpace(),~((uintb)0)), minaddr(d.getAddress()), maxaddr(d.getAddress()) { glb = data.getArch(); flags = 0; emitter.setFuncdata(&d); inline_head = (Funcdata *)0; inline_recursion = (set
*)0; insn_count = 0; insn_max = ~((uint4)0); flowoverride_present = data.getOverride().hasFlowOverride(); } /// Prepare a new flow cloned from an existing flow. /// Configuration from the existing flow is copied, but the actual PcodeOps must already be /// cloned within the new function. /// \param d is the new function that has been cloned /// \param o is the internal p-code container for the function /// \param b is the internal basic block container /// \param q is the internal container of call sites /// \param op2 is the existing flow FlowInfo::FlowInfo(Funcdata &d,PcodeOpBank &o,BlockGraph &b,vector &q,const FlowInfo *op2) : data(d), obank(o), bblocks(b), qlst(q), baddr(op2->baddr), eaddr(op2->eaddr), minaddr(d.getAddress()), maxaddr(d.getAddress()) { glb = data.getArch(); flags = op2->flags; emitter.setFuncdata(&d); unprocessed = op2->unprocessed; // Clone the flow address information addrlist = op2->addrlist; visited = op2->visited; inline_head = op2->inline_head; if (inline_head != (Funcdata *)0) { inline_base = op2->inline_base; inline_recursion = &inline_base; } else inline_recursion = (set
*)0; insn_count = op2->insn_count; insn_max = op2->insn_max; flowoverride_present = data.getOverride().hasFlowOverride(); } void FlowInfo::clearProperties(void) { flags &= ~((uint4)(unimplemented_present|baddata_present|outofbounds_present)); insn_count = 0; } /// For efficiency, this method assumes the given op can actually fall-thru. /// \param op is the given PcodeOp /// \return the PcodeOp that fall-thru flow would reach (or NULL if there is no possible p-code op) PcodeOp *FlowInfo::fallthruOp(PcodeOp *op) const { PcodeOp *retop; list::const_iterator iter = op->getInsertIter(); ++iter; if (iter != obank.endDead()) { retop = *iter; if (!retop->isInstructionStart()) // If within same instruction return retop; // Then this is the fall thru } // Find address of instruction containing this op map::const_iterator miter; miter = visited.upper_bound(op->getAddr()); if (miter == visited.begin()) return (PcodeOp *)0; --miter; if ((*miter).first + (*miter).second.size <= op->getAddr()) return (PcodeOp *)0; return target( (*miter).first + (*miter).second.size); } /// The first p-code op associated with the machine instruction at the /// given address is returned. If the instruction generated no p-code, /// an attempt is made to fall-thru to the next instruction. /// If no p-code op is ultimately found, an exception is thrown. /// \param addr is the given address of the instruction /// \return the targetted p-code op PcodeOp *FlowInfo::target(const Address &addr) const { map::const_iterator iter; iter = visited.find(addr); while(iter != visited.end()) { const SeqNum &seq( (*iter).second.seqnum ); if (!seq.getAddr().isInvalid()) { PcodeOp *retop = obank.findOp(seq); if (retop != (PcodeOp *)0) return retop; break; } // Visit fall thru address in case of no-op iter = visited.find( (*iter).first + (*iter).second.size ); } ostringstream errmsg; errmsg << "Could not find op at target address: ("; errmsg << addr.getSpace()->getName() << ','; addr.printRaw(errmsg); errmsg << ')'; throw LowlevelError(errmsg.str()); } /// \brief Generate the target PcodeOp for a relative branch /// /// Assuming the given op is a relative branch, find the existing target PcodeOp if the /// branch is properly internal, or return the fall-thru address in \b res (which may not have /// PcodeOps generated for it yet) if the relative branch is really a branch to the next instruction. /// Otherwise an exception is thrown. /// \param op is the given branching p-code op /// \param res is a reference to the fall-thru address being passed back /// \return the target PcodeOp or NULL if the fall-thru address is passed back instead PcodeOp *FlowInfo::findRelTarget(PcodeOp *op,Address &res) const { const Address &addr(op->getIn(0)->getAddr()); uintm id = op->getTime() + addr.getOffset(); SeqNum seqnum(op->getAddr(),id); PcodeOp *retop = obank.findOp(seqnum); if (retop != (PcodeOp *)0) // Is this a "properly" internal branch return retop; // Now we check if the relative branch is really to the next instruction SeqNum seqnum1(op->getAddr(),id-1); retop = obank.findOp(seqnum1); // We go back one sequence number if (retop != (PcodeOp *)0) { // If the PcodeOp exists here then branch was indeed to next instruction map::const_iterator miter; miter = visited.upper_bound(retop->getAddr()); if (miter != visited.begin()) { --miter; res = (*miter).first + (*miter).second.size; if (op->getAddr() < res) return (PcodeOp *)0; // Indicate that res has the fallthru address } } ostringstream errmsg; errmsg << "Bad relative branch at instruction : ("; errmsg << op->getAddr().getSpace()->getName() << ','; op->getAddr().printRaw(errmsg); errmsg << ')'; throw LowlevelError(errmsg.str()); } /// The \e code \e reference passed as the first parameter to the branch /// is examined, and the p-code op it refers to is returned. /// The reference may be a normal direct address or a relative offset. /// If no target p-code can be found, an exception is thrown. /// \param op is the given branch op /// \return the targetted p-code op PcodeOp *FlowInfo::branchTarget(PcodeOp *op) const { const Address &addr(op->getIn(0)->getAddr()); if (addr.isConstant()) { // This is a relative sequence number Address res; PcodeOp *retop = findRelTarget(op,res); if (retop != (PcodeOp *)0) return retop; return target(res); } return target(addr); // Otherwise a normal address target } /// Check to see if the new target has been seen before. Otherwise /// add it to the list of addresses that need to be processed. /// Also check range bounds and update basic block information. /// \param from is the PcodeOp issuing the branch /// \param to is the target address of the branch void FlowInfo::newAddress(PcodeOp *from,const Address &to) { if ((to < baddr)||(eaddr < to)) { handleOutOfBounds(from->getAddr(),to); unprocessed.push_back(to); return; } if (seenInstruction(to)) { // If we have seen this address before PcodeOp *op = target(to); data.opMarkStartBasic(op); return; } addrlist.push_back(to); } /// \brief Delete any remaining ops at the end of the instruction /// /// (because they have been predetermined to be dead) /// \param oiter is the point within the raw p-code list where deletion should start void FlowInfo::deleteRemainingOps(list::const_iterator oiter) { while(oiter != obank.endDead()) { PcodeOp *op = *oiter; ++oiter; data.opDestroyRaw(op); } } /// \brief Analyze control-flow within p-code for a single instruction /// /// Walk through the raw p-code (from the given iterator to the end of the list) /// looking for control flow operations (BRANCH,CBRANCH,BRANCHIND,CALL,CALLIND,RETURN) /// and add appropriate annotations (startbasic, callspecs, new addresses). /// As it iterates through the p-code, the method maintains a reference to a boolean /// indicating whether the current op is the start of a basic block. This value /// persists across calls. The method also passes back a boolean value indicating whether /// the instruction as a whole has fall-thru flow. /// \param oiter is the given iterator starting the list of p-code ops /// \param startbasic is the reference holding whether the current op starts a basic block /// \param isfallthru passes back if the instruction has fall-thru flow /// \param fc if the p-code is generated from an \e injection, this holds the reference to the injecting sub-function /// \return the last processed PcodeOp (or NULL if there were no ops in the instruction) PcodeOp *FlowInfo::xrefControlFlow(list::const_iterator oiter,bool &startbasic,bool &isfallthru,FuncCallSpecs *fc) { PcodeOp *op = (PcodeOp *)0; isfallthru = false; uintm maxtime=0; // Deepest internal relative branch while(oiter != obank.endDead()) { op = *oiter++; if (startbasic) { data.opMarkStartBasic(op); startbasic = false; } switch(op->code()) { case CPUI_CBRANCH: { const Address &destaddr( op->getIn(0)->getAddr() ); if (destaddr.isConstant()) { Address fallThruAddr; PcodeOp *destop = findRelTarget(op,fallThruAddr); if (destop != (PcodeOp *)0) { data.opMarkStartBasic(destop); // Make sure the target op is a basic block start uintm newtime = destop->getTime(); if (newtime > maxtime) maxtime = newtime; } else isfallthru = true; // Relative branch is to end of instruction } else newAddress(op,destaddr); // Generate branch address startbasic = true; } break; case CPUI_BRANCH: { const Address &destaddr( op->getIn(0)->getAddr() ); if (destaddr.isConstant()) { Address fallThruAddr; PcodeOp *destop = findRelTarget(op,fallThruAddr); if (destop != (PcodeOp *)0) { data.opMarkStartBasic(destop); // Make sure the target op is a basic block start uintm newtime = destop->getTime(); if (newtime > maxtime) maxtime = newtime; } else isfallthru = true; // Relative branch is to end of instruction } else newAddress(op,destaddr); // Generate branch address if (op->getTime() >= maxtime) { deleteRemainingOps(oiter); oiter = obank.endDead(); } startbasic = true; } break; case CPUI_BRANCHIND: tablelist.push_back(op); // Put off trying to recover the table if (op->getTime() >= maxtime) { deleteRemainingOps(oiter); oiter = obank.endDead(); } startbasic = true; break; case CPUI_RETURN: if (op->getTime() >= maxtime) { deleteRemainingOps(oiter); oiter = obank.endDead(); } startbasic = true; break; case CPUI_CALL: if (setupCallSpecs(op,fc)) --oiter; // Backup one op, to pickup halt break; case CPUI_CALLIND: if (setupCallindSpecs(op,true,fc)) --oiter; // Backup one op, to pickup halt break; case CPUI_CALLOTHER: { InjectedUserOp *userop = dynamic_cast(glb->userops.getOp(op->getIn(0)->getOffset())); if (userop != (InjectedUserOp *)0) injectlist.push_back(op); break; } default: break; } } if (isfallthru) // We have seen an explicit relative branch to end of instruction startbasic = true; // So we know next instruction starts a basicblock else { // If we haven't seen a relative branch, calculate fallthru by looking at last op if (op == (PcodeOp *)0) isfallthru = true; // No ops at all, mean a fallthru else { switch(op->code()) { case CPUI_BRANCH: case CPUI_BRANCHIND: case CPUI_RETURN: break; // If the last instruction is a branch, then no fallthru default: isfallthru = true; // otherwise it is a fallthru break; } } } return op; } /// \brief Generate p-code for a single machine instruction and process discovered flow information /// /// P-code is generated (to the raw \e dead list in PcodeOpBank). Errors for unimplemented /// instructions or inaccessible data are handled. The p-code is examined for control-flow, /// and annotations are made. The set of visited instructions and the set of /// addresses still needing to be processed are updated. /// \param curaddr is the address of the instruction to process /// \param startbasic indicates of the instruction starts a basic block and passes back whether the next instruction does /// \return \b true if the processed instruction has a fall-thru flow bool FlowInfo::processInstruction(const Address &curaddr,bool &startbasic) { bool emptyflag; bool isfallthru = true; // JumpTable *jt; list::const_iterator oiter; int4 step; uint4 flowoverride; if (insn_count >= insn_max) { if ((flags & error_toomanyinstructions)!=0) throw LowlevelError("Flow exceeded maximum allowable instructions"); else { step = 1; artificialHalt(curaddr,PcodeOp::badinstruction); data.warning("Too many instructions -- Truncating flow here",curaddr); if (!hasTooManyInstructions()) { flags |= toomanyinstructions_present; data.warningHeader("Exceeded maximum allowable instructions: Some flow is truncated"); } } } insn_count += 1; if (obank.empty()) emptyflag = true; else { emptyflag = false; oiter = obank.endDead(); --oiter; } if (flowoverride_present) flowoverride = data.getOverride().getFlowOverride(curaddr); else flowoverride = Override::NONE; try { step = glb->translate->oneInstruction(emitter,curaddr); // Generate ops for instruction } catch(UnimplError &err) { // Instruction is unimplemented if ((flags & ignore_unimplemented)!=0) { step = err.instruction_length; if (!hasUnimplemented()) { flags |= unimplemented_present; data.warningHeader("Control flow ignored unimplemented instructions"); } } else if ((flags & error_unimplemented)!=0) throw err; // rethrow else { // Add infinite loop instruction step = 1; // Pretend size 1 artificialHalt(curaddr,PcodeOp::unimplemented); data.warning("Unimplemented instruction - Truncating control flow here",curaddr); if (!hasUnimplemented()) { flags |= unimplemented_present; data.warningHeader("Control flow encountered unimplemented instructions"); } } } catch(BadDataError &err) { if ((flags & error_unimplemented)!=0) throw err; // rethrow else { // Add infinite loop instruction step = 1; // Pretend size 1 artificialHalt(curaddr,PcodeOp::badinstruction); data.warning("Bad instruction - Truncating control flow here",curaddr); if (!hasBadData()) { flags |= baddata_present; data.warningHeader("Control flow encountered bad instruction data"); } } } VisitStat &stat(visited[curaddr]); // Mark that we visited this instruction stat.size = step; // Record size of instruction if (curaddr < minaddr) // Update minimum and maximum address minaddr = curaddr; if (maxaddr < curaddr+step) // Keep track of biggest and smallest address maxaddr = curaddr+step; if (emptyflag) // Make sure oiter points at first new op oiter = obank.beginDead(); else ++oiter; if (oiter != obank.endDead()) { stat.seqnum = (*oiter)->getSeqNum(); data.opMarkStartInstruction(*oiter); // Mark the first op in the instruction if (flowoverride != Override::NONE) data.overrideFlow(curaddr,flowoverride); xrefControlFlow(oiter,startbasic,isfallthru,(FuncCallSpecs *)0); } if (isfallthru) addrlist.push_back(curaddr+step); return isfallthru; } /// From the address at the top of the \b addrlist stack /// Figure out how far we could follow fall-thru instructions /// before hitting something we've already seen /// \param bound passes back the first address encountered that we have already seen /// \return \b false if the address has already been visited bool FlowInfo::setFallthruBound(Address &bound) { map::const_iterator iter; const Address &addr( addrlist.back() ); iter = visited.upper_bound(addr); // First range greater than addr if (iter!=visited.begin()) { --iter; // Last range less than or equal to us if (addr == (*iter).first) { // If we have already visited this address PcodeOp *op = target(addr); // But make sure the address data.opMarkStartBasic(op); // starts a basic block addrlist.pop_back(); // Throw it away return false; } if (addr < (*iter).first + (*iter).second.size) reinterpreted(addr); ++iter; } if (iter!=visited.end()) // Whats the maximum distance we can go bound = (*iter).first; else bound = eaddr; return true; } /// \brief Generate warning message or throw exception for given flow that is out of bounds /// /// \param fromaddr is the source address of the flow (presumably in bounds) /// \param toaddr is the given destination address that is out of bounds void FlowInfo::handleOutOfBounds(const Address &fromaddr,const Address &toaddr) { if ((flags&ignore_outofbounds)==0) { // Should we throw an error for out of bounds ostringstream errmsg; errmsg << "Function flow out of bounds: "; errmsg << fromaddr.getShortcut(); fromaddr.printRaw(errmsg); errmsg << " flows to "; errmsg << toaddr.getShortcut(); toaddr.printRaw(errmsg); if ((flags&error_outofbounds)==0) { data.warning(errmsg.str(),toaddr); if (!hasOutOfBounds()) { flags |= outofbounds_present; data.warningHeader("Function flows out of bounds"); } } else throw LowlevelError(errmsg.str()); } } /// The address at the top stack that still needs processing is popped. /// P-code is generated for instructions starting at this address until /// one no longer has fall-thru flow (or some other error occurs). void FlowInfo::fallthru(void) { Address bound; if (!setFallthruBound(bound)) return; Address curaddr; bool startbasic = true; bool fallthruflag; for(;;) { curaddr = addrlist.back(); addrlist.pop_back(); fallthruflag = processInstruction(curaddr,startbasic); if (!fallthruflag) break; if (addrlist.empty()) break; if (bound <= addrlist.back()) { if (bound == eaddr) { handleOutOfBounds(eaddr,addrlist.back()); unprocessed.push_back(addrlist.back()); addrlist.pop_back(); return; } if (bound == addrlist.back()) { // Hit the bound exactly if (startbasic) { PcodeOp *op = target(addrlist.back()); data.opMarkStartBasic(op); } addrlist.pop_back(); break; } if (!setFallthruBound(bound)) return; // Reset bound } } } /// An \b artificial \b halt, is a special form of RETURN op. /// The op is annotated with the desired \e type of artificial halt. /// - Bad instruction /// - Unimplemented instruction /// - Missing/truncated instruction /// - (Previous) call that never returns /// /// \param addr is the target address for the new p-code op /// \param flag is the desired \e type /// \return the new p-code op PcodeOp *FlowInfo::artificialHalt(const Address &addr,uint4 flag) { PcodeOp *haltop = data.newOp(1,addr); data.opSetOpcode(haltop,CPUI_RETURN); data.opSetInput(haltop,data.newConstant(4,1),0); if (flag != 0) data.opMarkHalt(haltop,flag); // What kind of halt return haltop; } /// A set of bytes is \b reinterpreted if there are at least two /// different interpretations of the bytes as instructions. /// \param addr is the address of a byte previously interpreted as (the interior of) an instruction void FlowInfo::reinterpreted(const Address &addr) { map::const_iterator iter; iter = visited.upper_bound(addr); if (iter==visited.begin()) return; // Should never happen --iter; const Address &addr2( (*iter).first ); ostringstream s; s << "Instruction at (" << addr.getSpace()->getName() << ','; addr.printRaw(s); s << ") overlaps instruction at (" << addr2.getSpace()->getName() << ','; addr2.printRaw(s); s << ')' << endl; if ((flags & error_reinterpreted)!=0) throw LowlevelError(s.str()); if ((flags & reinterpreted_present)==0) { flags |= reinterpreted_present; data.warningHeader(s.str()); } } /// \brief Check for modifications to flow at a call site given the recovered FuncCallSpecs /// /// The sub-function may be in-lined or never return. /// \param fspecs is the given call site /// \return \b true if the sub-function never returns bool FlowInfo::checkForFlowModification(FuncCallSpecs &fspecs) { if (fspecs.isInline()) injectlist.push_back(fspecs.getOp()); if (fspecs.isNoReturn()) { PcodeOp *op = fspecs.getOp(); PcodeOp *haltop = artificialHalt(op->getAddr(),PcodeOp::noreturn); data.opDeadInsertAfter(haltop,op); if (!fspecs.isInline()) data.warning("Subroutine does not return",op->getAddr()); return true; } return false; } /// If there is an explicit target address for the given call site, /// attempt to look up the function and adjust information in the FuncCallSpecs call site object. /// \param fspecs is the call site object void FlowInfo::queryCall(FuncCallSpecs &fspecs) { if (!fspecs.getEntryAddress().isInvalid()) { // If this is a direct call Funcdata *otherfunc = data.getScopeLocal()->getParent()->queryFunction( fspecs.getEntryAddress() ); if (otherfunc != (Funcdata *)0) { fspecs.setFuncdata(otherfunc); // Associate the symbol with the callsite if (!fspecs.hasModel()) { // If the prototype was not overridden fspecs.copyFlowEffects(otherfunc->getFuncProto()); // Take the symbols's prototype // If the callsite is applying just the standard prototype from the symbol, // this postpones the full copy of the prototype until ActionDefaultParams // Which lets "last second" changes come in, between when the function is first walked and // when it is finally decompiled } } } } /// The new FuncCallSpecs object is created and initialized based on /// the CALL op at the site and any matching function in the symbol table. /// Any overriding prototype or control-flow is examined and applied. /// \param op is the given CALL op /// \param fc is non-NULL if \e injection is in progress and a cycle check needs to be made /// \return \b true if it is discovered the sub-function never returns bool FlowInfo::setupCallSpecs(PcodeOp *op,FuncCallSpecs *fc) { FuncCallSpecs *res; res = new FuncCallSpecs(op); data.opSetInput(op,data.newVarnodeCallSpecs(res),0); qlst.push_back(res); data.getOverride().applyPrototype(data,*res); queryCall(*res); if (fc != (FuncCallSpecs *)0) { // If we are already in the midst of an injection if (fc->getEntryAddress() == res->getEntryAddress()) res->cancelInjectId(); // Don't allow recursion } return checkForFlowModification(*res); } /// \brief Set up the FuncCallSpecs object for a new indirect call site /// /// The new FuncCallSpecs object is created and initialized based on /// the CALLIND op at the site. Any overriding prototype or control-flow may be examined and applied. /// \param op is the given CALLIND op /// \param tryoverride is \b true is overrides should be applied for the call site /// \param fc is non-NULL if \e injection is in progress and a cycle check needs to be made /// \return \b true if it is discovered the sub-function never returns bool FlowInfo::setupCallindSpecs(PcodeOp *op,bool tryoverride,FuncCallSpecs *fc) { FuncCallSpecs *res; res = new FuncCallSpecs(op); qlst.push_back(res); if (tryoverride) { data.getOverride().applyIndirect(data,*res); data.getOverride().applyPrototype(data,*res); } queryCall(*res); if (fc != (FuncCallSpecs *)0) { if (fc->getEntryAddress() == res->getEntryAddress()) { res->cancelInjectId(); res->setAddress(Address()); // Cancel any indirect override } } if (!res->getEntryAddress().isInvalid()) { // If we are overridden to a direct call // Change indirect pcode call into a normal pcode call data.opSetOpcode(op,CPUI_CALL); // Set normal opcode data.opSetInput(op,data.newVarnodeCallSpecs(res),0); } return checkForFlowModification(*res); } /// \param op is the BRANCHIND operation to convert /// \param failuremode is a code indicating the type of failure when trying to recover the jump table void FlowInfo::truncateIndirectJump(PcodeOp *op,int4 failuremode) { data.opSetOpcode(op,CPUI_CALLIND); // Turn jump into call bool tryoverride = (failuremode == 2); setupCallindSpecs(op,tryoverride,(FuncCallSpecs *)0); data.getCallSpecs(op)->setBadJumpTable(true); // Create an artificial return PcodeOp *truncop = artificialHalt(op->getAddr(),0); data.opDeadInsertAfter(truncop,op); data.warning("Treating indirect jump as call",op->getAddr()); } /// \brief Test if the given p-code op is a member of an array /// /// \param array is the array of p-code ops to search /// \param op is the given p-code op to search for /// \return \b true if the op is a member of the array bool FlowInfo::isInArray(vector &array,PcodeOp *op) { for(int4 i=0;i notreached; // indirect ops that are not reachable int4 notreachcnt = 0; clearProperties(); addrlist.push_back(data.getAddress()); while(!addrlist.empty()) // Recovering as much as possible except jumptables fallthru(); if (hasInject()) injectPcode(); do { bool collapsed_jumptable = false; while(!tablelist.empty()) { // For each jumptable found PcodeOp *op = tablelist.back(); tablelist.pop_back(); int4 failuremode; JumpTable *jt = data.recoverJumpTable(op,this,failuremode); // Recover it if (jt == (JumpTable *)0) { // Could not recover jumptable if ((failuremode == 3) && (!tablelist.empty()) && (!isInArray(notreached,op))) { // If the indirect op was not reachable with current flow AND there is more flow to generate, // AND we haven't tried to recover this table before notreached.push_back(op); // Save this op so we can try to recovery table again later } else if (!isFlowForInline()) // Unless this flow is being inlined for something else truncateIndirectJump(op,failuremode); // Treat the indirect jump as a call } else { int4 num = jt->numEntries(); for(int4 i=0;igetAddressByIndex(i)); if (jt->isPossibleMultistage()) collapsed_jumptable = true; while(!addrlist.empty()) // Try to fill in as much more as possible fallthru(); } } checkContainedCall(); // Check for PIC constructions if (collapsed_jumptable) checkMultistageJumptables(); while(notreachcnt < notreached.size()) { tablelist.push_back(notreached[notreachcnt]); notreachcnt += 1; } if (hasInject()) injectPcode(); } while(!tablelist.empty()); // Inlining or multistage may have added new indirect branches } void FlowInfo::generateBlocks(void) { fillinBranchStubs(); collectEdges(); splitBasic(); // Split ops up into basic blocks connectBasic(); // Generate edges between basic blocks if (bblocks.getSize()!=0) { FlowBlock *startblock = bblocks.getBlock(0); if (startblock->sizeIn() != 0) { // Make sure the entry block has no incoming edges // If it does we create a new entry block that flows into the old entry block BlockBasic *newfront = bblocks.newBlockBasic(&data); bblocks.addEdge(newfront,startblock); bblocks.setStartBlock(newfront); data.setBasicBlockRange(newfront, data.getAddress(), data.getAddress()); } } if (hasPossibleUnreachable()) data.removeUnreachableBlocks(false,true); } /// In the case where additional flow is truncated, run through the list of /// pending addresses, and if they don't have a p-code generated for them, /// add the Address to the \b unprocessed array. void FlowInfo::findUnprocessed(void) { vector
::iterator iter; for(iter=addrlist.begin();iter!=addrlist.end();++iter) { if (seenInstruction(*iter)) { PcodeOp *op = target(*iter); data.opMarkStartBasic(op); } else unprocessed.push_back(*iter); } } /// The list is also sorted void FlowInfo::dedupUnprocessed(void) { if (unprocessed.empty()) return; sort(unprocessed.begin(),unprocessed.end()); vector
::iterator iter1,iter2; iter1 = unprocessed.begin(); Address lastaddr = *iter1++; iter2 = iter1; while(iter1 != unprocessed.end()) { if (*iter1==lastaddr) iter1++; else { lastaddr = *iter1++; *iter2++ = lastaddr; } } unprocessed.erase(iter2,unprocessed.end()); } /// A special form of RETURN instruction is generated for every address in /// the \b unprocessed list. void FlowInfo::fillinBranchStubs(void) { vector
::iterator iter; findUnprocessed(); dedupUnprocessed(); for(iter=unprocessed.begin();iter!=unprocessed.end();++iter) { PcodeOp *op = artificialHalt(*iter,PcodeOp::missing); data.opMarkStartBasic(op); data.opMarkStartInstruction(op); } } /// An edge is held as matching PcodeOp entries in \b block_edge1 and \b block_edge2. /// Edges are generated for fall-thru to a p-code op marked as the start of a basic block /// or for an explicit branch. void FlowInfo::collectEdges(void) { list::const_iterator iter,iterend,iter1,iter2; PcodeOp *op,*targ_op; JumpTable *jt; bool nextstart; int4 i,num; if (bblocks.getSize() != 0) throw RecovError("Basic blocks already calculated\n"); iter = obank.beginDead(); iterend = obank.endDead(); while(iter!=iterend) { op = *iter++; if (iter==iterend) nextstart = true; else nextstart = (*iter)->isBlockStart(); switch(op->code()) { case CPUI_BRANCH: targ_op = branchTarget(op); block_edge1.push_back(op); // block_edge2.push_back(op->Input(0)->getAddr().Iop()); block_edge2.push_back(targ_op); break; case CPUI_BRANCHIND: jt = data.findJumpTable(op); if (jt == (JumpTable *)0) break; // If we are in this routine and there is no table // Then we must be doing partial flow analysis // so assume there are no branches out num = jt->numEntries(); for(i=0;igetAddressByIndex(i)); if (targ_op->isMark()) continue; // Already a link between these blocks targ_op->setMark(); block_edge1.push_back(op); block_edge2.push_back(targ_op); } iter1 = block_edge1.end(); // Clean up our marks iter2 = block_edge2.end(); while(iter1 != block_edge1.begin()) { --iter1; --iter2; if ((*iter1)==op) (*iter2)->clearMark(); else break; } break; case CPUI_RETURN: break; case CPUI_CBRANCH: targ_op = fallthruOp(op); // Put in fallthru edge block_edge1.push_back(op); block_edge2.push_back(targ_op); targ_op = branchTarget(op); block_edge1.push_back(op); block_edge2.push_back(targ_op); break; default: if (nextstart) { // Put in fallthru edge if new basic block targ_op = fallthruOp(op); block_edge1.push_back(op); block_edge2.push_back(targ_op); } break; } } } /// PcodeOp objects are moved out of the PcodeOpBank \e dead list into their /// assigned PcodeBlockBasic. Initial address ranges of instructions are recorded in the block. /// PcodeBlockBasic objects are created based on p-code ops that have been /// previously marked as \e start of basic block. void FlowInfo::splitBasic(void) { PcodeOp *op; BlockBasic *cur; list::const_iterator iter,iterend; iter = obank.beginDead(); iterend = obank.endDead(); if (iter == iterend) return; op = *iter++; if (!op->isBlockStart()) throw LowlevelError("First op not marked as entry point"); cur = bblocks.newBlockBasic(&data); data.opInsert(op,cur,cur->endOp()); bblocks.setStartBlock(cur); Address start = op->getAddr(); Address stop = start; while(iter != iterend) { op = *iter++; if (op->isBlockStart()) { data.setBasicBlockRange(cur, start, stop); cur = bblocks.newBlockBasic(&data); // Set up the next basic block start = op->getSeqNum().getAddr(); stop = start; } else { const Address &nextAddr( op->getAddr() ); if (stop < nextAddr) stop = nextAddr; } data.opInsert(op,cur,cur->endOp()); } data.setBasicBlockRange(cur, start, stop); } /// Directed edges between the PcodeBlockBasic objects are created based on the /// previously collected p-code op pairs in \b block_edge1 and \b block_edge2 void FlowInfo::connectBasic(void) { PcodeOp *op,*targ_op; BlockBasic *bs,*targ_bs; list::const_iterator iter,iter2; iter = block_edge1.begin(); iter2 = block_edge2.begin(); while(iter != block_edge1.end()) { op = *iter++; targ_op = *iter2++; bs = op->getParent(); targ_bs = targ_op->getParent(); bblocks.addEdge(bs,targ_bs); } } /// When preparing p-code for an in-lined function, the generation process needs /// to be informed of in-lining that has already been performed. /// This method copies the in-lining information from the parent flow, prior to p-code generation. /// \param op2 is the parent flow void FlowInfo::forwardRecursion(const FlowInfo &op2) { inline_recursion = op2.inline_recursion; inline_head = op2.inline_head; } /// If the given injected op is a CALL, CALLIND, or BRANCHIND, /// we need to add references to it in other flow tables. /// \param op is the given injected p-code op void FlowInfo::xrefInlinedBranch(PcodeOp *op) { if (op->code() == CPUI_CALL) setupCallSpecs(op,(FuncCallSpecs *)0); else if (op->code() == CPUI_CALLIND) setupCallindSpecs(op,true,(FuncCallSpecs *)0); else if (op->code() == CPUI_BRANCHIND) { JumpTable *jt = data.linkJumpTable(op); if (jt == (JumpTable *)0) tablelist.push_back(op); // Didn't recover a jumptable } } /// \brief Clone the given in-line flow into \b this flow using the \e hard model /// /// Individual PcodeOps from the Funcdata being in-lined are cloned into /// the Funcdata for \b this flow, preserving their original address. /// Any RETURN op is replaced with jump to first address following the call site. /// \param inlineflow is the given in-line flow to clone /// \param retaddr is the first address after the call site in \b this flow void FlowInfo::inlineClone(const FlowInfo &inlineflow,const Address &retaddr) { list::const_iterator iter; for(iter=inlineflow.data.beginOpDead();iter!=inlineflow.data.endOpDead();++iter) { PcodeOp *op = *iter; PcodeOp *cloneop; if ((op->code() == CPUI_RETURN)&&(!retaddr.isInvalid())) { cloneop = data.newOp(1,op->getSeqNum()); data.opSetOpcode(cloneop,CPUI_BRANCH); Varnode *vn = data.newCodeRef(retaddr); data.opSetInput(cloneop,vn,0); } else cloneop = data.cloneOp(op,op->getSeqNum()); if (cloneop->isCallOrBranch()) xrefInlinedBranch(cloneop); } // Copy in the cross-referencing unprocessed.insert(unprocessed.end(),inlineflow.unprocessed.begin(), inlineflow.unprocessed.end()); addrlist.insert(addrlist.end(),inlineflow.addrlist.begin(), inlineflow.addrlist.end()); visited.insert(inlineflow.visited.begin(),inlineflow.visited.end()); // We don't copy inline_recursion or inline_head here } /// \brief Clone the given in-line flow into \b this flow using the EZ model /// /// Individual PcodeOps from the Funcdata being in-lined are cloned into /// the Funcdata for \b this flow but are reassigned a new fixed address, /// and the RETURN op is eliminated. /// \param inlineflow is the given in-line flow to clone /// \param calladdr is the fixed address assigned to the cloned PcodeOps void FlowInfo::inlineEZClone(const FlowInfo &inlineflow,const Address &calladdr) { list::const_iterator iter; for(iter=inlineflow.data.beginOpDead();iter!=inlineflow.data.endOpDead();++iter) { PcodeOp *op = *iter; if (op->code() == CPUI_RETURN) break; SeqNum myseq(calladdr,op->getSeqNum().getTime()); data.cloneOp(op,myseq); } // Because we are processing only straightline code and it is all getting assigned to one // address, we don't touch unprocessed, addrlist, or visited } /// \brief For in-lining using the \e hard model, make sure some restrictions are met /// /// - Can only in-line the function once. /// - There must be a p-code op to return to. /// - There must be a distinct return address, so that the RETURN can be replaced with a BRANCH. /// /// Pass back the distinct return address, unless the in-lined function doesn't return. /// \param inlinefd is the function being in-lined into \b this flow /// \param op is CALL instruction at the site of the in-line /// \param retaddr holds the passed back return address /// \return \b true if all the \e hard model restrictions are met bool FlowInfo::testHardInlineRestrictions(Funcdata *inlinefd,PcodeOp *op,Address &retaddr) { if (inline_recursion->find( inlinefd->getAddress() ) != inline_recursion->end()) { // This function has already been included with current inlining inline_head->warning("Could not inline here",op->getAddr()); return false; } if (!inlinefd->getFuncProto().isNoReturn()) { list::iterator iter = op->getInsertIter(); ++iter; if (iter == obank.endDead()) { inline_head->warning("No fallthrough prevents inlining here",op->getAddr()); return false; } PcodeOp *nextop = *iter; retaddr = nextop->getAddr(); if (op->getAddr() == retaddr) { inline_head->warning("Return address prevents inlining here",op->getAddr()); return false; } // If the inlining "jumps back" this starts a new basic block data.opMarkStartBasic(nextop); } inline_recursion->insert(inlinefd->getAddress()); return true; } /// A function is in the EZ model if it is a straight-line leaf function. /// \return \b true if this flow contains no CALL or BRANCH ops bool FlowInfo::checkEZModel(void) const { list::const_iterator iter = obank.beginDead(); while(iter != obank.endDead()) { PcodeOp *op = *iter; if (op->isCallOrBranch()) return false; ++iter; } return true; } /// \brief Inject the given payload into \b this flow /// /// The injected p-code replaces the given op, and control-flow information /// is updated. /// \param payload is the specific \e injection payload /// \param icontext is the specific context for the injection /// \param op is the given p-code op being replaced by the payload /// \param fc (if non-NULL) is information about the call site being in-lined void FlowInfo::doInjection(InjectPayload *payload,InjectContext &icontext,PcodeOp *op,FuncCallSpecs *fc) { // Create marker at current end of the deadlist list::const_iterator iter = obank.endDead(); --iter; // There must be at least one op payload->inject(icontext,emitter); // Do the injection bool startbasic = op->isBlockStart(); ++iter; // Now points to first op in the injection PcodeOp *firstop = *iter; bool isfallthru = true; PcodeOp *lastop = xrefControlFlow(iter,startbasic,isfallthru,fc); if (startbasic) { // If the inject code does NOT fall thru iter = op->getInsertIter(); ++iter; // Mark next op after the call if (iter != obank.endDead()) data.opMarkStartBasic(*iter); // as start of basic block } if (payload->isIncidentalCopy()) obank.markIncidentalCopy(firstop, lastop); obank.moveSequenceDead(firstop,lastop,op); // Move the injection to right after the call map::iterator viter = visited.find(op->getAddr()); if (viter != visited.end()) { // Check if -op- is a possible branch target if ((*viter).second.seqnum == op->getSeqNum()) // (if injection op is the first op for its address) (*viter).second.seqnum = firstop->getSeqNum(); // change the seqnum to the first injected op } // Get rid of the original call data.opDestroyRaw(op); } /// The op must already be established as a user defined op with an associated injection /// \param op is the given PcodeOp void FlowInfo::injectUserOp(PcodeOp *op) { InjectedUserOp *userop = (InjectedUserOp *)glb->userops.getOp((int4)op->getIn(0)->getOffset()); InjectPayload *payload = glb->pcodeinjectlib->getPayload(userop->getInjectId()); InjectContext &icontext(glb->pcodeinjectlib->getCachedContext()); icontext.clear(); icontext.baseaddr = op->getAddr(); icontext.nextaddr = icontext.baseaddr; for(int4 i=1;inumInput();++i) { // Skip the first operand containing the injectid Varnode *vn = op->getIn(i); icontext.inputlist.emplace_back(); icontext.inputlist.back().space = vn->getSpace(); icontext.inputlist.back().offset = vn->getOffset(); icontext.inputlist.back().size = vn->getSize(); } Varnode *outvn = op->getOut(); if (outvn != (Varnode *)0) { icontext.output.emplace_back(); icontext.output.back().space = outvn->getSpace(); icontext.output.back().offset = outvn->getOffset(); icontext.output.back().size = outvn->getSize(); } doInjection(payload,icontext,op,(FuncCallSpecs *)0); } /// P-code is generated for the sub-function and then woven into \b this flow /// at the call site. /// \param fc is the given call site /// \return \b true if the in-lining is successful bool FlowInfo::inlineSubFunction(FuncCallSpecs *fc) { Funcdata *fd = fc->getFuncdata(); if (fd == (Funcdata *)0) return false; PcodeOp *op = fc->getOp(); Address retaddr; if (!data.inlineFlow( fd, *this, op)) return false; // Changing CALL to JUMP may make some original code unreachable setPossibleUnreachable(); return true; } /// The call site must be previously marked with the \e injection id. /// The PcodeInjectLibrary is queried for the associated payload, which is /// then inserted into \b this flow, replacing the original CALL op. /// \param fc is the given call site /// \return \b true if the injection was successfully performed bool FlowInfo::injectSubFunction(FuncCallSpecs *fc) { PcodeOp *op = fc->getOp(); // Inject to end of the deadlist InjectContext &icontext(glb->pcodeinjectlib->getCachedContext()); icontext.clear(); icontext.baseaddr = op->getAddr(); icontext.nextaddr = icontext.baseaddr; icontext.calladdr = fc->getEntryAddress(); InjectPayload *payload = glb->pcodeinjectlib->getPayload(fc->getInjectId()); doInjection(payload,icontext,op,fc); // If the injection fills in the -paramshift- field of the context // pass this information on to the callspec of the injected call, which must be last in the list if (payload->getParamShift() != 0) qlst.back()->setParamshift(payload->getParamShift()); return true; // Return true to indicate injection happened and callspec should be deleted } /// \param fc is the given call site (which is freed by this method) void FlowInfo::deleteCallSpec(FuncCallSpecs *fc) { int4 i; for(i=0;iinsert(data.getAddress()); // Insert ourselves // inline_head = (Funcdata *)0; } else { inline_recursion->insert(data.getAddress()); // Insert ourselves } for(int4 i=0;icode() == CPUI_CALLOTHER) { injectUserOp(op); } else { // CPUI_CALL or CPUI_CALLIND FuncCallSpecs *fc = FuncCallSpecs::getFspecFromConst(op->getIn(0)->getAddr()); if (fc->isInline()) { if (fc->getInjectId() >= 0) { if (injectSubFunction(fc)) { data.warningHeader("Function: "+fc->getName()+" replaced with injection: "+ glb->pcodeinjectlib->getCallFixupName(fc->getInjectId())); deleteCallSpec(fc); } } else if (inlineSubFunction(fc)) { data.warningHeader("Inlined function: "+fc->getName()); deleteCallSpec(fc); } } } } injectlist.clear(); } /// \brief Check if any of the calls this function makes are to already traced data-flow. /// /// If so, we change the CALL to a BRANCH and issue a warning. /// This situation is most likely due to a Position Indepent Code construction. void FlowInfo::checkContainedCall(void) { vector::iterator iter; for(iter=qlst.begin();iter!=qlst.end();++iter) { FuncCallSpecs *fc = *iter; Funcdata *fd = fc->getFuncdata(); if (fd != (Funcdata *)0) continue; PcodeOp *op = fc->getOp(); if (op->code() != CPUI_CALL) continue; const Address &addr( fc->getEntryAddress() ); map::const_iterator miter; miter = visited.upper_bound(addr); if (miter == visited.begin()) continue; --miter; if ((*miter).first + (*miter).second.size <= addr) continue; if ((*miter).first == addr) { ostringstream s; s << "Possible PIC construction at "; op->getAddr().printRaw(s); s << ": Changing call to branch"; data.warningHeader(s.str()); data.opSetOpcode(op,CPUI_BRANCH); // Make sure target of new goto starts a basic block PcodeOp *targ = target(addr); data.opMarkStartBasic(targ); // Make sure the following op starts a basic block list::const_iterator oiter = op->getInsertIter(); ++oiter; if (oiter != obank.endDead()) data.opMarkStartBasic(*oiter); // Restore original address data.opSetInput(op,data.newCodeRef(addr),0); iter = qlst.erase(iter); // Delete the call delete fc; if (iter == qlst.end()) break; } else { data.warning("Call to offcut address within same function",op->getAddr()); } } } /// \brief Look for changes in control-flow near indirect jumps that were discovered \e after the jumptable recovery void FlowInfo::checkMultistageJumptables(void) { int4 num = data.numJumpTables(); for(int4 i=0;icheckForMultistage(&data)) tablelist.push_back(jt->getIndirectOp()); } }