ROSE  0.11.23.0
Partitioner.h
1 #ifndef ROSE_Partitioner2_Partitioner_H
2 #define ROSE_Partitioner2_Partitioner_H
3 
4 #include <featureTests.h>
5 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
6 
7 #include <Partitioner2/AddressUsageMap.h>
8 #include <Partitioner2/BasicBlock.h>
9 #include <Partitioner2/BasicTypes.h>
10 #include <Partitioner2/Config.h>
11 #include <Partitioner2/ControlFlowGraph.h>
12 #include <Partitioner2/DataBlock.h>
13 #include <Partitioner2/Function.h>
14 #include <Partitioner2/FunctionCallGraph.h>
15 #include <Partitioner2/InstructionProvider.h>
16 #include <Partitioner2/Modules.h>
17 #include <Partitioner2/Reference.h>
18 
19 #include <Sawyer/Attribute.h>
20 #include <Sawyer/Callbacks.h>
21 #include <Sawyer/IntervalSet.h>
22 #include <Sawyer/Map.h>
23 #include <Sawyer/Message.h>
24 #include <Sawyer/Optional.h>
25 #include <Sawyer/ProgressBar.h>
26 #include <Sawyer/SharedPointer.h>
27 
28 #include <BinarySourceLocations.h>
29 #include <BinaryUnparser.h>
30 #include <Progress.h>
31 
32 #include <boost/filesystem.hpp>
33 #include <boost/move/utility_core.hpp>
34 #include <boost/serialization/access.hpp>
35 #include <boost/serialization/split_member.hpp>
36 #include <boost/serialization/version.hpp>
37 
38 #include <ostream>
39 #include <set>
40 #include <string>
41 #include <vector>
42 
43 // Derived classes needed for serialization
44 #include <BinaryYicesSolver.h>
45 #include <BinaryZ3Solver.h>
46 #include <DispatcherAarch64.h>
47 #include <DispatcherM68k.h>
48 #include <DispatcherPowerpc.h>
49 #include <DispatcherX86.h>
50 
51 // Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
52 //
53 // prototype for
54 // 'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
55 // does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
56 //
57 // followed by saying that the exact same signature is one of the candidates:
58 //
59 // candidates are:
60 // Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
61 //
62 // This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0.
63 #if __cplusplus >= 201103L
64  #define ROSE_PARTITIONER_MOVE
65 #elif defined(__GNUC__)
66  #if __GNUC__ > 5
67  #define ROSE_PARTITIONER_MOVE
68  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
69  #define ROSE_PARTITIONER_MOVE
70  #endif
71 #endif
72 
73 namespace Rose {
74 namespace BinaryAnalysis {
75 
107 namespace Partitioner2 {
108 
322 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
323 #ifdef ROSE_PARTITIONER_MOVE
324  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
325 #endif
326 
327 public:
330  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
331  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
334  struct Thunk {
336  rose_addr_t target;
337  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
338  };
339 
342 
343 private:
344  BasePartitionerSettings settings_; // settings adjustable from the command-line
345  Configuration config_; // configuration information about functions, blocks, etc.
346  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
347  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
348  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
349  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
350  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
351  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
352  Functions functions_; // List of all attached functions by entry address
353  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
354  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
355  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
356  AddressNameMap addressNames_; // Names for various addresses
357  SourceLocations sourceLocations_; // Mapping between source locations and addresses
358  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
359  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
360  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
361  Unparser::BasePtr insnPlainUnparser_; // For unparsing just instruction mnemonic and operands
362 
363  // Callback lists
364  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
365  BasicBlockCallbacks basicBlockCallbacks_;
366  FunctionPrologueMatchers functionPrologueMatchers_;
367  FunctionPaddingMatchers functionPaddingMatchers_;
368 
369  // Special CFG vertices.
370  ControlFlowGraph::VertexIterator undiscoveredVertex_;
371  ControlFlowGraph::VertexIterator indeterminateVertex_;
372  ControlFlowGraph::VertexIterator nonexistingVertex_;
373  static const size_t nSpecialVertices = 3;
374 
375  // Optional cached information
376  Sawyer::Optional<rose_addr_t> elfGotVa_; // address of ELF GOT, set by findElfGotVa
377 
378  // Protects the following data members
379  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
380  Progress::Ptr progress_; // Progress reporter to update, or null
381  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
382 
383 
384 
387  //
388  // Serialization
389  //
392 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
393 private:
394  friend class boost::serialization::access;
395 
396  template<class S>
397  void serializeCommon(S &s, const unsigned version) {
398  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
399  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
400 #ifdef ROSE_ENABLE_ASM_AARCH64
401  s.template register_type<InstructionSemantics2::DispatcherAarch64>();
402 #endif
403  s.template register_type<InstructionSemantics2::DispatcherX86>();
404  s.template register_type<InstructionSemantics2::DispatcherM68k>();
405  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
406  s.template register_type<SymbolicExpr::Interior>();
407  s.template register_type<SymbolicExpr::Leaf>();
408  s.template register_type<YicesSolver>();
409  s.template register_type<Z3Solver>();
410  s.template register_type<Semantics::SValue>();
411  s.template register_type<Semantics::MemoryListState>();
412  s.template register_type<Semantics::MemoryMapState>();
413  s.template register_type<Semantics::RegisterState>();
414  s.template register_type<Semantics::State>();
415  s.template register_type<Semantics::RiscOperators>();
416  s & BOOST_SERIALIZATION_NVP(settings_);
417  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
418  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
419  s & BOOST_SERIALIZATION_NVP(memoryMap_);
420  s & BOOST_SERIALIZATION_NVP(cfg_);
421  // s & vertexIndex_; -- initialized by rebuildVertexIndices
422  s & BOOST_SERIALIZATION_NVP(aum_);
423  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
424  s & BOOST_SERIALIZATION_NVP(functions_);
425  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
426  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
427  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
428  s & BOOST_SERIALIZATION_NVP(addressNames_);
429  if (version >= 1)
430  s & BOOST_SERIALIZATION_NVP(sourceLocations_);
431  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
432  // s & unparser_; -- not saved; restored from disassembler
433  // s & cfgAdjustmentCallbacks_; -- not saved/restored
434  // s & basicBlockCallbacks_; -- not saved/restored
435  // s & functionPrologueMatchers_; -- not saved/restored
436  // s & functionPaddingMatchers_; -- not saved/restored
437  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
438  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
439  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
440  if (version >= 2)
441  s & BOOST_SERIALIZATION_NVP(elfGotVa_);
442  // s & progress_; -- not saved/restored
443  // s & cfgProgressTotal_; -- not saved/restored
444  }
445 
446  template<class S>
447  void save(S &s, const unsigned version) const {
448  const_cast<Partitioner*>(this)->serializeCommon(s, version);
449  }
450 
451  template<class S>
452  void load(S &s, const unsigned version) {
453  serializeCommon(s, version);
454  rebuildVertexIndices();
455  }
456 
457  BOOST_SERIALIZATION_SPLIT_MEMBER();
458 #endif
459 
460 
461 
464  //
465  // Constructors
466  //
469 public:
474  Partitioner();
475 
480  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
481 
482 #ifdef ROSE_PARTITIONER_MOVE
483 
484  Partitioner(BOOST_RV_REF(Partitioner));
485 
487  Partitioner& operator=(BOOST_RV_REF(Partitioner));
488 #else
489  // These are unsafe
490  Partitioner(const Partitioner&);
491  Partitioner& operator=(const Partitioner&);
492 #endif
493 
494  ~Partitioner();
495 
502  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
503 
505  void clear() /*final*/;
506 
514  Configuration& configuration() { return config_; }
515  const Configuration& configuration() const { return config_; }
523  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
524  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
536  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
542  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
543  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
544  }
545 
548  //
549  // Unparsing
550  //
553 
563  Unparser::BasePtr unparser() const /*final*/;
564  void unparser(const Unparser::BasePtr&) /*final*/;
576  Unparser::BasePtr insnUnparser() const /*final*/;
577  void insnUnparser(const Unparser::BasePtr&) /*final*/;
581  void configureInsnUnparser(const Unparser::BasePtr&) const /*final*/;
582 
586  void configureInsnPlainUnparser(const Unparser::BasePtr&) const /*final*/;
587 
596  std::string unparse(SgAsmInstruction*) const;
597  void unparse(std::ostream&, SgAsmInstruction*) const;
598  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
599  void unparse(std::ostream&, const DataBlock::Ptr&) const;
600  void unparse(std::ostream&, const Function::Ptr&) const;
601  void unparse(std::ostream&) const;
607  std::string unparsePlain(SgAsmInstruction*) const;
608 
611  //
612  // Partitioner CFG queries
613  //
616 public:
622  size_t nBytes() const /*final*/ { return aum_.size(); }
623 
631  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
632  return undiscoveredVertex_;
633  }
634  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
635  return undiscoveredVertex_;
636  }
649  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
650  return indeterminateVertex_;
651  }
652  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
653  return indeterminateVertex_;
654  }
666  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
667  return nonexistingVertex_;
668  }
669  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
670  return nonexistingVertex_;
671  }
680  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
681 
688  const AddressUsageMap& aum() const /*final*/ { return aum_; }
689 
691  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
692 
697  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
698 
706  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
707 
736  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
737  const Function::Ptr &function = Function::Ptr()) const /*final*/;
738  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
739  const Function::Ptr &function = Function::Ptr()) const /*final*/;
776  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
777  const Function::Ptr &sourceFunction = Function::Ptr(),
778  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
779  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
780  const Function::Ptr &sourceFunction = Function::Ptr(),
781  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
786  //
789  // Partitioner instruction operations
790  //
793 public:
799  size_t nInstructions() const /*final*/;
800 
810  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
811  return aum_.findInstruction(startVa);
812  }
814  return aum_.findInstruction(insn);
815  }
824  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
825 
834  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
835 
844  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
845 
855  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
856 
864  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
865 
878  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
879 
884  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
885 
886 
887 
890  //
891  // Partitioner basic block placeholder operations
892  //
895 public:
905  size_t nPlaceholders() const /*final*/;
906 
915  bool placeholderExists(rose_addr_t startVa) const /*final*/;
916 
927  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
928  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
929  return *found;
930  return cfg_.vertices().end();
931  }
932  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
933  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
934  return *found;
935  return cfg_.vertices().end();
936  }
955  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
956 
970  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
971  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
976  //
979  // Partitioner basic block operations
980  //
983 public:
997  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
1009  void basicBlockDropSemantics() const /*final*/;
1010 
1019  size_t nBasicBlocks() const /*final*/;
1020 
1028  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
1029 
1051  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1052  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1064  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1065 
1076  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1077 
1087  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1088 
1095  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1096 
1106  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1107 
1113  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1114 
1139  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1140  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1141  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1156  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1157  SgAsmInstruction *insn) /*final*/;
1158 
1191  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1192  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1280  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1281  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1298  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1299  Precision::Level precision = Precision::HIGH) const /*final*/;
1300 
1309  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1310 
1329  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1330 
1340  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1341 
1352  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1353 
1358  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1359 
1399  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1400  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1411  void forgetStackDeltas() const /*final*/;
1412  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1424  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1425  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1478  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1479 
1480  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1489  void basicBlockMayReturnReset() const /*final*/;
1490 
1491 private:
1492  // Per-vertex data used during may-return analysis
1493  struct MayReturnVertexInfo {
1494  enum State {INIT, CALCULATING, FINISHED};
1495  State state; // current state of vertex
1496  bool processedCallees; // have we processed BBs this vertex calls?
1497  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1498  boost::logic::tribool result; // final result (eventually cached in BB)
1499  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1500  };
1501 
1502  // Is edge significant for analysis? See .C file for full documentation.
1503  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1504  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1505 
1506  // Determine (and cache in vertexInfo) whether any callees return.
1507  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1508  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1509 
1510  // Maximum may-return result from significant successors including phantom call-return edge.
1511  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1512  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1513 
1514  // The guts of the may-return analysis
1515  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1516  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1517 
1518 
1519 
1522  //
1523  // Partitioner data block operations
1524  //
1527 public:
1533  size_t nDataBlocks() const /*final*/;
1534 
1541  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1542 
1551  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1552 
1564  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1565 
1572  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1573 
1583  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1584 
1597  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1598 
1608  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1609 
1619  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1620 
1630  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1631 
1638  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1639 
1645  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1646 
1647 
1648 
1651  //
1652  // Partitioner function operations
1653  //
1656 public:
1662  size_t nFunctions() const /*final*/ { return functions_.size(); }
1663 
1682  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1683  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1684  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1692  std::vector<Function::Ptr> functions() const /*final*/;
1693 
1703  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1704 
1715  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1716 
1726  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1727 
1744  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1745  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1746  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1747  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1748  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1749  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1771  size_t attachFunction(const Function::Ptr&) /*final*/;
1772  size_t attachFunctions(const Functions&) /*final*/;
1788  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1789 
1806  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1807  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1823  void detachFunction(const Function::Ptr&) /*final*/;
1824 
1859  std::vector<Function::Ptr>
1860  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1861 
1862  std::vector<Function::Ptr>
1863  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1864 
1865  std::vector<Function::Ptr>
1866  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1867 
1868  std::vector<Function::Ptr>
1869  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1870 
1871  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1872  std::vector<Function::Ptr>
1873  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1874  std::vector<Function::Ptr> retval;
1875  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1876  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1877  insertUnique(retval, function, sortFunctionsByAddress);
1878  }
1879  return retval;
1880  }
1892  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1893 
1905  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1906 
1916  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1917 
1928  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1929 
1936  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1937 
1945  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1946 
1966  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1967 
1971  void allFunctionStackDelta() const /*final*/;
1972 
1979  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1980 
1984  void allFunctionMayReturn() const /*final*/;
1985 
2012  const CallingConvention::Analysis&
2013  functionCallingConvention(const Function::Ptr&,
2014  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2015  const /*final*/;
2016 
2029  void
2030  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2031  const /*final*/;
2032 
2058  CallingConvention::Dictionary
2059  functionCallingConventionDefinitions(const Function::Ptr&,
2060  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2061  const /*final*/;
2062 
2075  void
2076  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2077  CallingConvention::Definition::Ptr()) const /*final*/;
2078 
2087  void fixInterFunctionEdges() /*final*/;
2088  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2108  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2109 
2115  void allFunctionIsNoop() const /*final*/;
2116 
2124  void forgetFunctionIsNoop() const /*final*/;
2125  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2132  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2133 
2134 
2135 
2138  //
2139  // Callbacks
2140  //
2143 public:
2161  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2162  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2173  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2174  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2177 public:
2185  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2186  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2213  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2214  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/) /*final*/;
2217 public:
2223  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2224  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2234  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2235 
2236 
2237 
2240  //
2241  // Partitioner miscellaneous
2242  //
2245 public:
2257  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2258  bool computeProperties=true) const /*final*/;
2259 
2273  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2274  bool showNeighbors=true) const /*final*/;
2275 
2281  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2282  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2288  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2289 
2295  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2296  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2304  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2305  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2313  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2314  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2320  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2321 
2325  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2326 
2330  static std::string functionName(const Function::Ptr&) /*final*/;
2331 
2336  void expandIndeterminateCalls();
2337 
2355  Progress::Ptr progress() const /*final*/;
2356  void progress(const Progress::Ptr&) /*final*/;
2363  void updateProgress(const std::string &phase, double completion) const;
2364 
2366  void showStatistics() const;
2367 
2368  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2369  void checkConsistency() const;
2370 
2377 
2381  Sawyer::Optional<rose_addr_t> elfGotVa() const;
2382 
2383 
2384 
2387  //
2388  // Settings
2389  //
2392 public:
2393 
2401  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2402  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2413  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2414  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2415  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2439  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2440  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2457  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2458  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2470  void addressName(rose_addr_t, const std::string&) /*final*/;
2471  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2472  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2480  const SourceLocations& sourceLocations() const /*final*/ { return sourceLocations_; }
2481  SourceLocations& sourceLocations() /*final*/ { return sourceLocations_; }
2482  void sourceLocations(const SourceLocations &locs) { sourceLocations_ = locs; }
2492  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2493  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2498  //
2501  // Instruction semantics
2502  //
2505 public:
2515  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2516  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2525  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2526 
2537  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2538  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2548  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2549 
2550 
2551 
2554  //
2555  // Python API support functions
2556  //
2559 #ifdef ROSE_ENABLE_PYTHON_API
2560  void pythonUnparse() const;
2561 #endif
2562 
2563 
2564 
2567  //
2568  // Partitioner internal utilities
2569  //
2572 private:
2573  void init(Disassembler*, const MemoryMap::Ptr&);
2574  void init(const Partitioner&);
2575  void updateCfgProgress();
2576 
2577 private:
2578  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2579  // and destination CFGs are identical.
2580  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2581  ControlFlowGraph::ConstVertexIterator otherIter);
2582 
2583  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2584  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2585  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2586 
2587  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2588  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2589  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2590 
2591  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2592  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2593 
2594  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2595  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2596  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2597 
2598  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2599  // The call happens immediately after the CFG/AUM are updated.
2600  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2601 
2602  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2603  void rebuildVertexIndices();
2604 };
2605 
2606 } // namespace
2607 } // namespace
2608 } // namespace
2609 
2610 // Class versions must be at global scope
2611 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::Partitioner, 2);
2612 
2613 #endif
2614 #endif
Represents information about a thunk.
Definition: Partitioner.h:334
size_t size() const
Number of addresses represented by the map.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:329
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2186
Contiguous region of a file.
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2525
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:335
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2185
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2471
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2414
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2493
Represents the file header of an ELF binary container.
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:652
const SourceLocations & sourceLocations() const
Property: Source locations.
Definition: Partitioner.h:2480
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:515
Base class for machine instructions.
Bidirectional mapping between addresses and source locations.
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2224
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:813
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:680
Provides and caches instructions.
Settings that directly control a partitioner.
Definition: BasicTypes.h:313
STL namespace.
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:649
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:523
void sourceLocations(const SourceLocations &locs)
Property: Source locations.
Definition: Partitioner.h:2482
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1442
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:341
A container holding a set of values.
Definition: IntervalSet.h:55
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2173
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:631
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2515
Name space for the entire library.
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:514
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2458
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:932
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:688
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2472
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:434
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2402
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2457
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:336
ControlFlowGraph::VertexIterator nonexistingVertex()
Returns the special "non-existing" vertex.
Definition: Partitioner.h:666
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:502
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2415
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:85
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2174
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:998
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:577
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1425
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:524
bool checkingCallBranch
Check for situations where CALL is used as a branch.
Definition: BasicTypes.h:318
bool usingSemantics
Whether instruction semantics are used.
Definition: BasicTypes.h:314
A general, thread-safe way to report progress made on some task.
Definition: Progress.h:165
void autoAddCallReturnEdges(bool b)
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2439
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:997
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
Definition: BasicTypes.h:319
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:634
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:669
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:330
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2223
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2162
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:536
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:322
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2492
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:542
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:50
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:386
void enableSymbolicSemantics(bool b=true)
Use or not use symbolic semantics.
Definition: Partitioner.h:2413
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2440
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:328
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:331
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2516
Holds configuration information.
Definition: Config.h:282
SourceLocations & sourceLocations()
Property: Source locations.
Definition: Partitioner.h:2481